Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
Source: https://arxiv.org/abs/2402.12875 Author: Zhiyuan Li, Hong Liu, Denny Zhou et al. Date: 2024-09-17
Summary
Theoretical paper proving that chain-of-thought (CoT) reasoning fundamentally changes what transformers can compute. Without CoT, transformers are limited to problems solvable in constant circuit depth. With CoT, they can solve arbitrarily serial problems.
Key Claims
- Fundamental result: transformers without CoT can only solve problems in TC^0 (constant-depth parallel computation).
- With CoT: each reasoning step extends the computation — arbitrarily serial problems become solvable.
- Why this matters: many real-world problems (sequential planning, complex reasoning) are inherently serial — they cannot be solved in parallel.
- Implication: CoT isn’t just a helpful trick; it’s a necessary condition for certain problem classes.
- Training implication: models trained with CoT have qualitatively different capabilities from models trained without it.
Connection to Other Sources
Theoretical foundation for Lilian Weng’s thinking survey and test-time compute concepts.
Concepts
- Test-Time Compute — CoT as computation extension mechanism
- Mechanistic Interpretability — what computation transformers can vs. cannot do