Technical Summary: Mixture of Complementary Agents for Robust LLM Ensemble

Problem Statement

The paper addresses the challenge of selecting an optimal subset of proposers (LLM-prompt pairs) for a multi-LLM ensemble framework, specifically within the "Mixture-of-Agents" (MoA) paradigm. In this setup, responses from $N$ proposers are aggregated by a single summarizer LLM to produce a final answer. The core problem is combinatorial: given a large pool of proposers and a fixed ensemble size $k$, which $k$ proposers should be selected to maximize the summarizer's accuracy on downstream tasks?

The authors argue that existing selection heuristics are insufficient because they treat proposers in isolation.

1. Accuracy-seeking methods select the strongest individual models, ignoring how they interact with the summarizer or each other.
2. Diversity-seeking methods prioritize variance in outputs, often at the expense of quality, and fail to account for the summarizer's specific error-correction capabilities.

The paper posits that the critical factor is complementarity: how well a set of proposers works together as a team and specifically how their outputs complement the summarizer's internal reasoning. The authors demonstrate theoretically (via a counterexample involving a Bayesian summarizer) and empirically that a set of proposers with low individual accuracy can outperform a set of high-accuracy proposers if the former provides information that the summarizer can uniquely synthesize.

Methodology

The authors reframe proposer selection as a feature selection problem where the "features" are proposers and the "model" is the summarizer. However, standard wrapper methods are computationally prohibitive because evaluating a candidate set requires expensive calls to the summarizer LLM. To address the trade-off between accuracy and query complexity (summarizer calls), the paper proposes three greedy-style selection algorithms:

1. Model-First Greedy

This is a wrapper-style method that reduces query complexity by operating at the model level rather than the individual proposer level.

• Mechanism: Instead of evaluating every single proposer, the algorithm first scores entire LLMs based on the average marginal gain of their prompt variants on a validation set. It selects the best-performing model and then picks the best prompt instance within that model.
• Complexity: Reduces summarizer calls from $O(N \cdot m)$ to $O(n_{LLM} \cdot m \cdot k)$, where $n_{LLM}$ is the number of models, $m$ is the validation set size, and $k$ is the ensemble size.
• Rationale: Diversity across different models is assumed to be more valuable than diversity across prompts within the same model.

2. Truth-Prediction Greedy

This is a filter-style method that avoids summarizer calls entirely during the selection phase.

• Mechanism: It treats the proposers' predicted labels as features for a lightweight machine learning model (e.g., a classifier) trained to predict the ground truth. The algorithm uses a $k$-greedy strategy (Algorithm 1) to select proposers that maximize the accuracy of this surrogate predictor.
• Key Innovation: Unlike standard greedy selection, $k$-greedy estimates marginal gain by conditioning on a final team size of $k$. This accounts for the non-monotonic nature of LLM summarizers, where a proposer beneficial at small $k$ might be detrimental at the target size $k$.
• Complexity: Zero summarizer calls during selection; relies only on label-level statistics.

3. Oracle-Surrogate Greedy

This method bridges the gap between the previous two by using a simple surrogate to approximate the summarizer's behavior.

• Mechanism: It fits a simple function $\tilde{g}(c)$ that maps the count of correct labels ($c$) among $k$ inputs to the expected summarizer accuracy. This surrogate is trained using a small number of oracle (summarizer) queries. Proposers are then selected to maximize the predicted accuracy of this surrogate.
• Complexity: Requires $(k+1)T_{\tilde{g}}$ summarizer calls for training, significantly fewer than Model-First Greedy.

Key Contributions

1. Identification of Complementarity: The paper establishes complementarity (between proposers and the summarizer) as a decisive, yet overlooked, objective for LLM ensembles. It provides a theoretical counterexample showing that accuracy- and diversity-seeking heuristics can fail to identify the optimal set even under a Bayes-optimal summarizer.
2. Algorithmic Framework: The authors introduce the Complementary-MoA framework and three specific algorithms (Model-First, Truth-Prediction, Oracle-Surrogate) that navigate the accuracy-efficiency trade-off. These methods are designed specifically for the constraints of LLM ensembles, where evaluation costs are high.
3. Empirical Validation: Through extensive experiments on three reasoning benchmarks (AIME, CLadder, MMLU-Pro) with diverse proposer pools and summarizers, the paper demonstrates that complementarity-guided methods are robust across scenarios where standard heuristics fail.

Experimental Results

The authors evaluated their methods against baselines including "Best-model" (accuracy-seeking), "Conditioned-diversity" (diversity-seeking), "LLM-judge," and "Approximate Shapley."

• Performance:
  • Model-First Greedy consistently achieved top-tier performance, ranking in the top two across five of six tested settings (e.g., 0.812 accuracy on CLadder vs. 0.793 for Best-model).
  • Truth-Prediction Greedy and Oracle-Surrogate Greedy provided consistently strong performance across all scenarios, often outperforming diversity-seeking baselines which failed on datasets like MMLU-Pro.
  • Baseline Failures: Accuracy-seeking methods (Top-accuracy, Best-model) performed poorly on AIME, while diversity-seeking methods degraded performance on MMLU-Pro. LLM-judge baselines performed poorly, suggesting that judging proposers in isolation does not capture ensemble value.
• Efficiency:
  • Truth-Prediction Greedy required zero summarizer calls.
  • Oracle-Surrogate Greedy required ~1,200 calls.
  • Model-First Greedy required ~16,000 calls.
  • Approximate Shapley (a strong but expensive baseline) required ~64,000 calls and was outperformed by Model-First Greedy in accuracy.
• Distribution Analysis: The authors observed that accuracy-seeking baselines induced a U-shaped distribution of correct labels (many all-correct or all-wrong sets), while diversity-seeking baselines induced a bell-shaped distribution centered around $k/2$. Complementarity-based methods produced distributions that better aligned with the summarizer's accuracy curve, avoiding the pitfalls of both extremes.

Significance and Claims

The paper claims that the primary contribution is a shift in perspective: optimal ensembles are not merely collections of the strongest or most diverse agents, but teams that are structurally complementary to the summarizer.

• Robustness: The proposed methods are claimed to be robust across different datasets, summarizer models, and proposer pool compositions (including "mixed-crowd" regimes where the strongest model is removed).
• Practicality: By offering a spectrum of algorithms from zero-call (Truth-Prediction) to moderate-call (Model-First), the work provides practitioners with principled tools to select proposers under varying query budgets.
• Limitations: The authors modestly note that their label-level algorithms are currently tailored to multiple-choice tasks and may require adaptation for open-ended generation. They also suggest that hybrid selection strategies (combining complementarity and accuracy) remain an open area for future exploration.

The paper concludes that explicitly optimizing for complementarity is crucial for effective multi-LLM collaboration, as individual quality metrics are unreliable proxies for ensemble performance.