[2603.03612] Why Are Linear RNNs More Parallelizable?

Abstract:The community is increasingly exploring linear RNNs (LRNNs) as language models, motivated by their expressive power and parallelizability. While prior work establishes the expressivity benefits of LRNNs over transformers, it is unclear what makes LRNNs -- but not traditional, nonlinear RNNs -- as easy to parallelize in practice as transformers. We answer this question by providing a tight connection between types of RNNs and standard complexity classes. We show that LRNNs can be viewed as log-depth (bounded fan-in) arithmetic circuits, which represents only a slight depth overhead relative to log-depth boolean circuits that transformers admit. Furthermore, we show that nonlinear RNNs can solve $\mathsf{L}$-complete problems (and even $\mathsf{P}$-complete ones, under polynomial precision), revealing a fundamental barrier to parallelizing them as efficiently as transformers. Our theory also identifies fine-grained expressivity differences between recent popular LRNN variants: permutation-diagonal LRNNs are $\mathsf{NC}^1$-complete whereas diagonal-plus-low-rank LRNNs are more expressive ($\mathsf{PNC}^1$-complete). We provide further insight by associating each type of RNN with a corresponding automata-theoretic model that it can simulate. Together, our results reveal fundamental tradeoffs between nonlinear RNNs and different variants of LRNNs, providing a foundation for designing LLM architectures that achieve an optimal balance between expressivity and parallelism.

[2603.03612] Why Are Linear RNNs More Parallelizable? Skip to main content arXiv is now an independent nonprofit! Learn more × Search arXiv Press Enter to search · Advanced search --> Computer Science > Machine Learning arXiv:2603.03612 (cs) [Submitted on 4 Mar 2026 ( v1 ), last revised 1 Jun 2026 (this version, v3)] Title: Why Are Linear RNNs More Parallelizable? Authors: William Merrill , Hongjian Jiang , Yanhong Li , Anthony Lin , Ashish Sabharwal View a PDF of the paper titled Why Are Linear RNNs More Parallelizable?, by William Merrill and Hongjian Jiang and Yanhong Li and An

related reading

• Aman's AI Journal • Primers • Ilya Sutskever's Top 30aman.ai
• How To Scale Your Modeljax-ml.github.io
• The Unreasonable Effectiveness of Recurrent Neural Networkskarpathy.github.io
• A Mathematical Framework for Transformer Circuitstransformer-circuits.pub
• Defeating Nondeterminism in LLM Inference - Thinking Machines Labthinkingmachines.ai
• LoRA Without Regret - Thinking Machines Labthinkingmachines.ai
• Linear Attention Fundamentals | Hailey Schoelkopfhaileyschoelkopf.github.io
• Linear Transformers Are Faster After All – Manifest AImanifestai.com
• Parallelizing Linear Transformers with the Delta Rule over Sequence Lengtharxiv.org
• On the Tradeoffs of SSMs and Transformers | Goomba Labgoombalab.github.io
• [2407.04620] Learning to (Learn at Test Time): RNNs with Expressive Hidden Statesar5iv.labs.arxiv.org
• GenAI Handbookgenai-handbook.github.io