acceptodds
Under review as a conference paper at ICLR 2027

Information-Theoretic Query Complexity for LLM Ensemble Selection

Abstract

Selecting an LLM ensemble is fundamentally about complementarity: a model is valuable when it succeeds where others fail. We study how many evaluations are needed to identify the best fixed-size ensemble and show that comparison difficulty is determined entirely by disagreement. Tasks that both ensembles solve or both miss are uninformative; only outcomes on which exactly one succeeds matter. For binary feedback indicating whether each model succeeds, this yields the exact information rate governing reliable comparison and, when all models are evaluated on the same sampled tasks, the exact asymptotic number of sampled tasks required to identify the best ensemble. The same principle extends to model-ranking feedback. Building on this, we develop a greedy procedure that is asymptotically optimal in the number of accepted tasks for identifying the model that best solves tasks missed by the current ensemble. Yet, this greedy decision can require arbitrarily more sampled tasks under full-vector feedback than identifying the best ensemble directly, even when greedy ultimately selects it. Direct identification faces a separate computational limitation: even when the required number of sampled tasks is polynomially bounded, computing the exact best ensemble in time polynomial in that bound and the number of models on every instance would imply . Experiments on published LLM evaluations and a fresh multilingual benchmark are consistent with these predictions. Even with the same overall success gap, ensembles can require substantially different numbers of sampled tasks to distinguish depending on how their successes overlap. Exploiting this complementarity can outperform selection by individual accuracy. Compared with the closest existing method, ours requires less evidence to confirm its choices while achieving similar average ensemble quality. Finally, realistic benchmarks can enable improved ensemble selection while containing too few tasks to confirm the choices with high confidence.

Primary area:
learning theory
Keywords:
Large language models, Ensemble learning, Information theory, Query complexity, Sequential testing

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_ae3KOpenReview ↗
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
  1. The paper characterizes the difficulty of comparing two ensembles.
  2. It shows that the greedy algorithm can require more samples than directly identifying the optimal ensemble.
Critical weaknesses
  1. 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.
  2. 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?

  1. 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
AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

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.

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

This paper studies fixed-size LLM ensemble selection under a best-member coverage objective, where an ensemble succeeds whenever at least one selected model succeeds. Its main theoretical contribution is a closed-form KL characterization of comparison difficulty: under unrestricted binary success-vector distributions, the relevant information depends on the probabilities of the two exclusive outcomes, rather than on the coverage gap alone. Under full-vector feedback, this characterization yields an asymptotically optimal stopping rule for identifying the globally optimal ensemble. The paper also develops an asymptotically optimal greedy rescue selector in accepted-task units, proves that identifying a greedy intermediate choice can be arbitrarily harder than identifying the optimal ensemble directly, and establishes computational hardness of exact identification even on statistically well-separated instances. Experiments using published outcome matrices and a fresh multilingual evaluation examine disagreement-dependent sample costs, budgeted selection quality, and confidence-boundary reachability. The proposed method achieves similar selection quality to AFG, while requiring less evidence on the controlled comparisons.

Critical strengths
  1. An explicit and interpretable characterization of identification difficulty. Theorems 3.2 and 3.3 provide a concrete information quantity for the non-additive coverage objective. The closed-form projection makes clear why comparisons with the same coverage gap can have different sample requirements, and connects this insight to a matching asymptotic identification procedure. This is more informative than a gap-only sample-complexity bound and is the strongest contribution supporting acceptance.

  2. A useful separation between local statistical optimality, global identification, and computation. The three-model construction in Theorem 5.1 shows that even an asymptotically optimal greedy decision rule can spend arbitrarily more samples resolving an intermediate choice than direct ensemble identification requires, despite population greedy returning the optimum. Together with Theorem 5.2, this distinguishes two genuinely different obstacles: unnecessary statistical precision in intermediate decisions and computational difficulty of exact global optimization. This substantially strengthens the paper beyond simply proposing another greedy selection method.

Critical weaknesses

Limited evidence that the proposed confidence criterion delivers practical benefits on representative finite benchmarks.

