PaperlayerView exact revision on arXiv

Source-linked AI summary

Beyond Majority Voting: LLM Aggregation by Leveraging Higher-Order Information

Rui Ai, Yuqi Pan, David Simchi-Levi, Milind Tambe, Haifeng Xu

arXiv:2510.01499v2cs.LGcs.AIcs.GT

TL;DR

Majority voting treats LLM answers equally, while models can differ in accuracy and their answers can be correlated. The paper proposes aggregation methods using first- and second-order information, and reports that its algorithms consistently outperform majority voting and other baselines across evaluations.

  • Problem

    Majority voting treats LLM answers equally and does not account for model heterogeneity or correlations among answers.

    Source: §1 · p. 1

  • Method

    The paper proposes OW using first-order accuracy information and second-order approaches, including ISP and OW-L/OW-I, which approximate accuracies without true labels.

    Source: §1 · p. 2, §3 · p. 3

  • Results

    Across simulations, LLM post-training datasets, and real-world healthcare data, OW and ISP consistently dominate majority voting and other baselines.

    Source: §7 · p. 9

  • Takeaways & Limitations

    The authors state that effective aggregation can improve LLM debate and help characterize the collective power frontier for reasoning and forecasting.

    Source: §1 · p. 1

    In healthcare, the authors say accuracy gains should be accompanied by human-in-the-loop oversight to ensure patient safety.

    Source: Impact Statement · p. 10

Abstract

from arXiv · show

With the rapid progress of multi-agent large language model (LLM) reasoning, how to effectively aggregate answers from multiple LLMs has emerged as a fundamental challenge. Standard majority voting treats all answers equally, failing to consider latent heterogeneity and correlation across models. In this work, we design two new aggregation algorithms called Optimal Weight (OW) and Inverse Surprising Popularity (ISP), leveraging both first-order and second-order information. Our theoretical analysis shows these methods provably mitigate inherent limitations of majority voting under mild assumptions, leading to more reliable collective decisions. We empirically validate our algorithms on synthetic datasets, popular LLM fine-tuning benchmarks such as UltraFeedback and MMLU, and a real-world healthcare setting ARMMAN. Our algorithms consistently outperform standard baselines, establishing a robust, training-free framework for effective multi-agent LLM aggregation.

1. Introduction

The introduction asks whether higher-order information can improve LLM answer aggregation beyond majority voting, which treats answers equally and does not account for model heterogeneity or answer correlations. It presents OW and ISP, motivated by the cost of accuracy labels, and reports consistent empirical gains over majority voting.

1. Introduction

  • Majority voting is widely used but treats LLM answers equally, leaving model heterogeneity and correlations unaccounted for.The introduction frames higher-order information as including expected accuracy and answer correlation.Source: §1 · p. 1
  • The paper distinguishes response aggregation from mixture-of-experts selection, which chooses an expert based on a query rather than aggregating final outputs.The related-work discussion frames this paper as label-free, unsupervised aggregation with a theoretically optimal one-round method.Source: §1 · pp. 1–2
  • The authors connect effective aggregation to improving LLM debate and understanding the collective power frontier for reasoning and forecasting.They also identify prediction markets and prediction-as-a-service as potential downstream applications.Source: §1 · p. 1
  • LLM aggregation raises distinct challenges and opportunities: shuffled answers support a closed-form optimal solution, while accuracy estimation can require costly ground-truth labels.The paper motivates using correlations across models as a lower-cost, label-free source of information.Source: §1 · pp. 1–2
  • OW is Bayesian-optimal when model accuracies are known, while ISP uses second-order information and is designed to outperform majority voting without requiring true answers.Estimating OW's accuracy inputs requires comparing predictions against correct answers across many questions, which is costly.Source: §1 · p. 2
  • OW-L and OW-I are empirically consistent with each other and, together, achieve the best performance; the proposed algorithms consistently outperform majority voting across evaluation settings.Evaluations include simulations, UltraFeedback, MMLU, and the ARMMAN maternal health dataset.Source: §1 · p. 2

2. Model

The model considers aggregating answers from multiple LLM agents on questions whose correct labels are unknown. It uses randomized label shuffling and states assumptions about answer ordering and conditional independence.

