索引：开始和结束

我们通过索引基元的视角研究现代深度学习架构中的信息瓶颈——RNN、softmax Transformer、线性注意力 Transformer 和状态空间模型。在此原语中，输入由 $n$ 位和一个从 $1$ 到 $n$ 的整数 $i$（称为索引）组成，输出等于第 $i$ 位的值。我们引入了屏蔽架构的因果复杂性。我们表明，当索引出现在输入末尾时，因果复杂度较低的架构无法解决任何恒定层数中的索引原语。特别是，此限制适用于低参数 RNN、SSM 和屏蔽线性注意力 Transformer。相比之下，小型 softmax Transformer 可以在一层中解决它，而非屏蔽线性注意力 Transformer 可以在 2 层中解决它，这将它们与屏蔽对应层分开。反过来，当索引出现在开头时，我们表明小型 RNN 能够在 1 层中解决此任务，而所有其他架构都需要 2 层。我们所有的不可能性结果都是无条件的，甚至适用于采用无限精度实数算术的模型。此外，高达 $n=64$ 的实验在质量上与我们的理论一致：具有低参数理论解决方案的配置可以轻松学习索引任务，而不允许此类理论解决方案的配置随着序列长度的增长而难以学习。