acceptodds
Under review as a conference paper at ICLR 2027

The Missing Link: Relational Tool Retrieval for More Capable and Consistent Agents

Abstract

Recent advances in tool-calling agents have focused on expanding capability through stronger foundation models and larger tool catalogs. Enterprise environments provide a natural setting for this challenge, with knowledge distributed across large, evolving collections of tools and resources. Yet the utility of a tool ecosystem depends not only on the tools it contains, but also on the relationships connecting them. We present GEAR (Graph-Expanded Agent Retrieval), a retrieval framework that uses an ontology to link tools, concepts, and execution contexts. GEAR was designed to avoid both the fine-tuning required by COLT and the additional large language model (LLM) calls that MCP-Zero incurs at inference time. Our experiments on CAR-bench demonstrate that GEAR outperforms both baselines in capability while maintaining comparable consistency and consuming fewer tokens than MCP-Zero.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
ontology, graph-based retrieval, tool use, tool retrieval, agents

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_3TaoOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes GEAR, a graph-based tool retrieval framework that expands conventional similarity-based retrieval using relationships between tools. It constructs a tool ontology with four types of relations (REQUIRES, INFORMS, semantic-routing, and CONFLICT), allowing the retriever to include tools that may be necessary for task execution but are not explicitly mentioned in user requests. The method is evaluated on CAR-bench and ToolBench, with comparisons against similarity-based retrieval, COLT, and MCP-Zero. Results show improvements in task completion capability, although gains in execution consistency are limited.

Critical strengths
  1. The paper addresses a practical problem in tool-using agents. Conventional similarity-based retrieval can miss prerequisite or complementary tools that are not explicitly mentioned in user requests. Exploiting relationships between tools is a reasonable way to address this limitation.

  2. The proposed framework is relatively simple and lightweight. It does not require additional model training or per-turn LLM calls, making it potentially easy to integrate into existing agent systems.

  3. The paper provides encouraging results on CAR-bench, where GEAR substantially improves Pass@3 over conventional retrieval methods. The experiments also examine repeated-trial consistency, which is an important but often overlooked aspect of agent reliability.

Critical weaknesses
  1. The comparison with existing methods is insufficient. Several relevant tool retrieval approaches, such as ToolGen, Tool Graph Retriever, Re-Invoke, and ToolRet, are missing from the experiments. In particular, comparisons with existing graph-based retrieval methods are important to establish the novelty and effectiveness of GEAR.
  2. The benchmark coverage is limited. The end-to-end evaluation mainly relies on only 50 tasks from CAR-bench in a single domain, while ToolBench only evaluates retrieval quality without actual agent execution. More diverse benchmarks and domains are needed to demonstrate generalizability. W3. The paper needs clearer presentation and stronger experimental analysis. Some methodological details, particularly the construction and contribution of different relation types, are insufficiently explained. Moreover, the paper does not adequately isolate the benefits of relational modeling from simply increasing the number of retrieved tools. The overall presentation could also be better organized to clarify the main contributions.
Questions for authors
  1. Can the authors include comparisons with more recent tool retrieval methods, particularly existing graph-based approaches?
  2. How much of GEAR's improvement remains when all methods are constrained to the same shortlist size or token budget?
  3. Can the authors provide a broader end-to-end evaluation across different domains and more diverse tool ecosystems?
1 comment

Thank you for the review: the ask for graph-based comparisons, sharpened what the paper now claims about where the relations help. We address each point below; the general response summarises the new controls.

W1 / Q1: COLT is graph-based (its second stage reranks over a learned graph of requests, tools and tool sets) and is compared throughout. Re-Invoke is now added: on CAR-bench it equals similarity search at 12 tools and GEAR at 37; on ToolBench it is the strongest method. COLT and MCP-Zero at 37 tools do not differ significantly from GEAR either.

