The Illusion of State in State-Space Models
Open accessAbstract
State-space models (SSMs) have emerged as a potential alternative architecture for building large language models (LLMs) compared to the previously ubiquitous transformer architecture. One theoretical weakness of transformers is that they cannot express certain kinds of sequential computation and state tracking (Merrill & Sabharwal, 2023), which SSMs are explicitly designed to address via their close architectural similarity to recurrent neural networks (RNNs). But do SSMs truly have an advantage (over transformers) in expressive power for state tracking? Surprisingly, the answer is no. Our analysis reveals that the expressive power of SSMs is limited very similarly to transformers: SSMs cannot express computation outside the complexity class $\mathsf{TC}^0$. In particular, this means they cannot solve simple state-tracking problems like permutation composition. It follows that SSMs are provably unable to accurately track chess moves with certain notation, evaluate code, or track entities in a long narrative. To supplement our formal analysis, we report experiments showing that Mamba-style SSMs indeed struggle with state tracking. Thus, despite its recurrent formulation, the "state" in an SSM is an illusion: SSMs have similar expressiveness limitations to non-recurrent models like transformers, which may fundamentally limit their ability to solve real-world state-tracking problems.
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.
Integrity signals
Registry
Cites
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.
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?
Titans are capable of solving problems beyond TC0, meaning that Titans are theoretically more expressive than Transformers and most modern linear recurrent models in state tracking tasks.
“Contrary to Transformers, diagonal linear recurrent models, and DeltaNet, all of which are limited to TC0 (Merrill, Petty, and Sabharwal 2024), Titans are capable of solving problems beyond TC 0, meaning that Titans are theoretically more expressive than Transformers and most modern linear recurrent models in state tracking tasks.”
From Titans: Learning to Memorize at Test Time (2025) · cites this paper as Merrill, Petty, and Sabharwal 2024
Section 2.3 states that Transformers are limited to TC0, and Theorem 4.4 (Section 4.3) establishes that limit for diagonal generalized linear SSMs under its stated conditions. The cited paper does not establish a TC0 limit for DeltaNet, so it does not support the full list attached to this citation. The sentence's claim about Titans is not directly attributed to this source. (LLM, conf=0.86)
Experimental — accuracy not yet measuredTransformers and State Space models are fundamentally less powerful than RNNs.
“This result is in agreement with findings that Transformers and State Space models are fundamentally less powerful than RNNs (Merrill et al., 2024;Merrill & Sabharwal, 2023;Delétang et al., 2023).”
From xLSTM: Extended Long Short-Term Memory (2024) · cites this paper as Merrill et al., 2024
The Introduction reports that the linear and Mamba-style SSMs studied, like transformers, cannot express certain sequential state-tracking problems that RNNs can express. But the claim says State Space models generally are less powerful than RNNs; the paper limits its result to particular architectures and assumptions, including bounded depth, and §4.4 makes its formal separation conditional on TC0 ≠ NC1. (LLM, conf=0.87)
Experimental — accuracy not yet measuredThe result that models without memory mixing cannot solve regular grammars is in agreement with findings that Transformers and State Space models are fundamentally less powerful than RNNs.
“This result is in agreement with findings that Transformers and State Space models are fundamentally less powerful than RNNs (Merrill et al., 2024;Merrill & Sabharwal, 2023;Delétang et al., 2023).”
From xLSTM: Extended Long Short-Term Memory (2024) · cites this paper as Merrill et al., 2024
The Introduction says that linear and Mamba-style SSMs, like transformers, cannot express certain sequential state-tracking problems that RNNs can. But the claim is broader than the paper’s result: the Discussion (§4.4) limits the separation to specified SSM architectures and assumptions, and the Conclusion (§7) describes an input-dependent SSM that can express the S5 word problem. (LLM, conf=0.87)
Experimental — accuracy not yet measuredMemory mixing enables solving state tracking problems, and therefore LSTMs are more expressive than State Space Models and Transformers.
“Memory mixing enables to solve state tracking problems, and therefore LSTMs are more expressive than State Space Models (SSMs) and Transformers (Merrill et al., 2024;Delétang et al., 2023).”
From xLSTM: Extended Long Short-Term Memory (2024) · cites this paper as Merrill et al., 2024
The Introduction and Section 4.4 say that simple RNNs can express permutation-composition state tracking that fixed-depth S4/S6-style SSMs and transformers cannot. The paper does not identify LSTMs or memory mixing as the reason, and its conclusion notes that an extended SSM can also express this task. Thus the comparison is supported for the models studied, not as an unqualified claim about all SSMs. (LLM, conf=0.86)
Experimental — accuracy not yet measuredThe Transformer design has limited computational depth, as stated in recent studies on state-tracking and similar computational capabilities of models.
“This design, however, has limited computational depth as also stated in recent studies on state-tracking and similar computational capabilities of models (Merrill et al. 2024; Sanford et al. 2024; Grazzi et al. 2025).”
From Nested Learning: The Illusion of Deep Learning Architectures (2025) · cites this paper as Merrill et al. 2024
Transformers both in theory and practice significantly underperform models with non-linear recurrence on state tracking and non-parallelizable tasks.
“several studies have shown that Transformers both in theory and practice significantly underperforms models with non-linear recurrence (Merrill et al. 2024; Grazzi et al. 2025).”
From Nested Learning: The Illusion of Deep Learning Architectures (2025) · cites this paper as Merrill et al. 2024
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
No references could be resolved yet.
Research works printed but not linked: 25
- Angluin, D., Chiang, D., and Yang, A. Masked hard- attention transformers and Boolean RASP recognize ex- actly the star-free languages, 2023. arXiv:2310.13897. · arXiv
- Barrington, D. A. Bounded-width polynomial- size branching programs recognize exactly those languages in nc1. Journal of Computer and System Sciences, 38(1):150-164, 1989. URL https://www.sciencedirect.com/ science/article/pii/0022000089900378.
- Chiang, D., Cholak, P., and Pillay, A. Tighter bounds on the expressivity of transformer encoders. In ICML, 2023.
- Feng, G., Zhang, B., Gu, Y., Ye, H., He, D., and Wang, L. Towards revealing the mystery behind chain of thought: A theoretical perspective. In NeurIPS, 2023.
- Fu, D. Y., Dao, T., Saab, K. K., Thomas, A. W., Rudra, A., and Re, C. Hungry hungry hippos: Towards language modeling with state space models. In ICLR, 2023.
- Gu, A. and Dao, T. Mamba: Linear-time sequence modeling with selective state spaces, 2023. arXiv:2312.00752. · arXiv
- Gu, A., Johnson, I., Goel, K., Saab, K. K., Dao, T., Rudra, A., and Re, C. Combining recurrent, convolutional, and continuous-time models with linear state space layers. In NeurIPS, 2021.
- Gu, A., Goel, K., and Re, C. Efficiently modeling long sequences with structured state spaces. In ICLR, 2022a.
- Hao, S., Angluin, D., and Frank, R. Formal language recog- nition by hard attention transformers: Perspectives from circuit complexity. TACL, 10:800-810, 2022.
- Hasani, R., Lechner, M., Wang, T.-H., Chahine, M., Amini, A., and Rus, D. Liquid structural state-space models. In ICLR, 2023.
- Heim, I. File change semantics and the familiarity theory of definiteness. Semantics Critical Concepts in Linguistics, pp. 108-135, 1983.
- Hesse, W. Division is in uniform T C 0 . In International Colloquium on Automata, Languages, and Programming, pp. 104-114, 2001.
- Hopcroft, J. E., Motwani, R., and Ullman, J. D. Introduction to automata theory, languages, and computation. ACM SIGACT News, 32(1):60-65, 2001.
- Immerman, N. and Landau, S. The complexity of iterated multiplication. In [1989] Proceedings. Structure in Com- plexity Theory Fourth Annual Conference, pp. 104-111, 1989. doi: 10.1109/SCT.1989.41816. · DOI
- Kim, N. and Schuster, S. Entity tracking in language models. In Rogers, A., Boyd-Graber, J., and Okazaki, N. (eds.), ACL, July 2023.
- Krohn, K. and Rhodes, J. Algebraic theory of machines. i. prime decomposition theorem for finite semigroups and machines. Transactions of the American Mathematical Society, 116:450-464, 1965.
- Liu, B., Ash, J. T., Goel, S., Krishnamurthy, A., and Zhang, C. Transformers learn shortcuts to automata. In ICLR, 2023.
- Mereghetti, C. and Palano, B. Threshold circuits for iterated matrix product and powering. RAIRO-Theor. Inf. Appl., 34(1):39-46, 2000. doi: 10.1051/ita:2000105. URL https://doi.org/10.1051/ita:2000105. · DOI
- Merrill, W. Sequential neural networks as automata. In Eis- ner, J., Gallé, M., Heinz, J., Quattoni, A., and Rabusseau, G. (eds.), Proceedings of the Workshop on Deep Learn- ing and Formal Languages: Building Bridges, Florence, August 2019. ACL.
- Merrill, W. and Sabharwal, A. The parallelism tradeoff: Limitations of log-precision transformers. TACL, 11, 2023a.
- Merrill, W. and Sabharwal, A. A logic for expressing log- precision transformers. In NeurIPS, 2023b.
- Merrill, W. and Sabharwal, A. The expressive power of transformers with chain of thought. In ICLR, 2024.
- Minsky, M. Neural nets and the brain-model problem. Un- published doctoral dissertation, Princeton University, NJ, 1954.
- Mohri, M. Weighted Automata Algorithms, pp. 213- 254. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. ISBN 978-3-642-01492-5. doi: 10.1007/ 978-3-642-01492-5 6. URL https://doi.org/10. 1007/978-3-642-01492-5_6. · DOI
- Reif, J. H. and Tate, S. R. On threshold circuits and polynomial computation. SIAM Journal on Comput- ing, 21(5):896-908, 1992. doi: 10.1137/0221053. URL https://doi.org/10.1137/0221053. · DOI
Cited by
Sorted by citations
xLSTM: Extended Long Short-Term Memory
Beck, M., Pöppel, K., Spanring, M., Auer, A., Prudnikova, O., Kopp, M., Klambauer, G., Brandstetter, J., & Hochreiter, S. (2024) · Advances in Neural Information Processing Systems 37 · doi:10.52202/079017-3417 · Cited by 286 · see citing works
xLSTM: Extended Long Short-Term Memory
Beck, M., Pöppel, K., Spanring, M., Auer, A., Prudnikova, O., Kopp, M., Klambauer, G., Brandstetter, J., & Hochreiter, S. (2024) · arXiv · doi:10.48550/arxiv.2405.04517 · Cited by 299 · see citing works
Evaluating the World Model Implicit in a Generative Model
Vafa, K., Chen, J., Rambachan, A., Kleinberg, J., & Mullainathan, S. (2024) · Advances in Neural Information Processing Systems 37 · doi:10.52202/079017-0846 · Cited by 22 · see citing works
Titans: Learning to Memorize at Test Time
Behrouz, A., Zhong, P., & Mirrokni, V. (2025) · arXiv · doi:10.48550/arxiv.2501.00663 · Cited by 24 · see citing works
Evaluating the World Model Implicit in a Generative Model
Vafa, K., Chen, J. Y., Rambachan, A., Kleinberg, J., & Mullainathan, S. (2024) · arXiv · Cited by 22 · see citing works
Nested Learning: The Illusion of Deep Learning Architectures
Behrouz, A., Razaviyayn, M., Zhong, P., & Mirrokni, V. (2025) · arXiv · doi:10.48550/arxiv.2512.24695 · Cited by 1 · see citing works
“…not change with more layers [21, 22], leaving their ability to implement complex algorithms untouched compared to traditional shallow approaches [23]; (ii) The capacity of some class of parameters might show marginal improvement with increasing the depth/width of the model [24]; (iii) The…”
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
Behrouz, A., Razaviyayn, M., Zhong, P., & Mirrokni, V. (2025) · arXiv · doi:10.48550/arxiv.2504.13173
MesaNet: 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
“Recent work has investigated the (missing) state-tracking ability of transformers, modern state space models and linearized transformer RNN models, see e.g. [ 70].”
ATLAS: Learning to Optimally Memorize the Context at Test Time
Behrouz, A., Li, Z., Kacham, P., Daliri, M., Deng, Y., Zhong, P., Razaviyayn, M., & Mirrokni, V. (2025) · arXiv · doi:10.48550/arxiv.2505.23735
Language models need inductive biases to count inductively
Chang, Y., & Bisk, Y. (2024) · arXiv · doi:10.48550/arxiv.2405.20131
“Extending the expressivity analysis for Transformers to these new RNN architectures (Merrill, 2019; Merrill et al., 2024)”
MethodImplicit 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
“Implicit SSMs Lift the Illusion of State The Illusion of State (Merrill et al., 2024) reveals that SSMs cannot simulate arbitrary finite state machines.”
Influential
- Authors
- Merrill, W., Petty, J., & Sabharwal, A.
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2024
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2404.08819
- OpenAlex
- W4394867439
- Cited by
- 5
- References
- 0
- Citations by year
- 2026: 1 · 2025: 4
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (1922658)
- 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, state tracking, computational complexity, TC0, Mamba, transformer models, recurrent neural networks, large language models, code evaluation, entity tracking
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
