acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

Best-of- selection returns the response with the highest judge score among candidates. As 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 responses ordered by judge score, the quality curve averages the outcome of the highest-ranked response in a uniformly random -subset, for every . Under independent queries at chosen ranks with outcomes in , we establish matching upper and lower bounds of on the minimax expected label cost for simultaneous error at confidence . 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.

Primary area:
learning theory
Keywords:
LLM-as-a-judge, best-of-n selection, label complexity, minimax rates, label-efficient evaluation, optimal allocation, inference-time scaling

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_Su3KOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

Given an input and a pool of L responses, best-of-k selection returns the best response (based on the judge scores) for a subset of responses of size k≤Lk \le L. As the judge might overestimate the quality of a response, one can use Quality curves that quantify the (weighted) quality of a response at position k based on the judge's score. The paper's central investigation is the minmax label cost, which defines the minimum number of labeled responses needed to estimate the quality curves. Throughout the paper, theoretical insights are gained on the complexity of approximating the quality curves. Experiments show that envelope, MMV, and GW perform among the best of the techniques investigated.

Critical strengths

[S1] Experimental Diversity: The authors conduct experiments spanning a vast range of generators, judges, and settings. In each experiment, the 8 studied methods are compared.

[S2] Theoretical Results: The shown bounds and insights hold for almost all the investigated methods of estimating quality curves (not MMV and GW) and, as such, provide strong insight into the approximation problem for those methods. Whilst the write-up is difficult to follow, the authors also consider sampling with replacement (Section 3) and without replacement (Section 4).

Critical weaknesses

[W1] Presentation and Writeup: The overall derivations of the theory are difficult to follow. A clear red line is missing, and the section order seems quite modular and does not read as a cohesive research insight. Some wording, such as „pools of interest“, „corpus“, and the link between „quality“ and „trusted outcome“, is not clearly described or defined, which makes the paper difficult to understand. Sections, in general, are formed rather loosely and seem quite modular, making it difficult to follow and understand the insights in the general paper. Missing links of contributions to the specific results further cause this. Another example is Theorem 2, which does not seem to contain a dedicated proof, nor is it named where one can find any. It seems the proof is scattered around the manuscript, with the lower bound proved in Theorem 5 and the upper bound at the beginning of Section 3.3, or at least that is what my readings suggest. Overall, I conclude that the paper is difficult to follow; a rewrite is necessary to align the storyline, the insights from the sections, and the section arrangement.

Questions for authors

[Q1] Can you point to the Proof of Theorem 2? It seems not to be contained in the paper directly. Only a reference to the lower bound is made in the Appendix, but not an upper bound.

[Q2] Can you provide details on what is meant by „finite time τ\tau“? How do the methods use these finite times, or is that not necessary due to the insights of Theorem 2?

[Q3]: Why does Figure 2 show the first audit replication and not the mean of all 1000 audits, as indicated by the blue range? This caused some confusion with the plotting, particularly for the MATH / InternLM figure.

[Q4] Could you provide more details on the derivation of equation (3)? I can not fully follow the argument.

[Q5] Why is equation (10) not also a correction for the envelope sampling in (4) and using the prediction-plus-correction from equation (5)? More broadly, what is the connection between Eq. (5) and (10)?

[Q6] What is the reason for Table 2 to use n=512n=512 and n=2Ln=2L for the different settings? What is the effect of nn on these settings? In D.3, the number of budgets differs between the different settings of LL. Why were the choices not equivalent overall, like $L, 2L, 4L, 8L, … $?

4 comments
AuthorsOpenReview ↗

Response to Reviewer Su3K (1/2)

Thank you for your careful reading, for your appreciation of the breadth of the experiments and of the theoretical results, and for your concrete guidance on the presentation. As you suggested, we have rewritten the paper to align the storyline, the insights of the sections, and their arrangement. The revised PDF has been uploaded, and our comment "Summary of the revision" describes the changes. We respond to each of your points below, with pointers to the revised paper.

