Rethinking Tool Retrieval for LLM Agents: New Study Reveals Complexity-Dependent Crossover Between Retrieval Paradigms

As Large Language Models (LLMs) increasingly transition from conversational chat interfaces to autonomous agents capable of executing complex workflows, their reliance on external APIs has grown exponentially. Modern tool-augmented LLM agents must navigate vast digital landscapes, discovering and utilizing relevant APIs from massive registries before they can even begin planning their execution. However, a fundamental bottleneck stands in the way: finite context windows prohibit developers from injecting thousands of tool definitions into a single system prompt.

To solve this challenge, artificial intelligence researchers have long relied on a dominant paradigm known as Retrieve-then-Plan, or RtP. In this traditional setup, a user query is directly embedded into a vector space, and the system retrieves similar tools via approximate nearest-neighbor searches against a registry. But is this direct approach always the most effective strategy? A new study authored by Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang, and Michael Xu explores an alternative paradigm called Plan-then-Retrieve, or PtR, offering fresh insights into how LLM agents discover and utilize tools.

The research team set out to rigorously evaluate the performance differences between the established Retrieve-then-Plan approach and the alternative Plan-then-Retrieve strategy. In the PtR paradigm, the LLM takes a different route: instead of searching the registry immediately with the raw user query, the model first generates what the researchers call Abstract Tool Stubs. These are essentially hypothesized function signatures that describe the specific capabilities needed to accomplish the task. Once generated, these stubs serve as the retrieval queries used to search the tool registry, bridging the gap between raw human intent and structured API specifications.

To test these paradigms under realistic conditions, the researchers turned to ToolBench, a comprehensive benchmark containing 46,984 unique API endpoints categorized across 50 distinct domains. They evaluated both approaches across three specific query subsets designed to test varying degrees of task complexity: single-tool queries, classified as G1; intra-category multi-tool queries, classified as G2; and cross-category multi-tool queries, classified as G3.

The evaluation revealed a clear, complexity-dependent crossover between the two methods. According to the findings, RtP outperforms PtR when handling straightforward, single-tool queries. However, the dynamic shifts entirely when tasks become more intricate, with PtR outperforming RtP on multi-tool queries. This performance crossover is remarkably robust. The researchers found that it holds true across every retrieval budget tested—ranging from a retrieval count of $k=1$ up to $k=20$—and remains consistent across varying registry sizes scaling from 1,000 to 47,000 APIs. Furthermore, the crossover effect transcends specific underlying architectures, proving consistent across major model families including Gemini 2.5 Flash and gpt-oss-120b.

To understand why this crossover occurs, the study dives deeply into the behavioral mechanics of the LLMs, identifying a distinct failure mode dubbed "stub-hallucination." When utilizing the Plan-then-Retrieve paradigm, the LLM occasionally invents plausible-sounding but entirely non-existent API names and function structures. Interestingly, the researchers discovered that this hallucination tendency acts as a double-edged sword.

On simple queries, PtR’s generated stubs inadvertently abstract away crucial proper-noun signals that the traditional RtP approach would normally match directly and accurately, leading to poorer performance for PtR on basic tasks. Yet, on complex queries, that very same hallucination and abstraction mechanism serves a vital function. It successfully decomposes a multifaceted user intent into discrete functional sub-needs, allowing the agent to target diverse aspects of a complex problem that a single direct query might miss.

The study also addresses the pragmatic realities of computational overhead. Analyzing token consumption, the researchers demonstrated that PtR’s extra discovery call roughly doubles the overall inference cost of the pipeline. While this added expenditure easily pays off on complex, multi-tool queries where thorough discovery is critical, it becomes an unnecessary tax that hurts efficiency on simple, single-tool tasks.

These findings point toward a practical forward direction for agent architecture design: complexity-adaptive routing. By dynamically routing queries based on estimated task difficulty, systems could employ the lightweight Retrieve-then-Plan method for simple tasks and reserve the more thorough Plan-then-Retrieve paradigm for complex multi-tool challenges. Crucially, the research suggests that this routing decision does not require an expensive auxiliary classifier. Instead, it can be driven naturally by a zero-cost signal already present within the standard pipeline—specifically, the top-1 retrieval score generated during the initial steps of the RtP process.