MASTraceBench: Diagnosing Collaboration Gains through Proposal Trajectories in LLM-Based Multi-Agent Systems

Introduction

• Existing benchmarks often judge only final-answer correctness, obscuring fine-grained proposal changes and how gains arise, persist, or are lost.Other MAS benchmarks add intermediate metrics but do not directly track candidate-solution trajectories during interaction and aggregation.Source: Introduction · pp. 1–2
• MASTraceBench tracks and grades initial and final proposals alongside final MAS answers across six cooperative and competitive tasks, enabling method-level diagnosis of collaboration gains.Its metric suite includes Task Score, Collaboration Gain, proposal-trajectory indicators, and Token Cost.Source: Introduction · p. 2
• CLEARS more often preserves or improves the strongest initial proposal and achieves the highest Collaboration Gain on five of six benchmarks.Across evaluated methods, final answers rarely surpass the strongest initial proposal; interaction more often lifts weaker proposals toward it, while strong proposals may regress.Source: Introduction · p. 2

LLM-based Multi-Agent Systems

• LLM-based MAS research includes self-consistency [Wang et al. 2023], reflection [Madaan et al. 2023; Shinn et al. 2023], debate [Du et al. 2024; Liang et al. 2024], peer review [Xu et al. 2023], verification [Lifshitz, McIlraith, and Du 2025], and adaptive MAS construction.MASTraceBench evaluates representative methods and diagnoses their collaboration gains.Source: LLM-based Multi-Agent Systems · p. 2

MAS Benchmarks

• MAS benchmarks broaden evaluation to interactive tasks and intermediate metrics, while MASTraceBench focuses on method-level diagnosis through proposal trajectories.Examples include coordination and competition benchmarks and measures of task progress, communication, planning, or subproblem verification.Source: MAS Benchmarks · p. 2

Sources and Reliability of MAS Gains

• Studies analyze how MAS gains depend on voting, discussion, initial reasoning strength, diversity, majority pressure, model capability, task properties, and architecture.MASTraceBench quantitatively tracks proposal trajectories to examine how gains are produced, preserved, or lost.Source: Sources and Reliability of MAS Gains · p. 3

MASTraceBench

• MASTraceBench combines a unified framework, a multi-layer metric suite, and six cooperative and competitive tasks with graded proposal-trajectory scoring.It records and scores Proposer Agents’ initial and final proposals alongside the final MAS answer.Source: MASTraceBench · p. 3, Unified Evaluation Framework · p. 3

Unified Evaluation Framework

• For dynamic tasks, MASTraceBench records proposal trajectories at each action decision, while the complete action sequence determines the task outcome.Static tasks instead use a query and final MAS answer; Proposer Agents produce evaluated proposals, while Function Agents provide auxiliary signals.Source: Unified Evaluation Framework · p. 3

Multi-Layer Metrics

• The metric suite measures task-level performance, gain over a Single-Agent baseline, proposal evolution, aggregation loss, and token cost.Trajectory diagnostics compare the final answer with the best initial proposal, track individual proposals, and measure the gap between the final answer and best final proposal.Source: Multi-Layer Metrics · pp. 3–4

Benchmark Design

• Six tasks span cooperative and competitive, static and dynamic settings, assigning graded scores to intermediate proposals and final MAS answers.Graded scoring makes changes in proposal quality observable, including partial progress such as moving from one to two robots reaching their goals.Source: Benchmark Design · pp. 4–5, Table 1 · p. 4

CLEARS: Claim-Level Evaluation Across Agents for Reliable Synthesis

• CLEARS replaces whole-proposal interaction with claim-level evaluation, identifying endorsed and avoidable content to synthesize an answer from information across proposals.The procedure decomposes proposals into claims and uses cross-agent perspectives to identify top-endorsed claims.Source: CLEARS: Claim-Level Evaluation Across… · p. 5

Setup

• The evaluation covers selection-based, debate-based, revision-based, and adaptive MAS construction methods, all using Qwen3-32B as the shared backbone.The first three categories capture common collaboration primitives, while adaptive construction configures roles and workflows automatically.Source: Setup · p. 5
• Configurable multi-Proposer methods use three Proposers, while Int. Debate and MAPR use one interaction round.Source: Setup · p. 5
• Static-task main results average three runs per method, and competitive methods play a fixed Single-Agent baseline rather than opponent-set-dependent tournaments.Source: Setup · p. 5

50 Gomoku

