Research map / Large language models / Reasoning and chain of thought

ROC-n-reroll: How verifier imperfection affects test-time scaling

ICLR 2026 · Large language models › Reasoning and chain of thought · approach: Test-time compute scaling · 0 citations (OpenAlex)

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.

Shows that per-query accuracy of rejection sampling and Best-of-N under an imperfect verifier is fully determined by the verifier's ROC curve, and derives RS dominance and non-extrapolability results, validated on GSM8K and MATH500 with Qwen3 and Llama models.

Problem

Test-time scaling with imperfect verifiers lacks theory: it is unclear how verifier errors affect the accuracy and compute scaling of Best-of-N and rejection sampling, and whether low-compute performance predicts high-compute performance.

Approach

Characterizes RS and BoN accuracy exactly via the verifier's ROC curve: RS accuracy is a function of the ROC slope/geometry (local at the top-right for low compute, at the origin for high compute), and BoN accuracy is an integral over the ROC curve. Concave ROC implies RS beats BoN at fixed compute, both converge to the same high-compute limit, and extrapolation from low compute is impossible.

Key results

• For concave ROC curves, rejection sampling outperforms Best-of-N at fixed compute on GSM8K and MATH500 with Qwen3 and Llama models, while the gap vanishes at large compute.
• Per-query predictions from the ROC-based formulas match simulated RS and BoN accuracies with absolute errors mostly below one percentage point (Llama-3.2-3B, GSM8K question 2).
• Verifiers with identical low-compute performance (e.g., Qwen3-4B vs Qwen3-32B on GSM8K) diverge at high compute, showing low-compute scaling does not predict high-compute performance.

Surprising findings

• Verifiers that scale identically at small compute can reach very different accuracy limits at large compute, so extrapolation of scaling curves is unreliable.

Limitations

• Theory assumes per-query fixed generator and verifier; aggregate results rely on heuristic thresholds and are not fully covered by the theory.
• RS can run indefinitely for hard queries with high constant thresholds, requiring hybrid or capped variants.

Experimental setup

Datasets: GSM8K MATH500

Benchmarks: GSM8K MATH500 GPQA HumanEval+

Metrics: accuracy compute (expected samples)

Baselines: Best-of-N Rejection sampling Majority voting

Builds on: pass@N scaling analysis KL-regularized RL Best-of-N theory

Closest papers by meaning

• Test-time Verification via Optimal Transport: Coverage, ROC, & Sub-optimality (ICLR 2026 · similarity 0.90)
• Sample Complexity and Representation Ability of Test-time Scaling Paradigms (ICLR 2026 · similarity 0.87)
• Consilience for Verifier-Free Test-Time Scaling (NeurIPS 2026 · similarity 0.87)
• Scaling Test-Time Compute Without Verification or RL is Suboptimal (ICML 2025 · similarity 0.87)
• Understanding the Role of Training Data in Test-Time Scaling (ICLR 2026 · similarity 0.86)
• ATTS: Asynchronous Test-Time Scaling via Conformal Prediction (ICLR 2026 · similarity 0.86)