PaperlayerView exact revision on arXiv

Source-linked AI summary

Data Shapley in One Training Run

Jiachen T. Wang, Prateek Mittal, Dawn Song, Ruoxi Jia

arXiv:2406.11011v3cs.LGcs.CLstat.ML

TL;DR

Retraining-based Data Shapley is costly at large scale and does not attribute contributions to a particular model produced by one training run. In-Run Data Shapley computes attribution during a single run; the paper reports case studies on pretraining data and a first-order implementation close to regular-training runtime. Its findings address data curation, stage-dependent contributions, and copyright discussions.

  • Problem

    Retraining-based Data Shapley requires many subset-model retrainings and yields scores for a general learning algorithm rather than a specific training run.

    Source: §2 · p. 3

  • Method

    In-Run Data Shapley attributes data to a target model by computing contributions during the realized training run.

    Source: §1 · p. 2, §3 · p. 4

  • Results

    The first-order method ran close to regular training, while case studies found negative-valued points in the Pile, stage-dependent corpus contributions, and contributions from rewritten training data.

    Source: §1 · p. 2, §5.1 · p. 7

  • Takeaways & Limitations

    The case studies point to opportunities for improved pretraining-data curation and inform discussion of copyright contributions beyond near-verbatim memorization.

    Source: §1 · p. 2

    Attribution scores must be computed during training, so validation data needs to be available beforehand; intermediate checkpoints are suggested as a possible workaround when it arrives later.

    Source: §6 · p. 10

Abstract

from arXiv · show

Data Shapley provides a principled framework for attributing data's contribution within machine learning contexts. However, existing approaches require re-training models on different data subsets, which is computationally intensive, foreclosing their application to large-scale models. Furthermore, they produce the same attribution score for any models produced by running the learning algorithm, meaning they cannot perform targeted attribution towards a specific model obtained from a single run of the algorithm. This paper introduces In-Run Data Shapley, which addresses these limitations by offering scalable data attribution for a target model of interest. In its most efficient implementation, our technique incurs negligible additional runtime compared to standard model training. This dramatic efficiency improvement makes it possible to perform data attribution for the foundation model pretraining stage for the first time. We present several case studies that offer fresh insights into pretraining data's contribution and discuss their implications for copyright in generative AI and pretraining data curation.

1 INTRODUCTION

The introduction argues that foundation-model training needs fair data attribution, but retraining-based Data Shapley is too costly at scale and does not target a particular training run. In-Run Data Shapley offers attribution for a specific model, and its case studies surface issues in pretraining-data curation, changing data contributions over training, and copyright analysis.

1 INTRODUCTION

  • Foundation models use vast, multi-source datasets, and poor attribution can contribute to legal and societal concerns, while low-quality or harmful data can waste compute and skew outputs.The introduction links attribution to identifying and mitigating low-quality data.Source: §1 · p. 1
  • Retraining-based Data Shapley is computationally infeasible for foundation models and attributes data to a general learning algorithm rather than a particular model.The distinction matters especially for randomized, data-order-sensitive algorithms, where runs can yield different models.Source: §1 · p. 2
  • In-Run Data Shapley targets a specific model of interest, addressing the target-model limitation of retraining-based attribution.The approach is presented as applicable to large-scale foundation models.Source: §1 · p. 2
  • Taylor approximations turn per-update attribution into gradient dot-products or gradient-Hessian-gradient products, accumulated across training steps.The proposed tools compute these products in one or two backward passes without instantiating additional gradient vectors or Hessian matrices.Source: §1 · p. 2
  • The method enables pretraining-scale attribution, demonstrated as a pilot study on GPT2 and Pythia-410M and presented as applicable to larger models with sufficient computing resources.The paper reports case studies of training data’s contribution to foundation-model pretraining.Source: §1 · p. 2
  • Removing negatively valued points from the Pile produced faster convergence and better performance; about 16% of its data points received negative values despite prior curation.The authors found substantial noise among these negatively valued points.Source: §1 · p. 2
  • General corpora contribute relatively more early in training, while domain-specific corpora become dominant later as general-corpus contributions phase out.The paper attributes early general-corpus contributions to learning basic language patterns, grammar, and common knowledge.Source: §1 · p. 2
  • Training data contributed significantly to validation points that completely rewrote training data while retaining the topic, informing copyright discussions beyond near-verbatim memorization.The authors argue that some data owners should receive a royalty share even when generated content does not closely resemble copyrighted material.Source: §1 · p. 2

