acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

A decline in Best-of-N utility at small does not imply that utility cannot recover at larger , even with smooth calibration and exact knowledge of the early utility curve. For every finite horizon , we construct a fixed generator–verifier law whose utility first peaks at , decreases at , yet exceeds the first peak by at least at . We explain this behavior through a task-conditional rank transform: for every , the expected utility is obtained by averaging a single calibration profile against a 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- utility labels at fixed confidence, whereas directly labeling selected winners at the relevant breadths requires a number of labels independent of 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.

Primary area:
learning theory
Keywords:
best-of-N, test-time scaling, imperfect verification, verifier calibration, reward overoptimization, minimax theory, audit complexity

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_aHe1OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper analyzes the population utility curve JN=E[Ui^N]J_N = \mathbb{E}[U_{\hat{i}_N}] of Best-of-NN test-time scaling as a function of candidate breadth NN, alongside the statistical sample complexity of auditing JNJ_N. By applying a task-conditional probability integral transform X=FZ(S)X = F_Z(S) to the verifier scores within each task ZZ, the winning candidate's quantile follows a Beta(N,1)\text{Beta}(N, 1) density pN(x)=NxN−1p_N(x) = N x^{N-1}. This reduces the expected utility curve to a family of Beta-weighted averages of a single average calibration profile ψˉ(x)=EZ[E[U∣X=x,Z]]\bar{\psi}(x) = \mathbb{E}_Z[\mathbb{E}[U \mid X = x, Z]]: JN=N∫01ψˉ(x)xN−1dx.J_N = N \int_0^1 \bar{\psi}(x) x^{N-1} dx. Using this representation, the authors establish three main sets of theoretical results:

  1. For every integer horizon H≥64H \ge 64, Theorem 3.1 constructs a smooth (C∞C^\infty) profile ψH∈[0.1,0.9]\psi_H \in [0.1, 0.9] whose utility increases from N=1N=1 to N=2N=2 (J2−J1≥0.06J_2 - J_1 \ge 0.06), decreases at N=3N=3 (J2−J3≥0.01J_2 - J_3 \ge 0.01), and subsequently recovers to exceed the first peak by a constant margin at N=HN=H (JH−J2≥0.15J_H - J_2 \ge 0.15). Thus, stopping at the first decline can lose constant utility even when early population utilities are known exactly.
  2. Using Stieltjes integration by parts, both the discrete utility increments GN=JN+1−JN=∫[0,1]xN(1−x)dψ(x)G_N = J_{N+1} - J_N = \int_{[0,1]} x^N(1-x) d\psi(x) and continuous-breadth derivatives J′(t)=∫[0,1]xt(−log⁡x)dψ(x)J'(t) = \int_{[0,1]} x^t(-\log x) d\psi(x) are expressed as transforms of the fixed signed measure dψd\psi against totally nonnegative kernels. Theorem 4.1 proves that the number of sign changes of (GN)(G_N) and J′(t)J'(t) is sharply bounded by the ordered sign complexity osc(dψ)\text{osc}(d\psi), whereas smoothness alone provides no finite bound. Proposition 4.3 provides an explicit C1C^1 log-periodic profile r(x)=12+ε2(1−x)ρcos⁡(ωlog⁡(1−x))r(x) = \frac{1}{2} + \frac{\varepsilon}{2}(1-x)^\rho \cos(\omega \log(1-x)) that satisfies all hypotheses of Theorem 1 and Corollary 3 in Khalaf et al. (NeurIPS 2025) yet exhibits infinitely many reversals.
  3. Theorem 5.1 shows that distinguishing recovery from non-recovery at horizon HH using KK-pool winners requires m=Θ(H/K)m = \Theta(H/K) labeled observations, so passive auditing (K=1K=1) requires Ω(H)\Omega(H) labels while direct winner comparisons require O(1)O(1) labels (at the cost of generating O(H)O(H) candidates per label). Section 6 establishes nonasymptotic minimax squared-error bounds for estimating JNJ_N under general rank design densities qq via the chi-square overlap AN(q)=Eq[(pN/q)2]A_N(q) = \mathbb{E}_q[(p_N/q)^2] and maximum weight BN(q)=∥pN/q∥∞B_N(q) = \|p_N/q\|_\infty (Theorem 6.1), derives the cost-optimal partial-targeting breadth K≤NK \le N balancing generation cost cgc_g and label cost cyc_y (Theorem 6.4), and proves a sharp minimax phase transition under rank-space Hölder smoothness ψ∈Hs(L)\psi \in \mathcal{H}^s(L) for passive auditing: Rm,N(Ψs(L);1)≍s,LNm∧m−2s/(2s+1)\mathcal{R}_{m,N}(\Psi_s(L); 1) \asymp_{s,L} \frac{N}{m} \wedge m^{-2s/(2s+1)} (Theorem 6.5). Appendices B–D and H additionally characterize complete realizability via the bounded-density Hausdorff moment problem and analyze raw-score rank estimation using unlabeled reference pools. Validation is theoretical and analytical, supported by exact closed-form derivations and numerical verification scripts.
