SkillShapley: Boundary-Adaptive Shapley Valuation for Skill Step Attribution in LLM Agents

SkillShapley: Boundary-Adaptive Shapley Valuation for Skill Step Attribution in LLM Agents

Summary

This paper introduces SkillShapley, a framework for step-level attribution in LLM agent skills, addressing the open problem of quantifying how each individual step within a skill contributes to overall task performance. The authors model skill-step attribution as a Shapley value-based contribution estimation problem and propose a two-stage approximation method called Boundary-Adaptive Edge Shapley (BAES).

Problem and Motivation

Agent skills are crucial external instructions that enable language agents to execute long procedural tasks such as coding or document processing. Existing skills are created through human manual crafting or agent execution traces, but there is limited understanding of how each step contributes to overall skill performance on specific tasks. The paper notes that skill design is still often done by trial and error, and without fine-grained step-level attribution, practitioners either over-specify skills, wasting context and cost, or prune blindly, risking sharp failures.

The authors treat a skill as a set of step players in a cooperative game, where each step's contribution is quantified with the Shapley value. They motivate this with an exact-reference exploration on low-step-count skills, finding that Shapley rankings produced differentiated step values, whereas Individual and LOO scores produced many ties, and that Removing Shapley top-ranked steps also caused clear performance degradation.

Formulation

A fixed skill is segmented into n semantically coherent steps indexed by N = 1,..., n, where each index is a player. A subset S ⊆ N corresponds to a skill variant that keeps exactly those steps in their original order. The value of a coalition S is its measured benchmark utility: v(S) = (1/M) Σ r(oj(S), yj), where r is the task scoring function, often a binary success indicator, making v(S) an empirical success rate.

The target attribution vector uses Shapley values: ϕi = Σ [S!(n-S-1)!/n!] [v(S ∪ i) - v(S)], with an equivalent size-stratified form: ϕi = (1/n) Σ E[∆i(S) S = k, i ∉ S], where ∆i(S) = v(S ∪ i) - v(S) is a one-step marginal contribution.

Key Observations

BAES is derived from three observations about agent skill evaluation:

1. Configuration cost dominates edge cost – the algorithm must decide which new configuration to evaluate to produce as many useful cached one-flip comparisons as possible.

2. Rewards are discrete and noisy under limited repeated evaluation – when each configuration is scored on a small benchmark subset, observed performance can change sharply between coalitions, making some strata much more uncertain.

3. Rewards often flatten out over large parts of the coalition space – when neighboring coalitions have similar rewards, additional evaluations provide little new information.

BAES Method

BAES operates in two phases. The warmup stage builds a cache that gives broad stratum coverage and identifies which strata remain uncertain. It begins by evaluating anchor configurations (empty set, full set, all singletons, all (n-1)-subsets) to maximize potential edge reuse, then expands with intermediate-size configurations selected by a greedy cache-aware rule. The adaptive stage repeatedly evaluates the single most informative unevaluated configuration, scored by the number of high-priority one-flip edges it forms with the cached configurations.

BAES maintains a cache D of evaluated configurations and records each observed one-flip comparison in its corresponding stratum (i, k). It updates empirical mean µ̂i,k, variance σ̂2i,k, and count mi,k for each stratum. The allocation score is: ai,k = √(σ̂2i,k + ε) / √(mi,k + 1), so high-variance and under-sampled strata receive more attention.

The acquisition score for an unevaluated configuration C is: A(C) = Σ ai,k · b(v(C△ i)), summed over one-flip cached neighbors, where b(y) = 1 + max 0, round((1-y)/g) gives higher priority to configurations adjacent to low-reward cached states.

Stopping and Estimation

BAES tracks a normalized standard-error signal over stratum estimates, using reward granularity g to prevent reacting to numerical changes below benchmark resolution. It stops when the uncertainty signal shows diminishing returns or when a preset maximum sampling count is reached. The final estimator is: ϕ̂i = (1/n) Σ µ̂i,k. If strata remain empty, Fill replaces missing values with the mean of observed stratum means at the same size k.

Experiments

Experiments use SkillsBench skills with three task-skill pairs: offer-letter-generator/docx (n=10, 1024 exact configurations), manufacturing-fjsp-optimization/fjsp-baseline-repair-with-downtime-and-policy (n=9, 512 exact configurations), and dialogue-parser/dialogue-graph (n=11, 2048 exact configurations). Each configuration is evaluated on three benchmark instances, so empirical rewards take values in 0, 1/3, 2/3, 1 with g = 1/3. The agent harness is OpenHands with temperature T = 0.

Experiment 1: Exact Shapley as Skill-Step Attribution

