For years, a fundamental trade-off dominated sequence modeling: you could have the infinite impulse response and memory efficiency of Recurrent Neural Networks (RNNs), or the massive parallelism of Transformers. RNNs were notoriously slow to train because each hidden state $h_t$ depended on the previous state $h_{t-1}$, forcing a serial $O(T)$ computation over a sequence of length $T$.
However, a growing body of research has demonstrated that this sequential bottleneck is not a property of recurrence itself, but rather a property of how we compute it. By reformulating recurrences as associative operations, we can use parallel scan algorithms to reduce training complexity from $O(T)$ to $O(\log T)$, allowing recurrent models to scale to millions of timesteps on modern GPUs.
The Core Intuition: From Chains to Trees
To understand why parallelization is possible, consider the simplest form of a linear recurrence: $$h_t = a_t h_{t-1} + b_t$$ In a standard RNN, we compute $h_1$, then $h_2$, then $h_3$, and so on. This is a linear chain. But as Chris Cundy and Eric Martin point out in Parallelizing Linear Recurrent Neural Nets Over Sequence Length, this operation is mathematically similar to a prefix sum.
Just as you can sum a list of numbers in parallel using a binary tree (adding pairs, then pairs of sums, etc.), you can "sum" linear transformations. If we define an operator that combines two steps of the recurrence into one, and that operator is associative—meaning $(A \circ B) \circ C = A \circ (B \circ C)$—we can process the sequence using a parallel scan. This allows the GPU to compute the state at $t=1024$ without waiting for all 1023 previous steps to finish sequentially.
Linearizing the Recurrence
The primary obstacle to this speedup is nonlinearity. Traditional RNNs like LSTMs and GRUs use nonlinear activation functions (like $tanh$ or $sigmoid$) inside the recurrence, which breaks associativity.
Recent work has solved this by "stripping down" these models. In Were RNNs All We Needed?, Leo Feng and Yoshua Bengio introduced minLSTM and minGRU. By removing the hidden-state dependencies from the gates, they linearized the recurrence, enabling $O(\log T)$ training via parallel scans while matching the performance of Transformers.
Similarly, Shiva Kaul proposed LDStack in Linear Dynamical Systems as a Core Computational Primitive, arguing that we should move nonlinearity from the time dimension to the depth dimension. By stacking linear dynamical systems (LDS) with nonlinear layers in between, we maintain the expressive power of deep networks while keeping the temporal processing fully parallelizable.
Expanding the Domain: SSMs and Point Processes
This parallelization strategy has sparked a renaissance in State-Space Models (SSMs). Because SSMs are inherently linear recurrences (often derived from continuous-time differential equations), they are perfectly suited for parallel scans.
- Reinforcement Learning: In Accelerating Model-Based Reinforcement Learning with State-Space World Models, Maria Krinner and Ángel Romero show that replacing sequential RNNs with SSMs (the S5WM model) speeds up world model training by 10x.
- Event Sequences: Yuxin Chang and Alex James Boyd applied this to Hawkes processes. Their S2P2 model, detailed in Deep Continuous-Time State-Space Models for Marked Event Sequences, treats events as impulses in a linear system, using parallel scans to scale to massive datasets of irregularly timed events.
- Physical Dynamics: T. Konstantin Rusch and Daniela Rus introduced LinOSS in Oscillatory State-Space Models, modeling sequences as systems of forced harmonic oscillators. Even these complex second-order physical dynamics can be reformulated as associative scans for high-speed training.
A Unifying Framework for Parallel-in-Time
The shift toward parallel scans is not just a trick for RNNs; it is becoming a unifying framework for sequential computation. E. Kelly Buchanan and Ke Alexander Wang argue in A Unifying Framework for Parallelizing Sequential Models with Linear Dynamical Systems that many classical iterative methods—like Newton and Picard iterations—are actually approximations of linear dynamical systems that can be accelerated via parallel scans.
This even extends to hard optimization problems. In A Parallel-in-Time Newton's Method for Nonlinear Model Predictive Control, Casian Iacob and Simo Särkkä demonstrate that the sequential steps of a Newton solver for control can be mapped onto associative operators, achieving $O(\log N)$ scaling for the planning horizon.
Why It Works: The Associative Property
The reason this research direction is so potent is that it maps the mathematical structure of time onto the hardware structure of the GPU. Modern hardware is designed for "wide" operations, not "deep" ones. By finding the associative primitive in a sequential process—whether it's a recommendation engine (LRURec), a brain dynamics model (BDO), or a reservoir computer (ParalESN)—researchers are able to bypass the "arrow of time" during training.
As Xavier Gonzalez and Scott Linderman suggest in Predictability Enables Parallelization of Nonlinear State Space Models, if a system's evolution is predictable, we can often frame its evaluation as a global optimization problem solvable in $O((\log T)^2)$ time. The result is a new generation of models that possess the persistent memory of RNNs but the training velocity of the most advanced parallel architectures.