Learned Too Fast for How Hard It Looks: Poison-Aware Coresets at Any Budget

Training on a small, carefully chosen slice of a dataset (a "coreset") can match full-data accuracy at a fraction of the cost. When that data may be poisoned, the same choice decides whether a backdoor survives. A backdoor is a hidden rule planted by an attacker: the model behaves normally on ordinary inputs but outputs the attacker's label whenever a trigger pattern is present. Current coreset methods sort examples along a single axis of difficulty, and two published results show that every point on that axis is unsafe. Defenses such as Anti-Backdoor Coreset Selection via Cumulative Entropy keep the hard, uncertain examples, on the reasoning that poisons are easy shortcuts. Wicked Oddities shows that a careful attacker poisons the hard examples instead. Meanwhile SIMS shows that at small budgets a coreset has to move toward easy, typical examples to avoid accuracy collapse, and easy examples are exactly where classic shortcut poisons sit.

We propose replacing "how hard is this example?" with a relative question: "is this example learned faster than examples that look equally hard?" How hard an example looks can be measured without labels, as its distance from same-labeled neighbors in a frozen self-supervised embedding. How fast it is learned comes from the cheap loss history of an early training run. A trigger is a shortcut, so poisoned examples should be learned anomalously fast for their apparent difficulty. This should hold for dirty-label poisons, which look like a different class than their label, and for clean-label poisons placed on hard outliers. Clean hard examples, by contrast, are slow to learn and are compared only against other hard examples. They are therefore not thrown out as outliers, which is the failure that costs self-supervised cleansing 2–3% of clean accuracy. Because the difficulty strata double as the coreset's sampling plan, the same score can drive selection at a 10% budget or a 55% budget.

Core Claim

A single poison-exclusion rule can produce coresets that hold attack success near the level of clean training across budgets from 10% to 55% of the data. The rule uses learning speed relative to label-free difficulty, needs no trusted clean examples, and handles both shortcut attacks and hard-sample clean-label attacks. At each budget it should lose no more clean accuracy than the best non-defensive coreset method at that budget on clean data. No method in the file has been evaluated on this combination: small budgets, the Wicked Oddities attack, and seedless operation.

Prior Work and Where This Sits

Two defensive coreset methods motivate the gap. ABCS keeps examples with high entropy summed over training epochs, plus an unlearning step. It reports defense effectiveness above 95% on CIFAR-10, but it needs about 55% of the data, it does not fully neutralize the Adaptive Blend (A-Blend) attack, and it has never faced hard-sample poisons. Its own entropy criterion would keep exactly the examples Wicked Oddities poisons. COLLIDER selects examples whose gradients sit near the center of their class and whose local intrinsic dimensionality is low, meaning they lie in well-populated regions of feature space. It cuts BadNets attack success to 4.80%, but clean accuracy falls to 80.66%, showing that its geometric criterion also removes useful clean examples.

Three other works supply ingredients. ASD found that poisoned examples lose their loss faster than clean hard examples during rapid adaptation. That is the closest existing signal to ours, but ASD needs 10 trusted examples per class and a semi-supervised final stage, and it does not condition speed on how hard the example looks. Wicked Oddities supplies the label-free difficulty measure: k-nearest-neighbor distance in a pretrained VICReg embedding. We turn the attacker's own selection tool into the defender's reference axis. SIMS supplies the budget-dependent shift from hard examples at mild budgets toward typical ones at aggressive budgets, which we reuse to allocate examples across difficulty strata.

The non-defensive selectors are the constraint. Moderate-DS, CLD, LBCS and PBCS were tested only against label noise and adversarial perturbations, never against backdoors. Any defensive method has to match their clean accuracy at equal budget, or it has merely moved where the robustness-accuracy cost falls.

Research Program

Scoring. For each training example $i$ with label $y_i$, compute two quantities.

The first is apparent difficulty, $h_i$. It is the percentile, within class $y_i$, of the mean distance from $i$ to its $k$ nearest same-labeled neighbors in a frozen self-supervised encoder.

The second is learning speed, $v_i$. It is the negative area under example $i$'s training-loss curve over the first $T$ epochs of an ordinary short run on the full data. This is the same kind of cheap scalar logging used by CLD, with no gradients or Hessians stored.

The poison score is the standardized speed residual within a difficulty band:

$$r_i = \frac{v_i - \mathrm{median}\{v_j : j \in B(i)\}}{\mathrm{MAD}\{v_j : j \in B(i)\}}$$

Here $B(i)$ is the set of examples sharing label $y_i$ whose $h_j$ falls in the same difficulty band as $h_i$ (for example, the same decile), and MAD is the median absolute deviation. We also compute a class-agnostic version of the bands. As in ASD's enlarging step, this keeps a poisoned target class from shifting its own reference statistics.

Selection. Given a budget fraction $\alpha$ of examples to keep, first allocate kept examples to difficulty bands using a SIMS-style schedule: favor hard bands when $\alpha$ is large and typical bands when $\alpha$ is small. Within each band, discard examples with large positive $r_i$ before sampling. Train a fresh model on the result with ordinary supervised learning.

Analysis. We will characterize when the residual separates clean from poisoned examples. The intended statement is that a trigger lowers the loss of its carrier examples at a rate set by trigger strength rather than by semantic difficulty. Separation should therefore improve with difficulty, which is the opposite of entropy-based criteria. This also predicts the attacker's escape route: weakening the trigger until its learning speed matches that of clean hard examples. We will measure what that costs the attacker in attack success.

