Efficiently Verifiable Proofs of Data Attribution
Authors: Ari Karchmer
Seth Neel
Martin Pawelczyk
Venue: NeurIPS 2025 poster ()
Keywords: Data Attribution
Component Attribution
Verifiable ML
Interactive Proofs
PAC-Verification
Primary area: theory
TL;DR: We demonstrate an efficient interactive verification protocol that allows resource-constrained parties to trust and reliably check the quality of expensive attribution models provided by powerful, untrusted parties.

Abstract: Data attribution methods aim to answer useful counterfactual questions like "what would a ML model's prediction be if it were trained on a different dataset?" However, estimation of data attribution models through techniques like empirical influence or "datamodeling" remains very computationally expensive. This causes a critical trust issue: if only a few computationally rich parties can obtain data attributions, how can resource-constrained parties trust that the provided attributions are indeed ``good,'' especially when they are used for important downstream applications (e.g., data pricing)? In this paper, we address this trust issue by proposing an interactive verification paradigm for data attribution. An untrusted and computationally powerful Prover learns data attributions, and then engages in an interactive proof with a resource-constrained Verifier. Our main result is a protocol that provides formal completeness, soundness, and efficiency guarantees in the sense of Probably-Approximately-Correct (PAC) verification (Goldwasser et al., 2021). Specifically, if both Prover and Verifier follow the protocol, the Verifier accepts data attributions that are $\varepsilon$-close to the optimal data attributions (in terms of the Mean Squared Error) with probability $1-\delta$. Conversely, if the Prover arbitrarily deviates from the protocol, even with infinite compute, then this is detected (or it still yields data attributions to the Verifier) except with probability $\delta$. Importantly, our protocol ensures the Verifier's workload, measured by the number of independent model retrainings it must perform, scales only as $O(1/\varepsilon^2)$; i.e., independently of the dataset size. At a technical level, our results apply to efficiently verifying any linear function over the boolean hypercube computed by the Prover, making them broadly applicable to various attribution tasks.

Efficiently Verifiable Proofs of Data Attribution
Ari Karchmer
Martin Pawelczyk
Seth Neel
Abstract
Data attribution methods aim to answer useful counterfactual questions like "what would ML model's prediction be if it were trained different dataset?" How- ever, estimation of data attribution models through techniques like empirical in- fluence "datamodeling" remains very computationally expensive. This causes a critical trust issue: only a few computationally rich parties can obtain data attributions, how can resource-constrained parties trust that the provided attribu- tions are indeed "good," especially when they are used for important downstream applications (e-g., data pricing)? In this paper, address this trust issue by proposing an interactive verification paradigm for data attribution. An untrusted and computationally powerful Prover learns data attributions, and then engages in an interactive proof with a resource-constraiiee protocol that provides formal completeness, soundness, and efficiency guarantees in the sense of Apppabbby-pprooiiatttlyyyl Correct (PAC) verification (Goldwasser al., 2021). Specifically, both Prover and Verifier follow the protocol, the Verifier accepts data attributions that are s-close to the optimal data attributions (in terms of the Mean Squared Error) with probability 1 5. Conversely, if the Prover arbitrarily deviates from the protocol, even with infinite compute, then this is detected (or still yields data attributions to the Verifier) except with probability 6. Importantly, our protocol ensures the Verifier's workload, measured by the number of independent model retrainings it must perform, scales only as O(1/=²); i.e., independently of the dataset size. At technical level, our results apply efficiently verifying any linear function over the boolean hypercube computed by the Prover, making them broadly applicable to various attribution tasks.
Verifier. Our main result is a
Introduction
The attempt to understand and explain the behavior of complex machine learning systems has given rise to the field of attribution. Broadly, attribution methods seek to trace model outputs or behaviors back to their origins. This takes several forms. One prominent form is training data attribution, which aims to quantify the influence of individual training examples on model predictions, facilitating interpretability, debugging, and data valuation (e.g., Koh and Liang, 2017; Ghorbani and Zou, 2019; Ilyas et al., 2022). Complementary to this, component attribution (Shah et al., 2024) focuses on decomposing model's prediction in terms of its internal components, such convolutional filters or attention heads, to understand how they combine to shape model behavior.
While many applications of attribution may be of interest to the model developers. others are inherently of interest to third parties who may not have access to the internal details of how the attributions were computed. For instance, consider a framework where entities that supply data for training are compensated in proportion to the degree their training data influences model outputs, an idea which
Morgan Stanley Machine Learning Research, Harvard Business School, akar akar akarchnerOOgmail.coo
I Harvard Business School, martin, pawelczyk: 10gmail, com Google Research, Harvard Business School, sethnee looonneee@ggggle..oomm
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

