arXiv cs.CL· Jianguo Huang, Zhiyi Lyu, Fuxiang Zhang, Yanchen Deng, Deheng Ye, Bo An·· 12 小时前AI 评分38
UAA：面向高效 LLM 树搜索的不确定性感知预算分配框架
Uncertainty-Aware Budget Allocation for Efficient LLM Tree Search
AI 导读
研究者提出免训练的 UAA 框架，将价值与不确定性解耦：价值决定哪些候选值得扩展，由兄弟节点语义分散度估计的不确定性决定扩展多少，并通过不确定性感知剪枝与预算分配实现。在数学推理、逻辑推理和规划基准上，UAA 在精度相当的情况下最多减少 90% token 用量、延迟最多降低 9 倍，且可泛化到四种树搜索算法及开源与闭源 LLM。
正文 · 原文
Abstract: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.
| Subjects: | Computation and Language (cs.CL); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2610.22858 [cs.CL] |
| (or arXiv:2610.22858v1 [cs.CL] for this version) | |
| https://doi.org/10.48550/arXiv.2610.22858 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Jianguo Huang [view email]
[v1]
Fri, 16 Oct 2026 03:03:28 UTC (403 KB)
来源：arXiv cs.CL · arxiv.org