Best-of-N Can Recover After Decline: Sharp Reversals and Audit Complexity

A decline in Best-of-N utility at small $N$ does not imply that utility cannot recover at larger $N$, even with smooth calibration and exact knowledge of the early utility curve. For every finite horizon $H\ge 64$, we construct a fixed generator–verifier law whose utility first peaks at $N=2$, decreases at $N=3$, yet exceeds the first peak by at least $0.15$ at $N=H$. We explain this behavior through a task-conditional rank transform: for every $N$, the expected utility is obtained by averaging a single calibration profile against a $\mathrm{Beta}(N,1)$ density. This representation lets us characterize the shape of the entire Best-of-N curve. In particular, the ordered sign changes of the calibration profile sharply bound the number of utility reversals, while smoothness alone imposes no finite bound. We then study how much evaluation is required to determine whether utility later recovers. For an explicit smooth recovery/no-recovery pair, passive evaluation requires order-$H$ utility labels at fixed confidence, whereas directly labeling selected winners at the relevant breadths requires a number of labels independent of $H$ for a constant utility gap. More generally, we derive minimax audit bounds that quantify the effects of distribution overlap, generation cost, and calibration smoothness. These results show why an early decline is not, by itself, a reliable stopping criterion for Best-of-N scaling and provide structural and statistical conditions for evaluating later recovery.