Efficiently Modeling Long Sequences with Structured State Spaces

The paper introduces the Structured State Space sequence model (S4), aiming at a single principled model for sequence data across modalities and tasks, especially long-range dependencies where conventional RNNs, CNNs, and Transformers struggle beyond 10,000 steps. It builds on the continuous state space model x'(t)=Ax(t)+Bu(t), y(t)=Cx(t)+Du(t), which handles long dependencies for appropriate choices of A but had prohibitive computation and memory costs. S4 introduces a new parameterization that conditions A with a low-rank correction, allowing stable diagonalization and reducing the SSM to the well-studied computation of a Cauchy kernel, so it can be computed much more efficiently while preserving theoretical strengths.

Empirically, S4 delivers strong results across benchmarks: 91% accuracy on sequential CIFAR-10 without data augmentation or auxiliary losses, on par with a larger 2-D ResNet; it substantially closes the gap to Transformers on image and language modeling while generating 60x faster; and it achieves state of the art on every Long Range Arena task, including solving the challenging 16k-length Path-X task that all prior work fails on, while remaining as efficient as competitors. This mattered because it made state space models a practical, general-purpose tool for very long sequence modeling.