Retrieval vs. Planning: New Study Reveals Complexity-Dependent Crossover in Tool-Augmented LLM Agents

As Large Language Models (LLMs) increasingly transition from conversational chat interfaces into autonomous agents capable of performing complex multi-step digital workflows, the mechanism by which these systems discover and utilize external software tools has become a critical area of AI research. A new study authored by Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang, and Michael Xu sheds fresh light on this challenge, investigating how tool-augmented LLM agents navigate massive registries of Application Programming Interfaces (APIs) before executing complex user tasks.

The core engineering hurdle facing developers of tool-augmented LLM agents is the finite nature of context windows. Modern software ecosystems boast tens of thousands of unique API endpoints, making it fundamentally impossible to inject every available tool definition and function signature into a single model prompt. To circumvent this limitation, autonomous systems rely on tool retrieval mechanisms to extract only the most relevant API definitions from a broader registry.

In their new research, the authors examine the trade-offs between two distinct paradigms for bridging the gap between user requests and expansive API registries: the dominant Retrieve-then-Plan approach and an alternative methodology known as Plan-then-Retrieve.

Understanding the Competing Paradigms: Retrieve-then-Plan Versus Plan-then-Retrieve

The standard paradigm in the field, which the researchers term Retrieve-then-Plan (RtP), operates by embedding the raw user query directly into a vector space. The system then queries a large registry using approximate nearest-neighbor search to pull the most mathematically similar tool definitions before handing those definitions over to the LLM for execution planning. While computationally efficient, this approach assumes that the user’s initial prompt contains all the necessary semantic signals required to surface the correct functional tools.

By contrast, the study evaluates an alternative paradigm called Plan-then-Retrieve (PtR). In the PtR workflow, the LLM bypasses direct query embedding and instead reviews the user’s intent to first generate what the researchers call Abstract Tool Stubs. These stubs function as hypothesized, pseudo-code function signatures that describe the specific functional capabilities required to solve the task. These generated stubs are then used as retrieval queries against the underlying API registry, rather than the raw user prompt.

To rigorously evaluate how these two paradigms scale, the research team tested both approaches using ToolBench, a comprehensive benchmark dataset encompassing 46,984 unique API endpoints distributed across 50 distinct categories. The evaluation framework segmented queries into three specific subsets: single-tool queries, denoted as G1; intra-category multi-tool queries, designated as G2; and complex cross-category multi-tool queries, labeled as G3.

Complexity-Dependent Crossover and Empirical Findings

The study’s empirical evaluation uncovered a striking, complexity-dependent crossover between the two retrieval strategies. Rather than one paradigm universally outperforming the other, the optimal choice depends heavily on the structural complexity of the task at hand.

According to the findings, the traditional Retrieve-then-Plan approach outperforms Plan-then-Retrieve when handling single-tool queries. When a user request maps directly to a single, straightforward action, the overhead and intermediate generation steps of PtR introduce unnecessary latency and potential points of failure, whereas RtP matches the proper-noun signals in the user query directly to the correct tool endpoint.

However, the dynamic reverses entirely when scaling up to multi-tool queries. For complex tasks requiring the coordination of multiple distinct functions—particularly those spanning different categories within the vast registry—Plan-then-Retrieve consistently outperforms Retrieve-then-Plan.

Crucially, the research demonstrates that this performance crossover is remarkably robust. The crossover holds steady across every tested retrieval budget, spanning from a tight constraint of retrieving just one tool up to twenty tools ($k=1$ to $k=20$). Furthermore, the trend remains consistent across varying registry scales—from compact registries containing one thousand APIs up to the full 47,000-endpoint ToolBench benchmark—and holds true across different underlying model families, including Gemini 2.5 Flash and gpt-oss-120b.

The Double-Edged Sword of Stub Hallucination and Inference Overhead

To better understand the mechanics driving these results, the authors characterized a specific failure mode intrinsic to the PtR methodology: stub hallucination. In this phenomenon, the LLM invents plausible-sounding but entirely non-existent API names and function signatures during the initial planning phase.

Interestingly, the researchers discovered that stub hallucination acts as a double-edged sword within the agent pipeline. On simple queries, this mechanism proves detrimental because the LLM’s generated stubs abstract away precise proper-noun signals—such as specific database names, proprietary service titles, or exact parameters—that RtP is able to match directly.

Conversely, on complex multi-faceted queries, this same abstraction mechanism transforms into a distinct asset. By breaking down a convoluted user request into functional sub-needs, the hallucinated or generalized stubs effectively decompose a broad intent into targeted functional components that successfully mine the registry for relevant tools that a direct query embedding might otherwise miss.

This operational divergence also carries significant implications for inference costs and computational token overhead. The study shows that the extra discovery call required by the Plan-then-Retrieve paradigm roughly doubles the overall inference cost per request. For simple, single-tool operations, this doubled expenditure is an inefficient use of resources that yields no performance gain. However, for complex multi-tool workflows, the performance boost easily justifies the added token overhead.

These insights point toward a practical path forward for agent architecture: complexity-adaptive routing. By dynamically evaluating whether a user request requires single-step execution or multi-step coordination, an orchestration layer can route queries to the most appropriate retrieval paradigm. Notably, the researchers highlight that such an adaptive system can be implemented efficiently using a zero-cost signal already natively present in the pipeline—specifically, the top-1 retrieval score generated during the initial stages of a standard Retrieve-then-Plan run.