Apple Research Finds Plan-then-Retrieve Outperforms Retrieve-then-Plan for Multi-Tool LLM Agents

Tool-augmented LLM agents must discover relevant APIs from large registries, but finite context windows prevent injecting all definitions into a single prompt. Apple researchers compare the dominant Retrieve-then-Plan (RtP) approach, which embeds user queries for approximate nearest-neighbor search, against an alternative Plan-then-Retrieve (PtR) paradigm. In PtR, the LLM first generates Abstract Tool Stubs—hypothesized function signatures describing needed capabilities—which then serve as retrieval queries.

Complexity-Dependent Performance Crossover

Evaluating on ToolBench (46,984 unique API endpoints across 50 categories), the study identifies a clear crossover based on query complexity. RtP outperforms PtR on single-tool queries (G1), while PtR outperforms RtP on both intra-category (G2) and cross-category (G3) multi-tool queries. This trend holds consistently across retrieval budgets (k=1 to 20), registry sizes from 1k to 47k APIs, and model families including Gemini 2.5 Flash and gpt-oss-120b.

Stub-Hallucination and Cost Implications

The researchers characterize a stub-hallucination failure mode where the LLM invents plausible but non-existent API names. On simple queries, this mechanism causes PtR to lose proper nouns that RtP would have matched directly. However, on complex multi-tool tasks, the functional description in the stub helps retrieve the correct tools. PtR incurs higher costs due to an extra LLM call, doubling the latency and token usage compared to RtP. The authors suggest complexity-aware routing as a practical solution, using RtP’s initial retrieval score as a zero-cost signal to decide whether to switch to PtR for harder queries.