Research map / Large language models / Reasoning and chain of thought

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

ICML 2026 · Large language models › Reasoning and chain of thought · approach: Long CoT dynamics and efficiency · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proves Omega(n) chain-of-thought token lower bounds for BAPO-hard tasks (majority, triplet matching, graph reachability) under constant-bandwidth BAPO-CoT, gives matching upper bounds via cBAPO constructions, and shows GPT-5.2 and Gemini 2.5 Pro use roughly linear reasoning tokens on these tasks.

Problem

How many chain-of-thought tokens are needed for LLMs to solve communication-hard problems as input size grows, i.e., the asymptotic token complexity of reasoning.

Approach

Extends the BAPO hardness technique to CoT by requiring the fooling inputs to produce identical information at every CoT step, yielding linear lower bounds; introduces self-consistent BAPO (cBAPO) to rule out an input-doubling loophole so that matching upper bounds via Turing-machine simulation and direct constructions are meaningful.

Key results

• Theory: Majority, Match3_n and Reachability require Omega(n), Omega(n), Omega(m) CoT tokens under constant-bandwidth BAPO-CoT, with upper bounds O(n log n), O(n), O(n^2) for cBAPO-CoT.
• GPT-5.2 with reasoning achieves near-perfect accuracy on all three tasks with reasoning token counts scaling approximately linearly in n; with reasoning disabled accuracy falls to chance.
• Gemini 2.5 Pro uses 8000-9000 reasoning tokens at n=101 on Match3 and Majority, and its Majority accuracy degrades to about 0.75 at larger n.

Surprising findings

• GPT-5.2 often refuses or jumps to incorrect counts when asked to count ones step by step externally on Majority.
• With 200-word CoT budgets GPT-5.2 reaches near-perfect accuracy at n=101 on Match3 and Reachability, suggesting internal reasoning is inefficient relative to the linear lower bound.

Limitations

• Model abstraction does not capture tool use, retrieval or other system features.
• Experiments limited to three synthetic tasks and access constraints (Claude excluded, Gemini 3 Pro not tested).
• Open questions remain, e.g. whether Reachability needs Theta(n^2) or O(m+n) tokens and finite-alphabet simulation questions.

Experimental setup

Datasets: synthetic majority, triplet matching (Match3), and graph reachability instances

Benchmarks: Majority Match3 Reachability

Metrics: accuracy reasoning token count

Baselines: GPT-5.2 no reasoning Gemini 2.5 Pro

Builds on: bounded attention prefix oracle chain-of-thought unique hard attention transformer bounds

Closest papers by meaning

• Lost in Transmission: When and Why LLMs Fail to Reason Globally (NeurIPS 2025 · similarity 0.92)
• Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought (NeurIPS 2025 · similarity 0.90)
• On the Token Value Inequality in Efficient Reasoning (NeurIPS 2026 · similarity 0.90)
• TERMINATOR: Learning Optimal Exit Points for Early Stopping in Chain-of-Thought Reasoning (NeurIPS 2026 · similarity 0.90)
• Towards Thinking-Optimal Scaling of Test-Time Compute for LLM Reasoning (NeurIPS 2025 · similarity 0.89)
• ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning (ICML 2025 · similarity 0.89)