Critical strengths
  1. The strongest and most consequential contribution of the paper is Theorem 4.1 paired with Proposition 4.3. Recent work on inference-time reward hacking (Khalaf et al., NeurIPS 2025) claimed via variation-diminishing properties of strictly TP2\text{TP}_2 likelihood families that the expected utility curve of any bounded nonnegative reward is either monotone or has a unique interior extremum. This paper identifies the precise structural error in that claim: differentiating J(t)=∫pt(x)r(x)dxJ(t) = \int p_t(x) r(x) dx yields ∫pt(x)r(x)∂tlog⁡pt(x)dx\int p_t(x) r(x) \partial_t \log p_t(x) dx, where the signed factor r(x)(t−1+log⁡x)r(x)(t^{-1} + \log x) varies with the parameter tt, violating the fixed-measure requirement of Karlin's variation-diminishing theorem. By applying Stieltjes integration by parts, Theorem 4.1 isolates dψd\psi as a tt-independent signed measure integrated against the totally nonnegative kernels xN(1−x)x^N(1-x) and xt(−log⁡x)x^t(-\log x), establishing that ordered sign complexity osc(dψ)\text{osc}(d\psi) is the exact invariant governing reversals. Proposition 4.3 cements this insight with a clean, closed-form Gamma-function counterexample exhibiting infinitely many reversals.
  2. Reducing heterogeneous task-conditional score distributions to a canonical Beta-moment problem on [0,1][0, 1] provides a clean, unified lens for both population curve geometry (Hausdorff moment realizability in Theorem B.1, Abelian tail transfer in Theorem C.1) and finite-sample auditing. In particular, Theorem 6.4 (rate-optimal KK-pool targeting under generation vs. labeling budget constraints) and Theorem 6.5 (the Nm∧m−2s/(2s+1)\frac{N}{m} \wedge m^{-2s/(2s+1)} phase transition showing when local polynomial smoothing at the x=1x=1 boundary beats importance weighting) provide crisp, nonasymptotic characterizations of the fundamental statistical limits of evaluating test-time scaling.
Critical weaknesses
  1. While Theorem 3.1 rigorously proves that a smooth calibration profile can decline at N=3N=3 and recover by 0.150.15 at N=HN=H, the constructed witness ψH\psi_H is an adversarial step-function smoothing whose derivative scales as ∥ψH′∥∞=Θ(H)\|\psi_H'\|_\infty = \Theta(H) and which plants a high-utility plateau specifically on the extreme tail [1−1/H,1][1 - 1/H, 1]. In standard reward overoptimization (Gao et al., 2023), utility eventually declines because extreme verifier scores select out-of-distribution completions that exploit verifier blind spots (ψ(x)\psi(x) decreases near x=1x=1). For a curve to decline at small NN and strongly recover at large NN, the verifier must be miscalibrated at moderately high quantiles (x∈[0.75,1−1/H]x \in [0.75, 1-1/H]) yet become highly accurate again in the extreme tail (x∈[1−1/H,1]x \in [1-1/H, 1]). The paper contains no empirical validation on real language models and verifiers/reward models showing that such multi-reversal profiles (osc(dψ)≥2\text{osc}(d\psi) \ge 2) arise naturally. Without empirical grounding, the recovery phenomenon risks being viewed as a worst-case mathematical construction rather than a practical failure mode of early stopping.

  2. The minimax auditing bounds in Section 6—most notably the partial targeting analysis (Theorem 6.4) and the Hölder smoothness phase transition (Theorem 6.5)—assume the auditor observes exact within-task quantiles Xj=FZj(Sj)X_j = F_{Z_j}(S_j). In practice, the conditional CDF FzF_z of an LLM generator on prompt zz is unknown. While Appendix H.2 addresses raw-score auditing by drawing N−1N-1 unlabeled reference scores per task (Theorem H.1) or sharing a reference pool of size MM under a single homogeneous task law (Proposition H.2), two significant limitations remain: (a) under realistic task heterogeneity, Theorem H.1 requires m(N−1)m(N-1) additional unlabeled candidate generations, which requires the same order of generation compute Θ(mN)\Theta(mN) as direct winner auditing (K=NK=N) while still suffering the worse Θ(N/m)\Theta(N/m) passive label variance; and (b) Theorem 6.5 requires both exact ranks XjX_j and Hölder smoothness Hs(L)\mathcal{H}^s(L) directly on the quantile profile ψ(x)=E[U∣FZ(S)=x]\psi(x) = \mathbb{E}[U \mid F_Z(S)=x] near x=1x=1, which depends sensitively on the extreme-value tail ratio between utility and score distributions and is not shown to be achievable when ranks must be estimated from raw scores.

