Why Are Linear RNNs More Parallelizable?¶

会议: ICML2026
arXiv: 2603.03612
代码: https://arg-git.informatik.uni-kl.de/pub/LinearRNN
领域: LLM效率 / 序列模型理论 / 并行计算
关键词: Linear RNN, 并行化, 电路复杂度, 表达能力, 长上下文架构

一句话总结¶

这篇论文用电路复杂度严格解释了为什么 Linear RNN 比传统非线性 RNN 更容易像 Transformer 一样并行：LRNN 可落在近似 log-depth 的算术电路类中，而非线性 RNN 能表达更难并行的 logspace / polynomial-time 完全问题，二者形成表达力与并行性的基本权衡。

研究背景与动机¶

领域现状：长上下文 LLM 架构正在重新关注 RNN 和 state-space / linear attention 类模型。Mamba、RWKV、DeltaNet 等 Linear RNN 变体希望兼具递归状态的长度泛化和类似 Transformer 的高并行吞吐，因此“线性递归为什么容易并行”不再只是理论问题，而直接关系到长序列模型设计。

现有痛点：大家知道传统 RNN 是顺序更新，Transformer 可以并行；也知道某些 LRNN 能通过 scan 并行。但这只是算法直觉，还没有清楚回答两个更细的问题：第一，非线性 RNN 是否存在不可避免的并行化障碍；第二，不同 LRNN 变体之间是否只差工程实现，还是表达能力上也有严格层级。

核心矛盾：模型越表达力强，往往越像通用顺序计算，也越难压缩到浅层并行电路；模型越容易并行，可能又会牺牲某些算法ic任务的表达力。LRNN 恰好处在中间地带：它比 Transformer 的某些简单类别更强，但似乎没有传统非线性 RNN 那么难并行。

本文目标：论文要给 RNN/LRNN 建立一张复杂度地图：非线性 RNN 能表达哪些复杂度类，LRNN 上界在哪里，DPLR、PD、Mamba 等不同线性更新参数化之间又有什么细粒度差异。

切入角度：作者把神经网络识别语言的问题映射到电路复杂度与自动机理论。非线性 RNN 通过 counter machine / stack machine 展示顺序计算能力；LRNN 通过矩阵乘法和算术电路展示可并行性；不同 LRNN 参数化则对应不同 weighted finite automata 能力。

核心 idea：线性状态更新可以被写成矩阵乘积和求和，因此能由 log-depth 算术电路并行模拟；非线性递推可以模拟更强的顺序机器，所以除非复杂度理论发生重大塌缩，否则无法同等高效并行。

方法详解¶

这篇论文不是提出一个新模型，而是给现有 RNN 家族做理论分类。理解它的关键是：作者把“是否容易并行”转化成“能否用浅层 bounded fan-in 电路模拟”，把“表达能力”转化成“能解决哪个复杂度类的完全问题”。

整体框架¶

论文先定义两大类序列层。非线性 RNN 的状态更新是 \(h_t=f(h_{t-1},x_t)\)，其中 \(f\) 可包含 ReLU/MLP 等非线性。Linear RNN 的状态更新是 \(S_t=A_t(x_t)S_{t-1}+b_t(x_t)\)，也就是每一步对前一状态做线性变换再加输入相关项。实际多层模型可以像 Transformer 一样交替堆叠 recurrent sublayer 和 feedforward sublayer。

随后作者引入复杂度类：Transformer 和简单 LRNN 常落在 \(\mathsf{TC}^0\) 或 \(\mathsf{NC}^1\) 附近；LRNN 的一般上界是 \(\mathsf{PNC}^1\)，也就是 log-depth 算术电路加 positivity check；非线性 RNN 在 log precision 下能解决 \(\mathsf{L}\)-complete 问题，在 polynomial precision 下甚至能解决 \(\mathsf{P}\)-complete 问题。最后，论文用两个合成任务验证理论预测：sorted deterministic graph connectivity 和 iterated \(3\times3\) matrix multiplication。

关键设计¶

