Research map / Architectures and efficiency / Attention and transformers
Generalization Error Analysis for Selective State-Space Models Through the Lens of Attention
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.
Derives a covering-number generalization bound for selective SSMs (Mamba-style) by reducing them to a linear-attention structure, shows the bound is length-independent when the spectral abscissa of the continuous-time state matrix is negative, and validates on majority, IMDb and ListOps.
Problem
Generalization behavior of nonlinear, input-dependent selective SSMs (the core of Mamba) is theoretically unexplored; prior SSM bounds rely on LTI stability assumptions that do not apply.
Approach
Unroll the selective SSM into an attention-like (linear attention with causal mask) form and apply Transformer-style covering-number techniques, combined with a Gelfand-formula-based control of state-matrix powers, to obtain a bound whose sequence-length dependence is governed by the spectral abscissa of A_c.
Key results
- Selective SSMs with negative spectral abscissa (s_A < 0) yield length-independent generalization bounds; with s_A > 0 the bound grows exponentially in T.
- Models initialized with s_A = 0.1 fail to train for longer sequences (e.g., T=350 IMDb), while those initialized at s_A = 0 train smoothly and show a generalization gap that stays roughly stable across sequence lengths.
- A lower bound on Rademacher complexity shows the T-dependence cannot be removed when s_A >= 0, growing at least exponentially for s_A > 0.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Initialize the state matrix in the unstable regime with s_A = 0.1 | Selective SSM · Longer-sequence classification tasks | training stability | Hurt |
| Initialize the state matrix at s_A = 0 | Selective SSM · Varying sequence lengths | generalization gap | No clear effect |
| Initialize in the stable regime with s_A < 0 rather than the unstable regime with s_A > 0 | Selective SSM · IMDb and ListOps | training stability | Helped |
Surprising findings
- Training successfully pushes the spectral abscissa of unstable initializations toward zero from above, implying an implicit bias toward the stability boundary.
- Initial loss grows exponentially with sequence length when s_A > 0, causing training failure for long sequences.
Limitations
- Theory applies only to the Mamba-style discretization of a continuous-time SSM, not other selective SSM variants.
- Assumes train and test data come from the same distribution; out-of-distribution and length generalization are not addressed.
- Lower bounds are looser than the upper bounds by a factor of O(T).
Experimental setup
Datasets: Majority (synthetic) IMDb ListOps
Benchmarks: Majority IMDb ListOps
Metrics: test loss generalization gap accuracy spectral abscissa trajectory
Baselines: linear attention bound softmax attention bound vanilla RNN bound LTI SSM bounds
Builds on: Transformer covering-number bounds (Trauger & Tewari style) Mamba selective SSM Dudley integral Rademacher bound Mamba official implementation
Closest papers by meaning
- From Generalization Analysis to Optimization Designs for State Space Models (ICML 2024 · similarity 0.89)
- Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality (ICML 2024 · similarity 0.89)
- Mamba Modulation: On the Length Generalization of Mamba Models (NeurIPS 2025 · similarity 0.88)
- Theoretical Foundations of Deep Selective State-Space Models (NeurIPS 2024 · similarity 0.88)
- On the Expressiveness and Length Generalization of Selective State Space Models on Regular Languages (AAAI 2025 · similarity 0.88)
- Block-Biased Mamba for Long-Range Sequence Processing (NeurIPS 2025 · similarity 0.86)
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.