Study Reveals Complexity-Dependent Crossover Between Retrieval Paradigms in Tool-Augmented LLM Agents

As large language models take on increasingly complex workflows, researchers continue to refine how these systems interact with external applications and APIs. A recent study authored by Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang, and Michael Xu sheds new light on this challenge, examining how tool-augmented language model agents discover relevant application programming interfaces from massive registries before executing tasks. Because finite context windows prohibit injecting thousands of tool definitions into a single prompt, finding the right tool efficiently remains a critical hurdle in artificial intelligence engineering.

The dominant approach currently employed in the field is known as Retrieve-then-Plan, or RtP. In this paradigm, the system embeds the user’s query and subsequently retrieves similar tools from a registry via approximate nearest-neighbor search. While efficient for straightforward queries, this method often struggles when a user’s intent requires multiple, diverse capabilities. To address these limitations, the research team studied an alternative paradigm called Plan-then-Retrieve, or PtR. In this inverted workflow, the language model first generates abstract tool stubs—hypothesized function signatures that describe the needed capabilities—which then serve as the retrieval queries against the API registry.

To understand the practical differences between these two methodologies, the researchers conducted a comprehensive evaluation using ToolBench, a robust benchmark featuring 46,984 unique API endpoints spanning 50 distinct categories. Their evaluation spanned three distinct query subsets: single-tool tasks, intra-category multi-tool tasks, and cross-category multi-tool tasks. The results uncovered a clear complexity-dependent crossover in performance between the two approaches.

Specifically, the study found that the traditional Retrieve-then-Plan method outperforms Plan-then-Retrieve on single-tool queries. However, the dynamic shifts when handling multi-tool queries, where Plan-then-Retrieve clearly surpasses its counterpart. According to the findings, this performance crossover remains remarkably consistent across every tested retrieval budget, holding steady whether the system retrieves a handful of candidates or up to twenty. Furthermore, this behavioral crossover is robust across varying registry scales, scaling predictably from one thousand to nearly forty-seven thousand APIs, and remains consistent across different foundational model families, including Gemini 2.5 Flash and gpt-oss-120b.

A deeper analysis of the mechanisms at play revealed a fascinating structural behavior within the Plan-then-Retrieve paradigm: a stub-hallucination failure mode. In this scenario, the language model invents plausible-sounding but entirely non-existent API names during the initial planning phase. The researchers characterize this phenomenon as a double-edged sword. On simple queries, these generated stubs can actually abstract away proper-noun signals that the simpler Retrieve-then-Plan approach would otherwise match directly and efficiently. Conversely, on complex queries, this exact same mechanism acts as a powerful decomposition tool, breaking down a multi-faceted user intent into distinct functional sub-needs that yield superior retrieval results from the broader registry.

The investigation also addressed the operational economics of deploying these systems, particularly regarding token overhead. The extra discovery call required by the Plan-then-Retrieve paradigm roughly doubles the overall inference cost of the pipeline. For multi-tool queries, this added expense is easily justified by the significant improvement in task execution accuracy. However, for straightforward single-tool queries, the doubled inference cost becomes a distinct disadvantage, burning computational resources without a corresponding performance gain.

These economic and performance tradeoffs naturally point toward a practical architectural solution: complexity-adaptive routing. By dynamically switching between Retrieve-then-Plan and Plan-then-Retrieve depending on the nature of the incoming request, engineering teams can capture the best of both worlds. Crucially, the researchers noted that this adaptive routing decision does not require complex preliminary classifiers; it can be driven by a zero-cost signal already readily available within the standard pipeline workflow, namely the top-one retrieval score generated during the initial Retrieve-then-Plan phase.