Plan or Retrieve First? A Scale Study of Tool Discovery Architectures

A scale study by Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang and Michael Xu found a complexity-dependent crossover between two tool-discovery architectures for LLM agents: Retrieve-then-Plan (RtP) beats Plan-then-Retrieve (PtR) on single-tool queries, while PtR wins on multi-tool queries. Evaluated on ToolBench's 46,984 unique API endpoints across 50 categories and query subsets G1, G2 and G3, the crossover held at every retrieval budget from k=1 to 20, across registry sizes from 1k to 47k APIs, and across Gemini 2.5 Flash and gpt-oss-120b. The authors attribute PtR's edge on complex queries to Abstract Tool Stubs decomposing multi-faceted intent, but note PtR's extra discovery call roughly doubles inference cost, motivating complexity-adaptive routing driven by RtP's top-1 retrieval score.

content type paper https://machinelearning.apple.com/research/ published October 2026 Plan or Retrieve First? A Scale Study of Tool Discovery Architectures AuthorsMingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang, Michael Xu Tool-augmented LLM agents discover relevant APIs from large registries before planning execution, yet finite context windows prohibit injecting all tool definitions into a single prompt. The dominant approach, which we term Retrieve-then-Plan RtP , embeds the user query and retrieves similar tools via approximate nearest-neighbor search. We study an alternative Plan-then-Retrieve PtR paradigm in which the LLM first generates Abstract Tool Stubs hypothesized function signatures describing needed capabilities which then serve as retrieval queries against the registry. Evaluating on ToolBench 46,984 unique API endpoints, 50 categories across single-tool G1 , intra-category multi-tool G2 , and cross-category multi-tool G3 query subsets, we find a clear complexity-dependent crossover: RtP outperforms PtR on single-tool queries while PtR outperforms RtP on multi-tool queries. This crossover holds at every retrieval budget k=1 to 20 , is robust across registry sizes from 1k to 47k APIs, and is consistent across model families Gemini 2.5 Flash and gpt-oss-120b . We characterize a stub-hallucination failure mode the LLM invents plausible but non-existent API names that acts as a double-edged sword: on simple queries PtR’s stubs abstract away proper-noun signals that RtP matches directly, yet on complex queries the same mechanism decomposes multi-faceted intent into functional sub-needs. We further analyze token overhead and show that PtR’s extra discovery call roughly doubles inference cost, which pays off on multi-tool queries but hurts on single-tool ones, motivating complexity-adaptive routing as a practical direction—one that can be driven by a zero-cost signal already present in the pipeline RtP’s top-1 retrieval score . ProTIP: Progressive Tool Retrieval Improves Planning December 20, 2023 research area Knowledge Bases and Search https://machinelearning.apple.com/research/?domain=Knowledge%20Bases%20and%20Search , research area Speech and Natural Language Processing https://machinelearning.apple.com/research/?domain=Speech%20and%20Natural%20Language%20Processing Large Language Models LLMs are increasingly employed for complex multi-step planning tasks, where the Tool Retrieval TR step is crucial for achieving successful outcomes. Two prevalent approaches for TR are single-step retrieval, which utilizes the complete query, and sequential retrieval using Task Decomposition TD , where a full query is segmented into discrete atomic subtasks. While single-step retrieval lacks the flexibility to handle… Context Tuning for Retrieval Augmented Generation December 18, 2023 research area Knowledge Bases and Search https://machinelearning.apple.com/research/?domain=Knowledge%20Bases%20and%20Search , research area Speech and Natural Language Processing https://machinelearning.apple.com/research/?domain=Speech%20and%20Natural%20Language%20Processing Workshop at EACL https://machinelearning.apple.com/research/?event=EACL%20Workshop This paper was accepted at the UncertaiNLP workshop at EACL 2024. Large language models LLMs have the remarkable ability to solve new tasks with just a few examples, but they need access to the right tools. Retrieval Augmented Generation RAG addresses this problem by retrieving a list of relevant tools for a given task. However, RAG’s tool retrieval step requires all the required information to be explicitly present in the query. This is a…