# Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues

arXiv: https://arxiv.org/abs/2411.12537 · HTML: https://mlsanity.com/paper/2411.12537/

## 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.

## Placed in

- State-space sequence models (S4, Mamba) / [Core SSM architectures for language](https://mlsanity.com/ssm/core-ssm-architectures-for-language/)

## Builds on (most cited first, 30 of 41)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge](https://mlsanity.com/paper/1803.05457/) (2018)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [HellaSwag: Can a Machine Really Finish Your Sentence?](https://mlsanity.com/paper/1905.07830/) (2019)
- [TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension](https://mlsanity.com/paper/1705.03551/) (2017)
- [PIQA: Reasoning about Physical Commonsense in Natural Language](https://mlsanity.com/paper/1911.11641/) (2019)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Know What You Don't Know: Unanswerable Questions for SQuAD](https://mlsanity.com/paper/1806.03822/) (2018)
- [Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality](https://mlsanity.com/paper/2405.21060/) (2024)
- [ZeRO: Memory Optimizations Toward Training Trillion Parameter Models](https://mlsanity.com/paper/1910.02054/) (2019)
- [The LAMBADA dataset: Word prediction requiring a broad discourse context](https://mlsanity.com/paper/1606.06031/) (2016)
- [RWKV: Reinventing RNNs for the Transformer Era](https://mlsanity.com/paper/2305.13048/) (2023)
- [Combining Recurrent, Convolutional, and Continuous-time Models with Linear State-Space Layers](https://mlsanity.com/paper/2110.13985/) (2021)
- [Gated Linear Attention Transformers with Hardware-Efficient Training](https://mlsanity.com/paper/2312.06635/) (2023)
- [Linear Transformers Are Secretly Fast Weight Programmers](https://mlsanity.com/paper/2102.11174/) (2021)
- [Hungry Hungry Hippos: Towards Language Modeling with State Space Models](https://mlsanity.com/paper/2212.14052/) (2022)
- [Parallelizing Linear Transformers with the Delta Rule over Sequence Length](https://mlsanity.com/paper/2406.06484/) (2024)
- [Learning to (Learn at Test Time): RNNs with Expressive Hidden States](https://mlsanity.com/paper/2407.04620/) (2024)
- [xLSTM: Extended Long Short-Term Memory](https://mlsanity.com/paper/2405.04517/) (2024)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Looped Transformers as Programmable Computers](https://mlsanity.com/paper/2301.13196/) (2023)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [Language Models Enable Simple Systems for Generating Structured Views of Heterogeneous Data Lakes](https://mlsanity.com/paper/2304.09433/) (2023)

## Built on by (most cited first, 30 of 101)

- [Gated Delta Networks: Improving Mamba2 with Delta Rule](https://mlsanity.com/paper/2412.06464/) (2024)
- [Kimi Linear: An Expressive, Efficient Attention Architecture](https://mlsanity.com/paper/2510.26692/) (2025)
- [Mamba-3: Improved Sequence Modeling using State Space Principles](https://mlsanity.com/paper/2603.15569/) (2026)
- [DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Products](https://mlsanity.com/paper/2502.10297/) (2025)
- [It's All Connected: A Journey Through Test-Time Memorization, Attentional Bias, Retention, and Online Optimization](https://mlsanity.com/paper/2504.13173/) (2025)
- [End-to-End Test-Time Training for Long Context](https://mlsanity.com/paper/2512.23675/) (2025)
- [MesaNet: Sequence Modeling by Locally Optimal Test-Time Training](https://mlsanity.com/paper/2506.05233/) (2025)
- [Log-Linear Attention](https://mlsanity.com/paper/2506.04761/) (2025)
- [PaTH Attention: Position Encoding via Accumulating Householder Transformations](https://mlsanity.com/paper/2505.16381/) (2025)
- [Understanding Transformer from the Perspective of Associative Memory](https://mlsanity.com/paper/2505.19488/) (2025)
- [Gated DeltaNet-2: Decoupling Erase and Write in Linear Attention](https://mlsanity.com/paper/2605.22791/) (2026)
- [Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers](https://mlsanity.com/paper/2502.02393/) (2025)
- [Implicit Language Models are RNNs: Balancing Parallelization and Expressivity](https://mlsanity.com/paper/2502.07827/) (2025)
- [Distilling to Hybrid Attention Models via KL-Guided Layer Selection](https://mlsanity.com/paper/2512.20569/) (2025)
- [Finite State Automata Inside Transformers with Chain-of-Thought: A Mechanistic Study on State Tracking](https://mlsanity.com/paper/2502.20129/) (2025)
- [Structured Linear CDEs: Maximally Expressive and Parallel-in-Time Sequence Models](https://mlsanity.com/paper/2505.17761/) (2025)
- [TempoPFN: Synthetic Pre-training of Linear RNNs for Zero-shot Time Series Forecasting](https://mlsanity.com/paper/2510.25502/) (2025)
- [Mamba Modulation: On the Length Generalization of Mamba](https://mlsanity.com/paper/2509.19633/) (2025)
- [Structured Sparse Transition Matrices to Enable State Tracking in State-Space Models](https://mlsanity.com/paper/2509.22284/) (2025)
- [On the Expressiveness and Length Generalization of Selective State-Space Models on Regular Languages](https://mlsanity.com/paper/2412.19350/) (2024)
- [Comba: Improving Bilinear RNNs with Closed-loop Control](https://mlsanity.com/paper/2506.02475/) (2025)
- [Blending Complementary Memory Systems in Hybrid Quadratic-Linear Transformers](https://mlsanity.com/paper/2506.00744/) (2025)
- [Parallelization of Non-linear State-Space Models: Scaling Up Liquid-Resistance Liquid-Capacitance Networks for Efficient Sequence Modeling](https://mlsanity.com/paper/2505.21717/) (2025)
- [ARWKV: Pretrain is not what we need, an RNN-Attention-Based Language Model Born from Transformer](https://mlsanity.com/paper/2501.15570/) (2025)
- [Selective Rotary Position Embedding](https://mlsanity.com/paper/2511.17388/) (2025)
- [Deep Delta Learning](https://mlsanity.com/paper/2601.00417/) (2026)
- [The Expressive Limits of Diagonal SSMs for State-Tracking](https://mlsanity.com/paper/2603.01959/) (2026)
- [Block-Biased Mamba for Long-Range Sequence Processing](https://mlsanity.com/paper/2505.09022/) (2025)
- [Sequential-Parallel Duality in Prefix Scannable Models](https://mlsanity.com/paper/2506.10918/) (2025)
- [Fast weight programming and linear transformers: from machine learning to neurobiology](https://mlsanity.com/paper/2508.08435/) (2025)

## 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.