Efficient Ensemble Selection from Binary and Pairwise Feedback

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 $k$ 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 $(1-1/e){\mathrm{OPT}}_k-\epsilon$ 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-$k$ committees to within a factor $1-1/e$, up to additive error $\epsilon$, using polynomially many comparisons. Experiments on controlled synthetic populations illustrate the savings from agreement, the limits of conditional sampling, and the gain from randomization.