# Finite State Automata Inside Transformers with Chain-of-Thought: A Mechanistic Study on State Tracking

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning.
- Builds on 27 of its 41 references that are in the map.
- First posted on arXiv 27 Feb 2025.

## Placed in

- LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/)

## Builds on (most cited first, 27 of 27)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Transformer Feed-Forward Layers Are Key-Value Memories](https://mlsanity.com/paper/2012.14913/) (2020)
- [AgentBench: Evaluating LLMs as Agents](https://mlsanity.com/paper/2308.03688/) (2023)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Training Large Language Models to Reason in a Continuous Latent Space](https://mlsanity.com/paper/2412.06769/) (2024)
- [Finding Neurons in a Haystack: Case Studies with Sparse Probing](https://mlsanity.com/paper/2305.01610/) (2023)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Think before you speak: Training Language Models With Pause Tokens](https://mlsanity.com/paper/2310.02226/) (2023)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [FOLIO: Natural Language Reasoning with First-Order Logic](https://mlsanity.com/paper/2209.00840/) (2022)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [Evaluating the World Model Implicit in a Generative Model](https://mlsanity.com/paper/2406.03689/) (2024)
- [Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues](https://mlsanity.com/paper/2411.12537/) (2024)
- [Looped Transformers for Length Generalization](https://mlsanity.com/paper/2409.15647/) (2024)
- [Arithmetic Without Algorithms: Language Models Solve Math With a Bag of Heuristics](https://mlsanity.com/paper/2410.21272/) (2024)
- [LLMs Still Can't Plan; Can LRMs? A Preliminary Evaluation of OpenAI's o1 on PlanBench](https://mlsanity.com/paper/2409.13373/) (2024)
- [Copy Suppression: Comprehensively Understanding an Attention Head](https://mlsanity.com/paper/2310.04625/) (2023)
- [Chess as a Testbed for Language Model State Tracking](https://mlsanity.com/paper/2102.13249/) (2021)
- [Autoregressive + Chain of Thought = Recurrent: Recurrence's Role in Language Models' Computability and a Revisit of Recurrent Transformer](https://mlsanity.com/paper/2409.09239/) (2024)
- [Ask, and it shall be given: On the Turing completeness of prompting](https://mlsanity.com/paper/2411.01992/) (2024)
- [Addressing Some Limitations of Transformers with Feedback Memory](https://mlsanity.com/paper/2002.09402/) (2020)

## Built on by (most cited first, 18 of 18)

- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [PaTH Attention: Position Encoding via Accumulating Householder Transformations](https://mlsanity.com/paper/2505.16381/) (2025)
- [Do Latent-CoT Models Think Step-by-Step? A Mechanistic Study on Sequential Reasoning Tasks](https://mlsanity.com/paper/2602.00449/) (2026)
- [Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilities](https://mlsanity.com/paper/2505.21785/) (2025)
- [Outcome-Based RL Provably Leads Transformers to Reason, but Only With the Right Data](https://mlsanity.com/paper/2601.15158/) (2026)
- [Do Language Models Track Entities Across State Changes?](https://mlsanity.com/paper/2605.30233/) (2026)
- [Critical Thinking: Which Kinds of Complexity Govern Optimal Reasoning Length?](https://mlsanity.com/paper/2504.01935/) (2025)
- [Thinking Machines: Mathematical Reasoning in the Age of LLMs](https://mlsanity.com/paper/2508.00459/) (2025)
- [Distributional Semantics Tracing: A Framework for Explaining Hallucinations in Large Language Models](https://mlsanity.com/paper/2510.06107/) (2025)
- [Indications of Belief-Guided Agency and Meta-Cognitive Monitoring in Large Language Models](https://mlsanity.com/paper/2602.02467/) (2026)
- [CodeCircuit: Toward Inferring LLM-Generated Code Correctness via Attribution Graphs](https://mlsanity.com/paper/2602.07080/) (2026)
- [Weights to Code: Extracting Interpretable Algorithms from the Discrete Transformer](https://mlsanity.com/paper/2601.05770/) (2026)
- [When Does Activation Steering Change What a Model Computes From?](https://mlsanity.com/paper/2606.29522/) (2026)
- [Scaling Reasoning Hop Exposes Weaknesses: Demystifying and Improving Hop Generalization in Large Language Models](https://mlsanity.com/paper/2601.21214/) (2026)
- [Diagnosing CFG Interpretation in LLMs](https://mlsanity.com/paper/2604.20811/) (2026)
- [Evaluating the Formal Reasoning Capabilities of Large Language Models through Chomsky Hierarchy](https://mlsanity.com/paper/2604.02709/) (2026)
- [StateSwap: Probing Support-Elimination Hidden States in Multiple-Choice Questions](https://mlsanity.com/paper/2609.01081/) (2026)
- [Learning to Compute Is Not Learning to Retain or Reuse in Looped Transformers](https://mlsanity.com/paper/2610.19768/) (2026)

## Abstract (arXiv)

Chain-of-thought (CoT) significantly enhances the performance of large language models (LLMs) across a wide range of tasks, and prior research shows that CoT can theoretically increase expressiveness. However, there is limited mechanistic understanding of the algorithms that Transformer+CoT can learn. Our key contributions are: (1) We evaluate the state tracking capabilities of Transformer+CoT and its variants, confirming the effectiveness of CoT. (2) Next, we identify the circuit (a subset of model components, responsible for tracking the world state), indicating that late-layer MLP neurons play a key role. We propose two metrics, compression and distinction, and show that the neuron sets for each state achieve nearly 100% accuracy, providing evidence of an implicit finite state automaton (FSA) embedded within the model. (3) Additionally, we explore three challenging settings: skipping intermediate steps, introducing data noises, and testing length generalization. Our results demonstrate that Transformer+CoT learns robust algorithms (FSAs), highlighting its resilience in challenging scenarios. Our code is available at https://github.com/IvanChangPKU/FSA.