CoChat
Sign Up
PreprintCited by 805Topic ModelingAdvanced Neural Network ApplicationsTime Series Analysis and Forecasting

Efficiently Modeling Long Sequences with Structured State Spaces

Open access
Gu, Albert, Goel, Karan, Ré, Christopher·2021·arXiv
DOI 10.48550/arxiv.2111.00396arXiv 2111.00396
Open this paper in CoChat — free accountOpen PDF

Abstract

A central goal of sequence modeling is designing a single principled model that can address sequence data across a range of modalities and tasks, particularly on long-range dependencies. Although conventional models including RNNs, CNNs, and Transformers have specialized variants for capturing long dependencies, they still struggle to scale to very long sequences of $10000$ or more steps. A promising recent approach proposed modeling sequences by simulating the fundamental state space model (SSM) \( x'(t) = Ax(t) + Bu(t), y(t) = Cx(t) + Du(t) \), and showed that for appropriate choices of the state matrix \( A \), this system could handle long-range dependencies mathematically and empirically. However, this method has prohibitive computation and memory requirements, rendering it infeasible as a general sequence modeling solution. We propose the Structured State Space sequence model (S4) based on a new parameterization for the SSM, and show that it can be computed much more efficiently than prior approaches while preserving their theoretical strengths. Our technique involves conditioning \( A \) with a low-rank correction, allowing it to be diagonalized stably and reducing the SSM to the well-studied computation of a Cauchy kernel. S4 achieves strong empirical results across a diverse range of established benchmarks, including (i) 91\% accuracy on sequential CIFAR-10 with no data augmentation or auxiliary losses, on par with a larger 2-D ResNet, (ii) substantially closing the gap to Transformers on image and language modeling tasks, while performing generation $60\times$ faster (iii) SoTA on every task from the Long Range Arena benchmark, including solving the challenging Path-X task of length 16k that all prior work fails on, while being as efficient as all competitors.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2111.00396

Cites

6 of 6 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Modern recurrent architectures replace the growing key-value cache with a compact recurrent state, achieving constant cost per token.

    “Modern recurrent architectures approach this challenge by replacing the growing key-value cache with a compact recurrent state [38, 21, 20, 50, 22], achieving constant cost per token.”

    From Learning What to Remember: Test-Time Training via Context Distillation (2026) · cites this paper as [21]

    Section 2.3 (p. 4) describes a recurrent hidden state, and Section 4.3 (p. 10) says S4 uses constant memory and computation per time step during inference. The paper contrasts this with standard autoregressive models, but does not specifically describe replacing a growing key-value cache. (LLM, conf=0.82)

    Experimental — accuracy not yet measured

  • Recent recurrent and test-time training architectures use fixed-size states or fast-weight updates as sub-quadratic alternatives to full attention.

    “Recent recurrent and test-time training architectures use fixed-size states or fast-weight updates as sub-quadratic alternatives to full attention [21, 16, 35, 33, 20, 12, 52, 50].”

    From Learning What to Remember: Test-Time Training via Context Distillation (2026) · cites this paper as [21]

  • The model's per-token inference cost is O(1) in memory and O(d·N) in compute independent of context length.

    “Per-token inference cost is O (1) in memory and O ( d · N ) in compute independent of context length”

    From Structured Memory for Edge Language Models: Persistent Context and Corpus Retrieval via O(1) SSM State Injection (2026) · cites this paper as [1]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 41

  1. [1][1] Martin Arjovsky, Amar Shah, and Yoshua Bengio. Unitary evolution recurrent neural networks. In The International Conference on Machine Learning (ICML) , pages 1120-1128, 2016. -
  2. [2][2] Alexei Baevski and Michael Auli. Adaptive input representations for neural language modeling. arXiv preprint arXiv:1809.10853 , 2018. - · arXiv
  3. [3][3] Shaojie Bai, J Zico Kolter, and Vladlen Koltun. An empirical evaluation of generic convolutional and recurrent networks for sequence modeling. arXiv preprint arXiv:1803.01271 , 2018. - · arXiv
  4. [4][4] Shaojie Bai, J Zico Kolter, and Vladlen Koltun. Trellis networks for sequence modeling. In The International Conference on Learning Representations (ICLR) , 2019. -
  5. [5][5] Shiyu Chang, Yang Zhang, Wei Han, Mo Yu, Xiaoxiao Guo, Wei Tan, Xiaodong Cui, Michael Witbrock, Mark Hasegawa-Johnson, and Thomas S Huang. Dilated recurrent neural networks. In Advances in Neural Information Processing Systems (NeurIPS) , 2017. -
  6. [6][6] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv:1904.10509 , 2019. - · arXiv
  7. [7][7] Narsimha Chilkuri and Chris Eliasmith. Parallelizing legendre memory unit training. The International Conference on Machine Learning (ICML) , 2021. -
  8. [9][9] Yann N Dauphin, Angela Fan, Michael Auli, and David Grangier. Language modeling with gated convolutional networks. In International conference on machine learning , pages 933-941. PMLR, 2017. -
  9. [10][10] Edward De Brouwer, Jaak Simm, Adam Arany, and Yves Moreau. Gru-ode-bayes: Continuous modeling of sporadically-observed time series. In Advances in Neural Information Processing Systems (NeurIPS) , 2019. -
  10. [11][11] Chris Donahue, Julian McAuley, and Miller Puckette. Adversarial audio synthesis. In ICLR , 2019. -
  11. [13][13] N Benjamin Erichson, Omri Azencot, Alejandro Queiruga, Liam Hodgkinson, and Michael W Mahoney. Lipschitz recurrent neural networks. In International Conference on Learning Representations , 2021. -
  12. [14][14] Karan Goel, Albert Gu, Chris Donahue, and Christopher R´ e. It's raw! audio generation with state-space models. arXiv preprint arXiv:2202.09729 , 2022. - · arXiv
  13. [15][15] Gene H Golub and Charles F Van Loan. Matrix computations , volume 3. JHU press, 2013. -
  14. [16][16] Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher R´ e. Hippo: Recurrent memory with optimal polynomial projections. In Advances in Neural Information Processing Systems (NeurIPS) , 2020. -
  15. [17][17] Albert Gu, Caglar Gulcehre, Tom Le Paine, Matt Hoffman, and Razvan Pascanu. Improving the gating mechanism of recurrent neural networks. In The International Conference on Machine Learning (ICML) , 2020. -
  16. [18][18] Albert Gu, Isys Johnson, Karan Goel, Khaled Saab, Tri Dao, Atri Rudra, and Christopher R´ e. Combining recurrent, convolutional, and continuous-time models with the structured learnable linear state space layer. In Advances in Neural Information Processing Systems (NeurIPS) , 2021. -
  17. [19][19] Albert Gu, Ankit Gupta, Karan Goel, and Christopher R´ e. On the parameterization and initialization of diagonal state space models. arXiv preprint arXiv:2206.11893 , 2022. - · arXiv
  18. [20][20] Albert Gu, Isys Johnson, Aman Timalsina, Atri Rudra, and Christopher R´ e. How to train your hippo: State space models with generalized basis projections. arXiv preprint arXiv:2206.12037 , 2022. - · arXiv
  19. [23][23] Patrick Kidger, James Morrill, James Foster, and Terry Lyons. Neural controlled differential equations for irregular time series. arXiv preprint arXiv:2005.08926 , 2020. - · arXiv
  20. [24][24] Mario Lezcano-Casado and David Mart´ ınez-Rubio. Cheap orthogonal constraints in neural networks: A simple parametrization of the orthogonal and unitary group. In The International Conference on Machine Learning (ICML) , 2019. -
  21. [25][25] Shuai Li, Wanqing Li, Chris Cook, Ce Zhu, and Yanbo Gao. Independently recurrent neural network (IndRNN): Building a longer and deeper RNN. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition , pages 5457-5466, 2018. -
  22. [26][26] Vasileios Lioutas and Yuhong Guo. Time-aware large kernel convolutions. In International Conference on Machine Learning , pages 6172-6183. PMLR, 2020. -
  23. [29][29] Victor Pan. Structured matrices and polynomials: unified superfast algorithms . Springer Science & Business Media, 2001. -
  24. [32][32] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning , pages 1310-1318, 2013. -
  25. [33][33] Jack Rae, Chris Dyer, Peter Dayan, and Timothy Lillicrap. Fast parametric learning with activation memorization. The International Conference on Machine Learning (ICML) , 2018. -
  26. [34][34] Prajit Ramachandran, Tom Le Paine, Pooya Khorrami, Mohammad Babaeizadeh, Shiyu Chang, Yang Zhang, Mark A Hasegawa-Johnson, Roy H Campbell, and Thomas S Huang. Fast generation for convolutional autoregressive models. arXiv preprint arXiv:1704.06001 , 2017. - · arXiv
  27. [35][35] David W Romero, Anna Kuzina, Erik J Bekkers, Jakub M Tomczak, and Mark Hoogendoorn. Ckconv: Continuous kernel convolution for sequential data. arXiv preprint arXiv:2102.02611 , 2021. - · arXiv
  28. [36][36] David W Romero, Robert-Jan Bruintjes, Jakub M Tomczak, Erik J Bekkers, Mark Hoogendoorn, and Jan C van Gemert. Flexconv: Continuous kernel convolutions with differentiable kernel sizes. In The International Conference on Learning Representations (ICLR) , 2022. -
  29. [37][37] Yulia Rubanova, Tian Qi Chen, and David K Duvenaud. Latent ordinary differential equations for irregularly-sampled time series. In Advances in Neural Information Processing Systems , pages 5321-5331, 2019. -
  30. [38][38] T Konstantin Rusch and Siddhartha Mishra. Unicornn: A recurrent model for learning very long time dependencies. The International Conference on Machine Learning (ICML) , 2021. -
  31. [39][39] Tim Salimans, Andrej Karpathy, Xi Chen, and Diederik P Kingma. Pixelcnn++: Improving the pixelcnn with discretized logistic mixture likelihood and other modifications. arXiv preprint arXiv:1701.05517 , 2017. - · arXiv
  32. [40][40] Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena : A benchmark for efficient transformers. In International Conference on Learning Representations , 2021. URL https://openreview.net/forum? id=qVyeW-grC2k . -
  33. [41][41] Ilya Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Unterthiner, Jessica Yung, Daniel Keysers, Jakob Uszkoreit, Mario Lucic, et al. Mlp-mixer: An all-mlp architecture for vision. arXiv preprint arXiv:2105.01601 , 2021. - · arXiv
  34. [42][42] Trieu H Trinh, Andrew M Dai, Minh-Thang Luong, and Quoc V Le. Learning longer-term dependencies in RNNs with auxiliary losses. In The International Conference on Machine Learning (ICML) , 2018. -
  35. [43][43] Arnold Tustin. A method of analysing the behaviour of linear systems in terms of time series. Journal of the Institution of Electrical Engineers-Part IIA: Automatic Regulators and Servo Mechanisms , 94(1): 130-142, 1947. -
  36. [44][44] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems (NeurIPS) , 2017. -
  37. [45][45] Aaron Voelker, Ivana Kaji´ c, and Chris Eliasmith. Legendre memory units: Continuous-time representation in recurrent neural networks. In Advances in Neural Information Processing Systems , pages 15544-15553, 2019. -
  38. [46][46] Aaron Russell Voelker. Dynamical systems in spiking neuromorphic hardware . PhD thesis, University of Waterloo, 2019. -
  39. [47][47] Pete Warden. Speech commands: A dataset for limited-vocabulary speech recognition. ArXiv , abs/1804.03209, 2018. - · arXiv
  40. [49][49] Felix Wu, Angela Fan, Alexei Baevski, Yann N Dauphin, and Michael Auli. Pay less attention with lightweight and dynamic convolutions. In The International Conference on Learning Representations (ICLR) , 2019. -
  41. [50][50] Haoyi Zhou, Shanghang Zhang, Jieqi Peng, Shuai Zhang, Jianxin Li, Hui Xiong, and Wancai Zhang. Informer: Beyond efficient transformer for long sequence time-series forecasting. In The Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Virtual Conference , volume 35, pages 1110611115. AAAI Press, 2021.

Cited by

Sorted by citations

Authors
Gu, A., Goel, K., & Ré, C.
Affiliations
Stanford University (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2021
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2111.00396
arXiv
2111.00396
OpenAlex
W3209374680
Cited by
805
References
6
Citations by year
2026: 38 · 2025: 457 · 2024: 247 · 2023: 59 · 2022: 4
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • National Science Foundation (1937301)
  • Gordon and Betty Moore Foundation
  • Accenture
  • VMware
  • National Institutes of Health (N000141712266, CCF1563078, CCF1763315)
  • Office of Naval Research (N000141712266, ONR-N00014, N00014-20, N00014)
  • National Institute of Biomedical Imaging and Bioengineering (U54EB020405, P41EB027060)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
  • Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Neural Network Applications
  • Physical Sciences › Computer Science › Signal Processing › Time Series Analysis and Forecasting
Keywords
structured state space models, S4, long-range dependencies, sequence modeling, Cauchy kernel, efficient computation

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review