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

As large language models (LLMs) evolve from simple conversational interfaces into autonomous agents capable of complex multi-step workflows, the mechanism by which they discover and utilize external software tools has become a critical bottleneck. A new study authored by Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang, and Michael Xu investigates this challenge, shedding light on how tool-augmented LLM agents interact with massive API registries. Their findings reveal a distinct complexity-dependent crossover between two competing paradigms for tool discovery, offering valuable insights for the future architecture of AI agent systems.

The core challenge in tool-augmented generation stems from a fundamental architectural limitation: finite context windows. Modern enterprise ecosystems and public repositories feature tens of thousands of individual application programming interfaces (APIs). Because it is computationally and structurally impossible to inject all available tool definitions into a single prompt without overwhelming the context window, agents must rely on external retrieval mechanisms to find relevant capabilities before planning their execution steps.

To address this, the artificial intelligence research community has predominantly relied on an approach the authors term Retrieve-then-Plan (RtP). In this traditional paradigm, the system embeds the raw user query and subsequently retrieves similar tools from a registry via approximate nearest-neighbor search. While efficient for straightforward tasks, RtP assumes that the user’s initial prompt explicitly or implicitly contains the precise semantic markers needed to match the correct API signatures in the database.

Seeking to evaluate alternative architectures, the researchers studied a contrasting paradigm known as Plan-then-Retrieve (PtR). In the PtR framework, the LLM does not immediately search the database using the raw user query. Instead, the model first generates what the researchers call Abstract Tool Stubs—hypothesized function signatures that describe the specific capabilities needed to solve the problem. These generated stubs are then utilized as the retrieval queries against the API registry, bridging the gap between abstract user intent and concrete technical endpoints.

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

The empirical results uncovered a clear complexity-dependent crossover between the two strategies. According to the study, RtP outperforms PtR when handling single-tool queries, where direct semantic matching of the user prompt is often sufficient to locate the correct API. However, the dynamics shift significantly as complexity increases. PtR outperforms RtP when handling multi-tool queries, proving superior at breaking down multifaceted requests into discrete functional components.

Further analysis demonstrated that this crossover effect is remarkably resilient. The performance crossover holds true across every tested retrieval budget, spanning from a tight constraint of a single retrieved item up to twenty items. Furthermore, the findings remain robust across varying registry scales, maintaining their consistency in environments containing anywhere from 1k to 47k APIs. The researchers also confirmed that this behavioral pattern is consistent across different model families, verifying their results using both Gemini 2.5 Flash and gpt-oss-120b.

A deeper examination of the mechanisms at play revealed a fascinating behavioral characteristic of the PtR paradigm: stub-hallucination. In this failure mode, the LLM invents plausible-sounding but non-existent API names during the planning phase. The researchers characterize this phenomenon as a double-edged sword. On simple queries, PtR’s generated stubs tend to abstract away proper-noun signals that RtP would otherwise match directly, causing unnecessary friction and lower accuracy. Conversely, on complex queries, that same hallucination and abstraction mechanism acts as a constructive decomposition tool, breaking down a complex, multi-faceted user intent into manageable functional sub-needs that can successfully unearth relevant tools from the registry.

The study also addressed the computational and economic trade-offs associated with these paradigms by analyzing token overhead. The extra discovery call required by the PtR approach roughly doubles the overall inference cost compared to traditional single-step retrieval. While this additional expenditure easily pays off in multi-tool queries where comprehensive exploration is required, it represents an unnecessary financial and computational penalty when applied to straightforward, single-tool tasks.

These cost and performance dynamics point toward complexity-adaptive routing as a highly practical direction for future AI system design. The authors suggest that systems could dynamically choose between RtP and PtR based on the complexity of the incoming request. Intriguingly, this routing decision can be driven by a zero-cost signal already natively present in standard pipelines: the top-1 retrieval score generated during the initial phase of an RtP search. By leveraging this existing metric, agent frameworks could intelligently switch strategies on the fly, optimizing both accuracy and token efficiency without incurring additional computational overhead.