The incremental practical value of the exclusive-KL criterion over AFG is not yet convincingly established. On fresh XQuAD, neither method certifies any greedy step before exhausting the available budget or task block, and their selected committees are almost identical. Consequently, the observed coverage improvement mainly supports the missed-task greedy mechanism shared by both methods, rather than the proposed confidence criterion. The paper also reports substantial finite-confidence overhead: in Appendix F.3, the global identification rule’s median stopping time at 𝛿 = 0.1 is 42.4 times the information-theoretic lower bound. This does not contradict asymptotic optimality, but limits its demonstrated practical relevance.

Questions for authors
  1. Finite-benchmark correctness. Can you state and prove the confidence guarantee for the actual without-replacement, block-partitioned implementation, explicitly accounting for the adaptively selected current ensemble and failure filtering? Please identify whether the target is the underlying task distribution, the complete finite training population, or a block-specific population.

  2. Representativeness of the confidence-efficiency comparison. Can you report the matched comparison with AFG on all 124 greedy decisions, including censored runs, rather than only the reference-reachable subset? At minimum, paired certification outcomes and actual evaluation expenditure would help establish how broadly the reported advantage applies.

3 comments
AuthorsOpenReview ↗

Response (1/2)

Thank you for the question about the finite-benchmark confidence guarantee. Appendix I establishes that our existing stopping rule controls the probability of an incorrect confidence decision for the tasks missed by the current ensemble in the current task group, even when tasks are sampled without replacement. This holds when the group's order is randomized independently of the ensemble's earlier selection. A stronger guarantee for the entire finite training set requires an additional adjustment, and a guarantee for future tasks needs further sampling assumptions. These are three different targets, which we now distinguish explicitly.

Q1: What is guaranteed on the current tasks? In our experiment, each greedy step receives a separate group of training tasks. To understand the guarantee, first fix the current ensemble and the tasks in its group. Once that group is shuffled independently of how the ensemble was selected, keeping only the tasks the ensemble fails to solve leaves a uniformly random ordering of the missed tasks. These observations are not independent, since each task appears only once. Nevertheless, Appendix I proves that the probability of incorrectly certifying the best next model for those missed tasks is at most the error allowance assigned to that step. The bound covers all candidate comparisons and possible stopping times. This remains true even though tasks are not replaced after being used and the stopping time depends on the observed outcomes.

Q1: Why earlier adaptive choices do not invalidate it. The experiment first shuffles the training tasks and assigns separate groups to successive greedy steps. At a later step, the current ensemble depends on observations from earlier groups. Conditional on that history and on which tasks are in the current group, the order inside the current group remains random, provided this order was not used to select the ensemble and was randomized independently of the earlier selection history. Filtering the new group to tasks missed by the selected ensemble leaves those missed tasks in a uniformly random order. The same confidence argument therefore applies to that group's missed tasks. The error allowance is divided across the greedy steps. A certificate concerns the best rescuer for the current group's missed tasks, not automatically the entire training set.

Q1: Which population does a certificate concern? The distinction is essential. For the actual threshold, a certificate at a later greedy step identifies the best rescuer among the tasks missed by the current ensemble in that step's group. It does not automatically establish the same ordering on the entire training benchmark. Appendix I proves a separate full-training-set statement using a more conservative threshold that accounts for the possible ensembles selected adaptively. We do not claim that the original unadjusted threshold has this stronger later-step guarantee. A guarantee for future tasks from an underlying distribution needs further assumptions about how the benchmark was sampled; multilingual questions sharing passages cannot automatically be treated as independent observations.

Q1: What happens when the budget runs out? Only a run that crosses the confidence threshold is certified. If the group contains no missed tasks, or the available tasks or evaluation budget are exhausted first, the procedure may return its empirically best candidate, but that return is not a confidence certificate. Appendix I states the guarantees and their assumptions, including ties and stopping at data-dependent times. We added a short interpretation in Section 4 so readers do not have to study the proof to understand the scope of the result.

AuthorsOpenReview ↗

Response (2/2)

