Paper deep dive
SkillShapley: Boundary-Adaptive Shapley Valuation for Skill Step Attribution in LLM Agents
Chang Liu, Yuqi Zhang, Yiman Zhong, Boyi Liu, Hengjun Wang, Shuyue Wei
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 8/14/2026, 6:20:30 AM
Summary
The paper introduces SkillShapley, a framework for attributing value to individual steps within LLM agent skills using Shapley values. It proposes Boundary-Adaptive Edge Shapley (BAES), a two-phase approximation method (warmup and adaptive sampling) that efficiently estimates step contributions by exploiting cache reuse and handling discrete reward cliffs, validated on SkillsBench.
Entities (7)
Relation Signals (5)
SkillShapley → evaluatedon → SkillsBench
confidence 95% · Experiments on skills from the widely adopted SkillsBench demonstrate that our SkillShapley can effectively and efficiently identify high- or low-value skill steps
SkillShapley → implements → BAES
confidence 95% · We answer these questions with SkillShapley and a budgeted active approximation method called Boundary-Adaptive Edge Shapley (BAES)
SkillShapley → uses → Shapley Value
confidence 95% · We propose to treat a skill as a set of step “players” in a cooperative game and quantify each step’s contribution with the Shapley value
BAES → approximates → Shapley Value
confidence 90% · BAES is a budgeted active approximation method for Shapley values in the skill setting
BAES → optimizesfor → LLM Agent
confidence 85% · BAES is designed for the skill regime where new configuration evaluations are expensive
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Agent skills are crucial external instructions that enable language agents to execute long procedural tasks such as coding or document processing. Existing agent skills are primarily created through human manual crafting or agent execution traces, with limited understanding of how each step contributes to overall skill performance on specific tasks; i.e., there remains an open problem in quantifying the contribution of individual steps within an agent skill. To address this issue, we first model skill-step attribution as a Shapley value-based contribution estimation problem, and then propose SkillShapley, a step-level attribution framework for agent skills. Notably, SkillShapley operates in two phases, motivated by key empirical insights, i.e., discretized benchmark rewards that create sharp performance cliffs, and step interactions that are largely additive rather than synergistic. Specifically, it first identifies informative coalitional regions, and then adaptively samples new coalitions that can yield reusable marginal evidence. Experiments on skills from the widely adopted SkillsBench demonstrate that our SkillShapley can effectively and efficiently identify high- or low-value skill steps, providing several key takeaways for agent skill creation.
Tags
Links
- Source: https://arxiv.org/abs/2608.13173v1
- Canonical: https://arxiv.org/abs/2608.13173v1
Trouble viewing inline? Open PDF directly →
Full Text
45,881 characters extracted from source content.
Expand or collapse full text
SkillShapley: Boundary-Adaptive Shapley Valuation for Skill Step Attribution in LLM Agents Chang Liu Affiliation: Beihang University, Beijing, China Yuqi Zhang Affiliation: Beihang University, Beijing, China Yiman Zhong Affiliation: Beihang University, Beijing, China Boyi Liu Affiliation: Beihang University, Beijing, China Hengjun Wang Affiliation: Beihang University, Beijing, China Shuyue Wei Thanks: Corresponding author: weishuyue@sdu.edu.cn Affiliation: Shandong University, Jinan, China Abstract Agent skills are crucial external instructions that enable language agents to execute long procedural tasks such as coding or document processing. Existing agent skills are primarily created through human manual crafting or agent execution traces, with limited understanding of how each step contributes to overall skill performance on specific tasks; i.e., there remains an open problem in quantifying the contribution of individual steps within an agent skill. To address this issue, we first model skill-step attribution as a Shapley value-based contribution estimation problem, and then propose SkillShapley, a step-level attribution framework for agent skills. Notably, SkillShapley operates in two phases, motivated by key empirical insights, i.e., discretized benchmark rewards that create sharp performance cliffs, and step interactions that are largely additive rather than synergistic. Specifically, it first identifies informative coalitional regions, and then adaptively samples new coalitions that can yield reusable marginal evidence. Experiments on skills from the widely adopted SkillsBench demonstrate that our SkillShapley can effectively and efficiently identify high- or low-value skill steps, providing several key takeaways for agent skill creation. 1 Introduction Large language models (LLMs) are increasingly deployed in the role of autonomous agents that execute multi-step procedures such as debugging, data analysis, and repository-level code changes [1, 21]. A key mechanism for controlling such agents is the skill: a step-by-step natural-language specification that guides the agent through a compound task. Skills, tools, and workflow modules are widely used in systems such as SWE-agent [25], ReAct [26], DSPy [14], and Toolformer [23], enabling substantial capability gains without further training the base model [18]. Despite their practical importance, skill design is still often done by trial and error. Benchmarking can show how well an end-to-end skill performs, but it does not explain which steps are responsible for the performance or where redundancy lies. Without fine-grained step-level attribution, practitioners often either over-specify skills, wasting context and cost, or prune blindly, risking sharp failures. Existing methods have yet to offer a principled resolution to this problem. Prompt optimization methods improve prompts or programs as a whole, prompt compression methods identify compressible tokens, and workflow optimizers improve execution structure, but none directly assigns value to individual steps within a fixed skill. As a result, there is still no clear framework for asking which specific steps of an agent skill are truly doing the work. We propose to treat a skill as a set of step “players” in a cooperative game and quantify each step’s contribution with the Shapley value [24]. Shapley values provide a standard way to measure marginal contribution across contexts and have been successfully used for feature importance and data value [16, 8]. The central question is whether this attribution tool remains meaningful when the “players” are natural-language procedural steps. Our motivation comes from an exact-reference exploration of low-step-count skills. We compare Shapley values against two simple baselines used here: Individual scores, which evaluate each step in isolation, and Leave-One-Out (LOO) scores, which remove one step from the full skill. In this setting, Shapley rankings produced differentiated step values, whereas Individual and LOO scores produced many ties. Removing Shapley top-ranked steps also caused clear performance degradation. This observation suggests that Shapley values can serve as a behaviorally meaningful target for skill-step attribution. It also exposes the practical bottleneck: exact enumeration quickly becomes infeasible as the number of skill steps grows. This work investigates three questions: (1) whether Shapley values are behaviorally meaningful for natural-language skill steps; (2) whether BAES can approximate exact Shapley rankings under a much smaller unique-configuration budget; and (3) what the resulting attribution patterns reveal about skill pruning, revision, and creation. We answer these questions with SkillShapley and a budgeted active approximation method called Boundary-Adaptive Edge Shapley (BAES), which is designed for the skill regime where new configuration evaluations are expensive and cached one-flip comparisons can be reused. Contributions. We make three contributions. (1) We formulate skill-step valuation as a cooperative-game attribution problem, where skill steps are players, retained-step subsets are coalitions, and benchmark performance is the utility. (2) We introduce BAES, a cache-aware approximation method that combines warmup coverage with adaptive acquisition over reusable one-flip marginal edges. (3) We show that BAES approximates Shapley values effectively in the skill setting, achieving better approximation with fewer unique configuration samples than competing estimators. 2 Related Work Agent Skills. LLM agents increasingly use external procedural knowledge, tools, and workflow modules to improve long-horizon task execution, including reasoning-and-acting frameworks [26], tool-use models [23, 18], agent-computer interfaces [25], and declarative LM pipelines [14]. Recent SkillsBench formalizes agent skills as structured procedural knowledge and provides a benchmark of curated skills and deterministic verifiers across diverse tasks [15]. Skill optimization and refinement methods improve skill sets, refine LLM-authored skills, compress skill content, or compile skills across frameworks [20, 7, 6, 22]. However, existing skill-centered work generally treats skills as whole units, rather than assigning contribution scores to individual instruction steps inside a fixed skill. Instruction Attribution in LLMs. Beyond optimizing instructions as wholes, instruction attribution asks which parts of an LLM input or instruction affect model behavior. Prior work probes prompt content [13], compresses prompts by identifying removable tokens [11, 12], or assigns importance to tokens and spans [19, 9]. These methods provide fine-grained evidence about text units, but they do not directly address semantic procedure steps as the units of attribution. Shapley Values for Attribution. Shapley values provide a principled way to aggregate marginal contributions across contexts [24]. They are widely used for feature importance (e.g., SHAP [16]) and data value (e.g., Data Shapley [8]). Because exact computation is exponential, many approximation methods have been proposed, including permutation sampling [4], stratified and uncertainty-aware sampling [3, 2], amortized estimators such as FastSHAP [10], and broad empirical comparisons of Shapley estimators [5]. Most existing estimators target settings where coalition evaluation is relatively cheap compared with executing new LLM-agent skill variants. Across these literatures, prior work optimizes skills or skill sets, but does not attribute value to individual steps inside a fixed skill under a benchmark distribution. SkillShapley fills this gap by treating steps as Shapley players and by introducing BAES, a cache-aware approximation method tailored to the cost model and saturation patterns of skill evaluation. Figure 1: Overview of BAES for budgeted skill-step attribution. The left panel shows how semantic instruction blocks define skill variants and enter the evaluation cache. The middle panel illustrates the warmup stage, which samples broadly across coalition sizes. The right panel illustrates the adaptive stage, which exploits the accumulated cache by selecting the next variant near high-priority regions with uncertain effects, under-sampled coverage, and many cached neighbors. 3 Problem Formulation We formulate skill-step attribution as a cooperative game because a skill is naturally composed of reusable instruction steps whose effects depend on which other steps are present. Let a fixed skill be segmented into n semantically coherent steps indexed by N=1,…,nN=\1,…,n\: X=(x1,…,xn),X=(x_1,…,x_n), (1) where each index i∈Ni∈ N is treated as one player. The segmentation is done over the body of skill.md: blocks may correspond to task-entry guidance, decision rules, API examples, validation instructions, or common pitfalls, and tightly coupled snippets are not split when doing so would make a block semantically incomplete. A subset of players S⊆NS N corresponds to a skill variant that keeps exactly those steps and preserves their original order: XS=(xi)i∈S,orderedasinX.X_S=(x_i)_i∈ S,\ ordered\ as\ in\ X. (2) This subset construction gives the standard cooperative-game notion of a coalition: a coalition is not a different task or a rewritten prompt, but the same skill context with only a chosen set of steps retained. To make the attribution well-defined, all factors other than the selected body steps are fixed across coalitions. The frontmatter is always retained so the skill can still be discovered and loaded. We also keep the non-target context, benchmark instances, and scoring rule fixed. Let ℬ=(qj,yj)j=1MB=\(q_j,y_j)\_j=1^M be the fixed benchmark subset. When the agent runs with skill variant XSX_S on input qjq_j, it produces output oj(S)o_j(S). The value of coalition S is its measured benchmark utility: v(S)=1M∑j=1Mr(oj(S),yj),v:2N→ℝ,v(S)= 1M _j=1^Mr\! (o_j(S),y_j ), v:2^N , (3) where r(⋅,⋅)r(·,·) is the task scoring function. In many skill benchmarks, r is a binary success indicator, so v(S)v(S) is an empirical success rate. Under this cooperative-game view, skill-step attribution asks how much each player contributes to the utility function v across possible coalitional contexts. The desired output is a contribution vector =(α1,…,αn)∈ℝn, α=( _1,…, _n) ^n, (4) where αi _i summarizes the contribution of step i to benchmark performance. The practical constraint is that observing v(S)v(S) requires executing an LLM agent with skill variant XSX_S on benchmark instances, so each new coalition evaluation can be costly. 4 Method 4.1 Overview We instantiate the attribution vector in Eq. (4) with Shapley values. For step player i∈Ni∈ N, the target value is ϕi=∑S⊆N∖i|S|!(n−|S|−1)!n![v(S∪i)−v(S)]. _i= _S N \i\ |S|!(n-|S|-1)!n! [v(S∪\i\)-v(S) ]. (5) An equivalent size-stratified form is ϕi=1n∑k=0n−1[Δi(S)∣|S|=k,i∉S], _i= 1n _k=0^n-1E [ _i(S) |S|=k,\ i∉ S ], (6) where Δi(S)=v(S∪i)−v(S) _i(S)=v(S∪\i\)-v(S) is a one-step marginal contribution. Eq. (6) partitions the target into player-size strata (i,k)(i,k) and separates where uncertainty lives across coalition sizes. BAES is a budgeted active approximation method for Shapley values in the skill setting, where evaluation cost is dominated by new configurations, cached one-flip comparisons can be reused, and rewards are discrete and quickly flatten out. The attribution target remains the standard Shapley value in Eq. (5); BAES changes the sampling policy to decide which coalitions to evaluate when only a small number of configuration evaluations is affordable. When used below, g denotes the smallest observable reward increment. BAES proceeds in two stages. Algorithm 1 summarizes the complete procedure. The warmup stage builds a cache that gives broad stratum coverage and identifies which strata remain uncertain. The adaptive stage then repeatedly evaluates the single most informative unevaluated configuration, scored by the number of high-priority one-flip edges it forms with the cached configurations. This separation between coverage and exploitation is important. If BAES were purely greedy from the beginning, early random fluctuations could lock the sampling process onto a narrow set of strata. The warmup stage prevents this failure mode by first creating enough local structure for acquisition scores to become meaningful. 4.2 Observations BAES is derived from three observations about agent skill evaluation. First, configuration cost dominates edge cost: the algorithm must decide which new configuration to evaluate so that it produces as many useful cached one-flip comparisons as possible. Second, rewards are discrete and noisy under limited repeated evaluation: when each configuration is scored on only a small benchmark subset, the observed performance can change sharply from one coalition to another, making some strata much more uncertain than others. Third, rewards often flatten out over large parts of the coalition space: when many neighboring coalitions have similar rewards, additional evaluations in those regions provide little new information. Useful samples are therefore those that expose larger variation in marginal effects across player-size strata, suggesting adaptive sample allocation rather than uniform sampling. Together, these observations motivate a two-stage strategy: a warmup stage that builds coverage and identifies which strata remain uncertain, followed by an adaptive stage that uses the remaining evaluations only where they continue to reduce uncertainty. In effect, BAES treats cached configurations and their one-flip neighbors as a reusable measurement structure rather than as a set of separate prompt variants. The algorithm benefits when a new configuration simultaneously illuminates several neighboring comparisons, especially around strata whose current estimates remain unstable. 4.3 Two-Stage Procedure BAES maintains a cache D of evaluated configurations and records each observed one-flip comparison in its corresponding stratum (i,k)(i,k). As the cache grows, BAES updates the empirical mean μ^i,k μ_i,k, variance σ^i,k2 σ^2_i,k, and count mi,km_i,k of observed marginal effects within each stratum. These statistics are used to decide where the next evaluation should go. Specifically, BAES assigns each stratum an allocation score ai,k=σ^i,k2+ϵmi,k+1,a_i,k= σ^2_i,k+ε m_i,k+1, (7) so high-variance and under-sampled strata receive more attention. Here uncertainty is empirical rather than model-based: BAES does not predict the reward of an unevaluated coalition, but allocates new cache-aware evaluations toward strata whose observed marginal effects are still variable or poorly covered. BAES also applies a coarse cached-reward weight b(y)=1+max0,round((1−y)/g)b(y)=1+ \0,round((1-y)/g)\, which gives higher priority to configurations adjacent to low-reward cached states. The warmup operator TopPriority ranks strata by ai,k/mi,k+1a_i,k/ m_i,k+1 and selects at most three unevaluated coalitions per round that expose the highest-ranked strata while maximizing A(C)A(C). All ties are broken lexicographically by coalition bit string. Warmup begins by evaluating anchor configurations that maximize potential edge reuse: the empty set, the full set, all singletons, and all (n−1)(n\!-\!1)-subsets. It then expands the cache with intermediate-size configurations selected by a greedy cache-aware rule that prefers candidates with many cached one-flip neighbors. Ties are resolved by a fixed deterministic ordering. Each such configuration yields multiple marginal edges immediately, improving stratum coverage rapidly with only a small number of evaluations. This cache-aware design creates more effective marginal-edge observations from the same configuration budget. Warmup does not aim to produce the final best estimate; its purpose is to stabilize the relative priority ordering of strata. Once the cache contains enough coverage, the algorithm can distinguish strata that are truly uncertain from strata that only appeared uncertain because they had not yet been observed. The predicate RankUnstable compares successive allocation-score rankings with Kendall’s τ and remains true until the exponential moving average of per-configuration τ improvement falls below 1/e1/e of its observed peak after at least 60 observed strata, or until the warmup cap is reached. After the cache reaches broad coverage, BAES transitions to adaptive acquisition. At this stage, BAES scores an unevaluated configuration C by A(C)=∑i:C△i∈ai,k⋅b(v(C△i)),A(C)= _i:\ C \i\ a_i,k· b\! (v(C \i\) ), (8) where the sum runs over one-flip cached neighbors and k is the context size associated with that edge. BAES then evaluates the unevaluated configuration with the largest A(C)A(C), adds it to the cache, and updates all affected strata statistics. This directly targets configurations that simultaneously reduce uncertainty across multiple high-priority strata, rather than spreading samples uniformly across the lattice. Because the acquisition score depends on the evolving cache, BAES is inherently adaptive: the value of evaluating a coalition depends not only on the coalition itself but also on which neighbors have already been evaluated. This makes the sampling trajectory data-dependent, which is precisely what allows BAES to concentrate evaluations in the most informative parts of the search space. Algorithm 1 Boundary-Adaptive Edge Shapley (BAES) Input: N (step players), v(⋅)v(·) (evaluator), g (reward granularity) Param: R (warmup cap), B (total budget) Output: ϕ^∈ℝ|N| φ ^|N| (step values) 1: n←|N|n←|N| (player count); ←∅D← (cache) 2: ℰi,k←∅,∀i,kE_i,k← ,\ ∀ i,k (edge strata) 3: 0←∅,N∪i,N∖i:i∈NS_0←\ ,N\∪\\i\,N \i\:i∈ N\ (anchors) 4: ∀S∈0:v(S)←(S),←∪S∀ S _0:\ v(S)← Eval(S),\ D ∪\S\ 5: ℰ←()E← Edges(D) 6: rank←(ℰ)U_ rank← RankUnstable(E) (rank unstable) 7: while rank∧||<RU_ rank |D|<R do 8: μ^,σ^2,m,ai,k←(ℰ,g)\ μ, σ^2,m,a\_i,k← Update(E,g) 9: batch⋆←(,ℰ,a)C_ batch ← TopPriority(D,E,a) 10: ←∪batch⋆;ℰ←()D _ batch ;\ E← Edges(D) 11: rank←(ℰ)U_ rank← RankUnstable(E) 12: end while 13: uncert←(ℰ,g)U_ uncert← UncertDec(E,g) (uncertainty decreases) 14: while uncert∧||<BU_ uncert |D|<B do 15: ai,k←σ^i,k2+ϵ/mi,k+1,∀i,ka_i,k← σ_i,k^2+ε/ m_i,k+1,\ ∀ i,k 16: C⋆←argmaxC∉A(C)C ← _C A(C) 17: v(C⋆)←(C⋆);←∪C⋆v(C )← Eval(C );\ D ∪\C \ 18: ℰ←();uncert←(ℰ,g)E← Edges(D);\ U_ uncert← UncertDec(E,g) 19: end while 20: μ^i,k←(μ^i,k),∀(i,k):mi,k=0 μ_i,k← Fill( μ_i,k),\ ∀(i,k):m_i,k=0 21: return ϕ^i≜n−1∑k=0n−1μ^i,k,∀i∈N φ_i n^-1 _k=0^n-1 μ_i,k,\ ∀ i∈ N 4.4 Stopping and Estimation To monitor whether additional evaluations still reduce uncertainty, BAES tracks a normalized standard-error signal over the stratum estimates. The normalization uses the reward granularity g, which prevents the stopping rule from reacting to numerical changes below the resolution of the benchmark reward. In Algorithm 1, UncertDec denotes this check: it remains true while the recent slope of the normalized standard-error trajectory is still negative over a data-derived decorrelation window, with a minimum coverage requirement of 85 observed strata. BAES stops when this uncertainty signal shows diminishing returns, or when a preset maximum sampling count is reached. After stopping, it returns the size-stratified estimator ϕ^i=1n∑k=0n−1μ^i,k. φ_i= 1n _k=0^n-1 μ_i,k. (9) If a small number of strata remain empty under a very small sampling count, Fill replaces each missing μ^i,k μ_i,k with the mean of observed stratum means at the same size k, or 0 if that size has no observed stratum, so that ϕ φ is well-defined. The target of BAES remains the standard Shapley value, but BAES is best understood as a budgeted active approximation rather than as a claim of finite-sample unbiasedness under every possible cooperative game. Because the adaptive stage deliberately samples more often in uncertain or high-variation strata, the empirical stratum means in Eq. (9) are optimized for low-budget ranking recovery rather than for uniform random sampling within each stratum. When the budget is large enough that every player-size stratum is directly observed and no fallback fill is used, the returned value reduces to the empirical size-stratified average in Eq. (6); under finite adaptive budgets it should be interpreted as a biased approximation for ranking recovery. Under the finite budgets relevant to LLM skill evaluation, we therefore evaluate BAES by comparing it against exact Shapley references under matched unique-configuration budgets. This matches the intended use case: the practitioner typically needs a low-cost estimate that is close enough to guide which steps to preserve, inspect, or prune, not to report a scalar value with negligible numerical error. This stopping logic is designed for settings where rewards are coarse. When v(S)v(S) is measured on only a few benchmark instances, insisting on near-zero numerical error is unrealistic; a more useful criterion is whether additional evaluations are still changing the practically relevant ranking or only refining values below the reward granularity. Figure 2: Experiment 1 removal validation on the three SkillsBench tasks. Each panel corresponds to one task. The x-axis is the number of removed players following each method’s ranking. The y-axis is the mean success rate over all coalitions that do not contain the removed players. Curves compare simple baselines (Individual, Leave-One-Out, and Random Removal), LeastCore [17], and full Shapley [24]. Stronger attribution should produce a sharper success-rate drop when its top-ranked players are removed. 5 Experiments We evaluate SkillShapley along the three claims introduced above. First, we test whether Shapley values are useful in the skill setting by comparing exact Shapley against simpler contribution measures and by validating the rankings through step-removal behavior. Second, we test whether BAES is a better low-cost approximation to exact Shapley than other Shapley approximation methods under matched coalition-evaluation budgets. Third, we use case studies from the resulting attribution profiles to extract guidance for skill pruning, revision, and creation. This ordering is important: the exact-reference analysis first establishes that full Shapley values are behaviorally meaningful for skill steps; the approximation analysis then tests whether BAES can recover this validated target at lower cost; and the case study translates attribution patterns into editing guidance. 5.1 Experimental Setup All experiments use SkillsBench skills [15]. We split each skill.md into semantically coherent instruction blocks and treat each block as one Shapley player. The frontmatter is always retained so that the skill remains discoverable and loadable by the agent, and auxiliary resources such as reference files and scripts are kept unchanged across all coalitions. For a coalition S, the corresponding skill variant retains exactly the instruction blocks in S while keeping the task, system prompt, output format, benchmark instances, and scoring function fixed. Thus changes in v(S)v(S) are attributed to the retained instruction blocks rather than to changes in evaluation data, package resources, or prompt paraphrasing. Evaluating a coalition requires running the LLM skill on benchmark instances, which can be slow and token-expensive. Therefore, the central cost in this setting is not the number of arithmetic marginal comparisons, but the number of new skill variants that must be executed by the model. We use the number of unique evaluated configurations as the primary cost measure and explicitly reuse cached coalition values whenever possible. All approximation methods are compared under matched unique-configuration budgets. The agent harness is OpenHands. All model calls use temperature T=0T=0, and within each skill all methods are evaluated on the same benchmark subset. 5.2 Exact Shapley as Skill-Step Attribution The first experiment tests whether Shapley values are behaviorally meaningful for skill-step attribution. It focuses on low-step-count SkillsBench skills for which exact enumeration is feasible: offer-letter-generator, manufacturing-fjsp-optimization, and dialogue parser. These skills need not share the same number of instruction blocks; each is evaluated over its own coalition lattice. We compare exact Shapley with simple baselines, Individual, Leave-One-Out, and Random Removal, and with LeastCore [17], and validate the resulting rankings by measuring the utility degradation caused by removing top-ranked blocks. We analyze these exact-reference skills to determine whether the cooperative-game view produces a clearer and more actionable step ranking than simpler alternatives. We evaluate attribution validity through top-ranked removal across all three exact-reference tasks (Figure 2). If a method truly identifies important steps, then deleting high-ranked steps should cause faster utility degradation than deleting low-ranked or randomly selected steps. In Figure 2, 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. We also report whether each method produces tied or diverse value profiles in the accompanying interpretive text, but do not use a separate figure for this diagnostic. This experiment establishes the target that BAES later approximates. Its role is therefore foundational: before claiming that BAES is efficient, we verify that Shapley-based skill rankings correspond to actual deletion risk in the SkillsBench setting. 5.3 BAES Approximation Accuracy and Cost The second experiment tests whether BAES approximates the exact Shapley target more effectively than other Shapley approximation methods. We use the exact Shapley values from the low-step-count skills as references for budgeted approximation. All compared methods estimate Shapley values: BAES, Monte Carlo Shapley [4], Quasi-Monte Carlo Shapley [5], paired Monte Carlo Shapley [5], and size-k-truncated Shapley, a simple baseline that keeps only marginal strata with coalition size at most k. The Monte Carlo variants follow the broader Shapley-estimation literature. We compare them against the full Shapley reference under matched unique-configuration budgets. This design isolates approximation quality from raw API cost: every method pays for the same number of distinct skill variants, while BAES gains an advantage only if its cache-aware acquisition selects more informative coalitions and reuses more marginal edges from the same cache. Figure 3: Experiment 2 approximation error under increasing unique-configuration budgets. The x-axis is the sampling budget, and the y-axis is error relative to full Shapley, aggregated over players. Lines compare BAES, Monte Carlo Shapley [4], Quasi-Monte Carlo Shapley [5], paired Monte Carlo Shapley [5], and size-k-truncated Shapley. Lower curves indicate faster convergence to the exact Shapley reference. Figure 3 focuses on value error as a function of unique-configuration budget. BAES reaches lower approximation error under smaller budgets in the plotted comparison, indicating that cache-aware acquisition selects more informative coalitions than the competing Shapley approximation baselines. We also report a cache-efficiency diagnostic to separate BAES’s sampling mechanism from raw API cost. In our 10-player SkillsBench pilot, 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. This supports the interpretation that BAES improves low-budget approximation partly by creating more reusable marginal-edge evidence from the same number of evaluated skill variants. Figure 4: Token-cost diagnostic for Dialogue Parser coalitions. The y-axis shows the total token count (input plus output tokens) for coalition variants with varying coalition sizes. Figure 4 provides an auxiliary diagnostic on prompt cost for the Dialogue Parser skill. Token count is not strongly determined by coalition size: many coalition-size groups have similar median costs, and their ranges overlap substantially. This suggests that token cost depends not only on how many instruction blocks are retained, but also on which semantic blocks and auxiliary context are present. We therefore treat attribution-guided editing as a way to remove low-value content, not as a guarantee of proportional token savings. 5.4 Case Study: Practical Guidance for Skill Creation and Modification Beyond validating attribution and approximation, SkillShapley provides multiple actionable takeaways for skill creation and modification. Across the three cases, 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. This pattern appears in different forms across the evaluated tasks. In Offer Letter, high-value steps combine placeholder replacement with tables, nested tables, and headers or footers. In Dialogue Parser, high-value steps connect the user scenario to concrete graph-building actions such as node construction, validation, or visualization. In FJSP, high-value steps connect scheduling constraints to repair decisions, such as when to preserve the baseline machine and when to consider an alternative. 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. Overall, these observations suggest that effective skills should be written as compact, decision-complete guidance units, rather than as shorter text or disconnected snippets. High-value step: FJSP P9 (code block) ϕ=0.1155φ=0.1155 # A naive ‘always keep baseline machine’ can cause large start shifts. This often reduces Shift_L1 enough to pass tight budgets without exploding machine changes. Use a simple trigger to consider alternates only when it helps: THRESH = 6 # tune; small instances often 3--10 works # First try baseline machine cand = best_candidate_restricted_to([base_m]) # If shift is large and we still can change machines, search alternates if (cand.start - base_start) >= THRESH and mc_used < max_mc: cand2 = best_candidate_over_all_allowed_machines() if cand2.start < cand.start: cand = cand2 Low-value step: Offer Letter P2 (plain text) ϕ=−0.0194φ=-0.0194 This happens due to spell-check, formatting changes, or Word’s internal XML structure. Practical workflow. SkillShapley is most useful when users already have a fixed skill and want to know which steps are essential, redundant, or worth reinforcing. Start from a candidate skill, use exact Shapley when feasible or BAES with a limited unique-configuration budget to estimate step values, propose one or two low-value deletions or reinforcements, and validate the edit using the same removal-curve protocol that underpins RQ1. This turns skill editing into a measurable loop: hypothesize, edit, and re-evaluate, with attribution yielding a clear proposal mechanism rather than blind trial-and-error. The same logic also supports skill creation, not only pruning. When attribution repeatedly surfaces procedural bridges, those patterns indicate which conditions, decisions, or fallbacks should be made explicit in future skills. Conversely, steps that are repeatedly low-value across tasks and models become candidates for templating, compression, or removal. 6 Conclusion We introduced SkillShapley, a Shapley-value-based framework for step-level skill attribution in LLM agents. Our SkillsBench experiments show 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. Building on these observations, 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. Our exact-reference analysis focuses on low-step-count SkillsBench skills because exact Shapley references are only practical in this regime. 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. References [1] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al. (2020) Language models are few-shot learners. In Advances in Neural Information Processing Systems, Vol. 33, p. 1877–1901. Cited by: §1. [2] M. A. Burgess and A. C. Chapman (2021) Approximating the Shapley value using stratified empirical bernstein sampling. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, p. 73–81. External Links: Document Cited by: §2. [3] J. Castro, D. Gómez, E. Molina, and J. Tejada (2017) Improving polynomial estimation of the Shapley value by stratified random sampling with optimum allocation. Computers & Operations Research 82, p. 180–188. External Links: Document Cited by: §2. [4] J. Castro, D. Gómez, and J. Tejada (2009) Polynomial calculation of the Shapley value based on sampling. Computers & Operations Research 36 (5), p. 1726–1730. External Links: Document Cited by: §2, Figure 3, §5.3. [5] H. Chen, I. C. Covert, S. M. Lundberg, and S. Lee (2023) Algorithms to estimate Shapley value feature attributions. Nature Machine Intelligence 5 (6), p. 590–601. External Links: Document Cited by: §2, Figure 3, §5.3. [6] Y. Gao, Z. Li, Y. Yuan, Z. Ji, P. Ma, and S. Wang (2026) SkillReducer: optimizing LLM agent skills for token efficiency. External Links: 2603.29919 Cited by: §2. [7] S. Gautam, A. Radhakrishna, and S. Gulwani (2026) SkillAxe: sharpening LLM-authored agent skills through evaluation-guided self-refinement. External Links: 2606.10546 Cited by: §2. [8] A. Ghorbani and J. Zou (2019) Data Shapley: equitable valuation of data for machine learning. In Proceedings of the 36th International Conference on Machine Learning, p. 2242–2251. Cited by: §1, §2. [9] M. Horovicz and R. Goldshmidt (2024) TokenSHAP: interpreting large language models with Monte Carlo Shapley value estimation. In Proceedings of the 1st Workshop on NLP for Science (NLP4Science), p. 1–8. External Links: Document Cited by: §2. [10] N. Jethani, M. Sudarshan, I. Covert, S. Lee, and R. Ranganath (2022) FastSHAP: real-time Shapley value estimation. In International Conference on Learning Representations, Cited by: §2. [11] H. Jiang, Q. Wu, C. Lin, Y. Yang, and L. Qiu (2023) LLMLingua: compressing prompts for accelerated inference of large language models. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, p. 13358–13376. External Links: Document Cited by: §2. [12] H. Jiang, Q. Wu, X. Luo, D. Li, C. Lin, Y. Yang, and L. Qiu (2024) LongLLMLingua: accelerating and enhancing LLMs in long context scenarios via prompt compression. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics, p. 1658–1677. External Links: Document Cited by: §2. [13] Z. Jiang, F. F. Xu, J. Araki, and G. Neubig (2020) How can we know what language models know?. Transactions of the Association for Computational Linguistics 8, p. 423–438. External Links: Document Cited by: §2. [14] O. Khattab, A. Singhvi, P. Maheshwari, Z. Zhang, K. Santhanam, S. Vardhamanan, S. Haq, A. Sharma, T. T. Joshi, H. Moazam, H. Miller, M. Zaharia, and C. Potts (2024) DSPy: compiling declarative language model calls into self-improving pipelines. In International Conference on Learning Representations, External Links: Document Cited by: §1, §2. [15] X. Li, Y. Liu, W. Chen, B. You, Z. Di, Y. He, S. Zheng, K. W. Choe, J. Sun, S. Wang, et al. (2026) SkillsBench: benchmarking how well agent skills work across diverse tasks. External Links: 2602.12670 Cited by: §2, §5.1. [16] S. M. Lundberg and S. Lee (2017) A unified approach to interpreting model predictions. In Advances in Neural Information Processing Systems, Vol. 30. Cited by: §1, §2. [17] M. Maschler, B. Peleg, and L. S. Shapley (1979) Geometric properties of the kernel, nucleolus, and related solution concepts. Mathematics of Operations Research 4 (4), p. 303–338. External Links: Document Cited by: Figure 2, §5.2. [18] G. Mialon, R. Dessì, M. Lomeli, C. Nalmpantis, R. Pasunuru, R. Raileanu, B. Rozière, T. Schick, J. Dwivedi-Yu, A. Celikyilmaz, et al. (2023) Augmented language models: a survey. Transactions on Machine Learning Research. Cited by: §1, §2. [19] E. Mosca, F. Szigeti, S. Tragianni, D. Gallagher, and G. Groh (2022) SHAP-based explanation methods: a review for NLP interpretability. In Proceedings of the 29th International Conference on Computational Linguistics, p. 4593–4603. External Links: Document Cited by: §2. [20] K. Nottingham, B. Majumder, B. Dalvi Mishra, S. Singh, P. Clark, and R. Fox (2024) Skill set optimization: reinforcing language model behavior via transferable skills. In Proceedings of the 41st International Conference on Machine Learning, External Links: Document Cited by: §2. [21] OpenAI (2023) GPT-4 technical report. External Links: 2303.08774 Cited by: §1. [22] Y. Ouyang, Y. Xiao, Y. Gu, and X. Zhang (2026) SkCC: portable and secure skill compilation for cross-framework LLM agents. External Links: 2605.03353 Cited by: §2. [23] T. Schick, J. Dwivedi-Yu, R. Dessì, R. Raileanu, M. Lomeli, E. Hambro, L. Zettlemoyer, N. Cancedda, and T. Scialom (2023) Toolformer: language models can teach themselves to use tools. In Advances in Neural Information Processing Systems, Vol. 36. External Links: Document Cited by: §1, §2. [24] L. S. Shapley (1953) A value for n-person games. In Contributions to the Theory of Games, Vol. 2, p. 307–317. External Links: Document Cited by: §1, §2, Figure 2. [25] J. Yang, C. E. Jimenez, A. Wettig, K. Lieret, S. Yao, K. R. Narasimhan, and O. Press (2024) SWE-agent: agent-computer interfaces enable automated software engineering. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, Cited by: §1, §2. [26] S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y. Cao (2023) ReAct: synergizing reasoning and acting in language models. In International Conference on Learning Representations, External Links: Document Cited by: §1, §2. Appendix A Experiment Details For each evaluated skill, we manually segment skill.md into semantically coherent instruction blocks, such as task-entry guidance, decision rules, API examples, validation instructions, or common pitfalls. We do not split inside tightly coupled code snippets or checklist items when doing so would make the block incomplete. Frontmatter is retained in every coalition variant to preserve skill discovery and loading. Auxiliary files, including references, scripts, templates, and test assets, are kept unchanged; only selected instruction blocks in the body of skill.md are included or removed. All coalition variants are generated by deleting steps without rewriting the remaining steps, and the order of steps is kept across all coalitions. The evaluated task–skill pairs are offer-letter-generator/docx (n=10n=10, 1024 exact configurations), manufacturing-fjsp-optimization/fjsp-baseline-repair-with-downtime-and-policy (n=9n=9, 512 exact configurations), and dialogue-parser/dialogue-graph (n=11n=11, 2048 exact configurations). Each configuration is evaluated on three benchmark instances, so the empirical reward takes values in 0,1/3,2/3,1\0,1/3,2/3,1\ and g=1/3g=1/3. The benchmark subset is fixed within each skill and shared by all attribution and approximation methods. All coalitions are executed with the OpenHands harness and temperature T=0T=0. Approximation budgets follow B=3n2B=3n^2 and R=⌊0.4B⌋R= 0.4B , giving (B,R)=(300,120)(B,R)=(300,120), (243,97)(243,97), and (363,145)(363,145) for the three pairs. Metrics are player-wise MAE against the exact Shapley vector and removal success under the top-ranked deletion protocol. Appendix B BAES Implementation Details For each player-size stratum (i,k)(i,k), BAES records mi,km_i,k observed marginal effects and computes μ^i,k=1mi,k∑j=1mi,kΔi(Sj), μ_i,k= 1m_i,k _j=1^m_i,k _i(S_j), (10) σ^i,k2=1mi,k−1∑j=1mi,k(Δi(Sj)−μ^i,k)2. σ^2_i,k= 1m_i,k-1 _j=1^m_i,k ( _i(S_j)- μ_i,k )^2. When mi,k≤1m_i,k≤ 1, we set the empirical variance to the default unseen-stratum variance used by the allocation score. The cached-reward weight used in the acquisition score is b(vcached)=1+max(0,round(1−vcachedg)),b(v_cached)=1+ \! (0,\ round\! ( 1-v_cachedg ) ), (11) where g is the reward granularity. For stopping, BAES monitors the normalized standard error NSEi,k=SE(μ^i,k)max(|ϕ^max|,g)+δ, _i,k= SE( μ_i,k) (| φ_ |,\ g )+δ, (12) whereSE(μ^i,k)=σ^i,kmi,k. ( μ_i,k)= σ_i,k m_i,k. Here ϕ^max=maxi∈N|ϕ^i| φ_ = _i∈ N| φ_i| for the current estimate and δ=10−8δ=10^-8. Default operators. BAES evaluates ∅ , N, all i\i\, and all N∖iN \i\ before greedy warmup. The allocation score is ai,k=σ^i,k2+(g/10)2/mi,k+1a_i,k= σ_i,k^2+(g/10)^2/ m_i,k+1; unseen strata use the median observed positive variance, or g2/4g^2/4 if no positive variance exists. TopPriority ranks strata by ai,k/mi,k+1a_i,k/ m_i,k+1, inspects the top 30 strata, and adds up to three unevaluated coalitions that expose those strata and maximize A(C)A(C). The acquisition score A(C)A(C) sums ai,kb(v(C△i))a_i,kb(v(C \i\)) over cached one-flip neighbors, with lexicographic coalition bit strings breaking ties. RankUnstable stops warmup when the exponential moving average of Δτ/Δ|| τ/ |D| falls below 1/e1/e of its observed peak, with τ>0τ>0 and at least 60 observed strata; otherwise it stops at R. The EMA half-life is three warmup rounds. UncertDec stops adaptive sampling when the recent NSE slope over a decorrelation window is non-decreasing and at least 85 strata are observed; otherwise it stops at B. The decorrelation lag is the first lag whose autocorrelation is not significantly positive under the one-sided 95% rule r<1.645/T−ℓr<1.645/ T- . Fill uses the mean of observed μ^j,k μ_j,k at the same size k for empty (i,k)(i,k), and uses 0 if no stratum at size k has been observed. Recorded diagnostics are stratum coverage, reusable edge counts, and the NSE trajectory.