Why Are Linear RNNs More Parallelizable?

学界正日益将线性循环神经网络（LRNN）作为语言模型加以探索，其动因在于LRNN兼具强大的表达能力与良好的并行可扩展性。尽管已有研究证实了LRNN相较于Transformer在表达能力上的优势，但一个关键问题仍悬而未决：为何LRNN（而非传统的非线性RNN）在实践中能像Transformer一样高效并行化？我们通过建立不同类型的RNN与标准计算复杂度类之间的紧致关联，回答了这一问题。我们证明，LRNN可被视作深度为对数级（且门扇入有界）的算术电路；该深度仅略高于Transformer所对应的对数深度布尔电路，因而并行开销极小。进一步地，我们指出，非线性RNN能够求解L-完全问题（甚至在多项式精度假设下可求解P-完全问题），这揭示出其在并行效率上存在根本性瓶颈——无法像Transformer那样高效并行化。我们的理论还进一步刻画了近期若干主流LRNN变体之间细粒度的表达能力差异：置换-对角型LRNN是NC¹-完全的，而对角加低秩型LRNN则具有更强的表达能力（达到PNC¹-完全）。我们还通过为每一类RNN关联一个相应的自动机理论模型（即该RNN所能模拟的自动机类型），提供了更深入的理解。综上所述，我们的研究成果揭示了非线性RNN与各类LRNN之间固有的表达能力与并行效率权衡关系，为设计大语言模型（LLM）架构奠定了理论基础——使模型能在表达能力与并行效率之间实现最优平衡。

论文试图解决为什么线性RNN（LRNNs）能像Transformer一样高效并行化，而传统非线性RNN却不能——这一长期被忽视的理论根源问题；它并非经验性工程观察，而是首次从计算复杂性理论（NC¹、L、P等标准复杂度类）出发，严格刻画不同RNN类型在并行可计算性上的本质差异。

将RNN建模为电路复杂度模型：证明LRNN等价于log-depth算术电路（属NC¹或其扩展PNC¹），故天然支持高效并行；而非线性RNN可模拟L-完全甚至P-完全问题（需串行依赖），构成并行化的根本理论障碍；进一步通过自动机对应关系（如LRNN↔weighted automata）建立形式语义桥梁。

首次建立RNN架构与经典复杂度类的紧致对应（如permutation-diagonal LRNN = NC¹-complete，diagonal-plus-low-rank = PNC¹-complete）；不依赖实证实验，纯理论推导，但结论具强实践指导性（解释为何Mamba等LRNN变体可实现线性推理+并行训练）；隐含重要设计原则：避免状态更新中的非线性耦合是保障并行可扩展性的关键；未报告具体实验或代码，但为后续架构搜索（如自动机约束下的RNN结构发现）和硬件映射（log-depth电路综合）提供理论基础。

Mamba: Linear-Time Sequence Modeling with Selective State Spaces (ICML 2023); The Expressive Power of Transformers (NeurIPS 2021); On the Parallel Complexity of Linear Recurrent Networks (ICLR 2022 Workshop); Neural Turing Machines (arXiv 2014); Recurrent Neural Networks Are Universal Approximators (Neural Computation 1995)