2. Model

  • The model treats questions, ground-truth labels, and agent predictions as random variables, while the correct answers across the question set are fixed but unknown.Agents may have heterogeneous accuracies, and the prior-free setting assumes no knowledge of the joint distribution.Source: §2 · pp. 2–3
  • The goal is to design an aggregator that exploits cross-agent information to improve accuracy over majority voting.The setting includes questions without ground truth and predictions over a fixed number of candidate labels.Source: §2 · pp. 2–3
  • Randomly shuffling candidate labels for each question enforces uniformity in the error distribution and, within the setting, loses no information.The authors state that this preprocessing depends on assuming agent outputs are unaffected by option ordering.Source: §2 · p. 3
  • After shuffling, each agent's probability of selecting the correct label remains its accuracy, while its probability of selecting each incorrect label is uniform.The paper presents these as structural consequences of preprocessing, not assumptions about the original distribution.Source: §2 · p. 3
  • Conditional on the ground-truth label, agents’ predictions are assumed independent; the authors extend theoretical results beyond this assumption and test methods where perfect independence may not hold.The paper describes conditional independence as standard in information aggregation literature.Source: §2 · p. 3

3. Leveraging First-order Information

The section introduces Optimal Weight (OW), which uses agents’ first-order accuracy information to weight their votes rather than treating every answer equally. Under Theorem 2.2, OW is Bayesian optimal; the section also identifies when majority voting is optimal and how OW compares with individual agents.

3. Leveraging First-order Information

  • OW weights agents using first-order accuracy information, unlike majority voting, which gives each agent an equal vote.The algorithm randomly shuffles candidate labels before aggregation and maps the result back afterward.Source: §3 · p. 3
  • Under Theorem 2.2, OW is the Bayesian optimal aggregator for any P.The paper defines Bayesian optimality as maximizing the posterior probability of the correct label given the observed answers.Source: §3 · pp. 3–4
  • For K = 2 labels, optimal weights are proportional to the inverse logistic function of each agent’s accuracy.The section connects this weighting scheme to the Bradley–Terry model used in LLM post-training.Source: §3 · p. 4
  • When agents are homogeneous, majority voting is the Bayesian optimal aggregator; it is also optimal when repeatedly sampling from the same agent.These are conditions under which equal weighting is appropriate.Source: §3 · p. 4
  • OW is strictly more accurate than any individual agent except in an extreme case that becomes harder to achieve as N or K increases.The passage characterizes the exception in terms of an exceptionally strong model.Source: §3 · p. 4

4. Leveraging Second-order Information

Because first-order accuracy estimates require ground-truth labels, this section develops aggregation based on second-order information that can be estimated from repeated model queries without labels.

4. Leveraging Second-order Information

  • Second-order information, such as conditional prediction correlations, can be estimated from repeated model queries without ground-truth answers.The section assumes agents perform at least as well as random guessing; inferior agents can be excluded.Source: §4 · p. 4

4.1. Surprisingly Popular Aggregation

  • In finite, heterogeneous settings, majority voting has greater expected advantage than Surprising Popularity (SP), whose bias-correction benefit is less pronounced for LLMs.The authors attribute this to LLMs’ reduced systematic bias relative to human crowds.Source: §4.1 · p. 5

4.2. From Surprisingly Popular to Inverse Surprisingly Popular

  • Inverse Surprising Popularity (ISP) modifies SP by amplifying prediction bias in a controlled way, and its expected advantage is at least MV’s, which is at least SP’s.ISP’s advantage over MV scales as Θ(1/K), while MV’s advantage over SP scales as Θ(1).Source: §4.2 · pp. 5–6

4.3. Practical Estimation of Second-order Information

  • ISP estimates second-order information from finite samples using empirical conditional probabilities, and its empirical advantage over MV is retained with sufficiently large sample size.The stated guarantee applies with probability at least 1 − δ under the paper’s theorem assumptions.Source: §4.3 · p. 6

5. Experiments

The experiments assess OW and ISP through simulations, label-free accuracy estimation, and real-world datasets, comparing aggregation methods with majority voting.

