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

📄 arXiv: 2601.03048v1 📥 PDF

作者: Siyi Lyu, Quan Liu, Feng Yan

分类: cs.CV, cs.AI, cs.CC

发布日期: 2026-01-06

💡 一句话要点

揭示Transformer图像嵌入在非可解空间推理中的内在局限性

🎯 匹配领域: 支柱五：交互与反应 (Interaction & Reaction)

关键词: Vision Transformer 空间推理 群同态 计算复杂性 非可解群

📋 核心要点

  1. ViT在空间推理任务中存在局限性，并非单纯由数据规模决定，而是源于其内在的架构复杂性。
  2. 论文将空间理解形式化为学习群同态，并分析了ViT在处理非可解群时的计算复杂性下界。
  3. 通过潜在空间探测，验证了ViT在处理非可解任务时，随着网络深度的增加，表示会发生结构性崩溃。

📝 摘要（中文）

Vision Transformer (ViT) 在语义识别方面表现出色，但在空间推理任务（如心理旋转）中表现出系统性失败。虽然通常归因于数据规模，但我们认为这种限制源于架构的内在电路复杂性。我们将空间理解形式化为学习群同态：将图像序列映射到保留底层变换群代数结构的潜在空间。我们证明，对于非可解群（例如，3D旋转群 $\mathrm{SO}(3)$），维持这种保持结构的嵌入在计算上受到 Word Problem 的下界约束，该问题是 $\mathsf{NC^1}$-complete。相反，我们证明具有多项式精度的常数深度 ViT 严格受 $\mathsf{TC^0}$ 约束。在猜想 $\mathsf{TC^0} \subsetneq \mathsf{NC^1}$ 下，我们建立了一个复杂性边界：常数深度 ViT 从根本上缺乏有效捕获非可解空间结构的逻辑深度。我们通过潜在空间探测验证了这种复杂性差距，表明 ViT 表示在非可解任务中随着组合深度的增加而遭受结构崩溃。

🔬 方法详解

问题定义：ViT在空间推理任务，特别是涉及非可解群（如SO(3)旋转）的任务中表现不佳。现有的解释通常归因于数据规模不足，但论文认为根本原因是ViT架构的内在计算复杂性不足以捕捉复杂的空间关系。现有方法缺乏对ViT架构本身局限性的理论分析。

核心思路：论文的核心思路是将空间理解问题形式化为学习群同态，即学习一个从图像序列到潜在空间的映射，该映射能够保持底层变换群的代数结构。对于非可解群，维持这种结构保持的嵌入在计算上是困难的，需要更高的电路复杂性。ViT的架构复杂性不足以有效学习这种映射，导致其在非可解空间推理任务中表现不佳。

技术框架：论文主要通过理论分析和实验验证来支持其观点。理论分析部分，论文将空间理解问题与Word Problem联系起来，证明了对于非可解群，学习结构保持的嵌入需要$\mathsf{NC^1}$-complete的计算复杂性。同时，论文证明了常数深度ViT的计算能力受限于$\mathsf{TC^0}$。实验部分，论文通过潜在空间探测，观察ViT在处理非可解任务时，随着网络深度的增加，表示是否会发生结构性崩溃。

关键创新：论文最重要的技术创新点在于将空间理解问题与计算复杂性理论联系起来，揭示了ViT架构在处理非可解空间推理任务时的内在局限性。与现有方法不同，论文不是简单地通过增加数据规模或修改网络结构来提升性能，而是从理论层面分析了ViT架构的根本瓶颈。

关键设计：论文的关键设计包括：1) 将空间理解形式化为学习群同态；2) 将学习群同态问题与Word Problem联系起来，从而分析计算复杂性；3) 通过潜在空间探测来验证理论分析的结果。论文并没有提出新的网络结构或损失函数，而是侧重于理论分析和实验验证。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

论文通过实验验证了ViT在处理非可解空间推理任务时，随着网络深度的增加，表示会发生结构性崩溃。这表明ViT无法有效地学习非可解群的结构保持嵌入。实验结果与理论分析相符，进一步支持了论文的观点，即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.