Uncertainty-Aware Budget Allocation for Efficient LLM Tree Search
作者: Jianguo Huang, Zhiyi Lyu, Fuxiang Zhang, Yanchen Deng, Deheng Ye, Bo An
分类: cs.CL, cs.AI
发布日期: 2026-10-16
💡 一句话要点
提出不确定性感知预算分配以提升LLM树搜索效率
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 大语言模型 树搜索 不确定性感知 预算分配 多步推理 语义分散性 效率提升
📋 核心要点
- 现有树搜索方法在每一步扩展时使用固定预算，未考虑扩展的边际效用，导致效率低下。
- 论文提出不确定性感知分配（UAA），通过分析兄弟动作的语义分散性来动态调整预算，提高扩展效率。
- UAA在多个基准测试中表现出色，减少了90%的标记使用和9倍的延迟，同时保持了相似的准确性。
📝 摘要（中文）
树搜索增强了大语言模型（LLMs）的多步推理能力，但现有方法在每一步扩展时使用固定预算，忽视了扩展的边际效用。本文首先展示了现有搜索算法中，从共享中间状态采样的后续结果大多是重复的，并且收敛到少数不同的答案。我们发现，兄弟动作的语义分散性可以预测其后续扩展的冗余性，从而允许在扩展前固定子树的预算。基于信息论的分析表明，将每步预算视为估计步骤剩余答案熵的蒙特卡洛样本大小，我们推导出一个随着兄弟分散性缩小的足够预算。我们提出了不确定性感知分配（UAA），这是一个无训练框架，解耦了价值与不确定性：价值决定哪些候选者有前景，而不确定性则通过不确定性感知修剪和预算决定扩展的数量。UAA在数学推理、逻辑推理和规划基准上，减少了多达90%的标记使用和9倍的延迟，同时保持相似的准确性，适用于四种树搜索算法和开放及闭源的LLMs。
🔬 方法详解
问题定义：本文旨在解决现有树搜索方法在每一步使用固定预算的问题，这种方法未能考虑扩展的边际效用，导致资源浪费和效率低下。
核心思路：论文的核心思路是通过分析兄弟动作的语义分散性来预测后续扩展的冗余性，从而动态调整预算。这种设计使得在扩展前可以合理分配资源，提高搜索效率。
技术框架：整体架构包括不确定性感知修剪和预算分配两个主要模块。首先，通过分析兄弟动作的语义分散性来估计不确定性，然后根据不确定性动态调整扩展的预算。
关键创新：最重要的技术创新点在于将价值与不确定性解耦，利用兄弟分散性来优化预算分配。这与现有方法的本质区别在于，现有方法未能考虑扩展的冗余性。
关键设计：关键设计包括如何计算兄弟动作的语义分散性，以及如何将其转化为预算分配的依据。此外，论文中还探讨了不确定性感知修剪的具体实现方式，以确保在扩展时选择最有潜力的候选者。
🖼️ 关键图片
📊 实验亮点
实验结果表明，UAA在数学推理、逻辑推理和规划基准上，标记使用减少了高达90%，延迟降低了9倍，同时保持了与基线相似的准确性。这些结果展示了UAA在多种树搜索算法中的广泛适用性。
🎯 应用场景
该研究的潜在应用领域包括智能问答系统、自动推理和决策支持系统等。通过优化树搜索的效率，UAA可以显著提升大语言模型在复杂任务中的表现，具有广泛的实际价值和未来影响。
📄 摘要（原文）
Tree search enhances multi-step reasoning in large language models (LLMs), yet prevailing methods expand every step with a fixed budget, irrespective of the marginal utility of expansion. We first show, across existing search algorithms, that continuations sampled from a shared intermediate state are largely duplicates and collapse to a few distinct answers. Critically, we find that the semantic dispersion of sibling actions predicts the redundancy of their downstream continuations, permitting a subtree's budget to be fixed before expansion. An information-theoretic analysis motivates this: treating the per-step budget as the Monte Carlo sample size for estimating a step's residual answer entropy, we derive a sufficient budget that shrinks with sibling dispersion. We accordingly propose $\textbf{Uncertainty-Aware Allocation}$ (UAA), a training-free framework that decouples value from uncertainty: values determine which candidates are promising, while uncertainty, estimated from sibling dispersion at no additional model cost, determines how many merit expansion, via uncertainty-aware pruning and uncertainty-aware budgeting. Across mathematical reasoning, logical reasoning, and planning benchmarks, UAA reduces token usage by up to $90\%$ and latency by up to $9\times$ at comparable accuracy, generalizing across four tree search algorithms and both open- and closed-source LLMs.