Thank you for asking us to test the confidence rule on all 124 decisions, including runs that exhaust their tasks. The expanded comparison supports a practical advantage for paired-KL: it certifies more greedy decisions within the same finite task supply, and it uses fewer evaluations when both methods certify the same candidate. We have made the original matched comparison the main confidence-efficiency result in Figure 1 and Appendix J rather than relying on the earlier selected subset.

Weakness/Q2: Complete matched comparison. Comparing paired-KL with AFG, we ran 24 matched task orders for each of 124 offline decision settings, including cases where neither method reaches a confidence decision. At a 95% confidence target, paired-KL certifies 33.3% of the 2,976 runs and AFG 26.6%. These overall rates overlap: both certify in 26.6% of runs, only paired-KL in 6.7%, only AFG in none, and neither in 66.7%. The difference in certification frequency is 6.7 percentage points (95% decision-level bootstrap interval [2.6, 11.5]). This is the representative result across the collection, rather than a result conditioned on our own test having previously succeeded.

What the evaluation costs show. Among the 792 jointly certified runs, drawn from 33 decision settings, compared with paired-KL, AFG requires approximately 47% more accepted tasks and 38% more total model evaluations. Across all runs, including exhausted ones, mean observed model-evaluation expenditure is 25,190 for paired-KL and 27,867 for AFG. We do not impute stopping times for runs that exhausted their tasks. At 10,000 model evaluations, paired-KL has certified 14.6% of runs and AFG 2.3%. The original 20-setting subset gave 100% versus 75% certification in a matched rerun, so it overstated how often either rule can certify across all 124 settings. The full collection is now primary.

Where the gain comes from. AFG uses separate confidence bounds on each candidate's success rate among missed tasks. Paired-KL compares candidates on the same tasks, using the disagreements that actually determine their ordering. It can therefore reach a decision before separate bounds become narrow enough, especially when informative disagreements are available but the total evaluation budget is tight. On the GSM8K offline settings, paired-KL certifies 16.8% of runs and AFG none. Both select the same candidate in every matched run, so the gain is in certification cost rather than average ensemble coverage. The fresh XQuAD experiment remains a difficult case: neither method certifies a greedy step there. We now state that explicitly.

Finite-confidence overhead. The 42.4-fold factor in Appendix F.3 concerns the global identification rule at error level 0.1, not the greedy test. It compares a finite-sample stopping time with a first-order asymptotic information scale; the asymptotic theorem does not promise a small constant at that confidence level. Appendix J examines the extra terms in the finite-time threshold. We also analyze a separate test that counts only tasks on which candidates disagree. It raises the certification rate on the finite greedy settings from 33.3% to 37.4% and reduces the median normalized global stopping constant from 41.3 to 11.4 in controlled simulations. This is a separate refinement, not the original Algorithm 1, and it does not eliminate the difficult XQuAD cases.

Figure 1 and Appendix J now give paired outcomes, budget curves, accepted-task and total-evaluation costs, censoring and the finite-confidence analysis.

I believe the authors' response has addressed my concerns. I will maintain my original score. Good luck.

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

The paper proposes an information-theoretic framework for LLM ensemble selection. It exploits "exclusive outcomes" to derive exact information rates and proposes a greedy algorithm with a paired KL stopping rule.

Critical strengths

The insight that agreement outcomes carry no comparison information is theoretically sound.

Critical weaknesses
  1. The 76-page length is disproportionate to the core contribution. The main text lacks intuitive figures and key results (pushing most experimental details to the appendix), while the appendix is heavily bloated with excessive over-explanations and defensive justifications that bury the core narrative.

  2. The main incremental improvement in the core algorithm seems to be applying paired KL evidence to the failure-condition sampling framework of AFG (Neoh et al., 2026). The authors should clearly distinguish the non-trivial theoretical advances from a specialization of established fixed-confidence identification tools to paired feedback. In particular, which steps require substantive new arguments, and what new understanding or actionable guidance does the resulting theory provide for LLM ensemble selection beyond improving the stopping rule within the existing AFG framework?

  3. Theorem 5.1 (and the abstract) acknowledges that intermediate greedy certification can be arbitrarily inefficient compared to global identification. However, Algorithm 1 still relies on this step-wise greedy certification. While not a logical contradiction, the algorithm fails to address the practical obstacles revealed by the theoretical findings. This significantly weakens its practical utility.

