Best-of-N Certification Width

(1) Exact integration point: add this as a validation and deployment-budget controller around a generator, reward model, or reranking system, not inside the forward pass. For each prompt, draw iid candidates, rank them with the existing scalar score, and measure binary task success after selecting the top candidate. Run audits at budgets n = 1,...,m and use the controller before approving a best-of-N configuration for deployment. (2) Pseudocode: set deployment budget N and target structural ambiguity epsilon. For m from 1 to N, initialize B = 1; for r from 1 to m, set theta = pi*r/(2*(m+1)) and update B = B + 2*(-1)^r*cos(theta)^(2*N); stop at the first m with B <= epsilon. Evaluate empirical reliabilities \hat R_n on a fixed set of audit prompts for n <= m. Estimate the deployment reliability interval using a lower endpoint obtained from the observed reliability constraints and a width B; conservatively intersect the result with [0,1]. For comparing systems A and B, require the measured reliability gap to exceed B_A + B_B, plus ordinary statistical confidence margins, before declaring a structural improvement. (3) The cosine sum and the m^2/N scaling are computed exactly from the paper. Empirical quantities include \hat R_n, binomial confidence intervals, prompt-level bootstrap uncertainty, and any correction for non-iid candidate generation. The theorem assumes iid candidates, scalar ranking, binary bounded truth, and an unchanged ranking-truth relation; therefore run separate diagnostics for temperature dependence, prompt heterogeneity, and ranker drift. (4) First cheap experiment: use a small language model on GSM8K or a binary code-generation benchmark, compare greedy, best-of-32, and best-of-128 selection with a reward-model ranker, and audit n = 1,2,4,8,16,32. Plot measured reliability against N together with B_{m,N} for each audit cutoff. The expected signal is that audits with m far below sqrt(N) produce very wide certification intervals and fail to distinguish systems despite apparent best-of-N gains, while increasing m toward sqrt(N) sharply narrows the structural ambiguity. The immediate success criterion is improved calibration of deployment claims and fewer unsupported model comparisons, not necessarily lower training loss.