W1 (red line, terms, links).

  • Red line. The introduction describes what a quality curve is used for, evaluating a judge on a given task and choosing the candidate budget, and ends with the central question. Section 2 defines the setup and what an accurate curve provides. Section 3 answers the question when each label is an independent draw at a chosen rank (sampling with replacement). Section 4 gives the audit for a stored corpus in which each response is labeled at most once (sampling without replacement), with an error bound that is computable before labeling. Section 5 tests the audits on corpora with complete labels and returns to the uses described in the introduction, evaluating a judge (Section 5.1) and choosing the candidate budget for new inputs (Section 5.2). Each contribution in Section 1.1 cites the section that establishes it.
  • Terms. A pool is the LL scored responses to one input, and a corpus is the pools of MM inputs. Quality is the trusted outcome of a response, and a label is one such outcome obtained by the audit. Section 1 introduces these terms and Section 2.1 gives their definitions. The revised paper uses "corpus" throughout, replacing "pools of interest".

Q1. The proof of Theorem 2 now follows its statement in Section 3.2. It combines the upper bound of Theorem 4 (Section 3.3; proved in Appendix A.2) and the lower bound of Theorem 5 (Section 3.4; proved in Appendix A.3).

Q2. τ\tau is the number of labels an audit uses (Section 2.3). An audit may stop based on the labels it has observed, which makes τ\tau a stopping time. Every method in the paper uses a number of labels TT fixed in advance, the special case of a constant τ\tau. Stopping times appear in Definition 1 so that the lower bound also covers audits that stop adaptively, and Theorem 2 shows that such audits cannot improve the order of the label cost (Section 3.2).

Q3. Figure 2 is meant to show what a single audit delivers. The estimator is unbiased, so the mean over the 1,000 audits coincides with the reference curve and would not show the error of an individual audit. The shaded band gives the pointwise 2.5th to 97.5th percentiles over the 1,000 audits and shows their spread. The original submission plotted the first replication, an audit chosen without regard to its outcome. For MATH / InternLM this replication was at the 99.6th percentile of the maximum error, so its curve left the band at small budgets, which caused the confusion you describe. The revised Figure 2 shows a typical audit instead, the one whose maximum error is the median of the 1,000 audits (Section 5.1; protocol in Appendix F.2).

AuthorsOpenReview ↗

Response to Reviewer Su3K (2/2)

Q4. Equation (3) in Section 2.2 states that the budget with the highest estimated utility has utility within 2ε2\varepsilon of the highest:

max⁡k(θk−ck)−(θk^−ck^)≤2ε.\max_k(\theta_k-c_k)-(\theta_{\widehat k}-c_{\widehat k})\le2\varepsilon.

Here θk−ck\theta_k-c_k is the utility of budget kk, ckc_k is the cost of using kk candidates in units of quality, and k^\widehat k maximizes the estimated utility θ^k−ck\widehat\theta_k-c_k. To derive it, let k⋆k^\star maximize the utility. If ∣θ^k−θk∣≤ε|\widehat\theta_k-\theta_k|\le\varepsilon for every kk, then

θk⋆−ck⋆≤θ^k⋆−ck⋆+ε≤θ^k^−ck^+ε≤θk^−ck^+2ε.\theta_{k^\star}-c_{k^\star}\le\widehat\theta_{k^\star}-c_{k^\star}+\varepsilon\le\widehat\theta_{\widehat k}-c_{\widehat k}+\varepsilon\le\theta_{\widehat k}-c_{\widehat k}+2\varepsilon.

The outer inequalities use the error bound at k⋆k^\star and at k^\widehat k, and the middle one holds because k^\widehat k maximizes the estimated utility. Section 2.2 gives this derivation after Equation (3).

Q5. Equations (5) and (10) are the same estimator, and with fixed quotas no correction term remains. Equation (5) is