References:

Neoh et al. (2026). Efficient Ensemble Selection from Binary and Pairwise Feedback.

Garivier & Kaufmann (2016). Optimal Best Arm Identification with Fixed Confidence.

Kaufmann et al. (2016). On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models.

Questions for authors

See Weaknesses

7 comments
AuthorsOpenReview ↗

Response (1/3)

Thank you for asking us to clarify what is new beyond AFG and what the theory tells us about ensemble selection. The central improvement to greedy selection is substantive: paired-KL uses the candidates' outcomes on the same missed tasks to certify the next model with less evidence than AFG's separate rescue-rate bounds. The full comparison with AFG supports its practical value: our rule certifies more decisions within finite task budgets and requires fewer evaluations when both methods certify the same choice (Figure 1; Appendix J). The paper also establishes broader results about identifying complete ensembles.

W2: What is new in the greedy decision? Both procedures focus on tasks the current ensemble misses. AFG estimates, separately for each candidate, the probability of solving one of these tasks; this is the candidate's rescue rate. Our test uses the paired outcomes of two candidates on the same task. If both succeed or both fail, that task cannot distinguish them. The useful evidence comes from the tasks on which exactly one succeeds, including how frequently these disagreements occur and which candidate wins them. A sequential Kullback–Leibler (KL) test measures that evidence and eliminates a candidate once the evidence for its inferiority is sufficient. This is not simply a different confidence level: it changes which information is used to make the decision. Theorem 4.1 proves that paired-KL is asymptotically optimal in the number of accepted tasks needed for this individual greedy choice. In the full 124-setting comparison, paired-KL certifies 33.3% of runs versus AFG's 26.6%; when both certify, AFG requires about 38% more model evaluations.

W2: Which theoretical advances require new arguments? Existing fixed-confidence theory provides general lower-bound tools, but does not solve the coverage problem, in which an ensemble succeeds whenever any of its members succeeds. Theorem 3.2 identifies the closest alternative distribution that would reverse the ranking of two ensembles. The proof shows that, despite the many possible joint model outcomes, comparison difficulty depends only on whether both ensembles succeed, both fail, or just one succeeds. It derives an exact information rate from the two exclusive-success outcomes. Consequently, two ensemble pairs with the same coverage gap can require very different numbers of evaluations; an ordinary gap-only bound misses this difference.

Theorem 3.3 then uses this coverage-specific information to determine the asymptotically optimal sample cost of identifying the best complete ensemble when every model's outcome is observed on each task. Establishing the matching stopping rule requires handling all competing ensembles and the possibility of tied alternatives. Theorem 5.1 constructs a case where certifying the first greedy choice is arbitrarily more expensive than identifying the best final ensemble. Theorem 5.2 proves a different limitation: exact global identification can remain computationally hard even when the statistical information needed is not large. These are distinct mathematical statements, not special cases of a generic best-arm formula.

W2: What guidance does this provide? The practical lesson is not merely to replace one confidence threshold. First, look at overlap and disagreement, not just the gap in ensemble coverage, when estimating evaluation cost. Second, do not assume that certifying each greedy addition is the most economical way to identify a final ensemble. Third, although direct global identification may save statistical evidence, exact optimization can be computationally prohibitive. These distinctions explain why our paper separately reports selection quality, confidence certification, accepted tasks, and total model evaluations. Appendix I additionally establishes the finite-benchmark scope of the greedy certificate.

AuthorsOpenReview ↗

Response (2/3)

Thank you for raising the apparent tension between our optimal greedy test and Theorem 5.1. The two results address different questions: our test is asymptotically optimal for deciding the next greedy addition, while Theorem 5.1 shows that insisting on such intermediate decisions can itself be unnecessary for identifying the best final ensemble. We have clarified this distinction in Section 5.

