Research map / Large language models / Reasoning and chain of thought
Scaling Test-Time Compute Without Verification or RL is Suboptimal
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.
Proves and empirically shows that verifier-based (RL or best-of-N with trained verifier) finetuning scales test-time compute better than verifier-free distillation/SFT on search traces, under heterogeneity and anti-concentration conditions.
Problem
Which finetuning paradigm makes more efficient use of test-time compute as the token budget grows: verifier-based methods (RL with 0/1 rewards or trained verifiers, search) or verifier-free methods (distilling or cloning search/thinking traces)?
Approach
Shows an information-theoretic lower bound (H/sqrt(n)) for any verifier-free expert-cloning method under base-policy reward heterogeneity, and an upper bound (H/n) for a simple verifier-based pessimistic-verifier RL method when the base policy is anti-concentrated, yielding a provable asymptotic separation in test-time scaling.
Key results
- On the didactic task with n=2^10, SFT's gap to the expert grows with test-time budget H while RL nearly matches the expert until much higher H.
- On MATH with Llama-3.1-8B, best-of-N against a trained verifier scales test-time compute by about 8x over SFT on stitched search traces at fixed data budget 2^14.
- Verifier-based BoN improves over budget-forced s1 under compute-matched evaluation even when training data is fixed.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use verifier-guided Best-of-N instead of verifier-free SFT on stitched search traces | Llama-3.1/3.2 8B/3B Instruct · MATH | test-time compute scaling: 8× | Helped |
| Use verifier-guided Best-of-N instead of verifier-free SFT on stitched search traces | Llama-3.1/3.2 8B/3B Instruct · MATH | data efficiency: 6× | Helped |
| Use verifier-guided Best-of-N instead of budget-constrained verifier-free distillation | s1 · MATH500 and AIME | performance | Helped |
| Use verifier-free SFT rather than verifier-guided Best-of-N on low-heterogeneity problems (ablation) | Llama-3.1/3.2 8B/3B Instruct · MATH, low-heterogeneity bucket | performance | Helped |
| Use verifier-free SFT rather than verifier-guided Best-of-N on high-heterogeneity problems (ablation) | Llama-3.1/3.2 8B/3B Instruct · MATH, high-heterogeneity bucket | performance | Hurt |
| Scale verifier-based RL rather than verifier-free SFT as the data budget increases (ablation) | GPT2-xl didactic setup · Planted subsequence problem | performance | Helped |
| Reduce base-policy heterogeneity (ablation) | GPT2-xl didactic setup · Planted subsequence problem | SFT suboptimality gap | Helped |
| Reduce base-policy heterogeneity (ablation) | GPT2-xl didactic setup · Planted subsequence problem | performance | Mixed |
| Scale test-time token budget (ablation) | Verifier-free SFT on stitched search traces · MATH | accuracy gap versus Best-of-N | Hurt |
| Scale training data and test-time compute together (ablation) | Best-of-N versus verifier-free SFT · MATH | reward gap: Ω(√H) | Helped |
Surprising findings
- Verifier-free SFT outperforms verifier-based BoN on problems with low heterogeneity, where VF generalizes well.
- The gap between SFT and expert policy worsens as test-time budget grows, because per-prompt heterogeneity scales with H.
Limitations
- Verifier-based analysis restricted to sparse bi-level 0/1 rewards; dense or process rewards not analyzed.
- Experiments limited to didactic setting and MATH/AIME with 3B/8B models; RL online experiments on MATH not run at high H due to compute.
- Verifier accuracy degrades at higher token budgets, causing reward hacking in RL.
Experimental setup
Datasets: MATH planted subsequence (synthetic)
Benchmarks: MATH AIME planted subsequence (didactic)
Metrics: normalized bi-level reward J_r accuracy
Baselines: SFT on stitched search traces s1 budget forcing best-of-N with verifier
Builds on: planted subsequence problem STaR s1 budget forcing best-of-N sampling
Closest papers by meaning
- Optimizing Test-Time Compute via Meta Reinforcement Finetuning (ICML 2025 · similarity 0.91)
- Consilience for Verifier-Free Test-Time Scaling (NeurIPS 2026 · similarity 0.91)
- Rethinking Fine-Tuning when Scaling Test-Time Compute: Limiting Confidence Improves Mathematical Reasoning (NeurIPS 2025 · similarity 0.90)
- Rethinking Optimal Verification Granularity for Compute-Efficient Test-Time Scaling (NeurIPS 2025 · similarity 0.90)
- CodeScaler: Scaling Code LLM Training and Test-Time Inference via Reward Models (NeurIPS 2026 · similarity 0.90)
- Sample, Scrutinize and Scale: Effective Inference-Time Search by Scaling Verification (ICML 2025 · similarity 0.90)
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.