Beyond Retrieval-then-Plan: New Study Reveals Complexity-Dependent Crossover in Tool-Augmented LLM Agents

As Large Language Models (LLMs) transition from conversational assistants into autonomous agents capable of executing complex multi-step workflows, the mechanism by which they discover and utilize external application programming interfaces (APIs) has become a central focus of artificial intelligence research. A new study authored by Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang, and Michael Xu investigates the fundamental architectural trade-offs in tool-augmented LLM agents, offering fresh insights into how these systems interact with massive API registries.

Tool-augmented agents must discover relevant APIs from expansive registries before they can plan and execute a user’s request. However, finite context windows strictly prohibit injecting the definitions of thousands of tools into a single prompt. To solve this bottleneck, the field has predominantly relied on an approach known as Retrieve-then-Plan, or RtP. In this standard paradigm, the system embeds the raw user query and retrieves similar tools using approximate nearest-neighbor search algorithms before passing those tools to the LLM for execution planning.

Challenging the exclusivity of this standard method, the researchers conducted a comprehensive study examining an alternative paradigm called Plan-then-Retrieve, or PtR. In the PtR framework, the LLM first generates what the authors term Abstract Tool Stubs—hypothesized function signatures that describe the specific capabilities needed to solve the task. These generated stubs then serve as the retrieval queries against the API registry, rather than the original user text.

To evaluate the comparative strengths of RtP and PtR, the research team conducted large-scale experiments using the ToolBench benchmark, a comprehensive testing ground encompassing 46,984 unique API endpoints distributed across 50 distinct categories. The evaluation was structured across three core query subsets designed to test varying levels of complexity: single-tool queries, designated as G1; intra-category multi-tool queries, designated as G2; and cross-category multi-tool queries, designated as G3.

The empirical results revealed a clear, complexity-dependent crossover between the two paradigms. According to the study, RtP consistently outperforms PtR when handling simple, single-tool queries. When a user request maps directly to a single, easily identifiable API, the direct embedding approach of RtP is more efficient and accurate. However, the dynamics shift entirely when confronting multi-tool queries. For tasks requiring multiple APIs—whether within the same functional category or spanning across different categories—PtR outperforms RtP.

Crucially, the research demonstrates that this performance crossover is remarkably robust. The crossover holds steady at every tested retrieval budget, spanning from a modest retrieval parameter of $k=1$ up to $k=20$. Furthermore, the pattern remains consistent across varying registry scales, holding true whether the registry contains 1,000 APIs or the full dataset of 47,000 endpoints. The findings also prove resilient across different model families, verified using both Gemini 2.5 Flash and gpt-oss-120b architectures.

To understand why this performance split occurs, the authors closely examined the behavioral mechanics of the models, identifying a specific failure mode they term "stub-hallucination." In this phenomenon, the LLM invents plausible-sounding but non-existent API names when generating its abstract stubs. Interestingly, the researchers characterize this hallucination tendency as a double-edged sword.

On simple queries, PtR’s generated stubs inadvertently abstract away proper-noun signals that RtP is able to match directly and accurately, leading to poorer performance for the plan-first approach. Conversely, on complex queries, that exact same generative mechanism acts as a powerful asset. By breaking down a multifaceted user intent into functional sub-needs through hypothesized stubs, the model successfully decomposes complex problems into manageable retrieval targets that standard semantic search would otherwise miss.

The study further analyzes the computational trade-offs, specifically examining token overhead and inference costs. The authors show that PtR’s mandatory extra discovery call roughly doubles the overall inference cost of the pipeline. While this added expenditure pays off dividends on complex multi-tool queries where deeper decomposition is necessary, it introduces unnecessary latency and financial cost when applied to straightforward, single-tool tasks.

These findings point toward a practical architectural direction for future agent design: complexity-adaptive routing. By dynamically routing queries based on estimated complexity, systems could harness RtP for straightforward tasks and deploy PtR for complex multi-step challenges. Excitingly, the researchers note that such a routing mechanism does not require complex external classifiers. Instead, it can be driven by a zero-cost signal already natively present in the standard pipeline: RtP’s top-1 retrieval score.

As the deployment of autonomous LLM agents scales across enterprise and consumer applications, optimizing the delicate balance between discovery, planning, and computational overhead remains critical. This research provides a rigorous foundation for building more efficient, context-aware agent architectures capable of navigating massive software ecosystems with precision.