Research map / Architectures and efficiency / Attention and transformers
On the Expressiveness and Length Generalization of Selective State Space Models on Regular Languages
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.
Introduces SD-SSM, a selective SSM with a softmax-weighted dictionary of dense transition matrices and a linear readout that achieves near-perfect length generalization on regular-language (FSA emulation) tasks with one layer, and analyzes why diagonal selective SSMs fail on non-commutative automata.
Problem
Selective SSMs' formal expressiveness and length generalization on finite-state automaton emulation (regular language state tracking) are underexplored; diagonal selective SSMs appear limited.
Approach
A selective SSM whose per-step transition matrix is a softmax-weighted convex combination of k learned dense matrices, followed by column-wise lp operator normalization and a linear readout (layer norm + linear), enabling single-layer perfect length generalization; plus a proposition that single-layer diagonal selective SSMs without the B term are restricted to commutative automata.
Key results
- SD-SSM with one layer reaches >=99.9% maximum length-generalization accuracy on Parity, Even Pairs, Cycle, Arithmetic, D4 and A5 (100% on A5), while Mamba reaches only 20.1% on Arithmetic.
- On Modular Arithmetic, a nonlinear MLP readout drops SD-SSM accuracy to 71.9% versus 99.9% with the linear readout.
- On D30 the C-diagonal model with linear readout and B=0 reaches only 11.3% max accuracy, while SD-SSM achieves 100%; parallel scan reduces 512-length fwd+bwd runtime from 77.27s to 26.68s.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace the linear readout with a two-layer ReLU MLP (ablation) | SD-SSM · Arithmetic | maximum length-generalization accuracy (%): 99.9\% -> 71.9\% | Hurt |
| remove the B matrix and use a linear readout (ablation) | C-complex diagonal SSM · C2 × C30 | maximum length-generalization accuracy (%): 65.8 -> 100 | Helped |
| remove the B matrix and use a nonlinear readout (ablation) | C-complex diagonal SSM · C2 × C30 | maximum length-generalization accuracy (%): 81.7 -> 87.6 | Helped |
| add the B matrix while keeping a nonlinear readout (ablation) | C-complex diagonal SSM · C2 × C30 | maximum length-generalization accuracy (%): 87.6 -> 81.7 | Hurt |
| add the B matrix and use a nonlinear readout (ablation) | C-complex diagonal SSM · D30 | maximum length-generalization accuracy (%): 8.35 -> 61.0 | Helped |
| add the B matrix and use a linear readout (ablation) | C-complex diagonal SSM · D30 | maximum length-generalization accuracy (%): 8.35 -> 11.3 | Hurt |
| replace linear readout with nonlinear readout while B=0 (ablation) | C-complex diagonal SSM · D30 | maximum length-generalization accuracy (%): 8.35 -> 8.35 | No clear effect |
| replace linear readout with nonlinear readout while B is present (ablation) | C-complex diagonal SSM · D30 | maximum length-generalization accuracy (%): 11.3 -> 61.0 | Helped |
| increase depth from 1 to 2 layers (ablation) | C-complex diagonal SSM with B≠0 and nonlinear readout · C2 × C30 | maximum length-generalization accuracy (%): 81.7 -> 24.6 | Hurt |
| increase depth from 1 to 2 layers (ablation) | C-complex diagonal SSM with B≠0 and nonlinear readout · D30 | maximum length-generalization accuracy (%): 61.0 -> 29.2 | Hurt |
| use parallel scan instead of recurrent computation | SD-SSM · sequence length 512 | runtime (seconds): 77.27\,s -> 26.68\,s | Helped |
| use parallel scan instead of recurrent computation | SD-SSM · sequence length 64 | runtime (seconds): 1.82\,s -> 1.91\,s | Hurt |
Surprising findings
- A nonlinear readout, common in prior work, hurts length generalization for SD-SSM on Arithmetic.
- Mamba, the most prominent selective SSM, fails in-domain on Arithmetic (91.6% in-domain best) and reaches only 20.1% max length-generalization accuracy.
Limitations
- Theoretical result on diagonal commutativity relies on an assumed FSA-to-SSM mapping with B irrelevant; non-commutative automata may be emulated by other mappings.
- SD-SSM shows higher variability across seeds on C2xC4 and in the length-efficiency analysis.
- Evaluation is limited to synthetic FSA tasks, not natural data.
Experimental setup
Datasets: synthetic finite-state automaton tasks: Parity, Even Pairs, Cycle Navigation, Modular Arithmetic, C2xC4, D4, A5, C2xC30,
Benchmarks: Parity Even Pairs Cycle Navigation Modular Arithmetic C2xC4 D4 A5 C2xC30 D30
Metrics: maximum/average length generalization accuracy area under accuracy vs length curve runtime (s)
Baselines: RNN LSTM Transformer S4D H3 Mamba RegularLRNN C diagonal selective SSM
Builds on: Mamba S4D RegularLRNN Deletang et al. state tracking benchmark
Closest papers by meaning
- The Expressive Capacity of State Space Models: A Formal Language Perspective (NeurIPS 2024 · similarity 0.89)
- Theoretical Foundations of Deep Selective State-Space Models (NeurIPS 2024 · similarity 0.89)
- Repeat After Me: Transformers are Better than State Space Models at Copying (ICML 2024 · similarity 0.88)
- Bridging Expressivity and Scalability with Adaptive Unitary SSMs (NeurIPS 2025 · similarity 0.88)
- Generalization Error Analysis for Selective State-Space Models Through the Lens of Attention (NeurIPS 2025 · similarity 0.88)
- The Illusion of State in State-Space Models (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.