Six tool-retrieval structures were put on the same test paper, and the result is easy to miss: recall can double while completeness barely moves.
A metric buried under an average
The paper starts from a measure in tool retrieval that is rarely taken apart: completeness@k — whether the entire set of tools a request needs appears within the top k of the retrieval list. On single-tool requests the measure collapses into a hit rate; it only starts to measure the retriever when a request needs several tools.
The authors first stratify a standard benchmark. ToolRet has 7,961 queries, and 55% of them point at a single target tool. Split by target count the gap is immediate: completeness@10 lands between 0.58 and 0.67 on single-target queries, but falls to just 0.08 to 0.17 on queries needing four or more targets. bge-base's aggregate score of 0.507 is the weighted average of 0.672 on single-target and 0.303 on multi-target queries — a number propped up by the difficulty distribution of the query set.
Rankings also flip. In the paper's own evaluation, bge-base is best or tied for best on single-target queries, but at two targets the COLT stage 1 retriever beats it by 0.077 to 0.122 and query decomposition by 0.006 to 0.041; at four or more targets, decomposition is ahead by 0.013 to 0.064. A separate independent study finds a crossover in the same direction on a completely different registry: retrieve-then-plan designs win on single-tool queries, plan-then-retrieve designs win on multi-tool ones, and the crossover holds at every budget from k=1 to 20 and across registry sizes from 1k to 47k APIs.
On a multi-tool testbed, completion drops to a tenth
The paper then moves the fight to two testbeds that genuinely need several tools. AppWorld uses the expert parameter-level dependency labels from In-N-Out: 345 official test queries (129 test-normal, 216 test-challenge) run over 456 APIs, each request needing between 2 and 12 APIs with a median of 6, of which 258 are single chains and 87 carry dependencies. The second testbed, MCP-Bench, is 103 tasks over 257 tools on 28 servers, and 97 of those tasks explicitly need several tools.
C@16 on AppWorld is grim: BM25, MCP-Zero and HYSET all sit at 0, bge-base reaches only 0.020, query decomposition 0.035, e5-base 0.064 and the dependency graph GoS 0.096. Only two structures clear the bar — COLT at 0.328 and AnyTool at 0.301 — and the confidence interval on the gap between them, [-0.081, 0.029], crosses zero, so they are indistinguishable. On MCP-Bench, COLT leads with 0.583 (recall 0.887), ahead of AnyTool at 0.398 and decomposition at 0.359.
Broken down by server count, COLT scores 0.782 on single-server tasks, 0.467 on two-server and 0.167 on three-server. Among three-server tasks, nobody completes a single one except AnyTool at 0.278.
Recall and completeness are not the same thing
The most telling numbers sit in the paper's fourth observation: query decomposition lifts AppWorld recall@16 from bge-base's 0.190 to 0.417, more than doubling it, while completeness@16 moves only from 0.020 to 0.035. Recall says "most tools were found"; completeness asks "is the whole set there?" On MCP-Bench, AnyTool and decomposition post recall@16 of 0.783 and 0.776, apparently catching COLT's 0.887, yet completeness is only 0.398 and 0.359, still short of COLT's 0.583. Tuning a retriever on recall alone means tuning a metric that has little to do with whether the agent gets the job done.
Two failure modes, two different repairs
The paper decomposes every incomplete retrieval into causes, and the two leading structures fail in opposite ways. Of the APIs COLT loses, 58% (404 of 698) are actually sitting at ranks 17 to 50 of its own list — 90% of them on MCP-Bench — so it is a ranking-depth problem that a larger budget or a reranker could recover. AnyTool loses them differently: of 538 missing APIs, 317 are "unrecognized prerequisites", meaning it found the API the request names but never collected the APIs feeding its inputs, which points to completing the set along producer-consumer dependencies. Flat and graph retrievers mostly lose the target itself at the initial retrieval step.
The bills differ too. COLT needs no LLM call at query time, 0 tokens and 0 latency, but demands labelled queries over the same tool pool up front — 90 official training queries on AppWorld, 75 per fold on MCP-Bench. AnyTool needs no training data, but spends a median of 31 to 38 LLM calls per query, 99,739 tokens and 307 to 311 seconds of wall-clock time, roughly five minutes per query.
The downstream check: 21 against 39
The most persuasive piece is the downstream check the paper runs itself. The official AppWorld ReAct agent runs 60 tasks, one group given the gold APIs and one given only COLT's top 16: the former succeeds 46 times, the latter 23, with a paired test p-value of 5.6×10⁻⁶. In the paper's own evaluation, all 21 tasks where COLT's top 16 was complete succeeded every time, with the gold set succeeding on 20 of the same tasks; among the 39 tasks COLT failed to complete, COLT succeeded twice and the gold set succeeded 26 times. An agent short of tools keeps hitting walls: median steps rise from 19 to 32, 30 episodes run into an unexposed-API error (8 under the gold set), and prompt tokens go from 7.4M to 15.1M. The paper honestly flags the comparison as observational — complete tasks may simply be easier — but the same incomplete tasks succeed two thirds of the time under the gold set, so difficulty alone does not explain the gap.
The limits the paper sets for itself
The author states two limitations. Every LLM-dependent step runs on DeepSeek-V3.2, so swapping in a different model could reshuffle that cost line (another study he cites shows that moving the gateway model from GPT-5.4 to GPT-5.1 drops hierarchical gateway task success by 37.6 points on average, against 11.9 points for flattened gateways). And every dense retriever uses a base-size encoder, so that 10% ceiling describes encoders of that size.
So what does it mean in practice: if you are wiring a whole set of tools into an agent, the evaluation metric should move from recall@k to completeness@k, and it should be stratified by how many tools a request needs — otherwise the aggregate score gets propped up by single-tool queries. The resource bill matters too. If you can pair the tool pool with labelled requests, use a set-level retriever and push query-time cost to zero; without labelled data, hierarchical navigation can make up the capability gap, but budget for roughly five minutes of latency per query. What to watch is not "how many came back" but "is the set complete" — the paper's own downstream number is 21 against 39.