Questions for authors
  1. Do you have any empirical examples from actual LLM test-time scaling workloads (e.g., math or code generation scored by a learned PRM/ORM or self-consistency heuristic) where the estimated average conditional profile ψˉ(x)\bar{\psi}(x) exhibits a mid-quantile dip followed by an extreme-tail recovery (osc(dψˉ)≥2\text{osc}(d\bar{\psi}) \ge 2)? Alternatively, can you point to a natural structural mechanism—such as task mixtures where different tasks dominate different quantile regimes even after task-conditional rank normalization—that produces Theorem 3.1's behavior without manually placing a narrow spike at [1−1/H,1][1-1/H, 1]?

  2. As noted in Section 3, the smooth witness ψH\psi_H in Theorem 3.1 has derivative norms growing with HH. If ψ\psi is constrained to a fixed Hölder ball Hs(L)\mathcal{H}^s(L) (with s,Ls, L constant as H→∞H \to \infty), what is the largest possible missed utility max⁡n≤HJn−JτH\max_{n \le H} J_n - J_{\tau_H} after a strict decline at τH\tau_H? Can a constant recovery gap still occur if the first decline τH\tau_H is allowed to occur at a larger breadth, or does fixing the Lipschitz/Hölder constant uniformly bound the post-decline recovery?

  3. Theorem 6.5 shows that for N>m1/(2s+1)N > m^{1/(2s+1)}, local polynomial regression near x=1x=1 improves passive auditing risk from N/mN/m to m−2s/(2s+1)m^{-2s/(2s+1)} when exact ranks XjX_j are observed. If XjX_j is not observed and must be estimated using MM task-matched unlabeled reference scores per labeled prompt (as in Section H.2), how must MM scale with mm and ss to preserve the m−2s/(2s+1)m^{-2s/(2s+1)} rate?

1 comment

Thank you for the detailed review and for your positive assessment of the theoretical contributions. I appreciate your careful reading of the paper, particularly the discussion of Theorem 4.1 and Proposition 4.3. I'd like to address your three questions below.

1. Empirical relevance

I agree that empirical evidence would be helpful in understanding whether this kind of recovery occurs in practice. I don't currently have a verified example from an actual LLM/verifier pair showing the pattern in Theorem 3.1.

One possible mechanism is task heterogeneity. Even after normalizing scores within each task, the conditional calibration profiles can differ substantially. Averaging across tasks could therefore produce a profile with multiple changes in direction. However, I haven't established that this happens in real LLM workloads.

The point of Theorem 3.1 is more limited: an initial decline, even when measured exactly at the population level, does not rule out recovery at larger N. I agree that examining how often this occurs with learned verifiers would be a useful next step.

2. Recovery under a fixed Hölder constraint

This is a good point, and I agree that the current construction does not establish the same guarantee under a fixed Hölder constraint.

As noted in the discussion following Theorem 3.1, the constructed profile depends on H. In particular, the recovery region is placed near the extreme tail, and the transition width shrinks as H increases. Consequently, the derivative norms are not uniformly bounded in H.

The theorem guarantees a constant recovery gap for every finite H using a corresponding smooth profile, but this should not be interpreted as a uniform guarantee over a fixed Hölder ball.

