Comparative Study of Tool-Augmented LLM Paradigms Reveals Complexity-Dependent Crossover Between Retrieval-First and Planning-First Strategies

As Large Language Models (LLMs) evolve from conversational chat interfaces into autonomous agents capable of complex workflows, they increasingly rely on external application programming interfaces (APIs) to interact with the digital world. A central challenge in this domain is tool retrieval: finding the right API from massive registries containing tens of thousands of endpoints when finite context windows make it impossible to inject every tool definition into a single prompt.

A new research paper authored by Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang, and Michael Xu investigates this critical bottleneck. The researchers evaluate two contrasting paradigms for tool-augmented LLM agents: the dominant Retrieve-then-Plan approach and an alternative Plan-then-Retrieve strategy. Their findings uncover a clear complexity-dependent crossover between the two methods, offering new insights for the design of efficient, scalable AI agent architectures.

The standard industry paradigm, termed Retrieve-then-Plan, embeds a user’s natural language query and directly queries a massive API registry using approximate nearest-neighbor search to pull the most similar tool definitions before the LLM begins its execution phase. While straightforward, this method assumes that a user’s initial prompt contains all the necessary semantic signals to match the exact functions required for the task.

In contrast, the research team studied an alternative Plan-then-Retrieve paradigm. In this workflow, the LLM first analyzes the user request and generates what the authors call Abstract Tool Stubs—hypothesized function signatures that describe the needed capabilities. These generated stubs are then used as retrieval queries to search the API registry.

To rigorously test both paradigms, the researchers evaluated them on ToolBench, a comprehensive benchmark featuring 46,984 unique API endpoints distributed across 50 distinct categories. The evaluation spanned three core query subsets representing escalating degrees of task complexity: single-tool queries, intra-category multi-tool queries, and cross-category multi-tool queries.

The evaluation revealed a distinct complexity-dependent crossover in performance. Retrieve-then-Plan outperformed Plan-then-Retrieve on simple, single-tool queries. However, the performance dynamic inverted as task complexity increased, with Plan-then-Retrieve outperforming Retrieve-then-Plan on multi-tool queries.

Crucially, the researchers found that this crossover phenomenon is remarkably robust. It holds steady across every tested retrieval budget, ranging from a top-k value of 1 to 20. Furthermore, the crossover remains consistent across varying registry scales—from compact registries containing 1,000 APIs up to the full scale of nearly 47,000 endpoints—and proves resilient across different foundational model families, including Gemini 2.5 Flash and gpt-oss-120b.

To understand why this performance shift occurs, the authors closely examined the underlying mechanics and identified a specific failure mode they call stub-hallucination. During the planning phase of the Plan-then-Retrieve approach, the LLM occasionally invents plausible-sounding but entirely non-existent API names and structures.

The researchers characterize this phenomenon as a double-edged sword. On simple, straightforward queries, Plan-then-Retrieve’s generated stubs inadvertently abstract away proper-noun signals and exact keywords that the Retrieve-then-Plan method can match directly against the registry. This unnecessary layer of abstraction leads to a performance penalty for single-tool tasks. Conversely, on complex queries, that exact same generative mechanism acts as an analytical filter, effectively decomposing a multifaceted user intent into discrete, functional sub-needs that improve the subsequent retrieval of diverse tools.

Beyond raw accuracy, the study also analyzed the computational and token overhead associated with each paradigm. The researchers demonstrated that the additional discovery and planning call required by the Plan-then-Retrieve approach roughly doubles the overall inference cost. For complex, multi-tool queries, this investment pays off through higher retrieval precision and successful task execution. For simpler, single-tool queries, however, the doubled inference cost becomes an inefficient overhead.

This economic trade-off points toward a practical engineering solution: complexity-adaptive routing. By dynamically routing user queries based on task complexity, systems could harness the speed and efficiency of Retrieve-then-Plan for simple tasks while deploying Plan-then-Retrieve only when multi-tool coordination is required.

Significantly, the authors suggest that implementing such adaptive routing does not require complex classification models. Instead, it can be driven by a zero-cost signal already natively present within the standard pipeline: the top-1 retrieval score generated during the initial Retrieve-then-Plan phase. This signal could serve as an effective indicator of query ambiguity and complexity, guiding the system on whether an advanced planning phase is necessary.

As the AI community continues to refine tool-augmented agents for enterprise automation, software engineering, and complex digital workflows, these insights into retrieval dynamics highlight the limitations of treating tool selection as a one-size-fits-all problem. Balancing computational efficiency with multi-step reasoning capabilities will remain a central design consideration for next-generation AI systems.