- 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 . 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 “? 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 and for the different settings? What is the effect of on these settings? In D.3, the number of budgets differs between the different settings of . Why were the choices not equivalent overall, like $L, 2L, 4L, 8L, … $?
4 comments
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 of the highest:
Here is the utility of budget , is the cost of using candidates in units of quality, and maximizes the estimated utility . To derive it, let maximize the utility. If for every , then
The outer inequalities use the error bound at and at , and the middle one holds because 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
Grouping the sum by rank, with the number of queries at rank and their mean outcome, gives
Under fixed quotas, , , and , so the factor equals one, the predictions cancel against , and what remains is Equation (10),
Envelope enters (10) through the quotas , which follow (Algorithm 2). Section 4.1 gives this derivation after Equation (10).
Q6. The two budgets of Table 2 follow from the pool sizes . Fixed quotas label at least one response at every rank (Algorithm 2), so they require . The budget 512 is therefore unavailable for the large pools (), which Table 2 reports at , the smallest multiple of at which the allocations differ (at they coincide). For the small pools (, 16, or 32), a budget of gives one label to every rank and leaves only 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 , , and (Table 32). On the effect of , Envelope's error decreases approximately as 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 , , and ).
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.
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).
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. τ is the number of labels an audit uses (Section 2.3). An audit may stop based on the labels it has observed, which makes τ a stopping time. Every method in the paper uses a number of labels T fixed in advance, the special case of a constant τ. 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).