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

arXiv: https://arxiv.org/abs/2405.17394 · HTML: https://mlsanity.com/paper/2405.17394/

## 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 (most cited first, 30 of 47)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [GLU Variants Improve Transformer](https://mlsanity.com/paper/2002.05202/) (2020)
- [Root Mean Square Layer Normalization](https://mlsanity.com/paper/1910.07467/) (2019)
- [Language Modeling with Gated Convolutional Networks](https://mlsanity.com/paper/1612.08083/) (2016)
- [Retentive Network: A Successor to Transformer for Large Language Models](https://mlsanity.com/paper/2307.08621/) (2023)
- [HiPPO: Recurrent Memory with Optimal Polynomial Projections](https://mlsanity.com/paper/2008.07669/) (2020)
- [Gated Linear Attention Transformers with Hardware-Efficient Training](https://mlsanity.com/paper/2312.06635/) (2023)
- [Hungry Hungry Hippos: Towards Language Modeling with State Space Models](https://mlsanity.com/paper/2212.14052/) (2022)
- [Resurrecting Recurrent Neural Networks for Long Sequences](https://mlsanity.com/paper/2303.06349/) (2023)
- [Assessing the Ability of LSTMs to Learn Syntax-Sensitive Dependencies](https://mlsanity.com/paper/1611.01368/) (2016)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Long Range Language Modeling via Gated State Spaces](https://mlsanity.com/paper/2206.13947/) (2022)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Griffin: Mixing Gated Linear Recurrences with Local Attention for Efficient Language Models](https://mlsanity.com/paper/2402.19427/) (2024)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Repeat After Me: Transformers are Better than State Space Models at Copying](https://mlsanity.com/paper/2402.01032/) (2024)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [On the Turing Completeness of Modern Neural Network Architectures](https://mlsanity.com/paper/1901.03429/) (2019)
- [HGRN2: Gated Linear RNNs with State Expansion](https://mlsanity.com/paper/2404.07904/) (2024)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://mlsanity.com/paper/1805.04908/) (2018)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [Self-Attention Networks Can Process Bounded Hierarchical Languages](https://mlsanity.com/paper/2105.11115/) (2021)
- [Hierarchically Gated Recurrent Neural Network for Sequence Modeling](https://mlsanity.com/paper/2311.04823/) (2023)
- [In-Context Language Learning: Architectures and Algorithms](https://mlsanity.com/paper/2401.12973/) (2024)

## Built on by (most cited first, 30 of 46)

- [Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues](https://mlsanity.com/paper/2411.12537/) (2024)
- [Mamba-3: Improved Sequence Modeling using State Space Principles](https://mlsanity.com/paper/2603.15569/) (2026)
- [DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Products](https://mlsanity.com/paper/2502.10297/) (2025)
- [MesaNet: Sequence Modeling by Locally Optimal Test-Time Training](https://mlsanity.com/paper/2506.05233/) (2025)
- [Implicit Language Models are RNNs: Balancing Parallelization and Expressivity](https://mlsanity.com/paper/2502.07827/) (2025)
- [Structured Sparse Transition Matrices to Enable State Tracking in State-Space Models](https://mlsanity.com/paper/2509.22284/) (2025)
- [On the Expressiveness and Length Generalization of Selective State-Space Models on Regular Languages](https://mlsanity.com/paper/2412.19350/) (2024)
- [Blending Complementary Memory Systems in Hybrid Quadratic-Linear Transformers](https://mlsanity.com/paper/2506.00744/) (2025)
- [From Markov to Laplace: How Mamba In-Context Learns Markov Chains](https://mlsanity.com/paper/2502.10178/) (2025)
- [The Expressive Limits of Diagonal SSMs for State-Tracking](https://mlsanity.com/paper/2603.01959/) (2026)
- [Fast weight programming and linear transformers: from machine learning to neurobiology](https://mlsanity.com/paper/2508.08435/) (2025)
- [Why Are Linear RNNs More Parallelizable?](https://mlsanity.com/paper/2603.03612/) (2026)
- [Understanding Input Selectivity in Mamba: Impact on Approximation Power, Memorization, and Associative Recall Capacity](https://mlsanity.com/paper/2506.11891/) (2025)
- [Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilities](https://mlsanity.com/paper/2505.21785/) (2025)
- [Learning State-Tracking from Code Using Linear RNNs](https://mlsanity.com/paper/2602.14814/) (2026)
- [Generalization Error Analysis for Selective State-Space Models Through the Lens of Attention](https://mlsanity.com/paper/2502.01473/) (2025)
- [Fixed-Point RNNs: Interpolating from Diagonal to Dense](https://mlsanity.com/paper/2503.10799/) (2025)
- [Overcoming Long-Context Limitations of State-Space Models via Context-Dependent Sparse Attention](https://mlsanity.com/paper/2507.00449/) (2025)
- [On the Expressivity of Selective State-Space Layers: A Multivariate Polynomial Approach](https://mlsanity.com/paper/2502.02209/) (2025)
- [Revisiting Bi-Linear State Transitions in Recurrent Neural Networks](https://mlsanity.com/paper/2505.21749/) (2025)
- [Rethinking State Tracking in Recurrent Models Through Error Control Dynamics](https://mlsanity.com/paper/2605.07755/) (2026)
- [The Capability Convergence Hypothesis: Capability from Access Structure, Not Scale](https://mlsanity.com/paper/2607.14144/) (2026)
- [Multilingual State Space Models for Structured Question Answering in Indic Languages](https://mlsanity.com/paper/2502.01673/) (2025)
- [On the Expressiveness of State Space Models via Temporal Logics](https://mlsanity.com/paper/2601.19467/) (2026)
- [On the "Induction Bias" in Sequence Models](https://mlsanity.com/paper/2602.18333/) (2026)
- [An Algebraic View of the Expressivity of Recurrent Language Models](https://mlsanity.com/paper/2606.01765/) (2026)
- [Indexing: the Beginning and the End](https://mlsanity.com/paper/2607.22361/) (2026)
- [Three tiers of computation in transformers and in brain architectures](https://mlsanity.com/paper/2503.04848/) (2025)
- [Parity Requires Unified Input Dependence and Negative Eigenvalues in SSMs](https://mlsanity.com/paper/2508.07395/) (2025)
- [The Computational Complexity of Satisfiability in State Space Models](https://mlsanity.com/paper/2508.18162/) (2025)

## 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.