Research map / Architectures and efficiency / Attention and transformers
The Illusion of State in State-Space Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves that S4- and Mamba-style linear SSMs are simulable in L-uniform TC^0 (so cannot solve S5 word problem or NC1-hard state tracking), validates with experiments, and shows input-dependent transition SSMs (IDS4) or RNN-SSMs can express S5.
Problem
Whether state-space models (S4, Mamba) have greater expressive power for state tracking than transformers, given their recurrent-like formulation.
Approach
Shows the convolutional form of generalized linear SSMs with input-independent or diagonal (or simultaneously diagonalizable) transition matrices lies in L-uniform TC^0 under log-precision floats, hence cannot solve NC1-hard state tracking like S5; a minimal input-dependent transition extension (IDS4) escapes TC^0 and learns A5 with one layer.
Key results
- One-layer RNN and IDS4 learn the A5 word problem for arbitrarily long sequences, while transformer, S4, and Mamba require depth increasing with sequence length.
- S4 and Mamba show the same depth limitations as transformers on A5 and A4xZ5; for non-commutative groups the transformer needs at least as many layers as S4 or Mamba.
- Theoretically, S4 and S6 (Mamba) convolutional forms are computable in L-uniform TC^0, so under TC0 != NC1 they cannot solve S5 or other NC1-hard problems.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a one-layer RNN instead of a fixed-depth transformer, S4, or Mamba | State-tracking models · A5 word problem | minimum depth for >90% validation accuracy | Helped |
| Use input-dependent transitions in IDS4 instead of fixed-transition S4 | S4 · A5 word problem | minimum depth for >90% validation accuracy | Helped |
| Increase sequence length without increasing model depth | Transformer, S4, and Mamba · A5 word problem | minimum depth for >90% validation accuracy | Hurt |
| Increase sequence length without increasing model depth | Transformer, S4, and Mamba · A4 × Z5 word problem | minimum depth for >90% validation accuracy | Hurt |
| Use S4 or Mamba instead of a transformer | State-tracking models · A5 and A4 × Z5 word problems | minimum depth for >90% validation accuracy | Helped |
Surprising findings
- S4 and Mamba appear empirically better than transformers at approximate state tracking on non-commutative tasks despite sharing the same TC0 limitation.
- Transformers and SSMs struggle even on A4xZ5, which is expressible in TC0, requiring growing depth with sequence length.
Limitations
- Analysis assumes log-precision floats and L-uniform TC0; relies on the conjecture TC0 != NC1 for hardness.
- Experiments are limited to small synthetic group word problems, not large-scale language modeling.
- Whether input-dependent SSMs such as IDS4 are practically viable for large-scale language modeling is left open.
Experimental setup
Datasets: synthetic group word problem sequences (A5, A4xZ5, Z60)
Benchmarks: A5 word problem A4xZ5 word problem Z60 word problem
Metrics: full-sequence test accuracy minimum depth to reach 90% test accuracy
Baselines: transformer RNN S4 Mamba
Builds on: S4 Mamba Liquid S4 Merrill & Sabharwal transformer TC0 results
Closest papers by meaning
- The Expressive Capacity of State Space Models: A Formal Language Perspective (NeurIPS 2024 · similarity 0.92)
- (How) Do Language Models Track State? (ICML 2025 · similarity 0.91)
- Rethinking State Tracking in Recurrent Models Through Error Control Dynamics (NeurIPS 2026 · similarity 0.89)
- Chess-World-Model: A 10M-Game Benchmark for Exact State Tracking from Chess Move Sequences (NeurIPS 2026 · similarity 0.87)
- On the Expressiveness and Length Generalization of Selective State Space Models on Regular Languages (AAAI 2025 · similarity 0.87)
- Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.