acceptodds
Under review as a conference paper at ICLR 2027

GraphMAS: A Systematic Benchmark of Multi-Agent Coordination for Graph Learning

Abstract

Large language model (LLM)-based multi-agent systems coordinate specialized reasoning through aggregation, interaction, and adaptive control, yet their potential for graph learning remains largely unexplored. Graph learning is a natural setting for such systems because useful evidence may arise from heterogeneous local, long-range, global structural, and semantic perspectives whose relevance varies across instances. Existing LLM-based graph learning approaches primarily rely on single-agent reasoning, while multi-agent coordination has been studied mainly in general reasoning settings. Consequently, it remains unclear whether multiple specialized agents can improve graph learning and how different coordination strategies should be designed and evaluated. To address this gap, we introduce GraphMAS, a systematic benchmark of multi-agent coordination for graph learning. GraphMAS builds a shared pool of graph reasoning specialists and organizes coordination along two dimensions, inter-agent interaction and runtime adaptivity, yielding four paradigms and seven representative coordination methods. Under a unified protocol, we evaluate these methods across seven text-attributed graphs, three domains, and two representative graph learning tasks: node classification and link prediction. Our study shows that heterogeneous graph perspectives are strongly complementary, and that coordinating specialists improves over both individual specialists and single-agent graph reasoning methods, with gains that arise from decomposing reasoning across specialists rather than from broader evidence access alone. However, richer inter-agent interaction does not reliably help, whereas instance-adaptive specialist selection yields the strongest accuracy–efficiency trade-off. We further show that the coordination policy can be learned over a fixed specialist pool and transfers to held-out graphs. GraphMAS therefore provides a controlled evaluation framework and empirical principles for understanding when and how multi-agent coordination benefits graph learning. The benchmark code is available at https://anonymous.4open.science/r/GraphMAS.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Multi-Agent Systems, Large Language Models, Graph Learning, Agentic Graph Learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_nCzJOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes GraphMAS, a systematic benchmark for evaluating multi-agent coordination strategies in graph learning. The authors construct a shared pool of four graph reasoning specialists, organize coordination along two dimensions, including inter-agent interaction and runtime adaptivity, yielding four paradigms, and instantiate seven representative coordination methods. Evaluation is conducted across seven text-attributed graph (TAG) datasets on two tasks: node classification and link prediction. Key findings include: multi-agent gains arise from "reasoning decomposition" rather than "evidence accumulation"; richer inter-agent interaction does not reliably improve performance; instance-adaptive routing achieves the best accuracy–efficiency Pareto trade-off; and the coordination policy can be learned via PPO and generalizes to held-out graphs.

Critical strengths

This paper provides a summary of current agent coordination approaches and graph datasets in the graph learning domain, conducts robust experiments, and offers certain conclusions and reference results, such as training a Router via PPO and validating its transferability to unseen graphs.

Critical weaknesses
  1. The narrative logic in the Introduction suffers from a fundamental ambiguity. The authors first state that multi-agent coordination for graph learning "remains largely unexplored," implying that agents should be employed to solve graph learning problems (Agent-for-Graph). They then immediately claim that graph learning "provides a natural setting for studying multi-agent coordination," implying that multi-agent coordination can be studied through graph learning (Graph-for-Agent). This reversal of the service relationship makes it difficult to determine whether this paper aims to evaluate an agent-for-graph benchmark or a graph-for-agent benchmark, resulting in a confused positioning.
  2. The contribution is very limited. The benchmark comprises only 7 datasets, covers only two graph tasks, is restricted entirely to text-attributed graphs, and uses exclusively publicly available datasets. This cannot reasonably be called a "Systematic Benchmark" for graph learning; it should more accurately be termed a TAG benchmark.
  3. The attribution of "reasoning decomposition" lacks rigorous controls. In Table 3(b), the paper concludes that multi-agent gains arise from "reasoning decomposition," because distributing evidence across multiple agents for independent reasoning outperforms a single agent processing all evidence in one long context. However, the true cause of the single agent's performance degradation may simply be context window overload or attention dilution due to excessively long prompts (i.e., the "lost-in-the-middle" phenomenon), rather than any inherent "cognitive advantage" of multi-agent coordination. The authors lack critical control experiments, for example, restricting the single agent's total token input (via Top-K truncation or evidence compression), or using models with long-context optimization (e.g., Ring Attention). Without eliminating the "context length confound," one cannot rigorously demonstrate the independent contribution of "decomposed reasoning."
  4. The theoretical analysis is limited. Although the core contribution of this paper is to provide a benchmark that offers reference for future research directions, the paper lacks theoretical justification for why such a benchmark is needed. Furthermore, the reasons why certain methods perform poorly in the experiments are not elaborated in detail. A substantial portion of the paper is devoted to describing repetitive conclusions.
Questions for authors
  1. What is the positioning of this paper—is it an agent-for-graph benchmark or a graph-for-agent benchmark? This distinction is critical for evaluating the paper's contribution and value。
  2. In Table 3(b), is the single agent's weaker performance simply due to excessively long input context? If the single agent's total token input were strictly constrained, would the multi-agent "decomposition advantage" still persist?
  3. My concern is: what is the core objective of this paper? Is it to provide design guidance for multi-agent systems in graph learning? If so, the experimental conclusions presented here appear to offer limited actionable guidance. More meaningful conclusions would explain why such performance patterns emerge, identify substantial performance gaps on other domains or self-constructed datasets, thereby revealing what problems exist in current research and how future work should proceed.
6 comments

We appreciate the reviewer’s careful evaluation and suggestions. We respond to the raised concerns below:

W1,Q1: Paper positioning.

To clarify, GraphMAS is an Agent-for-Graph benchmark. We compare seven coordination strategies over the same four graph specialists to measure how specialist participation and communication affect accuracy and inference cost in graph learning tasks.

By “largely unexplored,” we mean that multi-agent coordination has received little controlled study for graph learning. LLM-based graph methods are mostly single-agent, and existing multi-agent methods propose a single architecture for a single task. GraphMAS fixes a shared pool of specialists and varies only the coordination strategy. This separates the effects of graph evidence and reasoning from those of inter-agent interaction and runtime adaptivity.

By “natural setting,” we mean that the structure of graph evidence gives a direct reason to use multiple specialized agents for graph learning. Immediate neighbors may provide the strongest evidence for one prediction, while longer-range structure or semantically similar nodes matter more for another. Assigning these perspectives to specialists lets us test which specialists to consult and how to combine their judgments to improve graph predictions. Both sentences therefore treat graph learning as the beneficiary of multi-agent coordination. These revisions are detailed in the Abstract and Section 1.

W2: Benchmark scope.

“Systematic” refers to our controlled study of multi-agent coordination across two design dimensions, four paradigms, and seven methods under a unified protocol, rather than exhaustive coverage of graph learning. Text-attributed graphs are the standard setting for LLM-based graph learning, as LLM agents reason over node text.

Within this setting, GraphMAS is diverse along several axes. It spans three domains (citation, e-commerce, and social networks), two task levels (node classification and link prediction, giving 14 dataset-task settings), and a wide range of scales and label spaces (13K to 173K nodes and 3 to 47 classes). It further tests generalization on held-out graphs and validity under two additional backbones.

This scope is consistent with established benchmarks and studies for LLM-based graph learning, which are likewise restricted to text-attributed graphs with a similar number of datasets and tasks. Chen et al. (SIGKDD Explorations 2024) [1], GLBench (NeurIPS 2024) [2], and LLMNodeBed (ICML 2025) [3] evaluate four, seven, and ten graphs on node classification alone, and Wang et al. (ACL Findings 2026) [4] evaluate four on node classification and link prediction, whereas GraphMAS covers more dataset-task settings than each. Public datasets with splits aligned with prior work also keep our results reproducible and comparable.

  • [1] Chen et al. Exploring the Potential of Large Language Models (LLMs) in Learning on Graphs. SIGKDD Explorations, 2024.
  • [2] Li et al. GLBench: A Comprehensive Benchmark for Graph with Large Language Models. NeurIPS Datasets and Benchmarks, 2024.
  • [3] Wu et al. When Do LLMs Help With Node Classification? A Comprehensive Analysis. ICML, 2025.
  • [4] Wang et al. Exploring Graph Learning Tasks with Pure LLMs: A Comprehensive Benchmark and Investigation. Findings of ACL, 2026.

W3,Q2: Context length and reasoning decomposition.

