🤖 AI

From Relevance to Execution Utility: Reward-Aware Dynamic Execution Gating for Skill-Based LLM Agents

This paper introduces RADEG, a lightweight, reward-aware gating mechanism that predicts the execution utility of retrieved skill bundles for LLM agents to significantly reduce unnecessary computational costs while preserving downstream task performance.

Original authors: Liang He, Jingbo Wen, Hongyu Gu, Hao Li, Haoyu Wang, Yixiong Chen, Kangning Cui, Xilu Wang

Published 2026-08-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Liang He, Jingbo Wen, Hongyu Gu, Hao Li, Haoyu Wang, Yixiong Chen, Kangning Cui, Xilu Wang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the conductor of a massive, high-tech orchestra where every musician is a super-smart robot. In the world of artificial intelligence, these robots are called "LLM agents," and they are getting better at solving complex problems, like planning a trip or fixing a broken code. But to do these jobs, they need a toolbox full of "skills"—pre-written instructions or code snippets that tell them how to use specific tools, like a calculator or a map.

The problem is that these toolboxes are getting huge. If you ask the robot to "plan a surprise party," it might pull out a thousand different skills: some for baking, some for sending invitations, and some for budgeting. The robot has to figure out which ones to use. Usually, it uses a "retriever," a sort of librarian that scans the library and picks the skills that sound most relevant to your request. It's like asking a librarian for a book about "space" and them handing you a book about "space travel" because the words match.

But here is the catch: just because a book sounds relevant doesn't mean it's actually useful for your specific homework assignment. Sometimes the librarian hands you a book that looks perfect on the cover, but when you open it, the pages are blank or the story makes no sense. In the world of AI, checking if a skill actually works is expensive. It takes time, money, and computer power to let the robot try using the skill. If the robot tries a bad skill, it wastes all that effort for nothing. So, the big question for scientists is: How can we know if a skill is actually worth trying before we spend all that time and money?

This paper introduces a clever new "bouncer" for AI agents called RADEG (Reward-Aware Dynamic Execution Gating). Think of RADEG as a smart security guard standing between the librarian (the retriever) and the robot (the agent).

Usually, the process works like this: The librarian picks a bundle of skills, and the robot immediately tries to use them. If the skills are bad, the robot wastes time and money, and the result is a failure. The authors of this paper realized that the librarian is really good at finding things that look relevant, but terrible at predicting if those things will actually work. They call this the "relevance–utility gap." It's like the librarian handing you a book titled "How to Bake a Cake" because you asked for "cake," but the book is actually about "how to build a cake-shaped house out of bricks." It's relevant to the word "cake," but useless for your goal.

To fix this, the researchers built RADEG. This new layer doesn't replace the librarian or the robot; it just stands in the middle and asks a simple question: "If we let the robot try this specific bundle of skills, will it actually get a good result?"

Here is how RADEG learns to be a good bouncer. The researchers took a dataset of 72 different tasks and, for each one, they created a few "what-if" scenarios. They took the skills the librarian picked and made tiny changes: they removed one skill, added a random one, or swapped one for a similar-looking one. Then, they let the robot try all these different versions. They found something surprising: changing just one skill could turn a total failure into a success, or vice versa. This proved that the librarian's "relevance score" (how well the skills match the words) was a terrible predictor of whether the robot would actually succeed.

So, RADEG learns from these trial-and-error runs. It looks at the question and the bundle of skills and predicts the "utility" (the chance of success) before the robot ever starts working. If RADEG thinks the bundle is a waste of time, it says "Skip!" and saves the robot from doing the work. If it thinks the bundle looks promising, it says "Go!" and lets the robot proceed.

The results are pretty impressive. In their tests, RADEG managed to skip about 68% of the robot's attempts (saving a huge amount of time and money) while still keeping 61% of the total success points. That means they cut the work in half but still got most of the good results. Even better, RADEG is "dynamic." As the robot tries new things and gets new feedback, RADEG can update its own rules without needing to be retrained from scratch. It's like a bouncer who learns from every person who walks through the door, getting smarter every day without needing a new job description.

The paper also shows that RADEG works well even when the robot changes (like switching from one type of AI brain to another) or when the librarian uses different ways to find skills. It's a flexible, lightweight tool that doesn't require rebuilding the whole system.

In short, the authors found that just because a skill looks right, it doesn't mean it works. By adding a smart, learning gatekeeper that predicts success before the robot starts, we can save a massive amount of computing power while still getting the job done. It's a shift from asking "Does this look relevant?" to asking "Is this actually useful?"—a small change that could make AI agents much faster and cheaper to run.

Technical Summary: From Relevance to Execution Utility

Problem Statement

Large Language Model (LLM) agents increasingly rely on skill libraries containing reusable procedural knowledge to tackle complex, long-horizon tasks. While recent advancements have significantly improved skill retrieval—ensuring that retrieved skill bundles are semantically relevant to a query—this relevance does not guarantee execution utility.

The paper identifies a critical "relevance–utility gap": retrieving a plausible skill bundle does not ensure that executing it will yield a positive outcome. Since agent execution is computationally expensive (consuming API calls, tokens, and wall-clock time), relying solely on retrieval relevance risks wasting resources on bundles that appear relevant but fail to produce useful results. Existing benchmarks and metrics (e.g., Hit@K, Recall@K) focus on ranking relevance rather than the end-to-end utility of the execution, leading to issues such as "skill shadowing" and negative transfer.

