arXiv:2607.22361cs.LGcs.AI2026-07

通过索引任务揭示深度模型的瓶颈,证明不同架构在位置敏感性上的本质差异。

Indexing: the Beginning and the End

  • 用索引任务分析模型信息瓶颈,定义因果复杂度衡量能力上限。
  • 索引在末尾时,小规模RNN/SSM/掩码线性注意力无法常数层解决,但软标签变换器可单层完成。
  • 索引在开头时,小RNN仅需1层,其余需2层;理论与实验一致,验证模型局限性。

本文通过索引原语研究现代深度学习架构(RNN、softmax Transformer、线性注意力Transformer、状态空间模型)中的信息瓶颈。该原语输入为n位数据和一个1到n的索引i,输出为第i位的值。引入掩码架构的因果复杂度概念,证明因果复杂度低的模型在索引位于输入末尾时,无法在常数层数内解决该任务。这适用于参数少的RNN、SSM和掩码线性注意力Transformer。相反,小型softmax Transformer可在1层内解决,非掩码线性注意力则需2层,二者因此区别显著。当索引位于开头时,小型RNN可在1层完成,其余架构需2层。所有不可能性结果均为无条件成立,即使使用无限精度实数运算也适用。实验显示,n=64以内,理论上可解的配置易学习,而不可解的配置随序列长度增长学习困难,与理论预测一致。

原文摘要 · Abstract (English)

We study information bottlenecks in modern deep-learning architectures -- RNNs, softmax transformers, linear-attention transformers and state-space models -- through the lens of the indexing primitive. In this primitive, the input consists of $n$ bits and one integer $i$ from $1$ to $n$ called the index, and the output equals the value of the $i$-th bit. We introduce causal complexity for masked architectures. We show that architectures with low causal complexity cannot solve the indexing primitive in any constant number of layers when the index appears at the end of the input. In particular, this limitation applies to low-parameter RNNs, SSMs and masked linear-attention transformers. In contrast, small softmax transformers can solve it in one layer, while non-masked linear-attention transformers can solve it in 2, which separates them from their masked counterparts. In turn, when the index appears at the beginning, we show that small RNNs are capable of solving this task in 1 layer, while all the other architectures require 2. All our impossibility results are unconditional and apply even to models that employ infinite-precision real arithmetic. Moreover, experiments for up to $n=64$ qualitatively align with our theory: configurations with low-parameter theoretical solutions learn the indexing task easily, while configurations that do not admit such theoretical solutions struggle to learn as the sequence length grows.

信息瓶颈TransformerRNN理论分析

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。