31 October 2021

S4: structured state spaces advance long-sequence modelling

Albert Gu, Karan Goel, and Christopher Ré introduced S4, a sequence model based on structured state spaces that achieved state-of-the-art results on the Long Range Arena benchmark and solved the Path-X task of length 16,000 steps that all prior work had failed.

Architectures and models Machine learning Neural networks Recurrent networks and LSTM Foundational method Independently validated

Background

Sequence modelling asks a single system to handle data of very different kinds: audio, text, images processed pixel by pixel, time-series signals. The long-standing difficulty is that useful patterns in a sequence are sometimes separated by thousands of steps. A model that forgets early context before it reaches the later, related part cannot learn those patterns.

RNNs, CNNs, and Transformers each have specialised variants designed to help with this, but as Albert Gu, Karan Goel, and Christopher Ré noted, they “still struggle to scale to very long sequences of 10000 or more steps.” An earlier approach had tried modelling sequences by simulating a continuous-time state space model, the system described by the equations x’(t) = Ax(t) + Bu(t), y(t) = Cx(t) + Du(t). For the right choice of the matrix A, that approach could handle long-range dependencies in theory and in practice. The catch was cost: the computation and memory requirements were prohibitive enough to rule it out as a practical general-purpose tool.

What happened

Gu, Goel, and Ré proposed the Structured State Space sequence model, S4. The key idea was a new parameterisation for the state matrix A. Rather than working with A directly, they conditioned it with a low-rank correction. That let them diagonalise A in a numerically stable way, which in turn reduced the whole computation to evaluating a Cauchy kernel, a well-studied mathematical object with efficient algorithms. The result preserved the theoretical properties of the earlier state space approach while cutting the computational cost to a level that made it usable.

The empirical results covered a wide spread of tasks. On sequential CIFAR-10, S4 reached 91% accuracy without data augmentation or auxiliary losses. The paper notes that is “on par with a larger 2-D ResNet.” On image and language modelling, S4 substantially narrowed the gap to Transformers, while producing outputs approximately 60 times faster in autoregressive mode.

The sharpest result came from the Long Range Arena, a benchmark suite specifically designed to test how well models handle long dependencies. S4 achieved state of the art on every task in the suite. That included Path-X, a spatial reasoning problem over sequences of length 16,000, which the paper describes as a “challenging” task that “all prior work fails on.” S4 solved it while remaining as efficient as the competing methods.

The paper was submitted to arXiv on 31 October 2021 and later received an Outstanding Paper Honourable Mention at ICLR 2022.

Why it mattered

S4 was the first method to solve every task in the Long Range Arena benchmark, including Path-X at sequence length 16,000, which had defeated all prior approaches. It achieved 91% accuracy on sequential CIFAR-10 with no data augmentation, approaching the accuracy of a 2-D ResNet as reported by the authors, while generating sequences approximately 60 times faster than Transformers in autoregressive mode. The work showed that state space models, with the right parameterisation, could deliver competitive performance across diverse modalities on standard benchmarks.

Sources

Efficiently Modeling Long Sequences with Structured State Spaces. arxiv.org. Primary source
Efficiently Modeling Long Sequences with Structured State Spaces. arxiv.org. Primary source

Cite this page

AI Achievements. (2021). S4: structured state spaces advance long-sequence modelling. Retrieved 2026-08-29, from https://achievements.ai/milestone/s4-structured-state-spaces-advance-long-sequence-modelling

@misc{achievements_s4_structured_state_spaces_advance_long_sequence_modelling,
  title  = {S4: structured state spaces advance long-sequence modelling},
  author = {{AI Achievements}},
  year   = {2021},
  url    = {https://achievements.ai/milestone/s4-structured-state-spaces-advance-long-sequence-modelling}
}