Transformer图像嵌入在复杂空间推理上存在理论极限，难以捕捉非可解群结构。
On the Intrinsic Limits of Transformer Image Embeddings in Non-Solvable Spatial Reasoning
- 将空间理解建模为保持物理变换代数结构的同态问题
- 证明常深ViT受限于TC^0复杂度类，无法处理SO(3)等非可解群任务
- 提出LSA基准，实证显示组合深度增加时嵌入性能显著下降
视觉变压器（ViTs）在语义识别上表现优异，但在心理旋转等空间推理任务中存在系统性失败。本文认为，这一限制源于架构的内在电路复杂度，而非数据规模。通过将空间理解形式化为学习一个群同态问题——即隐空间嵌入需保持作用于图像的物理变换的代数结构——我们发现：对于非可解群（如$ m SO(3)$），维持结构保持嵌入的计算下限由字问题（Word Problem）决定，其复杂度为$ m NC^1$-完全。而具有多项式精度的常深ViT严格受限于$ m TC^0$复杂度类。在标准假设$ m TC^0 ot= NC^1$下，常深架构缺乏单次前向传播中捕获非可解空间结构所需的逻辑深度。为验证此理论差距，我们提出了潜空间代数（LSA）基准，结果表明随着非可解任务组合深度增加，ViT表示性能显著退化。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。