Beyond Retrieve-Then-Plan: New Study Reveals Complexity-Dependent Crossover in Tool-Augmented LLM Agents

As Large Language Models (LLMs) increasingly evolve from simple conversational interfaces into autonomous agents capable of complex multi-step reasoning, their utility relies heavily on their ability to interact with external software. Tool-augmented LLM agents discover relevant Application Programming Interfaces (APIs) from massive registries before planning execution. However, finite context windows strictly prohibit injecting thousands of tool definitions into a single prompt.

To address this fundamental limitation, researchers Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang, and Michael Xu have released a comprehensive study examining how agents discover and select tools. Their findings challenge the prevailing paradigm in AI system design, uncovering a distinct complexity-dependent crossover that could fundamentally reshape how developers build tool-using LLM architectures.

For years, the dominant approach in the field has been what the researchers term "Retrieve-then-Plan" (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 search before handing them over to the language model for execution planning. While effective for straightforward tasks, RtP struggles when user intents become multifaceted, requiring tools across entirely different functional domains.

Seeking an alternative, the research team investigated a paradigm known as "Plan-then-Retrieve" (PtR). In this inverted workflow, the LLM first generates Abstract Tool Stubs—hypothesized function signatures that describe the capabilities needed to solve the problem. These generated stubs then serve as the retrieval queries against the API registry, rather than the raw user prompt itself.

To rigorously test both paradigms, the researchers evaluated the frameworks on ToolBench, a massive benchmark comprising 46,984 unique API endpoints distributed across 50 distinct categories. The evaluation was categorized across three specific query subsets: single-tool tasks, intra-category multi-tool tasks, and cross-category multi-tool tasks.

The empirical results revealed a clear complexity-dependent crossover between the two approaches. Specifically, the researchers found that traditional Retrieve-then-Plan outperforms Plan-then-Retrieve on single-tool queries. When an agent only needs to find and execute a single, straightforward API, searching the registry directly using the user’s prompt is faster, more accurate, and less prone to intermediate errors.

However, the dynamic flips entirely when tasks grow in complexity. For multi-tool queries—particularly those spanning multiple functional categories—Plan-then-Retrieve consistently outperforms RtP. By decomposing a complex user request into abstract functional sub-needs before searching the registry, the LLM agent can bypass the semantic ambiguity of the initial prompt and target specialized APIs that a direct vector search would otherwise miss.

Crucially, the research team discovered that this performance crossover is remarkably robust. The trend holds steady across every retrieval budget tested, ranging from retrieving a single candidate tool up to twenty candidates. Furthermore, the crossover remains consistent across varying registry scales, from compact environments containing one thousand APIs up to the full scale of nearly 47,000 endpoints. The phenomenon is also model-agnostic, repeating reliably across different leading model families, including Gemini 2.5 Flash and gpt-oss-120b.

To better understand why PtR behaves the way it does, the study characterizes a specific failure mode termed "stub-hallucination," where the LLM invents plausible but entirely non-existent API names during the planning phase. Interestingly, the researchers found that this hallucination mechanism acts as a double-edged sword. On simple queries, PtR’s generated stubs inadvertently abstract away proper-noun signals that RtP’s direct search matches effortlessly, leading to degraded performance. Conversely, on complex queries, that exact same mechanism proves beneficial by decomposing a convoluted, multi-faceted human intent into structured functional sub-needs that map effectively to registry metadata.

Beyond accuracy and task complexity, the authors also analyzed the token overhead associated with each approach. They demonstrated that Plan-then-Retrieve requires an extra discovery call, which roughly doubles the overall inference cost of the interaction. For multi-tool queries, this added computational expense is well justified by the substantial boost in task success rates. For single-tool queries, however, the extra inference call introduces unnecessary latency and financial cost without delivering a performance advantage.

These insights point toward a practical path forward for AI engineers: complexity-adaptive routing. By dynamically switching between RtP and PtR depending on the nature of the incoming request, systems can capture the high accuracy of direct retrieval on simple tasks while leveraging the deep compositional power of task-first planning on complex workflows.

Significantly, the researchers noted that implementing such an adaptive router does not require an expensive classification model. Instead, the routing decision can be driven by a zero-cost signal already natively present in the standard pipeline: the top-1 retrieval score generated during an initial RtP pass. If the top match crosses a certain confidence threshold, the system can proceed with direct execution; if uncertainty is high, it can gracefully pivot to the Plan-then-Retrieve paradigm.

As the industry continues to push the boundaries of autonomous agent capabilities, findings from studies like this highlight the delicate balance required between computational efficiency, architectural design, and task complexity in modern artificial intelligence deployments.