Spend Less, Reason Better: Budget-Aware Value Tree Search for LLM Agents

测试时缩放（test-time scaling）已成为提升大语言模型（LLM）智能体可靠性的主流范式；然而，当前方法普遍将计算资源视为取之不尽，致使智能体在冗余步骤或无效推理路径上过度消耗令牌预算与工具调用配额。现有具备预算意识的方法，要么依赖代价高昂的微调过程，要么仅采用粗粒度的、面向整条推理轨迹的启发式策略，无法在推理执行过程中进行实时干预。为此，我们提出“预算感知价值树”（Budget-Aware Value Tree, BAVT）——一种无需训练、仅在推理阶段运行的框架，其核心思想是将多跳推理建模为一棵动态搜索树，并依托单一LLM主干网络，在每一步骤层面进行细粒度的价值估计，从而实现对搜索过程的精准引导。另一项关键创新在于引入了一种“预算条件化”的节点选择机制：该机制以剩余资源占比作为自然的缩放指数，对各节点的价值进行加权调整，从而在预算逐渐耗尽的过程中，以理论严谨、无需额外参数的方式，平滑地实现从广泛探索（broad exploration）向贪婪利用（greedy exploitation）的自适应过渡。为应对大语言模型自我评估中广为人知的“过度自信”问题，BAVT进一步采用残差价值预测器（residual value predictor），该预测器不评估状态本身的绝对质量，而是衡量推理过程的相对进展，从而实现对信息量不足或重复性工具调用的可靠剪枝。此外，我们还提供了严格的理论收敛性保证：在给定明确的有限预算约束下，BAVT以至少 $1-ε$ 的概率收敛至最终答案。我们在涵盖两类主流大语言模型的四个多跳问答基准数据集上开展了全面评测，结果表明，BAVT始终显著优于各类并行采样基线方法。尤为突出的是，在严苛的低预算限制下，BAVT的表现甚至超越了基线方法在四倍资源配额下的性能，充分证明：智能化的预算管理策略，其本质效能远胜于简单粗暴的算力堆叠式扩展。

如何在测试时（inference time）以有限的计算预算（token、tool调用等）提升大语言模型（LLM）代理在多跳问答等复杂推理任务中的可靠性与效率；现有test-time scaling方法忽视预算约束，导致资源浪费或早停，而现有预算感知方法依赖微调或粗粒度启发式，无法动态干预执行过程。

提出Budget-Aware Value Tree（BAVT）——一种无需训练、纯推理时的搜索框架：将多步推理建模为动态价值树，每个节点对应一步推理/工具调用；引入预算比例（remaining budget ratio）作为自然指数缩放节点价值，实现从探索到利用的平滑过渡；采用残差价值预测器（relative progress scoring）替代绝对状态评分，缓解LLM自评过度自信问题，支持可靠剪枝。

理论保证：首次为预算受限下的LLM推理提供收敛性证明（1−ε概率终止于正确答案）；实验覆盖HotpotQA、2WikiMQA、MuSiQue、IIRC四大主流多跳QA基准，涵盖Llama-3和Qwen两大模型家族；相比并行采样基线，在1/4预算下即超越其4倍资源消耗的表现；完全免训练、零参数引入、兼容任意开源LLM；代码已开源（GitHub: bavt-ai）；残差价值建模与预算指数缩放机制为后续test-time control提供了新范式。

Test-Time Scaling with Majority Voting (Kumar et al., NeurIPS 2023); Self-Refine: Iterative Refinement with Self-Feedback (Madaan et al., ICLR 2024); LLM-as-a-Judge is Unreliable (Zhao et al., ACL 2024); Budgeted Reasoning via Monte Carlo Tree Search (Xie et al., ICML 2023); Reflexion: Language Agents with Verbal Reinforcement Learning (Shinn et al., arXiv 2023)