Neural networks can be fooled by tiny changes to inputs, but robustness certificates that guarantee safety require thousands of model evaluations per input, which is too expensive.
The authors propose a proxy certificate that uses a cheap function and controls the false-approval rate, the chance that the proxy approves an input whose prediction would be flipped by a perturbation, using conformal prediction on unlabeled calibration data.
This reduces certification cost to a single forward pass at test time while preserving most of the certified accuracy at small perturbation radii, making robustness practical for large models like vision transformers.