🤖 machine learning

Indexing: the Beginning and the End

本文引入了因果复杂度（causal complexity）的概念，旨在证明像 RNN 和线性注意力 Transformer 这种掩码深度学习架构，在索引原语（indexing primitive）出现在输入末尾时存在本质上的局限性，而 Softmax 注意力和非掩码线性注意力 Transformer 则能高效地解决该问题，这一理论上的差异通过经验实验得到了证实。

原作者： Alexander Kozachinskiy, Vicente Opazo, Felipe Urrutia

发布于 2026-07-27

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Alexander Kozachinskiy, Vicente Opazo, Felipe Urrutia

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图制造一个超级聪明的机器人，它能够阅读一个故事并回答关于这个故事的问题。这就是人工智能的世界，具体来说是一个叫做“深度学习”的领域，在这里，计算机通过观察海量的数据来学习模式。长期以来，这类任务中最受欢迎的机器人被称为“Transformer”。它们就像是才华横溢的图书管理员，能够瞬间翻遍整本书来寻找某个特定的事实。但问题在于：随着书变得越来越长，图书管理员的速度也会变得越来越慢，而且建造它们需要消耗大量的能量和资金。

为了解决这个问题，科学家们发明了新型机器人，比如“RNN”（它们像人类一样一次读一个词）和“SSM”（它们尝试以一种非常精简的方式同时阅读整个故事）。大家都在问的一个大问题是：“这些更快的新型机器人是否和那些又慢又旧的机器人一样聪明，还是说它们存在隐藏的盲点？”为了找到答案，研究人员并不只是靠猜测；他们给这些机器人出了一些极其微小且棘手的谜题。这些谜题就像是 AI 世界里的“数学作业”。如果一个机器人连一个简单的作业题都解不出来，那就证明这个机器人的大脑存在一个根本性的极限，无论你如何训练它，它都无法逾越。

这篇题为《索引：开始与结束》（Indexing: the Beginning and the End）的论文，使用了一个非常具体且简单的谜题——“索引”——来测试不同机器人架构的大脑。这个谜题看似简单，实则具有欺骗性：想象你有一组 $n$ 个比特（由 0 和 1 组成的字符串）和一个告诉你该挑选哪一位的数字 $i$ 。目标仅仅是输出那个特定比特的值。这就像是递给你一排由 64 个开关组成的序列，并给你一个数字，比如“17”，然后问你：“第 17 个开关是开还是关？”

研究人员 Alexander Kozachinskiy、Vicente Opazo 和 Felipe Urrutia 发现，机器人观察信息的方式改变了一切。他们发现，有些机器人处理这项任务的速度极快，而另一些机器人则撞上了一堵无论增加多少层“思考”也无法逾越的墙。

这里有一个转折：论文证明了对于某些类型的机器人（特别是那些以“因果”或“掩码”方式处理信息的机器人，即它们只能看到过去的信息，而不能看到未来的信息），如果比特列表很长，且索引号出现在最后，那么解决这个谜题在数学上是不可能的。这就像是你给机器人排了一长队人，要求它记住每个人的脸，然后在最后时刻低声说：“告诉我第 42 个人的名字。”论文表明，像 RNN、Mamba 和掩码线性注意力 Transformer 这样的机器人存在“记忆瓶颈”。当索引最终到达时，它们无法将所有这些信息压缩成足够小的包，从而记住那个特定的比特。作者通过严密的数学证明了这一点，即使机器具有无限精度（意味着它们不会因为舍入误差而产生混乱），这一结论依然成立。

然而，如果你反转剧本，故事就会发生变化。如果索引号出现在列表的开头（即在向机器人展示那排人之前，先告诉它“记住第 42 个人”），那么 RNN 就变成了超级英雄。它们可以仅用一步就解决这个问题，而其他机器人（包括著名的 Transformer）至少需要两步才能搞定。

作者不仅做了数学推导，还用真实的模型进行了实验。他们在长达 64 个比特的列表上训练了这些机器人。结果与他们的理论完美吻合。那些数学理论预测会失败的机器人（即在长列表中尝试寻找末尾比特的因果型机器人）在列表变长时表现出持续的无力感。与此同时，那些数学理论预测会成功的机器人则轻松学会了这项任务。