5.1. Evaluation on Simulated Data

  • In simulations across different answer-choice counts, ISP outperforms MV, which outperforms SP; ISP also exceeds the single best agent.Table 2 reports overall accuracy for different K values.Source: §5.1 · pp. 6–7, Table 2 · p. 7

5.2. Adapted Optimal Weight Algorithm Without Ground Truth

  • OW-L estimates accuracies from empirical second-order information, while OW-I uses ISP predictions as pseudo-ground truth; both use OW weights and converge to the same optimal weights theoretically.The two estimators also show similar performance even with small N.Source: §5.2 · p. 7

5.3. Real-world Datasets

  • UltraFeedback tests preference labeling with K = 2, MMLU tests finite-choice answers with K = 4, and ARMMAN tests dropout-risk prediction in maternal health programs.The ARMMAN task concerns pregnant and postpartum women at risk of leaving call-based maternal health information programs.Source: §5.3 · pp. 7–8

5.4. Evaluation Results on Real-World Datasets

  • The method yields absolute accuracy gains over MV of 2.78% on UltraFeedback, 3.36% on MMLU, and 1.16% on ARMMAN, respectively; with four strong models, all three algorithms outperform majority voting.Source: §5.4 · p. 8
  • Across 16 model ensembles, OW-L beats MV in 97.92% of cases, OW-I and ISP each beat MV in 95.83%, and MV is never best.Absolute accuracy improvement ranges from 0.54% to 14.20%.Source: §5.4 · p. 8

6. Robustness and Ablation Studies

The aggregation methods remain effective under positional bias and larger, potentially correlated ensembles. Their gains are especially pronounced on a hard MMLU subset and with weaker models.

6. Robustness and Ablation Studies

  • Table 4 reports the ratio of option A selections by model; stronger models choose A at a frequency close to 50%, while weaker models show positional bias.The reported 50% pattern is consistent with the random-shuffling assumption.Source: Table 4 · p. 9, §6 · p. 9
  • With four weak models, gains over majority voting can exceed 9%, and the methods perform well across strong and weak models despite positional bias.The authors report these results without debiasing.Source: §6 · p. 9
  • On 13,886 MMLU questions with concentrated errors, the method’s gain over MV is over 7% and larger than on the full dataset.The subset contains questions where at least two strong models choose the same incorrect option.Source: §6 · p. 9, Table 5 · p. 9
  • With all eight models, the methods still outperform MV, although some same-family models may violate the theoretical assumptions.The authors describe this as evidence of robustness to larger, more correlated ensembles.Source: §6 · p. 9, Table 6 · p. 9

7. Conclusion and Discussion

The paper concludes that first- and second-order information can improve multi-agent LLM aggregation over majority voting. It identifies finer-grained weighting, open-ended questions, higher-order signals, and post-training integration as future directions.

7. Conclusion and Discussion

  • Across simulations, post-training datasets, and healthcare data, OW and ISP consistently outperform majority voting and other baselines, with theoretical results showing benefits from higher-order information.The paper presents these results as insights into multi-agent reasoning, including LLM debates.Source: §7 · p. 9
  • Future work could study prompt-specific weights, optimal aggregation for open-ended questions, higher-order information, and integration with LLM post-training.Source: §7 · p. 9

Impact Statement

The paper presents a principled framework for aggregating heterogeneous model decisions and discusses potential benefits and risks of its use. It distinguishes its label-free LLM setting from related work and justifies random shuffling for worst-case analysis.

Impact Statement

  • The framework targets collective decisions from heterogeneous models, with potential fairness and robustness benefits for automated consensus systems such as data annotation and prediction markets.The impact statement also reports performance gains on the maternal-health dataset ARMMAN and stresses human oversight for patient safety.Source: Impact Statement · p. 10
  • Improved aggregation could also make misinformation or persuasive-content generation more efficient, motivating responsible use and ethical-output safeguards.Source: Impact Statement · p. 10

A.1. Related Works

  • The paper distinguishes its label-free setting from other multi-agent LLM approaches and extends information aggregation to heterogeneous LLM experts using first- and second-order information.It frames this as one-round aggregation for improving on zero-order majority voting.Source: §A.1 · p. 14