We ran single-agent controls with the same settings used in Appendix C.8, while reducing the evidence budget through Top-1 truncation, proportional truncation, and LLM-based evidence compression respectively.

ConfigurationEvidence tokens (LP / NC)LPNC
Single agent (original)1593 / 106674.665.6
Top-1 truncation592 / 37573.364.6
25% truncation402 / 27070.964.3
Evidence compression390 / 26474.265.4
Multi-agent (LLM Aggregation)398 / 266 per specialist80.067.7

Shorter contexts do not close the gap. Truncation lowers accuracy, while compression retains similar accuracy to the original single-agent setting at evidence lengths close to those of each specialist. It still trails multi-agent reasoning by 5.8 points on LP and 2.3 on NC, suggesting that context length alone does not explain the gap. The controls are detailed in Appendix C.8.

W4,Q3: Research objectives and empirical insights.

GraphMAS has several main objectives, including: establishing the effectiveness of MAS for graph prediction, providing a controlled benchmark that yields insights into coordination design, and presenting a strong learned-coordination baseline for future works. We consider such an empirical foundation necessary at this stage, as multi-agent graph learning is still emerging, with limited controlled evidence on whether, why, or when coordination helps. To our knowledge, GraphMAS is the first systematic benchmark to establish it against GNN, LLM-based, and agentic single-agent methods. We therefore see a theoretical account as valuable future work building on these findings.

In the original manuscript, we included extensive analyses of why the benchmark is needed and why methods differ. The oracle exceeds the best specialist by 16.9 points on LP, showing that specialists are complementary and leave clear headroom for coordination, as detailed in Appendix C.1. Specialized roles reduce LP accuracy by 3.1 points without matching evidence, showing that specialization requires combining evidence and roles (Finding 3). A single agent given all four evidence sources trails distributed specialists by 5.4 points, showing that decomposition provides gains beyond evidence access (Finding 4). Coordination methods differ by 4.4 points under unanimous agreement but 19.3 under strong disagreement, showing that coordination matters most where specialists disagree (Finding 6).

To give further insight into why specific methods underperform, we conducted an additional trajectory analysis in the revised manuscript. Recorded trajectories show that Debate, DyLAN, and Graph of Agents abandon an initially correct prediction on 10% to 16% of disagreeing LP instances while independent methods abandon none, indicating that specialists often give up correct answers after seeing incorrect peer responses (Appendix C.10, see also our response to Reviewer qpWz [Q1]), which provides more insights on why richer interaction does not improve over independent coordination (Finding 5).

Again, we sincerely appreciate the reviewer's thoughtful feedback. We hope our responses and revisions further clarify our contributions and address the concerns.

We thank the authors for the detailed response. The additional control experiments addressing the "reasoning decomposition" attribution are well-designed and effectively eliminate the context-length confound. This is acknowledged.

However, two fundamental issues remain unresolved:

  1. Limited Benchmark Scope and Lack of New Data (W2): The authors defend the narrow scope by citing other works that also focus on TAGs. However, an "appeal to common practice" is not a valid defense for a limited scope and overclaiming. The existence of similar limitations in other works does not absolve this paper of its own. Furthermore, the paper introduces no new datasets or evaluation protocols to expose the blind spots of current SOTA methods. Relying solely on public datasets to benchmark existing generic coordination templates severely limits its core contribution as a benchmark.
  2. Missing Analysis on Graph Topological Properties: The response entirely fails to address how graph topological properties (e.g., homophily/heterophily) influence the optimal coordination strategies. If the conclusions regarding coordination are entirely independent of graph topologies, what fundamentally distinguishes this work from a general-purpose multi-agent evaluation report? Without this graph-specific analysis, the paper offers limited actionable guidance for future algorithmic design in graph learning.
Reviewer_Wra5OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces GraphMAS, a benchmark for studying multi-agent coordination in graph learning. It constructs four specialists covering proximal, distal, global structural, and semantic evidence, and compares seven coordination methods across seven text-attributed graphs on node classification and link prediction. Experiments examine the contributions of evidence specialization, reasoning decomposition, and inter-agent interaction. Results favor adaptive specialist selection over richer communication, while PPO training further improves routing performance and enables transfer to held-out graphs.

