New Research Reveals Complexity-Dependent Crossover Between Retrieval Strategies in Tool-Augmented LLM Agents

A new study by researchers Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang, and Michael Xu investigates the fundamental mechanics of tool-augmented Large Language Model (LLM) agents, shedding light on how these systems discover relevant Application Programming Interfaces (APIs) from massive registries before planning their execution. As artificial intelligence applications increasingly rely on external tools to solve intricate problems, the question of how to efficiently match user queries with the correct functions has become a central challenge in computer science and machine learning architecture.

Tool-augmented LLM agents operate in environments where finite context windows prohibit injecting thousands of tool definitions into a single prompt. Because modern registries can contain tens of thousands of unique API endpoints, agents must intelligently filter and retrieve only the most pertinent tools. In their new research, the authors examine the trade-offs between two distinct paradigms for tool retrieval: the dominant approach known as Retrieve-then-Plan, and an alternative approach known as Plan-then-Retrieve.

The dominant approach in the field, Retrieve-then-Plan, typically embeds the raw user query and retrieves similar tools by performing an approximate nearest-neighbor search against the registry. While efficient for straightforward tasks, this method relies entirely on the explicit keywords and semantic structures present in the initial user prompt. By contrast, the researchers studied the Plan-then-Retrieve paradigm, in which the LLM first generates what the authors term Abstract Tool Stubs. These stubs are hypothesized function signatures that describe the specific capabilities needed to address the user’s request, which then serve as the actual retrieval queries against the registry.

To rigorously evaluate these competing paradigms, the research team turned to ToolBench, a comprehensive benchmark containing 46,984 unique API endpoints distributed across 50 distinct categories. Their evaluation spanned three specific query subsets designed to test varying degrees of task complexity: single-tool queries, intra-category multi-tool queries, and cross-category multi-tool queries.

Through this extensive testing, the authors uncovered a clear complexity-dependent crossover between the two methodologies. Specifically, the data demonstrates that Retrieve-then-Plan outperforms Plan-then-Retrieve on single-tool queries, where direct semantic matching of the user’s explicit request proves most effective. However, the performance dynamic reverses as task complexity increases, with Plan-then-Retrieve outperforming Retrieve-then-Plan on multi-tool queries that require a broader synthesis of capabilities.

The significance of this crossover extends far beyond isolated test conditions. According to the study, this crossover holds steady across every tested retrieval budget, ranging from a retrieval count of one up to twenty. Furthermore, the findings are robust across varying registry scales, maintaining their consistency whether the registry contains one thousand or forty-seven thousand APIs. The research also confirms that this behavioral pattern is consistent across different model families, holding true for advanced architectures such as Gemini 2.5 Flash and gpt-oss-120b.

To understand why this performance shift occurs, the authors characterized a specific mechanism they call the stub-hallucination failure mode. In this scenario, the LLM invents plausible but non-existent API names during the planning phase. The researchers discovered that this phenomenon acts as a double-edged sword within the agent’s workflow. On simple queries, Plan-then-Retrieve’s stubs inadvertently abstract away proper-noun signals that Retrieve-then-Plan is able to match directly, leading to lower efficiency. Conversely, on complex queries, that exact same mechanism serves a vital function by decomposing a multi-faceted user intent into distinct functional sub-needs, allowing the retrieval system to unearth deeply relevant tools that a direct search might miss.

The study further delves into the operational costs associated with these strategies by analyzing token overhead. The authors show that Plan-then-Retrieve requires an extra discovery call that roughly doubles the overall inference cost. For multi-tool queries, this added investment pays off in terms of accuracy and successful execution. However, for simple, single-tool queries, the doubled inference cost becomes a distinct disadvantage, introducing unnecessary computational overhead without a corresponding benefit in output quality.

These insights point toward a practical and efficient direction for future agent architecture: complexity-adaptive routing. By dynamically shifting between Retrieve-then-Plan and Plan-then-Retrieve depending on the nature of the incoming request, systems could capture the strengths of both paradigms while mitigating their respective weaknesses. Crucially, the researchers note that such adaptive routing can be driven by a zero-cost signal already natively present in the standard pipeline—specifically, the top-one retrieval score generated during the initial stages of the Retrieve-then-Plan process.

As the deployment of autonomous LLM agents scales across enterprise and consumer landscapes, optimizing how these systems discover and integrate external capabilities remains a vital area of study. The findings by Zhang, Surana, Majid, Wang, and Xu provide a foundational framework for understanding the interplay between planning and retrieval, offering clear pathways for building more intelligent, cost-effective, and robust AI systems.