Spending Adversarial Training Compute Only Where Nearest Neighbors Say It Is Needed

Adversarial training makes a network robust to small, deliberately chosen input perturbations by training it on its own worst-case inputs. Finding those inputs is the expensive part. Each training example usually gets 10 or more steps of projected gradient descent (an iterative attack that nudges the input uphill on the loss and clips it back into a small ball), and every step costs a full forward and backward pass. Most of that compute probably goes to examples that are already safe. This proposal asks whether a gradient-free signal, the distance from an example's features to its nearest same-class and other-class neighbors in a small cached bank, can decide per example how many attack steps it actually needs. The goal is to keep multi-step robustness while paying for multi-step attacks on only a minority of the data.

The idea joins two lines of work that have so far mostly been used in the opposite direction. Non-parametric distance-based detection flags unfamiliar inputs by their distance to stored reference features, with no assumed distribution shape. Its typical use is as a test-time detector or a test-time replacement for adversarial training. When nearest-neighbor geometry has been brought inside adversarial training, it has made training more expensive, not less. We propose using it as a cheap triage step inside the training loop. Because the triage signal does not depend on gradients, it should also be harder for the model to fool than confidence-based triage, which is the failure that makes fast adversarial training unreliable.

Core Claim

At a fixed budget of attack gradient computations, set well below full multi-step adversarial training, allocating attack steps by a feature-space nearest-neighbor margin will give higher AutoAttack robustness than three alternatives: allocating them by the model's own logit margin, allocating them at random, or using single-step training. The resulting model should also show a smaller gap between weak-attack and strong-attack accuracy. The reasoning is that logit margins measure exactly the quantity that gradient masking inflates, while distance to other-class training features measures how far a perturbation must move the representation before it reaches confusing territory. The second quantity is computed without touching the gradient landscape.

Research Program

Prior work frames the opportunity in three ways. Several papers show that nearest-neighbor geometry carries robustness information. On adversarial training and the 1 Nearest Neighbor classifier proves that a 1-nearest-neighbor rule is robust on the training set to any perturbation smaller than half the inter-class distance, in any norm. It also shows that indexing with FAISS is about 20,000 times cheaper than TRADES training. Defending Against Adversarial Examples with K-Nearest Neighbor applies nearest-neighbor voting to intermediate network features. Both papers replace the classifier at test time. We keep the parametric classifier and use distance only to decide where training compute goes. The authors of the 1NN paper explicitly call for nearest-neighbor logic in learned feature spaces and leave open how to obtain such spaces without full adversarial training cost. This proposal addresses that question directly.

Two other papers constrain the design. Nearest Neighbor Projection Removal Adversarial Training searches for each sample's nearest other-class competitor during adversarial training and strips the feature component that points toward it. This improves robustness, but it adds a search on top of the full attack loop. Memorization Weights for Instance Reweighting in Adversarial Training (MeoW) uses distance to a compact prototype codebook to reweight samples, adding about 0.01 seconds per batch. That second result is evidence that a small nearest-neighbor lookup is essentially free relative to an attack step. MeoW, however, leaves the attack loop untouched. We use the same kind of cheap lookup to shorten the loop.

The mechanism works as follows. At epoch $t$, the forward passes already performed during training produce $L_2$-normalized penultimate features $z_i$ for the adversarial examples. Normalization follows Out-of-Distribution Detection with Deep Nearest Neighbors, which shows that unnormalized distances fail. We store a class-balanced subsample of these features, around 1%, the fraction that paper found sufficient, in a GPU FAISS index. At epoch $t+1$, each example gets a margin computed from its previous-epoch adversarial feature:

$$m_i = d_k^{\text{other}}(z_i) - d_k^{\text{same}}(z_i),$$

where $d_k^{\text{other}}$ is the distance from $z_i$ to its $k$-th nearest bank feature of a different class and $d_k^{\text{same}}$ is the distance to its $k$-th nearest bank feature of its own class. The number of attack steps $K_i \in \{0, 1, K_{\max}\}$ is set by margin quantiles chosen so that the average steps per example equals a target budget $B$. Low-margin examples receive full PGD and mid-margin examples receive one step. High-margin examples receive only clean or random-noise training.

The bank is refreshed every epoch at no extra forward cost. A small fraction of high-margin examples, around 5%, is attacked fully at random to guard against a stale or wrong margin. The margins of these spot-checked examples also serve as an online audit. If many high-margin examples turn out to be easily broken, the margin is miscalibrated, and that is logged as a measured outcome.

As a secondary readout tied to the detection side, we take the final feature space and run zero-shot $k$-NN novelty scoring under attack, following Killing it with Zero-Shot: Adversarially Robust Novelty Detection. That paper requires a fully adversarially trained backbone. The readout tests whether the cheaper training preserves the distance stability that its method depends on.

Baselines

The naive reference point is standard training followed by full-budget evaluation. It fixes the floor of near-zero AutoAttack accuracy and the compute unit, one forward plus one backward pass.

