Deciding When to Plan or Retrieve: New Study Reveals Complexity-Dependent Crossover in Tool-Augmented LLM Agents

As Large Language Models (LLMs) increasingly transition from simple text generators into autonomous agents capable of complex reasoning and execution, the methods they use to interact with external software ecosystems are coming under intense academic scrutiny. A team of researchers—comprising Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang, and Michael Xu—has released a comprehensive study examining how tool-augmented LLM agents discover and select relevant application programming interfaces (APIs) from massive software registries before planning their execution steps.

The core challenge facing modern AI agents lies in the fundamental limitations of finite context windows. Modern enterprise software registries and digital marketplaces often house tens of thousands of unique API endpoints spanning dozens of distinct categories. Because an LLM cannot ingest the complete definitions of thousands of tools into a single prompt without hitting token limits or diluting its attention mechanisms, agents must rely on intelligent tool retrieval systems to surface only the most relevant capabilities for a given user query.

For the artificial intelligence research community, understanding the optimal architecture for this retrieval phase has become a central priority. The new research paper investigates a critical structural dichotomy in how agents discover these tools, offering fresh empirical insights that could reshape the design of next-generation AI agent frameworks.

Exploring the Paradigm Shift: Retrieve-then-Plan Versus Plan-then-Retrieve

To understand the scope of the study, it is necessary to examine the two primary paradigms governing tool-augmented generation. The dominant methodology in the field is known as Retrieve-then-Plan, or RtP. Under this conventional approach, the system takes the raw user query, embeds it into a vector space, and searches a massive repository via approximate nearest-neighbor search. This surfaces a targeted subset of tool definitions, which are then injected into the LLM’s prompt so the model can plan its execution strategy.

While RtP has served as the industry standard for numerous applications, the authors investigate an alternative methodology: Plan-then-Retrieve, or PtR. In this inverted paradigm, the LLM is first prompted to analyze the user’s intent and generate what the researchers call Abstract Tool Stubs. These stubs function as hypothesized function signatures that describe the specific capabilities needed to solve the problem, completely detached from the rigid, pre-existing proper nouns of actual APIs. These generated stubs then serve as the retrieval queries against the primary API registry.

To rigorously test these competing approaches, the research team conducted exhaustive evaluations using ToolBench, a prominent benchmark featuring 46,984 unique API endpoints distributed across 50 distinct functional categories. The experiments systematically divided test queries into three specific complexity subsets: single-tool queries, intra-category multi-tool queries, and cross-category multi-tool queries.

The empirical results reveal a clear, undeniable complexity-dependent crossover between the two paradigms. According to the findings, the traditional Retrieve-then-Plan approach consistently outperforms Plan-then-Retrieve when handling simple, single-tool queries. However, the dynamics shift dramatically as task complexity increases; PtR clearly outperforms RtP when dealing with intricate, multi-tool queries that require multifaceted problem decomposition.

Robustness Across Budgets, Scales, and Model Families

The significance of the crossover finding is further underscored by its remarkable resilience across multiple experimental dimensions. The researchers tested the paradigms across varying retrieval budgets, adjusting the number of retrieved items from a tight constraint of $k = 1$ all the way up to $k = 20$. Across every budget level tested, the performance crossover between single-tool and multi-tool queries remained entirely consistent.

Furthermore, the study verified that this behavioral crossover is not an artifact of small-scale testing. The researchers scaled the registry sizes from 1,000 APIs up to the full 47,000-API collection, observing the same fundamental performance dynamics. To ensure that the conclusions were not tied to the architectural quirks of a single proprietary or open-weights model, the team evaluated the framework using different advanced model families, specifically testing Gemini 2.5 Flash and gpt-oss-120b. The consistency of the results across diverse foundational models suggests that the performance trade-offs stem from inherent structural properties of the retrieval paradigms rather than model-specific idiosyncrasies.

A closer look at the mechanics of Plan-then-Retrieve revealed a fascinating failure mode that the authors describe as a double-edged sword: stub hallucination. When generating Abstract Tool Stubs, the LLM occasionally invents plausible-sounding but entirely non-existent API names and structures. On simple queries, this phenomenon actively harms performance; the LLM’s generated stubs abstract away crucial proper-noun signals that the traditional RtP approach can match directly and efficiently against real database entries.

However, on complex, multi-faceted queries, this exact same hallucination mechanism transforms into a distinct operational advantage. By generating abstract stubs, the model effectively decomposes a complex, tangled user intent into distinct functional sub-needs, allowing the retrieval system to unearth relevant tools that might otherwise be missed by a direct keyword or vector search on the raw, unstructured prompt.

Token Overhead and the Path Toward Complexity-Adaptive Routing

Despite the functional advantages of Plan-then-Retrieve on complex tasks, efficiency remains a paramount concern in production environments. The authors analyzed the token overhead associated with both methodologies and discovered that PtR’s extra discovery call roughly doubles the total inference cost compared to standard RtP.

This added computational expense is a worthwhile investment when processing multi-tool queries, where the extra discovery step successfully unlocks the necessary capabilities. However, for simple, straightforward single-tool queries, the doubled inference cost represents pure waste, penalizing overall system efficiency without yielding any tangible performance gain.

This economic and performance trade-off naturally points toward complexity-adaptive routing as a highly practical direction for future agent design. Rather than forcing all incoming user queries down a single, rigid retrieval pipeline, an ideal system would dynamically route queries based on their inherent complexity.

Crucially, the research points out that such a routing mechanism does not require a heavy, separate classification model. A zero-cost signal already exists natively within the standard pipeline: the top-1 retrieval score produced during the initial stages of the Retrieve-then-Plan process. By monitoring this baseline score, agent architectures can dynamically decide whether to stick with efficient single-step retrieval or escalate to multi-step planning and retrieval strategies only when the task demands it.