Training data attribution methods give a ranking of training examples by how much each one "caused" a model's prediction. The only ground truth for that ranking is to delete the examples and retrain from scratch, and that is exactly what practitioners cannot afford to do. As a result, attribution scores are used as if they were causal claims, such as "these forty images are why the model calls this a cat," even though nobody checks them. We propose to treat retraining itself as an expensive black-box function and to reuse the search algorithms from query-efficient adversarial attacks to find small training subsets whose removal actually flips a chosen prediction. Each retraining is one "query," and the goal is to use as few as possible. In this setup, cheap attribution scores play the role that a low-frequency prior plays in a black-box image attack: they tell the search where to look first, but they do not have the final word.
The pieces are already on the table. Query-efficient attacks such as Simple Black-box Adversarial Attacks (SimBA, which tries one random direction at a time and keeps it only if the target score drops) and Square Attack (random localized perturbations whose size shrinks over time) show that simple accept/reject search with a good prior reaches its goal in hundreds to a few thousand queries. Attribution methods such as TRAK produce the prior cheaply. Unlearning-based proxies such as GUDA show that approximate removal can stand in for full retraining at roughly 100 times lower cost. Nobody has combined them into a procedure that outputs a verified counterfactual, meaning a removal set together with the retrained models showing that it works.
Core Claim
Let $D$ be the training set, $A(\cdot)$ the training algorithm, $x$ a test input with label $y$, and $m(x;\theta)$ the classification margin of model $\theta$ on $x$ (the correct-class logit minus the largest other logit). We seek
$$S^* = \arg\min_{S \subset D,\ |S|\le k} \ \mathbb{E}_{s}\big[m(x; A_s(D\setminus S))\big],$$
where $s$ indexes training seeds and the expectation is taken over a small number of seeds so that a "flip" reflects removal rather than retraining noise. A flip is certified when this averaged margin is negative. The claim is that an attribution-guided, multi-fidelity accept/reject search finds certified flips for many more test points than removing the top-$k$ attributed examples and retraining once. It also finds much smaller removal sets, under a budget of a few dozen full retrainings per test point. The expected gap has a stated source. Group removal effects in deep networks are not additive, and linear attribution scores misestimate them (Influence Functions in Deep Learning Are Fragile documents how first-order estimates break down). A one-shot top-$k$ removal inherits those errors, while a search that observes retraining outcomes can correct them.
This differs from the closest connected work in the file. Adversarial Attacks on Data Attribution uses black-box search to attack attribution; we use it to perform and check attribution. Z0-Inf and Forward-INF reduce the cost of computing scores, but they still output estimates rather than verified counterfactuals. Black-Box Forgetting applies derivative-free search (the evolutionary optimizer CMA-ES) to forget coarse classes, not to identify which individual training points carry a prediction.
Research Program
The search has three components, and each is borrowed from a specific method.
The first component is the prior, taken from TRAK. It ranks training points by attribution score for $x$ and is recomputed on the current reduced-data model after each accepted removal. This refresh costs gradient computations, not retraining. It plays the role of the low-frequency DCT basis in SimBA, the set of smooth image patterns that SimBA searches first. We also keep SimBA's lesson about basis truncation: its low-frequency restriction "fail[s] entirely on about 2.5% of the ImageNet dataset (even after 60,000 queries)." We therefore mix a fixed fraction of proposals drawn from outside the top of the ranking, so that points the prior misranks can still be found.
The second component is the proposal schedule, taken from Square Attack. The search proposes removal blocks of $b$ points from a sliding window over the ranked list. Blocks start large and shrink on a decaying schedule, mirroring Square Attack's shrinking patch size. Removals are accepted only if they lower the margin, as in SimBA's accept/reject rule. A final pruning pass then tries restoring points one block at a time and keeps each restoration if the flip survives. This yields a near-minimal set.
The third component is the fidelity ladder. Each proposal is first scored by a cheap proxy: warm-start fine-tuning from the full model on $D\setminus S$ for a few epochs, or gradient-ascent unlearning in the style of UnTrac. Only proposals that pass this screen are escalated to full retraining from scratch across seeds. The budget is counted in retraining-equivalents of GPU time, so cheap queries are not free.
The analysis questions are how the number of retrainings needed scales with $k$ and with the test point's original margin, how often the cheap proxy's accept decisions agree with full retraining, and which kinds of test points (low-margin, atypical, near-duplicate-supported) need search at all.
Baselines
The naive reference is random removal of $k$ points followed by retraining. It measures how often a prediction flips simply because of retraining noise and data loss, and every other number is read against it.
The strongest existing competitor is one-shot top-$k$ removal by TRAK (TRAK) followed by one averaged retraining. It is the strongest because TRAK was validated specifically for counterfactual prediction, matching datamodels that needed 30,000 models "by using only a few dozen." A reviewer would say that if TRAK is good, its top-$k$ should already flip the prediction. We give it the same seeds, the same $k$, and the same TRAK ensemble size used by our prior. We also give it a sweep over $k$ that spends our retraining budget: one retraining per candidate $k$, from small to large. Both methods then spend the same compute. We find no reported result on Lacuna for flip rate under top-$k$ TRAK removal on CIFAR-10. The file reports no numeric CIFAR-10 LDS for TRAK either, so we will measure this baseline ourselves. Beating it means a higher certified flip rate at equal $k$ and equal retraining budget, or an equal flip rate with a set at least twice as small.
The second baseline is iterative TRAK without retraining in the loop. It greedily removes the top point and recomputes scores on an unlearned proxy model, then verifies once at the end. This isolates whether observing real retraining outcomes matters or whether refreshing the ranking is enough.
The third baseline is an unlearning-only search. It runs our search, but accepts on the cheap proxy alone and verifies only at the end. For context, GUDA reports 72.7% Top-1 agreement with the leave-one-group-out retraining oracle on CIFAR-10 diffusion, at a cost of 2 hours versus 207. That is high agreement, but it is not certification, and this ablation measures what the missing roughly 27% costs.
The ablation that isolates our key ingredient replaces the attribution prior with a random order while keeping the search unchanged. This shows how much of the gain comes from the prior and how much from the search.
Why not just…?
Why not just remove TRAK's top-$k$ and retrain once? This is the real threat. If one-shot removal certifies flips for nearly all test points at small $k$, the search adds nothing, and we will report that outcome. The fragility evidence in Influence Functions in Deep Learning Are Fragile suggests that group effects will deviate from summed individual scores, but it does not settle the matter. The matched-budget comparison above does. Our search also begins from exactly this removal set, so its extra cost appears only on the test points where one-shot removal fails.
Why not just trust an unlearning proxy and skip full retraining? Unlearning is cheap, and GUDA's 72.7% oracle agreement is respectable. But roughly a quarter disagreement is too much for a claim meant to be causal, and it would be worse under deliberate manipulation. The unlearning-only baseline measures the fraction of proxy-accepted flips that fail under true retraining. If that fraction is near zero on CIFAR-10, we will adopt the proxy and restrict full retraining to spot checks.
Why not just rank by embedding similarity? Nonparametric Data Attribution for Diffusion Models reports that CLIP similarity reaches an LDS of 3.03% on CelebA, against 13.92% for its patch-level method. Similarity is therefore a weak prior. We include CLIP ranking as an alternative prior inside the same search. If the search is robust, it should still certify flips from this weaker starting point, only at a higher retraining cost.
Proposed Experiments
The main testbed is CIFAR-10 with ResNet-9, the TRAK configuration, where a single retraining takes minutes. We use 500 test points stratified by original margin, $k\in\{10, 50, 200\}$, a budget of 40 retraining-equivalents per point, and 5 seeds per full retraining. The metrics are certified flip rate, minimal certified set size, and retraining-equivalents per certified flip. The second testbed is QNLI with BERT-base fine-tuning, also used by TRAK, to check that the approach carries beyond vision.
The first decisive check is the matched-budget comparison with one-shot TRAK, broken down by margin stratum. The second is the proxy-versus-retraining agreement curve along the fidelity ladder.
The third is a manipulation test. We inject the realistic outliers from the Outlier Attack of Adversarial Attacks on Data Attribution, which inflates attribution-based compensation by 185% to 643%, and ask whether the injected points survive into certified removal sets. The hypothesis is that verification by retraining discards injected points that TRAK ranks highly, because removing them does not move the margin. If the hypothesis holds, this separates certified counterfactuals from scores that can be gamed, which matters for royalty schemes like the one proposed in Computational Copyright. If injected points do survive certification, then they genuinely change the model's behavior, and that is also worth reporting.
References
- Simple Black-box Adversarial Attacks
- Square Attack: A Query-Efficient Black-Box Adversarial Attack via Random Search
- TRAK: Attributing Model Behavior at Scale
- GUDA: Counterfactual Group-wise Training Data Attribution for Diffusion Models via Unlearning
- Influence Functions in Deep Learning Are Fragile
- Adversarial Attacks on Data Attribution
- Z0-Inf: Zeroth Order Approximation for Data Influence
- The Mirrored Influence Hypothesis: Efficient Data Influence Estimation by Harnessing Forward Passes
- Black-Box Forgetting
- Unlearning Traces the Influential Training Data of Language Models
- Nonparametric Data Attribution for Diffusion Models
- Computational Copyright: Towards A Royalty Model for AI Music Generation Platforms