State-Space Models (SSMs)
Definition
A state-space model for sequences carries a fixed-size hidden state forward one token at a time via a linear recurrence , — time and constant state by construction. The key structural fact is a duality: when the dynamics are time-invariant (LTI), the recurrence unrolls into a single long convolution, so the model trains in parallel like a Transformer and runs inference as a cheap recurrence. S4 (Gu, Goel, Ré, 2021; arXiv:2111.00396) made this competitive on long-range tasks; it is the anchor of the attention-alternative line that leads to Mamba.
Key math / How it works
A continuous linear SSM , is discretized (zero-order hold, step ):
Conv ⇄ recurrence duality. With constant across time, unrolling gives — a convolution with one long kernel:
So you train as a convolution (fully parallel, via FFT) and run inference as a recurrence ( state per step). The obstacle was that naive explodes/vanishes/is costly; S4’s contribution was a structured (diagonal-plus-low-rank / HiPPO, arXiv:2008.07669) parameterization of that makes the long kernel stable and cheap — enough to beat Transformers on Long Range Arena.
Cost. Train/prefill scan or FFT-conv; inference state per layer, constant in .
Why it matters
An SSM’s state size is fixed no matter the context, so generation is a fixed-cost matrix–vector update and memory never grows — the opposite of attention, whose KV cache grows and dominates long-context inference. That constant-state, linear-time profile made SSMs the serious challenger to attention on very long sequences. The limitation of LTI SSMs — the same dynamics at every position, so no content-based routing — is exactly what Mamba’s selectivity fixes.
Taught in
- 07-linear-and-subquadratic — §3.3 discretization, duality, S4.
See also
- mamba — the selective (input-dependent) successor
- linear-attention — the kernel-trick route to the same constant-state win
- kv-cache · attention-glossary · attention-mechanisms