Research map / Architectures and efficiency / RNNs and normalization
Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues
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.
Shows theoretically that LRNNs with only positive eigenvalues cannot solve parity or count modulo 3 in finite precision, and that extending state-transition eigenvalues to [-1,1] (for Mamba and DeltaNet) enables parity and improves state-tracking, with 1.3B-scale pretraining that stays competitive.
Problem
Linear RNNs (Mamba, DeltaNet, GLA, etc.) fail at state-tracking tasks such as parity and modular arithmetic, which limits performance on tasks like code evaluation.
Approach
Extend the eigenvalue range of diagonal and generalized Householder state-transition matrices from [0,1] to [-1,1] (via 2s-1 and I-2 beta v v^T), which provably enables parity and regular-language state tracking and extends to non-diagonal DeltaNet at no extra computational cost.
Key results
- Mamba [-1,1] and DeltaNet [-1,1] solve parity with score 1.000, while Mamba [0,1] scores 0.000 and DeltaNet [0,1] scores 0.017.
- On modular arithmetic without brackets, DeltaNet [-1,1] reaches 0.971 versus 0.314 for DeltaNet [0,1].
- DeltaNet [-1,1] at 1.3B trained on FineWeb-100B achieves lower perplexity than [0,1] on code and math datasets, while Mamba [-1,1] generally degrades slightly on these datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Extend Mamba's state-transition eigenvalue range from [0, 1] to [-1, 1] | Mamba · Parity | scaled accuracy: 0.000 -> 1.000 | Helped |
| Extend DeltaNet's state-transition eigenvalue range from [0, 1] to [-1, 1] | DeltaNet · Parity | scaled accuracy: 0.017 -> 1.000 | Helped |
| Extend Mamba's state-transition eigenvalue range from [0, 1] to [-1, 1] | Mamba · Modular arithmetic without brackets | scaled accuracy: 0.095 -> 0.241 | Helped |
| Extend DeltaNet's state-transition eigenvalue range from [0, 1] to [-1, 1] | DeltaNet · Modular arithmetic without brackets | scaled accuracy: 0.314 -> 0.971 | Helped |
| Extend Mamba's state-transition eigenvalue range from [0, 1] to [-1, 1] | Mamba · Modular arithmetic with brackets | scaled accuracy: 0.123 -> 0.116 | Hurt |
| Extend DeltaNet's state-transition eigenvalue range from [0, 1] to [-1, 1] | DeltaNet · Modular arithmetic with brackets | scaled accuracy: 0.194 -> 0.260 | Helped |
| Extend DeltaNet's state-transition eigenvalue range from [0, 1] to [-1, 1] | DeltaNet 340M · FineWeb 100B | Avg. accuracy: 46.1 -> 45.8 | Hurt |
| Extend DeltaNet's state-transition eigenvalue range from [0, 1] to [-1, 1] | DeltaNet 340M · FineWeb 100B | SWDE continuation: 35.2 -> 37.2 | Helped |
| Extend DeltaNet's state-transition eigenvalue range from [0, 1] to [-1, 1] | DeltaNet 340M · FineWeb 100B | SQUAD continuation: 28.7 -> 33.1 | Helped |
| Extend Mamba's state-transition eigenvalue range from [0, 1] to [-1, 1] | Mamba 370M · FineWeb 100B | Avg. accuracy: 47.3 -> 48.2 | Helped |
| Extend DeltaNet's state-transition eigenvalue range from [0, 1] to [-1, 1] | DeltaNet 1.3B · FineWeb 100B | Avg. accuracy: 53.1 -> 52.4 | Hurt |
| Extend DeltaNet's state-transition eigenvalue range from [0, 1] to [-1, 1] | DeltaNet 340M · CodeParrot and Math-Hard length extrapolation | perplexity | Helped |
Surprising findings
- Mamba [-1,1] degrades language modeling perplexity on code and math datasets, unlike DeltaNet.
- Extending the range is still beneficial for permutation tasks with 3-element permutations in S5 setups.
Limitations
- Modification is incompatible with log-space cumulative product numerical technique used by Mamba2, GLA and mLSTM.
- Expressivity of DeltaNet [-1,1] with multiple layers beyond Z3 is unclear.
- Possible trade-off between state-tracking and associative recall is conjectured but not tested.
Experimental setup
Datasets: FineWeb-100B FineWeb SlimPajama CodeParrot MATH-HARD TriviaQA lm-harness tasks SWDE SQUAD FDA
Benchmarks: Parity Modular arithmetic (w/o and w/ brackets) S5 word problem Z60 addition CodeParrot perplexity MATH-HARD perplexity TriviaQA perplexity SlimPajama perplexity lm-harness SWDE SQUAD FDA
Metrics: scaled accuracy sequence accuracy perplexity accuracy contains-based accuracy
Baselines: Transformer mLSTM sLSTM Mamba [0,1] DeltaNet [0,1] GLA Transformer++
Builds on: Mamba DeltaNet GLA xLSTM Merrill et al. positive-eigenvalue diagonal LRNN analysis
Closest papers by meaning
- DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Products (NeurIPS 2025 · similarity 0.90)
- M$^2$RNN: Non-Linear RNNs with Matrix-Valued States for Scalable Language Modeling (NeurIPS 2026 · similarity 0.89)
- Fixed-Point RNNs: Interpolating from Diagonal to Dense (NeurIPS 2025 · similarity 0.87)
- Rethinking State Tracking in Recurrent Models Through Error Control Dynamics (NeurIPS 2026 · similarity 0.87)
- Universality of Linear Recurrences Followed by Non-linear Projections: Finite-Width Guarantees and Benefits of Complex Eigenvalues (ICML 2024 · similarity 0.86)
- Revisiting Bi-Linear State Transitions in Recurrent Neural Networks (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.