Evaluating Tool Retrieval Paradigms for LLM Agents: When to Plan Before You Retrieve

As Large Language Models (LLMs) increasingly transition from conversational novelties into autonomous digital agents, their utility depends heavily on their capacity to interact with external systems. Tool-augmented LLM agents rely on discovering and executing relevant Application Programming Interfaces (APIs) from massive digital registries before planning their execution paths. However, this capability faces a fundamental engineering bottleneck: finite context windows make it impossible to inject thousands of comprehensive tool definitions into a single prompt.

To address this limitation, researchers have long relied on a dominant paradigm known as Retrieve-then-Plan, or RtP. In this traditional workflow, the user query is directly embedded into a vector space, and approximate nearest-neighbor search algorithms scour the registry to fetch the most statistically similar tools. While efficient for straightforward requests, this setup assumes that a single semantic pass can capture the nuanced, multi-layered requirements of complex user intents.

A new study authored by Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang, and Michael Xu investigates an alternative paradigm that reverses this operational sequence. Dubbed Plan-then-Retrieve, or PtR, this methodology prompts the LLM to first generate Abstract Tool Stubs—hypothesized function signatures that describe the specific capabilities needed to solve a problem—which are then utilized as search queries against the API registry.

To rigorously evaluate how these two strategies compare across varying levels of operational complexity, the researchers turned to ToolBench, a comprehensive benchmark encompassing 46,984 unique API endpoints distributed across 50 distinct categories. The evaluation framework segmented queries into three specific subsets: single-tool queries, designated as G1; intra-category multi-tool queries, categorized as G2; and cross-category multi-tool queries, classified as G3.

The empirical findings reveal a clear, complexity-dependent crossover between the two paradigms. According to the study, RtP outperforms PtR when handling single-tool queries, efficiently matching direct requests without the overhead of intermediary reasoning steps. Conversely, the tables turn entirely when scaling to multi-tool operations. For complex tasks requiring multiple coordinated APIs, PtR consistently outperforms RtP.

Crucially, this performance crossover is remarkably stable. The researchers observed that the crossover holds true across every tested retrieval budget, spanning from a tight retrieval limit of $k=1$ up to $k=20$. Furthermore, the dynamic remains robust across wildly varying registry sizes, scaling smoothly from compact catalogs of 1,000 APIs up to the full inventory of nearly 47,000 endpoints. This consistency also extends across different model architectures, with the behavior verified identically across major model families including Gemini 2.5 Flash and gpt-oss-120b.

Delving deeper into the mechanics of the Plan-then-Retrieve paradigm, the researchers characterized a distinct failure mode known as stub-hallucination, wherein the LLM invents plausible-sounding but entirely non-existent API names during the planning phase. Interestingly, this phenomenon acts as a double-edged sword within the agentic pipeline.

On simple queries, PtR’s generated stubs inadvertently abstract away proper-noun signals that RtP would otherwise match directly and efficiently, leading to inferior performance. However, on complex queries, this exact same hallucination or abstraction mechanism serves a vital decomposition purpose. It forces the model to break down a multi-faceted intent into smaller, functional sub-needs, bridging the semantic gap between a vague user goal and the specific technical parameters required by registry search tools.

Beyond raw accuracy and task success rates, the research team analyzed the operational token overhead associated with each workflow. Their findings indicate that PtR’s mandatory extra discovery call roughly doubles the overall inference cost compared to the single-step RtP approach. While this substantial investment pays clear dividends on multi-tool queries where comprehensive planning is paramount, it represents an unnecessary performance and financial penalty when applied to straightforward, single-tool tasks.

This economic trade-off points directly toward complexity-adaptive routing as a highly practical direction for future agent architectures. Rather than forcing all incoming user prompts through a static retrieval pipeline, systems could dynamically route queries based on their estimated complexity. The study highlights that such a routing mechanism does not require complex external classifiers; instead, it can be driven naturally by a zero-cost signal already present within the standard pipeline: the top-1 retrieval score generated during an initial RtP pass.

The insights contributed by Zhang, Surana, Majid, Wang, and Xu offer a clearer architectural roadmap for developers building scalable, tool-augmented language model agents. As AI systems take on increasingly sophisticated multi-step workflows, balancing the computational costs of planning against the raw speed of direct retrieval remains a central challenge in optimizing real-world agent deployments.