W3: What Theorem 4.1 guarantees. At a greedy step, the current ensemble is fixed and the task is to identify the remaining model most likely to solve a task that the ensemble misses. Theorem 4.1 proves that paired-KL attains the best possible leading-order number of such missed tasks as the required error probability becomes small. In that precise sense, the statistical test is asymptotically optimal. This is a meaningful improvement over separate rescue-rate confidence bounds; it does not claim that a sequence of greedy decisions is globally sample-optimal or that total model-evaluation cost is minimized in every instance.

W3: Why Theorem 5.1 does not contradict the algorithm. The theorem constructs a problem in which two candidates are almost tied for the first greedy addition, so certifying their ordering requires many observations. Yet the identity of the best pair of models is comparatively easy to establish. Even an optimal test for the first greedy choice must spend effort answering a question that direct identification can avoid. This limitation applies to AFG and any method that demands a confidence certificate at every greedy step; it is not caused by an inefficient paired-KL test.

W3: Why retain greedy selection? Greedy selection offers a computationally efficient approximation for the coverage objective. By contrast, Theorem 5.2 shows that exact global identification faces a separate computational obstacle, even in cases with favorable statistical information. Thus local statistical efficiency, global statistical efficiency, and computational tractability are three different properties. Our method improves the first without claiming to solve the other two. In budgeted experiments, an algorithm can still return an empirically strong ensemble when there are too few missed tasks to certify every addition; we now distinguish such an empirical choice from a certified decision. The revised Section 5 explains this immediately after the two limitation results.

AuthorsOpenReview ↗

Response (3/3)

Thank you for the detailed presentation feedback. We have made the main paper easier to follow without asking readers to reconstruct the results from the appendices. The introduction now explains the paired test in ordinary language, Section 3 gives a concrete example, Section 4 explains why the test uses disagreement information, and Section 6 brings the original matched AFG comparison into the main paper.

W1: Clearer main-text argument. We now explain the difference between separate rescue-rate estimates and a comparison on the same tasks before introducing the technical results. Section 3 illustrates why two pairs of ensembles can have the same coverage gap but different comparison costs. Section 4 explains the paired test in words alongside its formal guarantee. Section 5 follows the greedy/global separation and computational-hardness theorems with plain-language explanations of what each result establishes and what it does not. The theorem statements and assumptions remain available for readers who want the full mathematical details.

W1: Main empirical evidence. Figure 1 compares paired-KL with AFG on all 124 offline decision settings, including runs that exhaust their tasks. It shows both the matched certification outcomes and the proportion of runs that reach a confidence decision within a model-evaluation budget. The main conclusion is visible without consulting Appendix J: our test can confirm the same candidate with fewer evaluations, particularly when the budget is too small for AFG's separate bounds to settle the comparison. Appendix J gives the full costs, the original 20-setting analysis, positive-tolerance results and finite-confidence overhead.

W1: Navigating the appendices. We have replaced the prose appendix guide with a compact, linked "Appendix contents" table at the start of the appendix. It lists Appendices A–J and their subjects, so readers can find related work, proofs, experimental methods, additional results, finite-benchmark guarantees and the AFG comparison directly. The additional proof and experimental details are kept in the appendices rather than crowding the main argument. We do not claim to have removed large amounts of text or reordered every theorem: the changes are targeted improvements to explanation, placement of key evidence and navigation.

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

The paper studies how many evaluations are needed to identify the best fixed-size LLM ensemble, where an ensemble succeeds on a task if any member does. It shows that only tasks on which exactly one of two ensembles succeeds help to tell them apart. From this it derives the number of sampled tasks needed to identify the best ensemble, and an asymptotically optimal greedy procedure that adds, one at a time, the model that best solves the tasks the current ensemble misses.

The paper also shows that the greedy procedure can need arbitrarily more samples than direct identification, and that exact direct identification is computationally hard. Experiments on published evaluation matrices and a new multilingual benchmark are consistent with the theory. Selecting models on the tasks the current ensemble misses can outperform selection by individual accuracy. The method matches the closest prior method (AFG) in ensemble quality while needing less evidence to confirm its choices. Realistic benchmarks often contain too few tasks to confirm such choices with high confidence.

