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

• URL: http://arxiv.org/abs/2507.12399v2
• Date: Fri, 10 Oct 2025 07:34:34 GMT
• Title: ROC-n-reroll: How verifier imperfection affects test-time scaling
• Abstract summary: Test-time scaling aims to improve language model performance by leveraging additional compute during inference.<n>BoN and RS are techniques that make use of a verifier to enable test-time scaling.<n>We prove that the instance-level accuracy of these methods is precisely characterized by the geometry of the verifier's ROC curve.
• Score: 23.16719763215363
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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, 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.

Related papers

• Quantifying Empirical Compute-Supervision Tradeoffs in RLVR [0.15845117761091052]
  Recent theoretical work predicts that verifier noise affects the rate of learning but not its final outcome.<n>We test this prediction empirically by post-training Qwen2.5 (0.5B, 1.5B) with GRPO on GSM8K.<n>We find a structural asymmetry where false negatives monotonically degrade performance more quickly than false positives.
  arXiv  Detail & Related papers  (2026-05-24T20:28:12Z)
• Revisiting the Scaling Properties of Downstream Metrics in Large Language Model Training [11.179110411255708]
  We propose a direct framework to model the scaling of benchmark performance from the training budget.<n>Our results show that the direct approach extrapolates better than the previously proposed two-stage procedure.<n>We release the complete set of pretraining losses and downstream evaluation results.
  arXiv  Detail & Related papers  (2025-12-09T18:33:48Z)
• Understanding the Role of Training Data in Test-Time Scaling [56.12341509545198]
  We study the performance of test-time scaling for transformers trained on an in-context weight prediction task for linear regression.<n>We show that training on a diverse, relevant, and hard set of tasks results in best performance for test-time scaling.
  arXiv  Detail & Related papers  (2025-10-04T01:38:48Z)
• Scaling Test-Time Compute Without Verification or RL is Suboptimal [70.28430200655919]
  We show that finetuning LLMs with verifier-based (VB) methods based on RL or search is far superior to verifier-free (VF) approaches based on distilling or cloning search traces, given a fixed amount of compute/data budget.<n>We corroborate our theory empirically on both didactic and math reasoning problems with 3/8B-sized pre-trained LLMs, where we find verification is crucial for scaling test-time compute.
  arXiv  Detail & Related papers  (2025-02-17T18:43:24Z)
• On the Wasserstein Convergence and Straightness of Rectified Flow [54.580605276017096]
  Rectified Flow (RF) is a generative model that aims to learn straight flow trajectories from noise to data.<n>We provide a theoretical analysis of the Wasserstein distance between the sampling distribution of RF and the target distribution.<n>We present general conditions guaranteeing uniqueness and straightness of 1-RF, which is in line with previous empirical findings.
  arXiv  Detail & Related papers  (2024-10-19T02:36:11Z)
• The curious case of the test set AUROC [0.5242869847419834]
  We argue that considering scores derived from the test ROC curve alone gives only a narrow insight into how a model performs and its ability to generalise.
  arXiv  Detail & Related papers  (2023-12-19T17:40:58Z)
• The Lipschitz-Variance-Margin Tradeoff for Enhanced Randomized Smoothing [85.85160896547698]
  Real-life applications of deep neural networks are hindered by their unsteady predictions when faced with noisy inputs and adversarial attacks. We show how to design an efficient classifier with a certified radius by relying on noise injection into the inputs. Our novel certification procedure allows us to use pre-trained models with randomized smoothing, effectively improving the current certification radius in a zero-shot manner.
  arXiv  Detail & Related papers  (2023-09-28T22:41:47Z)
• Neural Operator Variational Inference based on Regularized Stein Discrepancy for Deep Gaussian Processes [23.87733307119697]
  We introduce Neural Operator Variational Inference (NOVI) for Deep Gaussian Processes. NOVI uses a neural generator to obtain a sampler and minimizes the Regularized Stein Discrepancy in L2 space between the generated distribution and true posterior. We demonstrate that the bias introduced by our method can be controlled by multiplying the divergence with a constant, which leads to robust error control and ensures the stability and precision of the algorithm.
  arXiv  Detail & Related papers  (2023-09-22T06:56:35Z)
• Instance-based Learning with Prototype Reduction for Real-Time Proportional Myocontrol: A Randomized User Study Demonstrating Accuracy-preserving Data Reduction for Prosthetic Embedded Systems [0.0]
  This work presents the design, implementation and validation of learning techniques based on the kNN scheme for gesture detection in prosthetic control. The influence of parameterization and varying proportionality schemes is analyzed, utilizing an eight-channel-sEMG armband.
  arXiv  Detail & Related papers  (2023-08-21T20:15:35Z)
• Collapsed Inference for Bayesian Deep Learning [36.1725075097107]
  We introduce a novel collapsed inference scheme that performs Bayesian model averaging using collapsed samples. A collapsed sample represents uncountably many models drawn from the approximate posterior. Our proposed use of collapsed samples achieves a balance between scalability and accuracy.
  arXiv  Detail & Related papers  (2023-06-16T08:34:42Z)
