A Tight Hierarchy for Chain of Thought

Thanh Le, A. Pavan, N. V. VinodchandranarXiv 2026 · arXiv

TL;DR

This paper provides the first formal proof that "thinking longer" makes transformers provably smarter. By establishing a hierarchy theorem for Chain-of-Thought (CoT) reasoning, the authors show that increasing the number of intermediate reasoning steps strictly expands the set of problems a transformer can solve, identifying CoT steps as a fundamental computational resource.

What Problem Does This Paper Address?

While Chain-of-Thought (CoT) reasoning—the process where a model generates intermediate "thoughts" before answering—has become a staple for improving Large Language Model (LLM) performance, its theoretical foundations have been somewhat murky. We know that transformers with CoT are "Turing complete" (they can eventually solve anything a computer can), but we haven't known if there is a fine-grained relationship between the number of steps and computational power.

In classical computer science, we have "hierarchy theorems" that prove a computer with more time or memory can solve strictly more problems than one with less. This paper asks: Is there a similar strict hierarchy for CoT reasoning? Specifically, if we give a transformer $n^{1.1}$ steps instead of $n$ steps, does it actually gain new capabilities, or is there some "universal threshold" where adding more steps stops helping?

Methods

Proving hierarchy theorems for neural networks is notoriously difficult because they lack the "clean" mathematical structure of Turing Machines (TMs). Standard proofs usually rely on diagonalization—a technique where you build a "universal" machine that simulates others and purposefully does the opposite of what they do. Building a "universal transformer" that can parse and simulate any other transformer's weights and architecture is conceptually messy.

To bypass this, the authors used a two-step strategy:

  1. Simulation: They leveraged existing research that translates between CoT-augmented transformers and Turing Machines. For example, a transformer with $t$ steps can be simulated by a TM in roughly $t^2$ time, and a TM running in $t$ time can be simulated by a transformer in $O(t)$ steps.
  2. Padding: They adapted the classical "padding technique" from complexity theory. If you have a coarse separation (e.g., knowing that $n^9$ steps is better than $n$ steps), you can "pad" a hard problem with dummy tokens to make the input artificially long. This allows you to "stretch" that coarse gap into a much finer one.

The technical heavy lifting involved creating "gadgets" within the transformer—specific configurations of layers and attention heads—that can handle this padding and simulation logic internally.

The padding argument used to establish the hierarchy. It shows how a transformer $R$ can generate padding and simulate a more powerful transformer $S$ to solve harder problems.

Datasets

Not applicable. This is a theoretical computer science paper focused on formal complexity classes and mathematical proofs rather than empirical benchmarks.

Key Insights and Ideas

  • CoT as a Fundamental Resource: The paper formalizes "decoding steps" as a primary computational resource, putting it on the same theoretical footing as "Time" or "Space" in traditional complexity theory.
  • The Power of Intermediate Tokens: The result confirms that the "scratchpad" provided by CoT isn't just a helpful heuristic; it is the engine that allows transformers to overcome their inherent architectural limitations (like fixed depth).
  • Bridging Neural and Classical Models: By using padding to translate Turing Machine hierarchies into the transformer domain, the authors provide a roadmap for applying other classical complexity tools to modern AI architectures.

Key Results

The main result is the CoT Hierarchy Theorem: For any reasonable resource bound $r(n)$ and any $\varepsilon > 0$: $$\mathrm{CoT}(r(n)) \subsetneq \mathrm{CoT}(r(n)^{1+\varepsilon})$$

In plain English: For any input of length $n$, a transformer allowed $O(r(n)^{1+\varepsilon})$ reasoning steps can solve problems that are mathematically impossible for a transformer limited to $O(r(n))$ steps. This proves that the computational landscape of transformers is "stratified"—small increases in the reasoning budget lead to provable gains in power.

Limitations and Future Work

  • Tightness of the Hierarchy: While the paper proves a polynomial hierarchy ($1+\varepsilon$), classical computer science often has much tighter "polylogarithmic" hierarchies. Whether we can prove that even a tiny bit more "thought" (e.g., $n \log n$ steps vs $n$ steps) helps remains an open question.
  • The Sub-linear Regime: The current proof requires the number of CoT steps to be at least as large as the input length ($r(n) \geq n$). The behavior of models that "think" for fewer steps than the input length is still unknown.
  • Model Assumptions: The proof relies on "saturated attention" (where attention is concentrated on a few tokens) and "log-precision" (limited numerical accuracy). Extending these results to standard "softmax" attention with arbitrary precision is a significant future challenge.

Summary updated

Abstract

Chain-of-thought (CoT) reasoning has emerged as a powerful paradigm for extending the computational capabilities of transformer-based models. A growing body of recent work has begun to uncover the fine-grained computational power of transformers augmented with CoT, as well as their connections to classical complexity theory. In this work, we advance this line of research by establishing the first hierarchy theorem for CoT-based computation. Our main result shows that for any reasonable resource bound $r(n) \geq n$ and any $\varepsilon > 0$, \[ \mathrm{CoT}(r(n)) \subsetneq \mathrm{CoT}(r(n)^{1+\varepsilon}), \] where $\mathrm{CoT}(r(n))$ denotes the class of decision problems solvable by transformers using $O(r(n))$ CoT reasoning steps on inputs of length $n$. Our result shows that increasing the number of CoT reasoning steps provably yields strictly greater computational power, establishing CoT steps as a fundamental resource in transformer-based computation. Unlike classical hierarchy theorems, which are typically proved via diagonalization, our approach leverages known coarse-grained simulations between CoT-augmented transformers and Turing machines in both directions. Building on these connections, we adapt the classical padding technique from complexity theory to this setting to obtain a tight hierarchy. A key technical contribution of our work is the implementation of padding within the transformer-based CoT model.
BibTeX
@misc{le2026tight,
  author = {Thanh Le and A. Pavan and N. V. Vinodchandran},
  title = {{A Tight Hierarchy for Chain of Thought}},
  year = {2026},
  eprint = {2611.09759},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.09759},
}
Figure