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

Research Question and Motivation

Large language models are increasingly deployed as autonomous agents that rely on external natural-language specifications called skills to execute multi-step tasks such as coding and document processing. However, skill design is still largely driven by trial and error. Benchmarking shows end-to-end performance but fails to reveal which individual steps are valuable, redundant, or harmful. Existing methods optimize prompts or workflows as wholes rather than assigning granular contribution scores to individual instruction steps. This paper investigates whether Shapley values can provide a behaviorally meaningful measure for skill-step attribution and how to approximate these values efficiently when executing agent skill variants is costly.

Cooperative-Game Attribution and BAES

The authors model skill-step attribution by treating each semantically coherent step in a skill as a player in a cooperative game, where retained step subsets form coalitions and benchmark performance serves as utility. Because exact Shapley calculation requires an exponential number of evaluations, the authors introduce Boundary-Adaptive Edge Shapley (BAES), a budgeted active approximation method tailored to agent skill evaluation. BAES operates in two distinct phases: a warmup stage that builds broad stratum coverage and uncovers local structure, followed by an adaptive stage that selectively evaluates new configurations near uncertain, high-priority regions by reusing cached one-flip marginal comparisons. This strategy maximizes the utility of each expensive agent execution.

Empirical Findings and Utility Validation

Experiments on SkillsBench demonstrate that exact Shapley rankings successfully differentiate step values and produce clear performance degradation when top-valued steps are removed, whereas simpler baselines like individual evaluation or leave-one-out scores yield excessive ties. Furthermore, BAES closely approximates exact Shapley rankings using significantly fewer unique configuration samples than alternative estimators. These attribution patterns provide practical takeaways for agent skill creation, enabling developers to prune bloated instructions, reduce context costs, and avoid sharp task failures.