Critical strengths
  1. The paper proposes a useful and well-motivated benchmark.
  2. Experiments help explain where the gains come from. The paper provides useful insights beyond simply showing that multiple agents outperform one.
  3. The paper includes Practical findings on accuracy and efficiency.
Critical weaknesses
  1. Limited evaluations. Results rely on single stochastic runs over approximately 1,000 test instances per dataset–task pair. Although additional backbones are examined, these checks cover only three graphs with 100 instances each. There is no controlled analysis of how graph size, context length, model capability, and computational budget affect the conclusions. In particular, it remains unclear whether the multi-agent advantage persists when a stronger single agent has a larger context window and a well-designed agentic harness.
  2. The PPO results do not isolate improvements in specialist selection. The router both selects specialists and generates the final answer. Freezing the specialists establishes that the improvement comes from the router, but does not distinguish better selection and stopping from better answer synthesis. A trained aggregator over fixed reports, or a trained answer generator with a fixed consultation policy, would help separate these effects.
  3. The practical advantage of predefined specialization remains underexplored. A fixed specialist pool is useful for controlled benchmarking, but its advantage over a single orchestrator that dynamically delegates subtasks to subagents is not established. I'm curious about this setting since modern agnetic harness seems more like that latter architecture rather than pre-defined roles.
  4. The link-prediction negatives may be insufficiently challenging. Uniformly sampled negative edges can be distinguishable from positive edges through broad semantic or degree differences.
  5. The study does not examine scaling the number of agents. All main conclusions depend on a pool of four predefined specialists. Varying the pool size and composition would clarify whether the observed benefits come from complementary perspectives, additional reasoning samples, or the coordination mechanism. It would also reveal whether adaptive routing becomes more valuable as the pool grows, and see the boundary of MAS.
Questions for authors
  1. How stable are the conclusions when increasing backbone capability, context length, and reasoning budget?
  2. What advantages do you expect from predefined graph specialists over a main agent that dynamically spawns subagents? Under matched model capacity and total inference budget, which benefits of explicit specialization would you expect to remain as models and agentic harnesses improve?
  3. How do you think MAS will affect the future of graph prediction? Will MAS or agent-harness-like structures stand out?
  4. For a specific task, is a better approach to train a specialized LLM/GNN, or to define an MAS? Which pipeline would be more cost-effective in the future?

A convincing response would increase my confidence in the conclusions and could justify a higher score.

9 comments

We appreciate the reviewer’s careful reading and helpful comments. Our responses are provided below.

W1,Q1: Multi-seed results, backbone generality, and where multi-agent gains arise.

Multi-seed results. Following prior single-agent graph learning work, our main results evaluate 1,000 instances per dataset and task in a single run. To account for stochasticity, we ran all four specialists with two additional fixed seeds, 43 and 44, and re-evaluated three representative coordination methods. We detail the mean and standard deviation of seven-dataset average accuracy below.

MethodLPNC
Best single specialist74.3 ± 1.067.7 ± 0.3
Majority Vote75.2 ± 1.068.6 ± 0.4
LLM Aggregation80.2 ± 1.068.4 ± 0.2
Adaptive Routing80.5 ± 0.968.7 ± 0.2

Adaptive Routing exceeds the best single specialist by 6.2 and 1.0 points, margins well above the run-to-run variation. Full per-dataset results are in Appendix C.6 of the revised manuscript.

Backbone capability. We expand the backbone check from 100 to 1,000 instances per dataset and task on the three graphs, replacing the backbone for all baseline, specialist, and coordination calls. We detail average accuracy below:

MethodQwen2.5-7B (LP / NC)GLM-4-32B (LP / NC)
Search-o163.8 / 51.068.6 / 69.5
GraphSearch64.5 / 48.759.2 / 70.9
LLM Aggregation67.9 / 56.172.7 / 73.3
DyLAN63.3 / 57.467.5 / 73.8
Adaptive Routing69.4 / 57.073.7 / 74.9

The best multi-agent method outperforms the strongest single-agent baseline in all four settings by 4.0 to 6.4 points, with Adaptive Routing best in three, suggesting that coordination benefits extend across model sizes and families. Updated full results are in Appendix C.5 of the revised manuscript.

