Complexity-Dependent Crossover Revealed: New Study Compares Tool Retrieval Paradigms for LLM Agents

As Large Language Models (LLMs) increasingly transition from conversational assistants to autonomous agents capable of executing complex multi-step workflows, the mechanism by which they discover and utilize external software tools has become a critical area of research. A new study authored by Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang, and Michael Xu sheds light on this challenge, offering a deep dive into how tool-augmented LLM agents discover relevant Application Programming Interfaces (APIs) from massive registries before planning execution.

Tool-augmented LLM agents rely heavily on external registries to solve specialized problems, retrieve real-time data, and interact with software ecosystems. However, a fundamental engineering constraint stands in the way of seamless integration: finite context windows prohibit developers from injecting thousands of tool definitions into a single prompt. To bypass this limitation, agent architectures must dynamically retrieve a small, relevant subset of tools tailored to the user’s immediate request.

The research paper investigates the mechanics of this selection process, contrasting the dominant industry standard with an alternative paradigm. By evaluating these methodologies across thousands of unique API endpoints and diverse query complexities, the researchers have uncovered a striking complexity-dependent crossover that could shape the next generation of AI agent design.

The Battle of Paradigms: Retrieve-then-Plan versus Plan-then-Retrieve

The prevailing methodology in the field is known as Retrieve-then-Plan, or RtP. In this standard workflow, the system takes the raw user query, embeds it into a vector space, and queries a large registry using approximate nearest-neighbor search. The top-matching tools returned by this search are then injected into the LLM prompt, allowing the model to formulate an execution plan. While intuitive and direct, RtP treats the initial search as a purely semantic matching problem between the user’s literal prompt and the documentation of available tools.

To test the limitations of this approach, the authors studied an alternative paradigm known as Plan-then-Retrieve, or PtR. In the PtR framework, the sequence is inverted. Rather than searching the registry immediately with the raw user query, the LLM first analyzes the user’s intent and generates what the researchers call Abstract Tool Stubs. These stubs are hypothesized function signatures that describe the specific capabilities needed to solve the task. Once generated, these conceptual function signatures serve as the retrieval queries against the API registry, rather than the original user prompt.

To rigorously evaluate how these two paradigms stack up against one another, the research team tested them on ToolBench, a comprehensive benchmark featuring 46,984 unique API endpoints distributed across 50 distinct categories. The evaluation was split into three granular query subsets designed to test scaling difficulty: single-tool queries, denoted as G1; intra-category multi-tool queries, denoted as G2; and cross-category multi-tool queries, denoted as G3.

The experimental results revealed a clear and consistent complexity-dependent crossover between the two approaches. RtP consistently outperforms PtR on single-tool queries, where direct semantic matching between the user’s request and the correct API signature is straightforward. Conversely, PtR outperforms RtP when dealing with multi-tool queries, where a single user prompt requires orchestrating multiple functional steps across different software services.

According to the study, this crossover holds firm across every tested retrieval budget—ranging from retrieving just one top candidate up to twenty—and remains robust across registry scales ranging from 1,000 to nearly 47,000 APIs. Furthermore, the findings are consistent across different model families, verified using both Gemini 2.5 Flash and gpt-oss-120b.

Understanding Stub Hallucination and Token Overhead

A significant contribution of the research is its granular characterization of a phenomenon the authors term "stub-hallucination"—a failure mode where the LLM invents plausible-sounding but entirely non-existent API names during the planning phase of the PtR process.

Interestingly, the researchers discovered that stub-hallucination acts as a double-edged sword within the agent pipeline. On simple queries, PtR’s generated stubs tend to abstract away proper-noun signals and specific terminology that RtP can otherwise match directly, leading to suboptimal retrieval performance. In these simpler scenarios, the intermediary step of generating hypothetical function signatures introduces unnecessary noise and abstraction.

However, on complex queries, that exact same hallucination and abstraction mechanism becomes an asset. It allows the LLM to decompose a multi-faceted, high-level intent into distinct functional sub-needs, effectively breaking a complex software integration problem into modular components before searching the registry. This decomposition helps the retrieval mechanism locate relevant tools that might not share direct literal keywords with the original, overarching user prompt.

Beyond retrieval accuracy, the study also addresses the pragmatic realities of inference cost and token overhead. The researchers note that PtR’s extra discovery call roughly doubles the inference cost compared to the single-step RtP approach. While this added expenditure easily pays off on complex, multi-tool queries where precision is paramount, it represents an inefficient use of resources when handling straightforward, single-tool requests.

This economic trade-off points directly toward a practical engineering solution: complexity-adaptive routing. By dynamically switching between RtP and PtR depending on the estimated difficulty of the user’s request, developers can optimize both performance and token expenditure. Crucially, the study points out that such a routing mechanism can be driven by a zero-cost signal already present natively within the pipeline—specifically, the top-1 retrieval score generated during the initial RtP pass.

As the AI research community continues to refine autonomous agent architectures for enterprise and consumer applications, findings from studies like this provide vital empirical guidance for balancing computational efficiency with execution reliability.