AI Tool Discovery at Scale: All You Need is DNS
06:00 · July 22, 2026 · arXiv cs.AI RSS
The coming era of autonomous AI agents demands a discovery mechanism capable of navigating millions of tools, yet existing solutions buckle under O(N) complexity and centralized governance. Instead of building another fragile overlay, we propose ToolDNS, a radical framework that retrofits semantic tool discovery onto the Internet's most resilient substrate: the Domain Name System (DNS). By embedding functional intent and organizational trust into a hierarchical namespace, ToolDNS transforms an expensive semantic search into a series of lightweight, O(log N) name resolutions. We introduce three protocol-compliant enhancements to enable decentralized governance and semantic pruning: partially unfolded names, EDNS0 intent payloads, and logical subdomains. To rigorously evaluate this approach across the fragmented tooling landscape, we construct and release a large-scale heterogeneous benchmark comprising 33,688 real-world tools spanning MCP, A2A, RESTful, and Skill protocols. On this dataset, ToolDNS slashes the per-query search space by 95.26% while matching state-of-the-art retrieval accuracy. Furthermore, its UDP-native design reduces discovery latency by orders of magnitude compared to HTTP-based registries. Our work demonstrates that scalable AI interoperability requires not more middleware, but a smarter utilization of the infrastructure already beneath our feet.
Summary
The rapid growth of autonomous AI agents has exposed a core bottleneck in service discovery: locating the right tool among potentially millions of candidates without incurring prohibitive latency or relying on fragile centralized indexes. Existing approaches either perform exhaustive vector similarity searches over global registries or inject tool descriptions directly into large language model contexts, both of which scale poorly and introduce single points of failure or governance disputes across organizations.
ToolDNS addresses this by repurposing the Domain Name System itself as the discovery substrate. Functional intent, organizational trust, and protocol metadata are encoded directly into a hierarchical namespace under a proposed .tools top-level domain. Agents express queries through standard recursive resolution rather than separate search infrastructure, converting what would be linear scans into a sequence of lightweight name lookups whose cost grows logarithmically with the number of tools.
Three protocol-compliant extensions make this possible. Partially unfolded domain names allow progressive narrowing of an initially vague intent. EDNS0 extension payloads carry semantic descriptions without violating label-length limits. Logical subdomains decouple functional hierarchy from administrative control, so multiple independent entities can manage tools under the same parent branch while retaining their own governance and trust boundaries. The resulting system remains fully compatible with existing DNS resolvers and requires no new servers or client SDKs.
Evaluation on a newly released benchmark of 33,688 real-world tools spanning MCP, A2A, RESTful, and Skill protocols shows that two layers of hierarchical pruning shrink the per-query search space by 95.26 percent while preserving retrieval accuracy comparable to state-of-the-art vector methods. Because queries travel over UDP, measured discovery latency drops by orders of magnitude relative to HTTP-based registries. The framework and dataset are publicly available, offering a concrete path toward decentralized, infrastructure-native tool discovery that avoids additional middleware layers.
Why it matters
This research is highly relevant for Dutch AI infrastructure developers and researchers building multi-agent systems. Its decentralized governance model aligns well with European data sovereignty and transparent AI goals, offering a scalable alternative to centralized tool registries.
