mlsanityData to 14 Oct 2026

The Expressive Capacity of State Space Models: A Formal Language Perspective

arXiv 2405.17394 ↗First posted 27 May 2024cs.CL cs.FL cs.LGcited by 46

Not on the map. Why?

Abstract (arXiv)

Recently, recurrent models based on linear state space models (SSMs) have shown promising performance in language modeling (LM), competititve with transformers. However, there is little understanding of the in-principle abilities of such models, which could provide useful guidance to the search for better LM architectures. We present a comprehensive theoretical study of the capacity of such SSMs as it compares to that of transformers and traditional RNNs. We find that SSMs and transformers have overlapping but distinct strengths. In star-free state tracking, SSMs implement straightforward and exact solutions to problems that transformers struggle to represent exactly. They can also model bounded hierarchical structure with optimal memory even without simulating a stack. On the other hand, we identify a design choice in current SSMs that limits their expressive power. We discuss implications for SSM and LM research, and verify results empirically on a recent SSM, Mamba.

Key facts. Cited by 46 papers in the map (data through 14 Oct 2026). Builds on 47 of its 87 references that are in the map. First posted on arXiv 27 May 2024.

Builds on

47 of 87 references.

References · 47

  1. 2017Attention Is All You Needcited by 60,361
  2. 2016Layer Normalizationcited by 5,669
  3. 2023Mamba: Linear-Time Sequence Modeling with Selective State Spacescited by 4,718
  4. 2021Efficiently Modeling Long Sequences with Structured State Spacescited by 2,465
  5. 2020GLU Variants Improve Transformercited by 1,804
  6. 2019Root Mean Square Layer Normalizationcited by 1,480
  7. 2016Language Modeling with Gated Convolutional Networkscited by 702
  8. 2023Retentive Network: A Successor to Transformer for Large Language Modelscited by 613
  9. 2020HiPPO: Recurrent Memory with Optimal Polynomial Projectionscited by 605
  10. 2023Gated Linear Attention Transformers with Hardware-Efficient Trainingcited by 514
  11. 2022Hungry Hungry Hippos: Towards Language Modeling with State Space Modelscited by 499
  12. 2023Resurrecting Recurrent Neural Networks for Long Sequencescited by 408
35 more
  1. 2016Assessing the Ability of LSTMs to Learn Syntax-Sensitive Dependenciescited by 354
  2. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
  3. 2022Transformers Learn Shortcuts to Automatacited by 268
  4. 2022Long Range Language Modeling via Gated State Spacescited by 265
  5. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 257
  6. 2024Griffin: Mixing Gated Linear Recurrences with Local Attention for Efficient Language Modelscited by 242
  7. 2022Neural Networks and the Chomsky Hierarchycited by 217
  8. 2024Repeat After Me: Transformers are Better than State Space Models at Copyingcited by 216
  9. 2024The Illusion of State in State-Space Modelscited by 187
  10. 2023Representational Strengths and Limitations of Transformerscited by 133
  11. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  12. 2024HGRN2: Gated Linear RNNs with State Expansioncited by 127
  13. 2023What Formal Languages Can Transformers Express? A Surveycited by 124
  14. 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
  15. 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 113
  16. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  17. 2023Hierarchically Gated Recurrent Neural Network for Sequence Modelingcited by 102
  18. 2024In-Context Language Learning: Architectures and Algorithmscited by 89
  19. 2016Quasi-Recurrent Neural Networkscited by 87
  20. 2023Exposing Attention Glitches with Flip-Flop Language Modelingcited by 75
  21. 2024Why are Sensitive Functions Hard for Transformers?cited by 74
  22. 2022A Logic for Expressing Log-Precision Transformerscited by 67
  23. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 66
  24. 2024On Limitations of the Transformer Architecturecited by 63
  25. 2017Simple Recurrent Units for Highly Parallelizable Recurrencecited by 61
  26. 2020RNNs can generate bounded hierarchical languages with optimal memorycited by 59
  27. 2023State-space Models with Layer-wise Nonlinearity are Universal Approximators with Exponential Decaying Memorycited by 39
  28. 2024Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformerscited by 39
  29. 2023Universality of Linear Recurrences Followed by Non-linear Projections: Finite-Width Guarantees and Benefits of Complex Eigenvaluescited by 36
  30. 2023StableSSM: Alleviating the Curse of Memory in State-space Models through Stable Reparameterizationcited by 30
  31. 2023Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuitscited by 26
  32. 2024Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theorycited by 19
  33. 2023Robustifying State-space Models for Long Sequences via Approximate Diagonalizationcited by 18
  34. 2018On Evaluating the Generalization of LSTM Models in Formal Languagescited by 17
  35. 2023Noncompact uniform universal approximationcited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 19; 2026: 25.

46 papers.

Sort:

