看到了什么现象？

一个令人惊讶的层级关系：RNN + CoT 比 RNN 严格更强，但仍然指数级弱于 Transformer + CoT。而仅仅加上一层 Transformer（或一个正则表达式检索接口），RNN 就能模拟任意多项式时间图灵机——与 Transformer 完全等价。

为什么这重要？

这不是又一篇"Transformer 比 RNN 好"的论文。它精确定位了差距的唯一根源——in-context retrieval（从上下文中精确检索信息的能力），并且证明了这个差距可以通过最小的架构修改来弥合。这为 Hybrid SSM-Attention 架构提供了迄今最强的理论基础。

这篇文章解决什么问题？

深读 Wen et al. (2024) “RNNs are not Transformers (Yet)” [ref] 的核心证明，理解其适用范围、局限性，以及与 Mamba-2 的结构化状态空间对偶性的关系。

证明框架的核心结构

RNN 的形式化定义（关键！）

论文定义的 RNN 极其宽泛（Definition 3.3）：任何具有状态转移函数 t: (state, input) → state 和输出函数 o: state → output 的模型，状态维度为 Λ，精度为 p bits。状态记忆量 M = Λ × p bits。

关键约束是**“regular RNN”**：电路大小 C = Θ(P)，参数量 P = Ω(M) 且 P = Poly(M)。

这个定义覆盖了：

  • 经典 RNN (LSTM, GRU)
  • SSM (S4, S5, S6/Mamba, Mamba-2)
  • Linear Attention (RWKV, RetNet)
  • 滑动窗口注意力（streaming context windows）
  • 有限 KV cache 模型

核心洞察：只要你的隐状态是固定大小的（不随序列长度线性增长），你就是一个 RNN，所有下界都适用。

下界证明的核心技巧：通信复杂度归约

证明的关键思想简洁而优美：

  1. 考虑两方通信问题：Alice 持有输入序列 x，Bob 持有查询 k
  2. 如果 RNN 能解决检索问题，Alice 可以在 x 上运行 RNN，把状态（o(n) bits）发给 Bob
  3. Bob 用这个状态继续运行 RNN 来回答关于 x 的任意查询
  4. 但 Index 问题需要 Ω(n) bits 通信（信息论下界），矛盾

这个论证对 CoT 也成立！因为即使 RNN 生成中间步骤，每一步的状态仍然是 o(n) bits——CoT 不增加 RNN 的"记忆带宽"，只增加计算步数。

上界证明：Match 和 Count 两个注意力原语

Transformer 的上界构造基于两个注意力机制：

  • Match：给定查询 token，注意力集中在与查询匹配的 key 上（content-based addressing）
  • Count：均匀地注意每个匹配的 token，利用注意力权重的平均效应来计数

这两个原语足以解决 Index、AR、c-gram Retrieval、Counting 所有四个基本检索任务。

三个关键定理的细节

定理 1：CoT 严格提升 RNN（Section 4.1）

条件假设：PSPACE ⊄ P/Poly（标准复杂度假设，几乎肯定成立）

直觉：

  • 没有 CoT 的 RNN（O(log n) memory）= 多项式大小浅层电路
  • 有 CoT 的 RNN = 可以模拟 O(log n) 空间的图灵机，运行 exp(O(log n)) = Poly(n) 步
  • 复杂度假设保证存在 O(n) 空间问题不在 P/Poly 中

批判性注意：这个正面结果的条件是"O(log n) bit memory"。真实的 SSM 模型的状态远大于 log n——例如 Mamba 的状态维度是 d_model × d_state（通常数千维）。但在形式化框架中，这仍然是 o(n)。

定理 2：CoT 不能弥合差距（Section 4.2）

对四个基本检索任务（Index, AR, c-gram, Counting），任何 o(n) bit 记忆的 RNN 都无法解决，即使有任意长度的 CoT。而常数大小、O(log n) 精度的 Transformer 可以轻松解决。

IsTree 的巧妙构造：

  • 从长度为 n-2 的二进制序列 x 和索引 k 构造图
  • 顶点 a 连接到顶点 x_a + n - 1（对所有 a ∈ [n-2]）
  • 额外连接 k 到 k+1
  • 图是树 ⟺ x_k ≠ x_{k+1}

这把 IsTree 归约到了 Index 问题！Alice 持有 x（构造图的大部分边），Bob 持有 k（构造一条边和查询）。如果 RNN 能解决 IsTree，Bob 就能用 o(n) bits 的状态判断 x_k ≠ x_{k+1}，但这需要 Ω(n) bits——矛盾。

定理 3：一层 Transformer 足以弥合差距（Section 5.2）

Hybrid RNN（Definition 5.2）：RNN + 末尾一层 Transformer。

定理（Theorem 5.7）：对任意多项式时间图灵机 T ∈ TIME(n^A)，存在 hybrid linear RNN with O(A log n) memory + O(AB² log n) parameters，可以在 O(n^A) 步 CoT 中模拟 T。

证明思路：

  1. RNN 负责局部推理（状态转移、计算）
  2. 当需要从上下文检索信息时，attention 层执行 Match 操作
  3. 整个系统模拟图灵机：RNN 维护机器状态和磁带头位置，attention 层读取磁带内容

适用范围与局限

证明覆盖了 Mamba/Mamba-2

关键问题：Mamba-2 的 SSD（Structured State Space Duality）[ref] 表明 SSM 在数学上等价于一种特殊的注意力形式。那 Wen 的下界是否还适用？