2 BACKGROUND OF DATA SHAPLEY

This section frames Data Shapley as a principled way to distribute training utility among data points. It explains the conventional retraining-based formulation and its computational and target-specific limitations.

2 BACKGROUND OF DATA SHAPLEY

  • The section situates the Shapley value as a game-theoretic method for equitably distributing total profit among participants.Data attribution seeks scores for training points that reflect their importance to model performance on a task.Source: §2 · p. 3
  • A utility function maps a training dataset to a score; existing work commonly uses a model’s hold-out validation performance as that score.Examples include accuracy for classification and perplexity for language completion.Source: §2 · p. 3
  • The Shapley value is a weighted average of a point’s marginal utility across possible datasets and uniquely satisfies the Null player, Symmetry, Linearity, and Efficiency axioms.Its linearity property allows Shapley values for a weighted combination of utility functions to be computed as the same weighted combination of their values.Source: §2 · p. 3
  • Retraining-based Data Shapley estimates a point’s marginal contribution by comparing models trained on subsets with and without that point, requiring repeated retraining.The resulting scores can be unstable with stochastic learning algorithms and describe average contribution to the algorithm rather than a specific training run.Source: §2 · p. 3

3 IN-RUN DATA SHAPLEY

In-Run Data Shapley decomposes attribution across the iterations of one realized training run. It computes per-step contributions to validation-loss changes and sums them into a run-specific score.

3 IN-RUN DATA SHAPLEY

  • The method defines a local utility for a single iteration, measuring the validation-loss change when a selected subset of that iteration’s batch supplies the update.This incorporates the realized batch selection and can encode other training randomness, such as dropout, yielding a deterministic utility for that iteration.Source: §3 · p. 4
  • The per-step utility can be extended from the batch to the full training set: points outside the iteration’s batch receive zero value for that step.Points within the batch retain the same Shapley value under the augmented utility.Source: §3 · p. 4
  • The global utility is the sum of local utilities across iterations, and Shapley linearity makes the overall score the sum of the per-iteration scores.The global utility represents cumulative loss change under the counterfactual that only a subset of training data is used.Source: §3 · p. 4
  • In-Run Data Shapley sums each data point’s Shapley values across gradient updates to obtain its cumulative contribution over one training run.By the Shapley efficiency axiom, the sum of individual points’ scores equals the run’s overall loss reduction.Source: §3 · p. 4
  • For multiple validation points, the Shapley value for their summed utility can be obtained by summing the values for individual validation points.The paper presents a single validation point for clarity and states that its techniques extend to multiple points.Source: §3 · p. 4

4 EFFICIENT COMPUTATION OF IN-RUN DATA SHAPLEY

The method makes per-update In-Run Data Shapley tractable through Taylor approximations and efficient gradient-product computations. Its deterministic approximation can add negligible runtime in the most efficient implementation.

4 EFFICIENT COMPUTATION OF IN-RUN DATA SHAPLEY

  • In the most efficient implementation, deterministic approximation adds negligible runtime beyond standard model training.Source: §4 · p. 5

4.1 APPROXIMATING U (t) WITH TAYLOR EXPANSION

  • First- and second-order Taylor approximations have per-step errors O(η^2_t) and O(η^3_t), respectively; first-order approximation achieves Spearman correlation >0.94 on GPT-2.Source: §4.1 · p. 5
  • Second-order In-Run Data Shapley adds a gradient-Hessian-gradient term that captures interactions among training points and discounts similar or duplicate points.Source: §4.1 · pp. 5–6

