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

Apple Machine Learning Research published a study by Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang and Michael Xu comparing two architectures for how tool-augmented LLM agents find relevant APIs inside large registries before they plan an execution. The paper is titled "Plan or Retrieve First? A Scale Study of Tool Discovery Architectures."
Tool-using agents cannot simply load every available API definition into a prompt, because context windows are finite. The paper's framing is that the dominant pattern is Retrieve-then-Plan, or RtP: the system embeds the user query, then pulls similar tool definitions using approximate nearest-neighbor search. The authors examine the reverse order, Plan-then-Retrieve, or PtR, in which the model first writes what they call Abstract Tool Stubs, essentially hypothesized function signatures that describe the capabilities it thinks it needs. Those stubs then become the retrieval queries sent against the registry.
The evaluation uses ToolBench, described in the paper as a registry of 46,984 unique API endpoints spanning 50 categories. Queries are split into three subsets: single-tool (G1), intra-category multi-tool (G2) and cross-category multi-tool (G3).
The central result is a crossover that depends on query complexity. RtP performs better on single-tool queries, while PtR performs better on multi-tool queries. The authors report that this pattern holds at every retrieval budget they tested, from k=1 to 20, across registry sizes ranging from 1k to 47k APIs, and across two model families: Gemini 2.5 Flash and gpt-oss-120b.
The paper also characterizes a failure mode it calls stub hallucination, where the model invents plausible but non-existent API names. The authors treat this as a double-edged mechanism rather than a simple defect. On simple queries, PtR's stubs abstract away the proper-noun signals that RtP matches directly, which helps explain why RtP wins there. On complex queries, the same mechanism decomposes multi-faceted intent into functional sub-needs, which helps explain why PtR wins there.
The authors also analyze token overhead. PtR's extra discovery call roughly doubles inference cost relative to RtP. That cost pays off on multi-tool queries but hurts on single-tool ones. They propose complexity-adaptive routing as a practical direction, and note it can be driven by a zero-cost signal already present in the pipeline: RtP's top-1 retrieval score.
For developers building agent tooling, the practical reading of this work is that the retrieval order is not a universal choice but a routing decision tied to expected query complexity. A single-tool lookup and a cross-category orchestration task appear to reward opposite architectures, and the cheap top-1 score from an initial RtP pass is offered as a way to decide which path to take without paying for an extra model call just to make the decision.
The reported robustness across retrieval budgets and registry scales is notable because retrieval quality in large tool registries is often sensitive to how many candidates are returned. A crossover that survives k=1 through k=20 and registries from one thousand to roughly forty-seven thousand endpoints suggests the effect is driven by query structure rather than by the amount of headroom in the context window.
One limitation to keep in mind is that the double-cost finding is a cost issue, not an accuracy issue: the study supports routing by complexity, not abandoning PtR outright. How well the top-1 score threshold that drives such routing generalizes to other registries or query distributions is not settled by the excerpt.
Why it matters: teams building tool-using agents should treat tool discovery as a two-regime problem rather than picking one retrieval order globally. If the crossover holds in a given product's query mix, routing simple lookups to Retrieve-then-Plan and complex multi-tool requests to Plan-then-Retrieve could improve accuracy without paying PtR's roughly doubled inference cost on every request. Inference: the top-1 retrieval score looks like the cheapest place to start building that router.
Based on reporting from the original publisher. Visit the source for full context and later updates.
Publisher excerpt
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) wh