The first experiment tests whether Shapley values are behaviorally meaningful by comparing exact Shapley with baselines (Individual, Leave-One-Out, Random Removal) and LeastCore, validating rankings through top-ranked removal. Results show the full Shapley removal curves drop fastest across the exact-reference tasks, supporting the claim that Shapley values identify behaviorally important skill blocks more reliably than the simpler baselines.

Experiment 2: BAES Approximation Accuracy and Cost

The second experiment compares BAES against Monte Carlo Shapley, Quasi-Monte Carlo Shapley, paired Monte Carlo Shapley, and size-k-truncated Shapley under matched unique-configuration budgets. Results show BAES reaches lower approximation error under smaller budgets, indicating cache-aware acquisition selects more informative coalitions than the competing Shapley approximation baselines.

A cache-efficiency diagnostic shows that under the same 99 unique-configuration budget, BAES Phase 1 yields 206 reusable one-flip marginal edges, whereas MC permutation sampling yields 130 permutation marginal observations, only 115 of which are unique, supporting that BAES improves low-budget approximation partly by creating more reusable marginal-edge evidence.

Case Study: Practical Guidance

The case study reveals that component value is better explained by procedural role than by surface form. High-value steps tend to act as procedural bridges: they connect a task condition to an executable decision rule, an API operation, or a constraint-aware fallback. Low-value steps are often locally correct but action-incomplete: they provide background facts or isolated helper information without changing the agent's next decision.

Examples include a high-value FJSP step (ϕ = 0.1155) that provides a code block with a decision rule for when to consider alternate machines, and a low-value Offer Letter step (ϕ = -0.0194) that provides background text about spell-check and formatting issues without actionable guidance.

Conclusions

The paper concludes that "step importance is highly heterogeneous within a skill, that the identity of critical steps depends on the task, and that full Shapley produces clearer rankings and stronger top-ranked-removal effects than the comparison methods. BAES leverages configuration-level caching and the discrete, high-variance, and often saturated reward structure of skills to approximate Shapley rankings efficiently with a small number of configuration evaluations."

The authors note limitations: "SkillShapley is also best suited to contexts with a fixed player set and reasonably stable benchmark signals; dynamic-length workflows and highly subjective assessment criteria make the underlying cooperative game less well defined. Strongly coupled assembly-line workflows remain especially challenging, because removing an intermediate step may collapse the entire pipeline and make a large Shapley value reflect structural necessity rather than step usefulness. Future work will expand exact anchors, improve uncertainty-aware editing decisions, and extend step attribution to multi-skill agent pipelines and richer evaluation signals."

Improvements to AI Systems:

1. Adaptive Skill Pruning and Compression: Implement SkillShapley's step-level attribution to automatically identify and remove low-value or redundant steps from agent skills, reducing context window usage and inference cost while preserving task performance. The improved system can prune skills dynamically based on measured step contributions, avoiding blind trial-and-error and preventing sharp performance failures from over-aggressive pruning.

2. Uncertainty-Aware Skill Refinement: Use BAES's boundary-adaptive sampling to detect which skill steps have high variance or insufficient evaluation data, then prioritize additional benchmark evaluations for those steps. The improved system can iteratively refine skills by focusing computational budget on the most uncertain and impactful steps, leading to more reliable skill optimization under limited evaluation budgets.

3. Procedural Role-Based Step Ranking: Leverage the finding that high-value steps act as procedural bridges (connecting task conditions to executable decisions) to build a classifier that predicts step importance from textual content and structural position. The improved system can automatically flag action-incomplete steps (e.g., background facts without actionable guidance) for revision or removal, enabling more efficient skill authoring.

4. Task-Specific Skill Customization: Apply the observation that critical steps depend on the specific task to enable a system that re-ranks or re-weights skill steps per task domain. The improved system can maintain a library of skills and automatically select or reorder steps based on learned task-specific Shapley values, improving generalization across heterogeneous tasks without manual re-engineering.

5. Cost-Aware Evaluation Budget Allocation: Integrate BAES's cache-aware acquisition strategy into agent evaluation pipelines to maximize information gain per configuration evaluation. The improved system can allocate limited benchmark runs to the most informative step combinations, reducing evaluation cost by up to an order of magnitude while maintaining accurate attribution for skill optimization.

6. Graceful Degradation Detection: Use the Shapley-based removal curves to identify structurally critical steps (where removal collapses the pipeline) versus functionally useful steps. The improved system can distinguish between steps that are essential for pipeline integrity and those that genuinely improve task outcomes, enabling safer step removal in coupled workflows and avoiding false attributions of usefulness.