S ^2 - MAD : Breaking the Token Barrier to Enhance Multi-Agent Debate Efficiency (2025)

Abstract: Large language models (LLMs) have demonstrated remarkable capabilities across various natural language processing (NLP) scenarios, but they still face challenges when handling complex arithmetic and logical reasoning tasks. While Chain-Of-Thought (CoT) reasoning, self-consistency (SC) and self-correction strategies have attempted to guide models in sequential, multi-step reasoning, Multi-agent Debate (MAD) has emerged as a viable approach for enhancing the reasoning capabilities of LLMs. By increasing both the number of agents and the frequency of debates, the performance of LLMs improves significantly. However, this strategy results in a significant increase in token costs, presenting a barrier to scalability. To address this challenge, we introduce a novel sparsification strategy designed to reduce token costs within MAD. This approach minimizes ineffective exchanges of information and unproductive discussions among agents, thereby enhancing the overall efficiency of the debate process. We conduct comparative experiments on multiple datasets across various models, demonstrating that our approach significantly reduces the token costs in MAD to a considerable extent. Specifically, compared to MAD, our approach achieves an impressive reduction of up to 94.5% in token costs while maintaining performance degradation below 2.0%.

## introduction large language models (llms) have shown exceptional capabilities across a variety of natural language processing (nlp) tasks @xcite @xcite @xcite @xcite . however, even the most advanced llms exhibit limitations * corresponding authors. to address these challenges, researchers have introduced techniques such as chain-of-thought (cot) reasoning @xcite which decomposes complex problems into sequential steps, and self-consistency (sc) mechanisms @xcite , along with self-correction strategies @xcite @xcite . despite these innovations, studies have shown that llms still struggle to improve through selfcorrection alone @xcite @xcite ). an emerging alternative is the multi-agent debate (mad) framework, in which multiple independent agents propose and critique their own answers through rounds of debate, ultimately converging on a more robust consensus @xcite . mad has demonstrated promise in addressing the limitations of llm self-correction by leveraging diverse agent perspectives to refine answers over iterative discussions @xcite @xcite . however, as the number of agents and debate rounds increase, the token cost escalates significantly, limiting the scalability of mad, especially in resource-constrained environments @xcite . to alleviate the token cost problem in multi-agent debates, researchers have proposed several strategies. for instance, @xcite summarizes agents' outputs at the end of each round, while @xcite introduces a "forgetting" mechanism, where only the previous round's outputs is retained for future rounds. another approach, sparse-mad (s-mad) @xcite , reduces communication overhead by limiting information exchange to neighboring agents. groupdebate (gd) @xcite further reduces token cost by clustering agents into smaller debate groups that exchange intermediate results between groups. although the reduction in token cost have achieved by the aforementioned approaches, our experiment reveals a substantial presence of redundancy and duplicate information in the inter-agent information exchange. as depicted in figure 1 , agent 1 and agent 3 exhibit repetitive viewpoints, leading to exacerbate the issue of token cost due to redundant duplication during the inter-agent information exchange. the issue of redundancy and duplication primarily stems from two potential factors: the limited solution space inherent in complex reasoning tasks, and the tendency of large language models to generate repetitive responses when faced with similar inputs @xcite @xcite . to address these limitations, we propose a novel approach selective sparse multi-agent debate (s 2 -mad), as shown in figure 2 . this approach utilizes a decision-making mechanism to determine whether to participate in the debate, thereby further reducing token cost within multi-agent debates. specifically, based on a grouping strategy, s 2 -mad first generates initial viewpoints for the agents. in each round of debate, the decision-making mechanism enables agents to selectively incorporate non-redundant responses that differ from their current viewpoints for answer checking and updating. the agents have the option to selectively engage in both intra-group and inter-group discussions, enabling them to actively participate in debates. the process concludes either when consensus is reached among the agents or when a final answer is obtained through majority voting. to validate the effectiveness of s 2 -mad, we conduct a theoretical analysis of total token cost and perform extensive experiments across five tasks using different models. these experiments compare s 2 -mad with existing multi-agent debate strategy as well as single-agent reasoning approaches, demonstrating its capability to significantly reduce token counts while maintaining comparable accuracy. specifically, s 2 -mad reduces token cost by up to 94.5% compared to mad, 90.2% compared to mad-sparse, and 87.0% compared to gd, while also significantly reducing token cost by up to 81.7% compared to cot-sc. importantly, these reductions come with a performance degradation of less than 2.0%, demonstrating that s 2 -mad maintains high accuracy while minimizing communication overhead. the main contributions of this paper are as follows: mad-based methods and token cost. (i) mad @xcite involves several steps. initially, each agent is provided with a question and generates an individual response. these responses then form the new input context for each agent, leading to the generation of subsequent responses. this debate procedure is repeated over multiple rounds, with the final answer derived through majority voting. the token cost complexity is t oken m @xmath0. (ii) s-mad @xcite decreases token consumption by sparsifying the fully connected topology of information exchange among agents within the standard mad framework. let p r denote the probability of each edge being removed. the token cost complexity can be represented as t oken s-m @xmath1. (iii) gd @xcite reduces token consumption through a group discussion strategy. let n denote the number of groups and s represent the number of inter-group debate stages. the token cost complexity is computed as t oken @xmath2. ## methodology in this section, we first introduce the overall process of s 2 -mad along with the details of decision-making mechanism. and then we provide mathematical analysis of the token cost for our method subsequently. ## conclusion in this work, we identified the issue of redundant viewpoints among agents in multi-agent debate (mad). to address this, we proposed selective sparse multi-agent debate (s 2 -mad), a novel strategy designed to reduce token cost by selectively incorporating non-redundant viewpoints from different agents, thereby significantly improving the efficiency of information exchange and debate. our theoretical analysis verify the effectiveness of s 2 -mad, and extensive experiments conducted on five benchmark datasets demonstrate that s 2 -mad can significantly reduce token cost in mad while maintaining competitive performance. for future work, we aim to refine s 2 -mad by further optimizing the identification and condensation of non-redundant viewpoints between agents, with the goal of further reducing token cost and enhancing efficiency. additionally, exploring methods to increase the diversity of thought among agents will be key to improving the overall accuracy of s 2 -mad.