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

• URL: http://arxiv.org/abs/2602.02909v1
• Date: Mon, 02 Feb 2026 23:33:34 GMT
• Title: Reasoning about Reasoning: BAPO Bounds on Chain-of-Thought Token Complexity in LLMs
• Authors: Kiran Tomlinson, Tobias Schnabel, Adith Swaminathan, Jennifer Neville,
• Abstract summary: In-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.<n>We address a fundamental theoretical question: how many reasoning tokens are required to solve a problem as input size grows?<n>We prove lower bounds on the CoT tokens required for three canonical BAPO-hard tasks: binary majority, triplet matching, and graph reachability.
• Score: 16.81068280262534
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• CoLT: Reasoning with Chain of Latent Tool Calls [31.228763375347608]
  Chain-of-Thought (CoT) is a critical technique in enhancing the reasoning ability of Large Language Models (LLMs)<n>We propose CoLT, a novel framework that implements latent reasoning as tool calls''
  arXiv  Detail & Related papers  (2026-02-04T06:12:53Z)
• Chain Of Thought Compression: A Theoritical Analysis [24.613200477865572]
  Chain-of-Thought (CoT) has unlocked advanced reasoning abilities of Large Language Models.<n>CoT incurs prohibitive computational costs due to generation of extra tokens.<n>Recent studies show that compressing reasoning steps into latent states, or implicit CoT compression, offers a token-efficient alternative.
  arXiv  Detail & Related papers  (2026-01-29T11:42:03Z)
• FrugalPrompt: Reducing Contextual Overhead in Large Language Models via Token Attribution [3.4666771782038652]
  Large language models (LLMs) owe much of their stellar performance to expansive input contexts, yet such verbosity inflates monetary costs, carbon footprint, and inference-time latency.<n>We introduce FrugalPrompt, a novel prompt compression framework for LLMs, which retains only the most semantically significant tokens.<n>We evaluate the approach across four NLP tasks: Sentiment Analysis, Commonsense QA, Summarization, and Mathematical Reasoning.
  arXiv  Detail & Related papers  (2025-10-18T10:22:13Z)
• Rethinking Thinking Tokens: LLMs as Improvement Operators [80.12087211785949]
  Reasoning training incentivizes LLMs to produce long chains of thought (long CoT), which allows them to explore solution strategies with self-checking.<n>This results in higher accuracy, but inflates context length, token/compute cost, and answer latency.<n>We ask: Can current models leverage their metacognition to provide other combinations on this Pareto frontier?<n>We identify an interesting inference family Parallel-Distill-Refine (PDR), which performs the following: (i) generate diverse drafts in parallel; (ii) distill them into a bounded, textual workspace; and (iii) refine conditioned on this workspace
  arXiv  Detail & Related papers  (2025-10-01T17:08:59Z)
• Truth in the Few: High-Value Data Selection for Efficient Multi-Modal Reasoning [71.3533541927459]
  We propose a novel data selection paradigm termed Activation Reasoning Potential (RAP)<n>RAP identifies cognitive samples by estimating each sample's potential to stimulate genuine multi-modal reasoning.<n>Our RAP method consistently achieves superior performance using only 9.3% of the training data, while reducing computational costs by over 43%.
  arXiv  Detail & Related papers  (2025-06-05T08:40:24Z)
• PixelThink: Towards Efficient Chain-of-Pixel Reasoning [70.32510083790069]
  PixelThink is a simple yet effective scheme that integrates externally estimated task difficulty and internally measured model uncertainty.<n>It learns to compress reasoning length in accordance with scene complexity and predictive confidence.<n> Experimental results demonstrate that the proposed approach improves both reasoning efficiency and overall segmentation performance.
  arXiv  Detail & Related papers  (2025-05-29T17:55:49Z)
• Fractured Chain-of-Thought Reasoning [61.647243580650446]
  We introduce Fractured Sampling, a unified inference-time strategy that interpolates between full CoT and solution-only sampling.<n>We show that Fractured Sampling consistently achieves superior accuracy-cost trade-offs, yielding steep log-linear scaling gains in Pass@k versus token budget.
  arXiv  Detail & Related papers  (2025-05-19T11:30:41Z)
• Critical Thinking: Which Kinds of Complexity Govern Optimal Reasoning Length? [72.70486097967124]
  We formalize a framework using deterministic finite automata (DFAs)<n>We show that there exists an optimal amount of reasoning tokens such that the probability of producing a correct solution is maximized.<n>We then demonstrate an implication of these findings: being able to predict the optimal number of reasoning tokens for new problems and filtering out non-optimal length answers results in consistent accuracy improvements.
  arXiv  Detail & Related papers  (2025-04-02T17:45:58Z)
• Sketch-of-Thought: Efficient LLM Reasoning with Adaptive Cognitive-Inspired Sketching [64.74765550805024]
  Chain-of-Thought prompting elicits step-by-step problem solving, but often at the cost of excessive verbosity in intermediate outputs.<n>We propose Sketch-of-Thought (SoT), a prompting framework that integrates cognitively inspired reasoning paradigms with linguistic constraints.<n>SoT achieves token reductions of up to 84% with minimal accuracy loss across 18 reasoning datasets.
  arXiv  Detail & Related papers  (2025-03-07T06:57:17Z)
• How Well do LLMs Compress Their Own Chain-of-Thought? A Token Complexity Approach [4.055489363682199]
  We conduct the first systematic study of the relationship between reasoning length and model performance.<n>We show that this tradeoff persists across even very distinct reasoning chains.<n>We show that prompt-based compression strategies operate far from theoretical limits.
  arXiv  Detail & Related papers  (2025-03-03T03:48:20Z)
• When More is Less: Understanding Chain-of-Thought Length in LLMs [51.631483479081645]
  Large Language Models (LLMs) employ Chain-of-Thought (CoT) reasoning to deconstruct complex problems.<n>This paper argues that longer CoTs are often presumed superior, arguing that longer is not always better.
  arXiv  Detail & Related papers  (2025-02-11T05:28:59Z)
• FLARE: Faithful Logic-Aided Reasoning and Exploration [47.46564769245296]
  We introduce a novel approach for traversing the problem space using task decompositions.<n>We use the Large Language Models to plan a solution, soft-formalise the query into facts and predicates using a logic programming code.<n>Our method allows us to compute the faithfulness of the reasoning process w.r.t. the generated code and analyse the steps of the multi-hop search without relying on external solvers.
  arXiv  Detail & Related papers  (2024-10-14T19:39:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.