Plan and Budget: Effective and Efficient Test-Time Scaling on Large Language Model Reasoning

本文提出 PLAN-AND-BUDGET 框架，通过结构化推理和基于不确定性的自适应 token 预算分配，显著提升大型语言模型在推理任务中的计算效率，E3 指标最高提升 187.5%，同时保持准确率。

Large Language Model, Reasoning, Efficiency, Test Time, Planning

Junhong Lin, Xinyue Zeng, Jie Zhu, Song Wang, Julian Shun, Jun Wu, Dawei Zhou

MIT CSAIL, Virginia Tech, Michigan State University, University of Virginia

Generated by grok-3

Background Problem

大型语言模型（LLMs）在复杂推理任务中表现出色，但其推理过程常常存在计算效率低下的问题，表现为‘过思考’（对简单问题生成冗长推理）和‘欠思考’（对复杂问题推理不足）。这一问题在需要严格计算和时间限制的现实场景中尤为突出，特别是在教育、金融、法律和科学研究等高风险领域。论文通过实证研究揭示了‘推理失调’（Reasoning Miscalibration）现象，并提出核心问题：如何根据任务复杂性自适应地分配计算资源，以提高推理效率并减少资源浪费。

Method

论文提出了 PLAN-AND-BUDGET 框架，这是一种模型无关的测试时方法，旨在通过结构化推理和自适应预算分配提高 LLMs 的推理效率。其核心思想和步骤如下：

理论基础：贝叶斯预算分配模型（BBAM）：将推理过程建模为一系列具有不同不确定性的子问题，通过贝叶斯决策理论优化 token 分配，优先为具有较高认知不确定性（epistemic uncertainty）的子问题分配更多计算资源。理论上通过拉格朗日优化推导出最优分配规则，但参数估计（如子问题复杂度和不确定性）在实践中难以精确实现。
实现框架：PLAN-AND-BUDGET：分为两个阶段：
- Plan 阶段：通过轻量级 LLM 将复杂查询分解为一系列子问题，并估计每个子问题的复杂性，形成推理的‘软脚手架’（soft scaffold），以减少推测性探索。
- Budget 阶段：基于子问题复杂性和位置，采用衰减调度策略（如线性、指数、多项式、余弦退火）动态分配 token 预算，优先为早期高不确定性步骤分配更多资源。
关键创新：引入 E3 指标（Efficiency-Aware Effectiveness Evaluation Score），通过 $E^3 = \frac{A^2}{T}$ （A 为准确率，T 为平均 token 数）平衡推理质量和计算成本。
批判性思考：虽然 BBAM 提供了理论支持，但其依赖的参数（如不确定性分解和复杂性估计）在实际操作中可能过于主观或不准确，导致分配策略偏离最优。此外，衰减调度作为一种启发式方法，虽然简单易用，但可能无法完全捕捉推理过程中的动态不确定性变化，特别是在任务结构复杂或子问题依赖性强的情况下。

Experiment

论文在三个代表性推理任务上进行了广泛实验：数学推理（MATH-500）、指令跟随（NaturalInstructions）和代理规划（TravelPlanner），使用四个先进的 LLMs（DS-Qwen-32B、QwQ-32B、DS-LLaMA-70B、o4-mini）。

实验设置：对比了多种基线方法（如无规划的 Vanilla、固定预算的 Global Budget）以及 PLAN-AND-BUDGET 的不同调度策略（均匀、加权、线性、指数、多项式、余弦退火）。评估指标包括任务准确率、平均 token 使用量和 E3 指标。
结果分析：PLAN-AND-BUDGET 在所有任务和模型上均表现出显著的效率提升，E3 指标最高提升 187.5%（DS-Qwen-32B 在 TravelPlanner 上），token 使用量减少高达 39%，准确率保持相当甚至有所提高。特别是在复杂任务（如 TravelPlanner）中，自适应预算分配的效果尤为明显。此外，小模型（DS-Qwen-32B）通过该方法在效率上接近大模型（DS-LLaMA-70B），显示出推理时优化的潜力。
批判性思考：实验结果令人印象深刻，但存在一些潜在问题：1）数据集选择可能偏向于结构化任务，未充分测试非结构化或高度开放性任务；2）E3 指标虽然创新，但其对准确率的平方加权可能过度惩罚 token 使用量，导致对计算成本敏感的任务结果被低估；3）不同调度策略的效果差异未深入分析其原因，可能存在任务特异性或超参数调优的影响；4）实验未探讨方法在极低预算或极高复杂性任务下的表现，可能存在适用范围限制。总体而言，实验设置较为全面，但需进一步验证泛化性和鲁棒性。

Further Thoughts

PLAN-AND-BUDGET 提供了一种有前景的测试时优化策略，但其依赖额外 LLM 调用进行规划可能在实际部署中增加延迟和成本，未来是否能通过单一模型内化这一过程值得探索。此外，该方法的不确定性估计和预算分配策略可能与任务类型高度相关，例如在高度创造性或非结构化任务中，早期步骤未必是高不确定性的关键点，这提示我们需要更动态的自适应机制。另一个有趣的方向是结合该方法与参数高效微调（如 Low-Rank Adaptation），以进一步提升小模型在复杂推理任务中的竞争力，特别是在资源受限的边缘设备上。最后，E3 指标的提出是一个亮点，但其设计是否适用于所有任务类型仍需更多跨领域验证，例如在生成任务中，token 数量与质量的关系可能更为复杂，需探索更灵活的评估框架。