State space models (SSMs)

A linear ODE x′ = Ax + Bu, y = Cx + Du, discretised with a step Δ, is both an RNN (x_k = Āx_{k−1} + B̄u_k) and a convolution with kernel (CB̄, CĀB̄, C²B̄, …). S4 made it trainable on 16k-step sequences with HiPPO initialisation and structured A.

15 min read1184 wordsadvanced0 viewsupdated 2026-10-12

Definition

State space model (SSM) in deep learning is a sequence layer built on the linear time-invariant system x′(t)=Ax(t)+Bu(t)x'(t)=Ax(t)+Bu(t), y(t)=Cx(t)+Du(t)y(t)=Cx(t)+Du(t), which maps a 1-D input signal uu to an output yy through an NN-dimensional latent state xx. Discretised with a step size Δ\Delta, 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 O(L2)O(L^2) 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 AA 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 AA 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 AA 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

x′(t)=A x(t)+B u(t),y(t)=C x(t)+D u(t)x'(t)=A\,x(t)+B\,u(t),\qquad y(t)=C\,x(t)+D\,u(t)
u(t)∈Ru(t)\in\mathbb R
one input channel; a layer with HH channels runs HH independent SSMs
x(t)∈RNx(t)\in\mathbb R^N
the latent state (NN = state size, typically 16 to 256)
A∈RN×NA\in\mathbb R^{N\times N}
state matrix: its eigenvalues set the timescales and frequencies of the memory; stability needs Re⁡λ(A)<0\operatorname{Re}\lambda(A)<0
B,  C,  DB,\;C,\;D
input map N×1N\times1, readout 1×N1\times N, and a skip term DD (a scalar, often treated as a residual connection)

A sequence u0,u1,…u_0,u_1,\dots is treated as samples uk=u(kΔ)u_k=u(k\Delta) 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.

xk=Aˉ xk−1+Bˉ uk,yk=Cxk+Duk;Aˉ=eΔA,    Bˉ=(ΔA)−1(eΔA−I) ΔB⏟ZOHAˉ=(I−Δ2A)−1(I+Δ2A),    Bˉ=(I−Δ2A)−1ΔB⏟bilinearx_k=\bar A\,x_{k-1}+\bar B\,u_k,\quad y_k=C x_k+Du_k;\qquad \underbrace{\bar A=e^{\Delta A},\;\; \bar B=(\Delta A)^{-1}\big(e^{\Delta A}-I\big)\,\Delta B}_{\text{ZOH}}\qquad \underbrace{\bar A=\big(I-\tfrac{\Delta}{2}A\big)^{-1}\big(I+\tfrac{\Delta}{2}A\big),\;\; \bar B=\big(I-\tfrac{\Delta}{2}A\big)^{-1}\Delta B}_{\text{bilinear}}
Δ\Delta
step size (learned, per channel). Small Δ\Delta means each token is a short slice of time: slow dynamics, long memory. Large Δ\Delta: fast dynamics, short memory
Aˉ,  Bˉ\bar A,\;\bar B
discrete parameters. If Re⁡λ(A)<0\operatorname{Re}\lambda(A)<0 then every eigenvalue of Aˉ\bar A is inside the unit circle, for any Δ>0\Delta>0, under both rules
eΔAe^{\Delta A}
for diagonal AA just eΔane^{\Delta a_n} per entry, which is why diagonal SSMs prefer ZOH

Two views of the same layer

Unroll the recurrence from x−1=0x_{-1}=0: xk=∑j=0kAˉ jBˉ uk−jx_k=\sum_{j=0}^{k}\bar A^{\,j}\bar B\,u_{k-j}. The output is therefore a causal convolution of the input with a fixed kernel:

y=Kˉ∗u+Du,Kˉ=(CBˉ,  CAˉBˉ,  CAˉ2Bˉ,  …,  CAˉL−1Bˉ)∈RL,∂yk∂uk−j=Kˉj=CAˉ jBˉy=\bar K*u+Du,\qquad \bar K=\big(C\bar B,\;C\bar A\bar B,\;C\bar A^2\bar B,\;\dots,\;C\bar A^{L-1}\bar B\big)\in\mathbb R^L,\qquad \frac{\partial y_k}{\partial u_{k-j}}=\bar K_j=C\bar A^{\,j}\bar B
Kˉ\bar K
the SSM convolution kernel, as long as the sequence LL
Kˉ∗u\bar K*u
computed for all kk at once with an FFT in O(Llog⁡L)O(L\log L): the training mode, parallel like a CNN
∂yk/∂uk−j\partial y_k/\partial u_{k-j}
the whole Jacobian is the kernel: no nonlinearity inside, so gradients through time are exactly powers of Aˉ\bar A, controlled by its eigenvalues