Graph scale. Across the seven graphs, Spearman correlations between node count and Adaptive Routing’s gain over GraphSearch are ρ = 0.64 with exact p = 0.14 on LP and ρ = −0.25 with p = 0.59 on NC, showing no consistent graph-size trend. We also rank instances by query degree within each dataset and task and split them into thirds. Degree is the mean endpoint degree for LP and target-node degree for NC. Median degrees across datasets are 2.5/16/68 for LP and 1/3/20 for NC. Seven-dataset average accuracy is shown below:

MethodLP LowLP MidLP HighNC LowNC MidNC High
GraphSearch81.672.161.165.668.268.5
Proximal80.471.769.065.168.769.1
Distal78.471.861.063.666.867.9
Global87.275.255.065.168.569.5
Semantic85.276.261.562.966.868.3
Majority Vote85.176.766.166.369.170.6
LLM Aggregation82.781.475.966.469.070.3
Adaptive Routing82.781.676.566.669.270.5

On LP, GraphSearch and Adaptive Routing perform similarly at low degree, but lose 20.5 and 6.2 points from low to high degree, respectively. In the high-degree third, Routing thus leads GraphSearch by 15.4 points and the strongest specialist, Proximal, by 7.5, indicating that coordination helps most where there is more evidence to weigh. On NC, all three coordination methods outperform GraphSearch and every specialist across all degree groups, with a consistent margin throughout. Full results are in Appendix C.11.

W1: Stronger single-agent baselines, larger context, and agentic harnesses.

We agree that stronger single-agent controls are important. Our baseline, GraphSearch, a purpose-built agentic graph reasoning method, already employs iterative graph retrieval and reasoning rather than single-pass prompting. We further discuss two extensions to examine whether its performance can be improved through additional context capacity and a structured agentic harness.

Longer Context. We expand GraphSearch's context window from 8K to 32K tokens and maximum searches from 4 to 16, matching the maximum combined search allowance of four specialists. Across seven datasets, accuracy is nearly unchanged at 71.6%/67.4% versus 71.6%/67.2% on LP/NC. Because the agent still chooses what to retrieve and when to stop, the results suggest that larger limits are insufficient under the existing search policy. Setup and results are detailed in Appendix C.3.

Agentic harness. We additionally develop a harnessed GraphSearch variant incorporating explicit planning, skill-based retrieval across four graph perspectives, evidence compaction, budget-aware stopping, and self-verification. Using the same backbone, graph retriever, and evaluation instances, the harness improves NC accuracy from 67.4% to 68.8%, matching Adaptive Routing. However, LP accuracy remains at 71.6%, below LLM Aggregation (80.0%) and Adaptive Routing (80.2%).

Trajectory analysis suggests that successive judgments within the harness are more correlated than those of independent specialists, potentially limiting the complementarity of retrieved evidence. The harness also incurs greater cumulative token consumption than LLM Aggregation (24.3K vs. 17.1K on LP; 13.7K vs. 12.1K on NC), illustrating the computational overhead of sequential context management.

We remain open to stronger single-agent harness designs in future work, but our findings show that the evaluated harness still faces challenges in reproducing the multi-agent gains. We have added the complete experimental setup, per-dataset results, failure analysis, and efficiency comparison to Appendix C.4.

W2: Disentangling learned selection from answer synthesis.

Our original claim concerns learned coordination, which includes specialist selection, stopping, and final answer synthesis (answer synthesis is modeled as a coordination operation, as defined in Sec. 3.3). We revised the wording in Finding 8 to avoid further confusion. Nevertheless, we agree that disentangling these components is important and conduct additional controlled experiments. We independently substitute the untrained or PPO-trained 7B router for selection/stopping and answer synthesis. The results reveal that answer synthesis accounts for much of the PPO improvement. Training synthesis alone improves LP/NC accuracy from 79.6%/68.4% to 86.9%/70.6%, whereas training selection/stopping alone yields 75.1%/68.5%. Combining both trained components further improves accuracy to 87.3%/72.4%, suggesting additional benefits from learned selection/stopping when paired with trained synthesis.

We also train a separate 7B LLM Aggregator with PPO over all four frozen specialist reports, providing a fixed-participation control without learned selection or stopping. The separately trained LLM Aggregator also achieves competitive accuracy (87.2%/71.2%), confirming that learned synthesis can produce gains without adaptive specialist selection. We have added the experimental details and component-level results to Appendix C.14.

W3,W5,Q2: Predefined specialization, dynamic delegation, and specialist pool scalability.

