mlsanityData to 14 Oct 2026

(How) Do Language Models Track State?

arXiv 2503.02854 ↗First posted 4 Mar 2025cs.CL cs.AI cs.LGcited by 34

Not on the map. Why?

Abstract (arXiv)

Transformer language models (LMs) exhibit behaviors -- from storytelling to code generation -- that seem to require tracking the unobserved state of an evolving world. How do they do this? We study state tracking in LMs trained or fine-tuned to compose permutations (i.e., to compute the order of a set of objects after a sequence of swaps). Despite the simple algebraic structure of this problem, many other tasks (e.g., simulation of finite automata and evaluation of boolean expressions) can be reduced to permutation composition, making it a natural model for state tracking in general. We show that LMs consistently learn one of two state tracking mechanisms for this task. The first closely resembles the "associative scan" construction used in recent theoretical work by Liu et al. (2023) and Merrill et al. (2024). The second uses an easy-to-compute feature (permutation parity) to partially prune the space of outputs, and then refines this with an associative scan. LMs that learn the former algorithm tend to generalize better and converge faster, and we show how to steer LMs toward one or the other with intermediate training tasks that encourage or suppress the heuristics. Our results demonstrate that transformer LMs, whether pre-trained or fine-tuned, can learn to implement efficient and interpretable state-tracking mechanisms, and the emergence of these mechanisms can be predicted and controlled.

Key facts. Cited by 34 papers in the map (data through 14 Oct 2026). Builds on 27 of its 34 references that are in the map. First posted on arXiv 4 Mar 2025.

Builds on

27 of 34 references.

References · 27

  1. 2022Locating and Editing Factual Associations in GPTcited by 2,691
  2. 2023Pythia: A Suite for Analyzing Large Language Models Across Training and Scalingcited by 1,786
  3. 2022Interpretability in the Wild: a Circuit for Indirect Object Identification in GPT-2 smallcited by 1,165
  4. 2019What Does BERT Look At? An Analysis of BERT's Attentioncited by 1,003
  5. 2022In-context Learning and Induction Headscited by 964
  6. 2022Emergent World Representations: Exploring a Sequence Model Trained on a Synthetic Taskcited by 431
  7. 2023Towards Best Practices of Activation Patching in Language Models: Metrics and Methodscited by 359
  8. 2023Emergent Linear Representations in World Models of Self-Supervised Sequence Modelscited by 319
  9. 2022Transformers Learn Shortcuts to Automatacited by 268
  10. 2022Neural Networks and the Chomsky Hierarchycited by 217
  11. 2024How to use and interpret activation patchingcited by 214
  12. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 193
15 more
  1. 2024The Illusion of State in State-Space Modelscited by 187
  2. 2021Implicit Representations of Meaning in Neural Language Modelscited by 180
  3. 2024Do Large Language Models Latently Perform Multi-Hop Reasoning?cited by 169
  4. 2023The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networkscited by 156
  5. 2024Fine-Tuning Enhances Existing Mechanisms: A Case Study on Entity Trackingcited by 149
  6. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
  7. 2023Sudden Drops in the Loss: Syntax Acquisition, Phase Transitions, and Simplicity Bias in MLMscited by 124
  8. 2023What Formal Languages Can Transformers Express? A Surveycited by 124
  9. 2024Evaluating the World Model Implicit in a Generative Modelcited by 113
  10. 2023Circuit Component Reuse Across Tasks in Transformer Language Modelscited by 108
  11. 2019BERTs of a feather do not generalize together: Large variability in generalization across models with similar test set performancecited by 89
  12. 2024Emergent World Models and Latent Variable Estimation in Chess-Playing Language Modelscited by 62
  13. 2023Entity Tracking in Language Modelscited by 44
  14. 2023Latent State Models of Training Dynamicscited by 16
  15. 2025Episodic Memories Generation and Evaluation Benchmark for Large Language Modelscited by 14

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 11; 2026: 23.

34 papers.

Sort:

By area:

  1. 2026When Models Manipulate Manifolds: The Geometry of a Counting Taskcited by 46
  2. 2026How Many Features Can a Language Model Store Under the Linear Representation Hypothesis?cited by 12
  3. 2025Too Long, Didn't Model: Decomposing LLM Long-Context Understanding With Novelscited by 9
  4. 2025Mechanistic evaluation of Transformers and state space modelscited by 9
  5. 2026Latent Reasoning with Supervised Thinking Statescited by 9
  6. 2025Sequential-Parallel Duality in Prefix Scannable Modelscited by 8
  7. 2026T^2MLR: Transformer with Temporal Middle-Layer Recurrencecited by 7
  8. 2026Do Language Models Track Entities Across State Changes?cited by 6
  9. 2025In-Context Algebracited by 5
  10. 2025Thinking Machines: Mathematical Reasoning in the Age of LLMscited by 4
  11. 2026Context-Free Recognition with Transformerscited by 4
  12. 2026WMF-AM: Probing LLM Working Memory via Depth-Parameterized Cumulative State Trackingcited by 4
22 more
  1. 2025Is This Just Fantasy? Language Model Representations Reflect Human Judgments of Event Plausibilitycited by 3
  2. 2026Toward Consistent World Models with Multi-Token Prediction and Latent Semantic Enhancementcited by 3
  3. 2026A retrieval conditioned rebinding circuit for dynamic entity tracking in large language modelscited by 3
  4. 2025Function Induction and Task Generalization: An Interpretability Study with Off-by-One Additioncited by 2
  5. 2025Fuzzy, Symbolic, and Contextual: Enhancing LLM Instruction via Cognitive Scaffoldingcited by 2
  6. 2025The Impossibility of Inverse Permutation Learning in Transformer Modelscited by 2
  7. 2026On the "Induction Bias" in Sequence Modelscited by 2
  8. 2025From Memories to Maps: Mechanisms of In-Context Reinforcement Learning in Transformerscited by 1
  9. 2025Overcoming State Inertia: Minimally Invasive Temporal Alignment for Evolving Contextscited by 1
  10. 2026Barriers to Universal Reasoning With Transformers (And How to Overcome Them)cited by 1
  11. 2026Chess-World-Model: A 10M-Game Benchmark for Exact State Tracking from Chess Move Sequencescited by 1
  12. 2026How Do Language Models Understand Tables? A Mechanistic Analysis of Cell Locationcited by 0
  13. 2026Quantum Coordination Advantages in AI State-Tracking Tasks: Semantic Compilation and Latent Memorycited by 0
  14. 2026A Calibrated Test of Internal Action Maps: State Signals Without Global Affine Closurecited by 0
  15. 2026Entity tracking emerges in sub-billion parameter language models and exceeds human performance in naturalistic narrativescited by 0
  16. 2026Non-Commutative State Tracking with Input-Dependent Low-Rank Updates in Mamba-3cited by 0
  17. 2026Tracking States or Tracking Cosets? An Algebraic Account of Learned State Trackingcited by 0
  18. 2026Repetition, Not Length: Isolating the Counting Failure in Neural Text-to-Speechcited by 0
  19. 2026When Context Changes: Understanding Update Failures in LLMscited by 0
  20. 2026Beyond Memory: Harnessing Long-Horizon Agents with Explicit Belief Statescited by 0
  21. 2026A Testable Theory of Atomic Featurescited by 0
  22. 2026Learning to Compute Is Not Learning to Retain or Reuse in Looped Transformerscited by 0