用复杂度类刻画并行化边界:
- 功能：把“能不能并行”从经验说法变成可证明的 circuit depth 上界/下界。
- 核心思路：如果一个模型能被 \(\mathsf{NC}^1\) 或近似 \(O(\log n\log^*n)\) 深度电路模拟，就可以视作接近 Transformer 的 log-depth 并行；如果它能表达 \(\mathsf{L}\)-complete 或 \(\mathsf{P}\)-complete 问题，则在标准复杂度猜想下无法压到同样浅的电路。
- 设计动机：长上下文长度 64K 到 1M 时，\(\log n\) 约 16-20，而 \(\log^2 n\) 可到 256-400。理论上的 depth 差异会转化成实际硬件上的顺序时间差异。
非线性RNN的表达力下界:
- 功能：解释为什么传统 RNN 难以像 LRNN/Transformer 那样并行。
- 核心思路：polynomial precision 的 MLP RNN 可以模拟 multi-stack machine，因此能识别 \(\mathsf{P}\)-complete 语言；log precision 的 MLP RNN 可以模拟 counter machine，解决 sorted deterministic graph connectivity 这个 \(\mathsf{L}\)-complete 问题。
- 设计动机：非线性递推可以把状态当成可更新的顺序存储器。这个能力带来更强算法表达力，但也意味着若想完全并行模拟它，就必须并行化本质上更顺序的计算。
LRNN和不同线性参数化的细粒度分类:
- 功能：说明 LRNN 不只是“都能 scan”，内部变体也有严格表达力差异。
- 核心思路：一般 LRNN 可写成卷积/矩阵乘积形式，因此语言识别落在 \(\mathsf{PNC}^1\)。DPLR LRNN 如 RWKV-7 和 DeltaNet 能解决 iterated \(3\times3\) matrix multiplication，达到 \(\mathsf{PNC}^1\)-complete；PD LRNN 的矩阵乘积保持 permutation-diagonal 结构，因此被限制在 \(\mathsf{NC}^1\)，但也能识别 \(\mathsf{NC}^1\)-complete 语言。
- 设计动机：这给架构设计提供了尺度尺。DPLR 比 PD 更强但仍保持近似 log-depth 可并行；Mamba/S4 等更简单结构可能更高效，却表达力更受限。

损失函数 / 训练策略¶

理论部分没有训练损失；实验部分用合成算法任务做二分类或逐步分类，所有模型用 AdamW、BCEWithLogitsLoss、batch size 128、梯度裁剪 1.0，最长训练 60K steps。比较对象包括 nonlinear RNN、Transformer、Mamba、RWKV-7、DeltaNet。训练长度范围为 \([1,100]\)，测试还包括 \([101,200]\) 和 \([201,300]\) 的长度外推。

实验关键数据¶

主实验¶

主结果首先是理论分类表。它回答的不是某个 benchmark 分数，而是不同模型家族的“最强能表达什么”和“最浅能并行到什么程度”。

模型类别	复杂度定位	并行深度含义	代表模型/任务	结论
Transformer / 简单 LRNN	约 \(\mathsf{TC}^0 \subseteq \mathsf{NC}^1\)	\(O(\log n)\) bounded fan-in 深度	Transformer、Mamba 类简单结构	最容易并行，但表达力有限
一般 LRNN	\(\mathsf{PNC}^1\) 上界	可由 \(O(\log n\log^*n)\) 深度模拟	线性状态更新家族	比 Transformer 多很小并行开销
DPLR LRNN	\(\mathsf{PNC}^1\)-complete	接近 LRNN 上界	RWKV-7、DeltaNet	在线性可并行范围内表达力最强
PD LRNN	\(\mathsf{NC}^1\)-complete	log-depth	permutation-diagonal LRNN	强于简单有限状态，但弱于 DPLR
log-precision nonlinear RNN	\(\mathsf{L}\)-complete	可能需要 \(\Omega(\log^2 n)\) 深度	MLP RNN 解图连通	表达力强，但并行成本更高
poly-precision nonlinear RNN	\(\mathsf{P}\)-complete	标准假设下不能 polylog-depth 并行	MLP RNN 模拟多栈机	最强但最顺序

合成实验验证理论预测。训练集和验证集长度在 \([1,100]\)，测试额外看 \([101,200]\) 和 \([201,300]\)。图中报告的是不同长度桶准确率趋势，论文结论可概括如下。

