New Study Reveals Complexity-Dependent Crossover Between Retrieval Strategies in Tool-Augmented LLM Agents

As artificial intelligence systems evolve from simple conversational agents into autonomous entities capable of complex multi-step execution, researchers face a foundational bottleneck: how can a Large Language Model navigate massive registries of external tools when finite context windows prohibit injecting every available application programming interface definition into a single prompt?

A new research paper authored by Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang, and Michael Xu tackles this pressing architectural challenge. The study investigates how tool-augmented LLM agents discover relevant APIs from expansive registries before planning execution. By analyzing the mechanics of tool retrieval, the authors illuminate a distinct performance crossover between two competing paradigms, offering fresh insights that could reshape how developers design efficient agentic workflows.

To understand the scope of the problem, one must examine the sheer scale of modern digital ecosystems. Tool registries frequently encompass tens of thousands of unique API endpoints categorized across dozens of domains. Because an LLM cannot ingest all these definitions at once without exhausting its context window or degrading in reasoning performance, agents must rely on selective retrieval.

The dominant industry standard for this task is a paradigm the authors term Retrieve-then-Plan, commonly known as RtP. In the RtP workflow, the system embeds the raw user query and searches for functionally similar tools by executing an approximate nearest-neighbor search against the registry. While straightforward and effective for direct queries, RtP operates under the assumption that a user’s prompt contains explicit signals that map neatly to the nomenclature and categorization of the underlying tools.

Seeking an alternative, the researchers studied a paradigm known as Plan-then-Retrieve, or PtR. In this inverted workflow, the LLM first analyzes the user request and generates what the authors describe as Abstract Tool Stubs. These stubs function as hypothesized function signatures that explicitly describe the capabilities needed to solve the user’s problem. Once generated, these conceptual stubs—rather than the raw user query itself—serve as the retrieval queries against the API registry.

To rigorously test these competing approaches, the research team evaluated both paradigms on ToolBench, a comprehensive benchmark featuring 46,984 unique API endpoints distributed across 50 distinct categories. The evaluation was conducted across three distinct query subsets designed to test scaling complexity: single-tool queries, denoted as G1; intra-category multi-tool queries, categorized as G2; and cross-category multi-tool queries, represented as G3.

The empirical results revealed a clear and consistent complexity-dependent crossover between the two strategies. The data demonstrates that RtP outperforms PtR when handling single-tool queries. However, the performance dynamic flips entirely when dealing with multi-tool queries, where PtR consistently outperforms RtP.

Crucially, this performance crossover is not an artifact of a narrow testing condition. The study demonstrates that this crossover holds true across every tested retrieval budget, spanning from a tight budget of one retrieved tool up to twenty tools ($k=1$ to $20$). Furthermore, the crossover remains robust across varying registry scales, proving resilient when tested against registry sizes ranging from a modest 1,000 APIs all the way up to the full 47,000-endpoint benchmark. The consistency of this finding also extends across different model families, holding true when evaluated using advanced systems such as Gemini 2.5 Flash and gpt-oss-120b.

To explain these performance differences, the researchers characterized a specific failure mode intrinsic to the PtR methodology: stub hallucination. In this phenomenon, the LLM occasionally invents plausible-sounding but entirely non-existent API names during the stub-generation phase. Interestingly, the study reveals that stub hallucination acts as a double-edged sword within the agentic pipeline.

On simple queries, this hallucination mechanism actively hinders performance. PtR’s generated stubs tend to abstract away proper-noun signals and exact keywords that RtP can match directly and efficiently against the registry. By abstracting the query, PtR introduces unnecessary friction for straightforward tasks.

Conversely, on complex multi-faceted queries, this same abstraction mechanism transforms into a powerful asset. For intricate tasks, the generation of stubs forces the model to decompose a multifaceted intent into discrete functional sub-needs. This decomposition effectively breaks down a complex problem into manageable components, allowing the subsequent retrieval step to locate specialized tools that a direct keyword search would otherwise miss.

Beyond raw accuracy, the researchers conducted a thorough analysis of token overhead and computational cost. They discovered that PtR’s required exploratory discovery call roughly doubles the total inference cost of the pipeline. For multi-tool queries, this added expenditure easily pays off by yielding higher-quality tool selections and more successful task execution paths. However, for simple single-tool queries, this doubled inference cost becomes an inefficient penalty that hurts overall system efficiency.

This economic and performance dichotomy points toward a practical engineering solution: complexity-adaptive routing. By dynamically routing queries based on their inherent complexity, developers could leverage RtP for straightforward tasks to save on latency and token overhead, while switching to PtR for complex, multi-step agentic workflows.

Fascinatingly, the authors point out that implementing such complexity-adaptive routing does not require complex external classifiers. Instead, the routing decision can be driven by a zero-cost signal already natively present in the standard pipeline: RtP’s top-1 retrieval score. By monitoring the confidence score of the initial retrieval attempt, a system can intuitively decide whether a query requires the advanced decomposition power of a Plan-then-Retrieve approach.

As the developer community continues to refine tool-augmented LLM agents for enterprise and consumer applications, findings such as these highlight the necessity of moving beyond one-size-fits-all architectures. Balancing computational overhead with task complexity will remain a central frontier in optimizing autonomous AI systems.