Parallelizing Recurrent Models via Linear State Transitions

1,876 concepts1,394 papers25 proposals

For years, sequence modeling has faced a fundamental architectural schism. On one side stand Recurrent Neural Networks (RNNs) and autoregressive models, which maintain a compact, fixed-size hidden state that updates incrementally with each incoming token. This design makes them exceptionally efficient during inference, requiring $O(1)$ time and memory per step. On the other side stand Transformers, which process entire sequences simultaneously during training by computing attention across all tokens in parallel, but suffer from a quadratic $O(L^2)$ computational cost that slows down inference on long sequences.

The core obstacle preventing RNNs from matching the training efficiency of Transformers is the sequential processing bottleneck. Traditional recurrent architectures force a strict temporal dependency: the hidden state at time step $t$ cannot be computed until the hidden state at step $t-1$ is entirely finished.

To overcome this bottleneck, a rapidly growing body of research focuses on linearizing the recurrence. By removing non-linear activation functions from the state-to-state transition, the sequential step-by-step update can be reframed as an associative mathematical operation. This single shift unlocks the ability to use highly efficient parallel scan algorithms on modern hardware, combining the fast training throughput of Transformers with the lightweight inference of recurrent networks.


The Anatomy of the Sequential Bottleneck

To understand why traditional RNNs cannot be easily parallelized, consider the standard hidden state update rule:

$$h_t = \sigma(W h_{t-1} + U x_t)$$

Here, $\sigma$ represents a non-linear activation function, such as $\tanh$ or $\text{ReLU}$. If we attempt to unroll this equation across a sequence of length $L$, we find that $h_L$ is nested deep within a chain of non-linearities:

$$h_L = \sigma(W \sigma(W \sigma(\dots) + U x_{2}) + U x_L)$$

Because matrix multiplication does not distribute over non-linear functions—meaning $\sigma(A) + \sigma(B) \neq \sigma(A + B)$—there is no mathematical shortcut to decouple these steps. As noted by Brakel et al. in their work on Bidirectional truncated recurrent neural networks for efficient speech denoising, this strict dependency prevents modern hardware accelerators like GPUs from executing simultaneous computations across the time dimension. The training depth is inherently bound to the sequence length $O(L)$.


Unlocking Parallelism Through Linearity

The breakthrough comes from removing the non-linear activation function $\sigma$ from the state transition itself, keeping it only for the input transformations and the final network outputs. A linear recurrent update takes the form:

$$h_t = A_t h_{t-1} + B_t x_t$$

Where $A_t$ and $B_t$ can be data-dependent matrices or scalars. Let's unroll this linear equation for the first few time steps, assuming an initial state $h_0 = 0$:

$$h_1 = B_1 x_1$$ $$h_2 = A_2 h_1 + B_2 x_2 = A_2 B_1 x_1 + B_2 x_2$$ $$h_3 = A_3 h_2 + B_3 x_3 = A_3 A_2 B_1 x_1 + A_3 B_2 x_2 + B_3 x_3$$

More generally, any state $h_t$ can be expressed directly as a function of the inputs and a sequence of cumulative products of the transition matrices:

$$h_t = \sum_{i=1}^t \left( \prod_{j=i+1}^t A_j \right) B_i x_i$$

Because matrix and scalar multiplications are associative—meaning $(A \times B) \times C = A \times (B \times C)$—we no longer need to compute the states chronologically. We can group the operations in any order we choose.


The Mechanism: Associative Parallel Scans

The mathematical associativity of linear recurrence allows us to compute the entire sequence of hidden states using an associative scan (or prefix sum) algorithm. Instead of stepping through time linearly, the computation is structured as a binary tree.

Imagine a sequence of 4 tokens. Instead of computing step 1, then step 2, then step 3, then step 4, the parallel scan operates in two primary phases:

  1. The Up-Sweep (Reduction): Pairwise combinations are computed in parallel. Step 1 and Step 2 combine their transition operators; Step 3 and Step 4 do the same simultaneously.
  2. The Down-Sweep: The partial products are propagated back down the tree to synthesize the final hidden states for all time steps.
Sequential Processing (O(L) steps):
[Step 1] ──> [Step 2] ──> [Step 3] ──> [Step 4]

