RATED: Reliability-Aware Tool Retrieval for AI Agents via Execution Dynamics

If tool retrieval only optimizes semantic relevance, it cannot promptly switch candidates after execution failures, and retraining the retriever cannot keep up with runtime changes.

• Scenario: The authors argue that LLMs cannot directly perform real-world actions, so agents must call external tools to query databases or run workflows. The authors claim the bottleneck has shifted to retrieving the correct entry from an ever-growing tool library.
• Existing shortcomings: ToolLLM and ToolExpNet treat retrieval as static ranking, matching only semantically against tool documentation. TRFeedback and ToolRL use execution feedback, but the authors point out they still optimize how the LLM plans and calls tools in a static environment; ToolRL uses GRPO to update from batched trajectories, and the object is still the planner, so it cannot immediately reorder between adjacent requests.
• Authors' observation: The authors crawled the catalogs of LangChain, CrewAI, LlamaIndex, and n8n. The authors claim that although the libraries are growing (Figure 1), over 50% of tools have broken links, missing authentication, and other issues; when functions are similar, semantics cannot distinguish which one will execute successfully.
• Proposed object: RATED uses frozen dual encoders for semantic matching, then a lightweight contextual bandit to rerank based on execution feedback, without retraining the semantic model. EcoAgent contains 5,172 real tools; the abstract writes over 210,000 query–tool pairs, and Section 2 additionally gives the counts of synthetic positive and negative pairs.

The paper has no separate Related Work section; comparisons are mainly written in the introduction and methods.

Static tool retrieval

• ToolLLM (Qin et al., 2023) and ToolExpNet (Zhang et al., 2025): they make tool retrieval a static ranking, using dense retrieval or an experience network to map queries to tool documents by semantics. The authors consider this approach to ignore execution-time availability.
• The introduction uses the tool library retrieval bottleneck to point to large-scale API scenarios, without further expanding on the method details of other static retrievers.

Execution feedback and planners

• TRFeedback (Xu et al., 2024) and ToolRL (Qian et al., 2025): they use execution feedback for tool use, with the goal still being how the LLM plans and calls. The authors note that both still target static environments.
• GRPO (Shao et al., 2024): the authors state that ToolRL uses it to update the LLM from batch trajectories, and the update target is the planner, so it cannot immediately change the candidate order after a single failure.

Contextual bandits

• LinUCB (Li et al., 2010) and linear bandits with immediate rewards (Abe et al., 2003): the authors use them to show that decisions can be conditioned on the current query, only the selected tool's feedback is observed, and adjustments can be made without retraining the retriever.
• Standard LinUCB and Global MAB (Auer et al., 2002): the authors write that standard LinUCB weights history equally and adapts slowly when arm quality changes; Global MAB's statistics are independent of the query context, which the authors state is cheaper to maintain but cannot represent rewards that depend on the current query.
• Discounted LinUCB (Garivier and Moulines, 2011): the authors choose it, lowering the weight of old rewards before updating so recent failures change scores faster, with one linear model per tool.

Baselines and benchmarks

• Baseline methods: TF-IDF, BM25; OpenAI Ada-002, BGE-M3, GTE-Large, E5-Large-v2; DRAGON and SPLADE-v3 not fine-tuned on EcoAgent-Syn; BGE-Reranker-v2-m3; ToolLLM API Retriever. Dynamic comparisons also include Health Check Blacklist, Retry (k=3), and ToolRL-like batch GRPO.
• Benchmark: self-built EcoAgent; real queries come from ToolBench and, after filtering, become EcoAgent-Real.

The authors place the difference in: semantic matching remains frozen, and reliability is estimated by an online bandit from single execution results, thereby changing the ranking between requests rather than retraining the planner or retriever.

RATED has two stages: a frozen semantic retriever first narrows the candidates, and a discounted LinUCB then reranks by execution feedback. The tool library U has M=5,172 in EcoAgent.

Problem Setting

• At time t the agent issues a query q_t, the retriever returns a candidate set of size K, and the policy selects one tool to execute. The goal is to increase the probability of successful execution.
• Unlike a fixed mapping, tools can fail at runtime. The authors write that success depends on both the semantic score and a time-varying reliability.
• After execution, only the selected tool gives binary feedback: 1 for success, 0 for error or timeout. The authors use a contextual bandit to handle this partial feedback.
• A new tool can be added by encoding its document with the tool encoder, without retraining the encoder.

Semantic Module

