PaperlayerView exact revision on arXiv

Source-linked AI summary

Beyond Solo and Consistency: Vindicating Multi-Agent Debate via Conditional Progressive Pruning

Ruosong Ye, Caiqi Zhang, Jiahao Li, Haijun Wu, Xiaolong Luo, Huiyuan Chen, Yu Wang, Ying Chen, Zhenting Wang, Kai Mei, Yang Zhou, Dimitris N. Metaxas

arXiv:2609.33974v1cs.CL

TL;DR

Existing MAD methods may underestimate communication cost by counting tokens without normalizing across LLMs, and underuse intermediate discussion results and agent-specific behavior for pruning and personalized information passing. CPP is a lightweight pruning framework that uses intermediate debate results and autoregressively models conditional actions, alongside a debate-tailored reward. CPP is reported as the first state-of-the-art MAD framework to fully outperform single agents and heterogeneous consistency methods under the same computational cost.

  • Problem

    Existing MAD methods may underestimate communication cost by counting tokens without normalizing across LLMs, and underuse intermediate discussion results and agent-specific behavior for pruning and personalized information passing.

    Source: §1 · pp. 1–2

  • Method

    CPP is a lightweight pruning framework that uses intermediate debate results and autoregressively models conditional actions, alongside a debate-tailored reward.

    Source: §1 · p. 2, §3.2.1 · p. 4

  • Results

    CPP is reported as the first state-of-the-art MAD framework to fully outperform single agents and heterogeneous consistency methods under the same computational cost.

    Source: §5 · p. 9

  • Takeaways & Limitations

    The authors conclude that their results verify MAD’s advantage and provide an empirical foundation for future multi-agent work.

    Source: §5 · p. 9

Abstract

from arXiv · show

Large Language Model (LLM) based Multi-Agent Debate (MAD) is one of the most effective test time scaling techniques. Through multi-round communication, agents complement each other in knowledge and reasoning and solve tasks that no single member can solve. However, existing MAD frameworks fail to beat strong Single Agent and Consistency-based baselines under the same strict cost limit, which shakes the foundation of the MAD field. We propose Conditional Progressive Pruning (CPP), a lightweight pruning framework that fully exploits multi-round MAD. CPP outperforms all existing MAD frameworks on multiple dominated benchmarks. It is also the first to fully outperform consistency methods. Our code, detailed agent interaction records will be released soon.

1 INTRODUCTION

Multi-Agent Debate (MAD) may benefit from multi-round communication, but under equal computational cost existing frameworks struggle to outperform strong consistency baselines. CPP addresses limits in cost accounting, use of intermediate results, and debate-specific optimization, and reports strong benchmark results.

1 INTRODUCTION

  • Existing MAD frameworks can underestimate cost by counting tokens without normalizing across different LLMs.The introduction also identifies insufficient use of intermediate discussion results for pruning and inadequate modeling of agent behavior for personalized information passing.Source: §1 · pp. 1–2
  • CPP autoregressively models conditional probabilities between earlier and later actions and progressively prunes using intermediate MAD results.The authors contrast this with prior methods that base decisions only on interactions between LLM profiles.Source: §1 · p. 2
  • CPP is reported as the first framework to fully outperform consistency methods and single agents under the same computational cost.The paper also presents this result as vindicating MAD’s value.Source: §1 · p. 2
  • The paper designs a reinforcement-learning algorithm for multi-round MAD with a tailored reward and Agent Behavior Embedding.The authors say these components can generally improve MAD convergence performance.Source: §1 · p. 2
  • Experiments on MATH-Hard, GPQA, and MMLU-Pro report CPP as the state-of-the-art MAD framework, with advantages in robustness, efficiency, and scalability.The paper also identifies a lack of debate-specific reinforcement-learning algorithms as an opportunity for optimization.Source: §1 · p. 2

2 RELATED WORK

Prior MAD work spans heuristic debate pruning and learned approaches to selecting communication edges or debate information. CPP is situated among methods that use learned pruning, agent representations, or intermediate debate results.

2.1 HEURISTIC MULTI-AGENT DEBATE

  • Heuristic MAD methods include fully connected debate, dynamic pruning based on response quality and diversity, and zero-shot LLM selection of information, which greatly increases cost.Consistency methods instead use independent sampling and majority voting, while self-discussion methods are described as unstable without external feedback.Source: §2.1 · p. 2