4.2 EFFICIENT COMPUTATION OF GRADIENT DOT-PRODUCT AND GRADIENT-HESSIAN-GRADIENT PRODUCT

  • Direct per-sample gradients make first-order computation at least |Bt| times slower, while second-order computation also requires storing or recomputing those gradients.Source: §4.2 · p. 6
  • Ghost dot-product computes pairwise gradient dot-products within one backpropagation without instantiating gradient vectors, versus at least |Bt| passes for the direct method.Source: §4.2 · pp. 6–7
  • Ghost techniques yield one backpropagation per iteration for first-order scores and one extra pass for second-order scores, reusing activations and output gradients.Source: §4.2 · p. 7

5 EXPERIMENTS

The experiments evaluate In-Run Data Shapley’s runtime and approximation fidelity, then use Pile pretraining case studies to examine data curation, stage-dependent contributions, and attribution of paraphrased content. Most experiments use GPT-2 and Pythia-410M because of resource constraints.

5.1 RUNTIME EVALUATION

  • First-order In-Run Data Shapley runs close to regular training, while both orders are over 30× faster than the naive implementation.Second-order attribution is approximately 2× slower than regular training because of additional backpropagation.Source: §5.1 · p. 7, Table 1 · p. 7

5.2 FIDELITY EVALUATION

  • First-order In-Run Data Shapley had RMSE around 0.0003 against a 1,000-permutation Monte Carlo estimate at GPT-2’s 3,500th Pile training iteration.Figure 1 compares the Monte Carlo estimate with first- and second-order estimates.Source: §5.2 · p. 8, Figure 1 · p. 8

5.3 CASE STUDY: DATA ATTRIBUTION ON PILE DATASET

  • The Pile case study examines data curation, contribution across training stages, and relevant-corpus detection, mostly using GPT-2 and Pythia-410M.The authors state that applying the approach to larger models is possible with adequate computing resources.Source: §5.3 · p. 8

5.3.1 IS WELL-CURATED DATASET ACTUALLY CLEAN?

  • Around 25% fewer iterations reached test loss 3.75 after removing negatively valued corpora; around 16% of training corpora had negative second-order values.The comparison is for a GPT-2 trained on a random Pile subset of around 10B tokens; some negative values may reflect domain shift from the validation corpora.Source: §5.3.1 · pp. 8–9, Figure 2 · p. 8

5.3.2 HOW DO DATA VALUES CHANGE DURING TRAINING?

  • For math validation data, ArXiv’s value exceeded other domains and its share of value changed rapidly early in training before stabilizing.Pile-CC contributions began positive, then fell negative and converged to zero; general corpora were more helpful early, while specialized domains mattered more later.Source: §5.3.2 · p. 9, Figure 3 · p. 9

5.3.3 DOES CONTRIBUTION REQUIRE MEMORIZATION?

  • The original Wikipedia corpus ranked highly for paraphrased validation texts, including complete rewrites with low BM25 distance but relevant topics.Influence function ranked the original corpus lower than In-Run Data Shapley; the authors connect the example to copyright concerns beyond near-verbatim replication.Source: Table 2 · p. 9, §5.3.3 · p. 10

6 CONCLUSION AND LIMITATIONS

The conclusion presents In-Run Data Shapley as addressing limitations of retraining-based attribution. The discussion also identifies practical constraints and reviews the Shapley axioms underlying Data Shapley.

6 CONCLUSION AND LIMITATIONS

  • In-Run Data Shapley is presented as addressing limitations of retraining-based Data Shapley.The conclusion passage does not specify further results.Source: §6 · p. 10
  • Validation data must be available before training; late-arriving data may require intermediate checkpoints, whose selection can significantly affect performance and remains unclear.The discussion also notes that efficient support for Adam-like optimizers and large batches remains future work.Source: §6 · p. 10

