跳转至

Rethinking Optimal Verification Granularity for Compute-Efficient Test-Time Scaling

会议: NeurIPS 2025
arXiv: 2505.11730
代码: https://github.com/hmarkc/VG-Search
领域: LLM推理 / 测试时计算
关键词: test-time scaling, verification granularity, beam search, process reward model, compute efficiency

一句话总结

提出 Variable Granularity Search (VG-Search)，通过可调的验证粒度参数 \(g\) 统一 Beam Search 和 Best-of-N，发现传统每步验证是次优的，自适应调整 \(g\) 可在提升准确率3%+的同时减少52%+的计算量。

研究背景与动机

  1. 领域现状：Test-time scaling (TTS) 通过推理时的额外计算提升LLM性能。采样型方法（Beam Search, Best-of-N）使用验证器（PRM）指导搜索。当前标准做法是每个生成步骤（通常以换行符分割）都调用验证器。
  2. 现有痛点：(a) 连续步骤间PRM分数变化很小（>50%的两步分差<1%），说明每步验证存在大量冗余；(b) 验证器调用的延迟占比越来越高，成为推理瓶颈。
  3. 核心矛盾：验证频率高→搜索精确但计算昂贵；验证频率低→计算便宜但错失纠错机会。当前固定 \(g=1\) 的做法是启发式的，不一定最优。
  4. 本文要解决什么？ (1) 系统研究验证粒度对准确率-计算量trade-off的影响；(2) 设计自适应策略动态选择最优 \(g\)。
  5. 切入角度：用无穷猴子定理类比——验证频率 \(g\) 控制了错误修剪的时机，过频浪费计算，过稀错过纠错；存在一个依赖于生成器能力和任务难度的最优均衡点。
  6. 核心idea一句话：验证器不需要每步都调，强生成器+简单任务适合稀疏验证，弱生成器+难任务需要频繁验证。

方法详解

整体框架

VG-Search在每个搜索周期中：(1) 对 \(B_1 \times B_2\) 个候选调用验证器评分和选择 → (2) 保留 \(B_1\) 个最优beam → (3) 每个beam向前生成 \(g-1\) 步（Extend，不验证） → (4) 每个beam分支 \(B_2\) 个单步续写（Branch） → 回到(1)。当 \(g=1\) 退化为标准Beam Search，\(g=L\) 退化为Best-of-N。

关键设计

  1. 统一搜索框架 VG-Search:
  2. 做什么：通过粒度参数 \(g\) 将 Beam Search 和 Best-of-N 统一为连续谱
  3. 核心思路：关键创新在于Extend步——被选中的beam先自由生成 \(g-1\) 步（不调用验证器），然后才分支+验证。这意味着只有 \(B_1\) 个beam参与Extend，而非 \(B_1 \times B_2\) 个，显著节省生成FLOPs

  4. 设计动机：Extend在验证之前发生，实现了"早期剪枝"——先验证筛选再扩展，而非先扩展再验证

  5. 计算成本模型:

  6. 做什么：用FLOPs精确量化不同 \(g\) 下的计算开销
  7. 核心思路：\(C_{total} = 2B_1 \frac{L}{g}[T(g-1+B_2)P_g + \alpha B_2 P_v]\)。增大 \(g\) → 验证次数 \(L/g\) 减少 → 验证FLOPs线性降低；同时生成FLOPs也降低（因为只需 \((g-1+B_2)/g\) 的分支开销）

  8. 设计动机：提供理论框架来精确分析不同 \(g\) 的成本，指导自适应策略

  9. 自适应 VG-Search 策略:

  10. 做什么：根据计算预算和任务属性动态选择最优 \(g\)
  11. 核心思路：在验证集MATH-250上profile不同 \((g, n)\) 组合的性能-计算曲线，找到Pareto最优配置。两种策略：(a) Budget-Adaptive：给定FLOPs预算选择最优 \(g\)；(b) Task-Adaptive：根据问题难度动态调整 \(g\)
  12. 设计动机：实验发现最优 \(g\) 随生成器能力、验证器质量、计算预算联合变化，没有一个固定值适合所有情况