θ^k=Gk+1T∑t=1TakRtqRt(Yt−gRt),Gk=∑rakrgr.\widehat\theta_k=G_k+\frac1T\sum_{t=1}^T\frac{a_{kR_t}}{q_{R_t}}(Y_t-g_{R_t}),\qquad G_k=\sum_r a_{kr}g_r.

Grouping the sum by rank, with NrN_r the number of queries at rank rr and Y‾r\overline Y_r their mean outcome, gives

θ^k=Gk+∑rakrNrTqr(Y‾r−gr).\widehat\theta_k=G_k+\sum_r a_{kr}\frac{N_r}{Tq_r}(\overline Y_r-g_r).

Under fixed quotas, T=nT=n, Nr=nrN_r=n_r, and qr=nr/nq_r=n_r/n, so the factor Nr/(Tqr)N_r/(Tq_r) equals one, the predictions grg_r cancel against GkG_k, and what remains is Equation (10),

θ^k=∑rakrY‾r.\widehat\theta_k=\sum_r a_{kr}\overline Y_r.

Envelope enters (10) through the quotas nrn_r, which follow qenvq^{\rm env} (Algorithm 2). Section 4.1 gives this derivation after Equation (10).

Q6. The two budgets of Table 2 follow from the pool sizes LL. Fixed quotas label at least one response at every rank (Algorithm 2), so they require n≥Ln\ge L. The budget 512 is therefore unavailable for the large pools (L≥1024L\ge1024), which Table 2 reports at 2L2L, the smallest multiple of LL at which the allocations differ (at n=Ln=L they coincide). For the small pools (L=14L=14, 16, or 32), a budget of 2L2L gives one label to every rank and leaves only LL labels to distinguish the allocations. The errors of the six non-uniform allocations then differ by at most 6% (Appendix L), so the budget 512 is more informative for comparing them. To put all pools on the common scale you suggest, the new Appendix L reports the small pools at 2L2L, 4L4L, and 8L8L (Table 32). On the effect of nn, Envelope's error decreases approximately as 1/n1/\sqrt n or faster for both the small and the large pools, and at every label budget it is below Uniform's and comparable to that of the numerically optimized designs (Appendix E; Appendix L for the small pools at 2L2L, 4L4L, and 8L8L).

We hope that these responses and the revised paper address your concerns. We would be happy to provide further clarification if needed.

Thank you for your response.

Thank you for clarifying my questions, and I feel my questions are resolved. However, the revision is not marked (e.g., in blue), so I cannot see what changed in the text, which makes it difficult to assess a revision described as a rewrite. I therefore maintain my score. I would also be interested in reviewer 32pG’s view on the rebuttal, in particular regarding the significance of the results.

Thank you for your reply. We are glad to hear that our responses resolved your questions.

In response, we have uploaded the revised PDF with the changes marked in blue, and our comment "Summary of the revision" describes these changes. The revision mainly improves the presentation, following the reviewers' suggestions, and keeps the main claims, theorems, algorithms, and experimental results of the original submission.

On the significance of the results, the introduction of the paper presents the motivation for the problem and the intuition behind our approach, Section 1.1 states the contributions, and Section 1.2 positions them relative to prior work. We hope that these sections convey the significance clearly, and that the marked version makes the revision easier to read and to assess.

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

This paper studies how to efficiently estimate the quality of Best-of-(k) selection across different candidate budgets using a limited number of trusted outcome labels. The authors formulate the problem as estimating an entire quality curve and propose a shared importance-sampling estimator that reuses labels across candidate budgets. They introduce Envelope, a simple and computationally efficient rank allocation strategy that minimizes the maximum importance ratio. The paper establishes matching minimax upper and lower bounds on label complexity, including a lower bound that allows adaptive querying and stopping, and extends the analysis to finite corpora.

