针对预算受限代理搜索的更充分利用与更智能探索

# 更精打细算，更智能探索：预算受限的智能体搜索
来源：https://arxiv.org/html/2608.23848

###### 摘要
预算受限的智能体搜索出现在大语言模型智能体必须在有限的评估预算下筛选候选项时，原因可能是验证成本高昂、生成过程需要多次模型调用，或两者兼有。在这种情况下，标准的蒙特卡洛树搜索（MCTS）对预算的分配效果不佳：在访问次数较低时探索奖励项占主导，有前景的分支链未能深入扩展前，无前途的兄弟节点就被扩展，且节点的扩展决策与质量无关。我们提出了**ExTS**，一种将“扩展”本身视为“信息价值”决策的树搜索策略。ExTS结合了三种机制：判别性奖励塑形，用于在狭窄的分数分布下区分候选项；随机虚拟子节点，利用父节点的奖励历史估算创建新分支的价值；以及质量条件扩展，仅在节点分数证明其消耗的预算成本合理时才进行扩展。在提示优化、代码生成、分子结构解析和智能体工作流优化等任务中，ExTS与特定任务的树搜索基线方法性能相当甚至更优，在单一固定配置下平均相对提升+5.5%。我们进一步引入了试点运行诊断方法，以表征预算受限智能体搜索问题在结构上的差异性，既提供了对问题空间的理解，也给出了实际的适配指导。

图1：标准UCT算法通过平坦奖励和强制扩展，将预算分配到广泛而浅层的树结构中。ExTS则使用虚拟子节点，将扩展决策视为一种信息价值判断，并基于塑形后的分数进行质量条件扩展。雷达图：归一化增益；ExTS*表示经过试点运行调整的配置。

