How Small Can a Backdoor-Safe Coreset Be?

Training on a coreset, a small, carefully chosen subset of the data that stands in for the whole, is a standard way to cut training cost. It has also become a backdoor defense. A backdoor is a hidden rule planted by poisoning a few training examples with a secret trigger (a patch, a blend, a subtle warp) so that the trained model misbehaves whenever the trigger appears. The best coreset defense, Anti-Backdoor Coreset Selection via Cumulative Entropy (ABCS), keeps the samples a model stays most uncertain about and drives attack success to near 1%. It chooses its size, about 55% of the data, by an empirical threshold, and its authors say both that this is far larger than coresets outside security and that they have no theory for why it works. The coreset-sizing literature points the other way. It shows that minimal sizes can be predicted and extrapolated, as in bootstrap sketch sizing (Error Estimation for Sketched SVD via the Bootstrap) or the compression threshold of A Statistical Perspective on Coreset Density Estimation. But it assumes corrupted points hurt the loss, which backdoor poisons do not.

This note proposes treating coreset size as the security variable. We claim a backdoor survives in a coreset according to roughly how many poisoned samples the selection rule lets through, not the poisoning rate. Aggressive, performance-driven shrinking tends to enrich poisons, because triggers are the easiest possible examples. If both claims hold, a defender can find the smallest safe coreset without knowing which samples are poisoned. The method is to plant their own harmless "canary" backdoors at known counts in a cheap pilot run, then measure how many canaries each selection rule keeps at each size and whether their backdoor is still learned.

Core Claim

Two thresholds govern a coreset built from poisoned data. The first is the clean threshold $m_c(\epsilon)$: the smallest size at which clean accuracy stays within $\epsilon$ of full-data training. This is the analogue of the compression threshold in A Statistical Perspective on Coreset Density Estimation, below which compression error dominates. The second is a backdoor extinction threshold. For a selection rule $\pi$ at coreset size $m$, define the poison enrichment factor

$$E_\pi(m) = \frac{\text{fraction of poisons in the size-}m\text{ coreset}}{\text{fraction of poisons in the full data } r},$$

so the coreset retains $k_\pi(m) = E_\pi(m)\, r\, m$ poisons. Our hypothesis is that attack success rate (ASR) is approximately a function of $k_\pi(m)$ alone for a fixed attack and architecture. That function is a sharp sigmoid with a critical count $k^*$. The critical count depends on the trigger type but not on the selection rule. A coreset is safe when $m \ge m_c(\epsilon)$ and $k_\pi(m) < k^*$.

Three consequences follow, and each is testable. First, loss-driven minimal-size selection should have $E_\pi(m)$ that grows as $m$ shrinks. The motivating tension comes from Refined Coreset Selection (LBCS), which finds minimal coresets under a performance constraint and prunes label noise because noisy points raise validation loss. Anti-Backdoor Learning shows the opposite behavior for triggers: they are shortcuts whose loss falls fastest, so a size-minimizer should prefer them. Second, entropy-based selection like ABCS should have $E_\pi(m) \ll 1$ over a range of sizes, but only for triggers that stay confident. Its admitted failure on Adaptive Blend, whose poisons are optimized to keep high entropy, should appear as $E_\pi$ climbing back toward 1. Third, attacker-side sample selection should mainly shift $E_\pi$ rather than $k^*$. This concerns Boosting Backdoor Attack with A Learnable Poisoning Sample Selection Strategy (LPS), which picks hard samples to poison, and Influence-Based Fair Selection (IFS), which balances poisons across classes. If instead those methods lower $k^*$, they are more dangerous to coreset defenses than anyone has measured.

The new part is the pair of thresholds, the count-based survival model, and a sizing procedure that follows from them. No existing paper measures ASR as a function of coreset size across selection rules. No paper sizes a backdoor coreset by prediction rather than by threshold.

Research Program

The first step is measurement. On poisoned datasets we build coresets at sizes from 5% to 70% of the data under several selection rules. The rules are uniform sampling, ABCS cumulative entropy, an "easy-first" rule that keeps the lowest-entropy samples (the kind of rule favored in small-budget pruning), and LBCS. For each run we record clean accuracy, ASR, and, since in these experiments we know the poison labels, the true retained count $k$ and enrichment $E$. The central analysis asks whether ASR curves from different rules and sizes collapse onto one curve when plotted against $k$ rather than against $m$ or $r$. If they collapse, the count model is right. If they do not, for example if entropy-selected poisons are "stronger per sample" than uniformly kept ones, then the model needs a per-rule potency term, and we report that.

The second step is the defender-side sizing procedure. The defender cannot observe $k$, so we give them something they can observe. Before selection, the defender inserts a small set of canary poisons into a pilot subset of the data. These are self-made triggers with known target labels and known counts $k_0$, spread across several trigger families: patch, blend, and a smooth warp in the style of WaNet. A short pilot run of the selection rule then gives two things for canaries at each candidate size: the canary enrichment $\hat E_\pi(m)$, and whether the canary backdoor is learned from $k_0 \hat E_\pi(m) r m$ retained copies.

We fit the clean threshold from a few pilot sizes by extrapolating a power law in $m$. The power-law form borrows from the rate structure in A Statistical Perspective on Coreset Density Estimation, and the pilot-then-extrapolate idea comes from the bootstrap rule in Error Estimation for Sketched SVD via the Bootstrap. The defender then picks the smallest $m$ above $m_c(\epsilon)$ at which canary enrichment implies a retained count below the canary-estimated $k^*$, under an assumed upper bound on the true poisoning rate. After selection the canaries are removed. The output is a recommended size together with a stated assumption, "safe if the real attack is no more selection-evasive than the canaries." This makes the failure mode explicit rather than hidden inside a threshold.

