acceptodds
Under review as a conference paper at ICLR 2027

Efficient Ensemble Selection from Binary and Pairwise Feedback

Abstract

To choose a small ensemble of models, prompts, or solvers, we must learn not only how well each candidate performs but also which tasks it solves that the others miss, and this information is costly to obtain. We ask how much feedback such a choice requires. Tasks are drawn from an unknown distribution, each query reveals either one candidate's correctness on one task or one pairwise comparison, and a committee of candidates is judged by its best member on each task. For binary feedback, we give a conditional greedy algorithm that evaluates possible additions only on tasks that the current committee misses. It attains coverage at least with high probability, and its query bound includes the cost of finding the missed tasks. For a fixed gap in success rate between two possible additions to a fixed committee, theoretical bounds show that agreement on missed tasks reduces the number of queries needed. For pairwise feedback, majority cycles can make every committee lose to another of the same size on nearly all tasks. We therefore ask a committee to beat every fixed omitted candidate on a large fraction of tasks. With complete rankings, this objective admits a polynomial-time approximation scheme (PTAS) but, under randomized Gap-ETH, no efficient one (EPTAS). Allowing for lotteries over committees changes the picture: by expressing weighted comparisons with candidates as coverage and reweighting these candidates with multiplicative weights, we approximate the best lottery over size- committees to within a factor , up to additive error , using polynomially many comparisons. Experiments on controlled synthetic populations illustrate the savings from agreement, the limits of conditional sampling, and the gain from randomization.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
ensemble selection, query complexity, multiwinner voting

Reviews

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

This paper studies how to select a small ensemble of complementary candidates using limited binary correctness or pairwise preference queries on tasks drawn from an unknown distribution. It leverages binary feedback and conditional greedy to evaluate potential additions on tasks that are missed by the current ensemble. With pairwise feedback, the proposed method optimizes performance against the worst individual rival. It conducted experiments on controlled synthetic populations to demonstrate the effectiveness of the proposed method.

Critical strengths

Strengths

  • Well-motivated problem. The paper studies candidate complementarity under limited evaluation budgets.
  • Careful query accounting. The analysis counts the cost of finding tasks missed by the committee.
  • Broad theoretical analysis. The results cover approximation guarantees, computational hardness, and statistical lower bounds.
  • Transparent experiments. The paper reports unfavorable results and clearly states the experiments’ limitations.
Critical weaknesses

Weaknesses

  • The distinction from prior methods could be made clearer. Sections 1.1 and 1.2 summarize the contributions and related work, but it remains difficult to assess how the proposed methods advance beyond noisy submodular maximization and action-elimination approaches. Please identify the specific technical challenges that these methods do not directly address, and explain which components of the proposed algorithms or analyses address each challenge. A more explicit comparison of feedback assumptions, query accounting, sample reuse, and guarantees would help clarify the novelty.

  • The agreement-based query savings remain local. The disagreement test is analyzed for comparing two candidate additions, whereas conditional greedy (CG) selects among multiple candidates using a separate elimination procedure. The paper does not show whether incorporating the disagreement test into CG could reduce the query cost of full ensemble selection. A discussion of the technical challenges would clarify the scope of this result; if feasible, an experiment comparing such an extension with CG and the screened baselines would further strengthen the paper.

  • The evidence for practical relevance is limited. The paper acknowledges that its experiments use synthetic populations and that deployment considerations remain open. A small evaluation on real model outcomes would help assess whether the observed benefits of conditional sampling arise in practice. The paper would also benefit from discussing how its assumptions of strict rankings and uniform query costs affect settings with noisy or tied judgments, or with unequal evaluation costs. Finally, since answer selection is outside the paper’s scope and the lottery guarantee averages over committee draws, it would help to specify which deployment settings the guarantee is intended to support.

Questions for authors
  • What technical obstacles/differences distinguish this approach from the closest noisy submodular maximization and robust optimization methods?

  • What prevents the disagreement test from being used in complete ensemble selection?

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

The paper examines how to efficiently select candidate models for an ensemble. Two setups are studied: binary feedback and pairwise feedback, and a conditional greedy algorithm is proposed for each. Synthetic experiments are conducted to partly justify the effectiveness of the proposed algorithms.

