Provable Adversarial Detection: Prime Quantization meets Gromov--Wasserstein

Manohar Kaul, Sadbhavana Babar, Aditya Ramesh, Aditya Saibewar, Fumiyoshi Kasahara, Maki Inui, Hiroaki Kurihara

Oct 19, 2026arXiv:2610.26102v1

cs.LG

Scorecard· 16/16

4.5/10 impact

Original keyed prime-quantization plus GW idea with broad experiments, but the 'provable' guarantees rest on strong assumptions disconnected from the actual SVM detector, and adaptive-attack evaluation is weak.

Abstract

Adversarial vulnerability persists across modern vision architectures from CNNs to vision language models (VLMs), yet existing detection methods rely on heuristics without theoretical guarantees. We address the fundamental question of when adversarial perturbations can be provably detected from a geometric perspective. Our key insight is that adversarial perturbations cannot simultaneously preserve geometric structure across spaces with fundamentally different properties. Accordingly, we construct two such complementary metric spaces. First, we use a standard CNN embedding space $Z$ , where adversarial samples exhibit significant displacement patterns. Second, we build a novel prime-quantized space $P$ , that absorbs small perturbations through number-theoretic discretization, resulting in minimal displacement, while preserving discriminability. We then leverage the geometric discrepancies across spaces $Z$ and $P$ to detect adversarial samples. To the best of our knowledge, we establish the first rigorous separation theory for adversarial detection, proving that adversarial samples create unavoidable geometric inconsistencies across both spaces. Our framework provides theoretical guarantees including pixel-level absorption bounds, neighborhood diameter concentration, Gromov-Wasserstein (GW) separation theorems, and practical risk control. Extensive experiments validate our theoretical predictions and achieve consistently strong detection performance across a wide range of attack types and model families.

AI Impact Assessments

(1 model)

Core Contribution

The paper proposes an adversarial *detector* with claimed provable guarantees. It compares an input's neighborhood structure in two spaces: a standard CNN embedding space Z, and a "prime-quantized" space P. In P, each pixel is scaled to an integer and rounded to a neighboring prime according to a secret bit key. Cross-space discrepancy is measured with entropic Gromov–Wasserstein (GW) distances at local (k-NN) and global (k-means centroid) scales, plus a JS divergence on label distributions. The resulting six features go to an SVM. The theory has four layers: pixel absorption radii, an image-level collision bound, k-NN diameter envelopes, and GW separation and gap theorems with a risk-control lemma.

The idea of pairing a learned embedding with a keyed number-theoretic discretization, then using GW to compare them, is unusual. The "provable detection" framing addresses a real gap in a field dominated by heuristics. The claim of a "first rigorous separation theory" is, however, strongly overstated, as discussed below.

Methodological Rigor

The theory has substantial weaknesses.

The absorption results are trivial: Proposition 1 and Lemma 1 are elementary. Lemma 1's lower bound is also off, since the minimum distance to a prime is at least 1 integer unit only for non-prime n. The paper's own remark concedes that practical absorption radii (≈1.8e-3 at k=4) are *smaller* than typical attack budgets (≥3.9e-3). So most attacks cross prime boundaries, and the "absorption" story is not the operative mechanism. Pixel flips and 8-bit quantization further complicate it. Theorem 4 only shows that *some* perturbation of size ≤ε crosses a boundary, not that a given adversarial one does.

The GW separation rests on assumptions that carry most of the weight. Assumption 2 (a Jacobian variance proxy, E‖Δ‖² ≤ dσ²ε²) is an upper bound used to derive a *lower* bound on displacement in Z. The lower bound γ_C is instantiated from clean geometry minus the shift, which makes the argument circular or at least unsupported. The K-NN gap condition in Theorem 7 is assumed rather than shown. The "Ω(dσ²ε²)" gap scaling is unconvincing, because the clean K-side radius does not contract with d.

The theorems are not about the actual detector. They concern a single-pair GW between neighborhood sets. The detector uses entropic GW, semantic GW, JS features, and an SVM trained on labeled adversarial data. The risk-control lemma is conditional on estimator concentration, which is assumed. Statements like "once the gap event holds, thresholding makes no error" are tautological given the event.

The theory is silent on adaptive adversaries. An attacker who knows the secret key can pass cross-space consistency, as the key-leakage experiment shows (detection drops to 55% at full key knowledge). This undercuts the claimed "unavoidable inconsistencies." It also makes the detector's security depend on key secrecy, a Kerckhoffs-type assumption not formalized.

Adaptive attacks assume the adversary does not know b⋆ and use a Monte Carlo prior over keys. This is weaker than a rigorous adaptive evaluation: there is no BPDA or EOT through the quantizer, and no attack that directly targets the GW features or the SVM. Detection drops to 84–90% under these attacks.

Empirically, the baselines are weak and some numbers look odd. MagNet sits at ~50%, MAD at ~50%, and MD at 50% on several FMNIST/KMNIST settings. A "detection accuracy" of 50% for Mahalanobis is suspicious and suggests poor tuning. The strongest competitor, EA, reaches 90–97% and is close to the proposed method in several cases. Ours is trained as a supervised SVM on adversarial examples, which is an advantage over unsupervised baselines. The cross-attack generalization is only tested on a few attack pairs. Gaussian blur, rotation, and frequency "attacks" are not really adversarial examples, and some baselines score ≈50% on them. Ablations over quantization show that prime rounding beats Fibonacci, log, and uniform quantization (0.94 vs ~0.61), but without a mechanistic explanation or a keyed-uniform baseline. Notably, a random-key uniform quantizer would be the fair control. Hyperparameters are selected apparently on test-like data, and sensitivity to klocal is non-monotone (97.9→86.2→92.6).

Evaluation covers CIFAR-10 mostly, with ResNet-18 and ViT, plus small MNIST-type sets, one ImageNet run with ResNet-18, and a zero-shot VLM experiment. The paper contains some internal inconsistencies, including prime-gap constants and "CNN vs crypto" labels.

Potential Impact

If the mechanism holds up, a keyed non-invertible transform as a second "view" for consistency-based detection is a reusable idea. The GW comparison across heterogeneous spaces is a nice conceptual tool. Practically, the detector costs 0.12 s per sample and a GPU, with an SVM that needs labeled adversarial examples. That is a deployment hurdle given the detector-evasion literature. The "provable" framing may draw attention, but experts will likely see the guarantees as conditional on strong assumptions that fail under adaptive attacks. Industrial relevance (Fujitsu) is modest.

Timeliness

Adversarial robustness for VLMs and detection with guarantees are timely, though adversarial-example detection has fallen out of favor after repeated breaks by adaptive attacks. The cryptographic angle is fresh.

Strengths

Novel combination of prime quantization, GW, and a secret key.

Broad attack suite, multiple architectures, and extra analyses (key leakage, quantizer comparison, runtime).

Honest limitations section and a key-leakage experiment.

Limitations

Theory is loosely connected to the detector, and the assumptions are strong and circular.

Adaptive-attack evaluation is weak, and the security rests on key secrecy.

Supervised detector with possibly under-tuned baselines.

Overstated claims of "first rigorous" and "must succeed".

Only small-scale ImageNet evidence.

Overall, this is a moderately interesting idea with overstated theory and a limited adversarial evaluation, so I expect modest impact.

Rating:4.5/ 10

Significance 4Rigor 3.5Novelty 6.5Clarity 5

Generated Oct 20, 2026

Comparison History (0)

No comparisons yet.

Scorecard· 16/16

4.5/10 impact