实验关键数据

主实验

在MATH-500和AIME上评估：

配置 \(g=1\) (Beam) \(g=3\) (最优) 提升
Strong G + Small V (MATH-500) 87.5% ~88% +0.5%, FLOPs减少75%
Strong G + Small V (AIME) ~50% ~54% +4%, \(g=4\)最优
Medium G + Large V (MATH-500) ~83% ~84% (\(g=2\)) +1%
Weak G + Small V (MATH-500) 最优 下降 弱生成器需 \(g=1\)

自适应VG-Search最终结果： | 方法 | MATH-500 Acc | AIME Acc | FLOPs节省 | |------|-------------|----------|----------| | Beam Search (\(g=1\)) | 87.4% | 50.0% | 基线 | | Best-of-N | 86.0% | 46.7% | - | | Adaptive VG-Search | 90.5% | 53.6% | >52% |

消融实验

消融项 发现
随机PRM（无用验证器） 最优 \(g\) 显著增大（稀疏验证更好）
不同模型规模 最优 \(g\) 动态变化的结论在各规模上一致
不同难度级别 简单题小 \(g\) 足够；难题大 \(g\) 更优
DVTS vs VG-Search VG-Search在保持多样性的同时计算效率更高

关键发现

  • 强生成器偏好稀疏验证：Qwen2.5-Math-7B在 \(g=3\) 时性能最高，因为它能可靠地生成较长的正确推理片段，频繁验证反而在不成熟处截断引入噪声
  • 弱生成器需要频繁验证：Llama-3B在 \(g=1\) 时最优（MATH-500），但在更难的AIME上也转向稀疏验证
  • 最优 \(g\) 随计算预算变化：低预算时 \(g=1\)（积极剪枝）更好；高预算时 \(g>1\)（更广探索）更优
  • PRM分数稳定性：>50%的两步分数差<1%，直接验证了当前每步验证的冗余性

亮点与洞察

  • "思考步"的重新定义：当前以换行符定义的"一步"过于细粒度，不对应有意义的推理单元。更大的 \(g\) 定义了更大的语义连贯推理块，延迟验证可避免在不完整推理片段上注入噪声
  • 生成器-验证器协同的深层理解：验证频率应随两者能力比值动态调整。这不只是效率问题，还影响搜索的质量——过频验证扼杀了生成器的自主推理能力
  • 实用的计算节省策略：在不损失（甚至提升）性能的前提下节省52%+ FLOPs，对LLM推理的部署非常有价值

局限性 / 可改进方向

  • 仅在数学推理任务上验证，代码生成、逻辑推理等任务的最优 \(g\) 特性待探索
  • 自适应策略需要在验证集上预先profile，增加了设置成本
  • 仅考虑PRM作为验证器，ORM或LLM-as-verifier的情况未覆盖
  • \(g\) 在整个搜索过程中是固定的——理想情况下，\(g\) 应在搜索过程中随推理的进展动态调整（如开头用小 \(g\)，后期用大 \(g\)）

相关工作与启发

  • vs Beam Search: VG-Search的 \(g=1\) 退化为Beam Search，但 \(g>1\) 通过减少验证次数实现显著加速
  • vs Best-of-N: Best-of-N是 \(g=L\) 的极端情况，缺乏中间引导；VG-Search提供了连续的折中
  • vs DVTS: DVTS追求搜索多样性，VG-Search追求验证效率，两者正交可结合

评分

  • 新颖性: ⭐⭐⭐⭐ 验证粒度这一维度之前被忽视，值得系统研究。VG-Search的统一框架简洁优雅
  • 实验充分度: ⭐⭐⭐⭐⭐ 多模型、多数据集、多粒度的组合实验非常全面，消融控制变量严格
  • 写作质量: ⭐⭐⭐⭐⭐ 论文结构清晰，RQ驱动的叙述方式很好，图表设计精良
  • 价值: ⭐⭐⭐⭐⭐ 高度实用的洞察——只需调整一个超参数就能显著节省推理成本