Critical strengths
  • The paper is generally easy to follow.
  • The motivation is clear, and the setup is reasonable. Overall, I find the studied problem interesting.
Critical weaknesses
  • Section 3.2 looks interesting to me. However, they are not really used in the proposed algorithms and are not well connected to the rest of the paper.
  • Along with the previous comment, I find the whole Section 3 not very informative. Essentially, it introduces a simple and naive greedy algorithm, under the intuition that there's no need to evaluate those tasks already covered by the selected committee.
  • The experiments are rather thin and cannot really justify the effectiveness of the proposed algorithms. If I understand correctly, the algorithm in Section 4 is the paper’s main contribution, but it is not tested empirically, even on synthetic data.
Questions for authors
  • How do you use the results of Section 3.2 in the rest of the paper? Or how should people interpret them in general?
  • In line 152, you assumed that each task induces a strict ranking. I think this is not necessarily true in practice, and I wonder how necessary this assumption is for the rest of the paper.
Reviewer_WgAzOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies how to select a K-LLM ensemble from m candidates while minimizing pre-deployment evaluation queries under binary and pairwise feedback. The authors frame this as a distributional multiwinner voting problem where an ensemble's utility on a sampled task is determined by its best member. For binary feedback, they propose a failure-conditioned greedy algorithm that preserves coverage guarantee while saving queries by only testing candidates on tasks missed by the current committee. For pairwise feedback, they show that finding winning committees is non-submodular and overcome this via a submodular weighted coverage relaxation paired with a multiplicative-weights wrapper. Experiments on multilingual QA and LiveBench confirm that their adaptive algorithms outperform naive Top-k baselines and use far fewer queries than random-committee ERM.

Critical strengths
  • Framing pre-deployment LLM ensemble selection as distributional multiwinner voting is a natural fit. The core algorithmic idea of conditioning candidate evaluation on the failure instances of the current committee (Adaptive-Fail-Greedy) is simple, intuitive, and yields clean instance-dependent query savings while preserving the (1−1/e)(1-1/e) guarantee.
  • The paper does a solid job navigating the obstacles in the ordinal model. Showing that θ\theta-winning maximization is non-submodular (and lacks an EPTAS under Gap-ETH) and then bypassing this via a submodular weighted relaxation (Φλ\Phi_\lambda) + MWU minimax wrapper makes the theoretical story complete and non-trivial.
Critical weaknesses
  • There seems to be a disconnection between theoretical query savings and actual experimental query counts. The algorithms are motivated by reducing expensive model calls, but the experiments require Q≈106Q \approx 10^6 queries on training pools that only have 89×1482≈1.3×10589 \times 1482 \approx 1.3 \times 10^5 (binary) and 37×107≈4×10337 \times 107 \approx 4 \times 10^3 (pairwise) unique cells. Because the algorithms re-sample the finite training matrix with replacement via rejection sampling and use conservative Hoeffding bounds, they end up making more oracle calls than simply evaluating the entire training table exhaustively (m⋅ntrainm \cdot n_{\text{train}}). Furthermore, in Table 1, simple heuristics (UniformGreedy, UCB-Greedy) match AFG within ±0.01\pm 0.01 on test coverage.
  • The experimental implementations differ substantially from the algorithms analyzed theoretically. For example, the theoretical guarantees assume (\varepsilon\in(0,1)), whereas the experiments sweep values as large as (\varepsilon=3.0). In the pairwise setting, the theoretical algorithm requires a confidence-dependent number of samples for miss-rate estimation, but the experiments use a fixed budget of 200 samples and impose a cap of 10,000 rounds on the elimination procedure. Moreover, the theoretical analysis assumes strict rankings, while the LiveBench experiments use weak rankings with ties. These deviations may be reasonable for computational efficiency, but it is unclear whether the resulting implementations retain the stated approximation and query-complexity guarantees. The paper would benefit from clarifying which theoretical guarantees apply to the algorithms evaluated experimentally.
Questions for authors

see weaknesses

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.