揭示大模型推理所需思维步骤的理论下限，解释为何越复杂问题越耗算力。
Reasoning about Reasoning: BAPO Bounds on Chain-of-Thought Token Complexity in LLMs
- 用抽象模型推导出三种典型任务至少需线性增长的推理词数
- 实验证明前沿模型在相同任务上推理消耗与输入规模呈近似线性关系
- 为优化推理长度提供理论依据，适合研究大模型效率的学者参考
通过扩展有界注意力前缀预言机（BAPO）模型——一种量化任务求解信息流的LLM抽象——我们证明了在三个经典BAPO难题（二元多数、三元匹配、图可达性）中，当输入规模为n时，链式思维（CoT）推理所需令牌数均需Ω(n)。我们进一步通过显式构造给出了匹配或接近匹配的上界。实验显示，前沿推理模型在这些任务上的推理令牌消耗与输入规模近似线性增长，且在受限推理预算下会失败，与理论下界一致。结果揭示了基于推理的计算开销的根本瓶颈，并提供了分析最优推理长度的系统化工具。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。