Research map / Architectures and efficiency / Attention and transformers
Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows via circuit complexity that constant-precision, constant-depth transformers are limited to AC^0 without CoT, while polynomial CoT steps let them solve any poly-size circuit problem, and validates this empirically on S_5 composition, iterated squaring, and circuit value.
Problem
Why chain-of-thought improves LLM reasoning: the expressiveness limits of constant-depth, finite-precision decoder-only transformers with and without intermediate CoT steps.
Approach
Tightens the expressiveness upper bound for constant-depth, constant-precision transformers to AC^0 (from TC^0) by handling per-step rounding, and shows that T steps of CoT let constant-depth transformers simulate any size-T boolean circuit, so CoT supplies serial computation that parallel depth lacks.
Key results
- Theory: constant-depth, constant-precision transformers without CoT are in AC^0, and T=poly(n) CoT steps let them simulate any poly-size circuit (Ppoly).
- Empirically, without CoT permutation composition accuracy stays around 20%, near random guessing among 5 outcomes, while CoT training succeeds for low-depth transformers.
- CoT is consistently better than the hint-only and no-CoT baselines on the serial tasks, with the largest gains at small depth.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add chain-of-thought supervision and autoregressive CoT generation | Low-depth transformers · Permutation composition (S5) | accuracy | Helped |
| Add chain-of-thought supervision and autoregressive CoT generation | Low-depth transformers · Iterated squaring | accuracy | Helped |
| Add chain-of-thought supervision and autoregressive CoT generation | Low-depth transformers · Circuit value problem | accuracy | Helped |
| Provide chain-of-thought steps as hint labels | Transformers · Arithmetic and symbolic reasoning tasks | accuracy | Helped |
| Use CoT instead of hint supervision | Low-depth transformers · Modular addition (C7) | accuracy | Helped |
Surprising findings
- Logarithmic CoT steps do not let constant-depth transformers exceed AC^0, so only polynomial CoT adds expressive power.
- Modular addition with float16 training reached high accuracy despite the TC^0 bound, attributed to finite sequence length and float16 acting like log-precision.
Limitations
- Results are non-uniform circuit-class statements rather than uniform learnability results.
- Experiments use synthetic tasks with a fixed architecture (embedding 512, 8 heads) and do not test natural language reasoning.
- Tree-structured summation and log-precision exponent cases (TC^0 for e>0) are left open.
Experimental setup
Datasets: synthetic modular addition data synthetic permutation composition data synthetic iterated squaring data synthetic circuit value problem data
Benchmarks: modular addition permutation composition S_5 iterated squaring circuit value problem
Metrics: accuracy probability of predicting all CoT tokens correctly
Baselines: no-CoT (BASE) training hint-only training
Builds on: Krohn-Rhodes decomposition theorem Transformers as parallel computers (TC^0 bounds) Adam
Closest papers by meaning
- The Expressive Power of Transformers with Chain of Thought (ICLR 2024 · similarity 0.92)
- Exact Expressive Power of Transformers with Padding (NeurIPS 2025 · similarity 0.91)
- Efficiently Representing Algorithms With Chain-of-Thought Transformers (NeurIPS 2026 · similarity 0.91)
- Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers (ICML 2025 · similarity 0.90)
- Analyzing the Power of Chain of Thought through Memorization Capabilities (NeurIPS 2025 · similarity 0.90)
- A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers (NeurIPS 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.