# Efficiently Verifiable Proofs of Data Attribution

arXiv: https://arxiv.org/abs/2508.10866 · HTML: https://mlsanity.com/paper/2508.10866/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 28 references that are in the map.
- First posted on arXiv 14 Aug 2025.

## Builds on (most cited first, 18 of 18)

- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation](https://mlsanity.com/paper/2008.03703/) (2020)
- [Studying Large Language Model Generalization with Influence Functions](https://mlsanity.com/paper/2308.03296/) (2023)
- [TRAK: Attributing Model Behavior at Scale](https://mlsanity.com/paper/2303.14186/) (2023)
- [Towards Efficient Data Valuation Based on the Shapley Value](https://mlsanity.com/paper/1902.10275/) (2019)
- [Datamodels: Predicting Predictions from Training Data](https://mlsanity.com/paper/2202.00622/) (2022)
- [Representer Point Selection for Explaining Deep Neural Networks](https://mlsanity.com/paper/1811.09720/) (2018)
- [If Influence Functions are the Answer, Then What is the Question?](https://mlsanity.com/paper/2209.05364/) (2022)
- [DsDm: Model-Aware Dataset Selection with Datamodels](https://mlsanity.com/paper/2401.12926/) (2024)
- [What is Your Data Worth to GPT? LLM-Scale Data Valuation with Influence Functions](https://mlsanity.com/paper/2405.13954/) (2024)
- [Simfluence: Modeling the Influence of Individual Training Examples by Simulating Training Runs](https://mlsanity.com/paper/2303.08114/) (2023)
- [An Automatic Finite-Sample Robustness Metric: When Can Dropping a Little Data Make a Big Difference?](https://mlsanity.com/paper/2011.14999/) (2020)
- [Understanding Influence Functions and Datamodels via Harmonic Analysis](https://mlsanity.com/paper/2210.01072/) (2022)
- [On the Trade-Off between Actionable Explanations and the Right to be Forgotten](https://mlsanity.com/paper/2208.14137/) (2022)
- [Decomposing and Editing Predictions by Modeling Model Computation](https://mlsanity.com/paper/2404.11534/) (2024)
- [Attribute-to-Delete: Machine Unlearning via Datamodel Matching](https://mlsanity.com/paper/2410.23232/) (2024)
- [Data Debiasing with Datamodels (D3M): Improving Subgroup Robustness via Data Selection](https://mlsanity.com/paper/2406.16846/) (2024)

## Built on by (most cited first, 1 of 1)

- [Train Once, Answer All: Many Pretraining Experiments for the Cost of One](https://mlsanity.com/paper/2509.23383/) (2025)

## Abstract (arXiv)

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. Specifically, if both Prover and Verifier follow the protocol, the Verifier accepts data attributions that are ε-close to the optimal data attributions (in terms of the Mean Squared Error) with probability 1-δ. 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 δ. 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 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.