# Towards Scalable and Stable Parallelization of Nonlinear RNNs

arXiv: https://arxiv.org/abs/2407.19115 · HTML: https://mlsanity.com/paper/2407.19115/

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 80 references that are in the map.
- First posted on arXiv 26 Jul 2024.

## Builds on (most cited first, 30 of 35)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Neural Ordinary Differential Equations](https://mlsanity.com/paper/1806.07366/) (2018)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [WaveNet: A Generative Model for Raw Audio](https://mlsanity.com/paper/1609.03499/) (2016)
- [Optimizing Neural Networks with Kronecker-factored Approximate Curvature](https://mlsanity.com/paper/1503.05671/) (2015)
- [Simplified State Space Layers for Sequence Modeling](https://mlsanity.com/paper/2208.04933/) (2022)
- [Deep Equilibrium Models](https://mlsanity.com/paper/1909.01377/) (2019)
- [Resurrecting Recurrent Neural Networks for Long Sequences](https://mlsanity.com/paper/2303.06349/) (2023)
- [Parallelizing Linear Transformers with the Delta Rule over Sequence Length](https://mlsanity.com/paper/2406.06484/) (2024)
- [Hyena Hierarchy: Towards Larger Convolutional Language Models](https://mlsanity.com/paper/2302.10866/) (2023)
- [xLSTM: Extended Long Short-Term Memory](https://mlsanity.com/paper/2405.04517/) (2024)
- [Break the Sequential Dependency of LLM Inference Using Lookahead Decoding](https://mlsanity.com/paper/2402.02057/) (2024)
- [On Neural Differential Equations](https://mlsanity.com/paper/2202.02435/) (2022)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [The Hardware Lottery](https://mlsanity.com/paper/2009.06489/) (2020)
- [Multiscale Deep Equilibrium Models](https://mlsanity.com/paper/2006.08656/) (2020)
- [Intensity-Free Learning of Temporal Point Processes](https://mlsanity.com/paper/1909.12127/) (2019)
- [Parallelizing Linear Recurrent Neural Nets Over Sequence Length](https://mlsanity.com/paper/1709.04057/) (2017)
- [Accelerating Transformer Inference for Translation via Parallel Decoding](https://mlsanity.com/paper/2305.10427/) (2023)
- [CKConv: Continuous Kernel Convolution For Sequential Data](https://mlsanity.com/paper/2102.02611/) (2021)
- [Parallel Sampling of Diffusion Models](https://mlsanity.com/paper/2305.16317/) (2023)
- [Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving](https://mlsanity.com/paper/2002.03629/) (2020)
- [Scheduled Sampling for Transformers](https://mlsanity.com/paper/1906.07651/) (2019)
- [Parallelizing non-linear sequential models over the sequence length](https://mlsanity.com/paper/2309.12252/) (2023)
- [Temporal Parallelization of Bayesian Smoothers](https://mlsanity.com/paper/1905.13002/) (2019)
- [SIXO: Smoothing Inference with Twisted Objectives](https://mlsanity.com/paper/2206.05952/) (2022)

## Built on by (most cited first, 30 of 38)

- [Gated Delta Networks: Improving Mamba2 with Delta Rule](https://mlsanity.com/paper/2412.06464/) (2024)
- [Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues](https://mlsanity.com/paper/2411.12537/) (2024)
- [ATLAS: Learning to Optimally Memorize the Context at Test Time](https://mlsanity.com/paper/2505.23735/) (2025)
- [It's All Connected: A Journey Through Test-Time Memorization, Attentional Bias, Retention, and Online Optimization](https://mlsanity.com/paper/2504.13173/) (2025)
- [Lattice: Learning to Efficiently Compress the Memory](https://mlsanity.com/paper/2504.05646/) (2025)
- [Structured Linear CDEs: Maximally Expressive and Parallel-in-Time Sequence Models](https://mlsanity.com/paper/2505.17761/) (2025)
- [TempoPFN: Synthetic Pre-training of Linear RNNs for Zero-shot Time Series Forecasting](https://mlsanity.com/paper/2510.25502/) (2025)
- [ParaRNN: Unlocking Parallel Training of Nonlinear RNNs for Large Language Models](https://mlsanity.com/paper/2510.21450/) (2025)
- [Memory Caching: RNNs with Growing Memory](https://mlsanity.com/paper/2602.24281/) (2026)
- [Real-Time Recurrent Learning using Trace Units in Reinforcement Learning](https://mlsanity.com/paper/2409.01449/) (2024)
- [Parallelization of Non-linear State-Space Models: Scaling Up Liquid-Resistance Liquid-Capacitance Networks for Efficient Sequence Modeling](https://mlsanity.com/paper/2505.21717/) (2025)
- [TNT: Improving Chunkwise Training for Test-Time Memorization](https://mlsanity.com/paper/2511.07343/) (2025)
- [Predictability Enables Parallelization of Nonlinear State Space Models](https://mlsanity.com/paper/2508.16817/) (2025)
- [Learning State-Tracking from Code Using Linear RNNs](https://mlsanity.com/paper/2602.14814/) (2026)
- [Fixed-Point RNNs: Interpolating from Diagonal to Dense](https://mlsanity.com/paper/2503.10799/) (2025)
- [SING: SDE Inference via Natural Gradients](https://mlsanity.com/paper/2506.17796/) (2025)
- [Trellis: Learning to Compress Key-Value Memory in Attention Models](https://mlsanity.com/paper/2512.23852/) (2025)
- [Pretraining Recurrent Networks without Recurrence](https://mlsanity.com/paper/2606.06479/) (2026)
- [Accelerated Training through Iterative Gradient Propagation Along the Residual Path](https://mlsanity.com/paper/2501.17086/) (2025)
- [A Unifying Framework for Parallelizing Sequential Models with Linear Dynamical Systems](https://mlsanity.com/paper/2509.21716/) (2025)
- [Maglev: Sliding Recurrent Memory](https://mlsanity.com/paper/2608.02870/) (2026)
- [R2DN: Scalable Parameterization of Contracting and Lipschitz Recurrent Deep Networks](https://mlsanity.com/paper/2504.01250/) (2025)
- [Context-Selective State Space Models: Feedback is All You Need](https://mlsanity.com/paper/2510.14027/) (2025)
- [Hyper Hawkes Processes: Interpretable Models of Marked Temporal Point Processes](https://mlsanity.com/paper/2511.01096/) (2025)
- [SNLP: Layer-Parallel Inference via Structured Newton Corrections](https://mlsanity.com/paper/2605.17842/) (2026)
- [Proteus: Incremental Memory Activation for Long-Context Sequence Modeling](https://mlsanity.com/paper/2608.16844/) (2026)
- [MMformer with Adaptive Transferable Attention: Advancing Multivariate Time Series Forecasting for Environmental Applications](https://mlsanity.com/paper/2504.14050/) (2025)
- [Generalized Orders of Magnitude for Scalable, Parallel, High-Dynamic-Range Computation](https://mlsanity.com/paper/2510.03426/) (2025)
- [Integrative neurocybernetic modeling in the era of large-scale neuroscience](https://mlsanity.com/paper/2604.23903/) (2026)
- [LBI: Parallel Scan Backpropagation via Latent Bounded Interfaces](https://mlsanity.com/paper/2605.09204/) (2026)

## Abstract (arXiv)

Transformers and linear state space models can be evaluated in parallel on modern hardware, but evaluating nonlinear RNNs appears to be an inherently sequential problem. Recently, however, Lim et al. '24 developed an approach called DEER, which evaluates nonlinear RNNs in parallel by posing the states as the solution to a fixed-point problem. They derived a parallel form of Newton's method to solve the fixed-point problem and achieved significant speedups over sequential evaluation. However, the computational complexity of DEER is cubic in the state size, and the algorithm can suffer from numerical instability. We address these limitations with two novel contributions. To reduce the computational complexity, we apply quasi-Newton approximations and show they converge comparably to Newton, use less memory, and are faster. To stabilize DEER, we leverage a connection between the Levenberg-Marquardt algorithm and Kalman smoothing, which we call ELK. This connection allows us to stabilize Newton's method while using efficient parallelized Kalman smoothing algorithms to retain performance. Through several experiments, we show that these innovations allow for parallel evaluation of nonlinear RNNs at larger scales and with greater stability.