W2 / Q3: The end-to-end evidence covers one domain, 50 tasks and two small models, ToolBench tests retrieval only, and CAR-bench's catalogue fits in context. The limitations state all of this. On ToolBench, the mined graph's small gain comes from the content of its edges. Please see response to Yj1L for more details on the added benchmarks.

W3 / Q2: We reran every retriever at about 37 tools: at equal size GEAR's lead is not significant (p≥0.18), and all 57 tools are level with GEAR's 37.6. More tools help only until the needed ones are in view. After that, the relations help as run-time checks rather than as a way of choosing tools: with all 57 tools in context, removing the ontology lowers Pass@3 from 0.80 to 0.48 (p<0.0001), whereas giving the same knowledge as text lowers it to 0.62. The contribution now restricts GEAR's difficulty advantage to the 12-tool baselines.

Please see the updated paper for more information.

Reviewer_Yj1LOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies which tools should enter a tool-calling agent’s context at each turn when the catalogue is larger than the shortlist the agent can be shown. It proposes GEAR: compute a similarity shortlist (BGE-small cosine top-K plus tools already called), then expand it over a tool graph by following REQUIRES edges to closure and INFORMS / co-use edges one hop, so that prerequisite look-ups and companion tools the user never names reach the agent. On CAR-bench (58 in-car tools, 19 policies, 50 unseen tasks, k = 3) the graph is an LLM-drafted frozen ontology; on ToolBench (1,419 / 11,474 tools) it is mined from gold-tool co-occurrence and used as a score boost. GEAR is compared with similarity search, COLT and MCP-Zero and against a golden-tool upper bound, on gpt-5.4-nano and claude-haiku-4.5, under Pass@k and Pass^k. GEAR attains the highest Pass@3 on both models (0.74 / 0.78), within 0.02 of or above the golden set, with no training and no extra model call. No method moves Pass³ out of a 0.24–0.44 band, and adding the same structure to the prompt lowers a metric.

Critical strengths
  • The problem is framed precisely. Section 3 reduces every method to a single question, which tools should enter the context this turn, and the paper remains within that framing throughout. The method is simple to deploy: one additional artefact, no training, no learned parameters and no per-turn model call, at roughly two seconds of added latency compared with 9.2 s for COLT’s ranking server.
  • The evaluation design is more rigorous than is typical for tool-retrieval work: the retriever is evaluated inside the agent loop, each of the 50 tasks is run three times at temperature 0, Pass@k and Pass^k are reported separately, the main contrast is supported by a paired McNemar test (p = 0.0026, §5.1), and the study is replicated on a second model.
Critical weaknesses

W1. The main benchmark does not instantiate the problem that motivates the paper. Sections 1–2 motivate GEAR by catalogues that exceed the context window. CAR-bench contains 58 tools, whose descriptions would occupy roughly 6k–12k tokens, whereas a single trial already consumes 86k–147k tokens (Table 1). Capacity is therefore not binding on the only benchmark with an agent loop, while ToolBench is evaluated retrieval-only, without an agent, policies or Pass^k.

W2. The control that would establish whether retrieval is necessary, the full catalogue in context, is absent. Given a 58-tool catalogue, exposing all tools is feasible and is the natural baseline for any shortlist method. Tables 1 and 2 contain no such condition; the golden set bounds retrieval from above but is not a no-retrieval condition. Without it, it cannot be determined whether GEAR’s 0.74 reflects better selection or merely the presence of the required tools, nor whether admission control reduces token cost, given that GEAR has the highest tokens per trial. This single experiment would substantially affect the assessment of the paper.

W3. The set of retrieval baselines is narrow for a retrieval contribution. The comparators are BGE-small cosine similarity, COLT and MCP-Zero. ToolGen is cited in Section 2 but not evaluated; Re-Invoke and ToolRet are not cited; BM25 appears only as a citation. K is fixed and not varied, so the simplest alternative to graph expansion, a larger K, is untested. COLT, adapted on 129 instructions and served as precomputed top-12 rankings, is some distance from its intended regime.