A.1 DATA SHAPLEY AXIOMS

  • Data Shapley is justified by null-player, symmetry, linearity, and efficiency axioms, including zero scores for non-contributors and total scores equal to total utility.The axioms also require equal scores for equally impactful points and additive decomposition across utility functions.Source: §A.1 · p. 15, §4 · p. 15

A.2 DATA SHAPLEY AND FRIENDS

Data Shapley research spans retraining-based estimators and alternatives, while this paper presents In-Run Data Shapley as an exact Shapley computation for an approximated per-step utility. Its discussion distinguishes model-specific attribution from related methods and illustrates how per-step scores are accumulated during one run.

A.2 DATA SHAPLEY AND FRIENDS

  • In-Run Data Shapley computes exact Shapley values for a Taylor-approximated utility rather than relying on potentially inefficient and unstable Monte Carlo estimators.The authors state that this retains Shapley fairness axioms for the approximated utility.Source: §A.2 · p. 16

A.3 COMPARISON WITH TRACIN (PRUTHI ET AL., 2020)

  • The first-order method coincides with TracIN-Ideal, while the ghost dot-product technique computes it without additional approximations.The discussion contrasts this with TracIN-CP’s checkpoint-based approximation and last-layer implementation constraints.Source: §A.3 · p. 16

B ADDITIONAL DISCUSSION

  • Figure 4 decomposes attribution into per-iteration Shapley values that are summed for each example, while Figure 5 contrasts this single-run accounting with retraining on all subsets.The local utility measures a batch’s contribution to reducing validation loss.Source: Figure 4 · p. 17, Figure 5 · p. 17, B ADDITIONAL DISCUSSION · p. 17

B.1 WHEN IS IN-RUN DATA SHAPLEY DESIRABLE FOR DATA ATTRIBUTION?

The discussion weighs when model-specific, single-run attribution is useful against retraining-based valuation’s costs and scope. It also identifies settings where retraining remains preferable and outlines possible extensions of the per-iteration approach.

B.1 WHEN IS IN-RUN DATA SHAPLEY DESIRABLE FOR DATA ATTRIBUTION?

  • Retraining-based Data Shapley requires evaluating every data subset, while Monte Carlo and proxy-model alternatives still leave substantial computation or interpretation concerns.The relationship between cheaper KNN proxies and the original learning algorithm remains unclear.Source: §B.1 · p. 18
  • Retraining-based scores average contributions across subset-trained models rather than targeting the specific full-data model, and stochastic training can make those scores unstable.Subset choice also leaves unclear whether to retain full-dataset hyperparameters or adjust them to subset size.Source: §B.1 · p. 18
  • In-Run Data Shapley computes values during training, targets the model being trained, and incorporates the run’s sequence and randomness to produce deterministic valuations.The paper frames it as suitable when efficiency, model-specific contributions, and stability are important.Source: §B.1 · p. 18
  • Attribution choice depends on the application: algorithm-level valuation suits data-quality assessment, whereas model-specific valuation suits interpreting a particular checkpoint.The authors identify mapping approaches to application scenarios as future work.Source: §B.1 · p. 19

B.2 WHEN IS RETRAINING-BASED DATA SHAPLEY DESIRABLE FOR DATA ATTRIBUTION?

  • Retraining-based Data Shapley remains applicable to all learning algorithms and useful for general learning-process contributions, without modifying training code.In-Run Data Shapley is limited to iterative training algorithms.Source: §B.2 · p. 19

B.3 POTENTIAL EXTENSIONS OF IN-RUN DATA SHAPLEY TO OTHER DOMAINS

  • Potential extensions include per-update attribution for iterative non-gradient algorithms, hyperparameter contributions against a baseline, and feature attribution across network layers.The paper presents these as possible directions; adapting hyperparameter attribution still has technical challenges.Source: §B.3 · pp. 19–20

C MISSING PROOFS

