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

• URL: http://arxiv.org/abs/2502.20129v2
• Date: Wed, 12 Mar 2025 15:47:08 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>In this work, we evaluate the state tracking capabilities of Transformer+CoT and its variants, confirming the effectiveness of CoT.<n>We propose two metrics, compression and distinction, and show that the neuron sets for each state achieve nearly 100% accuracy.
• 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. In this work, we (1) 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, finding 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 realistic settings: skipping intermediate steps, introducing data noise, and testing length generalization. Our results demonstrate that Transformer+CoT learns robust algorithms (FSA), highlighting its resilience in challenging scenarios.

Related papers

• (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)

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.