Definition
State space model (SSM) in deep learning is a sequence layer built on the linear time-invariant system , , which maps a 1-D input signal to an output through an -dimensional latent state . Discretised with a step size , the same layer can be computed recurrently (one state update per token, like an RNN) or convolutionally (one long convolution over the whole sequence, like a CNN). A deep SSM stacks many such layers, one per channel, with nonlinear mixing in between.
State space models are old: they are the standard description of linear systems in control and signal processing, and the Kalman filter (Kalman, 1960) is inference in one. Their arrival in deep learning was driven by the long-range dependency problem. RNNs forget or explode over thousands of steps (see Vanilla RNN), attention costs in the sequence length (see Self-Attention), and convolutions have a fixed receptive field (see Temporal convolutional network (TCN)). A linear SSM has none of these limits: it carries a state, so its memory is unbounded, and its kernel is as long as the sequence.
Three papers by Albert Gu and colleagues made the idea work. HiPPO (Gu, Dao, Ermon, Rudra and Ré, NeurIPS 2020) derived matrices for which the state optimally memorises the input's history as coefficients of orthogonal polynomials. LSSL (Gu et al., NeurIPS 2021) used them in a deep linear state-space layer and showed that the recurrent and convolutional views coincide; replacing a random by the HiPPO matrix improved sequential MNIST from 60% to 98%. S4 (Gu, Goel and Ré, "Efficiently Modeling Long Sequences with Structured State Spaces", ICLR 2022) found a structure for that makes computing the kernel fast and stable, and was the first model to solve the 16,384-step Path-X task of the Long Range Arena. Diagonal variants (DSS, S4D, S5) and then the selective Mamba followed.
Continuous model and discretisation
- one input channel; a layer with channels runs independent SSMs
- the latent state ( = state size, typically 16 to 256)
- state matrix: its eigenvalues set the timescales and frequencies of the memory; stability needs
- input map , readout , and a skip term (a scalar, often treated as a residual connection)
A sequence is treated as samples of a continuous signal. Integrating the ODE over one step, with the input held constant inside the step (zero-order hold, ZOH), or approximating the integral by the trapezoid rule (bilinear transform), gives a discrete linear recurrence. S4 used bilinear; DSS, S4D's ZOH variant and Mamba use ZOH.
- step size (learned, per channel). Small means each token is a short slice of time: slow dynamics, long memory. Large : fast dynamics, short memory
- discrete parameters. If then every eigenvalue of is inside the unit circle, for any , under both rules
- for diagonal just per entry, which is why diagonal SSMs prefer ZOH
Two views of the same layer
Unroll the recurrence from : . The output is therefore a causal convolution of the input with a fixed kernel:
- the SSM convolution kernel, as long as the sequence
- computed for all at once with an FFT in : the training mode, parallel like a CNN
- the whole Jacobian is the kernel: no nonlinearity inside, so gradients through time are exactly powers of , controlled by its eigenvalues
So an SSM layer trains like a convolution (parallel over , no backpropagation through a loop) and generates like an RNN ( work and memory per new token, no growing cache). That duality is the central idea. It holds only because are the same at every step (the system is linear time-invariant, LTI); Mamba gives up exactly this property to gain selectivity.
The gradient expression also explains the design choices. involves : with it explodes, with the kernel and its gradient die after a few steps. Parameterising and keeps every , and spreading and the eigenvalues over several orders of magnitude gives each layer kernels with many timescales.
At a glance
- Parameters per channel
- ( values when diagonal), , ( each), ,
- Training cost
- kernel (diagonal, Vandermonde) or (S4), then FFT convolution
- Generation cost
- per token and channel, constant memory: the state is the whole cache
- Nonlinearity
- none inside the SSM; added between layers (GELU, gating, MLPs) as in any deep stack
- Typical init
- HiPPO-LegS (S4), S4D-Lin , S4D-Real ; log-uniform in
- Benchmark
- Long Range Arena (Tay et al., ICLR 2021): six tasks with 1K–16K-token inputs
HiPPO: choosing A so the state remembers
A random gives a state that forgets quickly and arbitrarily. HiPPO ("high-order polynomial projection operators") asks instead: which make the coefficients of the best polynomial approximation of the whole history ? For the scaled Legendre measure, which weights all of the past uniformly, the answer is the HiPPO-LegS matrix used to initialise S4:
- state indices : is the coefficient of the -th Legendre polynomial
- each coefficient is driven by the lower-order ones; the diagonal gives decay rates that grow with
The HiPPO matrix is not diagonal, and its powers are numerically explosive to compute naively. S4's contribution was to write it as normal plus low-rank (NPLR), with rank 1 for LegS, and to compute the kernel through its generating function at the roots of unity: a Cauchy kernel plus a Woodbury correction, followed by an inverse FFT. Each recurrent step costs and the kernel .
Diagonal SSMs: DSS, S4D, S5
Gupta, Gu and Berant (DSS, NeurIPS 2022) found that simply dropping the low-rank term and using a diagonal complex works about as well. Gu, Gupta, Goel and Ré (S4D, NeurIPS 2022) explained why: the diagonal part of HiPPO-LegS's diagonal-plus-low-rank form recovers the same kernel as S4 in the limit of infinite state size. They proposed simple initialisations, S4D-Lin (damped Fourier modes, as in the figure) and S4D-Inv. With diagonal the kernel is a Vandermonde product, , a few lines of code. Smith, Warrington and Linderman (S5, ICLR 2023) replaced the single-input SSMs by one multi-input multi-output SSM with a diagonal , computed with a parallel scan instead of a convolution, the same primitive Mamba uses.
| model | ListOps | Text | Retrieval | Image | Pathfinder | Path-X | Avg |
|---|---|---|---|---|---|---|---|
| Transformer | 36.37 | 64.27 | 57.46 | 42.44 | 71.40 | ✗ | 53.66 |
| S4 (LegS) | 59.60 | 86.82 | 90.90 | 88.65 | 94.20 | 96.35 | 86.09 |
| S4D-LegS | 60.47 | 86.18 | 89.46 | 88.19 | 93.06 | 91.95 | 84.89 |
| S5 | 62.15 | 89.31 | 91.40 | 88.00 | 95.33 | 98.58 | 87.46 |
Worked example: a scalar SSM
Take , , , , , step , and input .
Discretise, build the kernel, and run both views (checked in Node with the figure's library)
- 1ZOH: , . Bilinear: , . The two rules differ only at second order in .
- 2ZOH kernel : .
- 3Recurrence: , , , .
- 4Convolution: . Same number, as it must be. With bilinear the outputs are .
1import math, torch, torch.nn as nn23def s4d_kernel(log_dt, A, C, L):4 """ZOH kernel of H diagonal SSMs with B = 1. A, C: (H, M) complex. Returns (H, L) real."""5 dtA = log_dt.exp()[:, None] * A # (H, M)6 Bbar = (dtA.exp() - 1) / A # (exp(dt*A) - 1) / A * B7 ell = torch.arange(L, device=A.device, dtype=torch.float32)8 powers = (dtA[..., None] * ell).exp() # Abar^l, (H, M, L)9 return 2 * torch.einsum("hm,hml->hl", C * Bbar, powers).real # conjugate pairs -> 2 Re1011def fft_conv(u, K): # u: (B, H, L), K: (H, L)12 L = u.shape[-1]13 return torch.fft.irfft(torch.fft.rfft(u, n=2 * L) * torch.fft.rfft(K, n=2 * L), n=2 * L)[..., :L]1415class S4DLayer(nn.Module):16 def __init__(self, H, N=64, dt_min=1e-3, dt_max=1e-1):17 super().__init__()18 M = N // 2 # N real states = M complex conjugate pairs19 self.log_dt = nn.Parameter(torch.rand(H) * (math.log(dt_max) - math.log(dt_min)) + math.log(dt_min))20 self.log_neg_re = nn.Parameter(torch.full((H, M), math.log(0.5))) # Re A = -0.521 self.im = nn.Parameter(math.pi * torch.arange(M, dtype=torch.float32).repeat(H, 1)) # S4D-Lin22 self.C = nn.Parameter(torch.randn(H, M, dtype=torch.cfloat))23 self.D = nn.Parameter(torch.randn(H))24 def A(self):25 return torch.complex(-self.log_neg_re.exp(), self.im) # Re A < 0 always: stable26 def forward(self, u): # u: (B, H, L), parallel "training" mode27 K = s4d_kernel(self.log_dt, self.A(), self.C, u.shape[-1])28 return fft_conv(u, K) + self.D[:, None] * u2930layer = S4DLayer(H=4, N=16)31u = torch.randn(2, 4, 256)32with torch.no_grad():33 y_conv = layer(u)34 # recurrent "generation" mode: O(N) per step, constant memory35 A = layer.A(); dtA = layer.log_dt.exp()[:, None] * A36 Abar, Bbar = dtA.exp(), (dtA.exp() - 1) / A37 x = torch.zeros(2, 4, A.shape[-1], dtype=torch.cfloat)38 ys = []39 for k in range(u.shape[-1]):40 x = Abar * x + Bbar * u[..., k, None]41 ys.append(2 * (layer.C * x).sum(-1).real + layer.D * u[..., k])42 y_rec = torch.stack(ys, dim=-1)43print((y_conv - y_rec).abs().max()) # float32 rounding level: the two views agreeUse when
- +Train in parallel (convolution) and generate in O(N) per token (recurrence) with the same parameters
- +Unbounded memory in principle; kernels as long as the sequence
- +Linear dynamics: exact, well-conditioned gradients when Re A < 0
- +Principled initialisation (HiPPO, S4D) and a continuous-time view: Δ handles sampling-rate changes
- +State of the art on Long Range Arena and raw audio at the time (S4, S5)
Avoid when
- −Time-invariant: cannot select or ignore inputs by content
- −Kernel computation needs care: structured A (S4), complex arithmetic, FFT padding
- −Weaker than attention on language modelling unless made selective (Mamba) or hybridised
- −Nonlinearity lives only between layers, so depth and mixing layers do the heavy lifting
Check yourself
Why can an LTI SSM layer be trained with an FFT convolution but a Mamba layer cannot?
Check yourself
A diagonal SSM has a mode with a = −0.5 and is discretised by ZOH with Δ = 0.1. After how many steps has that mode decayed to 1/e?
Remember
- ✓Continuous , ; ZOH gives , ; bilinear is the trapezoid alternative.
- ✓Same layer, two views: recurrence for generation, convolution with for parallel training.
- ✓Stability and memory come from the eigenvalues: keeps for every , and sets the timescale.
- ✓HiPPO matrices make the state a polynomial summary of the past; S4 computes their kernels fast via NPLR structure, Cauchy kernels and FFTs.
- ✓Diagonal SSMs (DSS, S4D, S5) are nearly as good and much simpler; S4 and S5 reach 86–87% average on Long Range Arena versus 54% for a Transformer.