The proof appendix states closed-form first- and second-order In-Run Data Shapley results. Its technical details describe ghost computations for gradient products and a way to combine score calculation with the training update’s backpropagation.

C MISSING PROOFS

  • The first-order approximation gives a closed-form In-Run Data Shapley score, with the per-step expression proportional to the validation and training gradients’ dot product.The per-step factor is −ηt∇ℓ(wt, z(val)) · ∇ℓ(wt, z).Source: C MISSING PROOFS · p. 21
  • The second-order approximation also has a closed-form score, separating a point’s influence on validation loss from its interaction with other training points.The proof identifies these as two terms in the expression.Source: C MISSING PROOFS · p. 22

D.1 GHOST DOT-PRODUCT

  • Ghost dot-product computes gradient dot products between batch examples from quantities available in one backpropagation, avoiding materialization of per-example gradients.For sequential data, the implementation chooses the multiplication order according to the relative sizes of 2T^2 and d1d2.Source: §D.1 · pp. 23–24

D.2 GHOST GRADIENT-HESSIAN-GRADIENT PRODUCT

  • The ghost gradient-Hessian-gradient procedure reuses a fixed right-hand gradient vector, so the second backpropagation is needed only once.The passage identifies the Hessian as that of validation-example loss on a layer’s weights.Source: §D.2 · pp. 25, 27

D.3 MERGING BATCH SELECTION AND GRADIENT UPDATE IN ONE BACKPROPAGATION

  • The implementation includes validation loss in backpropagation to compute attribution scores, then reuses available output-gradient quantities for the parameter update.The bookkeeping technique is adapted from Bu et al. (2023).Source: §D.3 · p. 27

E.1 DATA PREPROCESSING & TRAINING SETTINGS & IMPLEMENTATION DETAILS

The implementation details describe Pile pretraining settings for GPT2 and Pythia-410M, identify influence-function and BM25 comparisons, and explain why TRAK is omitted.

E.1 DATA PREPROCESSING & TRAINING SETTINGS & IMPLEMENTATION DETAILS

  • The pretraining experiments use GPT2 (124M) and Pythia-410M on the Pile, with training stopped at 500,000 iterations because of limited computing resources.The setup uses sequence length 1024, batch size 16, and AdamW.Source: §E.1 · p. 28
  • Comparisons include the influence function as a leave-one-out approximation and BM25 word-frequency similarity scores for ranking training instances.BM25 uses k1 = 1.5 and b = 0.75.Source: §E.1 · p. 28
  • The study omits TRAK because reasonable performance generally requires aggregating estimates across multiple trained models, and its original codebase does not support Huggingface models.The largest-scale experiment in TRAK’s original paper was fine-tuning BERT-base.Source: §E.1 · p. 28

E.2.1 APPROXIMATION ERROR FOR IN-RUN DATA SHAPLEY WITH LARGER LEARNING RATES

The first- and second-order approximations closely track Monte Carlo-estimated In-Run Data Shapley at learning rates of 6 × 10−4 and 5 × 10−3, with accuracy declining at the larger rate.

E.2.1 APPROXIMATION ERROR FOR IN-RUN DATA SHAPLEY WITH LARGER LEARNING RATES

  • RMSE = 0.0012 and Spearman correlation = 0.99 at η = 6 × 10−4; both approximations closely match Monte Carlo-estimated In-Run Data Shapley.Figure 6 compares the Monte Carlo estimates with the first- and second-order approximations.Source: §E.2.1 · p. 28, Figure 6 · p. 28
  • RMSE ≈0.0017 and Spearman correlation = 0.79 at η = 5 × 10−3, indicating lower but still reasonable approximation accuracy.Figure 7 shows the comparison at this substantially larger-than-typical pretraining learning rate.Source: §E.2.1 · p. 28, Figure 7 · p. 29
  • At learning rates typical for pretraining (η ≤10−3), strong rank correlation suggests the approximations preserve relative data-point importance.Relative rankings matter for identifying low-quality data and selecting valuable examples.Source: §E.2.1 · p. 28

