# (How) Do Language Models Track State?

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

## Key facts

- Cited by 35 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 (most cited first, 27 of 27)

- [Locating and Editing Factual Associations in GPT](https://mlsanity.com/paper/2202.05262/) (2022)
- [Pythia: A Suite for Analyzing Large Language Models Across Training and Scaling](https://mlsanity.com/paper/2304.01373/) (2023)
- [Interpretability in the Wild: a Circuit for Indirect Object Identification in GPT-2 small](https://mlsanity.com/paper/2211.00593/) (2022)
- [What Does BERT Look At? An Analysis of BERT's Attention](https://mlsanity.com/paper/1906.04341/) (2019)
- [In-context Learning and Induction Heads](https://mlsanity.com/paper/2209.11895/) (2022)
- [Emergent World Representations: Exploring a Sequence Model Trained on a Synthetic Task](https://mlsanity.com/paper/2210.13382/) (2022)
- [Towards Best Practices of Activation Patching in Language Models: Metrics and Methods](https://mlsanity.com/paper/2309.16042/) (2023)
- [Emergent Linear Representations in World Models of Self-Supervised Sequence Models](https://mlsanity.com/paper/2309.00941/) (2023)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [How to use and interpret activation patching](https://mlsanity.com/paper/2404.15255/) (2024)
- [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)
- [Implicit Representations of Meaning in Neural Language Models](https://mlsanity.com/paper/2106.00737/) (2021)
- [Do Large Language Models Latently Perform Multi-Hop Reasoning?](https://mlsanity.com/paper/2402.16837/) (2024)
- [The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networks](https://mlsanity.com/paper/2306.17844/) (2023)
- [Fine-Tuning Enhances Existing Mechanisms: A Case Study on Entity Tracking](https://mlsanity.com/paper/2402.14811/) (2024)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [Sudden Drops in the Loss: Syntax Acquisition, Phase Transitions, and Simplicity Bias in MLMs](https://mlsanity.com/paper/2309.07311/) (2023)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [Evaluating the World Model Implicit in a Generative Model](https://mlsanity.com/paper/2406.03689/) (2024)
- [Circuit Component Reuse Across Tasks in Transformer Language Models](https://mlsanity.com/paper/2310.08744/) (2023)
- [BERTs of a feather do not generalize together: Large variability in generalization across models with similar test set performance](https://mlsanity.com/paper/1911.02969/) (2019)
- [Emergent World Models and Latent Variable Estimation in Chess-Playing Language Models](https://mlsanity.com/paper/2403.15498/) (2024)
- [Entity Tracking in Language Models](https://mlsanity.com/paper/2305.02363/) (2023)
- [Latent State Models of Training Dynamics](https://mlsanity.com/paper/2308.09543/) (2023)
- [Episodic Memories Generation and Evaluation Benchmark for Large Language Models](https://mlsanity.com/paper/2501.13121/) (2025)

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

- [When Models Manipulate Manifolds: The Geometry of a Counting Task](https://mlsanity.com/paper/2601.04480/) (2026)
- [How Many Features Can a Language Model Store Under the Linear Representation Hypothesis?](https://mlsanity.com/paper/2602.11246/) (2026)
- [Too Long, Didn't Model: Decomposing LLM Long-Context Understanding With Novels](https://mlsanity.com/paper/2505.14925/) (2025)
- [Mechanistic evaluation of Transformers and state space models](https://mlsanity.com/paper/2505.15105/) (2025)
- [Sequential-Parallel Duality in Prefix Scannable Models](https://mlsanity.com/paper/2506.10918/) (2025)
- [Latent Reasoning with Supervised Thinking States](https://mlsanity.com/paper/2602.08332/) (2026)
- [Do Language Models Track Entities Across State Changes?](https://mlsanity.com/paper/2605.30233/) (2026)
- [T^2MLR: Transformer with Temporal Middle-Layer Recurrence](https://mlsanity.com/paper/2607.15178/) (2026)
- [In-Context Algebra](https://mlsanity.com/paper/2512.16902/) (2025)
- [Is This Just Fantasy? Language Model Representations Reflect Human Judgments of Event Plausibility](https://mlsanity.com/paper/2507.12553/) (2025)
- [Thinking Machines: Mathematical Reasoning in the Age of LLMs](https://mlsanity.com/paper/2508.00459/) (2025)
- [Context-Free Recognition with Transformers](https://mlsanity.com/paper/2601.01754/) (2026)
- [WMF-AM: Probing LLM Working Memory via Depth-Parameterized Cumulative State Tracking](https://mlsanity.com/paper/2603.27343/) (2026)
- [On the "Induction Bias" in Sequence Models](https://mlsanity.com/paper/2602.18333/) (2026)
- [Toward Consistent World Models with Multi-Token Prediction and Latent Semantic Enhancement](https://mlsanity.com/paper/2604.06155/) (2026)
- [A retrieval conditioned rebinding circuit for dynamic entity tracking in large language models](https://mlsanity.com/paper/2606.08644/) (2026)
- [Function Induction and Task Generalization: An Interpretability Study with Off-by-One Addition](https://mlsanity.com/paper/2507.09875/) (2025)
- [Fuzzy, Symbolic, and Contextual: Enhancing LLM Instruction via Cognitive Scaffolding](https://mlsanity.com/paper/2508.21204/) (2025)
- [The Impossibility of Inverse Permutation Learning in Transformer Models](https://mlsanity.com/paper/2509.24125/) (2025)
- [Chess-World-Model: A 10M-Game Benchmark for Exact State Tracking from Chess Move Sequences](https://mlsanity.com/paper/2605.30100/) (2026)
- [From Memories to Maps: Mechanisms of In-Context Reinforcement Learning in Transformers](https://mlsanity.com/paper/2506.19686/) (2025)
- [Overcoming State Inertia: Minimally Invasive Temporal Alignment for Evolving Contexts](https://mlsanity.com/paper/2512.03704/) (2025)
- [Barriers to Universal Reasoning With Transformers (And How to Overcome Them)](https://mlsanity.com/paper/2604.25800/) (2026)
- [How Do Language Models Understand Tables? A Mechanistic Analysis of Cell Location](https://mlsanity.com/paper/2602.08548/) (2026)
- [Quantum Coordination Advantages in AI State-Tracking Tasks: Semantic Compilation and Latent Memory](https://mlsanity.com/paper/2608.11066/) (2026)
- [A Calibrated Test of Internal Action Maps: State Signals Without Global Affine Closure](https://mlsanity.com/paper/2608.13626/) (2026)
- [Entity tracking emerges in sub-billion parameter language models and exceeds human performance in naturalistic narratives](https://mlsanity.com/paper/2608.18083/) (2026)
- [Non-Commutative State Tracking with Input-Dependent Low-Rank Updates in Mamba-3](https://mlsanity.com/paper/2609.28273/) (2026)
- [Tracking States or Tracking Cosets? An Algebraic Account of Learned State Tracking](https://mlsanity.com/paper/2609.29951/) (2026)
- [Repetition, Not Length: Isolating the Counting Failure in Neural Text-to-Speech](https://mlsanity.com/paper/2609.36974/) (2026)

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