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

Kiran Tomlinson, Tobias Schnabel, Adith Swaminathan, Jennifer Neville

Introduction

Large Language Models (LLMs) have achieved remarkable performance gains through "inference-time scaling"—granting models more "time to think" by generating intermediate reasoning tokens via Chain-of-Thought (CoT). However, this capability comes at a steep computational price. Because transformer attention costs scale quadratically with sequence length, generating long reasoning chains is expensive and latency-heavy.

While empirical work often focuses on "reasoning compression" (e.g., prompting models to use fewer words), a fundamental theoretical question remains: What is the absolute minimum reasoning budget required to solve a task as the input size grows? This paper bridges the gap between empirical observation and theoretical limits, establishing asymptotic lower and upper bounds for reasoning token complexity.

The Theoretical Framework: From BAPO to cBAPO

To analyze transformer reasoning, the authors build upon the Bounded Attention Prefix Oracle (BAPO) model. BAPO abstracts a transformer as a system constrained by two specific communication bottlenecks:

  1. Prefix Bandwidth ($a$): The limited information that can be passed forward through the "residual stream" summary of previous tokens.
  2. Attention Bandwidth ($b$): The limited number of specific previous tokens a model can "look back" at during a single generation step.

A critical innovation in this work is the identification of a "loophole" in the original BAPO model, where a theoretical model could solve any problem simply by writing a second copy of the input. To resolve this, the authors introduce the self-consistent BAPO (cBAPO) model. Under cBAPO, the "prefix oracle" (the summary of the past) must itself be computable by a BAPO. This constraint much more accurately reflects how real transformers process information layer-by-layer. Using this framework and masking techniques, the authors prove that if a model fails to generate enough reasoning tokens, it eventually loses the capacity to distinguish between inputs that require different answers.

Fundamental Limits on Reasoning

The study focuses on three synthetic, "BAPO-hard" problem families where the input size $n$ serves as a natural scaling parameter:

  • MAJORITY: Determining if a bitstring contains more 1s than 0s.
  • MATCH3n: A modular arithmetic task involving finding specific triplets in a list.
  • REACHABILITY: Determining if a path exists between two nodes in a directed graph.

The Linear Floor: The central theoretical finding is that for these tasks, linear scaling is inescapable. If the input consists of $n$ tokens, a model requires at least $\Omega(n)$ reasoning tokens to solve it reliably. Because attention mechanisms scale quadratically with total sequence length, this implies that total inference compute for these fundamental tasks will scale at least quadratically.

Interestingly, the authors also prove that sublinear scaling is possible for certain tasks. For example, Pointer Chasing (following a chain of references) is BAPO-hard but only requires tokens proportional to the length of the chain, not the entire input size. This highlights that computational "hardness" and "token complexity" are distinct properties.

Empirical Validation on Frontier Models

To test these theoretical bounds, the authors evaluated frontier models, including GPT-5.2 and Gemini 2.5 Pro. The empirical results closely mirror the theoretical predictions:

  • Linear Scaling in Practice: GPT-5.2 exhibits almost perfect linear scaling in reasoning tokens across all three hard tasks as input size increases.
  • Budget Failures: When models were artificially constrained by a strict token budget (e.g., "solve this in exactly 50 words"), accuracy plummeted as the problem size $n$ increased. This confirms that the $\Omega(n)$ lower bounds represent practical, not just theoretical, walls.
  • Model Inefficiencies: While models can solve these problems with linear tokens, they often use significantly more than the theoretical minimum. For instance, on a Majority task of size $n=101$, Gemini 2.5 Pro used 8,000–9,000 tokens, whereas GPT-5.2 used roughly 1,500. This suggests massive room for "constant-factor" optimization in how current models reason.

Limitations and Future Directions

While cBAPO provides a robust framework for analyzing token complexity, it is a "pure" communication model. It does not account for modern LLM paradigms like external tool use (e.g., code interpreters) or Retrieval-Augmented Generation (RAG), which could potentially bypass these internal bottlenecks. Furthermore, the tasks studied are clean, mathematical problems; real-world reasoning tasks are significantly harder to parameterize strictly by "input size."

Ultimately, this work provides a principled tool for analyzing optimal reasoning length, identifying fundamental bottlenecks in inference-time compute, and paving the way for future research into architectures that might overcome these quadratic scaling limits.

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 $\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.
BibTeX
@inproceedings{tomlinson2026reasoning,
  author = {Kiran Tomlinson and Tobias Schnabel and Adith Swaminathan and Jennifer Neville},
  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