CS Paper Radar

Tool Recommendation for Multi-Step Agents: Finding Every Tool a Task Needs

Sam Partee, River Stevens, Thierry Damiba, Valerie Fanelle

cs.LG cs.IR ·submitted 2026-10-16 16:30 UTC · v1
benchmark

Abstract

A multi-step agent task fails when a single tool it needs is missing, yet the tools an agent may need are too many to list: the roughly 8,200 tools on the platform we study have definitions that together exceed the context window of any model we evaluate. We present Tool Recommendation, a deployed system that gives an agent all of them, hundreds of times more than a typical MCP server exposes, through a fixed interface of three tools. It runs at the gateway between agent and tools, executing every call under the end user's own credentials and checking it against the user's consent for each service and the tools the agent may use. We evaluate it on both a public retrieval benchmark and billed end-to-end session cost. On ToolRet, Tool Recommendation places every tool a query needs in the top ten 57% more often than BM25, a lexical ranking that commercial tool search offers, and compares favorably with published systems up to nine times its size. In paired multi-step workflows, its first recommendation covered every required tool in 93% of Codex sessions, and against a fixed list of 100 tools it cut input tokens by 17% with Codex and 40% with Claude Code and the total bill in all 14 runs, by up to 40%, with no change in task completion.

Comment
11 pages, 3 figures, 5 tables

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.IR cs.CL ·2026-10-30 ·Shuyang Zhang
similarity 0.78
Abstract · 17 pages, 3 figures, 9 tables

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.

0.21

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

cs.AI cs.IR ·2026-10-13 ·Mingfei Zhang, Amit Surana, Ziauddin Majid, Chenxi Wang, Michael Xu
top venue similarity 0.76
Abstract

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).

0.44

Explore Separately, Adopt Selectively: Execution-Guided Tool Use over Large Tool Libraries

cs.CL cs.AI ·2026-10-15 ·Anna Mazhar, Seiji Maekawa, Nikita Bhutani
similarity 0.75
Abstract

Enterprise LLM agents using growing tool catalogs must surface capabilities as workflows evolve without flooding context or committing to the wrong tool. Adaptive retrieval can expose new capabilities, but when several tools seem plausible, probing them sequentially can stop at an early failure or leave failed attempts in the agent context. We present BRIA (BRanch-Inspect-Adopt), a plug-and-play method that investigates candidates in isolated branches. Each branch retrieves and executes tools independently. A task agent inspects the execution evidence and selectively adopts useful results in its context. BRIA also retrieves tools as new capability needs arise. To evaluate BRIA in an enterprise setting, we assemble a single catalog with 1897 tools from PlanBench-XL and MCP-Atlas. We compare BRIA with static and adaptive baselines using three LLM families. We observe that BRIA lies on the accuracy-cost frontier. Compared with the strongest baseline, BRIA uses less than half as many input tokens to achieve equal or higher success rates on PlanBench-XL, and improves task performance by up to 14.4 percentage points on MCP-Atlas. For enterprise agents over large catalogs, these results suggest that candidate tools can be effectively explored with execution evidence without carrying every result in the agent's context.

0.21

Agents' Overreliance on Unreliable Tools

cs.AI ·2026-09-04 ·Hoyeol Yang, Woojung Song, Taewon Kim, Jonghyun Song, Seoyeon Park +1 more
similarity 0.73
Abstract · 49 pages, 4 figures

LLM agents use tools to access information and perform computations beyond their parametric knowledge. Existing tool-use benchmarks evaluate whether agents select and call the right tools, assuming that tool returns are reliable. However, tools can return plausible but incorrect outputs. We evaluate 14 models with three tools (web search, an LLM sub-agent, and a code executor), corrupting their returns to examine whether agents overrely on unreliable tools. Agents adopt corrupted returns at high rates, with mean adoption exceeding one third for every tool and reaching 68.0% for web search. Corrupted returns also frequently override correct answers that agents give without tools, and this reliance persists in more complex tasks and in tasks that combine multiple tools. Agents often make more tool calls under corrupted returns, and reasoning traces show them questioning a return and even stating the correct answer. Nevertheless, they still pass the corrupted content to users, rarely warning them of the conflict. We further test interventions spanning prompts, tool metadata, post-training, and activation steering. Verification prompts reduce adoption across all three tools while largely preserving accuracy with correct returns, and reliability labels provide partial mitigation in web search. The tested post-training methods offer limited gains, and the effect of activation steering depends on the model and intervention strength. Overall, our findings provide a basis for diagnosing tool overreliance and for developing agents that assess tool returns rather than assuming their reliability.

0.45

EGI-BENCH: An Enterprise General Intelligence Benchmark Suite

cs.AI ·2026-10-19 ·Zhiwei Liu, Zhujun Lan, Jielin Qiu, Zixiang Chen, Liangwei Yang +10 more
benchmarkcode/data similarity 0.72
Abstract

