Source-linked AI summary
Agent-as-a-Graph: Knowledge Graph-Based Tool and Agent Retrieval for LLM Multi-Agent Systems
Faheem Nizar, Elias Lumer, Anmol Gulati, Pradeep Honaganahalli Basavaraju, Vamse Kumar Subbiah
TL;DR
Existing agent, MCP, and retrieval methods often match queries to a single agent description, obscuring fine-grained tool capabilities. Agent-as-a-Graph jointly retrieves tool and agent nodes, reranks them with type-specific wRRF, and traverses to parent agents; on LiveMCPBenchmark, it improves Recall@5 and nDCG@5 over prior state-of-the-art retrievers.
Problem
Existing methods typically match queries against a single agent description, obscuring fine-grained tool capabilities and resulting in suboptimal agent selection.
Source: §1 · p. 1Method
Agent-as-a-Graph represents tools and parent agents as knowledge-graph nodes and edges, retrieves both through vector search, applies type-specific wRRF, then traverses to parent agents.
Source: §1 · pp. 1–2Results
14.9% and 14.6% improvements in Recall@5 and nDCG@5, respectively, over prior state-of-the-art retrievers; wRRF optimizations improve by 2.4%.
Source: §1 · p. 2Takeaways & Limitations
The knowledge graph jointly indexes tools and agents, and the authors report that it mitigates context dilution and improves multi-step routing without sacrificing fine-grained precision.
Source: §4.2.2 · p. 6
Abstract
from arXiv · showhide
Recent advances in Large Language Model Multi-Agent Systems enable scalable orchestration and retrieval of specialized, parallelized subagents, each equipped with hundreds or thousands of Model Context Protocol (MCP) servers and tools. However, existing agent, MCP, and retrieval methods typically match queries against a single agent description, obscuring fine-grained tool capabilities of each agent, resulting in suboptimal agent selection. We introduce Agent-as-a-Graph retrieval, a knowledge graph retrieval augmented generation approach that represents both tools and their parent agents as nodes and edges in a knowledge graph. During retrieval, i) relevant agents and tool nodes are first retrieved through vector search, ii) we apply a type-specific weighted reciprocal rank fusion (wRRF) for reranking tools and agents, and iii) parent agents are traversed in the knowledge graph for the final set of agents. We evaluate Agent-as-a-Graph on the LiveMCPBenchmark, achieving 14.9% and 14.6% improvements in Recall@5 and nDCG@5 over prior state-of-the-art retrievers, and 2.4% improvements in wRRF optimizations.
1 INTRODUCTION
Agent-as-a-Graph jointly retrieves tools and agents through a knowledge graph to address limitations of agent-only and tool-only retrieval. On LiveMCPBenchmark, it improves Recall@5 and nDCG@5 over prior state-of-the-art retrievers.
1 INTRODUCTION
- Large collections of specialized agents and MCP tools make identifying both the right agent and its specific tool increasingly challenging.A single assistant may delegate to subagents that bundle tens to hundreds of tools, while systems may expose hundreds or thousands of agent bundles and tool servers.Source: §1 · p. 1
- Agent-only retrieval can hide relevant tools, while tool-only retrieval ignores the complementary benefits of an agent bundle on multi-step tasks.Existing approaches commonly match queries against a single agent description, obscuring fine-grained tool capabilities.Source: §1 · p. 1
- Agent-as-a-Graph represents tools and their parent agents as nodes and edges in a knowledge graph for joint retrieval.Retrieval uses vector search for agent and tool nodes, type-specific wRRF to rerank them, and graph traversal to return parent agents.Source: §1 · pp. 1–2
- 14.9% and 14.6% improvements in Recall@5 and nDCG@5, respectively, over prior state-of-the-art retrievers; wRRF optimizations improve by 2.4%.The contribution summary reports the benchmark evaluation across eight embedding models and gives a 2.41% wRRF improvement.Source: §1 · p. 2
2 RELATED WORKS
Prior routing methods choose between agent-level and tool-level retrieval, while graph-based work has explored tool relations and graph-augmented reasoning. Agent-as-a-Graph combines graph structure with joint agent-tool retrieval and interpretable type-specific weighting.
2.1 Agent Routing and Tool Selection
- Agent-first retrieval can miss relevant tools, while tool-only retrieval ignores coherent agent bundles needed for multi-step tasks.Prior work often commits to one retrieval granularity per decision step; this paper instead treats agents and tools as co-equal graph nodes and traverses tool-to-agent edges at query time.Source: §2.1 · p. 2, §2.2 · p. 3
- A transparent, nonlearned weighted scoring approach combines dense similarity with type-specific priors to balance tool versus agent emphasis.The paper presents this as an efficient, controllable alternative to heavy LLM rerankers and corrective pipelines.Source: §2.1 · p. 3
2.2 Graph-Based Routing and Retrieval
- Related graph work covers tool graphs, graph search, prompt-level graph augmentation, and Graph RAG, but the cited task-planning and API-selection work does not evaluate tool retrieval through knowledge-graph RAG.The paper positions its approach against this related graph-based literature.Source: §2.2 · p. 3
- The paper distinguishes its approach by automatically inducing an agent-tool graph from MCP manifests and schemas, then combining traversal with type-specific weighted reciprocal rank fusion.The authors describe this combination as, to their knowledge, the first of its kind for agent and tool retrieval in multi-agent systems.Source: §2.2 · p. 3
3 METHOD
The method embeds tools and their parent agents in one vector space while linking them in a knowledge graph. This structure supports fine-grained tool retrieval while preserving agent context through graph traversal.
3 METHOD
- Agent-as-a-Graph embeds tools and parent agents in a unified vector space and links each tool to its parent through metadata edges.Its three components are knowledge graph construction and indexing, graph retrieval, and weighted reciprocal rank fusion for graph nodes.Source: §3 · p. 3
3.1 Knowledge Graph Construction and Indexing
The method models MCP agents and their tools as two node types in a bipartite knowledge graph joined by ownership edges. Tool and agent nodes offer fine-grained and higher-level retrieval targets, respectively.
3.1.1 Bipartite Knowledge Graph Modeling
- The system models agents and their tools as a bipartite knowledge graph, with edges representing tool ownership.Each agent owns a set of tools, including API calls, functions, or actions.Source: §3.1 · p. 3
3.1.2 Node Representation and Indexing
- Tool nodes index tool names and descriptions, with metadata edges linking each tool to its parent agent for query resolution.Traversal from a retrieved tool reaches the corresponding executable agent.Source: §3.1.2 · p. 4
- Agent nodes represent higher-level capabilities and aggregate their associated tools, providing coarser-grained retrieval targets when tool-level specificity is unnecessary.The graph can surface relevant tools while retaining agent-level execution context, including authentication, parameter inference, or access policies.Source: §3.1.2 · p. 4, §3.1.1 · p. 4
3.2 Agent-as-a-Graph Retrieval
Agent-as-a-Graph retrieves candidate nodes from a knowledge-graph catalog, then aggregates parent agents through ownership edges to select the top-K agents. Queries can be submitted directly or decomposed into steps; evaluation uses the step-wise approach.
3.2 Agent-as-a-Graph Retrieval
- Semantic similarity retrieves the top N nodes, then graph traversal aggregates their parent agents and selects the top-K unique agents.The target is the most relevant agents for a query or sub-query.Source: §3.2 · p. 4
3.2.1 Query Processing
- The input may be the original query, decomposed sub-steps, or a combination of both.Source: §3.2.1 · p. 4
- Step-wise Querying submits each decomposed sub-task independently and is the primary setting used in evaluation.Direct Querying instead retrieves agents or tools from the high-level question without preprocessing.Source: §3.2.1 · p. 4
3.3 Weighted Reciprocal Rank Fusion for Knowledge Graph Nodes
The method fuses retrieved agent and tool nodes with type-specific weights, then reranks candidates while preserving distinctions between node types. The weighting balances agent coverage and tool specificity, with reported gains in benchmark retrieval metrics.
3.3 Weighted Reciprocal Rank Fusion for Knowledge Graph Nodes
- Modest emphasis on agent nodes improves top-K routing stability while retaining sensitivity to specific tool nodes.The weights apply to distinct node types retrieved from the knowledge graph.Source: §3.3 · pp. 4–5
3.3.1 Standard Reciprocal Rank Fusion
- Standard RRF sums reciprocal ranks with a constant k, and its weighted generalization assigns a separate weight to each retrieval method.Here, retrieval methods correspond to elements retrieved from tool and agent catalogs.Source: §3.3.1 · p. 5
3.3.2 Type-Specific Weighted RRF
- The method merges agent and tool candidates, assigns each a global base rank, applies type-specific weights, and reranks by the resulting score.Ties are broken by smaller base rank; decoupling scoring avoids blending calibration from distinct retrievers.Source: §3.3.2 · p. 5
- Type-specific weighting improves Recall@K and nDCG@K, particularly on mixed-intent workloads involving agent orchestration and tool specificity.The passage describes interpretability, stable within-type rankings, and flexibility to shift the balance between agent coverage and tool specificity.Source: §3.3.2 · p. 5
4 Evaluations
The evaluation tests retrieval accuracy on LiveMCPBench across baseline comparisons, embedding models, and type-weighted ranking. Its setup uses step-wise queries and measures retrieved agents against ground-truth agents.
4 Evaluations
- The evaluation covers baseline comparison, cross-architecture generalization, and type-weighted ranking.The authors report that the approach improves retrieval accuracy, generalizes across embedding architectures, and benefits from type-specific weighting.Source: §4 · p. 5
4.1 Experimental Setup
- LiveMCPBench contains 70 MCP servers, 527 tools, and 95 real-world questions annotated with step-by-step breakdowns and relevant agent-tool mappings.Questions average 2.68 steps, 2.82 tools, and 1.40 MCP agents; an agent-only dataset contains only server names and descriptions.Source: §4.1 · p. 5
- Table 3 compares weighted RRF approaches across type-specific weight ratios using OpenAI text-embedding-ada-002.The caption reports that Equation 3 outperforms standard weighted RRF at balanced configurations.Source: Table 3 · p. 6
- The setup compares against BM25, standard RRF, MCPZero, and ScaleMCP, and evaluates eight embedding models.Embedding models span Vertex AI, Amazon Titan, OpenAI, and All-MiniLM-L6-v2.Source: §4.1 · pp. 5–6
- Retrieval accuracy is measured with Recall@K, mAP@K, and nDCG@K at K = 1, 3, and 5, against ground-truth agents.Step-wise querying submits each step independently; retrieval first searches the top N nodes and then selects top-K unique agents through graph traversal.Source: §4.1 · p. 6
4.2 Baseline Comparison Experiments
On LiveMCPBench, Agent-as-a-Graph outperforms the listed baselines across Recall@K, mAP@K, and nDCG@K. The discussion attributes the gains primarily to jointly indexing tools and agents while preserving agent context through graph traversal.
4.2.1 Results
- Recall@5 is 0.83 for Agent-as-a-Graph versus 0.79 for RRF, a 5.1% improvement; the approach consistently outperforms baselines across all reported metrics.The comparison uses the unified agent-and-tool corpus without type-specific weighting.Source: §4.2.1 · p. 6, §4.2 · p. 6
- nDCG@5 is 0.46 for Agent-as-a-Graph, compared with 0.44 for RRF and 0.41 for MCPZero.The retrieved top-K includes agent nodes as well as tool nodes whose parent agents are reached through graph edges.Source: §4.2.1 · p. 6
4.2.2 Discussion
- The authors attribute the gains primarily to jointly indexing tools and agents as co-equal nodes, enabling fine-grained semantic alignment while preserving agent context through traversal.They report that over 39% of retrieved items come from agent nodes, so tool-level retrieval alone does not account for the performance lift.Source: §4.2.2 · p. 6
4.3 Cross-Architecture Generalization Experiments
Across eight embedding models, Agent-as-a-Graph improves retrieval metrics over MCPZero with low variance across encoder families. The weighting analysis also favors modest agent emphasis, and the reported robustness matters where embedding choice is constrained by cost, latency, or licensing.
4.3.1 Results
- Agent-as-a-Graph improves consistently across encoder families, with variance of approximately 0.02 in Recall@5 and 0.01 in nDCG@5.The strongest reported Recall@5 improvement is 28.8% with Amazon Titan v2; All-MiniLM-L6-v2 improves by 19.4%.Source: §4.3.1 · pp. 6–7
- Average Recall@5 rises from 0.70 with MCPZero to 0.85 with Agent-as-a-Graph, a 19.4% improvement, across the evaluated embedding models.Average nDCG@5 rises from 0.41 to 0.48, a 17.7% improvement; average mAP@5 rises from 0.31 to 0.36.Source: §4.3.1 · pp. 6–7
4.3.2 Discussion
- The authors report that low variance suggests gains stem primarily from graph structure, and note robustness for deployments constrained by embedding cost, latency, or licensing.They also report substantial improvement with the compact All-MiniLM-L6-v2 model.Source: §4.3.2 · p. 7, §4.3.1 · p. 7
- The optimal type-specific configuration, αA = 1.5 and αT = 1.0, achieves Recall@5 of 0.85 and nDCG@5 of 0.47, ahead of both reported baselines.The unweighted baseline has Recall@5 of 0.83 and nDCG@5 of 0.46; standard weighted RRF has 0.79 and 0.44, respectively.Source: §4.3.2 · p. 7
4.4 Type-Weighted Ranking Experiments
The experiments compare standard weighted RRF with type-conditioned weighting across agent-to-tool weight ratios. Modest agent emphasis performs best in the reported sweep, while the type-conditioned scoring keeps node-type weights interpretable and tunable.
4.4.1 Results
- At 3:1 agent bias, Recall@5 falls to 0.76, while tool-dominant 1:3 weighting reaches 0.80; the performance curve peaks at modest agent emphasis of 1.5:1.The experiments fix k = 60 and use OpenAI text-embedding-ada-002 to retrieve initial top-K entities.Source: §4.4.1 · pp. 7–8, §4.4 · p. 7
- The authors describe type-specific weights as transparent knobs for balancing agent coverage against tool specificity, with the optimum favoring agents modestly.They frame query-adaptive type weights and structure-aware graph priors as directions for future research.Source: §4.4.1 · pp. 7–8
4.4.2 Discussion
- Type-conditioned weights outperform standard weighted RRF by decoupling node types at scoring time while preserving within-type ordering through the shared denominator k + r(e).The weights provide interpretable controls over retrieval granularity without learned reranking.Source: §4.4.2 · p. 8
- The authors argue that exposed αA and αT weights can be adjusted to domain characteristics or query intent without retraining.The discussion identifies interpretability and control as priorities for production systems.Source: §4.4.2 · p. 8
5 CONCLUSION
The conclusion presents Agent-as-a-Graph as a knowledge-graph framework for routing in large multi-agent systems. Across eight embedding models on LiveMCPBench, it reports improvements over prior state-of-the-art retrievers and meaningful retrieval contributions from both agent and tool nodes.
5 CONCLUSION
- On LiveMCPBench, Agent-as-a-Graph achieves Recall@5 of 0.85 and nDCG@5 of 0.48 with optimal type-specific weighting, improving over prior state-of-the-art retrievers by 14.9% and 14.6%.The evaluation spans eight embedding models.Source: §5 · p. 8
- The framework represents tools and agents as co-equal knowledge-graph nodes linked by explicit metadata edges, then retrieves through graph traversal and type-specific weighted reciprocal rank fusion.The conclusion reports that 39.13% of retrieved items originate from agent nodes and 34.44% trace from tool nodes through graph edges.Source: §5 · p. 8
- The authors frame routing to the correct agent as a fundamental challenge as systems grow to hundreds of agents and thousands of tools and MCP servers.The conclusion identifies both agent-node and tool-node retrieval as meaningful contributors to routing performance.Source: §5 · p. 8