The Illusion of State in State-Space Models
2024/04/12 by William Merrill, Jackson Petty, Merrill, William +3 · 3 voices · 83 citations
Computer Science · Mathematics · Psychology · #Adversarial Robustness in Machine Learning #Algorithm #Cognitive psychology #Computer science #Illusion #Machine Learning in Healthcare #Mathematics #Political science #Psychology #Space (punctuation) #State (computer science) #State space #Statistics #Topic Modeling
paper · pdf · doi:10.48550/arxiv.2404.08819
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2024/04/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Abstract
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 TC0. 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.
Cited by
- Pretraining Recurrent Networks without Recurrence
- Indexing: the Beginning and the End
- When Does Recurrence Become an Algorithm? Convergence Selection in Weight-Tied Looped Transformers
- The Capability Convergence Hypothesis: Capability from Access Structure, Not Scale
- T2MLR: Transformer with Temporal Middle-Layer Recurrence
- Mamba-3: Improved Sequence Modeling using State Space Principles
- M2RNN: Non-Linear RNNs with Matrix-Valued States for Scalable Language Modeling
- Memory Caching: RNNs with Growing Memory
- Kimi Linear: An Expressive, Efficient Attention Architecture
- Expected Attention: KV Cache Compression by Estimating Attention from Future Queries Distribution
- Transformers are Inherently Succinct
- Fast weight programming and linear transformers: from machine learning to neurobiology
- Log-Linear Attention
- Blending Complementary Memory Systems in Hybrid Quadratic-Linear Transformers
- ATLAS: Learning to Optimally Memorize the Context at Test Time
- Why Are Linear RNNs More Parallelizable?
- Raven: High-Recall Sequence Modeling with Sparse Memory Routing
- Exact Learning of Arithmetic with Differentiable Agents
- Selective Rotary Position Embedding
- Evolution Strategies at the Hyperscale
- TNT: Improving Chunkwise Training for Test-Time Memorization
- Next-Latent Prediction Transformers Learn Compact World Models
- Hyper Hawkes Processes: Interpretable Models of Marked Temporal Point Processes
- FlashEVA: Accelerating LLM inference via Efficient Attention
- Comparing Transformers and Hybrid Models at the Token Level
- Symbol-Equivariant Recurrent Reasoning Models
- The Scaling Properties of Implicit Deductive Reasoning in Transformers
- ParaRNN: Unlocking Parallel Training of Nonlinear RNNs for Large Language Models
- On the Reasoning Abilities of Masked Diffusion Language Models
- Benefits and Limitations of Communication in Multi-Agent Reasoning
- Sparse Query Attention (SQA): A Computationally Efficient Attention Mechanism with Query Heads Reduction
- Design Principles for Sequence Models via Coefficient Dynamics
- Recurrence-Complete Frame-based Action Models
- Structured Sparse Transition Matrices to Enable State Tracking in State-Space Models
- A Unifying Framework for Parallelizing Sequential Models with Linear Dynamical Systems
- Improving the Performance and Learning Stability of Parallelizable RNNs Designed for Ultra-Low Power Applications
- The Topological Trouble With Transformers
- Predictability Enables Parallelization of Nonlinear State Space Models
- Fast attention mechanisms: a tale of parallelism
- Beyond Memorization: Extending Reasoning Depth with Recurrence, Memory and Test-Time Compute Scaling
- Time-Scaling State-Space Models for Dense Video Captioning
- The Computational Complexity of Satisfiability in State Space Models
- Too Easily Fooled? Prompt Injection Breaks LLMs on Frustratingly Simple Multiple-Choice Questions
- Parity Requires Unified Input Dependence and Negative Eigenvalues in SSMs
- Towards High-Order Mean Flow Generative Models: Feasibility, Expressivity, and Provably Efficient Criteria
- Automated Code Development for PDE Solvers Using Large Language Models
- Minimal Convolutional RNNs Accelerate Spatiotemporal Learning
- Systolic Array-based Accelerator for Structured State-Space Models
- Learning State-Tracking from Code Using Linear RNNs
- Agent Identity Evals: Measuring Agentic Identity
- The Serial Scaling Hypothesis
- What Has a Foundation Model Found? Using Inductive Bias to Probe for World Models
- Self-supervised learning predicts plant growth trajectories from multi-modal industrial greenhouse data
- Bridging Expressivity and Scalability with Adaptive Unitary SSMs
- Overcoming Long-Context Limitations of State-Space Models via Context-Dependent Sparse Attention
- A "Good" Regulator May Provide a World Model for Intelligent Systems
- Why Neural Network Can Discover Symbolic Structures with Gradient-based Training: An Algebraic and Geometric Foundation for Neurosymbolic Reasoning
- TPTT: Transforming Pretrained Transformers into Titans
- Understanding Input Selectivity in Mamba: Impact on Approximation Power, Memorization, and Associative Recall Capacity
- pLSTM: parallelizable Linear Source Transition Mark networks
- Sequential-Parallel Duality in Prefix Scannable Models
- Diagonal Batching Unlocks Parallelism in Recurrent Memory Transformers for Long Contexts
- MesaNet: Sequence Modeling by Locally Optimal Test-Time Training
- Weight-Space Linear Recurrent Neural Networks
- TiRex: Zero-Shot Forecasting Across Long and Short Horizons with Enhanced In-Context Learning
- Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilities
- Revisiting Bi-Linear State Transitions in Recurrent Neural Networks
- Understanding Transformer from the Perspective of Associative Memory
- Structured Linear CDEs: Maximally Expressive and Parallel-in-Time Sequence Models
- PaTH Attention: Position Encoding via Accumulating Householder Transformations
- Learning to Dissipate Energy in Oscillatory State-Space Models
- Dynamic Domain Information Modulation Algorithm for Multi-domain Sentiment Analysis
- CodeSSM: Towards State Space Models for Code Understanding
- When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?
- Parallelizable memory recurrent units
- On Subquadratic Architectures: From Applications to Principles
- An Algebraic View of the Expressivity of Recurrent Language Models
- Do Language Models Track Entities Across State Changes?
- Can Vision-Language Models Solve the Shell Game?
- Nested Learning: The Illusion of Deep Learning Architectures
- Perfect diffusion is TC0 -- Bad diffusion is Turing-complete
- It's All Connected: A Journey Through Test-Time Memorization, Attentional Bias, Retention, and Online Optimization
- Lattice: Learning to Efficiently Compress the Memory
Discussions
Related