Efficient Sequence Modeling via Linear State Space Duality

This direction is merged into another direction: sequential processing bottleneck (sequential computation bottleneck). Its last version stays readable and citable here.

Version 1 of 168 papers69 conceptsfrozen 2026-10-04

For a decade, sequence modeling has been trapped in a fundamental trade-off. On one side, Recurrent Neural Networks (RNNs) offer efficient, constant-time inference by compressing history into a fixed-size state, but they are notoriously slow to train because their sequential nature prevents parallelization. On the other side, Transformers revolutionized the field with massive parallel training, but they pay for it with quadratic complexity—as sequences grow longer, the "KV cache" explodes, and inference slows to a crawl.

A new generation of research is breaking this "impossible triangle" by proving that recurrence and parallelization are not mutually exclusive. By leveraging the mathematical duality between linear recurrences, convolutions, and prefix scans, researchers are building models that train like Transformers and run like RNNs.

The Core Insight: Associative Duality

The breakthrough begins with a simple mathematical observation: if a recurrence is linear, it can be reformulated. Traditional RNNs like LSTMs use non-linear gates that force each step to wait for the previous one. However, as William Merrill and colleagues show in Why Are Linear RNNs More Parallelizable?, linearizing these updates allows us to use the associative property of matrix multiplication.

If we represent a state update as $h_t = A h_{t-1} + B x_t$, and $A$ is a constant matrix, we can compute any future state $h_T$ directly. More importantly, we can compute all intermediate states in parallel using a Parallel Prefix Scan (or "All-Prefix-Sums") algorithm. This reduces the training complexity from $O(N)$ sequential steps to $O(\log N)$ parallel depth.

From Linear Transformers to State-Space Models

This duality was first popularized through two distinct but converging paths:

  1. Linear Attention: Angelos Katharopoulos and his team demonstrated in Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention that by swapping the softmax in attention for a kernel-based feature map, the entire Transformer can be mathematically rewritten as an RNN. This allows for $O(1)$ inference while maintaining the parallel training of the original architecture.
  2. State-Space Models (SSMs): Albert Gu and others introduced the Linear State-Space Layer (LSSL) in Combining Recurrent, Convolutional, and Continuous-time Models with Linear State Space Layers. SSMs treat sequence modeling as a continuous differential equation that, when discretized, can be computed as either a fast convolution (for training) or a recurrent state update (for inference).

These two paths merged into a unified framework. As explored in Sequential-Parallel Duality in Prefix Scannable Models by Kazuki Irie and Jacob Andreas, models like Mamba, RetNet, and Linear Transformers are all facets of the same underlying mechanism: Prefix-Scannable Models.

Solving the Impossible Triangle

The "Impossible Triangle" consists of three goals: parallel training, low-cost inference, and high performance. Yutao Sun and the Microsoft Research team proposed the Retentive Network (RetNet) in Retentive Network: A Successor to Transformer for Large Language Models as a solution. RetNet uses a "retention" mechanism that has a dual form: a parallel representation for high-throughput training and a recurrent representation for $O(1)$ inference.

Similarly, in the world of robotics and real-time control, where inference latency is a physical constraint, Thomas Schmied showed that the xLSTM architecture in A Large Recurrent Action Model: xLSTM enables Fast Inference for Robotics Tasks can match Transformer performance while maintaining constant inference speeds, regardless of how long the robot has been operating.

The Next Frontier: Reintroducing Non-linearity

While linear models are easy to parallelize, they sometimes lack the "expressive "state-tracking" power of traditional non-linear RNNs like LSTMs. Recent work is now focused on bringing parallelization to non-linear systems.

Why It Works: A Summary of Intuition

The shift from Transformers to Linear State-Space Duality works because it recognizes that context is a choice. In a standard Transformer, the context is the entire history (the KV cache), which grows forever. In a State-Space Model or a Linear Transformer, the context is a fixed-size "summary" (the hidden state).

By ensuring the update rule for that summary is associative, we unlock the ability to compute the summary for the 1000th token without waiting for the 999th. This mathematical bridge allows us to keep the best part of Transformers (the training speed) while reclaiming the best part of RNNs (the inference efficiency).

Papers in this version

Showing 60 of 68 papers.

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_efficient_sequence_modeling_via_linear_s_f4b948ec,
  title = {Efficient Sequence Modeling via Linear State Space Duality},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/efficient-sequence-modeling-via-linear-state-space-duality/rdr_f4b948ec3bbd4de6a76436a88ee9e22e},
  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_efficient_sequence_modeling_via_linear_s_f4b948ec_v1,
  title = {Efficient Sequence Modeling via Linear State Space Duality},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/efficient-sequence-modeling-via-linear-state-space-duality/rdr_f4b948ec3bbd4de6a76436a88ee9e22e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}