Back to paper library
arXiv 2021ICLR 2022State space modelsPaper notes

S4

The Prelude of Mamba

Original paper

Efficiently Modeling Long Sequences with Structured State Spaces

Paper authors

Albert Gu · Karan Goel · Christopher Ré

Publication
ICLR 2022Conference
First submitted to arXiv
arXiv:2111.00396
Cite this paper · BibTeX

The citation identifies the linked source version. It cites the original paper and its authors.

@misc{mambas42021,
  title = {{Efficiently Modeling Long Sequences with Structured State Spaces}},
  author = {Albert Gu and Karan Goel and Christopher Ré},
  year = {2021},
  eprint = {2111.00396},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2111.00396}
}
On this page

We wanted to dive into Mamba, but we discovered there were quite a few prerequisites to tackle first—some foundational knowledge needed to be addressed.

So, we’re starting with S4.

This paper primarily aims to improve upon existing issues with State Space Models (SSMs).

Since it involves SSMs, it means we need to backtrack and delve into the relevant concepts of SSMs first.

State Space Models

State Space Models (SSMs) are mathematical tools used to describe the behavior of dynamic systems. They are widely applied in control engineering, signal processing, economics, and, more recently, deep learning.

The core idea of SSMs is to describe the dynamic behavior of systems through internal "states." It maps external input signals to the system's internal states, which then generate output signals. This framework captures the temporal evolution of systems, making it particularly suitable for handling time-series data and dynamic processes.

SSMs describe system behavior using two core equations:

  1. State Equation: Describes how the system's state evolves over time.

    x˙(t)=Ax(t)+Bu(t)\dot{x}(t) = A x(t) + B u(t)
    • State Transition Matrix AA: Determines the intrinsic dynamics of the system, such as natural decay or oscillation.
    • Input Matrix BB: Defines how inputs affect the system's state.
  2. Output Equation: Describes how to obtain outputs from the states.

    y(t)=Cx(t)+Du(t)y(t) = C x(t) + D u(t)
    • Output Matrix CC: Specifies which states influence the output.
    • Direct Transmission Matrix DD: Represents the direct impact of inputs on outputs (if any).

Thus, given an initial state x(0)x(0) and an input u(t)u(t), one can solve for x(t)x(t) and y(t)y(t), describing how the system evolves over time.

HiPPO Theory

In prior studies, basic State Space Models (SSMs) struggled in some practical applications. Their dynamics involve a matrix exponential, and gradients can vanish or explode as sequence length grows, depending on the state matrix. This can hinder learning on tasks that require long-term memory; the exponential form alone does not make every SSM unstable.

To address this issue, the Linear State Space Layer (LSSL) model introduced the HiPPO Theory (High-order Polynomial Projection Operators), which focuses on a mathematical framework for continuous-time memory.

HiPPO introduces a class of specialized matrices A∈RN×NA \in \mathbb{R}^{N \times N}. When these matrices are applied to the state transition equation in SSMs, they enable the state x(t)x(t) to efficiently retain information about the input history u(t)u(t).

The mathematical definition of the HiPPO matrix is as follows:

Ank={−2n+12k+1if n>k−(n+1)if n=k0if n<kA_{nk} = \begin{cases} -\sqrt{2n+1}\sqrt{2k+1} & \text{if } n > k \\ -(n+1) & \text{if } n = k \\ 0 & \text{if } n < k \end{cases}
  • n>kn > k: Defines the interaction between different orders.
  • n=kn = k: Represents reflexivity (self-interaction).
  • n<kn < k: Indicates no influence between states.

This is the HiPPO-LegS-derived matrix used to initialize the SSM; the indices start at zero. The original online HiPPO-LegS dynamics also have a 1/t1/t factor, so this time-invariant SSM is not the same as the online projection. In the Sequential MNIST experiment cited by S4, replacing the baseline initialization with HiPPO raised accuracy from about 60% to 98%, showing the value of this memory design in that setting.

Discretization

When handling discrete input sequences (u0,u1,… )(u_0, u_1, \dots), SSMs need to discretize the continuous-time equations because inputs uku_k are typically discrete samples derived from a continuous signal u(t)u(t):

uk=u(kΔ),u_k = u(k\Delta),

where Δ\Delta represents the time step. This indicates that the kk-th sample corresponds to the value of the continuous signal at time kΔk\Delta.

To achieve this transformation, the bilinear method is commonly used, which converts the continuous-time state matrix AA into its discrete counterpart Aˉ\bar{A}.

The state space model in its discrete form is represented as:

xk=Aˉxk−1+Bˉuk,yk=Cˉxk,\begin{aligned} x_k &= \bar{A} x_{k-1} + \bar{B} u_k, \\ y_k &= \bar{C} x_k, \end{aligned}

where:

Aˉ=(I−Δ2A)−1(I+Δ2A),Bˉ=(I−Δ2A)−1ΔB,Cˉ=C.\begin{aligned} \bar{A} &= \left( I - \frac{\Delta}{2} A \right)^{-1} \left( I + \frac{\Delta}{2} A \right), \\ \bar{B} &= \left( I - \frac{\Delta}{2} A \right)^{-1} \Delta B, \\ \bar{C} &= C. \end{aligned}
  • Aˉ\bar{A}: The discrete state matrix, describing the evolution of the hidden state.
  • Bˉ\bar{B}: The discrete input matrix, describing how the input influences the state.
  • Cˉ\bar{C}: The output matrix, identical to the continuous case.

The discretized equations transform the continuous-time representation into a sequence-to-sequence mapping, where the hidden state at each time step xkx_k is linked to the previous state xk−1x_{k-1}, resembling the structure of Recurrent Neural Networks (RNNs).

In this formulation, xk∈RNx_k \in \mathbb{R}^N can be seen as the hidden state of an RNN, and Aˉ\bar{A} functions as the weight matrix for the recurrent layer.

Convolutional Representation

While the recursive formula above captures sequence relationships, its sequential nature makes it challenging to train efficiently on modern hardware like GPUs, as each step depends on the previous step's computation.

To overcome this, we transform the recursive formula into a convolutional form. Assuming the initial state x−1=0x_{-1} = 0, the recursive formula unfolds as follows:

x0=Bˉu0,x1=AˉBˉu0+Bˉu1,x2=Aˉ2Bˉu0+AˉBˉu1+Bˉu2,…\begin{aligned} x_0 &= \bar{B} u_0, \\ x_1 &= \bar{A} \bar{B} u_0 + \bar{B} u_1, \\ x_2 &= \bar{A}^2 \bar{B} u_0 + \bar{A} \bar{B} u_1 + \bar{B} u_2, \\ &\dots \end{aligned}

The output yky_k is given by:

yk=Cˉxk,y_k = \bar{C} x_k,

which expands to:

yk=CˉAˉkBˉu0+CˉAˉk−1Bˉu1+⋯+CˉBˉuky_k = \bar{C} \bar{A}^k \bar{B} u_0 + \bar{C} \bar{A}^{k-1} \bar{B} u_1 + \cdots + \bar{C} \bar{B} u_k

Upon expanding, we observe that this can be expressed in convolutional form:

y=K∗u,y = K * u,

where:

K=(CˉBˉ,CˉAˉBˉ,…,CˉAˉL−1Bˉ)K = (\bar{C} \bar{B}, \bar{C} \bar{A} \bar{B}, \dots, \bar{C} \bar{A}^{L-1} \bar{B})

Here, KK represents the convolution kernel, which describes how the system's output is generated from the input as it propagates through the state matrices.

Defining the Problem

The authors clearly state at the outset that the core goal of this paper is to address the efficiency bottlenecks in sequence models when handling Long-Range Dependencies (LRDs). Specifically, the focus is on the computational and memory challenges faced by existing models when processing long sequences.

At the time of publication, many sequence models struggled with tens of thousands of time steps. For example, the Path-X task has length 16,384; the prior models in the paper's LRA comparison did not beat random guessing on it. This describes that benchmark and comparison, rather than a fixed sequence-length limit for all models.

Although traditional models—such as CTMs, RNNs, CNNs, and Transformers—have introduced specialized variants to tackle LRD, such as orthogonal RNNs, dilated convolutions, and efficient Transformers, these approaches still struggle on challenging benchmarks like LRA and raw audio classification.

Beyond the mainstream techniques, State Space Models (SSMs) have theoretical potential but have long been difficult to apply to deep learning due to several limitations:

  • Deep SSMs: While theoretically capable of handling LRDs, their practical performance in real-world tasks has been limited.
  • Linear State Space Layers (LSSLs): Although LSSLs can unify the strengths of CTMs, RNNs, and CNNs and demonstrate potential for addressing LRDs, they suffer from excessive computational and memory demands. Additionally, their practical application has been hindered by numerical instability, especially due to the high non-normality of the matrix AA, which makes traditional algorithms difficult to apply stably.

To address these challenges, the authors propose a Structured State Space Model (S4).

The goal of S4 is to significantly reduce computational complexity and memory requirements by re-parameterizing the state matrix AA and leveraging frequency-domain computations via generating functions, while maintaining numerical stability.

Solving the Problem

In discrete-time state space models (SSMs), direct computations involve repeated multiplications of the matrix AA, which constitutes the primary computational bottleneck:

  • Time Complexity: For a sequence of length LL, computing the formula requires O(N2L)O(N^2L) operations.
  • Space Complexity: Storing all hidden states for training requires O(NL)O(NL) space. Streaming inference can retain only the current O(N)O(N) state, aside from parameters and input/output storage.

To address this, the authors first analyze diagonalization of AA, then explain why applying it directly to the HiPPO matrix fails numerically.

Given the state space model (A,B,C)(A, B, C), conjugation transforms it into (V−1AV,V−1B,CV)(V^{-1}AV, V^{-1}B, CV).

If AA can be diagonalized stably, kernel evaluation becomes a Vandermonde matrix-vector product, for which the analyzed fast algorithm costs O((N+L)log⁡2(N+L))O((N + L) \log^2(N + L)). The kernel KK remains a vector; it is not itself a Vandermonde matrix.

However, for HiPPO matrices, direct diagonalization leads to numerical instability because the elements of the diagonalizing matrix VV grow exponentially large. This makes direct numerical computations infeasible.

S4 Parameterization

The term Normal Plus Low-Rank (NPLR) refers to a matrix decomposition combining a normal matrix with a low-rank matrix.

In the previous discussion, the authors concluded that a well-conditioned change of basis is needed. Ideally, matrix AA would be diagonalizable by a unitary matrix VV, for which V∗V=IV^*V=I and the 2-norm condition number is 1. A unitary matrix need not be the identity matrix II.

According to the spectral theorem in linear algebra, matrices satisfying this condition are normal matrices, which fulfill AA∗=A∗AAA^* = A^*A. However, this class of matrices is limited, and notably, HiPPO matrices do not belong to this category.

Although HiPPO matrices are not normal, they can be decomposed into the sum of a normal matrix and a low-rank matrix. However, directly leveraging this decomposition is computationally inefficient because exponentiating such a decomposition remains slow and hard to optimize.

To overcome these challenges, the authors introduced three key techniques:

  • Technique 1: Spectral Computation via Generating Functions

    Instead of directly computing KK, they calculate its truncated generating function:

    ∑j=0L−1Kjζj\sum_{j=0}^{L-1} K_j \zeta^j

    at the roots of unity ζ\zeta. The convolution kernel KK is then recovered using Inverse Fast Fourier Transform (IFFT).

  • Technique 2: Matrix Resolvent and Woodbury Identity

    The generating function involves matrix inversion rather than exponentiation. The authors apply the Woodbury identity to express (A+PQ∗)−1(A + P Q^*)^{-1} in terms of A−1A^{-1}, reducing the computation to the diagonal case efficiently:

    (A+PQ∗)−1=A−1−A−1P(I+Q∗A−1P)−1Q∗A−1.(A + P Q^*)^{-1} = A^{-1} - A^{-1}P (I + Q^*A^{-1}P)^{-1} Q^*A^{-1}.
  • Technique 3: Equivalence to Cauchy Kernel Computation

    For diagonal matrices, the computation reduces to calculating the Cauchy kernel:

    1ωj−ζk,\frac{1}{\omega_j - \zeta_k},

    a well-studied problem in numerical analysis with fast, stable algorithms that operate in near-linear time. These algorithms are detailed in works such as:

These techniques are broadly applicable to matrices that can be decomposed into the Normal Plus Low-Rank (NPLR) form.

  • Theorem 1: NPLR Representation of HiPPO Matrices

    The authors formally state the first theorem of the paper:

    The HiPPO-LegS, LegT, and LagT matrices analyzed here can be represented in the NPLR form:

    A=VΛV∗−PQ⊤=V(Λ−(V∗P)(V∗Q)∗)V∗,A = V \Lambda V^* - P Q^\top = V (\Lambda - (V^*P) (V^*Q)^*) V^*,

    where:

    • V∈CN×NV \in \mathbb{C}^{N \times N} is a unitary matrix,
    • Λ\Lambda is a diagonal matrix,
    • P,Q∈RN×rP, Q \in \mathbb{R}^{N \times r} are the low-rank correction factors, with r=1r=1 or 22 for these matrices.

    This representation demonstrates that HiPPO matrices are well-structured and amenable to efficient computation using the NPLR framework.

S4 Complexity

NPLR matrices can be transformed into a diagonal plus low-rank matrix form (DPLR), but it is important to note that their elements extend from R\mathbb{R} to C\mathbb{C}.

When matrix AA is expressed in the DPLR form, the theorems give optimal or near-optimal computational bounds for recurrence and convolution at fixed low rank rr.

  • Theorem and Efficiency of S4 Recurrence

    • Theorem 2: Computational Efficiency of S4 Recurrence

      It is proven that for any given step size Δ\Delta, each step of the recurrence formula (3) can be computed in O(N)O(N) operations, where NN is the size of the state dimension.

  • Theorem and Efficiency of S4 Convolution

    • Theorem 3: Computational Efficiency of S4 Convolution Filter

      It is proven that for any given step size Δ\Delta, the computation of the SSM convolution filter KK can be reduced to 4 Cauchy matrix multiplications, requiring only O~(N+L)\tilde{O}(N + L) operations and O(N+L)O(N + L) space.

Theorem 3 represents the core technical contribution of this research, and its algorithm embodies the design motivation behind the NPLR S4 parameterization. The complete algorithm is outlined as follows:

The recurrence bound is O(N)O(N) per step, while the convolution-kernel bound is O~(N+L)\tilde{O}(N + L), with logarithmic factors hidden by the tilde. These are theoretical bounds: the paper's actual GPU implementation uses a parallel O(NL)O(NL) Cauchy-kernel algorithm through PyKeOps, rather than the asymptotically fast method.

Architecture Details

At initialization, the matrix AA in one S4 state space model (SSM) is set to the HiPPO matrix. According to Theorem 1, a unitary change of basis gives (Λ−PQ∗,B~,C~)(\Lambda - P Q^*, \widetilde B, \widetilde C). In the rank-one case, the diagonal of Λ\Lambda and each of P,Q,B~,C~P,Q,\widetilde B,\widetilde C have NN complex entries. This is the paper's 5N5N count for one SSM, not the entire deep layer with feature mixing and step sizes.

The deep SSM uses HH independent copies of the SSM, each with its own parameters, then mixes their features through position-wise linear layers. This lets S4 handle multiple feature channels while state transitions still connect time steps. Nonlinear activations between layers make the full network nonlinear. The paper counts about O(HN)+O(H2)O(HN)+O(H^2) parameters per layer.

The overall architecture outputs sequences in a shape consistent with other sequence models like Transformers, RNNs, and CNNs: (batch size, sequence length, hidden dimension).

Compared to other models, S4 shares similarities with convolutional neural networks (CNNs). While the S4 core module is a linear transformation, the overall deep SSM becomes nonlinear through the nonlinear transformations across layers. Additionally, the broadcasting of features across HH dimensions in the S4 layer resembles depthwise-separable convolutions, but S4’s convolution kernels are global.

The following table compares the computational complexities of the S4 layer and other sequence models:

Discussion

Efficiency Benchmarks

To evaluate the training speed and resource efficiency of S4, the authors conducted efficiency benchmarks, starting with a comparison against LSSL.

At dimensions 128, 256, and 512 in the table, S4's training steps are respectively 1.9, 6.7, and 29.6 times faster than LSSL, and its allocated memory is 42, 133, and 392 times lower. The gain varies with layer size.

Next, the authors compared S4 with efficient Transformer variants such as Linear Transformer and Performer. The results are shown in the table below. At sequence length 4096 with matched parameter counts, S4's speed and memory ratios relative to a standard Transformer are 5.19 and 0.091, close to Linear Transformer's 5.35 and 0.067.

Stability Benchmarks

The authors further investigated S4's stability in long-range reasoning by comparing its performance with other models on challenging tasks such as LRA and raw speech classification.

On LRA, S4 outperforms the baselines in the displayed table. The original results average 80.48%; the imported image shows the paper's later updated Table 2, with an 86.09% average and 96.35% on Path-X. The other models in that table average below 60%. The original and updated S4 figures come from different experimental versions and should not be read as the same row.

On the SC10 subset, S4 reaches 98.32% accuracy on raw waveforms of length 16,000, above the listed raw-waveform baselines and models using shorter MFCC features.

Visualization

The authors conducted a visualization analysis of S4's learned representations to further understand its performance.

The figure above visualizes convolution kernels from a trained S4 model on LRA Path-X. Each SSM kernel K∈R16384K \in \mathbb{R}^{16384} is reshaped into a 128×128128 \times 128 image.

The left image depicts an example from the Path-X task, where the model is required to determine whether two markers are connected by a path.

  • Top two rows (First Layer Convolution Kernels): These kernels show local patterns concentrated in a small number of rows.

  • Bottom two rows (Last Layer Convolution Kernels): These kernels show structure varying across columns and the full 16,384-pixel sequence, at different spatial frequencies.

Some learned kernels display two-dimensional spatial structure. Whether the model handles long-range dependencies is best judged alongside its Path-X test result, not from the visualization alone.

A General Model?

The authors conducted a series of experiments to explore whether S4 can function as a general sequence model.


Image Generation: CIFAR Density Estimation

CIFAR density estimation is a popular benchmark for autoregressive image modeling. The images are flattened into a sequence of 3072 RGB subpixels, which are predicted one by one.

Despite lacking a built-in two-dimensional image bias, S4 large reaches 2.85 bits per dimension (bpd), matching PixelSNAIL's 2.85 but trailing Sparse Transformer's 2.80. S4 base obtains 2.92 bpd; the figure's generation speeds also belong to their respective model sizes.


Text Generation: WikiText-103

WikiText-103 is a classic benchmark for language modeling, requiring the model to predict tokens in a sequence based on contextual order.

Replacing a Transformer's self-attention layers with S4 layers gives 20.95 test perplexity, versus 20.51 for the Transformer in the table, a difference of 0.44. The next best listed attention-free model is at 23.3. In the paper's generation setup, S4 produces 48K tokens per second versus 0.8K for the Transformer; this speed comparison belongs to that setup.


Time-Series Forecasting: Weather Data

S4 was applied to time-series forecasting tasks and compared with Informer, a model specifically designed for such problems.

The authors report S4 ahead of the comparison methods in 40 of 50 settings across five forecasting tasks. For Weather at a 720-step (30-day) horizon, its MSE is 0.245, versus Informer's 0.359, a reduction of about 31.8%. The paper's prose says 37%, which does not match those columns and is closer to the gap against LogTrans at 0.388.


Through these experiments, S4 shows potential as a general sequence model across image, text, and time-series tasks. Its generation speed and ability to adapt to sampling rates were measured under particular settings, so their value still depends on the application.

Importance of HiPPO

One of the key design aspects of S4 is using the HiPPO matrix to initialize the SSM.

The authors conducted ablation studies to evaluate the importance of various components and addressed the following questions:

  1. How important is HiPPO initialization?
  2. Is training the SSM on top of HiPPO necessary?
  3. Are the benefits of S4 derived solely from the NPLR parameterization, independent of HiPPO?

These ablations use Sequential CIFAR-10 with at most 100K trainable parameters and a learning-rate schedule triggered by a validation plateau. The first two experiments use no regularization; the third adds 0.1 dropout. Their conclusions are bounded by this task and model size.


Experiment 1: Unconstrained SSM Initialization

  • Comparison of Initialization Methods
    • Random Gaussian Initialization: Initializes matrixAA with a random Gaussian distribution.
    • HiPPO Initialization: Initializes AA using the HiPPO matrix.
    • Random Diagonal Matrix: Sets AA as a random diagonal matrix without applying S4's NPLR parameterization.
    • Both freezing and training AA were tested for the above initialization methods.

The results show that training the SSM improves performance across all initialization methods, with the largest gains observed for randomly initialized models.

The three models with trainable AA all approach perfect training accuracy, yet their validation accuracies differ by more than 15 percentage points, with HiPPO initialization highest.


Experiment 2: Combining NPLR Parameterization with HiPPO

This experiment tested whether HiPPO initialization is the primary driver of S4's success or if the benefits are derived solely from the NPLR parameterization.

In the plotted comparison with the same NPLR parameterization, the randomly initialized model's validation curve lies below the HiPPO-initialized one. This supports the role of HiPPO initialization in this ablation setting.


Experiment 3: Regularization and Full S4 Performance

This experiment added lightweight regularization (Dropout = 0.1) to the main ablation studies, comparing the performance of S4 with HiPPO initialization to other initialization methods.

In the plotted validation curves with 0.1 dropout, HiPPO initialization remains highest. Separately, the paper reports 84.27% test accuracy for full S4 (HiPPO + NPLR) with at most 100K trainable parameters.

Conclusion

In this paper, the authors introduced the "S4" sequence model, which leverages innovative parameterization of State Space Models (SSMs) by integrating continuous-time, recurrent, and convolutional perspectives. This approach provides an effective and principled solution to the Long-Range Dependency (LRD) problem.

Across a series of benchmarks, S4 demonstrated outstanding performance across various data modalities and model capabilities, showcasing its potential as a general solution for sequence modeling. It holds significant application value and research implications.