Should We Pay This Much for Robustness? Efficient Proxy Certificates with Marginal Guarantees

Modern classifiers remain sensitive to small input perturbations, while strong model-agnostic robustness certificates such as randomized smoothing are often too expensive for deployment, requiring an extensive number (e.g. 2000) of model forward passes per input. We propose a framework that delegates certification to a cheap proxy function while statistically controlling its deviation from the original sound certificate. Given an exchangeable unlabeled calibration set, we tune the proxy via robust conformal risk control to guarantee a bounded marginal false-approval rate: the probability that the proxy accepts an input whose prediction is flipped due to perturbation. The resulting proxy certificate can be used either as a standalone marginal certificate or as a fallback mechanism that invokes the expensive certificate only when the proxy rejects. We provide both single-sample and sample-heavy calibration recipes. Empirically, our method substantially reduces test-time certification cost (to a single model forward) while retaining much of the certified performance of randomized smoothing, enabling cheap yet effective robustness guarantees for larger architectures such as vision transformers and language models.