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 L-complete problems (and even 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 NC1-complete whereas diagonal-plus-low-rank LRNNs are more expressive (PNC1-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.
Figures & tables
Figure 1: Main results, summarized as a hierarchy of increasingly expressive RNN classes with popular models within each class. Each RNN shown is “tight” for the respective complexity class C ( PNC1 , L , etc.) in the sense that both falls in C and can solve a C -complete problem. LRNNs are in PNC1 , implying they can be nearly as efficiently parallelized as transformers, incurring only a small O(log∗(n)) depth overhead in terms of bounded fan-in boolean circuits. Nonlinear RNNs, in contrast, can solve L -complete and even P -complete problems, but this comes at the cost of being less parallelizable, requiring notably deeper circuits. Bottom row lists the classes of automata that each RNN model class can simulate, where WFA stands for weighted finite automaton and DWFA stands for deterministic WFA.
Figure 2: Accuracy across size/length ranges. (a) Deterministic graph connectivity over graph-size ranges. (b) Iterated 3×3 matrix multiplication over Zm . (c) Iterated 3×3 matrix multiplication over Z . Models are evaluated on in-distribution ranges [1,100] and out-of-distribution ranges [101,200] and [201,300] .
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Task
Model
Configuration
LR
Steps
DGC
RNN
dm=256 , L=2 , dh=256 ,
3×10−4
60k
Transformer
dm=256 , L=2 , h=4
3×10−4
60k
Mamba
dm=256 , L=2 , dstate=128
3×10−4
60k
RWKV-7
dm=256 , L=2 , h=4
3×10−4
60k
DeltaNet
dm=256 , L=2 , h=4
3×10−4
60k
IMM
RNN
dm=256 , L=2 , dh=256 ,
3×10−4
60k
Appendix
Table 1: Training hyperparameters for deterministic graph connectivity (DGC) and iterated matrix multiplication (IMM). dm , L , dh , h , dstate , and LR denote the model dimension, number of layers, hidden size, number of attention heads, SSM state expansion factor, and learning rate, respectively. All models are trained with AdamW, batch size 128, and gradient clipping at 1.0.