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

Paper: arXiv:2603.12634 Code: none — no public official code is documented; pseudocode below is paper-derived, not a released implementation.

1. Motivation (研究动机)

现有 LLM Agent 的 test-time scaling 往往默认「算力越多越好」，把 token budget 和 tool-call budget 当成可以粗放消耗的资源：并行采样会同时跑很多完整 trajectory，但它无法在中途判断某条路径是否已经陷入重复搜索、错误前提或 dead-end，因此经常把外部搜索调用和生成 token 浪费在低收益分支上。论文把这个问题具体化为：在多跳问答这类需要连续检索、推理、再检索的任务中，agent 不仅要答对，还要在严格的 tool / token 限额内把预算花在最可能带来信息增益的步骤上。

更早的 budget-aware 方法主要有两类不足。第一类依赖 fine-tuning 或额外策略学习，把「省预算」内化进模型策略，但训练成本高，且不一定能迁移到动态 tool-use agent。第二类是 trajectory-level heuristic，例如给 prompt 加预算提醒、或在整条轨迹失败后再停止；这类方法只能在完整路径层面处理成本，不能在每个环境反馈后及时剪掉坏分支。论文认为真正缺失的是 step-level budget control：每执行一次 reasoning step 或 tool call 后，立即评估这个步骤是否产生了边际信息增益，并据此决定继续深入、横向换路，还是尽快收束生成答案。

这个问题值得研究的原因在于，多跳 agent 的主要成本往往来自外部交互而不是模型输出本身。论文 Appendix B 的成本估计显示，假设 search API 每次 $0.005，Low/Middle/High三档工具调用预算分别是5/10/20次时，搜索成本约为$0.025/$0.050/$0.100；而 GPT-OSS-20B 的最大 token 成本只有 $0.00088/$0.00176/$0.00352，Qwen3-30B-A3B的token成本也只有$0.00108/$0.00216/$0.00432。换言之，如果 agent 能少走无效搜索路径，就能直接降低部署成本、延迟和 rate-limit 压力。

Figure 1 解读：左侧的 parallel sampling 把预算平均撒到多条完整 trajectory 上，缺点是每条路径即使早期已经低价值，也会继续消耗预算；右侧的 BAVT 把 reasoning 过程组织成树，每个节点带有 step-level value，并随着剩余预算下降从广泛探索切换到集中 exploitation。这张图直观说明了论文的核心问题：不是「给 agent 更多调用次数」，而是「在有限调用次数内选择最该扩展的中间状态」。

2. Idea (核心思想)

BAVT 的核心洞察是：预算受限的 agent 推理不应被看作若干条独立 rollout 的投票，而应被看作一个带成本约束的动态搜索树。每个中间状态都是一个节点，每次 reasoning / tool call 是一条边；模型既扮演 Generator 生成下一步，也扮演 Critic 对新节点的边际信息增益打分。

关键创新可以概括为三点：第一，用 test-time value tree 替代独立 parallel sampling，让多条候选路径共享搜索前沿；第二，用 residual value predictor 预测 ${\Delta }_t$，即最近一步相对父节点带来的信息增量，而不是直接让 LLM 给绝对分数；第三，用剩余预算比例 $r_t$ 的倒数作为 exponent，把节点值转成采样分布，使策略在预算充足时更平滑、更探索，在预算枯竭时自动变尖锐、更贪心。

它和 Tree-of-Thought / LATS 这类 search-based agent 的根本差异在于，后者通常追求 accuracy-driven search，默认搜索 horizon 足够长；BAVT 则把 tool/token budget 显式放进节点选择公式，让搜索几何随剩余资源改变。它和普通 self-consistency / parallel sampling 的差异也很直接：parallel sampling 只在最后投票，BAVT 在每个中间步骤就可以 widen、deepen 或 answer，从而避免坏轨迹跑完整条路径。

3. Method (方法)

3.1 总体框架：Budget-Aware Value Tree

