The paper studies how tool-augmented LLM agents should discover APIs from large registries when the full set of tool definitions cannot fit in the context window. The dominant approach is Retrieve-then-Plan (RtP): embed the user query, run approximate nearest-neighbor search, retrieve similar tools, and then plan with those tools. The authors propose an alternative, Plan-then-Retrieve (PtR), where the LLM first generates Abstract Tool Stubs — hypothesized function signatures describing needed capabilities — and then uses those stubs as retrieval queries against the registry.

Experiments on ToolBench, which contains 46,984 unique API endpoints across 50 categories, cover three query subsets: single-tool (G1), intra-category multi-tool (G2), and cross-category multi-tool (G3). The results show a clear complexity-dependent crossover: RtP outperforms PtR on single-tool queries, while PtR outperforms RtP on multi-tool queries. This pattern is stable across all retrieval budgets from k=1 to k=20, across registry sizes ranging from 1k to 47k APIs, and across two model families, Gemini 2.5 Flash and gpt-oss-120b.

The authors characterize a stub-hallucination failure mode: PtR sometimes invents plausible but non-existent API names. This behaves as a double-edged sword. On simple queries, PtR’s stubs abstract away proper-noun signals that RtP can match directly, hurting accuracy. On complex queries, the same stub-generation mechanism decomposes multi-faceted intent into functional sub-needs, which improves retrieval and downstream planning.

The paper also analyzes token overhead. PtR’s extra discovery call roughly doubles inference cost. That cost is justified on multi-tool queries but not on single-tool ones. The authors therefore suggest complexity-adaptive routing as a practical direction, and note that the routing decision can be driven by a zero-cost signal already available in the pipeline: RtP’s top-1 retrieval score.