Transformers Provably Learn to Internalize Chain-of-Thought

• URL: http://arxiv.org/abs/2605.28600v1
• Date: Wed, 27 May 2026 15:17:06 GMT
• Title: Transformers Provably Learn to Internalize Chain-of-Thought
• Abstract summary: Implicit Chain-of-Thought (ICoT) trains models to internalize intermediate steps within their hidden states.<n>Log-ICoT removes thinking tokens one at a time, reducing the number of stages from linear in $k$ to logarithmic.<n>Experiments on multi-layer transformers confirm the theory and visualize how reasoning is progressively absorbed into deeper layers.
• Score: 65.41010769606844
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Chain-of-Thought (CoT) prompting substantially improves the sample efficiency of transformers, reducing the complexity of tasks like parity learning from exponential to polynomial in the input length. However, generating explicit reasoning steps at inference is computationally expensive. Implicit Chain-of-Thought (ICoT) has emerged as a promising empirical remedy that trains models to internalize intermediate steps within their hidden states, but its theoretical foundations remain poorly understood. We give the first theoretical analysis of ICoT, proving that an $L$-layer transformer trained under our proposed Log-ICoT curriculum learns $k$-parity with $\mathsf{poly}(n)$ samples and $L = \log_2 k$ training stages. This matches the sample efficiency of explicit CoT while eliminating its inference overhead, and extends prior one-layer parity guarantees to multi-layer architectures. Compared to standard ICoT, which removes thinking tokens one at a time, Log-ICoT removes them in geometric chunks, reducing the number of stages from linear in $k$ to logarithmic. Experiments on multi-layer transformers confirm the theory and visualize how reasoning is progressively absorbed into deeper layers.

Related papers

• Fractured Chain-of-Thought Reasoning [61.647243580650446]
  We introduce Fractured Sampling, a unified inference-time strategy that interpolates between full CoT and solution-only sampling.<n>We show that Fractured Sampling consistently achieves superior accuracy-cost trade-offs, yielding steep log-linear scaling gains in Pass@k versus token budget.
  arXiv  Detail & Related papers  (2025-05-19T11:30:41Z)
• Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought [64.43689151961054]
  We prove that a two-layer transformer with $D$ steps of continuous CoTs can solve the directed graph reachability problem.<n>In our construction, each continuous thought vector is a superposition state that encodes multiple search frontiers simultaneously.
  arXiv  Detail & Related papers  (2025-05-18T18:36:53Z)
• 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.<n>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.51626700527835]
  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.<n>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)
• Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time [17.086679273053853]
  We show that a novel fast approximation method can calculate the gradients in almost linear time. By improving the efficiency of gradient, we hope that this work will facilitate more effective training and deployment of long-context language models.
  arXiv  Detail & Related papers  (2024-08-23T17:16:43Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  Chain of thought (CoT) is a highly effective method to improve the accuracy of large language models (LLMs) on arithmetics and symbolic reasoning tasks. This work provides a theoretical understanding of the power of CoT for decoder-only transformers through the lens of expressiveness.
  arXiv  Detail & Related papers  (2024-02-20T10:11:03Z)

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.