Critical strengths
  1. The paper addresses an important and practical problem: how to efficiently estimate the quality of Best-of-(k) selection across different candidate budgets without requiring expensive labels for every response. The idea of reusing a limited set of trusted labels to estimate the entire quality curve is intuitive and well motivated, with clear relevance to inference-time scaling and evaluation cost reduction.

  2. The paper provides rigorous theoretical guarantees, including matching minimax upper and lower bounds on label complexity, even allowing adaptive querying and stopping. The proposed Envelope allocation is simple, computationally efficient, and theoretically justified. The experiments cover diverse tasks, generators, and judges, with comparisons against strong sampling baselines, providing convincing support for the proposed approach.

Critical weaknesses

None

Questions for authors

The theoretical analysis focuses on reducing the number of trusted labels while assuming that candidate responses and judge scores are already available. Could the authors clarify the practical scenarios in which obtaining these labels dominates the cost of candidate generation and scoring? This seems particularly relevant to mathematical reasoning benchmarks, where correctness labels can often be obtained automatically. How would accounting for the full evaluation cost affect the practical benefits of the proposed method?

1 comment
AuthorsOpenReview ↗

Response to Reviewer X36n

Thank you for your thoughtful review and for your positive assessment of the problem, the theoretical guarantees, and the experiments. The revised PDF has been uploaded; it addresses your question about cost in Section 2.1 and in the new Appendix K, and we summarize the answer below. Our comment "Summary of the revision" describes the other changes.

How the paper accounts for cost (Sections 2.1 and 2.2; Appendix K). An audit involves costs at different stages. Before the audit, the corpus is built by generating and scoring its MLML responses. This cost is computation, it is incurred once, and the same corpus serves every candidate budget k≤Lk\le L. During the audit, each label requires a trusted evaluation, and the number of labels is the cost that our theorems count. After the audit, the estimated curve is used to choose the candidate budget kk for new inputs at deployment, where each input incurs the cost ckc_k of generating and scoring kk candidates. Section 2.2 chooses the budget with the highest estimated quality minus ckc_k, and Equation (3) shows that its utility is within 2ε2\varepsilon of the highest. In the experiments of Section 5.2, the budgets chosen in this way average 138 and 29 of the 2,048 available candidates for two generators.

When labels dominate (Section 1; Appendix K, "When labels dominate"). A judge is used for selection where the trusted evaluation is unavailable at inference time, because each evaluation is costly or because it requires a reference answer. In translation, summarization, and open-ended generation, the trusted evaluation is a human rating of each response. Machine translation is a documented case. Systems sample up to 1,024 candidates per sentence and select with a quality-estimation model, and published studies collect human ratings at one or two candidate budgets on 50 to 400 sentences (Fernandes et al., 2022; Kovacs et al., 2024; Tan et al., 2025; cited in Section 1.2 and Appendix K); Tan et al. attribute their choice to time and cost. For 1,000 sentences with 256 candidates each, labeling every candidate requires 256,000 ratings, and 8,192 ratings guarantee error 0.027 at all 256 candidate budgets with probability 0.95 (Section 4.1; Table 30).

Mathematical benchmarks (Section 5; Appendix K). Labels are indeed automatic there, because every benchmark question has a reference answer. We use these benchmarks as test cases. Measuring the error of an audit requires the complete curve, hence a label for every response, and automatic checks provide this for pools of up to 2,048 responses. A deployed system receives questions without reference answers, which is why it selects with a reward model. Our SummEval and WMT22 experiments use human ratings.

Counting the cost of the corpus (Appendix K, "Adding the cost of building the corpus"; Table 31). The cost of generating and scoring the corpus is the same under every allocation of labels, so the comparison between allocations is unaffected. Let cgenc_{\rm gen} be the cost of generating and scoring one response, in units of the cost of one label. Without the cost of the corpus, labeling all MLML responses costs ML/nML/n times as much as an audit with nn labels; with it, the ratio is (cgen+1)/(cgen+n/(ML))(c_{\rm gen}+1)/(c_{\rm gen}+n/(ML)). For WMT22 English to German with 512 labels, the ratio is 36 without the cost of the corpus, 26.7 at cgen=0.01c_{\rm gen}=0.01 (one label costs as much as 100 responses), 8.6 at cgen=0.1c_{\rm gen}=0.1, and 1.9 at cgen=1c_{\rm gen}=1.

