# Parallelizing Linear Recurrent Neural Nets Over Sequence Length

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

## Key facts

- Cited by 127 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2017.

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

- [VMamba: Visual State Space Model](https://mlsanity.com/paper/2401.10166/) (2024)
- [RWKV: Reinventing RNNs for the Transformer Era](https://mlsanity.com/paper/2305.13048/) (2023)
- [Simplified State Space Layers for Sequence Modeling](https://mlsanity.com/paper/2208.04933/) (2022)
- [Gated Delta Networks: Improving Mamba2 with Delta Rule](https://mlsanity.com/paper/2412.06464/) (2024)
- [Gated Linear Attention Transformers with Hardware-Efficient Training](https://mlsanity.com/paper/2312.06635/) (2023)
- [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)
- [MiniMax-M1: Scaling Test-Time Compute Efficiently with Lightning Attention](https://mlsanity.com/paper/2506.13585/) (2025)
- [Griffin: Mixing Gated Linear Recurrences with Local Attention for Efficient Language Models](https://mlsanity.com/paper/2402.19427/) (2024)
- [Samba: Simple Hybrid State Space Models for Efficient Unlimited Context Language Modeling](https://mlsanity.com/paper/2406.07522/) (2024)
- [Eagle and Finch: RWKV with Matrix-Valued States and Dynamic Recurrence](https://mlsanity.com/paper/2404.05892/) (2024)
- [Kimi K3: Open Frontier Intelligence](https://mlsanity.com/paper/2607.24653/) (2026)
- [HGRN2: Gated Linear RNNs with State Expansion](https://mlsanity.com/paper/2404.07904/) (2024)
- [Caduceus: Bi-Directional Equivariant Long-Range DNA Sequence Modeling](https://mlsanity.com/paper/2403.03234/) (2024)
- [Hierarchically Gated Recurrent Neural Network for Sequence Modeling](https://mlsanity.com/paper/2311.04823/) (2023)
- [The Hidden Attention of Mamba Models](https://mlsanity.com/paper/2403.01590/) (2024)
- [Gated Slot Attention for Efficient Linear-Time Sequence Modeling](https://mlsanity.com/paper/2409.07146/) (2024)
- [DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Products](https://mlsanity.com/paper/2502.10297/) (2025)
- [Theoretical Foundations of Deep Selective State-Space Models](https://mlsanity.com/paper/2402.19047/) (2024)
- [Sparser is Faster and Less is More: Efficient Sparse Attention for Long-Range Transformers](https://mlsanity.com/paper/2406.16747/) (2024)
- [Parallelizing non-linear sequential models over the sequence length](https://mlsanity.com/paper/2309.12252/) (2023)
- [Parallel Spiking Neurons with High Efficiency and Ability to Learn Long-term Dependencies](https://mlsanity.com/paper/2304.12760/) (2023)
- [Mamba-R: Vision Mamba ALSO Needs Registers](https://mlsanity.com/paper/2405.14858/) (2024)
- [MambaMixer: Efficient Selective State Space Models with Dual Token and Channel Selection](https://mlsanity.com/paper/2403.19888/) (2024)
- [State-space Models with Layer-wise Nonlinearity are Universal Approximators with Exponential Decaying Memory](https://mlsanity.com/paper/2309.13414/) (2023)
- [Oscillatory State-Space Models](https://mlsanity.com/paper/2410.03943/) (2024)
- [Towards Scalable and Stable Parallelization of Nonlinear RNNs](https://mlsanity.com/paper/2407.19115/) (2024)
- [Universality of Linear Recurrences Followed by Non-linear Projections: Finite-Width Guarantees and Benefits of Complex Eigenvalues](https://mlsanity.com/paper/2307.11888/) (2023)
- [StableSSM: Alleviating the Curse of Memory in State-space Models through Stable Reparameterization](https://mlsanity.com/paper/2311.14495/) (2023)
- [Parallelizing Legendre Memory Unit Training](https://mlsanity.com/paper/2102.11417/) (2021)

## Abstract (arXiv)

Recurrent neural networks (RNNs) are widely used to model sequential data but their non-linear dependencies between sequence elements prevent parallelizing training over sequence length. We show the training of RNNs with only linear sequential dependencies can be parallelized over the sequence length using the parallel scan algorithm, leading to rapid training on long sequences even with small minibatch size. We develop a parallel linear recurrence CUDA kernel and show that it can be applied to immediately speed up training and inference of several state of the art RNN architectures by up to 9x. We abstract recent work on linear RNNs into a new framework of linear surrogate RNNs and develop a linear surrogate model for the long short-term memory unit, the GILR-LSTM, that utilizes parallel linear recurrence. We extend sequence learning to new extremely long sequence regimes that were previously out of reach by successfully training a GILR-LSTM on a synthetic sequence classification task with a one million timestep dependency.