Plan or Retrieve First? A Scale Study of Tool Discovery Architectures
Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang and Michael Xu (Apple) compare two tool-discovery designs over ToolBench's 46,984 APIs: retrieving tools by query similarity before planning, and having the LLM first write hypothetical function stubs that are then used as retrieval queries.
Ask this paper
Crossover. Retrieve-then-Plan wins on single-tool queries. Plan-then-Retrieve wins on multi-tool queries (intra-category recall +0.045, p<0.001).
Robustness. The crossover holds at every retrieval budget from k=1 to 20, at registry sizes from 1k to 47k APIs, and on both Gemini 2.5 Flash and gpt-oss-120b.
Stub hallucination. Invented API names remove proper-noun matches on simple queries but split complex requests into functional sub-needs, which helps retrieval.
Retrieval decides the trajectory. Planners use whatever tools they are given with at least 96% fidelity, so the retrieval architecture largely determines downstream behavior.
Routing. Sending single-tool queries to RtP and multi-tool queries to PtR cuts discovery-call overhead by about 36% with no loss in retrieval quality, using RtP's top-1 score as a free signal.
Abstract
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).