Research map / Large language models / Reasoning and chain of thought
Rethinking Optimal Verification Granularity for Compute-Efficient Test-Time Scaling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes VG-Search, a unified beam-search/Best-of-N algorithm with a tunable verification granularity g, and adaptive strategies that choose g per difficulty and compute budget to improve accuracy-FLOPs trade-offs on math reasoning.
Problem
Verifier-guided test-time scaling typically verifies at a fixed granularity (every newline-delimited step), which is heuristic and static; its optimality for accuracy-compute scaling is unknown.
Approach
Introduce a verification granularity parameter g that interpolates between Beam Search (g=1) and Best-of-N (g=full solution), with a cheaper branch design where only top beams are extended, and adaptively select g by compute budget and task difficulty.
Key results
- Adaptive VG-Search (AM-g) reaches 90.1% on MATH-500 at n=64 vs 87.0% for Beam Search, a gain of up to 3.1% over Beam Search and 3.6% over Best-of-N.
- CM-g at n=128 (val-tuned) reaches 89.9% accuracy using 11086 FLOPs, about 46% of the baseline budget (24021 FLOPs).
- Optimal g is strategy-dependent: strong generators (Qwen2.5-Math-7B) favor g=3 which beats g=1 by about 4% on MATH-500, while weak Llama-3B favors g=1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Select granularity with AM-g rather than use fixed Beam Search | VG-Search on Qwen2.5-Math-7B with Skywork-o1-1.5B · MATH-500, n=64 | accuracy: 87.0 -> 90.1 | Helped |
| Select granularity with CM-g rather than use fixed Beam Search | VG-Search on Qwen2.5-Math-7B with Skywork-o1-1.5B · MATH-500, n=64 | FLOPs: 12010 -> 5543 | Helped |
| Tune CM-g granularity on MATH-250 rather than use fixed Beam Search | VG-Search on Qwen2.5-Math-7B with Skywork-o1-1.5B · MATH-500, n=128 | FLOPs: 24021 -> 11086 | Helped |
| Use sparse verification (g>1) instead of g=1 as sample budget increases | VG-Search with Qwen-Math-7B and Skywork-o1-1.5B PRM · MATH-500, n=64 | accuracy: 86.20 $\pm$ 0.33 -> 88.27 $\pm$ 0.34 | Helped |
| Use sparse verification (g>1) instead of g=1 as sample budget increases | VG-Search with Qwen-Math-7B and Skywork-o1-1.5B PRM · MATH-500, n=128 | accuracy: 86.67 $\pm$ 0.19 -> 88.47 $\pm$ 0.32 | Helped |
| Use sparse verification (g>1) rather than dense verification at low sample count | VG-Search with Qwen-Math-7B and Skywork-o1-1.5B PRM · MATH-500, n=4 | accuracy: 84.13 $\pm$ 0.50 -> 80.40 $\pm$ 0.43 | Hurt |
| Replace the standard PRM with a random-score noisy PRM (ablation) | VG-Search · Mathematical reasoning tasks | accuracy | Helped |
Surprising findings
- Sparser verification (larger g) can improve accuracy while reducing compute, challenging the conventional per-step verification convention.
- A stronger verifier used sparsely can outperform a weaker verifier used frequently at high compute budgets.
Limitations
- The chosen granularity g is fixed for an entire problem instance and does not adapt step-by-step during generation.
- Adaptive selection requires a validation set and tuning of g per model, task, and budget.
- Experiments focus primarily on math reasoning with a few generator-verifier pairs; the code generation check is limited.
Experimental setup
Datasets: MATH MATH-500 (sampled) AIME22-24
Benchmarks: MATH-500 AIME HumanEval
Metrics: accuracy FLOPs pass@1
Baselines: Beam Search DVTS Best-of-N
Builds on: Beam Search Best-of-N sampling DVTS search-and-learn (HuggingFace)
Closest papers by meaning
- T1: Tool-integrated Verification for Test-time Compute Scaling in Small Language Models (ICLR 2026 · similarity 0.92)
- Variation in Verification: Understanding Verification Dynamics in Large Language Models (ICLR 2026 · similarity 0.90)
- Sample, Scrutinize and Scale: Effective Inference-Time Search by Scaling Verification (ICML 2025 · similarity 0.90)
- Scaling Test-Time Compute Without Verification or RL is Suboptimal (ICML 2025 · similarity 0.90)
- Every Rollout Counts: Optimal Resource Allocation for Efficient Test-Time Scaling (NeurIPS 2025 · similarity 0.90)
- Test-Time Scaling in the Wild: Why Exploitation, Not Exploration, Is the Bottleneck (NeurIPS 2026 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.