Our design of four predefined specialists is grounded in established findings from graph learning. Previous graph learning works, e.g., Mao et al. (ICLR 2024) [1], identify local structural proximity, global structural proximity, and feature proximity as complementary predictive factors. Recent agentic graph learning methods, such as AgentGL (ACL 2026), further demonstrate the effectiveness of agentic reasoning over these structural and semantic perspectives. Building on these works, we instantiate four dedicated graph specialists to enable complementary rather than redundant evidence exploration and reasoning, as classified in Sec. 3.2. Since their predictive utility varies across instances, we predefine specialist scopes while allowing their participation and coordination to adapt at inference time. We address the reviewer's concerns regarding this design from several aspects below:

Benefits of explicit specialization. Our ablation in Sec. 4.3 shows that, holding the number of agents, backbone, and coordination mechanism fixed, combining differentiated evidence with specialized roles improves LP/NC accuracy from 73.0%/66.0% to 80.0%/67.7%. This suggests that the benefits are not merely due to additional reasoning samples, but also depend on how graph evidence and specialist roles are organized.

Comparison with dynamic delegation. We agree that dynamically spawning subagents is an interesting alternative. We therefore implement a Qwen2.5-32B orchestrator that generates free-form task briefs for up to four subagents, each with the same four-search allowance as a GraphMAS specialist, and synthesizes their reports. This variant achieves 78.2%/67.3% (LP/NC), compared with 80.0%/68.6% for LLM Aggregation and 80.2%/68.8% for Adaptive Routing. Its subagents also retrieve substantially more overlapping evidence (average pairwise Jaccard similarity of 0.225/0.185 vs. 0.091/0.093 on LP/NC), suggesting that predefined specialization helps maintain complementary evidence coverage. This highlights a challenge of dynamic delegation that GraphMAS controls for through predefined specialization. The setup and results are detailed in Appendix C.9.

Scaling beyond four specialists. Given the coverage of the principal graph evidence perspectives discussed above, we expect that increasing the pool size would largely involve replicating existing perspectives or further subdividing their scopes, without necessarily introducing substantially new complementary information. Our design prioritizes evidence diversity over agent count, allowing us to focus on how complementary perspectives should be coordinated. We acknowledge that scaling the specialist pool is an interesting direction for future graph learning work, but careful specialist design would be needed to avoid redundancy and preserve evidence complementarity.

  • [1] Mao et al. Revisiting Link Prediction: A Data Perspective. ICLR, 2024.

Q3: MAS vs. harness for graph learning.

We view MAS as particularly promising because graph prediction is inherently complex. Evidence must be gathered through multiple rounds of interaction with the graph, spanning local, long-range, graph-wide, and semantic perspectives whose usefulness varies across instances. Within a single trajectory, earlier judgments can steer later exploration and accumulated evidence complicates context management, whereas MAS lets separate specialists gather complementary evidence and coordinate their predictions. Figure 1 shows the resulting headroom, as instances missed by the best specialist are often solved by another.

Our results further show that the value of MAS grows with task complexity. On LP, the wider performance gap between coordination methods under strong disagreement (19.3 vs. 4.4 points under unanimous agreement) highlights the potential of MAS on challenging instances (Figure 4). Similarly, single-agent method achieved its highest accuracy at low query degrees, where structural evidence is limited, but its performance gap with multi-agent methods widens as query degree increases (Appendix C.11). We therefore expect specialization and adaptive coordination to become increasingly important as graph prediction grows more complex.

We see MAS and agentic harnesses as complementary. A harness improves how an agent plans, manages evidence, and calls tools, while MAS determines how multiple reasoning processes explore and combine evidence. Stronger harnesses could improve individual specialists, and single agents may suffice for simpler instances. However, our harness experiment in W1 suggests that structured single-agent exploration alone does not necessarily resolve the complexity of integrating multiple graph perspectives within a shared trajectory. Therefore, adaptive hybrids that match their reasoning structure to instance complexity may be a promising direction.

Reviewer_qpWzOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces GraphMAS, a benchmark for studying multi-agent coordination in graph learning. It builds a shared pool of specialists using local, distant, global structural, and semantic graph perspectives. Coordination methods are organized by inter-agent interaction and runtime adaptivity, with seven methods instantiated across four paradigms. Experiments cover node classification and link prediction on seven text-attributed graphs. The paper also examines specialist design, disagreement, computational cost, and learning a routing policy over frozen specialists.

