Dynamic Shapley Computation

Xuan Yang, Hsi-Wen Chen, Ming-Syan Chen, Jian PeiarXiv 2026 · arXiv

TL;DR

Shapley-based data valuation is a powerful tool for quantifying data contributions, but its exponential computational cost makes it impractical when training data or evaluation tasks change dynamically. This paper introduces D-Shap, a framework that treats Shapley values as a persistent player-by-task matrix and leverages "model-induced locality" to perform fast, localized updates. D-Shap achieves millisecond-level task updates and up to a $1000\times$ speedup for data updates while maintaining high valuation accuracy.

What Problem Does This Paper Address?

In machine learning, data valuation helps us understand which training examples are most valuable for tasks like data pricing, dataset curation, and model debugging. The Shapley value is the gold standard for this, but computing it is notoriously expensive (#P-hard), often requiring training a model on exponentially many data subsets.

Worse still, real-world machine learning pipelines are dynamic: new evaluation tasks constantly appear, and new data contributors regularly expand the training set. Existing Shapley estimation methods are fundamentally static; they collapse fine-grained task-specific contributions into a single aggregated score per player. Consequently, whenever a new task or player arrives, the entire expensive computation must be rerun from scratch. This paper tackles the challenge of performing dynamic, incremental Shapley updates without global recomputation.

Methods

The core innovation of D-Shap is shifting the perspective of Shapley values from a one-shot aggregated score to a persistent player-by-task matrix ($\Phi$), where each entry records the contribution of a specific training instance (player) to a specific evaluation objective (task).

To maintain this matrix efficiently, D-Shap exploits model-induced locality—the insight that a model's performance on a given task usually depends only on a small subset of relevant training instances (e.g., nearest neighbors in KNN or local neighborhoods in Graph Neural Networks). This gives rise to two types of localized updates:

  1. Task-Incremental Updates (Utility Locality): When a new task arrives, D-Shap avoids retraining models by interpolating the new column from nearby existing columns. Crucially, instead of using raw feature proximity, it measures distance ($d_\Gamma$) based on the model's local computation structure (e.g., decision paths in trees or message-passing paths in GNNs).
  2. Player-Incremental Updates (Coalition Locality): When a new training instance is added, it only alters the local cooperative games of a small subset of tasks. D-Shap identifies these affected tasks and updates only their corresponding local matrix blocks, leaving the rest of the matrix frozen.
Figure 1: Overview of D-Shap. (a) D-Shap represents Shapley values as a player-by-task matrix Φ, where Φi,j = ϕ(zi, tj) denotes player zi’s contribution to task tj. (b) Task-incremental update (Sec. 3.3): a new task t′ is valued by interpolating nearby columns (green) under the model-induced distance dΓ. (c) Player-incremental update (Sec. 3.4): a new player z′ affects only columns whose local games involve it (coral); other entries (gray) stay frozen.

To bootstrap this matrix without requiring pre-specified external evaluation tasks, the authors introduce self-valuation. This technique treats each training player as a proxy task (using a leave-one-out approach). To make self-valuation scalable, they implement shared subset scheduling (reusing trained models across multiple tasks) and coverage-aware anchor selection (computing exact values only for a small set of representative "anchor" players and interpolating the rest).

Datasets

The authors evaluated D-Shap across five distinct model-dataset pairs, each representing a different type of model-induced locality:

  • Weighted K-Nearest Neighbors (WKNN) on MNIST (neighbor-based locality)
  • Decision Trees (DT) on Iris (partition-based locality)
  • RBF Kernel SVM on Breast Cancer (kernel-relevance locality)
  • Convolutional Neural Networks (CNN) on MNIST (representation-space locality)
  • Graph Convolutional Networks (GCN) on Cora (graph neighborhood locality)

Key Insights and Ideas

  • Preserving Fine-Grained Structure Enables Reuse: Moving from a scalar score per player to a player-by-task matrix prevents information loss, turning an exponential one-shot problem into a manageable matrix maintenance problem.
  • Model Geometry over Feature Geometry: Feature similarity can be highly misleading for data valuation. For instance, two nodes in a GNN might have identical features but completely different graph neighborhoods, leading to entirely different data values. D-Shap's model-induced distance metric ($d_\Gamma$) successfully captures how the model actually uses the data.
  • Data as its Own Workload: Self-valuation elegantly solves the cold-start problem by transforming the training set into a self-contained evaluation suite, ensuring the initialized matrix is well-aligned with the training data's intrinsic relationships.

Key Results

  • Task-Incremental Speedups: D-Shap reduces per-task evaluation costs by $10^6$ to $10^8\times$, enabling real-time, millisecond-level updates while maintaining accuracy competitive with static baselines.
  • Player-Incremental Speedups: For newly arriving data contributors, D-Shap cuts down update costs by $10^1$ to $10^3\times$ compared to standard recomputation methods.
  • Efficient Matrix Construction: Shared subset scheduling and anchor selection deliver a $>25\times$ speedup in constructing the initial matrix. For deep models (CNNs and GNNs), where naive methods failed to finish within 100 hours, D-Shap successfully completed matrix construction in just a few hours.

Limitations and Future Work

  • GNN Performance: While D-Shap consistently outperformed learning-based baselines on GNNs, its overall accuracy was lower on graph data than on tabular or image data. The authors note this is due to the inherent complexity of capturing multi-hop graph propagation within a simple distance metric ($d_\Gamma$).
  • Fixed Encoders for Deep Models: For deep neural networks, the framework currently assumes that the feature encoder remains fixed during incremental updates to preserve a stable geometric space for interpolation. Extending D-Shap to handle continuously fine-tuned encoders remains an open challenge.

Summary updated

Abstract

Shapley-based data valuation provides a principled way to quantify the contribution of training data, but its high computational cost makes 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. We introduce a new perspective that represents Shapley values as a player-by-task matrix and formulates dynamic valuation as a structured matrix maintenance problem. We exploit the fact that each task depends on a small subset of training players and that similar tasks yield similar valuations, leading to utility locality and coalition locality. Based on these insights, we 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, we 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 show 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.
BibTeX
@misc{yang2026dynamic,
  author = {Xuan Yang and Hsi-Wen Chen and Ming-Syan Chen and Jian Pei},
  title = {{Dynamic Shapley Computation}},
  year = {2026},
  eprint = {2605.20620},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.20620},
}

Loading related content...

Figure