Reasoning about Reasoning: BAPO Bounds on Chain-of-Thought Token Complexity in LLMs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917541576704000 |
|---|---|
| author | Tomlinson, Kiran Schnabel, Tobias Swaminathan, Adith Neville, Jennifer |
| author_facet | Tomlinson, Kiran Schnabel, Tobias Swaminathan, Adith Neville, Jennifer |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_02909 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Reasoning about Reasoning: BAPO Bounds on Chain-of-Thought Token Complexity in LLMs Tomlinson, Kiran Schnabel, Tobias Swaminathan, Adith Neville, Jennifer Artificial Intelligence Formal Languages and Automata Theory Machine Learning 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. |
| title | Reasoning about Reasoning: BAPO Bounds on Chain-of-Thought Token Complexity in LLMs |
| topic | Artificial Intelligence Formal Languages and Automata Theory Machine Learning |
| url | https://arxiv.org/abs/2602.02909 |