Test-Time Scaling Is Bounded by Verification, Not Generation

Test-time compute methods draw many candidate solutions and return one. What sampling makes available, coverage, is fixed by single-sample accuracy; what a user receives depends on selection, and selection is governed by other quantities. We prove that a verifier's AUC does not determine its best-of-$k$ accuracy: with one correct candidate among $k$, a verifier of AUC $a$ selects it with probability anywhere between $a^{k-1}$ and $a$, so no verifier can recover a lone correct answer more often than its AUC, and the AUC needed for a fixed accuracy rises with the budget. For voting, whose success depends on whether the most common wrong answer outnumbers the right one, we show that the usual way of measuring difficulty, stratifying problems on the same samples used for evaluation, understates voting on hard problems in every model we test, enough to make it look worse than random for some, and overstates it on easy ones. With a held-out protocol across six models from three families, 1,400 problems and 32 samples each, real verifiers sit well inside the interval, so that their AUC leaves best-of-8 accuracy undetermined over tens of points, voting's held-out gains follow its error condition, and 32 samples predict coverage and reward-model accuracy at 128, including where selection levels off. On the 10,000 samples per problem released by Brown et al., the voting condition predicts the height of the voting plateau to within a point for 8B and 70B models. On hard problems, even a trained process reward model leaves 38–66% of the correct answers added by doubling the budget unselected. Sampling has outrun our ability to tell which sample is right.