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

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.

Modern AI chatbots like ChatGPT have gotten much better at hard problems by "thinking out loud" before answering. But this thinking isn't free--every extra word the model generates costs time and computing power. That raises an important question: as problems get bigger, how much thinking does a large language model like GPT-5 need to do? In this paper, we give a mathematical answer for three representative problems, such as checking whether one point connects to another in a network (e.g., “can I get from Seattle to Austin by bus?”). For this problem, we prove that the amount of thinking required scales with the size of the network; there is no clever shortcut to looking at a bunch of bus routes and seeing how they might be chained together. Similarly, we show that other problems also require step-by-step reasoning chains that are at least as long as the input to the problem. To check that this theory matches reality, we ran frontier reasoning models (GPT-5.2 and Gemini 2.5 Pro) on these problems. Their reasoning length grew with input size, just as our theory predicts, and forcing them to think less caused mistakes. The takeaway is that for some genuinely hard tasks, long, expensive chains of thought are likely unavoidable. This points to a real need for new architectures or external tools rather than ever-longer reasoning. But our experiments also show that today's models often use far more tokens than strictly necessary, so there is still meaningful room to make reasoning more efficient, even if dramatic shortcuts are impossible.