Data Shapley in One Training Run
Authors: Jiachen T. Wang
Prateek Mittal
Dawn Song
Ruoxi Jia
Venue: ICLR 2025 Oral (2025)
Keywords: Shapley value
data valuation.
Primary area: interpretability and explainable AI
TL;DR: We develop a new notion of Data Shapley that requires only one model training run.

Abstract: Data Shapley offers a principled framework for attributing the contribution of data within machine learning contexts. However, the traditional notion of Data Shapley requires re-training models on various data subsets, which becomes computationally infeasible for large-scale models. Additionally, this retraining-based definition cannot evaluate the contribution of data for a specific model training run, which may often be of interest in practice. This paper introduces a novel concept, In-Run Data Shapley, which eliminates the need for model retraining and is specifically designed for assessing data contribution for a particular model of interest. In-Run Data Shapley calculates the Shapley value for each gradient update iteration and accumulates these values throughout the training process. We present several techniques that allow the efficient scaling of In-Run Data Shapley to the size of foundation models. In its most optimized implementation, our method adds negligible runtime overhead compared to standard model training. This dramatic efficiency improvement makes it possible to perform data attribution for the foundation model pretraining stage. 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.

Published as a conference paper at ICLR 2025
DATA SHAPLEY IN ONE TRAINING RUN
Jiachen T. Wang Princeton University
Prateek Mittal Princeton University
Dawn Song UC Berkeley
Ruoxi Jia Virginia Tech
ABSTRACT
Data Shapley offers principled framework for attributing the contribution of data within machine learning contexts. However, the traditional notion of Data Shapley requires re-training models various data subsets, which becomes com- putationally infeasible for large-scale models. Additionally, this retraining-based definition cannot evaluate the contribution of data for specific model training run, which may often be of interest in practice. This paper introduces a novel concept, In-Run Data Shapley, which eliminates the need for model retraining and is specifically designed for assessing data contribution for a particular model of interest. In-Run Data Shapley calculates the Shapley value for each gradient update iteration and accumulates these values throughout the training process. We present several techniques that allow the efficient scaling of In-Run Data Shapley to the size of foundation models. In its most optimized implementation, our method adds negligible runtime overhead compared to standard model training. This dra- matic efficiency improvement makes it possible to perform data attribution for the foundation model pretraining stage. We present several case studies that offer fresh insights into pretraining data's 's contribution and discuss their implications for copyright in generative AI and pretraining data curation.
INTRODUCTION
In today's data-driven world, understanding the contribution of each data point is crucial, especially with the advent of foundation models that rely on vast amounts of training data from various sources. The lack of reliable data attribution mechanisms can lead to significant legal and societal issues, resulting in a growing backlash against the broader use of data for model training (Heikkilä 2023). For instance, there is risk of violating intellectual property rights, failing fairly compensate data creators, and disincentivizing them from producing new, high-quality content (Henderson et al. 2023). This has already resulted in legal disputes, such the New York Times lawsuit Microsoft/OpenA/ (Grynbaum & Mac 2023). Moreover, foundation models are often trained on massive datasets scraped from the internet, which can include low-quality and harmful content (Gao al. 2020 Raffel et al., [0200] Touvron al. (023). Problematic data not only wastes computational resources but also skews model outputs, potentially leading to biased or inaccurate results. By understanding the contribution of each data source, we can identify and mitigate the influence of low-quality data, thereby improving the efficiency and quality of model training.
Tamestlawsut against
Since the training data of foundation models comes from multiple stakeholders, it is essential to have an algorithm that can fairly attribute data contributions. In recent years, significant progress has been made in understanding what means fairly quantify and attribute data source contributions, with the Shapley value (Shapley) 1953) emerging as a widely adopted framework (Ghorbani & Zou 2019 Dia et al.) (019b)) Originating from cooperative game theory, the Shapley value uniquely satisfies several desirable properties: (1) It assigns equal scores to equally impactful data points, ensuring fairnsss; (2) the sum of contribution scores equals the total utility, meaning the scores always represent a share of the total utility; (3) it supports additive decomposition across multiple utility functions, allowing for the calculation of contributions to the entire test set by summing the scores of individual test points. As the Shapley value uniquely satisfies these properties, it eliminates the uncertainty and ambiguity surrounding which attribution frameworks should be used conceptually. While there are other Son-Shapley data attribution frameworks, such as Datamodels (Park et al.) 2023: Ilyas et al. 2022) and influence functions (Koh & Liang 2017). they lack the clear theoretical foundation and uniqueness provided by the Shapley value.

---

