acceptodds
Under review as a conference paper at ICLR 2027

Calibration under Best-of-N Scaling

Abstract

How far does calibration at small Best-of- budgets constrain calibration at larger ones? For a fixed predictor under Best-of- selection, we derive a bound on population calibration error when calibration holds at budgets . The error at the next budget is , and the error is order one when . A single model whose predictor is the raw score has calibration error of this order at every budget . We extend the analysis to finite samples: an extrapolation bound recovers 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.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
calibration, test-time scaling

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_9cCMOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

I have very serious concerns with the paper. Among these, two concern me the most. The first one is obviously clarity. The writing is so obscure I could in no reasonable time provide a constructive feedback. Infact, the authors make no effort whatsoever in comunicating clearly the problem they are trying to solve nor their intents. This makes most of the paper so hard to follow. Nonetheless, I want to mention a second concern of mine. Indeed, although I see many other problems with the paper, related for instance to notation and positioning with related literature, what concerned me the most is the relevance of the contribution. Again, even if one could grasp what the authors objective with this manuscript was, which is not straightforward at all, there is no motivation for what they are doing. I cannot figure one practical use case of the paper contribution nor one context where one would even resort to the same anlaysis they try to propose: determining claibration error when moving from evaluations with KK candidates to evluations with N>KN > K candidates. If calibration was so important, and one could not do without more candidates, why not just calibrating the new confidence when more candidates are present? I simply do not undertsand what the practical use case of the analysis, which is the whole point of the paper, would be. IAnd I just cannot ignore that the trivial notion, that calibration may not hold when increasing the number of candidates, seems to me all one would ever need to know.

Critical strengths

see summary

Critical weaknesses

see summary

Questions for authors

see summary

5 comments

Thanks for encouraging us to improve the clarity of our writing. We have revised the draft to state the problem, the setup, and the analysis more directly. We hope these changes make the paper more accessible.

Regarding the relevance of the contribution, we would like to clarify. Our work is a theoretical analysis of how calibration changes as the selection budget NN grows. We characterize how much calibration error can grow when a predictor calibrated at small budgets is deployed at a larger NN. Our main result shows that as NN grows, the guarantee from calibration at small budgets becomes progressively weaker, and beyond a certain scale it provides no useful constraint on calibration error at all. Moreover, we show there exist natural predictors whose calibration error reaches this worst case.

We further analyze the case with realistic, noisy estimates, where the useful range becomes even shorter. Our analysis tells a practitioner how far existing calibration can be trusted and when recalibration becomes necessary. As the reviewer mentions, simply recalibrating at the new NN is one option. We never deny the value of recalibration — in fact, our analysis explains why it is necessary in many real scenarios when deploying at a larger NN.

Beyond this, we also analyze a practical alternative: incorporating within-prompt rank. We prove that this approach removes the limitation on the extrapolation range. In experiments, rank-aware calibration g(S,U^)g(S,\hat U), trained once, achieves accuracy comparable to recalibration at the target NN (details in Appendix G.3), without requiring new labeled data or retraining required by recalibration. It needs only unlabeled references at inference time. In summary, our contribution goes beyond the qualitative observation that calibration may not hold at larger NN. We provide analysis of when and how much it degrades, and a theoretically grounded solution that works in practice.

We recognize that the presentation in our original submission may not have conveyed these contributions as intended. We have revised the writing and added new results that validate the theoretical predictions on real datasets. We would be grateful if you could refer to the updated draft for further details, and we are happy to provide additional information that would be helpful for your review.

I thank the authors for their detailed response and substantial revisions. The presentation has improved, and I now have a clearer understanding of the problem being investigated and its intended contributions.

However, I remain unconvinced of the practical significance of the proposed approach. In particular, I would have liked to see a direct comparison between the rank-aware method and established post-hoc calibration techniques applied at the target selection budget, such as isotonic regression or temperature scaling. I understand that the authors aim to avoid collecting additional labeled data and recalibrating at each budget. Nevertheless, such a comparison would help establish whether the rank-aware approach offers meaningful advantages over simpler alternatives, or at least quantify the trade-offs involved. In particular, understanding how calibration performance varies with the amount of additional labeled data required by conventional methods would provide valuable practical guidance and substantially strengthen my assessment of the contribution.

While I acknowledge the theoretical contributions and the improvements made during rebuttal, my reservations regarding the overall significance of the work remain. I therefore maintain my original score at this stage.

Thank you for the follow-up and we are glad the revision made the problem and our contributions clearer. Following your suggestion, we compared the rank-aware predictor, which is fitted once at N=1N=1 and uses no labels at the target budget, with standard post-hoc calibration methods applied at the target budget, and measured how their performance changes with the number of additional labels.


Compare the rank-aware method with established post-hoc calibration applied at the target budget, such as isotonic regression or temperature scaling, and show how calibration varies with the amount of additional labeled data.

Setup. We use Weaver, in which Llama-3.1 8B and 70B each generate 100 candidate answers per prompt, every candidate is labeled for correctness and scored by 96 verifiers, and the prompts come from MATH500 and MMLU-Pro. We follow the config of our Weaver experiment (details in App. G.6).

g1(S)g_1(S) and g1(S,U^)g_1(S,\hat U) are fitted once at N=1N=1. At each target N∈{4,16,64}N\in\{4,16,64\}, we fit 4 post-hoc calibration methods, temperature scaling (TS), Platt scaling, isotonic regression, and histogram binning, on top of g1(S)g_1(S) with m∈{25,50,100,200}m\in\{25,50,100,200\} additional labels. One label is the correctness of the selected Best-of-NN answer for one prompt in the calibration set, which is disjoint from the training and test sets. The calibrators therefore use all the labels used to train g1(S,U^)g_1(S,\hat U), together with mm additional labels at the target budget.

ECE(%) at the target budget. In each cell, the four values correspond to m=25m=25, 5050, 100100, and 200200 target labels. Medians over the 96 verifiers, and each averaged over 10 splits.

