Completeness and Cost of Retrieval Structures for Multi-Tool Requests in LLM Agents

Shuyang ZhangarXiv 2026 · arXiv

TL;DR

For LLM agents performing complex tasks, missing just one required tool in a retrieval set often leads to total failure. This paper demonstrates that standard retrieval benchmarks hide this "all-or-nothing" challenge and compares six different retrieval architectures, finding that achieving high "completeness" requires a steep trade-off between expensive human-labeled training data and high-latency LLM reasoning at runtime.

What Problem Does This Paper Address?

Most research on tool retrieval for LLMs focuses on "single-tool" queries—where a user asks a simple question and the retriever finds the one right API. However, real-world agents often need to chain multiple tools together (e.g., fetching a user ID from a database before calling a messaging API).

The authors argue that for these multi-tool requests, traditional metrics like Recall (what percentage of the tools did we find?) are misleading. Instead, we should measure Completeness: did the retriever find every single tool required for the task? If a task requires four tools and the retriever finds three, the agent will likely fail. This paper investigates which retrieval structures actually provide complete sets and at what cost in terms of latency and computation.

Methods

The authors evaluate six distinct "families" of retrieval structures:

  1. Flat Retrieval: Standard lexical (BM25) or dense embedding-based search.
  2. Decomposition: Using an LLM to split a complex query into simpler sub-queries before retrieving.
  3. Hierarchical (AnyTool): An LLM-navigated search that explores categories, then servers, then specific APIs.
  4. Server-then-tool (MCP-Zero): A two-stage process that first identifies the right server/domain and then searches within it.
  5. Dependency Graphs (GoS): Using a pre-built graph of how tools relate to one another to expand the search.
  6. Set-level Retrievers (COLT/HYSET): Specialized models trained specifically to predict groups of tools rather than individual ones.

The study visualizes these different workflows to highlight where LLM calls and training data are required:

Figure 2. The compared retrieval structures as run in this study. Shaded steps call an LLM (orange) or are trained on the testbed’s labelled queries (green); dashed boxes are built once from the tool pool before any query arrives.

Datasets

The study uses three primary testbeds:

  • ToolRet: A large-scale benchmark (7,961 queries) used to show how performance changes as the number of required tools increases.
  • AppWorld: A complex environment of everyday apps with 345 queries that have expert-labeled dependencies (e.g., Tool A must be called before Tool B).
  • MCP-Bench: 103 tasks involving real-world Model Context Protocol (MCP) servers.

Key Insights and Ideas

  • The "Crossover" Effect: A retriever that is the "best" at finding a single tool is often overtaken by other methods when the task requires three or more tools. Aggregate scores on standard benchmarks often hide this "multi-tool regime."
  • Completeness is a High Bar: On the AppWorld dataset, standard zero-shot methods (like basic embedding search) failed to provide a complete tool set for more than 10% of queries.
  • Buying Completeness: You can "buy" completeness in two ways: with data (training a set-level retriever like COLT on ~90 in-domain examples) or with compute (using a hierarchical LLM search like AnyTool that makes dozens of calls per query).
  • The "Prerequisite" Failure: Hierarchical search often finds the "target" tool the user asked for but fails to retrieve the "prerequisite" tools needed to generate the inputs for that target.

Key Results

The performance gap between single-tool and multi-tool queries is stark. As shown in Figure 1, completeness scores plummet as the number of required tools grows:

Figure 1. ToolRet, in-sub-dataset retrieval, query only. (a) Completeness at 10 by number of target tools. (b) Multi-target queries (two or more targets, n = 3,559): completeness at 10 (filled) and recall at 10 (open) per retriever; values are query-weighted means of the 2, 3 and 4+ strata.

In the head-to-head comparison on AppWorld and MCP-Bench (Table 2):

  • COLT (Trained): Reached .328 completeness on AppWorld with zero LLM calls at query time.
  • AnyTool (Hierarchical): Reached a similar .301 completeness but required a median of 31 LLM calls and 5 minutes per query.
  • Downstream Impact: In a live test with an agent, tasks with a complete retrieved set succeeded 100% of the time (21/21), while those with incomplete sets succeeded only 5% of the time (2/39).
Table 2. Completeness at k (C@k) and recall at 16 (R@16). AppWorld: 345 test queries; MCP-Bench: 103 tasks. The last column of each block is the paired bootstrap 95% confidence interval of C@16 minus COLT’s C@16.

Limitations and Future Work

  • Model Dependency: All LLM-based results were measured using DeepSeek-V3.2. The authors note that hierarchical search is highly sensitive to the underlying model's reasoning capabilities.
  • Training Data Requirements: While COLT performed well, it requires human-labeled "gold" tool sets for training, which may not be available for all new tool catalogs.
  • Encoder Size: The study used base-sized embedding models; the authors suggest that evaluating larger, more "tool-savvy" encoders is a necessary next step.
  • Hybrid Approaches: The failure modes suggest a hybrid approach—using hierarchical search to find the target and then using dependency graphs to automatically pull in prerequisites—could be a promising path forward.

Summary updated

Abstract

An agent that must call several tools to fulfill a request fails when the tool retriever omits any one of them, yet tool retrievers are mostly built and evaluated on queries requiring a single tool. We compare representatives of six retrieval structures (flat lexical and dense retrieval, LLM query decomposition, LLM-navigated hierarchies, server-then-tool matching, dependency graphs, and trained set-level retrievers) across two multi-tool testbeds: 345 AppWorld queries with expert dependency labels and 103 MCP-Bench tasks over 257 MCP tools. We measure completeness@k, the share of queries whose entire required tool set appears in the top k, alongside the LLM calls, tokens, and latency that each structure incurs at retrieval time. A motivating analysis on all 7,961 ToolRet queries shows that aggregate completeness mixes two regimes: completeness at 10 is .58 to .67 on single-target queries and .08 to .17 on queries with four or more targets, and the ordering of retrievers on single-target queries reverses on multi-target ones. Across the two testbeds, none of the compared structures that is untrained on the testbed and makes at most one LLM call per query completes more than 10% of AppWorld queries at k = 16. The two structures that do better incur different costs: a set-level retriever trained on 75 to 90 in-domain queries reaches .33 on AppWorld and .58 on MCP-Bench with no LLM calls, while an LLM-navigated hierarchy reaches .30 and .40 with a median of 31 to 38 LLM calls and about five minutes per query. Their failure modes also differ: the trained retriever mostly ranks the missing tools just below the cutoff, whereas the hierarchy finds the target API and stops before collecting its prerequisites. In a downstream check with the official AppWorld agent, tasks with a complete retrieved set succeeded 21 of 21 times, whereas incomplete ones succeeded 2 of 39 times.
BibTeX
@misc{zhang2026completeness,
  author = {Shuyang Zhang},
  title = {{Completeness and Cost of Retrieval Structures for Multi-Tool Requests in LLM Agents}},
  year = {2026},
  eprint = {2610.41905},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.41905},
}
Figure