B.1. Justification of Random Shuffling

  • In worst-case analysis, random shuffling entails no loss; its justification assumes each agent has roughly the same accuracy across questions, a symmetry that shuffling enforces.The paper says the question-level symmetry may not hold in reality and is needed only for the shuffling justification.Source: §B.1 · p. 15

C. Extension: Beyond Conditional Independence

The extension models varying question difficulty, which can induce dependence across agents’ outputs in the dataset even when outputs are conditionally independent for each question. Under the extended setting, EOW remains Bayesian optimal and ISP outperforms MV in expectation; the appendices connect OW’s optimality to accuracy-based weights.

C. Extension: Beyond Conditional Independence

  • Varying question difficulty can break dataset-level conditional independence, so the extension assumes conditional independence only for each individual question.The paper identifies shared performance changes on easy versus difficult questions as a source of positive correlation across agents.Source: C. Extension: Beyond Conditional… · pp. 15–16
  • The model represents question difficulty by α and agent strength by β_i; larger values indicate easier questions and stronger agents, respectively.For binary choices, the probability of a correct answer follows a logistic function of αβ_i.Source: C. Extension: Beyond Conditional… · p. 16
  • Without knowing the difficulty distribution, EOW remains Bayesian optimal, while ISP outperforms MV and MV outperforms SP in expectation.Source: C. Extension: Beyond Conditional… · p. 16

D.1. Proof of Theorem 3.1

  • The OW proof maps each agent’s accuracy to an ability parameter and selects the candidate label with the highest posterior probability under the shuffled-label model.Source: §D.1 · p. 17

D.2. Proof of Theorem 3.2

  • For K = 2, OW’s optimal weights are proportional to the logits of agent accuracies.Source: §D.2 · p. 17

D.3. Proof of Theorem 3.3

The proofs establish when majority voting is optimal and describe symmetry, monotonicity, and null-information properties of second-order information. They also frame Bayesian optimality of an individual agent through posterior comparisons with alternative labels.

D.3. Proof of Theorem 3.3

  • When agents have equal accuracy, all optimal weights are equal, making majority voting optimal for homogeneous agents.The result also justifies majority voting when reasoning with a single model.Source: §D.3 · pp. 17–18

D.4. Proof of Theorem 3.4

  • The proof of Theorem 3.4 tests whether an individual agent's output is Bayesian-optimal by comparing its posterior probability with those of alternative labels.The supplied proof passages state the posterior comparison criterion but do not report its outcome.Source: §D.4 · p. 18

E.1. Basic Properties of Second-order Information

  • After random shuffling, second-order information has symmetry, monotonicity, and null-information properties.Symmetry equates conditional agreement probabilities across labels; monotonicity links higher accuracy to a higher conditional match probability, and chance-accuracy agents provide null information.Source: §E.1 · p. 18

E.2. Proof of Example 1

The section illustrates ISP’s advantage over majority voting, how it diminishes as the number of choices grows, and how SP can underperform in this setting. It also describes training-free aggregation steps that run locally on a personal CPU at negligible cost.

E.2. Proof of Example 1

  • In the four-agent example, accuracies are 7/8 for MV, 3/4 for SP, and 1 for ISP.For the tied case, MV breaks the tie uniformly; SP favors the wrong label, while ISP favors the correct label.Source: §E.2 · p. 19
  • With nine agents, MV is wrong only with probability 1/32, SP is wrong with probability 3/16, and ISP predicts correctly with probability 1.The example has four agents of accuracy 1, five of accuracy 0.5, and two candidate labels.Source: §E.2 · p. 19

E.3. Proof of Theorem 4.1

  • For fixed agent accuracies, ISP’s expected advantage over MV scales as Θ(N/K), so its performance gap diminishes as the number of options K increases.The authors attribute this decline to ISP’s single round of uniform reflection, which gives roughly 1/K probability of reaching the correct answer when an original prediction is wrong.Source: §E.3 · p. 20
  • SP’s gap relative to MV is Θ(N) as K increases, and SP can perform worse because it can remain stuck on a wrong option rather than reflect on alternatives.The authors conclude that surprising popularity is unsuitable for LLM aggregation when agents have no incentive to deliberately answer incorrectly.Source: §E.3 · p. 21

