For decades, a fundamental assumption has shaped the design of sequence models: time must be processed sequentially. Whether tracking a physical system using a Kalman filter, simulating a differential equation, or training a Recurrent Neural Network (RNN), computing the state at time step $t$ has traditionally required knowing the state at time step $t-1$.
This creates a strict linear dependency—an $O(T)$ computational bottleneck. On modern hardware like GPUs, which derive their power from massive parallelism across thousands of cores, sequential dependencies force hardware to sit idle. This bottleneck is precisely what drove the deep learning community away from RNNs and toward architectures like the Transformer, which processes all tokens simultaneously during training.
However, a rapidly growing body of research is breaking this sequential bottleneck. By reframing time-series dependencies as associative operations, researchers are unlocking the ability to process sequential data in logarithmic time ($O(\log T)$) using parallel associative scans.
The Core Intuition: The Power of Associativity
To understand how a sequential process can be executed in parallel, consider the simple problem of computing a prefix sum (or cumulative sum) of an array of numbers: [3, 1, 4, 2].
The sequential approach adds the numbers one by one:
- $3$
- $3 + 1 = 4$
- $4 + 4 = 8$
- $8 + 2 = 10$
This requires 3 sequential steps. But addition is associative: $(a + b) + c = a + (b + c)$. Because the grouping does not matter, we can construct a binary tree to perform the operations in parallel:
- Step 1: Compute $3 + 1 = 4$ and $4 + 2 = 6$ simultaneously on separate cores.
- Step 2: Combine the results: $4 + 6 = 10$.
By organizing the computation into a tree structure, the number of sequential steps drops from $O(T)$ to $O(\log T)$.
Parallel associative scans (such as the Blelloch scan algorithm highlighted by Jiaxi Hu et al.) apply this exact tree-based reduction to complex algebraic operations. If the transition function that carries a system from state $h_{t-1}$ to $h_t$ can be formulated as an associative operator, the entire history of the sequence can be computed concurrently.
Linearizing the State Space
The primary obstacle to using parallel scans in sequence modeling is non-linearity. In a standard RNN or an ordinary differential equation (ODE), the hidden state update involves a non-linear activation function (like $\tanh$ or $\text{ReLU}$):
$$h_t = \sigma(W h_{t-1} + U x_t)$$
Because non-linear functions do not distribute over addition or matrix multiplication, they destroy associativity. To bypass this, modern sequence models deliberately linearize the recurrence.
In Resurrecting Recurrent Neural Networks for Long Sequences, Antonio Orvieto et al. demonstrated that stripping the non-linearities out of the recurrent step yields a Linear Recurrent Unit (LRU) that can be trained via parallel scans. Similarly, the Hierarchically Gated Recurrent Neural Network (HGRN) developed by Zhen Qin et al. utilizes element-wise linear recurrence to remove sequential dependencies, matching Transformer performance while maintaining linear scaling with sequence length during inference.
As Jimmy T. H. Smith et al. noted in Simplified State Space Layers for Sequence Modeling, this parallel scan approach serves as a powerful time-domain alternative to the frequency-domain convolutions used in early State-Space Models (SSMs). Crucially, because parallel scans operate in the time domain, they easily accommodate time-varying parameters—a property that frequency-domain convolutions cannot support.
Parallelizing Classical Inference and Control
The shift from linear to logarithmic temporal complexity extends far beyond deep learning. Classical algorithms for state estimation, probabilistic inference, and optimal control are being systematically rewritten through the lens of associativity.
Bayesian Filtering and Smoothing
In tracking and time-series filtering, the Kalman filter updates its latent state estimates recursively as new measurements arrive. In Temporal Parallelization of Bayesian Filters and Smoothers, Simo Särkkä et al. reframed Bayesian filtering and smoothing equations as an all-prefix-sums problem. By defining an associative operator to combine sub-sequences of observations, they mapped the sequential filtering process onto a binary tree, achieving massive speedups on GPUs. This mathematical equivalence means the parallelized version yields the exact same results as the traditional recursive filter, but in a fraction of the time.
Continuous-Time Control
A similar breakthrough has occurred in optimal control. Solving the Hamilton–Jacobi–Bellman (HJB) equation traditionally requires a backward-in-time sweep across the entire time horizon. Simo Särkkä et al. introduced an associative composition operator for "conditional value functions." This allows sub-intervals of a control trajectory to be aggregated simultaneously, reducing the temporal complexity of continuous-time linear quadratic control to $O(\log T)$.
Conquering Non-Linearity via Iterative Optimization
If parallel associative scans fundamentally require linearity, how can we parallelize systems that are inherently non-linear? Researchers have developed two primary strategies to overcome this limitation:
1. Shifting Non-Linearity to Depth
Instead of placing non-linearities inside the temporal recurrence, models can isolate non-linear operations within feed-forward layers stacked above or between linear recurrent layers. For example, Shiva Kaul proposed the LDStack architecture in Linear Dynamical Systems as a Core Computational Primitive. By moving non-linearity entirely from the time dimension to the depth dimension, the model retains the ability to approximate complex non-linear functions while computing the temporal dimension in parallel via scans.
2. Iterative Linearization (Newton's Method)
For systems where non-linear temporal dynamics are unavoidable—such as traditional LSTMs, GRUs, or Markov chain Monte Carlo (MCMC) sampling—researchers use iterative optimization to unlock parallelism.
In Parallelizing MCMC Across the Sequence Length, David M. Zoltowski et al. treated a sequential MCMC chain as a fixed-point solution to a non-linear recursion. By linearizing the entire trajectory around a candidate sequence, they generated a block-bidiagonal system of equations that can be solved in parallel using an associative scan.
This exact insight was applied to deep learning by Federico Danieli et al. in ParaRNN: Unlocking Parallel Training of Nonlinear RNNs for Large Language Models. They demonstrated that the forward and backward passes of standard non-linear RNNs can be cast as a system of equations and solved via Newton’s method. During each Newton iteration, parallel reduction algorithms solve the linearized dependencies simultaneously, achieving up to a $665\times$ training speedup for large-scale language models.
Sequential Processing (O(T) Span):
[Step 1] ──> [Step 2] ──> [Step 3] ──> [Step 4] ──> [Step 5] ──> [Step 6]
Parallel Associative Scan (O(log T) Span):
[Step 1] [Step 2] [Step 3] [Step 4] [Step 5] [Step 6]
└─── ┬ ───┘ └─── ┬ ───┘ └─── ┬ ───┘
[Combined 1-2] [Combined 3-4] [Combined 5-6]
└────────────── ┬ ──────────────┘ │
[Combined 1-4] │
└──────────────────────── ┬ ────┘
[Combined 1-6]
Broad Impact Across Domains
The transition from linear to logarithmic temporal complexity is unifying sequence processing across disparate fields of computer science and engineering:
- Spiking Neural Networks (SNNs): In Bullet Trains: Parallelizing Training of Temporally Precise Spiking Neural Networks, Todd Morrill et al. modeled sub-threshold neuron dynamics as affine maps. This formulation allowed them to use parallel associative scans to scale SNN training with the number of spike events rather than simulation time steps.
- Controlled Differential Equations (CDEs): Benjamin Walker et al. integrated associative parallel scans with structured linear vector fields in Structured Linear CDEs: Maximally Expressive and Parallel-in-Time Sequence Models, bridging the gap between continuous-time modeling and parallel hardware efficiency.
- Probabilistic Numerical Solvers: In Parallel-in-Time Probabilistic Numerical ODE Solvers, Nathanael Bosch et al. reframed ODE simulation as a Bayesian state estimation problem, leveraging parallel prefix-sum algorithms to reduce the computational complexity of long-horizon simulations to $O(\log N)$.
By recognizing that the mathematical backbone of time-series processing can be mapped to associative operations, this research direction effectively decouples sequence length from execution time, allowing modern parallel hardware to process historical dependencies at unprecedented scales.