Baselines

Naive reference points. These are random subsampling at each budget and full-data training with no defense. Vanilla BadNets reaches 99.98% attack success on CIFAR-10 in COLLIDER. Random subsampling retains poison in proportion to the budget, so beating it should be easy. Its clean accuracy, however, is the bar a defense must not fall far below.

Strongest defensive coreset competitor: ABCS. ABCS is the closest method in kind, also seedless and also coreset-based. It reports defense effectiveness above 95% on CIFAR-10, 97% on Tiny-ImageNet, attack success near 1%, and clean accuracy comparable to clean training, all at roughly 55% of the data. We will run it from released settings, and with its automatic size rule overridden, at our smaller budgets. No reported result was found on Lacuna for ABCS against Wicked Oddities poisons or below its default coreset size. Beating ABCS means two things: matching its attack success at 55% while equaling its clean accuracy, and keeping attack success under 5% at 10–20% budgets where ABCS either cannot be configured or readmits poison.

Strongest seedless cleansing competitor. This is SimCLR k-nearest-neighbor cleansing from self-supervised cleansing, which reports attack success below 5% and clean accuracy usually above 91% on CIFAR-10, with a 2–3% clean drop. We compose it with the best clean coreset selector at each budget.

Reference ceiling. ASD is given its 10 seeds per class and serves as an upper reference rather than a direct competitor. It reports 0.3% attack success and 82.7% clean accuracy on ImageNet.

Non-defensive selectors. Moderate-DS and SIMS are run on poisoned data as is. On clean CIFAR-100 they also provide the accuracy ceiling for each budget; SIMS reports 33.83% at 90% pruning against 6.37% for EL2N, a selector that ranks examples by early-training error.

Fairness and ablations. All methods share the architecture (ResNet-18), augmentation, epoch budget for the final model, and total wall-clock accounting including scoring. Each method gets the same small hyperparameter sweep, tuned on a held-out split of the poisoned training data, never on clean test data.

Three ablations isolate the key ingredient. The first uses speed alone, an ASD-like criterion with no seeds and no difficulty conditioning. The second uses difficulty alone, Wicked Oddities' measure applied defensively by dropping outliers. The third uses an embedding trained in-dataset versus an off-the-shelf one.

Why not just…?

Why not just run ABCS with a smaller coreset? Its rule keeps high-entropy examples. At small budgets it would retain the hard outliers that Wicked Oddities poisons, and its own partial failure on A-Blend already points that way. It would also discard the typical examples that SIMS shows small budgets need. The budget sweep tests this directly. If ABCS holds up at 10–20% against hard-sample poisons, our contribution reduces to the clean-accuracy comparison.

Why not just clean with self-supervised k-nearest neighbors, then apply any good coreset method? This is a real threat. It is seedless and reaches below 5% attack success. Its documented weakness is flagging unusual clean examples, costing 2–3% of clean accuracy, and clean-label hard poisons agree with their labels, so label-disagreement filtering may miss them. Our composed baseline measures both effects. If it matches us on attack success and clean accuracy, the relative-speed score adds nothing. We will report that outcome rather than tune around it.

Why not just use Moderate-DS, which already drops both extremes? This is also a real threat. Median-distance selection in a clean pretrained embedding should exclude far-from-class dirty-label poisons and 90th-percentile outliers. The cost is that at mild budgets the median band must widen and readmit both tails. At any budget it discards clean hard examples, which carry accuracy at mild budgets. The decisive comparison is clean accuracy and attack success at equal budgets from 30% to 55%, where our method keeps hard bands and Moderate-DS cannot.

Why not just measure loss-drop speed, as ASD does, without the difficulty conditioning? Without seeds, a raw speed threshold removes easy clean examples along with poisons, and it confuses slow clean hard examples with slow weak poisons. The speed-only ablation measures exactly the margin the difficulty conditioning buys.

Proposed Experiments

The first experiment is a decisive check that precedes any method building. On CIFAR-10 we inject BadNets, Blend, WaNet, A-Blend, and Wicked Oddities clean-label poisons at its reported setting of 10% of the target class, about 1% of the data. For each attack we compute how well each score separates poisoned from clean examples, measured as the area under the ROC curve: $r_i$, cumulative entropy, raw speed, and raw difficulty. Separation is also broken down by difficulty decile. The idea is falsified if $r_i$ fails to separate Wicked Oddities poisons from clean examples in the top difficulty deciles. That would mean hard-sample poisons are not learned unusually fast, and the project would pivot to the measurement itself as a negative result about entropy- and speed-based defenses.

If the check passes, we run the full grid on CIFAR-10, GTSRB, and Tiny-ImageNet. The grid covers the five attacks, budgets of 10, 20, 30, 55, and 80%, and all baselines. We report clean accuracy, attack success, defense effectiveness, and end-to-end wall clock. On clean CIFAR-100 with no attack, we compare against SIMS and Moderate-DS to measure how much accuracy the defense costs when nothing is wrong.

An adaptive-attacker study sweeps trigger strength and the difficulty of the samples chosen for poisoning. It traces attacker success against our score's ability to detect the poisons, testing the prediction that evading the residual requires weakening the backdoor. A final check swaps the frozen encoder between off-the-shelf and in-dataset SimCLR, to quantify dependence on an encoder trained on unpoisoned data. That dependence is the method's main stated assumption.