methodN=4N=4N=16N=16N=64N=64
g1(S)g_1(S), no target labels4.246.738.34
g1(S,U^)g_1(S,\hat U), no target labels2.702.963.90
TS4.58 / 3.72 / 3.14 / 2.995.00 / 3.92 / 3.31 / 3.055.37 / 4.22 / 3.66 / 3.24
Platt6.94 / 4.36 / 2.86 / 1.976.92 / 4.53 / 3.13 / 2.197.04 / 4.82 / 3.21 / 2.36
isotonic10.79 / 7.48 / 5.11 / 3.399.98 / 7.07 / 4.95 / 3.249.33 / 6.58 / 4.56 / 3.02
hist. binning7.70 / 7.29 / 6.87 / 5.347.30 / 6.93 / 6.22 / 4.887.30 / 6.43 / 5.19 / 3.89

Brier score / log loss at the target budget, with m=200m=200 target labels for each calibrator.

methodN=4N=4N=16N=16N=64N=64
g1(S)g_1(S), no target labels16.43 / 49.7215.92 / 48.6715.65 / 51.53
g1(S,U^)g_1(S,\hat U), no target labels15.65 / 47.3514.91 / 46.4614.91 / 46.92
TS16.38 / 49.4415.39 / 47.2414.91 / 47.45
Platt16.24 / 49.1015.28 / 47.3015.06 / 47.32
isotonic16.53 / 55.5115.52 / 52.5315.10 / 50.03
hist. binning17.29 / 62.3415.99 / 57.0115.42 / 53.11

Analysis.

  1. With few labels, recalibration does not reach the rank-aware predictor. With m≤50m\le50, every calibrator has higher ECE than rank-aware g1(S,U^)g_1(S,\hat U) at every budget.
  2. Achieving comparable performance takes 100–200 labels for each budget. At N=64N=64, TS and Platt scaling need 100 labels to reach an ECE comparable to g1(S,U^)g_1(S,\hat U), and isotonic regression and histogram binning need 200. At N=4N=4 and 1616, only Platt scaling with 200 labels achieves comparable performance.
  3. In Brier score and log loss, rank-aware g1(S,U^)g_1(S,\hat U) is better at every budget / label we tested. The calibrators themselves are fitted by minimizing these two metrics. TS and Platt scaling minimize log loss, and isotonic regression and histogram binning minimize Brier score. Even when every calibrator uses 200 target labels, g1(S,U^)g_1(S,\hat U) has lower log loss than all of them at every budget, and lower or equal Brier score. With fewer labels, the gap is larger. This holds for all 96 verifiers at N=4N=4 and 1616, and for 74–95 of the all 96 verifiers at N=64N=64.
  4. A calibrator fitted at one budget does not transfer to other budgets, so its labels must be collected again whenever NN changes. After fitting at N=64N=64 with 200 labels, TS, Platt scaling, and isotonic regression have ECE 3.83, 9.43, and 12.75 at N=4N=4. Here Platt scaling and isotonic regression are even worse than g1(S)g_1(S) without recalibration (4.24). The rank-aware g1(S,U^)g_1(S,\hat U), trained once at N=1N=1, has ECE 2.70 at N=4N=4 and 3.90 at N=64N=64 without any target labels.
Reviewer_nHYVOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies how probability calibration of a fixed verifier changes under Best-of-N selection as the number of candidate responses increases. The authors show that calibration at smaller selection budgets does not necessarily guarantee calibration at larger budgets. By expressing the distribution of the selected candidate through a change of measure involving its relative rank, they establish an upper bound on the population calibration error when the predictor is perfectly calibrated at budgets {1,…,K}\{1,\ldots,K\}. They show that this bound is sharp up to a universal constant and characterize the extrapolation scale as order K2K^2. The authors further extend their analysis to finite-sample calibration constraints and derive minimax bounds for estimating the mean calibration residual when additional labeled observations are available. Finally, numerical experiments on synthetic data and language-model-generated programs illustrate the theoretical findings and show that incorporating relative-rank information can help reduce calibration errors at larger selection budgets.

Critical strengths

The paper presents a rigorous theoretical understanding of the behavior of calibration under best-of-N scaling. In particular, the paper investigates how the expected calibration error changes as the number of generated responses per prompt increases, assuming we have a perfectly calibrated model for N={1,…,K}N = \{1, \dots, K\}. This is the part I really like, as given the plethora of methods available for calibration and alignment, it is imperative to develop theoretical understanding.

Critical weaknesses
  1. I think the presentation of the probabilistic setup in Section 2 needs a bit improvement. In particular, it would be helpful if the authors could more explicitly describe the data-generating process, where a prompt X∼μX\sim\mu is first drawn, followed by NN conditionally independent candidate responses Zi∼QXZ_i\sim Q_X, each associated with a verifier score SiS_i, a predicted correctness probability CiC_i, and a correctness label YiY_i. In particular, it may be helpful if the authors say that one may think Si=S(X,Zi),Ci=C(X,Zi)S_i = S(X, Z_i), C_i = C(X, Z_i) for some deterministic or stochastic function (S,C)(S, C), where ideally the stochasticity is independent of (X,Z1,…,Zn,Y)(X, Z_1, \dots, Z_n, Y). It would also help to clarify that calibration is evaluated over the selected-candidate distribution after averaging over the prompts, rather than conditional on each prompt.

  2. How does the calibration-extrapolation bound change when the residual function belongs to a uniformly smooth function class, for example, a Hölder class with a fixed smoothness radius? Is the K2K^2 scaling still relevant under such restrictions or should we see some improvement? Some comments would be helpful.

  3. Although the theoretical results are interesting, I think it would be helpful to illustrate their practical implications more explicitly. In particular, Theorem 2 provides extrapolation bounds when the calibration moments are estimated from finite samples, but it is not clear how informative these bounds are under realistic sample sizes. Can the authors demonstrate, using the real datasets, how a practitioner could use these results to determine the largest selection budget NN for which calibration error remains below a prespecified tolerance? It would also be useful to report the number of labeled observations required to obtain a nontrivial bound and compare this with directly evaluating calibration at the target budget.

Questions for authors

