Cartograph: A Federated Proxy Approach to Reimagining Tool Discovery for AI Agents

When the tool catalogs connected to AI agents grow increasingly large, a hidden cost problem emerges: to let an agent "know" which tools are available, systems often need to inject all tool definitions into the context at once. This is inconsequential at small scale, but as catalogs balloon from dozens of tools to hundreds or even thousands, both token overhead and retrieval accuracy deteriorate sharply. A paper recently published on arXiv introduces Cartograph — a federated proxy approach for the Model Context Protocol (MCP) that aims to fundamentally transform this discovery mechanism.

From O(n) Full Traversal to O(k) Progressive Disclosure

The core value of MCP lies in enabling AI agents to discover and invoke external tools. But as the paper notes, as connected tool catalogs grow, "loading every tool definition" becomes increasingly expensive. The traditional approach is essentially an $O(n)$ full-catalog traversal — agents must face the complete tool listing every time.

Cartograph's central idea is to reduce this to $O(k)$ progressive disclosure. In a deployment environment with 22 servers and 374 tools, Cartograph exposes only 3 proxy tools to the agent — not 374 complete definitions. This means agents no longer need to bear an enormous context burden at startup; instead, they progressively retrieve the tool information they need on demand.

The difference in token consumption is striking: a single top-5 discovery interaction measured in the paper uses just 475 tokens, whereas the same operation under a full-catalog accounting approach requires approximately 42,450 tokens. A nearly hundredfold gap — precisely the critical bottleneck in large-scale tool ecosystems.

Model Context Protocol (MCP) is an open protocol standard proposed by Anthropic in late 2024, designed to unify the interface specifications between AI agents and external tools and data sources. Its core concept is analogous to a programming language's "package manager" — tool publishers describe their capabilities in a standardized format, and agents dynamically discover and invoke these tools through the protocol without writing custom adapter code for each one. MCP's adoption has enabled rapid expansion of the "tool ecosystem," but it also introduces the scaling challenge discussed in this paper: when the number of tools in the ecosystem grows explosively, the protocol itself provides no guidance on how to efficiently filter a subset of tools, and the default behavior still injects all tool definitions into the context.

Three Core Mechanisms: Signed Credentials, Confusion Analysis, and Two-Stage Retrieval

Cartograph's implementation rests on three mutually reinforcing mechanisms, each targeting a specific pain point in tool discovery.

Operator-Attested Capability Cards

The first mechanism is "operator-attested capability cards." These cards use Ed25519 signatures and are generated by deployment operators under their own control, rather than relying directly on official descriptions from tool publishers that may have been "optimized for ranking." The intent of this design is clear: keeping the trustworthiness and provenance of tool descriptions in the hands of the deploying operator, avoiding distorted retrieval rankings caused by publishers' marketing-driven copy.

Ed25519 is a digital signature algorithm based on elliptic curve Diffie-Hellman (an Edwards curve variant), known for its high performance, short keys, and strong security. It is widely used in SSH, TLS, and blockchain contexts. In Cartograph, operators use their own Ed25519 private keys to sign the contents of capability cards; any verifier holding the corresponding public key can confirm the card hasn't been tampered with and genuinely originates from that operator. This mechanism addresses the trust question of "who defines tool descriptions": tool publishers have incentives to exaggerate or optimize their descriptions to increase invocation probability (analogous to SEO), while operator attestation binds description authority to ultimate usage responsibility, forming a more reliable provenance chain.

Rift: Three-Layer Confusion Cluster Analysis

The second mechanism, named Rift, is a three-layer "confusability clustering" analysis consisting of density clustering, query-margin analysis, and token diagnostics. Its role is to identify tool descriptions that agents are likely to confuse with one another. In experiments, Rift identified 49 confusable clusters, including 4 "high-risk" clusters present in auto-generated cards. This type of analysis is critical for ensuring retrieval accuracy — when multiple tool descriptions are too semantically close together in vector space, agents are highly prone to invoking the wrong tool.