Critical strengths

[C1] A clear question with an intuitive answer. The paper asks how many evaluations are needed to identify the best ensemble. Its answer is that only tasks on which exactly one of two ensembles succeeds carry information, so ensembles with the same overall gap can need very different numbers of tasks to tell apart. The paper gives matching upper and lower bounds for this, together with two limitation results: greedy selection can need arbitrarily more samples than direct identification, and exact direct identification is computationally hard.

Critical weaknesses

[W1] The practical benefit of the proposed procedure is not clearly established. According to Appendix E.6, Algorithm 1 differs from the closest prior method, AFG, only in its confidence criterion. In practice this criterion is rarely reached: no greedy step reaches a fixed-confidence decision on XQuAD, MMLU-PromptEval or GSM8K. The two methods also select the same committee in 99.9% of XQuAD runs (Appendices G.1 and G.4). The claim that the method needs less evidence than AFG therefore rests on the controlled comparison in Appendix F.5. That comparison uses 20 steps drawn from the 41 steps (out of 124) on which Algorithm 1 itself reaches a decision at δ = 0.01 (Appendix F.6), and AFG is run in the η → 0 limit of its elimination rule (Appendix E.6). Because the steps are selected using Algorithm 1's own results, it is not clear that this comparison is neutral between the two methods, although the paper describes the restriction as conservative.

Questions for authors

[Q1] Could you run the comparison of Appendix F.5 on all 124 offline greedy steps, or on steps that were not selected using Algorithm 1's own results? Please also report AFG with η > 0. Do the differences in censoring and in accepted tasks remain?

2 comments
AuthorsOpenReview ↗

Response (1/2)

Thank you for your comments and for asking us to extend the comparison with AFG beyond the original 20 decisions. We now evaluate all 124 offline decision settings and include runs that do not reach a confidence decision (Figure 1; Appendix J). Paired-KL confirms more greedy choices within finite budgets and requires fewer evaluations when both methods confirm the same choice. Its advantage is clearest when there is enough evidence to distinguish promising candidates, but not enough for AFG's separate rescue-rate bounds to settle the comparison.

W1/Q1: Why paired-KL needs less evidence. Both methods evaluate candidates on tasks that the current ensemble fails to solve. AFG estimates each candidate's rescue rate, the fraction of these missed tasks it solves, and places a separate confidence bound around that estimate. Our paired-KL test instead compares candidates using their outcomes on the same tasks. Shared successes and shared failures do not favor either candidate. What matters is how often exactly one candidate succeeds and which candidate wins those disagreements. When two candidates usually agree, paired-KL can establish their ordering before separate bounds become sufficiently narrow. This is a change in the evidence used for the decision, not just a change in the confidence level. Theorem 4.1 proves asymptotic optimality in accepted-task cost for this individual greedy decision.

W1/Q1: All 124 decisions, including censoring. We used the same 24 matched random task orders per setting as in the original experiment, giving 2,976 paired runs. All runs, including those that exhausted the available tasks, are counted. At a 95% confidence target, paired-KL certifies 990 runs (33.3%) and AFG certifies 792 (26.6%). These totals overlap: both methods certify the same 792 runs (26.6%); paired-KL alone certifies 198 (6.7%); AFG alone certifies none; and neither certifies the remaining 1,986 (66.7%). Thus paired-KL certifies 6.7 percentage points more runs (95% bootstrap interval over decision settings [2.6, 11.5]). This is the complete-collection result, not an estimate conditioned on our test having succeeded in advance.

W1/Q1: Accepted tasks and model evaluations. Among the 792 jointly certified runs (from 33 decision settings), compared with paired-KL, AFG requires approximately 47% more accepted tasks and 38% more total model evaluations. Accepted tasks are those the current ensemble misses; total evaluations also include the model calls needed to determine whether a task is missed. These percentages summarize matched, decision-level cost ratios on jointly certified runs, not the unknown stopping times of exhausted runs. Across all runs, the mean observed expenditure is 25,190 model evaluations for paired-KL and 27,867 for AFG. At a budget of 10,000 model evaluations, paired-KL certifies 14.6% of runs versus 2.3% for AFG. This is the practical advantage most directly visible under tight budgets.

