For years, sequence modeling faced a fundamental trade-off between training efficiency and inference speed. Recurrent Neural Networks (RNNs) process tokens sequentially, maintaining a compact hidden state that allows for fast, $O(1)$ inference. However, this step-by-step nature creates a strict dependency chain: you cannot compute the hidden state at time step $t$ until you have computed it for $t-1$. This sequential bottleneck prevents RNNs from fully utilizing the massive parallel processing power of modern GPUs during training.
Conversely, architectures like the Transformer discard recurrence entirely, allowing them to parallelize training across the entire sequence length. But this comes at a cost: inference becomes computationally expensive ($O(T^2)$ or requiring large Key-Value caches), as the model must attend to the entire history to generate the next token.
The research direction of parallelizable recurrence bridges this gap. By restructuring how states are updated and decoupling heavy computations from the temporal loop, these models achieve the best of both worlds: the high-throughput parallel training of Transformers and the efficient, constant-time inference of traditional RNNs.
Decoupling Gating from the Hidden State
To understand how we can parallelize a recurrent network, let us look at where the sequential bottleneck actually lives. In a standard LSTM or GRU, the gating mechanisms depend directly on the previous hidden state:
$$g_t = \sigma(W_x x_t + W_h h_{t-1})$$
Because $h_{t-1}$ is embedded inside the non-linear activation function $\sigma$, we cannot compute the gate values for the entire sequence in advance. The heavy matrix multiplication $W_h h_{t-1}$ must be executed step by step.
The first major insight of parallelizable recurrence is simple: remove the hidden-state dependency from the gates.
If the gates depend only on the current input $x_t$ (or a local window of inputs), the heavy linear transformations can be computed for the entire sequence simultaneously in a single, massive matrix multiplication.
Standard RNN (Sequential Bottleneck):
x_1 ──> Matrix Mult ──> Gate (needs h_0) ──> h_1
│
x_2 ──> Matrix Mult ──> Gate (needs h_1) ─────> h_2
Parallel Recurrence (Decoupled Gates):
[x_1, x_2, ..., x_T] ──> Massive Parallel Matrix Mult ──> All Gates Computed At Once
│
All Candidate States ──────────────────────────────────────────┴──> Lightweight Element-wise Scan
James Bradbury et al. pioneered this approach with Quasi-Recurrent Neural Networks (QRNN). By offloading the linear transformations to a parallelizable convolutional layer across the time dimension, they computed candidate states and gates for all timesteps at once. The actual recurrence was then reduced to a minimalist, element-wise pooling layer that runs incredibly fast on hardware.
Similarly, Tuan Lai demonstrated in The Context-Dependent Additive Recurrent Neural Net that removing the hidden-state dependency from gates allows sequence-level parallelization without sacrificing performance in context-driven tasks.
This architectural shift was further refined by Zhaowei Zhang et al. in their work on Simple Recurrent Units (SRUs), where decoupling the gating logic from state dependencies allowed the model to leverage full GPU parallelization during training while preserving long-term memory capabilities for real-time applications like State of Charge Estimation for Lithium-Ion Batteries Using Simple Recurrent Units and Unscented Kalman Filter.
Linear Recurrence and Associative Scans
While decoupling gates allows us to pre-compute the inputs to the recurrence, the state update itself ($h_t = f(h_{t-1})$) must still be resolved. If $f$ is non-linear (like a $\tanh$ or $\text{sigmoid}$ function), we are still forced to compute the states one after another.
The second core mechanism of this field is linearization. If we restrict the state transition to be strictly linear, the recurrence relation can be written as:
$$h_t = A_t h_{t-1} + B_t x_t$$
Because matrix multiplication and addition are associative operations, we can rewrite the sequential chain into a closed-form expression. As Zhenrui Yue et al. note in Linear Recurrent Units for Sequential Recommendation, linearizing these transitions allows the hidden states of an entire sequence to be expressed as a closed-form summation.
This algebraic trick unlocks the use of parallel associative scan algorithms. Instead of computing $h_1, h_2, h_3$ in order, a parallel scan splits the sequence into pairs, combining them hierarchically (similar to a prefix sum or merge sort). This reduces the time complexity of the state computation from $O(T)$ sequential steps to $O(\log T)$ parallel steps on hardware accelerators.
Sequential Scan (O(T)):
h_0 ──> h_1 ──> h_2 ──> h_3 ──> h_4 ──> h_5 ──> h_6 ──> h_7
Parallel Associative Scan (O(log T)):
[h_0, h_1] [h_2, h_3] [h_4, h_5] [h_6, h_7]
└───┬───┘ └───┬───┘ └───┬───┘ └───┬───┘
[h_0..1] [h_2..3] [h_4..5] [h_6..7]
└────────┬───────┘ └────────┬───────┘
[h_0..3] [h_4..7]
└───────────────────┬──────────────┘
[h_0..7]
As Steven D. Morad et al. explain in Recurrent Reinforcement Learning with Memoroids, framing linear recurrent models as associative operations allows for the complete decoupling of input, hidden state, and output, enabling sequence states to be computed simultaneously across the time dimension.
However, running a global parallel scan across long sequences can introduce data integrity issues if multiple independent documents are packed together. To solve this, Haoran Xu et al. developed PackMamba, which introduces a state-reset mechanism directly within the parallel associative scan. By zeroing out the transition matrix at document boundaries, they isolate packed sequences mathematically without disrupting the parallel execution flow on the GPU.
Chunkwise Parallelization and Matrix Duality
As sequence lengths grow into the tens of thousands, even an $O(\log T)$ associative scan can hit hardware communication bottlenecks. The modern evolution of parallelizable recurrence addresses this by breaking the sequence into local chunks, combining local recurrence with global matrix operations.
A prime example of this is the State Space Duality (SSD) framework introduced by Tri Dao et al. in Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality. The authors proved that linear state-space models and linear attention are dual views of the same mathematical structure. By reformulating the recurrence using block-decomposed matrix multiplications, they allowed the model to leverage high-throughput hardware accelerators like GPU Tensor Cores. Instead of scanning token-by-token, the model processes blocks of tokens in parallel, outperforming traditional selective scans at scale.
This chunkwise strategy is also vital for models that perform memory updates via error-correction rules. For instance, Songlin Yang et al. developed a hardware-efficient algorithm for DeltaNet. By utilizing a numerical linear algebra trick known as the compact WY representation, they reformulated sequential memory updates (the delta rule) into high-rank transformations that can be computed in parallel across chunks.
Building on this, Sumin Park et al. introduced Q-Delta, which integrates query-conditioned prediction errors into the state evolution using a similar chunkwise-parallel formulation to maintain high training throughput.
Solving Non-linear Recurrence Globally
The methods discussed so far rely on making the recurrence linear or quasi-linear. But what if the task strictly requires the expressive power of a fully non-linear RNN (like a traditional LSTM or GRU)? Can we parallelize a system where states are bound by non-linear equations?
The answer lies in reframing the problem from a sequential simulation to a global optimization problem.
Instead of computing the hidden states one by one, we can treat the entire sequence of hidden states ($h_1, h_2, \dots, h_T$) as a massive system of simultaneous non-linear equations. Federico Danieli et al. introduced this paradigm with ParaRNN: Unlocking Parallel Training of Nonlinear RNNs for Large Language Models. By applying Newton's method globally to the entire sequence of equations, they allowed all hidden states to be updated simultaneously rather than sequentially, unlocking massive training speedups for highly non-linear architectures.
A similar mathematical philosophy appears in PonderLM-2, where Boyi Zeng et al. used Jacobi iterations to parallelize the refinement of continuous hidden states across a sequence, transforming a step-by-step thinking process into a highly parallelizable computation.
Alternative Structural Decompositions
Beyond mathematical reformulations, researchers have found that changing the geometric layout or structural connectivity of the recurrent network can also break the sequential bottleneck.
- Dilation and Sub-sequences: Yang Zhang demonstrated in Dilated Recurrent Neural Networks that by introducing a dilation factor $s$, a recurrent layer can decompose a single sequence into $s$ independent sub-sequences. Because these sub-sequences do not depend on each other's intermediate states, they can be processed completely in parallel on hardware.
- Grid Rotation: In multi-dimensional sequence processing (like image processing), standard RNNs scan pixels in a cuboid fashion, creating long dependency chains. Marijn F. Stollenga et al. solved this in PyraMiD-LSTM by rotating the connection grid by 45 degrees. This geometric shift transforms the sequential dependency chain into a flat computation frontier, allowing all units on the frontier plane to be processed in parallel.
- State Variable Decoupling: Instead of unrolling gradients through time, the training process can be decoupled by treating hidden states as explicit variables to be optimized. Somjit Nath et al. proposed Fixed Point Propagation in Training Recurrent Neural Networks Online by Learning Explicit State Variables, allowing updates to different time steps in a state buffer to be performed independently and concurrently.
Conclusion
Parallelizable recurrence changes our understanding of sequence models. It proves that the stateful memory advantages of RNNs are not mathematically locked into serial execution. By linearizing state transitions, decoupling gating mechanisms, or solving state equations globally, these architectures achieve the high-throughput training efficiency of modern parallel hardware while retaining the fast, constant-time inference that makes recurrent networks so powerful.
Key Foundational Work
Bidirectional truncated recurrent neural networks for efficient speech denoising (2013) — contributed 2 concept elements to this direction.