Structured State-Space Models (S4)
Structured state-space models represent a sequence layer as a linear dynamical system, computed as a long convolution to capture very long-range dependencies efficiently.
A linear system as a layer
A structured state-space model (S4) treats a sequence layer as a continuous linear dynamical system: a hidden state evolves according to dx/dt = A x + B u, and the output is y = C x + D u, where u is the input signal. Discretized to the time steps of a sequence, this defines a linear recurrence. The appeal is that a well-chosen state matrix A can retain information over thousands of steps, addressing the long-range dependency problem that defeats ordinary recurrent networks.
Recurrence and convolution duality
Because the recurrence is linear, unrolling it shows the output is a convolution of the input with a fixed kernel determined by A, B, and C. S4 exploits this duality: it trains and runs on long sequences as a single long convolution, computed efficiently in the frequency domain, and can switch to the recurrent form for step-by-step inference. This gives parallel training like a convolutional model and fast autoregressive generation like a recurrent one.
- Linear recurrence, so no vanishing-gradient nonlinearity in the state path
- Convolutional view enables parallel training over the whole sequence
- Recurrent view enables constant-memory streaming inference
- Cost grows roughly linearly with sequence length, unlike quadratic attention
The HiPPO initialization
The key to S4's memory is how A is initialized. The HiPPO framework derives a special structured matrix that makes the state optimally compress the history of the input onto a basis of orthogonal polynomials. Starting from this matrix, rather than a random one, is what lets S4 remember signals over extremely long ranges; a random linear recurrence would not.
Significance
S4 showed that a carefully structured linear model can beat attention on tasks demanding very long context while scaling linearly in sequence length. Its main limitation is that the convolution kernel is fixed regardless of input content, unlike attention which is data-dependent. That gap motivated the selective mechanism of Mamba, which lets the state-space parameters vary with the input. S4 is a strong alternative to the attention-based transformer for long-sequence modeling.