Thank you again for your supportive review. We hope that our response answers your question.

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

This work is concerned with best-of-kk selection, a procedure meant for improving LLM responses to an input by scaling inference and with LLM judges for scoring. The authors consider the objective of estimating the so-called quality curve θ\theta which characterises the best-of-kk selection procedure. They focus on the estimation task in the max norm with a prescribed accuracy level ϵ\epsilon and confidence level δ\delta given a pool of LL responses. The authors assume a noisy observation model, and ask what is the sample complexity of identifying the quality curve denoted θ\theta. They first provide a minimax lower bound on the number of queries m⋆(L,ε,δ)m^\star(L, \varepsilon, \delta) required to identify θ\theta, and establish matching upper and lower bounds characterising the scaling of m⋆m^\star with respect to L,ε,δL, \varepsilon, \delta, namely scaling as log⁡(L)(log⁡(1/δ)+log⁡log⁡(L))/ϵ2\log(L)(\log(1/\delta)+\log\log(L))/\epsilon^2. They later provide an envelop algorithm with a simple corrected estimator see (Algorithm 1) and provide a guarantee on its estimation error exhibiting the minimax scaling log⁡(L)(log⁡(1/δ)+log⁡log⁡(L))/T\sqrt{\log(L)(\log(1/\delta)+\log\log(L))/T} where TT is the budget of samples (see Theorem 4 where BL≤1+log⁡(L)B_L \le 1+ \log(L)), thus matching their established lower bound. The authors later extend their results to a finite corpus setting, where one has MM pools of size LL. Finally, they provide experimental results to complement their results.

Critical strengths
  1. Auditing best-of-kk selection is an interesting and timely problem for improving LLM responses at inference time. Providing a statistical understanding of such problem is compelling.

  2. The authors provide a sample complexity minimax lower bound on the estimation of the so-called quality curve characterizing best-of-k selection. The authors also provide an envelop algorithm that leverages a simple corrected estimator that enjoys an estimation upper bound matching the lower bound. Providing a minimax lower bound and a matching upper bound although under a fixed budget is a nice result.

  3. The authors provide real-world experimental results complementing their theoretical results which is appreciated.

Critical weaknesses
  1. One of the major weaknesses of this work is a lack of clarity and rigour in the problem description and presented results. (Please see questions). This makes it very hard to follow the paper, situate the paper within the literature, and thus gauge the significance of the paper. The authors must resolve this.

  2. The provided performance guarantee of the algorithm, namely the scaling of order BLlog⁡(BL/δ)/T\sqrt{B_L\log(B_L/\delta)/T}, is somewhat expected for a worst case estimation bound in the infinity norm. It is unclear what are the key challenges in deriving such result, and what are the new insights from such analysis.

  3. The lower bound is valid for algorithms with a stopping rule, yet the proposed algorithm uses a fixed budget. A fixed budget setting may have a lower complexity than a fixed confidence problem (with a stopping rule construction). This is a subtle point that is not well discussed and therefore optimality is not yet established.

  4. The authors only provide a minimax lower bound, which only provides a worst case understanding of the problem. Providing a more refined lower bound, one that is instance-dependent would be much more interesting. This might also require a much more interesting and insightful algorithm design.

  5. The extension to the finite corpus case is okay, but it remains unclear how meaningful or insightful is such an extension, and what are the key challenges.