答案是：完全适用。 原因：

  1. SSD 的对偶性只是训练/计算形式的对偶（可以用注意力矩阵乘法训练，用递归状态推理）
  2. 推理时 Mamba-2 仍然使用固定大小的状态向量——状态大小不随序列长度增长
  3. Wen 的下界只依赖"状态是 o(n) bits"这个性质
  4. SSD 不改变 Mamba-2 推理时的记忆复杂度

类比：把一张 1000×1000 的照片"等价"地编码为 1000000 个像素值。编码方式不同，但信息量相同。Mamba-2 的"注意力等价"是训练时的并行计算等价，不是推理时的记忆等价。

"一层 Transformer 就够"的实际含义

理论上一层就够，但有两个重要限制：

  1. 需要 CoT：hybrid RNN 模拟图灵机需要 O(n^A) 步 CoT。没有 CoT，一层 Transformer 只能做 O(1) 次检索——对简单任务够了（Index, AR），对复杂任务不够

  2. 参数量依赖任务复杂度：O(AB² log n)，其中 A 是时间复杂度指数，B 是图灵机状态数。复杂任务可能需要很多参数，即使只有一层

  3. 理论 vs 实践：Wen 的构造是存在性证明（constructive），但不保证梯度下降能找到这些参数。实际训练可能需要多层 attention 来实现理论上一层就够的功能

局限：只研究表达能力，不涉及学习

论文明确指出只研究 representation power（是否存在参数使模型能解决问题），不涉及：

  • 训练动态（梯度下降能否找到这些参数？）
  • 泛化（在训练分布外能否工作？）
  • 实际规模效应（理论构造在大规模上是否实用？）

与之前积累的整合

和 Hybrid 架构 blog 的关系

之前的 Hybrid 架构博客提炼了"归纳偏置匹配原则"——SSM 压缩、Attention 检索、MLP 变换。Wen 的定理给这个经验性原则提供了严格的理论下界：

  • 不是只是"SSM 在检索上效率不高"→ 是"SSM 在 o(n) memory 下不可能完美检索"
  • 不是"Attention 在检索上更好" → 是"一层 Attention 足以赋予 RNN 多项式时间图灵完备性"
  • NVIDIA 的 ~8% Attention 最优比例现在有了理论解释：你需要的不是很多 Attention（它只负责检索），而是至少一些 Attention

和 Autoregressive 近视性的关系

Autoregressive 近视性讨论了四层近视性。Wen 的结果指出了第五个维度：架构级别的记忆近视性。RNN 的固定大小状态强制执行了一种"信息压缩近视"——处理每个 token 时必须决定保留什么丢弃什么，但此时不知道未来的查询。这与 NVIDIA 发现的 Multi-Document QA 弱点一致（问题在序列末尾，SSM 层被不相关文档"污染"）。

和 Bitter Lesson 修正的关系

Bitter Lesson 修正讨论了"数据可弥补的差距 vs 架构硬边界"。Wen 的证明给出了一个架构硬边界的精确数学表述：o(n) memory 的 RNN 在 in-context retrieval 上有不可逾越的信息论下界，再多数据也无法弥补。

但有一个微妙之处：Wen 讨论的是精确检索（perfect solve）。NVIDIA 的实验表明，SSM 在 Phonebook 任务上虽然不能精确回忆，但展现出"模糊记忆"——预测的电话号码与正确答案共享多个数字。在实际语言建模中，"近似检索"可能比"精确检索"更常见。所以 Wen 的硬边界是精确意义上的，实践中 SSM 的降级可能是 graceful 的。

开放问题

  1. Input-dependent gating 的影响：Mamba/Mamba-2 使用输入依赖的门控（选择性 SSM），这是否能缩小精确检索的差距？Wen 的下界适用于所有 o(n) memory 模型，所以答案是"不能完美解决"，但是否能显著改善近似检索？

  2. CoT 长度的实际限制：理论上 hybrid RNN + CoT 能模拟任意多项式时间计算，但 CoT 长度是 O(n^A)。实际推理中，用户不会容忍 n² 甚至 n³ 长度的中间推理。这是否意味着理论等价性在实践中被 CoT 长度约束限制？

  3. 检索粒度：Wen 定义的检索任务都是 token 级别的精确匹配。实际语言模型需要的"检索"往往是语义级别的模糊匹配。Attention 的 softmax 归一化天然提供了模糊匹配能力。SSM 的"模糊记忆"在语义检索上是否反而有优势？

  4. 多层 RNN 的"隐式检索"：深层 RNN 是否通过多层状态传递实现了某种"隐式检索"？如果每层 RNN 都能执行 O(1) 步状态相关操作，L 层 RNN 是否等价于 L 步的受限检索？

关键引用

  • Wen, Dang, Lyu (2024). RNNs are not Transformers (Yet): The Key Bottleneck on In-context Retrieval. [ref]
  • Gu & Dao (2024). Mamba-2: Structured State Space Duality. [ref]
  • Waleffe et al. (2024). An Empirical Study of Mamba-based Language Models. [ref]
  • Sanford et al. (2023). Representational Strengths and Limitations of Transformers. [ref]
  • Li et al. (2024). Chain of Thought Empowers Transformers to Solve Inherently Serial Problems. [ref]
  • Feng et al. (2023). Towards Revealing the Mystery Behind Chain of Thought. NeurIPS 2023. [ref]

最后更新: 2026-03-20 09:30