ToolDNS: Using DNS to Discover Tools for AI Agents Cuts the Search Space by 95%

In July 2026, researchers published ToolDNS on arXiv, a framework that moves tool discovery for AI agents into the Domain Name System (DNS). It cuts the per-query search space by 95.26% while keeping accuracy on par with the best existing solutions.

Why tool discovery was moved into DNS

ToolDNS targets a scaling problem: autonomous AI agents will soon have to navigate millions of tools, and existing registries run in O(N) time and require centralized management. Instead of building yet another brittle layer on top, the authors propose using the most resilient infrastructure on the internet: DNS. A tool's functional purpose and its organization's trust level are encoded in a hierarchical namespace, which turns expensive semantic search into a series of lightweight name resolutions with O(log N) complexity.

Key facts about the work:

• A benchmark of 33,688 real-world tools across four protocols: MCP, A2A, RESTful and Skill
• 95.26% reduction in the per-query search space
• Discovery complexity of O(log N) instead of the O(N) of centralized registries
• Three protocol-compatible extensions: partially unfolded names, intent payloads in EDNS0, and logical subdomains
• Native UDP transport instead of HTTP

Three extensions on top of DNS

ToolDNS introduces three protocol-compatible extensions that provide decentralized governance and semantic pruning. The first is partially unfolded names: part of a tool's hierarchy is expanded directly in the domain name, so irrelevant branches can be pruned without querying an external index. The second is an intent payload in EDNS0: the agent passes its functional intent in an extended field of the DNS query. The third is logical subdomains that encode organizational trust: the structure of the name itself shows which organization a tool belongs to.

What the benchmark showed

On the assembled dataset of 33,688 tools, ToolDNS cut the per-query search space by 95.26%, while retrieval accuracy stayed on par with state-of-the-art solutions. The dataset was deliberately built to be heterogeneous, drawn from a fragmented tool landscape and covering the MCP, A2A, RESTful and Skill protocols; the authors released it publicly alongside the paper.

The key result is that the 95.26% reduction came with no loss of accuracy: on retrieval metrics, ToolDNS keeps pace with the best semantic search systems available today, even though it examines only a small fraction of the tool space.

How much faster is it?

ToolDNS's UDP-based design lowers discovery latency by orders of magnitude compared with registries running over HTTP. Name resolution fits into lightweight UDP packets instead of full HTTP requests, so an agent does not need to establish a connection and wait for a heavy registry to respond for each tool. The authors say the move to native UDP, rather than an additional middleware layer, is the key to scalability.

"Scalable AI interoperability requires not more intermediate layers,

but a smarter use of the infrastructure that is already right under our feet," the paper's arXiv abstract says.

What this means

ToolDNS shows that infrastructure for the AI agent ecosystem does not have to be invented from scratch; it can be built on DNS, a protocol that has scaled to the entire internet for decades. For AI agent developers, this points to a potentially standard, decentralized way to publish and find tools, with no single intermediary registry that would become a bottleneck and a point of control. If the approach catches on, finding the right tool among millions could become as cheap as an ordinary DNS query.

Frequently asked questions

What is ToolDNS?

ToolDNS is a framework proposed on arXiv in July 2026 that embeds semantic tool discovery into the Domain Name System (DNS). It turns a search across millions of tools from an O(N) operation into a chain of name resolutions with O(log N) complexity.

Which protocols does the benchmark cover?

The ToolDNS benchmark consists of 33,688 real-world tools and covers four protocols: MCP, A2A, RESTful and Skill. The dataset is publicly available alongside the paper.