By area:

  1. 2024Unlocking State-Tracking in Linear RNNs Through Negative Eigenvaluescited by 101
  2. 2026Mamba-3: Improved Sequence Modeling using State Space Principlescited by 89
  3. 2025DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Productscited by 75
  4. 2025MesaNet: Sequence Modeling by Locally Optimal Test-Time Trainingcited by 47
  5. 2025Implicit Language Models are RNNs: Balancing Parallelization and Expressivitycited by 22
  6. 2025Structured Sparse Transition Matrices to Enable State Tracking in State-Space Modelscited by 16
  7. 2024On the Expressiveness and Length Generalization of Selective State-Space Models on Regular Languagescited by 15
  8. 2025Blending Complementary Memory Systems in Hybrid Quadratic-Linear Transformerscited by 12
  9. 2025From Markov to Laplace: How Mamba In-Context Learns Markov Chainscited by 11
  10. 2026The Expressive Limits of Diagonal SSMs for State-Trackingcited by 9
  11. 2025Fast weight programming and linear transformers: from machine learning to neurobiologycited by 8
  12. 2026Why Are Linear RNNs More Parallelizable?cited by 8
34 more
  1. 2025Understanding Input Selectivity in Mamba: Impact on Approximation Power, Memorization, and Associative Recall Capacitycited by 7
  2. 2025Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilitiescited by 6
  3. 2026Learning State-Tracking from Code Using Linear RNNscited by 6
  4. 2025Generalization Error Analysis for Selective State-Space Models Through the Lens of Attentioncited by 5
  5. 2025Fixed-Point RNNs: Interpolating from Diagonal to Densecited by 5
  6. 2025Overcoming Long-Context Limitations of State-Space Models via Context-Dependent Sparse Attentioncited by 5
  7. 2025On the Expressivity of Selective State-Space Layers: A Multivariate Polynomial Approachcited by 4
  8. 2025Revisiting Bi-Linear State Transitions in Recurrent Neural Networkscited by 4
  9. 2026Rethinking State Tracking in Recurrent Models Through Error Control Dynamicscited by 4
  10. 2026The Capability Convergence Hypothesis: Capability from Access Structure, Not Scalecited by 4
  11. 2025Multilingual State Space Models for Structured Question Answering in Indic Languagescited by 3
  12. 2026On the Expressiveness of State Space Models via Temporal Logicscited by 2
  13. 2026On the "Induction Bias" in Sequence Modelscited by 2
  14. 2026An Algebraic View of the Expressivity of Recurrent Language Modelscited by 2
  15. 2026Indexing: the Beginning and the Endcited by 2
  16. 2025Three tiers of computation in transformers and in brain architecturescited by 1
  17. 2025Parity Requires Unified Input Dependence and Negative Eigenvalues in SSMscited by 1
  18. 2025The Computational Complexity of Satisfiability in State Space Modelscited by 1
  19. 2026Bayesian Optimality of In-Context Learning with Selective State Spacescited by 1
  20. 2026On the Expressive Power and Limitations of Multi-Layer SSMscited by 1
  21. 2026Length Generalization with Log-Depth Recurrent Unitscited by 1
  22. 2026An expressivity analysis of hierarchical modelling in deep transformers via bounded-depth grammarscited by 1
  23. 2026SHiPPO: Recurrent Memory with Transported Polynomial Projectionscited by 1
  24. 2026State Propagation Also Satisfies: A Complex-Valued State-Space Model for Deterministic State Trackingcited by 1
  25. 2025mGRADE: Minimal Recurrent Gating Meets Delay Convolutions for Lightweight Sequence Modelingcited by 0
  26. 2026Logic-Gated Time-Shared Feedforward Networks for Alternating Finite Automata: Exact Simulation and Learnabilitycited by 0
  27. 2026The UNDO Flip-Flop: A Controlled Probe for Reversible Semantic State Management in State Space Modelcited by 0
  28. 2026Flash PD-SSM: Memory-Optimized Structured Sparse State-Space Modelscited by 0
  29. 2026Refit the Probe: Single-Direction Ablation Is Not a Necessity Testcited by 0
  30. 2026When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?cited by 0
  31. 2026How Wrong Can a Good Predictor Be? Diverging Updates with Vanishing Predictive KLcited by 0
  32. 2026Length-Independent State Tracking Under a Parallel Scancited by 0
  33. 2026Beyond Diagonal State Space Models: Exact Non-Abelian Group Tracking, Solvability Barriers, and Geometric Physical Manifoldscited by 0
  34. 2026Rotate the Loop: Blockwise Conformality for Looped Transformerscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Interpreting and Steering State-Space Models via Activation Subspace Bottlenecks
  2. 2024An Empirical Study of Mamba-based Language Models
  3. 2026Harmonic: Hierarchical State Space Models for Efficient Long-Context Language Modeling
  4. 2026Towards Understanding What State Space Models Learn About Code
  5. 2026Benchmarking the Computational and Representational Efficiency of State Space Models against Transformers on Long-Context Dyadic Sessions
  6. 2023State space models can express n-gram languages
  7. 2025Scaling Laws for State Dynamics in Large Language Models
  8. 2025Exploring State Tracking Capabilities of Large Language Models