Published as a conference paper at ICLR 2025
Original Data Shapley definition faces computational & conceptual limitation. However, Data Shapley, i.e., the application of the Shapley value in data attribution, has been limited to very small- scale models. Existing methods (Ghorbani & Zou| 2019) to estimate the Shapley value require retraining the model numerous times using different subsets of data to evaluate the contribution of each data source, making them computationally infeasible for foundation models. On the other hand, retraining-based methods suffer from a conceptual issue often overlooked in the literature: they assess data contribution for a general learning algorithm rather than particular model. While one might interpret the former as an approximation of the latter, these two quantities can be quite different in practice, especially when the learning algorithm is randomized and sensitive to factors like random initialization and training data order. In many real-life scenarios, however, the primary interest lies in understanding data contribution to the specific model being trained and deployed.
This paper introduces In-Run Data Shapley, novel approach that makes fair data attribution applicable to large-scale foundation models. Unlike retraining- based Data Shapley, In-Run Data Shapley quantifies the contribution of each data source to the specific target model of interest.
Technical contributions. Our key insight is that ML models are trained using iterative algorithms,, where the model performance change in one iteration is sufficiently small to be accurately ap- proximated by first- or second-order Taylor expansions. We show that the Shapley value for the approximated one-step model performance change can be derived analytically via gradient dot- products or gradient-Hessian Hessianngrradinnt products between training and validation data. Hence, we can compute the Data Shapley scores for each model update step, and accumulate the scores throughout the training process. However, the per-sample gradient vectors required for computing the Shapley value in each training iteration introduce significant overhead due to per-sample gradient calculation. To address this challenge, we develop a series of technical tools that enable the exact calculation of gradient dot-products and gradient-Hessian- -gradienn products in one and two backward passes, respectively, without the need to instantiate any additional gradient vectors or Hessian matrices. Collectively, these tools allow for the efficient computation of In-Run Data Shapley. In particular, with sufficient GPU memory, its most efficient implementation is fast as regular training.
Empirical implications. Given the efficient algorithms developed in this paper, for the first time, one can perform data attribution the scale of foundation model pretraining. While in this paper, we focus on GPT2 and Pythia-410M as pilot study, our approach is applicable to larger-scale industrial models with sufficient computing resources. We performed various case studies that provide fresh insights into training data's 's contribution to the foundation model pretraining
(1) There is considerable room for improvement in data curation for pretraining (Section 5.3.1
Even well-curated pretraining corpora contain data points that negatively impact the training process. We demonstrate the effectiveness of In-Run Data Shapley in identifying these low-quality data points. By computing In-Run Data Shapley values during training and removing negatively valued data points, we show that the cleaned dataset leads to significantly faster model convergence and improved performance compared to the original dataset. Interestingly, despite the Pile dataset (Gao et a (020)) already undergoing multiple layers of curation, In-Run Data Shapley assigns negative values approximately 16% of the data. We found significant amount of noisy data among them, highlighting the need for improved data curation for foundation model training.
(2) Data's contribution is stage-dependent (Section 5.3.2). In-Run Data Shapley can capture the dynamics of contribution through the course of training. a fine- grained aspect that cannot be captured by prior works. In-Run Data Shapley shows that in the early stages of training, general corpora tend to have relatively large contribution regardless of the downstream tasks. This is because general corpora help the model learn basic language patterns, grammar, and common knowledge. However, in the later stages of training, the contribution from domain-speciff corpora becomes dominant, and the contribution of the general corpus phases out.
(3) Rethinking copyright in generative AI: contribution beyond memorization (Section 5.3.3 We studied training data's contribution to validation points of varying similarity levels. We found that even when the validation data is complete rewrite of the training data while maintaining the topic, the training data still contributes significantly. This finding has implications for the current dialogue around what constitutes copyright violation in generative AI (Mulligan & Li 2024). While the unfair use of copyrighted content is generally only considered when the generated data is an almost verbatim replication of the training data, our contribution analysis shows that some data owners should receive a certain royalty share for generated content, even if the output does not closely resemble the copyrighted material.
2

---

Published as a conference paper at ICLR 2025
2 BACKGROUND OF DATA SHAPLEY
In this section, we formalize the setup of data attribution for ML and revisit Data Shapley's definition.
Setup & Goal. Given a dataset Drr := { N data attribution or valuation aims assign a score to each training data point 2,, reflecting its importance for the trained ML model's 's performance on a certain task. Formally, we seek a score vector (0=;)²=1 where each Φz.- E R reflects the value of z4.
The Shapley value (SV) (Shapley 1953). originating from game theory, stands out as a distinguished method for equitably distributing total profit among all participating players. Before diving into its definition, we first discuss fundamental concept: the utiliity function.
Utility function. A utility function maps an input dataset to a score indicating the utility of the dataset for model training. In most of the existing literature (Ghorbani & Zou| 2019 Jia et al. [2019)), the utility function U is chosen as the performance (e.g., accuracy or loss) of the trained models on a hold-out validation set. That is, given training set S, the utility function US) = Per (A(S)), where A represents a learning algorithm that trains a model on dataset S, and (-) is a function assessing the model's performance. For example, Perf(-) can be the accuracy for classification task or the perplexity for a language completion task, evaluated on (set of) hold-out validation data.
Definition (Shapley value (Shapley 1953)). Let U.) denote a utility function and D represent a training set of N data points. The Shapley value, 6₂ (U), assigned data point 2 D is defined
as 02 (U) = 1 N Σx - (W=1) -1 Escp-., (US U {2]) USS) where D- = D > {z}.
In simple terms, the Shapley value is weighted average of the marginal contribution [=]) U(S), i.e., the utility change when the point is added to different Ss. For simplicity, we often write d² when the utility function is clear from the context. The popularity of the Shapley value is attributable to the fact that it is the unique data value notion satisfying four axioms: Null player, Symmetry, Linearity, and Efficiency. The mathematical definitions of these axioms are deferred to Appendix A.T Here, we introduce the linearity axiom which will be used later.
Theorem 2 (Linearity of the Shapley value (Shapley 1953)). For any of two utility functions U1, U2 and any a 02 E R, we have &2 (a, U1 + 2222) 0. 02 (U1) + 02Φz (U2).
Retraining-based Data Shapley. The convention of defining the utility function for Data Shapley as US)) = Pe()(A(S)) was introduced in Ghorbani & Zou (2019), where A is a learning algorithm such as a neural network trained by stochastic gradient descent (SGD) or its variants. With this choice of utility function, the precise calculation of the Shapley value requires retraining models various subsets of the data. This is because the marginal contribution of a data point, USS U {2)) - US)), can only be obtained by training models on both S and S U {2) and comparing their performance. As result, we refer to this method as FRetraining-buser Data Shapley".
Limitations beyond efficiency (detailed in Appendix B.I. In addition to the high computational costs, we emphasize that retraining- based Data Shapley also suffers from the following limitations: (1) Highly unstable value scores: When stochastic learning algorithms such as SGD are used, the resulting value scores can be highly unstable (Wang & Jia (023a). This instability may lead to unreliable results and potential violations of Shapley value's 's fairness axioms. (2) Conceptual limitations: Retraining-basse
Data Shapley measures the average data contribution to the learning process itself, across many retrainings on different data subsets. As a result, it produces attribution scores that apply broadly to the algorithm but fail to reflect the data contribution to specific training run. On the other hand, providing insights into how individual data points contribute to the deployed model enables more targeted analysis and debugging, thereby improving model interpretability.
IN- DATA SHAPLEY
To address the issues associated with Retraining- based Data Shapley such as high computational costs, value instability, and the inability to assess the contribution towards a specific trained model, we propose a novel data attribution method specifically tailored for a single training run. Our key idea is to leverage the iterative nature of model training and employ "divide and conquer" approach: breaking down the problem of valuing data contributions for the entire training process into subproblems of valuing data contributions for individual iterations.
Utility function for a single gradient update. Traditionally, the utility function U(S) = (A(S( encapsulates the overall impact of a training set S across the complete training process.
3

---

Published as a conference paper at ICLR 2025
Here, we instead consider a "local utility function" that evaluates the impact of data subsets within single iteration. Specifically, given a training dataset Dr = { a deep learning model is usually being trained to minimize the training loss Σi= {(w, 21) via an iterative optimization procedure such as SGD. The performance of the model is typically being measured through a set of validation points {2 During an iteration t, a batch B, - Du of the training points used to update the model parameters from Wy to w with W+++1 == Wty - T/ Eze,, Ve(W,, 2). where 1/ is the learning rate at iteration & +I complete run of neural network training thus consists of model checkpoints
fwo, Wi...., wr)- ). For given validation data point 2(val), we can define the "local utility function" at a single iteration as
U0 (val)) == (( ((va)) E(wr, ((W,22(vv) (val)))
(1)
where ( :- w2 The EEs Vl(we, 2) and S C Be is subset of the batch being selected in t-th iteration in the original training. Interpretation: The local utility function (+*) represents the loss change at iteration & when only the subset S is used for the gradient update. This approach incorporates the realization of random batch selection at f-th iteration into the utility function. can also encode other forms of training randomness (e.g., dropout) at iteration t. By accounting for the specific realization of training randomness, we obtain a deterministic utility function for each iteration, effectively enabling the targeted attribution to the specific training run.
Data Shapley for a single gradient update. While the utility U is defined over B, instead of the full training set Dir. is easy to augment it to Dr., More formally, in the augmented utility function we have w (S) := W0g 7) EsEsnB, Ve(w,, 2), S S Prr The Shapley value ø (L((t) will be exactly the same as the Shapley value corresponds to the augmented utility function for any = E B., and (U = 0 for any 2 E Drr \ B, (see Theorem 5 in Wang & Jia (023b)). Therefore, for a clean presentation, we slightly abuse the notation where U meaning depends on the context.
Data Shapley for the entire training run. Building on the concept of a "local" utility function for single gradient update iteration, we naturally extend this to a "global" utility function for the entire training process, defined as (S) E (S). Interpretation: This global utility function can be interpreted as the cumulative loss change of the entire training run, but under the counterfactual scenario where only subset of the training data S is used. In other words, it aggregates the total impact of the subset S on the model's performance throughout the entire training process. Due to the linearity property of the Shapley value (Theorem 2). we have (U)) = Σt= & (U.)). This new Data Shapley value, which we call In-Run Data Shapley, represents the cumulative contribution of the data point z across all gradient update iterations within single training run. This approach breaks down the broader utility into more manageable, step-by-step assessments that capture the immediate effects of data points on model updates, and provide a more fine-grained view of how individual data points contribute to the model's performance at each step of the training process. Notably, the sum of individual data points' Shapley values equals the overall loss reduction achieved by the model during the entire training run due to the Shapley value's ' efficiency axiom (see Appendix [A.I). This provides meaningful and interpretable measure of data importance. In Appendix B we give an in-depth
comparison between Retraining-based and In-Run Data Shapley.
Remark 1 (Multiple validation points). In practice, the model performance is often being assessed based on a validation set ((val) = {2(val)), After computing Φ2 (U(=:(vval)) for each 2(val) E D(val), one can compute the Shapley value corresponding to the utility function on the full validation set U(S; U(S;Dival) D(val) := Exveate U(S; z(val)) by simply taking the sum = ExtmetDiio oz (vaa)))a))) due to the linearity property of the Shapley
6z (U(; value (Theorem Z). Hence, for a clean presentation, consider only single (val) in this paper. However, all the techniques we developed can be extended to multiple validation points.
EFFICIENT COMPUTATION OF IN-RUN DATA SHAPLEY
The newly proposed In-Run Data Shapley does not require retraining models from scratch on different data subsets. However, calculating Φ= (U7()) for each training iteration remains computationally
Note that in practice, we take the gradient average for the update, hut here we incorporate the normalization term [8, into the learning rate T7e for clean presentation.
4

---

Published as a conference paper at ICLR 2025
intensive, as it involves evaluating the performance impact of all possible combinations within the sampled data batch. In this section, we introduce an efficient method for approximating In-Run Data Shapley scores during specific training run. Our approach, distinct from Monte Carlo methods, is deterministic and optimized to minimize additional runtime to regular training. In particular, in its most efficient implementation, our approximation technique incurs negligible extra runtime beyond what is required for standard model training, making it highly practical for real-world applications.
4.1 APPROXIMATING ( WITH TAYLOR EXPANSION
To derive a more tractable structure for the local utility function U(O), we propose using first and second-order Taylor approximations. The advantage of this approach is that the approximated utility function exhibits a form where closed-form Data Shapley formulas can be derived. The second-order Taylor approximation the local utility function is follows:
(S) = ((W6+1(S), 2(val))
E(w; z (val))
Velur, (val)) (S) w.) + (1 (S) I (mm))
(w)+1(S) - my) + higher order terms
(1) (8)
where the Hessian matrix H (ral)) Vell 2(va)).. We label the first-order term as U/) (5)
and the second-order term as (S). Note that the gradient update (s+ we
- Te EEes Vf(w,, =). Given that the learning rate b in model training is typically small, a lower- order Taylor expansion often provides an accurate approximation for the change in loss during single gradient update, with approximation errors of O and O(T²)) for first and second-order approximations, respectively. In Appendix E.2.2 we empirically investigate the errors of first- and second-order approximations to (+()) on GPT2. In particular, the first-order approximation can already achieve great performance with Spearman correlation > 0.94.
First-order In-Run Data Shapley. Using the first-order approximation U(t) ze U(O). and substituting (1))
the gradient update expression, we have U (1) (S) = -1; Exes Vilwe, ((val)) (- Vi(w,, z). This shows
that U7(t) is an additive utility function with a closed-form Shapley calculation as follows:
Theorem 3. In-Run Data Shapley considering the first-order approximation has closed-form
Φ (U)
(T())
(1)
where
de (u))) -T) V (vall) Ve(we, 2), t = 0, O
Thus, the first-order approximation of In-Run Data Shapley for a training point accumulates its gradient dot products with the validation data point each time the training point is sampled in the training batch. The gradient dot product between the training point 2 and the validation point z(val) represents the direct influence of z; on the validation loss at the current model parameters Wa which essentially measures the alignment between the two gradient vectors in the parameter space. Notably, de (U()) is equivalent to the TracIN-Ideal score proposed by (rruth et al. 2020). That is. the TracIN-Ides score be interpreted as the Shapley value when we use first-order Taylor approximation for (1t), However, TracIN-Ideal has been described as "computationaaly infeasible," and our approach completely overcomes this problem. In Appendix AA.3 we provide a detailed discussion of the differences between this work and (Pruthi et al. 2020).
Second-order In-Run Data Shapley. We further improve the approximation of (F(() using a second- order Taylor expansion, i.e., (1)) as U(0 + _ Fortunately, the approximated utility function maintains tractable structure that allows closed-form Shapley value calculation.
Theorem 4. Iu-Run Data Shapley considering the second-order approximation has closed-form
1 0= (v!))
(.) R
Σ 1=0
Φ= (U())
(2)
2
5

---

Published as a conference paper at ICLR 2025
where
Φ2 (v()) + 22 (Ug)
te Velwe, ( Ve(ue,)) =)
Vilae, a)
Σ FJEB
2
(3)
befiurnce glonl)
intersacioon between and other maining points
for any (- 0...., T 1.
Compared to the first-order variant, the second-order In-Run Data Shapley includes an additional Meadient-Hessiant Hessian-gradient product term that captures the interaction between the training point of interest and the rest of the training set. The Hessian matrix represents the curvature of the validation loss function at the current model parameters Wt. This interaction term measures the alignment between the gradient of and the gradients of the other points in the training batch, adjusted by the Hessian. If this term is large, it indicates that the presence of other points in the batch significantly impacts the value attributed to z. For example, if there many identical or similar copies of in the training set, the contribution of 2 will decrease, as the interaction term will be large, effectively distributing the value among the similar points. By incorporating this interaction term, the second- order In-Run Data Shapley provides a more fine-grained contribution measure that takes into account both the relevance of a data point towards validation set and its uniqueness within the population.
4.2 EFFICIENT COMPUTATION OF GRADIENT DOT-PRODUCT AND HAADIENT-HESSIAN-GRAAA
PRODUCT
Although we have derived closed-form formulas for In-Run Data Shapley using first- or second-order Taylor approximation of the local utility functions, efficiently computing these values remains challenge. Specifically, for the first-order In-Run Data Shapley, it requires computing ! the pairwise gradient dot products between each z E B3 and the validation point. For the second-order In-Run Data Shapley, it additionally requires computing
2 the gradient- Hessian- dressian-gradient products for each = E B,. A direct implementation to compute involves calculating the individual gradient for each data point in B,, which cannot benefit from fast batch processing in GPUs and necessitates running backpropagation [B,| times with a mini-batch size of 1. Consequently, this approach would be at least [B,] times slower than regular training. making computationally prohibitive for practical applications. Furthermore, computing 2 requires either computing each individual gradient again or storing all individual gradients, which incurs significant time or memory overhead.
Computing piir-wise gradient dot-products in backpropagation. Our technique for efficiently computing pairwise gradient dot products is inspired by the "ghost clipping" technique from the differential privacy (DP) literature (Lee & Kifer 2021). "Ghost clipping" enables computing all of the per-sample gradient norms within one backpropagation without explicitly forming any individual gradient vectors, which enhances the efficiency of DP model training. Here, we propose a "ghost dot- product" technique that shares the idea of exploiting the computation that has been done in the backpropagation. Specifically, denote a sample batch as B, = {ži, zn). We demonstrate this technique using simple linear layer = aW, where W E RRd xd2 is the weight matrix, (s(1) .....
"......s..)..... s(B))T is the output (i.e., the (a(1) 2....: a ( is the mini-batch input, and Bxdi ,s E Bxds, By applying the chain rule, pre-activation tensor). For (non-sequential) data, a E TR.
we can express the gradient of an individual loss g(3 := f(w, 2;) with respect to W as
ag(i)
ae(i)
Os
de(i)
de
aw
OW
as(t)
where e : Eド= (65) is the aggregated loss, and the last step is because other data points' losses
8t is readily available have no dependency on s;, Note that the individual's output gradient कडी 361т
8r03
during the backpropagation pass in terms of L. Suppose we are interested in computing the gradient
dot-product aw aw between two data points 21, 22 in the same batch in the backpropagation.
agdh)
0e(2)
For non-sequential data, have each ( E dR and ag(
RR IXdx, By 44, we have
8x(5)
1
2
agei
2
((a)) aat)) (
(000) ()(2))
1)
a
(5)
aW
aW
(s(1)
(5
05(1) (x(2)

---

Published as a conference paper at ICLR 2025
Hence, first take the two inner products, and then multiply the results together. All of the quantities a11), (2)) (g(1) ag33)
Tgtty's āytzy in 55) that are required for computation are all already available in the backpropagation. Hence, within single backpropagation, we can efficiently compute the gradient dot-producd between every pair of 2,, 2j E B,. Since we are interested in computing the gradient dot-product between ((val) and for all
Bi, we can backpropagate on ExeR, (()) + g(alval)
to save another backpropagation for 2((al), We call this technique the "ghost dot-product", as no gradient vectors instantiated during the computation. Overall, we only need one backpropagation to compute ! for all data points in B,, a significant improvement over the direct method requiring
2 |B,] backpropagations. Additional details for this technique are in Appendix D
Remark 2. While we illustrate our "ghost dot- not-product" technique using linear layers, it can be
extended to other types of layers by leveraging similar decompositions as in Equation (4) that have
been developed in differential privacy literature (Rochelte et al. 2020 Bu et al. 2022 Li el al. 2027
Bu et al. 2023 Kong & Munoz Medina 2024).
Computing gradient- Hessian-gradient products in 2 backpropagations (Appendix D.2). For second-order In-Run Data Shapley, outstanding challenge is how efficiently compute the pairwise interaction term among training points. In Appendix [D2] we develop a "ghost -antient--lessian- gradient product" " technique for computing the desired quantity through one extra backpropagation pass, without materializing any gradient-sized vectors. This technique leverages several properties of neural network gradients across different layers, and its derivation is complex.
Further improvement of runtime and memory requirements (Appendix D.3). With the "ghost" techniques developed, the computation of first- and second-order In-Run Data Shapley requires one and two backpropagattons in each gradient update iteration respectively. Although we still need to compute the gradient of the aggregated loss E..er, L, for the training batch to perform parameter updates, we do not need an additional backpropagation. By reusing the activations and output
gradients from the previous backpropagation on Exes, (()) + ((=(m)) we can easily compute this quantity without incurring the cost of an extra backpropagation pass. Consequently, training while computing first-order In-Run Data Shapley will have minimal additional runtime overhead, as it still requires only one backpropagation per iteration. The second-order In-Run Data Shapley necessitates one extra backpropagation per iteration. Nevertheless, both methods provide significant advantages over the direct approach of instantiating per-sample gradients and -eector products.
5 EXPERIMENTS
In this section, we evaluate In-Run Data Shapley in terms of its efficiency (Section 5.1 fidelity (Section 5.2)). and its applications in data attribution for language model pretraining (Section 5.3) In
Appendix E.6 we compare a variety of existing data attribution methods in small-scale settings.
5.1 RUNTIME EVALUATION
We empirically assess the computational efficiency of In-Run Data Shapley with "ghost Heae--eesiiineee product" techniques developed in Section
dot-product" and "ghost implementation of In-Run We compare this the direct
Data Shapley, which requires computing per-sample gra- dients, as well as to regular training without Data Shapley computations. The experiment is conducted by training GPll-Small on a single 80GB A100 GPU. As illustrated in Table [ the runtime of first-order In- Run Data Shapley is close to that of regular training when using the ghost dot- dot-product algorithms developed in Section 4.2 The second-order In-Run Data Shapley is approximately 2 slower than regular training due to the additional backprop- agation. However, both the first- and second-order In-Run Data Shapley are significantly faster (> 30x) compared to the naive implementation. These results showcase the substantial improvements achieved by our techniques, making In-Run Data Shapley computationally feasible for practical applications.
Throughput
Regular Training
76.2
First-order Data Shapley (ghost)
70.5
Second-order Data Shapley (ghost)
34.4
First-order Data Shapley (direct)
4.2
Second-order Data Shapley (direct)
Table I: Efficiency comparison of dif- ferent implementations of In-Run Data Shapley. We use throughput, i.e., train- ing data points being processed per sec- ond as the efficiency metric.
7

---

Published as a conference paper at ICLR 2025
5.2 FIDELITY EVALUATION
In this section, we directly assess the approxima- tion accuracy of first- and second-order In-Run Data Shapley. In Appendix E.6 we further com- pare the performance of Run Data Shapley with existing (less scalable) data attribution tech- niques on standard benchmarks (e.g. mislabeled data detection) as an additional sanity check.
Pask-antar Apprentnalkan (1960050.9000))
Shapley
Seorsd-arder Appreciration (1M65--6-0000))
3.002
Porseder Data
2.001
0,501
2.000
0,500
Spoodd
-2.00
-0.001
-2,002
-0.002
(a)
(b)
Staato Carlo bitenadion
Mocte-Cutlo tstaraleos
Given that computing the exact In-Run Data Shapley value is computationally prohibitive, we compare their performance against Monte Carlo estimates of the Shapley value using large number of samples. The experiment is conducted on GPT2 model at the 3500th training iteration on Pile, where the batch size 16 and learning rate 10-4. We use 1000 permutations to approximate the groundtruth In-Run Shapley value. Figure 0 shows that with just first-order In-Run Data Shapley, the root mean squared error (RMSE) is only around 0.0003. In Appendix E.2. we provide additional results with different learning rates.
Figure 1: Comparison between the Monte Carlo- estimated In-Run Data Shapley and First/Second-
order In-Run Data Shapley.
5.3 CASE STUDY: DATA ATTRIBUTION ON PILE DATASET
In this section, we present a case study to demonstrate the use cases of In-Run Data Shapley by pretraining on the well-known Pile dataset (Gao al. 2020p. We explore its application in data curation, examine data contribution across different training stages, and investigate relevant corpus detection. Due to computational resource constraints, most of our experiments focus on the GPT-2 and Pythia-410M models. but this is not limitation of the algorithm itself. With adequate computational resources, our approach can easily be applied to larger-scale models.
5.3.1 Is WELL-CURATED DATASET ACTUALLY CLEAN?
Carefully curated pretraining corpora still contain data points that can adversely affect the training process. Identifying and removing these data points can accelerate model convergence and enhance overall performance, thereby saving computational resources. In this experiment, we demonstrate the effectiveness of In-Run Data Shapley in assessing the data quality of subset of the Pile dataset. We uniformly select a random subset of Pile with around 10B tokens and train a GPT2 model on this subset. We compute the data attribution results with Pile's validation set. By filtering out all negatively valued corpora and retraining the model on the cleaned subset, we observe significant improvement in model convergence. For both first- and second-order In-Run Data Shapely, we can achieve around 25% fewer training iterations to reach test loss of 3.75. Surprisingly, our analysis reveals that around 16% of the training corpora had negative second-order In-Run Data Shapley values. While some of the negatively valued corpora may be attributed to the significant domain shift. compared to the validation corpora, we still find many low-quality corpora from Pile, a pretraining dataset that has undergone several layers of data curation (Gao al. 2020). Examples of low-quality corpora identified can be found in Appendix E.3
Test
Figure 2 shows a performance comparison between the original training run and the model trained on the cleaned subsets for GPT2, and additional results on Pythia-410M in Appendix E.3.I We also compare with influence function (Koh & Liang, 2017), which approximates the change in the model's loss on the test example when the training example removed from the training set (i.e., the leave-one-out score). We omit TRAK (Park et al. 2023) and other techniques such as datamodel (Ilyas et al. 2022) as they are not scalable to our setting. As we can see, influence function can also filter out low-quality data that can accelerate training convergence. However, the performance is slightly worse than In-Run Data Shapley as the influence function only uses information from the final trained models, which can result in highly noisy value scores since the removal of one training data point might have a negligible effect on the final model performance. The results demonstrate that removing lower-quality
Original
8
Data Shopley
Influence Puretion
available
7
5
25% faster
1000
2000
3000
4000
5000
Iterations
Figure 2: Test loss comparison be- tween the original training run and the model trained on the cleaned subset according to different data attribution techniques.
8

---

Published as a conference paper at ICLR 2025
Original Wikipedia Corpus
Synthetic "Similar topic" Corpus
In 2012, Radhi recruited new 'musicians' for OAG, who were selected from among the stu- dents of Akademi Seni Budaya dan Warisan Ke- bangsaan (). The new line-up consists of Qi Razali (drums/backing vocals original drummer...
Write short story about classical violinist who decides to explore jazz music, detailing her first encounter with jazz band. #H# Answer: Elena, classically trained violinist known for precise and emotive performances ...
### Instruction:
Similarity Category
In-Run Data Shapley (1st order)
In-Run Data Shapley (2nd order)
Influence Function
BM25
Partial exactly the same
Paraphrase
Significant paraphrase
32.3
32
39.3
1.6
Simillar topic
145.6
141.6
292
20917.3
Table 2: Top: (left) An original training corpus from Wikipedia. (right) A synthetic corpus falls in the category of "Similar topic" to the Wikipedia corpus on the left (prompt in Appendix E.5). Bottom: the (average) value rank of the original corpus among all training corpora for validation corpora that are of varying similarity to the original corpus. The rank is out of ==20 data points.
Contribution by Domain
Domain Size
Validation Corpus
Pile-CC
100
Domain Contribution Percentage (%)
Github
In several applications, the matrix coef- ficients the nonlinear valued function G(A) in are usually of low rank
StackExchange
HackerNews
80
Wikipedia (en)
ArXiv
(+) High-valued Corpus
60
DM Mathematics
PubMed Abstracts
The Lagrangian L4 00.000000000 describes meson interactions,
PubMed Central
NIH ExPorter
Appendix of Ref. [@ Gallas]. After ...
Ubuntu IRC
EuroParl
20
PhilPapers
(-) Low-valued Corpus
USPTO Backgrounds
FreeLaw
Coronavirus Testing in San Diego County' n How San Diego Is Getting Ready for Self-Driving Cars
00
2000
4000
Gutenberg (PG-19)
Number of Steps
Enron Emails
Figure: 3: Left: Domain value composition for corpus of math text. Right: The math corpus we use as the validation data for attribution, and examples of high- and low-valued training corpus for it.
data leads to a significantly faster drop in test loss compared to the original training run. This implies that there is still huge room for data curation for well-curated datasets such as Pile.
5.3.2 How Do DATA VALUES CHANGE DURING TRAINING?
As In-Run Data Shapley tracks the cumulative data values across different training steps, assess the contribution of training points at various stages of training, providing a more fine-grained perspective data attribution. We evaluate the data attribution results for math-related validation data using second-order In-Run Data Shapley. In Figure we present the value composition of training сorporа by their domains over the first 10,000 training iterations, summing the values of all corpora from the same domain. We then calculate the percentage of the total value attributed to each domain, excluding domains with a total value from ArXiv achieve a significantly higher value compared to other domain corpora, far exceeding its size proportion within the full Pile dataset. This is expected, as ArXiv papers predominantly cover fields like Math, Computer Science, and Physics, which contain extensive math-related content. Furthermore, the value composition changes rapidly at the beginning of training and stabilizes as training progresses. We hypothesize that this initial fluctuation is due to the presence of relevant paragraphs in corpora from other domains. The stable value proportion observed later stages likely reflects the relative abundance of math content in each domain. Interestingly, domain, which contains general website crawls, initially shows positive contributions during the first few iterations. However, its value quickly drops negative and eventually converges zero. This implies that general corpora tend to have large contribution in the beginning of training, as they help the model learn the basics of languages, such as grammar and common knowledge. However, as training progresses and the model focuses on more specialized topics, the relevance of general domains diminishes. additional figure for the average domain values is in Appendix E..4
As illustrated in the figure, the corpora
observe that Pile-CC

---

Published as a conference paper at ICLR 2025
5.3.3 DOES CONTRIBUTION REQUIRE MEMORIZATION?
In this experiment, we evaluate the robustmess of different data attribution techniques in identifying relevant individual corpora that have been paraphrased. We start by selecting a data point from the training set and creating several paraphrased versions using GPT-4, with varying levels of paraphrasing (see Appendix F..5 for the prompt). These paraphrased versions form our validation set. We then calculate the average value rank of the original training data for each of its paraphrased versions. In addition to In-Run Data Shapley and influence function, we include the ranking result based on BM25 distance. BM25 (Robertson et al. 2009) featurizes examples by their word frequency statistics (i.e.. TF-IDF) rank the training instances. We use BM25 distance verbatim or lexical similarity between the validation data (query) and the training data, as opposed to semantic similarity.
oracle for assessing the
As shown in Table 2 even for a validation data that is a complete rewrite (with low BM25 distance) but covers relevant topics. the original training data still ranks very high according to both In-Run Data Shapley and influence function. Influence function ranks the original training data lower than In-Run Data Shapley, which may be attributed the inherent noisy nature of the leave-one-out error estimation. The results of this experiment have important implications for the ongoing discussion about the copyright of generative AI. Specifically, the table presents a compelling example where the original Wikipedia training corpus related to musician's 's experience can significantly contribute to generating a story about a musician, even when the generated story shares no token-wise resemblance to the original training data. This finding supports that training data profoundly influences the capabilities of generative AI models and should be compensated accordingly (Deng & Ma [2023] Wang al., 2024b), even when the output does not closely resemble the original copyrighted material or when the model applies output filters to avoid generating verbatim replicates of the training data. This discovery expands the conventional focus on copyright violations, which typically addresses instances of near-verbatin replication, as seen in the dispute between New York Times and OpenAL, to also include cases where the generated content is significantly influenced by copyrighted material without directly replicating it.
6 CONCLUSION AND LIMITATIONS
In this work, we introduce In- Data Shapley, novel data attribution technique that addresses the limitations of Rettaaining--aae based Data Shapley. Extensive experiments demonstrate the effectiveness of In-Run Data Shapley in various applications. Here, we discuss the potential limitations of this work.
Availability of validation data before training. One potential limitation of In-Run Data Shapley is that it requires the validation data to be available before training, the data attribution scores computed during the training process. However, there are many scenarios where validation data is naturally available before training, such when using publicly available benchmark datasets, partici- pating in machine learning competitions, or adhering to regulatory requirements. For scenarios where validation data arrives after the model has been trained, potential solution is to save checkpoints of intermediate models during training and approximate In-Run Data Shapley using these checkpoints, in the same spirit of TracIN-CP described in Pruthi et al. (2020). However, the choice of checkpoints can significantly impact performance, and it is unclear w which checkpoints to pick.
Extension to other optimization algorithms. Extending the "ghost" family techniques developed in this work to support Adam and similar optimizers remains an exciting direction for future research. We stress that extending the formulation of In-Run Data Shapley from SGD to Adam is feasible, but the actual challenge lies in computing it efficiently without instantiating each individual gradient vector, which cannot be solved by simple extensions described in Xia et al. (2024).
Handling memory constraints. In scenarios where GPU memory constraints prevent large batch sizes, the "ghost" techniques can be extended by using gradient accumulation. This approach accom- modates larger training batch sizes by dividing the batch into smaller sub-batches and accumulating gradients over multiple iterations. While this method may increase runtime due to additional back- propagation steps, it maintains the feasibility of the techniques under memory constraints. Improving computational efficiency for large batch sizes remains an important direction for future research.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENT
This work is supported in part by the National Science Foundation under grants IIS-2312794, IIS- 2313130, OAC-2239622, Amazon- Virginia Tech Initiative in Efficient and Robust Machine Learning. and the Commonwealth Cyber Initiative.
We thank Meng Ding, Chong Xiang, Chendi Wang for their helpful feedback on the preliminary version of this work.
REFERENCES
Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. In International Conference on Learning Representations, 2019.
Juhan Bac, Nathan Ng, Alston Lo, Marzyeh Ghassemi, and Roger B Grosse. If influence functions are the answer, then what is the question? Advances in Neural Information Processing Systems, 15:17953-17991 2022.
S Basu, P Pope, and S Feizi. Influence functions in deep learning are fragile. In International Conference on Learning Representations (ICLR), 2021.
Stella Biderman, Hailey Schoelkopf, Quentin Gregory Anthony, Herbie Bradley, Kyle O' O'Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, et al. Pythia: A suite for analyzing large language models across training and scaling. In International Conference on Machine Learning, pp. 2397-2430. PMLR, 2023.
Zhiqi Bu, Jialin Mao, and Shiyun Xu. Scalable and efficient training of large convolutional neural networks with differential privacy. Advances in Neural Information Processing Systems, 35: 38305-38318, 2022.
Zhiqi Bu, Yu-Xiang Wang, Sheng Zha, and George Karypis. Differentially private optimization on large model small cost. In International Conference Machine Learning, pp. 3192-3218. PMLR, 2023.
Mark Alexander Burgess and Archie C Chapman. Approximating the shapley value using stratified empirical bernstein sampling. In IJCAI, pp. 73-81, 2021.
Sang Keun Choe, Hwijeen Ahn, Juhan Bae, Kewen Zhao, Minsoo Kang, Youngseog Chung, Adithya Pratapa, Willie Neiswanger, Emma Strubell, Teruko Mitamura, et al. What is your data worth to gpt? Ilm-scale data valuation with influence functions. arXiv preprint arXiv:2405. 13954, 2024.
R Dennis Cook and Sanford Weisberg. Characterizations of empirical influence function for detecting influential cases in regression. Technometrics, 22(():495-55 1980.
Ian Covert, Chanwoo Kim, Su-In Lee, James Zou, and Tatsunori Hashimoto. Stochastic amortization: A unified approach to accelerate feature and data attribution. arXiv preprint arXiv:2401.15866 2024.
Junwei Deng and Jiaqi Ma. Computational copyright: Towards a royalty model for ai music generation platforms. arXiv preprint arXiv:2312.06646 2023.
Jasjeet Dhaliwal and Saurabh Shintre. Gradient similarity: An explainable approach to detect adversarial attacks against deep learning. arXiv preprint arXiv: 10707, 2018.
Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. Advances in Neural Information Processing Systems, 33:2881-2891, 2020.
Stanislav
Fort and Surya Ganguli. Emergent properties of the local geometry of neural loss landscapes. arXiv preprint arXiv: arXiv:1910.0550 1910.05929, 2019.
11

---

Published as a conference paper at ICLR 2025
Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, et al. The pile: An 800gb dataset of diverse text for language modeling. arXiv preprint arXiv:2101.0002, 2020.
Amirata Ghorbani and James Zou. Data shapley: Equitable valuation of data for machine learning. In International Conference on Machine Learning, pp. 2242-2251. PMLR, 2019.
Amirata Ghorbani, Michael Kim, and James Zou. distributional framework for data valuation. In International Conference Machine Learning, pp- 3535-3544, PMLR, 2020.
Roger Grosse, Juhan Bae, Cem Anil, Nelson Elhage, Alex Tamkin, Amirhossein Tajdini, Benoit Steiner, Dustin Li, Esin Durmus, Ethan Perez, et al. Studying large language model generalization with influence functions. arXiv preprint arXiv:2308.03222 2023.
Michael M Grynbaum and Ryan Mac. The times openai and microsoft. The New York Times, pp. B B1-B1, 2023.
Melissa Heikkilä. this http:://www...cooooooooooe/e////
This new tool
could
give artists an edge over
ai.
2023. 2023
Peter Henderson, Xuechen Li, Dan Jurafsky, Tatsunori Hashimoto, Mark A Lemley, and Percy Liang. Foundation models and fair use. arXiv preprint arXiv:2303./5715, 2023.
Ferene Illés and Péter Kerényi. Estimation of the shapley value by ergodic sampling. arXiv preprint arXiv:1906.0522 052244 2019.
Andrew Ilyas, Sung Min Park, Logan Engstrom, Guillaume Leclere, and Aleksander Madry. Data- models: Predicting predictions from training data, arXiv preprint urXiv:2202.00622. 2022.
Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nezihe Merve Gurel, Bo Li, Ce Zhang, Costas J Spanos, and Dawn Song. Efficient task-specific data valuation for nearest neighbor algorithms. Proceedings of the VLDB Endowment, 2019a.
Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes. Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, and Costas J Spanos. Towards efficient data valuation based on the shapley value. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1167-1176. PMLR, 2019b.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International Conference Machine Learning, pp. 1885-1894, PMLR, 2017.
Weiwei Kong and Andres Munoz Medina. A unified fast gradient clipping framework for dp-sgd. Advances in Neural Information Processing Systems, 36, 2024.
Yongchan Kwon and James Zou. Beta shapley: a unified and noise-reduced data valuation framework for machine learning. In International Conference Artificial Intelligence and Statistics, pp. 8780-8802. PMLR, 2022.
Yongchan Kwon, Manuel A Rivas, and James Zou. Efficient computation and analysis of distributional shapley values. In International Conference Artificial Intelligence and Statistics, pp. 793-801. PMLR, 2021.
Jaewoo Lee and Daniel Kifer. Scaling up differentially private deep learning with fast per-example gradient clipping. Proceedings on Privacy Enhancing Technologies, 2021.
Weida Li and Yaoliang Yu. Faster approximation of probabilistic and distributional values via least squares. In The Twelfth International Conference on Learning Representations, 2023.
Weida Li and Yaoliang Yu. Robust data valuation with weighted banzhaf values. Advances in Neural Information Processing Systems, 36, 2024.
Xuechen Li. Florian Tramer, Percy Liang, and Tatsunori Hashimoto. Large language models can be strong differentially private learners. In International Conference on Learning Representations, 2021.
12

---

Published as a conference paper at ICLR 2025
Jinkun Lin, Anqi Zhang, Mathias Lécuyer, Jinyang Li, Aurojit Panda, and Siddhartha Sen. Measuring the effect of training data on deep learning predictions via randomized experiments. In International Conference Machine Learning, pp. 13468-1333 13504. PMLR, 2022.
Rory Mitchell, Joshua Cooper, Eibe Frank, and Geoffrey Holmes. Sampling permutations for shapley value estimation. 2022.
Caitlin right.
Mulligan and James Li. AI Snake Oil, 2024. URL Sttps://wwwp aisnakeoil com/p/
Generative ai's end run around copy-
run couu---round-- generatiie-ais-end
Elisa Nguyen, Minjoon Seo, and Seong Joon Oh. A bayesian approach to analysing training data attribution in deep learning. Advances in Neural Information Processing Systems, 36, 2023.
Ramin Okhrati and Aldo Lipani. A multilinear sampling algorithm to estimate shapley values. In 2020 25th International Conference on Pattern Recognition (ICPR), pp. 7992-7999. IEEE, 2021.
Sung Min Park, Kristian Georgiev, Andrew Ilyas, Guillaume Leclere, and Aleksander Madry. Trak: attributing model behavior scale. In Proceedings of the 40th International Conference Machine Learning, pp. 27074-27111 27113, 2023.
Garima Pruthi, Frederick Liu, Satyen Kale, and Mukund Sundararajan. Estimating training data influence by tracing gradient descent. Advances in Neural Information Processing Systems, 33: 19920-19930, 2020.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models unsupervised multitask learners. 2019.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research, 21(140):1-6) 2020.
Stephen Robertson, Hugo Zaragoza, al. The probabilistic relevance framework: Bm25 and beyond. Foundations and Trends@ in Information Retrieval, 3(4)3333-38, 2009.
Gaspar Rochette, Andre Manoel, and Eric W Tramel. Efficient per-example gradient computations in convolutional neural networks. In Workshop Theory and Practice of Differential Privacy (TPDP), 2020.
Andrea Schioppa. Gradient sketches for training data attribution and studying the loss landscape. arXiv preprint arXiv:2402.039)) 2024.
Lloyd Shapley. A value for n-person games. Contributions the Theory of Games, 2(28))307-317,
1953.
Anders Søgaard et al. Revisiting methods for finding influential examples. 1rXiv:2111.0466 2021.
arXiv preprint
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 13971, 2023.
Jiachen T Wang and Ruoxi Jia. Data banzhaf: A robust data valuation framework for machine learning. In International Conference on Artificial Intelligence and Statistics, pp. 6388-6421. PMLR, 2023a.
Jiachen T Wang and Ruoxi Jia. note on" towards efficient data valuation based on the shapley value". arXiv preprint arXiv:2302.1143), 2023b.
Jiachen T Wang and Ruoxi Jia. note on" efficient task-specific data valuation for nearest neighbor algorithms". arXiv preprint 23X::23044.0258.. 2023c.
Jiachen T Wang, Yuging Zhu, Yu-Xiang Wang, Ruoxi Jia, and Pratcek Mittal. Threshold knn-shapley: A linear-time and privacy-friendle approach to data valuation. arXiv preprint arXiv:2308.15700 15709, 2023.
13

---

Published as a conference paper at ICLR 2025
Jiachen T Wang, Zhun Deng, Hiroaki Chiba-Okabe, Boaz Barak, and Weijie Su. An economic solution to copyright challenges of generative ai. Technical report, 2024a.
Jiachen T Wang, Zhun Deng, Hiroaki Chiba-Okabe, Boaz Barak, Weijie Su, et al. An economic solution to copyright challenges of generative ai. arXiv preprint arXiv:2404. 13964, 2024b.
Jiachen T Wang, Prateek Mittal, and Ruoxi Jia. Efficient data shapley for weighted nearest neighbor algorithms. arXiv preprint arXiv:2401. /100,, 2024c.
Jiachen I Wang, Tianji Yang. James Zou, Yongchan Kwon, and Ruoxi Jia. Rethinking data shapley for data selection tasks: Misleads and merits. arXiv preprint arXiv:2405.0387,, 2024d.
Tianhao Wang, Johannes Rausch, Ce Zhang, Ruoxi Jia, and Dawn Song. A principled approach to data valuation for federated learning. In Federated Learning, pp. 153-167. Springer, 2020.
Mengzhou Xia, Sadhika Malladi, Suchin Gururangan, Sanjeev Arora, and Danqi Chen. Less: Selecting influential data for targeted instruction tuning, In Forty-first International Conference on Machine Learning, 2024.
Ziao Yang, Han Yue, Jian Chen, and Hongfu Liu. On the inflation of knn-shapley value. arXiv preprint arXiv:2405.1744 2024.
Chih-Kuan Yeh, Ankur Taly, Mukund Sundararajan, Frederick Liu, and Pradeep Ravikumar. First is better than last for training data influence. arXiv preprint arXiv:2202. 11844, 2022.
Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn. Gradient surgery for multi-task learning. Advances Neural Information Processing Systems, 33: 1824-5836 2020.
14

---

Published as a conference paper at ICLR 2025
A EXTENDED RELATED WORKS
A.1 DATA SHAPLEY AXIOMS
Data Shapley is one of the first prineipled approaches to data attribution being proposed Ghorbani & Zou ) Jia et al.] (2019b). Data Shapley is based on the famous Shapley value (Shapley [953)) In almost all of the literature, the Shapley value is being justified as the unique value notion satistying the following four axioms:
1. Null player: U U (z+)) = USS for all S D {zi,, then oz (U) =0
2. Symmetry: if USSUUUU {21}) = USS (zy1) for all S _ D fas, 2j}, then (U) = (U).
3. Linearity: For utility functions U1, U2 and any an 02 E R. (z, + a2U2) =
0102, (U1) + a202, (U2).
4. Efficiency: for every U, EXED 6z, (U) U(D).
In plain words, null player axiom means the Shapley value will assign zero score to data points with no contribution. Symmetry axiom requires equal scores assigned to equally impactful data points, ensuring fairness. Efficiency axiom requires the sum of contribution scores equal to the total utility, meaning the scores always represent share of the total utility. Linearity axiom means the Shapley value supports additive decomposition across multiple utility functions, allowing for the calculation of contributions to the entire test set by summing the scores of individual test points.
A.2 DATA SHAPLEY AND FRIENDS
Since its introduction in 2019 Ghorbani & Zou 2019: Jia et al. 2019b). Data Shapley has rapidly gained popularity as a principled solution for data attribution. Due to the computationally expensive nature of retraining-baac based Data Shapley, various Monte Carlo-based approximation algorithms have
been developed (Jia et al. 2019b IIlés & Kerényi 2019 Okhrati & Lipani 2021
Burgess & Chapman
2021 [ et al.) 2022 Lin al. [022] Wang & Jia [202bb] Li & Yu 2023 Covert et al.) [2024).
these methods still necessitate extensive computational resources due to repeated model retraining,
which is clearly impractical for modern-sized ML models. Many of its variants have been proposed. Kwon & Zou| (2022) argues that the efficiency axiom is not necessary for many machine learning applications, and the framework of semivalue derived by relaxing the efficiency axiom. [Lin et al.) (2022) provide an alternative justification for semivalue based on causal inference and randomized experiments. Based on the framework of semivalue, Kwon & Zou (2022) propose Beta Shapley, which is collection of semivalues that enjoy certain mathematical convenience. [Wang & Jia (2023a) propose Data Banzhaf, and show that the Banzhaf value, another famous solution concept from cooperative game theory, achieves more stable valuation results under stochastic learning algorithms. Li & Yu (2024) further improves the valuation stability by considering value notions outside the scope of semivalue.
The classic leave-one-ous out error is also a semivalue, where the influence function (Cook & Weisberg 1980: Koh & Liang, 2017: Grosse al. 2023) is generally considered as its approximation. A concurrent work (Choe et al.) 2024) leverages a similar gradient decomposition technique as our paper to speed up influence function calculation. However, several works have pointed out the fragility of influence function for deep learning models (Basu et al. 2021 Søgaard et al. 2021 Bac al. 2022), due to the strong assumptions of training convergence and strongly convexity of the loss function. Nguyen et al. (2023) takes Bayesian view of data attribution and is able to evaluate the variance of LoO. Unlike Nguyen et al. (2023), our work explicitly incorporates specific training randomness (e.g., model initialization, batch ordering) into the utility function definition, providing attribution scores that reflect contributions to the exact training trajectory.
Another line of works focuses improving the computational efficiency of Data Shapley by considering K nearest neighbor (KNN) as the surrogate learning algorithm for the original, potentially complicated deep learning models (Jia et al.) 2019a; Wang & Jia, 2023c; Wang et al.) 2023 2024c
Yang et al. 2024). Ghorbani et al. (2020); K won et al. (202)) Li & Yu (2023) consider Distributional Shapley, generalization of Data Shapley to data distribution. In federated learning setting, Wang
ct al. (020)) proposes a similar idea of computing the Shapley value for each federated learning round.
15