Kindly see the Weakness section.

3 comments

We appreciate your highlighting the importance of our theoretical analysis and your constructive suggestions. We address each of your concerns below.


W2: How does the bound change when the residual function belongs to a Hölder class with a fixed radius? Is the K2K^2 scaling still relevant, or should we see some improvement?

Smoothness lowers the level of the worst case, but K2K^2 remains the scale of the transition. We derive a bound and verify it.

Suppose rh(u)=E[Rh(C)∣U=u]r_h(u)=\mathbb E[Rh(C)\mid U=u] is Hölder with exponent β∈(0,1]\beta\in(0,1] and radius LL. Then

∣θN,h∣≤min⁡{dK,N,L((N−K)/((K+1)(N+1)))β}→L(K+1)−β(N→∞)|\theta_{N,h}| \leq \min\{d_{K,N}, L((N-K)/((K+1)(N+1)))^\beta\} \to L(K+1)^{-\beta} \quad (N\to\infty)

Proof. Let UnU_n have density wnw_n. Since θK,h=0\theta_{K,h}=0, we have ∣θN,h∣=∣E rh(UN)−E rh(UK)∣|\theta_{N,h}|=|\mathbb E\,r_h(U_N)-\mathbb E\,r_h(U_K)|. Couple the two as UK=V1/K≤V1/N=UNU_K=V^{1/K}\le V^{1/N}=U_N, with VV uniform. The Hölder condition and Jensen's inequality (xβx^\beta is concave) give ∣θN,h∣≤L E(UN−UK)β≤L(EUN−EUK)β|\theta_{N,h}|\le L\,\mathbb E(U_N-U_K)^\beta\le L(\mathbb E U_N-\mathbb E U_K)^\beta. Finally, EUN−EUK=NN+1−KK+1\mathbb E U_N-\mathbb E U_K=\frac{N}{N+1}-\frac{K}{K+1}.