Questions for authors
  1. This work needs a mathematically more precise and well presented problem description. Right now, it is quite obscure what is the learning objective and observation model. Does the learner observe kk observations at each round? or is it just one observation with the objective of finding the top-kk? what is the observation model? do you observe the scores or some noisy version of it? is kk fixed? Also how is the model different from combinatorial bandits which seems to be related?

  2. In Definition 2, the minimax constant m⋆(L,ε,δ)m^\star(L, \varepsilon, \delta) is defined depends on a certain class of procedures for estimating the quality curve. What kind of procedures? are these procedures adaptive? is there some notion of sigma-algebra or filtration used to model past observations? what observations these procedures use?

  3. Can you define N(η,F,L2(Q))\mathcal{N}(\eta, \mathcal{F}, L_2(Q)) explicitly? what is L2(Q)L_2(Q)? This should be given in a notation section. Do you also need to provide Lemma 3 in the main manuscript?

  4. In the main text, you should reference where the proofs of theorems are given. For instance, after presenting Theorem 2, where is the proof?

  5. I am very confused regarding the setting. Definition 2, introduces τ\tau and suggests it is a stopping time, in view of the expectation used to define m⋆(L,ε,δ)m^\star(L, \varepsilon, \delta). However, Theorem 2 seems to require TT to be fixed. I suggest the authors clarify this and add a discussion. The sample complexity of fixed budget and fixed confidence setting can be quite different. Could clarify this part? in view of this discrepancy, can you justify the minimax optimality of your result?

  6. What is Y‾r\overline{Y}_r?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 32pG (1/2)

Thank you for your thorough and technically detailed review, and for your encouraging comments on the problem, the matching bounds, and the experiments. We have revised the paper in response to your comments. The revised PDF has been uploaded, and our comment "Summary of the revision" describes the changes. We respond to each of your points below.

W1, Q1, Q2 (problem description). Sections 2.1 and 2.3 present the setup and the protocol. In answer to your questions:

  • What is observed. In each round the audit chooses one rank rr and observes one label Y∈[0,1]Y\in[0,1], drawn from an unknown distribution PrP_r with mean μr\mu_r (Section 2.3).
  • Scores. Judge scores are known for every response, without noise, and serve to rank the responses. The labels are the costly, noisy observations.
  • Objective and the role of kk. The audit does not choose kk and does not look for a top-kk set. It estimates all LL values θk=∑rakrμr\theta_k=\sum_r a_{kr}\mu_r, k=1,…,Lk=1,\dots,L, within ε\varepsilon simultaneously, with probability 1−δ1-\delta. The weights are the known selection probabilities akr=(r−1k−1)/(Lk)a_{kr}=\binom{r-1}{k-1}/\binom{L}{k} for r≥kr\ge k (Equation (2)).
  • Class of procedures. An audit is a sampling rule that chooses the rank RtR_t from the history Ht−1H_{t-1} and internal randomness UU, a stopping time τ\tau of the filtration Ft=σ(U,Ht)\mathcal F_t=\sigma(U,H_t), and an Fτ\mathcal F_\tau-measurable estimate. m⋆m^\star is the infimum of sup⁡PEPτ\sup_P\mathbb E_P\tau over (ε,δ)(\varepsilon,\delta)-accurate audits (Definition 1).
  • Combinatorial bandits. In bandit terms, an audit is pure exploration with one arm per rank. Combinatorial pure exploration and transductive linear bandits also involve linear functionals of arm means, but they identify a best arm or set, at a cost that depends on gaps. Our task is to estimate LL known functionals to a fixed tolerance, and its cost does not depend on gaps (Section 1.2).