论文将 agent 推理形式化为 resource-constrained deterministic decision process（资源受限确定性决策过程） $(\mathcal{S},\mathcal{A},\mathcal{T},\mathcal{B},\mathcal{C})$。状态 $s_t\in \mathcal{S}$ 包含原始 query、历史 action、内部 reasoning trace 和外部环境 observation；动作 $a_t\in \mathcal{A}$ 可以是内部推理生成，也可以是外部工具调用；转移函数 $\mathcal{T}:\mathcal{S}\times \mathcal{A}\to \mathcal{S}$ 把新 action 与 observation 追加进上下文。预算不是静态约束，而是动态状态： $b_t=(b_{\text{tool},t},b_{\text{token},t})\in \mathcal{B},b_0=(B_{\text{tool}},B_{\text{token}}).$ 每个动作有成本： $\mathcal{C}(a_t)=({\mathcal{C}}_{\text{tool}}(a_t),{\mathcal{C}}_{\text{token}}(a_t)),$ 其中成功工具调用的 ${\mathcal{C}}_{\text{tool}}(a_t)=1$，否则为 $0$；${\mathcal{C}}_{\text{token}}(a_t)$ 是该步输出 token 数。预算更新为： $b_{t+1}=b_t-\mathcal{C}(a_t),$ 也就是： $\begin{array}{rl}{b}_{\text{tool},t+1}& =b_{\text{tool},t}-{\mathcal{C}}_{\text{tool}}(a_t),\\ b_{\text{token},t+1}& =b_{\text{token},t}-{\mathcal{C}}_{\text{token}}(a_t).\end{array}$ 搜索目标不是直接选一条 trajectory，而是在预算约束下优化搜索策略 $\pi$，从若干竞争分支中找到最终答案 $\hat{y}$。parallel sampling 的 baseline 是在同一总预算 $B$ 下运行 $K$ 条独立 trajectory，并用 majority vote： ${\sum }_{i=1}^K\mathcal{C}({\tau }_i)\le B,\hat{y}=\arg {\max }_y{\sum }_{i=1}^K\mathbb{I}(A({\tau }_i)=y).$ BAVT 则把预算分配决策下沉到每个节点扩展步骤。

Figure 2 解读：图中 a) 展示预算感知扩展：剩余预算高时，节点选择分布较平，鼓励搜索多个方向；剩余预算低时，分布集中到高 value 节点。b) 展示 test-time scaling tree：节点是中间状态，边是 tool call 或 reasoning action，agent 不再被单条线性轨迹困住。c) 展示同一个 LLM backbone 的 Actor-Critic 双角色：Generator 负责产生下一步，Critic 负责评价新节点的 step-level progress。三部分连在一起后，BAVT 才能在「多分支搜索」和「严格预算收束」之间动态切换。

3.2 Test-Time Scaling Tree

BAVT 初始化一个 root node $s_0=x$，其中 $x$ 是用户问题。之后维护一棵搜索树 $\mathcal{T}$ 和候选节点池 ${\mathcal{N}}_{\text{cand}}$。树节点对应中间 reasoning state 或环境 observation，边对应模型产生的 action。Generator 每次读取当前节点及动态 structural instruction，生成一个 action：可能是搜索查询、逻辑推理、进一步分解，也可能是最终答案。

这一设计的直觉是：多跳问答的失败通常不是最后一步才出现，而是在中途某个事实链条就走偏了。线性 agent 一旦沿着错误前提继续执行，后续检索和推理都会围绕错误前提自洽展开；而树结构允许系统保留多个前沿，在某条路径 value 下降时转向 sibling 或 cousin branch，不必重新开始整条 trajectory。

3.3 Step-Level Value Estimation：残差价值而非绝对自评分

BAVT 使用同一个 LLM backbone 作为 Critic，对新生成的 child node $n^{\prime }$ 估计最近一步的 residual score / information delta ${\Delta }_t$。如果父节点 value 是 $V(n)$，则 child value 更新为： $V(n^{\prime })=\Phi (V(n)+{\Delta }_t),$ 其中 $\Phi (\cdot )$ 把值限制在归一化范围内。Appendix B 说明，Critic 原始分数是 $[1,10]$ 的离散刻度，再除以 10 归一化到 $V(n)\in [0.1,1.0]$；${\Delta }_t$ 被 clip 到 $[-4,+4]$；terminal confidence threshold 是 $\tau =0.8$。

