Overcoming the Retraining Bottleneck in Data Valuation

16 concepts16 papers

Data valuation frameworks aim to answer a fundamental question in data-centric machine learning: how much does an individual training example or data source contribute to a model's performance? Quantifying this value is essential for filtering out noisy or malicious data, mitigating negative transfer (Parvez et al.), and establishing fair pricing in data marketplaces (Zhang et al.).

However, mathematically rigorous data valuation is notoriously expensive. Game-theoretic formulations like the Shapley value (Zou et al.) or the Banzhaf value (Wang et al.) define a data point's worth by its marginal contribution across all possible subsets of a dataset. To compute this exactly or even approximate it via Monte Carlo sampling, a model must be retrained from scratch on thousands of different data combinations. As highlighted by Jiang et al. and Covert et al., this iterative retraining bottleneck makes traditional valuation methods computationally prohibitive for modern large-scale datasets and foundation models.

To scale data valuation, recent research focuses on bypassing or optimizing this retraining loop. The field has converged on three primary strategies: learning-agnostic geometric proxies, recycling internal training dynamics, and predictive surrogate models.

Learning-Agnostic and Geometric Proxies

If training a model is the core computational bottleneck, one intuitive solution is to eliminate the model entirely from the valuation step. Instead of measuring how a data point changes a model's accuracy, learning-agnostic methods evaluate how a data point alters the geometry of the dataset itself.

Just et al. introduced this paradigm with LAVA, a framework that uses Optimal Transport and sensitivity analysis. LAVA treats the training dataset and a target validation set as probability distributions. It computes the Wasserstein distance between them to determine how much a single data point shifts the source distribution toward the target. If removing a point makes the training distribution more similar to the target distribution, that point is deemed harmful or redundant.

Building on this geometric perspective, Zhu et al. proposed KAIROS, which leverages Maximum Mean Discrepancy (MMD) to achieve a closed-form solution for data ranking. By operating purely in the feature space, these methods turn an exponential model-training problem into a highly parallelizable distance calculation. For specialized architectures like K-Nearest Neighbor (KNN) algorithms, Jia et al. demonstrated that the exact Shapley value can be computed analytically in $O(N \log N)$ time by exploiting the local geometric structure of the embeddings, avoiding retraining altogether.

For complex post-training scenarios in large language models, Zeng et al. shifted the geometric analysis to the gradient space. By mapping candidate datasets to their expected gradients and using Kernel Mean Matching (KMM), their framework solves a convex optimization problem that jointly accounts for target task alignment and data redundancy without executing full-scale training cycles.

Recycling Artifacts and Training Dynamics

Another strategy extracts data value from the telemetry of a standard training run, treating the model's internal dynamics as a natural experiment.

For ensemble models, Kwon et al. introduced Data-OOB, which reuses the "out-of-bag" (OOB) samples inherent to bagging algorithms like Random Forests. Because each base estimator is trained on a random subset of the data, a portion of the dataset is naturally left out of each model. By evaluating each data point exclusively on the sub-models that did not see it during training, Data-OOB computes a robust data value with zero additional training overhead. To extend this efficiency to deep learning, Wang et al. designed a "Maximum Sample Reuse" algorithm for the Banzhaf value, proving that the stochasticity of standard training runs can be mathematically leveraged to share evaluations across different subset configurations.

Alternatively, instead of isolating a sample by removing it, researchers can observe how a model interacts with a sample over time. Arriaga et al. proposed the Action Score, which accumulates a sample's loss across the epochs of a single training run. Samples that consistently yield high loss or exhibit erratic loss trajectories signify high difficulty or mislabeling, providing a direct proxy for data quality without requiring combinatorial subset evaluation.

Predictive Surrogates

A third approach treats the mapping from a data subset to model performance as an unknown, smooth function that can be learned by a meta-model.

Pham developed DUPRE (Data Utility Prediction for Efficient Data Valuation), which replaces the expensive model-evaluation step with a Gaussian Process Regression (GPR) surrogate. The core insight is that different data subsets can be treated as points in a metric space. By using the Sliced Wasserstein distance to measure the similarity between different data subsets, the GPR model can interpolate and predict downstream model utility from just a small number of actual training samples, drastically reducing the number of full training runs required to approximate Shapley values.

Traditional Valuation:
[Data Subsets] ───► [Full Model Retraining (Thousands of Times)] ───► [Utility Score]

Predictive Surrogate (DUPRE):
[Data Subsets] ───► [Sliced Wasserstein Distance] ───► [GPR Predictor] ───► [Predicted Utility]

Theoretical Boundaries and Scaling Laws

As the field shifts toward these computational approximations, researchers have begun formalizing the theoretical limits of scalable data valuation. Ilyas et al. established a fundamental "trilemma" proving that a data valuation mechanism cannot simultaneously achieve perfect computational efficiency, market truthfulness (preventing sellers from manipulating prices), and optimal model utility. This framework provides a theoretical foundation for designing compute-constrained selection heuristics that still maintain market integrity.

Furthermore, understanding how data value behaves as datasets grow is critical for long-term scalability. Covert et al. demonstrated that individual data points follow predictable "value decay" scaling laws. As the total volume of data increases, the marginal utility of any single point shrinks at a predictable rate, allowing practitioners to project a sample's utility at scale based on cheap, small-scale evaluations. Finally, to make valuation robust to shifting deployment environments without a fixed validation set, Lin et al. introduced a training-free approach based on model deviation, measuring a point's contribution to distributionally robust generalization error directly.

Key Foundational Work

Evaluating the Values of Sources in Transfer Learning (2021) — contributed 1 concept elements to this direction.
Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms (2019) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_computational_scalability_of_data_valuat_008ab015,
  title = {computational scalability of data valuation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-scalability-of-data-valuation/rdr_008ab015c55f4a1c90057346d0a8181c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_computational_scalability_of_data_valuat_008ab015_v1,
  title = {computational scalability of data valuation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-scalability-of-data-valuation/rdr_008ab015c55f4a1c90057346d0a8181c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}

See something wrong? Report a mistake