비가역적 공간 추론에서 트랜스포머 이미지 임베딩의 고유한 한계에 대하여

On the Intrinsic Limits of Transformer Image Embeddings in Non-Solvable Spatial Reasoning

비전 트랜스포머(ViT)는 의미 인식에서는 뛰어난 성능을 보이지만, 정신 회전과 같은 공간 추론 작업에서는 체계적인 오류를 나타냅니다. 이러한 한계는 종종 데이터 규모 문제로 설명되지만, 본 연구에서는 이 한계가 아키텍처 자체의 고유한 회로 복잡성에서 비롯된다고 제안합니다. 우리는 공간 이해를, 기본 변환 그룹의 대수적 구조를 보존하는 잠재 공간으로 이미지 시퀀스를 매핑하는 그룹 동형 사상 학습으로 공식화합니다. 비가역적 그룹(예: 3차원 회전 그룹 $\mathrm{SO}(3)$)의 경우, 이러한 구조를 보존하는 임베딩을 유지하는 것은 계산적으로 '워드 문제'로 인해 하한이 제한되며, 이는 $\mathsf{NC^1}$-완전입니다. 반대로, 우리는 다항 정밀도를 갖는 일정한 깊이의 ViT는 $\mathsf{TC^0}$으로 엄격하게 제한됨을 증명합니다. $\mathsf{TC^0} \subsetneq \mathsf{NC^1}$이라는 가설 하에, 우리는 복잡성 경계를 설정합니다. 즉, 일정한 깊이의 ViT는 기본적으로 비가역적인 공간 구조를 효율적으로 포착할 수 있는 충분한 논리적 깊이가 부족합니다. 우리는 잠재 공간 탐색을 통해 이 복잡성 차이를 검증하고, ViT 표현이 합성 깊이가 증가함에 따라 비가역적인 작업에서 구조적 붕괴를 겪는다는 것을 보여줍니다.

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, we propose that this limitation arises from the intrinsic circuit complexity of the architecture. We formalize spatial understanding as learning a Group Homomorphism: mapping image sequences to a latent space that preserves the algebraic structure of the underlying transformation group. We demonstrate that for non-solvable groups (e.g., the 3D rotation group $\mathrm{SO}(3)$), maintaining such a structure-preserving embedding is computationally lower-bounded by the Word Problem, which is $\mathsf{NC^1}$-complete. In contrast, we prove that constant-depth ViTs with polynomial precision are strictly bounded by $\mathsf{TC^0}$. Under the conjecture $\mathsf{TC^0} \subsetneq \mathsf{NC^1}$, we establish a complexity boundary: constant-depth ViTs fundamentally lack the logical depth to efficiently capture non-solvable spatial structures. We validate this complexity gap via latent-space probing, demonstrating that ViT representations suffer a structural collapse on non-solvable tasks as compositional depth increases.