残差评分比绝对评分更适合 agent search。LLM self-evaluation 容易对幻觉或低质量 reasoning 给出虚高绝对分数；而 BAVT 问的是「这一步相对上一步有没有带来新证据或缩小不确定性」。如果 action 只是重复检索、得到无关观察，${\Delta }_t\le 0$；如果 action 得到关键桥接事实，${\Delta }_t>0$。这使 Critic 更像 process verifier，而不是一个事后 answer judge。

3.4 Value-Guided Structural Instruction：Answer / Widen / Deepen

Critic 的 value 不只是排序分数，还直接决定下一步结构指令。给定 terminal threshold $\tau$：

• Answer Generation：若 $V(n^{\prime })\ge \tau$，认为证据充分，要求模型停止工具调用并合成最终答案。
• Search Widening：若 $V(n^{\prime })\le V(n)$，说明最近 action 没有正信息增益，要求模型换一个 query 或 reasoning line，避免重复原路径。
• Search Deepening：若 $V(n)<V(n^{\prime })<\tau$，说明路径有正增益但未达到终止阈值，要求模型继续沿该方向深入一步。

Appendix C 给出了对应 prompt。Generator 的基础规则是每轮只能做一个 action：要么调用一个工具，要么提交一行 <answer>FINAL_ANSWER</answer>。Critic prompt 则强制只输出 JSON {"delta": 0} 这类 delta，并要求对弱证据保守、对重复动作给非正增益。

3.5 Budget-Aware Node Expansion：用剩余预算调整探索/利用

BAVT 的节点选择公式把预算显式注入 search geometry。首先定义有效剩余预算比例： $r_t=\min \left(\frac{b_{\text{tool},t}}{B_{\text{tool}}},\frac{b_{\text{token},t}}{B_{\text{token}}}\right),r_t\in (0,1].$ 动态 exponent 是： ${\alpha }_t=\frac{1}{r_t}.$ 对于候选池中每个节点 $n_i\in {\mathcal{N}}_{\text{cand}}$，用累计 value 计算未归一化权重： $w_{n_i}=V(n_i{)}^{{\alpha }_t},$ 然后归一化为扩展概率： $\mathbb{P}(n_i)=\frac{w_{n_i}}{{\sum }_{j=1}^N{w}_{n_j}}.$ 当预算充足时，$r_t\approx 1$、${\alpha }_t\approx 1$，采样概率大致与 value 成正比，仍保留多方向探索；当预算下降时，$r_t\to 0$、${\alpha }_t$ 增大，value 差异被指数放大，分布趋向 one-hot，高 value 分支被强制优先扩展。与 UCB 不同，这里不是为无限 horizon 的 asymptotic regret 做平衡，而是为有限预算下的及时收束服务。

3.6 Backstop、回传与收束

完整算法还有两个实用细节。第一，如果已经发现 terminal answer node，BAVT 会把该答案加入集合 $\mathcal{A}$，并触发 bottom-up value backpropagation，平滑更新树中相关节点的 value。第二，如果预算快耗尽但还没有答案，触发 budget backstop：从候选池中选 $V$ 最大的节点 $n^{\ast }$，强制 synthesize answer，避免预算用尽后没有任何输出。Appendix B 给出的 backstop threshold 是 $\eta =0.2$，即当 token ratio 低于 20% 或 tool budget 用尽时触发兜底回答。

3.7 论文伪代码（无官方 released code）

代码搜索未找到官方开源实现（checked: arXiv/PDF/Hugging Face 页面、title+github、BAVT+github、arXiv ID+github、first-author/org candidate repos、GitHub repo/code search；mlbrilliance/bavt-budget-aware-agent 是 2026-05-10 创建的非作者第三方/不相关 ML Intern 仓库，未作为官方实现记录）。以下伪代码基于论文 Algorithm A、Appendix B/C 与公式重写，不是 released code 映射。

3.7.1 Budget-aware node selection

import torch
 
 
def budget_aware_node_probs(values, tool_left, token_left, tool_budget, token_budget):
    """values: tensor in [0.1, 1.0], one scalar per active candidate node."""
    r_tool = tool_left / max(tool_budget, 1)
    r_token = token_left / max(token_budget, 1)
    r_t = max(min(r_tool, r_token), 1e-6)
    alpha_t = 1.0 / r_t
    weights = torch.clamp(values, min=0.1, max=1.0).pow(alpha_t)
    return weights / weights.sum(), alpha_t

