Reasoning about Reasoning: BAPO Bounds on Chain-of-Thought Token Complexity in LLMs

Kiran Tomlinson, Tobias Schnabel, Adith Swaminathan, Tara Safavi

Abstract

Inference-time scaling via chain-of-thought (CoT) reasoning is a major driver of state-of-the-art LLM performance, but it comes with substantial latency and compute costs. We address a fundamental theoretical question: how many reasoning tokens are required to solve a problem as input size grows? By extending the bounded attention prefix oracle (BAPO) model—an abstraction of LLMs that quantifies the information flow required to solve a task—we prove lower bounds on the CoT tokens required for three canonical BAPO-hard tasks: binary majority, triplet matching, and graph reachability. We show that each requires $\Omega(n)$ reasoning tokens when the input size is $n$. We complement these results with matching or near-matching upper bounds via explicit constructions. Finally, our experiments with frontier reasoning models show approximately linear reasoning token scaling on these tasks and failures when constrained to smaller reasoning budgets, consistent with our theoretical lower bounds. Together, our results identify fundamental bottlenecks in inference-time compute through CoT and offer a principled tool for analyzing optimal reasoning length.

Introduction: The Token Complexity Hypothesis

Large Language Models (LLMs) have achieved significant performance gains through "inference-time scaling"—the practice of allowing models to generate intermediate "Chain-of-Thought" (CoT) tokens. While effective, this process is computationally expensive. A critical question remains: is there a minimum number of tokens required to solve a specific task? This paper investigates the token complexity hypothesis, proposing that every problem has an inherent, minimal reasoning length that cannot be bypassed without sacrificing accuracy.

The BAPO-CoT Framework

To formalize this, we utilize the Bounded Attention Prefix Oracle (BAPO) model. BAPO abstracts an LLM as a system with constrained information flow, defined by two parameters:

  1. Prefix Bandwidth ($a$): A small summary of the preceding context.
  2. Attention Bandwidth ($b$): The number of specific previous tokens the model can directly attend to.

We extend this into BAPO-CoT, where the model generates intermediate tokens to solve "BAPO-hard" problems—tasks that exceed the communication capacity of a single-step LLM. We also introduce cBAPO (Self-consistent BAPO), a refinement requiring that the internal summarization mechanism itself be computable within the BAPO constraints, preventing theoretical "cheating" through arbitrary input doubling.

Theoretical Lower Bounds

We analyze three canonical tasks: Binary Majority, Triplet Matching (MATCH3n), and Graph Reachability. Our theoretical analysis proves that for these tasks, the reasoning chain must grow at least linearly with the input size $n$. Specifically, we establish a lower bound of $\Omega(n)$ tokens for Majority and Match3, and $\Omega(m)$ for Reachability (where $m$ is the number of edges).

Table 1: Theoretical lower and upper bounds for BAPO-hard tasks.

As shown in Table 1, these lower bounds are complemented by upper bounds achieved through explicit algorithmic constructions, demonstrating that linear scaling is both necessary and sufficient for these fundamental problems. This implies that CoT serves as a necessary communication channel to move information across the architectural bottlenecks of the transformer.

Empirical Validation

We evaluated these theoretical predictions using frontier models, including GPT-5.2 and Gemini 2.5 Pro, on synthetic datasets with input sizes ranging from 5 to 101.

Figure 1: Average completion tokens vs. input size $n$ across three tasks.

The experimental results (Figure 1) confirm our theory:

  • Linear Scaling: GPT-5.2 naturally exhibits linear token growth as $n$ increases, maintaining high accuracy.
  • The Cost of Shortcuts: When models are constrained by a fixed word budget below the theoretical $\Omega(n)$ requirement, accuracy collapses toward random guessing as the problem size grows.
  • Algorithmic Efficiency: Providing explicit algorithms (e.g., BFS for reachability) helps models stay within the linear scaling regime, whereas unguided CoT can lead to inefficient token usage or failed shortcut attempts.

Conclusion

Our work establishes that for many logical and mathematical tasks, there is a fundamental "information bottleneck" that prevents infinite reasoning compression. Because generating $n$ tokens in a transformer involves quadratic attention costs, a linear requirement for reasoning tokens implies that total compute scales at least quadratically ($n^2$) with context size. These findings provide a principled framework for analyzing optimal reasoning length and identifying bottlenecks in inference-time compute.

Summary updated

Abstract

Inference-time scaling via chain-of-thought (CoT) reasoning is a major driver of state-of-the-art LLM performance, but it comes with substantial latency and compute costs. We address a fundamental theoretical question: how many reasoning tokens are required to solve a problem as input size grows? By extending the bounded attention prefix oracle (BAPO) model--an abstraction of LLMs that quantifies the information flow required to solve a task--we prove lower bounds on the CoT tokens required for three canonical BAPO-hard tasks: binary majority, triplet matching, and graph reachability. We show that each requires $Ω(n)$ reasoning tokens when the input size is $n$. We complement these results with matching or near-matching upper bounds via explicit constructions. Finally, our experiments with frontier reasoning models show approximately linear reasoning token scaling on these tasks and failures when constrained to smaller reasoning budgets, consistent with our theoretical lower bounds. Together, our results identify fundamental bottlenecks in inference-time compute through CoT and offer a principled tool for analyzing optimal reasoning length.
BibTeX
@inproceedings{tomlinson2026reasoning,
  author = {Kiran Tomlinson and Tobias Schnabel and Adith Swaminathan and Tara Safavi},
  title = {{Reasoning about Reasoning: BAPO Bounds on Chain-of-Thought Token Complexity in LLMs}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=FXKhOhbgEz},
}
Figure