W1/Q1: The earlier 20-decision experiment. Those decisions were selected from a set on which paired-KL had already certified in a preliminary run, making them unsuitable for estimating the overall frequency of certification. In a matched rerun, paired-KL certifies 100% and AFG 75% on those 20 settings; across all 124, the corresponding rates are 33.3% and 26.6%. The subset magnified the frequency difference, but the evaluation-cost advantage remains on the full collection: the jointly certified AFG/paired-KL evaluation-cost ratio is about 1.35 on the 20 settings and 1.38 across all 124.

W1: Practical meaning. The methods choose the same candidate in every matched run. The improvement is therefore not higher average ensemble coverage than AFG; it is reaching a defensible decision sooner. This matters, for example, when selecting models for a question-answering system where each extra evaluation requires a paid or time-consuming model call. Figure 1 shows the budget dependence; Appendix J reports the complete matched outcomes and costs.

AuthorsOpenReview ↗

Response (2/2)

Thank you also for asking about AFG with a positive approximation tolerance. The advantage of paired evidence persists in the tested approximate-selection setting. AFG does not reach more confidence decisions when its tolerance increases over the tested range, whereas our separately analyzed tolerance-aware paired-KL extension reaches more decisions with lower observed evaluation cost (Appendix J).

Q1: What positive tolerance means. A tolerance of 0.02 permits a model whose probability of solving a missed task is up to two percentage points below that of the best candidate. This is a different goal from proving which candidate is exactly best. We therefore compare AFG's tolerance-based procedure with our tolerance-aware paired-KL extension, analyzed for the same approximate-selection target. Both receive the same task orders and check after every accepted task. The exact-identification results in Figure 1 remain separate.

Certification and censoring. With tolerance 0.02, our extension reaches a confidence decision in 42.0% of runs, versus 26.6% for AFG; thus 58.0% and 73.4%, respectively, exhaust the available tasks without a decision. At tolerance 0.05, our extension certifies 55.3% and AFG 24.2%, with corresponding noncertification rates of 44.7% and 75.8%. At tolerances 0.005 and 0.01, AFG still certifies 26.6% of runs. At positive tolerance, AFG stops in these runs only after elimination leaves one candidate. On the simultaneous-confidence event, this certifies the exact best candidate: the elimination rule cannot remove a maximizer. Its alternative approximate stopping condition cannot be reached with the available tasks, so the table counts these AFG stops as exact certificates.

Accepted tasks and model evaluations. The advantage remains in evaluation expenditure, not only in the certification rate. At tolerance 0.02, our extension uses a mean of 1,579 accepted tasks and 19,914 model evaluations, compared with AFG's 2,398 accepted tasks and 29,022 model evaluations. At tolerance 0.05, the corresponding means are 1,079 and 17,314 for our extension, versus 2,840 and 33,632 for AFG. These are observed averages over all runs, including exhausted runs, rather than inferred uncensored stopping times.

Why AFG does not benefit from tolerance in these runs. Its elimination condition requires evidence that a candidate is worse than the leader by more than the allowed tolerance. As the tolerance grows, elimination becomes harder. Its alternative stopping condition requires the confidence radius to fall below one-quarter of the tolerance. At tolerance 0.05, this would require roughly 95,000 accepted tasks under the tested settings, while the largest failure population contains only 27,248. That branch cannot stop within these benchmarks. Our extension instead uses paired evidence to determine whether the remaining candidates are close enough to the leader. This explains the observed result for these procedures; it is not a claim that positive tolerance is unhelpful for all approximate-selection methods.

Our original exact-identification Algorithm 1 should not be credited with the extension's positive-tolerance results. Appendix I states the extension's guarantee, and Appendix J gives the full sensitivity analysis.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.