---

Published as a conference paper at ICLR 2025
Remark 3. Randomized Monte Carlo estimators can be inefficient and may produce unstable valuation results, potentially violating fairness axioms of the Shapley value (e.g. the Symmetry axiom) due inherent approximation errors. In contrast, In-Run Data Shapley does not rely on Monte Carlo estimators. Instead, it computes the exact Shapley value for an approximated utility function via Taylor expansion. This approach adheres the fairness axioms while ensuring the reliability and consistency of the data valuation results.
A.3 COMPARISON WITH TRACIN (RRTHI ET AL. 2020
The form of first-order In-Run Data Shapley from Section 4.1 coincides with the TracIN-Ideal in Pruthi et al. (2020). This provides new understanding of TracIN-Ideal as an approximation to In-Run Data Shapley. Both works face the technical challenge of requiring per-sample gradient computations during single training run. PPrtth et al. (2020) proposes TracIN-CP, which mitigates the computational burden by examining only a subset of intermediate checkpoints during training. At each checkpoint, the individual gradients for the entire training set computed, rather than for a sampled batch, under the assumption that each training example is visited exactly once between checkpoints. A recent work (Xia al., 2024) leverages TracIN-CP, an approximation algorithm for TracIN-Ideal, for instruction-folln following data selection. This approach, however, may deviate significantly from the original TracIN- with the final valuation results heavily dependent on the selected checkpoints. Furthermore, Pruthi et al. (2200's 's implementation is limited to the parameters of the last linear layer due to memory constraints, potentially biasing the measurement of data contribution. For instance, Yeh al. (2022) suggests that the last layer of neural network might exhibit a strong "cancellation effect," where the data influence of different examples have large, contradictory magnitudes. Additionally, Schioppa (2024) demonstrates that selecting different layers can distort data attribution scores. contrast, this work introduces the "ghost dot- dot-product" technique to efficiently compute the first-order Ru-Run Data Shapley (i.e., TracIN-Idee Ideal)) directly and accurately, without additional approximations.
16

---

Published as a conference paper at ICLR 2025
B ADDITIONAL DISCUSSION
In this section, we provide additional discussion about In-Run Data Shapley as well as its comparison with Retraining- based Data Shapley. Figure gives more detailed overview of our algorithm, and Figure pl a visualized comparison between Retraining- baasid and In-Run Data Shapley.
8
84
Iterative SGD Training Processes
Decompose
8
0,
Ocos
Oco
Gradient update on Bg
Gradient update on B,
Gradlent update on B:11
8, Σ 7)(9..4)
6ee - 6 WW y ve(6,
Pou fer Rest
ve(6
Compute Shapley "local utility function"
Computo Data Shapley for a word. "local utility funetion" piu
Compute Data Shapley for e Bost w.s.t "local utility function" yitea
(.(1100) if a olae
4,(0 z a else
d2(W++ if Booss eloe
Overall d₂ LeseR, Eesc,,0((U0t)
Figure 4: The core idea and algorithm overview of In-Run Data Shapley. Rather than evaluating data contribution across the entire training process (top), we decompose it into individual gradient update steps (bottom). For each iteration we compute the Shapley value o= (U(()) with respect to "local utility function" ((t)) that measures how the batch B, contributes to reducing validation loss. A data point's 's final contribution score is the sum of its Shapley values across all iterations where it appears: Φ₂ = Enggg, d2 (U()). This decomposition approach maintains the Shapley value properties through the linearity axiom while making computation tractable.
Mini-batch
1-Step Updatto
yel bottch's Data Shapley
2dd Mini-batch
Seb-
aumpph
gi batch's Datu Shapley
Training cuntinues
Points' Shapley
Retraining based Data Shapley
In-Run Data Shapley (this work)
Modal (Cheekpoint)
Training Data
Validation Data
Shupky Calculator
Figure 5: Comparison between Retraining- based and In-Run Data Shapley. Retraining-based Data Shapley requires training a model from scratch on all possible subsets of the full training set, which computationally inefficient and raises concerns about interpretability and stability. In contrast, In- Data Shapley acts as "contribution accountant", efficiently tracking and attributing data value scores to each training example across gradient update steps during a single training run.
17

---

Published as a conference paper at ICLR 2025
B.1 WHEN IS IN-RUN DATA SHAPLEY DESIRABLE FOR DATA ATTRIBUTION?
While Retraining-basse based Data Shapley has been widely adopted in the literature, it suffers from several critical issues that limit its practicality and effectiveness. In this section, we discuss these problems from four key aspects: computational efficiency, alignment with the purpose of data valuation, stability of the valuation results, and the choice of training hyperparameters.
(1) Computational burden. Retraining- Data Shapley calculation is often computationally prohibitive, as it requires retraining the model on every possible subset of the original dataset, leading to a computational complexity that grows exponentially with the size of the dataset. Despite the development of various Monte Carlo-based approximation algorithms (Jia et al., 2019b; lllés &
Kerényi 2019 Okhrati & Lipani| [222 BBuggess & Chapman, 2021; Mitchell et al. 2022 Lin et al.
2022] Wang & Jia 2023b; Li & Yu, 2023] Covert et al., 2024). these methods still necessitate extensive computational resources due to repeated model retraining, which is clearly impractical for modern-sized ML models. Another line of work attempts to use efficient proxy learning algorithmss such K K-ncarest neighbors (KNN) (Jia et al., 2019a; Wang & Jial 2023c Wang et al.) 2023 2024c Yang et al., 2024), to accelerate Data Shapley computation. However, it remains unclear how closely these cheaper proxy models approximate the original learning algorithm, and it is also uncertain how to interpret the derived Data Shapley scores in this context.
(2) Retraining- based Data Shapley is unable to assess data contribution specific model. Crucially, Retraining- based Data Shapley is not designed to value data contribution towards a specific model. It attempts to quantify the average contribution of each training data point to models trained on different subsets of the data, rather than its contribution to the specific model trained on the full dataset. While one might interpret the former as an approximation of the latter, these two quantities can be quite different in practice, especially when the learning algorithm is randomized and sensitive to factors like random initialization and the order of the data points during training. More importantly, in most real-life scenarios, the primary interest lies in understanding the contribution of each data point to the specific model being trained and deployed.
(3) Retraining- based Data Shapley produces unstable valuation results for stochastic training algorithms. Furthermore, when the training algorithm involves randomness, such as in the case of SGD with random mini-batch selection, the corresponding utility function becomes randomized. Prior work (Wang& & Jia 2023a) suggests that this randomness can introduce substantial noise into the estimated Shapley values, rendering them unreliable and unstable. This instability poses significant challenges for interpreting and using the resulting data valuations, as the scores may vary considerably across different runs of the algorithm, even the same dataset. Consequently, this limits the practical applicability of Retraining- based Data Shapley when working with stochastic training algorithms, which are prevalent in modern machine learning. We note that similar vulnerabilities learning stochasticity have been observed for LOO-based data influence scores (c.g., influence function (Koh
Liang 2017)) in several works (Basu et al. 2021 Søgaard et al. 2021 Nguyen et al., 2023).
(4) Training hy hyperparameter choices in Retraining-based Data Shapley are unclear. In machine learning, training hyperparameters (e.g., learning rate and batch size) typically need to be adjusted based on the size of the training dataset. This creates a fundamental ambiguity when computing Data Shapley values: when evaluating the utility USS) for different data subsets S, should we use the same hyperparameters as those optimized for the full dataset, or should we adjust them based on the subset size? This choice can significantly impact the calculated values.
In-Run Data Shapley addresses all these issues, making it more desirable for specific scenarios. Firstly, it is computationally efficient as it computes data values during the training run, avoiding the need for multiple retraining iterations. This makes it feasible for modern large-scale ML models. Secondly, it aligns better with the purpose of data valuation by assessing the contribution of each data point to the specific model being trained, providing more relevant insights for real-world applications. Lastly, In-Run Data Shapley offers deterministic valuation results even with stochastic training algorithms, as incorporates the specific sequence and randomness of the training process into the utility function. Therefore. for scenarios where computational efficiency, model-specific contributions, and result stability are critical, nn-Run Data Shapley is a more suitable choice.
18

---

Published as a conference paper at ICLR 2025
Remark 4 (In-run Data Shapley is model-specific data attribution technique.). In the original Data Shapley literature, US) rypically defines utility as the final performance (e.g., accuracy, loss) of a model trained on a data subset S. However, things become more complicated in the context of deep learning. A specific deep learning training run is an iterative process. Defining utility USS) for a particular run makes it a sequence function rather than the pure set function required by the standard Shapley value framework. Extending Shapley axioms to sequence functions is not straightforward. Previous works often define US) as "expected model utility across all possible training runs" to circumvent this conceptual issue. In this work, we initiate the study of model -seecf-peeifiic data attribution, which is crucial for applications like model diagnosis and behavior interpretation where we focus on specific training run rather thun expected ulility across all possible runs.
Data attribution should consider specific application scenario. From a broader perspective, the "optimal data attribution" notion heavily depends on the intended application. In the literature, data attribution techniques are being used for various purposes such as data quality assessment, data valuation, and interpreting model predictions. For data quality assessment, we require "algorithm- level data attribution" that measures a data point's 's general inftuence on the learning algorithm. independent of specific training random seeds. On the other hand, when interpreting model decisions, we need model-specific data attribution focused on the particular checkpoint we train. Systematically mapping which data attribution approaches best suit specific application scenarios remains an important direction for future research.
B.2 WHEN IS RETRAINING-BASED DATA SHAPLEY DESIRABLE FOR DATA ATTRIBUTION?
Retraining-based Data Shapley is still desirable in several scenarios. Firstly, it is more general and applicable to all learning algorithms, whereas In-Run Data Shapley is only applicable iterative training algorithms. Secondly, retraining- eeraainigg-based Shapley is useful when the goal is to understand the contribution of data points to the general learning process rather than to a specific model. Thirdly, because Retraining- Data Shapley does not require modifying the internal code of the training algorithm, its estimation algorithm, typically Monte Carlo-based, is straightforward and clean to implement.
B.3 POTENTIAL EXTENSIONS OF IN-RUN DATA SHAPLEY TO OTHER DOMAINS
While this work focuses on data attribution for SGD-trained machine learning models, we believe the core idea of In-Run Data can potentially be extended to other contexts and applications. Here, we discuss some directions.
contribution analysis into per-iteration assessments-
Data attribution for iterative learning algorithms that do not use gradient descent. Our frame- work could potentially extend to iterative learning algorithms that don't 't use gradient descent, such as k-means clustering or decision tree learning. Though these algorithms update models differently, they still proceed iteratively (e.g., k-means alternates between assignment and update steps; decision trees are built through recursive partitioning). For such algorithms, we could analyze how each data point influences these discrete update steps and aggregate these influences across iterations, similar to our approach with gradient- based training.
Hyperparameter importance. The framework could potentially be adapted evaluate hyperparam- eter contributions during training. One possibility is to set a "baseline" hyperparameter value and assess how choosing different value impacts each training iteration compared to this baseline. For instance, when evaluating learning rate choices, we could measure how using specific learning rate value affects model updates compared to using a baseline learning rate. For differentiable hyperpa- rameters, we could leverage Taylor expansion to approximate this difference; for non-differentiabbl ones, zero-order methods could potentially be used. By accumulating these contributions across training iterations, training runs. At a high level, this view unifies our treatment of training data and hyperparameters both can be seen as choices that influence each training iteration, where we aim quantify their impact against baseline scenarios. While technical challenges remain in adapting our method, this direction presents interesting opportunity for future research.
could understand hyperparameter impact without requiring multiple complete
Feature attribution (e.g., context-attribution for language models). Another possible extension we envision is feature attribution for machine learning models. Feature attribution aims understanding
19

---

Published as a conference paper at ICLR 2025
how each part of the input (like individual words in sentence pixels in image) influences model's final prediction. When model makes prediction, the input features are processed through multiple layers, with each layer transforming the information before passing to the next layer. Feature attribution aims to track how this information flows and transforms through the network determine each input feature's contribution to the final output. We envision unified theoretical framework connecting training data attribution and feature attribution, drawing parallels between how information flows during training (through gradient updates) and during prediction (through layer operations). This could lead to more efficient methods for explaining model behavior, particularly for complex architectures like transformers.
20

---

Published as a conference paper at ICLR 2025
C
MISSING PROOFS
Theorem 5 (Restate of Theorem 3). In-Run Data Shapley considering the first-order approximation has closed-form
(U) Φ (U(1)
where
de (U)) -1/ Ve(w,, z (vvll) Ve(w,, 2), == O
Proof. For notation simplicity, let xz == Ve(w,, 2z). Given the utility function
(5) =-1 Σ
Vilwi, (vaa))) Ve(we, 2z);
2y
the marginal contribution of for any S C B \ i
6 U (5) = n/ Ve(u,, (val)) Vl(wE,2)
Plugging in the expression the Shapley value's 's definition immediately gives the result.
21

