Retrieval vs. Planning: New Study Reveals Complexity-Dependent Crossover in Tool-Augmented LLM Agents

As large language models increasingly evolve from conversational chatbots into autonomous agents capable of interacting with external software, the mechanics of how these systems discover and utilize tools have 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 a fundamental architectural question in tool-augmented LLM systems: whether an agent should retrieve available tools before planning its execution, or plan its approach before attempting to retrieve the necessary resources.

Tool-augmented LLM agents rely heavily on discovering relevant Application Programming Interfaces from massive registries before they can plan and execute complex workflows. However, this capability faces a fundamental engineering bottleneck. Because finite context windows prohibit developers from injecting thousands of tool definitions into a single system prompt, agents must selectively retrieve only the most pertinent APIs for a given user request.

The research team examines the limitations and advantages of two distinct paradigms for this crucial discovery phase. The dominant approach in contemporary AI engineering is termed Retrieve-then-Plan, commonly referred to as RtP. In this traditional pipeline, the system embeds the raw user query and retrieves similar tools by performing an approximate nearest-neighbor search against an API registry.

While straightforward, this methodology assumes that a user’s initial query contains all the necessary semantic signals to locate the exact tools required for the task. To test alternative configurations, the researchers studied a contrasting workflow known as Plan-then-Retrieve, or PtR. In this inverted paradigm, the LLM first generates what the authors describe as Abstract Tool Stubs. These are hypothesized function signatures that explicitly describe the functional capabilities required to solve the user’s problem. Once generated, these conceptual stubs serve as the retrieval queries against the underlying API registry, rather than the raw user prompt itself.

To evaluate the comparative strengths of both paradigms, the authors conducted a rigorous empirical evaluation using ToolBench, a comprehensive benchmark comprising nearly 47,000 unique API endpoints spanning 50 distinct categories. The evaluation framework tested both pipelines across three distinct query subsets: single-tool tasks, intra-category multi-tool tasks where multiple APIs from the same domain are required, and complex cross-category multi-tool tasks.

The experimental results uncovered a clear, complexity-dependent crossover between the two methodologies. The data shows that the traditional Retrieve-then-Plan approach consistently outperforms Plan-then-Retrieve on single-tool queries. When a task requires only one straightforward API call, skipping the intermediate planning step and querying the registry directly with the user prompt proves to be the more efficient and accurate strategy.

Conversely, the study reveals that the Plan-then-Retrieve paradigm decisively outperforms RtP as the complexity of the user request scales upward into multi-tool territory. When an agent faces multifaceted problems requiring coordination across multiple APIs—especially those spanning different functional categories—generating abstract tool stubs first allows the model to effectively decompose a complex intent into discrete functional sub-needs before searching the registry.

Crucially, the research demonstrates that this performance crossover is remarkably robust. The complexity-dependent shift holds true across every evaluated retrieval budget, tested from a narrow window of the top single result up to twenty retrieved candidates. Furthermore, the crossover remains consistent across varying registry scales—from compact registries containing one thousand APIs up to the full scale of nearly 47,000 endpoints—and proves invariant across different major model families, including Gemini 2.5 Flash and gpt-oss-120b.

A significant contribution of the new study is its detailed characterization of a specific failure mode intrinsic to the PtR pipeline, known as stub hallucination. In this phenomenon, the LLM invents plausible-sounding but entirely non-existent API names and signatures during the initial planning phase. The researchers identify this characteristic as a double-edged sword for the architecture. On simple queries, the hallucination of abstract stubs strips away proper-noun signals and exact keywords that the RtP approach would otherwise match directly against the registry, leading to degraded performance. However, on complex queries, this exact mechanism aids the agent by decomposing a tangled, multi-faceted user intent into structured functional requirements that abstract away irrelevant noise.

The authors also performed a rigorous token overhead analysis to understand the economic and computational trade-offs of the two architectures. They revealed that the Plan-then-Retrieve paradigm requires an extra discovery call that roughly doubles the inference cost of the pipeline. For multi-tool queries, this added computational expenditure is a worthwhile investment that pays off in higher task success rates. For simple, single-tool queries, however, the extra inference cost is unjustified and hurts overall efficiency.

These economic and performance findings point toward practical future directions in agent design, most notably the implementation of complexity-adaptive routing. The authors suggest that systems could dynamically choose between RtP and PtR depending on the nature of the incoming request. Furthermore, this adaptive routing decision could be driven by a zero-cost signal already natively present in the standard execution pipeline: the top-1 retrieval score generated during an initial RtP pass.

As the deployment of autonomous LLM agents scales across enterprise and consumer applications, optimizing the delicate balance between retrieval efficiency and planning depth remains a vital area of study for improving both the reliability and cost-effectiveness of AI systems.