3.7.2 Residual critic value update and structural instruction

import torch
 
 
def update_value_and_instruction(parent_value, critic_delta, tau=0.8):
    delta = torch.clamp(torch.tensor(float(critic_delta)), -4.0, 4.0) / 10.0
    child_value = torch.clamp(torch.tensor(parent_value) + delta, 0.1, 1.0).item()
 
    if child_value >= tau:
        instruction = "answer"
    elif child_value <= parent_value:
        instruction = "widen"
    else:
        instruction = "deepen"
    return child_value, instruction

3.7.3 BAVT search loop

import torch
 
 
def bavt_search(root_query, generator, critic, tool_budget=10, token_budget=4000, eta=0.2):
    tree = []
    candidates = []
    answers = []
    root = {"state": root_query, "value": 0.1, "parent": None, "terminal": False}
    tree.append(root)
    candidates.append(root)
    tool_left, token_left = tool_budget, token_budget
 
    while tool_left > 0 and token_left > 0:
        values = torch.tensor([node["value"] for node in candidates], dtype=torch.float32)
        probs, alpha_t = budget_aware_node_probs(
            values, tool_left, token_left, tool_budget, token_budget
        )
        node = candidates[int(torch.multinomial(probs, 1))]
 
        instruction = generator.structural_instruction(node)  # widen / deepen / answer
        action, observation, cost = generator.step(node["state"], instruction)
        tool_left -= cost.tool_calls
        token_left -= cost.output_tokens
 
        child_state = generator.transition(node["state"], action, observation)
        if generator.is_answer(child_state):
            child = {"state": child_state, "value": node["value"], "parent": node, "terminal": True}
            answers.append(child)
        else:
            delta = critic.delta(parent_state=node["state"], child_state=child_state)
            child_value, next_instruction = update_value_and_instruction(node["value"], delta)
            child = {"state": child_state, "value": child_value, "parent": node, "terminal": False}
            candidates.append(child)
        tree.append(child)
 
        if answers:
            generator.backpropagate_values(tree, answers)
 
        if not answers and (tool_left <= 0 or token_left / token_budget <= eta):
            best = max(candidates, key=lambda n: n["value"])
            forced_answer = generator.answer_now(best["state"])
            answers.append({"state": forced_answer, "value": best["value"], "parent": best, "terminal": True})
 
    best_answer = max(answers, key=lambda n: n["value"])
    return generator.extract_answer(best_answer["state"])

3.8 理论保证

论文给出 probabilistic convergence to answer generation。假设存在一条 oracle trajectory ${\mathcal{P}}^{\ast }$，每次 deepening 至少带来 ${\Delta }_t\ge \delta >0$；在阈值前 bounding function 保持线性，即 $\Phi (x)=x$ for $x\le v_{\max }$ 且 $\tau <v_{\max }$；候选池大小有上界 $N_{\max }$，value 在 $[v_{\min },v_{\max }]$，exponent 有上界 ${\alpha }_{\max }$。则任一候选节点被采样的概率有下界： $p_{\min }=\frac{v_{\min }^{{\alpha }_{\max }}}{N_{\max }\cdot v_{\max }^{{\alpha }_{\max }}}>0.$ 从初始状态达到阈值最多需要： $K=\lceil \frac{\tau -V(s_0)}{\delta }\rceil$ 个 oracle progress step。若每次扩展最大成本为 $c_{\max }$，初始预算 $B$ 能支持 $M=\lfloor B/c_{\max }\rfloor$ 次扩展。论文用 Bernoulli coupling 和 Chernoff bound 得到，只要： $M\ge \frac{1}{p_{\min }}\left(K+\sqrt{2K\log \frac{1}{ϵ}}+2\log \frac{1}{ϵ}\right),$ 就能保证 failure probability 不超过 $ϵ$，即以至少 $1-ϵ$ 的概率到达 $V(s_t)\ge \tau$ 的 terminal node。这个定理保证的是「足够预算下会收束到可回答节点」，不是保证答案一定语义正确；语义正确仍依赖 Critic 质量、检索质量和 base model 能力。

4. Experimental Setup (实验设置)

4.1 Datasets 与评测规模

