Research map / Architectures and efficiency / Attention and transformers
The Expressive Capacity of State Space Models: A Formal Language Perspective
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.
Gives a formal-language theory of expressivity for linear state space models (SSMs) versus transformers and RNNs, showing SSMs handle star-free state tracking, bounded Dyck, and counters, but a nonnegative-gate design choice prevents PARITY, and checks this empirically on Mamba.
Problem
Understanding the in-principle expressive capacity of recent linear state space language models (e.g., Mamba) relative to transformers and traditional RNNs, using formal languages and automata.
Approach
Characterizes SSM expressivity via formal languages: nonnegative (exponential/sigmoid) gates provably block PARITY and modular counting, so non-time-invariant nonnegative SSMs recognize/predictively model exactly the star-free regular languages at finite precision; SSMs also solve Flip-Flop length-generally and model bounded Dyck with optimal width without a stack.
Key results
- Mamba learns FlipFlop to near-zero error in both in- and out-of-distribution settings after about 1400 steps, versus about 500 steps for an LSTM; transformers kept making mistakes after 10K steps.
- On the 27-language suite, Mamba learns all star-free languages with strong length generalization but performs poorly on non-star-free languages.
- A two-layer Mamba models Dyck_{8,10} essentially perfectly across model sizes, including on test strings of length 700-1400.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a one-layer Mamba for Flip Flop state tracking | Mamba · Flip Flop, in-distribution and out-of-distribution validation sets | test error: 0 error after ~ 1400 steps | Helped |
| Use Mamba for star-free formal languages | Mamba · Test suite of 27 formal languages, star-free subset | accuracy | Helped |
| Use Mamba for non-star-free formal languages | Mamba · Test suite of 27 formal languages, non-star-free subset | accuracy | Hurt |
| Use Mamba to model counter languages | Mamba · Test suite of 27 formal languages, counter languages | accuracy | Mixed |
| Increase the number of Mamba layers from 1 to 2 (ablation) | Mamba · Bounded-depth Dyck(K, h), test strings of length 700–1400 | accuracy | Helped |
Surprising findings
- Nonnegative-gate SSMs cannot recognize PARITY at arbitrary lengths, a limit that applies to Mamba itself.
- Mamba learns counter languages at in-distribution lengths, but its length generalization lags behind transformers.
Limitations
- Results concern in-principle expressiveness and say nothing about learning or generalization dynamics.
- Empirical validation is limited to Mamba and implementational differences may matter.
- Positive constructions for counters use unbounded state values, which hurts length generalization.
Experimental setup
Datasets: Delétang et al. 2023 formal language test suite (27 languages) FlipFlop dataset from Liu et al. 2023 Dyck_{K,h} synthetic data
Benchmarks: 27 formal languages (Delétang et al. 2023) FlipFlop Dyck_{K,h}
Metrics: accuracy (all positions correct) length generalization accuracy
Baselines: Transformer LSTM Transformer results from Delétang et al. 2023
Builds on: Mamba S4 Krohn-Rhodes theorem Deletang et al. formal language benchmark Merrill et al. saturated transformer analysis
Closest papers by meaning
- The Illusion of State in State-Space Models (ICML 2024 · similarity 0.92)
- On the Expressiveness and Length Generalization of Selective State Space Models on Regular Languages (AAAI 2025 · similarity 0.89)
- (How) Do Language Models Track State? (ICML 2025 · similarity 0.89)
- Implicit Language Models are RNNs: Balancing Parallelization and Expressivity (ICML 2025 · similarity 0.89)
- Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality (ICML 2024 · similarity 0.88)
- Repeat After Me: Transformers are Better than State Space Models at Copying (ICML 2024 · similarity 0.88)
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.