Researchers Reveal Complexity-Dependent Crossover Between Retrieval Paradigms in Tool-Augmented LLM Agents

As large language models (LLMs) increasingly transition from conversational interfaces into autonomous agents capable of performing complex multi-step workflows, the mechanism by which they discover and utilize external software tools has become a critical area of computer science research. A new study authored by Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang, and Michael Xu investigates the fundamental architectural trade-offs involved when tool-augmented LLM agents interact with massive API registries.

The core challenge facing modern AI agents is a structural limitation inherent to transformer-based architectures: finite context windows. Because modern software ecosystems feature tens of thousands of unique Application Programming Interfaces, it is impossible to inject every available tool definition into a single model prompt. To overcome this limitation, agents rely on tool retrieval systems to surface relevant APIs before attempting to plan and execute a user’s request.

In their comprehensive evaluation, the researchers contrast the dominant industry approach, known as Retrieve-then-Plan (RtP), with an alternative paradigm called Plan-then-Retrieve (PtR). Through extensive testing on the ToolBench benchmark—which encompasses 46,984 unique API endpoints distributed across 50 distinct categories—the team uncovered a distinct complexity-dependent crossover between the two methods. Their findings demonstrate that neither approach is universally superior; rather, the optimal retrieval strategy depends heavily on the structural complexity of the user query.

Deconstructing the Paradigms: Retrieve-then-Plan Versus Plan-then-Retrieve

To understand the significance of the study, one must examine how both paradigms operate within an agent’s pipeline. Under the conventional Retrieve-then-Plan paradigm, the agent takes a user’s natural language query, generates an embedding of that request, and queries a vector database via approximate nearest-neighbor search to retrieve a set of similar tools. Once these tools are retrieved, the LLM incorporates their definitions into its working context and attempts to construct a coherent execution plan. While efficient for straightforward tasks, this method relies entirely on the initial text match between the user’s prompt and the static documentation of the API registry.

By contrast, the Plan-then-Retrieve paradigm reverses this workflow. Instead of searching the registry immediately using the raw user prompt, the LLM first analyzes the user’s intent and generates what the researchers term Abstract Tool Stubs. These stubs function as hypothesized function signatures that describe the specific capabilities needed to solve the problem, even if the exact naming conventions or parameters of the real APIs are initially unknown to the model. These generated stubs are then utilized as retrieval queries against the API registry, casting a functionally driven net rather than a purely semantic one.

To evaluate these competing strategies rigorously, the researchers tested both frameworks across three distinct query subsets within the ToolBench benchmark: single-tool queries, classified as G1; intra-category multi-tool queries, classified as G2; and cross-category multi-tool queries, classified as G3. This granular categorization allowed the team to isolate how query complexity impacts the retrieval accuracy and overall success rate of the agentic pipeline.

The Complexity-Dependent Crossover and Empirical Robustness

The empirical results of the study reveal a clear, undeniable crossover point governed by task complexity. Specifically, the data shows that the conventional Retrieve-then-Plan approach outperforms Plan-then-Retrieve on single-tool queries. When an agent only needs to find and execute a single, straightforward API, the overhead and extra steps introduced by generating intermediate stubs are unnecessary and occasionally counterproductive.

However, the dynamic shifts dramatically when moving to multi-tool queries. For complex tasks spanning multiple tools within the same category (G2) or crossing disparate categories entirely (G3), the Plan-then-Retrieve paradigm consistently outperforms RtP. When faced with multifaceted requests, the initial planning phase allows the LLM to decompose a complex, ambiguous user intent into distinct functional sub-needs. These decomposed functional descriptions serve as superior retrieval queries when searching massive API registries compared to the monolithic original prompt.

Crucially, the research team demonstrated that this complexity-dependent crossover is not an artifact of specific experimental parameters. The crossover holds steady across every tested retrieval budget, ranging from a restricted top-1 retrieval up to top-20 retrieved tools. Furthermore, the findings remain robust across varying registry sizes, scaling smoothly from 1,000 APIs up to the full 47,000-endpoint registry. The consistency of this pattern across diverse model families—including tests with Gemini 2.5 Flash and gpt-oss-120b—suggests that the phenomenon is a fundamental characteristic of LLM interaction with external tool environments rather than a quirk of a single proprietary architecture.

The Dual Nature of Stub Hallucination and Inference Overhead

A key contribution of the study is its deep characterization of a specific failure mode intrinsic to the Plan-then-Retrieve paradigm: stub hallucination. During the initial planning phase, the LLM frequently invents plausible-sounding but entirely non-existent API names and function signatures. Interestingly, the researchers found that this hallucination phenomenon acts as a double-edged sword within the agentic pipeline.

On simple queries, stub hallucination actively harms performance. The LLM’s invented stubs often abstract away crucial proper-noun signals and specific naming conventions that the traditional RtP approach is able to match directly against the registry’s metadata. By replacing exact terminology with abstract functional guesses, PtR introduces noise that degrades retrieval precision.

Conversely, on complex queries, that exact same hallucination mechanism transforms into an asset. By forcing the model to articulate what kind of tool it needs in a structured, abstract format, the LLM effectively decomposes a sprawling, multi-faceted intent into manageable functional components. Even if the specific names are fabricated, the functional semantics embedded within the stubs enable the vector search to surface the correct underlying APIs from the registry.

The study also provides a pragmatic analysis of token overhead and computational economics. Because PtR requires an initial generation step to produce the tool stubs before the actual retrieval and execution phases can occur, it roughly doubles the inference cost of the pipeline compared to standard RtP. While this added computational expense is well justified for complex, multi-tool queries where success rates climb, it represents an inefficient use of resources for simple single-tool tasks.

This economic trade-off points naturally toward a practical system design: complexity-adaptive routing. By dynamically evaluating whether a incoming request requires a simple single-tool lookup or a complex multi-tool workflow, an agent framework can route queries to the appropriate retrieval paradigm on the fly. The authors note that such adaptive routing can be driven efficiently by a zero-cost signal already present within the standard pipeline architecture—specifically, RtP’s top-1 retrieval score, which can serve as a reliable confidence indicator to determine when a query warrants escalating to a more robust planning-first approach.