• To control order effects, the evaluation alternates the first mover in Gomoku; each of the 100 Negotiation configurations is run twice, reversing which side makes the first offer.Source: §50 · p. 5

Results and Analysis

• On Gomoku, Int. Debate scores 80.00 versus 50.00 for Consistency, 46.00 for MAV, and 58.00 for Reflection; MAPR scores 72.00.Gomoku first movers are alternated; Negotiation configurations are run twice with the first-offer side reversed.Source: Results and Analysis · p. 5, §50 · p. 5
• GAB Improve remains limited on most benchmarks; most cases are OptKeep or SubKeep, while Regress is non-negligible, especially on OptionGen and EvidenceChain.Observed gains mainly carry forward an already available strong proposal rather than form a stronger answer.Source: Results and Analysis · pp. 5–6
• Weak agents often move toward the strongest initial proposal, while strong agents show limited improvement and non-negligible regression.Whole-proposal revision may carry errors from weaker proposals into otherwise strong proposals.Source: Results and Analysis · p. 6
• On MAPF, Int. Debate raises final-proposal agreement from Consistency's 3.5% to 58.2% and reduces Aggregation Loss from 11.63 to 2.22.These results associate lower aggregation loss with proposal convergence before the final decision; LLM-based aggregation yields comparable rather than uniformly better loss than majority voting.Source: Results and Analysis · pp. 6–7, Figure 6 · p. 7
• Int. Debate converts additional token cost over Consistency into stronger Collaboration Gain, while the costlier MAV and MAPR do not consistently yield further gains.Adding cross-agent claim evaluation increases token cost but consistently improves Collaboration Gain.Source: Results and Analysis · p. 7
• CLEARS achieves the highest Collaboration Gain on five of six benchmarks and reaches 6.42 on EvidenceChain, 2.50 points above Int. Debate (3.92).On Negotiation, CLEARS raises Improve to 11.2% versus 4.0% for Int. Debate and 6.6% for MAPR, while reducing Regress to 15.2% versus 24.5% and 25.4%, respectively.Source: Table 2 · p. 6, Results and Analysis · p. 7

Ablation Study

• Removing cross-agent claim evaluation lowers Collaboration Gain across all six benchmarks, supporting its contribution to CLEARS.The ablation bypasses claim evaluation and directly synthesizes all decomposed claims without filtering.Source: Ablation Study · p. 7
• On EvidenceChain, limited GAB Improve and substantial GAB Regress and strong-proposal regression persist across proposer counts, interaction rounds, and model compositions.The reported configurations still frequently improve initially weak proposals.Source: Ablation Study · p. 7

• MASTraceBench enables method-level comparison and proposal-trajectory diagnosis of LLM-based MAS.Source: Conclusion · p. 7
• Analyses using MASTraceBench reveal recurring limitations in existing methods and motivate CLEARS.Source: Conclusion · p. 8
• CLEARS is validated across six tasks, and MASTraceBench is presented as a testbed for studying collaboration mechanisms and developing more reliable MAS.Source: Conclusion · p. 8

• For static tasks, Task Score (TS) averages the scores of final MAS answers across samples.Source: Benchmark Details · p. 10
• For dynamic tasks, TS is computed over complete interaction episodes.Source: Benchmark Details · p. 10
• The proposal scoring function S(·) evaluates each action proposed at an intermediate state in dynamic tasks.Source: Benchmark Details · p. 10

• MAPF is a cooperative planning task in which robots move simultaneously on a shared grid toward designated goals.Each joint plan gives an action sequence for every robot and is executed for at most 30 steps, with invalid movements and inter-robot collisions checked.Source: MAPF · p. 10
• The benchmark uses 157 independently constructed MAPF instances with varying map layouts and robot configurations.Source: MAPF · p. 10
• A proposal score is the fraction of robots in an instance that reach their designated goals when the joint plan is executed.The graded score gives partial credit when only a subset succeeds.Source: MAPF · p. 10
• TS is the mean arrival rate of final MAS plans over all instances, and both proposal scores and TS are multiplied by 100 for reporting.Source: MAPF · p. 10

