The assumption that chain-of-thought (CoT) prompting universally improves language model performance has become something close to received wisdom in the NLP community. This paper, available at arXiv:2608.09942, subjects that assumption to rigorous empirical scrutiny, using a theoretical framework from computational complexity to predict when CoT should and should not help. The result is a cleaner, more principled account of CoT's actual role than the field has had before.
The Theoretical Motivation
The paper anchors its hypotheses in the Hdp bandwidth bound from Chen et al. (2024), which provides the first unconditional lower bounds for multi-layer decoder-only transformers. The core idea is that a transformer's single forward pass has a finite capacity for serial computation, governed by the product of attention heads, head dimension, and numerical precision. Tasks requiring more serial depth than this capacity permits cannot be solved in one pass; they must externalise intermediate state, which is precisely what CoT does by writing reasoning steps to the output stream.
The authors are careful about a significant caveat: the formal bound only applies asymptotically, at prompt lengths so large as to be physically unrealisable (the paper calculates n* values on the order of 10^(10^34) for their smallest model). They therefore reframe Hdp not as a literal predictor but as conceptual motivation, using it to generate ordinal predictions about which task classes should benefit from CoT. This epistemic honesty about the theory's limits is one of the paper's stronger methodological choices.
The depth classification maps benchmarks onto computational complexity classes: GSM8K and MATH as P-complete (high serial depth), MMLU and ARC-Challenge as TC0 (shallow, parallelisable), and HumanEval as an intermediate class L. The prediction follows directly: CoT should provide large recovery gains for P-complete tasks and be redundant or harmful for TC0 tasks.
Methodology
Three instruction-tuned models are evaluated: Qwen-2.5-7B, Qwen-2.5-32B, and Llama-3.1-8B. The experimental design compares a no-CoT condition (short token cap forcing direct answers) against a CoT condition (2048-token budget with standard step-by-step prompting) across all five benchmarks. Key methodological details worth noting:
- All hypotheses were pre-registered on OSF, which substantially raises the evidential value of the results
- Answer extraction is handled carefully, with an appendix dedicated to extraction methodology and a pre-registered LLM-as-judge inter-rater check
- Per-item serial depth estimates are derived from structural proxies: calculator-step counts for GSM8K, equation counts for MATH, and AST nesting depth for HumanEval
- Statistical corrections use Bonferroni adjustment across 15 McNemar tests
- A memorisation-separation analysis using GSM-Symbolic perturbations was completed to partially address contamination concerns
The inter-rater reliability check deserves attention. The pre-registered target was Cohen's kappa of 0.70; the achieved value was 0.293. The authors treat this as a deviation indicating that real benchmarks are mixtures of computational primitives rather than pure instances of a single class. This is honest reporting, though it does weaken the precision of the theoretical mapping. The depth-based hypotheses themselves are not affected, since they depend on ordinal depth classification rather than primitive identity.
Results
The positive hypothesis is supported clearly and consistently:
- GSM8K and MATH show CoT recovery gaps of +54 to +68 percentage points across all three models
- No-CoT accuracy degrades monotonically with per-item serial depth on MATH; CoT accuracy is approximately depth-invariant across the same range
- Within the Qwen family, no-CoT accuracy on GSM8K rises with model size (23.1% for 7B, 39.9% for 32B), qualitatively consistent with larger Hdp permitting more within-pass serial computation
- HumanEval shows the predicted model-size-dependent transition: +23.2pp for Qwen-32B, +9.1pp for Llama-8B, and -28.7pp for Qwen-7B
The negative hypothesis is not supported. On MMLU and ARC-Challenge, CoT changes accuracy by 0.0 to +4.6pp across all six model-benchmark cells, with no Bonferroni-significant negative effects. The pooled cross-benchmark depth-recovery correlation is Spearman rho = 0.661 (p = 0.007, n = 15), with 9 of 15 McNemar tests significant after correction.
The one significant negative result is Qwen-7B on HumanEval (-28.7pp, p = 4x10^-9). The authors flag this as genuine but unexplained within the bandwidth framework, noting that the no-CoT condition for code generation permits 256 tokens for a function body, making it a contrast between writing code directly versus explaining first and then writing, rather than a clean single-pass test.
Limitations and Open Questions
The authors identify several important confounds. The most significant is that the no-CoT and CoT conditions differ simultaneously in whether intermediate state is externalised and in total inference-time compute. Because a decoder-only transformer performs additional serial computation only by emitting tokens, these two factors cannot be separated within the current design. The results are therefore equally consistent with an inference-time compute-scaling account, and the paper does not claim otherwise.
The TC0 null result is particularly hard to interpret cleanly. No-CoT accuracy on ARC-Challenge reaches 82-95% across the three models, a striking figure given that no system significantly outperformed random on the ARC Challenge Set in 2018. The authors discuss three non-exclusive explanations: ceiling effects leaving insufficient headroom for any architectural effect, annotation artifacts exploitable via lexical shortcuts (following Gururangan et al., 2018), and pretraining contamination (following Magar and Schwartz, 2022). All three are plausible; the paper cannot distinguish between them. This means the TC0 null is not a clean architectural test, and the authors say so explicitly.
The Llama-3.1-8B results also introduce a complication. Its nominal Hdp would place it between the two Qwen models, but its no-CoT accuracy on GSM8K (13.8%) falls well below Qwen-7B (23.1%). The authors attribute this to Grouped-Query Attention reducing effective per-token bandwidth, which is a reasonable hypothesis but one that requires the Hdp formula to be modified for GQA architectures in ways the paper does not formalise. With only three models and a family confound, the model-size trend remains suggestive rather than quantitative.
These results converge well with Sprague et al. (2025), whose meta-analysis across 100+ papers and 20 datasets reaches similar conclusions through a different methodology: CoT helps on math and symbolic reasoning, with negligible or negative effects on commonsense and knowledge tasks. The Hdp framework provides a principled theoretical account for why this pattern exists, even if it cannot yet predict the magnitude of effects at practical context lengths.
The practical implication is straightforward. For practitioners, CoT should be treated as a targeted intervention for tasks with high serial depth, not a default improvement. For researchers, the paper raises a pointed question about TC0 benchmark validity: if MMLU and ARC are too contaminated or artifact-laden to serve as clean architectural tests, the field needs benchmarks explicitly designed to resist both problems. The Hdp framework offers a useful design criterion for constructing such benchmarks, even if it cannot yet serve as a quantitative predictor.
Full paper, data, code, and inference logs are available at https://arxiv.org/abs/2608.09942.