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

Summary

Tool-augmented LLM agents must discover relevant APIs from large registries before planning, but finite context windows prevent injecting all tool definitions into a single prompt. Two competing architectures are Retrieve-then-Plan (RtP), which embeds the query and retrieves similar tools via nearest-neighbor search, and Plan-then-Retrieve (PtR), which first generates abstract tool stubs as retrieval queries. Evaluating on ToolBench with 46,984 API endpoints across 50 categories reveals a clear complexity-dependent crossover: RtP outperforms PtR on single-tool queries while PtR outperforms RtP on multi-tool queries. PtR’s stub-hallucination failure mode acts as a double-edged sword—on simple queries it abstracts away proper-noun signals, yet on complex queries it decomposes multi-faceted intent into functional sub-needs. PtR roughly doubles inference cost, which pays off on multi-tool queries but hurts on single-tool ones, motivating complexity-adaptive routing driven by RtP’s top-1 retrieval score.

Takeaways

1. 1

   A complexity-dependent crossover exists: RtP outperforms PtR on single-tool queries, while PtR outperforms RtP on multi-tool queries, consistent across retrieval budgets, registry sizes, and model families.

2. 2

   PtR’s stub-hallucination (inventing plausible but non-existent API names) is a double-edged sword: it abstracts away proper-noun signals on simple queries but decomposes multi-faceted intent on complex queries.

3. 3

   PtR’s extra discovery call roughly doubles inference cost, beneficial for multi-tool queries but wasteful for single-tool ones, motivating complexity-adaptive routing using RtP’s top-1 retrieval score as a zero-cost signal.

FAQ