W2 (challenges and insights). The key steps of the analysis, and what each of them shows, are the following.

  • Allocation (Sections 3.1 and 3.3). Uniform sampling of ranks has largest importance ratio LL and needs of order Lε−2log⁡(1/δ)L\varepsilon^{-2}\log(1/\delta) labels for θL\theta_L alone. Envelope, qrenv=br/BLq_r^{\rm env}=b_r/B_L with br=max⁡kakrb_r=\max_k a_{kr} and BL=∑rbrB_L=\sum_r b_r (Equation (4)), is a closed-form allocation that minimizes the largest importance ratio, and BL≤1+log⁡LB_L\le1+\log L.
  • Covering (Section 3.3; Lemma 3 in Appendix A.1.1). Envelope with a union bound over the LL budgets gives ε−2log⁡Llog⁡(L/δ)\varepsilon^{-2}\log L\log(L/\delta) labels. Because each rank's selection probability rises and then falls in kk, at most 1+2/η21+2/\eta^2 representative budgets cover all LL budgets at resolution η\eta. The proof needs O(log⁡L)O(\log L) of them, so the union bound costs log⁡log⁡L\log\log L in place of log⁡L\log L.
  • Lower bound (Section 3.4, Theorem 5; proof in Appendix A.3). No adaptive sampling or stopping rule removes the factor log⁡L\log L or the term log⁡log⁡L\log\log L. This is the main technical result. The curve contains about log⁡8L\log_8L scales of ranks, each hiding a sign that any accurate estimate must recover, and the signs stay independent under adaptive stopping.

The resulting insight is that the entire curve of LL budgets costs a polylogarithmic factor in LL more labels than a single budget fixed in advance, whereas current practice evaluates every candidate automatically or collects human ratings at one or two candidate budgets (Section 1.2).

AuthorsOpenReview ↗

Response to Reviewer 32pG (2/2)

W3, Q5 (fixed budget and stopping rules). Section 3.2 relates the fixed budget of the upper bound to the stopping times of the lower bound, and Appendix A.3 gives the argument in full. A fixed number of queries is a constant stopping time, so audits with a fixed budget form a subclass of the audits in Definition 1. Let T⋆T^\star be the smallest fixed number of queries with which some audit is (ε,δ)(\varepsilon,\delta)-accurate, and let ρ=ε−2log⁡L⋅(log⁡log⁡L+log⁡(1/δ))\rho=\varepsilon^{-2}\log L\cdot(\log\log L+\log(1/\delta)). The subclass relation and Theorem 5 give T⋆≥m⋆≥cρT^\star\ge m^\star\ge c\rho, so a fixed budget cannot require fewer labels than the lower bound. Theorem 4 shows that Envelope with a fixed number of queries of order ρ\rho is accurate, so T⋆≤CρT^\star\le C\rho. Hence cρ≤m⋆≤T⋆≤Cρc\rho\le m^\star\le T^\star\le C\rho, and adaptive stopping cannot improve the worst-case order.

In exact best-arm identification, the number of samples needed grows without bound as the gap shrinks, so no fixed number of samples is δ\delta-correct on every instance, and the two complexities can differ (Kaufmann et al., 2016). Our criterion is a worst-case tolerance ε\varepsilon, which a fixed budget meets on every instance. The same holds in (ε,δ)(\varepsilon,\delta)-PAC best-arm identification, where a fixed sample size attains the worst-case complexity (Even-Dar et al., 2002) and the lower bound covers every sampling policy (Mannor and Tsitsiklis, 2004); the references are in Section 3.2 and Appendix A.3.

W4 (instance-dependent bound). Thank you for this suggestion, which we followed in the new Appendix J. Proposition J.1 holds for every adaptive (ε,δ)(\varepsilon,\delta)-accurate audit. For δ≤1/8\delta\le1/8 and ε<V⋆(σ2)/(8BL)\varepsilon < V^\star(\sigma^2)/(8B_L),

EPτ≥V⋆(σ2)12ε2log⁡1δ,V⋆(σ2)=inf⁡qmax⁡k∑rakr2σr2qr,\mathbb E_P\tau\ge\frac{V^\star(\sigma^2)}{12\varepsilon^2}\log\frac1\delta,\qquad V^\star(\sigma^2)=\inf_q\max_k\sum_r\frac{a_{kr}^2\sigma_r^2}{q_r},

where σr2\sigma_r^2 is the outcome variance at rank rr on the instance PP. With all variances equal to 1/41/4, the bound has the order of the minimax rate up to the term log⁡log⁡L\log\log L (Appendix J.1). On 17 correctness corpora, V⋆(σ2)V^\star(\sigma^2) is 91% to 99% of its largest value, so these instances are close to the worst case (Appendix J.2, Table 26). On the human-rating corpora the variances are smaller, and predictions fitted to judge scores in estimator (5) lower Envelope's error on SummEval from 0.0255 to 0.0146 (Table 27).

