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

Apple researchers studied two tool discovery architectures for LLM agents: Retrieve-then-Plan (RtP) and Plan-then-Retrieve (PtR).

Evaluating on ToolBench across single-tool and multi-tool queries, they found a complexity-dependent crossover where RtP outperforms PtR on single-tool queries while PtR outperforms RtP on multi-tool queries.

The crossover holds across retrieval budgets, registry sizes, and model families, and the paper characterizes a stub-hallucination failure mode that acts as a double-edged sword.