Majority voting is the standard for aggregating multi-agent responses into a final decision. However, traditional methods typically require all agents to complete their reasoning before aggregation begins, leading to significant computational overhead, as many responses become redundant once a majority consensus is achieved. In this work, we formulate efficient multi-agent voting as a reliability-aware agent scheduling problem and propose Efficient Majority-then-Stopping (EMS) to improve reasoning efficiency. EMS first estimates a Task-Conditioned Reliability Ordering (TCRO) for each agent by retrieving its historical consensus evidence on semantically similar queries, and then invoking agents in descending reliability order. Next, Adaptive Incremental Voting (AIV) terminates the process once the current leading answer cannot be overturned by any possible votes from the remaining agents, and returns this answer. Finally, Reliability History Updating (RHU) updates only the invoked agents according to their consensus with the final decision. Extensive evaluations across five benchmarks show that EMS preserves the accuracy of Majority Voting while reducing the average number of invoked agents by 35% and token consumption by 44%, respectively. The code is available at https://github.com/fuyu66/EMS.
Figures & tables
Figure 1: Intuitive comparison of different multi-agent voting processes. There exists a significant difference in terms of Number of Invoked Agents among different voting sequences.
Figure 2: Overview of the proposed Efficient Majority-then-Stopping (EMS) framework. For each query, EMS first uses the Task-Conditioned Reliability Ordering (TCRO) to determine a reliability-aware voting order. It then performs incremental voting via Adaptive Incremental Voting (AIV), where agents are invoked sequentially according to the estimated order. Finally, Reliability History Updating (RHU) updates the confidence state of the agents contributing to the majority-voting.
Figure 3: Analysis of the Adaptive Incremental Voting. Each bar represents the proportion of questions that achieve the final results based on the “Agents Invoked”.
Methods
Avg. Acc.
Avg.#Agents
Avg.Tokens
Full MV
87.01
9.00
7,381
Random 5
85.59
5.00
4,065
Fixed Top 5
86.40
5.27
4,374
Random + ES
87.01
6.32
5,121
Fixed + ES
87.01
5.71
4,966
EMS
87.01
5.84
4,123
Table 2: Effect of different ordering and stopping strategies. Random 5 and Random+ES use random agent orders without cold-start information. For the other ordered variants, 5% of the data is used for cold-start, and the reported efficiency metrics include this cold-start cost. ES denotes early stopping.
Metric
Easy (AQuA)
Hard (GPQA)
n
254
198
ES
87.80%
76.77%
TP
81.89%
58.08%
FP
5.91% (15)
18.69% (37)
H-FP
0.39% (1)
3.54% (7)
Shared Err.
5.51% (14)
15.15% (30)
Table 3: Early-stopping error analysis. ES : early-stop rate; TP : correct early stops; FP : incorrect early stops. H-FP : harmful false-positive stops corrected by FullMV. Shared Err. : errors shared by early stopping and FullMV.
N
Acc.
Avg.#Agents
Avg.Tokens
5
67.17
3.98
7,073
7
68.18
5.43
8,725
9
70.20
6.84
9,432
11
71.21
8.17
10,547
13
71.72
9.56
12,250
Table 4: Performance scaling with respect to the maximum agent pool size N on GPQA.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Dataset
Domain
Test Size
Mathematical Reasoning
GSM8K
Grade School Math
1,319
AQuA
Algebra Problems
254
Commonsense & General Knowledge
MMLU
Academic Subjects
1,474
CommonsenseQA
General Sense
1,221
Appendix
Table 5: Overview of Datasets.
Setting
Avg. Acc.
Avg.#Agents
Avg.Tokens
EMS-CS- 5%
87.01
5.84
4,123
EMS-CS- 10%
87.01
6.01
4,455
EMS-Onlie
87.01
5.87
4,283
Appendix
Table 6: Effect of different cold-start ratios.
Method
LLM Latency
Computer Overhead
Total Latency
Full MV
26.306s/q
-
26.306s/q
Random+ES
19.022s/q
-
19.031s/q
EMS
14.146s/q
16.007ms/q
14.162s/q
Appendix
Table 7: Runtime analysis on AQUA. LLM latency is recomputed according to the actual scheduling protocol. Computer overhead includes ACM scoring, stopping verification, and reliability updating.
Department of Electrical and Computer Engineering, The University of Hong Kong · School of Artificial Intelligence, Sun Yat-sen University · Southern Marine Science and Engineering Guangdong Laboratory (Zhuhai) +1