Selection Under an Imperfect Verifier: An Extreme-Value Theory of Test-Time Compute

Abstract

Test-time procedures such as best-of-n sampling, reranking and verifier-guided search all share one structure: many candidates are drawn, one is selected by a learned score, and the user receives the true quality of the selected candidate. The score and the truth are different random variables, so the delivered quality is a concomitant of an extreme order statistic rather than an extreme order statistic itself. We develop the consequences of that observation. First, whenever the regression of quality on verifier score is affine, the entire gain curve collapses to g(n)=a+b E[S_{n:n}], which is increasing and discretely concave; for jointly Gaussian pairs this yields the scaling law g(n)=mu_Q+rho sigma_Q sqrt(2 log n) (1+o(1)), explaining the log-linear best-of-n curves reported empirically and identifying their slope as the verifier correlation. Second, we prove a sharp dichotomy for overoptimisation: if the verifier error is long-tailed and independent of quality, then g(n) -> E[Q], while g(n)>E[Q] for every n >= 2, so the optimal sample count n^* is necessarily finite and more test-time compute eventually destroys all value. The controlling quantity is the upper-tail dependence of the (quality, score) copula: we exhibit verifiers with identical Kendall tau=0.50 whose best-of-512 quality differs by 0.79 standard deviations. Third, we give an unbiased U-statistic estimator of the whole gain curve from a single pilot pool, and use it to allocate a fixed sampling budget across heterogeneous problems; greedy allocation is exactly optimal under concavity, and the plug-in version attains the utility of uniform allocation using 1.22-1.50x less compute. We then test the theory on 128,000 real completions - MATH-500 solved by Llama-3.2-1B-Instruct and scored by an 8B process reward model. The predicted reversal appears exactly where predicted: the verifier with negligible within-problem signal peaks at n^*=4 and then loses a seventh of its accuracy, with a paired bootstrap interval excluding zero, while stronger verifiers merely saturate. The same data refute one of our own conjectures - that upper-tail dependence is the summary to report - since binary correctness has no upper tail to estimate; we report that and withdraw the claim. What survives is sharper: pooled AUC predicts delivered quality well on real data yet is negatively related to it when verifiers lack within-problem signal, because it rewards separating easy problems from hard ones, which best-of-n can never exploit.