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:
- Flat Retrieval: Standard lexical (BM25) or dense embedding-based search.
- Decomposition: Using an LLM to split a complex query into simpler sub-queries before retrieving.
- Hierarchical (AnyTool): An LLM-navigated search that explores categories, then servers, then specific APIs.
- Server-then-tool (MCP-Zero): A two-stage process that first identifies the right server/domain and then searches within it.
- Dependency Graphs (GoS): Using a pre-built graph of how tools relate to one another to expand the search.
- 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:
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:
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).
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