# 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.

Source: https://www.mlfoundry.in/learn/state-space-models-ssms  
Section: Deep Learning › Recurrent Neural Networks and Sequence Models  
Level: advanced · 15 min read · updated 2026-10-12

**State space model:** (SSM) in deep learning is a sequence layer built on the linear time-invariant system $x'(t)=Ax(t)+Bu(t)$, $y(t)=Cx(t)+Du(t)$, which maps a 1-D input signal $u$ to an output $y$ through an $N$-dimensional latent state $x$. 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(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 $A$ 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 $A$ 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 $A$ 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),\qquad y(t)=C\,x(t)+D\,u(t)
$$

- $u(t)\in\mathbb R$: one input channel; a layer with $H$ channels runs $H$ independent SSMs
- $x(t)\in\mathbb R^N$: the latent state ($N$ = state size, typically 16 to 256)
- $A\in\mathbb R^{N\times N}$: state matrix: its eigenvalues set the timescales and frequencies of the memory; stability needs $\operatorname{Re}\lambda(A)<0$
- $B,\;C,\;D$: input map $N\times1$, readout $1\times N$, and a skip term $D$ (a scalar, often treated as a residual connection)

A sequence $u_0,u_1,\dots$ is treated as samples $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.

$$
x_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
- $\bar A,\;\bar B$: discrete parameters. If $\operatorname{Re}\lambda(A)<0$ then every eigenvalue of $\bar A$ is inside the unit circle, for **any** $\Delta>0$, under both rules
- $e^{\Delta A}$: for diagonal $A$ just $e^{\Delta a_n}$ per entry, which is why diagonal SSMs prefer ZOH

## Two views of the same layer

Unroll the recurrence from $x_{-1}=0$: $x_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=\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
$$

- $\bar K$: the SSM convolution kernel, as long as the sequence $L$
- $\bar K*u$: computed for all $k$ at once with an FFT in $O(L\log L)$: the **training** mode, parallel like a CNN
- $\partial y_k/\partial u_{k-j}$: the whole Jacobian is the kernel: no nonlinearity inside, so gradients through time are exactly powers of $\bar A$, controlled by its eigenvalues

So an SSM layer **trains like a convolution** (parallel over $L$, no backpropagation through a loop) and **generates like an RNN** ($O(N)$ work and memory per new token, no growing cache). That duality is the central idea. It holds only because $\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. $\partial \bar K_j/\partial\bar A$ involves $j\,\bar A^{\,j-1}$: with $|\lambda(\bar A)|>1$ it explodes, with $|\lambda|\ll1$ the kernel and its gradient die after a few steps. Parameterising $\operatorname{Re}(a_n)=-\exp(\cdot)<0$ and $\Delta=\exp(\log\Delta)>0$ keeps every $|\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:** $A$ ($N$ values when diagonal), $B$, $C$ ($N$ each), $D$, $\Delta$
- **Training cost:** kernel $O(N L)$ (diagonal, Vandermonde) or $\tilde O(N+L)$ (S4), then FFT convolution $O(L\log L)$
- **Generation cost:** $O(N)$ per token and channel, constant memory: the state $x_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 $a_n=-\tfrac12+i\pi n$, S4D-Real $a_n=-(n+1)$; $\Delta$ log-uniform in $[10^{-3},10^{-1}]$
- **Benchmark:** Long Range Arena (Tay et al., ICLR 2021): six tasks with 1K–16K-token inputs

