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.
Abstract (translated)
社区越来越多地探索将线性递归神经网络（LRNN）作为语言模型，这一趋势受到其表达能力和并行化潜力的驱动。尽管先前的研究已经证明了LRNN在表达能力上优于转换器模型，但尚不清楚是什么原因使得LRNN能够在实践中像转换器一样易于并行化，而传统的非线性RNN则不能。 我们通过将不同类型的RNN与标准复杂度类紧密联系起来回答了这个问题。研究表明，LRNN可以被视作对数深度（有界扇入）算术电路，这仅相对于转换器模型所允许的对数深度布尔电路带来微小的深度开销。此外，我们还证明了非线性RNN能够解决$\mathsf{L}$-完全问题（甚至在多项式精度下可以解决$\mathsf{P}$-完全问题），揭示了它们实现与转换器同等高效并行化的根本障碍。 我们的理论也区分出了近期流行的LRNN变体之间细微的表达能力差异：排列对角线LRNN是$\mathsf{NC}^1$-完全，而对角加低秩LRNN则更为复杂（$\mathsf{PNC}^1$-完全）。我们通过将每种RNN类型与它可以模拟的自动机理论模型关联起来进一步提供了见解。 综上所述，我们的研究成果揭示了非线性RNN和不同变体的LRNN之间在表达能力和并行化之间的根本权衡，并为设计实现两者最优平衡的语言模型（LLM）架构奠定了基础。
URL
https://arxiv.org/abs/2603.03612