Critical strengths
  1. I appreciate the use of a shared specialist pool and common graph interfaces across coordination methods. This makes the comparisons easier to interpret than comparisons between complete systems with different evidence sources and backbones. The framework provides a useful basis for studying how coordination choices affect graph prediction.

  2. The analysis by specialist agreement helps identify the instances on which coordination choices matter most. Together with the computational cost measurements, it gives a useful picture of the benefits and costs of different strategies. This adds insight beyond identifying the highest-scoring method on each dataset.

Critical weaknesses

My main reservation concerns the interpretation of the advantage of adaptive selection over richer interaction. Alongside these coordination choices, the methods use different final decision rules: SOP returns the last specialist's answer, Debate uses plurality voting, and Adaptive Routing allows the router to synthesize a prediction. Prior work suggests that decision protocols can themselves materially affect multi-agent performance [1]. These differences make it harder to attribute the observed advantage specifically to selection or interaction, which limits the strength of the general design guidance drawn from an otherwise useful benchmark.

[1] Voting or Consensus? Decision-Making in Multi-Agent Debate. Findings of ACL, 2025.

Questions for authors

Could the authors clarify what drives the weaker performance of some interactive methods when specialists initially disagree? For example, do agents abandon correct predictions after seeing incorrect peer responses, or does the final decision rule overlook a correct prediction that remains available? Any evidence from the recorded trajectories would help explain when exchanging graph evidence is beneficial.

3 comments

We thank the reviewer for the thoughtful and constructive feedback. We appreciate the recognition of our contributions. We address each concern below.

W1: Final decision rules.

We agree that decision protocols can materially affect multi-agent performance. In GraphMAS, each method's final decision rule follows its original design, as summarized in Table 1. These rules are an integral part of each coordination paradigm, and Section 3.4 treats final decision-making as one of the dimensions along which the benchmarked methods differ. Replacing them would evaluate modified variants rather than the coordination methods as designed. For instance, Adaptive Routing stops once its router judges the collected evidence sufficient and then answers directly, consulting only 1.80 specialists per NC query on average. Imposing plurality voting would be ill-defined over one or two reports and would require consulting every specialist, removing the adaptive stopping that defines the method.

Comparing methods that share a decision rule further indicates that the observed differences stem mainly from coordination itself. Majority Vote and Debate both use plurality voting, yet Debate, which adds interaction, does not improve over Majority Vote on either task while costing more. LLM Aggregation and Adaptive Routing both use an LLM to produce the final prediction, yet Adaptive Routing, which selects specialists, matches LLM Aggregation's accuracy with fewer specialist calls. Since the decision rule is fixed within each pair, these differences reflect the coordination structure rather than how the final answer is chosen.

We understand that a systematic study across decision rules would further clarify their role in multi-agent coordination for graph learning, and we will note it as a direction for future research.

Q1: Failure modes of interactive methods under disagreement.

We conducted additional analysis concerning recorded trajectories on initially disagreeing instances. We find both failure modes raised by the reviewer, but answer abandonment, where a correct prediction is lost after interaction, occurs only in interactive methods, while decision miss, where a correct prediction remains available but the final decision is wrong, affects all methods. We detail the percentage of each failure mode where specialists initially disagree below:

InteractionMethodAbandoned (LP / NC)Decision miss (LP / NC)
IndependentLLM Aggregation0.0 / 0.030.5 / 30.5
IndependentAdaptive Routing0.0 / 0.029.2 / 24.0
InteractiveDebate15.2 / 19.525.2 / 12.6
InteractiveDyLAN10.3 / 10.428.7 / 18.3
InteractiveGraph of Agents15.5 / 14.812.9 / 11.3

The weaker performance is driven by answer abandonment rather than the final decision rule. Interactive methods overlook available correct predictions less often than independent ones, yet lose correct predictions on 10% to 20% of disagreeing instances, which independent methods never do. In Debate on LP, specialists adopt the peer plurality label almost as often when it is wrong (44.7%) as when it is right (49.5%), so final decisions flip from correct to incorrect 450 times relative to the initial plurality vote, against only 268 in the opposite direction.