E.4. Proof of Theorem 4.2

  • For M i.i.d. questions, the Theorem 4.2 proof uses leave-one-question-out conditional-probability estimates and Hoeffding concentration to bound the estimated ISP advantage over MV.The proof combines this estimation bound with Theorem 4.1 to obtain a lower bound on the expected estimated advantage.Source: §E.4 · pp. 21–22

F.1. Omitted Details in Section 5.1

  • As K increases, the ISP–MV gap gradually decreases, while the MV–SP gap first decreases and then stabilizes.The authors link the initial MV–SP reduction to improving accuracy across all three algorithms; Figure 1 presents the performance-gap trend.Source: Figure 1 · p. 23

F.2. Omitted Details in Section 5.2

  • For Equation (6), the authors mention gradient descent and leave exploring loss functions beyond squared loss for future research.Source: §F.2 · p. 23

F.3. Omitted Details in Section 5.3

  • The omitted setup retains 56,380 UltraFeedback questions, 109,820 MMLU questions answered by all models, and 11,785 ARMMAN cases answered by all models.The ARMMAN setup uses call reception records from the past ten weeks; UltraFeedback responses and MMLU choices are randomly shuffled.Source: §F.3 · pp. 23–24
  • On an Apple M3 Pro, OW-L and OW-I accuracy estimation on UltraFeedback takes 10.3 and 6.1 seconds, respectively, while the second aggregation step takes around 0.1 seconds.The training-free approach avoids the gradient-based training that typically dominates modern LLM pipelines, enabling use by individuals and small organizations with limited compute resources.Source: §F.3 · p. 25

F.4. Omitted Details in Section 5.4

Across ensemble configurations, OW-L, OW-I, and ISP generally outperform majority voting and Surprising Popularity, with OW methods also outperforming Dawid-Skene. The section also reports results under correlated ensembles and gives a Bayesian posterior criterion in the G.1 proof.

F.4. Omitted Details in Section 5.4

  • OW-L, OW-I, and ISP achieve the highest accuracy across ensemble configurations and generally outperform MV, SP, and DS.OW-L and OW-I lead in most cases; ISP occasionally tops the results. Tables 7–9 report overall accuracy for UltraFeedback, MMLU, and ARMMAN.Source: §F.4 · p. 26, Table 7 · p. 26, Table 8 · p. 27
  • The section reports statistical tests as evidence that the proposed algorithm consistently outperforms MV.The accompanying calculation describes a per-question comparison for UltraFeedback and says the MMLU and ARMMAN calculations follow the same process.Source: §F.4 · p. 27
  • Under correlated model ensembles, ISP, OW-L, and OW-I significantly outperform MV across all three datasets, with gains up to 7.7%.The comparison is reported for UltraFeedback, MMLU, and ARMMAN.Source: §F.4 · p. 28, Table 11 · p. 28, Table 12 · p. 28

G.1. Proof of Theorem C.2

  • The Bayesian-optimal aggregator selects the label with the highest posterior probability given the agents' predictions.Figure 2 presents the eight selected models' accuracies across UltraFeedback, MMLU, and ARMMAN.Source: §F.4 · p. 25, Figure 2 · p. 25, §G.1 · p. 28

G.2. Proof of Theorem C.3

For two-label questions of unknown difficulty, the proof establishes that ISP has a larger expected advantage than majority voting. It also shows that majority voting's expected advantage is at least as large as Surprising Popularity's.

G.2. Proof of Theorem C.3

  • With unknown question difficulty, ISP's expected advantage remains greater than MV's across difficulty levels.The proof considers two labels and does not assume the difficulty level for each question is known.Source: §G.2 · pp. 29–30
  • Under the analyzed setting, MV's expected advantage is at least as large as SP's.The comparison follows from the proof's inequality for the two-label case with unknown difficulty.Source: §G.2 · pp. 29–30

Related papers

Loading 2510.01499v2…