A fixed Hölder constraint would restrict how sharply the profile can change near the endpoint. The present argument does not directly address how this restriction affects the maximum missed utility, or whether the same finite-horizon guarantees can be maintained. I agree that this distinction is important.

3. Unknown ranks and reference-pool size

I agree that the assumption of observed ranks in Theorem 6.5 is a limitation when considering practical auditing.

Appendix H.2 addresses the unknown-CDF setting using raw-score comparisons. Theorem H.1 gives an unbiased estimator of J_N using N−1 independent task-matched reference scores per labeled observation, without requiring knowledge of the conditional CDFs. The resulting worst-case squared-error risk is bounded by 1∧N/m1\wedge N/m.

Proposition H.2 also considers using a shared reference pool in the homogeneous setting, which can reduce the additional generation cost.

However, neither result establishes the smoothness-dependent rate in Theorem 6.5 when ranks are unknown. That theorem assumes observed ranks, and the current analysis does not give a sufficient scaling of M for preserving the m−2s/(2s+1)m^{-2s/(2s+1)} rate when ranks must be estimated.

Answering this would require an additional analysis of how the reference-pool size affects the estimation error under the Hölder assumption. I agree that this is an important gap between the theoretical observation model and its practical implementation.

Thank you again for these questions. They help identify where the current guarantees apply and where further analysis would be needed.

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

This paper studies the utility of the best-of-n selection technique and how it changes as n grows in situations where the verifier is imperfect. The paper hinges on a task-conditional rank transform where each score is mapped to its within-task percentile. The utility at breadth n is then the average of this under a beta density. This accumulates around x equal to 1 as n grows. Then the paper goes on to show a few things: for large horizons (greater than 64), the paper's constructions can show a smooth profile whose utility peaks at n equal to 2, declines at 3, and then exceeds the first peak. They also show a tight bound on reversals of the utility curve. The paper is mostly theoretical, with complete proofs and numerical checks.

Critical strengths

The rank transform representation is very clean and gives structural strength to the problem. It lets the authors apply various mathematical techniques to this problem. It makes ad hoc descriptions very checkable, and as per my understanding, the same view exposed a gap in the already published theorem, as mentioned in the paper.

The passive vs targeted separation and the label trade-offs should shed light into why the passively collected labels can miss some large n behavior and how to budget for targeted evaluation. If this is occurring in the wild this should change empirical practice.

Critical weaknesses

The starting motivation of the paper is an empirical warning, but the paper mostly rests on artificially constructed profiles. The theoretical contributions are sound for sure but it is unclear whether these profiles have real occurrence in the wild or they are a contrived mathematical possibility. From my understanding, the transform is cheap to estimate on standard benchmarks. So, the addition of one empirical profile would close this gap.

This is minor, but the paper is compressing many results into a dense presentation. It is somewhat hard to segregate novel results from prior results. It would be good to state most clearly what is new relative to the old works.

Questions for authors

Can we show an estimated profile for at least one real generator-verifier pair, e.g., a math or code benchmark? Is there any empirical evidence of a non-monotone with a recovering tail?

2 comments

Thank you for taking the time to read our paper and for your thoughtful comments. We especially appreciate your positive assessment of the rank-transform formulation and our theoretical contributions. We were also glad to see that you found the passive-versus-targeted evaluation results potentially useful in practice.

1. Empirical relevance

You raise a fair concern. Our recovery example is deliberately constructed, and we agree that showing a similar pattern in a real LLM system would make the practical motivation much stronger.

Theorem 3.1 establishes that an initial decline does not necessarily rule out a substantial recovery at a larger breadth, even with smooth calibration and a fixed generator–verifier pair. But it does not tell us how often this happens in practice, or whether the particular pattern in our construction occurs naturally.

We think your suggestion of estimating a calibration profile from a real generator–verifier pair is a good way to investigate this. For a math or coding benchmark, one could generate multiple responses per task, assign verifier scores, and independently check their correctness. The scores could then be converted into within-task percentiles, allowing us to estimate the average calibration profile across tasks.

We agree that estimating the score ranks themselves can be relatively inexpensive. Our concern is not the rank transformation, but obtaining enough reliable utility labels to determine what happens in the extreme tail.

In our construction, the region responsible for recovery has probability mass only 1/H1/H under passive sampling, yet it can substantially affect the selected winner at breadth HH. This is part of the motivation for our auditing results: even when score ranks are available, the relevant utility behavior may be difficult to estimate from passively collected labels.