> Figure: 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 $A$ gives a state that forgets quickly and arbitrarily. HiPPO ("high-order polynomial projection operators") asks instead: which $A,B$ make $x(t)$ the coefficients of the best polynomial approximation of the whole history $u(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:

$$
A_{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,k$: state indices $0,\dots,N-1$: $x_n(t)$ is the coefficient of the $n$-th Legendre polynomial
- $\text{lower triangular}$: each coefficient is driven by the lower-order ones; the diagonal $-(n+1)$ gives decay rates that grow with $n$

The HiPPO matrix is not diagonal, and its powers $\bar A^{\,j}$ are numerically explosive to compute naively. S4's contribution was to write it as **normal plus low-rank** (NPLR), $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)$ and the kernel $\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 $A$ 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** $a_n=-\tfrac12+i\pi n$ (damped Fourier modes, as in the figure) and **S4D-Inv**. With diagonal $A$ the kernel is a Vandermonde product, $\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 $H$ single-input SSMs by one multi-input multi-output SSM with a diagonal $A$, computed with a **parallel scan** instead of a convolution, the same primitive Mamba uses.

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

| 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 $N=1$, $a=-1$, $b=1$, $c=1$, $D=0$, step $\Delta=0.5$, and input $u=(1,\,0,\,2,\,1)$.

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

1. ZOH: $\bar a=e^{-0.5}=0.60653$, $\bar b=(e^{-0.5}-1)/(-1)=0.39347$. Bilinear: $\bar a=(1-0.25)/(1+0.25)=0.6$, $\bar b=0.5/1.25=0.4$. The two rules differ only at second order in $\Delta$.
2. ZOH kernel $\bar K_j=c\,\bar a^{\,j}\bar b$: $(0.39347,\;0.23865,\;0.14475,\;0.08779)$.
3. Recurrence: $x_0=0.39347$, $x_1=0.60653\cdot0.39347=0.23865$, $x_2=0.60653\cdot0.23865+0.39347\cdot2=0.93169$, $x_3=0.60653\cdot0.93169+0.39347=0.95857$.
4. Convolution: $y_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)$.

```python
import math, torch, torch.nn as nn

def s4d_kernel(log_dt, A, C, L):
    """ZOH kernel of H diagonal SSMs with B = 1. A, C: (H, M) complex. Returns (H, L) real."""
    dtA = log_dt.exp()[:, None] * A                      # (H, M)
    Bbar = (dtA.exp() - 1) / A                           # (exp(dt*A) - 1) / A * B
    ell = torch.arange(L, device=A.device, dtype=torch.float32)
    powers = (dtA[..., None] * ell).exp()                # Abar^l, (H, M, L)
    return 2 * torch.einsum("hm,hml->hl", C * Bbar, powers).real   # conjugate pairs -> 2 Re

def fft_conv(u, K):                                      # u: (B, H, L), K: (H, L)
    L = u.shape[-1]
    return torch.fft.irfft(torch.fft.rfft(u, n=2 * L) * torch.fft.rfft(K, n=2 * L), n=2 * L)[..., :L]

class S4DLayer(nn.Module):
    def __init__(self, H, N=64, dt_min=1e-3, dt_max=1e-1):
        super().__init__()
        M = N // 2                                       # N real states = M complex conjugate pairs
        self.log_dt = nn.Parameter(torch.rand(H) * (math.log(dt_max) - math.log(dt_min)) + math.log(dt_min))
        self.log_neg_re = nn.Parameter(torch.full((H, M), math.log(0.5)))       # Re A = -0.5
        self.im = nn.Parameter(math.pi * torch.arange(M, dtype=torch.float32).repeat(H, 1))  # S4D-Lin
        self.C = nn.Parameter(torch.randn(H, M, dtype=torch.cfloat))
        self.D = nn.Parameter(torch.randn(H))
    def A(self):
        return torch.complex(-self.log_neg_re.exp(), self.im)   # Re A < 0 always: stable
    def forward(self, u):                                # u: (B, H, L), parallel "training" mode
        K = s4d_kernel(self.log_dt, self.A(), self.C, u.shape[-1])
        return fft_conv(u, K) + self.D[:, None] * u

layer = S4DLayer(H=4, N=16)
u = torch.randn(2, 4, 256)
with torch.no_grad():
    y_conv = layer(u)
    # recurrent "generation" mode: O(N) per step, constant memory
    A = layer.A(); dtA = layer.log_dt.exp()[:, None] * A
    Abar, Bbar = dtA.exp(), (dtA.exp() - 1) / A
    x = torch.zeros(2, 4, A.shape[-1], dtype=torch.cfloat)
    ys = []
    for k in range(u.shape[-1]):
        x = Abar * x + Bbar * u[..., k, None]
        ys.append(2 * (layer.C * x).sum(-1).real + layer.D * u[..., k])
    y_rec = torch.stack(ys, dim=-1)
print((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

> **Unconstrained A or Δ:** If $\operatorname{Re}(a_n)$ is a free parameter it can drift positive, and then $|\bar a_n|>1$ and the kernel explodes as $|\bar a_n|^L$ over a 16k-step sequence. Parameterise $\operatorname{Re}a_n=-e^{\theta}$ and $\Delta=e^{\phi}$ as in the code. S4 also caps the learning rate of the SSM parameters ($A$, $B$, $C$, $\Delta$) at 0.001 for stability.

> **Circular FFT convolution:** An FFT of length $L$ computes a **circular** convolution: the tail of the kernel wraps around and lets late inputs leak into early outputs, which breaks causality. Zero-pad both signals to length $2L$ (`n=2 * L` in the code) and keep the first $L$ outputs.

> **Δ is a learned timescale:** Changing $\Delta$ is like changing the sampling rate: the kernel is the continuous impulse response sampled every $\Delta$, so halving $\Delta$ stretches it over twice as many tokens (memory $2/\Delta$ steps for $\operatorname{Re}a=-\tfrac12$ in the figure). A deep SSM initialises $\Delta$ log-uniformly over two orders of magnitude so that different channels watch different timescales, and the continuous view lets a trained model be run at a different sampling rate by rescaling $\Delta$ (S4's speech-classification table includes a test at half the training sampling rate, handled by changing $\Delta$).

> **Limits of LTI SSMs:** Because $\bar K$ is fixed, an LTI SSM treats every token the same way: it cannot decide, based on content, to ignore a filler token or to reset its state. Gated hybrids (H3, Hyena) narrowed the gap to attention on language but did not close it. **Mamba** makes $\Delta$, $B$ and $C$ functions of the input, which costs the convolution view and is computed with a hardware-aware parallel scan instead.

**Strengths**

- 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)

**Limitations**

- 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

**Question:** Why can an LTI SSM layer be trained with an FFT convolution but a Mamba layer cannot?

- A. Mamba uses a larger state size
- B. In an LTI SSM, Ā, B̄ and C are the same at every step, so the output is a convolution with one kernel (CB̄, CĀB̄, …); Mamba's parameters depend on the token, so there is no single kernel
- C. Mamba uses ZOH and FFTs require the bilinear transform
- D. FFTs only work for real-valued A

**Answer:** B. In an LTI SSM, Ā, B̄ and C are the same at every step, so the output is a convolution with one kernel (CB̄, CĀB̄, …); Mamba's parameters depend on the token, so there is no single kernel — Unrolling $x_k=\bar Ax_{k-1}+\bar Bu_k$ gives $y_k=\sum_j C\bar A^{\,j}\bar B\,u_{k-j}$ only when the matrices do not depend on $k$. With input-dependent $\bar A_k$ the weight of $u_s$ in $y_k$ is $C_k\bar A_k\cdots\bar A_{s+1}\bar B_s$, which differs for every pair $(k,s)$.

**Question:** 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?

- A. 2
- B. 5
- C. 20
- D. 200

**Answer:** C. 20 — $|\bar a|=e^{\Delta\operatorname{Re}a}=e^{-0.05}$, so $|\bar a|^\ell=e^{-1}$ at $\ell=1/0.05=20$ steps. In general the memory is $1/(\Delta|\operatorname{Re}a|)$ steps: smaller $\Delta$, longer memory.

**Key points**

- Continuous $x'=Ax+Bu$, $y=Cx+Du$; ZOH gives $\bar A=e^{\Delta A}$, $\bar B=(\Delta A)^{-1}(e^{\Delta A}-I)\Delta B$; bilinear is the trapezoid alternative.
- Same layer, two views: recurrence $x_k=\bar Ax_{k-1}+\bar Bu_k$ for generation, convolution with $\bar K=(C\bar B,C\bar A\bar B,\dots)$ for parallel training.
- Stability and memory come from the eigenvalues: $\operatorname{Re}a<0$ keeps $|\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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
