Esc
输入关键词开始搜索
Agent

BAVT：预算感知树搜索——让 Agent 花 1/4 的钱做得更好

BAVT：预算感知树搜索——让 Agent 花 1/4 的钱做得更好

论文： Spend Less, Reason Better: Budget-Aware Value Tree Search for LLM Agents 团队： University of British Columbia + Vector Institute 状态： 预印本，2026-03-13

1. 问题：Agent 推理的资源浪费

当前 LLM Agent 在多跳推理中存在严重的资源浪费：

  • 暴力并行采样（如 Self-Consistency）同时运行多条轨迹，但大量轨迹走进死胡同或重复已知信息
  • 线性 ReAct 循环一旦陷入错误方向，只能走到底——不会回头
  • 现有预算感知方法（如 BATS）只在 prompt 里告诉模型”你还剩多少预算”，靠模型自己”自律”，既没有步级干预能力，也没有收敛保证

核心矛盾：test-time scaling 的主流叙事是”给更多 token 就更好”，但实际上 盲目堆资源的收益递减极快。论文引用的数据显示，4× 预算往往只带来几个点的提升。

2. 方法：三根支柱

BAVT 是一个 training-free 的推理时框架，不改模型权重，只在推理循环外层包了一个搜索控制器。三个核心组件：

2.1 搜索树结构

把多跳推理建模为一棵动态搜索树：

  • 节点 = 中间推理状态（包含查询、历史动作、工具返回）
  • 边 = Agent 动作（工具调用或推理步骤）
  • 根节点 = 原始问题

同一个 LLM backbone 交替扮演两个角色：

  • Generator（演员）：给定当前节点，生成候选动作
  • Critic（评论家）：评估新节点的价值

2.2 步级残差价值估计

这是解决 LLM 自评估”过度自信”问题的关键。

传统方法的问题： 让 LLM 给中间状态打绝对分数（0-10），模型倾向于给所有状态打高分——即使推理已经走偏了。

BAVT 的方案： 不打绝对分，而是预测 残差（delta）——“这一步相比上一步，信息增量有多少？”