论文使用四个 multi-hop QA benchmark：HotpotQA、2WikiMultihopQA、MuSiQue 和 Bamboogle。作者强调这些任务需要 sequential tool use 和 dynamic information gathering，不能只靠模型参数知识直接回答，适合评估 resource-constrained environment interaction。论文未详细说明本次每个 benchmark 的评测样本数或是否使用子集，因此这里不补写外部数据集总规模，避免把原始数据集规模误当作本文实验规模。

4.2 Models、retrieval 与 baseline

模型覆盖两个架构族：

• GPT-OSS-20B：reasoning model，具备较强内部 chain-of-thought 和 tool-use 能力。
• Qwen3-30B-A3B-Instruct-2507：instruct model，偏通用指令跟随。

实现基于 Inspect AI。检索工具沿用 Search-R1 设置，使用 2018 Wikipedia dump 作为知识库，用 E5 dense retriever，每次 search query 固定返回 5 个 passages。Baseline 是 budget-constrained parallel sampling / majority voting：在同一 tool/token 总预算内并行运行尽可能多的独立 trajectory，预算耗尽后对 terminal answers 做 majority vote。

4.3 Budget 与 generation config

三档预算如下：

Budget tier	Max tool calls	GPT-OSS token limit	Qwen token limit
Low	5	2000	1000
Middle	10	4000	2000
High	20	8000	4000

BAVT 的动态搜索超参数在所有数据集上保持不变：raw critic value scale $[1,10]$，${\Delta }_t\in [-4,+4]$，归一化 $V(n)\in [0.1,1.0]$，terminal threshold $\tau =0.8$，backstop threshold $\eta =0.2$，每次调用最多输出 512 tokens。论文没有 released code，因此这些训练/运行配置来自 arXiv source main.tex Appendix B，而非官方 launch script。

Generation settings 使用各模型官方默认：Qwen instruct 采用 temperature 0.7、top-$p$ 0.8、top-$k$ 20；GPT-OSS reasoning model 采用 temperature 1.0、top-$p$ 1.0、top-$k$ 0。评估指标是 Exact Match (EM) 和 F1：EM 衡量答案字符串是否完全匹配，F1 衡量答案 token-level overlap。

5. Experimental Results (实验结果)

5.1 平均 performance-efficiency frontier

Figure 3 解读：四个子图分别汇总 OSS-20B / Qwen3-30B 在 EM 和 F1 上随 tool budget 增长的平均表现。BAVT 的曲线在每个 budget 点都高于 parallel sampling baseline。最关键的结论是，OSS-20B 上 BAVT Low tier 仅用 5 次 tool call 就达到平均 EM 0.338，超过 baseline High tier 20 次 tool call 的 0.334；Qwen 上 baseline 从 Low 到 High 几乎不涨（平均 EM 0.289 到 0.293），但 BAVT Low 已达到约 0.386。

5.2 OSS-20B reasoning model：BAVT 放大 reasoning trajectory 的有效性

Figure 4 解读：OSS-20B 的 baseline 会随预算增加而改善，说明 reasoning model 的多样化 rollout 确实能从 parallel sampling 中受益；但它仍会让错误 premise 的 trajectory 跑到结束。BAVT 在每个数据集、每个预算档都更高，尤其 Low budget 下平均 EM 从 baseline 0.194 提升到 0.338。图中可见 Bamboogle 的 Low EM 从 0.31 提升到 0.49，2Wiki 的 Low EM 从 0.13 提升到 0.37，说明 step-level verification 对检索链路很关键。

OSS-20B 图中标注的主要数值如下（每格为 baseline → BAVT）：

Dataset / Metric	Low	Middle	High
HotpotQA EM	0.23 → 0.36	0.34 → 0.40	0.37 → 0.43
HotpotQA F1	0.33 → 0.50	0.47 → 0.55	0.50 → 0.58
2Wiki EM	0.13 → 0.37	0.21 → 0.41	0.38 → 0.45
2Wiki F1	0.17 → 0.47	0.26 → 0.52	0.47 → 0.55
MuSiQue EM	0.10 → 0.15	0.14 → 0.19	0.17 → 0.20
MuSiQue F1	0.14 → 0.23	0.20 → 0.27	0.24 → 0.30
Bamboogle EM	0.31 → 0.49	0.38 → 0.55	0.42 → 0.54
Bamboogle F1	0.44 → 0.64	0.52 → 0.67	0.58 → 0.65