Methodology: Reward-Aware Dynamic Execution Gating (RADEG)

To address this gap, the authors propose RADEG, a lightweight, retriever-agnostic decision layer positioned between skill retrieval and agent execution. RADEG predicts whether a retrieved query–bundle pair is likely to produce non-zero verifier reward before the expensive agent rollout is launched.

Core Components

Execution-Gating Objective:
RADEG learns to estimate the probability $s_\theta(q, b) \approx \text{Pr}(r(q, b) > 0 | q, b)$ , where $r$ is the task-specific verifier reward. The decision rule $g_\theta(q, b; \tau)$ determines whether to execute (if $s_\theta \ge \tau$ ) or skip the agent.
Query–Bundle Encoding:
- Semantic Representation: A fixed text encoder ( $E$ ) generates embeddings for the query ( $e_q$ ) and each skill in the bundle ( $e_s$ ). The bundle representation ( $e_b$ ) is obtained via mean pooling of skill embeddings.
- Joint Input: The model concatenates the query and bundle embeddings ( $x_{sem} = [e_q \| e_b]$ ).
- Augmented Features: The implementation includes optional metadata and PPR (Personalized PageRank) statistics from the upstream retriever, though the core formulation relies on semantic content.
Offline Utility Learning:
The system is trained on historical execution records $(q, b, r)$ . A neural encoder maps inputs to a latent space, followed by a logistic head predicting the probability of positive reward. Training uses class-weighted binary cross-entropy to handle the imbalance between zero-reward and positive-reward executions.
Reward-Aware Dynamic Gating:
A key innovation is the separation of the utility encoder (frozen after offline training) and the logistic execution head (updated online).
- During deployment, as new verifier feedback becomes available, only the lightweight logistic head is updated via online gradient descent.
- This allows the decision boundary to adapt to new execution feedback without retraining the retriever, the encoder, or the agent itself.

Motivating Study

The authors empirically demonstrate the relevance–utility gap using 72 tasks from SkillsBench. By perturbing retrieved bundles (deleting top skills, adding irrelevant ones, or replacing with similar alternatives), they found that:

22 of 72 tasks changed their reward status under at least one perturbation.
Aggregate relevance scores (PPR) showed near-zero correlation with downstream execution reward (Spearman $\rho \approx -0.09$ ).
Relevance scores failed to predict positive reward (AUROC $\approx 0.42$ ), confirming that relevance is a poor proxy for execution utility.

Key Contributions

Empirical Diagnosis: The paper provides a controlled analysis showing that downstream reward is sensitive to bundle composition, while standard retrieval relevance scores offer little predictive signal for execution success.
RADEG Framework: It introduces a post-retrieval, pre-execution gating module that estimates execution utility using observed feedback, operating independently of the specific retriever or agent architecture.
Dynamic Adaptation: The method enables inexpensive adaptation of the execution/skip boundary via online updates to a logistic head, avoiding the cost of retraining complex models.
Evaluation: Extensive experiments on 288 collected rollouts demonstrate that RADEG significantly reduces unnecessary executions while preserving a substantial fraction of downstream reward.

Experimental Results

Evaluated on a query-level held-out protocol with 288 rollouts:

Prediction Performance: RADEG achieved an AUROC of 0.717 and AUPRC of 0.570, substantially outperforming relevance-based gating (PPR-Gate: AUROC 0.447) and random gating (AUROC 0.500).
Execution Efficiency: At a default threshold ( $\tau=0.5$ ), RADEG skipped 68% of agent calls while retaining 61% of the total verifier reward. This increased the reward-per-call from 0.309 (Always-Execute) to 0.483.
Fixed-Budget Performance: Under a strict 20% execution budget, RADEG retained 40% of the total reward, compared to 15% for PPR-Gate and 19% for Random-Gate.
Generalization:
- Cross-Agent: The model trained on Claude Sonnet executions successfully adapted to Qwen3.7-Max, DeepSeek-Chat, and GLM-5.2 with only head updates, maintaining AUROCs between 0.628 and 0.752.
- Cross-Retriever: RADEG remained effective across different upstream retrievers (Hybrid, BM25, Embedding) and bundle sizes, indicating it learns semantic compatibility rather than relying on specific retrieval artifacts.
Overhead: The computational overhead of RADEG is negligible (~75 $\mu$ s per prediction) compared to agent execution times (ranging from 60s to >1500s).

Significance and Claims

The paper claims that execution-aware surrogate modeling provides a practical and cost-effective complement to skill retrieval. By decoupling the decision of what to retrieve from whether to execute, RADEG addresses the high cost of agent rollouts without modifying existing retrieval pipelines or agent architectures.

The authors position RADEG as a modular solution that:

Leaves the retriever and agent unchanged.
Adapts to new feedback with minimal computational cost.
Generalizes across different agents and retrieval strategies.

The study acknowledges limitations, including reliance on logged verifier feedback, the scale of collected rollouts, and the scope of controlled perturbations. Future work is suggested to evaluate RADEG on larger skill libraries and in real-world deployment settings to measure monetary and latency savings.