On the Intrinsic Limits of Transformer Image Embeddings in Non-Solvable Spatial Reasoning
For researchers in computer vision and AI, this work provides a theoretical explanation for ViTs' failure in spatial reasoning, grounded in circuit complexity, rather than data scale.
The paper identifies a fundamental computational bottleneck in Vision Transformers for non-solvable spatial reasoning tasks (e.g., mental rotation), formalized as a Group Homomorphism Problem. It proves that constant-depth ViTs with polynomial precision are limited to complexity class TC^0, which is strictly weaker than NC^1 required for such tasks, and empirically validates this gap via the Latent Space Algebra benchmark showing performance degradation with task depth.
Vision Transformers (ViTs) excel in semantic recognition but exhibit systematic failures in spatial reasoning tasks such as mental rotation. While often attributed to data scale, this work argues that the limitation arises from the intrinsic circuit complexity of the architecture. By formalizing spatial understanding as learning a Group Homomorphism Problem -- where latent embeddings preserve the algebraic structure of physical transformations acting on images -- we identify a fundamental computational bottleneck. Specifically, for non-solvable groups (e.g., $\mathrm{SO}(3)$), maintaining such structure-preserving embeddings is lowerbounded by the Word Problem, which is $\mathsf{NC^1}$-complete. In contrast, constant-depth ViTs with polynomial precision are strictly bounded by the complexity class $\mathsf{TC^0}$. Under the standard conjecture $\mathsf{TC^0} \subsetneq \mathsf{NC^1}$, a complexity boundary emerges: constant-depth architectures lack the logical depth required to capture non-solvable spatial structures in a single forward pass. To empirically validate this theoretical gap, we propose the Latent Space Algebra (LSA) benchmark, which reveals a significant degradation in ViT representations as the compositional depth of non-solvable tasks increases.