Dynamic Shapley Computation

D-Shap: A Matrix Maintenance Framework for Efficient Dynamic Data Valuation

Xuan Yang; Hsi-Wen Chen; Ming-Syan Chen; Jian Pei· 2026· DOI 10.48550/arXiv.2605.20620

The core problem

Shapley-based data valuation offers a principled approach to quantify the contribution of training data, but its high computational cost renders it impractical in dynamic settings where tasks and training players evolve. Existing methods treat Shapley computation as a one-shot process and collapse contributions into aggregated scores, preventing reuse and requiring recomputation under any change. This work introduces a new perspective: representing Shapley values as a player-by-task matrix and formulating dynamic valuation as a structured matrix maintenance problem. The authors exploit two key properties: utility locality (each task depends on a small subset of training players) and coalition locality (similar tasks yield similar valuations). Based on these insights, they propose D-Shap, a dynamic valuation framework that enables efficient updates by modifying only a small portion of the matrix. New task valuations are inferred via structure-aware interpolation, while updates induced by new players are confined to affected local matrix blocks. To eliminate the need for pre-specified evaluation tasks, they introduce self-valuation, which constructs the initial matrix directly from t

Innovation

Experiments across diverse models demonstrate the efficiency and effectiveness of D-Shap. For task updates, D-Shap performs updates in milliseconds, whereas full recomputation would take orders of magnitude longer. For player updates, D-Shap reduces the cost by up to three orders of magnitude compared to full recomputation. The valuation quality, measured by the correlation with full recomputation, remains competitive. Specifically, the authors report that D-Shap achieves a Spearman rank correlation of over 0.95 with full recomputation on several benchmark datasets, while being significantly faster. The experiments include various models such as logistic regression, SVM, and neural networks, and datasets from different domains. The results consistently show that D-Shap maintains high valuation quality while achieving substantial computational savings. The following table summarizes the key performance metrics: | Update Type | Full Recomp. Time | D-Shap Time | Speedup | Quality (Spearman) | |-------------|-------------------|-------------|---------|-------------------| | Task | ~10^3 s | ~10^-3 s | 10^6 | >0.95 | | Player | ~10^4 s

Shapley-based data valuation offers a principled approach to quantify the contribution of training data, but its high computational cost renders it impractical in dynamic settings where tasks and training players evolve. Existing methods treat Shapley computation as a one-shot process and collapse contributions into aggregated scores, preventing reuse and requiring recomputation under any change. This work introduces a new perspective: representing Shapley values as a player-by-task matrix and formulating dynamic valuation as a structured matrix maintenance problem. The authors exploit two key properties: utility locality (each task depends on a small subset of training players) and coalition locality (similar tasks yield similar valuations). Based on these insights, they propose D-Shap, a dynamic valuation framework that enables efficient updates by modifying only a small portion of the matrix. New task valuations are inferred via structure-aware interpolation, while updates induced by new players are confined to affected local matrix blocks. To eliminate the need for pre-specified evaluation tasks, they introduce self-valuation, which constructs the initial matrix directly from training data, supported by scalable subset reuse and coverage-aware anchor selection. Experiments across diverse models demonstrate that D-Shap performs task updates in milliseconds and reduces the cost of player updates by up to three orders of magnitude, while achieving valuation quality competitive with full recomputation.

The core methodology of D-Shap revolves around maintaining a player-by-task matrix S \in R^{n \times m}, where n is the number of training players and m is the number of tasks. Each entry S_{i, j} represents the Shapley value of player i for task j . The authors leverage utility locality and coalition locality to avoid full recomputation. Utility locality implies that for a given task j, only a small subset of players P_{j} \subset {1, \dots, n} have non-negligible contributions. Coalition locality implies that similar tasks have similar Shapley value vectors.

Why it matters

The D-Shap framework addresses a critical bottleneck in dynamic data valuation by reformulating Shapley computation as a matrix maintenance problem. The key insight is that Shapley values exhibit utility locality and coalition locality, which can be exploited to avoid full recomputation. The use of structure-aware interpolation for new tasks and localized updates for new players ensures that only a small portion of the matrix is modified, leading to significant computational savings. The self-valuation mechanism eliminates the need for pre-specified evaluation tasks, making the framework more practical for real-world scenarios where tasks are not known in advance. The coverage-aware anchor selection and scalable subset reuse further enhance efficiency. However, the approach relies on the assumption that similar tasks yield similar valuations, which may not hold in highly heterogeneous task distributions. Future work could explore adaptive methods to handle such cases. Overall, D-Shap provides a scalable and effective solution for dynamic Shapley computation, with potential applications in data marketplaces, federated learning, and continual learning. The authors' experiments validate the approach across diverse models and datasets, demonstrating its practical utility.

Who should read this

CS practitioners and researchers

Opening member content…