The strongest existing method is full multi-step training with PGD-10 and with TRADES on the same architecture, epochs, and learning-rate schedule. This defines the robustness target at 100% budget. For reference, MeoW reports TRADES at 53.00% AutoAttack accuracy on CIFAR-10, rising to 55.60% with MeoW. Nearest Neighbor Projection Removal Adversarial Training reports 26.31% AutoAttack accuracy on CIFAR-100. We will rerun these methods ourselves rather than compare against the quoted figures, because architectures may differ. Beating this baseline does not mean exceeding its robustness. It means coming within one point of its AutoAttack accuracy at no more than 35% of its attack gradient computations.

The fast-training competitor is Bilateral Adversarial Training (BAT), a one-step targeted attack with label smoothing. It reports 63.7% under PGD-100 on CIFAR-10 against 47.2% for standard PGD training, with a 7–10× per-epoch speedup. We run BAT and single-step training with random initialization at matched wall-clock time and judge them by AutoAttack only. To beat them, we need higher AutoAttack accuracy at equal time together with a smaller gap between PGD-10 and AutoAttack.

Two ablations isolate the key ingredient. In the first, the nearest-neighbor margin is replaced by the logit margin of the current model, using the same quantile allocation, budget, and spot checks. In the second, the steps are allocated at random. Each ablation gets the same hyperparameter search budget, about 20 runs, as our method. Beating the logit-margin ablation is the central claim. If we fail to beat it, the nearest-neighbor contribution is unsupported.

Why not just…?

Why not just use the logit margin to decide which examples to attack? This is the most serious threat, because the logit margin is free and correlated with vulnerability. The case against it is indirect. Adversarial Robustness Overestimation and Instability in TRADES shows that models can look robust under PGD-10 (28.72%) and collapse under AutoAttack (10.42%), which means confidence-based signals can be inflated by masking. A logit-margin allocator would then classify masked examples as safe and stop attacking them, which could reinforce the masking. That argument does not settle the question, so the per-example prediction test and the matched-budget ablation below decide it. If logit margin performs equally well, we will report that and drop the nearest-neighbor claim.

Why not just use single-step training like BAT? Single-step methods already cut cost roughly tenfold, but they are prone to catastrophic overfitting and masking (Adversarial Robustness Overestimation and Instability in TRADES). BAT itself relies on a heuristic label rule. Our allocator includes single-step as one of its three levels, so it can only add multi-step attacks where the margin is thin. Matched-wall-clock runs evaluated under AutoAttack will show whether that targeted addition matters.

Why not just reweight examples, as MeoW does? Reweighting changes how much each attacked example counts but still attacks every example fully, so it saves no compute. The two approaches are complementary, and we will test MeoW weights on top of our allocation. MeoW is not a substitute for reducing the attack budget.

Why not just download a robust pretrained backbone, as ZARND does? For the detection readout this works whenever such a backbone exists. It does not address training cost for new data, new architectures, or domains with no public robust model. The core contribution is the training procedure, not the detector.

Proposed Experiments

The first experiment is cheap and could end the project early. We train a PGD-10 ResNet-18 on CIFAR-10, save checkpoints at several epochs, and for each training example compute the nearest-neighbor margin, the logit margin, and whether AutoAttack succeeds. We then measure how well each margin predicts per-example attack success, as AUROC, conditioned on epoch. If the nearest-neighbor margin is not more predictive than the logit margin, and especially in runs that show masking, the allocation hypothesis is unlikely to hold.

The main experiments train ResNet-18 and WideResNet-34-10 on CIFAR-10, CIFAR-100, and Tiny ImageNet under $\ell_\infty$ with $\epsilon = 8/255$. We sweep budgets $B$ at 15%, 25%, 35%, and 50% of PGD-10 and report clean accuracy, AutoAttack accuracy through RobustBench: a standardized adversarial robustness benchmark, the gap between PGD-10 and AutoAttack, and the time spent on attack gradients plus FAISS search. To probe the norm-agnostic intuition from the 1NN paper, we also evaluate the $\ell_\infty$-trained models under $\ell_2$ and $\ell_1$ attacks. Stability is measured over 10 seeds at the TRADES settings that the instability paper found fragile (batch size 128, learning rate 0.1, β = 3), counting how many runs collapse.

The secondary readout scores CIFAR-10 one-class novelty detection under PGD-100 with summed $k$-NN distances, comparing our cheaply trained backbone with a fully adversarially trained one on the same architecture. ZARND reports 62.4% AUROC under PGD for CIFAR-10. That figure comes from an ImageNet-pretrained backbone, so it serves as context, not a matched target.

The proposal succeeds if the nearest-neighbor allocator, at 35% budget or less, stays within one point of full TRADES or PGD AutoAttack accuracy, beats the logit-margin and random allocators by a margin larger than seed variance, and shows fewer collapsed runs than single-step training.