New AI Research Reveals Complexity-Dependent Crossover Between Retrieval Paradigms for Tool-Augmented LLM Agents

As Large Language Models (LLMs) transition from conversational chat interfaces to autonomous agents capable of performing complex multi-step workflows, the mechanism by which they discover and utilize external software tools has become a critical area of study. A team of researchers—comprising Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang, and Michael Xu—has released a comprehensive study examining how tool-augmented LLM agents discover relevant Application Programming Interfaces (APIs) from massive registries before planning their execution.

Tool-augmented LLM agents rely heavily on external registries to solve specialized tasks, ranging from database queries to real-time data retrieval. However, because finite context windows prohibit injecting thousands of tool definitions into a single prompt, efficient tool retrieval is a mandatory prerequisite for successful execution. The dominant approach in the field, which the authors term Retrieve-then-Plan, embeds the user query and retrieves similar tools via approximate nearest-neighbor search.

In this new study, the research team investigates an alternative paradigm known as Plan-then-Retrieve. In this reversed workflow, the LLM first generates what the researchers call Abstract Tool Stubs—hypothesized function signatures that describe the needed capabilities. These stubs then serve as the retrieval queries against the API registry, fundamentally altering how the agent interacts with external tool libraries.

To rigorously test both paradigms, the researchers evaluated them on ToolBench, a massive benchmark comprising 46,984 unique API endpoints distributed across 50 distinct categories. The evaluation spanned three core query subsets designed to test different levels of complexity: single-tool queries, intra-category multi-tool queries, and cross-category multi-tool queries.

The empirical results revealed a clear complexity-dependent crossover between the two approaches. The traditional Retrieve-then-Plan paradigm outperforms Plan-then-Retrieve on straightforward, single-tool queries. Conversely, the Plan-then-Retrieve paradigm outperforms Retrieve-then-Plan when handling more complex, multi-tool queries.

Crucially, the research demonstrates that this performance crossover is remarkably robust. The crossover holds steady at every retrieval budget tested, ranging from $k=1$ to $k=20$. Furthermore, it remains consistent across varying registry sizes—from compact registries containing just 1,000 APIs up to the full-scale 47,000-API benchmark—and proves resilient across different foundational model families, including Gemini 2.5 Flash and gpt-oss-120b.

To understand why this crossover occurs, the authors closely examined the underlying mechanics and identified a distinctive failure mode they term "stub-hallucination." In this scenario, the LLM invents plausible but entirely non-existent API names during the planning phase. Interestingly, the researchers found that stub-hallucination acts as a double-edged sword within the agentic workflow.

On simple queries, the LLM’s generated stubs tend to abstract away proper-noun signals that the standard Retrieve-then-Plan method matches directly, causing unnecessary friction and performance drops. However, on complex queries, that exact same hallucination and abstraction mechanism serves a vital purpose by decomposing a multi-faceted, high-level intent into discrete functional sub-needs, enabling much more targeted and effective retrieval from massive registries.

The study also delves into the operational economics of deploying these architectures, specifically analyzing token overhead and inference costs. The findings show that the Plan-then-Retrieve paradigm requires an extra discovery call that roughly doubles the overall inference cost. For multi-tool queries, this added computational and financial expense easily pays off through higher success rates and better tool selection. However, for simpler single-tool queries, the doubled overhead becomes a clear disadvantage.

This economic and performance trade-off points directly toward a practical engineering solution: complexity-adaptive routing. By dynamically routing queries based on estimated complexity, developers could leverage Retrieve-then-Plan for simple tasks and switch to Plan-then-Retrieve only when faced with multi-faceted challenges.

Moreover, the research suggests that implementing such a routing system does not require complex external classifiers. Instead, it can be driven by a zero-cost signal already natively present in the standard pipeline: the top-1 retrieval score generated during the initial Retrieve-then-Plan phase. This signal provides an immediate, computationally free indicator of query simplicity, offering a clear path forward for optimizing next-generation AI agent architectures.