ROC-N-REROLL - HOW VERIFIER IMPERFECTION AFFECTS TEST-TIME SCALING - Paper

Aug 27, 2026

Test-time scaling improves language model performance by using extra compute during inference. Many approaches rely on a verifier via Best-of-N sampling and Rejection Sampling, yet verifier imperfection lacks a clear theoretical account. This work proves that instance-level accuracy is determined by the geometry of the verifier’s ROC curve. Experiments with Qwen and LLaMA models on GSM8K and MATH500 confirm: for concave ROC curves, RS beats BoN at fixed compute and both meet as compute grows large.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages42

Reading Time1 h 46 min

AccessFree to download

Introduction

Test-time scaling approaches

Role and limits of imperfect verifiers

Contributions overview

ROC-N-REROLL: HOW VERIFIER IMPERFECTION AFFECTS TEST-TIME SCALING Florian E. Dorner 1,2,3,4 , Yatong Chen* 3,4 , Andr F. Cruz* 3,4 , and Fanny Yang 1 1ETH Z¨urich, 2Max Planck ETH Center for Learning Systems, 3Max Planck Institute for Intelligent Systems, T¨ubingen, 4T¨ubingen AI Center 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 averifier 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 high-compute 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 (OpenAI, 2024) . 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 (Muennighoff et al., 2025; Guo et al., 2025; Kimi et al., 2025; Qu et al., 2025; Aggarwal and Welleck, 2025; Zaremba et al., 2025; Kavukcuoglu, 2025) . 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’soutputs—but at different stages of the pipeline. Resampling methods employ a verifier at testtime to filter or rank candidate responses after they are generated (Cobbe et al., 2021) . 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 asa reward for post-training with reinforcement learning (RL) (Guo et al., 2025) . 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 groundtruth 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 (Brown et al., 2024; Schaeffer et al., 2025) . In most domains, however, access to a perfectly accurate verifier is not realistic. errors may slip through: insecure code can pass static tests (Zhou et al., 2024), and flawed reasoning can arrive at the correct numerical answer (Petrov et al., 2025) . More broadly, there has been an increasing interest in using another language model as a verifier (Huang et al., 2025a; Songet al., 2025), an approach that can be applied to any domain, but has been shown to have far from perfect accuracy (Bavaresco et al., 2025; Dorner et al., 2025) . Despite growing interest in verifier-based test-time scaling, the relationship between scaling behavior and the properties of imperfect verifiers remains poorly understood. This work addresses this * Equal contribution. Code: [https://github.com/socialfoundations/roc-n-reroll](https://github.com/socialfoundations/roc-n-reroll) 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

FAQs

What does ROC-N-REROLL study about verifier imperfection in test-time scaling?

It analyzes how the accuracy of verifier-based methods changes when the verifier is imperfect, showing that instance-level performance is governed by the verifier ROC geometry.

How do Rejection Sampling (RS) and Best-of-N (BoN) relate through the verifier ROC curve?

For a fixed query, both methods’ accuracy depends on the generator’s initial accuracy and the verifier’s ROC curve, not on finer implementation details.

Why can’t high-compute performance be reliably predicted from low-compute behavior?

The paper shows extrapolation from early scaling observations is generally impossible, because different verifiers can diverge at higher numbers of test-time samples even when low-compute accuracy matches.

Aug 27, 2026

Upload by Lucas Martin