• OptionGen converts RACE reading comprehension into generating four options from an article and question: one correct answer and three plausible, distinct distractors.The evaluation uses 235 instances, withholding original options and derived scoring criteria from the MAS.Source: OptionGen · p. 10
• Instance-specific rubrics specify the correct answer’s required content and errors to avoid, and the distractors’ plausibility, incorrectness, and suitability.The rubrics are generated from the original RACE options and ground-truth label before scoring and are not given to the MAS.Source: OptionGen · p. 10
• The judge separately scores correct-option and distractor-set quality on 0–100 scales using six anchored intervals; it is Qwen3-32B at temperature 0.Source: OptionGen · p. 10
• TS is the mean score of final MAS option sets across evaluation instances.Source: OptionGen · p. 10
• Human validation covered 50 stratified instances and 550 option sets from 11 methods, scored independently by three blinded graduate student annotators.Annotators used the same two-component rubric and 0–100 anchors as the LLM judge, with outputs presented in randomized order.Source: OptionGen · pp. 10–11
• 0.919 Pearson and 0.818 Spearman correlations measure agreement between the LLM judge and mean human ratings on OptionGen outputs.Source: Table 5 · p. 11, OptionGen · p. 11

EvidenceChain

• EvidenceChain requires selecting and ordering supporting facts into a coherent reasoning chain, scored for set correctness and pairwise ordering consistency.The benchmark contains 100 detective-story instances; final Task Score averages evidence-chain scores and is reported on a 0–100 scale.Source: EvidenceChain · p. 11, Figure 9 · p. 16

Gomoku

• Gomoku evaluates win rate and move quality separately, using rule-based self-formation and defense-interception scores whose mean correlates positively with task score.Games use a 15 × 15 board with 50 games per method pairing and balanced starting colors; invalid moves score zero, and blocking the opponent’s sole open five-stone endpoint receives the highest defense score.Source: Gomoku · pp. 11–12

Negotiation

• Negotiation uses private item valuations, alternating complete-allocation proposals, and a 10-round discounted horizon; proposal scores are zero unless the opponent would accept.Task Score averages normalized episode payoffs across scenarios and both role assignments.Source: Negotiation · p. 12

TacticDuel

• TacticDuel scores wins, draws, and losses as 1, 0.5, and 0, and its graded move scores account for damage dealt and received; mean proposal score correlates positively with Task Score.The task is a simultaneous-action combat game, and the proposal score also gives Charge a fixed energy-management bonus.Source: TacticDuel · pp. 12–13

Benchmark Task Prompts; Model and Inference Settings; Main-Experiment Method Configurations

• All methods receive the same task-specific benchmark prompts and common inference settings, while coordination prompts remain benchmark-agnostic; CLEARS evaluates endorsements and challenges on decomposed claims before synthesis.The configurations also include single-agent and selection-based, debate-based, revision-based, and adaptive MAS approaches; CLEARS w/o CCE removes cross-agent claim evaluation.Source: Benchmark Task Prompts · p. 13, Model and Inference Settings · p. 13, Main-Experiment Method Configurations · pp. 13–14

Output Validity and Final-Proposal Agreement

• Output Validity ranges from 93.4% to 100.0%, while MAPF Final-Proposal Agreement rises from 3.5% for Consistency to 58.2% for Int. Debate; MAPR has lower agreement than Int. Debate on all six benchmarks.Agg. Debate has agreement broadly comparable to Int. Debate, and the high validity rates indicate extraction failures have little influence on trajectory diagnostics.Source: Output Validity and Final-Proposal… · p. 14, Table 9 · p. 15

Full Token Cost Results

• Across four additional benchmarks, interactive methods use substantially more tokens than Single-Agent without necessarily gaining more collaboration; MAPR costs the most, while removing CLEARS cross-agent claim evaluation cuts its cost by approximately half.The main results show that cross-agent claim evaluation consistently improves Collaboration Gain.Source: Full Token Cost Results · p. 14, Table 10 · p. 15

Full Agent Refinement Results

• On four additional benchmarks, weak proposals often move toward the strongest initial proposal, while strong proposals are usually preserved or kept and may regress; MAPR increases both upward refinement and regression.Figure 10 shows these patterns for Int. Debate and MAPR on MAPF, OptionGen, Negotiation, and TacticDuel; Surpass and Improve remain relatively limited.Source: Full Agent Refinement Results · p. 14, Figure 10 · p. 17

Full Token Cost Results

• The templates specify Gomoku’s board, legal placements, and tactical priorities; Negotiation’s valuations, payoffs, rules, and strategic guidance; and TacticDuel’s combat state, actions, and round history.Source: Figure 14 · p. 18, Figure 15 · p. 18, Figure 16 · p. 19