那么，结论是什么呢？并不是说某种机器人比另一种更“好”。相反，这篇论文揭示了不同的架构拥有不同的“超能力”和不同的“克里普顿石”（致命弱点）。机器人处理信息的方式——无论是从左向右阅读、同时观察全局，还是尝试总结过去——决定了它究竟能解决哪些谜题，以及哪些谜题会让它永远止步不前。这有助于科学家理解人工智能的根本极限，确保当我们构建下一代智能机器时，能够准确地知道它们的边界在哪里。

技术摘要：索引：开始与结束

问题陈述

本文通过**索引原语（indexing primitive）**的视角，研究了现代深度学习架构——具体包括循环神经网络（RNNs）、Softmax Transformer、线性注意力 Transformer 以及状态空间模型（SSMs）——的表达能力与信息瓶颈。

该索引任务定义如下：给定一个由 $n$ 个比特 $\sigma_1, \dots, \sigma_n \in \{0, 1\}$ 组成的序列以及一个索引 $i \in \{1, \dots, n\}$ ，模型必须输出第 $i$ 个比特 $\sigma_i$ 的值。作者通过分析两种特定的任务变体来探测不同的架构限制：

右侧索引（Right-Hand Indexing, RHI）： 索引 $i$ 出现在输入序列的末尾（在比特序列之后）。模型必须根据处理过的先前 $n$ 个比特的信息来检索 $\sigma_i$ 。
左侧索引（Left-Hand Indexing, LHI）： 索引 $i$ 出现在输入序列的开头（在比特序列之前）。模型必须将索引信息在整个序列中传递，以便在末尾检索 $\sigma_i$ 。

本研究聚焦于“小型”架构，其定义为具有 $o(1)$ 参数（相对于序列长度 $n$ 为常数个参数）且可能使用无限精度实数运算的架构。

方法论

作者采用基于**因果复杂度（causal complexity）**和 **VC 维（VC dimension）**的理论框架来推导无条件的下界。

因果复杂度

对于因果（掩码）架构（即输出 $k$ 仅取决于输入 $1 $到$ k $），作者引入了**因果复杂度**的概念。它衡量了输入历史（$ x_1, \dots, x_{k-1} $）被压缩（通过一个“指纹”函数）到最小维度$ s $的程度，使得第$ k $个输出可以由该压缩表示和当前输入$ x_k$ 通过低算术复杂度计算得出。

核心见解： 如果一个架构具有低因果复杂度（具体为 $o(1)$ ），那么当所需的信息无法立即获取时，它无法压缩必要的历史信息以解决此类任务。

理论工具

VC 维： 作者改编了 Kozachinskiy 等人 (2025) 的技术，证明如果一个模型解决了索引任务，则其相关的概念类其 VC 维至少为 $n$ 。
算术复杂度： 他们利用各层所计算函数的算术复杂度（包括指数、算术运算和条件判断）来限制 VC 维。
无条件界限： 与以往依赖有限精度假设的研究不同，这些结果即使对于使用无限精度实数的模型也成立。

实验验证

作者通过对序列长度 $n \in \{8, 16, 32, 64\}$ 的二进制索引任务进行实验，验证了理论发现。作者对比了：

全量（Full）和因果（Causal）变体的 Softmax 及线性注意力 Transformer。
RNN（特指 GRU）。
SSM（特指 Mamba）。
所有模型均从头开始训练，并固定超参数，以观察随着 $n$ 增加时的学习动态。

核心贡献与结果

1. 右侧索引（索引在末尾）

在这种场景下，模型在看到索引之前会处理所有的 $n$ 个比特。为了解决此任务，模型必须将整个 $n$ 比特字符串压缩成足够小的状态，以便被索引标记（index token）处理。

