II · THE IDEA · ARTIFICIAL INTELLIGENCE
State Space Models for Long Sequences
▶ Listen · narrated
Attention grows expensive as context lengthens. A structured state-space layer offers another path: long-range memory through linear-time recurrence and an equivalent convolutional form for training.
At a glance
- Core idea
- A continuous-time state space turned into a discrete sequence layer
- Two views
- Same model as linear recurrence or as a global convolution
- Scaling
- Linear in sequence length for both training and inference paths
- Structure
- Constrained state matrices make long kernels tractable
- Target
- Long-range dependencies without quadratic attention cost
Think of a notebook with a fixed number of pages. Each time a new word arrives, you update those pages by a simple rule, then write down a summary line. You never rescan the whole book—only the notebook—so the work per word stays roughly constant even if the story is huge.
That notebook is the state. Structured state-space models define the update rule with ideas borrowed from control and signal processing: a hidden state changes smoothly under a matrix, driven by the input, and an output is read from the state. For computers, the continuous rule is turned into discrete steps that match token sequences.
Because the rule is linear and does not change with time, two shortcuts appear. You can apply it one token after another (the recurrence), which is handy when generating text. Or you can precompute how a single impulse would echo through the system and apply that echo pattern to the whole sequence at once (the convolution), which is handy when training on long passages in parallel. Structure on the state matrix keeps those computations affordable when sequences get very long.
Unlike attention, the model is not comparing every word to every other word. It is compressing the past into the notebook and letting the notebook’s dynamics decide what survives.
Start from a continuous-time linear state-space model: x'(t) = A x(t) + B u(t), y(t) = C x(t) + D u(t). Discretise with a suitable rule to obtain a sequence map x_k = Ā x_{k-1} + B̄ u_k, y_k = C x_k + D u_k. Unrolling yields a recurrence suitable for online inference with O(1) state updates per step relative to sequence length (cost depending on state size, not on k). The same LTI system has a convolutional representation y = K * u, where the kernel K is the impulse response built from powers of Ā and the input/output maps. Fast convolution then trains over full sequences without stepping through time in the implementation.
Naïve dense A makes forming or applying long kernels too expensive. Structured parameterisations of A—chosen so the continuous system can still represent long-range memory—reduce that cost and stabilise training, which is the practical core of the structured state-space (S4-style) layer. Stacked in depth with non-linearities between blocks, these layers act as sequence backbones or hybrids.
Limitations follow from the inductive bias. The basic layer is linear and time-invariant inside the SSM; content-dependent routing must come from surrounding non-linearities or from later extensions, not from pairwise attention scores inside the kernel itself. Quality depends on discretisation, state dimension and the chosen structure on A. Equivalence between recurrent and convolutional modes holds for the LTI core; modifications that break that structure need fresh analysis before you assume you can train in one mode and deploy in the other unchanged.
Look closer
One system, two algorithms
The underlying object is a linear state-space model: a hidden state evolves under a matrix A driven by the input, and an output is read out from that state. After discretisation, the same dynamics can be unrolled step by step as a recurrence, which is natural at generation time, or collapsed into a single convolutional kernel over the whole sequence, which suits parallel training. The mathematics is shared; only the evaluation order changes.
Why the state matrix must be structured
A naïve state-space layer on long sequences is still too costly if the state transition is a dense unstructured matrix. Structured parameterisations keep the continuous-time system expressive enough to remember distant signals while making the discrete kernel computable in near-linear time. Without that structure, the convolutional view loses its practical advantage over attention.
Memory lives in the kernel, not in pairwise scores
In attention, every position re-scores every other position. In a structured state-space layer, long-range influence is carried by the impulse response of the discretised system—the convolutional kernel—whose shape is determined by A, B and C. Distant tokens interact because the state was designed to retain them, not because a separate weight was learned for each pair.
The story
Sequence models face a stubborn tension. You want each new token to be able to depend on a long history, yet you also want training and inference to remain affordable as that history grows. Self-attention resolves the first demand directly—every position may look at every earlier one—but pays for it with cost and memory that grow quadratically with length. Recurrent networks keep cost linear, yet standard forms struggle to carry information across thousands of steps, and their step-by-step nature is awkward for modern parallel hardware during training.
Structured state-space models attack the same tension from a different tradition: continuous-time linear systems. In that setting a hidden state evolves under a differential equation driven by the input signal, and a linear map produces the output. The continuous system is then discretised so that it can consume a token sequence. Once discrete, two computationally useful identities appear. Unrolling the update gives a recurrence whose cost per step is independent of total length, which is attractive when producing tokens one by one. Expanding the same recurrence gives an explicit convolutional kernel; applying that kernel to the full input can be done with fast convolution, so training need not step through time.
The practical difficulty is that a generic state transition does not yield a cheap kernel when sequences are long and the state is wide. The structured state-space approach therefore restricts the continuous transition matrix to families that remain expressive—especially for retaining information over long horizons—while admitting stable, efficient algorithms for the discrete kernel. The layer that results can be dropped into deep networks much as a convolution or attention block would be, but its asymptotic behaviour with length follows the linear recurrence and convolution path rather than pairwise attention.
What you give up is the content-dependent routing that attention provides at every layer: the state-space kernel is linear and time-invariant in its basic form, so which past signals survive is governed by the learned system dynamics rather than by a fresh similarity score between every pair of positions. What you gain is a route to very long context in which the dominant costs scale with length rather than its square, and in which the same learned parameters serve both the recurrent and the convolutional implementations. The design is less a replacement for every attention layer than a distinct inductive bias: history compressed through a structured dynamical state, readable either online or in batch.
Why it mattered then
When structured state spaces were proposed for deep sequence modelling, the field had clear evidence that many tasks needed far longer context than ordinary recurrent nets handled reliably, while full attention on those lengths was already straining memory and compute. Benchmarks built around long-range dependencies made the gap visible: models either truncated history, paid quadratic cost, or failed to propagate signals across the full span. A layer that could be trained as a convolution yet run as a linear-time recurrence offered a concrete architectural alternative at the moment when sequence lengths in language, audio and other modalities were being pushed hard against hardware limits. It reframed long memory as a systems-identification problem—design a state that retains what matters—rather than only as a sparse or approximate attention problem.
Why it matters now
Context windows have continued to grow, and with them the bill for quadratic attention. Linear-time and sub-quadratic sequence layers therefore remain central to anyone training or serving models on long documents, high-rate sensor streams or multi-modal timelines. Structured state-space ideas, and the broader family of models they helped popularise, matter because they keep an explicit, inspectable notion of state: a fixed-size summary updated by each new input, paired with a convolutional view that hardware can train efficiently. Even where practitioners mix these layers with attention rather than discarding attention entirely, the lesson stands—long-range capacity need not always be bought with pairwise scores at every depth. Understanding the recurrence–convolution duality also clarifies later variants and hybrids that show up in open-weight stacks aimed at long context on limited hardware.
The surprising detail
The same learned parameters define both a step-by-step recurrent filter and a single global convolutional kernel. Training can use the convolutional form for parallelism; deployment can switch to the recurrent form without re-learning weights. That duality is not an implementation trick bolted on afterwards—it is a direct consequence of discretising a linear time-invariant state space. The modelling choice (a linear dynamical system) and the systems choice (two evaluation orders) are the same fact viewed twice.
What is disputed
The source material for this lesson is the structured state-space sequence model line of work centred on efficient long-sequence modelling with recurrent and convolutional dual forms. Specific benchmark scores, later model variants, and comparisons to subsequent architectures are outside the facts used here and should not be read into the prose. The second listed paper concerns numerical methods for diffusion models and is not relied on for the claims above.
Remember this
A structured state-space layer stores history in a dynamical state that can be read either as a linear recurrence or as one convolutional kernel—long range at linear cost, without pairwise attention.
Test yourself
You must train on sequences of tens of thousands of steps and then generate token-by-token with a small memory budget. In the basic structured state-space setup, which computational form do you want during training, which during generation, and what has to be true of the layer for those two forms to stay equivalent?
During training you want the convolutional form so the whole sequence can be processed in parallel with fast convolution. During generation you want the recurrent form so each new token updates a fixed-size state in time independent of total history length. Equivalence holds because both forms are discretisations of the same linear time-invariant state-space system: once A, B, C (and the discretisation) are fixed, the unrolled recurrence and the convolutional kernel implement the same map. If you broke time-invariance or the linearity of the state update in a way that invalidated that identity, you would no longer be free to switch views without changing the function.
Go deeper
- [2111.00396] Efficiently Modeling Long Sequences with Structured State Spaces · arxiv.org
- [2202.09778] Pseudo Numerical Methods for Diffusion Models on Manifolds · arxiv.org
Image: Original diagram, The Daily Triptych. Licence: Original work. Source.