We do not currently have empirical evidence of a recovering tail in an actual LLM system, and we do not want to suggest otherwise. We have acknowledged this limitation in Section 8 (p. 9).

Our main aim here is to establish that recovery is mathematically possible and to understand what determines its behavior and detectability. Whether the same phenomenon appears in real systems is an important question that remains open. We appreciate you raising it.

2. Novelty relative to prior work

We also appreciate your comment about distinguishing our contributions from existing results. This is a useful distinction, particularly because our analysis draws on several classical mathematical tools.

The Beta distribution of the winning rank is a standard order-statistic result, and the underlying techniques from moment theory, total positivity, and importance sampling are not new. We do not claim otherwise.

What we believe is new is what these tools allow us to establish about Best-of-N utility.

Theorem 3.1 shows that stopping after the first decline can miss a constant improvement, even at a finite horizon. Theorem 4.1 gives a sharp bound on the number of utility reversals, while Proposition 4.3 identifies a counterexample to the published TP2-based shape claim.

The statistical results address a different but related question: even if recovery is possible, how much evaluation data would we need to recognize it? Theorem 5.1 shows why passive labels can miss the relevant region, while Section 6 studies how distribution mismatch, generation costs, and smoothness affect evaluation accuracy.

We see these as the main contributions of the paper, rather than the classical techniques themselves. The distinction is discussed in the Contributions section (p. 2) and Related Work (p. 8).

Thank you again for your encouraging assessment and for pointing out these limitations. Your comments have helped us think more carefully about the gap between what our theoretical results establish and what would need to be demonstrated empirically. We hope this response makes that distinction clearer.

Thanks for the response! I also appreciate the acknowledgement in the limitations section. I maintain my positive assessment of the theoretical novelty and would like to keep my rating.

Reviewer_AqofOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper identifies and explains an interesting phenomenon: there exist instances where utility from best-of-NN inference declines at small NN (due to mismatch of verifier score & true utility) but recovers at larger NN. The paper makes a clean decomposition: expected best-of-NN utility is a family of Beta-weighted averages of one calibration profile. They use this decomposition to construct a family which exhibits initial decline in utility from N=2N=2 to N=3N=3 but ultimately recovers more utility at N=HN=H for any choice of HH. To reason about best-of-NN inference in the face of this phenomenon, the paper bounds number of reversals and studies how much data is necessary to understand whether further recovery (exceeding utility at larger NN despite current decrease) is possible.

Critical strengths

The paper identifies an interesting phenomenon and includes clean theoretical contributions that illuminate it. The decomposition in (1) is understandable and clearly simplifies the resulting analysis. The sharp reversal bound of Theorem 4.1 is informative and Proposition 4.3 seemingly provides a counterexample to a published result; the counterexample motivates Theorem 4.1 which provides the necessary characterization for the specific Beta family. In general, the paper rigorously tackles an interesting question with a clean/well-motivated approach. Its theoretical contributions are novel and significant.

Critical weaknesses

The most significant weakness of the paper is presentation quality. Despite careful reading, the main text is difficult to follow. Statements are rigorous, but I wish that notation and jargon were better explained.

Whereas the terms UU, ii, SS, ZZ, etc… can be inferred from context in the introduction, it would be helpful to state that we care about the expected final utility UU over some distribution of tasks ZZ, where the UU is the utility of the chosen candidate i^N\hat{i}_N which is chosen since it maximizes the verifier score SiS_i. The rank transform of (1), which is a fundamental observation of the paper, can also be better explained.

The exposition problem is progressively worse as the theory becomes more complex. For example, it seems Theorem 4.1 is saying that best-of-N utility curve can reverse direction at most kk times if the calibration profile changes direction kk times. It would be helpful for an expository description of this Theorem. Section 6 is very hard to parse and reads like a list of very deep / complicated results.

Decision: Weak reject; willing to move to weak accept / accept.

Reason: The paper offers substantive theoretical contributions and addresses an interesting and novel question. Currently, too much of the paper is hard to parse for it to warrant acceptance at this stage. I am willing to move towards weak accept / clear accept if the authors demonstrate willingness and ability to improve the expository quality of the paper, especially in Section 6.

Questions for authors

