Why Are Linear RNNs More Parallelizable?

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.

Recurrent neural networks (RNNs) are a classical neural network approach for processing sequential data by maintaining a recurrent state while reading tokens in the sequence one by one. RNNs are quite natural and expressive, but they suffer in scalability because it is hard to parallelize their sequential state update. Recently, RNNs with linear updates have been proposed because they are easy to parallelize and past theoretical work has shown they are expressive. However, it was unknown whether they may be fundamentally weaker in some way than nonlinear RNNs, or, conversely, whether it might be possible to parallelize nonlinear RNNs similarly. Our work shows theoretically that nonlinear RNNs are more expressive than linear RNNs and that this corresponds to greater fundamental parallelizability for linear RNNs. This suggests that, while nonlinear RNNs may be attractive due to their greater expressivity, this will always come with a parallelism cost. Our results also reveal finegrained differences between different linear RNNs that could inform the design of linear RNN architectures.