Apple study: planning first beats retrieval first for multi-tool AI agent queries
Apple researchers report that the best way for an LLM agent to find tools depends on how complex the request is. In a study on ToolBench, retrieving tools first worked better for single-tool queries, while having the model plan first worked better for multi-tool queries.
- Apple researchers compared Retrieve-then-Plan (RtP) with Plan-then-Retrieve (PtR) for LLM tool discovery.
- On ToolBench (46,984 API endpoints), RtP won on single-tool queries and PtR won on multi-tool queries.
- The crossover held for k=1 to 20, registry sizes from 1k to 47k APIs, and for Gemini 2.5 Flash and gpt-oss-120b.
- PtR's extra discovery call roughly doubles inference cost, according to the authors.
- The authors suggest complexity-adaptive routing based on RtP's top-1 retrieval score.
Two ways to find the right tool
LLM agents that call external tools usually have to pick from large registries of APIs. According to the paper, finite context windows make it impossible to put every tool definition into a single prompt, so agents must discover relevant tools before they plan how to execute a task.
The authors say the dominant approach is Retrieve-then-Plan (RtP). It embeds the user query and retrieves similar tools using approximate nearest-neighbor search. The team studies an alternative, Plan-then-Retrieve (PtR), in which the LLM first generates Abstract Tool Stubs. These are hypothesized function signatures that describe the capabilities needed, and they then serve as the retrieval queries against the registry.
A crossover that depends on complexity
The researchers evaluated both paradigms on ToolBench, which contains 46,984 unique API endpoints across 50 categories. They split queries into three subsets: single-tool (G1), intra-category multi-tool (G2) and cross-category multi-tool (G3).
The result was a clear complexity-dependent crossover. RtP outperformed PtR on single-tool queries, while PtR outperformed RtP on multi-tool queries. According to the authors, this holds at every retrieval budget from k=1 to 20, is robust across registry sizes from 1k to 47k APIs, and is consistent across two model families, Gemini 2.5 Flash and gpt-oss-120b.
Stub hallucination cuts both ways
The paper describes a failure mode it calls stub hallucination: the LLM invents plausible but non-existent API names. The authors describe this as a double-edged sword.
- On simple queries, PtR's stubs abstract away proper-noun signals that RtP can match directly.
- On complex queries, the same mechanism decomposes multi-faceted intent into functional sub-needs, which helps retrieval.
Cost and what comes next
PtR requires an extra discovery call. The authors analyze token overhead and show that this roughly doubles inference cost. That extra spend pays off on multi-tool queries but hurts on single-tool ones.
For that reason, the paper points to complexity-adaptive routing as a practical direction. According to the authors, such routing can be driven by a zero-cost signal already present in the pipeline: RtP's top-1 retrieval score. In practice, this suggests that developers of tool-using agents may not need to choose one architecture for all requests, but could send simple queries down the cheaper retrieval path and complex ones through planning first.
The paper is by Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang and Michael Xu, and is listed under the EMNLP conference on Apple's machine learning research site.
