SkillShapley Incrementally Estimates the Value of Agent Skills, Producing 206 Reusable Marginal Comparisons From 99 Configurations

Agent skills are typically long instruction documents containing operating procedures, validation rules, API examples, and common pitfalls, but an aggregate score cannot reveal which steps are genuinely useful. SkillShapley divides a skill into semantic blocks while preserving their original order, treats each retained set of steps as a coalition, and uses the success rate on a fixed test set as the utility. A step’s Shapley value is its average marginal gain across all possible contexts.

Exhaustive enumeration requires running $2^n$ skill variants, so the team proposed Boundary-Adaptive Edge Shapley (BAES). The system first tests the empty set, the full skill, every single-step configuration, and every configuration missing one step. It then selects the next coalition based on the variance and sample count in each “step–set size” stratum. If a new configuration differs by only one step from several cached configurations, a single agent run can generate multiple reusable marginal comparisons. More budget is allocated to regions with lower rewards and less stable results.

The study used SkillsBench, the OpenHands harness, and a temperature setting of zero. Experiments on three skills that could be exhaustively enumerated showed that removing high-value steps according to the full Shapley ranking caused the success rate to decline faster than removal based on standalone testing, leave-one-out, LeastCore, or random selection. In a ten-step experiment, both methods evaluated 99 unique configurations, but BAES produced 206 single-step marginal edges in its first phase. Monte Carlo permutation produced only 130 observations, 115 of which were unique. The authors also report that, under the same configuration budget, BAES converged more quickly toward the full Shapley ranking.

This turns skill maintenance from repeated trial and error on an entire prompt into a diagnostic process that can identify redundant, fragile, or negatively contributing steps. However, under a limited budget, BAES is a biased estimator designed to recover rankings, not an unbiased Shapley-value computation. Full validation covered only three skills with small numbers of steps, while the ten-step result was merely a pilot. Researchers still determine the semantic segmentation, and removing low-value blocks does not guarantee a proportional reduction in token costs. The next questions are whether the code, configuration cache, and complete evaluation records will be released, and whether the results can be reproduced across models, stochastic decoding settings, and longer skills.