Enterprise adoption of LLMs in agentic workflows is gated by evaluations that span a wide arc of abilities: CRM operations, heterogeneous-document retrieval, personal data understanding, multi-turn planning, tool use, function calling, long-horizon research, and long-context software engineering. These evaluations live today in separate repositories with divergent runners, dependencies, and scoring conventions, which makes cross-benchmark comparison difficult and obscures what a single aggregate number actually represents. We release EGI-BENCH, a unified LLM agent benchmark suite that consolidates eight enterprise facing agent benchmarks (CRMARENA, HERB, PERSONABENCH, USERBENCH, MCP-UNIVERSE, MCPEVAL, BENCHFORCE, LOCOBENCH) behind a single command-line interface with two runtime-budgeted execution modes. On top of the suite we define the Enterprise General Intelligence (EGI) Score, a six-dimensional framework (M1-M6) whose buckets are populated by fine-grained sub-metrics routed from each benchmark rather than by benchmark-level averages. We describe the suite, the sub-metric routing, and the quick/deep budgets, and report results for fourteen frontier and cost-efficient LLMs spanning the GPT, Claude, and Gemini families under quick mode. Top-line EGI ranges from 39.6 (GPT-4o mini) to 65.6 (gpt-5.5), and no single model dominates every capability axis: gpt-5.5 leads task outcome, planning, and retrieval grounding; Claude Sonnet 4.5 leads tool actioning and safety/abstention; and Claude Haiku 4.5 leads engineering quality. Code is available at https://github.com/SalesforceAIResearch/egi-bench.

0.33

Toollery: Scaling LLM Agents to Thousands of Skills and Tools

cs.LG cs.AIcs.CL ·2026-09-02 ·Xiangxi Tian, Ran Guan
top venuebenchmark similarity 0.72
Abstract · To be presented at the 2026 Conference on Empirical Methods in Natural Language Processing (EMNLP 2026)

As LLM agents are exposed to hundreds to tens of thousands of skills, tools, and API functions, full-library prompting becomes costly, slow, and less reliable: each added candidate increases prompt tokens and latency, while longer candidate lists introduce more distractors for LLM selection. We present Toollery, a training-free candidate-compression framework for scalable LLM skill/tool selection. Following established document-side query expansion, Toollery generates user-intent queries from each skill/tool specification and builds a retrieval index that maps real user requests to compact candidate sets before final LLM decision-making. By treating high-level skills and atomic tools as selectable capabilities, Toollery can be applied to both skill libraries and tool registries. We evaluate Toollery on the roughly 79K-capability SkillRouter benchmark, BFCL-V4 with over 440 atomic tools, and 3,396 proprietary smart-cockpit requests over 220 tools. Across these settings, Toollery keeps online selection bounded to a compact top-K candidate set and improves recall over ordinary specification retrieval. At a fixed top-10 budget, Toollery improves end-to-end selection on the cockpit dataset, and maintains comparable AST Accuracy on BFCL-V4. These results support Toollery as a practical candidate-compression framework for large and evolving agent capability libraries, while showing that quality and cost gains depend on workload coverage and provider caching.

0.36

RecToolBench: Benchmarking Recommendation-Specific Tool Orchestration under Fuzzy User Intent

cs.IR ·2026-09-25 ·Xiao Chen, Yicheng Zhao, Yingying Wu, Zhendong Chu, Changyi Ma +2 more
top venuebenchmarkcode/data similarity 0.71
Abstract · EMNLP Findings 2026

Recent advances in agentic recommender systems are shifting recommender systems from passive filtering engines to instruction-following agents that use external tools to resolve user intent. However, existing benchmarks often assume explicit user intent, simplified tool environments, or isolated function calls, leaving realistic tool orchestration for recommendation underexplored. To bridge this gap, we propose RecToolBench, a Model Context Protocol (MCP)-based benchmark for evaluating tool-using recommender agents under fuzzy user instructions. RecToolBench contains more than 1,200 executable tasks across three recommendation domains, 13 MCP servers, and 32 tools, spanning single-tool calls, parallel tool calls, sequential tool chains, and hybrid tool orchestration. We construct RecToolBench with a scalable synthesize--fuzzify--judge pipeline that generates executable fuzzy recommendation tasks, and evaluates agent trajectories using rule-based execution checks and rubric-based LLM evaluation. Experiments on representative LLMs show that syntactically valid tool calls do not guarantee successful recommendations. Models struggle with semantic parameter grounding, multi-step evidence integration, and grounded final recommendations, especially as orchestration complexity increases. Our results identify tool orchestration under fuzzy user intent as a major bottleneck for agentic recommender systems. Our data and code are available at https://github.com/ShawnChenn/RecToolBench.

0.75

Lookahead-R: Budget-Aware Tool Retrieval via Execution-Centric Planning

cs.CL cs.AIcs.SE ·2026-09-20 ·Zongze Wu, Yani Guo, Runnan Li
publishedbenchmark similarity 0.71
Abstract · 10 pages, 3 figures, 3 tables. Published in ICMR 2026

Tool retrieval is a critical bottleneck for LLM-based agents operating over large, heterogeneous API ecosystems. Existing approaches face an inherent trade-off: semantic retrievers are fast but suffer from the semantic-functional gap, while execution-based validation improves precision at the cost of prohibitive latency. We propose Lookahead-R, a planning-based framework that reformulates tool retrieval as a resource-constrained sequential decision-making problem. At its core, Lookahead-R introduces a lightweight execution-aware surrogate world model that jointly predicts tool execution success, latency cost, and semantic utility---without invoking real APIs. This world model drives a cost-sensitive, uncertainty-guided Monte Carlo Tree Search that navigates the tool space under strict budget constraints. Evaluated on the large-scale ToolBench benchmark, Lookahead-R achieves a superior accuracy-efficiency trade-off across all test scenarios. On the most challenging I3 split, it attains an NDCG@5 of 91.40\%, outperforming the state-of-the-art ToolGen (90.16\%) by 1.24\%. Ablation studies confirm that explicit latency modeling is the key discriminative signal for identifying high-quality tools under resource constraints.

0.51