New Study Reveals Complexity-Dependent Crossover in Tool-Augmented LLM Agents, Comparing Retrieve-then-Plan and Plan-then-Retrieve Paradigms

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 area of artificial intelligence research. A new study authored by Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang, and Michael Xu sheds light on this challenge, offering a deep dive into how tool-augmented LLM agents interact with massive API registries.

Tool-augmented agents must discover relevant application programming interfaces from large registries before they can plan and execute user requests. However, finite context windows strictly prohibit injecting thousands of tool definitions into a single model prompt. To navigate this limitation, the artificial intelligence community has largely relied on an approach the authors term Retrieve-then-Plan, commonly known as RtP. In this dominant paradigm, the system embeds the raw user query and retrieves similar tools through approximate nearest-neighbor search mechanisms.

Challenging this conventional wisdom, the researchers conducted a comprehensive study examining an alternative paradigm known as Plan-then-Retrieve, or PtR. In the PtR workflow, the LLM first generates abstract tool stubs—hypothesized function signatures that describe the 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 these two paradigms, the research team tested them on ToolBench, a massive benchmark encompassing 46,984 unique API endpoints distributed across 50 distinct categories. The evaluation was structured across three specific query subsets designed to test scaling complexity: single-tool queries, intra-category multi-tool queries, and cross-category multi-tool queries.

The findings reveal a clear and consistent complexity-dependent crossover between the two approaches. According to the study, the conventional Retrieve-then-Plan paradigm outperforms Plan-then-Retrieve when handling single-tool queries. Conversely, the Plan-then-Retrieve paradigm surpasses RtP when managing multi-tool queries that require a broader functional scope.

Crucially, the researchers discovered that this performance crossover is remarkably robust. The trend holds true across every retrieval budget tested, ranging from a budget of $k=1$ up to $k=20$. Furthermore, the crossover effect remains stable across varying registry sizes—scaling smoothly from 1,000 APIs up to the full catalog of nearly 47,000 APIs—and demonstrates consistency across different foundational model families, specifically being tested on Gemini 2.5 Flash and gpt-oss-120b.

A significant contribution of the new study is its detailed characterization of a specific failure mode identified as stub hallucination. This occurs when the LLM invents plausible-sounding but entirely non-existent API names during the planning phase. The authors characterize this phenomenon as a double-edged sword within the agentic workflow.

On simpler queries, the tendency of PtR to generate stubs acts as a hindrance by abstracting away proper-noun signals and specific naming conventions that the traditional RtP approach matches directly and efficiently. However, on more complex queries, this exact same hallucination and abstraction mechanism proves beneficial. It successfully decomposes a multifaceted user intent into discrete functional sub-needs, allowing the retrieval engine to locate relevant disparate tools that a direct text match would otherwise miss.

The study also delves into the operational economics of deploying these architectures by analyzing token overhead and computational costs. The researchers show that the additional discovery call required by the Plan-then-Retrieve paradigm roughly doubles the overall inference cost of the system. While this added expenditure easily pays off on complex multi-tool queries where comprehensive discovery is paramount, it introduces unnecessary latency and financial overhead on straightforward single-tool interactions.

These insights point toward a practical and efficient path forward for developers and researchers: complexity-adaptive routing. By dynamically directing queries to either the RtP or PtR pipeline based on the estimated complexity of the task, systems can optimize both accuracy and resource consumption. The authors note that such adaptive routing can even be driven by a zero-cost signal already readily present within the existing pipeline architecture—specifically, the top-1 retrieval score generated during the initial stages of the Retrieve-then-Plan process.

The implications of these findings contribute directly to the ongoing refinement of Retrieval-Augmented Generation architectures and agentic frameworks. As research into large language models continues to advance, understanding the precise trade-offs between direct text retrieval and task decomposition through tool stubs remains essential for building scalable, reliable, and cost-effective AI agents capable of navigating real-world digital ecosystems.