mlsanityData to 7 Oct 2026

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

arXiv 2502.20129 ↗First posted 27 Feb 2025cs.CL cs.LGcited by 17

On the map: LLM reasoning → Prompting and chain-of-thought reasoning

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.

Key facts. Cited by 17 papers in the map (data through 7 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.

Builds on

27 of 41 references.

Closest ancestors · 4

Same direction, newest first

  1. 2024Training Large Language Models to Reason in a Continuous Latent Space9 Dec
  2. 2024Autoregressive + Chain of Thought = Recurrent: Recurrence's Role in Language Models' Computability and a Revisit of Recurrent Transformer14 Sep
  3. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problems20 Feb
  4. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Models28 Jan

Other references · 23

  1. 2023GPT-4 Technical Reportcited by 18,132
  2. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 13,958
  3. 2023Mamba: Linear-Time Sequence Modeling with Selective State Spacescited by 4,616
  4. 2021Efficiently Modeling Long Sequences with Structured State Spacescited by 2,424
  5. 2020Transformer Feed-Forward Layers Are Key-Value Memoriescited by 1,307
  6. 2023AgentBench: Evaluating LLMs as Agentscited by 1,211
  7. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 871
  8. 2023Finding Neurons in a Haystack: Case Studies with Sparse Probingcited by 328
  9. 2022Transformers Learn Shortcuts to Automatacited by 260
  10. 2023Think before you speak: Training Language Models With Pause Tokenscited by 254
  11. 2022FOLIO: Natural Language Reasoning with First-Order Logiccited by 233
  12. 2022Neural Networks and the Chomsky Hierarchycited by 214
11 more
  1. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 198
  2. 2024The Illusion of State in State-Space Modelscited by 181
  3. 2024Evaluating the World Model Implicit in a Generative Modelcited by 107
  4. 2024Unlocking State-Tracking in Linear RNNs Through Negative Eigenvaluescited by 97
  5. 2024Arithmetic Without Algorithms: Language Models Solve Math With a Bag of Heuristicscited by 94
  6. 2024LLMs Still Can't Plan; Can LRMs? A Preliminary Evaluation of OpenAI's o1 on PlanBenchcited by 93
  7. 2024Looped Transformers for Length Generalizationcited by 91
  8. 2023Copy Suppression: Comprehensively Understanding an Attention Headcited by 73
  9. 2021Chess as a Testbed for Language Model State Trackingcited by 69
  10. 2024Ask, and it shall be given: On the Turing completeness of promptingcited by 10
  11. 2020Addressing Some Limitations of Transformers with Feedback Memorycited by 8

Built on by

Cited by year (2026 to 7 Oct)

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

17 papers.

Sort:

By area:

  1. 2025Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Modelscited by 381
  2. 2025PaTH Attention: Position Encoding via Accumulating Householder Transformationscited by 32
  3. 2026Do Latent-CoT Models Think Step-by-Step? A Mechanistic Study on Sequential Reasoning Taskscited by 10
  4. 2025Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilitiescited by 6
  5. 2026Outcome-Based RL Provably Leads Transformers to Reason, but Only With the Right Datacited by 5
  6. 2026Do Language Models Track Entities Across State Changes?cited by 5
  7. 2025Critical Thinking: Which Kinds of Complexity Govern Optimal Reasoning Length?cited by 4
  8. 2025Thinking Machines: Mathematical Reasoning in the Age of LLMscited by 4
  9. 2025Distributional Semantics Tracing: A Framework for Explaining Hallucinations in Large Language Modelscited by 3
  10. 2026Indications of Belief-Guided Agency and Meta-Cognitive Monitoring in Large Language Modelscited by 3
  11. 2026CodeCircuit: Toward Inferring LLM-Generated Code Correctness via Attribution Graphscited by 3
  12. 2026Weights to Code: Extracting Interpretable Algorithms from the Discrete Transformercited by 2
5 more
  1. 2026When Does Activation Steering Change What a Model Computes From?cited by 2
  2. 2026Scaling Reasoning Hop Exposes Weaknesses: Demystifying and Improving Hop Generalization in Large Language Modelscited by 1
  3. 2026Diagnosing CFG Interpretation in LLMscited by 1
  4. 2026Evaluating the Formal Reasoning Capabilities of Large Language Models through Chomsky Hierarchycited by 0
  5. 2026StateSwap: Probing Support-Elimination Hidden States in Multiple-Choice Questionscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Adaptive Loops and Memory in Transformers: Think Harder or Know More?
  2. 2026The Topological Trouble With Transformers
  3. 2026Barriers to Universal Reasoning With Transformers (And How to Overcome Them)
  4. 2024On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning
  5. 2024Let's Think Dot by Dot: Hidden Computation in Transformer Language Models
  6. 2025The Kinetics of Reasoning: How Chain-of-Thought Shapes Learning in Transformers?
  7. 2025Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization
  8. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective