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

The paper addresses a fundamental mismatch in skill-based LLM agents: Retrieval answers which skills appear relevant to a query. However, it does not necessarily answer whether the resulting query–bundle pair is worth executing. The authors term this the relevance–utility gap. This gap is consequential because agent execution is typically far more expensive than retrieval: invoking the underlying agent consumes API calls, tokens, tool interactions, and wall-clock time, even when the final verifier reward is zero.

The authors empirically examine this gap on 72 SkillsBench tasks using Graph-of-Skills (GoS) retrieval. They construct local variants of retrieved eight-skill bundles by deleting, adding, or replacing one skill, producing 288 query–bundle pairs. Key findings include:

1. Bundle composition affects realized utility: 22 of the 72 tasks exhibit a reward change under at least one perturbation. Across 216 original–perturbed comparisons, they observe 17 zero-to-positive and 15 positive-to-zero transitions.

2. PPR relevance provides little utility signal: Aggregate GoS relevance scores show Spearman(Rsum, r) = −0.089 and Spearman(Rmax, r) = −0.131, with AUROCs of 0.435 and 0.418 respectively. The authors conclude: These results provide no evidence that higher aggregate PPR relevance reliably identifies query–bundle pairs that will obtain positive reward.

The authors introduce the Reward-Aware Dynamic Execution Gate (RADEG), described as a lightweight, retriever-agnostic decision layer between skill retrieval and agent execution. RADEG learns a low-cost surrogate model that predicts the execution utility of a query–bundle pair before the expensive rollout is launched.

Architecture and Training:

• Query–Bundle Encoding: Uses a fixed text encoder (all-MiniLM-L6-v2) to produce 384-dimensional query and skill embeddings, mean-pooled to form a bundle representation, then concatenated to form a 776-dimensional feature vector (including query embedding, bundle embedding, a four-dimensional bundle-condition indicator, and four GoS PPR summary statistics).

• Offline Utility Learning: A neural encoder (776 → 256 → 128 → 64 MLP with ReLU, dropout 0.3) maps inputs to representations, with a logistic execution head estimating the probability of obtaining non-zero verifier reward. Training uses class-weighted binary cross-entropy.

• Reward-Aware Dynamic Gating: After offline training, RADEG freezes the utility encoder hφ and updates only the lightweight logistic execution head, enabling inexpensive adaptation of the execute/skip boundary without retraining either the retriever or the agent.

Primary Results (five query-level splits):

• RADEG achieves AUROC 0.717 and AUPRC 0.570

• At default threshold τ = 0.5, RADEG skips 68% of agent calls while retaining 61% of the available verifier reward

• This raises reward per executed call from 0.309 under Always-Execute to 0.483, a relative improvement of approximately 56%

Robustness (30 splits): RADEG obtains AUROC 0.747±0.059 and AUPRC 0.595±0.095. At τ = 0.5, it skips 68.1% ± 6.9% of calls while retaining 60.4%±9.2% of reward.

Fixed-Budget Evaluation: At 20% budget, it retains 40% of total reward, versus 15% for PPR-Gate and 19% for Random-Gate. At 40% budget, the corresponding values are 61%, 40%, and 41%. Bootstrap analysis confirms "RADEG's advantage over both baselines remains positive at every evaluated budget (p < 0.001)."

Cross-Agent Adaptation: RADEG obtains AUROCs of 0.733 ± 0.024 on Qwen3.7-Max, 0.628 ± 0.018 on DeepSeek-Chat, and 0.752 ± 0.029 on GLM-5.2, demonstrating the source-trained representation can support utility prediction across multiple downstream execution configurations.

Generalization Across Retrievers: RADEG remains effective across hybrid retrieval (AUROC 0.750 ± 0.032), BM25 (0.683 ± 0.041), and embedding retrieval (0.683 ± 0.057), with performance is consistently stronger for hybrid, BM25, and embedding retrieval than for the gold-distractor construction.

Feature Ablation: Removing the bundle embedding produces the largest numerical decrease in mean AUROC, from 0.744 to 0.730, suggesting bundle semantics provides a useful utility signal.

Runtime Analysis: A complete execution-gating decision requires approximately 75 µs (0.075 ms), whereas the fastest evaluated execution agent requires approximately 60 s, making RADEG over six orders of magnitude smaller than the execution it decides whether to invoke.

The paper concludes that execution-utility prediction as a lightweight, retrieval-agnostic complement to skill retrieval, with applicability beyond GoS to different relevance-based retrieval pipelines. RADEG leaves both the retriever and the downstream agent unchanged, making it applicable to different skill-selection pipelines with low integration cost. Limitations include the scale of collected rollouts, reliance on logged verifier feedback, the scope of controlled perturbation types, and incomplete feedback when skipped executions are not explored.

Improvements to AI Systems Based on This Paper:

1. Add a lightweight execution-utility gate between retrieval and action. Any AI system that retrieves candidate skills, tools, or plans before acting can insert a frozen encoder + logistic head (as in RADEG) to predict whether a retrieved bundle will yield non-zero reward. This reduces wasted API calls, tokens, and latency by skipping low-utility executions (e.g., 68% of calls skipped while retaining 61% of reward).

2. Use reward-aware gating to improve cost-efficiency in multi-step reasoning agents. The improved system can dynamically decide, per query, whether to execute a full reasoning/action rollout or defer to a cheaper fallback (e.g., direct answer or retrieval-only response). This yields higher reward-per-executed-call (e.g., +56% relative improvement) without retraining the underlying agent.

3. Enable cross-agent and cross-retriever transfer of utility prediction. The improved system can pre-train a utility encoder on one agent (e.g., a strong LLM) and adapt only the lightweight head for new agents (e.g., weaker or cheaper models), maintaining AUROC 0.63–0.75. This allows cost-aware deployment across heterogeneous model backends with minimal integration effort.

4. Implement fixed-budget execution planning. The system can use the predicted utility scores to rank candidate query–bundle pairs and execute only the top-k within a compute budget. At 20% budget, it retains 40% of total reward (vs. 15–19% for baselines), enabling principled trade-offs between accuracy and cost in batch or streaming settings.

5. Add a feedback loop for continuous improvement from logged verifier rewards. The improved system can periodically retrain the logistic head using newly collected execution outcomes (positive/negative rewards) without touching the retriever or agent, adapting to shifts in task distribution or reward functions over time.

6. Incorporate bundle semantics as a utility signal. The system can explicitly encode the composition of retrieved skills (not just relevance scores) to better predict execution success, as removing bundle embeddings degrades AUROC from 0.744 to 0.730. This improves robustness against misleading relevance-only rankings.

7. Provide real-time gating decisions at negligible overhead. The improved system can make a gate decision in 75 microseconds, enabling interactive or streaming applications where execution costs are high (e.g., tool calls, code execution, database queries) but gating must not introduce noticeable latency.

8. Support safe exploration of skipped executions. The system can occasionally execute low-utility pairs (e.g., epsilon-greedy) to gather feedback and improve the utility model, addressing the incomplete feedback limitation and preventing the gate from becoming overly conservative.

Agent skills are increasingly used to equip large language model (LLM) agents with reusable procedural knowledge. Although recent work has substantially improved skill retrieval due to the increasing skill libraries, retrieving a plausible skill bundle does not guarantee that executing it is worthwhile. Since every skill-conditioned rollout is computationally expensive, deciding whether a retrieved bundle should be executed has become an increasingly important challenge. To this end, we introduce the Reward-Aware Dynamic Execution Gate (RADEG), a lightweight, retriever-agnostic decision layer between skill retrieval and agent execution. RADEG learns a low-cost surrogate model that predicts the execution utility of a query--bundle pair before the expensive rollout is launched. To obtain informative supervision while controlling for task difficulty, we locally perturb each retrieved bundle by deleting, adding, or replacing one skill, producing matched same-query rollouts that isolate the effect of bundle composition on verifier reward. During deployment, RADEG updates only a warm-started logistic head as new verifier feedback becomes available, enabling inexpensive adaptation of the execute/skip boundary without retraining either the retriever or the agent. Under a query-level held-out evaluation on 288 collected rollouts, RADEG substantially reduces unnecessary agent executions while preserving a large fraction of the downstream verifier reward. It consistently outperforms relevance-based and random gating across different execution budgets, demonstrating that execution-aware surrogate modeling provides a practical and cost-effective complement to skill retrieval.