---

Published as a conference paper at ICLR 2025
Theorem 6 (Restate of Theorem 4 tion has closed-form
In-Run Data Shapley considering the second-order approxima-
T-1
Φx (U)
2
Φ
(T()
(1)
2
1
0x
(U(1))
(6)
t=0
where
Ø (U(1))
+ 2
1
(u())
= 7 V flwee 2 vvaal)) Ve(we, 2) +
M
v Velwu, 2) { (mall)
Vilwer Eg)
2
infiuence of on the loss of ((va1)
interaction between and other training points
(7)
for any 1- 0 , T 1.
Proof. We show that
Φ (1//)) = ni V H)H,
(2 (ma))
ve(wer2)) F
For notation simplicity, let æ, == Ve(we, 2z), and ;= Ve(w,, 2). Furthermore, let ne = |B, the batch size in 1-th iteration. For any 5 _ B, 2, the marginal contribution of
-(0 = n H
Σ 25ES
H
(ratt)
Øj
Plug the above expression into the Shapley value's formula, we have
(u()) =
nr
f
(mll))
The
Σ
i iTH iTH (afaaa))
Σ 2j
k
1=1
SCB, (=),
IS -h-1
ZyES
i H
ball)
x + H
T4e
E
Σ 2j
k
k=
181
FEES
2 + - H (val))
2
R1
f4
-
-1
f4 2
Σ 13 (GEBA\(=)
n4
h
5
(=(v)))
2
Rs
k
Σ x3 3j E)B((())
n4
T4
33/ ))
3 H
(2
55 .. H (v())))
Σ
Σ 2
SEB
22