On algorithm design, the bound depends on the instance through the rank variances, so the algorithm it suggests adapts the allocation to them. Appendix J.3 tests such an audit, with the variances estimated from a pilot sample counted in the label budget. Under the same estimator, the fitted allocation does not reduce the mean error relative to the Envelope allocation in any collection (Table 27). With equal variances, Envelope's largest variance is at most 1.22 (L=32L=32) to 1.30 (L=2048L=2048) times that of the best allocation, while the pilot uses an eighth or a quarter of the labels.

W5 (finite corpus). Section 4 is the case met in practice. The scored pools are stored, each response can be labeled at most once, and the target is the curve of that corpus. Section 4 gives the audit for this case (Algorithm 2) and an error bound that holds for every set of outcomes and is computable before any label is collected (Theorem 6), so the label budget can be chosen in advance. For M=1,000M=1{,}000 pools of L=256L=256 responses, 8,192 labels (3.2% of the responses) guarantee error 0.027 at all 256 budgets with probability 0.95 (Section 4.1; Table 30). The results of Section 3 do not transfer directly. Labels at one rank are dependent, the covering argument has to work without independent observations (Appendix B.3), and the lower bound has to be transferred from independent queries to a fixed corpus (Appendix B.2), which is the source of the condition on MM in Corollary 7.

Q3. N(η,F,L2(ν))\mathcal N(\eta,\mathcal F,L_2(\nu)) is the smallest number of functions such that every member of F\mathcal F lies within distance η\eta of one of them in the norm ∥f∥L2(ν)=(∫f2dν)1/2\Vert f\Vert_{L_2(\nu)}=(\int f^2 d\nu)^{1/2}, where ν\nu is a probability measure on pairs of a queried rank and its label (written QQ in the original submission). Lemma 3 and these definitions are in Appendix A.1.1, and Section 3.3 describes the content of the lemma.

Q4. Thank you for the suggestion. The proof of Theorem 2 now follows its statement in Section 3.2. The main text states where the other results are proved. Theorem 4 is proved in Appendix A.2, Theorem 5 in Appendix A.3, Theorem 6 in Appendix B.3, and Corollary 7 in Appendix B.2.

Q6. Y‾r=1nr∑i∈Iryir\overline Y_r=\frac1{n_r}\sum_{i\in\mathcal I_r}y_{ir} is the mean of the labeled outcomes at rank rr, where Ir\mathcal I_r is the set of nrn_r pools sampled at that rank (Equation (10)).

We hope that these responses and the revised paper address your concerns. We would be happy to provide further clarification if needed.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the revision

We thank the three reviewers for their thorough reading of the paper and for their detailed and constructive comments. We have carefully revised the paper in light of these comments, and the revised PDF has been uploaded.

The revision mainly improves the presentation, following the reviewers' suggestions. Section 2 presents the problem setup in more detail, with the observation model and the class of audits stated before Definition 1. The introduction describes what a quality curve is used for, each contribution cites the section that establishes it, and Sections 3, 4, and 5 open with what they establish. The proof of Theorem 2 follows its statement, and Section 3.2 relates fixed label budgets to adaptive stopping. Lemma 3 is stated with its definitions in Appendix A.1.1, and Section 3.3 describes its content. Figure 2 has been redrawn to show a typical audit.

In response to specific questions, we also added four appendices. Appendix J gives an instance-dependent lower bound, Appendix K relates the cost of labels to the cost of generation and scoring, Appendix L reports the small pools at label budgets 2L2L, 4L4L, and 8L8L, and Appendix M measures how accurately audits recover the curve of a judge.

The revised version keeps the main claims, theorems, algorithms, and experimental results of the original submission. Our replies to the individual reviews follow, and the references in them are to the revised PDF.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.