First CoT hierarchy theorem: more reasoning steps provably unlock harder problems
gurtej__gill_ · x · 2026-11-12
A NeurIPS 2026 paper, 'A Tight Hierarchy for Chain of Thought' (Le, Pavan, Vinodchandran), establishes the first true hierarchy theorem for CoT-based computation:
- Result: for any reasonable resource bound r(n) ≥ n and ε > 0, CoT(r(n)) ⊊ CoT(r(n)^(1+ε)) — giving a transformer slightly more reasoning steps provably unlocks decision problems entirely unreachable before.
- Significance: formalizes CoT steps as a fundamental computational resource, akin to time or space in classical complexity theory.
- Technique: classical hierarchy theorems rely on diagonalization, which fails for transformers; the authors link CoT-augmented transformers and Turing machines in both directions and adapt the classical padding technique to the transformer CoT model to obtain a tight hierarchy.
This gives rigorous theoretical backing to the intuition that bigger reasoning budgets make models fundamentally stronger.
Related event: Paper proves more reasoning tokens unlock harder problems, sparking debate(3 posts)→
More from Research
- Erik Hoel unveils 'Qualiaphobic AI': neural architectures designed to repel consciousness — erikphoel · 2026-11-13
- OpenAI: frontier models hide their thoughts because training optimizes for capability and compute — The Decoder · 2026-11-13
- 199 reports of soundness bugs in proof checkers collected on one page — jedisct1 · 2026-11-13
- Thermodynamics of words: word frequencies in literature match Rayleigh-Jeans thermalization — burny_tech · 2026-11-13
- Stochastic rounding lets BF16 RL post-training converge as fast as FP16 — heghbalz · 2026-11-13
- ML volume forecasting turns trade execution into alpha, Goyenko/Kelly/Moskowitz study — iblanco_finance · 2026-11-13