These traces suggest that exchange is beneficial when it informs the final decision, but harmful when it leads specialists to revise their own predictions. Under disagreement, the second effect offsets the first, explaining why interaction can underperform independent aggregation. This analysis is now detailed in Appendix C.10.

We thank the reviewer again for the valuable suggestions that helped strengthen our work!

Thank you for the author's response. I have no further questions and will maintain the initial rating.

Thank you for reading our response. We appreciate your careful evaluation and are glad that our clarifications and additional results addressed your concerns.

Comments on the paper

1 comment

Dear AC, SAC, and PC,

Thank you for overseeing the review of GraphMAS. For your convenience, we briefly summarize our rebuttal below, and we hope this overview will help inform your final review.

1. The reviewers highlighted several strengths of GraphMAS.

  • A well-motivated benchmark for controlled comparisons of coordination strategies.

    • Wra5 called GraphMAS a “useful and well-motivated benchmark” and recognized the value of a fixed specialist pool for controlled benchmarking.
    • qpWz found the comparisons “easier to interpret than comparisons between complete systems with different evidence sources and backbones.”
  • Analyses that show when coordination matters and test where its gains come from.

    • Wra5 noted that the analyses “help explain where the gains come from.”
    • qpWz highlighted the analysis of “the instances on which coordination choices matter most.”
    • nCzJ described the additional reasoning-decomposition controls as “well-designed” and acknowledged that they “effectively eliminate the context-length confound.”
  • Cost analysis that makes coordination strategies easier to compare in practice.

    • qpWz highlighted the analysis of “the benefits and costs of different strategies.”
  • Evidence that learned coordination transfers to unseen graphs.

    • nCzJ highlighted “training a Router via PPO and validating its transferability to unseen graphs.”
    • Wra5 acknowledged in the follow-up that “the learned coordinator demonstrates transfer to held-out graphs.”

2. We clarified the benchmark’s contribution and strengthened the evidence for when, why, and at what cost MAS coordination improves graph prediction.

During the discussion, Reviewer qpWz confirmed that they had no further questions. Reviewer nCzJ acknowledged that the added controls addressed the context-length concern, and we received no further follow-up after our response on benchmark scope and graph topology. Across both rounds, our responses addressed the following points.

  • Graph prediction benefits both from matching each specialist’s role to its evidence and from letting specialists reason independently. First, holding each agent’s evidence fixed, assigning reasoning roles tailored to that evidence improved link prediction (LP) by 6.3 percentage points and node classification (NC) by 1.6. Second, we tested whether context length could explain the failure of single-agent methods. Compressing the single agent’s evidence to approximately the length seen by each specialist preserved its original accuracy, yet independent specialist reasoning still led by 5.8 points on LP and 2.3 on NC.

  • The most reliable specialist varies with local graph structure, and discussion can overturn a correct minority judgment. On true links, the proximal specialist performs best when the endpoints share a neighbor, while the distal specialist leads when they share none. On NC, the semantic specialist overtakes the proximal specialist on locally heterophilous nodes, where disagreement is also more frequent. Our trajectory analysis shows why preserving independent judgments matters under disagreement. Across the interactive methods studied, specialists abandoned an initially correct answer on roughly 10–20% of cases where they disagreed.

  • Adaptive Routing and other GraphMAS methods outperform all the single-agent and multi-agent variants raised by the reviewers. We tested GraphSearch with 4× the search and context limits, a single-agent harness prototype, and dynamic delegation. Noticeably, the harness incurred overhead from planning, context management, and answer verification within a single trajectory. With Qwen2.5-32B, Adaptive Routing beat the harness by 8.6 pp on LP with 22% fewer tokens and matched its NC accuracy with 20% fewer tokens. Similarly with Qwen3.5-9B, Adaptive Routing led the harness by 10.11 pp on LP and 1.97 pp on NC, with both paired 95% CIs above zero. On Qwen2.5-32B, it also significantly outperformed dynamic delegation on both tasks, since the delegated subagents retrieved substantially more overlapping evidence than the predefined specialists.

Additionally, to further validate our results, we added three-seeds, different backbone ablations, and 95% CIs data detailed in our rebuttal and revised manuscript. We hope this summary is helpful in preparing the meta-review. We thank the reviewers and chairs for their time and for the feedback that strengthened our work.

Best,

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.