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

AI summary

arXiv: 2602.02909v2 [cs.AI] | Authors: Kiran Tomlinson, Tobias Schnabel, Adith Swaminathan, Jennifer Neville | Affiliations: Microsoft Research, Redmond, WA; Netflix, Los Gatos, CA

Overview

• Research area: Theory of large language models — specifically the computational complexity of chain-of-thought (CoT) reasoning, building on the bounded attention prefix oracle (BAPO) abstraction of transformers.
• Technical level: Advanced. The paper is a complexity-theory paper with formal definitions, lower-bound impossibility proofs, and explicit algorithmic constructions, supported by empirical evaluation on frontier reasoning models.
• Scope (one sentence): The paper proves asymptotic lower and upper bounds on how many reasoning tokens are required to solve three BAPO-hard problems as input size grows, and checks those predictions against GPT-5.2 and Gemini 2.5 Pro.

What This Paper Is About

Inference-time scaling — letting a model generate intermediate reasoning tokens before answering — is a major driver of state-of-the-art LLM performance, but each additional token adds latency and compute (and attention cost grows quadratically with context). The open question the authors address is: how does the number of required reasoning tokens scale with input size for a given task? Existing work on compressing reasoning chains reports only constant-factor reductions (e.g., "30% shorter") on benchmarks where input size is not a natural scaling parameter, so it is unclear whether required reasoning length stays roughly constant, grows linearly, or grows faster. This paper supplies principled asymptotic bounds for three problems that are known to be hard for LLMs without reasoning, and tests whether frontier models behave as predicted.

Key Contributions

1. A formal definition of BAPO token complexity — the worst-case minimum number of CoT tokens a constant-bandwidth BAPO-CoT needs to solve all size-n instances of a problem (a nonuniform notion, allowing a different optimal BAPO per input length).
2. Linear lower bounds for three BAPO-hard problems. Extending the BAPO-hardness proof technique of Schnabel et al. (2025), the authors prove that Majority and Match3_n each require Ω(n) CoT tokens, and Reachability requires Ω(m) CoT tokens for m-edge graphs, under any constant-bandwidth BAPO-CoT.
3. Matching or near-matching upper bounds via explicit constructions. An O(n) cBAPO-CoT for Match3_n (tight), an O(n²) cBAPO-CoT for Reachability (tight for dense graphs with m = Θ(n²)), and an O(n log n) cBAPO-CoT for Majority (leaving a gap to the Ω(n) lower bound).
4. The introduction of the self-consistent BAPO (cBAPO) model, which restricts the prefix oracle to be computable by a BAPO itself, closing an "input-doubling loophole" that otherwise lets a (1,1)-BAPO-CoT solve any decision problem in n+1 tokens.
5. Empirical confirmation on frontier models. GPT-5.2 and Gemini 2.5 Pro show approximately linear reasoning-token scaling on the three tasks, and degraded accuracy when reasoning is disabled or budgeted too tightly.

Main Findings

• Majority requires Ω(n) CoT tokens (Theorem 4.1). Any constant-bandwidth BAPO-CoT solving binary majority on length-n inputs uses at least linearly many reasoning tokens.
• Match3_n requires Ω(n) CoT tokens (Theorem 4.2). The same linear lower bound holds for triplet matching over ℤ_{n²}^n.
• Reachability requires Ω(m) CoT tokens (Theorem 4.3). For directed graphs with m edges, the lower bound scales with the number of edges, not just nodes.
• Majority has an O(n log n) cBAPO upper bound (Theorem 5.6). A (0,2)-cBAPO-CoT uses Θ(n log n) tokens via bit-by-bit counting, leaving a gap to the Ω(n) lower bound; the authors conjecture O(n log n) is tight for a binary alphabet, but note real LLM token alphabets are large enough that counts fit in a single token for reasonable instance sizes.
• Match3_n's lower bound is tight (Theorem 5.7). A (0,2)-cBAPO-CoT using O(n) tokens reduces Match3_n to a sequence of Match2_n instances, each cBAPO-easy.
• Reachability's upper bound is O(n²) (Theorem 5.8). A (0,3)-cBAPO-CoT performs a graph search, tracking the frontier and visited nodes; this matches the Ω(m) lower bound when m = Θ(n²).
• A general Turing-machine simulation gives cBAPO upper bounds (Theorem 5.5). Any language decided by a multi-tape, multi-head Turing machine with time t(n) and auxiliary space s(n) has token complexity O(t(n) · max(n, s(n))), using a (0, 2+τη)-cBAPO-CoT. This improves the O(n³) bound implied by a single-head construction for Majority to O(n²), later tightened to O(n log n).
• BAPO-hardness does not imply linear token complexity. κ(n)-PointerChasing is BAPO-hard for κ(n) = ω(1), yet has token complexity O(κ(n)) via a (0,1)-cBAPO-CoT (Theorem 5.10). Choosing κ(n) = log n or √n yields sublinear token complexity — the first example in the paper of a BAPO-hard problem with sublinear token complexity.
• The input-doubling loophole (Proposition 5.3). For any language L, the problem p_L(x|x) = 1[x ∈ L] is solved by a (1,0)-BAPO. Consequently, a (1,1)-BAPO-CoT solves any decision problem on inputs up to size n in at most n+1 tokens (Proposition 5.4), which is why the restricted cBAPO model is needed for meaningful upper bounds.
• Constant-bandwidth BAPOs/cBAPOs cannot in general be simulated by Turing machines (Proposition 4.4). The proof encodes an undecidable problem (whether the final token is a Turing machine that halts on all inputs) as a (0,0)-cBAPO. The paper notes this impossibility still holds for BAPOs with finite Σ, while the question for cBAPOs with finite Σ is open.
• Turing-machine lower bounds are generally weak. Since a transformer forward pass takes O(n²) time, algorithmic lower bounds translate to CoT lower bounds only as Ω(t(n)/n²), which the authors call effectively useless for problems in P.
• Native reasoning token counts scale approximately linearly for GPT-5.2. On Majority, Match3_n, and Reachability, GPT-5.2 at all reasoning efforts achieves near-perfect accuracy, with reasoning token counts scaling linearly with problem size — consistent with the theoretical lower bounds.
• Gemini 2.5 Pro uses many more tokens. It uses 8000–9000 tokens at n = 101 for Match3_n and Majority, and its Majority accuracy degrades to approximately 0.75 at larger n.
• Constrained reasoning budgets cause failures. With reasoning disabled or at minimum budget, accuracy rapidly degrades to random guessing. With external CoT and word limits of 50 or 100 words, the accuracy gap is only partially closed, indicating those budgets fall below the problem's token complexity; a 200-word limit appears long enough for near-perfect accuracy at n = 101, revealing inefficiency in the models' internal reasoning.
• BAPO-easy problems behave differently. On BAPO-easy tasks (including Max and Equality), token usage is far lower and often plateaus with high accuracy, and models can achieve near-perfect accuracy without reasoning.
• Models do not always execute BAPO-easy decompositions. Even when instructed, GPT-5.2 often refuses to count 1s step by step for Majority, or jumps to an incorrect count in a single step. For Match3_n, a plain "think step by step" prompt often elicits the same linear algorithm used in the paper's construction, and for Reachability it elicits a graph search.
• Practical implication of linear lower bounds. Because attention cost grows quadratically, linear lower bounds on required reasoning length translate into at least quadratic compute in practice as context grows.

Methodology in Plain English

The authors work within the BAPO model, which treats an LLM's single next-token prediction as a communication-limited computation. An arbitrary split divides the input into a prefix and a suffix; information from the prefix can cross the split only through a small a-bit summary (the prefix oracle, which must be computed without seeing the suffix) and at most b attended tokens whose selection may depend on the suffix. A problem is "BAPO-easy" if constants a and b suffice; otherwise it is "BAPO-hard."

Chain of thought is modeled by chaining these steps: each reasoning token is one BAPO computation over an ever-growing context.

• For lower bounds, the authors adapt the standard BAPO-hardness technique, which builds collections of prefixes and suffixes that fool any supposed low-bandwidth solver: the prefixes share strategically placed "masking tokens" so the model always attends to them, the collection of prefixes is larger than 2^a so the pigeonhole principle forces two prefixes to produce the same oracle output, and for any such pair a suffix exists that flips the answer. The authors extend this so that the two instances look identical to the BAPO-CoT at every reasoning step, forcing identical reasoning sequences and hence identical (and wrong) answers on one of them.
• For upper bounds, they introduce the self-consistent BAPO (cBAPO), which requires the prefix oracle itself to be computable by a BAPO — mirroring how causally masked transformers build prefix representations. They show all previously known BAPO-easy and BAPO-hard problems retain their status under this restriction, then either simulate multi-tape/multi-head Turing machines or hand-construct explicit cBAPO-CoT algorithms.
• For experiments, they generate 250 positive and 250 negative instances per problem and size, testing sizes n = 5, 11, 25, 51, 75, 101 (for Reachability, m ≤ 3n edges so input length stays linear in node count). They test GPT-5.2, whose reasoning_effort can be set to none, low, medium, or high, and Gemini 2.5 Pro, whose thinking_budget ranges over 128–32768 tokens. Both APIs expose internal reasoning token counts. Claude models could not be tested because they do not expose reasoning token counts, offer no option to disable internal reasoning, and enforce a minimum of 1024 for the thinking_budget parameter. Gemini 3 Pro was not tested because the authors' access tier is limited to 250 requests per day. They also test externalized CoT with three prompts: plain "think step by step," a word budget, and explicit instructions to follow the algorithms from their upper-bound constructions. Code is available at https://github.com/microsoft/bapo-cot.

Why This Matters

• For research: The paper supplies the first token-complexity lower bounds under BAPO for these three BAPO-hard problems, confirming the token complexity hypothesis of Lee et al. (2025) — that every problem has an inherent minimal reasoning chain length. It also shows that BAPO-hardness alone does not imply linear token complexity (via PointerChasing), and it aligns with reasoning-length bounds for unique hard-attention transformers (Bavandpour et al., 2025). Unlike prior work such as Li et al. (2024), which shows O(log n) CoT steps add no expressivity beyond AC⁰/TC⁰, these bounds are per-problem and asymptotic in input size rather than a single coarse threshold.
• Industry relevance: Inference-time scaling is a core cost driver for deployed reasoning models. The results imply that for tasks resembling majority, matching, or reachability, no clever prompting strategy can avoid reasoning cost that grows at least linearly with input size — and at least quadratic in wall-clock compute, given attention's quadratic cost. At the same time, frontier models use substantially more tokens than the linear lower bounds require, indicating room for constant-factor efficiency gains even where sublinear scaling is information-theoretically impossible under BAPO bandwidth limits.

Real-world applications implied by these findings:

• Reasoning-budget allocation for long-context agents: knowing a task has a linear token floor means budgets set below that floor will produce unreliable answers, as the paper's 50- and 100-word experiments show.
• Cost and latency forecasting for inference-time scaling: linear token growth combined with quadratic attention translates into predictable superlinear serving costs as inputs grow.
• Benchmark design: the paper argues that reported compression percentages are misleading when input size is not a scaling parameter, motivating benchmarks that scale instance size and measure token complexity.
• Architecture and tooling decisions: the results motivate exploring new architectures or more effective tool use, since prompt-level compression cannot beat the lower bound for these task families.

Future Directions

• Closing the Majority gap. The paper proves Ω(n) but only O(n log n) for Majority over a binary alphabet, and conjectures that O(n log n) is tight. Whether the factor of log n can be removed is left open.
• The finite-alphabet cBAPO question. Proposition 4.4 shows BAPOs/cBAPOs cannot generally be simulated by Turing machines; the authors note the impossibility still holds for BAPOs with finite Σ, but state that the corresponding question for cBAPOs with finite Σ is open.
• The general BAPO upper bound for arbitrary languages is listed as open in the results table, in contrast to the n+1 bound for cBAPO.
• Characterizing when models actually decompose problems. The paper identifies as an important question: for which problems do models effectively perform BAPO-easy decompositions when reasoning? It suggests that explicitly guiding decomposition, or training models to perform BAPO-easy decompositions, could help on problems with less obvious decompositions or more tempting shortcuts.
• Separating unavoidable cost from inefficiency. Since frontier models often use more tokens than the linear lower bounds require, an open practical direction is identifying and capturing the available constant-factor efficiency gains.

Target Audience

This paper is best suited to:

• Theoretical computer scientists and complexity researchers working on transformer expressivity, circuit complexity, and lower-bound techniques.
• Machine learning researchers studying inference-time scaling and chain-of-thought, especially those interested in reasoning-length compression and when compression is possible in principle.
• LLM systems and infrastructure engineers who need to reason about reasoning-token cost and latency budgets in production.
• Benchmark designers and evaluation researchers who want task suites where input size is a genuine scaling parameter.
• Graduate students with a background in algorithms and complexity who want an entry point into formal analysis of chain-of-thought.

Beginners will find the proof machinery and the BAPO formalism demanding, though the empirical figures and the plain-language intuitions about token scaling are accessible.

Authors’ 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.