Modern machine learning models are entirely dependent on the quality of their training data. However, not all data points contribute equally: some are highly informative, some are redundant, and others are actively harmful due to noise or mislabeling. To build secure data marketplaces, clean datasets, or fairly reward contributors in federated learning, we need a principled way to measure the economic or performance contribution of individual data points.
Cooperative game theory provides a mathematically rigorous framework for this problem via the Shapley value, which defines a data point's value as its average marginal contribution across all possible subsets of a dataset.
The catch is the combinatorial explosion. For a dataset of size $N$, there are $2^N$ possible subsets. Computing the exact Shapley value requires retraining a machine learning model an exponential number of times. As noted by Fan Wu et al. in their work on Scalability vs. Utility, this exponential complexity makes exact computation NP-hard and completely impractical for modern large-scale datasets. This fundamental bottleneck is echoed across applications ranging from federated learning marketplaces (Qi Li et al. in martFL) to security audits (Rui Wen et al. in Understanding Data Importance in Machine Learning Attacks).
To bypass this exponential wall, researchers have developed a suite of algorithmic shortcuts, proxy models, and statistical estimation techniques that make data valuation scalable.
The Neighborhood Shortcut: Exact Valuation via KNN Surrogates
The most direct way to defeat the $2^N$ complexity is to swap the complex machine learning model for a surrogate where marginal contributions can be computed analytically without retraining: the $K$-Nearest Neighbor (KNN) classifier.
In a foundational breakthrough, Ruoxi Jia et al. (Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms) demonstrated that the marginal contribution of a training point to a KNN model depends entirely on its distance rank relative to a test point. By sorting the dataset by distance—a process taking only $O(N \log N)$ time—the exact Shapley value can be computed recursively. The combinatorial explosion completely collapses because we no longer need to evaluate every subset; we only need to know which points are closer to the target than the point being valued.
Traditional Shapley: [Evaluate 2^N Subsets] -> Exponential Time
KNN-Shapley: [Sort by Distance] -> O(N log N) Analytical Calculation
Building on this geometric intuition, researchers have pushed the boundaries of neighborhood-based valuation:
- Weighted Neighborhoods: Guangyi Zhang et al. (Shapley-Based Data Valuation for Weighted $k$-Nearest Neighbors) introduced a "conceptual data duplication" technique that maps complex, distance-weighted KNN models back into an unweighted space, enabling near-linear time exact valuation for datasets with up to a million records.
- Deterministic Approximations: Dimitrios Dimitriadis et al. (Invariant Aggregator for Defending against Federated Backdoor Attacks) slashed the complexity of weighted KNN-Shapley down to a deterministic $O(N^{1.5})$ approximation, making real-time data denoising practical for large-scale pipelines.
Proxy Models and Value Transferability
While KNN models offer an elegant mathematical shortcut, we often care about the value of data inside deep neural networks or large language models (LLMs). The core insight enabling this is value transferability: data quality anomalies (like mislabeling or high informational redundancy) are largely intrinsic to the data distribution itself, meaning values computed on a cheap "proxy" model will transfer effectively to an expensive target architecture.
Fan Wu et al. proved this intuition by computing KNN-Shapley values on top of frozen, pre-trained embeddings. The resulting data importance scores were orders of magnitude faster to compute than full model retraining, yet they actually outperformed traditional methods at detecting noisy labels.
This proxy paradigm has been widely adapted across different domains:
- Classification Fine-Tuning: Stephanie Schoch et al. (CS-Shapley) introduced class-wise Shapley values computed on lightweight proxies that successfully isolate how data points impact specific class boundaries before transferring those insights to deep networks.
- LLM Data Pruning: Yangfeng Ji et al. (Data Selection for Fine-tuning Large Language Models Using Transferred Shapley Values) combined proxy models with subset sampling to prune harmful data from LLM fine-tuning sets. To scale this further for instruction fine-tuning, Yexiao He proposes SHED, a framework that clusters data and evaluates only representative proxy samples, curating high-performing datasets using a fraction of the compute.
- Validation-Free Estimation: Himanshu Jahagirdar et al. (Data Valuation in the Absence of a Reliable Validation Set) bypassed the need for expensive validation sets by leveraging a Regularized Least Squares (RLS) proxy model to calculate robust data values via leave-one-out cross-validation.
Amortized Inference and Statistical Prediction
Instead of evaluating subsets or relying on structural proxies, another direction treats data valuation as a machine learning problem in its own right: learning to predict a data point's utility.
Haifeng Sun et al. (Fast-DataShapley) proposed training a reusable neural "explainer model" that maps data points directly to their estimated Shapley values. This shifts the computational burden from a slow, iterative retraining process into a real-time inference task, achieving a 100x speedup.
Traditional Approach: New Dataset -> [Run 2^N Retrains] -> Data Values
Amortized Approach: New Dataset -> [Neural Explainer Inference] -> Data Values (Instant)
Alternatively, the performance landscape can be modeled statistically using Gaussian Processes (GPs). Khang-Nguyen Pham et al. developed DUPRE, which uses a GP regression framework to predict model performance across subsets. By utilizing a specialized kernel based on the Sliced Wasserstein distance to capture the similarity between different datasets, DUPRE bypasses retraining entirely. When the goal is simply to find the best data rather than valuing every single point, Xiaoqiang Lin et al. (Efficient Top-m Data Values Identification for Data Selection) demonstrated that GPs can be paired with adaptive subset evaluations to isolate the top-$m$ most valuable points with up to a 50x speedup over standard baselines.
Axiomatic Relaxations and Simultaneous Sampling
A final, powerful mathematical lever involves changing the definition of "value" itself to make it easier to estimate. The classical Shapley value enforces strict mathematical axioms (such as the efficiency axiom), which force the metric to weight all subset sizes equally. However, in machine learning, a data point's utility is often best surfaced when added to moderately sized or large subsets where the model has already established a baseline distribution.
James Y. Zou et al. (Beta Shapley) proposed relaxing the efficiency axiom to create Beta Shapley. By using a Beta distribution to reweight the importance of different subset sizes, Beta Shapley drastically reduces the statistical noise inherent in random sampling, allowing practitioners to detect harmful data points with significantly fewer model evaluations.
To optimize the sampling process itself, Weida Li et al. (One Sample Fits All) developed a framework capable of approximating multiple probabilistic values (such as Shapley, Banzhaf, and Beta Shapley values) simultaneously from a single set of random permutations.
Finally, in highly dynamic environments like data markets, Boxin Zhao et al. (Addressing Budget Allocation and Revenue Allocation...) bypassed subset evaluation entirely. They utilized an adaptive sampling process based on Online Stochastic Mirror Descent to achieve Shapley-like fairness in linear time, proving that algorithmic and mathematical reformulations can successfully tame the combinatorial explosion of data valuation.
Key Foundational Work
Data Shapley: Equitable Valuation of Data for Machine Learning (2019) — contributed 2 concept elements to this direction.
Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms (2019) — contributed 1 concept elements to this direction.