Local Shapley: Model-Induced Locality and Optimal Reuse in Data Valuation

Xuan Yang; Hsi-Wen Chen; Ming-Syan Chen; Jian Pei

cs.LGMar 4, 2026

Local Shapley: Model-Induced Locality and Optimal Reuse in Data Valuation

Authors: Xuan Yang, Hsi-Wen Chen, Ming-Syan Chen, Jian Pei

Organizations: Duke University Durham, NC, USA · National Taiwan University Taipei, Taiwan

Abstract

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

Panel of Figure 1 — Figure 1. (a) Intra-support redundancy : the blue area denotes the support set $\mathcal{N}(t)$ . For training points $z_{i}$ and $z_{j}$ , many training subsets are shared in their Shapley value computations. (b) Inter-support redundancy : test points $t_{i}$ and $t_{j}$ 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.

Panel of Figure 2 — Figure 2. Scatter plots of Local Shapley (x-axis) versus Global Shapley (y-axis). Green lines indicate linear regression fits.

Panel of Figure 3 — 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
WKNN	# Train	1,126M	65.1M	16.8M	9.0M	0.9M
DT	Time	1,446	250	206	243	111
DT	# Train	2.8M	0.5M	0.4M	0.5M	0.2M
RBF-SVM	Time	101,903	2,790	3,087	16,013	251
RBF-SVM	# Train	81.7M	4.9M	5.1M	32M	0.4M

Table 1. Total running time and number of model trainings.

Panel of Figure 4 — Figure 4. Scalability with respect to the training set size $|\mathcal{D}|$ on MNIST, plotted on logarithmic scales.

Method	$\|\mathcal{N}(t)\|$	$r$	$\rho$	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

\mathcal{N}(t)

Model	Support Set	$r$	$\rho$	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$	$\rho$	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\in\mathcal{D}$	Training dataset (set of training points).
$t\in\mathcal{T}$	Test set (set of test points).
$S\subseteq\mathcal{D}$	A group formed by a subset of the training samples $z$ .
$\theta(S)$	Model trained on subset $S$ .
$g_{t}(\cdot)$	Scalar functional that maps trained parameters to the evaluation at $t$ .
$v_{t}(S)$	Utility of subset $S$ for test point $t$ , i.e., $g_{t}(\theta(S))$ .

Appendix

Table 4. Notations Table

Dataset	$\|\mathcal{D}\|$	$\|\mathcal{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$	$\rho$	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
DT	# Train	2.8M	0.5M	0.3M	0.2M
GNN	Time (s)	200,860	45,378	16,075	7,241
GNN	# 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.

Shapley Value Attribution

Shapley value attribution fairly assigns a prediction or outcome among contributing features, data points, agents, or modalities.

See all 103 papers

Provably Accurate Shapley Value Estimation via Leverage Score Sampling
Oct 2, 2024Christopher Musco, R. Teal WitterSHAP Feature Attribution Shapley Value Attribution
New York University
Dynamic Shapley Computation
May 20, 2026Xuan Yang, Hsi-Wen Chen, Ming-Syan Chen +1Shapley Value Attribution Data Valuation
1Duke University · 2National Taiwan University
Validation-Induced Shapley Shifts: How Validation Structure Distorts Data Valuation
Jul 4, 2026Yinan Shen, Ziao Yang, Hongfu LiuShapley Value Attribution Data Valuation
Adobe Waltham, MA 02451, USA · Department of Computer Science Brandeis University Waltham, MA 02453-2728, USA

Oct 2, 2024J/K move · Enter open · S save

Provably Accurate Shapley Value Estimation via Leverage Score Sampling

Christopher Musco, R. Teal Witter

New York University

SHAP Feature Attribution Shapley Value Attribution

Open paper AskPDF arXiv

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(2^n)

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(n\log n)

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].

Abstract

Shapley Value Attribution

Explore similar work

Provably Accurate Shapley Value Estimation via Leverage Score Sampling

Dynamic Shapley Computation

Validation-Induced Shapley Shifts: How Validation Structure Distorts Data Valuation