Density clustering (such as the DBSCAN algorithm) is an unsupervised learning method that automatically identifies "high-density regions" based on the distribution of samples in vector space, without presetting the number of clusters. In the context of tool descriptions, each tool's text description is embedded as a high-dimensional vector, and density clustering can find collections of tools that are highly semantically similar to each other — precisely the sources of confusion that cause agents to "misidentify" tools. Query-margin analysis further examines this: when a query simultaneously activates multiple tools within the same cluster, the smaller the gap (margin) between ranking scores, the higher the confusion risk. Token diagnostics supplements this at the lexical level, identifying keyword patterns in descriptions that lead to semantic overlap. The three layers working together can systematically locate weak points in retrieval accuracy.

Two-Stage Retrieval

The third mechanism is two-stage retrieval: first ranking servers, then ranking specific tools. This "coarse-then-fine" hierarchical retrieval approach is fully consistent with the overall progressive disclosure design, enabling reduction of the candidate set while maintaining recall quality.

Experimental Results: Dual Validation of Recall and Latency

The paper evaluates using a 49-query benchmark constructed by the authors. Results show Cartograph achieves R@5 of 0.816, while the Jaccard keyword-matching baseline reaches only 0.592. This improvement demonstrates that semantic two-stage retrieval significantly outperforms traditional keyword matching.

On latency, the authors measured gateway overhead across ten trials, finding that compared to direct stdio MCP calls, the average increase is only 5ms (approximately 0.8%). In other words, Cartograph dramatically reduces token costs and improves retrieval accuracy while introducing virtually no perceptible performance penalty.

Also noteworthy is an exploratory comparison in the paper: the authors experimented with 119 LLM-generated descriptions and found this eliminated the observed "zero-distance clusters" (i.e., completely overlapping, highly confusable descriptions), but also revealed a cautionary finding — mixing different card generation mechanisms can actually reduce R@5. This reminds practitioners that consistency in description generation is itself a variable affecting retrieval quality.

R@5 (Recall at 5) is a standard evaluation metric in information retrieval, measuring what proportion of the top 5 returned results contain the genuinely relevant tool (i.e., the tool that should actually be invoked). R@5 = 0.816 means that across the 49 test queries, the correct tool appeared in the top 5 candidates approximately 81.6% of the time. Jaccard keyword matching is a classic set similarity method that calculates the ratio of shared vocabulary between two texts to their combined vocabulary. Simple to implement, it is completely insensitive to synonyms, near-synonyms, word order variations, and other semantic relationships — which explains its significantly weaker performance of 0.592 in tool catalogs with diverse natural language descriptions.

Positioning: Complementary to Code-Execution Approaches

The paper explicitly emphasizes that Cartograph is complementary to — not a replacement for — "code execution" type approaches. Its responsibility is to control which tool descriptions are exposed to agents and to record the description provenance used for ranking each query. In other words, Cartograph focuses on the "discovery" and "trusted provenance" layer, while the actual execution of tool invocations can still be handled by other mechanisms.

From an engineering perspective, this positioning is quite pragmatic. As the MCP ecosystem and multi-tool agents proliferate, the scalability, trustworthiness, and cost control of tool discovery are becoming inescapable practical concerns. The federated proxy architecture proposed by Cartograph offers a technical path that balances efficiency, accuracy, and secure provenance tracking.

Summary

Cartograph's value lies not only in reducing token overhead from tens of thousands to hundreds, but also in incorporating the governance question of "where tool descriptions come from and whether they can be trusted" into the retrieval design itself. The combination of signed credentials, confusion cluster analysis, and two-stage retrieval forms a scalable, auditable tool discovery framework. For teams building large-scale agent systems, this research offers architectural ideas worth borrowing — though its benchmarks are still author-constructed and limited in scale, and real-world performance will require broader validation.