Rethinking API Retrieval for LLM Agents: New Study Reveals Complexity-Dependent Crossover Between Paradigms

As Large Language Models (LLMs) increasingly transition from conversational chat interfaces 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 addresses a fundamental bottleneck in tool-augmented LLM architectures: how agents navigate massive application programming interface (API) registries when finite context windows prohibit injecting every available tool definition into a single prompt.

The research investigates a central architectural question in tool retrieval, comparing the dominant paradigm against an alternative approach. Through rigorous evaluation across extensive datasets, the authors uncover a distinct complexity-dependent crossover between the two methods, offering new insights that could fundamentally shape the design of future agentic frameworks and inference cost optimization strategies.

The Context Window Dilemma and the Rise of Tool Retrieval

Modern LLM agents frequently rely on external tools—ranging from weather databases and financial calculators to specialized enterprise software functions—to accomplish user goals. However, as enterprise registries grow to encompass tens of thousands of unique API endpoints, including them all within a single prompt is rendered impossible by finite context window constraints and the degradation of model attention over excessively long inputs.

To solve this, tool-augmented systems typically employ a retrieval phase. The dominant paradigm in the field, which the authors term Retrieve-then-Plan (RtP), operates by embedding the raw user query and subsequently retrieving similar tools from a registry via approximate nearest-neighbor search. While efficient for straightforward requests, this direct retrieval approach lacks the structural flexibility required when user intents are nuanced, multi-faceted, or require distinct operational steps.

Seeking an alternative, the researchers study a paradigm known as Plan-then-Retrieve (PtR). In this inverted workflow, the LLM first generates what the authors call Abstract Tool Stubs—hypothesized function signatures that describe the specific functional capabilities needed to solve the user’s problem. These generated stubs then serve as the actual retrieval queries against the API registry, rather than the raw user prompt itself.

Empirical Evaluation Across ToolBench Categories

To rigorously test these competing paradigms, the authors conducted evaluations on ToolBench, a comprehensive benchmark featuring 46,984 unique API endpoints spanning 50 distinct categories. The study broke down performance across three core query subsets to isolate how task complexity impacts retrieval efficacy: single-tool queries (G1), intra-category multi-tool queries (G2), and cross-category multi-tool queries (G3).

The findings reveal a clear and consistent complexity-dependent crossover between the two methods. Retrieve-then-Plan (RtP) outperforms Plan-then-Retrieve (PtR) when handling single-tool queries. When a user requests a straightforward action that maps directly to a single, easily identifiable API, the additional planning step in PtR introduces unnecessary overhead and potential points of failure.

Conversely, the study demonstrates that PtR significantly outperforms RtP when dealing with multi-faceted, multi-tool queries. By decomposing a complex intent into functional sub-needs via abstract stubs, the model can more accurately target disparate or specialized tools that a direct nearest-neighbor search of the raw user prompt might overlook or conflate.

Crucially, the authors established that this crossover phenomenon is remarkably robust. The pattern holds at every retrieval budget tested—ranging from $k = 1$ to $k = 20$ retrieved items—and remains consistent across varying registry scales, from compact environments of 1,000 APIs up to the full 47,000-API registry. Furthermore, the crossover behavior was validated across different model families, including Gemini 2.5 Flash and gpt-oss-120b, indicating that the dynamic is an inherent property of the retrieval paradigms rather than an artifact of a specific LLM architecture.

Characterizing Stub Hallucination and Token Overhead

A significant contribution of the research is the detailed characterization of a specific failure mode intrinsic to the PtR approach: stub hallucination. During the initial planning phase, the LLM frequently invents plausible-looking but entirely non-existent API names and signatures.

The researchers discovered that this hallucination acts as a double-edged sword. On simple queries, PtR’s generated stubs tend to abstract away proper-noun signals and exact terminology that RtP matches directly against the registry, leading to degraded performance. However, on complex queries, that same generative mechanism functions as an asset, successfully decomposing a convoluted, multi-faceted user intent into distinct functional sub-needs that improve the subsequent retrieval of relevant tools.

Beyond accuracy, the study provides a thorough economic analysis of token overhead. Because the Plan-then-Retrieve paradigm requires an extra discovery and planning call before the final execution phase, it roughly doubles the inference cost compared to direct retrieval. While this added computational expenditure easily pays dividends on complex, multi-tool queries where higher accuracy is paramount, it represents an unnecessary financial and latency penalty when applied to simple, single-tool tasks.

Implications for Complexity-Adaptive Routing

These insights point toward a practical direction for future agent design: complexity-adaptive routing. By dynamically selecting whether to use Retrieve-then-Plan or Plan-then-Retrieve based on the characteristics of the incoming request, systems can maximize task success rates while minimizing unnecessary inference costs.

Notably, the authors suggest that such an adaptive routing mechanism can be driven by a zero-cost signal already natively present within the standard pipeline: the top-1 retrieval score generated during the initial RtP phase. By evaluating the confidence score of the first retrieved result, an orchestration layer can instantly determine whether a query is straightforward enough to resolve immediately or sufficiently complex to justify escalating to a full Plan-then-Retrieve workflow.