Source-linked AI summary
Graph-of-Agents: A Graph-based Framework for Multi-Agent LLM Collaboration
Sukwon Yun, Jie Peng, Pingzhi Li, Wendong Fan, Jie Chen, James Zou, Guohao Li, Tianlong Chen
TL;DR
Multi-agent LLM systems struggle to select relevant agents, communicate effectively, and integrate responses efficiently as model pools grow. GoA addresses these challenges with graph-based agent selection, relevance-driven bidirectional message passing, and graph pooling. Across diverse benchmarks, it outperforms recent multi-agent baselines while using only 3 selected agents instead of 6, although its outputs retain the biases and misuse risks of the underlying LLMs.
Problem
Multi-agent LLM systems lack effective mechanisms for selecting relevant agents, facilitating fine-grained communication, and integrating unequal-quality responses efficiently.
Method
GoA selects agents using model-card metadata, builds relevance-weighted directed edges, performs bidirectional message passing, and aggregates refined responses with graph pooling.
Results
Using only 3 agents, GoA outperforms recent multi-agent baselines that rely on pools of 6 agents across diverse benchmarks.
Takeaways & Limitations
Graph-based collaboration provides a scalable and effective framework for coordinating multi-agent LLMs across diverse tasks.
Takeaways & Limitations
GoA outputs may retain inherent biases and undesirable traits from the underlying LLMs, carrying similar misuse risks to other test-time methods.
Abstract
from arXiv · showhide
With an ever-growing zoo of LLMs and benchmarks, the need to orchestrate multiple models for improved task performance has never been more pressing. While frameworks like Mixture-of-Agents (MoA) attempt to coordinate LLMs, they often fall short in terms of (1) selecting relevant agents, (2) facilitating effective intra-agent communication, and (3) integrating responses efficiently. In this work, we propose Graph-of-Agents (GoA), a new graph-based framework for modeling multi-agent LLM communication. Our approach begins with node sampling, selecting only the most relevant agents by leveraging model cards that summarize each model's domain, task specialization, and other characteristics. Next, we construct edges between the selected agents by evaluating their responses against one another to determine relevance ordering. Directed message passing is then performed from highly relevant agents to less relevant ones to enhance their responses, followed by reverse message passing to refine the original responses of the more relevant agents. Finally, the updated responses are aggregated via graph-based pooling (e.g., max or mean pooling) to produce a single, unified answer. We evaluate GoA on diverse multi-domain benchmarks (MMLU, MMLU-Pro, GPQA) and domain-specific benchmarks (MATH, HumanEval, MedMCQA), with an agent pool of 6 LLMs spanning multiple domains. Surprisingly, GoA achieves superior performance using only 3 selected agents, outperforming recent multi-agent LLM baselines that utilize all 6 agents simultaneously. By adopting a graph structure, GoA offers both scalability and effectiveness through structured message passing-positioning it as a strong candidate for navigating the challenges of the ever-growing LLM zoo. Code is available at: https://github.com/UNITES-Lab/GoA.
1 INTRODUCTION
The paper identifies agent selection, communication, and response integration as central challenges in multi-agent LLM systems, then introduces Graph-of-Agents (GoA) to address them through a structured graph. GoA selects relevant agents, passes messages according to relevance, and pools refined responses; experiments report stronger performance with fewer agents than competing approaches.
- MoA forwards queries to all available agents, causing excessive computation and noise from irrelevant agents.
- MoA aggregates agent responses as a single chunk, limiting fine-grained pairwise interaction and adaptive relevance weighting.
- GoA models agents as nodes and relevance-based relationships as edges, selectively activating a subgraph and using structured message passing and graph pooling.
- GoA selects relevant agents from model-card metadata through a general-domain meta-LLM given the query.
- GoA passes information from highly relevant agents to less relevant agents, then sends refined information back to update the higher-ranked agents.
- GoA uses max or mean graph pooling to aggregate refined outputs and is evaluated across multi-domain and domain-specific benchmarks.
- Multi-agent LLM systems must select relevant agents, support effective communication, and integrate responses efficiently.
- Using only 3 agents, GoA outperforms recent multi-agent baselines that use pools of 6 agents across reported benchmarks.
2 RELATED WORK
Related work covers test-time reasoning methods that structure a single LLM’s problem solving and ensemble approaches that aggregate or selectively query multiple models. GoA is presented as a graph-based approach to multi-agent communication, illustrated through a pipeline that selects agents, constructs relevance-based connections, passes messages, and pools outputs.
- Prior test-time reasoning methods use prompting structures such as chains, trees, and graphs to decompose complex problems into sub-tasks.
- Ensemble-based inference aggregates or selects outputs from several models, while router mechanisms selectively query subsets to reduce computational cost.
- GoA frames multi-agent communication as a graph pipeline that selects relevant agents, evaluates their responses, passes messages, and pools outputs.
3 METHODOLOGY
GoA models multi-agent collaboration as a directed graph that selects relevant agents, structures their communication, and pools refined responses. It uses relevance-based edges, bidirectional message passing, and graph pooling to support scalable multi-agent inference.
- Overview: GoA represents LLM agents as graph nodes and relevance-based relationships as directed edges, enabling structured message passing and selective activation.The framework treats the selected agents as a subgraph of the full agent pool.
- Node Sampling: A meta-LLM selects task-relevant agents from model-card metadata describing domains, specialized tasks, model size, and features.Top-k selection filters unnecessary agents while preserving those aligned with the query.
- Edge Sampling: Selected agents score one another’s responses, and aggregate relevance scores rank agents while thresholding prunes weak or noisy responders.The resulting weighted adjacency matrix assigns greater influence to more relevant neighbors and supports fine-grained one-to-one communication.
- Message Passing: Source-to-target message passing lets lower-ranked agents refine responses using stronger agents’ outputs, followed by target-to-source refinement using improved neighbors.This two-step procedure preserves influential agents’ initial strength while enabling collaborative response refinement.
- Graph Pooling: GoA integrates refined responses through max-pooling or weighted mean-pooling, with max-pooling prioritizing the most relevant agent and mean-pooling incorporating all selected agents.The two variants are named GoAmax and GoAmean; mean-pooling requires an additional Meta-LLM forward pass.
- Evaluation: Table 1 evaluates GoA against single-agent and six-agent multi-agent baselines across multi-domain and domain-specific benchmarks, using only three selected agents.The evaluation covers MMLU, MMLU-Pro, GPQA, MATH, HumanEval, and MedMCQA.
4 EXPERIMENTS
Experiments evaluate GoA across multi-domain and domain-specific benchmarks, showing strong performance and efficiency from selective, graph-structured collaboration. Ablations further identify bidirectional message passing, relevance weighting, and suitable graph size and sparsity as important design choices.
- Experimental Setup: GoA is evaluated on multi-domain and domain-specific benchmarks, including MMLU, MMLU-Pro, GPQA, MATH, HumanEval, and MedMCQA.The study also compares single-agent baselines, six-agent multi-agent baselines, and GoA using three agents.
- Main Results: GoAMax achieves the highest average score, with top results on MMLU (79.18), MMLU-Pro (54.78), and MedMCQA (60.04).GoAMean performs best on GPQA, MATH, and HumanEval.
- Main Results: GoAMean records the best scores on GPQA (40.54), MATH (73.12), and HumanEval (84.98), demonstrating gains across reasoning and domain-specific tasks.GoA achieves these results using three agents, whereas other multi-agent methods use six.
- Efficiency: GoA reduces LLM usage and latency while improving MMLU-Pro accuracy compared with MoA.Node and edge sampling followed by graph pooling selectively involves relevant agents.
- Graph-based Reasoning: In an anatomy-domain case study, GoA avoids irrelevant agents and produces more accurate discussions and final predictions than MoA.MoA uses agents from unrelated domains, whereas GoA constructs a query-specific graph through node and edge sampling.
- Ablation Study: Reversing message-passing direction causes drops of 2.60 on MMLU-Pro and 5.05 on GPQA, the largest ablation losses.Removing Source-to-Target causes drops of 2.57 and 3.86, while removing Target-to-Source causes drops of 1.12 and 1.95, respectively.
- Ablation Study: Disabling edge scoring reduces performance, while k = 3 and τ = 0.05 provide a strong balance between diversity, focus, and connectivity.k = 2 limits diversity, k = 5 slightly degrades performance, and overly sparse graphs with τ = 0.1 or 0.2 harm performance.
5 CONCLUSION
The paper concludes that GoA redesigns multi-agent communication around graph-based selection, interaction, and integration. Experiments demonstrate consistent gains across diverse benchmarks.
- 5 CONCLUSION: GoA addresses agent selection, inter-agent communication, and response integration through a graph-based framework.The authors present these mechanisms as a redesign of multi-agent communication.
- 5 CONCLUSION: Experiments demonstrate consistent gains across diverse benchmarks.The conclusion presents GoA as a potential advance for large-scale collective intelligence in multi-agent LLMs.
ETHICS STATEMENT
The ethics statement notes that GoA inherits biases and undesirable traits from the underlying pretrained LLMs. Its outputs therefore carry misuse risks similar to other test-time methods.
- ETHICS STATEMENT: GoA may inherit inherent biases and undesirable traits from the pretrained LLMs it uses.The statement identifies this as a limitation of the framework's outputs.
- ETHICS STATEMENT: GoA outputs carry similar misuse risks to those of other test-time methods.The risk follows from the inherited properties of the underlying LLMs.
REPRODUCIBILITY STATEMENT
The reproducibility statement provides the GoA code and reports the experimental hardware and dataset availability. The code is publicly linked, experiments used A6000 GPUs, and datasets are publicly available.
- REPRODUCIBILITY STATEMENT: The authors provide GoA code through a public GitHub link.The repository is identified as https://github.com/UNITES-Lab/GoA.
- REPRODUCIBILITY STATEMENT: All experiments were conducted on A6000 GPUs, and the datasets used are publicly available.These details describe the reported experimental environment and data accessibility.
A THE USE OF LARGE LANGUAGE MODELS (LLMS)
ChatGPT2 was used only for grammar checking and text refinement. It polished author-written text without contributing research ideas.
- ChatGPT2 was used exclusively for grammar checking.
- Its role included refining author-written text.
- ChatGPT2 did not contribute research ideation.
B PROMPTS
The prompts define GoA’s test-time inference stages, including structured response generation, model-card-based node sampling, and relevance-oriented model selection.
- GoA operates during test-time inference with detailed prompts for each pipeline stage.
- Model Card Extraction: Model cards summarize characteristics such as domain, task specialization, and application area without including benchmark results.
- Initial Response Generation: Initial responses contain brief reasoning, an answer, and a confidence level in structured JSON.
- Initial Response Generation: Confidence levels filter models with limited ability to produce the required answer format.
- Node Sampling: Node sampling selects the top-k models using model descriptions and question suitability.
- Node Sampling: Selection prioritizes domain match and task specialization, while optionally including a generalist and favoring larger models only for significant size gaps.
• Edge Sampling:
GoA builds relevance-aware communication among selected models through bidirectional message passing, then scores and synthesizes their responses into one answer.
- Graph-Pooling: The pooling stage assigns response scores based on correctness, coherence, and relevance, with scores summing to exactly 1.0.
- Message-Passing (1) Source-to-Target: Source-to-target message passing lets target models refine answers using responses from source models.
- Message-Passing (1) Source-to-Target: Normalized edge scores label source responses as high, moderate, or low relevance using thresholds above 0.7, between 0.4 and 0.7, or at most 0.4.
- Prompts instruct models to integrate useful insights critically because other responses may be incorrect.
- Message-Passing (2) Target-to-Source: Target-to-source message passing lets source models finalize responses after seeing refined target answers.
- Graph-Pooling: Graph pooling uses a meta-LLM to synthesize refined model responses into one final answer.