Diagonal State Spaces are as Effective as Structured State Spaces

Ankit Gupta

TL;DR

This paper introduces Diagonal State Spaces (DSS), a simpler yet equally effective alternative to the recent Structured State Space (S4) model for handling long-range dependencies in sequential data. DSS achieves comparable performance to S4 on challenging benchmarks like the Long Range Arena and Speech Commands dataset, but with a significantly simpler architecture and implementation.

What Problem Does This Paper Address?

Modern deep learning models, particularly Transformers, excel at capturing short-range dependencies in sequential data (like text, audio, or images). However, their performance degrades significantly on tasks requiring the model to understand relationships between elements that are far apart in the sequence. This is largely due to the quadratic computational complexity of the attention mechanism in Transformers. While the S4 model offered a breakthrough by using state-space models to efficiently handle long-range dependencies, its complex parameterization (diagonal plus low-rank structure) made it difficult to understand, implement, and analyze. This paper addresses the need for a simpler, yet equally powerful, approach to long-range sequential modeling.

Methods

The core innovation of this paper is the Diagonal State Space (DSS) model. Building on the theoretical insight that general state-space models can be approximated by diagonal ones (Proposition 1), DSS simplifies the S4 architecture by removing the "low-rank" component from the state matrix. This means the state matrix is purely diagonal, making computations much more straightforward.

The paper proposes two variants of DSS:

  • DSSEXP: This variant uses a diagonal state matrix and restricts the real part of its eigenvalues to be negative. This ensures numerical stability but might limit expressiveness.
  • DSSSOFTMAX: This variant uses a diagonal state matrix and employs a numerically stable softmax function to parameterize the state matrix. This approach is shown to be as expressive as general state spaces and is the primary focus of their experiments.

Crucially, DSS avoids complex mathematical machinery like Padé approximations, Woodbury identity reductions, and Fourier analysis that were necessary for S4's efficient computation. The DSS layer can be implemented in just a few lines of code.

Datasets

The paper evaluates DSS on the following datasets:

  • Long Range Arena (LRA): A benchmark suite for sequence-level classification tasks with diverse input lengths (1K-16K) across modalities like text, images, and mathematical expressions.
  • Speech Commands (SC): A dataset for raw speech classification, consisting of audio samples of length 16000.

Key Insights and Ideas

  • Diagonal is Sufficient: The most significant insight is that a purely diagonal state matrix is sufficient to achieve state-of-the-art performance on long-range dependency tasks, matching the more complex diagonal-plus-low-rank structure of S4. This dramatically simplifies the model.
  • Initialization Matters: The performance of state-space models is highly sensitive to initialization. The paper highlights the importance of a "Skew-Hippo" initialization for the state matrix, which significantly outperforms random initialization.
  • Kernel Locality vs. Long-Range: The paper visually analyzes learned kernels and finds that for tasks requiring local interactions (like IMAGE and SC), the kernels are indeed local. However, for tasks demanding long-range reasoning (like PATH-X), the kernels exhibit long-range behavior, explaining the model's effectiveness.
  • Simplicity Breeds Efficiency: By removing the low-rank component, DSS becomes significantly easier to implement and analyze, making it more accessible for researchers and practitioners.

Key Results

  • LRA Performance: DSS achieved an average accuracy of 81.88% on the Long Range Arena, comparable to S4's 80.21% and significantly outperforming the best Transformer variant (61.41%).
  • Speech Commands Performance: On the Speech Commands dataset, DSS variants achieved performance comparable to S4 (98.2% vs. 98.1%).
  • Ablation Studies:
    • Random initialization of the state matrix led to a significant performance drop, confirming the importance of structured initialization.
  • Truncating the kernel length (limiting it to 128) also degraded performance, underscoring the role of long-range modeling capabilities.

Limitations and Future Work

  • Initialization Sensitivity: While the paper demonstrates the effectiveness of Skew-Hippo initialization, the sensitivity of DSS parameters (especially $\Delta_{log}$) to initialization and learning rates is noted as an area for future investigation.
  • Token-Level Generation: The current evaluation focuses on sequence-level classification. Future work aims to extend DSS to token-level generation tasks like language modeling and forecasting.
  • Pretraining: The authors suggest pretraining DSS models on large amounts of raw data as a promising future direction.
  • Outlier in LISTOPS: An outlier value in the LISTOPS task's $\Delta_{log}$ parameter was observed, which could potentially lead to training instabilities. Addressing this is a future research direction.

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},
  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