• The encoder is based on DRAGON, with separate query and tool encoders. The CLS representation is taken and L2-normalized, and the semantic score is their dot product: S_sem(q,a)=e_q^⊤ e_a.
• The authors state that DRAGON is suitable for open-domain retrieval, but tool descriptions have specialized API language, so they fine-tune both encoders on EcoAgent-Syn with in-batch InfoNCE. Training uses hard negatives from construction time, with other in-batch samples as additional negatives. The encoders are frozen at deployment.
• Inference takes the top-K by semantic score. In experiments K=10 and temperature τ=0.05.

Metadata Prior

• When execution history is scarce, a static prior is used for initialization. It is weighted by name–description consistency, source weight, and document quality, with weights summing to 1. Experiments use (0.5, 0.3, 0.2).
• Consistency is the SBERT cosine between the tool name and description. Source weights: official lists 1.0, LangChain, CrewAI, LlamaIndex 0.9, n8n 0.8, others 0.6. Document quality normalizes description length and tag-string length relative to the median, then passes through a logistic with a 0.6 and 0.4 combination.
• The arm bias is initialized as the prior times x_0, where x_0 is one over the square root of d. Tools with a score of at least 0.8 are marked in the benchmark statistics, 2,940 in total (56.8%); this threshold does not replace the prior itself. All three items read only catalog fields, and the authors state that no per-tool manual scoring is needed.

Discounted Update and Fusion

• Each tool maintains a matrix A and a vector b. The bandit score is the inner product of the parameter estimate and the query vector, plus an exploration coefficient α times the uncertainty. Experiments use α=0.1.
• After observing feedback, the update is discounted by γ, with experiments using γ=0.95: old statistics are first multiplied by γ, then the current outer product and the feedback times the query vector are added. The authors state this emphasizes recent feedback. The implementation keeps the diagonal, and the scoring complexity is O(d).
• The final score weights the semantic score, the bandit score, and the static prior, with weights summing to 1: S_final=w₁ S_sem+w₂ S_bandit+w₃ r_static. The validation set sets (0.75, 0.15, 0.10), fixed at test time. There are also 2,000 warm-up pairs. Algorithm 1 gives the single-step loop.

Benchmark Construction

• Tool definitions come from the four platforms above, with fields including functional description, name, endpoint, and authentication. The encoder is trained only on EcoAgent-Syn; retrieval and dynamic experiments are done on the test split of EcoAgent-Real, with hyperparameters selected on the validation split.
• Syn is generated by Gemma-3-1b, which produces 10–20 queries per tool, with the prompt in Figure 2. Section 2 writes that queries are limited to 5–120 words, and near-duplicates with Jaccard similarity above 0.7 are removed. Hard negatives come from SBERT, with additional random negatives. The scale is 69,501 synthetic queries, 70,122 positive pairs, and 140,244 negative pairs.
• Real comes from ToolBench. GTE-Large takes the top-5 for each query, drops pairs with cosine below 0.7, and Gemma-3-1b keeps only pairs with a functional match score of at least 0.85. A manual check of 200 items agrees with the validator on 94%. After deduplication, there are 6,379 queries and 9,946 verified pairs.

Experimental Setup

