AI Tool Discovery at Scale: All You Need is DNS

A new framework called ToolDNS retrofits semantic tool discovery onto the Domain Name System (DNS), enabling autonomous AI agents to navigate millions of tools with O(log N) complexity. On a benchmark of 33,688 real-world tools spanning MCP, A2A, RESTful, and Skill protocols, ToolDNS reduces the per-query search space by 95.26% while matching state-of-the-art retrieval accuracy, and its UDP-native design cuts discovery latency by orders of magnitude compared to HTTP-based registries.

arXiv:2607.18242v1 Announce Type: new Abstract: 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.