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

Aug 27, 2026

Upload by Anda

Test-time scaling improves language model performance by spending extra compute during inference, and many methods rely on a verifier to enable resampling such as Best-of-N and Rejection Sampling. This work develops theory for the impact of verifier imperfection, proving instance-level accuracy is determined by the geometry of the verifier’s ROC curve. Experiments with Qwen and LLaMA verifiers on GSM8K and MATH500 confirm that for concave ROC curves RS beats BoN at fixed compute, while both match in the infinite-compute limit. The paper also shows high-compute behavior cannot be reliably inferred from low-compute observations.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages47

Reading Time1 h 58 min

AccessFree to download

Introduction

Two approaches to test-time scaling

Verifier reliability and theoretical gap

Main contributions

ROC-curve characterization of accuracy

RS vs BoN under concave ROC curves

Empirical validation on GSM8K and MATH500

arXiv :2507 . 12399v3 [ cs .LG] 17 Aug 2026 ROC-n-reroll: How verifier imperfection affects test-time scaling Florian E. Dorner 1,2,3,4 , Yatong Chen*3,4 , Andr´e F. Cruz*3,4 , and Fanny Yang 1 1 ETH Z¨urich, 2 Max Planck ETH Center for Learning Systems, 3 Max Planck Institute for Intelligent Systems, T¨ubingen, 4 T¨ubingen AI Center August 18, 2026 Abstract 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, for any query with a concave verifier ROC curve, 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 highcompute performance of either method based on observations in the low-compute regime. 1 Introduction Just as further scaling up large language model (LLM) pre-training started to show diminishing returns, OpenAI released o1, vastly improving upon the state-of-the-art on many challenging benchmarks [1] . Instead of spending more compute on pre-training, o1 was the first flagship LLM to prominently improve performance by spending additional compute at test-time. Since then, interest in test-time scaling has exploded [2–8] . There are two broad approaches to test-time scaling: resampling and “reasoning”. Both approaches typically use a verifier—a scoring mechanism that evaluates the quality or correctness of an LLM’s outputs—but at different stages of the pipeline. Resampling methods employ a verifier at test-time to filter or rank candidate responses after they are generated [9] . In contrast, reasoning methods employ a verifier to modify how the LLM generates outputs, usually increasing output quality at the cost of increased response length. Most prominently, the verifier can be used as a reward for post-training with reinforcement learning (RL) [3] . In practice, both test-time scaling approaches have primarily been successful in domains where a reliable oracle verifier can be implemented—e.g., coding using unit tests and math using ground-truth numerical solutions. As such, previous theoretical analysis has focused on the scaling behavior of pass@N, the probability that at least one of the N candidate responses is correct [10, 11] . In most domains, however, access to a perfectly accurate verifier is not realistic. Errors may slip through: insecure code can pass static tests [12], and flawed reasoning can arrive at the correct numerical answer [13] . More broadly, there has been an increasing interest in using another language model as a verifier [14, 15], an approach that can be applied to any domain, but has been shown to have far from perfect accuracy [16, 17] . * Equal contribution. True Pos itive Rate 1.00 0.75 0.50 0.25 0.00 Verifier ROC 0.0 0.5 1.0 False Positive Rate Accuracy 0.8 0.6 0.4 0.2 Rejection Sampling 5 10 15 Number of Generations 0.8 0.6 0.4 0.2 Best-of-N | | | |
| | | --- | --- | --- | --- | --- | | | | | | | | | | | Q 32B | | | | |
| Q 14B
Q 4B | | | | | | Predicted | | | | | | | | | | | | | | 0 10 20 30 Number of Generations Figure 1: Empirical performance (markers) of RS (middle) and BoN (right) on GSM8K test question 58, overlaid with theoretical predictions (lines) . Different verifiers scale similarly at first, but then diverge. RS matches BoN accuracy, using less

FAQs

Can high-compute performance be predicted from low-compute observations?

No; the paper argues that extrapolation from the low-compute regime to high-compute performance is generally impossible for these methods.

Aug 27, 2026

Upload by Anda