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

2025-07-16 · Florian E. Dorner, Yatong Chen, André F. Cruz, Fanny Yang 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.

📄 PDF Abstract BibTeX arXiv:2507.12399

Code (0)

등록된 구현이 없습니다.

Diffusion ReRoll: Revisable Denoising for Robotic Sequential Prediction

2026-07-22 · Seonsoo Kim, Seongil Hong, Jun-Gill Kang arxiv

We propose Diffusion ReRoll, a diffusion-based framework for robotic sequential prediction that enables revisable denoising over horizons. Existing diffusion-based sequence predictors typically perform a single monotonic…

Test-time Verification via Optimal Transport: Coverage, ROC, & Sub-optimality

2025-10-21 · Arpan Mukherjee, Marcello Bullo, Debabrota Basu, Deniz Gündüz arxiv

While test-time scaling with verification has shown promise in improving the performance of large language models (LLMs), the role of the verifier and its imperfections remain underexplored. The effect of verification ma…

Quantifying Empirical Compute-Supervision Tradeoffs in RLVR

2026-05-24 · Ryo Mitsuhashi, Patrick Chen, Isabelle Tseng, Jasin Cekinmez 외 arxiv

Reinforcement learning with verifiable rewards (RLVR) has become a standard paradigm for post-training language models, but in practice, verifiers are rarely perfect. Recent theoretical work predicts that verifier noise …

Reinforcement Learning

Multi-Agent Verification: Scaling Test-Time Compute with Multiple Verifiers

2025-02-27 · Shalev Lifshitz, Sheila A. McIlraith, Yilun Du

By utilizing more computational resources at test-time, large language models (LLMs) can improve without additional training. One common strategy uses verifiers to evaluate candidate outputs. In this work, we propose a n…

Can graph neural network-based detection mitigate the impact of hardware imperfections?

2023-05-08 · Lamprini Mitsiou, Stylianos Trevlakis, Argiris Tsiolas, Dimitrios J. Vergados 외

Until recently, researchers used machine learning methods to compensate for hardware imperfections at the symbol level, indicating that optimum radio-frequency transceiver performance is possible. Nevertheless, such appr…

Decoder Graph Neural Network