2.2 LEARNING-BASED MULTI-AGENT DEBATE

  • Learned MAD methods range from reinforcement-learning edge pruning and profile-based pruning models to autoregressive topology generation and direct filtering of intermediate results.GPTSwarm (Zhuge et al., 2024) introduced reinforcement learning for dynamic pruning; G-Designer (Zhang et al., 2024) bases decisions on agent-profile interactions, while AnyMAC (Wang et al., 2025a) filters intermediate results without modeling conditional action probabilities.Source: §2.2 · p. 2
  • Prior agent embeddings usually start from textual profiles, whereas CPP encodes each agent’s responses to specific validation questions and trains the embedding with CPP.The paper characterizes response-based initialization as modeling concrete behavior and carrying richer information than a general profile description.Source: §2.2 · p. 3

3 CPP: CONDITIONAL PROGRESSIVE PRUNING

CPP combines agent-specific behavior representations with conditional, progressive edge pruning across debate rounds. Its pipeline also uses a debate-tailored reward and accumulates rewards across related actions.

3.1 INFERENCE PIPELINE

  • FuseGLU takes an LLM behavior embedding, query, and candidate response as inputs and makes action decisions autoregressively, conditioning on previous actions.The figure describes the candidate as being combined with the available information at each decision.Source: Figure 1 · p. 3

3.1.1 AGENT BEHAVIOR MODELING

  • CPP initializes each agent’s behavior embedding by encoding its responses to specific validation questions, then trains that embedding with the pruning framework.The authors say this directly models concrete agent behavior and carries richer information than a general profile description.Source: §3.1.1 · p. 3

3.1.2 CONDITIONAL PRUNING: FUSEGLU

  • FuseGLU fuses the receiving agent’s behavior embedding with the query, then fuses that result with the candidate response to produce an edge-keeping probability.Its gate and up projections incorporate the behavior embedding and candidate response rather than transforming the query alone.Source: §3.1.2 · p. 3
  • Each selected response is appended to the query for the agent’s next decision, conditioning actions on earlier same-round choices and linking them across rounds through debate history.The policy is modeled autoregressively over the full debate graph and uses intermediate MAD results for pruning decisions.Source: §3.1.2 · p. 4

3.2.1 DEBATE-TAILORED REWARD DESIGN

  • The debate-tailored reward depends on whether an answer is correct before and after an action and whether its edge is kept or pruned.Correct-to-wrong transitions receive −2a, wrong-to-correct transitions 2a, while later rounds use a larger reward scale; Table 1 presents the reward design.Source: §3.2.1 · p. 4, Table 1 · p. 4

3.2.2 INTER-ROUND REWARD ACCUMULATION

  • An action’s return accumulates rewards from subsequent related actions, with β discounting across rounds and γ within a round.The paper illustrates this with an edge that affects later same-round decisions and responses passed to agents in the next round.Source: §3.2.2 · p. 4

4 EXPERIMENTS

Across the reported benchmarks, CPP outperforms existing MAD methods while costing less than Full-Debate, and it is the only method reported to outperform all consistency methods on every benchmark. The experiments also compare MAD with cost-matched consistency and scaled single-agent chain-of-thought settings.

4.1 EXPERIMENTAL SETUP

  • Experiments use MATH-Hard, MMLU-Pro, and GPQA, with three LLMs in the main experiments and Grok-4.3 in specified robustness, ablation, and efficiency experiments.The pruning model uses FuseGLU and is trained with on-policy reinforcement learning.Source: §4.1 · p. 5

4.2.1 BEYOND EXISTING MADS

  • 68.17% on MATH-Hard, 68.67% on GPQA-Diamond, and 66.33% on MMLU-Pro: CPP achieves the highest accuracy among MAD methods while costing less than Full-Debate on each benchmark.The comparison includes learned-pruning baselines ARG-Designer and AnyMAC, which CPP also outperforms on all three benchmarks.Source: §4.2.1 · pp. 5–6, Table 2 · p. 5