Worst case. We also computed the supremum over {∣rh∣≤1\{|r_h|\le1, calibration at budgets at budgets 1..K1..K, Hölder$(L,\beta)}$, as a linear program on a fine grid. The optimum is attained by a feasible residual, so it is also a lower bound of the same order.

KKN=K+1N=K+1N=(K+1)2N=(K+1)^2N→∞N\to\inftyno smoothness, dK,(K+1)2d_{K,(K+1)^2}
20.0310.1500.2500.850
30.00670.0940.1530.841
50.00040.0480.0750.835
8<10−4<10^{-4}0.0240.0360.833

The transition still happens at N≍K2N\asymp K^2: at N=(K+1)2N=(K+1)^2, the worst case has already reached 60–66% of its N→∞N\to\infty value. Smoothness reduces the worst case beyond K2K^2 (compare the last two columns), but does not change where the transition occurs.

Smoothness of rhr_h is an assumption on the data; without it, the construction using raw scores reaches the Theorem 1 bound. We add the bound, its derivation, and the LP results in App. C.7, and point to them after Theorem 1.

W3: Show, on real data, how a practitioner would determine the largest budget N with calibration error below a tolerance, the number of labels needed for a nontrivial bound, and how this compares with directly evaluating calibration at the target budget.

We run the experiments on CALIBRI. Since CALIBRI limits selection to N≤10N\le10, we also added Weaver (MATH500 and MMLU-Pro, Llama-3.1 8B/70B, 96 verifiers), where each prompt has 64 selection candidates and up to 36 references, allowing us to test at larger NN. The steps are: (1) Train the predictor. On an evaluation set of mm prompts, label complete pools at budgets n≤Kn\le K; (2) Estimate the residual moments θ^n,h\hat\theta_{n,h} with simultaneous radii ρn,h\rho_{n,h} (Hoeffding or bootstrap), and set ϵn,h=∣θ^n,h∣+ρn,h\epsilon_{n,h}=|\hat\theta_{n,h}|+\rho_{n,h} as in Eq. 14; (3) Solve the dual LP of Theorem 3 for each target NN using Eq. 15. We report the largest NN for which the bound stays within the tolerance τ\tau.

On both datasets, the extrapolation range is short: on CALIBRI (m=264m=264, δ=0.05\delta=0.05), extrapolation reaches at most N=K+1N=K+1; on Weaver (m=125m=125), extrapolation from n≤3n\le3 reaches only N=2N=2. Even shrinking the radii as if mm grew to 10610^6, the range saturates between KK and K+2K+2, because ∣θ^∣|\hat\theta| itself acts as a floor. This is what Theorem 3 predicts: under estimation error, g(S)g(S) can be extrapolated only to about Θ(K)\Theta(K) budgets beyond KK. The full cost comparison is in App. G.4.

The practical alternative is to use rank, as Theorems 2 and 4 suggest: g(S,U^)g(S,\hat U) with rank has a range that grows as (τ/ϵ)2(\tau/\epsilon)^2 with no K2K^2 cap. On Weaver at N=64N=64, frozen g1(S,U^)g_1(S,\hat U) achieves ECE 3.9%, close to 3.5% g64(S)g_{64}(S) retrained at the target, while frozen g1(S)g_1(S) reaches 8.3%. Recalibrating gN(S)g_N(S) at a new budget requires collecting labeled pools at that NN, re-estimating the calibration map, and repeating this whenever NN changes. But g1(S,U^)g_1(S,\hat U) is trained once and needs only kk unlabeled references at inference time. In practice, recalibrating at every new NN may not be feasible. Rank-aware calibration achieves comparable accuracy without that cost.


W1: Describe the data-generating process more explicitly, and clarify that calibration is evaluated over the selected-candidate distribution after averaging over prompts.

Thank you for pointing this out. We have revised Sec. 2 of the updated draft, included details of our data-generating process. Each candidate now carries named maps Si=S(X,Zi)S_i=S(X,Z_i), Ci=C(X,Zi)C_i=C(X,Z_i), and YiY_i, with their independence structure stated. We also add a sentence clarifying that all calibration quantities are evaluated under the selected-candidate distribution PNP_N, averaged over prompts.


Thanks again for your insightful comment and feedback. Please let us know if you have further questions and suggestions.

I want to thank the authors for the clarifications. I will maintain my positive score.

Reviewer_vGqaOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies how calibration at Best-of-N budgets 1, ..., K constrains calibration at larger budgets. It derives an explicit bound through polynomial approximation, establishes a quadratic extrapolation scale, and constructs a calibrated model matching the bound within a universal constant. Extensions address uncertain calibration moments and passive-label estimation; experiments illustrate the theory and investigate rank-aware calibration for code generation.

Critical strengths
  • The central result gives a precise characterization beyond merely demonstrating calibration failure: exponentially small next-budget error, a transition at N≍K2N\asymp K^2, and a single raw-score construction matching the bound within a constant simultaneously at every larger budget (Theorem 1, Corollary 1).
  • The finite-sample analysis meaningfully qualifies the idealized result. Theorem 2 accounts for amplification of moment uncertainty, while Corollary 3 shows that a fixed positive uncertainty floor reduces the guaranteed budget range to linear in K. The matching minimax bounds further characterize the information supplied by additional labels.
Critical weaknesses
  • The practical significance of the main extrapolation result remains unclear. The quadratic budget range requires exact calibration at budgets 1, ..., K, while Corollary 3 shows that a fixed positive moment-uncertainty floor reduces the guaranteed range to linear in K. The paper does not demonstrate whether its finite-sample bounds yield useful extrapolation guarantees at realistic sample sizes.
  • Evidence for reliable empirical improvement from rank-aware reporting seems limited. In Table 1, seven of eight endpoint improvement intervals include zero under both designs. Moreover, the independent-reference experiment reaches only N=5, leaving effectiveness under substantially stronger selection untested.
Questions for authors
  • When Theorem 2 is applied to estimated low-budget moments, what larger budgets can be certified at a meaningful tolerance, and how does this depend on the number of labeled prompts?
  • Do the rank-aware improvements persist across repeated fitting splits and alternative calibration-bin resolutions, particularly in the independent-reference design where most reported intervals include zero?
3 comments

Thanks for your careful review. We appreciate your highlighting the precise characterization in our main result, and found that the analysis, Theorem 2 and Corollary 3, meaningfully. We answer your questions with new experiments.


W1 / Q1: When Theorem 2 is applied to estimated low-budget moments, what larger budgets can be certified at a meaningful tolerance, and how does this depend on the number of labeled prompts?

The K2K^2 range (Thm. 1) assumes calibration at budgets 1,…,K1,\dots,K without estimation error. In practice, calibration is estimated from data with error ϵ\epsilon. With this error, Thm. 3 shows that the range shrinks to Θ(K)\Theta(K) — roughly Kτ/ϵK\tau/\epsilon, and still capped at K2K^2. Our main practical finding is that g(S)g(S) cannot be reliably extrapolated to new budgets, it must be recalibrated or evaluated at new target NN.

The answer is to use rank. Under the same estimation error ϵ\epsilon, g(S,U)g(S,U) with rank has a much wider range:

no estimation errorwith estimation error ϵ\epsilon
g(S)g(S), calibrated at 1..K1..KN≲K2N\lesssim K^2 (Thm. 1)N≲Kτ/ϵN\lesssim K\tau/\epsilon, capped at K2K^2 (Thm. 3)
g(S,U)g(S,U)every NN (Thm. 2)N≲2(τ/ϵ)2N\lesssim 2(\tau/\epsilon)^2, no cap (Thm. 4)

The range for g(S)g(S) is linear in 1/ϵ1/\epsilon and capped. The range for g(S,U)g(S,U) is quadratic in 1/ϵ1/\epsilon and uncapped, so the gap between the two widens as more labeled data become available. We add this comparison as Table 1 and discuss it at the end of Sec. 4.

Experiments. We apply Eq. (15) on CALIBRI with m=264m=264 evaluation prompts and calibrated budgets K∈{1,2,3,5}K\in\{1,2,3,5\}, using 16 bin tests at δ=0.05\delta=0.05 and tolerances τ∈{0.05,0.1,0.2}\tau\in\{0.05,0.1,0.2\}.

  • At m=264m=264: Hoeffding radii cannot confirm any budget. Even with θ^=0\hat\theta=0, the bound for K=5→N=6K=5\to N=6 is 0.33. Bootstrap radii confirm at most N=K+1N=K+1.
  • Dependence on mm: we keep the point estimates θ^n,h\hat\theta_{n,h} and shrink the radii as if mm grew to 10610^6. The largest confirmed NN (at τ=0.2\tau=0.2) still saturates between KK and K+2K+2, because ∣θ^∣|\hat\theta| itself acts as a floor.
  • Labels needed extrapolating from K=5K=5 to N=6N=6 requires 35× the cost of testing that NN directly. Going to N=7N=7 requires about 800×.
  • Second dataset: CALIBRI has at most K=5K=5 calibrated budgets. To test with stronger selection, we use Weaver (m=125m=125, selection up to N=64N=64). Extrapolation from n≤3n\le3 can only confirm up to N=2N=2. Directly evaluating frozen g1(S,U^)g_1(S,\hat U) confirms calibration up to N=32N=32 (τ=0.1\tau=0.1) and N=64N=64 (τ=0.2\tau=0.2).

Results analysis. The data follow the theory on both sides. At any realistic mm, score-based calibration g(S)g(S) can only be extrapolated Θ(K)\Theta(K) budgets ahead. Calibration with rank, g(S,U^)g(S,\hat U), trained once, holds across the full range we can test. The practical conclusion: recalibrate at the target NN, or use rank.

W2: The independent-reference experiment reaches only N=5, leaving stronger selection untested.

CALIBRI has only 10 candidates per prompt, which limits the 5+5 design to N=5N=5. We therefore added experiments on Weaver, a dataset with 500 problems × 100 samples, MATH500 and MMLU-Pro with Llama-3.1 8B/70B, and 96 verifiers. Each problem has 64 selection candidates and up to 36 disjoint, unlabeled references.

N=1N=1N=16N=16N=64N=64
score-only g1(S)g_1(S)2.26.58.7
rank-aware, k=5k=5 references2.44.66.8
rank-aware, k=20k=202.43.75.4
rank-aware, k=36k=362.53.45.3

Results analysis. At N=64N=64, ECE of score-based g(S)g(S) rises from 2.2% to 8.7%. With independent references, g(S,U^)g(S,\hat U) stays far lower, beating g(S)g(S) at N=64N=64 for 91/96 verifiers. The curve flattens as kk grows, aligned with our Thm. 4 (rank error ≤Λ/6k\le\Lambda/\sqrt{6k} for all NN). With the full pool, the gain at N=64N=64 is positive for 93/96 verifiers. g(S,U^)g(S,\hat U) also beats g1:3(S)g_{1:3}(S), calibrated at budgets 1..3 we tested, for 95/96 verifiers.


W2 / Q2: Do the rank-aware improvements persist across repeated fitting splits and alternative calibration-bin resolutions, particularly in the independent-reference design?

Setup. We retrain on 10 re-splits with disjoint groups across all 8 configurations and both designs. The gain (g1(S)g_1(S) minus g1(S,U^)g_1(S,\hat U)) is pooled over configurations within each split.

metricgain
ECE, equal-width, 5 / 10 / 15 bins+3.05 [+0.77, +5.33] / +2.77 [+0.77, +4.76] / +2.64 [+0.70, +4.58]
ECE, equal-mass, 5 / 10 / 15 bins+3.00 [+0.98, +5.02] / +2.59 [+0.75, +4.43] / +2.41 [+0.92, +3.91]
debiased L2 ECE+2.21 [+0.26, +4.16]
Brier+0.67 [+0.36, +0.97]
log loss+1.61 [+0.93, +2.30]

The gain is significant for: the main 5-bin ECE; Brier (+0.39 [+0.17, +0.60]); and log loss (+0.90 [+0.41, +1.40]). Brier and log loss are positive in 8/8 configurations. With 10 or 15 bins and with debiased ECE, the gain stays positive (+1.0 to +1.2) in 7/8 configurations.

More data. CALIBRI has only about 264 evaluation prompts per configuration, which makes the confidence intervals wide. To further test whether the gain persists when sample size is not a bottleneck, we run a semi-synthetic study (ground truth is each configuration's η^(S,U)\hat\eta(S,U), 20k evaluation prompts). The gain at N=10N=10 excludes 0 in 8/8 configurations once m≥2000m\ge2000. g(S)g(S) drifts to 1.4–15.1%, while g(S,U^)g(S,\hat U) stays below 1.1%.

Results analysis. We found that the gain does not depend on the split, the binning, or the metric. The proper scores without bins (Brier, log loss) are significant in both designs. Together with the results on Weaver dataset above (93/96 verifiers at N=64N=64), the evidence shows the gain is consistent across datasets, metrics, and selection strengths.


We hope these new results address your concerns about practical significance and empirical evidence. Please let us know if you have any further questions or you would like additional clarification on any of these points. Thank you.

Thank you for the substantial additional experiments. The larger-budget evaluation and robustness checks substantially address my empirical concerns. The finite-sample analysis also clarifies the practical limits of extrapolation. I therefore maintain my current positive rating.

Reviewer_mw9hOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies what calibration at small Best-of-N budgets tells us about calibration at larger budgets, with the probability predictor kept fixed. It writes selection as a change in sampling weight determined by a candidate’s rank within its prompt. This turns extrapolation from calibrated budgets 1 through K into an L1 polynomial approximation problem. The authors derive an explicit bound using Chebyshev nodes and give one valid score model that matches it within a constant factor. They also study errors in the calibration constraints and the value of additional labels from ordinary candidates. Synthetic experiments and code-generation examples illustrate the results.

Critical strengths
  1. The main result gives a clear explanation of why calibration can fail after selection. A candidate’s rank within its prompt is the key quantity. The analysis also gives specific limits: the error at the next budget and the K² scale at which the bound becomes large. One valid model, using the raw score as the reported probability, reaches a constant fraction of the upper bound at every larger budget. Having the same example work for all those budgets makes the result especially convincing.

  2. Theorem 2 is helpful because it allows errors in the calibration constraints. It shows that fitting the selection weight more closely can amplify errors in the estimated moments. Corollary 3 then explains why the K² result under exact calibration may be too optimistic once those constraints are noisy. I also appreciated the authors spelling out what the bounds cover. Testing a finite set of residual moments does not give a bound on full continuous ECE, and the results that assume known population ranks need separate treatment when ranks are estimated.

Critical weaknesses
  1. The experiments do not show the benefit over calibrating the full pipeline at a fixed N. One can generate N candidates, select the winner, and fit a standard calibrator on its score and correctness label, without requiring a calibrated candidate predictor. The paper uses a flexible, capacity-matched score-only baseline, but both g(S) and g(S,Uhat) are fitted at N=1. This tests transfer across budgets, leaving the benefit of rank at a fixed N unclear. A target-N score-only fit could reuse the existing labeled pools with the winner weights in Appendix K.3. This keeps costs comparable, but uses the target budget and should be distinguished from frozen transfer.

  2. The code experiments use at most ten candidates and do not show whether Equation (15) certifies an additional budget at the costs already given in Appendix K.5. Section 5.3 shows drift in all eight configurations, and Section 5.4 includes a useful rank permutation control. However, it remains unclear how drift varies with the mix of correct and incorrect candidates or the spread of S and C within a prompt. Theorem 4 and Corollary 7 already describe conditions with no drift. Comparing these cases with the observed data would help explain when the issue matters. Seven of eight endpoint confidence intervals for the gain from adding rank include zero, so the practical gains also need more evidence.

Questions for authors
  1. For a fixed N, can you fit a score-only calibrator on the selected-answer distribution using the same labeled pools and Appendix K.3 weights? Compare it with the rank-aware report on ECE and Brier score or log loss, with uncertainty across prompt splits and costs including rank references. Please distinguish this fit from transfer without target-budget fitting.

  2. On one generation dataset, which budgets can Equation (15) certify at a chosen tolerance and confidence level? Please report the bound even if it is too large, using the costs in Appendix K.5.

  3. Can you compare drift across groups with different proportions of correct candidates and spreads of S and C, including nearly identical scores? In mixed pools, do S and C distinguish correct answers? Does rank predict correctness at similar C? Please test a larger independent reference pool. Please qualify the conclusion's min{1, sqrt(N/m)} passive-label rate as K=1; Appendix D gives the general result as omega_{K,N}(m^{-1/2}).

3 comments

We thank the reviewer for the detailed review and questions. We are glad the reviewer found that our analysis gives "a clear explanation of why calibration can fail after selection". We revised the Introduction to state our finding based on our theory: calibration based on the verifier score alone must be retrained whenever the selection budget NN changes, whereas calibration that also uses the candidate's rank transfers across budgets without retraining. We ran every requested experiment and address your concerns below.


W1 / Q1: For a fixed N, fit a score-only calibrator on the selected-answer distribution with the App. K.3 weights; compare it with the rank-aware report on ECE, Brier and log loss, with uncertainty across splits and costs; distinguish this fit from transfer.

Setup. We train gN(S)g_N(S) on the distribution of selected answers using App. F.3 winner weights, and train gN(S,U^)g_N(S,\hat U) at the same NN. The table compares frozen (N=1N=1) and target-NN variants. We use CALIBRI dataset with pools of 10 candidates, 10 re-splits with disjoint groups, pooled over 8 configurations.

Paired differences at N=10N=10. Each entry is the loss of the first report minus the loss of the second.

comparisonECEBrierlog loss
(a) frozen g1(S)g_1(S) vs target-NN gN(S)g_N(S)+3.01 [+0.42, +5.60]+0.47 [+0.10, +0.84]+1.07 [+0.24, +1.89]
(b) target-NN gN(S)g_N(S) vs frozen g1(S,U^)g_1(S,\hat U)+0.32 [−0.70, +1.33]+0.27 [+0.09, +0.46]+0.73 [+0.37, +1.08]
(c) gN(S)g_N(S) vs gN(S,U^)g_N(S,\hat U), same NN+0.30 [−0.39, +0.99]+0.26 [+0.09, +0.42]+0.65 [+0.29, +1.01]

Results analysis.

  1. g(S)g(S) must be recalibrated when NN changes (row a). Frozen at N=1N=1, g1(S)g_1(S) is 3.0 pp worse in ECE than gN(S)g_N(S) trained at the target NN.
  2. g1(S,U^)g_1(S,\hat U) trained once at N=1N=1 matches target-NN recalibration (row b). ECE is comparable, and Brier and log loss are better at every N=2,…,10N=2,\dots,10, with no retraining.
  3. Rank helps even at a given NN (row c). Brier and log loss improve at every N=2,…,10N=2,\dots,10. The rank U^\hat U carries correctness information beyond SS (Thm. 2).

At larger NN (Weaver, N=64N=64, 96 verifiers), frozen g1(S,U^)g_1(S,\hat U) has median ECE 3.9%, close to g64(S)g_{64}(S) retrained at the target (3.5%), while frozen g1(S)g_1(S) reaches 8.3%.

Costs. Training: both routes reuse the same labeled pools; At a new NN: frozen g1(S,U^)g_1(S,\hat U) needs the NN candidates plus kk unlabeled references for the rank (k=5k=5 to 36 in our experiments), but no new labels and no retraining. Details are in draft App. G.3.


W2 / Q2: On one generation dataset, which budgets can Eq. (15) certify at a chosen tolerance and confidence level? Please report the bound even if it is too large, using the costs in App. K.5.

Setup. We apply Eq. (15) on CALIBRI with m=264m=264 evaluation prompts and calibrated budgets K∈{1,2,3,5}K\in\{1,2,3,5\}. We use 16 bin tests at confidence level δ=0.05\delta=0.05 and tolerances τ∈{0.05,0.1,0.2}\tau\in\{0.05,0.1,0.2\}.

Results.

  • At m=264m=264: with Hoeffding radii, Eq. (15) cannot confirm any budget. Even with θ^=0\hat\theta=0, the bound for K=5→N=6K=5\to N=6 is 0.33. With bootstrap radii, the bound only reaches N=K+1N=K+1.
  • With more labels: we keep the point estimates θ^n,h\hat\theta_{n,h} and shrink the radii as if mm grew to 10610^6. The largest confirmed NN (at τ=0.2\tau=0.2) still saturates between KK and K+2K+2, because ∣θ^∣|\hat\theta| itself acts as a floor.
  • Label cost (App. F.5, τ=0.05\tau=0.05, best case θ^=0\hat\theta=0): testing one target NN directly needs 2,952 prompts. Extrapolating from K=5K=5 to N=6N=6 needs 35× prompts, and to N=7N=7 about 800×.

Results analysis. This is the prediction of Thm. 3. With nonzero moment error, the confirmed range is Θ(K)\Theta(K). Because ∣θ^∣|\hat\theta| acts as a floor, the range stays bounded even as m→∞m\to\infty. This is the quantitative reason why g(S)g(S) must be recalibrated or tested at the target NN. Testing directly is also cheaper, by one to three orders of magnitude.

We also test on Weaver (m=125m=125), where selection goes up to N=64N=64. The pattern is the same: extrapolation from n≤3n\le3 can only confirm up to N=2N=2. By contrast, directly evaluating frozen g1(S,U^)g_1(S,\hat U) confirms calibration up to N=32N=32 (τ=0.1\tau=0.1) and N=64N=64 (τ=0.2\tau=0.2). For g1:3(S)g_{1:3}(S) the bound only reaches N=4N=4 (τ=0.1\tau=0.1).

W2 / Q3: Compare drift across groups with different proportions of correct candidates and spreads of S and C, including nearly identical scores. In mixed pools, do S and C distinguish correct answers? Does rank predict correctness at similar C?

Setup. CALIBRI dataset. g1(S)g_1(S) and g1(S,U^)g_1(S,\hat U) are trained with cross-validation over problem groups. Drift is the change in the selected answer's residual EN[Y−C]\mathbb E_N[Y-C] from N=1N=1 to N=10N=10 (negative = increasingly overconfident).

Drift from N=1N=1 to N=10N=10.

configscore-onlyrank-awarenearly identical SS (nn)low → high SS-spreadlow → high CC-spread
LCB/Qwen3−7.5−0.5−0.4 (142)−1.6 → −14.5−0.4 → −16.8
LCB/GPT-OSS−14.4−0.2–−7.3 → −22.4−3.7 → −22.0
McEval/Qwen3−5.9−0.3+0.7 (198)−3.5 → −10.6−3.7 → −9.4
McEval/GPT-OSS−6.9−0.3–−6.4 → −8.3−3.6 → −8.1
McEval/R1−3.1+0.0–−2.7 → −3.4−1.1 → −5.7
MultiPL-E/Qwen3−3.1−0.2+0.0 (254)−2.3 → −2.8−1.7 → −4.2
MultiPL-E/GPT-OSS−1.2−0.2–−1.4 → −2.1−0.8 → −1.0
MultiPL-E/R1−4.9−0.0–−6.9 → −3.1−6.7 → −1.7

Results analysis. When candidate scores are nearly identical (spread < 0.01), there is no drift, as Thm. 2 predicts. As the spread of SS or CC grows, drift increases. Much of the drift comes from prompts whose candidates are all wrong (e.g., −5.3 of −7.5 pp on LCB/Qwen3). The full breakdown by fraction correct is in App. G.7. With rank, g(S,U^)g(S,\hat U) shows no detectable drift in any configuration.

Do SS and CC distinguish correct answers in mixed pools? Yes. AUROC within each prompt is 0.57–0.81 for SS and 0.58–0.80 for CC (all above 0.5; in Weaver dataset, median 0.68 over 96 verifiers). Higher AUROC correlates with more drift (Spearman +0.31, p=0.002p=0.002).

Does rank predict correctness at similar CC? Yes and this is the condition of Thm. 2. Within CC bins, the slope of Y−CY-C on rank is negative with CI excluding 0 in 7/8 configurations. The one exception, MultiPL-E/GPT-OSS, is also the configuration with the smallest drift and smallest gain from rank, as Thm. 2 predicts.


To test with a larger pool, we use Weaver (MATH500 and MMLU-Pro, Llama-3.1 8B/70B, 96 verifiers), where each prompt has 64 selection candidates and up to 36 disjoint, unlabeled references.

ECE at N=64N=64, g(S,U^)g(S,\hat U) with kk independent references.

score-onlyk=5k=5k=20k=20k=36k=36
main verifier10.87.35.44.9
median over 96 verifiers8.76.85.45.3

Results analysis. More references flatten the ECE curve, aligned with Thm. 4 (rank error ≤Λ/6k\le\Lambda/\sqrt{6k} for all NN). k=5k=5 (six rank levels) is least accurate because coarse levels cost ≈NΔU/2\approx N\Delta_U/2 (aligned with Thm. 10). With k=36k=36, g(S,U^)g(S,\hat U) beats g(S)g(S) at N=64N=64 for 91/96 verifiers.


W2: Seven of eight endpoint confidence intervals for the gain from adding rank include zero.

The intervals in Table 3 come from a single split with only about 264 evaluation prompts per configuration, so the confidence intervals might be wide. We addressed this in two ways:

  • Repeated splits (10 re-splits with disjoint groups). The gain (g(S)g(S) minus g(S,U^)g(S,\hat U), mean ECE over N=6..10N=6..10) is +3.05 [+0.77, +5.33], positive in 8/8 configurations. With independent references it is +1.43 [+0.08, +2.78]. With the original pools, the gain is significant for every ECE variant (equal width and equal mass, 5/10/15 bins, debiased ECE), and for Brier and log loss.
  • More data (semi-synthetic: the truth is each configuration's fitted η^(S,U)\hat\eta(S,U), with 20k evaluation prompts). The gain at N=10N=10 excludes 0 in 8/8 configurations once m≥2000m\ge2000.

Results analysis. The gain is consistent and becomes significant with more data or larger NN, aligned with the theory: drift of g(S)g(S) grows with NN, while the error of g(S,U^)g(S,\hat U) grows only as N ϵ\sqrt{N}\,\epsilon.


Q3: Please qualify the conclusion's min⁡{1,N/m}\min\{1,\sqrt{N/m}\} passive-label rate as K=1.

Thank you for pointing this out. We have revised the conclusion to state the general rate ωK,N(m−1/2)\omega_{K,N}(m^{-1/2}) from Thm. 15, and note that it reduces to min⁡{1,N/m}\min\{1,\sqrt{N/m}\} when K=1K=1.


We have (1) shown that g(S)g(S) must be retrained at the target NN while g(S,U^)g(S,\hat U) transfers without retraining (Q1); (2) demonstrated that extrapolation of g(S)g(S) is short-range on real data, confirming Thm. 3 (Q2); and (3) provided evidence that drift occurs where the theory predicts and that larger reference pools further reduce ECE (Q3). If our new results address your concerns, we would be grateful if you would consider raising the score, and we are happy to discuss any remaining questions. Thank you.

AuthorsOpenReview ↗

Follow Up on W1, Additional Results with Standard Calibrators

Thank you again for your detailed review. After our first response, we ran an additional experiment that related to W1, and we would like to share the results.


W1: Show the benefit over calibrating the full pipeline at a fixed N, where one generates N candidates, selects the winner, and fits a standard calibrator on its score and correctness label. Clarify the benefit of rank at a fixed N, and distinguish this fit from frozen transfer.

Previously, we answered this with the winner-weighted gN(S)g_N(S). We have now also run the full pipeline version you described.

Setup. We use the Weaver data with 96 verifiers and 100 labeled candidates for each prompt. At each target N∈{4,16,64}N\in\{4,16,64\}, we select the winner among NN candidates and fit 4 standard calibrators, temperature scaling (TS), Platt scaling, isotonic regression, and histogram binning, on its score and correctness label. They use m∈{25,50,100,200}m\in\{25,50,100,200\} prompts from a calibration set disjoint from the training and test sets. We fit them on top of g1(S)g_1(S), so each calibrator uses all the labels used to train g1(S,U^)g_1(S,\hat U), together with mm additional labels at the target budget. The rank-aware g1(S,U^)g_1(S,\hat U) is fitted once at N=1N=1 and uses no labels at the target budget.

ECE(%) at the target budget. Each cell, the values correspond to m=25m=25, 5050, 100100, and 200200 target labels.

methodN=4N=4N=16N=16N=64N=64
g1(S)g_1(S), no target labels4.246.738.34
g1(S,U^)g_1(S,\hat U), no target labels2.702.963.90
TS4.58 / 3.72 / 3.14 / 2.995.00 / 3.92 / 3.31 / 3.055.37 / 4.22 / 3.66 / 3.24
Platt6.94 / 4.36 / 2.86 / 1.976.92 / 4.53 / 3.13 / 2.197.04 / 4.82 / 3.21 / 2.36
isotonic10.79 / 7.48 / 5.11 / 3.399.98 / 7.07 / 4.95 / 3.249.33 / 6.58 / 4.56 / 3.02
hist. binning7.70 / 7.29 / 6.87 / 5.347.30 / 6.93 / 6.22 / 4.887.30 / 6.43 / 5.19 / 3.89

Brier score / log loss at the target budget, with m=200m=200 target labels for each calibrator.

methodN=4N=4N=16N=16N=64N=64
g1(S,U^)g_1(S,\hat U), no target labels15.65 / 47.3514.91 / 46.4614.91 / 46.92
TS16.38 / 49.4415.39 / 47.2414.91 / 47.45
Platt16.24 / 49.1015.28 / 47.3015.06 / 47.32
isotonic16.53 / 55.5115.52 / 52.5315.10 / 50.03
hist. binning17.29 / 62.3415.99 / 57.0115.42 / 53.11

Analysis.

  1. Without target labels, the rank-aware predictor performs comparably to calibrating the full pipeline with 100–200 labels for each budget. With m≤50m\le50, every calibrator has higher ECE than g1(S,U^)g_1(S,\hat U) at every budget. In Brier score and log loss, g1(S,U^)g_1(S,\hat U) remains better or equal even when every calibrator uses 200 target labels, as with gN(S)g_N(S) in our earlier response.
  2. The rank helps. Fitting the same calibrator on the same labels, but on top of g1(S,U^)g_1(S,\hat U) instead of g1(S)g_1(S), lowers the ECE of TS and Platt scaling in all settings, and the Brier score of all calibrators in 47 of 48 settings. At every budget and label size, the best result in each metric is with rank.
  3. Fit at NN does not transfer. Fitted at N=64N=64 with 200 labels, Platt scaling and isotonic regression have ECE 9.43 and 12.75 at N=4N=4, worse than g1(S)g_1(S) without recalibration (4.24), so the labels must be collected again whenever NN changes. The frozen g1(S,U^)g_1(S,\hat U) is trained once at N=1N=1 and needs no target labels at any budget.

Our theory explains these results. Every calibrator above is a function of the score. By Thm. 2, a score-only predictor is calibrated at every budget only if the rank carries no information beyond the score, and the drift of g1(S)g_1(S) (ECE from 2.1 at N=1N=1 to 8.3 at N=64N=64) shows that it does. A score-only calibrator therefore has to be refitted whenever NN changes (Thms. 1 and 3), and even at NN it leaves the information in the rank unused.


We hope these results, together with our earlier response, address your concerns. As the discussion period is ending soon, we would be grateful to know whether any concerns remain, and if they are resolved. Thank you.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response by Authors

We sincerely thank all reviewers for their careful reading and constructive suggestions. Their feedback helped us strengthen both the empirical validation and the presentation of our theoretical results. During the rebuttal period, we conducted the following additional analyses and experiments, and we have incorporated all of them into the revised manuscript.


Comparison with recalibration at the target budget. We compared the rank-aware predictor, trained once at N=1N=1, with score-only calibrators refitted at each target budget, including a winner-weighted refit and some post-hoc calibration methods (temperature scaling, platt scaling, isotonic regression, and histogram binning) with different numbers of additional labels. Without any labels at the target budget, the rank-aware predictor performs comparably to recalibration that uses 100–200 additional labels for each budget. When labels are available, adding the rank further improves these post-hoc calibration methods.

Larger budgets and statistical robustness. We added experiment over a second benchmark, Weaver, with 96 verifiers, selection budgets up to N=64N=64, and larger independent reference pools. We also repeated the main evaluation over 10 random splits with disjoint prompt groups, reported confidence intervals under multiple ECE variants, Brier score, and log loss, and ran a semi-synthetic study with larger evaluation sets. Gains from rank are consistent across datasets, metrics, and selection strengths, and rank-aware predictor improves further with larger reference pools, as our theory predicts.

Empirical validation of the theory. We applied our extrapolation bound to moments estimated from real data and compared its label cost with direct evaluation at the target budget. When the rank-aware predictor is evaluated directly, the bound stays within the tolerance up to much larger budgets, whereas for extrapolated score-only calibration it does so only over a short range of budgets, as predicted under estimation error. We also analyzed when drift occurs. It is close to zero when candidate scores within a prompt are nearly identical, grows with the spread of scores within each prompt, and appears where the rank carries information beyond the score, consistent with our characterization.

Theory and presentation. We derived a bound for smooth (Hölder) residual classes, showing that smoothness lowers the worst case while the transition still occurs at N≍K2N\asymp K^2. We added a comparison of the budget ranges guaranteed for score-only and rank-aware calibration under estimation error. We also added details about our data-generating process, and revised the draft to make our main contributions more directly.


We again thank reviewers for their thoughtful and constructive feedback. All additional experiments, analyses, and discussions from the rebuttal period have been incorporated into the updated manuscript.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.