mlsanityData to 7 Oct 2026

The Illusion of State in State-Space Models

arXiv 2404.08819 ↗First posted 12 Apr 2024cs.LG cs.CC cs.CLcited by 181

Not on the map. Why?

Cited by 24 in State-space sequence models (S4, Mamba), but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

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

Key facts. Cited by 181 papers in the map (data through 7 Oct 2026). Builds on 16 of its 40 references that are in the map. First posted on arXiv 12 Apr 2024.

Builds on

16 of 40 references.

References · 16

  1. 2023Mamba: Linear-Time Sequence Modeling with Selective State Spacescited by 4,616
  2. 2014Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translationcited by 4,016
  3. 2021Efficiently Modeling Long Sequences with Structured State Spacescited by 2,424
  4. 2021Combining Recurrent, Convolutional, and Continuous-time Models with Linear State-Space Layerscited by 607
  5. 2022Hungry Hungry Hippos: Towards Language Modeling with State Space Modelscited by 495
  6. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 293
  7. 2022Transformers Learn Shortcuts to Automatacited by 260
  8. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  9. 2022Liquid Structural State-Space Modelscited by 134
  10. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  11. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 92
  12. 2021Chess as a Testbed for Language Model State Trackingcited by 69
4 more
  1. 2022A Logic for Expressing Log-Precision Transformerscited by 67
  2. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 65
  3. 2019Sequential Neural Networks as Automatacited by 54
  4. 2023Entity Tracking in Language Modelscited by 44

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 28; 2025: 76; 2026: 77.

181 papers.

Sort:

By area:

  1. 2024Gated Delta Networks: Improving Mamba2 with Delta Rulecited by 483
  2. 2024Parallelizing Linear Transformers with the Delta Rule over Sequence Lengthcited by 373
  3. 2025Kimi Linear: An Expressive, Efficient Attention Architecturecited by 169
  4. 2024Samba: Simple Hybrid State Space Models for Efficient Unlimited Context Language Modelingcited by 167
  5. 2024Evaluating the World Model Implicit in a Generative Modelcited by 107
  6. 2025TiRex: Zero-Shot Forecasting Across Long and Short Horizons with Enhanced In-Context Learningcited by 107
  7. 2024Unlocking State-Tracking in Linear RNNs Through Negative Eigenvaluescited by 97
  8. 2026Mamba-3: Improved Sequence Modeling using State Space Principlescited by 76
  9. 2025Expected Attention: KV Cache Compression by Estimating Attention from Future Queries Distributioncited by 70
  10. 2025DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Productscited by 69
  11. 2025Nested Learning: The Illusion of Deep Learning Architecturescited by 69
  12. 2025It's All Connected: A Journey Through Test-Time Memorization, Attentional Bias, Retention, and Online Optimizationcited by 60
38 more
  1. 2025ATLAS: Learning to Optimally Memorize the Context at Test Timecited by 57
  2. 2025A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformerscited by 49
  3. 2025What Has a Foundation Model Found? Using Inductive Bias to Probe for World Modelscited by 46
  4. 2024The Expressive Capacity of State Space Models: A Formal Language Perspectivecited by 45
  5. 2024A Survey of Mambacited by 39
  6. 2025Log-Linear Attentioncited by 39
  7. 2024Towards Scalable and Stable Parallelization of Nonlinear RNNscited by 38
  8. 2025MesaNet: Sequence Modeling by Locally Optimal Test-Time Trainingcited by 37
  9. 2025PaTH Attention: Position Encoding via Accumulating Householder Transformationscited by 32
  10. 2025(How) Do Language Models Track State?cited by 31
  11. 2025Understanding Transformer from the Perspective of Associative Memorycited by 31
  12. 2025Next-Latent Prediction Transformers Learn Compact World Modelscited by 29
  13. 2024Understanding the differences in Foundation Models: Attention, State Space Models, and Recurrent Neural Networkscited by 26
  14. 2024Language Models Need Inductive Biases to Count Inductivelycited by 25
  15. 2024Recurrent neural networks: vanishing and exploding gradients are not the end of the storycited by 25
  16. 2025Evolution Strategies at the Hyperscalecited by 22
  17. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  18. 2025Implicit Language Models are RNNs: Balancing Parallelization and Expressivitycited by 21
  19. 2026Fixed-Point Reasoners: Stable and Adaptive Deep Looped Transformerscited by 21
  20. 2024Learning Long Range Dependencies on Graphs via Random Walkscited by 18
  21. 2025Lattice: Learning to Efficiently Compress the Memorycited by 18
  22. 2024Understanding and Mitigating Bottlenecks of State Space Models through the Lens of Recency and Over-smoothingcited by 17
  23. 2025Finite State Automata Inside Transformers with Chain-of-Thought: A Mechanistic Study on State Trackingcited by 17
  24. 2025Structured Linear CDEs: Maximally Expressive and Parallel-in-Time Sequence Modelscited by 16
  25. 2024Simulating Hard Attention Using Soft Attentioncited by 15
  26. 2025Structured Sparse Transition Matrices to Enable State Tracking in State-Space Modelscited by 15
  27. 2024Autoregressive Large Language Models are Computationally Universalcited by 14
  28. 2024A Large Recurrent Action Model: xLSTM enables Fast Inference for Robotics Taskscited by 14
  29. 2024Scaling Stick-Breaking Attention: An Efficient Implementation and In-depth Studycited by 13
  30. 2024Bio-xLSTM: Generative modeling, representation and in-context learning of biological and chemical sequencescited by 13
  31. 2025ParaRNN: Unlocking Parallel Training of Nonlinear RNNs for Large Language Modelscited by 13
  32. 2025Blending Complementary Memory Systems in Hybrid Quadratic-Linear Transformerscited by 12
  33. 2025Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalizationcited by 12
  34. 2026Memory Caching: RNNs with Growing Memorycited by 12
  35. 2025The Serial Scaling Hypothesiscited by 11
  36. 2025Decoder-Hybrid-Decoder Architecture for Efficient Reasoning with Long Generationcited by 10
  37. 2024How Well Can a Long Sequence Model Model Long Sequences? Comparing Architechtural Inductive Biases on Long-Context Abilitiescited by 9
  38. 2024Deep Continuous-Time State-Space Models for Marked Event Sequencescited by 9

50 most cited of 181 All 181 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2025Tracking World States with Language Models: State-Based Evaluation Using Chess
  2. 2024On the Expressiveness and Length Generalization of Selective State-Space Models on Regular Languages
  3. 2026Interpreting and Steering State-Space Models via Activation Subspace Bottlenecks
  4. 2025Characterizing Mamba's Selective Memory using Auto-Encoders
  5. 2024Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality
  6. 2024States Hidden in Hidden States: Implicit Discrete State Representations Emerge in LLMs' Hidden States
  7. 2024An Empirical Study of Mamba-based Language Models
  8. 2024Theoretical Foundations of Deep Selective State-Space Models