Auditing Best-of-$k$ Selection: Minimax Label Complexity of Quality Curves

Best-of-$k$ selection returns the response with the highest judge score among $k$ candidates. As $k$ grows, selection can favor responses whose quality the judge overestimates, causing actual quality to decline. We study how many trusted outcome labels, such as verified correctness or human ratings, are needed to estimate selected-response quality across candidate budgets. Given pools of $L$ responses ordered by judge score, the quality curve averages the outcome of the highest-ranked response in a uniformly random $k$-subset, for every $k\le L$. Under independent queries at chosen ranks with outcomes in $[0,1]$, we establish matching upper and lower bounds of $\Theta ({\epsilon }^{-2}\log L[\log \log L+\log (1/\delta )])$ on the minimax expected label cost for simultaneous error $\epsilon$ at confidence $1-\delta$. The lower bound allows adaptive query allocation and data-dependent stopping. We prove that an estimator reusing labels across candidate budgets attains this rate under several closed-form rank allocations. These include Envelope, our default allocation, which minimizes the largest importance ratio and can be constructed in linear time. For fixed corpora, we derive simultaneous error bounds for sampling without replacement and recover the same minimax rate when sufficiently many pools are available. Experiments across diverse tasks show that Envelope achieves accuracy comparable to numerically optimized designs. Audited curves also guide the choice of candidate budget, and hence of inference-time computation, for new inputs.