The third step is stress-testing that assumption. Here we use attacks built to be unlike the canaries (Adaptive Blend, SIG, LPS- and IFS-selected poisons) and an adaptive attacker who knows the canary families and designs triggers to be kept by the selection rule.

Baselines

The naive reference is full-data training with no defense. It fixes the undefended ASR and the clean-accuracy ceiling. Anti-Backdoor Learning reports over 97% average ASR undefended, and 88.41% clean accuracy for a model trained on 100% clean CIFAR-10 data. Next to it sits uniform random subsampling at every size we test. This is the cheapest possible coreset. Because it keeps the poisoning rate but lowers the absolute poison count, it is the direct test of whether our count model already explains away the need for clever selection. We found no reported result on Lacuna for uniform subsampling as a backdoor defense.

The strongest existing method is ABCS, Anti-Backdoor Coreset Selection via Cumulative Entropy. It reports a Defense Effectiveness Rate above 95% on CIFAR-10 and 97% on Tiny-ImageNet, ASR near 1% across most attacks, and clean accuracy comparable to clean-data training, all at about 55% of the data. We run it from the released code with its own warm-up and threshold. We also force it to each fixed size in our sweep, since the fairest comparison is at matched coreset size. To beat it, our procedure must produce a coreset clearly smaller than ABCS's roughly 55% at equal or lower ASR and within one point of its clean accuracy. Alternatively, at the same size, it must show lower ASR on Adaptive Blend, where ABCS itself reports incomplete defense.

We also run two further single-pass or isolation defenses on the same poisoned data and architectures through BackdoorBench. COLLIDER is a gradient-centrality coreset with a local-intrinsic-dimension filter. It reports ASR falling from 99.98% to 4.80% on CIFAR-10 BadNets at 80.66% clean accuracy. Anti-Backdoor Learning reports 7.69% average ASR over ten attacks at 84.76% clean accuracy. LBCS, Refined Coreset Selection, is run unmodified as the minimal-size competitor. The file gives no reported CIFAR-10 number for it, and no backdoor result at all. All methods get the same total GPU-hour budget, counting warm-up, selection, pilot, and final training. They also get the same hyperparameter-search allowance and the same PreAct-ResNet18 and EfficientNet-B3 training recipes.

The ablation that isolates the key ingredient is the sizing procedure without canaries. It picks the smallest size above the fitted clean threshold $m_c(\epsilon)$ and ignores backdoor survival. If this does as well as the canary version, then canary calibration adds nothing and the paper's contribution reduces to clean-threshold extrapolation. A second ablation uses canaries of a single trigger family, to measure how much family diversity matters.

Why not just…?

Why not just sweep ABCS's threshold to find a smaller safe size? This is the most serious alternative, and our sweep of ABCS at fixed sizes is exactly this experiment. The difference is that a sweep needs a known-poisoned validation set to read off ASR, which a real defender does not have. Our procedure replaces that oracle with canaries. If the canary-chosen size lands within a few percent of the oracle-chosen size from the sweep, canaries are a valid substitute. If it does not, we report the gap as the method's limit.

Why not just subsample uniformly, since fewer poisons survive in a smaller subset? Under our own count model this could work for weak attacks, so we treat it as a real threat rather than a strawman. The case against it is quantitative. LPS reaches 36.64% ASR on CIFAR-10 at a 0.216% poisoning ratio, which is about a hundred poisoned images. Pushing a strong attack below a critical count that small by uniform thinning would require shrinking the data well below the clean threshold. That tension is measurable: the uniform curve in our sweep will show whether any size exists where clean accuracy holds and ASR has collapsed.

Why not just filter with Anti-Backdoor Learning first, then run a minimal coreset method on what is left? The risk is that leftover poisons are the ones the filter found hardest to isolate. If our enrichment hypothesis is right, a size-minimizer like LBCS would then concentrate them. We run this two-stage pipeline as a baseline and report its retained poison count directly. That shows whether the concentration happens rather than leaving it as an argument.

Proposed Experiments

All experiments run inside BackdoorBench on CIFAR-10, GTSRB, and Tiny-ImageNet, with PreAct-ResNet18 and EfficientNet-B3. We use the second architecture because BackdoorBench documents defenses that fail when moved across architectures. Attacks are BadNets, Blended, SIG, WaNet, and Adaptive Blend, plus BadNets poisons placed by LPS and by IFS selection, at poisoning rates from 0.2% to 5%. Metrics are clean accuracy, ASR, robust accuracy (whether a triggered input still gets its true label), coreset size, and total compute.

Four checks decide the proposal. The first is the collapse test: if ASR versus true retained count does not fall on roughly one curve per attack across selection rules, the count model is wrong and the sizing procedure has no foundation. The second is the enrichment test: LBCS should show $E > 1$ that grows as size shrinks. If it does not, the claimed tension between minimal sizing and shortcut learning is false. The third is the prediction test: the canary-recommended size should be within a small margin of the oracle-safe size found with true poison labels, and noticeably below 55%. The fourth is the mismatch test on Adaptive Blend and an adaptive, canary-aware attacker. We expect the procedure to degrade here, and the question is whether it fails loudly, by recommending larger sizes, or silently, by certifying an unsafe coreset. A silent failure would mean canary calibration should not be trusted without a guard on how well the canaries cover the space of triggers.