沙丘社区
论文

对推理的推理：LLM 中思维链 token 复杂度的 BAPO 界

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

Kiran Tomlinson, Tobias Schnabel, Adith Swaminathan, Jennifer Neville
模型推理测试时计算扩展

摘要

经由思维链（CoT）推理进行推理时扩展是当前最先进 LLM 性能的主要驱动力，但伴随可观的延迟与计算成本。我们讨论一个基础理论问题：随着输入规模增长，求解一个问题需要多少推理 token？通过扩展有界注意力前缀预言机（BAPO）模型——一个量化求解任务所需信息流的 LLM 抽象——我们对三个经典 BAPO 难任务所需的 CoT token 证明下界：二值多数、三元组匹配与图可达性。我们证明当输入规模为 n 时，每个任务都需要 Ω(n) 个推理 token。我们通过显式构造给出匹配或近匹配的上界作为补充。最后，我们在前沿推理模型上的实验显示，这些任务上的推理 token 近似线性扩展，且在受限更小推理预算时出现失败，与我们的理论下界一致。综上，我们的结果识别了经由 CoT 的推理时计算的基本瓶颈，并为分析最优推理长度提供了有原则的工具。

对推理的推理：LLM 中思维链 token 复杂度的 BAPO 界
图3：GPT-5.2 在不同 CoT 提示方法下的性能（均设置 reasoning_effort = none 以禁用内部推理）。在固定字数限制下，性能随输入长度增加而下降。朴素 CoT 与算法式 CoT 两种方法均能使性能保持较高水平，但代价是近似线性的 token 开销。CoT 在 Majority 任务上表现不佳是由于模型拒绝进行逐步计数（见 C.4 节）。