• Hardware and fine-tuning: a single NVIDIA GeForce RTX 5070 (12 GB). DRAGON is fine-tuned on EcoAgent-Syn for 1 epoch, batch size 8, learning rate 1e-5, warmup 1,000 steps, τ=0.05, max length 256, mixed precision.
• Retrieval comparisons: TF-IDF, BM25, OpenAI Ada-002, BGE-M3, GTE-Large, E5-Large-v2, unfine-tuned DRAGON, SPLADE-v3, BGE-Reranker-v2-m3 (reranking DRAGON's top-50), ToolLLM API Retriever. RATED uses the fine-tuned DRAGON as its backbone, with variants Full, w/o Contrastive, w/o Feedback, and w/ Global MAB.
• Dynamic comparisons: Health Check Blacklist permanently excludes a tool after one failure, sharing DRAGON's ranking with Retry (k=3); Retry tries up to 3 candidates within the same step and keeps no memory across steps. ToolRL-like Batch GRPO periodically updates weights rather than updating online.
• Bandit settings: top-K=10, α=0.1, γ=0.95, warm-up 2,000 pairs, fusion weights (0.75, 0.15, 0.10), prior weights (0.5, 0.3, 0.2).
• Offline metrics: MRR, Recall@1, Recall@5 on the EcoAgent-Syn and EcoAgent-Real test splits. The paper does not report the number of items in the test splits. Judgments are against ground truth, not LLM scoring.
• Dynamic protocol: T=10,000 sequential selections. To simulate persistent failures, tools are sorted by the frequency of real tool occurrences in the evaluation stream, the top 10% are skipped, and the next ρN are marked as failed; the failed set is fixed before the run starts and remains unavailable from the failure onset until the end. ρ is 20% and 30%. Post-Fail SR and FSR are averaged over steps 2,001 to 5,000, a total of 3,000 steps. SR requires the selected tool to equal the ground truth and have Status available; FSR is the proportion of selected unavailable tools. AS uses a window width of 200 and reaches θ times the pre-failure peak; θ=0.9 at 20% and θ=0.8 at 30%, with failure to reach it recorded as Failed. The paper does not report the number of repetitions. In the method, y_t is execution success or error/timeout; the metrics in the table are computed from the simulator Status.

Main Results

The table below is excerpted from Table 2. SPLADE-v3, BGE-Reranker, Retry (k=3), and RATED (w/ Global MAB) are omitted. SR means Post-Fail SR. AS values at the 20% failure rate are not placed in the table; Full is 1,603, Health Check is 2,620, and ToolRL-like is 2,620.

Swipe horizontally to read the table

Method	20% SR	20% FSR	30% SR	30% FSR	30% AS
BM25	18.8%	20.0%	10.2%	30.0%	Failed
ToolLLM API Retriever	17.4%	79.6%	10.5%	86.2%	Failed
OpenAI Ada-002	19.4%	80.4%	11.1%	88.8%	Failed
DRAGON (pretrained)	78.1%	18.1%	75.7%	21.2%	Failed
Health Check Blacklist	82.6%	1.4%	80.2%	1.9%	Failed
ToolRL-like Batch GRPO	80.3%	5.4%	79.5%	6.1%	1
RATED (w/o Feedback)	81.1%	16.5%	78.7%	19.4%	Failed
RATED (Full)	83.4%	2.5%	82.1%	2.9%	0

• The authors state that static retrievers often select unavailable tools and do not recover within the evaluation range. Relative to the no-feedback variant, Full lowers FSR at both failure rates and keeps Post-Fail SR above 82%. Section 4.4 states 7.3 times relative to pretrained DRAGON and 30 times relative to ToolLLM; the Conclusion writes FSR of 2.5–2.9%, 7.3 times relative to static DRAGON.
• In the table, Health Check's FSR is lower than Full's, but its 30% AS is Failed. The authors state the blacklist has low FSR but slow recovery. At 20%, its AS is 2,620, while Full's is 1,603.
• Omitted rows: Retry at 20% has SR 84.8%, AS 70, and FSR 16.4%; at 30%, AS is Failed. SPLADE-v3 has FSR 7.7% and 9.1%, SR 16.0% and 15.8%, and AS Failed. BGE-Reranker has SR 83.2% and 81.0%, FSR 17.5% and 20.5%, and AS Failed. Global MAB at 30% has FSR 13.2%, SR 74.3%, and AS 2,718. The authors state Global MAB is worse than the full model, and batch GRPO's FSR is still higher.

Offline Retrieval

• Table 1: on Syn, Full's MRR, Recall@1, and Recall@5 are 0.845, 0.804, and 0.893. The authors state all three rank first in that table. w/o Contrastive and pretrained DRAGON have the same values, with Syn MRR 0.751 and Real 0.518. The authors attribute the gain to contrastive fine-tuning.
• On Real, Full is 0.618, 0.516, and 0.740. The authors report a relative MRR improvement of 52.2% over ToolLLM (MRR 0.406) and state it is still lower than Ada-002 (0.670) and SPLADE-v3 (0.626). In the same table, BGE-Reranker's MRR is 0.642 and Recall@5 is 0.840, also higher than Full. Full's Recall@1 is the highest in that column of the table.
• The authors state that high offline ranking on real queries does not guarantee correct selection after a tool fails at runtime.

Latency

• Table 3, at batch size 1, relative to DRAGON encoding only. Encoding averages 3.223 ms, with P95 at 4.269 ms.
• RATED (Full) averages 3.395 ms, with P95 at 4.391 ms, an extra 0.172 ms. The no-feedback variant adds 0.025 ms, and Global MAB adds 0.108 ms. The abstract also writes overhead of less than 1 ms.
• ToolRL-like Batch GRPO averages 17.839 ms, an extra 14.616 ms. The authors state RATED's overhead is far lower than this periodic synchronization while still reducing failed selections.

Hyperparameter Sensitivity

• Figure 4(a) sweeps w1 and w3 under 20% failures, with bandit settings fixed. The authors state Post-Fail SR rises with w1 and is highest at w1=0.75, w3=0.10; FSR rises slowly and stays in the low single digits. The authors state they therefore trade about 1 FSR percentage point for the highest SR in that sweep.
• Figure 4(b) fixes the fusion weights and sweeps γ and α. The authors state SR is highest at γ=0.95, with the three α curves nearly coinciding; FSR rises slowly with γ. The validation set chooses γ=0.95, α=0.1.
• The curve shapes above come from the text of Section 4.5; the main text does not give point-by-point readings of other points on the figures.

Other Ablations and Analyses

• No feedback: Table 2, FSR at 20%/30% is 16.5%/19.4%, SR is 81.1%/78.7%, and AS is Failed. Section 4.6 writes that this variant only adds the static prior.
• Global MAB: at 20%, FSR is 10.1% and AS is 3,852; at 30%, FSR is 13.2%, SR is 74.3%, and AS is 2,718.
• Contrastive fine-tuning: in Table 1, w/o Contrastive and pretrained DRAGON have identical values on all six metrics.
• Fusion weights are set to (0.75, 0.15, 0.10) on the validation set, and prior weights to (0.5, 0.3, 0.2).
• Health Check's AS at 30% is Failed; ToolRL-like's AS at 30% is 1 and FSR is 6.1%.
• At 30%, the highest FSR in the table is Ada-002's 88.8%; the lowest Post-Fail SR is BM25's 10.2%.

Limitations and Future Directions Noted by the Authors

The paper does not specifically discuss limitations. The Conclusion lists two future directions:

• Cold start for new tools: evaluating this cold-start path on newly added tools remains future work (Conclusion).
• Real runtime: validating RATED in a live agent runtime remains future work (Conclusion).

Experimental Coverage

• Offline metrics are reported on the EcoAgent-Syn and EcoAgent-Real test splits; the dynamic experiments are failure injection with failure rates of 20% and 30%, T=10,000, and a summary window of 3,000 steps (Section 4.2, Tables 1–2).
• Comparisons include lexical, dense, and neural retrievers from Section 4.3, the ToolLLM API Retriever, and the blacklist, Retry (k=3), batch GRPO, and four variants of RATED.
• The semantic backbone is DRAGON. Query synthesis and Real annotation use Gemma-3-1b, candidate recall uses GTE-Large, and hard negatives and consistency scores use SBERT (Sections 2–3).
• The manual check is a stratified sample of 200 items, with 94% agreement with the LLM validator (Section 2). Latency is measured on an RTX 5070 with batch size 1 (Table 3).
• The paper does not report the number of items in each split of EcoAgent-Real, nor the number of repetitions for the dynamic experiments. The cold-start evaluation of new tools and live runtime validation mentioned in the Conclusion have no corresponding results in the main text.

RATED is aimed at agent tool libraries, handling semantic matching and whether the tool can still execute at runtime separately.

• Problem: Tools can fail during execution. Ranking only by semantics, or using batch trajectories to modify the planner, cannot immediately change the candidate order after a single failure. The authors state that over 50% of tools in the catalogs of four platforms have broken links or lack authentication.
• Method: Fine-tune the DRAGON dual encoder on EcoAgent-Syn with InfoNCE and freeze it, then take the top-10 by dot product. Each tool has its own discounted LinUCB (γ=0.95, α=0.1), cold-started with a catalog prior, then fused with the semantic score. Feedback is only the success or failure of the selected tool.
• Data: 5,172 tools from four platforms. Syn has 70,122 positive pairs and 140,244 negative pairs; Real has 6,379 queries and 9,946 verified pairs. The abstract also writes over 210,000 query–tool pairs.
• Offline: Full's MRR on Syn is 0.845. On Real it is 0.618, and the authors report a 52.2% improvement relative to ToolLLM's 0.406; in the same table Ada-002 is 0.670 and BGE-Reranker is 0.642 (Table 1).
• Dynamic and latency: Under 30% injection, Full's Post-Fail SR is 82.1%, FSR is 2.9%, and AS is 0; ToolLLM's FSR is 86.2% and it does not recover. In the same table, Health Check's FSR is 1.9% and AS is Failed. At 20%, Full's FSR is 2.5% (Table 2). Relative to encoding only, the extra latency is 0.172 ms (Table 3); the abstract writes less than 1 ms.
• Authors' conclusion: The authors state that execution feedback should be incorporated into retrieval, and that RATED can discover tools in dynamic environments. Cold start on newly added tools and real runtime validation are written as future work.