Researchers Reveal Complexity-Dependent Trade-Offs in Tool-Augmented LLM Agent Architectures

As Large Language Models (LLMs) increasingly transition from conversational assistants to autonomous agents capable of interacting with external software, the mechanisms by which these models discover and utilize external Application Programming Interfaces (APIs) have become a central focus of artificial intelligence research. A newly published study authored by Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang, and Michael Xu dives deep into this architectural challenge, examining how tool-augmented LLM agents discover relevant APIs from massive registries before executing multi-step plans.

The core difficulty stems from a fundamental engineering constraint: finite context windows. Modern software ecosystems boast vast registries containing tens of thousands of unique API endpoints, making it impossible to inject every available tool definition directly into a single prompt. To bypass this limitation, tool-augmented systems must rely on targeted retrieval strategies.

For the broader AI research community, the dominant paradigm for solving this bottleneck has long been a straightforward methodology known as Retrieve-then-Plan, or RtP. Under this conventional approach, the system embeds the raw user query and subsequently retrieves similar tools from a registry via approximate nearest-neighbor search. While efficient for straightforward tasks, the RtP framework assumes that a user’s initial prompt contains all the necessary semantic signals to match against appropriate backend functions without prior decomposition.

Challenging this status quo, the research team investigated an alternative paradigm termed Plan-then-Retrieve, or PtR. In this inverted workflow, the LLM first generates what the authors call Abstract Tool Stubs—hypothesized function signatures that describe the specific capabilities needed to address the user’s intent. These generated stubs then serve as the retrieval queries against the underlying API registry, rather than the raw user prompt itself.

To rigorously evaluate these competing architectures, the researchers tested both paradigms on ToolBench, a comprehensive benchmark encompassing 46,984 unique API endpoints distributed across 50 distinct functional categories. The evaluation framework segmented tests into three granular query subsets: single-tool tasks, categorized as G1; intra-category multi-tool tasks, categorized as G2; and cross-category multi-tool tasks, categorized as G3.

The empirical findings revealed a clear, complexity-dependent crossover between the two paradigms. According to the study, RtP outperforms PtR when handling single-tool queries. However, the performance dynamic flips entirely when dealing with multi-tool queries, where PtR consistently outperforms RtP.

Crucially, this crossover phenomenon proved remarkably resilient across experimental variations. The researchers observed that the performance crossover holds steady at every tested retrieval budget—ranging from a retrieval count of $k=1$ up to $k=20$. Furthermore, the pattern remained robust across registry sizes spanning from 1,000 to 47,000 APIs and proved consistent across prominent model families, including Gemini 2.5 Flash and gpt-oss-120b.

To understand why this performance split occurs, the study provides a deep characterization of a specific failure mode unique to the PtR approach, known as stub hallucination. In this phenomenon, the LLM invents plausible-sounding but entirely non-existent API names during the planning phase.

The researchers discovered that this hallucination mechanism acts as a double-edged sword. On simple, single-tool queries, PtR’s generated stubs tend to abstract away crucial proper-noun signals that the conventional RtP approach can match directly against the registry. By stripping away these direct lexical matches, the abstraction process hinders accurate retrieval.

Conversely, on complex multi-faceted queries, this same hallucination and abstraction mechanism becomes a vital asset. It effectively forces the LLM to decompose a convoluted, multi-faceted user intent into smaller, discrete functional sub-needs. This decomposition allows the subsequent retrieval step to target specialized tools across different functional domains that a monolithic query search might otherwise miss.

Beyond raw task accuracy, the research team also analyzed the token overhead associated with each architectural approach. They demonstrated that PtR’s extra discovery call roughly doubles the overall inference cost compared to RtP.

While this elevated computational expense pays off handsomely on complex multi-tool queries where thorough decomposition is necessary, it represents an unnecessary performance tax on simple single-tool queries. This economic disparity naturally highlights a practical path forward for agent design: complexity-adaptive routing.

The authors suggest that implementing an adaptive routing mechanism—one that dynamically chooses between RtP and PtR based on the estimated complexity of the incoming task—could capture the best of both worlds. Intriguingly, the study notes that such routing can be driven efficiently by a zero-cost signal already present within the standard pipeline: RtP’s top-1 retrieval score. By evaluating the confidence of the initial retrieval step, systems could intelligently decide whether to trigger a full planning-and-stub generation phase or proceed with direct retrieval.

Related readings and updates in the broader field further underscore the critical nature of these retrieval dynamics. Large Language Models are increasingly deployed for complex multi-step planning tasks, where the tool retrieval step remains the linchpin for successful execution. Previous scholarly explorations, such as progressive tool retrieval frameworks presented at academic venues like the UncertaiNLP workshop at EACL 2024, have similarly grappled with the limitations of single-step retrieval versus sequential retrieval driven by task decomposition.

As the ecosystem of AI agents continues to expand into enterprise software and automated workflows, navigating these architectural trade-offs will be essential for balancing computational efficiency with task execution reliability.