FED-GRAPH-MCP: Scaling LLM Tool Discovery via Sparsified Functional Graphs and Incremental Synchronization

Abstract

As the Model Context Protocol (MCP) ecosystem scales past 10,000 servers, LLM agents face a severe tool-discovery bottleneck. Existing dense retrieval methods treat tools as isolated documents, ignoring functional interdependencies and real-time registry volatility. To address this, we present FED-GRAPH-MCP (Functionally-Enriched Dynamic Graph for MCP Tool Discovery), a hybrid retrieval architecture with three key components: (1) a multi-typed functional tool graph capturing relational dependencies; (2) a dual-branch pipeline that fuses Relational GCN (R-GCN) structural embeddings with dense semantic embeddings via a learned reranker; and (3) a CRUD-triggered incremental synchronization daemon. Evaluated on LiveMCPBench and MCP-Bench task distributions, FED-GRAPH-MCP bypasses memory and processing overheads where traditional baselines saturate. Our systems evaluation demonstrates that graph sparsification reduces the in-memory structural footprint by 95.6%, eliminating runtime out-of-memory errors and representation collapse. Additionally, graph expansion yields a 4.7-5.6% token reduction per task, and the incremental sync daemon decreases index update latency by 96.5-99.9% compared to full recomputation.