Research map / Large language models / Reasoning and chain of thought
Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
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.
Proves unconditional linear lower bounds on chain-of-thought length for high-sensitivity algorithmic problems (Parity, Multiplication, Median, Reachability) in unique-hard-attention transformers, with matching upper-bound constructions up to logarithmic factors.
Problem
How many chain-of-thought steps are necessary for transformers to solve algorithmic problems in TC^0 or beyond, such as Parity, multiplication, median and graph reachability, given that CoT length is currently poorly understood?
Approach
Extends random-restriction / switching-lemma techniques to transformers with CoTs: a sublinear-length UHAT CoT implies the function is fixable by restricting a constant fraction of inputs to be constant, so high-average-sensitivity functions (Parity, middle multiplication digits, median, DAG reachability) need Omega(N)-scale CoTs, with matching constructions.
Key results
- Any UHAT CoT for Parity has length Omega(N), attained by prefix-parity CoT of length Theta(N).
- A UHAT CoT for the middle multiplication digit M_N requires Omega(N); a UHAT scratchpad for the full product of length Theta(N log N) exists.
- For Median, UHAT scratchpads require Omega(N) length, attained by enumerating the lowest floor(N/2) numbers; trained models succeed with full CoT while no-CoT multiplication fails to generalize.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Provide prefix-parity CoT steps instead of no CoT | Transformer · Parity | accuracy | Helped |
| Provide only every k-th prefix-parity CoT step (ablation) | Transformer with prefix-parity CoT · Parity | accuracy | Hurt |
| Replace explicit prefix-parity steps with a dot-by-dot scratchpad (ablation) | Transformer with prefix-parity CoT · Parity | accuracy | Hurt |
| Provide the O(N log N) CoT instead of no CoT | 2-layer, 2-head transformer · Multiplication (up to 16 digits) | accuracy | Helped |
| Omit the CoT | 2-layer, 2-head transformer · Multiplication (up to 16 digits) | generalization accuracy | Hurt |
| Provide the full CoT rather than only every k-th step (ablation) | Transformer · Median | accuracy | Helped |
| Provide an O(|E| log |V|)-length scratchpad instead of no scratchpad | Transformer · DAG Reachability | accuracy | Helped |
| Omit the scratchpad | Transformer · DAG Reachability | accuracy | Hurt |
Surprising findings
- Dot-by-dot CoTs for Parity cannot have polynomial length (length omega(|x|^k)), while exponential-length dot-by-dot UHAT CoTs exist.
- Trained transformers on Parity with CoT skipping every k-th step succeed only for k up to roughly 3.
Limitations
- Bounds are worst-case and for the UHAT model, not softmax or log-precision transformers.
- Experiments use small models (2 layers, 2 heads) and are softmax-based, not the hard-attention theory setting.
- Bounds hold up to logarithmic factors and do not address average-case complexity.
Experimental setup
Datasets: synthetic Parity inputs (lengths 1-500) synthetic binary multiplication (up to 16 digits) synthetic Median inputs (lengths 6-398) random DAGs (5-35 vertices)
Benchmarks: Parity Multiplication Median DAG Reachability
Metrics: accuracy
Baselines: full linear CoT for Parity grade-school multiplication CoT no-CoT transformer dot-by-dot CoT
Builds on: Switching Lemma average sensitivity analysis of transformers (Hahn & Rofin) Chiang & Cholak style UHAT analysis Merrill & Sabharwal depth reduction Feng et al. multiplication CoT
Closest papers by meaning
- The Expressive Power of Transformers with Chain of Thought (ICLR 2024 · similarity 0.92)
- Chain of Thought Empowers Transformers to Solve Inherently Serial Problems (ICLR 2024 · similarity 0.90)
- Exact Expressive Power of Transformers with Padding (NeurIPS 2025 · similarity 0.88)
- Transformers Provably Solve Parity Efficiently with Chain of Thought (ICLR 2025 · similarity 0.88)
- Strassen Attention, Split VC Dimension and Compositionality in Transformers (NeurIPS 2025 · similarity 0.87)
- Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization (NeurIPS 2025 · similarity 0.87)
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.