---

Published as a conference paper at ICLR 2025
D TECHNICAL DETAILS
Notation review. Consider linear layer = aW, where W E Rdixda xd2 is the weight matrix, = (a(), (a()).... ( is the mini-batch input, and s (s(1), s B()))T is the output (i.e., the pre- de-activation tensor). For son-eetutntial data, a E IR Bxdi,
Bxds, For sequential data with sequence length T', E _Bxd xT , E BxdxxT Let g(0) l(w, 2,) denote the current model's
individual loss on 2₁. For notation convenience, we denote (()) = 00
D.1 GHOST DOT-PRODUCT
By applying the chain rule, we can express the gradient of an individual loss g(0) f(w,, with respect to W as
a aeto Os(()
Oe(3) aw ag(i) aw Og(1) Og(1)
ae
(*)
( =a b
(8)
where 8: := Σ}= gb) is the aggregated loss. Note that the individual's output gradient b Ogli) is readily available during the backpropagation pass.
0g(()
0s(()
ae
Suppose we are interested in computing the gradient dot-product ow points 21, 22 in the same batch in the backpropagation. We first discuss the case for non-sequential data and then extend it to sequential data.
ew between two data
Non-sequential data. For non-sequential data, we have each ( E Rgdix1 and (0) E 1xdds By have
( ow
eE(2)
a (1)
(1)
a
((b1)
( ((0)))
((a")) a2))
OW
Hence, we can compute the dot-product between
aw without actually instantiating the We can take the dot products between (bn) (b (2) and (a()) (2)),
and ar(2)
UW
gradient vector
ag(a) ae(a)
OW
and then multiply the results together. Moreover, all of the materials (1)) a (1) ((2) that are required for computation are all already available in one backpropagation. Hence, with a single backpropagation, we can efficiently compute the gradient dot-product between every pair of data points within the batch.
Sequential data. For sequential data, we have each a Rd XT and ((0) E Txds, By have
ae(1)
0E(2)
d..dz
(2) 3 b()) ① (2)
(2)
b())
(2 (al)&b) Eb2))
a
Ow
ow
j.k
j.k
d dd
(2)
(2)
a
a
j=
di d2
T
I
Σ
Σ
2
=
je
tk
a
jz
tk
A=A=1
T.T
(1) (2)
(2)
akc akta
f,,6==
T,T Σ
(1) (2)
( ( b3
a 2/1/2
f=,6=1
((b.) (b(2)) (a T
a (2)
23

---

Published as a conference paper at ICLR 2025
Hence, comparing with directly computing per-sample gradients, if 27 did2, it is more memory- efficient to first multiply the matrices of (D()) ( (b())) and (a())T a (2) then take the inner product
between the two 7 x T matrices. 27 2 d1d2, then we can first take the outer products a b(1) and (2) @ (2) then take their inner product. In either case, we only need a single backpropagation to compute the gradient dot product between every pair of data points within the batch, similar to the case of non-sequential data.
Remark 5 (Applications of "Ghost" Technique Beyond Data Attribution). The techniques developed in this work for efficiently computing gradient dot products may be of independent interest, this operation arises in various machine learning algorithms and applications beyond data attribution. For instance, the "ghost dot-product" technique can be used in calculating the cosine similarity between individual gradients (logether with the "ghost clipping" " technique), which is frequently heing employed analyze training dynamics (Fort & Ganguli (019) and detect adversarial attacks Dhaliwal & Shintre 2018). Additionally, gradient similarity is used in active learning to select the most informative data points for labeling (Ash et al. 2019) and in multitask learning balance the contributions of different tasks Yu et al. 2020).
24

---

Published as a conference paper at ICLR 2025
D.2 GHOST HAADEENT-HESSIANGGAADDD PRODUCT
We denote L as the number of layers in a neural network, and we denote W., i = .,, L as the weight parameters of each layer. We denote H (e(v as the Hessian matrix of g(z ((a(val)) on layer W
Suppose we are interested in computing the gradient dot product (e(0 (2(0)) (2(2)
L.
0p(1)
(8lt)p(a(mn)
02(2)
Σ
aw.ow,
OW;
aw,
s-=1
L.L
( ((())
Σ
x b(u))
ow,ow,
(a. & b)²)
We first look at the Hessian-vector product.
((2)g(=(mm)) aw,aw, (a)") @ bj (2) a del=(ral)
ow, (a)
(2) 2 b,2))
aw,
[ (a(
ow;
a
(2) (b) |
aw;
2
[c,d,]
aw;
ad
dc,
C3 ow,
d OW.
where we denote cy ag (val)))
(2) and d
b( (val) (2)
We the second backpropagation on the gradient dot product Vela Vg (2p)= = c,d,. Note
de, that here a (2) b (2) are constant vectors. For aw. have the similar decomposition
dc;
( (2)
oW:
aW.
(2
(val)) (2)
a (val))
ss (z(val))
a
For o.. the derivative is more complicated the b/ (2(va))
2d,
also depends the output from deeper
layers. When j 2 i, we still have
ad aw:
( (20) @ a (o(n
as! (((a))
25

---

Published as a conference paper at ICLR 2025
When < i, we have
ad,
bb.
(2
bj
(2)
ow;
aw,
(2)
aw:
(e(abval)
Os
(vul))
Oa
(elvall)
(2(vatt)
(2)
ow,
oa, (2(val)
0s (sivail)
)e(=(ma))
aa (2(v)))
da
W;
(2)
ow;
0s
0
Da
(anvae)
Ba
(invas)
W:
(inva)))
as
dal
Oa
(2)
as
(2) (vaut))
1- (ma))))))
2 a
by
isp
as
Overall,
0d,
a
(b) (2lta))) (2))
ow:
aw;
(2)
x (((m)))
j21
ouf (xfo(val))
b ( (2)
e a (لmn
+ bi (ouwary
j<i
Hence, we have
(val))
V
F.F.
Σ
(1))
C ad, aa:
+ d, de,
aw,
1-=1
L.L
L.L
Daa (f(r))))) Ös (c
Σ
(1)
(1)
Ös! (aaa (c,d,) & a (o(re))
0
aa
(1)
b (a
For the first part, we have
b(u)
Σ c,d
((()))))
(a
as! (ottn
@ a
Σ
(1) (
b (1)
i
Σ c,d,
a a:
Og
i=1
E/e c,d,) ) i i= 1,..., L is readily available from the second backpropagation.
where
26

---

Published as a conference paper at ICLR 2025
For the second part, we have
L.L
)
b
as (sstttarr b!:))
1>1
L.L
(1)
oa,
(z(mali)
(2)
(b: D (cfma))
a
(=(vi))
Üss
(1) 0a (v
The remaining question is how to compute f(i,j :- a,
(2)
Observe that
Ouf cgfatvati)
(1) 0a. (2(vul))
(2(vel))
0s (v(al)))
Os (2(2))))
(2(vn))
( Oa,
Da
b
s+1
j+1
Dj
(2)
Os (2(vat)
Os , (=(mat))
da (=(va)))
Oa (2(val)
Os
(stvally
j+1
a; Da! (2 (mal)
(=(val))
W Wi-1...
j+1
by (2)
Os! (201))
0s (((aa)
(val)) On
(= (a(vat)
Moreover,
Caaly easy to compute as the only operation between a j+1
and of
is an
0s
(a (val)) (va))) will
element-wise activation function. For example, if the activation function is ReLU, then
(val))
simply be matrix that contains elements in {0, 1), depending on the sign of the position in
To efficiently compute f(i,j) for all >>>li>>> j. for each
I, we can maintain the quantity
g(i.j) = Oa (va)))
aa (va)))
W W j+1 Os (2(val) by
(2)
as (2(val)
8a (v(l)))
and we have f(i,j) = a; j). To compute f(i+ 1,j,, note that ( g(i+1,1))
a (nn)) W.g(i,)).
Moreover, we note that in our scenario, we are interested in the gradient dot-product
Σ v
is fixed for any training point corre- sponds to ((1), Therefore, the second backpropagation only needs to be taken once the gradient vector on the right-hand side is always fixed.
where the Hessian-vect vector product ((= (vab))
(m(m)
m==
D.3 MERGING BATCH SELECTION AND GRADIENT UPDATE IN ONE BACKPROPAGATION
By utilizing the ghost Dot-Product technique developed in this paper, we can calculate or approximate all importance scores and correction terms in a single backpropagation pass, without materializing any model-sized vectors. To compute the gradient dot-product between each training point 2; E B, and the validation data (val)) we propose including =\val) in the backpropagation along with the training batch. Specifically, we can backpropagate with respect to (E.,e, (()) + ((())) After computing the In-Run Data Shapley scores for the current iteration, it may seem necessary to backpropagate with respect E,eB, g(x) to compute the gradient for the parameter update. However, this is not
ae(s) required. We can simply reuse the output gradient 2x00 from the original backpropagation and aggregate the gradients for all selected data points. This technique is adapted from the "book-keephe beekkkkeeing trick" proposed in Bu et al. (2023).
27

---

Published as a conference paper at ICLR 2025
E EVALUATION
E. DATA PREPROCESSING & TRAINING SETTINGS & IMPLEMENTATION DETAILS
We conduct the pretraining experiment using the GPT2 (124M) model (Radford et al. 2019) and Pythia-410M (Biderman et al. 2023) on the Pile dataset. Our codebase is adapted from https //github. com/ karpathy CaaanoPP/ttree
master) We first tokenize and split the entire dataset into chunks, and store them in the disk in numpy array format, which significantly speeds up data loading. The maximum sequence length set to 1024. The learning rate set at maximum of 0.0006, with minimum learning rate of 0.00006. We use Adam as the optimizer with a weight decay of 0.1, and beta values set 0.9 and 0.95. Gradients are clipped at a maximum value of 1.0 to maintain stability during training. The batch size is set to 16, with a learning rate warmup of 2000 iterations. Due the shortage computation resources, we stop the training at 500,000 iterations.
Methods for comparison. In Section 5 we compare In-Run Data Shapley with the influence function (Koh & Liang 2017). which approximates the change in the model's loss on the test example when the training example is removed from the training set (i.e., the leave-one-out score). BM25 (Robertson) al. 2009) featurizes examples by their word frequency statistics to rank the training instances. We measure the similarity between the query examples and the training corpus, using the similarity scores as the value scores for the training corpus. we set the hyperparameters to k = 1.5, = 0.75, which commonly used values that balance the term frequency scaling and document length normalization.
Remark 6. We do compare with TRAK Park al., 2023 generally requires aggregating the estimator across multiple trained models for reasonable performance, and the original codebase not applicable to Huggingface models. In their original paper, the largest scale experiment is fine-tuming BERT-base.
E.2 ADDITIONAL FIDELITY EVALUATION
E.2.1 APPROXIMATION ERROR FOR IN-RUN DATA SHAPLEY WITH LARGER LEARNING RATES
To further investigate the impact of learning rate on the approximation quality of In-Run Data Shapley, we conducted additional experiments to Section 5.2 with larger learning rates of 6 x 10-4 and 5 x 10-3, where the latter being significantly higher than typical learning rates used in foundation model pretraining. Figure 6 shows the comparison between Monte Carlo-estimated In-Run Data Shapley and our approximations with learning rate 7 6 10 Both first- and second-orde approximations achieve remarkably high accuracy with RMSE = 0.0012 and Spearman correlation 0.99. Even with extremely large learning rate of r 5 10-3 (Figure 7}.
approximations
maintain reasonable accuracy with RMSE x 0.0017 and Spearman correlation = 0.79. The strong rank correlation, particularly learning rates typical for model pretraining (7 S 10 10-3), suggests that our approximations effectively preserve the relative importance of training data points. This property crucial for practical applications such as identifying low- low-quality data or selecting valuable training examples, where relative rankings are more important than absolute values.
First-orderr Agoroximation (RMSE=0.00122 SP=0.89)
Second-order Approximation (RMSF-o -0.0012, SP=0.99)
Second order Ins-tum Mtn Deta Shaple
First order In Dun. Data Shapley
0.004
0.001
0.002
0.002
0.000
-0.002
-0.002
-0.004
-0.004
-0.004-0
002 0.000 0.002 0.004 Moale Carlo Estimation
-0.004-0
00.00--000000000
0.2.00200000000
0.002 0.004
Moute Carlo Estimetion
(a)
(b)
Figure 6: Comparison between the Monte Carlo-estimated In-Run Data Shapley and First/Second- order In-Run Data Shapley (learning rate 6 x 10 10-4).
28

---

Published as a conference paper at ICLR 2025
Second onder In-Ruu Dala Shuples Somoleooooon
First-arder Approximation (RMSE-0.0017) SP-0.79)
Sgrond-nneer Approximation (RMSE-00000 SP-0.79)
mist-artoor Tn-Rum Dataa Shapley
0.004
0.003
0.003
0,002
0.001
0.001
0.000
-0.001
-0.001
-0.002
00.00
-0.003
-0.002
0.000
0.002 0.004
-0.002
0.000
0.002
0.004
(a)
Moste Carlo Estimetion
(b)
Monte Carlo Estimation
Figure 7: Comparison between the Monte Carlo-estimated In-Run Data Shapley and First/Second- order In- In-Run Data Shapley (learning rate 5 x 10 10-3).
E.2.2 APPROXIMATION ERROR FOR UTILITY FUNCTION
In this experiment, we empirically investigate the errors of the first- and second-order approximations (1()) on GPT2, proposed in Section 4.1 The correlations shown in Figure 8 As we can see, even the first-order approximation achieves a high approximation accuracy, and the inclusion of the second-order interaction term does not provide notable improvement in accuracy.
Firsi-orterr Approximation
Second order Approximation Spearman correlation: 0.9665
Pearson correlation: 0.9421
0,0100
0.0100
0.0075
0.0075
0.0050
0.0050
True Utility
0.0025
True Utility
0.0025
0.0000
0.0000
-0.0025
0.0025
-0.0050
-0.0050
-0.0075
0.0075
0.0100
0.0100
0.0100
0.010
-0.005 0.000
0.005
0.010
0.010
-0.005
0.000 0.005 0,010
(a)
Predicted Utility
(b)
Predicted Utility
(a) We show the correlation between the ground-truth model validation loss change in f(we, ((va))) and the first-order Taylor approximation. (b) We show the correlation between (S; 2 (val)) and the second-order approximation.
Figure 8:
one gradient update iteration (S; (vva)) == (())+1(S),
Remark 7 (Difficulty in Extending to Adam). The techniques developed in this section specifically tailored for SGD. is not directly extendable to other popular optimizers like Adam due to their normalization terms. Nonetheless, using SGD) as a proxy for Adam allows for efficient data attribution, which is the approach we adopted in practice and has proved to be effective in our experiment. This provides practical and effective solution for the current scope of our work. Extending these techniques to support Adam and similar optimizers remains an exciting direction for future research.
E.3 DETAILS ABOUT SECTION
In this experiment, we first conduct one training run for 20,000 iterations. Among all the corpus that has been used in the training, we compute their In-Run Data Shapley and filter out all corpus among this subset that has negative contributions negative valued corpus, train another model on the remaining dataset for 10,000 iterations with all hyperparameters staying the same.
model training. After filtering out the 16%
Despite the Pile dataset undergoing multiple layers of data curation (Gao al. 2020 still find a significant amount of poor-quality corpus through In-Run Data Shapley. For example, we discovered a large amount of corpora in the PubMed Central domain that simply empty spaces. Figure D provides two examples of the corpus that received the lowest In- In-Run Data Shapley scores. Additionally, found several corpora with negative values that appear normal, which is likely due to
29

---

Published as a conference paper at ICLR 2025
distribution shift with the validation corpus. Crafting representative validation set is important direction for future work.
Corpus with meaningless numbers
2.3.3.1.333333322200000
0.0.0.000.000000000000.0..
3,3, 3,3.3,3,33333333333333
0.0.00000000000000000.2.2
1.0.0.00000000000002222.
3,3.3.3,3,,,,2233333 3.3.3.33311333333333 0.0.0.0..........0..II..
0.0.0.000.00000000.3.33.
Figure 9: Examples of low-quality corpus in Pile found by In-Run Data Shapley. Left: a corpus with meaningless numbers. Right: corpus with meaningless symbols (likely due to errors from web crawling.)
E.3.1 DATA SELECTION PERFORMANCE ON PYTHIA 410M
Figure 10 shows a performance comparison between the original training run and the model trained on the cleaned subsets on Pythia-410N 10M. Similar to results on GPT2, we can see that removing lower-quality data leads significantly faster drop in test loss compared to the original training run, highlighting the effectiveness In-Run Data Shapley across different architectures.
Test Loss (Pythia 410M)
Original Training Run
Io-Kun Data Shaplay (1st order)
Io-Ran Data Shapley (2nd order)
Influenen Function
Losss
5000
10000 15000 20000
25000
Iterations
Figure 10: Test loss comparison between the original training run and model trained on the cleaned subset according to different data attribution techniques for Pythia-410M.
E.4 ADDITIONAL RESULTS FOR SECTION 3
In addition to Figure 3 we also plot the average value scores of corpora from each domain, averaged across corpora within the same domain that has been used in gradient updates, over the first 10,000 gradient update iterations. As training progresses, the magnitude of data value scores converges towards zero, which aligns with the diminishing returns property of neural network training. This indicates that the contribution of data points depends the order in which they used during training. an aspect that Retraining- baased Data Shapley methods cannot capture. Data points introduced in later stages of training contribute less to model performance improvement.
30

---

Published as a conference paper at ICLR 2025
Average Topic Values Change Over Steps
0.6
0.5
In Run Data Shapley Values
0.4
0.3
0.2
0.0
-0.1
2000
4000
6000
8000
10000
Number of Steps
Figure 11: The change of average contribution for data points from each domain to corpus of math text (same setting as Figure 3)
E.5 DETAILS ABOUT SECTION
In Section 5.3.3 we use GPT-4 to generate varying levels of paraphrased versions of an original corpus from the training set, categorized as "Partial exactly the same," "Paraphrase," "Significant paraphrase," and "Similar topic." For "Partial exactly the same," the corpus is used as the answer in creative writing instruction-anse answer pair. The specific prompt for prompting GPT-4 with examples
of the full dialogue shown in Figure 13
We generate 3 sets of corpus groups, and the experiment results are taken as the average. Figure 12 shows the distribution of calculated
14
15
In-Run Data Shapley. As we can see, most corpora's values are around 0, but certain corpora have significantly higher values than the other, which means their contributions are higher for the target validation corpus.
10a
Distribution of In-Run Data Shapley Scores (1st order)
10a
Distribution of In-Run Data Shapley Scores (2nd order)
Value of Original Corpus: 0.00123
Value of Original Corpus: 0.00121
104
104
Density (log scale)
Density (log scale)
10a
10a
10
10a
10a
10
10a
10a
-0,0005
0.0000
0.0005
0,0010
0.0005
0.0000
0.0005
0,0010
0.0015
(a)
Value Score (normalized by total loss reduction)
(b)
Value Score (normalized by total loss reduction)
Figure 12: The distribution of calculated In Run Data Shapley values.
31

---

Published as a conference paper at ICLR 2025
Dialogue GPT4 generating corpus vary varying levek simillrity (Original corpus from Wikipedia))
(Sienestte Furrlat
somrr) <tiimans Instrctiion: [INSUR]]
Amsur 2012. Radhi monuited new 'muricuns" for 04G, who were selected from among the suudents Abalemi Seni Radays can Wirien Kehangeann () The now line-sp orrsies Resah drumnleewiing Jum postion), Mahanied
vocals octginal drummer
guatzz since 2005; gulturbacking vocaist, liner Khasbuliah rayybourdbaakit vocaso.
new Si
they
asies, Friday I'm Fow Progaeth Mads, Bonch lunah Ayer Amber"
soundrack and sour
released and clso full studio altem
coming aforwards.
Please help dilling [INSERT] the insruction for creative wetting usk.
<CPT4> Writc short sirey abou. Rulhi and his hand (AG ss they socruit new munher and bikrdd inalismal moie with diumatiiv sounds Deseribe their encaiiee chullenges and susocess lnallng their new releases.
[Getuvate "aaashrsse" <Humaro Could you paraphruse pangrruph stst from 2012,
nommital ..!?
<UPTT In 2012, Rachi assembled new 'musicians' for OMG, choosing from staderts the Altademi Seni Hudaya dan Worson Kehurgesmn The updaed linr inclides Qu Rarali drams and bocking vocals, souniig arisnal donz Mahumal Naaan cinnc 2005),
has
voculs. describes and providing becking "almmttff Khashulla keybouds and allemmativ they quiclly
scries "Frsday Upooming include singles Pongasth Mods." "UN Bowah Toonah Ayer" "Ambei,"
viandleskk
studio
in /Gletorane SSandioun purawhnase"? HHumago Could you make It less look like the original paragraph? Feel
<GPT4> la 2012, Rudhi scleste new sut of musiciim from the studemos Akademi Seri Budaya dan Warisan Kchangaan iois DAG, The band's updated compostion inclades Qi Razali, who retunedd his miggnall rale un drams and backing werass, alongede Mehaneal Nitam who has been on guiar eince 2015 Noori Zahihi or bass with backing wwstss and Lener Kloabulbá plaing the keyiveensi and adding backing vocils. Radhi his tormed the band's evolved musical expeesion os adinatit." a blezd of traiticnal and alternative sounds. Fnlowing their cometaakk, their fistt major projct was producing the soundrack and them:
aaies Friday I'm Love" hand aleo plamiing laanc several singks. each Pengasih Muds." "Di Buwsh Tansh Ayer," and "Amboi, and working lowards new full-lnugh album.
opur) <Humans
PREVIOUS
CATON-NNNSS PAIR)
ahove is an cample of intradiinnneeerr puir cocaiie whiing. Could you write an instmetiionnnneeer pair repeddng simtke wot compleiely inclovnt topic?
with vory net Assver. clauicully explore josr to dimnly in clib dowstwwn where the
detailing
musical Cariosity led sle spenoched the bad ofher their vielin in hand. They invite her the followngg week. As the mepped onto the stape. her tradiiionl technigues blended mespectedly with the saxophomin's smooth runs and the dnimmer's mythmi beots, The tusson or clasocal precicon and juzz sporunclls creued a dhilling sew sound. Eleas found heself be seinegueaaedd her victnn sinping with a needom she had sever before experiened.
performaccss something thythms and melisies experontd Hostsally.
them
sassion
Figure 13: Our dialogue with GPT4 for generating corpus of varying levels of similarity for the original corpus from Wikipedia.
32

---

Published as a conference paper at ICLR 2025
Example Dialogue
generating corpus of varying levels similarity (Orgginal
curpos from CNN)
sumrr)
[INSSSC]]
Answe: The moming after Obana's a wis. The New York Times declared Racial Barter Falls Decighe
Vistry:" Augolox Timas socnall lhe dhe lime tuman leater, legsly white
black man
winnessing panmount
black commetiaror openly west clestion night, prestem:
conceding oppenent, that
pointe grzatrens
promise lapacy lealed
possiblllty that
Pizase help filling [NSERT] the indruction for creative wriinng taak.
<CaP Weite reflective essr the significance of Barack Obama's 2008 presidential election victory. tecusing on impact on roce relation in the United States and the emerional resprnses eleneed from differeut communiees.
*n (Genvmir "Pamphmse" cHummn Coold you porapleane the paragraph!
moming
victory.
that proctaimed
Victory." has
black hatory, black presiders.
prelonizatly
black
nigln, John Me his conezition spoach. highlighrol the fu sillmmn Americns promier through pusibillty that wannle of America nadial listory
wineeuin election
upporan's wis. Dhams's triuggh were healing the very least becoming less acune.
in /Glenvnte "Sannforr pammlrras" "? Human Could you muke less look like the original pangraah? Fool fioe mabily
Di The mocting after Utuma's victary headlines capoured the humeeii moment The New York Times innounced "Racal Burner Fills in Decieve Victery. and The Los Angeles Times hightigheed that the fins dime, a prolominaall white raiins has chosc back mas as leale:" Ou clocton right, many blak. commenuner shel leas of joy, moved the nilestore of clectigg the fast Rack presieet Ever Sea. John zin. his cononsioo sposch. adkne lodged the malization of the Americn premae opponent's snsszce Obama's sigulaa a potenial healing of America's maiil wouns leae step towen! easing sheir pain.
"Samia upic? <Hamass (COPY PREVIOUS INSTRUCTION ANSWER
abowe is an example of intradiin--sseer pair coeaiie wnitng Could you write on intmectionannswe pair regurding los
not compleilly inclevast topic!
<CPT4s Instuction:
relective cocr significaaa Sqreme Counts
the emotional maninge naiimniikk ase Amswrr The
legalize
LGBTQ+ rights United
elictedd defferent commintees.
landmark docision. The New York Times declund Law. The Washington Pus highlighted. "Love Wits: Suprzme Court Attrams Same Sex Maniaag Natiozwide Mazy in the LGBTO- communiy celebrated with sears of fodding validaied and mangiioall Fiece uime of the jedices who duscatzd knowwllgggl the profoaadl impaci the dasiiis us America waidty. The roling repraentcd majee milustin in the fight for LCBTQQ+ rigtss, symbolizing a stift tward greater acceptonce and equaiity
"Equal Dignity the Eyes thee the
Figure 14: Our dialogue with GPT4 for generating corpus of varying levels of similarity for the original corpus from CNN news.
33

---

Published as a conference paper at ICLR 2025
Exumple Dialogue with GPT4 generating curpux of varying levels similarity (Original corpus from prinecton.edaa)
[Gieterate 'Furtlal
sime
Instrctioon [INSERT]
Atewe: The pecczsa was parchseal by the Geman chumical cumpany BASF (a and far dye wapolier). which ssigted Carl Bloch the dimolt task of scaling up Haber's tublepp machine industrall levell production fisher Bloch wer koe monded Notel pross 191 1911 muperrivily for their work overcoming chenical enginesiing problemi posed the use large scale, continouus flow. presuse
help filling (NSFFTT
for
writigg
Bosch's ettons scale Haber's machine
challenges he faced the he found. and the impact his work sociey, Itclude listoriaal contest and ansodones.
indusral
Highight sctemthc and
*n (Gennvir Pampllmsr" cHuumano Coold you perpleaae the paragriph??
<GPTT> The Genman chemical company BASI, known for suppiring coal car dyes, acquired the process and sacked Carl Booch with the challenging job of scaling Haber's is emall scale machine to induarial Bouch wese exesuully hoswrd Nebel peizes
and 1931, respestivels, scals,
breakthhoughs alacsinn chemical ougincering dificulties ussociated highegraaone tecrology
Saauforrr pamphmas""
<Humans Could you moke look like the eicorigizsl panagrap??
modify sentences.
spocialiring
Hibee's experinzed sciap indasmial
diiieelly
succzeded. Their groundreeakng Notel Prizes, with Haber
technology
1918 1931.
in (Glenonaee "Smmler rppic <Hamas (COPY PREVIOUS INSTRUCTION-ANSST PAIR) The Could
exumple
reparding
completely inelevant
<GPT4> 4d4 Instrcction: Wric shor story eaay about the developmnnt of the pulic vassine by Jocas Solk, Poccs the sceenit challenges he raced. the innovative methods he seed, and the impect voodie on public health include hisenccl contrst and penuotal sncoleees.
stp Anower In the early 1950, Joaas Salk cuberied on misico to develog a vaccise for poño, a disease that was cousing wadesgreed foar and paraysis Salk faced signdBiant scientife challenges, including Ending way so goow the puluiiin in lane qianilics and ieen inativating withost desimying ability to incus: inmunit.
rsing doenaadehyyde
preserving stracture. breoktheouhh
rigmmus resting drumticall: reducing iniddesce worldwide. The of Salk's
profound,
into preventable condition.
Suik's work noi only savdd comilese livzs but also demenoratea of sciertifie innovaiion mecnoming public bealth challengos His dellication and medical research.
inpiiation the ficdl
Figure 15: Our dialogue with GPT4 for generating corpus of varying levels of similarity for the original corpus from princeton.edu.
34

---

Published as a conference paper at ICLR 2025
E.5.1 ADDITIONAL EXPERIMENT: RELEVANT DOMAIN DETECTION
In this additional experiment, evaluate the effectiveness of different data attribution techniques in identifying relevant domain-specific corpora within the Pile dataset. Specifically, we take a random batch of the validation corpus from sub-domains of the Pile dataset and evaluate the normalized recall@ 1000 scores. This metric measures the proportion of same-domain corpora as the validation corpora among the 1000 highest-valued corpora, normalized by the global proportion of this domain within the Pile dataset. As shown in Table 3 BM25 performs well on this task in general. Both the first-order and second-order In-Run Data Shapley methods outperform the influence function in detecting relevant domain corpora. Analysis: The influence function only uses information from the final trained models, which can result in highly noisy value scores since the removal of one training data point might have negligible effect the final model performance. In contrast, In-Run Data Shapley effectively leverages information from all intermediate checkpoints during model training, providing more comprehensive and accurate assessment of each data point's value. While BM25 performs well on most of the domains, there are still cases where In-Run Data Shapley achieves better detection rate, which implies that gradient information may be more useful in determining semantic similarity to some extent.
Euroaad
Azklr
PhilPpper
FreeLav
HackerNens
Stacklsctuagg
Wileppdla (CR)
Ie-Rtan Shapley entiet In ti-ttnn thats Shapley (2ed ontert
12.7
16.1
14.
5488
16.
34
23
PulMied Alstracts
USPTO Backggeends
Publiid Custral
Enno Kmnals
NIH ExPreler
DM Matihesstio
Ubunte IRC
Gulmmbrrg (PG-19)
Ia Bun Data Skapley (odd unler)
16.
10.1
31.1
24.5
11,5
133
Juflucnce Fuscioos
10.2
74
363
02
10.1
Table 3: Results of relevant domain corpus detection experiment, where the metric the normalized @ 1000 (i.e., the proportion of the same domain corpora as the validation corpora among the 1000 corpora with the highest values, normalized by the global proportion of this domain among the Pile dataset).
35

---

Published as a conference paper at ICLR 2025
corpus that is partially same
Write short story about Radhi and his band OAG as they recruit new members and blend traditional music with alternative sounds. Describe their creative challenges and successes leading up their new releases. Answer: 2012. Radhi re- cruited new 'musicians' for OAG, who were selected from among the students of Akademi Seni Budaya dan Warisan Kebangsaan O. The new line-up con- sists of Qi Razali (drums/backing vocals original drummer...
### Instruction:
Original Wikipedia Corpus
'musicians' for OAG, who were selected from among the stu- dents of Akademi Seni Budaya dan Warisan Ke- bangsaan (). The new line-up consists of Qi Razali (drums/backing vocals original drummer...
In 2012, Radhi recruited
Original Wikipedia Corpus
Synthetic "Similar topic" Corpus
'musicians' for OAG, who were selected from among the stu- dents of Akademi Seni Budaya dan Warisan Ke- bangsaan (). The new line-up consists of Qi Razali (drums/backing vocals original drummer...
In 2012, Radhi recruited
Write short story about classical violinist who decides to explore jazz music, detailing her first encounter with a jazz band. ### Answer: Elena, classically trained violinist known for her precise and emotive performances...
### Instruction:
36

---

Published as a conference paper at ICLR 2025
E.6 COMPARISON WITH OTHER DATA ATTRIBUTION BASELINES ON SMALL- MODELS
In this section, we evaluate In-Run Data Shapley using standard benchmarks for data attribution techniques, including mislabeled data detection and data selection. While data attribution scores can generally indicate data quality, they are not specifically optimized for these benchmarks. Furthermore, approximating the Shapley value has intrinsic merit beyond these standard tasks (e.g., for royalty sharing of Al-generated contents (Wang et al. )024a)). As such, this evaluation primarily serves as a sanity check to confirm that In-Run Data Shapley can reasonably reflect data values. However, state-of-the -otthe--rtttttt performance is not expected since the method is not designed specifically for these tasks.
We compare In-Run Data Shapley with several data attribution baselines, including Retraining-basee Data Shapley (Ghorbani Zou| 2019), KNN-Shapley (Jia et al., 20T9a), influence function (Koh)
& Liang] 2017). Trak (Park et al. 2203), Empirical Influence Functions (Feldman & Zhang 2020). and Datamodels (Ilyas et al. 2022). We also compare with LESS (Xia et al. 20224) an extension of TracIN-CP tailored for instruction tuning data selection.
As some baselines here require multiple model retrainings, we use a subset of 1,000 samples from CIFAR1O and ResNet18 architecture. We evaluate these techniques two standard tasks for assessing data attribution methods: mislabeled data detection and data selection. We note that recent work (Wang et al., 2024d) questions the suitability of data attribution for data selection, but include this metric due to its prevalence in existing literature.
Experiment settings. We use ImageNet-pretraine We use Adam with learning rate 0.001, weight decay of le-4, and label smoothing of 0.1 over 50 epochs. The learning rate reduced by a factor of 0. every 10 epochs. The batch size is set to 64. For retraining- techniques (Retraining-basee Datamodels), we estimate the corresponding attribution scores with 1000 model training runs. For LESS, we use the checkpoints from epochs 10, 20, 30, 40, 50 and set the projection dimension to 2048 as recommended in the original paper. For Trak, we set the projection dimension to be 2048. For KNN-Shapley, we set K=5 and use the features extracted from the last linear layer of ResNet18. We also evaluate its performance by averaging the results using the last T checkpoints where T {1,5, 25,25..
ResNet18 as the architecture in the experiment.
Data Shapley, Empirical Influence Functions,
Mislabeled data detection. The results in Table show that KNN-Shapley achieves the highest performance in mislabeled data detection, likely due to its sensitivity to label changes. Retraining- based approaches (Retraining-bue based Data Shapley, Empirical Influence Functions, Datamodel) have the lowest performance, which can be attributed to Monte Carlo sample inefficiency and stochasticity during retraining, noted in Wang & Jia (2023a). Among techniques requiring only one training run, Trak does not outperform others, aligning with observations in its original paper (Park et al.. 2023) that ensembles are often necessary for high performance. LESS achieves better results by incorporating more information from intermediate checkpoints. In-Run Data Shapley and influence function achieve comparable performance, outperforming all other techniques except KNN-Shapley. The relatively high performance of In-Run Data Shapley is likely due to its deterministic estimation algorithm. Furthermore, makes use of the information from all intermediate checkpoints.
Data selection. Table 5 shows that KNN-Shapley again excels when the selection budget is small. Interestingly, most data attribution techniques perform worse than random baseline for small selection budgets, aligning with observations that selecting data points solely based on attribution scores can harm dataset diversity (Wang et al. 2024d). For larger selection budgets (60%, 80%), single-training techniques achieve similar performance levels.
37

---

Published as a conference paper at ICLR 2025
Retraining-bused Data Shapley (Chhorbani Zou 2019)
Empirical Influence Function
Felddman Zhanng 2020
Datamodels Tlyas et al
2022
0,582 (0,020)
0.552 (0.077)
0.52
KNN-Shapley Jia at 2019
Wang & Fin 20236
Influence Tumction 0.654 (UUDS4)
Koh & Linng 2017
LES8 Kia et al.
2024
0.70 (GAT1))
0S8 (UX15
1st Order In-Kun Data Shapley (ours)
2nd Order Ia-Run Datn Shapley (ours)
Trak (1 ept) Park et
2025
0.678 (0,045)
0.680 (0.048)
Trak epts) al. 2013
Trak (15 (Park al. 0.609 (17028)
Trak (25
2023
0.542703125)
0.617 (00021)
Table 4: AUROC scores of mislabeled data detection task with various data attribution techniques on CIFARIO 10 dataset. The higher the AUROC score is, the better the method is. The results across three different training runs (the randomness comes from construction corrupted datasets), where show the standard deviation in O. Methods with top-3 performance are bolded.
20%
40%
60%
80 %
Random
0.350 (0.010)
0.461 (0.010)
0.525 (0.004)
0.559 (0.003)
Influence function
(Koh & L jang
2017
0.320 (0.033)
0,450 (0.028)
0.530 (0.015)
0,580 (0.004)
Trak (1 cpt)
Park ct al 2023
0.329 (0.021)
0.443 (0.030)
0.517 (0.016)
0.572 (0.009)
Trak (5 epts)
Park et al. 2025
0.325 (0.022)
0.445 (0.031)
0.519 (0.018)
0.572 (0.009)
Trak (15 cpts)
Park al.
20255
0.327 (0.028)
0.446 (0.035)
0.523 (0.018)
0.573 (0.010)
Trak (25 epts)
Park cl
0.332 (0.025)
0.443 (0.035)
0.520 (0.018)
0.578 (0.015)
LESS Xta 2024
0.314 (0.012)
0.460 (0.015)
0.541 (0.006)
0,582 (0.006)
Data Shapley Ghorbani & Zou 2019
0,317 (0.047)
0.468 (0.010)
0.527 (0.004)
0.570 (0.008)
Datamodels (Tyas al. 2072
0.342 (0.004)
0.465 (0.004)
0.534 (0.010)
0.559 (0.005)
Empirical Influence Funciion (Ieltiman Zhang 2020
0.342 (0.004)
(0.016)
(0.009)
0.568 (0.010)
KNN-Shapley (Jia at 2019a]
0.354 (0.017)
0.478 (0.007)
0.525 (0.015)
0.563 (0.005)
1st Order In-Run Data Shapley
0.344 (0.009)
0.472 (0.003)
0.541 (0.006)
0.580 (0.004)
2nd Order In-Run Data Shapley
0.342 (0.010)
0.473 (0.008)
0.544 (0.005)
0.580 (0.004)
Table Test accuracies when training ResNet18 on high-value data points selected by various data attribution techniques. To be able to compare with techniques that require model retraining, for each training run we randomly sample a size- 1000 subset of CIFAR dataset (with 10% data points being mislabeled). The results are across three different training runs (the randomness comes from the construction corrupted datasets), where we show the standard deviation in (). Methods with top-3 performance are bolded.
38


Reviews:
[{"review_id": "kQ2DlDFSB3", "reviewer": "Reviewer_roW8", "summary": "This paper introduces In-Run Data Shapley, a novel principled way of attributing the data contribution for deep learning models within one training run. A classical Data Shapley technique requires retraining which is computationally prohibitive in practice for large models, and more importantly, it quantifies data contribution for a general learning algorithm, and not for a particular model at hand. Related to this, data contribution for a single model is of crucial importance for properly investigating fairness and copyright implications.\n\nIn-Run Data Shapley is powered by the fact that model training is performed iteratively, and Shapley values can be derived analytically for each model update step via gradient dot products or gradient-Hessian-gradient products between training and validation data. The authors propose an efficient method to approximate In-Run Data Shapley values during one training run via first- and second-order Taylor expansions, and compute these values in one and two backpropagation, respectively, inspired by the ghost clipping technique. This incurs negligible computational overhead, making In-Run Data Shapley highly usable in practice. Furthermore, the authors empirically evaluate their approach on Pile dataset, highlighting several important insights re: data curation and cleanliness of the dataset, dynamic data contribution throughout the entire training process, and the degree of data contribution in copyright issues.", "questions": "I would like to know the authors' opinion of applying the general idea of In-Run Data Shapley to other use-cases in machine learning, such as hyperparameter importance during the HPO run. More generally, do the authors envision transferring this idea to other domains, especially in the case where gradient information is not available?", "limitations": "", "rating": 10, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The proposed method is novel, efficient and promising. The presentation of the paper is very clear and succinct; technical contributions are clearly stated and rigorously developed. The authors carefully position their work and acknowledge several limitations which they claim will be a part of future work. Empirical evaluation is thorough and the paper raises important observations re: societal implications of the large model training.", "weaknesses": "I do not see any major weaknesses of the paper.\nMinor (typo): line 500 - sentence \"The results of this experiment...\" appears twice in a row", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "j6PUjCowN1", "reviewer": "Reviewer_wuoD", "summary": "This paper presents a new technique called \"in-run data shapley\" to eleminate model retraining for assessing data contributions. This seems a new angle to assess the data attribution and importance. The results shows that this can provide efficiency improvement, and help make more insights for data contribution. The paper also identifies and discussed potential implications for copyright in genAI and pretraining data curation.", "questions": "1. Could you please provide an example on how your method used in-run data Shapley to calculate the data contribution? Is it possible to provide a figure? Even using a simple example data set would be very helpful. This cannot be replaced with a loss-time curve. \n\n2. Is it possible to extend the method to regression and classification problems?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The motivations, problem statement and objectives and contributions are provided clearly. \n\n2. The mathematical induction and proof seem solid.\n\n3. The results and implications of the new concept/techniques are described clearly.", "weaknesses": "Compared with the introduction, background, methods and mathematical induction, which are presented clearly, the results and analyses are a bit weak. It would be better to provide concrete examples with more deep analyses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zU02NdDjtC", "reviewer": "Reviewer_ZCk2", "summary": "The paper presents a novel approach called In-Run Data Shapley that eliminates the need for model retraining to evaluate data contributions in machine learning. By leveraging gradient updates within a single training run, the authors develop a computationally efficient method suitable for large-scale models, such as foundation models like GPT-2. The work introduces efficient algorithms using Taylor expansions and techniques inspired by differential privacy to minimise runtime overhead. The study also demonstrates the practical utility of In-Run Data Shapley in data curation and understanding the impact of pretraining data.", "questions": "* The method requires validation data to be available before training. Can the authors elaborate on the potential limitations of this requirement and discuss scenarios where this may not be feasible? Are there alternative approaches that could make In-Run Data Shapley applicable when validation data is not pre-available?\n* How does the use of first- and second-order Taylor approximations affect the reliability of the Shapley values in practice, especially in highly non-convex or complex loss landscapes? Can the authors provide additional empirical results or theoretical analysis to quantify these approximation errors in diverse settings?\n* While the paper demonstrates efficiency improvements, how does the proposed method scale when applied to models even larger than GPT-2 or to models with different architectures, such as transformer-based models with sparse attention mechanisms? Can the authors provide insights or preliminary results on this?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The introduction of In-Run Data Shapley is a significant advancement over existing retraining-based methods, offering a scalable solution to data attribution in large models.\n* The case studies, particularly in data curation and copyright implications, highlight the real-world relevance of the proposed method.\n* The closed-form derivations for the Shapley values using first- and second-order Taylor approximations are mathematically sound and well-explained.", "weaknesses": "* The method's requirement for validation data to be available before training might limit its applicability in scenarios where such data is not readily available.\n* Even though the authors address memory concerns using gradient accumulation, the practicality of this approach in extremely large models with limited resources is not fully explored.\n* The first- and second-order Taylor approximations are empirically validated, but there is limited discussion on how these approximations might affect the reliability of the data attribution scores, especially in more complex models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Hl4JMIVkCU", "reviewer": "Reviewer_Vb7n", "summary": "The paper introduces in-run Shapley, a data valuation method for SGD based models that estimates data values in one training run across different update steps. \n\nThe authors further provide enhanced ways of computing these data values with first and second order approximations. \n\nThe method is evaluated on the PILE dataset for GPT-2 and Pythia 4.10 against influence functions and outperforms them.\n\nRemark: Thanks to the clarifications provided by the authors during rebuttal, I have raised Soundness from 2 to 3, Contribution from 3 to 4, and the overall score from 5 to 6.", "questions": "I want to confirm whether I have understood the definition of the in-run Shapley value for a data point $z$. It is the “cumulative contribution of the data point $z$ across all gradient update iterations within a single training run”. Does this mean that in each gradient update (e.g., for each batch) the Shapley data value w.r.t. to this batch is computed and averaged at the end? This would mean that for each batch $b$ the marginal contribution of $z$ would be estimated on all possible subsets of $b$. \n\nIf so, I would be interested in an intuition how this value is related to the standard Shapley data value. This could be done conceptually but also by experimental evidence, e.g., by comparing the method to other visiting Shapley based estimates, as suggested above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper introduces an interesting and to me novel method to estimate data values in a single training run. This makes data valuation feasible to large scale data sets. Furthermore, the method is evaluated on such a data set.", "weaknesses": "The evaluation is performed against influence functions only. This way it is unclear whether the method only outperforms leave-one-out (approximated by influence functions) or is also better than the standard data Shapley value. \n\nOther data valuation/pruning methods are dismissed due to scalability issues (Sec 5.3.1). However, to my understanding, both Memorization (Socher et al., 2022, Feldman and Zhang (2020)) and Supervised Prototypes (Socher et al., 2022) should be applicable to larger models and have been implemented on ImageNet scale by Socher et al. I'm uncertain if this generalizes to LLMS, but it should be discussed if not feasible.\n\nIt is specifically indicated that TRAK wouldn't scale to LLMs, yet according to my understanding, TRAK can function with checkpoints from a limited number of models (see Appendix \"E.3 Proxies for model ensembles in compute-constrained settings\" of the TRAK paper).\nGiven the evaluation of in-run Shapley on large datasets, I would elevate my vote if the authors either compare their method to the ones mentioned above or provide reasons why those methods don't scale to the dataset.\n\nMinor Remarks\n--------------------\nOpenDataVal is a recent benchmark for data valuation. Although it is designed for small-scale data, it offers ready-to-use implementations of various algorithms and could be employed to benchmark In-Run Shapley against other methods. This would enhance the paper by demonstrating whether In-Run Shapley performs comparably or even superior to the standard Shapley value.\nSome references are missing:\n* Toneva et al. (2019) demonstrated that data points learned early in training and not forgotten in later epochs are less important to model performance than points that are frequently forgotten. The former can be omitted to reduce dataset size.. This reminds of the method introduced in the paper. \n* Nguyen et al. (2023) proposed \"A Bayesian Approach To Analysing Training Data Attribution In Deep Learning\" to tackle the noise issue when training multiple models. This problem, referred to as \"instability,\" is also mentioned in this paper but without citing Nguyen et al.\n\nThere are a few spelling mistakes especially in Sec. 5.3.3:\n* In \"data set,\" the word \"set\" is missing.\n* The sentence \"The results of this experiment have important implications for the current discussion on the copyright of generative AI.\" is repeated.\n\nSources\n-----------\nRemark: the reviewer is not the author of any of the papers below.\n* Socher et. al (2022): Beyond neural scaling laws: beating power law scaling via data pruning\n* Feldman and Zhang (2020): What neural networks memorize and why: Discovering the long tail via influence estimation\n* Toneva et. al (2019): An Empirical Study of Example Forgetting during Deep Neural Network Learning\n* OpenDataVal (2023): OpenDataVal: a Unified Benchmark for Data Valuation\n* Nguyen et. al (2023): A Bayesian Approach To Analysing Training Data Attribution In Deep Learning", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)