GraSS: Scalable Data Attribution with Gradient Sparsification and Sparse Projection
Authors: Pingbang Hu
Joseph Melkonian
Weijing Tang
Han Zhao
Jiaqi W. Ma
Venue: NeurIPS 2025 poster ()
Keywords: data attribution
influence function
gradient compression
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: Propose a scalable gradient compression algorithm for data attribution with sub-linear complexity that achieves competitive attribution results.

Abstract: Gradient-based data attribution methods, such as influence functions, are critical for understanding the impact of individual training samples without requiring repeated model retraining. However, their scalability is often limited by the high computational and memory costs associated with per-sample gradient computation. In this work, we propose **GraSS**, a novel gradient compression algorithm and its variants **FactGraSS** for linear layers specifically, that explicitly leverage the inherent sparsity of per-sample gradients to achieve sub-linear space and time complexity. Extensive experiments demonstrate the effectiveness of our approach, achieving substantial speedups while preserving data influence fidelity. In particular, **FactGraSS** achieves up to 165% faster throughput on billion-scale models compared to the previous state-of-the-art baselines. Our code is publicly available at https://github.com/TRAIS-Lab/GraSS.

GRASS :::: Scalable Data Attribution with Gradient Sparsification and Sparse Projection
Pingbang Hu'
Joseph Melkonian
Weijing Tang*
Han Zhao' Jiaqi W. Ma'
Uniieersity of Illinois Urbana- Urbana-Champinn Champaign (pbb,hanzhag hanzhao, aammzha..jiaqnnnnn jjaagima/lillinois edd
Womp Labs joetwomplabs ai
*Carnegie Mellon University
veijingt cmu,
Abstract
Gradient-based data attribution methods, such influence functions, critical for understanding the impact individual training samples without requiring repeated model retraining. However, their scalability is often limited by the high computational and memory costs associated with per-sample gradient computation. In this work, we propose GRASS, novel gradient compression algorithm and its variants FACTGRASS for linear layers specifically, that explicitly leverage the inherent sparsity of per-sample gradients achieve sub-linear space and time complexity. Extensive experiments demonstrate the effectiveness of our approach, achieving substantial speedups while preserving data influence fidelity. In particular, FACTGRASS, ASS achieves up to 165% faster throughput on billion-scale models compared to the previous state-of-the-ar baselines."
Introduction
Data attribution [Deng et al., 2025] aims to measure the impact of individual training samples on machine learning model and has been widely applied to data-centric problems in modern AI, such as data curation [Koh and Liang, 2017], fact tracing [Lin et al., 2024], and data compensation [Deng et al., 2024b]. There are two major categories of data attribution methods, gradient-bunt and retraining- based [Hammoudeh and Lowd, 2024]. The former category. such as influence functions [Koh and Liang, 2017] and its variants. has gained increasing popularity in large-scale upplications as it does not require costly model retraining. One common feature of gradient-base methods is their reliance on the per-sample gradient- the gradient of the loss with respect to model parameters for each individual data point- to capture the local sensitivity of the model with respect to each training sample, providing a fine-grained understanding of data influence.
However, gradient-based methods still face significant scalability challenges for very large models, such as large language models (LLMs). Specifically, computing and storing per-sample gradients for model with n training samples and p parameters requires O(np) memory and compute, creating severe bottleneck for large-scale models. To address this, recent work has explored compressing these sigh-dimensional gradients into sower-dimensional representationss reducing memory requirements to ((k)) for target compression dimension & < [Wojnowicz et al., 2016, Park et al., 2023, Choe al., 2024]. However, this compression often introduces additional computational overhead, as the most common approach-randome matrix projection with the Johnson- -onnn-Liidnnntuuu (JL. cenrantee-reqiice dense matrix multiplications, resulting an overall time complexity of O(nkp).
To overcome these limitations, more specialized approaches have been proposed. For example, the fast LindesnnLindenstraauss transform (FJLT) used in TRAK's official implementation [Park et al., 2023] exploits structured random matrices, reducing the projection time to (((p + k) log per sample. Alternatively, recent work by Choe et al. [2024] proposed LOGRA that leverages the
*Our code is publicly available at httpp::///tit httpgggthhu..... www./oaao...//... LabsS-LbarrrSrS
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Kronecker product structure of gradients in linear layers, reducing projection time O(v for each data via a factorized matrix approach. However, these methods are often designed for general inputs and do not fully exploit the unique sparsity structures present in per-sample gradients.
In this paper, we push the boundaries of these state-of-the-ar (SOTA) gradient compression meth- ods by proposing novel, two-stage gradient compression algorithm called GRASS (Gradient Sparsification and itly leveraging the inherent sparsity of per-sample gradients. Our contributions
that achieves sub-linear space and time complexity by explic-
follows:
1. We identify two critical sparsity properties in per-sample gradients and leverage these to develop gradient compression algorithm. GRASS, that reduces both space and time complexity from (ppk) to O(k), where k is tunable hyperparameter in the range [k,p).
2. We further derive practically efficient variant of GRASS for linear layers, FACTGRASS (Factorized GR GRASS), which exploits the gradient structures for linear layers, similarly achieving time and space complexity of O(k)) without the need to ever materialize the full gradients.
3. Through extensive experiments, we demonstrate that our approach achieves several orders of magnitude speedup compared to previous SOTA while maintaining competitive performance standard evaluation metries. In particular, on billion-scale language models and datasets, FACTGRASS is up to 165% faster in terms of compression throughput compared to LOGRA.
2 Preliminary
We begin by introducing the influence function and its practical implementation our running example of gradient-based data attribution methods. We then demonstrate how random projection can be integrated with the influence function. We note that the proposed compression methods naturally approaches that share similar low-level computations. Examples in-
extend to other gradient- clude TRAK [Park et al., 2023], SGD-Influence [Hara et al., 2019], and Data Value Embedding [Wang et al., 2025]. A more detailed discussion of related work is provided in Section A.
2.1 Influence function
Given a dataset = {z; E (d) consider a model parametrized by â E TRP that this trained on the dataset D with a loss function é: Rd x IRP - R via empirical risk minimization: arg mingge= 1 Ex= ((z;; 0). Under this setup, the influence function [Koh and Liang, 2017] can be theoretically derived; essentially, it gives an estimation on every training data 2 s's "influence"
I(2,, Ziea) of the test loss (Zren: 0) of given test data 21stt when 2; is removed from D as
I(2s, Frest)
V QgÉ(Zrest (Zrest 0) H1 V (z(;)))
where H3 -
i=1 Vil(zz, is the empirical Hessian. As H3 E RRxx and computing it requires higher-order differentiation for every training data, several approximation algorithms aim to mitigate this. One famous approximation is the Fisher information matrix (FIM) [Fisher, 1922] approximation Ha E, (o((2; V (2; 0) which exact for model trained with the negative log- likeliiooood objective. Since FIM only involves the first-order gradient, which is also needed in the other parts of the calculation of influence I, and hence is popular and efficient approximation. Given this, people realize that an efficient way to compute the influence function is to divide the computation into two stages [L al., 2024, Choe et al., 2024]:
1. Cache stage: 1.) compute all per-sample gradients g, := 9s. = Vel(z;; 0), 2.) construct the FIM Fg = Σ 9.g.T 3.) perform inverse F'M--vctor-pruduut (iFVP) via D: == F7 1 gi for all z.'s.
2. Attribute stage: For query data ăestt 1.) compute its per-sample gradient Grest Vol( (rest: 0).
2.) compute all-pait-ineer-produut between Ieea and (Ø: [0 as I(zi, Ziess) (gtest D.) for all zz's.
The bottleneck of this pipeline is the cache stage, since the problem for the attribute stage is the well-studied vector inner product search, where numerous optimization techniques have been studied in the vector database community. the other hand, iFVP remains challenging task due to the matrix inversion of quadratic model size, where in most cases, materializing FIM is infeasible.

---

2.2 Random projection
Despite multiple attempts to accelerate influence function from various angles, one of the most naive and simple strategies, RANDOM [Wojnowicz et al., 2016, Schioppa et al.. 2022, Park et al., 2023], remains practically relevant and achieves SOTA attribution results. RANDOM leverages sketching (random projection) techniques by replacing each per-sample gradient Di E RR with 0 == Pg: E TR", a random projection matrix for some k < p. This subsequently leads to the projected FIM approximation F = pF [= () E R**k, i.e., restriction of F' to the subspace spanned by the columns of P. The theoretical merits of RANDOM largely come from the well-known Johnson-Lindenstrane Lindenstrauss lemma [Johnson, 1984], which states that for drawn
where P E kx
appropriately, e.g., Pij lid. (00, 1) or (({+1}) for all i. with high probability, the pair-wise distance [g gjl between any two 9i and gy will be preserved up to 1 = factor after the projection, whenever = (E - n). While this does not fully justify whether the inner product between a gradient 9 = (f:) ( will be preserved (see Section A.2 for an in-depth discussion), RANDOM remains to be one of the strongest baselines to date and is practically appealing due its simplicity.
projected per-test-sample gradient Best and the "conditioned" projected per-train-samp
Computational-wise RANDOM accelerates iFVP significantly as the matrix inversion complexity scales down from (pp²) to O(A²). In terms of the projection overhead, the matrix-based projection method requires (kp) overhead per projection. TRAK [Park et al., 2023] leverages the fast Johnson- Lindenstrauss transform (FJLT) [Ailon and Chazelle, 2009, Fandina et al., 2023] that has similar theoretical guarantee as the random matrix-based -baee projection to achieve a speed up of O(p-+ k) log p). Another line of work by Choe et al. [2024] called LOGRA exploits the gradient structure of linear layers and factorizes the projection accordingly, reducing the problem size quadratically. With suitable hyper-parameter choice, the computational complexity goes down from Okkp)) to O ((Vkip)). where ky and pt now refer to the projection dimension and number of model parameters of one (1th) linear layer. This sets the SOTA efficiency and attribution quality to date.
3 GRASS: Gradient Sparsification and Sparse projection
In this section, we first explore two key sparsity properties in per-sample gradients (Sections 3.1 and 3.2) and propose efficient compression methods for each. Combining them, we present GRASS and its variant FACTGRASS (Section 3.3), which beat the previous SOTA data attribution algorithms.
3.1 Per-sample gradient sparsity
Modern deep learning models often induce highly sparse per-sample gradients, especially when using popular activation functions like ReLU [Nair and Hinton, 2010]. To see this, consider the gradient of the first read-in linear layer with weight W E Te xd" with din and ReLU activations. Then given sample a E Rd, the output is h = ReLU(W2). Since RcLU(x) = max(0, .:) sets all negative reeaacivatioos to zero, naturally creating sparse activations. This sparsity propagates the gradient computations via the chain rule, resulting in gradients with numerous zero entries. This is not unique to ReLU and extends to many other activation functions that exhibit similar behavior.
Remark 3.1. Such sparsity is unique to per-sample gradients: for mini-batch gradients EiE 91/ Bt) the sparsity pattern differs for individual g, and will be destroyed when adding together.
Given the inherently sparse nature of these gradients, it is natural to consider other compression methods that can effectively exploit this input sparsity. Traditional dense random projection methods struggle to leverage sparse inputs without incurring significant overhead. Although FJLT is often more efficient, its algorithmic structure also prevents it from effectively exploiting sparsity patterns.
Sparse Linnsson-indenstrauuss Transform. A natural candidate for efficient gradient projection is the sparse Johnson- Lindenstrauss transform (SJLT) [Dasgupta al., 2010, Kane and Nelson, 2014], which significantly reduces the computational cost by sparsifying the projection matrix. To understand SJLT, it is useful to revisit the standard matrix-basee projection approach, which relies
We omit the normalization factor (in this case, 1/vK) to keep the presentation clean.
We follow the notational convention in the rest of the paper: denotes compression." 7 denotes (FIM) precondition, and denotes the compression and then (compressed FIM) precondition.
3

---

on matrix-vector multiplication. Given a projection matrix P Rexy and an input vector g RR to be projected, the product Pg can be computed as ÿ = P En= Pcj) where the j term represents the 5th column P.y of P scaled by the jth entry ( of g. In the case of dense Rademacher projection matrix (entries being 1:1,, this requires (pp) computation for both constructing g and summing them. This dense projection process is illustrated in Figure 1.
P
Pa xg(1) +"*
Pay xg(p)=== 9
X Paxx(()) + Py
x
A
kxp
Figure 1: Dense Rademacher projection.
Figure 2: Sparse Rademacher projection (s 1).
From this perspective, the SJLT arises naturally: by "zeroing" out the projection matrix P. we significantly reduce the required com- putation, illustrated in Figure 2. Specifically, Dasgupta al. [2010] and Kane and Nelson [2014] demonstrated that retaining only 8 (k) out of the k possible non-zero entries for each column of the projection matrix still preserves the essential proper- ties required by the Johnson Linssonn-indessrruuss lemma. This approach, which we denote as (-)., reduces both the time and space complexity to (ps). where
x1
X
9
1:
o, (k) is much smaller than k.
An equivalent way to view the computation of SJLT shown in Figure 3, where we initialize 9 to be zero vector and sequentially scan through g. with each g for j E [p] chooses many random j' E [k] to either add on subtract from the corresponding g(j").
Figure 3: SILT with s 1. is immediate that the input is itself sparse, the complexity can be further reduced. Specifically, for a dense matrix projection, the complexity becomes O mnz(g)), and for SJLT, this drops to (s an)(g)). where nnz(g) == llllo denotes the number of non-zero entries in g. We highlight g in red in Figure 3 signify that the computational complexity of SJLT scales with the size of g.
Implementation of SJLT. Despite these theoretical advantages, practical implementations of SJL.T face critical performance chal- lenges, such thread contention and irregular memory access patterns. While the latter overhead is due to the nature of SJLT, the former occurs because multiple threads may attempt write to the same entry in the output vector 9. causing race conditions that degrade performance, especially when the target dimension l is small. These are especially critical when implementing in libraries like PyTorch. Moreover, the default matrix multiplication algorithms in PyTorch are highly hardware- optimized (e.g.. fache-friendly memory layouts and fused multiply- accumulate instructions). in practice often outperforming any sim- ilar multiplication algorithms when the problem size is small.
22
Delative
Geazsian SUT (yyoarc
Figure 4: Benchmark of differ- ent projection methods with p- = 131,072 under several sparsity levels (distinguished by opacity). Relative error is w.r.t. pair pase- distance preservation.
To address these issues, we developed a SJLT CUDA kernef that optimizes the memory access patterns and minimizes thread con- tention to better exploit the underlying hardware capabilities. This kernel significantly reduces the overhead compared to its PyTorch implementation counterpart, resulting in substantial performance gains. As shown in Figure 4, for SJLT with s 1, our CUDA implementation outperforms the highly optimized dense matrix multiplications for small projection problem sizes, while retaining the speedup of SJLT w.r.t. input sparsity. In contrast, dense Gaussian projections exhibit a clear dependency on k while neglecting the input sparsity, making them less efficient in such cases. practice, we set s = to optimize for speed while enjoying strong empirical guarantee for small relative error, seen in Figure 4.
Thee code is publicly available at https: // http//gtthuhh.eee/eeeeeeee.e http://ttt...o//A.t...... Lab/sj

---

To summarize, the complexity of SJLT 1.) scales with the input sparsity, and 2.) is independent of the target dimension k, both of which are critical for efficient gradient compression. Specifically, 1.) per-sample gradients are naturally sparse, and 2.) larger k generally improves the fidelity of data attribution, which is more desirable. These make SJLT a natural fit for gradient compression.
3.2 Effective parameter sparsity
While SJLT effectively reduces the computational overhead and takes advantage of the sparsity structure of the input, it still scales linearly with the potentially large input dimensionality p. We now explore a more aggressive compression that achieves sub-linear complexity by directly exploiting the inherent effective parameter sparsity in neural networks. We term this approach as sparsification.
Random Mask. Modern deep learning models often exhibit high degree of parameter redun- dancy, where only a small fraction of the weights significantly contribute to the model's final performance [Han et al., 2016, Frankle and Carbin, 2019]. In similar vein, the distributed training community has observed that the majority of gradient updates are redundant, allowing for substantial compression without a significant impact on model accuracy [Lin al., 2018, Aji and Heafield, 2017]. This suggests that many parameters can be safely ignored without substantial loss in accuracy. In- spired by this observation, simple yet surprisingly effective sparsification algorithm, Random Mask, randomly selects small subset from the input dimensions to form a compressed representation.
Formally, the Random Mask (RM& (.)) involves selecting random subset of l: dimensions from the original p-dimensional gradient vector, effectively extracting length-k sub-vector. This can also be viewed as a random projection onto the standard basis of a randomly chosen k-dimensional Euclidean subspace, i.c., 9 = .g where MM E R is a sparse binary selection matrix with exactly one (non-repetitive) non-zero entry per row, corresponding to the randomly chosen dimensions. This is illustrated in Figure 5.
x1
At first glance, RM, may a substantial amount of information. However, empirical evidence suggests that this method can still yield non-trivial attribution performance, especially when the underlying gradient distribution is sparse when the model is wver-parameterized. Moreover, the extreme simplicity of this approach makes it highly efficient, with a computational cost of just O(k). achieving a sub-linear complexity w.r.t. p. We highlight ğ in red in Figure 5 to signify that the computational complexity of Random Mask scales with the size of g.
overly aggressive, it discards
p
Figure 5: Mask.
Selective Mask. Building the idea of Random Mask, we introduce a more structured approach, Selective Mask (SM&(-)) which aims to selectively retain the most important parameters based on simple, yet effective. data-drived optimization. Inspired by recent work identifying influential model parameters [He et al., 2025], Selective Mask introduces a small but meaningful optimization overhead to improve the fidelity of the compressed representation. Formally, given a training set ( we define the selective masking problem as the following unconstrained optimization task:
S = =ar max E. corr (((9s (000..gmm)) )) ((0r, 9 9z.e)))) Di AlIo(S))lI, SERP
(1)
where 9. = oS) O E IP is the (soft- masked g,, O denotes the element-wise product, and a() (0, is the sigmoid function. The first term of the objective encourages the average correlation between the original and masked gradients' GRADDOT attribution scores [Charpiat et al., 2019], widely used and computationally efficient approximation of the influence function. The second term, an é regularization penalty, promotes sparsity by pushing (S)) towards a binary mask.
Once the optimal S* is obtained after solving Eq. (1), the final binary mask M E {0, 1 can be extracted by thresholding the sigmoid outputs with k Σ 1o(5"),20 20.5 is the number of selected dimensions. Formally, one can obtain the explicit mask matrix . via solving (My, MM) 1r(8)))20.5 but the actual implementation is simply an index extraction for all for L=(55),20.5
This formulation avoids the exponential complexity of directly optimizing over discrete binary masks, as the continuous nature of allows for efficient, first-order gradient-based optimization. While incurs memtimme overhead for solving Eq. (I), this method provides more principled approach to
5

---

mask selection by directly targeting widely used surrogate data attribution score, making it natural extension of Random Mask. We use MASK; to refer to either R or SM₃, for convenience.
3.3 GRASS FACTGRASS: Multi-stage compression
We now formally introduce GRASS and FACTGRASS, an integration of the proposed approaches by combining the sparse projection (Section 3.1) and also sparsification techniques (Section 3.2).
3.3.1 GRASS: Sparsifyy first, sparse projection next
Recall that the time complexity of SJLT with is O(p) where p is the input dimension, while for both sparsification techniques are (kk) where is the target sparsification dimension. A natural idea employ a two-stage compression: Given an input g and target compression dimension & < p.
1. Sparsification: sparsify the input g to sub-vector g' of dimension k' with k < k' < p.
2. Sparse projection: then apply SJLT to g' get the compression 9 with target dimension k.
We term this simple per-sample gradient compression method Gradient Sparsification and Sparse projection (GRASS), which is illustrated in Figure 6. This leads to a sub-linear time complexity O(K' + k') = Okk)) to the input dimension p, since the runtime of SJLT depends only on its input dimension, which is now sparsified to k from
MASKE
x1
X
SJLT
p. In the extreme cases when k' p. GRASS reduces g to vanilla SJLT; while when = k GRASS reduces to sparsification. Notation-wise we write SJLT MASK
g'
Intuitively, k as a hyperparameter balances the computa- tional complexity and attribution performance: after select- ing k coordinates of g to form g', subsequent application of SJLT will compress o' down to the target dimension without losing the pair-wise distance information.
K
p
Figure 6: GRASS.
3.3.2 FACTGRASS: Exploiting layer-wise gradient l'actorization structure
In addition to FIM approximation, influence function on large-scale models often leverages the layer- wise independence assumption by approximating FIM as block-diagonal matrix, ignoring parameter interactions across layers. Specifically, this approach decomposes the FIM as (fa .Fo,) for
an L-layer neural network, where each block F'g, corresponds the (th layer's parameters 0, defined as Fg, E. [2; 0) Ve, ((2; J. By writing 94,1 Vo, (2z; 0). iFVP computation can now be done layer-wise as 9t.1 = F 0, 9a,1- Furthermore, coupling this trick with gradient compression, i.e.,
consider compressing It,1 Is.1. which subsequently forms Fb we now compute 91,1 F 9t.--
However, this renders critical challenge for GRASS to demonstrate practical speedup via direct application of each of these layer-wise compression sub-problems, since SJLT suffers from small problem sizes (Section 3.1). Specifically, if each layer has roughly the same number of parameters, the compression problem size is reduced from p & to p/ L x k/ L each if the compression dimension allocated uniformly. Moreover, recent techniques such as LOGRA [Choe et al., 2024] further reduce the compression problem size of each layer-wise compression via gradient factorization, making it even more difficult to integrate GRASS with these SOTA methods to achieve a further speedup.
This motivates the need for a specialized adaptation of GRASS that can effectively exploit a similar gradient factorization structure. To this end, we propose FACTGRASS, which explicitly incorporates this factorization structure to achieve even greater efficiency in gradient compression.
To motivate and understand the practical difficulties we must avoid, we first introduce LOGRA. Formally, LOGRA exploits the factorized structure of linear layer's gradients. For full generality, consider a sequential input z; E RdxT of length T to the model and the corresponding
Recap on LOGRA.
input 2 e 4 and output (pre- apre-activations 2, E _ xT of the ( linear layer with weight

---

Forward Pass
Backward Pass
d
Pin
D
D nut
60
du
Wi
Plut
W
Figure 7: LOGRA for one linear layer. Note that the application of vec(.) on 9 is omitted.
matrix Wi E xd such that =ou "i,1 = Wi
-in
Then the gradient of the 1th linear layer is given by
01(z;; 0) dw,
0b(z; 0) dz
01(2,;
0)
in
T
vec(DWi)
T E(et) @ D(2
out J
(2)
2zg OW,
2z
where we write v,l(z;; 0) as Du for any v. LOGRA then leverages this Kronecker-product structure of voc(DWi) by assuming the projection matrix Pt for this layer has a factorized structure, i.e.,
Pi vec(DWi) = (P P! voc(DW)) Σ (PT" ((("T))
where Pin R xd; Pr E " xdi". and P P| & PTtl ((TT"" Naturally, let k kjm hqal and pl = dj dill to be the compression dimension and number of parameters for the thh linear layer, respectively. Hence, Pt E ku as we expect, with = Σt= Pt and k Et= ky The computation of P. vec(DW)) of LoGRa is illustrated in Figure 7, where:
forward pass on and backward pass on ((2;6) give 2 and D=j for each of the 1h linear layer;
only two smaller projection problems size ki" din and kqth drtt are needed for each sequential index, instead of to project the entire gradient, which is of size (k:"* (df drt)) kj X pi; in addition, the actual gradient of the layer is never materialized (which will require computing Eq. OTT))), only the projected gradient materialized at the end (which takes O(Tk)).
Notation-wise, as Pin and pru are default to Gaussian projection [Choe et al., 2024], we write LOGRA as GAUSSypssee, where & indicates that the projection is done in factorized manner. We see that overall, assuming dith = dil = /pi, choosing ki ~ Aq = /ky results in a speedup from O(kip) to ((Vktp)) per projection (i.e., per input and per sequential index) for the 1 layer.
Bottlenecks of integrating GRASS with LOGRA. One can change the (dense) Gaussian pro- jection used in LOGRA to other compression methods, e.g., SJLT, Mask, or GRASS, resulting in pa.. SJLT @Aq", and GRASS GRASS respectively. However, trivial integration with GRASS will not lead to practical speed up compared to LOGRA since each compression problem size is now reduced, making GRASS slower than Gaussian projection due to the practical imple- mentation overhead one of its algorithmic components, SJLT, as shown Figure 4. This small projection problem size regime makes a direct integration of GRASS with LOGRA challenging.
natural idea to mitigate this issue is apply SJLT moderate dimension by not factorizing the projection: by first constructing the gradients of the layer via (2), we can perform GRASS on much larger problem size (pi X k2) rather than the two smaller problems (roughly /Pi x vk)). However, this results in another bottleneck: materializing the gradients explicitly blows up the space and time complexity to Opt)), which is slower than LOGRA, defeating the whole purpose.
Factorized GRASS W.. To bypass the bottlenecks, we propose Factorized GRASS (FACTGRASS) variant of GRASS that exploits the Kronecker-product structure. Specifically, given target compression dimension by = kim x k: < Pt for the 1th layer, after a forward pass on 2; and a backward pass [22;; 0) to get 2 and De FACTGRASS operates in three stages (Figure 8):
7

---

Forward Pass
Backward Pass
dr
MASK
ii
II
D 2u
duut
W
MASK gqur
W
kqua
SJLTA:
gi.t
Figure 8: FACTGRASS for one linear layer. Note that the output of SJLT is a vector in practice.
1. Sparsification: sparsify both zin and Dzj to an intermediate dimension k/po' and kq where 2i,1 kith S hip < and knth S hqwu & ditt respectively;
2. Reconstruction: construct the "sparsified gradient" I',1 of dimension ki == kil" x kque via (3),
i.e., Kronecker product between the sparsified =! and the sparsified Dz
3. Sparse projection: apply SJLT to Ih, to get the compressed Jr,1 with target dimension ky.
Intuitively, FACTGRASS resolves the two bottlenecks by 1.) avoid reconstructing the full gradient via sparsification, and 2.) avoid small problem size for SJLT via reconstruction. In terms of complexity, sparsification takes (As"")) and Okk"")) respectively, and reconstruction takes Ok()) where kj == kem" x kqua' for performing the Kronecker product between two vectors of size k-le' and k:qur,, finally sparse projection also takes Ok)), giving an overall time and space complexity of Ok()).
Notation-wise we write FACTGRASS as SJLT MASK SAT"r, where we use @ to indicate that the sparsification is done in factorized manner. The following summarizes the complexity of our proposed methods (GRASS and FACTGRASS), as well as other baselines we have mentioned:
General
Linear Layer
Sparsification
Sparee Projuction
FACYGRANS
(Bascline)
Compression
SILTS
MASR
GAMISA
FILT.
SILT MaSKge sag
GAUSS
Complexity
O1k)
O(K)
O(ub)
O +- Hllapp)
(18) paskyyr
OlyRR) perloyer
In particular, compared to LOGRA, by writing K E [k. as K cki for some blow-up factor
e m FACTGRASS theoretically faster than LOGRA if S Vkipi. or equivalently, S /pi/k, In practice, this is easy to satisfy: for instance, consider linear layer of size = 4096 x 4096 with k 64 64. In this case, for any blow-up factor e < 64, FACTGRASS is faster than LOGRA.
With K' Els M. FACTGRASS overall takes O(k) per compression, same GRASS without ever materializing the full gradient. We summarize both GRASS and FACTGRASS in Theorem 3.2:
Theorem 3.2. There is sub-linear compression algorithm with complexity of O(k') per sample, where& & < << p. Moreover, this extends to linear layers, where gradients are never materialized.
We conclude by noting that much of the recent gradient-based data attribution literature could benefit from per-sample gradient compression, underscoring the broad applicability of our methods.
4 Experiment
In this section, we evaluate the effectiveness of GRASS and FACTGRASS terms of accuracy and efficiency. Specifically, in Section 4.1, we first perform the standard counterfactual evaluations to quantitatively study the data valuation accuracy of GRASS and FACTGRASS on small-scale setups. Then, we scale FACTGRASS to a billion-scale model and billion-token dataset, where we investigate the qualitative accuracy and memorylcompute efficiency in Section 4.2. Further experimental details, such hyperparameters and compute resources, can be found in Section B.I.

---

4.1 Quantitative accuracy via counterfactual evaluation
We assess the quantitative accuracy of data attribution algorithms using the widely adopted linear datamodeling score (LDS) [Park et al., 2023], counterfactual evaluation method. While LDS relies on the additivity assumption, which is known to be imperfect [Hu et al., 2024], it remains a valuable evaluation metric for data attribution. All the quantitative experiments are conducted on one NVIDIA A40 CPU with 48 GB memory, and other details can be found in Section B.2.
GRASS with TRAK. We apply GRASS on one of the SOTA data attribution algorithms (in terms of attribution quality), TRAK [Park et al., 2023], with the implementation from the dattri library [Deng et al., 2024a]. To validate the effectiveness of our sparsification and sparse projection methods, we conduct an ablation study on a simple 3-layer MI. trained on MNIST [LeCun, 1998]. As shown in Table (a)), even standalone Random Mask achieves non-trivial LDS results, while Selective Mask improves the performance further. Additionally, the sparse projection SJLT signifieantly outperforms baselines like FJLT and Gaussian projection in both efficiency and LDS accuracy.
We evaluate GRASS on more complex models: 1.) ResNet9 [He al., 2016] with CI- FAR2 [Krizhevsky and Hinton, 2009], and 2.) Music Transformer [Huang et al., 2019] with MAE- STRO [Hawthorne et al., 2019]. Results in Tables 1(b) and I(c) demonstrate that while sparsification methods are highly efficient, they often fall short in LDS performance. In contrast, sparse projection methods achieve competitive LDS scores but typically incur higher projection costs, though they still outperform the baseline* FJLT by large margin. Notably, GRASS strikes a balance between these extremes, achieving competitive LDS scores at a fraction of the computational cost.
FACTGRASS with Influence Function on Linear Layers. We next evaluate FACTGR ASS with layer-wise block-diagonal FIM influence functions for linear layers. We consider a small language model, GPT2-small [Radford et al., 2019] fine-tuned on the WikiText dataset [Merity et al.. 2016], to enable LDS evaluation. The results are presented Table [dd) where ky indicates the target compression dimension for each linear layer. We further set k/"" h:qut v vki for simplicity. As discussed in Section 3.3.2, replacing the Gaussian projection matrices in LOGRA with SJLT most likely will result in an efficiency degradation, although it achieves a competitive LDS. On the other hand, standalone sparsification achieves competitive LDS results with minimal compression overhead, highlighting its potential as an efficient alternative in overparametrizee models. Finally, FACTGRASS not only maintains the LDS performance of SJLT but also significantly improves computational efficiency, achieving up to 250% speedup over the most efficient SOTA baseline LOGRA.
Table 1: Quantitative evaluation results with different gradient compression methods.
(a) LDS and compression wall-time for MLP with MNIST on TRAK.
Sparsificution
Sparse Projection
Basclines
RM,
SM,
SJLT
FILTs
GAUSSI
A
8192
4008
9182
8192
2048
4056
S192
H192
1DS
0.3903
0.4051
0. 0.1
0.3882
0.4105
0.4375
0.4171
0.4280
0. 4357
0.41.15
0-1359
0.4317
0.1101
0.4253 5.5421
0.5366
Time (6)
0.1517
0.1458
0.00
0.1354
0. 1316
0.14
0-1919
0.5172
0. 1717
0.8907
1.1511
2.1557
5.0800
10.8355
(b) LDS and compression wall time for ResNet9 with CIFAR2 on TRAK.
Spaniiaattee
Spana Prijecion
GRASS
Bonctin
KM.
SMs
SJLT.
SJLT, RM
SILT SMi
FILT,
4156
91/2
3MS
0230
200
5188
2308
4:35
LDS
1.3393
0.4116
844133
g.me
(14023
1-1131
0.409
54425:
144337
GAITL
EL4541
0.4157
0.4407
D. 47473
Tree
(c) LDS and compression wall-time for Transfrrrerr with MAESTRO on TRAK.
Spenilicaies
Syuree Projecion
GRASS
Radiec
RMs
SMs
SILT.
SILT, RMM
SILF, SSM
FILT,
1993
LDS
0.2773
22877
0 3394
3.2055
BOSITS
0.3002
03833
0.383
BL2520
(L252)
IL353T
(L2277
0,0000
D-4013
(d) LDS and compression wall-time for GPT2- small with WikiText on (block- diagonal FIM) influence function.
Spesileadien
Spare Projction
FACTGBAS8
LOGBa (Berchec)
SMuraye 1000
SULT ue TIFT
SULT MMM
SILT, MMaeasee
Y131
100
29
101
1164
37%
LDS
0 1004
1400
0 1240
In 1997
80000
8 1100
0.1984
8.0000
1900
(3080
0.3300 20 36-000
0 1.98
0
Time 01
5.4033
5.3643
sass
1,900)
6.346
333 108-5AM
135.5003
7,466
6-977
73440
6.5710
22-0107
We omit GAUSSE since the projection matrices for these models are too large to fit in the GPU memory.

---

4.2 Scaling up to billion-size model
To evaluate the practical utility of FACTGRASS in attributing fillion-scable models and datasets, we consider Llama-3. 1--m--..--BB-nsse 1-8B-Instruct [Meta AI, 2024] with random IB-token subset of the Open Texn dataset [Gokaslan et al., 2019], and apply FACTGRASS (specifically, SJLTT o R22 a2x7") with layer-wise diigonll FIM influence function for linear layers. The experiment is conducted with one NVIDIA H200 GPU with 96 GB of memory, and more details can be found in Section B.3.
Efficiency. We measure the efficiency through the throughputs for FACTGRASS and LOGRA. Table 2 shows the throughput of 1.) compress steps: compute the projected gradients from inputs and gradients of pre-activation, and the overall 2.) cache stage: compute and save the projected gradients.
We see that FACTGRASS significantly improves com- pute efficiency compared to the previous SOTA, Lo- GRA. In terms of com- pression steps, we achieve a 160% faster throughput compared to LOGRA, which subsequently improves the overall caching throughput by around 17%. We note that the memory usages are similar in both cases: we set the batch to be 7 that maximizes the usage of memory bandwidth for both LOGRA and FACTGRASS.
Table 2: Throughput (tokens per second) for Llama-3. 1-1.-B--- 1-8B-Instruct.
Compress
Cache
4
256
1024
4096
256
1024
4096
LOGRA FACTGRASS
27,292
27. 27.255
26, 26,863
7,307
7,478
7,367
72,218
72, 72,684
73,811
8,584
8,594
8,681
Qualitative Accuracy. We next assess the qualitative alignment between the outputs generated by LLMs and the influential data identified by FACTGRASS with Aą 4096. Since naive influence functions often highlight outlier data (e.g.. error messages, ASCII codes, or repetitive words) with disproportionately high gradient norms [Choe et al., 2024], we filter these cases and select the most contextually relevant samples from the top-10 influential data identified by FACTGRASS. representative example is presented in Figure 9, Given the simple prompt. "To improve data privacy," FACTGRAS ASS identifies a paragraph discussing journalist jailings, including references to privacy policies on various news websites. This content closely aligns with the generated outputs from the model, demonstrating the qualitative accuracy of FACTGRASS in capturing relevant data influences.
To improve data privacy,
Influential Data
To Improve data privacy, the European Union has implemented the General Data Protection Regulation (GDPR)... Data Protection Principles
The fact of registration and authorization of users on Sputrik web- networks indicates
accounts acceptance these rules.
via
sets
data protection principles...
Users are abliged abide by national and international laws, The administration has the right delete comments made in languages other than the language
Lawfulness, faimess, and transparency: Businesses must process
personal data in way that lawful, fair, and transparent. not personal data
majority
websites...
Sterage limitation: Businesses
longer than necessary. ...
violates privacy, distributes personal data of third parties without their consent violates privacy of correspondence;
Data Subject Rights
The GDPR gives individuals range of rights when comes to their
pursues commercial objectives, contains improper advertising
data. These rights include:
lewful political advertisement or links to other online resources
Right to access: Individuols have the right to access their per-
The administration has the right to block a user's accass to the page
sonal data and obtain information about how is being processed.
dillete user's account without notice if the is in violation behavier indicating said violation detected.
Right
Individuals have the right have their personal
If the moderators deem possible ble to restore the account/ /unlock access, it will be done. In the case of repeated violations of the rules account, access cannot
deleted if longer necessary for the purposes for which
It was collected.
above resuting second block
Figure 9: Qualitative accuracy of data attribution with FACTGRASS on Llama-3, 3.1-a--.1-BB-.... --n-tuutt
5 Conclusion
In this paper, proposed GRASS, a novel gradient compression algorithm that leverages the inherent sparsity of par-sample gradients to reduce memory and computational overhead significantly. Building this, we introduced FACTGRASS, variant GRASS that further exploits the gradient structure of linear layers, achieving substantial practical speedups by avoiding ever materializing the full gradient that is both theoretically and practically faster than the previous SOTA baselines.
Our extensive experiments demonstrate that GRASS and FACTGRASS consistently outperform existing approaches in both efficiency and scalability, particularly on billion-scale language models.
10

---

Acknowledgment
This work is supported in part by NAIRR Pilot grant NAIRR240134, WT is partially supported by NSF DMS grant No. 2412853, and HZ was partially supported by an NSF IIS grant No. 2416897, an NSF CAREER Award No. 2442290 and Google Research Scholar Award. We also thank Xueshen Liu from the University of Michigan for his invaluable discussion in improving the efficiency of our library's 's practical implementation. The views and conclusions expressed herein are those of the authors and do not necessarily reflect the official policies or positions of the supporting companies or government agencies.
Broader impacts
This paper presents work whose goal is advance the efficiency of data attribution algorithms. As there are many socially important applications of data attribution, with the fact that the present SOTA reliable data attribution methods do not scale well to commercial-size LLMs, there are many potential societal consequences of our work. However, none of which we feel must be specifically highlighted here.
References
N. Agarwal, B. Bullins, and E. Hazan. Second-order stochastic optimization for machine learning in linear time. Journal of Machine Learning Research, 18(116):1 100,,,14000000 2017.
N. Ailon and B. Chazelle. The fast johnson-lindeestraus transform and approximate nearest neighbors, SIAM Journal on computing, 39(1):302-322, 2009.
A. F. Aji and K. Heafield. Sparse communication for distributed gradient descent. In M. Palmer, R. Hwa, and S. Riedel, editors, Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 440-445, Copenhagen, Denmark, Sept. 2017. Association for Computational Linguistics. doi: 10.18853/11/D11-10060 URL httths//acllaatthollll
org/
1045/
W. E. Amoldi. The principle of minimized iterations in the solution of the matrix eigenvalue problem. Quarterly of applied mathematies, 9(1):17-22 1951.
G. Charpiat, N. Girard, L. Felardos, and Y. Tarabalka. Input similarity from the neural network perspective. Advances in Neural Information Processing Systems, 32, 2019.
H. Chen, S. F. Sultan, Y. Tian, M. Chen, and S. Skiena. Fast and accurate network embeddings via very sparse random projection. In Proceedings of the 28th ACM international conference on information and knowledge management, pages 399-408, 2019.
S. K. Choe, H. Ahn, J. Bae, K. Zhao, M. Kang, Y. Chung, A. Pratapa, W. Neiswanger, E, Strubell, T. Mitamura, al. What is your data worth gpt? I1m-scale data valuation with influence functions. arXiv preprint 21t.::2000.115544 2024.
A. Dasgupta, R. Kumar, and T. Sarlós. A sparse johnson: Lindenstrauss transform. In Proceedings of the forty- ACM symposium on Theory of computing, pages 341-350, 2010.
J. Deng, T.-W. Li, S. Zhang, S. Liu, Y. Pan, H. Huang, X. Wang, P. Hu, X. Zhang, and J. Ma. dattri: A library for efficient data attribution. Advances in Neural Information Processing Systems, 37: 136763-13678,, 2024a.
J. Deng, S. Zhang, and J. Ma. Computational copyright: Towards royalty model for music generative ai, 2024b. URL https: :/ap/vv////ii..a/// org/ abs/ 06646.
J. Deng, Y. Hu, P. Hu, T.-W. Li, S. Liu, J. T. Wang, D. Ley. Q. Dai, B. Huang, J. Huang, C. Jiao, H. A. Just, Y. Pan, J. Shen, Y. Tu, W. Wang, X. Wang. S. Zhang. S. Zhang, R. Jia, H. Lakkaraju, H. Peng, W. Tang, C. Xiong, J. Zhao, H. Tong, H. Zhao, and J. W. Ma. A survey of data attribution: Methods, applications, and evaluation in the era of generative ai. SSRN, 2025. doi: 39..1/99//...5550005 Available at SSRN: https:/ /ssrn com wtt.abstrractt545515555555

---

O. N. Fandina, M. M. Høgsgaard, and K. G. Larsen. The fast johnson-lindenstrauss transform is faster. In International Conference on Machine Learning, pages 9689-9715. PMLR, 2023.
R. Fisher. On the mathematical foundations of theoretical statistics. Philosophical transactions of the Royal Society of London. Series A, containing papers of mathematical or physical character, (11594-6044:3993 -688, 1922.
J. Frankle and M. Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019. URL httpss: net/ Derum?id==:1-b3RRtt
A. Gokaslan, V. Cohen, E. Pavlick, and S. Tellex. Openwebtext corpus. http://Skyliono07, github. hot.pppeeeeeeteeeoorppeeee 2019.
R. Grosse, J. Bae, C. Anil, N. Elhage, A. Tamkin, A. Tajdini, B. Steiner, D. Li, E. Durmus, E. Perez, et al. Studying large language model generalization with influence functions. arXiv preprint (rxiv:2308.03296, 2023.
Z. Hammoudeh and D. Lowd. Training data influence analysis and estimation: A survey. Machine Learning, 11355)2351-2444 2024.
S. Han, H. Mao, and W. J. Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. International Conference on Learning Representations (ICLR), 2016.
S. Hara, A. Nitanda, and T. Machara. Data cleansing for models trained with sgd. In Wallach, Larochelle, Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, ed- itors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https::/proceeddeee 5f 11161166664404100000000000004444
neurips. wtt.pppr.ccppppppppppeeppppeeee filerffiee/pppeeee haaperr_fllssppppr////////// /aper//0199/f1l/ .df.
C. Hawthorne, A. Stasyuk, A. Roberts, I. Simon, C.-Z. A. Huang, S. Dieleman, E. Elsen, J. Engel, and D. Eck. Enabling factorized piano music modeling and generation with the MAESTRO dataset. In International Conference on Learning Representations, 2019. URL htt.::ttt////// httpps://pparreview.rr net/ forum? forum?id=rine 1dr
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
Y. He, Y. Hu, Y. Lin, T. Zhang, and H. Zhao. Localizo-and-stice Efficient model merging via sparse task arithmetic. Transactions on Machine Learning Research, 2025. ISSN 2835-8856. URL https: openreviev sett/forumidd-gCUUBe
Y. Hu, P. Hu, H. Zhao, and J. Ma. Most influential subset selection: Challenges, promises, and beyond. Advances in Neural Information Processing Systems, 37:1 19711-1978888888 2024.
C.-Z. A. Huang, A. Vaswani, J. Uszkoreit, I. Simon, C. Hawthorne, N. Shazeer, A. M. Dai, M. D. Hoffman, M. Dinculescu, and D. Eck. Music transformer. International Conference on Learning Representations, 2019. URL https: http:::://////////eeeeee wwtpeeewwwww.eeeeeeeeeeeeeeeeeee met/foorumidd
W. B. Johnson. Extensions of lipshitz mapping into hilbert space. In Conference modern analysis and probability, 1984, pages 189-206. 1984.
D. M. Kane and J. Nelson. Sparser jowsson-lindenstraane transforms. Journal of the ACM (JACM), 61(1):1-23, 2014.
W. Koh and P. Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, pages 1885-1894, PMLR, 2017.
A. Krizhevsky and Hinton. Learning multiple layers of features from tiny images. Master's thesis, Department of Computer Science, University of Toronto, 2009.
12

---

Y. Kwon, E. Wu, K. Wu, and J. 7ou. Datainf: Efficiently estimating data influence in loRA-tuned L.Ms and diffusion models. In The Twelfth International Conference on Learning Representations, 2024. URL
Y. LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mnist/, 1998.
P. Li and X. Li. Oporp:
One permutation+ one random projection. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1303-1315, 2023.
H. Lin, Long, Xu, and W. Zhao. Token-wise influential training data retrieval for large language models. In L.-W. Ku, A. Martins, and V. Srikumar, editors, Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 841-860, Bangkok, Thailand, Aug. 2024. Association for Computational Linguistics. doi: 10.18653/v1/2024. 10.1865/.1122224.doooog4448 URL https: https::/aclaatttolliii// acl.atoootntoyyyyooooooo org/ org/2024. acl -lngg. 48/.
Y. Lin, S. Han, H. Mao, Y. Wang, and W. Dally. Deep Gradient Compression: Reducing the communication bandwidth for distributed training. In The International Conference Learning Representations, 2018.
Liu, X. Huang, Y. Chen, and A. Suykens. Random features for kernel approximation: survey on algorithms, theory, and beyond. IEEE Transactions Pattern Analysis and Machine Intelligence, 44( (4(100:7128-7111 2021.
I. Loshchilov and Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019.
M. W. Mahoney. Lecture notes randomized linear algebra. arXiv preprint 10X.v:6608.044000 2016.
Martens and R. Grosse. Optimizing neural networks with kronecker- factorrd approximate curvature. In F. Bach and D. Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 2408 2417, Lille, France, 07-09 Jul 2015. PMLR. URL https: h //pp/ceeeede...../////// mlr www.ppressvvr martens15.. html.
Merity, Xiong, Bradbury, and Socher. Pointer sentinel mixture models, 2016.
Meta AI Introducing meta Ilama The most capable openly available I1m date, April 2024. URL https:/ //ii meta. cow/ bbtg//etaaammmeeeeee//eeeea 1lama-3/. Accessed: 2025-05-13.
V. Nair and G. E. Hinton. Rectified linear units improve restricted boltzmann machines. In Pro- ceedings of the 27th international conference on machine learning (ICML-I0), pages 807-814, 2010.
S. M. Park, K. Georgiev, A. Ilyas, G. Leclerc, and A. Madry. Trak: Attributing model behavior at scale. In International Conference Machine Learning, pages 27074-27113, PMLR, 2023.
G. Pruthi, F. Liu, S. Kale, and M. Sundararajan. Estimating training data influence by tracing gradient descent. Advances in Neural Information Processing Systems, 33: 19919900-199300 2020.
A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I. Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8)9, 2019.
A. Schioppa. Efficient sketches for training data attribution and studying the loss landscape. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL htttp:://operrvvieee net/forum? wwwtoorrunniiiddieoeeeeeeee jdR8jy
A. Schioppa, P. Zablotskaia, D. Vilar, and A. Sokolov. Scaling influence functions. Proceedings of the AAAI Conference on Artificial Intelligence, 179-8)8817788886 Jun. 2022. doi: 10. 1609/aaaa. v3698.20791. URL https: htapp:///je //ojs. aaai. org/ index.ndxiiii php/ AAAI/article httpa/////v.eee//11...//
13

---

T. Wang, D. Song, J. Zou, P. Mittal, and R. Jia. Capturing the temporal dependence of training data inftuence. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openrevie
htt//torurriiceeutllgggg.....
M. Wojnowicz, B. Cruz, X. Zhao, B. Wallace, M. Wolff, J. Luan, and C. Crable. "influence sketching": Finding influential samples in large-scale regressions. In 2016 IEEE International Conference Big Data (Big Data), pages 3601-3612. IEEE, 2016.
D. Woodruff et al. Sketching tool for numerical linear algebra. Foundations and Trendy@ in Theoretical Computer Science, 10(1-2):1-157, 2014.
Z. Zhang, P. Cui, H. Li, X. Wang, and W. Zhu. Billion-scale network embedding with iterative random projection. In 2018 IEEE international conference on data mining (ICDM), pages 787-796. IEEE, 2018.
14

---

A Omitted details from Section 2
A.1 Related work
This section provides an in-depth discussion of gradient- based data attribution methods and their computational advancements, offering holistic view of the field. For more complete overview of other data attribution methods and their applications, we refer interested readers to the recent survey [Deng et al., 2025].
A.1.1 Gradient-based data attribution
Gradient-based data attribution methods represent a major category for quantifying the impact of individual training samples on a model's behavior [Deng et al., 2025]. These techniques operate under the principle of using the model's local sensitivity-capurre by the per-sample gradient with respect to model parameters-to infer how a training example contributes to model predictions or loss values.
The most influential and widely studied approach in this category is the inffuence function [Koh and Liang, 2017]. Rooted in robust statistics, the influence function provides computationally efficient, first-order approximation of the expensive leave-one-out (I.OO) retraining scenario. The core idea to estimate the change in target function (such the loss the removal of a training sample perturbs the final model parameters. This estimation involves the per-sample gradient and the inverse Hessian matrix. Recent advancements, such TRAK [Park et al., 2023], have been developed to improve on this classical framework.
point) by calculating how
Another family of gradient-based techniques called training dynamic methods has become popular due to its ability to adapt to complex training scenarios that might break the influence function assumptions. These include TracIn [Pruthi et al., 2020], SGD-Influence [Hara al., 2019], and, more recently, data value embedding [Wang et al., 2025]. They analyze how training samples dynamically affect model behavior across intermediate checkpoints of the training trajectory, making them well- suited for non-convex settings where the classical influence function approximations may be less accurate.
All gradient- based methods ultimately rely on similar low-level computations- most notably the inverse Hessian-vector product (iHVP)-which makes the influence function representative example for discussion.
A.1.2 Scaling up gradient-based data attribution
The literature on scaling up gradient-based data attribution methods, or more specifically, iHVP computation, is extensive. In Section 2, we provided detailed discussion of the RANDOM method, including various random projection techniques. Additionally, in Section 3.3.2, we briefly covered block-diagonal layer-wist wise independence approximations of the Fisher information matrix (FIM), which together represent the most popular state-of-the-ee in efficient approximations of iHVP. Here, we expand on this discussion by providing additional pointers to the broader literature on random projection and sketching for gradient compression, as well as alternative approaches to scaling up iHVP. This context helps clarify the positioning of our proposed methods within the larger landscape of scalable gradient-bai based data attribution research, offering a more complete understanding of the field.
Sketching and RANDOM. Random projection, or sketching, a well-studied technique for di- mensionality reduction, widely explored in both theoretical computer science [Woodruff et al., 2014, Mahoney, 2016] 6] and machine lcarning [Zhang et al., 2018, Liu et al., 2021, Chen et al., 2019, Li and Li, 2023]. In the context of gradient compression, sketching plays critical role in distributed training, where the overhead of communicating full gradients can be a major bottleneck [Lin et al., 2018, Aji and Heafield, 2017]. However, direct sketching is often avoided in this context, as it can destroy important gradient information for the exact parameter correspondence of the gradient. Instead, techniques like random dropout, which selectively transmit parts of the gradient while preserving critical information, are more common. This is closely related to the Random Mask approach discussed in Section 3.2.
With the rise of gradient-based attribution methods, gradient compression has also become relevant for data attribution [Schioppa, 2024, Lin et al., 2024, Choe et al., 2024]. Among these. Schioppa
15

---

[2024] approaches gradient compression from theoretical sketching perspective, refining traditional methods like the fast Johnson- Linnnonn-indeestrauus transform (FJI.T) [Ailon and Chazelle, 2009, Fandina al., 2023] improve computational efficiency on modern machine learning hardware such as TPUs. Notably, only Choe et al. [2024] specifically considers the structural properties of gradients when designing compression methods, potentially offering more accurate reconstructions with reduced communication cost.
Input-Output Independence. Two notable extensions of the block-diagonal approximation for empirical Hessians have emerged recently and can be further integrated with RANDOM. The first, Ktonecker-Factoree Approximate Curvature (K-FAC) [Martens and Grosse, 2015], leverages the Kronecker-factor structure of linear layers (same as Eq. (2)) by assuming independence between the inputs and the pre-activation gradients. This independent factorization significantly reduces the computational burden of Hessian approximations, as inverse FIM-vector product (iFVP) now only requires two smaller inversions of the factorized matrices. Compared to LOGRA, where the projected gradients and FIM are materialized at the end with the FIM of size k.2, K-FAC now only materializes two smaller projected inputs and gradients of the prevactivasions and their corresponding covariances. The latter covariances are of size roughly vk: x Vk, further reducing the matrix inversion computation.
Building on this, Eigenvalue-corre by correcting the cigenvalues of the factorized covariances, improving approximation quality without compromising efficiency. However, note that while EK-FAC enhances the accuracy of K-FAC, it does not offer further computational speedups.
K-FAC (EK-FAC) [Grosse et al., 2023] refines this approach
Direct iHVP. An alternative approach to scaling influence functions involves directly estimating the iHVP without explicitly forming or inverting the full Hessian. Unlike the two-stage methods discussed in Section 2, which approximate the full Hessian first and then compute iHVP for each training sample, this direct approach aims to bypass the costly inversion step. providing a more scalable solution for large-scale models.
One such algorithm is LiSSA [Agarwal al., 2017], initially developed for stochastic optimization and later adapted for influence function calculations [Koh and Liang, 20. It approximates iHVP through iterative stochastic updates that only involve Hessian-vector product, which is efficient to compute. While straightforward this method requires careful tuning of its hyperparameters to balance accuracy and runtime.
More recently, DataInf [Kwon et al., 2024] introduced less conventional approach by reordering the sequence of matrix operations in the iHVP calculation. This method effectively swaps the expectation and inversion steps, allowing per-sample gradient information to approximate the inverse directly. However, this strategy tightly couples the iHVP estimation with the influence calculation, making challenging to efficiently scale to large datasets, as it requires full computation for each training and test sample pair.
A.2 A note on Boonson--Lindensteeee lemma
While the
lemma [Johnson, 1984] ensures that the pair-wise distance, and hence the inner products, between gradients are approximately preserved under random i.i.d. projec- tion, if P is not injective when restricted to the range of Fj. i.c., the column rank is not kept, then F3 applied to vectors in this subspace can generate significant components orthogonal to the subspace. In this case, the projected FIM PF, PT implicitly neglects these orthogonal components, which leads directly to approximation errors [Schioppa et al., 2022]. Several potential strategies to mitigate this issue have been explored, focusing on how to construct the projection matrix P. One popular strategy is to first approximate the top-k eigenvectors of F3 using classical algorithms such as PCA [Choe al., 2024] and Arnoldi iteration [Schioppa et al., 2022, Arnoldi, 1951], then used the found top-k eigenvectors as the rows of P.
B Omitted details from Section 4
In this section, we provide further experimental details that we omitted in Section 4.
16

---

B.1 Details of models, datasets, and computing resources
We summarize all the models and datasets used the experiments in Table 3.
Table 3: Model details used in the experiments.
Models
Datasets tteeese
Task
Parameter Size
Train Samples
Test Samples
Sequential Length
MNIST 3.)
Image
ResNer9
CIFAR2 sim
Image ClassiScattion
4.53M
5,000
500
Music Transformer
MAESTRO voc B5-NC-A 4m
Music Generation
13.3M
5,000
178
GPTZ-mmll
WikiTest sY-S4
Text Generation
124M
4,656
481
512
OpenWehTeest
Text Genneratio
8B
976,562
1024
All the experiments in quantitative analysis are conducted on Intel (R) Xeon (R) Gold 6338 CPU @ 2. O0GHz with single Nvidia A40 GPU with 48 GB memory. On the other hand, the qualitative analysis experiment is conducted on the VISTA cluster with one Grace Hopper (GH) node, where each GH node has one H200 GPU with 96 GB of HBM3 memory and one Grace CPU with 116 GB of L.DDR memory.
B.2 Details of quantitative analysis
Model Training. For MLP, ResNet9, and Music Transformer, we utilize pretrained models from the dattri library [Deng et al., 2024a, Appendix CJ. For GPT2-small, we fine-tune the model on the WikiText dataset using the AdamW optimizer [Loshchilov and Hutter, 2019] with a learning rate of 5 x 10 and weight decay, training for epochs.
Linear Datamodeling Score (LDS). We measure LDS using 50 data subsets, each containing half of the original training set. For each subset, models are trained independently using the hyperparameters described above. For more comprchensive explanation the LDS evaluation, we refer readers to Park et al. [2023].
Data Attribution. For MLP MNIST, ResNet9 on CIFAR2, and Music Transformer MAE- STRO, we use TRAK [Park et al., 2023] with 10, 10, and independently trained checkpoints, respectively, as the backbone data attribution algorithm to evaluate different gradient compression methods. For GPT2-small fine-tuned on Wiki'Text, we employ layer-wise block-diagonal FIM approximation for linear layers the backbone data attribution method.
We remark that one of the important hyperparameters that requires careful attention the damp- ing term used for the Hessian/FIM inverse. We pick the damping À for each setting (each modee//atasetcommprssion method combination) via cross-validation grid search for LDS over A {10-7, 10-6 10-5 10-1, 10-3, 10-2, 10-10011100 1, 10, 102) on 10% of the test dataset, and evalu- ate the overall LDS result on the remaining 90% of the test dataset.
B.3 Details of qualitative analysis
Model and Dataset. For Llama-3. 1.tea....------- I-strutttt we directly load the pretrained model without fine-tuning. As for the attribution dataset, while we do not have access the massive 15T-token pre-training dataset used by Llama-3. 1-8--------nnstruct we anticipate that it will contain most of the OpenWebText dataset due to its high quality and popularity.
B.4 Practical implementation
Finally, we provide some remarks on the practical implementation of our proposed algorithms.
B.4.1 SJLT implementation
naive implementation of SJLT is straightforward: we first sample random indices cor- responding to each input dimension along with their associated signs, and then perform torch. Tensor index_add, () operation, which carries out the core computation of SJLT (Fig- ure 2). This operation implicitly uses atomic addition, which can lead to race conditions and slow
'See https:///dcc tacc. utexas edu/hpc/vista/.
17

---

down computation when the parallelization is not done carefully and the target compression dimension is small relative to the input dimension p."
In contrast, our CUDA kernel implementation adopts key optimization: parallelize the computa- tion by dividing the input dimension across different threads. This strategy reduces race conditions caused by atomic additions at each step.
B.4.2 Selective Mask
We discuss several practical considerations and tips for solving Eq. (1) in the context of Selective Mask.
Ensuring Exact k. Since the sparsity of the mask arises from & regularization, it generally not possible to guarantee that the final 5* contains exactly k active indices (i.e., entries greater than 0.5). simple workaround is to select the top-k indices based on their sigmoid values-i.e, adaptively setting the activation threshold to ensure exactly & active indices. However, this method may yield suboptimal masks the resulting values are far from binary, potentially degrading performance.
To address this issue, we increase the regularization strength and introduce an inverse-temperature term by replacing S with S/T, where I decreases as training progresses. As T approaches zero, (S/T)) becomes more binary-like, promoting a "hard" mask. That said, empirical results show that careful tuning of the regularization parameter combined with top-k selection, can yield performance comparable to the inverse- temperature approach.
Linear Layer. For linear layers, we derive factorized Selective Mask by decomposing the gradients according to (2). Specifically, following the notation established in Section 3.3.2, for reformulate Eq.
the 1th linear layer,
arg max Exce corr (((=)) @
in out 2i, les, Besat,
(12)))
2o0r 1)
test
S SPER
"""
A(Ila(st))11 + (((t)) (1),
out where 2!,, E R denotes the input feature of the 1th linear layer from 2,, Li_ E R denotes the
gradient of its pre-activation of the hth linear layer, and an o (ST") O 2 20u1 o (S O 2j
the (soft- maaked variants. Computationally, we leverage the Kronecker product structure to simplify inner product calculations; for example:
(2
@
out _in Ri " @ out
= (2]]) >le,,)) (2 out
As result, training with the Selective Mask does not require computing full layer-wise gradients, providing similar computational and memory efficiency as in FACTGRASS.
'A significant slowdown was previously observed when was extremely small, e.g., k = 32. However, with recent updates to PyTorch, this issue has been resolved, leading to consistent runtimes across different values of k. shown in Figure 4.
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main efficiency claim is justified both theoretically in Section 3.3 and empirically in Section 4.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The limitations of one of the proposed methods, GRASS is discussed in detail in Section 3.3.2 (with solution), and the contribution's 's (SJLT CUDA kernel) limitation is also discussed in Section 3.1.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well well-specification asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
19

---

Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
All the computational complexity claims are carefully proven and explained.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification; Yes. All the important hyperparameters that can be used reproduce the results are provided, together with highly optimized implementations for each of the baselines in the source code.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
20

---

5. Open access to data and code
Question: Does the paper provide open the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All the code, environment, and the setup guidelines that are required to reproduce the results are provided.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttps://nips.c cc/ public/ cublic/guides//// Seaeee//Coeuuumisseeeee
oolicyyyyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips cc/pccpppuoo http//ullcc//ae tttp///ww/eeeeeeeecccccce Sttplee///ooSSSemmmeeeeme wttsssubmmiiioooooooooooooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have included detailed setup of the model training in Section B, though not crucial to understand the contribution of the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Our main qualitative evaluation experiments on LDS are expensive to run; hence, currently, the confidence intervals for LDS are lacking. However, in terms of the main contribution. runtime is calculated over a long run (across the entire experiment), and hence we believe it is accurate enough and justifies the significance.
Guidelines:
The answer NA means that the paper does not include experiments.
21

---

The authors should answer "Yes" if the results accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative eπror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The information on the computer resources is reported in Section B.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https::/ h/tppr///////rpp//// wttpppp...pppbllae cctppblic//etteeeceeceecceeeeeet ctt.a///eehcccileelllellelle
Answer: [Yes]
Justification: Every author of this submission has reviewed the code of ethics guidelines and confirms compliance.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Broader impacts is discussed after Section 5 as additional material.
22

---

Guidelines:
The answer NA means that there is societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [Yes]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We properly cite the datasets and include their licenses in Section B.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
23

---

For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the thcode. com datasets package should be provided. For popular datasets, pacorewithcode
has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
24

---

Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality the research, declaration is not required.
Answer: [NA]
Justification:
The core method development does not involve any usage of LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to LLM policy http://uuii.cc//ooeeeeeeeeeeeeee for what should or should not be described.
25


Reviews:
[{"review_id": "AkV8VeUZrw", "reviewer": "Reviewer_HgYa", "summary": "The paper proposes to leverage the per-sample gradient sparsity inherit in neural networks with relu activations to speed up influence function computation.  In particular, the sparse JL lemma is leveraged to accelerate random projections to take advantage of the sparsity.  Furthermore, additional extensions are proposed: 1) the parameters are first further sparsified via a one-time optimization problem 2) extending Logra, the input activation and output gradients in linear layers are sparsified, and a similar approach is applied to their respective Kronecker product for computational speedup.  The resulting method is able to achieve up to 165% speedup over Logra on Llama-3.1-8b-instruct.", "questions": "- is it possible to perform some quantitative analysis of FactGrass for the 8B model beyond throughput?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths\n- the paper proposes a novel core idea - leveraging / introducing parameter sparsity to speedup influence function computations.  this idea could likely be extended to other problems involving per-sample gradient compression\n- the experiments show show significant speedup over Logra on billion-parameter models\n\nWeaknesses,\n- analysis focuses only on 1 billion-parameter model, unlike Logra (which considered 3), though this is understandable given computational resources.", "was_revised": true, "final_justification": "The discussion did not lead to new points which would change my rating.", "rebuttal": "We sincerely thank Reviewer HgYa for taking the time to review our paper and for their constructive feedback and recognition of our proposed algorithm and its potential impact. Below, we provide point-to-point responses to the questions and concerns raised.\n> Only 1 billion-scale model in empirical analysis.\n\nDue to computational constraints, we focused our quantitative analysis on smaller models and efficiency analysis on an 8B-parameter model. It is worth noting that our experimental setup follows closely to the previous state-of-the-art [1]. Specifically, for efficiency analysis, we highlight that:\n1. The efficiency analysis is conducted on the 8B model, the largest model [1] considered.\n2. The observed speedup is robust and model-agnostic, as supported both by our computational complexity analysis (independent of model) as well as the empirical evidence (up to overall 165% throughput speed up).\n\nHence, we believe the quantitative analysis results, as well as efficiency results for 8B model, provide a representative and reliable demonstration of the efficacy.\n\n> Possibility to perform quantitative analysis for 8B model beyond throughput.\n\nWe agree that it would be valuable to include additional quantitative analysis beyond throughput. However, computing common metrics such as LDS at the 8B scale is prohibitively expensive in terms of time and memory. This limitation is well recognized in prior work [1], which similarly did not include such measurements at this scale due to the prohibitively high computational cost.\n\n**Reference**\n\n[1]: What is Your Data Worth to GPT? LLM-Scale Data Valuation with Influence Functions"}, {"review_id": "6Iwds69Msr", "reviewer": "Reviewer_49cd", "summary": "This paper proposes GRASS, a new gradient compression method to make influence functions faster and more memory-efficient for large neural networks with sparsification and projection.", "questions": "Q1. Can the authors provide a direct quantitative comparison between GRASS/FACTGRASS and RapidIn (Lin et al., 2024) on common benchmarks?\n\nQ2. Can the authors add quantitative accuracy evaluation (such as LDS or other metrics) for the billion-scale model instead of only reporting speed and one qualitative example?\n\nQ3. Can the authors analyze how the Selective Mask is chosen and whether its stability or importance affects the attribution results?\n\nQ4. Can the authors include experiments or analysis showing how sensitive GRASS/FACTGRASS is to key hyperparameters like k and k'?\n\nQ5. Can the authors explain or empirically study why random masking leads to lower accuracy and in what situations it is still a good choice?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strong Points\n----\nS1. The paper tackles the important problem of scaling influence functions to very large models.\n\nS2. Combining gradient sparsity and sparse projection is a novel way to speed the influence function computation.\n\nWeak Points\n----\nW1. The paper mentions RapidIn (Lin et al., 2024), which also uses random projection, but does not include a direct experimental comparison or discussion of pros and cons versus RapidIn.\n\nW2. The experiments focus on only a few models, especially only one billion-scale model.\n\nW3. The importance and stability of mask selection in Selective Mask is not analyzed much.\n\nW4. The effect of different hyperparameter settings (like k and k') is not fully explored.\n\nW5. Random masking loses accuracy compared to other methods.\n\nW6. For the billion-scale model, the paper reports only speed and a single qualitative example, but does not provide any quantitative evaluation of data attribution accuracy.", "was_revised": true, "final_justification": "The additional experiment shows the comparison with more baselines and I have raised the score.", "rebuttal": "We sincerely thank Reviewer 49cd for taking the time to review our paper and for their constructive feedback. Below, we provide point-to-point responses to the questions, hopefully addressing the concerns raised.\n\n> Comparison with RapidIn.\n\nWe appreciate the reviewer’s suggestion to include a more direct comparison with RapidIn. Here, we provide a detailed discussion and empirical comparison that we will also integrate into the next version.\n\n **Theoretical Complexity**: In terms of computational complexity, the core RapidIn’s gradient compression method requires $O(\\lambda p)$, where $\\lambda$ is a hyperparameter that is of order $20$ to $100$, and $p$ is the model size. Compared to our proposed methods, which require only $O(k’)$ computational time for some $k < k’ \\ll p$, we argue that our methods outperform RapidIn significantly.\n\n**Empirical Comparison**: As the actual runtime of each method highly depends on the specific implementation, it is tricky to compare different methods. Nevertheless, we run the official implementation of RapidIn to compare. Below are the results using RapidIn’s public codebase and default hyperparameters ($\\lambda = 20$):\n\n*MLP+MNIST (RapidIn)*:\n\n* $k$=2048: LDS=0.1529, Time=4.5928\n* $k$=4096: LDS=0.1547, Time=4.6150\n* $k$=8192: LDS=0.1554, Time=4.7306\n\n*ResNet9+CIFAR2 (RapidIn)*:\n\n* k=2048: LDS=0.0234, Time=16.6967\n* k=4096: LDS=0.0235, Time=16.7008\n* k=8192: LDS=0.0223, Time=16.7235\n\n*MusicTransformer+MAESTRO (RapidIn)*:\n\n* $k$=2048: LDS=0.1268, Time=43.1692\n* $k$=4096: LDS=0.1338, Time=43.2024\n* $k$=8192: LDS=0.1432, Time=43.1993\n\nCompared to **Table 1** in our paper, our methods consistently achieve significantly lower projection times, often by several orders of magnitude, while yielding higher LDS values. We again note that the comparison has some caveats: first, our compression algorithms are implemented with a CUDA kernel, while theirs use only high-level PyTorch APIs; second, RapidIn is different from TRAK used in the paper: the former only requires one model checkpoint, while TRAK requires several (5~10) models ensemble, and the reported wall time is the total projection time for each attribution method. Besides all these caveats, we highlight that the *CUDA kernel implementation is also a key contribution of this work*, and it requires non-trivial efforts to implement a CUDA-kernel-equivalent algorithm for RapidIn.\n\n> Experiments focus on only a few models and only one billion-scale model.\n\nWe respectfully clarify that our experimental setup includes **five** different models, each evaluated on a distinct dataset, covering a diverse range of architectures and domains. For the billion-scale setting, we adopt the largest experimental configuration used in LoGra [1], which serves as a strong benchmark for evaluating attribution methods at scale. We believe this setup sufficiently demonstrates the efficiency and scalability of our proposed methods relative to the current state-of-the-art.\n\n> Stability and implementation of Selective Mask.\n\nWe address the two questions below, respectively:\n\n**Choosing Selective Mask**: The procedure for learning the Selective Mask is described in **Section 3.2.2**. Here, we provide additional implementation details and clarifications that were omitted from the main text due to space constraints:\n* *Forcing exact $k$*: A naive optimization for Selective Mask can not guarantee that the final $S^{\\ast}$ contains exactly $k$ active indices. A simple workaround is to select the top-$k$ indices based on their sigmoid values, which corresponds to adaptively setting the activation threshold to ensure exactly $k$ active indices.\n* *Linear Layer*: For linear layers, we can derive a **factorized** Selective Mask by decomposing the mask w.r.t. the gradients factorization, according to **Eq. 2**. Specifically, one can reformulate **Eq. 1** and leverage the Kronecker product structure to simplify inner product calculations. As a result, training Selective Mask does not require computing full layer-wise gradients, providing similar computational and memory efficiency as in FactGraSS. This additional discussion will be included in the next version.\n\n**Stability**: We refer to the ablation studies in **Table 1** (specifically the standalone Selective Mask (SM) columns), where we evaluate SM across multiple settings and varying target projection dimensions. The results demonstrate that SM is stable across runs and consistently outperforms the baseline Random Mask in terms of LDS, highlighting its effectiveness and robustness. Furthermore, we conducted additional ablation studies to assess the sensitivity and impact of using the Selective Mask alone as a gradient compression method on attribution results. Below, we report the *mean* LDS and the *standard error of the mean* across five different random seeds:\n\n*MLP+MNIST (TRAK with SM)*:\n\n* $k$=2048: LDS=0.3924 (±0.0030)\n* $k$=4096: LDS=0.4192 (±0.0034)\n* $k$=8192: LDS=0.4274 (±0.0032)\n\n*ResNet9+CIFAR2 (TRAK with SM)*:\n\n* $k$=2048: LDS=0.3733 (±0.0071)\n* $k$=4096: LDS=0.4072 (±0.0028)\n* $k$=8192: LDS=0.4326 (±0.0037)\n\n*MusicTransformer+MAESTRO (TRAK with SM)*:\n* $k$=2048: LDS=0.1470 (±0.0030)\n* $k$=4096: LDS=0.1628 (±0.0039)\n* $k$=8192: LDS=0.1651 (±0.0033)\n\nThis consistent LDS performance demonstrates the stability of the Selective Mask.\n\n> Add quantitative accuracy evaluation for billion-scale models beyond throughput.\n\nWe agree that it would be valuable to include additional quantitative analysis beyond throughput. However, computing common metrics such as LDS at the 8B scale is prohibitively expensive in terms of time and memory. This limitation is well recognized in prior work [1], which similarly did not include such measurements at this scale due to the prohibitively high computational cost. Our experimental setup follows closely with [1], aligning with the literature.\n\n> Sensitivity of GraSS/FactGraSS to key hyperparameters like $k$ and $k’$.\n\nWe have addressed the sensitivity of GraSS/FactGraSS to the hyperparameters $k$ and $k’$,  by the experiments in **Section 4** of our paper. In these experiments, we consider three different target compression dimensions across various settings, including billion-scale models and datasets. The consistent performance trend observed across these values demonstrates the robustness of our approach to reasonable variations of compression dimensions.  Additionally, as discussed in **Lines 271**-**272**, we don't include results for larger values of $k$ and $k′$ because increasing $k$ leads to a quadratic complexity blow-up. This would require storing and inverting a matrix that far exceeds our available GPU memory resources. This practical limitation prevents further exploration of such extreme ranges.\n\nIn terms of other hyperparameters, we follow the same settings as in [3] to align with the literature.\n\n> Why does Random Mask lead to lower accuracy, and when is it effective?\n\nRandom Masking, along with Selective Masking and SJLT, serves as a component within our proposed algorithm's pipeline. The experiments involving Random Masking are primarily designed as ablation studies to facilitate comparisons with other algorithmic components and our final proposed methods.\n\nOn the other hand, while Random Masking may lead to lower accuracy compared to more sophisticated compression techniques, its key advantage lies in its exceptional efficiency. This makes it the most efficient compression method within the pipeline. Consequently, its inclusion provides a valuable option for scenarios where a trade-off favoring computational efficiency over maximal accuracy is acceptable or necessary.\n\n**References**\n\n[1]: What is Your Data Worth to GPT? LLM-Scale Data Valuation with Influence Functions\n\n[2]: TRAK: Attributing Model Behavior at Scale\n\n[3]: 𝚍𝚊𝚝𝚝𝚛𝚒 : A Library for Efficient Data Attribution"}, {"review_id": "gvVdttAiwm", "reviewer": "Reviewer_SuDq", "summary": "This paper addresses the problem of scalable, gradient-based data attribution. Influence functions, commonly used for scoring the importance of samples in a dataset, require computing a (inverse) Hessian-gradient product, which is extremely costly for very large models. The authors propose two novel methods, GRASS and FACTGRASS. GRASS sparsifies the gradients using their proposed \"selective mask\" technique, after which they apply the sparse Johnson-Lindenstrauss transform. FACTGRASS enables the use of the compression technique via an interesting modification of the LoGRA technique applied to layerwise sparsified gradients of linear layers. The proposed data attribution techniques are evaluated with the LDS benchmark on million scale models and simple vision/music datasets, as well as on Llama3-8B models using the OpenWebText dataset, showing improved efficiency of computation over current methods.", "questions": "I have the following questions:\n\n* How does the gradient sparsification impact the accuracy of the influence function based attribution? That is, given a dataset, can you discuss how the GRASS/FactGRASS influence functions compare with a full influence function? \n* Can you provide a bound on the (expected) deviation from the \"true\" influence function score (as given in Koh and Liang's paper)? Can you quantify the manner in which gradient sparsity influences this?", "limitations": "I feel a key limitation to this work is the scope. The work, as presented, only proposes a method for efficiently computing influence functions. While the results appear to be technically correct, this work does not address any deeper question other than a simple improvement in cost. Moreover, there are no rigorous theoretical results - stated as Lemmas or Theorems - of interest from a statistical standpoint, though the computational complexity guarantees are nice to have.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n\n* The paper is generally quite well written\n* The methods proposed address the real problem of the scalability of gradient-based data attribution, and the proposed method has a significantly lower wallclock time than the baselines\n* The computational speedup of the GrASS method is shown rigorously in sections 3-4.\n\n## Weaknesses\n\n* Theoretical analysis could be written more clearly. The computational complexity resutls could be stated as formal results, at least in the appendix. Moreover, a table comparing computational costs of the different methods would have helped the exposition significantly/.\n* The GRASS and FACTGRASS influence functions should be written as numbered equations for clarity.\n* There is no discussion on the statistical properties of the GRASS estimator. Please refer to the \"Questions\" section as well.\n* The quantitative analysis with the LLM is not very clear, and should be more clearly expressed.\n* I feel the scope of this work is slightly limited - please refer to the \"Limitations\" section.", "was_revised": true, "final_justification": "I've raised my score to 4 (Borderline accept). While I still have some doubts about the significance of the work, the authors answered all my questions, particularly those pertaining to correctness.", "rebuttal": "We sincerely thank Reviewer SuDq for taking the time to review our paper and for their constructive feedback. Below, we provide point-to-point responses to the questions, hopefully addressing the concerns raised.\n> Better presentation of theoretical results\n\nWe appreciate the reviewer's valuable suggestions for enhancing the clarity of our theoretical analysis and computational complexity results.\n\nWe will update the paper accordingly, incorporating formal theorems to clearly state our method's computational complexity. Furthermore, we will include a comprehensive table comparing the computational costs of GraSS and FactGraSS, and other popular state-of-the-art methods, to significantly aid exposition. A sample table is provided below:\n\n| **Method**     | ***RM/SM*** | ***SJLT*** | ***GraSS*** | ***FactGraSS*** | **Gaussian** |      **FJLT**      |   **LoGra**    |\n| :------------- | :-------: | :------: | :-------: | :-----------: | :----------: | :----------------: | :------------: |\n| **Complexity** |  $O(k)$   |  $O(p)$  |  $O(k')$  | $O({k'}^{2})$ |   $O(pk)$    | $O((p + k)\\log p)$ | $O(\\sqrt{kp})$ |\n\nwhere $p$ denotes the model size, $k$ denotes the target compression dimension, and $k'$ is a parameter such that for GraSS, $k \\leq k' \\ll p$, and for FactGraSS, $\\sqrt{k} \\leq k' \\ll \\sqrt{p}$. We note that both LoGra and FactGraSS are specific for linear layers, and neither requires materializing the layer-wise gradients.\n\nRegarding the influence functions for GraSS and FactGraSS, we will ensure these are presented as numbered equations for improved clarity.\n\n> Discussion on the error between GraSS/FactGraSS compared to the full influence function\n\nWe appreciate the reviewer's interest in the statistical properties of the proposed estimators. In the literature, state-of-the-art methods like LoGra [1] and TRAK [2] adopt random projection, often motivated by the approximation error guarantees provided by the Johnson-Lindenstrauss (JL) Lemma. Our approach adopts SJLT, which comes with JL Lemma-type guarantees as well [6]. However, a theoretical error bound w.r.t. the full influence function remains a significant open challenge in the current literature for efficient data attribution methods, including LoGra [1] and TRAK [2]. Arguably, most of the gradient-based efficient data attribution methods are driven by empirical development.\n\nGiven this context, we believe our proposed methods are well-motivated. Our extensive empirical validation demonstrates competitive performance, highlighting the practical utility and reliability of GraSS/FactGraSS within the current research landscape. Further theoretical development in this area represents a promising direction for future work.\n\nWe will include the above discussion in the next version to better motivate our methods.\n\n> Quantitative analysis with LLM is unclear\n\nWe acknowledge the reviewer's feedback regarding the clarity of our quantitative analysis with LLMs:\n* Our experiments include results for GPT2-small (fine-tuned on Wikitext), presenting both LDS scores (in **Table 1**) and efficiency metrics. For Llama3-8B (evaluated on a subset of OpenWebText), we report throughput (in **Table 2**) as an efficiency measure.\n* Our experimental setup closely adheres to the methodology established by the recent state-of-the-art [1]. We will provide a more detailed and self-contained description of this setup in the updated version of the paper to enhance clarity.\n\n> Scope of the work is limited: only proposes a method for efficiently computing influence functions, without theoretical results\n\nWe contend that efficiency is a core and pressing challenge for all recent state-of-the-art gradient-based data attribution methods [1, 3, 4], and our proposed GraSS and FactGraSS methods offer broadly applicable gradient compression techniques, which are crucial components in nearly every modern gradient-based attribution approach [1,2,3,4,5]. Thus, addressing this fundamental efficiency bottleneck significantly advances the practical applicability and scalability of a wide range of gradient-based data attribution algorithms.\n\nRegarding the lack of rigorous statistical theoretical results, we would like to clarify:\n\n1. The key components of our proposed methods, particularly SJLT, come with strong theoretical justifications for their approximation quality [6], as discussed in **Lines 138**-**144**.\n2. While a full statistical analysis of the end-to-end attribution process is indeed complex, as noted in our response to the second response (i.e., \"Discussion on the error between GraSS/FactGraSS compared to the full influence function\"), the broader development and evaluation of data attribution methods have been largely driven by extensive empirical research [1, 2, 3].\n3. We have conducted comprehensive empirical evaluations on two of the most popular gradient-based data attribution methods, Influence Functions and TRAK [2], demonstrating the effectiveness and practical utility of our approach.\nTherefore, we believe that the proposed methods offer a substantial improvement in a critical area, supported by both component-wise theoretical guarantees and strong empirical evidence, aligning with the current trajectory of research in data attribution.\n\n**References**\n\n[1]: What is Your Data Worth to GPT? LLM-Scale Data Valuation with Influence Functions\n\n[2]: TRAK: Attributing Model Behavior at Scale\n\n[3]: Capturing the Temporal Dependence of Training Data Influence\n\n[4]: Data Shapley in One Training Run \n\n[5]: Scaling Up Influence Functions\n\n[6]: A Sparse Johnson--Lindenstrauss Transform"}, {"review_id": "P9KKPyR4of", "reviewer": "Reviewer_iWVy", "summary": "This paper introduces GraSS , a new method for making gradient-based data attribution more efficient. The key idea in this work is to exploit the sparsity of these per-sample gradients, most of the values are close to zero, and use that to compress the gradients. They also introduced a specialized version called FactGraSS , designed specifically for linear layers, which gives even better performance. In experiments, their method was significantly faster up to 165% faster throughput on huge models while still keeping the accuracy of influence estimation.", "questions": "1. Most current attribution methods, especially those based on Leave-One-Out (LOO) influence analysis, are built upon the Influence Function introduced by Koh and Liang. The core computation involves the product of the inverse Hessian matrix and the gradient. This framework has two main issues: \n\n**Efficiency** : Computing or approximating the inverse Hessian is time-consuming and difficult, which has led to many follow-up works focusing on how to accelerate this part. \n\n**Accuracy** : Influence Function-based methods assume the loss function is strongly convex, which theoretically limits their maximum achievable accuracy. \n\nLater, more accurate methods emerged, such as SGD-Inf. My question is: Can newer acceleration techniques like GraSS also be applied to speed up these more advanced attribution methods?\n\n---\n\n2. Building on the first question, if the issue of speed is largely resolved, does the accuracy of current attribution methods still fall significantly short of what is required in real-world applications? Take SGD-Inf, one of the most accurate methods available today, as an example: its error grows exponentially with the number of training steps (exp(T)), meaning the error deteriorates rapidly as training progresses. \n\n---\n\n3. Is such a level of error still acceptable in practical scenarios? The third question again concerns the computational bottleneck. Even with efficient algorithms like GraSS or DataInf, the overall computation time for attribution still requires at least one full pass over the training data — that is, it has O(N) complexity. Meanwhile, in many large-scale model trainings today, the model is often trained for only one or a few epochs. This implies that the cost of attribution may already approach or even exceed the cost of the entire training process.\nIn such cases, how viable is the application of data attribution methods in practice?", "limitations": "see Questions", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "strength: \n\nThe method demonstrates a significant improvement in computational efficiency. \n\nWeaknesses: \n\nThe presentation of the paper is somewhat difficult to follow.", "was_revised": true, "final_justification": "I keep my initial rate for this paper.", "rebuttal": "We sincerely thank Reviewer iWVy for taking the time to review our paper and for their constructive feedback and recognition of our proposed algorithm and its potential impact. Below, we provide point-to-point responses to the questions and concerns raised.\n> The presentation is difficult to follow\n\nWe appreciate the reviewer's feedback regarding the paper's presentation and acknowledge that some paragraphs could be clearer. We are committed to improving readability and flow.\n\nWe will thoroughly revise the writing in the next version to enhance clarity and ensure the paper is easier to follow. We welcome any further specific suggestions the reviewer might have to help us achieve this goal.\n\n> Can GraSS/FactGraSS also be applied to speed up advanced attribution methods such as SGD-Inf?\n\nYes, our proposed GraSS and FactGraSS gradient compression algorithms are general and broadly applicable to various data attribution methods that rely on per-sample gradients [1, 2, 3, 4].\n\nFor instance, recent advancements like [1,4] (which are conceptually similar to SGD-Inf) utilize techniques akin to those in LoGra [2]. Our methods can be seamlessly integrated into such frameworks to achieve significant acceleration.\n\nFor clarity of presentation within this paper, we focused our experimental scope primarily on the Influence Function and its variants TRAK [3]. However, integrating GraSS/FactGraSS with other, more recent data attribution methods like SGD-Inf and works such as [1, 4] is a promising application of our proposed methods.\n\n> Does the accuracy of current attribution methods still fall short of what is required in real-world applications?\n\nWhile we agree that the required accuracy for data attribution methods is application-specific, however, we would like to highlight that existing methods already demonstrate practical utility in many scenarios.\n\nOur work's core contribution is to significantly accelerate gradient-based data attribution, achieving state-of-the-art efficiency for well-known methods like Influence Function and TRAK. By resolving the critical computational bottleneck, we enhance the practical applicability of these valuable tools, making them feasible for larger scales. Our focus is on computational efficiency, an orthogonal problem to inherent algorithmic accuracy limitations.\n\n> Error and computational bottleneck remain\n\nWe appreciate the reviewer's insightful questions regarding the practical viability of data attribution methods. Regarding the level of error, whether it is acceptable remains application-specific. As discussed above, current data attribution methods have already demonstrated their utility and found practical use in various real-world scenarios. Our work focuses on addressing the computational bottleneck to expand their applicability.\n\nFurthermore, we acknowledge that current gradient-based attribution methods inherently require $N$ per-sample gradients, implying a complexity comparable to at least one training epoch. This is widely considered a hard computational lower bound in the field, with recent advancements [1, 2] that achieve attribution within \"one training run\" being recognized as significant breakthroughs.\n\nWhile we agree that for the largest frontier models during their pre-training phase, an attribution cost approaching or exceeding a single training epoch might be prohibitive, this is not universally true. For fine-tuning phases or smaller models, this level of computational expense is often affordable and efficient enough for practical application. Our methods significantly enhance this affordability for the scenarios where it is viable.\n\n**References**:\n\n[1]: Data Shapley in One Training Run\n\n[2]: What is Your Data Worth to GPT? LLM-Scale Data Valuation with Influence Functions\n\n[3]: TRAK: Attributing Model Behavior at Scale\n\n[4]: Capturing the Temporal Dependence of Training Data Influence"}]

Author rebuttal:

Meta-review: The authors propose a method for efficient computation of gradient-based data attribution methods that exploits the natural sparse structure of per-sample gradients in ReLU networks and well-adapted randomized projection methods, in particular the sparse JL transform. The methodology carefully integrates different techniques from prior work with this core approach and different strategies for masking. The authors provide a detailed complexity analysis of their method, as well as CUDA kernels for key components. Experimental results demonstrate significant speedups on large models.

Initial reviews for the paper were positive, and they further increased after the rebuttal, in which the authors clarified the potential for their method to be applied beyond computation of influence functions and provided additional comparisons to baselines. Concerns that the results did not demonstrate advantages beyond 1B scale were seen as acceptable by the reviewers after discussion. The AC agrees with the reviewers' judgment, and recommends acceptance. The authors should carefully incorporate feedback from the reviewers into the final revision.
Decision: Accept (poster)