技术摘要：在 LLM 测试时缩放中使树搜索策略与固定 Token 预算对齐

问题陈述

大语言模型（LLMs）可以通过测试时缩放（Test-Time Scaling）来提高响应质量，即在不更新模型参数的情况下，在推理过程中分配额外的计算资源。虽然树搜索解码（如蒙特卡洛树搜索，MCTS）是测试时缩放的一种有效形式，但现实世界的部署通常会施加固定的单查询 Token 预算。

现有的树搜索策略在很大程度上是与预算无关的（budget-agnostic）。它们通常仅将 Token 预算视为一种终止条件，而非引导搜索行为的动态约束。这种不匹配导致了两个主要的失效模式：

1. 后期过度分支（Late-stage over-branching）： 搜索在过程后期仍在扩展浅层节点，导致在能够精炼或完成有潜力的候选路径之前就耗尽了预算。
2. 过早终止（Premature termination）： 搜索提前停止，导致分配的一部分预算未被使用。

现有的早期停止变体侧重于节省 Token，但缺乏一种动态策略，能在剩余预算减少时，将搜索策略从广泛探索转向精炼。

方法论：预算引导的 MCTS (BG-MCTS)

作者提出了 BG-MCTS（预算引导的 MCTS），这是一种显式地将搜索策略以剩余 Token 预算为条件进行约束的树搜索解码算法。其核心机制依赖于一个预算充足率 $\rho \in [0, 1]$，定义为：
$$\rho = 1 - \frac{C_{used}}{B}$$
其中 $C_{used}$ 是累计生成的 Token，$B$ 是总预算。随着 $\rho$ 减小（趋向于 0），策略会从探索转向利用和完成。

BG-MCTS 引入了两个受预算控制的控制机制：

1. 预算引导的选择 (BG-PUCT)

标准的 PUCT 选择被修改为退火探索奖励并引入完成偏置：
$$\text{BG-PUCT}(p, s, \rho) = \frac{\tilde{W}(s, \rho)}{m_s} + \rho \cdot c \cdot P(s|p) \sqrt{\frac{\ln(m_p)}{m_s}}$$

• 探索退火： 探索项乘以 $\rho$。随着预算枯竭（$\rho \to 0$），探索新分支的动力随之减弱。
• 完成偏置： 累积价值 $\tilde{W}(s, \rho)$ 通过一个与节点深度 $d(x)$ 和 $(1-\rho)$ 成正比的项进行修正。这会使选择过程偏向于更接近生成最终答案的深层节点，而不会人为地提升那些已经包含完整答案的节点。

2. 预算引导的树扩展 (Budget-Guided Tree Widening)

为了防止浪费性的后期分支，BG-MCTS 将“扩展”（从父节点生成一个新的子节点）视为与现有子节点并列的可选动作。一个虚拟生成子节点 $s_{gen}(p)$ 被添加到选择集中。其分数为：
$$E_{gen}(p, \rho) = \mu(p) + \lambda \cdot \rho \cdot \sigma^2(p)$$

• $\mu(p)$ 和 $\sigma^2(p)$ 分别代表现有子节点得分的均值和方差。
• 该项由 $\rho$ 进行缩放。当预算充足时，鼓励扩展（尤其是当子节点之间存在分歧时）。当预算不足时，扩展的动力会被抑制，从而迫使搜索深化现有的有潜力轨迹。

统一算法

该算法遵循标准的 MCTS 循环，但使选择和扩展的决策都依赖于 $\rho$。这诱导了一个**“由宽变深”的调度表（wide-to-deep schedule）**：在搜索初期进行广泛探索，随后随着预算耗尽，转向专注的精炼和答案完成。

核心贡献

1. 预算感知策略设计： 本文引入了第一个能够根据剩余 Token 预算动态调整其搜索行为（探索 vs. 利用 vs. 扩展）的树搜索解码框架，而非仅仅将预算视为静态停止信号。
2. 新颖机制： 提出了 BG-PUCT（具有预算调节的探索和深度偏置的价值修正）以及用于预算感知扩展的虚拟生成子节点。
3. 实证验证： 在数学推理基准（MATH500, AIME24/25）和物理推理基准（UGPhysics）上，使用开源模型（Llama-3.1-8B, Qwen2.5-7B, Qwen3-32B）进行了全面的评估。

实验结果

作者在 10k、20k 和 30k Token 的固定预算下，将 BG-MCTS 与预算无关的基准模型（标准 MCTS, AB-MCTS-M, LiteSearch）以及缩放基准模型（重复采样, 顺序精炼）进行了对比评估。

• 性能： BG-MCTS 在所有模型和预算下均一致优于所有基准模型。例如，在 Qwen2.5-7B 的 MATH500 测试中，BG-MCTS 在 30k Token 时达到了 71.1% 的准确率，而次优的树搜索基准（MCTS）为 65.9%。
• 预算利用率： 与经常过早停止的 LiteSearch 不同，BG-MCTS 在接近预算耗尽时仍能持续提高准确率。
• 定性行为： 对搜索树的分析显示，BG-MCTS 在搜索早期保持较宽的宽度，但在搜索后期转向深化特定分支。相比之下，标准 MCTS 通常在预算耗尽前仍持续扩展浅层节点，导致无法完成有潜力的路径。
• 物理推理： 该方法的有效性延伸到了 UGPhysics，证明了预算对齐的“由宽变深”行为在纯数学推理之外同样受益。

意义与主张

论文声称，将树搜索决策以剩余预算为条件进行约束，比单纯将预算视为停止条件更为有效。

• 可预测的缩放： BG-MCTS 提供了一个简单的接口，用于实现可预测的测试时缩放，用户只需指定 Token 预算，策略即可在该成本范围内自动调整其“探索到完成”的调度方案。
• 数据合成意义： 作者指出，BG-MCTS 倾向于产生每个问题实例更少的回答节点，但具有显著更高的精确度（正确性）。这种“更少实例、更好答案”的模式被强调为对于数据合成特别有价值，因为在数据合成中，高质量的推理轨迹比原始覆盖率更为关键。
• 鲁棒性： 该方法即使在使用提供微弱或饱和信号的不完美过程奖励模型（PRM）时仍然有效，这表明预算感知的结构化改变可以补偿噪声评估信号。

该研究得出结论，将搜索策略与固定 Token 约束相匹配，是实现 LLM 在资源受限的现实世界场景中部署的关键一步。