• Learning for Transductive Threshold Calibration in Open-World Recognition [83.35320675679122]
  We introduce OpenGCN, a Graph Neural Network-based transductive threshold calibration method with enhanced robustness and adaptability. Experiments across open-world visual recognition benchmarks validate OpenGCN's superiority over existing posthoc calibration methods for open-world threshold calibration.
  arXiv  Detail & Related papers  (2023-05-19T23:52:48Z)
• Bridging Precision and Confidence: A Train-Time Loss for Calibrating Object Detection [58.789823426981044]
  We propose a novel auxiliary loss formulation that aims to align the class confidence of bounding boxes with the accurateness of predictions. Our results reveal that our train-time loss surpasses strong calibration baselines in reducing calibration error for both in and out-domain scenarios.
  arXiv  Detail & Related papers  (2023-03-25T08:56:21Z)
• Neural Inference of Gaussian Processes for Time Series Data of Quasars [72.79083473275742]
  We introduce a new model that enables it to describe quasar spectra completely. We also introduce a new method of inference of Gaussian process parameters, which we call $textitNeural Inference$. The combination of both the CDRW model and Neural Inference significantly outperforms the baseline DRW and MLE.
  arXiv  Detail & Related papers  (2022-11-17T13:01:26Z)
• Fast and Accurate Error Simulation for CNNs against Soft Errors [64.54260986994163]
  We present a framework for the reliability analysis of Conal Neural Networks (CNNs) via an error simulation engine. These error models are defined based on the corruption patterns of the output of the CNN operators induced by faults. We show that our methodology achieves about 99% accuracy of the fault effects w.r.t. SASSIFI, and a speedup ranging from 44x up to 63x w.r.t.FI, that only implements a limited set of error models.
  arXiv  Detail & Related papers  (2022-06-04T19:45:02Z)
• Error-based Knockoffs Inference for Controlled Feature Selection [49.99321384855201]
  We propose an error-based knockoff inference method by integrating the knockoff features, the error-based feature importance statistics, and the stepdown procedure together. The proposed inference procedure does not require specifying a regression model and can handle feature selection with theoretical guarantees.
  arXiv  Detail & Related papers  (2022-03-09T01:55:59Z)
• Leveraging Unlabeled Data to Predict Out-of-Distribution Performance [63.740181251997306]
  Real-world machine learning deployments are characterized by mismatches between the source (training) and target (test) distributions. In this work, we investigate methods for predicting the target domain accuracy using only labeled source data and unlabeled target data. We propose Average Thresholded Confidence (ATC), a practical method that learns a threshold on the model's confidence, predicting accuracy as the fraction of unlabeled examples.
  arXiv  Detail & Related papers  (2022-01-11T23:01:12Z)
• The $f$-divergence and Loss Functions in ROC Curve [2.9823962001574182]
  Given two data distributions and a test score function, the Receiver Operating Characteristic (ROC) curve shows how well such a score separates two distributions. Can the ROC curve be used as a measure of discrepancy between two distributions? This paper shows that when the data likelihood ratio is used as the test score, the arc length of the ROC curve gives rise to a novel $f$-divergence measuring the differences between two data distributions.
  arXiv  Detail & Related papers  (2021-10-18T23:12:35Z)
• Compressed Sensing Measurement of Long-Range Correlated Noise [1.6328866317851183]
  Long-range correlated errors can severely impact the performance of NISQ devices. We propose a compressed sensing method for detecting two-qubit correlated dephasing errors.
  arXiv  Detail & Related papers  (2021-05-26T14:47:26Z)
• Insta-RS: Instance-wise Randomized Smoothing for Improved Robustness and Accuracy [9.50143683501477]
  Insta-RS is a multiple-start search algorithm that assigns customized Gaussian variances to test examples. Insta-RS Train is a novel two-stage training algorithm that adaptively adjusts and customizes the noise level of each training example. We show that our method significantly enhances the average certified radius (ACR) as well as the clean data accuracy.
  arXiv  Detail & Related papers  (2021-03-07T19:46:07Z)
• Calibration of Neural Networks using Splines [51.42640515410253]
  Measuring calibration error amounts to comparing two empirical distributions. We introduce a binning-free calibration measure inspired by the classical Kolmogorov-Smirnov (KS) statistical test. Our method consistently outperforms existing methods on KS error as well as other commonly used calibration measures.
  arXiv  Detail & Related papers  (2020-06-23T07:18:05Z)
• The Right Tool for the Job: Matching Model and Instance Complexities [62.95183777679024]
  As NLP models become larger, executing a trained model requires significant computational resources incurring monetary and environmental costs. We propose a modification to contextual representation fine-tuning which, during inference, allows for an early (and fast) "exit" We test our proposed modification on five different datasets in two tasks: three text classification datasets and two natural language inference benchmarks.
  arXiv  Detail & Related papers  (2020-04-16T04:28:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.