The Shapley value provides a principled foundation for data valuation, but exact computation is #P-hard due to the exponential coalition space. Existing accelerations remain global and ignore a structural property of modern predictors: for a given test instance, only a small subset of training points influences the prediction. We formalize this model-induced locality through support sets defined by the model's computational pathway (e.g., neighbors in KNN, leaves in trees, receptive fields in GNNs), showing that Shapley computation can be projected onto these supports without loss when locality is exact. This reframes Shapley evaluation as a structured data processing problem over overlapping support-induced subset families rather than exhaustive coalition enumeration. We prove that the intrinsic complexity of Local Shapley is governed by the number of distinct influential subsets, establishing an information-theoretic lower bound on retraining operations. Guided by this result, we propose LSMR (Local Shapley via Model Reuse), an optimal subset-centric algorithm that trains each influential subset exactly once via support mapping and pivot scheduling. For larger supports, we develop LSMR-A, a reuse-aware Monte Carlo estimator that remains unbiased with exponential concentration, with runtime determined by the number of distinct sampled subsets rather than total draws. Experiments across multiple model families demonstrate substantial retraining reductions and speedups while preserving high valuation fidelity.
Figures & tables
Figure 1. (a) Intra-support redundancy : the blue area denotes the support set N(t) . For training points zi and zj , many training subsets are shared in their Shapley value computations. (b) Inter-support redundancy : test points ti and tj have overlapping supports (darker blue). Within this overlap, subsets are shared across their Shapley computations. The yellow dotted subset illustrates one such shared training subset.
Figure 2. Scatter plots of Local Shapley (x-axis) versus Global Shapley (y-axis). Green lines indicate linear regression fits.
Figure 3. Test accuracy versus the percentage of training data added in descending Shapley order.
Model
Metric
Global
TMC-S
Comple-S
Local-MC
LSMR-A
WKNN
Time
212,408
8,085
9,181
537
88
# Train
1,126M
65.1M
16.8M
9.0M
0.9M
DT
Time
1,446
250
206
243
111
# Train
2.8M
0.5M
0.4M
0.5M
0.2M
RBF-SVM
Time
101,903
2,790
3,087
16,013
251
# Train
81.7M
4.9M
5.1M
32M
0.4M
Table 1. Total running time and number of model trainings.
Figure 4. Scalability with respect to the training set size ∣D∣ on MNIST, plotted on logarithmic scales.
Method
∣N(t)∣
r
ρ
Acc@10%
Acc@20%
Time
# Train
Global
—
—
—
60.0
68.9
212k
1,126M
LSMR-A
1
0.443
0.460
68.3
74.7
20.2
0.4M
LSMR-A
3
0.619
0.613
71.7
76.5
55.7
0.8M
LSMR-A
5
0.721
0.717
70.5
76.9
65.1
0.8M
LSMR-A
10
0.839
0.840
70.4
78.6
87.6
0.9M
LSMR-A
20
0.901
0.898
70.5
77.2
89.2
0.9M
Table 2. Sensitivity to the support set size N(t) .
Model
Support Set
r
ρ
Acc@10%
Acc@20%
WKNN
WKNN
0.839
0.840
70.4
78.6
WKNN
DT
0.713
0.722
66.7
74.8
WKNN
RBF-SVM
0.596
0.575
68.0
75.3
WKNN
Random
0.118
0.120
64.1
68.0
Model
Support Set
r
ρ
Acc@5%
Acc@10%
GNN
GNN
0.516
0.376
78.6
83.9
Table 3. Effect of alignment between model architecture and support set construction
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Symbol
Meaning
z∈D
Training dataset (set of training points).
t∈T
Test set (set of test points).
S⊆D
A group formed by a subset of the training samples z .
θ(S)
Model trained on subset S .
gt(⋅)
Scalar functional that maps trained parameters to the evaluation at t .
vt(S)
Utility of subset S for test point t , i.e., gt(θ(S)) .
Appendix
Table 4. Notations Table
Dataset
∣D∣
∣T∣
Features
Classes
Domain
Iris
105
45
4
3
Tabular
Breast Cancer
398
171
30
2
Tabular
MNIST
1,000
1,000
1024
10
Image
Cora
1,708
1,000
1,433
7
Graph
Appendix
Table 5. Dataset statistics.
Method
r
ρ
Acc@5%
Acc@10%
Time
LSMR-A
0.516
0.376
78.6
83.9
7,241 s
In-Run o1 ( Wang et al., 2025 )
0.344
0.317
37.3
39.9
144 s
In-Run o2 ( Wang et al., 2025 )
0.347
0.319
38.0
39.7
260 s
Appendix
Table 6. LSMR-A vs. In-Run Data Shapley on GNN,Cora.
Model
Metric
Global-MC
+ Locality
+ Subset-Centric
LSMR-A
DT
Time (s)
1,446
243
152
111
# Train
2.8M
0.5M
0.3M
0.2M
GNN
Time (s)
200,860
45,378
16,075
7,241
# Train
28.2M
12.0M
3.8M
1.7M
Appendix
Table 7. Ablation of LSMR-A’s three efficiency mechanisms. Each column adds one mechanism to the previous.
Originally introduced in game theory, Shapley values have emerged as a central tool in explainable machine learning, where they are used to attribute model predictions to specific input features. However, computing Shapley values exactly is expensive: for a general model with n features, O(2n) model evaluations are necessary. To address this issue, approximation algorithms are widely used. One of the most popular is the Kernel SHAP algorithm, which is model agnostic and remarkably effective in practice. At the time of our original submission, no strong non-asymptotic complexity guarantees were known for Kernel SHAP. We address this issue by introducing Leverage SHAP, a lightweight modification of Kernel SHAP that provides provably accurate Shapley value estimates with just O(nlogn) model evaluations. Our approach takes advantage of a connection between Shapley value estimation and agnostic active learning by employing leverage score sampling, a powerful regression tool. Beyond theoretical guarantees, we find that Leverage SHAP achieves an approximately 50% reduction in error compared to the highly optimized implementation of Kernel SHAP in the widely used SHAP library [Lundberg & Lee, 2017].
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.
Shapley values are widely used to attribute value to training data based on their marginal contribution to performance on a validation set. Existing practice often assumes these values are stable once the training data and model are fixed. In this work, we uncover a systematic vulnerability: even modest changes to the validation set, such as introducing noises, cause directional shifts in Shapley distributions. As noises are added, Shapley values of training samples compress toward zero. We trace this to a noise-induced neighborhood reshuffling effect: perturbations alter the local rank order between validation and training samples, flattening the valuation landscape. Using the KNN-Shapley framework, we show through synthetic and real data that these shifts are consistent and reproducible. Our findings challenge the assumption of Shapley stability and reveal a new axis of fragility in data valuation. We propose normalization and boundary-aware validation strategies to mitigate these distortions and enable more robust, interpretable valuation in machine learning marketplaces.
Yinan Shen, Ziao Yang, Hongfu Liu
Adobe Waltham, MA 02451, USA · Department of Computer Science Brandeis University Waltham, MA 02453-2728, USA