mlsanityData to 14 Oct 2026

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

arXiv 2507.12399 ↗First posted 16 Jul 2025cs.LG stat.MLcited by 12

On the map: LLM reasoning → Test-time compute and efficient thinking

Abstract (arXiv)

Test-time scaling aims to improve language model performance by leveraging additional compute during inference. Many works have empirically studied techniques such as Best-of-N (BoN) and Rejection Sampling (RS) that make use of a verifier to enable test-time scaling. However, to date there is little theoretical understanding of how verifier imperfection affects performance -- a gap we address in this work. Specifically, we prove that the instance-level accuracy of these methods is precisely characterized by the geometry of the verifier's ROC curve. Our theory has two important takeaways, confirmed by experiments with Qwen and LLama models on GSM8K and MATH500. First, RS outperforms BoN for fixed compute, while both methods converge to the same accuracy in the infinite-compute limit. Second, it is generally impossible to predict the high-compute performance of either method based on observations in the low-compute regime.

Key facts. Cited by 12 papers in the map (data through 14 Oct 2026). Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning. Builds on 44 of its 69 references that are in the map. First posted on arXiv 16 Jul 2025.

Builds on

44 of 69 references.

Closest ancestors · 6

Same direction, newest first

  1. 2025A Survey on Test-Time Scaling in Large Language Models: What, How, Where, and How Well?31 Mar
  2. 2025L1: Controlling How Long A Reasoning Model Thinks With Reinforcement Learning6 Mar
  3. 2025s1: Simple test-time scaling31 Jan
  4. 2024Provable Scaling Laws for the Test-Time Compute of Large Language Models29 Nov
  5. 2024Theoretical guarantees on the best-of-n alignment policy3 Jan
  6. 2022STaR: Bootstrapping Reasoning With Reasoning28 Mar

Other references · 38

  1. 2024The Llama 3 Herd of Modelscited by 14,715
  2. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  3. 2021Training Verifiers to Solve Math Word Problemscited by 10,109
  4. 2025Qwen3 Technical Reportcited by 8,820
  5. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 8,065
  6. 2021Measuring Mathematical Problem Solving With the MATH Datasetcited by 5,371
  7. 2022Large Language Models are Zero-Shot Reasonerscited by 4,374
  8. 2023GPQA: A Graduate-Level Google-Proof Q&A Benchmarkcited by 2,879
  9. 2022Competition-Level Code Generation with AlphaCodecited by 1,462
  10. 2023Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generationcited by 1,391
  11. 2025Kimi k1.5: Scaling Reinforcement Learning with LLMscited by 1,210
  12. 2022Scaling Laws for Reward Model Overoptimizationcited by 1,095
26 more
  1. 2024Large Language Monkeys: Scaling Inference Compute with Repeated Samplingcited by 991
  2. 2025Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?cited by 982
  3. 2022Solving math word problems with process- and outcome-based feedbackcited by 901
  4. 2025AlphaEvolve: A coding agent for scientific and algorithmic discoverycited by 867
  5. 2023Just Ask for Calibration: Strategies for Eliciting Calibrated Confidence Scores from Language Models Fine-Tuned with Human Feedbackcited by 812
  6. 2025SimpleRL-Zoo: Investigating and Taming Zero Reinforcement Learning for Open Base Models in the Wildcited by 511
  7. 2023Scaling Relationship on Learning Mathematical Reasoning with Large Language Modelscited by 427
  8. 2024LLMs instead of Human Judges? A Large Scale Empirical Study across 20 NLP Evaluation Taskscited by 243
  9. 2023Reward Model Ensembles Help Mitigate Overoptimizationcited by 231
  10. 2025When More is Less: Understanding Chain-of-Thought Length in LLMscited by 183
  11. 2025A Minimalist Approach to LLM Reasoning: from Rejection Sampling to Reinforcecited by 145
  12. 2025Optimizing Test-Time Compute via Meta Reinforcement Fine-Tuningcited by 123
  13. 2024BoNBoN Alignment for Large Language Models and the Sweetness of Best-of-n Samplingcited by 121
  14. 2024Self-Improvement in Language Models: The Sharpening Mechanismcited by 104
  15. 2025Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignmentcited by 97
  16. 2022Solving Math Word Problems via Cooperative Reasoning induced Language Modelscited by 77
  17. 2025Proof or Bluff? Evaluating LLMs on 2025 USA Math Olympiadcited by 74
  18. 2025Trading Inference-Time Compute for Adversarial Robustnesscited by 61
  19. 2022Adversarial Training for High-Stakes Reliabilitycited by 60
  20. 2024Limits to scalable evaluation at the frontier: LLM as Judge won't beat twice the datacited by 51
  21. 2025How Do Large Language Monkeys Get Their Power (Laws)?cited by 43
  22. 2024Genie: Achieving Human Parity in Content-Grounded Datasets Generationcited by 31
  23. 2024Evaluating language models as risk scorescited by 27
  24. 2024Comparison of Static Application Security Testing Tools and Large Language Models for Repo-level Vulnerability Detectioncited by 18
  25. 2024Lower-Left Partial AUC: An Effective and Efficient Optimization Metric for Recommendationcited by 9
  26. 2022Human-Guided Fair Classification for Natural Language Processingcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 10.

12 papers.

  1. 2026Delay, Plateau, or Collapse: Evaluating the Impact of Systematic Verification Error on RLVRcited by 7
  2. 2025Test-time Verification via Optimal Transport: Coverage, ROC, & Sub-optimalitycited by 4
  3. 2025Balanced Accuracy: The Right Metric for Evaluating LLM Judges -- Explained through Youden's J statisticcited by 4
  4. 2026Beyond Consensus: Trace-Level Synthesis in Mixture of Agentscited by 4
  5. 2026Oracle Gap and Signal Fidelity: A Fixed-Pool Diagnostic for Test-Time Collaborationcited by 2
  6. 2026Verify, Repair, Repeat, or Stop? Robust Stopping for Noisy Verify-Repair Loops in LLM Agentscited by 2
  7. 2026The geometry of AI validation: From structural blindness to reusable auditscited by 1
  8. 2026Large Language Models Explore by Latent Distillingcited by 0
  9. 2026Refining Over Resampling: Test-Time Self-Correction for LLM Reasoningcited by 0
  10. 2026Diagnosing Sampled LLM Reasoning in Formal Geometry: Coverage, Realization, and Validity Evidencecited by 0
  11. 2026From Discovery to Decision: Finite-Budget Recoverability in LLM Votingcited by 0
  12. 2026Checking the Checkers: A Synthesis of Verifier Noise and Robustness in RLVRcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Parallel Test-Time Scaling with Multi-Sequence Verifiers
  2. 2025Trust but Verify! A Survey on Verification Design for Test-time Scaling
  3. 2025Scaling Flaws of Verifier-Guided Search in Mathematical Reasoning
  4. 2025Sample Complexity and Representation Ability of Test-time Scaling Paradigms
  5. 2026Consilience for Verifier-Free Test-Time Scaling
  6. 2026Predicting Inference-Time Scaling Gains from Labeled Validation-Set Output Statistics
  7. 2026SCATR: Simple Calibrated Test-Time Ranking
  8. 2025Adaptive Rectification Sampling for Test-Time Compute Scaling