mlsanityData to 14 Oct 2026

Transformers Provably Learn to Internalize Chain-of-Thought

arXiv 2605.28600 ↗First posted 27 May 2026cs.LGcited by 2

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

Abstract (arXiv)

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 mathsfpoly(n) samples and L = log2 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.

Key facts. Cited by 2 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 57 of its 58 references that are in the map. First posted on arXiv 27 May 2026.

Builds on

57 of 58 references.

Closest ancestors · 19

Same direction, newest first

  1. 2026Breaking the Reversal Curse in Autoregressive Language Models via Identity Bridge2 Feb
  2. 2026Self-Distilled Reasoner: On-Policy Self-Distillation for Large Language Models26 Jan
  3. 2025Emergence of Superposition: Unveiling the Training Dynamics of Chain of Continuous Thought27 Sep
  4. 2025Continuous Chain of Thought Enables Parallel Exploration and Reasoning29 May
  5. 2025Exact Expressive Power of Transformers with Padding25 May
  6. 2025Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought18 May
  7. 2025Transformers Learn to Implement Multi-step Gradient Descent with Chain of Thought28 Feb
  8. 2024Training Large Language Models to Reason in a Continuous Latent Space9 Dec
  9. 2024Transformers Provably Solve Parity Efficiently with Chain of Thought11 Oct
  10. 2024From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiency7 Oct
  11. 2024From Explicit CoT to Implicit CoT: Learning to Internalize CoT Step by Step23 May
  12. 2024Let's Think Dot by Dot: Hidden Computation in Transformer Language Models24 Apr
7 more
  1. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problems20 Feb
  2. 2023Implicit Chain of Thought Reasoning via Knowledge Distillation2 Nov
  3. 2023Guiding Language Model Reasoning with Planning Tokens9 Oct
  4. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective24 May
  5. 2022Large Language Models are Zero-Shot Reasoners24 May
  6. 2022Least-to-Most Prompting Enables Complex Reasoning in Large Language Models21 May
  7. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Models28 Jan

Other references · 38

  1. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 9,379
  2. 2017Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inferencecited by 1,593
  3. 2023Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotationscited by 928
  4. 2023MetaMath: Bootstrap Your Own Mathematical Questions for Large Language Modelscited by 735
  5. 2022Decomposed Prompting: A Modular Approach for Solving Complex Taskscited by 558
  6. 2023MAmmoTH: Building Math Generalist Models through Hybrid Instruction Tuningcited by 487
  7. 2023Trained Transformers Learn Linear Models In-Contextcited by 337
  8. 2026Reinforcement Learning via Self-Distillationcited by 332
  9. 2019Stabilizing Transformers for Reinforcement Learningcited by 270
  10. 2022Transformers Learn Shortcuts to Automatacited by 268
  11. 2023Think before you speak: Training Language Models With Pause Tokenscited by 264
  12. 2015Highway Networkscited by 260
26 more
  1. 2020Integer Quantization for Deep Learning Inference: Principles and Empirical Evaluationcited by 188
  2. 2023One Step of Gradient Descent is Provably the Optimal In-Context Learner with One Layer of Linear Self-Attentioncited by 170
  3. 2023Birth of a Transformer: A Memory Viewpointcited by 161
  4. 2024How Transformers Learn Causal Structure with Gradient Descentcited by 118
  5. 2023In-Context Convergence of Transformerscited by 115
  6. 2023Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformercited by 102
  7. 2022Vision Transformers provably learn spatial structurecited by 93
  8. 2025Token Assorted: Mixing Latent and Text Tokens for Improved Language Model Reasoningcited by 91
  9. 2024Hyper-Connectionscited by 84
  10. 2017Failures of Gradient-Based Deep Learningcited by 80
  11. 2024Active-Dormant Attention Heads: Mechanistically Demystifying Extreme-Token Phenomena in LLMscited by 56
  12. 2023Transformers learn through gradual rank increasecited by 52
  13. 2023JoMA: Demystifying Multilayer Transformers via JOint Dynamics of MLP and Attentioncited by 52
  14. 2022Sub-Task Decomposition Enables Learning in Sequence to Sequence Taskscited by 41
  15. 2023What can a Single Attention Layer Learn? A Study Through the Random Features Lenscited by 40
  16. 2025Learning Compositional Functions with Transformers from Easy-to-Hard Datacited by 36
  17. 2024From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformerscited by 34
  18. 2024Mechanics of Next Token Prediction with Self-Attentioncited by 34
  19. 2023ResiDual: Transformer with Dual Residual Connectionscited by 31
  20. 2024Towards a Theoretical Understanding of the 'Reversal Curse' via Training Dynamicscited by 27
  21. 2024Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannotcited by 22
  22. 2025How Do LLMs Perform Two-Hop Reasoning in Context?cited by 20
  23. 2024Distributional Associations vs In-Context Reasoning: A Study of Feed-forward and Attention Layerscited by 12
  24. 2025Generalization or Hallucination? Understanding Out-of-Context Reasoning in Transformerscited by 10
  25. 2024Learning and Transferring Sparse Contextual Bigrams with Linear Transformerscited by 9
  26. 2025Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformerscited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Reading Between the Dots: Decoding Hidden Computation across Filler Tokenscited by 2
  2. 2026What Pretraining and Midtraining Make Learnable from Rewards?cited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis
  2. 2025The Kinetics of Reasoning: How Chain-of-Thought Shapes Learning in Transformers?
  3. 2023Dissecting Chain-of-Thought: Compositionality through In-Context Filtering and Learning
  4. 2024Understanding Hidden Computations in Chain-of-Thought Reasoning
  5. 2025Latent Chain-of-Thought? Decoding the Depth-Recurrent Transformer
  6. 2024A Theoretical Understanding of Chain-of-Thought: Coherent Reasoning and Error-Aware Demonstration
  7. 2025Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization
  8. 2026Thinking Without Words: Efficient Latent Reasoning with Abstract Chain-of-Thought