W4. The golden-tool condition is not adequately defined and does not behave as an upper bound. On claude-haiku-4.5 GEAR exceeds the golden set on every metric (Pass@3 0.78 vs 0.74). The paper notes this in one sentence (Section 5.1) without analysis, and the condition is described only as the agent being “supplied the correct tools in advance”. Either the golden set is narrower than the tools the tasks require, or the margin reflects noise, in which case the 0.04 margins elsewhere in Table 1 should be read the same way.

Questions for authors

Q1. Could you add a full-catalogue condition to Table 1 on both models?

Q2. Could you add a baseline with policy encoding off on gpt-5.4-nano and recompute the McNemar test?

Q3. What is GEAR’s K, and how do similarity and GEAR compare when K is swept?

Q4. What exactly is in the golden tool set, and why might GEAR exceed the golden tool set on claude-haiku-4.5?

3 comments

Thank you for an insightful review: asking whether retrieval is needed at all when the catalogue fits in context, and requesting the full-catalogue run, changed how the paper reads its CAR-bench results. We address each point below; the general response summarises the new controls.

W1: CAR-bench's 57 tools fit in context, so it tests selection, not capacity. Our capacity argument was meant for catalogues that do not fit, such as ToolBench's, and the introduction now makes it only there. However when we tested using all 57 tools, the performance was significantly worse than GEAR. Futher, when we combine the full tool set with the ontology of GEAR as context we see similar performance to GEAR, highlighting the importance of the ontology. Incorporating the ontology in the full tool set raises Pass@3 from 0.54 to 0.80 (p=0.007).

W2 / Q1 and Q3: Added: Table 1 now lists every retriever at about 12 and 37 tools, and the full catalogue. More tools help until the needed ones are in view (similarity search 0.40 at 15 tools, 0.64 at 37, p=0.004) and not after. GEAR reaches that size per task without tuning K; capping it at 15 tools reduces its performance.

W3: Re-Invoke is now run on both benchmarks: on CAR-bench it equals similarity search at 12 tools and GEAR at 37; on ToolBench it is the strongest method. COLT and MCP-Zero at 37 tools do not differ significantly from GEAR either. ToolRet is now cited; ToolGen trains the agent model, which API-served agents do not allow. COLT remains adapted from 129 training instructions, as the paper states.

W4: It is now defined explicitly (the gold-action tools, the state-reads they require, all read-only and reasoning tools) and no longer called an upper bound. Rerun with policy encoding off, as for GEAR, it matches GEAR (Pass@3 0.74).

Please see the updated paper for more information.

Thank you for the candid response and the new controls. They largely confirm my main concern. Under matched conditions, the full catalogue with the guard layer performs on par with GEAR, and at equal shortlist size GEAR’s lead over the other methods is not significant. As the revision itself notes, the gain comes from the ontology enforced as run-time checks, not from tool selection. This no longer supports the central claim about relational retrieval, so I am keeping my score. Could the authors also clarify whether the original experiments already used the guard layer, which the original submission does not seem to describe?

Thank you for your response.

To address your question, Yes. Every CAR-bench condition in the original submission, including baseline retrieval, ran inside it. We omitted this description from the original submission; The appendix now makes it explicit. To keep the same terms throughout, the revision calls it the ontology layer, as it is built from the same ontology as GEAR's retrieval; it is the layer our previous response called the guard layer.

Tool selection still matters: All methods ran inside the same ontology layer, so the layer alone cannot explain the differences between them. With the ontology fixed, GEAR raises Pass@3 over baseline retrieval at top-12 from 0.40 to 0.74 on gpt-5.4-nano (19 against 2 tasks, p = 0.0002) and from 0.48 to 0.78 on claude-haiku-4.5 (15 against 0 tasks, p = 0.0001). The layer does interact with retrieval: it blocks a write until the required state-read is called, and a short shortlist may lack that read. Excluding every task in which this left a write blocked for baseline retrieval, GEAR's lead remains significant (10 against 2 tasks, p = 0.04; 12 against 0, p = 0.0005).

