This time, I’ll talk about the paper “Efficiently Modeling Long Sequences with Structured State Spaces”, also known as S4. The paper presents a state-space model (SSM) designed to handle long-range dependencies in sequence modeling.

S4 uses a new parameterization that improves computational efficiency, allowing it to handle very long sequences, over 10,000 steps. Its design relies on state-space models that have existed for decades in control theory, but adapts them for modern deep learning.

Key concepts

State-space models (SSM)

State-space models describe a dynamic system through a latent state (x_t) evolving over time in response to inputs (u_t). The output (y_t) is generated based on the current state. Formally, an SSM looks like this:

  • Continuous form:
    • State update: x’(t) = A * x(t) + B * u(t)
    • Output: y(t) = C * x(t) + D * u(t)
  • Discrete form (used in computation):
    • x[t+1] = A_d * x[t] + B_d * u[t]
    • y[t] = C_d * x[t] + D_d * u[t]

The latent state captures the “memory” of the system, which makes SSMs useful for modeling sequences with long-range dependencies.

Structured State Space (S4)

The main idea behind S4 is that previous SSM implementations were computationally impractical for long sequences. The authors decompose the state-transition matrix A into a normal matrix plus a low-rank correction. This structure simplifies computation and makes the model much more efficient.

HiPPO initialization

The HiPPO (High-order Polynomial Projection Operator) matrix is used to initialize the state-transition matrix A. It is structured to maintain long-term memory by projecting past sequence information onto orthogonal polynomials, specifically Legendre polynomials. This gives the model stable memory decay for long-range dependencies.

Convolutional representation

SSMs can also be represented as convolutions. By “unrolling” the state equations, the output at any time step can be computed as a convolution of inputs with a kernel defined by A. This convolutional view is computationally useful, especially when the state matrix can be diagonalized.

What I learned

Why the Gaussian assumption is important

Initially, I wondered why state-space models often assume Gaussian noise. The Gaussian assumption makes things mathematically convenient. It allows closed-form solutions, like Kalman filters, and connects to the Central Limit Theorem. Without this assumption, things become much harder to analyze.

Why discretization matters

Real-world data isn’t continuous; it is sampled at discrete intervals. S4 discretizes the continuous equations to match this reality. At first, this seemed trivial, but it matters because discrete forms (\bar{A}, \bar{B}, etc.) differ significantly from their continuous counterparts. This discretization strongly affects stability and computational efficiency.

The role of the A matrix

I initially struggled to understand why the A matrix is so central. After digging deeper, I realized A controls the internal dynamics, or “memory,” of the system. Its eigenvalues determine whether information fades quickly or persists longer. S4 carefully structures A so the system can capture long-term dependencies without exploding or collapsing to zero.

Why HiPPO matters

The paper frequently mentions HiPPO initialization, and I initially found it vague. The deeper reason HiPPO works is that it keeps the A matrix stable. By projecting sequence history onto stable polynomial bases, HiPPO gives controlled memory behavior. This initialization is a big part of why S4 handles long sequences.

Normality and stability

Another subtlety was why the normality of the A matrix matters. Normal matrices can be diagonalized, with eigenvalues organized along a diagonal matrix. This directly affects memory because eigenvalues describe information decay. Non-normal matrices lack this clean representation, which can lead to unstable or unpredictable behavior over long sequences.

How S4 compares to other models

Compared to conventional sequence models like RNNs, CNNs, or even Transformers, S4 captures long-range dependencies efficiently. This comes from its structured A matrix and convolutional form. S4 doesn’t need special tricks like dilations or gating mechanisms. It is a straightforward alternative that works well.

Summary

S4 is a state-space model adapted for deep learning, specifically for long-range sequence modeling. The authors address the computational challenges by structuring the A matrix and using HiPPO initialization for stability.

My main takeaway was how older mathematical tools, like state-space models and polynomial projections, can become useful again in modern deep learning. Understanding S4 helped me think more clearly about what makes sequence models “remember” or “forget.”