Parallel Associative Scans for Temporal State Space Models

This direction is merged into another direction: parallel associative scan. Its last version stays readable and citable here.

Version 1 of 159 papers96 conceptsfrozen 2026-10-04

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:

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.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_parallel_associative_scans_for_temporal__c61025b2,
  title = {Parallel Associative Scans for Temporal State Space Models},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parallel-associative-scans-for-temporal-state-space-models/rdr_c61025b2989f49c8b34bc3df4c38b6e2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_parallel_associative_scans_for_temporal__c61025b2_v1,
  title = {Parallel Associative Scans for Temporal State Space Models},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parallel-associative-scans-for-temporal-state-space-models/rdr_c61025b2989f49c8b34bc3df4c38b6e2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}