So an SSM layer trains like a convolution (parallel over LL, no backpropagation through a loop) and generates like an RNN (O(N)O(N) work and memory per new token, no growing cache). That duality is the central idea. It holds only because Aˉ,Bˉ,C\bar A,\bar B,C 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. ∂Kˉj/∂Aˉ\partial \bar K_j/\partial\bar A involves j Aˉ j−1j\,\bar A^{\,j-1}: with ∣λ(Aˉ)∣>1|\lambda(\bar A)|>1 it explodes, with ∣λ∣≪1|\lambda|\ll1 the kernel and its gradient die after a few steps. Parameterising Re⁡(an)=−exp⁡(⋅)<0\operatorname{Re}(a_n)=-\exp(\cdot)<0 and Δ=exp⁡(log⁡Δ)>0\Delta=\exp(\log\Delta)>0 keeps every ∣aˉn∣=eΔRe⁡an<1|\bar a_n|=e^{\Delta\operatorname{Re}a_n}<1, and spreading Δ\Delta and the eigenvalues over several orders of magnitude gives each layer kernels with many timescales.

At a glance

Parameters per channel
AA (NN values when diagonal), BB, CC (NN each), DD, Δ\Delta
Training cost
kernel O(NL)O(N L) (diagonal, Vandermonde) or O~(N+L)\tilde O(N+L) (S4), then FFT convolution O(Llog⁡L)O(L\log L)
Generation cost
O(N)O(N) per token and channel, constant memory: the state xkx_k 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 an=−12+iπna_n=-\tfrac12+i\pi n, S4D-Real an=−(n+1)a_n=-(n+1); Δ\Delta log-uniform in [10−3,10−1][10^{-3},10^{-1}]
Benchmark
Long Range Arena (Tay et al., ICLR 2021): six tasks with 1K–16K-token inputs
kernel Kₗ = 2·Re Σ Cₙ Āₙˡ B̄ₙ (max |K| 0.254)1/e after 40 stepsinput u (pulses) and output y: ━ recurrence ● convolutiontime step k → (y scale ±0.27, input drawn to its own scale)discrete poles Āₙ● ZOH ○ bilinear · unit circleΔ (step)0.050state N = 2M8max |Āₙ|0.9753memory 1/e40.0 stepsfastest mode0.47 rad/step discrete0.47 rad/stepmax |y_rec − y_conv|1.1e-16all modes below π rad/stepS4D-Lin: Aₙ = −½ + iπn, Bₙ = 1, C fixed (seed 7) · y = K * u equals the recurrence xₖ = Āxₖ₋₁ + B̄uₖ
discretisemodes M
input
Δ is log-scaled: small Δ = slow, long memory; large Δ = fast, short memory.
fig.A diagonal SSM with S4D-Lin initialisation (Aₙ = −½ + iπn, Bₙ = 1, fixed random C). Top: the kernel K over 128 steps; middle: the output computed as a recurrence (line) and as a convolution with that kernel (dots), which agree to about 1e-16; right: the discrete poles Āₙ in the unit circle (filled: current rule, hollow: the other rule). At the default Δ = 0.05 with 8 states, |Ā| = e^{−Δ/2} = 0.9753 and the slowest mode decays by 1/e in 40 steps; Δ = 0.2 shortens that to 10 steps and Δ = 0.01 stretches it to 200, longer than the window. The poles always stay inside the circle. With 8 modes and Δ = 0.2 the fastest mode should turn 4.40 rad per step: ZOH aliases it to 1.89 rad (shown in red), while bilinear warps it to 2.29 rad and pushes the pole towards the circle (max |Ā| 0.983).

HiPPO: choosing A so the state remembers

A random AA gives a state that forgets quickly and arbitrarily. HiPPO ("high-order polynomial projection operators") asks instead: which A,BA,B make x(t)x(t) the coefficients of the best polynomial approximation of the whole history u(s), s≤tu(s),\ s\le t? For the scaled Legendre measure, which weights all of the past uniformly, the answer is the HiPPO-LegS matrix used to initialise S4:

Ank=−{(2n+1)1/2(2k+1)1/2n>kn+1n=k0n<kBn=(2n+1)1/2A_{nk}=-\begin{cases}(2n+1)^{1/2}(2k+1)^{1/2} & n>k\\ n+1 & n=k\\ 0 & n<k\end{cases}\qquad B_n=(2n+1)^{1/2}
n,kn,k
state indices 0,…,N−10,\dots,N-1: xn(t)x_n(t) is the coefficient of the nn-th Legendre polynomial
lower triangular\text{lower triangular}
each coefficient is driven by the lower-order ones; the diagonal −(n+1)-(n+1) gives decay rates that grow with nn

The HiPPO matrix is not diagonal, and its powers Aˉ j\bar A^{\,j} are numerically explosive to compute naively. S4's contribution was to write it as normal plus low-rank (NPLR), A=VΛV∗−PQ⊤A=V\Lambda V^*-PQ^\top 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 O(N)O(N) and the kernel O~(N+L)\tilde O(N+L).

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 AA 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 an=−12+iπna_n=-\tfrac12+i\pi n (damped Fourier modes, as in the figure) and S4D-Inv. With diagonal AA the kernel is a Vandermonde product, Kˉℓ=2Re⁡∑nCnBˉnaˉnℓ\bar K_\ell=2\operatorname{Re}\sum_n C_n\bar B_n\bar a_n^{\ell}, a few lines of code. Smith, Warrington and Linderman (S5, ICLR 2023) replaced the HH single-input SSMs by one multi-input multi-output SSM with a diagonal AA, computed with a parallel scan instead of a convolution, the same primitive Mamba uses.

modelListOpsTextRetrievalImagePathfinderPath-XAvg
Transformer36.3764.2757.4642.4471.40✗53.66
S4 (LegS)59.6086.8290.9088.6594.2096.3586.09
S4D-LegS60.4786.1889.4688.1993.0691.9584.89
S562.1589.3191.4088.0095.3398.5887.46
Long Range Arena test accuracy (%). Transformer and S4 rows: S4 paper, Table 4 (arXiv version with updated S4 results; the ICLR version reported an 80.48 average and 88% on Path-X). S4D-LegS and S5 rows: S5 paper, Table 1. ✗ = chance level

Worked example: a scalar SSM

Take N=1N=1, a=−1a=-1, b=1b=1, c=1c=1, D=0D=0, step Δ=0.5\Delta=0.5, and input u=(1, 0, 2, 1)u=(1,\,0,\,2,\,1).

Discretise, build the kernel, and run both views (checked in Node with the figure's library)

  1. 1ZOH: aˉ=e−0.5=0.60653\bar a=e^{-0.5}=0.60653, bˉ=(e−0.5−1)/(−1)=0.39347\bar b=(e^{-0.5}-1)/(-1)=0.39347. Bilinear: aˉ=(1−0.25)/(1+0.25)=0.6\bar a=(1-0.25)/(1+0.25)=0.6, bˉ=0.5/1.25=0.4\bar b=0.5/1.25=0.4. The two rules differ only at second order in Δ\Delta.
  2. 2ZOH kernel Kˉj=c aˉ jbˉ\bar K_j=c\,\bar a^{\,j}\bar b: (0.39347,  0.23865,  0.14475,  0.08779)(0.39347,\;0.23865,\;0.14475,\;0.08779).
  3. 3Recurrence: x0=0.39347x_0=0.39347, x1=0.60653⋅0.39347=0.23865x_1=0.60653\cdot0.39347=0.23865, x2=0.60653⋅0.23865+0.39347⋅2=0.93169x_2=0.60653\cdot0.23865+0.39347\cdot2=0.93169, x3=0.60653⋅0.93169+0.39347=0.95857x_3=0.60653\cdot0.93169+0.39347=0.95857.
  4. 4Convolution: y3=Kˉ0u3+Kˉ1u2+Kˉ2u1+Kˉ3u0=0.39347+0.47730+0+0.08779=0.95857y_3=\bar K_0u_3+\bar K_1u_2+\bar K_2u_1+\bar K_3u_0=0.39347+0.47730+0+0.08779=0.95857. Same number, as it must be. With bilinear the outputs are (0.4,  0.24,  0.944,  0.9664)(0.4,\;0.24,\;0.944,\;0.9664).
python
1import math, torch, torch.nn as nn
2
3def 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 * B
7 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 Re
10
11def 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]
14
15class 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 pairs
19 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.5
21 self.im = nn.Parameter(math.pi * torch.arange(M, dtype=torch.float32).repeat(H, 1)) # S4D-Lin
22 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: stable
26 def forward(self, u): # u: (B, H, L), parallel "training" mode
27 K = s4d_kernel(self.log_dt, self.A(), self.C, u.shape[-1])
28 return fft_conv(u, K) + self.D[:, None] * u
29
30layer = 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 memory
35 A = layer.A(); dtA = layer.log_dt.exp()[:, None] * A
36 Abar, Bbar = dtA.exp(), (dtA.exp() - 1) / A
37 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 agree
An S4D-style diagonal SSM layer: kernel by Vandermonde product, FFT convolution, and a recurrent-mode check

Use 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 x′=Ax+Bux'=Ax+Bu, y=Cx+Duy=Cx+Du; ZOH gives Aˉ=eΔA\bar A=e^{\Delta A}, Bˉ=(ΔA)−1(eΔA−I)ΔB\bar B=(\Delta A)^{-1}(e^{\Delta A}-I)\Delta B; bilinear is the trapezoid alternative.
  • ✓Same layer, two views: recurrence xk=Aˉxk−1+Bˉukx_k=\bar Ax_{k-1}+\bar Bu_k for generation, convolution with Kˉ=(CBˉ,CAˉBˉ,… )\bar K=(C\bar B,C\bar A\bar B,\dots) for parallel training.
  • ✓Stability and memory come from the eigenvalues: Re⁡a<0\operatorname{Re}a<0 keeps ∣aˉ∣<1|\bar a|<1 for every Δ\Delta, and Δ\Delta 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.
← back to Deep Learning roadmap