低因果复杂度架构的不可能性： 作者证明，没有任何常数数量（ $O(1)$ $O (1)$ ）的层具有 $o(1)$ $o (1)$ 因果复杂度的架构能解决 RHI。
- 受影响的架构： 小型 RNN、SSM（如 Mamba）以及掩码线性注意力 Transformer 都具有 $o(1)$ 的因果复杂度。因此，即使使用无限精度，它们也无法在常数层数内解决 RHI。
- 实验确认： 这类模型（1 层和多层因果线性注意力、GRU、Mamba）在 $n$ 增长时持续无法学习 RHI，在 $n=64$ 时成功率降至 0%。
高因果复杂度架构的可能性：
- Softmax Transformer： 一个具有 $O(1)$ 参数的单层模型可以解决 RHI。这归功于其高因果复杂度（通过 Softmax 机制实现全局注意力）。
- 全量线性注意力（Full Linear-Attention）： 两个具有 $O(1)$ 参数的层可以解决 RHI。
- 实验确认： 这些配置能够轻松学习该任务，即使在 $n=64$ 时也能保持高成功率。

2. 左侧索引（索引在开头）

在这种场景下，索引首先被处理，并且必须被携带通过序列，直到到达相关的比特位置。

RNN 的主导地位： 小型 RNN 可以在单层、具有 $O(1)$ 参数的情况下解决 LHI。它们天生维持着一个隐藏状态，该状态可以携带索引 $i$ ，并在遇到第 $i$ 个比特时更新特定坐标。
其他架构的局限性：
- SSM 和线性注意力： 无论是 1 层 SSM 还是 1 层线性注意力（无论是掩码还是全量），都无法在 $o(1)$ 参数下解决 LHI。SSM 更新的线性特征阻碍了它们在不造成信息混合的情况下，选择性地将比特值“写入”由索引决定的特定位置。
- Softmax Transformer： 1 层 Softmax Transformer 在 $o(1)$ 参数下也无法解决 LHI。
通过深度解决： 所有架构（包括 SSM、线性注意力和 Softmax Transformer）如果拥有 2 层 且具有 $O(1)$ 参数，都可以解决 LHI。第一层负责传播索引，第二层负责检索比特。
实验确认： 1 层 GRU 在所有长度下均成功。1 层 Mamba 和线性注意力模型在 $n \ge 16$ 时失败。所有架构的 2 层版本均成功。

最小层数需求汇总表

架构	左侧索引 (LHI)	右侧索引 (RHI)
全量 Softmax	2	1
因果 Softmax	2	1
全量线性注意力	2	2
因果线性注意力	2	$\omega(1)$ (不可能)
SSM (如 Mamba)	2	$\omega(1)$ (不可能)
RNN	1	$\omega(1)$ (不可能)

（注： $\omega(1)$ 表示所需的层数不是常数；即它会随 $n$ 增长。）

意义与主张

本文声称提供了针对包括 SSM、RNN 和掩码线性注意力 Transformer 在内的低因果复杂度架构类别的首个多层、无限精度下界。

架构分离： 索引原语揭示了架构之间根本性的分离。虽然 Softmax Transformer 和全量线性注意力模型可以高效解决 RHI，但掩码变体和 SSM 则不行，这突显了全局注意力机制在克服信息瓶颈方面的特定作用。
线性的角色： 研究结果表明，SSM 常被称赞的线性更新规则在需要单步非线性选择性写入的 LHI 任务中反而成为了负担。
理论与实践的一致性： 实验表明，理论上的不可能结果（渐近下界）在有限训练设置中表现为定性的差异。具有理论解的配置能鲁棒地学习任务，而缺乏理论解的配置即使在小 $n$ 时表现尚可，也会随着序列长度增加而陷入困境。
谦逊态度： 作者明确指出，训练失败并非不可能性的证明，同样，在小 $n$ 时的成功也不代表对渐近下界的反驳。然而，理论界限与经验性能之间的强相关性表明，因果复杂度是检索类任务可学习性的鲁棒预测指标。

这项工作将对 Transformer 表达能力的分析（此前侧重于函数组合和归纳头）扩展到了现代且高效的替代方案上，为它们的局限性提供了严密的数学证明。