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

• URL: http://arxiv.org/abs/2502.20129v3
• Date: Tue, 03 Jun 2025 10:48:30 GMT
• Title: Finite State Automata Inside Transformers with Chain-of-Thought: A Mechanistic Study on State Tracking
• Authors: Yifan Zhang, Wenyu Du, Dongming Jin, Jie Fu, Zhi Jin,
• Abstract summary: Chain-of-thought (CoT) significantly enhances the performance of large language models (LLMs) across a wide range of tasks.<n>There is limited mechanistic understanding of the algorithms that Transformer+CoT can learn.<n>We evaluate the state tracking capabilities of Transformer+CoT and its variants, confirming the effectiveness of CoT.
• Score: 41.3496135369579
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• S3-CoT: Self-Sampled Succinct Reasoning Enables Efficient Chain-of-Thought LLMs [48.80914119283909]
  Large language models equipped with chain-of-thought (CoT) achieve strong performance and offer a window into behavior.<n>Recent evidence suggests that improvements in CoT capabilities often come with redundant reasoning processes.<n>Our study presents a self-sampling framework based on activation steering for efficient CoT learning.
  arXiv  Detail & Related papers  (2026-02-02T11:37:36Z)
• When Bayesian Tensor Completion Meets Multioutput Gaussian Processes: Functional Universality and Rank Learning [53.17227599983122]
  Functional tensor decomposition can analyze multi-dimensional data with real-valued indices.<n>We propose a rank-revealing functional low-rank tensor completion (RR-F) method.<n>We establish the universal approximation property of the model for continuous multi-dimensional signals.
  arXiv  Detail & Related papers  (2025-12-25T03:15:52Z)
• Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently [20.12397699480725]
  Reinforcement learning (RL) and supervised fine-tuning (SFT) are two primary approaches to this end, yet their underlying mechanisms and differences remain theoretically unclear.<n>We analyze the learning dynamics of fine-tuning the transformer via either RL or SFT with CoT to identify sufficient conditions for it to provably learn these functions.<n> Notably, we reveal that RL and SFT exhibit distinct learning behaviors: RL learns the whole CoT chain simultaneously, whereas SFT learns the CoT chain step-by-step.
  arXiv  Detail & Related papers  (2025-11-22T00:38:43Z)
• The Kinetics of Reasoning: How Chain-of-Thought Shapes Learning in Transformers? [25.29458951592086]
  Chain-of-thought (CoT) supervision can substantially improve transformer performance.<n>We investigate these learning dynamics through the lens of grokking by pretraining transformers on symbolic reasoning tasks.
  arXiv  Detail & Related papers  (2025-10-28T20:14:26Z)
• (How) Do Language Models Track State? [50.516691979518164]
  Transformer language models (LMs) exhibit behaviors that appear to require tracking the unobserved state of an evolving world. We study state tracking in LMs trained or fine-tuned to compose permutations. We show that LMs consistently learn one of two state tracking mechanisms for this task.
  arXiv  Detail & Related papers  (2025-03-04T18:31:02Z)
• Transformer Meets Twicing: Harnessing Unattended Residual Information [2.1605931466490795]
  Transformer-based deep learning models have achieved state-of-the-art performance across numerous language and vision tasks. While the self-attention mechanism has proven capable of handling complex data patterns, it has been observed that the representational capacity of the attention matrix degrades significantly across transformer layers. We propose the Twicing Attention, a novel attention mechanism that uses kernel twicing procedure in nonparametric regression to alleviate the low-pass behavior of associated NLM smoothing.
  arXiv  Detail & Related papers  (2025-03-02T01:56:35Z)
• Beyond In-Distribution Success: Scaling Curves of CoT Granularity for Language Model Generalization [35.16980045900664]
  Generalization to novel compound tasks under distribution shift is important for deploying transformer-based language models (LMs)<n>This work investigates Chain-of-Thought (CoT) reasoning as a means to enhance OOD generalization.
  arXiv  Detail & Related papers  (2025-02-25T15:04:17Z)
• Transformers Provably Solve Parity Efficiently with Chain of Thought [40.78854925996]
  This work provides the first theoretical analysis of training transformers to solve complex problems. We consider training a one-layer transformer to solve the fundamental $k$-parity problem.
  arXiv  Detail & Related papers  (2024-10-11T08:55:17Z)
• Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis [82.51626700527837]
  Chain-of-shift (CoT) is an efficient method that enables the reasoning ability of large language models by augmenting the query using examples with multiple intermediate steps. We show that despite the theoretical success of CoT, it fails to provide an accurate generalization when CoT does.
  arXiv  Detail & Related papers  (2024-10-03T03:12:51Z)
• Unveiling Induction Heads: Provable Training Dynamics and Feature Learning in Transformers [54.20763128054692]
  We study how a two-attention-layer transformer is trained to perform ICL on $n$-gram Markov chain data. We prove that the gradient flow with respect to a cross-entropy ICL loss converges to a limiting model.
  arXiv  Detail & Related papers  (2024-09-09T18:10:26Z)
• Unlock the Correlation between Supervised Fine-Tuning and Reinforcement Learning in Training Code Large Language Models [12.656574142412484]
  We make an attempt to understand the correlation between supervised fine-tuning and reinforcement learning.<n>We find that both atomic and synthetic functions are indispensable for SFT's generalization.
  arXiv  Detail & Related papers  (2024-06-14T03:39:01Z)
• In-Context Convergence of Transformers [63.04956160537308]
  We study the learning dynamics of a one-layer transformer with softmax attention trained via gradient descent. For data with imbalanced features, we show that the learning dynamics take a stage-wise convergence process.
  arXiv  Detail & Related papers  (2023-10-08T17:55:33Z)
• Joint Spatial-Temporal and Appearance Modeling with Transformer for Multiple Object Tracking [59.79252390626194]
  We propose a novel solution named TransSTAM, which leverages Transformer to model both the appearance features of each object and the spatial-temporal relationships among objects. The proposed method is evaluated on multiple public benchmarks including MOT16, MOT17, and MOT20, and it achieves a clear performance improvement in both IDF1 and HOTA.
  arXiv  Detail & Related papers  (2022-05-31T01:19:18Z)
• Inducing Transformer's Compositional Generalization Ability via Auxiliary Sequence Prediction Tasks [86.10875837475783]
  Systematic compositionality is an essential mechanism in human language, allowing the recombination of known parts to create novel expressions. Existing neural models have been shown to lack this basic ability in learning symbolic structures. We propose two auxiliary sequence prediction tasks that track the progress of function and argument semantics.
  arXiv  Detail & Related papers  (2021-09-30T16:41:19Z)
• Improving Transformer-Kernel Ranking Model Using Conformer and Query Term Independence [29.442579683405913]
  The Transformer- Kernel (TK) model has demonstrated strong reranking performance on the TREC Deep Learning benchmark. A variant of the TK model -- called TKL -- has been developed that incorporates local self-attention to efficiently process longer input sequences. In this work, we propose a novel Conformer layer as an alternative approach to scale TK to longer input sequences.
  arXiv  Detail & Related papers  (2021-04-19T15:32:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.