cs.IROct 30, 2026

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

Authors: Shuyang Zhang

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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.

Figures & tables

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.
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.
Figure 3. Completeness at 16 against median LLM tokens per query at retrieval time. Arms without a query-time LLM call appear in the left strip of each panel; GoS calls the LLM only when building its graph. Hollow markers are trained on the testbed’s labelled queries.
More in this topic

Tool Discovery for LLM Agents

See all 19 papers

Explore similar work

CardsList
Jul 28, 2026

Tools Are Not Islands: Set-Level Tool Retrieval for LLM Agents via Query-Conditioned Hyperedge Prediction

Large language model (LLM) agents increasingly rely on invoking external tools to complete real-world tasks. Tool retrieval, which selects a small task-relevant subset from a library of thousands of tools before the agent acts, has therefore become a critical component of LLM agent pipelines. However, existing retrievers either score each tool in isolation or assemble the tool set sequentially, so the joint utility of a candidate set is never evaluated as a whole. In this paper, we propose HYSET, short for HYperedge-based SEt-level Tool retrieval. Our contributions are threefold: (i) we formulate tool retrieval as query-conditioned hyperedge prediction on a tool co-invocation hypergraph, under which the tool set itself becomes the unit of scoring and most existing retrieval paradigms reduce to restricted instances; (ii) we capture size-dependent tool compatibility through cardinality-specific interactions; and (iii) we design HYSET as a pre-selection module requiring no modification to the downstream agent. Experiments on ToolBench demonstrate that HYSET consistently outperforms state-of-the-art baselines in both tool retrieval performance and end-to-end task success. Beyond the in-domain setting, HYSET further supports zero-shot/few-shot transfer, generalizing to held-out tools/categories and unseen domains with minimal supervision.

Xinyi Hong, Pinjun Dong, Xinyang Yu +1

School of Mathematical Sciences, Shanghai Jiao Tong University · Department of Data Science and Artificial Intelligence, The Hong Kong Polytechnic University

Tool-Augmented Language Model AgentsLLM Tool UseTool-Using Language AgentsHypergraph Learning
AskPDF
Oct 13, 2026

Plan or Retrieve First? A Scale Study of Tool Discovery Architectures

Tool-augmented LLM agents discover relevant APIs from large registries before planning execution, yet finite context windows prohibit injecting all tool definitions into a single prompt. The dominant approach, which we term Retrieve-then-Plan (RtP), embeds the user query and retrieves similar tools via approximate nearest-neighbor search. We study an alternative Plan-then-Retrieve (PtR) paradigm in which the LLM first generates Abstract Tool Stubs (hypothesized function signatures describing needed capabilities) which then serve as retrieval queries against the registry. Evaluating on ToolBench (46,984 unique API endpoints, 50 categories) across single-tool (G1), intra-category multi-tool (G2), and cross-category multi-tool (G3) query subsets, we find a clear complexity-dependent crossover: RtP outperforms PtR on single-tool queries while PtR outperforms RtP on multi-tool queries. This crossover holds at every retrieval budget (k=1 to 20), is robust across registry sizes from 1k to 47k APIs, and is consistent across model families (Gemini 2.5 Flash and gpt-oss-120b). We characterize a stub-hallucination failure mode (the LLM invents plausible but non-existent API names) that acts as a double-edged sword: on simple queries PtR's stubs abstract away proper-noun signals that RtP matches directly, yet on complex queries the same mechanism decomposes multi-faceted intent into functional sub-needs. We further analyze token overhead and show that PtR's extra discovery call roughly doubles inference cost, which pays off on multi-tool queries but hurts on single-tool ones, motivating complexity-adaptive routing as a practical direction, one that can be driven by a zero-cost signal already present in the pipeline (RtP's top-1 retrieval score).

Mingfei Zhang, Amit Surana, Ziauddin Majid +2

Apple

Tool Discovery for LLM AgentsLLM Tool UseAgentic RetrievalLLM Planning
AskPDF
May 23, 2026

How Many Tools Should an LLM Agent See? A Chance-Corrected Answer

Before an LLM agent can use a tool, a retrieval system must decide which candidate tools to show to the agent. How long should that shortlist be? Show too many tools and the model struggles to choose. Show too few and the correct tool may not appear. Most systems apply a fixed shortlist size to every query, but no standard metric exists to evaluate whether that size was appropriate. We treat the number of tools shown to an LLM agent as the object of evaluation and we apply Bits-over-Random (BoR), a chance-corrected metric that asks whether success at a given depth is better than what random selection would achieve at that same depth. We evaluate BoR across three tool-selection benchmarks, multiple scorers, and registries ranging from 20 to 3,251 tools. We then turn the same principle into a reinforcement learning (RL) reward for choosing tool shortlist depth per query. The RL agent is deliberately simple, serving as a probe of the metric rather than a proposed system. As the shortlist grows, random chance of including the correct tool rises, so the reward naturally decreases, reducing the need for an engineered depth penalty. On BFCL (370 tools), the learned policy nearly matches the coverage of showing 50 tools (90.3%90.3\% vs 90.8%90.8\%) while presenting only 7 on average. On ToolBench (3,251 tools), a fixed shortlist of 5 tools achieves higher aggregate coverage (64.7%64.7\% vs 61.9%61.9\%) but finds nothing on hard queries (correct tool ranked 6th-20th). The BoR agent finds 16.7%16.7\% on those same queries by searching deeper. Downstream validation with Claude Sonnet 4.6 indicates that shorter adaptive lists also improve the LLM's ability to select the right tool: 93.1%93.1\% versus 87.1%87.1\% when always shown 5 tools, widening to 76.8%76.8\% vs 60.9%60.9\% on medium-difficulty queries where the correct tool is present but not ranked first.

Vyzantinos Repantis, Ameya Gawde, Harshvardhan Singh +1

Meta Platforms

Tool-Use EvaluationTool-Augmented Language Model AgentsTool-Using AgentsLLM AgentsTool SelectionTool Selection for Language Model Agents
AskPDF