MAGIC: Near-Optimal Data Attribution for Deep Learning

Andrew Ilyas, Logan EngstromSubmission to ICLR 2026 · Rejected

TL;DR

Predictive data attribution—figuring out how removing or adding training data changes a model’s predictions—has notoriously struggled with deep neural networks. MAGIC solves this problem by using exact metadifferentiation (reverse-mode differentiation through the entire training trajectory) to compute ground-truth influence functions. In a deterministic "single-model" setting, MAGIC achieves near-perfect prediction of counterfactual model loss ($r > 0.96$) at only 2–3$\times$ the computational cost of training a single model.

What Problem Does This Paper Address?

In convex machine learning (like linear or logistic regression), the classical influence function accurately estimates how altering training data affects model predictions via a simple first-order Taylor expansion. In deep learning, however, modern attribution baselines (such as TRAK or EK-FAC) often show weak correlation with ground truth and suffer from massive scale errors.

Researchers previously attributed this failure to either:

  1. The chaotic, non-convex complexity of deep network optimization, or
  2. Poor approximations of the influence function itself.

Furthermore, standard data attribution conflates algorithmic randomness (e.g., random seeds, batch shuffling) with the effect of the data itself. The authors formulate and tackle single-model predictive data attribution: predicting how a specific, deterministic model run responds when its training data weights are altered.

Methods

MAGIC (Metagradient-based Attribution via Ground-truth Influence Computation) computes the exact influence function rather than relying on Hessian approximations (like Fisher/K-FAC) or linearized model proxies:

  • Exact Metadifferentiation via REPLAY: The authors view the entire iterative training run (e.g., Adam updates) as a single computational graph. They apply the REPLAY algorithm, which differentiates backward through all optimization steps using checkpointed states and minibatches at a cost of $T + T \log(T)$ operations and $\log(T)$ memory.
  • First-Order Taylor Expansion: Using the exact gradient of the test measurement with respect to training sample weights ($\nabla_{\mathbf{w}} f(\mathbf{w})$ evaluated at $\mathbf{w} = \mathbf{1}_n$), MAGIC predicts the counterfactual loss for any perturbed dataset weighting $\mathbf{w}$.
  • Enforcing Smoothness: To ensure learning updates are differentiable and well-behaved, small numerical stabilizers (such as an $\epsilon_{\text{root}}$ inside Adam's square-root denominator) are introduced.

Datasets

The authors evaluated MAGIC across vision and language tasks:

  • CIFAR-10: Training a ResNet-9 from scratch on 50,000 images, predicting test loss on 50 test samples.
  • WikiText: Fine-tuning a pre-trained GPT-2 (125M) model with causal language modeling on 4,608 chunked sequences, evaluating loss on 50 test chunks.
  • Instruction Fine-Tuning (IFT) Suite: LoRA fine-tuning of Gemma-2B on ~300,000 examples combined from FLAN V2, CoT, Dolly, and OpenAssistant 1, evaluating loss on 32 test examples from MMLU.
  • MNIST: A comparison against prior single-model attribution work using a two-layer CNN.

No new benchmarks were introduced; all setups adapt existing standard datasets and training configurations.

Key Insights and Ideas

  • The theory wasn't broken—the approximations were: Deep learning models are predictable via first-order influence functions. Prior failures stemmed almost entirely from heuristic Hessian and curvature approximations, not an inherent breakdown of influence theory.
  • Single-Model Determinism Eliminates Irreducible Noise: In standard stochastic retraining, inherent run-to-run variance places a hard upper bound on prediction quality. Fixing the randomness isolates the true causal effect of training data weights.
  • Near-Optimal Linear Predictor: For small data deletions (e.g., 1%), MAGIC achieves almost perfect correlation with ground truth. Because it matches the true gradient at the center, its predictions represent the optimal linear approximation; error at higher drop fractions stems solely from higher-order loss curvature.

Key Results

Attribution quality was measured using the Linear Datamodeling Score (LDS)—the Spearman correlation ($\rho$) between predicted loss and actual retrained loss across random data subsets:

  • CIFAR-10 (ResNet-9): When dropping 1% of training data, MAGIC achieves an LDS of $\rho = 0.96$, compared to $\rho \approx 0.25$–$0.35$ for EK-FAC and TRAK.
  • Gemma-2B (LoRA): On 1% data removal, MAGIC scores $\rho = 0.97$, while existing methods perform no better than random guessing ($\rho \approx 0$).
  • MNIST Benchmark: Achieved $\rho = 0.998$, significantly exceeding the previous state of the art ($\rho = 0.715$).
  • Absolute Calibration: Unlike baselines, which require manual rescaling to match the correct order of magnitude, MAGIC’s predicted losses align directly on the $y = x$ line with true losses.
  • Compute Cost: For attributing a single output measurement, MAGIC requires only 2–3$\times$ the cost of a single training run (~15 minutes on one A100 GPU for CIFAR-10), whereas TRAK and EK-FAC were 20–1000$\times$ slower.

Limitations and Future Work

  • Scaling with Multiple Targets: While baseline methods have runtimes scaling as $O(N + n)$ (where $N$ is training samples and $n$ is test targets), MAGIC requires a reverse backward pass per test measurement, scaling as $O(N \cdot n)$. It is vastly faster for small $n$ (or cohort-averaged metrics), but becomes computationally heavy if attributing thousands of individual test points independently.
  • Large Data Deletions: Because MAGIC is a first-order Taylor approximation, accuracy degrades at large drop fractions (e.g., dropping 20% of data) due to loss surface curvature.
  • Deterministic Requirement: The guarantees directly hold in deterministic training regimes; predicting behavior across stochastic training seeds requires running and averaging multiple single-model runs.

Summary updated

Abstract

The goal of data attribution is to estimate how adding or removing a given set of training datapoints will affect model predictions. This goal is straightforward in convex settings, but in non-convex settings, existing methods are far less successful. Current methods' estimates often only weakly correlate with the ground truth. In this work, we present a new data attribution method (MAGIC) that combines classical methods and recent advances in metadifferentiation (Engstrom et al., 2025) to nearly optimally estimate the effect of adding or removing training data on model predictions at the cost of only 2-3x the cost of training a single model. MAGIC essentially "solves" data attribution as it is currently studied, thus enabling downstream applications and motivating more fine-grained future evaluations.
BibTeX
@misc{ilyas2025magic,
  author = {Andrew Ilyas and Logan Engstrom},
  title = {{MAGIC: Near-Optimal Data Attribution for Deep Learning}},
  year = {2025},
  eprint = {2504.16430},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2504.16430},
}

Loading related content...

Figure