For decades, the "sequential bottleneck" has been the primary obstacle in time-series modeling. Whether you are tracking a satellite with a Kalman filter or training a recurrent neural network, the logic remains stubbornly linear: to know the state at time $t$, you must first compute the state at $t-1$. This $O(N)$ dependency means that as datasets grow longer, processing times stretch out, leaving modern parallel hardware like GPUs largely underutilized.
Recent breakthroughs have demonstrated that this bottleneck is not a mathematical necessity. By reframing temporal evolution as an associative operation, researchers have unlocked the ability to process sequences in $O(\log N)$ time using parallel prefix scans.
The Core Intuition: Breaking the Chain
To understand why this works, consider the simplest possible state-space update: $x_t = a_t x_{t-1} + b_t$. In a standard filter, we compute $x_1$, then $x_2$, and so on.
However, we can view the transition from $t-1$ to $t$ as a function $f_t(x) = a_t x + b_t$. If we want to jump from $t=0$ to $t=2$, we are looking for the composition of two functions: $f_2(f_1(x))$. Crucially, the composition of two linear functions is itself a linear function. If $f_1(x) = a_1 x + b_1$ and $f_2(x) = a_2 x + b_2$, then: $$f_{2 \circ 1}(x) = a_2(a_1 x + b_1) + b_2 = (a_2 a_1)x + (a_2 b_1 + b_2)$$
This composition is associative. It doesn't matter if we group $(f_3 \circ f_2) \circ f_1$ or $f_3 \circ (f_2 \circ f_1)$; the result is the same. Because the operation is associative, we can use a "divide and conquer" strategy—a parallel scan—to compute all prefix compositions in logarithmic steps rather than linear ones.
Parallelizing Bayesian Inference
The most significant application of this idea is in Bayesian filtering and smoothing. In Temporal Parallelization of Bayesian Smoothers, Ángel F. García‐Fernández and Simo Särkkä showed that the Kalman filter and smoother can be entirely reformulated as associative operators.
Instead of passing a single state estimate forward, the algorithm passes "elements" that represent the conditional distribution of a segment of time. Two adjacent segments can be merged into a larger segment using a specific binary operator. On a GPU, this allows a sequence of 10,000 time steps to be processed in roughly 14 parallel steps ($\log_2 10,000 \approx 13.3$), leading to speedups of several hundred times as documented in On The Performance of Prefix-Sum Parallel Kalman Filters and Smoothers on GPUs.
Beyond Filtering: ODEs and Control
This parallelization strategy is not limited to simple tracking. It has been extended to complex dynamical systems and optimization:
- Probabilistic ODE Solvers: Nathanael Bosch and colleagues introduced Parallel-in-Time Probabilistic Numerical ODE Solvers, which treat ODE solving as a state estimation problem. By using parallel scans, they reduce the complexity of simulating long-horizon physics from linear to logarithmic time.
- Optimal Control: The Hamilton–Jacobi–Bellman (HJB) equation and Bellman recursions, which are traditionally solved backwards in time, can also be parallelized. Temporal Parallelization of Dynamic Programming and Linear Quadratic Control demonstrates that merging optimal cost functions from adjacent intervals is an associative operation, allowing control policies to be computed in $O(\log N)$.
- Geometric Mechanics: For systems evolving on Lie groups (like rotating rigid bodies), Sungwoo Park and Jongwon Lee developed Euler–Poincaré Neural Dynamics, using associative Lie group operations to slash simulation times.
Integration into Deep Learning
The most recent frontier is the marriage of Bayesian filtering with modern sequence models. Vaisakh Shaj, Amos Storkey, and others introduced Kalman Linear Attention (KLA).
KLA reparameterizes the Kalman filter into its "information form" (using natural parameters and precisions). This specific mathematical form makes the Bayesian update step perfectly associative. The result is a model that has the expressive power of a Kalman filter—including explicit uncertainty tracking and non-linear state updates—but trains as fast as a Transformer or a State-Space Model (SSM) like Mamba.
Why This Works: The Semigroup Perspective
The unifying theme across these 53 papers is the search for a semigroup structure in dynamical systems. If the transition between any two points in time can be represented as an element of a set, and if there is a way to "multiply" these elements that is associative, then the sequential bottleneck is broken.
As Adrien Corenflos and Simo Särkkä argue in their work on Auxiliary MCMC, this shift doesn't just make things faster; it changes what is possible. It allows us to apply exact Bayesian inference to high-dimensional, long-duration datasets—from fMRI brain dynamics (BDO) to high-frequency inertial sensors (AirIMU)—that were previously computationally prohibitive.