Transformer alternatives 1: state space models from HiPPO to S4
A state space model keeps a small, fixed-size memory of the past and updates it once per token, like an RNN, but it can also be trained in parallel as one long convolution. This session builds the idea from the linear state equation, through HiPPO (how to choose the matrix so the memory really remembers) and S4 (how to compute it fast), to the simple diagonal models DSS, S4D and S5.
What you will learn
- The continuous linear state space model and how a step size Δ turns it into a discrete recurrence (zero-order hold and bilinear rules)
- Why a time-invariant SSM is both a recurrence (fast decoding) and a convolution (parallel training), with a worked example
- HiPPO: the state as the best polynomial summary of the past, and the HiPPO-LegS matrix
- S4: why the HiPPO matrix cannot be diagonalized directly, and the normal-plus-low-rank trick
- DSS and S4D: complex diagonal state matrices, the Vandermonde kernel and the S4D-Lin and S4D-Inv initializations
- S5: one multi-input SSM computed with a parallel scan
- Decode memory and training cost of SSMs compared with attention, and the main weakness that leads to Mamba
Why this matters
A transformer pays for its memory with a KV cache that grows with every token. A state space model (SSM) keeps a fixed-size memory instead: a small vector that it updates once per token, like an RNN. The trick that made SSMs work is that the same model can also be trained in parallel, as one long convolution, like a CNN.
In the last three sessions we made attention cheaper: fewer KV heads (session 97), low-rank keys (session 98), and kernel features that turn attention into an RNN with a \(d \times d\) state (session 99). This session leaves attention behind. We build a sequence layer from a different idea: a linear differential equation that compresses the whole past into a few numbers. The efficient-inference survey puts these models in its group of “transformer alternates” and says that an “SSM exhibits linear computational and memory complexity with respect to the input sequence length”. [Certain, survey Section 5.1.3]
The story has four steps, and each step fixed one problem of the previous one:
- The linear SSM: one equation with two faces, a recurrence and a convolution.
- HiPPO (2020): how to choose the matrix \(A\) so the state really remembers the past. It compresses history into the coefficients of a polynomial fit.
- S4 (2021): how to compute the long convolution kernel fast and stably, using a “normal plus low-rank” form of the HiPPO matrix.
- DSS, S4D, S5 (2022): it turns out a diagonal complex matrix with the right start values is enough. The code shrinks to a few lines.
S4 was the first model to solve the Path-X task of the Long Range Arena (sequences of 16,384 steps) with 88% accuracy, where all earlier models stayed at the 50% of random guessing. [Certain, S4 paper] It is also the direct parent of Mamba (session 101), which adds input-dependent parameters on top of everything in this session.
The linear state space model
Start in continuous time. A signal \(u(t)\) (one number per moment) goes in. The model keeps a state \(x(t) \in \R^N\), a vector of \(N\) numbers that summarizes the past. The state changes according to a linear differential equation, and the output \(y(t)\) is read from the state:
- Read the symbols
- \(x(t) \in \R^N\)
- the state: the model’s memory of the input so far; \(N\) is the state size (often 16 to 256)
- \(x'(t)\)
- how fast the state changes at time \(t\)
- \(A \in \R^{N \times N}\)
- the state matrix: how the memory evolves and fades on its own
- \(B \in \R^{N \times 1}\)
- how the input is written into the state
- \(C \in \R^{1 \times N}\)
- how the output is read from the state
- \(D\)
- a skip connection from input to output (a single number); often left out of the math because it is trivial
This is the classic model of control theory and signal processing (a Kalman filter uses the same form). Two things are important. First, it is linear: no tanh, no gates. Second, \(A, B, C\) do not depend on the input or on time. Such a system is called linear time-invariant (LTI). Everything good in this session (the convolution view) comes from LTI, and the main weakness (no content-based selection) comes from it too.
In a deep network, one SSM maps one channel to one channel. A layer with model width \(H\) runs \(H\) independent SSMs, one per channel, and then mixes the channels with a normal linear layer (and a nonlinearity). We come back to this in the S4 and S5 sections.
From continuous to discrete time
Tokens arrive at steps \(k = 0, 1, 2, \dots\), not as a continuous signal. We assume the tokens are samples \(u_k = u(k\Delta)\) of a hidden continuous signal, with a step size \(\Delta \gt 0\). Then we turn (100.1) into a rule from one step to the next. If the input is held constant during each step (a zero-order hold, ZOH), the exact solution of the differential equation over one step gives
S4 used the bilinear (trapezoid) rule instead, which avoids the matrix exponential:
Both give the same discrete model, a linear recurrence:
- Read the symbols
- \(\Delta\)
- the step size: how much continuous time one token covers. Small \(\Delta\): the state changes little per token and remembers for many tokens. Large \(\Delta\): it reacts fast and forgets fast. In S4 and S4D, \(\Delta\) is learned, one per channel
- \(\bar{A}, \bar{B}\)
- the discrete versions of \(A, B\); they depend on \(\Delta\)
- \(e^{\Delta A}\)
- the matrix exponential; for a diagonal \(A\) it is just \(e^{\Delta a_n}\) on the diagonal
The step size behaves like a gate in an RNN: it decides how much new input enters and how much old state stays. The HiPPO paper makes this link to RNN gates explicit. [Certain, HiPPO paper Section 2.5] Note also that \(\Delta\) is the only place where “time resolution” enters. If you sample the same audio at twice the rate, you can halve \(\Delta\) and keep \(A, B, C\).
Two views of one model
Now the key insight. Unroll the recurrence (100.4) from \(x_{-1} = 0\):
The output at step \(k\) is a weighted sum of all past inputs, and the weight of an input \(j\) steps ago is the number \(C\bar{A}^j\bar{B}\). These weights do not depend on \(k\) or on the input. So they form a fixed convolution kernel:
- Read the symbols
- \(\bar{K}\)
- the SSM convolution kernel; one number per lag \(0, 1, \dots, L-1\)
- \(L\)
- the sequence length
- \(*\)
- causal convolution: \(y_k = \sum_{j \le k} \bar{K}_j\, u_{k-j}\)
So one SSM has two ways to compute the same output:
| Recurrent view (100.4) | Convolutional view (100.6) | |
|---|---|---|
| Work | one state update per token | build \(\bar{K}\) once, then one long convolution (FFT) |
| Parallel over time? | no, step \(k\) needs step \(k-1\) | yes, all outputs at once |
| Memory during decode | the state: \(N\) numbers per channel, for any length | needs all past inputs |
| Used for | generation, one token at a time | training and prefill, all tokens known |
This is what RNNs never had. An LSTM can only be computed step by step, so its training does not use the GPU well (session 7). An LTI SSM trains like a CNN and decodes like an RNN. Figure 1 lets you check, step by step, that the two views give the same numbers.
How to read Figure 1
The top row is the input. The middle row is the state, filled in one step at a time (the recurrent view needs step \(k-1\) before step \(k\)). The bottom row shows the kernel laid backward under the inputs: the newest input gets weight \(\bar K_0 = \bar B\), one step back gets \(\bar A \bar B\), and so on. The readout shows both results and their difference, which stays at the level of rounding. Make \(\Delta\) small: \(\bar A\) gets close to 1, the kernel decays slowly and the model remembers longer. Make \(a\) more negative: memory fades faster.
Take \(a = -1\), \(b = c = 1\), \(\Delta = 0.5\). ZOH (100.2) gives \(\bar A = e^{-0.5} = 0.6065\) and \(\bar B = (e^{-0.5} - 1)/(-1) = 0.3935\). (The bilinear rule (100.3) gives \(\bar A = 0.75/1.25 = 0.6\) and \(\bar B = 0.5/1.25 = 0.4\): close, not equal.)
Kernel (100.6): \(\bar K = (0.3935,\ 0.2387,\ 0.1447,\ 0.0878,\ \dots)\); each entry is 0.6065 times the one before.
Input \(u = (1, 2, 0, -1)\). Recurrence: \(x_0 = 0.3935\); \(x_1 = 0.6065 \cdot 0.3935 + 0.3935 \cdot 2 = 1.0256\); \(x_2 = 0.6221\); \(x_3 = 0.6065 \cdot 0.6221 - 0.3935 = -0.0162\).
Convolution for the last step: \(y_3 = \bar K_0 u_3 + \bar K_1 u_2 + \bar K_2 u_1 + \bar K_3 u_0 = -0.3935 + 0 + 0.2895 + 0.0878 = -0.0162\). Same number, computed without any state.
The same loop with a matrix state
Figure 1 had a state of one number. With \(N \gt 1\) the state is a vector, \(\bar A\) is a matrix, and every step is a matrix times a vector. The smallest interesting case is \(N = 2\) with
- Read the symbols
- \(\alpha \gt 0\)
- the decay rate: each step shrinks the state by the factor \(e^{-\alpha\Delta}\)
- \(\omega\)
- the frequency: each step turns the state by the angle \(\omega\Delta\) (in radians)
- eigenvalues
- \(A\) has eigenvalues \(-\alpha \pm i\omega\), so this real 2 × 2 block is one complex mode written with real numbers. We meet these complex modes again in S4D (100.13)
So the ZOH step is simple to picture: shrink and rotate the state, then add \(\bar B u_k\). The state moves on a spiral, and the kernel \(C\bar A^j \bar B\) oscillates while it decays. Figure 2 runs the whole program on the input of Figure 1, with \(B = (1, 0)^\top\) and \(C = (1, 0.5)\). First it discretizes, then it builds the kernel (the convolution view), then it runs the recurrence (the recurrent view) and checks every output against the kernel.
- \(\bar A \leftarrow\) discretize\((A, \Delta)\) // (100.7) or (100.3)
- \(\bar B \leftarrow\) discretize\((B, \Delta)\) // (100.2) or (100.3)
- \(v \leftarrow \bar B\)
- for \(j = 0 \dots L-1\): \(\bar K_j \leftarrow C v\); \(v \leftarrow \bar A v\) // kernel (100.6)
- \(x \leftarrow 0\)
- for \(k = 0 \dots L-1\):
- \(x \leftarrow \bar A x\) // shrink and rotate
- \(x \leftarrow x + \bar B u_k\) // write the input
- \(y_k \leftarrow C x\) // check: \(= \sum_j \bar K_j u_{k-j}\)
How to read Figure 2
Press Play. Steps 1 and 2 compute \(\bar A\) and \(\bar B\). With the default ZOH, \(\Delta = 0.5\), \(\omega = 2\), \(\alpha = 0.5\): \(\bar A\) shrinks by \(e^{-0.25} = 0.7788\) and turns by exactly 1 radian per step, so \(\bar A\) has rows \((0.4208, -0.6553)\) and \((0.6553, 0.4208)\), and \(\bar B = (0.3765, 0.1955)\). The next 8 steps build the kernel: the orange arrow turns and shrinks on a spiral, and its reading by \(C\) gives \(\bar K = (0.4743, 0.1948, -0.1237, -0.2223, \dots)\), a damped oscillation. Then the loop runs, 3 steps per token. Watch the dashed arrow (\(\bar A x\): shrink and rotate) and then the blue arrow (\(+\bar B u_k\)). At \(k = 1\), \(y_1 = 1.1434\) both ways. With \(\omega = 0\) the spiral becomes a straight line and the kernel stops oscillating. The bilinear rule gives a slightly different \(\bar A\) (radius 0.8186 instead of 0.7788), but the two views still agree exactly with each other.
With \(N\) state dimensions the kernel entries are \(C\bar{A}^j\bar{B}\) with a full matrix power. Two problems remain, and they shaped the next five years of research. First, which \(A\)? A random \(A\) gives a state that forgets fast or explodes; the model then performs badly. Second, how to compute \(\bar K\) fast: \(L\) matrix powers of an \(N \times N\) matrix cost \(O(N^2 L)\) or more. HiPPO answers the first question, S4 and its diagonal successors the second.
HiPPO: compress the past into polynomial coefficients
HiPPO (“high-order polynomial projection operators”) asks a clear question: if you may keep only \(N\) numbers about the past of a signal, which \(N\) numbers should they be, and how do you update them when a new sample arrives? [Certain, HiPPO paper]
The answer: fit the history \(f(s)\), \(s \le t\), with a polynomial of degree \(N - 1\), and keep its \(N\) coefficients. As a basis use orthogonal polynomials, for example Legendre polynomials \(P_n\). “Best fit” needs a measure \(\mu^{(t)}\) that says how much each past moment counts:
- Read the symbols
- \(c(t) \in \R^N\)
- the memory at time \(t\): coefficients of the best polynomial fit of the past
- \(g_n^{(t)}\)
- the \(n\)-th basis polynomial, stretched to the window the measure covers
- \(\mu^{(t)}\)
- the measure: which part of the past matters. LegT: a sliding window of fixed length. LegS (“scaled Legendre”): uniform weight on the whole past \([0, t]\)
The HiPPO paper shows that for these measures the optimal coefficients obey a linear ODE, of exactly the SSM form (100.1). For LegS it is [Certain, HiPPO Theorem 2]:
So the HiPPO matrix is not learned at first; it is derived so that the state is the best polynomial summary of the past. It is lower triangular, and its eigenvalues are its diagonal entries \(1, 2, \dots, N\) (so \(-A\) is stable). For \(N = 3\):
The \(1/t\) factor makes LegS “scale” with time: the fit always covers the whole past, whatever its length, and the update has no window-size hyperparameter. When S4 uses this matrix inside an SSM it drops the \(1/t\) and uses a fixed, learned \(\Delta\). The basis then becomes Legendre polynomials in \(e^{-t}\), times \(e^{-t}\): an exponentially fading view of the past. [Certain, S4D paper Theorem 6] In practice, this choice of \(A\) matters a lot: the S4 paper reports that switching a simple SSM from a random \(A\) to the HiPPO matrix raised sequential MNIST accuracy from 60% to 98%. [Certain, S4 paper Section 2.2]
Figure 3 runs the HiPPO-LegS recurrence online on a signal, then rebuilds the whole history from only the \(N\) coefficients. It also computes the best offline fit, which sees all samples at once.
How to read Figure 3
With \(N = 4\) the memory keeps only the rough trend; with \(N = 64\) it follows the waves and even the jump at 55% of the signal. The orange and dashed lines nearly coincide: the online update, which never stores old samples, gives almost the same fit as an offline least-squares fit that sees everything. That is what “optimal online compression” means. Move \(t\) back: the fit always stretches over the whole past \([0, t]\), which is the “scaled” in LegS. The error grows with how much detail the past contains, not with how long it is.
On the default signal (400 samples), the root-mean-square error of the HiPPO rebuild is 0.842 with \(N = 4\), 0.327 with \(N = 16\) and 0.050 with \(N = 64\). The best offline fits give 0.842, 0.326 and 0.052. [Certain, computed with the same code in Python]
S4: making the HiPPO SSM fast
HiPPO solved “which \(A\)”. The first deep model built on it, LSSL, initialized \(A\) with HiPPO-LegS and trained in the convolutional view with an FFT. [Certain, survey Section 5.1.3] But computing the kernel \(\bar K\) needed many powers of a dense \(N \times N\) matrix, which was too slow and used too much memory. S4 (Gu, Goel and Ré) made it practical: compared with LSSL it is up to 30 times faster with 400 times less memory. [Certain, S4 paper]
Why not just diagonalize?
If \(A = V \Lambda V^{-1}\) with a diagonal \(\Lambda\), then \(\bar A^j = V \bar\Lambda^j V^{-1}\), and powers of a diagonal matrix are trivial. The problem: for the HiPPO-LegS matrix, \(V\) is terribly conditioned. Its entries grow like \(2^{4N/3}\) [Certain, S4 Lemma 3.2]; for \(N = 64\) that is about \(10^{25.7}\). Any computation through \(V\) loses all precision in float32.
Normal plus low-rank
The S4 observation: HiPPO-LegS is “almost” a nice matrix. It equals a normal matrix (one that a unitary, perfectly conditioned \(V\) diagonalizes) minus a rank-1 correction [Certain, S4 Theorem 1]:
- Read the symbols
- \(V\)
- a unitary matrix (complex), so multiplying by it loses no precision
- \(\Lambda\)
- a diagonal matrix of complex eigenvalues of the normal part
- \(P, Q \in \R^{N \times r}\)
- low-rank factors; for HiPPO-LegS, \(r = 1\) and \(P = Q\) with \(P_n = \sqrt{n + 1/2}\)
- \(V^{*}\)
- the conjugate transpose of \(V\)
In S4’s sign convention (state matrix \(-A\) with \(A\) from (100.10)), the normal part has entries \(-\sqrt{(n + \frac12)(k + \frac12)}\) below the diagonal, \(-\frac12\) on the diagonal and \(+\sqrt{(n+\frac12)(k+\frac12)}\) above it. All its eigenvalues have real part exactly \(-\frac12\). We check both facts in the code below.
With this diagonal-plus-low-rank (DPLR) form, S4 computes the kernel in three moves. It evaluates the kernel’s generating function at the \(L\) roots of unity instead of computing matrix powers. It removes the rank-1 term with the Woodbury identity. And the diagonal part reduces to a Cauchy kernel, a well-studied computation. The result is \(\tilde O(N + L)\) operations and \(O(N + L)\) memory per channel to build \(\bar K\), then an FFT convolution in \(O(L \log L)\). [Certain, S4 paper]
- input: sequence \(u \in \R^{H \times L}\) (\(H\) channels); per channel: \(\Lambda, P, B, C, \Delta\)
- for each channel \(h\) in parallel:
- \(\bar K_h \leftarrow\) kernel (100.6) from the DPLR form // S4: Cauchy kernel + Woodbury; S4D: Vandermonde (100.12)
- pad \(u_h\) and \(\bar K_h\) to length \(2L\) // so the FFT does a causal, not circular, convolution
- \(y_h \leftarrow \text{IFFT}\big(\text{FFT}(u_h) \cdot \text{FFT}(\bar K_h)\big)[0{:}L] + D_h u_h\)
- \(y \leftarrow\) GELU\((y)\), then a linear layer (or GLU) that mixes the \(H\) channels // the SSMs never mix channels themselves
- add the residual and normalize, as in a transformer block
A real S4 network stacks such layers like transformer blocks, with the SSM in the place of attention. On WikiText-103 language modeling the S4 paper reports a perplexity of 20.95 with 249M parameters, against 20.51 for a 247M transformer, while generating 48K tokens per second against 0.8K (60 times faster). [Certain, S4 paper Table 8] Close, but not better: this gap at language is the main topic of the next session.
DSS and S4D: a diagonal matrix is enough
The S4 algorithm was powerful but hard to implement. Months later, Gupta, Gu and Berant showed with DSS (diagonal state spaces) that you can simply drop the low-rank term and use a purely diagonal complex \(A\); it “matches the performance of S4 on Long Range Arena tasks”. [Certain, DSS paper] The follow-up S4D (Gu, Gupta, Goel, Ré) explained why and simplified it further. Its key findings [Certain, S4D paper]:
- Almost every matrix is diagonalizable over the complex numbers, so a diagonal complex SSM can express almost any SSM. It must be complex: real diagonal matrices give only decaying exponentials, no oscillations.
- The diagonal of S4’s normal part (dropping the low-rank term) gives, as \(N\) grows, the same kernel as S4. That is why DSS works.
- Expressive power is not the issue; initialization is. Random diagonal matrices perform poorly. Good start values matter.
With a diagonal \(A = \text{diag}(a_1, \dots, a_N)\), each state dimension is an independent one-number SSM, as in Figure 1, only complex. The kernel becomes a sum of \(N\) geometric sequences:
This is a product with a Vandermonde matrix (the matrix of powers \(\bar a_n^\ell\)), \(O(NL)\) work and very parallel. The parameters come in complex-conjugate pairs so that the kernel is real: S4D keeps only \(N/2\) modes and takes twice the real part. The two main initializations are
- Read the symbols
- \(n = 0, 1, \dots, N/2 - 1\)
- the index of a complex mode
- real part \(-\frac12\)
- every mode decays at the same rate, like the normal HiPPO part; the memory length is set by \(\Delta\)
- imaginary part
- the oscillation frequency of mode \(n\). Lin: evenly spaced, like a damped Fourier basis. Inv: an inverse law that approximates the eigenvalues of S4’s HiPPO-LegS normal part
- \(\Delta\)
- initialized log-uniform in \([0.001, 0.1]\), one per channel
With real part \(-\frac12\), a mode has decayed to 1% after \(\ln 100 / (0.5\,\Delta) \approx 9.2/\Delta\) steps: 92 steps for \(\Delta = 0.1\), 9,210 for \(\Delta = 0.001\). So the \(\Delta\) range gives the channels memories from about a hundred to about ten thousand tokens. S4D averages 85% on Long Range Arena, close to S4. [Certain, S4D paper] Figure 4 shows the poles \(\bar a_n\) and the kernel they produce.
How to read Figure 4
Every pole has radius \(e^{-\Delta/2}\) for Lin and Inv: they sit on one circle just inside the unit circle. The closer that circle is to 1 (small \(\Delta\)), the longer the kernel. The angle of a pole is its frequency per step, \(\Delta \cdot \text{Im}(a_n)\). Lin spreads the angles evenly, so the kernel mixes many frequencies. Inv puts most poles at low frequency and a few high. Real only puts all poles on the real axis: a smooth sum of decays with no oscillation, and the slowest mode decays at rate 1 instead of \(\frac12\), so the memory is shorter.
- input: state \(x \in \mathbb{C}^{H \times N/2}\) from the previous token, new input \(u_t \in \R^{H}\); precomputed \(\bar a, \bar B\) (they never change during generation)
- \(x \leftarrow \bar a \odot x + \bar B \odot u_t\) // formula (100.4), element-wise: \(O(HN)\) work
- \(y_t \leftarrow 2\,\text{Re}\big(\sum_n C_n x_n\big) + D \odot u_t\) // sum over modes, per channel
- channel mixing, residual, next layer, exactly as in training
- return \(y_t\) and the new \(x\) // the state size never grows: no KV cache
S5: one multi-input SSM and a parallel scan
S4 and S4D use a bank of \(H\) independent single-input, single-output (SISO) SSMs, one per channel, each with its own \(N\)-dimensional state. S5 (Smith, Warrington and Linderman) uses one multi-input, multi-output (MIMO) SSM instead: the whole \(H\)-dimensional input vector goes into one shared diagonal state of size \(P\), with \(B \in \mathbb{C}^{P \times H}\) and \(C \in \mathbb{C}^{H \times P}\). [Certain, S5 paper]
Because the state is shared and smaller, S5 does not need the convolution kernel at all. It computes the recurrence (100.4) directly with a parallel scan. A scan is a “running total” for any associative operation. For the linear recurrence, each step is a pair \((\bar a_k, b_k)\) with \(b_k = \bar B u_k\), and two steps combine as
This operation is associative: \((p \bullet q) \bullet r = p \bullet (q \bullet r)\). So we can combine neighbors in a tree: pairs, then pairs of pairs, and so on. With a diagonal \(\bar A\), the scan takes \(O(P \log L)\) parallel time on \(L\) processors and \(O(PL)\) total work. [Certain, S5 paper Section 2.2] S5 initializes with the diagonalized normal part of HiPPO (it calls it HiPPO-N), uses ZOH with learned \(\Delta\) per state, and averages 87.4% on Long Range Arena with 98.5% on Path-X. [Certain, S5 paper]
- input: elements \(e_k = (\bar a, b_k)\) for \(k = 0, \dots, L-1\) (with a time-varying \(\bar a_k\) it works the same)
- up-sweep: for levels \(s = 1, 2, 4, \dots\): combine \(e_{k-s} \bullet e_k\) for all \(k\) at that level in parallel // formula (100.14)
- down-sweep: push the partial results back down so every position gets \(e_0 \bullet \dots \bullet e_k\)
- the second component of \(e_0 \bullet \dots \bullet e_k\) is \(x_k\)
- \(y_k \leftarrow \text{Re}(C x_k) + D u_k\) for all \(k\) in parallel
The scan matters for history. The convolution view needs the kernel to be the same at every step (LTI). The scan does not: it works even if \(\bar a_k\) and \(b_k\) change with the input at each step. That is exactly the door Mamba walks through (session 101). The survey notes that S5 and Mamba both use a parallel scan for training instead of a convolution. [Certain, survey Section 5.1.3]
Figure 6 runs a scan on 8 steps. It uses the simplest parallel scan (Hillis and Steele): at level \(s = 1, 2, 4, \dots\), every position \(k \ge s\) combines with position \(k - s\). After level \(s\), position \(k\) holds the combined effect of the last \(2s\) inputs, so \(\log_2 L\) levels are enough. This version does more total work than the up-sweep and down-sweep of Algorithm 3 (\(O(L \log L)\) combines instead of \(O(L)\)), but it has the same \(\log_2 L\) depth and is easier to follow.
- \(e_k \leftarrow (\bar a_k,\ b_k = \bar B_k u_k)\) for all \(k\)
- for \(s = 1, 2, 4, \dots \lt L\):
- for all \(k \ge s\) in parallel:
- \(e_k \leftarrow e_{k-s} \bullet e_k\) // (100.14)
- \(x_k \leftarrow\) second part of \(e_k\) // equals the loop (100.4)
How to read Figure 6
Each step does one combine; all combines in one row could run at the same time on different processors. The thick lines show which two boxes feed the current one. The live panel shows (100.14) with the numbers: in the LTI case the first combine is \((0.6065, 0.3935) \bullet (0.6065, 0.7869) = (0.3679, 1.0256)\), and 1.0256 is exactly \(x_1\) of Figure 1. A box turns green when it already holds its final value: after level \(s\), positions \(k \lt 2s\) are done. After 3 levels (17 combines), all 8 boxes match the loop, which needed 8 steps one after the other. Switch to input-dependent \(\bar a_k\): the numbers change (for \(u_k = 0\), \(\bar a_k = 0.5\)), but the same 17 combines give the same result as the loop, 0.7623 at the last step. A convolution could not do this, because there is no single kernel when \(\bar a\) changes with \(k\).
What it costs: SSM vs attention
Now the inference view, which is why this session sits in this track. Per layer and per channel:
Compare attention: training costs \(O(L^2)\) per channel, and decoding token \(t\) reads a KV cache of \(2t\) numbers per channel (session 80). The survey’s summary table lists the same picture: per-token decoding cost \(O(nd)\) for a transformer but \(O(d^2)\) for recurrent models such as S4. [Certain, survey Table II]
Take width \(d = H = 4096\) and context \(L = 32{,}768\). Full multi-head attention keeps \(2 \cdot L \cdot d = 268{,}435{,}456\) numbers per layer in its KV cache, which is 512 MiB per layer in BF16. An SSM layer with \(N = 64\) keeps \(d \cdot N = 262{,}144\) numbers (as 32 complex modes per channel), 512 KiB in BF16. The ratio is \(2L/N = 1024\). And the SSM number stays the same at 1M tokens, while the KV cache grows 32 times larger.
(A fair comparison would use GQA, which divides the KV cache by the group factor, for example by 4 or 8 (session 97). The SSM still wins by a factor of more than 100 at this length.)
How to read Figure 7
Each step of the length slider doubles \(L\). The KV-cache bar moves right by the same step each time (a factor of 2 on the log scale); the SSM-state bar does not move at all. The training-work ratio is \(L / \log_2 L\): about 102 at 1K tokens and about 2,185 at 32K. Raising the group factor shrinks the KV cache, but it still grows with \(L\). Raising \(N\) makes the SSM state bigger and more expressive, and it is still independent of \(L\).
PyTorch: an S4D layer, both views
The code below builds the HiPPO-LegS matrix and checks the normal-plus-low-rank fact (100.11). Then it implements an S4D-Lin layer with ZOH, computes its output with the Vandermonde kernel and an FFT (training view), and again token by token with the recurrence (decode view), and checks they agree. It runs on CPU in about a second.
import math, torch torch.manual_seed(0) def hippo_legs(N): """HiPPO-LegS (formula 100.10), with the sign used by S4: dx/dt = A x + B u.""" n = torch.arange(N, dtype=torch.float64) r = torch.sqrt(2 * n + 1) A = torch.tril(r[:, None] * r[None, :], diagonal=-1) + torch.diag(n + 1) return -A, r.clone() # lower triangular, eigenvalues -1, -2, ..., -N class S4DKernel(torch.nn.Module): """One S4D layer for H channels, N/2 complex modes per channel, ZOH discretization.""" def __init__(self, H, N=64, dt_min=1e-3, dt_max=1e-1): super().__init__() log_dt = torch.rand(H) * (math.log(dt_max) - math.log(dt_min)) + math.log(dt_min) self.log_dt = torch.nn.Parameter(log_dt) self.log_A_re = torch.nn.Parameter(torch.log(0.5 * torch.ones(H, N // 2))) # Re(A) = -1/2 self.A_im = torch.nn.Parameter(math.pi * torch.arange(N // 2).repeat(H, 1).float()) # S4D-Lin self.C = torch.nn.Parameter(torch.randn(H, N // 2, dtype=torch.cfloat) * 0.5 ** 0.5) self.D = torch.nn.Parameter(torch.randn(H)) def discrete(self): dt = self.log_dt.exp()[:, None] # (H, 1) A = -self.log_A_re.exp() + 1j * self.A_im # (H, N/2); Re(A) < 0 always dA = torch.exp(dt * A) # formula (100.2), ZOH dB = (dA - 1) / A # B = 1: (dt A)^-1 (e^{dt A} - 1) dt B return dA, dB def kernel(self, L): dA, dB = self.discrete() powers = dA[:, :, None] ** torch.arange(L) # Vandermonde: (H, N/2, L) return 2 * torch.einsum("hn,hnl->hl", self.C * dB, powers).real # formula (100.12) def forward_conv(self, u): # u: (B, H, L), training view L = u.shape[-1] K = self.kernel(L) Kf = torch.fft.rfft(K, n=2 * L); uf = torch.fft.rfft(u, n=2 * L) y = torch.fft.irfft(uf * Kf, n=2 * L)[..., :L] # causal convolution, O(L log L) return y + self.D[:, None] * u def step(self, x, u_t): # decode view: one token dA, dB = self.discrete() x = dA * x + dB * u_t[..., None] # formula (100.4); x: (B, H, N/2) y = 2 * (self.C * x).sum(-1).real + self.D * u_t return x, y # 1) HiPPO-LegS = normal matrix minus rank 1 (formula 100.11) A, B = hippo_legs(8) P = torch.sqrt(torch.arange(8, dtype=torch.float64) + 0.5) AN = A + P[:, None] * P[None, :] print("normal part:", torch.allclose(AN @ AN.T, AN.T @ AN), "Re(eig):", torch.linalg.eigvals(AN).real.round(decimals=6).unique().tolist()) # 2) the two views give the same output layer = S4DKernel(H=4, N=16) u = torch.randn(2, 4, 300) with torch.no_grad(): y_conv = layer.forward_conv(u) x = torch.zeros(2, 4, 8, dtype=torch.cfloat); ys = [] for t in range(u.shape[-1]): x, y_t = layer.step(x, u[..., t]); ys.append(y_t) y_rec = torch.stack(ys, -1) print("max |conv - recurrent|:", (y_conv - y_rec).abs().max().item()) print("decode state per channel:", x.shape[-1], "complex numbers, for any length")
Output (PyTorch 2.8, CPU): normal part: True Re(eig): [-0.5], then max |conv - recurrent|: 1.67e-06 (float32 rounding), then decode state per channel: 8 complex numbers. Two details worth copying: \(\text{Re}(A)\) is stored as a log and negated, so it can never become positive (an unstable state), and the FFT is padded to \(2L\), so the convolution is causal.
Where this is used
| Setting | SSM used | Why an SSM |
|---|---|---|
| Long Range Arena (1K to 16K steps), Path-X | S4, S4D, S5 | First models to solve Path-X at length 16,384 [Certain] |
| Raw audio: speech classification (16,000 samples per clip), audio generation | S4; SaShiMi (S4-based) for generation [Likely] | Samples are very long sequences with smooth structure; S4 halved the test error of speech CNNs on 16K-length clips [Certain, S4 paper] |
| Long video classification (movie clips of minutes) | ViS4mer: a transformer for short-range frame features plus an S4 decoder over time | Reported 2.63× faster with 8× less GPU memory than the pure self-attention version, best on 6 of 9 LVU tasks [Certain, ViS4mer abstract] |
| Images and video as continuous signals | S4ND (multi-dimensional S4) [Likely] | The continuous-time view lets one model work at different resolutions by changing \(\Delta\) |
| Streaming video tasks (action recognition, key-moment detection on live streams) | Recurrent SSM layers over frame embeddings [Speculation] | Constant memory per frame, so a stream of any length fits on an edge device |
| Time-series forecasting, sensors | S4, S4D | Irregular or long histories; \(\Delta\) handles sampling rate |
| Language models | H3, then Mamba and hybrids (session 101) | Constant decode memory; pure LTI SSMs lag on language, input-dependent ones close most of the gap [Likely] |
Common mistakes
- Diagonalizing HiPPO-LegS directly. The eigenvector matrix has entries up to about \(2^{4N/3}\); in float32 the result is noise. Use the normal part (S4, S5) or a diagonal initialization such as S4D-Lin or S4D-Inv.
- Circular instead of causal convolution. An FFT of length \(L\) wraps the end of the sequence onto the start, so the future leaks into the past. Pad both signals to \(2L\) and keep the first \(L\) outputs.
- Letting \(\text{Re}(a_n)\) become positive. Then \(|\bar a_n| \gt 1\) and the state explodes over long sequences. Parameterize \(\text{Re}(a_n) = -\exp(\cdot)\) as in the code.
- Real-valued diagonal \(A\) and expecting S4 quality. Real poles give only smooth decays. In the S4D ablations, the real initialization \(a_n = -(n+1)\) (S4D-Real) does clearly worse than S4D-Lin and S4D-Inv, even though it has the same spectrum as S4-LegS. [Certain, S4D paper Section 5.2]
- Forgetting the conjugate pairs. If you keep \(N/2\) complex modes, the real kernel is \(2\,\text{Re}(\cdot)\), not \(\text{Re}(\cdot)\). Mixing both conventions halves or doubles the output.
- Wrong \(\Delta\) range for the data. \(\Delta\) sets the memory length (about \(9.2/\Delta\) steps for real part \(-\frac12\)). If your sequences are 100K long and \(\Delta \ge 0.01\), no channel can remember the start. For Path-X (16,384 steps) S4 and S4D lower the range from \([0.001, 0.1]\) to \([0.0001, 0.01]\). [Certain, S4D paper Appendix]
- Treating SSM parameters like other weights. The S4 code trains \(A\), \(B\), \(\Delta\) with a smaller learning rate and no weight decay; weight decay pulls \(\text{Re}(a)\) and \(\Delta\) toward values that change the memory length. [Likely]
- Computing the kernel in low precision. \(\bar a^\ell\) for \(\ell\) in the thousands loses precision in BF16. Keep kernel and state math in FP32 / complex64.
Interview questions
What is a state space model, and what are its two computational views?basic
Why can an SSM be trained in parallel when an LSTM cannot?core
Derive the zero-order-hold discretization.core
What problem does HiPPO solve, and what is the LegS matrix?core
Why does S4 not simply diagonalize the HiPPO matrix, and what does it do instead?advanced
Why does a purely diagonal SSM (DSS, S4D) work, and why must it be complex?core
How does S5 differ from S4?core
Compare decode-time memory of an SSM and a transformer layer at 32K context.core
What is the main weakness of LTI SSMs for language, and how is it addressed?advanced
How are SSMs related to linear attention?advanced
What does the step size \(\Delta\) control, and why is it learned per channel?basic
Exercises
- For a scalar SSM with \(a = -2\), \(b = 1\), \(\Delta = 0.1\), compute \(\bar A\) and \(\bar B\) with ZOH and with the bilinear rule.
- Using the worked example of Figure 1 (\(\bar A = 0.6065\), \(\bar B = 0.3935\)), compute \(y_2\) for \(u = (1, 2, 0)\) with the convolution formula.
- Write the HiPPO-LegS matrix for \(N = 3\). What are its eigenvalues? Why can you read them off without computing?
- An S4D-Lin channel has \(\Delta = 0.01\). After how many steps has its memory decayed to 1%?
- A model has width 2048 and an SSM state of \(N = 16\) per channel. At 8,192 tokens of context, how many numbers does one layer hold during decode, and how does that compare to a full-MHA KV cache?
- Why must the FFT in Algorithm 1 use length \(2L\)? What goes wrong with length \(L\)?
Answerscheck
Key takeaways
- A linear state space model (100.1), discretized with a step \(\Delta\) (100.2, 100.3), is a linear recurrence (100.4). Because it is time-invariant, it is also a convolution with kernel \(\bar K_j = C\bar A^j\bar B\) (100.6): train in parallel, decode with a fixed state.
- HiPPO (100.8 to 100.10) derives \(A\) so that the state holds the best polynomial summary of the past; the online update matches an offline least-squares fit.
- S4 makes HiPPO SSMs fast and stable: normal plus low-rank (100.11), Cauchy kernel and Woodbury, \(\tilde O(N+L)\) for the kernel, FFT for the convolution. First to solve Path-X (16,384 steps).
- DSS and S4D show a complex diagonal \(A\) is enough if it is initialized well (100.13); the kernel is a Vandermonde product (100.12). S5 uses one MIMO diagonal SSM and a parallel scan (100.14).
- Decode memory is \(N\) numbers per channel, independent of context: 1024 times smaller than an MHA KV cache at 32K tokens with \(N = 64\). The price: an LTI kernel cannot select content, which motivates Mamba.
Key formulas
References for this session
- Gu et al. (2020). HiPPO: Recurrent Memory with Optimal Polynomial Projections
- Gu et al. (2021). Efficiently Modeling Long Sequences with Structured State Spaces
- Gu et al. (2022). On the Parameterization and Initialization of Diagonal State Space Models
- Smith et al. (2022). Simplified State Space Layers for Sequence Modeling (S5)
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Gu et al. (2020). HiPPO: Recurrent Memory with Optimal Polynomial Projections
- Gu, Johnson, Goel, Saab, Dao, Rudra, Ré (2021). Combining Recurrent, Convolutional, and Continuous-time Models with Linear State-Space Layers
- Gu et al. (2021). Efficiently Modeling Long Sequences with Structured State Spaces
- Gupta, Gu & Berant (2022). Diagonal State Spaces are as Effective as Structured State Spaces
- Gu et al. (2022). On the Parameterization and Initialization of Diagonal State Space Models
- Smith et al. (2022). Simplified State Space Layers for Sequence Modeling (S5)
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Katharopoulos et al. (2020). Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention
- Gu & Dao (2023). Mamba: Linear-Time Sequence Modeling with Selective State Spaces
- Islam & Bertasius (2022). Long Movie Clip Classification with State-Space Video Models
- Goel, Gu, Donahue & Ré (2022). It's Raw! Audio Generation with State-Space Models
- Nguyen, Goel, Gu et al. (2022). S4ND: Modeling Images and Videos as Multidimensional Signals Using State Spaces
- Fu et al. (2022). Hungry Hungry Hippos: Towards Language Modeling with State Space Models