has been extensively discussed (Ghorbani and Zou, 2019; Castro Fernandez, 2023; Jia et al., 2023; Choe al., 2024). In this setting, a user may not only be concerned that the attributions for the dataset as whole are accurate -mennnn they have low predictive error in absolute terms- but that if the ground truth attribution for user j is lower than for user i, the received attributions also satisfy this property. As another example, suppose doctor is using a model to provide diagnoses, and wants to understand what training data the model used to reach its conclusions, in order to sanity check them.
In each of these settings, rather than simply trusting that attributions are computed correctly, third parties may want to verify that the attributions are "right." before making important downstream decisions. The challenge arises because of a computational disparity- third parties using these attributions typically have far, far fewer computational resources than the model developer that is providing them, whether they are an individual or even another small lab in academia or industry. Thus, given the large computational expense associated with estimating ground truth attributions, we have the following motivating question:
Is it possible to design a protocol by which computationalllyliiiii third party can "verify"" the correctness of attributions?
Our Contribution, in a Nutshell. In this paper, we demonstrate an interactive two-message protocol where the third party's i computational cost, which is measured by the number of full model retrainings it must conduct, is independent of the attribution set size N (e.g.. in data attribution N is dataset size, while in component attribution it is the number of components). That is, this number of required retrainings does not grow as a function of N. Our protocol comes with strong guarantees of correctness for the third party, even if the model developer deviates from the agreed protocol arbitrarily, and with infinite compute. To make this precise, we must specify (i) the form of attributions we study. (ii) how we measure computational cost, (iii) what our accuracy metric is, and finally (iv) what guarantees of correctness we can (and should) provide for our protocol.
While we will formalize each of these in section 2, we discuss each of them here in order to clearly state our contributions. Additionally, while our work applies to data attribution methods in general, we will proceed with predictive data attribution in mind, for purposes of exposition.
Predictive Training Data Attribution. In predictive training data attribution (TDA), the goal is to answer counterfactual questions: "What would have happened to a model's behavior if we had trained it different subset of the data?" To formalize this, we consider a model output function, f: [=1] - R. The domain of f are subsets r of a fixed training dataset S of size N (where x E (+INN and x; = 1 indicates inclusion of the 7th data point from S and x; = -1 indicates exclusion). The model output function [(x) measures the (expected) model behavior if it were trained on S, and is evaluated by retraining a model 0 ~ T(x) via a training algorithm T, and then computing some function of f often the prediction 0(z)
imput point æ (Ilyas et al., 2022), the test error of f on some subgroup of the data (Jain et al., 2024).
The objective of TDA is then to construct a predictive model, often a linear function g(x) (a. 2). where a are the attribution scores, in order to predict the counterfactual effect of training on a different subset of the data. The quality of this predictive model can be measured by its Mean Squared Error (MSE) with respect to the true model output function f and binomial product distribution B, over the subsets:
msse (P) (f, (),
E BB
[[f(x) (a, [3]
Achieving a low MSE indicates that the attribution scores a accurately predict how different subsets of data affect the model's 's behavior.* 4
Remark 1. While we will focus on the well-studied area of TDA throughout. the recently proposed "component attribution." " (Shah et al., 2024) that aims to determine which internal components of the model are primarily responsible for specific predictions, also fits neatly into our frumework. In this case, defined above corresponds the set of total model components, sampling x ~ B, corresponds to sampling a subset of components, and the model output function I consists of computing a forward
'Note. f is technically a randomized function, but we will assume a fixed random seed, and that f becomes deterministic once the random seed is fixed.
2

---

pass on a test input 2 where activations from components & x are set to constant. The methods in this paper can also be used to verify the accuracy of model component attributions.
Specific Methods for Training Data Attribution. There are two major classes of algorithms for TDA: those based on retraining, and gradient-bane -based methods like influence functions or representer point methods that leverage approximations to the model training process or architecture. In re- training based methods, first samples xy C S are drawn (typically from a product distribution), and the output function f(z;) is computed, which involves training a model ((z;)) and then computing the relevant statistic from ((z;). Different vetraining-based attribution methods generally correspond to different techniques for estimating a from samples { { computed by retraining. In Datamodels (Ilyas et al., 2022), a is computed via a Lasso regression to encourage sparsity in a, where the model output function computes the difference in correct class logit for specific test input 2. In Empirical Influence (Feldman and Zhang, 2020), the jth coefficient a, is estimated as the average of the sampled outcomes where the jth datapoint was included: M-EEze
[zz), where Mj- {=; (1a); 1). The clever work of Saunshi et al. (2022) proves that these two methods are essentially theoretically equivalent, though performance can vary in practice, in part due to optimizations such as applying the LASSO algorithm.
Most gradient-based TDA methods are based on approximations to the continuous influence function (Law, 1986; Koh and Liang, 2017; Park et al., 2023; Grosse et al., 2023; Guu et al., 2023). While these methods are more computationally efficient than exact retraining, the assumptions underlying influence functions (e.g., convexity, training to convergence) often do not hold in deep learning, potentially undermining their suitability for data attribution (Bae et al., 2022). Yet another class of TDA methods aim to approximate the model with simpler model class, where the attributions can be computed analytically (Park et al., 2023; Yeh et al., 2018). Prior work has found that retraining methods can be more accurate than those based on influence functions or model approximations, in settings where they are both tractable to compute (Ilyas et al., 2022), but so far these retraining based methods are unable to scale to large models (Grosse et al., 2023).
Computational Cost. While highly accurate vetraining-based predictive data attribution can prove invaluable for tasks like dataset selection (Engstrom et al., 2024) and sensitivity analysis (Broderick et al., 2020; Pawelczyk et al., 2023), they come with a large computational cost. Computing fresh sample (1;) corresponds retraining an entirely new model from scratch, and the number of samples required to obtain accurate Datamodels (attributions) is large: the work of Ilyas et al. (2022) trains three million ResNet-9 networks on random subsets of the CIFAR-10 dataset to construct their attribution. The recent work by Georgiev et al. (2024) uses Datamodels for the less stringent task of machine unlearning, and still requires training >> 10, 000 models. Methods based on the influence function avoid retraining but still require computations like Creerse-Hessian-veeee can be intractable for very large models. Moreover, even methods based on influence functions may require ensembling over multiple training runs to achieve reasonable accuracy (Park et al., 2023).
products, which
Trust Issues: Naive Verification Fails. The computational barriers described above put TDA, especially retraining-based methods like Datamodels or Empirical Influence, beyond the reach of individual practitioners or even moderately resourced academic labs. This effectively centralizes the task within a few industrial or institutional powerhouses.
Centralization causes trust issues. If only a few parties can effectively perform attribution, then, given a candidate attribution a computed by the computationally powerful group. how can a third party efficiently establish the accuracy of a? In keeping with the rich body of work relating to interactive proofs, going forward we will refer to the computationally powerful party as the Prover, and the coouurce-onstrriined third party as the Verifier.
A naive idea that seemingly fits into our setting, is for the Verifier to try to check the MSE of any proposed attributions a.
The Verifier randomly samples collection of subsets T c [=1]N of size m, obtains (x) Vo e T, and uses that data to estimate mss(p) (f, (a. -)) ~ d. Enjer((a, x.) - f(x)))²
When m is proportional to 1 1/e2, the estimate within an additive e error from the true MSE with high probability. Hence, the Verifier can check that the Prover has given him attributions which have
3

---

MSE at most a + E, for some pre-determined a. Most importantly, the Verifier can do this using only O(1/E²) retraining procedures on the modcl-which independent of the data set size N!
However, this is not actually satisfactory. To see why, consider again the setting of data valuation. For concreteness, imagine each data point is contributed by a user, under the agreement they will be compensated in proportion to the attribution scores for the data they contribute. Now, suppose the Prover proposes candidate attributions a such that mss( (ff, (a. -)) = 0.22. Then, when the Verifier checks the MSE, they will obtain estimate a' [0.22 E, 0.22 E] with high probability. But, what if there exists a' such that mse(p) (f, (a', -)) 0.022?
Indeed, in order to reduce total costs, a malicious Prover might cheat as follows:
Compute a by brute-force Empirical Influence." 5
Use a' = a (scalar multiplication).
Recall that in our simple data valuation setting, the Prover will pay out data sellers proportional to their attribution. Thus, by dividing the true attributions by 2, the Prover will save 50% money (at the necessary cost of increase to MSE).
As in the naive protocol, only checking the MSE fails shed light on whether such cheating has been carried out by the Prover (without loss of generality on the exact cheating strategy). To emphasize the point further, consider the case that the Prover wants to advantage subset of data contributors A over all other contributors, so they receive more payment. In order to do so, they modify a by increasing coordinates where i E by some value is reasonably small, the modified a' might also have low MSE, and so a Verifier that merely checks the MSE is below a certain threshold would accept these attributions.
to produce a new attribution vector a'. /
is not a priori clear whether or not the Verifier has any way of defending itself against this form of cheating Prover, without having to compute the attributions itself. That is, without having do the work of the Prover.
A Better Notion of Verifiability. As we have hopefully demonstrated, we need more meaningful notion of verifiability, that goes beyond simply checking the MSE of the proposed attribution. To this end, we suggest estimating sub-optimality. Put simply, the Verifier should ensure the attribution is "g-close" to optimal. This can be written as verifying the fact that
err(a', (S)) mse (p) (f, (a', mss (f. (+(), S E.
(I)
Here, (SS) denotes the optimal attribution vector for the set S, with respect to MSE. That is,
(S)) A arg min (s) (f, (a.
And so, in other words, verifying sub-optimality means checking if the error gap (equation 1) between the proposed attributions, and the optimal attributions, is small.
All in all, checking low sub-optimality tells the Verifier that for this specific setting, the provided attributions are nearly optimal, and therefore the Prover has acted in good faith. Thus, we propose to aim for the following (still informal) guarantees.
Informal verification Guarantees. When designing a verification protocol we will obtain:
Completeness. If both Prover and Verifier follow the protocol, the Verifier obtains attribution scores that are approximately optimal with respect to predictive MSE, with high probability.
Soundness. If the Prover deviates from the protocol in any way, then, with high probability, the Verifier either outputs "abort" or still obtains attribution scores that are approximately optimal with respect predictive MSE.
Efficiency. The Verifier's workload scales independently of the dataset size N.
Remark 2. In practice, even an honest, powerful Prover might only compute an estimate å' of (S) due to computational constraints (e.g., using an influence function). The soundness guarantee
'It is strongest to consider a malicious Prover to be computationally unbounded as is customary in the theory of interactive proof' Goldwasser et al. (2019, 2021) or statistical zero knowledge (Vadhan, 1999), and others.

---

still holds relative to the true ((S). However, the completeness guarantee might be affected if the honest Prover's estimate ät is itself far from D(S). If ffer(aa ((S)) is inherently large due to the Prover's own estimation limitations, the Verifier might reject even honest Prover if & is set too small. Therefore, the choice of & in practice should reflect not only the Verifier's desired precision but also potentially incorporate tolerance for the best achievable estimation error by an efficient (though powerful) honest Prover.
1.1 Our Contributions
Conceptual contributions. Conceptually, this work introduces the idea, motivation, and goal of efficient interactive verification of data attribution.
As we will see in the next section, our formalization of this goal is done via direct connection to the interactive PAC-verification framework (Definition 1) of Goldwasser et al. (2021). ). As we have discussed, key challenge in verifying proposed attribution vector a' is comparing its predictive quality against the optimal linear predictor (S) without actually computing (S)). The PAC- Verification paradigm turns out to be well-equipped to handle this challenge.
Technical contributions. As for technical contributions, we demonstrate two efficient protocols for the task of efficiently verifying optimality of proposed attributions.
For the first protocol, it turns that recent work by Saunshi al. (2022) actually provides "residual estimation" algorithm for exactly this task. More specifically, their algorithm estimates the optimal residual (that is, mns(P) (+))).)) ))) using only O(1/=)) samples of the function f (Theorem 2), without needing to compute ((S) itself. This naturally suggests potential non- interactive verification protocol where:
The Prover would compute Empirical Influence attributions a' and send them to the Verifier.
The Verifier could independently estimate the optimal (ss (f. (D(S).)) (within an additive factor of e) using the algorithm of Saunshi et al. (2022), and also independently estimate (Ps(P) (f, (a', (within an additive factor of E) using O(1/s²) samples. The Verifier would then accept if the two estimates were s-close.
The complexity of this non- interrtttrcttee approach would be dominated by the residual estimation step. resulting in a Verifier cost of O(1/=²) (derived from the sample complexity guarantee of Saunshi et al. (2022)). We consider this non-interactive protocol in detail in section
Main Technical Contribution. Our main technical contribution is to build out the above non- interactive protocol into interactive protocol. Our interaction strategy serves to reduce the Verifier's overall complexity to O(1/=²), and is implemented by a "spot-checking" mechanism. The function the "spot-checking" mechanism is to further move some of the Verifier's work required for residual estimation, onto the prover. This mechanism necessarily requires an interaction, though we only use messages (first the Verifier speaks, and then the Prover responds). To prove the intended qualities of the spot-checking mechanism, we do non-black box analysis of the proof of the residual estimation algorithm of Saunshi et al. (2022), in order demonstrate degree of adversarial robustness in the procedure.
We outline our protocol in Section 4. The interactive protocol satisfies the completeness and soundness guarantees that we have discussed. With respect to efficiency, we improve upon the non-interactive protocol by obtaining a Verifier workload that scales as (11
2 Formal PAC-verification Framework for Attribution and Main Theorem
To this point, we have not formalized what we mean by a Prover- Verifier protocol for data attribution. Let us begin with formalizing the interaction model.
Communication. As part of the interaction, we assume an asynchronous, reliable channel between the parties. An interaction consists of a finite sequence of messages WI, W2,....... W, E {0, 1)", sent alternately between the Verifier and the Prover P. Messages are unrestricted bit-strings and may encode, for example, hashes, sketches, model weights, or random seeds.
5

---

Shared resources. Both the Prover and the Verifier will agree on certain information regarding the objective of the protocol. For instance, the protocol is executed with respect fixed training set S (with |S| = N), fixed model architecture, and fixed objective function for model training which defines the model output function
{+1] R. as introduced earlier.
Termination. After the last message V halts and outputs a single value à E (abort respectively as rejection or an accepted vector of attribution scores. No further interaction occurs once abort or à is produced.
(UrborttURRA JUR*, interpreted
2.1 The Protocol Guarantees
We are now ready formalize our desired protocol guarantees. Namely, Completeness, Soundness, and Efficiency. To this end, we adapt a previous formalization of similar setting called Probably- Approximately-Corred Verification (PAC- Verification) (Goldwasser et al., 2021). After introducing the formalism, we will also comment on why it is necessary to use this framework, instead of other formalisms from Cryptography, such as Delegation of Computation protocols (see e.g., Goldwasser et al. (2015)).
Let X be the space of training examples. Recall the model output function f {+1] + R. which maps a representation of training subset to a model behavior, and our goal to find an attribution vector a such that the linear predictor (a. -) has low (P) (f, (a. ))).
Let (S)) R& denote the optimal attribution vector with respect to MSE.
Our error function car (S)) measures the sub-optimality of candidate attribution vector in terms of its predictive MSE performance compared to (SS):
err(a, ((S) & (s)(F) (f, (a, m (f, (4(S).
Note that crr(a, ((S) 2 0. The Verifier's goal is to accept if this error gap is less than equal to an accuracy threshold E.
Finally, fix a Verifier cost function x : (0, - N.
Definition 1 (PAC-verification for data attribution, adapted from Goldwasser et al. (2021)). Fix
accuracy E E (0. 1) and confidence å (0, 1). An interactive proof system (V, P) an (s, PAAC verifier for 4 if. for every dataset S, the following hold after V and P exchange messages, and then V outputs value à E (abort] UR.:
Completeness. P abides by the protocol, then
Pr + abort A err (á, ((S) < 2 1 6.
Soundness. For every (possibly computationally unbounded) dishonest prover P',
Pr(á F abort A err (á, ((S)) E| s 8.
Efficiency. There exists constant is 0, such that k<e, 8) (1/e log(1/8))
The Verifier's cost is required to be independent of N = SS]. For our choices of ④ and err (as defined above), the honest Prover's cost can be shown necessarily grow with N. Hence, our protocols allow the Verifier to expend arbitrarily less cost than the Prover.
Why PAC- Verrfifiicttinn and not Delegation of Computation? One might initially consider employ- ing general-puree purpose cryptographic protocols for delegation of computation or verifiable computation to ensure the prover P performed the expensive attribution computation correctly. However, such approaches are insufficient for the verification goal central to our work and discussed by Goldwasser al. (2021). First of all, computational overhead for the Prover can be significant in existing crypto- graphic solutions; this already renders the approach very impractical our setting, since the honest Prover may already be pushing the limits of their computational power. Second, Cryptographic
'Later in the paper, we will assume that f (+1)* + [-b, b] has a bounded range. This assumption is supported empirically by typical model output functions considered in the literature. For instance: change in correct-class margin at specific test point (Ilyas et al., 2022).

---

delegation can typically only ensure that P executed specific computation as promised, given some inputs. It cannot, in general, provide guarantees about the statistical quality of the output, particularly whether the resulting attribution scores a' are indeed e-close to the optimal scores (S) according to our error metric err(t,). We refer to section F for a continued discussion.
2.2
Main Theorem
The main result of this paper is an (e, 5)-PAC verifier for data attribution, where correctness is measured by the MSE difference defined in err(;:)) At this point, we only need to define the Verifier cost function in order to state the theorem.
We will take the Verifier's cost to be the expected number of training runs they conduct (over randomness of the protocol execution). We are now ready to state the theorem.
Theorem 1 (Main Protocol Theorem). We ussume that f {+1]8 - [-b,b) some constant For any E E (0, 1), Algorithm I is a (e.8)-PAC verifier for & (as defined above, with en measuring the MSE gap). The Verifier's cost function satisfies O(log(1/8)/{²). Furthermore, the interactive protocol requires only two messages.
Scalability to Multiple Attribution Tasks.
While our core protocol (Algorithm 1) presented for verifying attributions with respect single model output function f. a natural question arises regarding its applicability when attributions are needed for multiple scenarios simultaneously-Be
instance, across Z different test points for Z distinct output metrics. Our framework extends efficiently to such cases. The key observation is that, to maintain an overall (e, 8)-PAC verification guarantee across all Z attribution tasks, union bound can be applied to the confidence parameters. This means that the number of challenge subsets requested from the Prover for residual estimation, and the number of local samples used by the Verifier for its final MSE checks, would increase logarithmically in Z. We refer to section E for details.
3 A "Simple" Non-Interactive Verification Protocol
This section will use standard notation from Boolean Harmonic Analysis. We refer to section A. for the necessary definitions (see instead O'Donnell (2014) for the comprehensive treatment).
Before presenting our main interactive protocol, we first outline a simpler, non-interactivv approach to PAC-verifying empirical influence attribution (SS). This serves to establish bascline Verifier complexity and motivate the introduction of interaction to achieve greater efficiency.
Recall the verification goal defined in Definition 1. The Verifier V receives a candidate attribution vector a' from the Prover P and needs to determine if is e-close ((S). Using our chosen error metric, this means verifying if:
err err(a', ((S) (P) (P) (a', mse(P) (f. (D(S).
close relationship exists between (r (f, (S))).)) and the Boolean Fourier coefficients of f (see section A. for the definition and background Fourier coefficients). In fact, as demonstrated by Saunshi et al. (2022), the optimal linear predictor (T(S). -) satisfies the identity:
mse (P) (f. (I(S) =
Σ
f3 B22.
SCINSSS222
Therefore, the verification condition is equivalent to checking the Prover's solution a' satisfies:
(P) (f, (a', B22 t
The "residual estimation" algorithm developed by Saunshi et al. (2022) provides useful tool. As stated in Theorem 2, their algorithm, denoted EESSDUALESTIMATIONN allows estimating B2g up
"This but one way to define cost. For now, we only mention that this notion sample complexity data attribution is commonly used efficiency metric in the field (see e.g. llyas et al. (2022); Park et al. (2023)). We emphasize this metric as each retraining constitutes significant computational effort, potentially scaling with the dataset size N itself. Hence, it captures the primary bottleneck for the Verifier.
7

---

to an additive enror E' with high probability, using only n ((1/(=)) -polylog(/00) evaluations (samples) of the function f. Importantly. this algorithm estimates the residual error without needing to compute the optimal linear predictor (S) itself.
Theorem 2 (Residual Estimation, restated (Saunshi et al., 2022, Theorem 3.2)). Let f: {+1}) - R.
using degree d = 2 polynomial fitting based on noise stability estimates at points p. 2p] (along with p = 1), obtained using a total budget of n calls to f. If = O(1/E") and p = O @(vE), then with high probability (e.g., 1- - 8 for small constant 8),
Let Bzg be the ouppu of the residual estimation algorithm RESIDUALL
Bz Bz2l <;
where Bz2- = Es I' is the tre residual ervor under the Bp distribution.
This immediately suggests non-interactive PAC-verification protocol:
1. Prover P: Computes a' (e.g., its best estimate of ((S) and sends it to
2. Verifier V (Local Computation):
(a) Estimates the MSE of the Prover's solution: Compute mise Ro mss(P) (f; (a', .)) by drawing M O(1/E² polylog(1 (1/8)) samples I Bp. locally training models to evaluate f(x) for each sample, and calculating the empirical average squared error
(f(x) (((x))(a(xz))) ())
(b) Estimates the optimal residual error: Compute B32 R Bz² by running DESIDIALLESTTMATTONN;; p,n) locally, setting the budget n 0(1/e3 polylog(1/6) and p ((vE). This requires locally evaluating f on n (pairs of) input subsets.
3. Verifier V (Decision): If msc < B22 + e", output a' (where e" accounts for the combined estimation errors from steps (a) and (b), we can assume e" = c). Otherwise, output abort.
See section B in the appendix for overview of how the residual estimation algorithm works.
Informal Analysis of the Non-Interactive Protocol. Completeness and Soundness of this proto- col can be seen to follow from the accuracy guarantees of standard MSE estimation (via Hoeffd- ing/Chernoff bounds) and the guarantee of the residual estimation algorithm (Theorem 2), using a union bound over the failure probabilities.
The Verifier's efficiency measured by the number of calls I (i.e., model trainings). Step (a) re- quires (1//s² polylog(1//) calls. Step (b), the residual estimation, requires O(1/s ((1/s9-polylllll polylog(1/5)) calls. The overall Verifier cost k(e, 8) is therefore dominated by the residual estimation:
Kiyssiuull 5) O(1/8" polylog(1/6))
While this cost is independent of the dataset size N, the cubic dependence on 1/s can still be substantial.
Motivation for Interaction. The ( complexity arises directly from the need to execute the residual estimation algorithm locally. This motivates exploring interactive approach. If V could somehow leverage the computational power of P to perform the O(1==²) function evaluations required for residual estimation, while still retaining statistical guarantees against potentially dishonest P, the Verifier's workload could potentially be reduced.
This is precisely the approach taken in the remainder of this paper. We develop two-message interactive protocol where V challenges to perform the function evaluations needed for residual estimation. To ensure P's responses are trustworthy, V employs spor-checking mechanism, verifying a small random subset of P's computations locally. As we will show, this spot-checking strategy, combined with proof that the residual estimation algorithm is robust to a limited number of undetected errors (Section D.1, Lemma 1), allows V to achieve PAC verification with a reduced cost of O(1/²² p1l))og(1/8)). matching the complexity of the simpler MSE estimation step.
4 An Improved Interactive Protocol
In this section, we describe our improved interactive protocol. The formal protocol and its analysis are given in Appendix section C. Our protocol uses subroutinc the residual estimation algorithm
8

---

(Algorithm 1) of Saunshi et al. (2022). As part of the analysis of our improved protocol, we will need to analyze this residual estimation algorithm precisely, using the details of the algorithm's implementation. In Appendix section B, we give detailed overview of the algorithm.
Round 1 (V P): Challenge Setup.
The Verifier V generates set of computationnl "challenges" for the Prover P. These challenges consist of |8| ((log(1/)) ( randomly selected subsets of the training data ~ B,, using specific random seeds provided by V. Here |E] the number of samples that
will be used for the residual estimation algorithm.
V secretly designates a randomly chosen subset of k (1lo((1/0)/e²) of these challenges for later "spot-checking."
V sends the list of training subsets and their corresponding random seeds to P.
Round 2 (P V): Honest Prover's Response.
The Prover computes the optimal data attribution scores for the full dataset S.
performs the training runs requested by V in Round 1, using the specified subsets and random seeds.
sends the resulting trained model weights for all challenges, along with the computed attribution scores a, back to V.
Round 3 (V): Verification.
Spot-Checking: V repeats training runs for the challenges designated for spot-checking in Round I. V checks if the resulting models are equivalent to those sent by P (using an equivalence checking procedure). If any inequivalence occurs, aborts.
Consistency Check: If the spot-checks pass, V uses the model results provided by P (for all non-spot-checked challenges) to perform two estimations:
(a) For O(log(1/5)/88 models, evaluate the model output function f, and use them to estimate a = mse (a, ().
(b) Run the residual estimation algorithm (Theorem 2) minw (p) (w,
estimate s
compares a and [3. If and B deviate by more than e, V aborts.
Output: all checks pass, accepts and outputs the attribution scores provided by Otherwise, V outputs abort.
Now that we have a sense of the key steps involved in the improved protocol, we can sketch a proof of its guarantees.
4.1 Proof Sketch of Main Theorem
Due to space constraints defer the full proof to Appendix section D, and simply sketch the main ideas behind each correctness guarantee for the protocol.
Completeness. To argue completeness, start with the observation that if the Prover is honest, then the "spot-checks" used in the protocol will pass. In this case, the Verifier able to accurately estimate both the optimal linear prediction error using the residual estimation algorithm, and the actual error of the Prover's ' candidate attribution scores using local training runs.
Since the honest Prover submits the optimal scores a" Φ(S) (or e-close to optimal), these two errors are close, causing the final consistency check to pass and the Verifier to accept the correct attribution.
Soundness. To prove soundness, will consider different cases. First, where a dishonest Prover lies about "many" of the challenges, and second, where the dishonest Prover lies about "a few" of the challenges. In case one, we show that the Prover will be caught with high probability by the Verifier's random spot-checks; intuitively if the Prover lies about more than a certain fraction of the requested trainings, the Verifier will catch the Prover after conducting the appropriate amount of spot checks, with high probability. In this case, the Verifier outputs "abort" with high probability. In case two, the Prover might lie about less than that fraction of the challenges, and we will show that the Verifier's spot checks may all pass, but that despite this, the residual estimation will still be good. At technical level, in Lemma we show that the residual estimation algorithm of Saunshi et al. (2022) robust to ((1/)) adversarial corruptions. As result, in this case, even if the Prover has submitted incorrect

---

candidate attribution scores a', then the Verifier's s local estimate of the high error mss(P) (f., (a will then significantly exceed the estimated optimal error, causing the final consistency check to fail and the Verifier to abort.
Efficciency. To show efficiency, will directly estimate the expected number of model trainings done by the Verifier, which is straightforward: it is the sum of the number of model trainings in Round 3, which consists of (l/lo(1/0)/// spot checks, and (log(1/0))/²) to estimate the MSE. Thus the overall cost is ((log(1/))
References
Bae, J., Ng, N., Lo, A., Ghassemi, M., and Grosse, R. B. (2022). influence functions are the answer, then what is the question? Advances in Neural Information Processing Systems, 35:17953-1799
Broderick, T., Giordano, R., and Meager, R. (2020). An automatic finite-sample robustmess metric: when can dropping a little data make big difference? arXiv preprint arXiv:2011.14999
Castro Fernandez, R. (2023). Data-sharing markets: Model, protocol, and algorithms to incentivize the formation of data-sharing consortia. Proc. ACM Manag. Data, 1(2).
Choe, S. K., Ahn, H., Bae, J., Zhao, K., Kang, M., Chung, Y.. Pratapa, A., Neiswanger, W., Strubell, E., Mitamura, T., Schneider, J., Hovy, E.,, Grosse, R., and Xing, E. (2024). What is your data worth to gpt? Ilm-scale data valuation with influence functions.
Engstrom, L., Feldmann, A., and Madry, A. (2024). Dsdm: Model-aware dataset selection with datamodels. arXiv preprint arXiv:2401. 12926.
Feldman, and Zhang, C. (2020). What neural networks memorize and why: Discovering the long tail via influence estimation. Advances in Neural Information Processing Systems, 33:2881-2891
Georgiev, K., Rinberg, R., Park, S. M., Garg, S., Ilyas, A., Madry, A., and Neel, S. (2024). Attribute- to-delete: Machine unlearning via datamodel matching.
Ghorbani, A. and Zou, J. (2019). Data shapley: Equitable valuation of data for machine learning.
Goldwasser, S., Kalai, Y. T., and Rothblum, G. N. (2015). Delegating computation: interactive proof's for muggles. Journal of the ACM (JACM), 62(4):1-64.
Goldwasser, S., Micali, S., and Rackoff, C. (2019). The knowledge complexity of interactive proof- systems. In Providing sound foundations for cryptography: On the work of shafi goldwasser and silvio micali, pages 203-225,
Goldwasser, S., Rothblum, G. N., Shafer, J., and Ychudayoff, A. (2021). Interactive proofs for verifying machine learning. In 12th Innovations in Theoretical Computer Science Conference (ITCS 202/), pages 41-1. Schloss Begstuhl-Leibbiz-ZZee
für Informatik.
Grosse, R., Bae, J., Anil, C., Elhage, N., Tamkin, A., Tajdini, A., Steiner, B., Li, D., Durmus, E., Perez, E.. al. (2023). Studying large language model generalization with influence functions. arXiv preprint arXiv:2308.0322
Gun, K., Webson, A., Pavlick, E., Dixon, I.., Tenney, I., and Bolukbasi, T. (2023). Simfluence: Modeling the influence of individual training examples by simulating training runs.
Ilyas, A., Park, S. M., Engstrom, L., Leclere, G., and Madry, A. (2022). Datamodels: Predicting predictions from training data. arXiv preprint arXiv:2202.0000 00622.
Jain, S., Hamidieh, K., Georgiev, K., Ilyas, A., Ghassemi, M., and Madry, A. (2024). Data debiasing with datamodels (d3m): Improving subgroup robustness via data selection.
Jia, R., Dao, D., Wang, B., Hubis, F. A., Hynes, N., Gurel, N. M., Li, B., Zhang, C., Song, D., and Spanos, C. (2023). Towards efficient data valuation based on the shapley value.
Koh, P. W. and Liang, (2017). Understanding black-box predictions via influence functions. In International conference machine learning, pages 1885-1894, PMLR.
10

---

Law, J. (1986). Robust maaisticssthh approach based on influence functions.
O'Donnell, R. (2014), Analysis of boolean finctiins. Cambridge University Press.
Park, S. M.. Georgiev, K., Ilyas, A., Leclere, G., and Madry, A. (2023). Trak: Attributing model behavior at scale. arXiv preprint arXiv:2303.14186
Pawelczyk, M., Leemann, T., Biega, A., and Kasneci, G. (2023). On the trade-off between actionable explanations and the right to be forgotten. In International Conference Learning Representations (ICLR).
Saunshi. N., Gupta, A., Braverman, M., and Arora, S. (2022). Understanding influence functions and datamodels via harmonic analysis. arXiv preprint arXiv:2210.01072.
Shah, H., Ilyas, A., and Madry, A. (2024), Decomposing and editing predictions by modeling model computation. arXiv preprint arXiv:2404.11554
Vadhan, P. (1999). study of statistical gero-knowledge proofs. PhD thesis, Massachusetts Institute of Technology.
Yeh, C.-K., Kim, J. S., Yen, I. E. H., and Ravikumar, P. (2018). Representer point selection for explaining deep neural networks.

---

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 abstract and introduction claim the development of an interactive PAC- verification protocol for data attribution that is efficient for the Verifier, and provides formal completeness and soundness guarantees. These claims are directly addressed by the main theoretical contributions presented in Theorem and Algorithm with proofs and detailed explanations provided in the subsequent sections and appendices. The scope, while focusing on linear functions over the boolean hypercube and its applicability to data/component attribution, is also consistently maintained, though it is very broad scope in the context of data attribution as almost all methods fall in this category.
Guidelines: [NA]
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The paper discusses limitations. For instance, the (valid) assumption of bounded model output function (Line 229 footnote, Line 277) is stated. The practicalities and assumptions of the equivalence checking procedure are also briefly mentioned. The computational burden on the (assumed powerful) Prover for the interactive steps also an implicit consideration.
Guidelines: [NA]
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Ys]]
Justification: Complete proofs of all central claims are included in the appendix, in addition to all proof sketches in body.
Guidelines: [NA]
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of 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 or not)?
Answer: [NA]
Justification: This is theory paper. Provable security verifiability inherently requires theory, given that we provide guarantees against all possible adversaries. Future work on implementation may involve heuristies based this work.
Guidelines: [NA]
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: There is no data or code that goes with this paper.
Guidelines: [NA]
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?
12

---

Answer: [NA]
Justification: No models were trained or tested as part of this paper.
Guidelines: [NA]
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate
information about the statistical significance of the experiments?
Answer: [NA]
Justification: No statistical experiments are conducted as this is a theory paper consisting of mathematical proofs.
Guidelines: [NA]
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [NA]
Justification: There are no experiments since is primarily theory paper.
Guidelines: [NA]
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http:/::///eeueeeeeeeeee httpp///cepppceeetttttiiieeellll
Answer: [Yes]
Justification: The research presents theoretical framework for verifying data attributions. does not raise immediate concerns under the NeurlPS Code of Ethics. The aim the work is improve trust and transparency in ML systems, which aligns with ethical considerations.
Guidelines: [NA]
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper discusses motivation issues trust and safety of ML systems.
Guidelines: [NA]
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: [NA]
Justification: The paper focuses on a verification protocol for data attributions, not on the release of new data or models that might have risk of misuse.
Guidelines: [NA]
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: Relevant work is appropriately cited throughout the paper.
Guidelines: [NA]
13. New assets
13

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: No assets.
Guidelines: [NA]
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: No human subjects were used as part of this work.
Guidelines: [NA]
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: There are no study participants.
Guidelines: [NA]
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 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 required.
Answer: [NA]
Justification: The paper does not use LLMs as part of core methodology.
Guidelines: [NA]
14

---

A Preliminaries
A.1 Harmonic Analysis the p-biased Cube
Our work (and important prior work like Goldwasser et al. (2021) and Saunshi et al. (2022)) leverage tools that grounded in the analysis of real-valued functions defined the discrete hypereube, specifically under a non-uniform measure known as the p-biased distribution (see e.g. O' Donnell (2014) for a comprehensive overview of Boolean Fourier analysis). In this section, we will go over the necessary concepts for understanding the mathematics presented in this paper.
Let N = -S) be the size of the training dataset. Recall that we represent subset of the training data by a vector x E {+1}, N. where 2; = 1 indicates the i-th datapoint is included and z; = -1 indicates it is excluded. The model's 's behavior (e.g.. loss logit difference subset represented by x is given by a function f {+1} + R.
test point) after training the
We consider the p-biased distribution B, over {+1) where each coordinate is independently chosen to with probability p and -1 with probability p. Let BE [xx]] = p- (1-p) = 2p
and o² Var(x;;) EE |사ا|| (EE [ax]]² corresponds to p = 1/2, where μ 0 and =
(2p 1)² 4p(1 p). The uniform distribution
The space of functions f {+1) - forms a vector space equipped with the inner product (f. g)., Ez~88 (f)))((x)) An orthonormal basis for this space is given by the characters
{ds)s defined as:
T E
(5(2)
These basis functions satisfy [0s(+)) = 0 for S * and (Øs, OThE, = 65.T (Kronecker delta). Any function f can be uniquely expanded in this basis as:
f(z) Σ fsos(z),
SCINI
where fs = (f. (f. = EzuB, [(x)) are the Fourier coefficients of f. Parseval's 's identity states:
| = B. [f(x)
Σ L
SCIN
The coefficients fs capture the contribution of interactions among the datapoints in S to the function f- Of particular importance are the degree-1 coefficients f(i). which, up scaling by 2/a,, correspond to the average influence of datapoint and the optimal coefficients for linear datamodels (Saunshi et al., 2022, Theorem 2.2). To denote the total Fourier weight at degree k, let
B₁ A
(3)
S:[S==k
To analyze the structure of f, we use the concept noise stability. Definition 2 (p-correlated variables). For [+1]N drawn from Bp say random variable a! p-correlated to if it sampled coordinate-wiz independently as follows: For each i [N],
If = 1, then x/ 1 with probability (1 - p1 -p). and x otherwise.
1f r; = 1, then x = 1 with probability p(1 - p). and a = otherwise.
Crucially, x' is also distributed according to Bp
The noise stability of f noise rate p [0, is defined hy(p) Ey. [xx)) where & ~ B, and x' is p-correlated to æ. It admits a simple expression in terms of the Fourier weights:
hp(p) Σ Bap
This shows that the noise stability a polynomial in A. whose coefficients are precisely the total Fourier weights Bş at each degree k.
15

---

B Efficient Estimation of Linear Datamodel Residual
As established by Saunshi et al. (2022) (specifically their Theorem 2.2), the quality of the best linear datamodel approximation 0o + Σ Ocz, for a function f: {+11* - under the y-biased distribution By is determined by its residual emror:
R(0*) A B22= SCIN:
where 0* denotes the coefficients that minimize MSE of the datamodel Oo Limi 0,æ; with respect to the model output function f (Saunshi et al. (2022) use the notation R((0), so we include that here for clarity, even though throughout the paper we refer MSE explicitly).
Saunshi et al. (2022) cleverly leverage the connection between degree-k weight of f and the noise stability of (p))). Recall from (4) that
hy(p) = Σ BBp
k=
Separately, the total squared norm is |1 En_o BB h Therefore, the residual error can be expressed purely in terms of the degree-O and degree- Fourier weights and the total norm:
B22 B Bo B1 (1 Bo Bı
The algorithm from Saunshi et al. (2022) leverages this fact as follows:
1. Estimate Noise Stability at Key Points: Choose a small number & of distinct noise levels {P1,..- p (e-g., P; 2p for some small p) and additionally use p= 1. For each chosen (and for = 1), estimate the noise stability value hy (p)) by sampling multiple pairs (z,x²) of pooorellated inputs drawn from B, and averaging the product f(x) Let
these estimates be Új = hp(p)) and B =s (1)
2. Low-Degree Polynomial Fitting: Since hy(p) = Bo + Bip + B2p² + use the estimated values (py, 0)) from the previous step to fit a low-degree polynomial (e.g., degree d =) 2) P(p) -i Bip'. This is done via (non-negative) least squares, solving for the coefficients Bo. BI...,,a.
3. Calculate Residual Estimate: Combine the estimated total norm Ó (1 and the estimated lew-eegrce coefficients Bo, B1 obtained from the polynomial fit to compute the final estimate the residual error: Bz2 B Bg B1-
This approach allows estimating the quality of the best linear fit using a number of samples that is proportional to 1/e² for desired approximation error but is independent of the dimension N.
16

---

C
Our Full Protocol
We present our protocol for PAC-verification of empirical influence (Theorem 1), detailed in Algo-
rithm
Algorithm
1 Interactive PAC- Verificciin Protocol for Empirical Influence (Φ)
Shared Information:
Model Architecture, Training set $ S X' ([S) = N), subsampling probability Training loss function L. Stopping criteria for training.
Model output function f: {+1} E derived from training.
Equivalence check procedure (HUCCEQUIV(O,,...) 02). Verifier (V) Input:
Approximation parameter E (0, 1). Confidence parameter 5 (0, 1).
Round 1: Verifier (V) - Prover (P)
1: Sample M (m(m) ( (og4 where each w(1)) ~ Bp.
Subsets for final MSE check 2: Choose ((vE). Sample n O(1/e² log(1/0)) pairs ((x!*) ) where a!*) Bp and xte)
is p-correlated to (*)), Let E be the set of all unique subsets appearing in these pairs (at most 2n subsets). Subsets for residual estimation 3: Choose random seeds R < {re}a.En for training models on subsets E.
4: Set spot-check size ks O(1/e" 1og(1/5))- Sample spot-check set C S of size k uniformly random.
k will ensure high prob. detection Seeds R are indexed corresponding to subsets in F.
5:
Send (E, R) to P.
Round 2: Prover (P) Verifier (V)
6: Compute attribution a* + (SS).
Computationally expensive
7:
For each Ie E do
8: Train model with seed r. on subset ir to get weights Oc.
9: End For
10: Let θ = [0e
11: Send a0, V.
Sends all trained models and the computed attribution
Round Verifier (V) Verification and Output
12: Spot-check:
For each F. do
14: Train model with seed subset get local weights d..
V performs limited training Let 6', be the model weights received from a (possibly dishonest) Prover for subset Xe- Check if Prover's 's result matches Verifier's
15:
16: If not CHECKEQUIV( 6()) then
17:
Output: abort and Terminate.
18: End
19:
End For
20:
All spot-checks passed
21: Use received models 6' define the function values f'(x:) for Ie E E.
Compute residual estimate B2 + RESIDUALESTIMATION f') on E, p, budget [E].
23:
Uses function values derived from P models (for xe C)
24: For um MM do
25: Train model with fresh random seed r', on subset 7.m. to get weights 6.. V trains models for MSE estimate
26: Evaluate f fxm) using 8m.
27: End For
28: Let g(x) = (a*,x). Estimate msep(J.g) + TAT Exmem (f(mm) 3
29: mf B22 + e/2 then
30: Output: abort and Terminate.
31: Else
32:
Output: a'
Accept the Prover's attribution
33: End
17

---

The Equivalence Checking Procedure. Note that we assume access to sutivalence-checkin procedure between model training runs. The exact implementation of CHECKEQUIV depends on the training setup. Ideally, even with fully deterministic training (with a fixed architecture, data subset Tees and randomness seed r2), this check could be direct comparison of model weights (0.. = f')) However, practical MI training can exhibit non-determinism (e-g., due to GPU parallelism). In such cases, CHECKEQUIV might involve comparing model outputs on a held-out test set, comparing final loss values within tolerance, or potentially using cryptographic commitments or hashes if sufficient determinism can be enforced.
D Proof of Main Theorem
In this section, we will prove that the protocol outlined in Algorithm 1 works to witness Theorem 1. For now, let us start with outline of our proof.
Completeness. To argue completeness, we start with the observation that if the Prover is honest, then the "spot-checks" used in the protocol will pass. In this case, the Verifier is able to accurately estimate both the optimal linear prediction error (Bz2) using the residual estimation algorithm, and the actual error of the Prover's candidate attribution scores using local training runs.
Since the honest Prover submits the optimal, or near optimal, scores a* o(S). these two errors close, causing the final consistency check to pass and the Verifier to accept the correct attribution.
To prove soundness, will consider different cases. First, where dishonest Prover lies about "many" of the requested model trainings (f'), and second, where the dishonest Prover lies on "a few" of the requested model trainings.
Soundness.
In case one, we show that the Prover will be caught with high probability by the Verifier's random spot-checks. In this case, the Verifier outputs "abort" with high probability.
In case two, we will show that the Verifier's spot checks may all pass, but that despite this, the residual estimation will still be good. That is, we show that it is robust to some adversarial corruptions. We prove a standalone lemma to accomplish this.
As a result, in this case, even the Prover has submitted incorrect candidate attribution scores a', then the Verifier's 's local estimate of the high error mse(P) (f,, (a', will then significantly exceed the estimated optimal error B22, causing the final consistency check to fail and the Verifier to abort.
Efficiency. To show efficiency, we will directly estimate the expected number of model trainings done by the Verifier.
D.1 Supporting Lemma: Robust Residual Estimation
Before proving the main theorem, we establish the robustness of the RESIDUALESTIMATTIO subrou- tine against a limited number of adversarial corruptions.
Lemma 1 (Robust Residual Estimation). Let f {+1]N + [-b, be bounded. Let B2g be p.n. using degree d = 2, points [0, p. 2p] (and p = 1). and based on n evaluations of f run on the same sample points, but where an adversary corrupts up to m ((1/s) of the function evaluations, by replacing f() with f'(x) [-b, Let
the output of DESIDUALESTIMAATIONNS
= 0 (10), and p = O(vE).
Then, with probability at least 5/4 (over the internal randomness of the algorithmm):
B32 B22l Ō(b²E)
where the constant in Ö(-) depends on but not on n, m, E, N.
Proof of Lemma J. Let us first recap the RESIDUALESTIMATTONN algorithm.
RESIDUALESSIMATIIN uses total function evaluations, distributed among estimating (O),
hy(p), (2p) and hy()). Let no, npr 722 be the number pairs (z,z²) sampled to estimate
(0)(), (p), hy respectively, and let Ni be the number of samples x used to estimate h (1)
E [f()]] The total number of function evaluations is (no + no + m2p) x 2 + N1.
18

---

Let 8o: Up. V2p be the empirical estimates of (0), f (p), (2(p)) obtained using the original func- tion f evaluations from the samples. Let B be the estimate of hy(1) = E [f())]] Let y Lão. Mp. 522l". The algorithm RESIDUALESTTMATTION uses these estimates, which are corrupted by any adversary, compute the uncorrupted residual estimate Bz2. Specifically, a vector z [Bo. B1, Bu]" found by solving the constrained least squares problem
arg min || Az 811 220
(5)
Here,
A =
1
(6)
2p
4p²
Then B (ž) would correspond to Bo, ă2 would correspond to B1).
O(1/e) of the n function evaluations. Let f'(x) denote the value used in the computation after potential corruption. Since f {=1] 4
Now, we consider the setting where an adversary corrupts
[-b, b). we also have (x( [-b, b). Let do Uo: 82p be the estimates using the potentially corrupted
values f", and let B be the estimate of [f) Let y = [To. Pp- 02pl IT. Let:
2 = [Bo, B1, B2)" arg min Az 811
and B22 = B 22.
Our goal is to bound |Brr Bz2/, where Bzg is the "true value" (assume exact estimation). We use the triangle inequality:
B2 - B22l < B| 21
1 - -22
Here 21, 72 are the "true coefficients" of the noise stability polynomial (recall equation 4). To do this, will apply the triangle inequality again, and bound each of the terms the RHS above, by LB B
BI L B), and similarly, | zı| 1 3 121 zz).
First, bound the difference in the estimates Ú; 1i- -ū and i B. Consider ú, Dp- This is the difference between the average of (zx) and f(x)f(x') over n2 = (nn) pairs. An adversary corrupts m function evaluations total. Each term f(z) uses two evaluations. At most m terms in the average can be affected by corruption. Let S, S [np] be the indices of the affected terms. |Spl S m.
Úp úp 1 -(()))(())()))
Tpp jES,
Since (=(=))(==)) and [f()) < 12, the difference in each term is bounded by 262.
26 < m 26
10p - Tol S np jES,
Σ
Thp
Similarly,
m7 21
1300 Dol 1
(8)
710
and
2b2
1020
T2pl
(9)
12p
Also,
1 (
2b
B- B
(10)
N
Ni
jES,
Then the maximum element-wise error bounded:
2mbb
2mb
2mb²
mb²
-1loo S max
0
no
n
n2p
n
19

---

Since log//))) and m = O(1/E), we have
| - 51100 =0 = 1/58
(1///)))
O(6?=7)
Similarly, [ -(P2).
Now, we can bound the difference between the uncorrupted estimates yo, p, D2p and the "true values" hy(0), (p),,, hy
using standard concentration inequalities. For instance, see Lemma A.1 of Saunshi et al. (2022), which shows that the estimations are close enough to the true values with probability - 8, i.e. h(p) h(p) Tp where 17pl where O( (log((//)))
At this point, we can combine the adversarial bound and estimation error bounds for the noise sensitivity estimates, and complete the analysis as do Saunshi et al. (2022) in their analysis of RESIDUALESTIMATION
From above, we have, with high probability.
y y|l I 1 y
(c + ll y/l S 50 - 0(5)13
S 0(12)3/2
Then, applying the analysis from Saunshi et al. (2022) (Theorem 3.2), of how the perturbed estimates affect the constrained least squares solutions, we get
12g8/22
B B and |& - 21| and 122 - 22| R
+ Beap²
P
Hence,
1/28//2
Bz Bz2l 5o
+ B2ap²
Finally, for the setting of p Ve, and observing that B23 S 1s2 we obtain the desired expression.
B22 1-2-B221-0 B221 Obb's)
D.2 Proof of Main Theorem
Proof Theorem J. We prove Theorem by establishing Completeness, Soundness, and Efficiency as per Definition 1. Recall that we assume [f(z) < b =11). We set internal protocol confidence parameters for subroutines to 8' 8/4.
D.3 Completeness
For completeness we can assume both and P follow the protocol.
1. Prover's Output: Honest P computes a' (S) and correct models 0. We have crr(a", +(S)) S sends a0)
2. Verifier's Spot- ChecCCheck: Passes with probability 1, assuming deterministic training given fixed random seeds.
3. Verifier's Consistency Check:
(a) Residual Estimation: V uses correct 0 for f values. By Theorem 2, using [E] 2 log(1/8')), [Bzz - B22l < e/4 with probability at least
8'.
log(1/8')), (b) MSE Estimation: V uses local trainings for M. With [M] = ))))))))))))) by Hoeffding's inequality, [s (a*, Bz2l e/4 with probability at least 8'.
(c) Final Check: Compare mfe,(f. (a*.-) with B32 + e/2. With probability at least
1 28', both estimates within e/4 of Bz2. Then mse, B22 + e/4 and B e/2 2 (B22 - e/4) + e/2 B22 e/4. So, isse, S B2g + 8/2 Therefore the final check passes.
20

---

4. Verifier's Output: V outputs a" with err(a", (aaaaa,,,,3 ,(()) = 0 S E.
The overall success probability is at least 1 - 28' =1- 6/2 - proved.
6. Therefore completeness is
D.4 Soundness
To analyze soundness, we will proceed by case analysis. The first case deals with scenario where the Prover very dishonest, in the sense that many of the requested model trainings from the set E (see Round of the protocol) are wrong.
The second case will be mutually exclusive, and deal with the scenario where the Prover is mildly dishonest, in the sense that not too many of the requested model trainings are wrong. In this second case, the residual estimation robustness lemma (lemma will be useful.
To begin, recall that the dishonest Prover is sending (0',a)), Let W be the set of corrupted challenges where &g is not equivalent to correctly trained model, and let the number of corruptions be m = [ Let |E| be the total number of challenges sent to the Prover for residual estimation. We define the threshold for "many" corruptions by setting critical point m = c/E for sufficiently large constant c. The number of spot-checks is k = O(1/=² log(1/))).
Case 1: m > m'. In this case, we show that spot-check will fail with high probability. The Verifier samples set of ls challenges check. The Prover is caught if C n W * 0. The probability that the Prover is not caught is the probability that all checks land outside of the corrupted set W. This probability can be upper-bounded by sampling with replacement:
[E]
m
m
Pr[not caught]
E
E
Since m > m² = c/s, we have:
C/E
Pr|not caught] 1
S
(c
[E]
Substituting 1 = / log(4/)) and |E] = Ce/e² e -oo(1/0) for constants C", Ce. we get the exponent:
C" log((4/))
c/e
C'c log(//)
22 Cy log(1/8)/
Ce log(1/5)
By choosing the constant in the definition of m² be large enough, this exponent can be made smaller than - (4/5)), ensuring the failure probability is less than 8/4. Thus, we conclude V aborts with probability at least 8/4.
Case 2: m & m this second case, all spot-checks may pass with some probability. Let us (conservatively) assume that all checks indeed pass, and then consider how this affects the Verifier's output.
We analyze the protocol, step by step, in this case.
(1) Robust Residual Estimation: V runs RESIDUALESTIMATIUN using the function values derived from the models 0' sent by the Prover. Since m S m O11/e), the number of corruptions is within the required bound for Lemma 1. Therefore, the lemma applies directly.
We have BB2 Bz2l e/4 with probability least 1 8-8' 8'.
(2) MSE Estimation: V estimates mssep(ssg) for g' (a', This happens with local samples in the set M. Therefore, we can conclude that [f g') (P) (f.g') e/4 with probability at least 1 8', by applying standard Chernoff bounds.
(3) Final Check Condition: Assume err(a', ((S)) > which means mse (r) (f.g') > B22+E
with probability at least 1 25', we have (f, > msc (f.g') (ffgg))e/44 -e/4> (B22+E)-
e/4 = Bzg + 38/ Also, Bzz < B22 + e/4. Then B22 + e/2 (Bz2 + e/4) +
B22 B 35/4. Since msse, ('))) > B22 +ee and B22+3e/4 > B the condition
msee (f.g') B22 + E/2 holds.
21

---

(4) Verifier Output: If (er(aa, > and m I m², V outputs abort with probability at least 28'.
Combining Cases: If err(a' (S)) > c, the probability V does not abort is at most Pr [Case fails) + Pr [Case fails] I 8/4 28' 6/4 + 8/2 36/4 S 8. Therefore Sound- ness holds.
D.5 Efficiency
Finally, we consider efficiency. The Verifier's cost k(e, 6) the number of model trainings.
1. Spot-Checking:
The number of spot-checks is deterministic.
k == O01/s"2
2. MSE Estimation: |M| log///))
Thus, the total cost is O(1/c² 1og((/))) Treating 8 as constant yields k(c, O(1)) 0(1/e7).
E
Verifying Attributions for Multiple Test Points or Outputs
Our primary protocol (Algorithm 1) and its analysis (Theorem 1) are presented for verifying attribution with respect to single model output function f. However, a common and practical requirement is to obtain attributions for model's behavior across multiple distinet scenarios, such its predictions Z different test points, or changes in Z different output logits. This gives rise to a set of Z model output functions, {ʃ= - where each fa : [+1] - [-b, bj. For each Sz, there is corresponding empirical influence attribution $(S, =) and an optimal linear prediction residual B22,2-
The goal is to extend our verification framework such that the Verifier V can, with overall confi- dence simultaneously accept Z attribution vectors {a{) from the Prover and only err(a', (S, =)) < for all E [2]. This section details how our protocol can be adapted to achieve this, maintaining efficiency and the two-message structure.
The core strategy involves adjusting the internal confidence parameters of the statistical estimation subroutines using union bound. If the overall desired failure probability for the entire of Z verifications is 8, then the failure probability allocated to any critical estimation step concerning an individual function fz must reduced directly impacts the sample complexities, but only logarithmically in Z.
z 8/Z. This tightening of per-instance confidence
We formalize this extension with the following theorem:
Theorem 3 (PAC-Verification for Multiple Output Functions). Assume that for each E [Z]. the
model output function f= {=1] + [-b, bj for some constant b. For any & E (0. 1), and Z 2 1, there exists (EA verifier for the set of Z empirical influence operators ( 2) 2 The Verifier's expected cost function Kz (number of local model trainings) satisfies tzz E ((11/2).
polylog(Z) polylog(1/// (o))) The interactive protocol requires only two messages.
Proof Sketch for Theorem 3. The proof adapts the logic of Theorem by incorporating the union bound across the Z output functions. Let d, = 6/(4Z) be the target failure probability for individual statistical estimation steps (like residual estimation MSE estimation for a single fa) and for the spot-checking mechanism's 's success in detecting a certain level fraud for any fs. The result follows immediately from the logarithmic dependence of the sample complexities on f in each step.
F
Why PArifccificatioon and not Delegation of Computation?
As first mentioned in section 2, one might initially consider employing general-purpor cryptographic protocols for delegation of computation or verifiable computation to ensure the Prover P performed the expensive attribution computation correctly. However, such approaches are insufficient for the
22

---

verification goal central to our work. First of all, computational overhead of the cryptographic machinery is typically massive. and in our setting, the Prover has already pushed the limits of their feasible computations. Second, cryptographic protocols typically do not give guarantees for the statistical quality of the output. particular, whether the resulting attribution scores a' are indeed e-close to the optimal scores (S)).
For instance, if the Prover uses skewed, unrepresentative, or otherwise low-quality subsets for its internal estimation process (whether maliciously or inadvertently), a general-purpose delegation protocol might still verify the computation's 's execution correctly based those flawed inputs, offering no protection against poor-quality final result in terms of predictive accuracy. Note, the Verifier cannot supply the inputs due to computational constraints. A practical example of when the use of flawed inputs might occur is if the Prover itself obtains trained models from a public ledger or otherwise untrusted source.
Thus, when the Prover's computational steps are correct, standard cryptographic verification proce- dures would necessarily identify bad attributions. In other words, it does not inherently assess whether the output meets statistical benchmark defined relative to the underlying data generating process or the optimal achievable performance. The PAC-verification framework of Goldwasser et al. (2021) is designed precisely to handle verification of approximate correctness of the outcome relative statistical ideal (here, minimizing MSE), rather than merely the integrity of the computational steps taken.
23


Reviews:
[{"review_id": "q9TK0EdU1b", "reviewer": "Reviewer_fc4o", "summary": "This paper proposes a technical solution to the trust problem centered around data attribution vectors computed from datamodels. In this context, datamodels refer to mappings that quantify the relationship between subsets of a training dataset and the resulting performance of a model trained on those subsets. For example, given a fixed training set of size $N$, we can define a mapping $f: \\\\{\\pm 1\\\\}^N \\to [0,1]$, where the selection vector $x \\in \\\\{\\pm 1\\\\}^N$ indicates which data points are included in the subset and $f(x)$ gives the final 0/1 loss of the classifier trained on that subset.\n\nCurrent approaches compute data attribution vectors from datamodels. They are defined as the linear coefficients $a \\in \\mathbb{R}^N$ of the optimal linear approximation to $f$ with respect to an inner product. For simplicity, we work in the inner product space induced by the uniform distribution over $\\\\{\\pm 1\\\\}^N$. The analysis extends essentially unchanged to the case of i.i.d. products of $p$-Bernoulli distributions. These vectors have important practical applications, such as data pricing, allowing one to compensate individual data points within a training set according to their “influence” on the final performance of the model.\n\nEvaluating the datamodel $f$ on each training subset $x$ is extremely expensive, and therefore computing honest data attribution vectors creates significant asymmetry and trust issues. Only a few parties have the resources to perform these computations, while most others must rely on, and therefore trust, this small group of powerful actors. The paper addresses this asymmetry by introducing an interactive protocol in which the Verifier can check the *optimality* of the Prover’s data attribution vector with much less computational cost. Here, the Verifier’s computational cost, defined to be the number of datamodel evaluations, is shown to be *independent* of the dataset size $N$.\n\nA key technical insight comes from previous work by Saunshi et al., who observed that computing certain Fourier coefficients of the residual $g(x) = f(x) - \\langle a, x\\rangle$, given $a$ is much cheaper than computing the attribution vector from scratch. The novelty of this paper lies in formulating the trust problem as a PAC verification task and offloading the computation of the residual’s Fourier coefficients to the Prover. With the spectral computation pushed to the Prover, the Verifier only needs to perform random spot checks on the Prover’s results to verify their validity. The offloading reduces the Verifier’s computational cost from $1/\\epsilon^3$ to $1/\\epsilon^2$ (ignoring other parameters of the interaction), where $\\epsilon$ denotes the (additive) suboptimality of the Prover’s candidate attribution vector relative to the optimal one.", "questions": "1. Could the authors discuss the shortcomings of the current definition of Verifier’s computational cost?\n2. What general assumptions on the equivalence checking procedure are sufficient to preserve the PAC verification guarantees?\n3. How sensitive are the attribution vectors to the choice of $p$ in the $p$-Bernoulli marginal distribution over selection vectors? For example, are there empirical studies examining how the ranking of data point influence varies with $p$?", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n1. **Compelling narrative and motivation.** The paper presents a creative and well-motivated application of interactive proofs, clearly explaining how asymmetry in computational cost creates trust problems in data attribution, and highlighting the need to resolve them for practical applications such as data pricing. Formulating this trust problem as an interactive protocol feels natural and provides an elegant framework for a real, practical issue.\n2. **Insightful use of tools from theoretical computer science.** The paper elegantly combines Fourier analytic ideas from Saunshi et al. and techniques from interactive proofs to arrive at a quantitative improvement. Because random spot checks are sufficient to detect the Prover’s deviations with high probability, the Verifier can shift the computational burden of residual estimation to the Prover, an approach very much in the spirit of probabilistically checkable proofs (PCPs).\n3. **Clear, concise, and precise exposition.**  The paper is exceptionally well-written, presenting the technical content in an accessible way without compromising rigor. Moreover, the narrative and technical tools are tightly integrated, resulting in a seamless presentation that effectively connects the motivation to the methodology.\n\n### Weakness\n\n1. **Missing assumptions on equivalence checking.** The paper lacks precise details about the assumptions required for the equivalence checking procedure. I assume all PAC verification guarantees hold if model training is deterministic, with CheckEquiv(a_1, a_2) returning true if and only if a_1 = a_2. However, if there is significant randomness or noise in training outcomes, completeness and soundness guarantees may fail to hold. For example, if CheckEquiv always passes any input pair, the protocol would fail to satisfy soundness guarantees. A clearer specification of the conditions under which equivalence checking ensures both soundness and completeness would strengthen the paper.\n\n2. **Other choices of computational cost for the Verifier.** The claimed independence of Verifier’s cost from $N$ is somewhat misleading. While the number of datamodel evaluations required for the protocol is indeed independent of $N$, the cost of each individual evaluation can grow with $N$. For example, even with a fixed inclusion probability $p$, the expected training subset size scales with $pN$, and the cost of training a model on these subsets may increase accordingly. Moreover, in high-dimensional settings where the data point dimension $d$ scales linearly or superlinearly with the number of samples $N$, even parsing a single data sample can scale with $N$. In this sense, a more budget-relevant accounting of computational costs may not be truly independent of $N$. Clarifying these caveats and considering alternative, reasonable notions of the Verifier’s computational cost would strengthen the paper.", "was_revised": true, "final_justification": "Rating remains the same. Reasons are provided in my response to the authors' rebuttal.", "rebuttal": "Dear Reviewer fc4o,\n\nThank you for your kind and thoughtful review!\n\n**About the Notion of \"Efficiency\"**\n\nYour point is correct. We certainly don't mean to mislead and will clarify it in the final version. Currently, our use of \"efficiency\" refers to the Verifier's sample complexity (the number of retrainings), which is itself independent of the dataset size N. The cost of each individual retraining does of course depend on N, and we will make this distinction explicit in the final version of our paper.\n\n**Non-determinism in GPU training**\n\nWe would like to point out that we did discuss this, in the paragraph titled \"Equivalence Checking Procedure\" (Lines 536-543) of the submission. While the theorems as stated do assume a perfect equivalence checking procedure, the check-equiv procedure can be instantiated practically by, for instance, comparing model outputs or final loss values on a held-out set, rather than requiring a bit-for-bit identity of model weights. Any error in equivalence checking can be wrapped into the probabilities for soundness and completeness via union bounds.\n\nRegarding your question:\n\n> How sensitive are the attribution vectors to the choice of $p$ in the $p$-Bernoulli marginal distribution over selection vectors? For example, are there empirical studies examining how the ranking of data point influence varies with $p$?\n\nIn general, the choice of $p$ does affect the attributions. Different values of $p$ were used and studied in, for example, [1].\nHowever, due to high linearity observed in practice on typical benchmark settings (e.g., ResNet-18 trained on CIFAR-10), the values of attributions are not \"very\" sensitive to $p$.\n\nThanks again for your kind review!\n\nSincerely,\n\nAuthors\n\n-----\n\n**References**\n\n[1] Ilyas, A., Park, S. M., Engstrom, L., Leclerc, G., and Madry, A. (2022). Datamodels: Predicting\npredictions from training data. arXiv preprint arXiv:2202.00622."}, {"review_id": "ioIuNKLJ90", "reviewer": "Reviewer_cTDk", "summary": "This paper studies the \"verifiable\" problem for data attribution, an important growing field in data-centric AI. Specifically, the paper defines the verifying problem in data attribution and proposes an \"efficient\" interactive protocol that is PAC-verifiable.", "questions": "1. Can the authors discuss what is the role of the final attribution score $a'$ produced by the prover? Since, at the end of the day, if the prover is honest/passes the spot-checking, the verifier will use the provided models and curate the final attribution scores using the residual estimation algorithm. It seems to me that the attribution score $a'$ provided by the prover is useless in this sense.\n2. (**Weakness 1**) I suggest that the authors can elaborate and clarify the notion of efficiency used in this paper more explicitly.\n3. (**Weakness 2**) I understand that due to the space limits, no related works are presented in the paper. I suggest that (if published) the authors can add a dedicated related work section to carefully discuss the potential impacts and some design choices to help justify and position the paper in the literature.", "limitations": "While no specific limitations were discussed in the paper, the reviewer does not have additional concerns on potential limitations.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n1. With the growing interest in data attribution, with its potential societal impact on data compensation (or data economy), the problem studied in this work is indeed important and well-motivated.\n2. The writing is professional, consistent, and self-contained.\n3. The proposed algorithm and interactive protocol are clear and well-motivated (with the appropriate introduction to the prior works), which makes them easy to follow overall.\n\n**Weaknesses**\n1. If my understanding is correct, the notion of \"efficiency\" is the number of retrainings required. It is, hence, a bit misleading to say that the \"cost\" is independent of dataset size $N$. I suggest that the authors can elaborate and clarify this point in the next iteration.\n2. The scope of the present work is a bit restricted and not justified: for instance, the current vast data attribution literature has moved beyond retraining-based datamodel style methods to explore settings such as \"single-model TDA\" via, e.g., dynamic methods. I think the design of the present work is largely due to the prior work by Saunshi et al., which makes sense, but it'll be helpful to discuss this more in detail.\n\n**Writing**\nNothing really significant. Just want to point out:\n1. Page 13 can probably be handled more elegantly..", "was_revised": true, "final_justification": "I maintain my positive score, and no further concerns are raised after reading all the discussions with other reviewers.", "rebuttal": "Dear Reviewer cTDk,\n\nThank you for your kind and thoughtful review!\n\n**Notion of \"Efficiency\"**\n\nIndeed, you are correct. We definitely didn’t mean to be misleading and will clarify/correct it in the final version. Currently, our use of \"efficiency\" refers to the Verifier's sample complexity (the number of retrainings), which is itself independent of the dataset size $N$. The cost of each individual retraining does depend on $N$, and we will make this distinction explicit in the final version.\n\n**Scope/Relation to Other Methods**\n\nWe feel that focusing on datamodels and empirical influences in the context of predictive attribution will always be a worthwhile focus because they are the provably optimal linear attributions for minimizing predictive Mean Squared Error (MSE) (which is our metric). This is proved by [1].  Verifying w.r.t. empirical influence / datamodels thus addresses the fundamental question of whether a party has computed the best possible linear explanation. We agree that while related work is discussed as necessary throughout the body of the paper, a dedicated section would also be valuable, especially mentioning other lines of work like single model TDA. We will add this for the final version.\n\n**Prover's Attribution Score**\n\nThe Prover's attribution vector $a^{\\*}$ is very important. The core of the Verifier's protocol is to check if the error of this submitted particular $a^{\\*}$ is close to the optimal error (Algorithm 1). Without $a^{\\*}$ from the Prover, there would be no candidate solution for the Verifier to check.\n\nThank you again for your valuable comments. \n\nSincerely,\n\nAuthors\n\n\n-----\n\n**References**\n\n[1] Saunshi, N., Gupta, A., Braverman, M., and Arora, S. (2022). Understanding influence functions and datamodels via harmonic analysis. arXiv preprint arXiv:2210.01072.457"}, {"review_id": "EdoCx4Uj3m", "reviewer": "Reviewer_BYJZ", "summary": "Suppose that we train an ML model on an $N$ size dataset, and we would like to know how much each data element (or subset of elements) influenced the training. This is modeled by a function $f \\colon \\\\{-1,1\\\\}^N \\rightarrow \\mathbb{R}$, where each $x \\in  \\\\{-1,1\\\\}^N$ encodes a subset ($x_i = 1$ iff the $j$’th element is included in the subset), and this function can be estimated for every $x$ by retraining the model on the subset $x$ and then computing the prediction quality or test error of the new model. The problem is that computing this function is very expensive (each subset requires a fresh training), and we would like to compute an approximation of $f$, hopefully using only a few retrainings. The work of Saunshi et al. (2022) showed how to compute a linear model $a$ such that $f(x) \\approx <a,x>$, where the number of retrainings to obtain $a$ is only $\\approx 1/\\epsilon^3$, which is independent of $N$ ($\\epsilon$ is the required accuracy measured by the MSE distance from the optimal linear model). This is done using Residual Estimation.\n\n\nThis paper considered a model where we have two entities: a prover, which has more computational resources, and the verifier, which is more restrictive but still would like to get the estimation of $f$. The problem arises when the prover is not necessarily honest, so the verifier must have a way to check whether the linear model $a$ produced by the prover is indeed close to optimal. The main result of this paper is to provide a 2-message interactive protocol between the prover and the verifier, where the verifier, using only $\\approx 1/\\epsilon^2$ retrainings (and not $\\approx 1/\\epsilon^3$ as in the non-interactive version of Saunshi et al. (2022)), can catch an unhonest prover with high probability. The solution relies on the same Residual Estimation of Saunshi et al. (2022): The verifier asks the prover to perform the $1/\\epsilon^3$ retrainings, but checks only $\\epsilon$ fraction of them by doing the retrainings itself (where the exact $\\epsilon$ fraction is unknown to the prover). If the prover lied in more than $1/\\epsilon$ out of the $1/\\epsilon^3$ requests, the verifier will catch it with high probability. Otherwise, there could be at most $1/\\epsilon$ wrong values, so the main technical contribution of this paper is to prove that the approach of Saunshi et al. (2022) is error-robust against such an amount of errors.", "questions": "No questions", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I haven’t read the robustness proof that appears in the appendices (Lemma 1, page 15), but assuming it is correct, I think it is a nice paper that provides a nice solution to a well-motivated problem while addressing a real technical challenge (the robustness of the residual estimation). Therefore, I recommend acceptance.", "was_revised": true, "final_justification": "I had no questions for the authors, and the other reviews were also supportive, so I'm keeping my positive score.", "rebuttal": "Dear Reviewer BYJZ,\n\nThank you for your time and effort in completing your review. We appreciate the vote for acceptance.\n\nSincerely,\n\nAuthors"}, {"review_id": "SkZ8gKsPSy", "reviewer": "Reviewer_on4T", "summary": "The paper addresses the challenge of verifying data attributions in machine learning models, particularly in scenarios where a computationally powerful entity (the Prover) provides attributions to a resource-constrained party (the Verifier). The authors propose an interactive verification protocol to ensure that the attributions are \"good\" (i.e., close to optimal) without requiring the Verifier to perform the computationally expensive task of computing the attributions themselves.", "questions": "Add a flowchart or simplified pseudocode in the main text to visually summarize the interactive protocol (beyond Algorithm 1 in the appendix). This would help readers quickly grasp the key steps (e.g., challenge setup, spot-checking, residual estimation).", "limitations": "The paper acknowledges that retraining-based attribution methods (like datamodels) are computationally expensive, creating a trust gap between powerful entities (e.g., corporations) and resource-limited users (e.g., individuals or small labs). This is a key motivation for the work.", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- Well-Structured: The paper is logically organized, with clear motivation, problem formalization, protocol description, and proofs.\n- Good Intuition: The authors provide intuitive explanations (e.g., the \"naive verification fails\" example) before diving into technical details.\n- Full Proofs: The main text outlines key ideas, while detailed proofs are deferred to appendices, improving readability.\n\nWeaknesses:\n- The heavy reliance on Fourier analysis and Boolean function notation might make the paper less accessible to readers without a strong theoretical background.\n- While Algorithm 1 is detailed, a high-level pseudocode summary in the main text could improve clarity for practitioners.", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer on4T,\n\nThank you for your time and feedback! \n\nIn regards to the following weakness statement in your review:\n\n> While Algorithm 1 is detailed, a high-level pseudocode summary in the main text could improve clarity for practitioners.\n\nWe would like to clarify that Algorithm 1 does have a pseudocode/summary in the main text, at the beginning of section 4. If we have a misunderstanding, please let us know and we are happy to clarify further.\n\nThanks again for your review.\n\nSincerely,\n\nAuthors"}, {"review_id": "5QlgPc5TRt", "reviewer": "Reviewer_Hayo", "summary": "This paper introduces a novel interactive protocol that allows computationally limited verifiers to efficiently verify whether training data attribution vectors computed by a powerful prover are approximately optimal. The verification is grounded in a PAC framework, aiming to estimate the gap between the candidate attribution and the best possible attribution (in terms of MSE). The key technical contributions include a transformation of a previously known residual estimation algorithm into a two-message interactive protocol with spot-checking, reducing verifier cost from $O(1/\\varepsilon^3)$ to $O(1/\\varepsilon^2)$.", "questions": "See weaknesses.", "limitations": "- No experiments or simulation support.\n\n- Dependence on a strong determinism assumption.\n\n- Possible limited practicality in modern deep learning settings.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strenths\n- Introduces elegant and efficient PAC-verification protocol for data attribution.\n\n- Solid integration of Boolean harmonic analysis, noise stability, and residual estimation.\n\n- Robust theoretical analysis with completeness, soundness, and efficiency guarantees.\n\n## Weaknesses\n- No experimental results. Given the strong practical motivation (e.g., verifying attributions in sensitive settings like data pricing or medical diagnosis), this absence is glaring. Even synthetic experiments could have helped ground the theoretical claims. Moreover, real-world GPU training often struggles to meet non-deterministic conditions, potentially undermining completeness/reliability.\n\n- Lemma 1 assumes that erroneous samples are independent and uniformly distributed. If a malicious Prover selectively tampers with the subset that contributes significantly to noise-stable estimation, it can substantially shift $B̂_{≥2}$ within the corruption budget, breaking the ε/4 error bound.\n\n- The symbol ρ is not explained when it first appears in the main text.", "was_revised": true, "final_justification": "The authors’ rebuttal address my concerns and some of the minor typos are also corrected, therefore, I will keep my score.", "rebuttal": "Dear Reviewer Hayo,\n\nThank you for your time and feedback. Below, we address the raised weaknesses and questions.\n\n**Experimental Results and Practicality**\n\nWe agree that experimental validation is a natural next step. The primary contribution of this work is to establish the theoretical foundations for efficiently and verifiably proving data attribution, with formal guarantees of completeness and soundness against powerful, malicious Provers. Given focus on provable security and verifiability, which is difficult to simulate meaningfully, we deferred a full empirical study to future work.\n\nRegarding the non-determinism in GPU training, we discussed in the paragraph titled \"Equivalence Checking Procedure\" (Lines 536-543) that, while the theorems assume perfect equivalence checking procedure, the check-equiv procedure can be instantiated practically by, for instance, comparing model outputs or final loss values on a held-out set, rather than requiring a bit-for-bit identity of model weights. This accommodates the realities of modern deep learning frameworks, and any error in equivalence checking can be wrapped into the probabilities for soundness and completeness via union bounds.\n\n**On the conditions in Lemma 1**\n\nWe would like to clarify that the robustness guarantee of Lemma 1 is stronger than the review suggests. The lemma does not assume that bad samples are chosen uniformly or independently by the cheating Prover.\nInstead, our analysis considers the adversarial setting, where the Prover can corrupt any $m$ function evaluations of its choosing, in order to to most impact the Verifier's estimate (see Line 571: \"...an adversary corrupts up to $m$ ... of the $n$ function evaluations...\"). The proof in Appendix D.1 is constructed specifically to bound the worst-case error under these adversarial, non-uniform corruptions. Therefore, the scenario described by the reviewer is precisely the threat model that Lemma 1 is proven to be robust against.\n\n**Typos**\n\nThank you for your careful reading and help with notation and typos. We will be sure to make the edits in the final version, especially defining the symbol $\\rho$ at the right time.\n\nThank you again for your time and valuable comments.\n\nSincerely,\n\nAuthors"}]

Author rebuttal:

Meta-review: Estimating data subset influence on an ML model is computationally expensive due to repeated retraining. Building on Saunshi et al. (2022), who proposed an efficient linear approximation, this work introduces an interactive protocol where a weak verifier outsources this task to a powerful but untrusted prover. The verifier spot-checks a small fraction of the prover's computations. The paper's main technical contribution is proving that the approximation method is robust against a small number of errors, which allows the verifier to efficiently detect a dishonest prover. All reviewers are supportive, and the paper would make a great addition to NeurIPS.
Decision: Accept (poster)