See above. To highlight a few:

  • Questions: can you explain Theorem 4.1? Is it a surprising result? It seems deep techniques are necessary for the proof; are these due to difficulty of formalization or because the result is unexpected and deep?
  • It seems Section 4.1 is offering a counterexample to a published result. Is this the case?
  • Can you please offer a comprehensive and complete clarification of Section 6, including exposition of the results, why they matter, and why they were presented in that order?
3 comments

Thank you for taking the time to read our paper so carefully. We particularly appreciate your positive assessment of the theoretical contributions, especially the sharp reversal bound and the counterexample to the published result.

We also appreciate your comments on the presentation. Looking back at the manuscript, we agree that we moved too quickly through some arguments, especially in Section 6. We have revised the paper to make the main ideas and their connections easier to follow.

1. Theorem 4.1

Your interpretation is correct. If the calibration profile has at most kk ordered sign changes in dψd\psi, Best-of-N utility can reverse direction at most kk times. An increase–decrease–increase profile, for example, allows at most two reversals. The bound is sharp, although a particular profile need not attain it.

The key step is expressing both the discrete utility increments and the continuous-breadth derivative as transforms of the same signed measure dψd\psi, independent of NN and tt. This allows us to apply classical variation-diminishing theory for kernels that are totally positive of all orders.

The variation-diminishing principle itself is classical, so that part is not surprising. What is less obvious is finding a fixed-measure representation for both quantities and proving the bound sharp. The main difficulty lies there, rather than in developing a new variation-diminishing theorem. We have added this intuition and examples in Section 4 (pp. 3–4).

2. Counterexample to Khalaf et al. (2025)

Yes. Proposition 4.3 provides a counterexample to the one-extremum conclusion of Theorem 1 in the NeurIPS 2025 proceedings version of Khalaf et al., under its stated assumptions.

Differentiating the expected reward introduces a signed input that depends on the same parameter as the kernel, whereas the usual variation-diminishing argument requires a fixed input. It therefore cannot be applied directly. Our construction satisfies the stated assumptions but exhibits infinitely many reversals.

We have clarified the scope of the counterexample in Section 4.1 (p. 4). Our point concerns the theoretical shape claim, not the empirical findings or mitigation methods of that work.

3. Section 6

We agree with your point about Section 6. The previous version introduced several technical results without enough guidance on why they mattered or how they were connected. We have added a roadmap (p. 5) and revised the explanations (pp. 6–8) around three questions.

First, how accurately can we estimate JNJ_N when evaluation data come from a different distribution than the target winners? Theorem 6.1 gives general minimax bounds in terms of distribution overlap. In particular, AN(q)=1+χ2(pN∥q)A_N(q)=1+\chi^2(p_N\Vert q) controls the importance-weighting variance bound, while the maximum importance weight also affects the lower bound. Corollaries 6.2 and 6.3 show when the bounds match and why passive labels can be much less informative than winner labels.

Second, if winner evaluation is statistically efficient, should we always generate NN candidates for each label? Not necessarily, since generation has a cost. Theorem 6.4 balances generation and labeling costs, giving a pool-size choice that is rate-optimal up to a constant factor within fixed-KK designs (p. 7).

Third, can smoothness make passive evaluation more efficient? Under a Hölder condition, Theorem 6.5 gives minimax risk of order

\min\left\\{\frac{N}{m},m^{-2s/(2s+1)}\right\\}.

The transition at N≍m1/(2s+1)N\asymp m^{1/(2s+1)} occurs as the winner distribution concentrates near rank one. Once this region is narrower than the resolution of passive data, smoothness lets neighboring ranks provide useful information. Boundary local-polynomial estimation can then improve on direct importance weighting. As clarified in the revision, this result assumes observed ranks.

The progression is thus from distribution mismatch to the generation–label tradeoff, and finally to what smoothness can improve. Section 5 tests recovery directly; Section 6 instead studies estimation at a fixed breadth, which helps quantify the effort needed for reliable comparisons across breadths.

Thank you again for pointing out the issues with our presentation. We hope that the revisions have made the individual results and their connections easier to understand.

Thanks again for your review. I just wanted to follow up before the discussion period ends. We've made several changes to the exposition, especially in Section 6, based on your feedback.

Would be interested to hear if you think these address your main concerns, or if there's anything you'd still like us to clarify.

Thank you to the authors for the thoughtful comments. I have revised my score

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.