mlsanityData to 7 Oct 2026

Learning State-Tracking from Code Using Linear RNNs

arXiv 2602.14814 ↗First posted 16 Feb 2026cs.LG cs.CLcited by 5

Not on the map. Why?

Abstract (arXiv)

Over the last years, state-tracking tasks, particularly permutation composition, have become a testbed to understand the limits of sequence models architectures like Transformers and RNNs (linear and non-linear). However, these are often sequence-to-sequence tasks: learning to map actions (permutations) to states, which is incompatible with the next-token prediction setting commonly used to train language models. We address this gap by converting permutation composition into code via REPL traces that interleave state-reveals through prints and variable transformations. We show that linear RNNs capable of state-tracking excel also in this setting, while Transformers still fail. Motivated by this representation, we investigate why tracking states in code is generally difficult: actions are not always fully observable. We frame this as tracking the state of a probabilistic finite-state automaton with deterministic state reveals and show that linear RNNs can be worse than non-linear RNNs at tracking states in this setup.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 46 of its 70 references that are in the map. First posted on arXiv 16 Feb 2026.

Builds on

46 of 70 references.

References · 46

  1. 2016SGDR: Stochastic Gradient Descent with Warm Restartscited by 4,993
  2. 2023Mamba: Linear-Time Sequence Modeling with Selective State Spacescited by 4,616
  3. 2024Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Dualitycited by 1,283
  4. 2023Retentive Network: A Successor to Transformer for Large Language Modelscited by 594
  5. 2023Gated Linear Attention Transformers with Hardware-Efficient Trainingcited by 490
  6. 2024Gated Delta Networks: Improving Mamba2 with Delta Rulecited by 483
  7. 2021Linear Transformers Are Secretly Fast Weight Programmerscited by 471
  8. 2024Parallelizing Linear Transformers with the Delta Rule over Sequence Lengthcited by 373
  9. 2024Learning to (Learn at Test Time): RNNs with Expressive Hidden Statescited by 329
  10. 2024xLSTM: Extended Long Short-Term Memorycited by 320
  11. 2024Titans: Learning to Memorize at Test Timecited by 303
  12. 2024CRUXEval: A Benchmark for Code Reasoning, Understanding and Executioncited by 294
34 more
  1. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  2. 2022Transformers Learn Shortcuts to Automatacited by 260
  3. 2022Neural Networks and the Chomsky Hierarchycited by 214
  4. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  5. 2022Transformer Quality in Linear Timecited by 189
  6. 2024The Illusion of State in State-Space Modelscited by 181
  7. 2025Kimi Linear: An Expressive, Efficient Attention Architecturecited by 169
  8. 2025RWKV-7 "Goose" with Expressive Dynamic State Evolutioncited by 134
  9. 2017Parallelizing Linear Recurrent Neural Nets Over Sequence Lengthcited by 126
  10. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  11. 2024Evaluating the World Model Implicit in a Generative Modelcited by 107
  12. 2024Unlocking State-Tracking in Linear RNNs Through Negative Eigenvaluescited by 97
  13. 2025CWM: An Open-Weights LLM for Research on Code Generation with World Modelscited by 87
  14. 2021Chess as a Testbed for Language Model State Trackingcited by 69
  15. 2025DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Productscited by 69
  16. 2020A Formal Hierarchy of RNN Architecturescited by 61
  17. 2020Learning Associative Inference Using Fast Weight Memorycited by 51
  18. 2025What Has a Foundation Model Found? Using Inductive Bias to Probe for World Modelscited by 46
  19. 2023Parallelizing non-linear sequential models over the sequence lengthcited by 45
  20. 2024The Expressive Capacity of State Space Models: A Formal Language Perspectivecited by 45
  21. 2024NNsight and NDIF: Democratizing Access to Open-Weight Foundation Model Internalscited by 43
  22. 2024Towards Scalable and Stable Parallelization of Nonlinear RNNscited by 38
  23. 2023Code Execution with Pre-trained Language Modelscited by 33
  24. 2024Training Neural Networks as Recognizers of Formal Languagescited by 23
  25. 2025Implicit Language Models are RNNs: Balancing Parallelization and Expressivitycited by 21
  26. 2024What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languagescited by 20
  27. 2025Structured Linear CDEs: Maximally Expressive and Parallel-in-Time Sequence Modelscited by 16
  28. 2025Structured Sparse Transition Matrices to Enable State Tracking in State-Space Modelscited by 15
  29. 2023Advancing Regular Language Reasoning in Linear Recurrent Neural Networkscited by 13
  30. 2025ParaRNN: Unlocking Parallel Training of Nonlinear RNNs for Large Language Modelscited by 13
  31. 2026Kalman Linear Attention: Parallel Bayesian Filtering For Efficient Language Modelling and State Trackingcited by 7
  32. 2023Recurrent Neural Language Models as Probabilistic Finite-state Automatacited by 6
  33. 2024Uncertainty Representations in State-Space Layers for Deep Reinforcement Learning under Partial Observabilitycited by 5
  34. 2025Tracking World States with Language Models: State-Based Evaluation Using Chesscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 5.

5 papers.

  1. 2026On Subquadratic Architectures: From Applications to Principlescited by 1
  2. 2026Can Video World Models Track Unobserved World States?cited by 1
  3. 2026How Wrong Can a Good Predictor Be? Diverging Updates with Vanishing Predictive KLcited by 0
  4. 2026The Automaton Underneath: The Additive Input Pathway Is a Parasitic Attractor for State Tracking in Householder Linear RNNcited by 0
  5. 2026Switching Linear Attentioncited by 0