## 1 引言
一类日益增长的AI系统依赖于*智能体搜索*：大语言模型（LLM）迭代地提出并优化候选项，在生成和验证两个环节都消耗预算。这些系统涵盖提示优化（Agrawal等人，2025 (https://arxiv.org/html/2608.23848#bib.bib8); Opsahl-Ong等人，2024 (https://arxiv.org/html/2608.23848#bib.bib9)）、代码生成（Zhang等人，2023 (https://arxiv.org/html/2608.23848#bib.bib22); Inoue等人，2026 (https://arxiv.org/html/2608.23848#bib.bib17)）、工具增强推理（Yao等人，2022 (https://arxiv.org/html/2608.23848#bib.bib20); Schick等人，2023 (https://arxiv.org/html/2608.23848#bib.bib21)）、多步规划（Yao等人，2023 (https://arxiv.org/html/2608.23848#bib.bib10); Besta等人，2024 (https://arxiv.org/html/2608.23848#bib.bib23)）等。尽管应用多样，它们都面临一个共同约束：搜索预算仅限数十至数百次调用。我们将这种场景称为*预算受限的智能体搜索*。

近期关于LLM搜索的研究主要集中在*框架*：即包裹搜索过程的框架，如价值函数、动作空间或多智能体评估（Shinn等人，2023 (https://arxiv.org/html/2608.23848#bib.bib11); Madaan等人，2023 (https://arxiv.org/html/2608.23848#bib.bib3); Zhou等人，2023 (https://arxiv.org/html/2608.23848#bib.bib12); Qi等人，2024 (https://arxiv.org/html/2608.23848#bib.bib35); Antoniades等人，2025 (https://arxiv.org/html/2608.23848#bib.bib36); Zhang等人，2024 (https://arxiv.org/html/2608.23848#bib.bib33); Hao等人，2023 (https://arxiv.org/html/2608.23848#bib.bib37); Liu等人，2025 (https://arxiv.org/html/2608.23848#bib.bib1); Li等人，2025 (https://arxiv.org/html/2608.23848#bib.bib34); Fang等人，2026a (https://arxiv.org/html/2608.23848#bib.bib2)）。这些系统在选择和扩展环节仍采用线性搜索或标准UCT（附录A (https://arxiv.org/html/2608.23848#A1)），这为在树内部如何分配预算留下了巨大的改进空间。在搜索算法方面，AB-MCTS（Inoue等人，2026 (https://arxiv.org/html/2608.23848#bib.bib17)）用汤普森采样替代了UCT，GEPA（Agrawal等人，2025 (https://arxiv.org/html/2608.23848#bib.bib8)）使用帕累托前沿选择，AFlow（Zhang等人，2025 (https://arxiv.org/html/2608.23848#bib.bib31)）应用分数加权随机采样，但它们各自针对单一任务类型，且都未根据节点质量调整扩展决策，也未针对狭窄的分数分布进行奖励塑形。如何设计能够跨多种智能体问题迁移的选择和扩展策略，目前受到的关注有限。

我们提出**ExTS**¹，一种通过重新设计*节点选择方式*和*是否应当扩展*来实现“更精打细算，更智能探索”的树搜索策略。其核心洞见是，在预算紧张的情况下，“是否扩展”的决策与“访问哪个子节点”同样重要。标准MCTS在此场景下存在三个结构性缺陷：低访问次数时探索奖励项占主导、被迫扩展无前途的兄弟节点、以及扩展决策没有质量门槛。ExTS通过三种机制分别解决了这些问题：**判别性奖励塑形**（第3.1节 (https://arxiv.org/html/2608.23848#S3.SS1)）在原始分数分布狭窄时产生有效的选择信号；**虚拟子节点启发式方法**（第3.2节 (https://arxiv.org/html/2608.23848#S3.SS2)）通过从父节点的奖励历史中抽样来估算扩展的价值，使扩展成为一个与深入探索直接竞争的信息价值（VOI）决策；**质量条件扩展**（第3.3节 (https://arxiv.org/html/2608.23848#S3.SS3)）将扩展限制在分数足以证明其预算成本合理的节点上。这些机制的灵感来源于经典的MCTS思想（渐进式加宽（Coulom, 2007 (https://arxiv.org/html/2608.23848#bib.bib5)）、首次游玩紧迫性（Gelly和Wang, 2006 (https://arxiv.org/html/2608.23848#bib.bib29)）、PUCT（Rosin, 2011 (https://arxiv.org/html/2608.23848#bib.bib25)）），并针对预算受限的智能体搜索对其进行了改进（第5.3节 (https://arxiv.org/html/2608.23848#S5.SS3)）。在单一固定配置下，ExTS在提示优化（Yang等人，2018 (https://arxiv.org/html/2608.23848#bib.bib14); Jiang等人，2020 (https://arxiv.org/html/2608.23848#bib.bib15)）、代码生成（Jain等人，2024 (https://arxiv.org/html/2608.23848#bib.bib16)）、分子结构解析（Zhuang等人，2025 (https://arxiv.org/html/2608.23848#bib.bib4)）和智能体工作流优化（Dua等人，2019 (https://arxiv.org/html/2608.23848#bib.bib32)）任务上，性能与特定任务的方法相当或更优（在HotpotQA上+10.8%，LiveCodeBench困难集上+11.7%，K-MSE上+1.3%，DROP上+3.5%，HoVeR上+0.2%）。**ExTS***进一步通过试点运行诊断调整一个或两个超参数来提升性能。我们还报告了将问题结构特征与超参数敏感性、组件消融分析、预算缩放和树形分析相关联的诊断结果。

¹ 代码将在 https://github.com/amazon-science/ExTS 发布。在此之前，请联系我们。

## 2 预备知识
### 2.1 验证密集型搜索
我们将验证密集型搜索形式化为一个四元组 (S, A, f, B)，其中 S 是候选解集合（例如提示、代码或计划），A: S→S 是由LLM驱动的随机化精炼算子，f: S→R∪{⊥} 是返回分数或失败的验证函数，B 是总评估预算。搜索从初始候选解 x₀ 开始构建一棵树 T，目标是在预算 B 内最大化 max_{x∈T} f(x)。我们识别出四个*试点运行诊断指标*，用于刻画给定模型和评分器下验证密集型任务的搜索景观（形式化定义见附录C (https://arxiv.org/html/2608.23848#A3)）。除了指导超参数选择外，这些诊断指标还刻画了智能体搜索问题在结构上的差异维度，并有助于解释为何没有单一的搜索配置能普遍占优。这些诊断指标是通过使用*基线*搜索方法为每个数据集构建试点树，并测量任务原生算法所见的景观属性来计算的。

- *精炼方差* σ̂_A：使用相同输入进行独立精炼时 f 值的标准差（归一化），量化了LLM精炼算子的随机性。
- *归一化分数偏差* σ̂_f：在已完成的树中所有成功验证的候选解上 f 值的标准差，归一化到 [0,1] 区间。
- *分数漂移* κ：随着新候选解被发现，归一化分数边界发生变化所引起的归一化分数平均绝对偏移；高漂移表示搜索频繁发现分数范围极端的候选解。
- *失败率* ρ：精炼尝试中 f 返回 ⊥ 的比例。

表1 (https://arxiv.org/html/2608.23848#S2.T1) 在这些维度上刻画了我们研究的数据集。

表1：试点运行诊断指标（均值±标准差，3次随机种子）。σ̂_A：精炼方差；σ̂_f：分数分布宽度；κ：分数漂移；ρ：失败率。

### 2.2 标准MCTS及其局限性
在标准MCTS中，UCT策略（Kocsis和Szepesvári, 2006 (https://arxiv.org/html/2608.23848#bib.bib6)）通过最大化以下公式来选择节点 v 的子节点 c：
UCT_std(c) = R_c/n_c + C√(ln n_v / n_c)  (1)
其中 R_c/n_c 是平均奖励，n_c 和 n_v 是访问次数，C 控制探索。理论默认值 C=√2 是针对奖励范围在 [0,1] 且预算足以收敛的情况校准的（Browne等人，2012 (https://arxiv.org/html/2608.23848#bib.bib7)）。UCT 背后的两个假设在验证密集型搜索中被打破。首先，奖励塑形（第3.1节 (https://arxiv.org/html/2608.23848#S3.SS1)）压缩了有效的利用区间，导致探索奖励项占主导，使得所有节点看起来都同样有前景。其次，数十到数百次的评估预算远低于 UCT 收敛保证成立的渐近区域（Silver等人，2016 (https://arxiv.org/html/2608.23848#bib.bib24); Browne等人，2012 (https://arxiv.org/html/2608.23848#bib.bib7); Kocsis和Szepesvári, 2006 (https://arxiv.org/html/2608.23848#bib.bib6)）。这些违规的共同作用导致生成扁平、宽广的树，无法形成深入的精炼链。PUCT探索项（第3.1节 (https://arxiv.org/html/2608.23848#S3.SS1)）通过线性衰减而非对数衰减部分解决了第一个问题，在预算紧张时减少了探索的主导地位。

#### 经典扩展。
三个经典的MCTS思想与此相关，但无法直接迁移至本场景（第5.3节 (https://arxiv.org/html/2608.23848#S5.SS3)）。渐进式加宽（Coulom, 2007 (https://arxiv.org/html/2608.23848#bib.bib5); Chaslot等人，2008 (https://arxiv.org/html/2608.23848#bib.bib30)）将分支与访问次数挂钩，但与分数无关。首次游玩紧迫性（FPU）（Gelly和Wang, 2006 (https://arxiv.org/html/2608.23848#bib.bib29)）为未访问动作分配固定值，但无法适应非平稳的分数分布。PUCT（Rosin, 2011 (https://arxiv.org/html/2608.23848#bib.bib25); Silver等人，2017 (https://arxiv.org/html/2608.23848#bib.bib26)）使用学习到的策略先验并配合线性探索衰减。ExTS 重新设计了每一个：渐进式加宽变为质量条件式，FPU 变为从父节点奖励历史中抽样的随机虚拟子节点，而 PUCT 式衰减则无需学习先验。

## 3 方法论
*我们的直觉是，特别是在预算紧张的情况下，仅仅在奖励上增加一个标量加权的 UCT 或 PUCT 探索项，本身无法捕捉探索与利用之间的平衡（第5.1节 (https://arxiv.org/html/2608.23848#S5.SS1)）。ExTS 保留了这个加权探索项，但将选择和扩展决策都基于在两个作用域（局部：节点自身的子树；全局：整个搜索树）上观察到的奖励分布进行调整。*

具体而言，每个节点 v 存储一个候选解 x_v ∈ S，并维护以下信息：n_v（总访问次数）、n_v^+（成功访问次数）、ℝ_v（在 v 子树中成功扩展产生的奖励观测），以及 s_v = f(x_v)（验证分数）。奖励池 ℝ_v 实现了均值回溯：ExUCT(v) 估算的是在 v 下方进行扩展的精炼生产力，而非 v 自身候选解的质量。图1 (https://arxiv.org/html/2608.23848#S0.F1) 展示了这三种设计选择如何改变搜索树。完整的搜索循环遵循标准的 MCTS（选择、扩展、验证、回溯），见算法2 (https://arxiv.org/html/2608.23848#alg2)（附录B (https://arxiv.org/html/2608.23848#A2)）。

### 3.1 判别性奖励塑形
有效的选择和有意义的扩展决策都需要区分节点质量。当原始验证分数聚集在狭窄范围内时（在验证密集型领域很常见），UCT 的利用项使得所有节点看起来同样有吸引力：选择变得近乎随机，任何关于扩展 vs. 深入的价值比较都失去信息量。ExTS 的选择策略通过为每个已访问节点 v（n_v > 0）进行如下评分来解决此问题：
ExUCT(v) = (n_v^+ / n_v)^α · φ̄(r_i) + explore(n_par(v), n_v)  (2)
利用项结合了两个信号：塑形奖励 φ̄(r_i)，用于在原始分数狭窄时区分候选项；以及成功率权重 (n_v^+ / n_v)^α，用于折扣其子树主要产生无效输出的节点（α 控制失败折扣）。塑形函数 φ 通过*全局*归一化和温度控制的非线性映射原始分数：
φ(r) = (e^{r̂/T} - 1) / (e^{1/T} - 1)，其中 r̂ = (r - s_min) / (s_max - s_min)  (3)
φ̄(r_i) = (1 / |ℝ_v|) Σ_{r_i ∈ ℝ_v} φ(r_i)  (4)
当 T < 1 时，φ 是凸函数，压缩低分并放大高分。这在验证密集型领域很重要，因为分数聚集在狭窄范围内，线性归一化会使大多数节点看起来同样有吸引力。

探索项采用两种形式之一。UCT 变体对数衰减：
explore_UCT(n_par, n_v) = C√(ln n_par / n_v)  (5)
而 PUCT 风格变体线性衰减，在预算紧张时能更快地收敛到利用：
explore_PUCT(n_par, n_v) = C · √n_par / (1 + n_v)  (6)
与标准 PUCT（Rosin, 2011 (https://arxiv.org/html/2608.23848#bib.bib25); Silver等人，2017 (https://arxiv.org/html/2608.23848#bib.bib26)）结合学习到的策略先验 P(a|s) 不同，