Calibration under Best-of-N Scaling

How far does calibration at small Best-of-$N$ budgets constrain calibration at larger ones? For a fixed predictor under Best-of-$N$ selection, we derive a bound $d_{K,N}$ on population calibration error when calibration holds at budgets $1,\dots ,K$. The error at the next budget is $(K+1)4^{-K}$, and the error is order one when $N\asymp K^2$. A single model whose predictor is the raw score has calibration error of this order at every budget $N>K$. We extend the analysis to finite samples: an extrapolation bound recovers $d_{K,N}$ when moment uncertainty is zero and yields bounds on residual moments at larger budgets from finite-sample calibration estimates. A minimax result characterizes what additional passive labels reveal about the mean residual under selection, given calibration constraints and within-prompt ranks. We validate the theory on synthetic data and on language-model generations.