5.3 Qwen3-30B instruct model：打破 mode-collapse plateau

Figure 5 解读：Qwen3-30B 是 instruct model，baseline 的主要问题不是预算不够，而是生成多样性低、过早给出确定答案，导致更多 parallel rollout 也重复同类失败路径。BAVT 的 widen 指令在 ${\Delta }_t\le 0$ 时显式要求换 query 或换 reasoning line，因此能人为制造横向探索，显著提高上限。论文同时指出，BAVT 在更高预算下也会变平，说明 instruct model 最终受限于 base model 汇总多文档证据的能力。

Qwen3-30B 图中标注的主要数值如下（每格为 baseline → BAVT）：

Dataset / Metric	Low	Middle	High
HotpotQA EM	0.34 → 0.42	0.34 → 0.43	0.34 → 0.43
HotpotQA F1	0.48 → 0.56	0.48 → 0.58	0.49 → 0.58
2Wiki EM	0.35 → 0.47	0.37 → 0.48	0.38 → 0.47
2Wiki F1	0.45 → 0.56	0.46 → 0.57	0.47 → 0.57
MuSiQue EM	0.11 → 0.18	0.12 → 0.20	0.12 → 0.21
MuSiQue F1	0.22 → 0.29	0.23 → 0.31	0.23 → 0.32
Bamboogle EM	0.35 → 0.48	0.33 → 0.50	0.34 → 0.47
Bamboogle F1	0.49 → 0.63	0.47 → 0.65	0.49 → 0.63

5.4 Ablation：三组件缺一不可

Ablation 使用 OSS-20B、Middle budget。结果显示，单纯树结构不但不够，还会因为随机扩展分散预算而退化；step-level value 能明显恢复并超过 baseline；budget-aware exponent 是最终达到最优的关键。

Tree	Step-Level Value	Budget-Aware Selection	HotpotQA EM/F1	2Wiki EM/F1	MuSiQue EM/F1	Bamboogle EM/F1	AVG EM/F1
×	×	×	0.344 / 0.469	0.205 / 0.261	0.142 / 0.203	0.381 / 0.517	0.268 / 0.363
✓	×	×	0.243 / 0.340	0.124 / 0.163	0.100 / 0.140	0.392 / 0.478	0.215 / 0.280
✓	✓	×	0.356 / 0.481	0.265 / 0.332	0.158 / 0.224	0.456 / 0.575	0.309 / 0.403
✓	✓	✓	0.402 / 0.552	0.413 / 0.517	0.186 / 0.272	0.552 / 0.666	0.388 / 0.502

具体解释：tree-only 的 AVG EM 只有 0.215，低于 baseline 0.268，说明没有 value 的树会把预算切碎到大量低价值分支；加入 step-level value 后 AVG EM 到 0.309，说明 Critic 能把搜索导向有证据增益的节点；再加入 budget-aware selection 后 AVG EM 到 0.388，说明仅有静态 value 不够，还必须在预算降低时用 ${\alpha }_t$ 强制从探索转向 exploitation。

5.5 Limitations（限制）与结论

论文承认两类限制。第一，双角色 prompting 会产生额外 inference overhead：每个中间状态都用主 LLM backbone 做 Critic，会消耗 token 和 latency；未来可用轻量 Process Reward Model 或直接训练 value head 来降低成本。第二，当前评估集中在 knowledge-intensive multi-hop QA；若迁移到 BrowseComp、OSWorld、WebArena 这类长时程交互环境，会遇到不可逆动作、partial observability 和 delayed reward，需要更复杂的 temporal credit assignment 与 state-space exploration。

整体结论是，BAVT 证明了在 agent 推理中「聪明分配预算」可以优于「盲目增加预算」。在 OSS-20B 上，Low-budget BAVT 已超过 High-budget baseline；在 Qwen instruct model 上，BAVT 通过 widen/deepen/answer 指令显式打破低多样性 plateau。它的贡献不是训练出一个更强模型，而是在 inference-time 把搜索树、step-level critic 和 budget-dependent sampling 组合成一个可复用的资源控制框架。