Shortlist size dynamic top-K: We agree that at equal shortlist size GEAR's lead in Pass@3 is not statistically significant. At 37 tools this is expected on CAR-bench: baseline retrieval at top-35 already puts every tool in the gold actions and every required state-read on the first-turn shortlist in 98% of tasks, as GEAR does. On a shorter shortlist, the ontology's relations make a difference: at 15 tools, this first-turn coverage is 0.70 for GEAR against 0.48 for baseline retrieval (14 against 3 tasks, p = 0.013), although the difference in Pass@3 is not significant (0.44 against 0.40). GEAR also needs no parameter for its shortlist size, which follows from the ontology (27 to 52 tools). Baseline retrieval needs a top-K chosen for the catalogue, and the choice matters: from top-12 to top-35, its Pass@3 rises from 0.40 to 0.64 (p = 0.004). Our top-35 and top-37 controls took their size from GEAR.

The full catalogue: It is level with GEAR (0.80 against 0.74 on gpt-5.4-nano, p = 0.61; 0.70 against 0.78 on claude-haiku-4.5, p = 0.34), so the tools beyond GEAR's shortlist bring no measurable gain. It reaches this level only inside the ontology layer: without it, the full catalogue falls to 0.54, significantly below GEAR (12 against 2 tasks, p = 0.013). GEAR uses fewer tokens per trial (79k against 88k on gpt-5.4-nano, fewer in 42 of 50 tasks), and showing every tool is an option only while the catalogue fits in context.

The ontology layer. On the full catalogue, it raises Pass@3 from 0.54 to 0.80 (17 against 4 tasks, p = 0.007). Adding the same ontology as text in the prompt, on top of the layer, lowers Pass@3 to 0.62 (p = 0.02 and p = 0.04). Our earlier sentence that the gain came from run-time checks rather than tool selection overstated this, and we have rewritten it. The revision reports the two effects separately, the ontology layer with the tool set fixed and GEAR with the ontology layer fixed, and states that on CAR-bench GEAR does not lead at equal shortlist size.

Reviewer_9vwYOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents GEAR, a graph-expanded retrieval method for tool-calling agents. Standard dense retrieval selects tools whose descriptions resemble the conversation. GEAR first obtains this shortlist and then adds tools connected through REQUIRES, INFORMS, semantic-routing, and CONFLICT relations. On CAR-bench, the graph is an LLM-authored ontology over 58 in-car tools. On ToolBench, the graph is mined from tool co-occurrence in training instructions and used to adjust retrieval scores. The paper compares GEAR with dense retrieval, COLT, MCP-Zero, and a supplied-tool condition. On the 50-task CAR-bench split, GEAR improves Pass@3 from 0.36 to 0.74 with GPT-5.4-nano and reaches 0.78 with Claude Haiku 4.5. On ToolBench, graph expansion improves Recall and complete-toolset retrieval over the corresponding dense baseline.

Critical strengths
  1. The paper addresses a real failure mode in tool-calling systems. A request may mention the final action but omit a lookup or prerequisite tool. Explicit tool relations are a natural way to recover these dependencies. The method is simple, does not require an additional LLM call during retrieval, and can use either a small authored ontology or a graph mined from usage data.

  2. The evaluation separates capability from repeated-trial consistency and includes both end-to-end agent behavior and large-catalog retrieval. The paper reports three trials per CAR-bench task, paired significance for the main capability result, two agent models, token use, latency, and a prompt-side factorial ablation. It also states several negative results clearly, including the failure of prompt-side relation labels to improve consistency.

