[2605.28600] Transformers Provably Learn to Internalize Chain-of-Thought

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.

View PDF HTML (experimental) 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,…

saved by

• Ishaan Panigrahi

related reading

• [2510.24941] Can Aha Moments Be Fake? Towards Quantifying Decorative and True Thinking in Chain-of-Thoughtarxiv.org
• Quantifying the Necessity of Chain of Thought through Opaque Serial Deptharxiv.org
• Getting Caught Up to Modern LLM Research | Samarth Goeldev.samarthgoel.com
• Transformer Circuits Threadtransformer-circuits.pub
• Transformers Learn to Implement Multi-step Gradient Descent with Chain of Thoughtarxiv.org
• 2402.12875arxiv.org
• [2402.12875] Chain of Thought Empowers Transformers to Solve Inherently Serial Problemsarxiv.org
• Let's Think Dot by Dot: Hidden Computation in Transformer Language Modelsarxiv.org
• [2404.15758] Let's Think Dot by Dot: Hidden Computation in Transformer Language Modelsarxiv.org
• Transformer Explainer: LLM Transformer Model Visually Explainedpoloclub.github.io
• In-context Learning and Induction Headstransformer-circuits.pub
• Exact Expressive Power of Transformers with Paddingarxiv.org