E.2.2 APPROXIMATION ERROR FOR UTILITY FUNCTION

These additional experiments examine approximation accuracy, data cleaning, changing data contributions over training, paraphrase attribution, and domain detection. They report useful results while identifying limitations tied to optimizer choice and validation-set representativeness.

E.2.2 APPROXIMATION ERROR FOR UTILITY FUNCTION

  • The first-order approximation already achieves high accuracy for one-step utility changes on GPT2, while adding the second-order interaction term yields no notable improvement.Figure 8 shows correlations between the ground-truth change and both approximations.Source: §E.2.2 · p. 29, Figure 8 · p. 29
  • The techniques are tailored to SGD and do not directly extend to Adam’s normalization terms; the authors use SGD as an effective proxy in their experiments.Supporting Adam and similar optimizers remains future work.Source: §E.2.2 · p. 29

E.3 DETAILS ABOUT SECTION 5.3.1

  • After filtering out the 16% negatively valued corpus, the authors found poor-quality examples in the Pile, including empty PubMed Central corpora; some apparently normal negative-score examples may reflect validation-corpus distribution shift.Figure 9 shows examples with meaningless numbers and symbols; a representative validation set remains important.Source: §E.3 · pp. 29–30, Figure 9 · p. 30

E.3.1 DATA SELECTION PERFORMANCE ON PYTHIA 410M

  • Removing lower-quality data led to a significantly faster drop in test loss than the original run on Pythia-410M.The comparison is shown in Figure 10.Source: §E.3.1 · p. 30, Figure 10 · p. 30

E.4 ADDITIONAL RESULTS FOR SECTION 5.3.2

  • Across the first 10,000 updates, domain-averaged data-value scores move toward zero, consistent with diminishing returns; later-introduced data points contribute less, a pattern retraining-based methods cannot capture.The domain-level scores are averaged across corpora used in gradient updates.Source: §E.4 · p. 30, Figure 11 · p. 31

E.5.1 ADDITIONAL EXPERIMENT: RELEVANT DOMAIN DETECTION

  • For relevant-domain detection, first- and second-order In-Run Data Shapley outperform influence functions, while BM25 performs well generally and remains better on some domains.The task uses normalized recall@1000; In-Run Data Shapley uses information from intermediate checkpoints.Source: §E.5.1 · p. 35, Table 3 · p. 35

E.6 COMPARISON WITH OTHER DATA ATTRIBUTION BASELINES ON SMALL-SCALE MODELS

On small-scale CIFAR10 tasks, In-Run Data Shapley is competitive with attribution baselines, but the strongest method varies by task and selection budget. The evaluation is framed as a sanity check rather than an expectation of state-of-the-art performance.

Evaluation scope

  • These standard-task evaluations serve as sanity checks because attribution scores are not optimized for the benchmarks, so state-of-the-art performance is not expected.The paper notes that Shapley approximation has value beyond these tasks, including possible royalty sharing for AI-generated content (Wang et al., 2024a).Source: §E.6 · p. 37

Experiment settings

  • The comparison covers mislabeled-data detection and data selection on a 1,000-sample CIFAR10 subset using ResNet18.The subset is used because some baselines require repeated model retraining.Source: §E.6 · p. 37

Mislabeled data detection

  • In-Run Data Shapley and influence functions perform comparably on mislabeled-data detection, outperforming all methods except KNN-Shapley.KNN-Shapley achieves the highest AUROC; results span three runs, with standard deviations reported in Table 4.Source: §E.6 · p. 37, Table 4 · p. 38

Data selection

  • For data selection, KNN-Shapley excels at small budgets, while single-training-run methods achieve similar performance at 60% and 80% budgets.Most attribution methods perform worse than random at small budgets; Table 5 reports test accuracy.Source: §E.6 · p. 37, Table 5 · p. 38

Related papers

Loading 2406.11011v3…