Parallel Scan Processing (O(log L) steps):
[Step 1]   [Step 2]   [Step 3]   [Step 4]
   \         /           \         /
    \       /             \       /
  [Combine 1-2]         [Combine 3-4]
        \                     /
         \                   /
        [Combine Blocks 1-4]

By restructuring the workload into a tree, the computational depth drops from $O(L)$ to $O(\log L)$. For a sequence of 2,048 tokens, a traditional RNN requires 2,048 sequential iterations, whereas a parallel linear scan requires only $\log_2(2048) = 11$ parallel steps on a GPU.

As demonstrated by Orvieto et al. in Resurrecting Recurrent Neural Networks for Long Sequences, standard recurrent networks equipped with linear updates—termed Linear Recurrent Units (LRUs)—can match both the training speed and long-range accuracy of state-of-the-art State-Space Models (SSMs) like S4. Similarly, Yue et al. leveraged this mechanism in Linear Recurrent Units for Sequential Recommendation to bypass the heavy computational footprint of self-attention, achieving $O(1)$ inference while maintaining fast training convergence.


Advanced Parallelization: Beyond Basic Scans

While a simple linear recurrence can be parallelized via prefix sums, more complex memory update rules require specialized algebraic formulations to maintain hardware efficiency.

Compact WY Representations for Delta Updates

In models that use more expressive memory updates, such as the delta rule (where the model explicitly subtracts old information before writing new information), the transition matrices become more intricate. To parallelize these architectures, Yang et al. introduced a hardware-efficient algorithm for DeltaNet in Parallelizing Linear Transformers with the Delta Rule over Sequence Length. They utilized the compact WY representation—a technique borrowed from numerical linear algebra—to factorize historical updates into a pair of compact matrices. This allows the model to evaluate complex, state-dependent memory updates across the entire sequence length in parallel, outperforming standard recurrent baselines.

Sequence Slicing and Chunking

An alternative approach to mitigating the sequential bottleneck involves dividing the sequence into smaller, independent blocks. Yu proposed this in Sliced Recurrent Neural Networks, breaking long sequences into shorter subsequences that are processed simultaneously by a hierarchical network of recurrent units. This method balances local sequential context tracking with global parallel execution.


The Expressivity-Parallelism Trade-off

If linearizing the recurrence solves the training bottleneck so elegantly, why do we ever use non-linear recurrent updates? The answer lies in a fundamental trade-off between a model's training efficiency and its representational capacity.

As Elelimy et al. observe in Real-Time Recurrent Learning using Trace Units in Reinforcement Learning, there is an inherent tension between the representational benefits of non-linear state transitions and the scalability of the training process. Non-linearities allow a network to perform complex, iterative computation within a single time step, changing its behavior dynamically based on subtle combinations of past inputs.

This limitation is formalized by Chen et al. in The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity. The authors prove that because the recurrent state updates in parallelizable models (like selective SSMs) can be reduced to prefix-sum-like operations, their effective computational depth is fundamentally bounded. This mathematical restriction prevents them from solving certain classes of problems that require deep, inherently sequential reasoning—such as tracking complex state changes over long horizons or executing arbitrary iterative algorithms.

Complementing this perspective, Chi demonstrates in Transformer Working Memory Enables Regular Language Reasoning And Natural Language Length Extrapolation that while pure parallel processing excels at identifying statistical correlations within a training window, robust sequential state tracking remains essential for tasks requiring strict logical extrapolation.

The ongoing evolution of linear recurrent units, state-space models, and parallelized linear attention represents a targeted effort to navigate this boundary: engineering architectures that are linear enough to train in parallel, yet expressive enough to reason effectively.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sequential_processing_bottleneck_sequent_eea2e71c,
  title = {sequential processing bottleneck (sequential computation bottleneck)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-processing-bottleneck-sequential-computation-bottleneck/rdr_eea2e71c66d04e26baea5cca79ddde56},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_sequential_processing_bottleneck_sequent_eea2e71c_v1,
  title = {sequential processing bottleneck (sequential computation bottleneck)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-processing-bottleneck-sequential-computation-bottleneck/rdr_eea2e71c66d04e26baea5cca79ddde56/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake