# AI Tool Discovery at Scale: All You Need is DNS

arXiv: https://arxiv.org/abs/2607.18242 · HTML: https://mlsanity.com/paper/2607.18242/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 32 references that are in the map.
- First posted on arXiv 19 Apr 2026.

## Builds on (most cited first, 9 of 9)

- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [A survey of agent interoperability protocols: Model Context Protocol (MCP), Agent Communication Protocol (ACP), Agent-to-Agent Protocol (A2A), and Agent Network Protocol (ANP)](https://mlsanity.com/paper/2505.02279/) (2025)
- [Federated Edge Learning with Misaligned Over-The-Air Computation](https://mlsanity.com/paper/2102.13604/) (2021)
- [LLMind: Orchestrating AI and IoT with LLM for Complex Task Execution](https://mlsanity.com/paper/2312.09007/) (2023)
- [Agent Name Service (ANS): A Universal Directory for Secure AI Agent Discovery and Interoperability](https://mlsanity.com/paper/2505.10609/) (2025)
- [Beyond DNS: Unlocking the Internet of AI Agents via the NANDA Index and Verified AgentFacts](https://mlsanity.com/paper/2507.14263/) (2025)
- [AgentDNS: A Root Domain Naming System for LLM Agents](https://mlsanity.com/paper/2505.22368/) (2025)
- [MCPZoo: A Large-Scale Dataset of Runnable Model Context Protocol Servers for AI Agent](https://mlsanity.com/paper/2512.15144/) (2025)

## Abstract (arXiv)

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.