REVIEW 3 major objections 4 minor 33 references
This paper argues that AI tool discovery can be reduced to DNS name resolution, cutting per-query search space by 95.26% while matching flat retrieval accuracy.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · deepseek-v4-flash
2026-08-02 15:54 UTC pith:YCATAJ3V
load-bearing objection ToolDNS has a genuinely interesting idea, but its central compatibility claim fails as written; the evaluation metrics are too weak to support the accuracy claims. the 3 major comments →
AI Tool Discovery at Scale: All You Need is DNS
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central claim is that service discovery for AI agents is better modeled as hierarchical name resolution than as flat semantic matching. ToolDNS maps each tool to a node in a semantic namespace, and resolves an agent's intent by iteratively narrowing the namespace: at each level an authoritative server uses the EDNS0-carried intent to rank its child subdomains and returns the top-K as NS records. Partially unfolded names encode the current search position in the query name itself, so no per-query state is held by the resolver. This replaces the O(N) similarity scan of vector retrieval with O(beta*h + S) work, which is O(log N) on a balanced tree. Empirically, with only two hierarchy level
What carries the argument
The load-bearing object is the semantic namespace itself: a tree under a reserved .tools top-level domain where each label is a functional category and each leaf hosts tool SRV records. Three protocol-compliant mechanisms make it work: partially unfolded domain names, where an underscore before the domain acts as a cursor that the resolver replaces with the next matched subdomain; EDNS0 option payloads that carry the agent's natural-language intent and a K parameter to every authoritative server; and logical subdomains that decouple a functional prefix (weather.tools) from organizational identifiers (hku.weather.tools), enabling multi-tenant governance. The authoritative servers do the seman
Load-bearing premise
The scheme collapses if ordinary, unmodified recursive resolvers will not forward the custom EDNS0 payload and follow the NS referrals for partially unfolded names, because the claimed zero-modification deployment depends on that behavior.
What would settle it
Point a stock, unmodified recursive resolver at a .tools test zone, send it a partially unfolded SRV query with an EDNS0 intent payload (e.g., _mcp._tcp._weather.tools), and observe whether it follows the returned NS referral and rewrites the cursor. If the resolver returns NXDOMAIN or refuses to follow the referral, the protocol's compatibility premise is empirically false.
If this is right
- Tool discovery can scale to millions of tools with per-query cost that grows logarithmically instead of linearly, provided the taxonomy is balanced.
- New or updated tools become discoverable immediately, since matching happens at query time against local zone data and no global index needs rebuilding.
- A single discovery interface covers tools that use different invocation protocols, because SRV service and protocol labels encode the protocol in the name.
- Agents can enforce trust and security policies by resolving only within organizational subdomains, without a central trust anchor.
- The hierarchical decomposition itself improves LLM ranking accuracy by reducing attention dilution, beyond the efficiency gain.
Where Pith is reading between the lines
- Editorial extension: the same intent-to-namespace encoding could apply to other agent-facing resources—models, datasets, or even other agents—turning any registration problem into a DNS zone.
- Editorial extension: the claimed latency advantage depends on staying in plain UDP; if EDNS0 payloads grow or encrypted transports like DoT/DoH become mandatory, the messaging overhead may approach that of HTTP, so the comparison should be re-run under encrypted transports.
- Editorial extension: the search-space reduction is only as good as the taxonomy; a stress test with misclassified or overlapping categories, or with tools that legitimately span multiple branches, would show how robust the pruning is.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes ToolDNS, a DNS-based hierarchical tool discovery framework. Functional intent is encoded into partially unfolded domain names and EDNS0 payloads; LLM-based semantic scoring at authoritative servers prunes candidate subdomains level by level. The paper claims O(log N) per-query complexity, a 95.26% search-space reduction, retrieval accuracy comparable to state-of-the-art flat retrieval, and compatibility with unmodified DNS resolvers. It also contributes a 33,688-tool benchmark spanning MCP, A2A, RESTful, and Skill protocols. Experiments report category-level hit rates, search-space counts, and network-traffic comparisons against HTTP-based baselines.
Significance. The underlying vision of reusing DNS for agent tool discovery is thought-provoking, and the released multi-protocol dataset is a potentially useful community resource. The logical-subdomain idea for delegated trust is also interesting. However, the central deployment claim—that ToolDNS runs on unmodified recursive resolvers—is contradicted by the paper's own algorithm and compatibility discussion. In addition, the evaluation is substantially self-referential: the taxonomy, the ground-truth queries, and the semantic scorers all come from the same LLM family, and the hit-rate metric counts any tool in the same leaf sub-category as a hit. As presented, the paper does not support its headline claims of matching state-of-the-art retrieval accuracy and zero-modification deployment.
major comments (3)
- [§3.3.2, §3.4 Algorithm 1, §4.2] The claim that ToolDNS works with unmodified recursive resolvers is contradicted by Algorithm 1 and by the paper's own Section 4.2. Algorithm 1 requires the resolver to select a subdomain from returned NS records and rewrite the QNAME by replacing the cursor label (line 14). Standard iterative resolvers follow referrals only when the current QNAME is a descendant of the delegated zone (RFC 1034). The initial QNAME `_mcp._tcp._tools.` is not a descendant of `weather.tools`, and the derived name `_mcp._tcp._weather.tools.` is produced by nonstandard client/resolver logic. Section 4.2 concedes that unmodified resolvers 'will not perform semantic pruning, so the query will likely fail to resolve.' Thus the zero-modification, no-new-infrastructure contribution is not supported; a custom resolver or custom iterative client is required. This is a load-bearing issue, not a presentation detail.
- [§5.1, §5.2, Definition 2] The accuracy evaluation is circular and the metric is too lenient. The hierarchical taxonomy used by ToolDNS's semantic pruning is constructed by Qwen/DeepSeek in Steps 3–6 of the data pipeline, and the ground-truth query–tool pairs are generated by Qwen in Step 7. The same model family is then used as the semantic scorer in §3.5.1 and Appendix A. The evaluation therefore largely measures self-consistency among LLM outputs rather than retrieval quality. Moreover, Definition 2 counts any tool in the same leaf sub-category as a hit; with K=1 at the pruning levels, a query can be 'successful' even if the exact intended tool is not returned. This does not substantiate the claim of 'matching state-of-the-art retrieval accuracy.' Independent human relevance judgments and an exact-tool or properly ranked hit metric are needed.
- [§3.2.1 Remark 2, §5.3] The O(log N) claim is not established. Remark 2 states the queried-tool count as O(βh + S), where S is the size of the leaf node's tool list; S is not bounded by any logarithmic quantity in the design. The two-level experiment in §5.3 reports an average leaf candidate set of about 1,197 tools at N ≈ 25,300, which is not asymptotically logarithmic. No balanced-tree assumption, branching-factor distribution, or depth measurements are provided. The 95.26% reduction is an empirical constant-factor improvement at one scale, not evidence of O(log N) scaling. The asymptotic claim needs either a formal bound on S and β or a revised statement.
minor comments (4)
- [Table 1] The final row is garbled: 'Remaining' is shown as '100' and the Step 6 rate is '18.14%'. The raw counts (54,700 → 33,688 after removing 21,012) should be presented consistently, and the column headers should be aligned with the steps.
- [§3.1] 'As illustrated in Figure ?' contains a missing figure reference; the figure number should be filled in.
- [Appendix A] The prompt templates contain garbled text: 'öther¨' should be 'other', and several curly braces in the prompt placeholders are inconsistently formatted.
- [General] Typographical issues include 'offical', 'ereinafter', and inconsistent 'REST-ful' / 'RESTful'. Please run a proofreading pass.
Circularity Check
The reported retrieval accuracy is a self-consistency test: Qwen builds the taxonomy, labels, and ground-truth queries while ToolDNS's LLM scorer is judged by agreement with Qwen's own categories.
specific steps
-
fitted input called prediction
[Section 5.1, Step 7; Section 5.2; Appendix A]
"Following the methodology of ToolLLM, we used Qwen to generate task queries for each tool. These “intent-tool” pairs serve as the ground truth to test the retrieval effectiveness of ToolDNS. ... The System prompt used in this experiment is provided as “Agent Role of TLD server” and “Agent Role of NS server” in Appendix.A."
ToolDNS's semantic pruning is performed by an LLM ranker (Section 3.5.1: 'we use small LLM scoring'; Appendix A gives the LLM ranking prompts). The test queries and their ground-truth tool labels are generated by Qwen in the same pipeline that builds the dataset. The reported hit rate therefore measures the ranker's agreement with Qwen's own query-tool assignments, not retrieval accuracy against an independent or human-labeled ground truth. This is a fitted input being presented as a prediction: the evaluator and the evaluated share the label generator.
-
self definitional
[Section 5.1, Step 6; Section 5.2 (Definition 2)]
"We again used Qwen to assign sub-categories to data within each major category and removed unclassifiable items. ... A retrieval is counted as a hit if the returned tool belongs to the same semantic sub-category as T."
Definition 2 relativizes success to R_t, the set of tools in the same leaf sub-category. Those sub-categories were assigned by Qwen in Step 6, while ToolDNS's hierarchical pruning returns a sub-category selected by an LLM at each level. The hit-rate metric is thus defined in terms of the same classifier output that the experiment claims to validate; a 'hit' means the LLM scorer chose the LLM-assigned label. The accuracy comparison with ToolLLM is therefore a comparison of two models' agreement with Qwen's taxonomy, not an outcome of the DNS mechanism.
full rationale
The circularity is concentrated in the empirical validation, not in the DNS-based architecture itself. ToolDNS's O(log N) analysis (Remark 2) is a standard tree-search bound and is not circular. The 95.26% search-space number is an arithmetic consequence of the authors' own taxonomy's leaf sizes; while it is not independently validated, it is not itself a hidden reuse of the result. What makes the headline 'matching state-of-the-art retrieval accuracy' circular is the evaluation loop: Qwen generated the summaries, sub-category labels, and the query-tool ground truth (Section 5.1, Steps 1, 6, 7), and the ToolDNS scorer is an LLM prompt (Appendix A) judged by whether it lands in the Qwen-assigned sub-category (Section 5.2). The hit-rate metric is therefore a measure of an LLM's agreement with itself, so the central accuracy claim reduces to a self-consistency check. This warrants 7 rather than 8 because the framework has independent architectural content and the self-consistency could in principle have failed. The unmodified-resolver contradiction (Algorithm 1's cursor replacement vs. Section 3.3.2's compatibility claim) is a serious correctness issue but not a circularity, so it is not scored here. No load-bearing self-citation was found.
Axiom & Free-Parameter Ledger
free parameters (3)
- K (top-K at each pruning step) =
1
- Taxonomy depth and structure =
2 levels, 14 top-level categories (Appendix B)
- Semantic summaries per subdomain =
LLM-generated keywords/sentences
axioms (3)
- domain assumption Tool functionality can be adequately captured by a hierarchical taxonomy (Section 4.3).
- domain assumption Standard DNS resolvers will forward EDNS0 options and accept the partial-name referral pattern described in Algorithm 1 (Sections 3.3.2, 3.3.3).
- standard math Balanced tree and bounded branching factor for the O(log N) complexity claim (Remark 2).
invented entities (3)
-
Reserved .tools top-level domain
no independent evidence
-
New EDNS0 option code for intent payload
no independent evidence
-
Partially unfolded domain name cursor (underscore placeholder)
no independent evidence
read the original 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.
Figures
Reference graph
Works this paper leans on
-
[1]
Roy Arends, Rob Austein, Matt Larson, Dan Massey, and Scott Rose. 2005. RFC 4033: DNS security introduction and requirements
2005
-
[2]
2005.Reliable distributed systems: technologies, web services, and applications
Kenneth P Birman. 2005.Reliable distributed systems: technologies, web services, and applications. Springer
2005
-
[3]
Enfang Cui, Yujun Cheng, Rui She, Dan Liu, Zhiyuan Liang, Minxin Guo, Tianzheng Li, Qian Wei, Wenjuan Xing, and Zhijie Zhong. 2025. AgentDNS: A Root Domain Naming System for LLM Agents. arXiv:2505.22368 [cs.AI] https://arxiv.org/abs/2505.22368
Pith/arXiv arXiv 2025
-
[4]
Hongwei Cui, Yuyang Du, Qun Yang, Yulin Shao, and Soung Chang Liew. 2024. LLMind: Orchestrating AI and IoT with LLM for complex task execution.IEEE Communications Magazine63, 4 (2024), 214–220
2024
-
[5]
Joao Damas, Michael Graff, and Paul Vixie. 2013. RFC 6891: Extension mecha- nisms for DNS (EDNS (0))
2013
-
[6]
Yunus Durmus and Ertan Onur. 2015. Service knowledge discovery in smart machine networks.Wireless Personal Communications81, 4 (2015), 1455–1480
2015
-
[7]
Abul Ehtesham, Aditi Singh, Gaurav Kumar Gupta, and Saket Kumar. 2025. A survey of agent interoperability protocols: Model context protocol (MCP), agent communication protocol (ACP), agent-to-agent protocol (A2A), and agent network protocol (ANP).arXiv preprint arXiv:2505.02279(2025)
Pith/arXiv arXiv 2025
-
[8]
Robert Elz and Randy Bush. 1997. RFC2181: Clarifications to the DNS Specifica- tion
1997
-
[9]
2000.Architectural styles and the design of network-based software architectures
Roy Thomas Fielding. 2000.Architectural styles and the design of network-based software architectures. University of California, Irvine
2000
-
[10]
De Filippi et al. 2016. The invisible politics of Bitcoin: governance crisis of a decentralised infrastructure.Internet Policy Review5, 3 (2016)
2016
-
[11]
Arnt Gulbrandsen, Paul Vixie, and Levon Esibov. 2000. RFC2782: A DNS RR for specifying the location of services (DNS SRV)
2000
-
[12]
Mark Handley. 2006. Why the Internet only just works.BT Technology Journal 24, 3 (2006), 119–129
2006
-
[13]
Paul Hoffman and Patrick McManus. 2018. RFC 8484: DNS queries over HTTPS (DoH)
2018
-
[14]
Zi Hu, Liang Zhu, John Heidemann, Allison Mankin, Duane Wessels, and Paul Hoffman. 2016. RFC 7858: Specification for DNS over transport layer security (TLS)
2016
-
[15]
Ken Huang, Vineeth Sai Narajala, Idan Habler, and Akram Sheriff. 2026. Agent name service (ANS): A universal directory for secure AI agent discovery and interoperability. InInternational Conference on AI in Cybersecurity (ICAIC). IEEE, 1–9
2026
-
[16]
Shishir G Patil, Tianjun Zhang, Xin Wang, and Joseph E Gonzalez. 2024. Go- rilla: Large language model connected with massive APIs.Advances in Neural Information Processing Systems37 (2024), 126544–126565
2024
-
[17]
Yujia Qin, Shihao Liang, Yining Ye, Kunlun Zhu, Lan Yan, Yaxi Lu, Yankai Lin, Xin Cong, Xiangru Tang, Bill Qian, et al. 2023. ToolLLM: Facilitating large language models to master 16000+ real-world APIs.arXiv preprint arXiv:2307.16789(2023)
Pith/arXiv arXiv 2023
-
[18]
Ramesh Raskar, Pradyumna Chari, John Zinky, Mahesh Lambe, Jared James Grogan, Sichao Wang, Rajesh Ranjan, Rekha Singhal, Shailja Gupta, Robert Lincourt, et al. 2025. Beyond DNS: Unlocking the internet of AI agents via the nanda index and verified agentfacts.arXiv preprint arXiv:2507.14263(2025)
Pith/arXiv arXiv 2025
-
[19]
Partha Pratim Ray. 2025. A survey on model context protocol: Architecture, state-of-the-art, challenges and future directions.Authorea Preprints(2025)
2025
-
[20]
David P Reed. 2010. End-to-end arguments: The Internet and beyond. InUSENIX Security Symposium
2010
-
[21]
Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. 2023. Toolformer: Language models can teach themselves to use tools.Advances in Neural Information Processing Systems36 (2023), 68539–68551
2023
-
[22]
Yulin Shao, Qi Cao, and Deniz Gündüz. 2024. A theory of semantic communica- tion.IEEE Transactions on Mobile Computing23, 12 (2024), 12211–12228
2024
-
[23]
Yulin Shao, Deniz Gündüz, and Soung Chang Liew. 2021. Federated edge learn- ing with misaligned over-the-air computation.IEEE Transactions on Wireless Communications21, 6 (2021), 3951–3964
2021
-
[24]
Ion Stoica and Scott Shenker. 2021. From cloud computing to sky computing. In Proceedings of the Workshop on Hot Topics in Operating Systems. 26–32
2021
-
[25]
OpenClaw Team. 2024. OpenClaw Documentation. https://docs.openclaw.ai/. Accessed: 2026-03-30
2024
-
[26]
Qwen Team. 2025. Qwen3 Technical Report. arXiv:2505.09388 [cs.CL] https: //arxiv.org/abs/2505.09388
Pith/arXiv arXiv 2025
-
[27]
Lukas Weidener, Marko Brkić, Phillip Lee, Martin Karlsson, Kevin Noessler, and Paul Kohlhaas. 2026. From agent-only social networks to autonomous scientific research: Lessons from OpenClaw and Moltbook, and the architecture of ClawdLab and Beach.Science.arXiv preprint arXiv:2602.19810(2026)
arXiv 2026
-
[28]
Niklaus Wirth. 2002. A plea for lean software.Computer28, 2 (2002), 64–68
2002
-
[29]
Mengying Wu, Pei Chen, Geng Hong, Baichao An, Jinsong Chen, Binwang Wan, Xudong Pan, Jiarun Dai, and Min Yang. 2025. MCPZoo: A Large-Scale Dataset of Runnable Model Context Protocol Servers for AI Agent.arXiv preprint arXiv:2512.15144(2025)
arXiv 2025
-
[30]
Renjun Xu and Yang Yan. 2026. Agent skills for large language models: Architec- ture, acquisition, security, and the path forward.arXiv preprint arXiv:2602.12430 (2026)
Pith/arXiv arXiv 2026
-
[31]
John Yang, Carlos E Jimenez, Alexander Wettig, Kilian Lieret, Shunyu Yao, Karthik Narasimhan, and Ofir Press. 2024. Swe-agent: Agent-computer interfaces enable automated software engineering.Advances in Neural Information Processing Systems37 (2024), 50528–50652
2024
-
[32]
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R Narasimhan, and Yuan Cao. 2022. React: Synergizing reasoning and acting in language models. InInternational Conference on Learning Representations
2022
-
[33]
Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, et al. 2023. A survey of large language models.arXiv preprint arXiv:2303.182231, 2 (2023), 1–124. 13
Pith/arXiv arXiv 2023
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.