mlsanityData to 14 Oct 2026

Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues

arXiv 2411.12537 ↗First posted 19 Nov 2024cs.LG cs.CL cs.FLcited by 101

On the map: State-space sequence models (S4, Mamba) → Core SSM architectures for language

Abstract (arXiv)

Linear Recurrent Neural Networks (LRNNs) such as Mamba, RWKV, GLA, mLSTM, and DeltaNet have emerged as efficient alternatives to Transformers for long sequences. However, both Transformers and LRNNs struggle to perform state-tracking, which may impair performance in tasks such as code evaluation. In one forward pass, current architectures are unable to solve even parity, the simplest state-tracking task, which non-linear RNNs can handle effectively. Recently, Sarrof et al. (2024) demonstrated that the failure of LRNNs like Mamba to solve parity stems from restricting the value range of their diagonal state-transition matrices to [0, 1] and that incorporating negative values can resolve this issue. We extend this result to non-diagonal LRNNs such as DeltaNet. We prove that finite precision LRNNs with state-transition matrices having only positive eigenvalues cannot solve parity, while non-triangular matrices are needed to count modulo 3. Notably, we also prove that LRNNs can learn any regular language when their state-transition matrices are products of identity minus vector outer product matrices, each with eigenvalues in the range [-1, 1]. Our experiments confirm that extending the eigenvalue range of Mamba and DeltaNet to include negative values not only enables them to solve parity but consistently improves their performance on state-tracking tasks. We also show that state-tracking enabled LRNNs can be pretrained stably and efficiently at scale (1.3B parameters), achieving competitive performance on language modeling and showing promise on code and math tasks.

Key facts. Cited by 101 papers in the map (data through 14 Oct 2026). Placed in Core SSM architectures for language, one of 10 directions in State-space sequence models (S4, Mamba). Builds on 41 of its 65 references that are in the map. First posted on arXiv 19 Nov 2024.

Builds on

41 of 65 references.

Closest ancestors · 6

Same direction, newest first

  1. 2024Learning to (Learn at Test Time): RNNs with Expressive Hidden States5 Jul
  2. 2024Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality31 May
  3. 2024Theoretical Foundations of Deep Selective State-Space Models29 Feb
  4. 2023Gated Linear Attention Transformers with Hardware-Efficient Training11 Dec
  5. 2023Mamba: Linear-Time Sequence Modeling with Selective State Spaces1 Dec
  6. 2021Efficiently Modeling Long Sequences with Structured State Spaces31 Oct

Other references · 35

  1. 2017Attention Is All You Needcited by 60,361
  2. 2021Measuring Mathematical Problem Solving With the MATH Datasetcited by 5,371
  3. 2016SGDR: Stochastic Gradient Descent with Warm Restartscited by 5,045
  4. 2018Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challengecited by 4,886
  5. 2019HellaSwag: Can a Machine Really Finish Your Sentence?cited by 4,100
  6. 2017TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehensioncited by 2,955
  7. 2019PIQA: Reasoning about Physical Commonsense in Natural Languagecited by 2,883
  8. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 2,022
  9. 2018Know What You Don't Know: Unanswerable Questions for SQuADcited by 1,554
  10. 2019ZeRO: Memory Optimizations Toward Training Trillion Parameter Modelscited by 1,301
  11. 2016The LAMBADA dataset: Word prediction requiring a broad discourse contextcited by 992
  12. 2023RWKV: Reinventing RNNs for the Transformer Eracited by 827
23 more
  1. 2021Combining Recurrent, Convolutional, and Continuous-time Models with Linear State-Space Layerscited by 608
  2. 2021Linear Transformers Are Secretly Fast Weight Programmerscited by 502
  3. 2022Hungry Hungry Hippos: Towards Language Modeling with State Space Modelscited by 499
  4. 2024Parallelizing Linear Transformers with the Delta Rule over Sequence Lengthcited by 396
  5. 2024xLSTM: Extended Long Short-Term Memorycited by 327
  6. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
  7. 2022Transformers Learn Shortcuts to Automatacited by 268
  8. 2023Looped Transformers as Programmable Computerscited by 237
  9. 2022Neural Networks and the Chomsky Hierarchycited by 217
  10. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 193
  11. 2024The Illusion of State in State-Space Modelscited by 187
  12. 2023What Formal Languages Can Transformers Express? A Surveycited by 124
  13. 2023Language Models Enable Simple Systems for Generating Structured Views of Heterogeneous Data Lakescited by 111
  14. 2021Going Beyond Linear Transformers with Recurrent Fast Weight Programmerscited by 89
  15. 2020A Formal Hierarchy of RNN Architecturescited by 62
  16. 2020Learning Associative Inference Using Fast Weight Memorycited by 51
  17. 2024The Expressive Capacity of State Space Models: A Formal Language Perspectivecited by 46
  18. 2023Parallelizing non-linear sequential models over the sequence lengthcited by 45
  19. 2024Towards Scalable and Stable Parallelization of Nonlinear RNNscited by 38
  20. 2023Universality of Linear Recurrences Followed by Non-linear Projections: Finite-Width Guarantees and Benefits of Complex Eigenvaluescited by 36
  21. 2024Separations in the Representational Capabilities of Transformers and Recurrent Architecturescited by 29
  22. 2023Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensionscited by 20
  23. 2023Advancing Regular Language Reasoning in Linear Recurrent Neural Networkscited by 13

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 36; 2026: 63.

101 papers.

Sort:

By area:

  1. 2024Gated Delta Networks: Improving Mamba2 with Delta Rulecited by 532
  2. 2025Kimi Linear: An Expressive, Efficient Attention Architecturecited by 196
  3. 2026Mamba-3: Improved Sequence Modeling using State Space Principlescited by 89
  4. 2025DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Productscited by 75
  5. 2025It's All Connected: A Journey Through Test-Time Memorization, Attentional Bias, Retention, and Online Optimizationcited by 64
  6. 2025End-to-End Test-Time Training for Long Contextcited by 62
  7. 2025MesaNet: Sequence Modeling by Locally Optimal Test-Time Trainingcited by 47
  8. 2025Log-Linear Attentioncited by 40
  9. 2025PaTH Attention: Position Encoding via Accumulating Householder Transformationscited by 34
  10. 2025Understanding Transformer from the Perspective of Associative Memorycited by 34
  11. 2026Gated DeltaNet-2: Decoupling Erase and Write in Linear Attentioncited by 33
  12. 2025Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformerscited by 28
38 more
  1. 2025Implicit Language Models are RNNs: Balancing Parallelization and Expressivitycited by 22
  2. 2025Distilling to Hybrid Attention Models via KL-Guided Layer Selectioncited by 20
  3. 2025Finite State Automata Inside Transformers with Chain-of-Thought: A Mechanistic Study on State Trackingcited by 18
  4. 2025Structured Linear CDEs: Maximally Expressive and Parallel-in-Time Sequence Modelscited by 18
  5. 2025TempoPFN: Synthetic Pre-training of Linear RNNs for Zero-shot Time Series Forecastingcited by 17
  6. 2025Mamba Modulation: On the Length Generalization of Mambacited by 16
  7. 2025Structured Sparse Transition Matrices to Enable State Tracking in State-Space Modelscited by 16
  8. 2024On the Expressiveness and Length Generalization of Selective State-Space Models on Regular Languagescited by 15
  9. 2025Comba: Improving Bilinear RNNs with Closed-loop Controlcited by 15
  10. 2025Blending Complementary Memory Systems in Hybrid Quadratic-Linear Transformerscited by 12
  11. 2025Parallelization of Non-linear State-Space Models: Scaling Up Liquid-Resistance Liquid-Capacitance Networks for Efficient Sequence Modelingcited by 10
  12. 2025ARWKV: Pretrain is not what we need, an RNN-Attention-Based Language Model Born from Transformercited by 9
  13. 2025Selective Rotary Position Embeddingcited by 9
  14. 2026Deep Delta Learningcited by 9
  15. 2026The Expressive Limits of Diagonal SSMs for State-Trackingcited by 9
  16. 2025Block-Biased Mamba for Long-Range Sequence Processingcited by 8
  17. 2025Sequential-Parallel Duality in Prefix Scannable Modelscited by 8
  18. 2025Fast weight programming and linear transformers: from machine learning to neurobiologycited by 8
  19. 2026Kalman Linear Attention: Parallel Bayesian Filtering For Efficient Language Modelling and State Trackingcited by 8
  20. 2026Why Are Linear RNNs More Parallelizable?cited by 8
  21. 2026M2RNN: Non-Linear RNNs with Matrix-Valued States for Scalable Language Modelingcited by 8
  22. 2025Understanding Input Selectivity in Mamba: Impact on Approximation Power, Memorization, and Associative Recall Capacitycited by 7
  23. 2026Preconditioned DeltaNet: Curvature-aware Sequence Modeling for Linear Recurrencescited by 7
  24. 2026LT2: Linear-Time Looped Transformerscited by 7
  25. 2026T^2MLR: Transformer with Temporal Middle-Layer Recurrencecited by 7
  26. 2025Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilitiescited by 6
  27. 2026Learning State-Tracking from Code Using Linear RNNscited by 6
  28. 2025Fixed-Point RNNs: Interpolating from Diagonal to Densecited by 5
  29. 2025Weight-Space Linear Recurrent Neural Networkscited by 5
  30. 2026Debugging code world modelscited by 5
  31. 2025Rethinking Addressing in Language Models via Contexualized Equivariant Positional Encodingcited by 4
  32. 2025ParallelFlow: Parallelizing Linear Transformers via Flow Discretizationcited by 4
  33. 2025Revisiting Bi-Linear State Transitions in Recurrent Neural Networkscited by 4
  34. 2025A Unifying Framework for Parallelizing Sequential Models with Linear Dynamical Systemscited by 4
  35. 2026MDN: Parallelizing Stepwise Momentum for Delta Linear Attentioncited by 4
  36. 2026Rethinking State Tracking in Recurrent Models Through Error Control Dynamicscited by 4
  37. 2026The Capability Convergence Hypothesis: Capability from Access Structure, Not Scalecited by 4
  38. 2026The Topological Trouble With Transformerscited by 3

50 most cited of 101 All 101 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2023Dynamic Analysis and an Eigen Initializer for Recurrent Neural Networks
  2. 2024Recurrent neural networks: vanishing and exploding gradients are not the end of the story
  3. 2023Resurrecting Recurrent Neural Networks for Long Sequences
  4. 2025ParaRNN: Unlocking Parallel Training of Nonlinear RNNs for Large Language Models
  5. 2022Simplifying and Understanding State Space Models with Diagonal Linear RNNs
  6. 2024RotRNN: Modelling Long Sequences with Rotations
  7. 2026When Learning Hurts: Fixed-Pole RNN for Real-Time Online Training
  8. 2025Fast Training of Recurrent Neural Networks with Stationary State Feedbacks