The Expressive Capacity of State Space Models: A Formal Language Perspective
Open accessAbstract
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.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
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?
Using forget strength γ_t ∈ (-1,1) instead of γ_t ∈ (0,1) allows layers such as Mamba, GLA or gated DeltaNet to solve certain state tracking tasks.
“One simple architecture change proposed in Sarrof et al. (2024); Grazzi et al. (2025) which allows layers such as Mamba, GLA or gated DeltaNet to solve certain state tracking tasks is to use forget strength γ t ∈ ( -1 , 1) instead of γ t ∈ (0 , 1) .”
From MesaNet: Sequence Modeling by Locally Optimal Test-Time Training (2025) · cites this paper as Sarrof et al. (2024)
Cited by
Sorted by citations
Mamba-3: Improved Sequence Modeling using State Space Principles
Lahoti, A., Li, K. Y., Chen, B., Wang, C., Bick, A., Kolter, J. Z., Dao, T., & Gu, A. (2026) · arXiv · doi:10.48550/arxiv.2603.15569 · Cited by 1 · see citing works
“…modeling accuracy by +2.2 over Transformers, +1.9 points over Mamba-2, and +1.8 over GDN, while Mamba-3 (SISO) improves over the next best model, GDN, by +0.6 points. the perplexity of Mamba-2 with state size 128, effectively achieving the same language modeling performance with half the latency .”
InfluentialMesaNet: Sequence Modeling by Locally Optimal Test-Time Training
von Oswald, J., Scherrer, N., Kobayashi, S., Versari, L., Yang, S., Mittal, S., Schlegel, M., Maile, K., Schimpf, Y., Sieberling, O., et al. (2025) · arXiv
“One simple architecture change proposed in [87, 38] which allows layers such as Mamba, GLA or gated DeltaNet to solve certain state tracking tasks is to use forget strength γ t ∈ ( − 1 , 1) instead of γ t ∈ (0 , 1) .”
Implicit Language Models are RNNs: Balancing Parallelization and Expressivity
Schöne, M., Rahmani, B., Kremer, H., Falck, F., Ballani, H., & Gladrow, J. (2025) · arXiv · doi:10.48550/arxiv.2502.07827
“Many empirical studies confirm these theoretical limitations of transformers and SSMs to learn regular languages (Deletang et al., 2023; Sarrof et al., 2024; Strobl et al., 2024).”
Influential
- Authors
- Sarrof, Y., Veitsman, Y., & Hahn, M.
- ORCID
- Hahn, Michael
- Venue
- Advances in Neural Information Processing Systems 37
- Published
- 2024
- Pages
- 41202-41241
- ISSN
- 1049-5258 (ISSN-L)
- OpenAlex
- W4415798164
- Cited by
- 4
- References
- 0
- Citations by year
- 2026: 3 · 2025: 1
- FWCI
- 1.15
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- cc-by
- Locations
- neural information processing systems (publishedVersion)
- arXiv (Cornell University) (submittedVersion, cc-by)
- arXiv (Cornell University) (cc-by)
- Funders
- Deutsche Forschungsgemeinschaft (SFB 1102, 232722074)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
- Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Keywords
- state-space model, expressiveness, formal languages, automata, formal language theory
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