Critical weaknesses
  1. The main CAR-bench comparison does not control shortlist size. Dense retrieval and MCP-Zero return twelve tools, while GEAR expands the dense shortlist by traversing graph edges and can expose additional tools. The paper does not report the average or distribution of GEAR shortlist sizes. Its higher token count, 114k versus 101k for the baseline on GPT-5.4-nano, is consistent with a larger context. A size-matched top-N dense baseline or a graph method that reranks into a fixed budget is needed to show that relational selection, not simply showing the agent more tools, explains the gain.

  2. The supplied "Golden tool set" is not a valid upper bound as presented. GEAR exceeds it on Claude Haiku, and the discussion explains that gold records can leave out information-gathering tools that GEAR retrieves. If required state reads or policy-supporting tools are absent, this condition does not contain the complete correct tool set. Comparisons such as GEAR matching an agent supplied the correct tools therefore overstate the result. The issue is amplified by the CAR-bench judge, which the authors report incorrectly rejects about one in seven conversations whose actions match the gold record.

  3. The CAR-bench evidence is narrow and partly adapted to the evaluation setting. The ontology was authored from the same 58-tool setting used at test time, with no human correction, and only 50 tasks and two small agent models are evaluated. There is no ontology-quality analysis, relation-type ablation, or test on an unfamiliar tool catalog with the authored-ontology version. Consequently, the experiment shows that a benchmark-specific graph helps on that benchmark, but does not establish that the method will remain reliable when tools, policies, or relations change.

  4. The ToolBench experiment weakens the claim that GEAR needs no training data. Its graph is constructed from correct tool co-occurrence in training instructions, and the seed count, boost weight, and edge threshold are tuned on held-out training queries. This avoids gradient training, but still uses supervised task-tool information. The comparison should describe GEAR as a non-parametric trained-data method and separate gains from the co-occurrence labels, score propagation, and tuned encoder. On the off-the-shelf large-catalog setting, the improvements over dense retrieval are also small: Recall@3 rises from 0.235 to 0.243 and COMP@10 from 0.096 to 0.134.

Questions for authors

See Weaknesses.

2 comments

Thank you for a careful and constructive review: the questions about shortlist size, the golden tool set and the judge led directly to controls and corrections that are now in the paper. We address each point below; the general response summarises the new controls.

Shortlist size: GEAR shows 37.6 tools per turn on average against 12–15 for the baselines, so we reran every retriever at about 37 tools (Table 1, Appendix B). At equal size GEAR's lead is not significant (p≥0.18). However when we tested using all 57 tools, the performance was significantly worse than GEAR. However when we combine the full tool set with the ontology of GEAR as context we see similar performance to GEAR, highlighting the importance of the ontology. Incorporating the ontology in the full tool set raises Pass@3 from 0.54 to 0.80 (p=0.007). The abstract and contributions now state the size result, and the difficulty advantage is restricted to the 12-tool baselines.

The golden tool set: "Upper bound" is removed, and the set is defined explicitly: the gold-action tools, the state-reads they require, all read-only tools and the reasoning tools, so it does include the information-gathering tools. Rerun with policy encoding off, as for GEAR, it matches GEAR (Pass@3 0.74).

The judge: Judge-free rescoring (a trial passes if every gold-truth check passes) keeps the order of the methods: GEAR's lead over similarity search stays significant, its lead over COLT does not. The limitations now report this.

Narrow evidence: We agree that the evidence covers one domain, 50 tasks and two small models; the limitations say so. Removing any single relation type keeps first-turn coverage of the needed tools at 0.94 or above, so isolated wrong edges matter little, and the full ontology is drawn in Appendix A. The Methods now state that the co-use edges come from successful runs on the training split.

ToolBench and training data. GEAR trains no model, but its co-occurrence counts come from the training split's labelled tool sets and its settings are tuned on held-out training queries; the text now states this clearly. The gain is small and comes from the content of the edges, since a degree-preserving random rewiring gives none of it. Re-Invoke, now added, is the strongest method on ToolBench.

Please see the updated paper for more information.

Reviewer_9vwYOpenReview ↗

Official Comment

While the additional experiments strengthen the paper, my main concerns remain, so I will maintain my original score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.