Title: Unpacking the Parallelizability Advantage of Linear RNNs

Abstract:

Driven by their strong expressive capabilities and ease of parallelization, the research community is increasingly adopting linear recurrent neural networks (LRNNs) for language modeling tasks. Although previous studies have confirmed that LRNNs offer superior expressivity compared to transformers, the specific reasons why LRNNs—unlike conventional nonlinear RNNs—can be parallelized with the same efficiency as transformers remain opaque. This study resolves this ambiguity by establishing a rigorous link between RNN architectures and standard computational complexity classes.

We demonstrate that LRNNs function as arithmetic circuits with logarithmic depth and bounded fan-in. This structure incurs only a marginal depth penalty when compared to the log-depth boolean circuits characteristic of transformers. Conversely, our analysis reveals that nonlinear RNNs are capable of solving $\mathsf{L}$-complete problems, and even $\mathsf{P}$-complete problems when polynomial precision is assumed. This finding highlights a fundamental obstruction to parallelizing nonlinear RNNs with the same efficiency as transformers.

Additionally, our theoretical framework delineates the nuanced expressivity distinctions among contemporary LRNN variants. Specifically, permutation-diagonal LRNNs are identified as $\mathsf{NC}^1$-complete, while diagonal-plus-low-rank LRNNs exhibit greater expressivity, classified as $\mathsf{PNC}^1$-complete. By mapping each RNN category to a corresponding automata-theoretic model it can simulate, we offer deeper insights into these architectures. Collectively, these findings elucidate the essential trade-offs between nonlinear RNNs and various LRNN configurations, laying the groundwork for developing large language model (LLM) designs that strike an ideal equilibrium between parallelism and expressivity.

Source: arXiv Generated at: 2026-06-03 00:00:00 UTC