任务	理论预期	表现最强模型	表现较弱模型	观察
Sorted deterministic graph connectivity	\(\mathsf{L}\)-complete，非线性 RNN 可解，LRNN 难以完全表达	nonlinear RNN	Transformer、RWKV-7、Mamba、DeltaNet 在 OOD 长度退化	所有模型 ID 可学，只有 nonlinear RNN 长度外推接近完美
Iterated matrix multiplication over \(\mathbb{Z}_m\)	DPLR LRNN 与 nonlinear RNN 应更强	RWKV-7、DeltaNet、nonlinear RNN	Transformer、Mamba	DPLR 和非线性 RNN ID 近完美，OOD 只中等退化
Iterated matrix multiplication over \(\mathbb{Z}\)	无模数整数增长，更考验代数状态	RWKV-7、DeltaNet、nonlinear RNN	Transformer 明显退化，Mamba 低于 top models	DPLR 的线性代数结构非常适合矩阵乘积

消融实验¶

配置	关键指标	说明
nonlinear RNN on graph connectivity	OOD 长度仍接近满分	符合 \(\mathsf{L}\)-complete 能力分析
LRNN/Transformer on graph connectivity	长度越长退化越明显	理论上难以覆盖该顺序可达性问题
RWKV-7 / DeltaNet on IMM	ID 和 OOD 都强	DPLR 能表达 \(\mathsf{PNC}^1\)-complete 的矩阵乘积
Mamba on IMM	明显弱于 RWKV-7/DeltaNet	简单线性参数化表达力不足
Transformer on IMM	训练内也不稳定，长度外推更差	attention 的浅并行优势不等于代数递推能力
统一训练设置	AdamW、60K steps、batch 128	让差异主要来自架构 inductive bias

关键发现¶

LRNN 更容易并行的根本原因是线性递推可归约为矩阵乘积 / scan，而矩阵乘积有 log-depth 算术电路实现。
非线性 RNN 的“难并行”不是实现落后，而是因为它能模拟更强的顺序计算模型；这种表达力在复杂度意义上会带来深度代价。
DPLR 是一个很有吸引力的中间点：它比 Mamba/S4 等简单结构更能表达 iterated algebraic computation，但仍保持接近 Transformer 的并行深度。
实验虽然小，但和理论预测方向一致，说明这些复杂度结果不只是抽象分类，也能反映可训练模型在合成算法任务上的长度泛化行为。

亮点与洞察¶

论文最强的贡献是把 RNN 架构讨论从“经验上快/慢”提升到“复杂度类与 complete problem”的层面。对长上下文架构设计来说，这种理论坐标非常有用。
它给出了一个清晰 trade-off：如果想要 nonlinear RNN 的顺序算法能力，就要接受更深的并行模拟；如果想要接近 Transformer 的并行效率，就需要把状态更新限制在线性/可 scan 的形式。
DPLR 与 PD 的区分很有启发。许多论文会把“线性 RNN”合成一类，但这篇说明低秩项、置换对角结构等参数化选择会改变表达力上界。
合成任务选得比较贴理论：graph connectivity 分离 nonlinear RNN 和 LRNN，iterated matrix multiplication 分离 DPLR 和更简单架构，实验不是随便跑语言建模分数。

局限与展望¶

复杂度分析依赖精度、uniformity、bounded fan-in 等形式化假设。它解释的是渐近并行深度，不直接等价于 GPU kernel、显存带宽或训练稳定性。
实验是合成算法任务，能验证表达力倾向，但不能直接说明大规模语言建模质量。DPLR 在真实 LLM 预训练中的收益还要看数据、优化和硬件实现。
理论主要讨论精确模拟和语言识别能力；实际神经网络可以近似计算，也可能用多层 hybrid 结构绕开单层分类的局限。
论文指出 nonlinear RNN 的额外表达力可能需要 \(\Theta(\log n)\) 并行代价，但是否值得在真实任务中付出这个代价，仍是开放问题。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 用复杂度理论系统解释 LRNN 并行性，并细分 DPLR/PD 表达力，理论贡献很强。
实验充分度: ⭐⭐⭐☆☆ 实验和理论匹配度高，但规模较小，主要是合成任务验证。
写作质量: ⭐⭐⭐⭐☆ 论文结构清楚，但复杂度符号密集，对非理论读者门槛较高。
价值: ⭐⭐⭐⭐☆ 对长上下文 LLM 架构选择很有指导意义，尤其能帮助理解为什么 DPLR 类线性递推值得关注。