Diagonal State Spaces are as Effective as Structured State Spaces

Ankit Gupta, Albert Gu, Jonathan Berant

TL;DR

The Structured State Space (S4) model recently revolutionized long-range sequence modeling, but its reliance on complex "Diagonal Plus Low Rank" (DPLR) matrices made it difficult to implement and analyze. This paper introduces Diagonal State Spaces (DSS), proving that the low-rank correction is unnecessary. A much simpler, purely diagonal parameterization matches S4’s state-of-the-art performance while being significantly easier to code and understand.

What Problem Does This Paper Address?

Modern AI excels at short-range patterns (like predicting the next word in a sentence) but struggles with "long-range dependencies"—relationships between data points separated by thousands of steps, such as pixels in a high-resolution image or samples in a long audio clip.

While Transformers are the gold standard for many tasks, their self-attention mechanism has a computational cost that grows quadratically ($O(L^2)$) with sequence length, making them impractical for very long inputs. The S4 model solved this by using linear State Space Models (SSMs), which can be computed efficiently via convolutions. However, S4’s design was deeply tied to the "HiPPO" theory, requiring a complex mathematical structure (DPLR) to maintain stability and performance. The authors of this paper asked a fundamental question: Is all that complexity actually necessary, or can we get the same results with a simpler diagonal model?

Methods: The Diagonal State Space (DSS)

The authors propose the Diagonal State Space (DSS). Instead of the complex DPLR matrices used in S4, DSS uses a state matrix $A$ that is strictly diagonal.

Key technical components include:

  • Discretization: Like S4, DSS translates a continuous-time differential equation into a discrete sequence-to-sequence map.
  • Two Variants: They introduce $\text{DSS}_{\text{EXP}}$ (which ensures stability by forcing the real part of the state to be negative) and $\text{DSS}_{\text{SOFTMAX}}$ (which uses a softmax-based normalization to bound the kernel values).
  • Skew-Hippo Initialization: The authors found that while the structure of the matrix can be simple, the initialization is critical. They initialize the diagonal elements using the eigenvalues of the "HiPPO" matrix, a technique they call Skew-Hippo initialization.
  • Efficiency: Because the matrices are diagonal, the model can be implemented in just a few lines of code and computed extremely fast using Fast Fourier Transforms (FFTs).
Algorithm for DSS_SOFTMAX Kernel

Datasets and Key Results

The model was evaluated on two major benchmarks known for requiring long-range reasoning: the Long Range Arena (LRA) (a suite of six tasks with sequence lengths ranging from 1,000 to 16,000 tokens) and Speech Commands (SC) (raw audio samples for 10-way keyword classification).

Long Range Arena (LRA) Benchmark Results
  • LRA Superiority: DSS achieved an average accuracy of 81.88% across the LRA suite, slightly outperforming the original S4 (80.21%) and crushing the best Transformer variant (61.41%).
  • Path-X Success: DSS successfully solved the notoriously difficult Path-X task (87.8% accuracy), a benchmark where almost all previous models, including standard Transformers, failed completely (performing at chance level).
  • Speech Performance: On raw audio (Speech Commands), DSS matched S4 with an accuracy of 98.2%, proving its effectiveness in the audio domain.
  • Simplicity: The authors emphasize that their PyTorch implementation fits on a single page, making it a much more accessible "plug-and-play" layer for researchers.

Key Insights and Ideas

  • Diagonalization is Sufficient: The paper provides a mathematical proposition showing that diagonal state spaces are, in theory, just as expressive as general state spaces. The "low-rank" part of S4 wasn't providing extra power; it was just one way to achieve stability.
  • Initialization is the Secret Sauce: A random diagonal initialization performs poorly. The success of these models depends on starting with the right "spectral" properties (the Skew-Hippo init), which allows the model to capture different frequencies and time-scales of the input signal.
  • Visualizing the "Memory": By plotting the learned kernels, the authors show that for "local" tasks like image classification, the model learns to look only at the most recent pixels. For "global" tasks like Path-X, the model learns kernels that maintain high values even for very distant past inputs, effectively "remembering" the beginning of the sequence.

Limitations and Future Work

  • Sensitivity to Hyperparameters: The authors noted that the learning rate for the initialization parameters ($\Delta_{\text{log}}$) is quite sensitive and varies by task.
  • Numerical Stability: In the $\text{DSS}_{\text{SOFTMAX}}$ variant, certain tasks (like ListOps) produced outlier values that could potentially lead to training instabilities.
  • Scope: This work focused on sequence classification. The authors suggest that future work should explore "token-level" generation (like language modeling) and pre-training on massive datasets to see if the diagonal advantage holds at scale.

Summary updated

Abstract

Modeling long range dependencies in sequential data is a fundamental step towards attaining human-level performance in many modalities such as text, vision, audio and video. While attention-based models are a popular and effective choice in modeling short-range interactions, their performance on tasks requiring long range reasoning has been largely inadequate. In an exciting result, Gu et al. (ICLR 2022) proposed the $\textit{Structured State Space}$ (S4) architecture delivering large gains over state-of-the-art models on several long-range tasks across various modalities. The core proposition of S4 is the parameterization of state matrices via a diagonal plus low rank structure, allowing efficient computation. In this work, we show that one can match the performance of S4 even without the low rank correction and thus assuming the state matrices to be diagonal. Our $\textit{Diagonal State Space}$ (DSS) model matches the performance of S4 on Long Range Arena tasks, speech classification on Speech Commands dataset, while being conceptually simpler and straightforward to implement.
BibTeX
@inproceedings{gupta2022diagonal,
  author = {Ankit Gupta and Albert Gu and Jonathan Berant},
  title = {{Diagonal State Spaces are as Effective as Structured State Spaces}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=eGFINVfwai},
}
Figure