Rethinking Tool Retrieval for LLM Agents: A Complexity-Dependent Crossover Between Retrieval-then-Plan and Plan-then-Retrieve Paradigms

As Large Language Models (LLMs) increasingly transition from conversational assistants to 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 newly released study by researchers Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang, and Michael Xu investigates the fundamental architectural trade-offs in tool-augmented LLM systems, revealing a critical complexity-dependent crossover in how agents locate relevant software tools within massive registries.

Tool-augmented LLM agents rely heavily on external registries to discover relevant APIs before planning execution. However, finite context windows strictly prohibit injecting thousands of tool definitions into a single prompt. To circumvent this limitation, developers have traditionally relied on an approach known as Retrieve-then-Plan, or RtP. In the standard RtP paradigm, the system embeds the raw user query and retrieves similar tools using approximate nearest-neighbor search algorithms. While effective for straightforward tasks, this method encounters severe bottlenecks when handling multi-faceted user requests that span diverse functional domains.

Seeking to overcome these limitations, the research team studied an alternative paradigm known as Plan-then-Retrieve, or PtR. In this inverted architecture, the LLM first generates Abstract Tool Stubs—hypothesized function signatures that describe the specific capabilities needed to solve the user’s problem. These generated stubs then serve as the retrieval queries against the API registry, rather than the original user prompt.

To rigorously evaluate the efficacy of these two competing paradigms, the authors tested both approaches on the ToolBench benchmark, a comprehensive evaluation suite encompassing 46,984 unique API endpoints distributed across 50 distinct functional categories. The evaluation framework was divided into three distinct query subsets to measure performance across varying degrees of complexity: single-tool queries, denoted as G1; intra-category multi-tool queries, designated as G2; and cross-category multi-tool queries, categorized as G3.

The empirical findings reveal a clear and consistent complexity-dependent crossover between the two paradigms. Specifically, the researchers discovered that the traditional Retrieve-then-Plan approach outperforms Plan-then-Retrieve on single-tool queries. Conversely, the Plan-then-Retrieve paradigm decisively outperforms RtP when handling complex, multi-tool queries.

Crucially, this performance crossover proved remarkably robust. The pattern holds true at every tested retrieval budget, spanning values of $k$ from 1 to 20. Furthermore, the crossover remains consistent across varying registry scales, maintaining its validity from compact registries containing 1,000 APIs up to massive environments housing nearly 47,000 endpoints. The architectural behavior was also tested across diverse foundational model families, demonstrating consistency when utilizing both Gemini 2.5 Flash and gpt-oss-120b.

To understand the underlying mechanisms driving these performance differences, the authors closely examined a specific failure mode characteristic of the PtR approach, which they term stub-hallucination. In this phenomenon, the LLM invents plausible but non-existent API names and signatures during the initial planning phase. The researchers characterize this behavior as a double-edged sword. On simple queries, PtR’s generated stubs inadvertently abstract away proper-noun signals and exact keywords that RtP can match directly, leading to degraded performance. However, on complex queries, this exact same generative mechanism acts as a powerful decomposition tool, breaking down a multifaceted user intent into discrete functional sub-needs that successfully capture nuanced requirements.

Beyond raw task success rates, the study provides a detailed analysis of token overhead and computational economics. The research demonstrates that PtR’s mandatory extra discovery call roughly doubles the inference cost of the pipeline. While this added expense easily pays off on complex multi-tool queries where precise capability decomposition is paramount, it unnecessarily inflates costs and degrades efficiency on straightforward single-tool interactions.

This economic trade-off points toward a practical architectural solution: complexity-adaptive routing. By dynamically directing queries to either RtP or PtR based on the estimated complexity of the task, systems can capture the best of both worlds. Notably, the authors observe that such adaptive routing can be driven by a zero-cost signal already natively present in the standard pipeline—specifically, the top-1 retrieval score generated during the initial phase of the Retrieve-then-Plan approach.

Related readings and updates within the broader research community further contextualize these findings. Large Language Models are increasingly employed for complex multi-step planning tasks, where the Tool Retrieval step is widely recognized as crucial for achieving successful outcomes. Two prevalent approaches for tool retrieval have historically included single-step retrieval, which utilizes the complete query, and sequential retrieval using Task Decomposition, where a full query is segmented into discrete atomic subtasks. While single-step retrieval lacks the flexibility to handle intricate dependencies, sequential methods offer structured progression at the cost of higher latency and overhead.

Contextualizing these developments within academic discourse, research exploring similar optimization challenges has gained significant traction at specialized AI forums. For instance, related work addressing retrieval-augmented generation constraints was accepted and presented at the UncertaiNLP workshop at EACL. While LLMs possess the remarkable ability to solve novel tasks with minimal examples, their success fundamentally depends on accessing the correct tools. Retrieval-Augmented Generation addresses this problem by fetching a list of relevant tools for a given task, but traditional RAG tool retrieval steps historically required all necessary information to be explicitly present in the initial user query, highlighting the ongoing necessity for advanced paradigms like those evaluated in the new study.