Graph-of-Agents: A Graph-based Framework for Multi-Agent LLM Collaboration¶

🕒 Published (v1): 2026-01-01 · Source: ICLR · Venue: ICLR 2026 · link

Why this paper was selected

Graph-based framework outperforms Mixture-of-Agents for multi-LLM collaboration

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

Graph-of-Agents (GoA) is a test-time multi-agent LLM framework that models agent collaboration as a directed graph, enabling selective agent activation, relevance-weighted message passing, and graph-pooling-based response integration. Using only 3 agents from a pool of 6, GoA outperforms all multi-agent baselines that use all 6 agents simultaneously. GoA is proven to strictly generalize Mixture-of-Agents (MoA) as a special case.

Problem¶

Existing multi-agent LLM frameworks like MoA suffer three compounding failures: (1) no mechanism to select relevant agents from a large pool, so all agents are queried regardless of domain fit, introducing noise and \(O(LNd)\) token cost; (2) many-to-one aggregation that treats all agent outputs equally, ignoring per-query relevance; and (3) response integration via full token concatenation, which is prohibitively expensive at scale and does not weight responses by quality.

Method¶

GoA models the agent pool as a directed graph \(\mathcal{G} = (\mathcal{V}, \mathcal{E})\) and proceeds in four stages:

Node Sampling: A meta-LLM (Qwen2.5-7B-Instruct) reads model cards (domain, task specialization, size) and selects top-\(k\) relevant agents: \(V_s = \text{Meta-LLM}(\text{Top-}k \mid Q, \text{Model Cards})\).
Edge Sampling: Each selected agent scores all others' initial responses, producing a normalized score matrix. Per-agent relevance is \(S_j = \sum_{i \neq j} \text{Score}_{i \to j}\). Agents with \(S_j < \tau\) (\(\tau = 0.05\)) are pruned. A weighted directed adjacency matrix \(A_{ji} = S_i / \sum_{k \in \mathcal{N}_j} S_k\) encodes influence proportional to relevance.
Bidirectional Message Passing: First, source-to-target: higher-ranked (source) agents propagate to lower-ranked (target) agents, which refine their responses. Then target-to-source: source agents incorporate the now-improved target responses for a second refinement pass.
Graph Pooling: Two variants — GoA\(_{\text{Max}}\) selects the refined response of the agent with the most incoming edges; GoA\(_{\text{Mean}}\) has the meta-LLM average across all refined responses weighted by relevance scores.

MoA is recovered as a special case when \(k = N\), \(A = \mathbf{1}^{N \times N}\), and mean pooling is applied (Proposition 1).

Key Contributions¶

Formal identification of three structural failures in MoA: agent selection, communication granularity, and integration cost.
GoA framework: graph-theoretic formalization of multi-agent LLM collaboration with node sampling, directed edge construction, bidirectional message passing, and graph pooling.
Proof that GoA strictly generalizes MoA.
Empirical demonstration that \(k=3\) GoA outperforms 6-agent baselines across 6 benchmarks spanning multi-domain and domain-specific tasks, with no model fine-tuning (prompt-only, black-box compatible).

Results¶

All results zero-shot CoT, agent pool = 6 LLMs (7–8B params); GoA uses only top-3.

MMLU: GoA\(_{\text{Max}}\) 79.18 vs. best baseline Self-MoA 78.14 (+1.04)
MMLU-Pro: GoA\(_{\text{Max}}\) 54.78 vs. Self-MoA 54.19 (+0.59)
GPQA: GoA\(_{\text{Mean}}\) 40.54 vs. Refine 38.92 (+1.62)
MATH: GoA\(_{\text{Mean}}\) 73.12 vs. Refine 71.60 (+1.52)
HumanEval: GoA\(_{\text{Mean}}\) 84.98 vs. SC 82.57 (+2.41)
MedMCQA: GoA\(_{\text{Max}}\) 60.04 vs. SC 55.70 (+4.34)
GoA\(_{\text{Max}}\) achieves highest average over all benchmarks; GoA\(_{\text{Mean}}\) leads on reasoning-heavy tasks (GPQA, MATH, HumanEval).

Limitations¶

Experiments confined to 7–8B parameter open-source models; behavior with proprietary or much larger models is unexamined.
MMLU and MMLU-Pro are evaluated on stratified subsamples (50 and 150 per category) rather than full datasets, potentially affecting result reliability.
The meta-LLM (Qwen2.5-7B) is used both for node sampling and mean pooling aggregation, coupling the framework's quality to a single general-domain small model.
Threshold \(\tau\) and top-\(k\) are hyperparameters requiring tuning; sensitivity analysis scope is not detailed in the excerpt.
All evaluations are single-layer (one round of message passing); multi-layer GoA behavior is not characterized.
Model card quality from Hugging Face README files is inconsistent, potentially degrading node sampling accuracy.

Relevance to Agentic AI / LLM Agents¶

GoA directly addresses a core challenge in multi-agent orchestration: how to compose heterogeneous specialist LLMs at inference time without fine-tuning or access to model internals. By formalizing agent selection and communication as a graph problem, it provides a principled alternative to flat ensemble or chain-based architectures (MoA, Debate, ReConcile) that dominate the current multi-agent literature. The bidirectional message-passing mechanism is a concrete protocol for structured inter-agent influence, relevant to anyone designing agentic pipelines where role differentiation and information routing matter. The result that 3 well-chosen, well-connected agents beat 6 naively combined agents has direct practical implications for cost-efficient agentic system design.