4.2.2 BEYOND EXTENDED CONSISTENCY

  • The consistency comparison extends consistency methods beyond nine samples to match the cost of a three-agent, three-round debate.Consistency-Best adds samples from Grok; Consistency-Fuse adds samples from all models in equal proportion.Source: §4.2.2 · p. 6
  • CPP is the only method reported to outperform all consistency methods on every benchmark; MAD methods also beat consistency methods in the Extension setting.Extension changes the arrangement to Mistral-only in round one, GPT-only in round two, and Grok-only in round three.Source: §4.2.2 · p. 6, Table 3 · p. 7

4.2.3 BEYOND SCALED CHAIN OF THOUGHT

  • 51.00% is the best reported single-agent result across the tested MATH-Hard CoT settings, while CPP reaches 68.17% at a cost of 98.61%.The comparison is with single agents using more CoTs under similar computational cost.Source: §4.2.3 · p. 6, Table 4 · p. 7

4.3 ABLATION STUDY AND ANALYSIS

The ablations report adversarial-setting gains, examine how reward choices trade accuracy for lower cost, and test the pipeline components and output-token limits. They find that the full design and Adv-CPP retain strong accuracy-cost performance across these settings.

4.3.1 ADVERSARIAL ROBUSTNESS

  • Adv-CPP raised adversarial accuracy from 57.33% to 58.00%, the best among methods, while retaining 65.17% vanilla accuracy at lower cost and variance.Source: Table 5 · p. 7, §4.3.1 · p. 7

4.3.2 REWARD ABLATION WITH EFFICIENCY ANALYSIS

  • Kept edges fell from 15.83 to 7.18 as k fell from 1 to −1, with cost falling from 93.79% to 77.14% and accuracy also dropping.The authors report that pruning too much from the start removes useful communication; two-stage training preserves more accuracy at lower cost.Source: Table 6 · p. 8, §4.3.2 · p. 8

4.3.3 PIPELINE ABLATION

  • Using 10 initialization samples reached 66.00%, while removing the behavior embedding reduced accuracy to 57.83%.The authors attribute the latter drop to pruning too much when the model lacks information about which agent is deciding.Source: Table 6 · p. 8, §4.3.3 · p. 9

4.3.2 REWARD ABLATION WITH EFFICIENCY ANALYSIS

  • At q85/q95/q95, Adv-CPP reached 63.00% accuracy at 84.48% cost, while Full-Debate and ARG-Designer reached 60.67% and 60.33% at costs above 89%.Adv-CPP was the only debate method on the Pareto frontier; the comparison also held when agents gave partial early-round responses.Source: Table 7 · p. 8, §4.3.2 · p. 9

5 CONCLUSION

The conclusion presents CPP as an autoregressive, intermediate-information-based pruning framework and reports its same-cost advantage over single-agent and heterogeneous consistency methods.

  • CPP prunes MAD using intermediate information between rounds and conditions across actions.Source: §5 · p. 9
  • The authors report that CPP fully outperforms single-agent and heterogeneous consistency methods under the same computational cost.Source: §5 · p. 9
  • The paper describes its findings as empirical support for MAD and a foundation for future multi-agent work.Source: §5 · p. 9

AI USE STATEMENT

The authors describe AI assistance in code checking, optimization suggestions, table and figure generation, and English polishing, while distinguishing these uses from generating code or scientific content.

  • AI checked handwritten code and provided optimization suggestions, but the final code contained no directly AI-generated parts.Source: AI USE STATEMENT · p. 10
  • AI helped generate tables and figures from human-obtained experimental results, but did not generate raw data or explore scientific ideas.Source: AI USE STATEMENT · p. 10
  • AI polished the draft’s English and provided writing suggestions, but was not used for mathematical claims, proofs, hypotheses, methods, or experiments.Source: AI USE STATEMENT · p. 10

A ACTION-WISE INFLUENCE DEPENDENCY

The table is titled as showing the dependency structure of A1 and A2 under a 3 × 3 MAD architecture.

  • The table concerns the dependency structure of A1 and A2.Source: Table 8 · p. 12
  • Its stated scope is a 3 × 3 MAD architecture.Source: Table 8 · p. 12
  • The caption names A1 and A2 but does not specify a particular dependency pattern.Source: Table 8 · p. 12

D DETAILED CONSISTENCY RESULTS

The detailed consistency results comprise tables on reference ratios and edge counts, output-token limits, and consistency accuracy across models and benchmarks. The accuracy tables vary sample size, with additional adversarial-consistency results on MATH-Hard-II.

Related papers

Loading 2609.33974v1…