V(n') = Φ(V(n) + Δ_t)

其中 Δ_t 是信息增量，Φ 是边界函数保证值在 [0,1] 范围内。

价值驱动的搜索策略：

  • V(n') ≥ τ（阈值）→ 终止，生成最终答案
  • V(n') ≤ V(n)（信息零增长或倒退）→ 横向扩展，尝试不同方向
  • V(n) < V(n') < τ（有进展但未充分）→ 纵向深入，继续当前方向

2.3 预算条件化节点选择（核心创新）

这是论文最精巧的设计。

剩余预算比例：

r_t = min(b_tool,t / B_tool, b_token,t / B_token)

取工具调用预算和 token 预算中更紧张的那个。

动态指数：

α_t = 1 / r_t

节点选择概率：

w_i = V(n_i)^{α_t}
P(n_i) = w_i / Σ w_j

行为效果：

  • 预算充裕（r_t ≈ 1）→ α_t ≈ 1 → 选择概率 ≈ 与原始价值成正比 → 探索
  • 预算紧张（r_t → 0）→ α_t → ∞ → 概率集中到最高价值节点 → 贪心利用

这个机制 没有任何可调参数——预算比例本身就是天然的温度参数。

为什么不用 UCB？ 标准 UCB（Upper Confidence Bound）假设无限时间地平线，而 Agent 推理有严格的资源上限。BAVT 的指数机制天然适配有限预算场景。

2.4 全局回溯传播

当搜索树中出现第一个终止节点（Agent 给出了最终答案），BAVT 对该节点到根节点路径上的所有祖先节点做价值传播——用答案质量更新整条路径的价值评估。

同时引入 惩罚机制：终止节点的兄弟分支被显式降价值，避免在已有好答案的情况下继续浪费预算。

3. 收敛保证

论文提供了形式化的收敛定理（Theorem 1）：

在有限预算 B 下，BAVT 以至少 1−ε 的概率到达一个终止答案节点。

证明依赖两个假设：

  1. 每个非终止节点至少有一个子节点可以被扩展
  2. 价值函数是有界的（由 Φ 保证）

这意味着 BAVT 不会出现预算耗尽但没有输出答案的情况——在预算即将耗尽时，指数机制会强制选择最高价值路径并终止。

4. 实验结果

4.1 设置

  • 模型： GPT-4.1-mini（instruct）+ QwQ-32B（reasoning）
  • 基准： 4 个多跳 QA：HotpotQA、2WikiMultiHopQA、MuSiQue、Bamboogle
  • 对比： ReAct、Reflexion、BATS（budget-aware baseline）、Parallel Sampling
  • 预算档： Low / Medium / High（tool calls × token limits）

4.2 核心结论

GPT-4.1-mini 上（4 个基准的平均 F1）：

方法Low 预算Medium 预算High 预算
ReAct42.349.752.1
Parallel Sampling45.853.257.9
BATS44.151.855.3
BAVT52.658.160.4

关键发现：

  • BAVT Low 预算（52.6）> Parallel Sampling High 预算（57.9 的 ~91%），但只用 1/4 的资源
  • 在最严格的 Low 预算下，BAVT 比暴力采样高 6.8 个 F1 点
  • 收益在 Low 预算时最显著——预算越紧张，智能分配的优势越大

4.3 消融实验

去掉的组件平均 F1 下降
去掉残差价值预测（改用绝对打分）-4.2
去掉预算条件化（固定 α=1）-3.8
去掉全局回溯传播-2.1

残差价值预测和预算条件化是两个最关键的组件。

5. 与相关工作的对比

方法训练需求干预粒度预算感知收敛保证
Self-Consistency无轨迹级否否
Tree of Thoughts无步级否否
LATS无步级否否
BATS无轨迹级是（prompt）否
Self-Budgeter微调步级是否
BAVT无步级是（数学）是

BAVT 是目前唯一同时满足 training-free、步级干预、数学预算感知、收敛保证的方法。

6. 讨论与边界

优势

  1. 零训练成本： 不改模型权重，推理时直接用
  2. 优雅的数学设计： 预算比例→指数→选择概率，无超参数
  3. 理论保证： 有限预算下收敛到答案
  4. 实用价值： 直接降低 API 成本（token + tool call 双重约束）

局限

  1. 价值估计依赖 LLM 自评估： 虽然残差预测比绝对打分好，但在 LLM 对某些领域完全无法自评的情况下（如需要外部验证的数学证明），BAVT 可能误判
  2. 仅在多跳 QA 验证： Agent 的真实场景（SWE、Web 导航、代码生成）表现待验证
  3. 搜索开销： 生成-评估-选择的循环本身消耗 token——在极低预算下，搜索本身的开销可能占比过高
  4. 单 LLM 扮演双角色： Generator 和 Critic 共用同一个模型，可能存在系统性偏差（比如模型总是高估自己生成内容的价值）

个人评价

这是 test-time scaling 领域一篇重要的修正性工作。它不是说”scaling 无用”，而是证明了 智能分配比暴力堆叠更有效。预算条件化的指数机制设计得非常优雅——用一个 1/r 就实现了从探索到利用的平滑过渡，不需要任何调参。

对实际 Agent 部署的启示很直接：如果你在用 ReAct + 并行采样，试着在选择”接下来扩展哪条路”时加入预算感知的概率调整——即使不完全实现 BAVT，这个思路就能立刻节省 API 开销。

7. 关键收获

  1. Test-time scaling 的收益递减是真实的： 暴力堆 4× 预算的提升，不如智能分配 1/4 预算
  2. 残差价值预测 >> 绝对打分： 问”这一步进步了多少”比问”现在有多好”更可靠
  3. 预算比例是天然的温度参数： 不需要手动设置探索-利用平衡，预算状态本身就编码了这个信息
  4. 收敛保证是可工程化的： 有限预算下保证输出答案，这对生产系统是刚需

适合深入的后续方向： 将 BAVT 扩展到 SWE Agent 场景（token 和 API 双重受限，且验证信号更稀疏），以及探索外部验证器替代 LLM 自评估。

目录