Tool retrieval method improves with query complexity and registry size
Plan or Retrieve First? A Scale Study of Tool Discovery Architectures
Artificial IntelligenceInformation Retrieval
Summary
Finding the right software tools from a huge collection is hard for AI helpers because they can't look at everything at once. The authors compare two ways of searching: one that finds tools first then plans how to use them, and another that plans what is needed before searching. They show that the first works better when only one tool is needed, but the second is better when multiple tools are involved. The second method is more expensive to run but helps break down complex needs into smaller parts.
What this means in practice
- •For software engineers: Optimize AI-assisted code generation by choosing tool retrieval methods based on query complexity to improve multi-API integration.
- •For api platform operators: Enhance API registry search tools with complexity-aware retrieval that adapts between planning-first and retrieval-first approaches.
Authors
Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang, Michael Xu
Abstract
Tool-augmented LLM agents discover relevant APIs from large registries before planning execution, yet finite context windows prohibit injecting all tool definitions into a single prompt. The dominant approach, which we term Retrieve-then-Plan (RtP), embeds the user query and retrieves similar tools via approximate nearest-neighbor search. We study an alternative Plan-then-Retrieve (PtR) paradigm in which the LLM first generates Abstract Tool Stubs (hypothesized function signatures describing needed capabilities) which then serve as retrieval queries against the registry. Evaluating on ToolBench (46,984 unique API endpoints, 50 categories) across single-tool (G1), intra-category multi-tool (G2), and cross-category multi-tool (G3) query subsets, we find a clear complexity-dependent crossover: RtP outperforms PtR on single-tool queries while PtR outperforms RtP on multi-tool queries. This crossover holds at every retrieval budget (k=1 to 20), is robust across registry sizes from 1k to 47k APIs, and is consistent across model families (Gemini 2.5 Flash and gpt-oss-120b). We characterize a stub-hallucination failure mode (the LLM invents plausible but non-existent API names) that acts as a double-edged sword: on simple queries PtR's stubs abstract away proper-noun signals that RtP matches directly, yet on complex queries the same mechanism decomposes multi-faceted intent into functional sub-needs. We further analyze token overhead and show that PtR's extra discovery call roughly doubles inference cost, which pays off on multi-tool queries but hurts on single-tool ones, motivating complexity-adaptive routing as a practical direction, one that can be driven by a zero-cost signal already present in the pipeline (RtP's top-1 retrieval score).