- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This paper studies how to identify the ensemble with the highest success rate. Its main idea is that comparing two ensembles depends on the questions on which their outcomes differ. Based on this observation, the paper characterizes the difficulty of comparing two ensembles and derives the exact asymptotic sample complexity of identifying the globally optimal ensemble. It then proposes a greedy algorithm and shows that greedy selection can require substantially more samples than directly identifying the optimal ensemble.
Critical strengths
- The paper characterizes the difficulty of comparing two ensembles.
- It shows that the greedy algorithm can require more samples than directly identifying the optimal ensemble.
Critical weaknesses
- The algorithmic contribution is relatively incremental. Selecting additional models based on tasks that the current ensemble fails to solve has already been explored in prior work.
- The paper is very long and difficult to read, requiring frequent references to the appendix. The theorem statements also contain a large amount of notation, making them difficult to follow.
Questions for authors
1.The proposed method and AFG achieve nearly identical ensemble quality in the fresh XQuAD experiments. Could the authors clarify when the improved confidence criterion provides a meaningful practical advantage? In particular, would this advantage persist if AFG were allowed a small approximation tolerance, rather than being run in the exact-identification limit?
- I encourage the authors to improve the overall presentation. The main text should explain the core ideas and results clearly, with a coherent narrative that can be followed without frequent references to the appendix.
2 comments
Response (2/2)
Thank you for asking when the improved confidence rule is useful and whether the advantage survives a positive approximation tolerance. The larger AFG comparison and our additional tolerance experiments both support a benefit from paired evidence. Paired-KL is especially useful when there are enough informative disagreements to distinguish candidates but not enough evaluations for AFG's separate confidence bounds to certify the same choice.
Q1: When does paired-KL help in practice? We compared paired-KL with AFG on all 124 offline decision settings, with 24 matched task orders each and all exhausted runs retained. Paired-KL certifies 33.3% of runs and AFG 26.6%. Among runs where both certify, compared with paired-KL, AFG requires about 38% more total model evaluations and 47% more accepted tasks. At a budget of 10,000 model evaluations, paired-KL certifies 14.6% of runs versus 2.3% for AFG. The methods return the same candidate in every matched run, so the benefit is confirming a choice at lower cost, not higher average ensemble coverage. The gain is clearest in resolvable, budget-limited comparisons. For nearly tied candidates, or on the fresh XQuAD benchmark, the finite task supply is still insufficient for either method to certify.
Q1: Does the benefit persist with positive approximation tolerance? Yes, in the tested procedures. A positive tolerance allows the chosen candidate's rescue rate to be slightly below the best, so it changes the correctness target. We compared AFG's tolerance-based rule with our separately analyzed tolerance-aware paired-KL extension, under the same allowed loss. At tolerance 0.02, our extension certifies 42.0% of runs versus AFG's 26.6%; their mean observed model-evaluation costs are 19,914 versus 29,022. At tolerance 0.05, our extension certifies 55.3% versus AFG's 24.2%, at costs of 17,314 versus 33,632. AFG's elimination condition becomes harder to satisfy as tolerance grows, while its alternative tolerance stop needs a confidence radius smaller than the available tasks can provide here. These results concern the approximate-selection extension, not the original exact Algorithm 1. Appendix J reports the other tested tolerances and accepted-task costs.
W2/Q2: A clearer paper. The introduction now explains what paired comparisons measure before using the term paired-KL. Section 3 gives a concrete example showing that equal coverage gaps can lead to different comparison costs. Section 4 explains the intuition alongside the formal greedy guarantee; Section 5 explains why optimal per-step testing does not imply globally efficient identification and why exact global optimization is difficult. Figure 1 gives the main AFG comparison directly in Section 6. A compact linked appendix contents table points to the complete proofs, experimental methods, finite-benchmark guarantee and full comparison. The goal is that the main argument can be followed without repeated trips to the appendix, while the technical details remain available.
Response (1/2)
Thank you for asking us to make the algorithmic and theoretical contributions clearer. The key algorithmic improvement is not a different choice of confidence level: paired-KL uses the joint outcomes of candidates on the same missed tasks to decide which model to add. This makes a difference when candidates often agree, because only the disagreements can establish which one is better. Theorem 4.1 proves asymptotic optimality for this decision, and the complete AFG comparison shows the practical value of that result (Figure 1; Appendix J).
W1: What is new beyond the missed-task greedy strategy? AFG and our method both focus on tasks that the current ensemble cannot solve. AFG places separate confidence bounds around each remaining candidate's rescue rate, the fraction of those tasks it solves. Our paired-KL rule compares candidates on the same tasks. When both solve a task, or both miss it, the task does not favor either candidate. The test measures how often only one succeeds and which candidate wins these disagreements. If two candidates usually agree but one consistently wins their disagreements, this evidence can establish the ordering sooner than separate confidence bounds. Theorem 4.1 shows that our test achieves the optimal leading-order accepted-task cost for identifying the best next model. This is a substantive improvement to the statistical decision inside greedy selection, not a claim to have invented missed-task greedy selection.
W1: The broader theoretical contribution. Theorem 3.2 derives the exact information needed to compare two ensembles under the coverage objective. The proof identifies the closest distribution that would reverse their ordering and shows why the pattern of disagreement, rather than the coverage gap alone, determines difficulty. Theorem 3.3 uses this result to characterize the asymptotically optimal cost of identifying the best full ensemble when all model outcomes are observed on each task. Theorem 5.1 proves that an asymptotically optimal test for each greedy addition can still waste observations on intermediate decisions that are unnecessary for identifying the best final ensemble. Theorem 5.2 establishes a separate computational barrier to exact global identification. These results explain the opportunities and limits of paired evidence rather than simply transferring a generic stopping rule to a new application.
Why this matters. The theory suggests three concrete lessons: evaluate candidates using their overlap and disagreement, not only individual success rates; distinguish the cost of certifying intermediate greedy choices from the cost of identifying the final ensemble; and account separately for statistical evidence and computational optimization. We have made these points clearer in the introduction and Sections 3–5.