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

Soroush H. Zargarbashi; Mohammad Sadegh Akhondzadeh; Aleksandar Bojchevski

cs.LGNov 5, 2026

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

Authors: Soroush H. Zargarbashi, Mohammad Sadegh Akhondzadeh, Aleksandar Bojchevski

Organizations: CISPA Helmholtz Center for Information Security · University of Cologne

Abstract

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 (rather than pointwise) false-approval rate: the probability, over future inputs, 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, as a standalone certificate our method reduces the test-time certification cost to a single model forward while retaining much of the certified performance of randomized smoothing at small radii, and as a fallback it recovers the certified ratio of randomized smoothing at a more modest speedup. This enables cheap yet effective robustness guarantees for larger architectures such as vision transformers and language models.

Figures & tables

Method	Variant	Guarantee	Cert. Ratio	Cert. Accuracy	Error Rate	Forwards / image
Method	Variant	Guarantee	Cert. Ratio	Cert. Accuracy	Error Rate	Cal	Cert.-only (Speedup)	End-to-end (Speedup)
Rand. Smoothing	—	Pointwise	70.06%	56.08%	—	—	1950	2000
Verification	Hu et al. (2023)	Pointwise	—	35.0%	—	—	1	1
ProxC	Standalone	Marginal	56.11%	48.53%	2.29%	2000	1 $\mathbf{(1950\times)}$	51 $\mathbf{(39.2\times)}$
ProxC	Fallback	Marginal	72.35%	57.3%	2.29%	2000	779 $\mathbf{(2.50\times)}$	829 $\mathbf{(2.41\times)}$

Table 1: Results on ImageNet/ResNet,

r{=}0.14

\sigma{=}0.5

\alpha{=}0.05

, Gaussian smoothing (

2000

MC samples:

50

for the majority-vote label and

1950

for the certificate). The verification entry does not use smoothing (result directly reported from the reference); it gives a pointwise guarantee on a different architecture, so it is not directly comparable to the marginal guarantee of ProxC. Speedup is on forward calls and relative to randomized smoothing. Certification-only cost excludes the forwards for the label; end-to-end cost includes them.

Panel of Figure 1 — Figure 1: Top row (ImageNet). Left: certified ratio of randomized smoothing (RS) as a function of the Monte Carlo sample budget, across perturbation radii $r$ (dotted lines show the performance on perturbed points). Middle: certified ratio (solid) and certified accuracy (dotted) as functions of $r$ for ResNet. Right: the same comparison on the Vision Transformer. Bottom row (CIFAR-10). Left: Effect of $\sigma$ on certified ratio. Middle: certified ratio of ProxC, and Right ProxC-A across various radii. All results are with $\sigma=0.5$ unless specified. All curves report mean over 5 runs.

		RS (Pointwise)		ProxC (Marginal 5% Risk)			Ref. CA
Model	$r$	CR	CA	CR	CA	Risk	$(\dagger)$
ResNet-50	$0.00$	$78.79$	$60.00$	$72.88$	$56.78$	$4.17$	—
	$0.14$	$70.06$	$56.08$	$56.11$	$48.53$	$2.29$	—
	$0.25$	$64.91$	$53.61$	$46.29$	$41.70$	$1.25$	—
	$0.50$	$54.65$	$47.62$	$29.01$	$28.04$	$0.26$	—
	$0.75$	$45.54$	$41.12$	—			—

Table 2: Certified ratio (CR, %) and certified accuracy (CA, %) on ImageNet with

\sigma=0.5

. RS uses

n=2{,}000

(ResNet-50) and

n=10{,}000

(ViT) Monte Carlo samples (single calibration run each). Entries marked

\dagger

use deterministic (non-smoothing) certificates reported directly from the reference. Note the comparison is between pointwise and marginal guarantees.

	Base (Cohen)		ProxC-H Proxy CR (FA)
$r$	CR	CA	$K\!=\!1\mathrm{k}$	$K\!=\!2.5\mathrm{k}$	$K\!=\!5\mathrm{k}$	$K\!=\!10\mathrm{k}$	$K\!=\!20\mathrm{k}$
$0.25$	$79.0$	$55.2$	$62.2$ ( $2.6$ )	$63.9$ ( $2.9$ )	$64.6$ ( $3.0$ )	$63.2$ ( $2.4$ )	$63.6$ ( $2.6$ )
$0.38$	$73.4$	$53.3$	$51.8$ ( $1.5$ )	$54.4$ ( $2.0$ )	$55.7$ ( $2.3$ )	$55.5$ ( $1.5$ )	$56.0$ ( $1.6$ )
$0.50$	$68.4$	$51.6$	$39.2$ ( $0.4$ )	$46.1$ ( $0.9$ )	$48.1$ ( $1.1$ )	$49.1$ ( $1.0$ )	$49.8$ ( $1.0$ )
$0.75$	$59.8$	$48.2$	—	—	$21.5$ ( $0.0$ )	$35.2$ ( $0.2$ )	$38.9$ ( $0.5$ )

Table 3: Calibration sample budget

n_{\mathrm{mc}}

for ProxC-H on ImageNet (ViT + denoising,

\sigma\!=\!0.5

\alpha\!=\!0.05

, averaged over 3 runs). Each cell reports CR (%) with FA (%) in parentheses. All FA values remain

\leq\alpha=5\%

		$r$
Method	Metric	$0$	$1$	$2$	$3$	$4$	$5$
Backbone	CR	$98.5$ %	$89.3$ %	$77.9$ %	$61.8$ %	$38.8$ %	$14.6$ %
Backbone	CA	$91.0$ %	$84.7$ %	$75.2$ %	$60.3$ %	$38.2$ %	$14.5$ %
ProxC	CR	$100.0$ %	$70.7$ %	$45.2$ %	$23.9$ %	$10.3$ %	$4.5$ %
ProxC	CA	$92.0$ %	$66.3$ %	$43.6$ %	$23.5$ %	$10.3$ %	$4.5$ %
Risk	–	$1.5$ %	$4.5$ %	$4.1$ %	$3.7$ %	$3.7$ %	$3.3$ %

Table 4: NLP task: Certified ratio (CR) and certified accuracy (CA) of the backbone certificate and ProxC and risk. The certification is over

r

-insertions.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

\lambda^{*}\leftarrow\inf\left\{\lambda:\bar{R}_{n}(\lambda)\leq\mathrm{c}^{\downarrow}(\alpha,{\mathcal{B}}^{-1})\right\}.

Appendix

Algorithm 1 ProxC : Proxy Certificate Inference

\lambda^{*}\leftarrow\inf\left\{\lambda:\bar{R}_{n}(\lambda)\leq\mathrm{c}^{\downarrow}(\alpha,{\mathcal{B}}^{-1})\right\}.

Appendix

Algorithm 2 ProxC-A : Proxy-Augmented Inference

Method	Prediction rule	Randomness	Averaged over	Guarantee
RS	Majority vote, small $n_{0}$	MC-corrected	— (pointwise)	Pointwise soundness
ProxC	Same as RS	One fresh smoothing noise at proxy evaluation	Clean input, calibration set, internal noise	Marginal false-approval control (not pointwise)
ProxC-H	Same as ProxC	One fresh noise draw at test	Same as ProxC, plus calibration MC	Same marginal guarantee, usually less conservative
ProxC-A	One-sample noise-augmented inference; approves with the same draw	One fresh draw affects both prediction and approval	Clean input, calibration set, noises	Controls the joint event {randomized prediction toggles} $\wedge$ {proxy approves}; not a certificate for a fixed deterministic prediction

Appendix

Table 5: What is guaranteed by randomized smoothing (RS) and by the ProxC variants. In all cases the adversary knows the model weights, the clean input, and the procedure, and may choose any

\tilde{\bm{x}}_{n+1}\in{\mathcal{B}}({\bm{x}}_{n+1})

; it does not control or observe the internal randomness (e.g.

\bm{\epsilon}

	ProxC			ProxC-A
$r$	CR	CA	Risk	CR	CA	Risk
$0.00$	$70.83$ $\pm$ $1.56$	$56.25$ $\pm$ $1.45$	$1.91$ $\pm$ $0.80$	$49.18$ $\pm$ $5.46$	$42.31$ $\pm$ $3.69$	$4.86$ $\pm$ $1.99$
$0.06$	$55.47$ $\pm$ $0.78$	$45.31$ $\pm$ $1.19$	$0.69$ $\pm$ $0.15$	$43.17$ $\pm$ $4.80$	$37.82$ $\pm$ $3.48$	$3.53$ $\pm$ $1.16$
$0.12$	$44.88$ $\pm$ $2.36$	$38.45$ $\pm$ $1.48$	$0.69$ $\pm$ $0.30$	$39.49$ $\pm$ $3.81$	$34.28$ $\pm$ $2.43$	$2.72$ $\pm$ $0.58$
$0.25$	$27.78$ $\pm$ $6.43$	$23.78$ $\pm$ $4.56$	$0.26$ $\pm$ $0.26$	$28.81$ $\pm$ $1.05$	$25.24$ $\pm$ $0.68$	$1.60$ $\pm$ $0.31$
$0.38$	$19.27$ $\pm$ $5.13$	$16.32$ $\pm$ $4.05$	$0.09$ $\pm$ $0.15$	$15.70$ $\pm$ $3.39$	$14.15$ $\pm$ $2.69$	$0.51$ $\pm$ $0.22$

Appendix

Table 6: Certified ratio ( CR , %) and certified accuracy ( CA , %) on perturbed CIFAR-10 (

\sigma=0.5

, calibration fraction

0.2

), reported as mean

\pm

std over two independent calibration runs. Test datapoints are attacked with PGD-RS attack on

\ell_{2}

ball. Risk is the empirical false-approval rate of the proxy certificate under attack. Calibration fails at

r\geq 0.75

for both methods.

	RS (backbone)		ProxC-H			ProxC
$r$	CR	CA	CR	CA	Risk	CR	CA	Risk
$0.00$	$91.8\pm 0.4$	$59.4\pm 0.6$	$93.2\pm 2.1$	$58.5\pm 0.9$	$4.4\pm 1.1$	$95.0\pm 3.2$	$59.6\pm 0.6$	$5.8\pm 1.6$
$0.06$	$88.5\pm 0.4$	$58.5\pm 0.5$	$82.0\pm 2.1$	$55.6\pm 1.1$	$3.7\pm 0.7$	$84.1\pm 2.8$	$57.2\pm 0.7$	$4.1\pm 1.0$
$0.12$	$85.6\pm 0.3$	$57.7\pm 0.5$	$75.2\pm 2.5$	$54.0\pm 1.2$	$3.2\pm 0.8$	$76.7\pm 4.0$	$55.0\pm 1.4$	$3.5\pm 1.1$
$0.18$	$82.2\pm 0.3$	$56.5\pm 0.5$	$68.5\pm 2.0$	$51.8\pm 1.1$	$2.5\pm 0.6$	$67.1\pm 4.4$	$51.1\pm 1.8$	$2.7\pm 1.0$
$0.25$	$79.0\pm 0.4$	$55.2\pm 0.5$	$63.6\pm 1.6$	$49.9\pm 0.9$	$2.6\pm 0.4$	$58.6\pm 2.4$	$47.0\pm 1.3$	$1.8\pm 0.3$

Appendix

Table 7: Certified Ratio (CR, %) and Certified Accuracy (CA, %) on ImageNet with ViT + Denoising pipeline (

\sigma{=}0.5

, 400 calibration samples, 3 independent runs,

99.9\%

confidence).

\alpha=5\%

. All values: mean

\pm

std over runs. “—” denotes calibration failure.

	RS (backbone)		ProxC ( $\alpha=2\%$ )			ProxC ( $\alpha=5\%$ )			ProxC ( $\alpha=10\%$ )
$r$	CR	CA	CR	CA	Risk	CR	CA	Risk	CR	CA	Risk
$0.00$	$81.0$	$63.7$	$48.8$	$42.4$	$1.6$	$70.9$	$56.1$	$5.6$	$82.3$	$61.9$	$9.6$
$0.06$	$75.8$	$61.1$	$41.7$	$37.6$	$1.4$	$59.3$	$49.2$	$4.4$	$71.7$	$56.6$	$8.2$
$0.12$	$70.7$	$58.6$	$29.6$	$27.7$	$0.5$	$47.3$	$42.1$	$2.2$	$59.8$	$49.9$	$5.6$
$0.18$	$66.1$	$55.9$	$27.9$	$26.3$	$0.6$	$35.4$	$32.7$	$1.6$	$49.6$	$42.4$	$4.4$
$0.25$	$61.2$	$53.0$	$20.8$	$19.9$	$0.4$	$29.6$	$27.7$	$1.2$	$38.5$	$34.9$	$2.8$

Appendix

Table 8: Certified Ratio (CR, %) and Certified Accuracy (CA, %) on CIFAR-10 (

\sigma{=}0.5

, ResNet backbone, single run). Results are for three risk levels

2\%

5\%

, and

10\%

Variant	Label	Certification-only	End-to-end
Randomized smoothing (backbone)	50	1950	2000
ProxC/ ProxC-H (standalone)	50	1	51
ProxC-A	shared	1	1
ProxC/ ProxC-H (fallback)	50	$\mathrm{CR}\cdot 1+(1-\mathrm{CR})(1+N_{\mathrm{MC}})$	$50\,+$ certification-only

Appendix

Table 9: Forward passes per test input on ImageNet (

2000

MC samples for randomized smoothing:

50

for the label and

N_{\mathrm{MC}}=1950

for the certificate). CR is the certified ratio of the proxy; the fallback calls the backbone certificate only when the proxy rejects.

		Certification-only		End-to-end
$r$	Reject rate	Forwards	Speedup	Forwards	Speedup
0.00	24.2%	473	4.12 $\times$	523	3.82 $\times$
0.06	32.1%	627	3.11 $\times$	677	2.95 $\times$
0.12	38.6%	753	2.59 $\times$	803	2.49 $\times$
0.14	39.9%	779	2.50 $\times$	829	2.41 $\times$
0.18	45.7%	893	2.18 $\times$	943	2.12 $\times$

Appendix

Table 10: Fallback ProxC on ImageNet/ResNet: proxy reject rate and average forwards per query. Speedups are relative to randomized smoothing with 1950 (certification-only) and 2000 (end-to-end) forwards.

$r$	Group	#points	Proxy risk	Proxy cert. ratio
0.12	top 100	4,577	0.0	0.5724
0.12	worst 100	10,654	0.0428	0.6555
0.25	top 100	7,023	0.0	0.5090
0.25	worst 100	8,025	0.0320	0.5499
0.50	top 100	12,229	0.0	0.2728
0.50	worst 100	2,613	0.0168	0.3750

Appendix

Table 11: False-approval risk and certified ratio of the proxy on ImageNet, stratified to the best and worst 100 classes.

	$r=0.12$ ( $\alpha_{r}=2.97$ )			$r=0.25$ ( $\alpha_{r}=1.60$ )
Class	Risk	CR	FA/appr	Risk	CR	FA/appr
airplane	3.27	59.9	5.5	2.25	44.9	5.0
automobile	3.37	67.7	5.0	2.59	54.7	4.7
bird	2.73	32.3	8.5	1.18	16.7	7.1
cat	2.75	23.0	12.0	0.82	7.9	10.4
deer	3.16	25.4	12.4	1.09	11.1	9.8

Appendix

Table 12: Per-class false-approval risk, certified ratio (CR), and risk conditional on approval (FA/appr

=

risk

/

CR) of the proxy on CIFAR-10, in % (setup of Table 13 ,

|{\mathcal{D}}_{n}|=500

, averaged over

500

calibration splits). All classes have the same frequency (

10\%

), so the marginal values (last row) are the averages over classes.

	$r=0$		$r=0.12$		$r=0.25$		$r=0.5$
	$\alpha_{r}=5.00$ , RS CR $81.3$		$\alpha_{r}=2.97$ , RS CR $71.1$		$\alpha_{r}=1.60$ , RS CR $61.1$		$\alpha_{r}=0.41$ , RS CR $44.4$
$n$	Risk	CR	Risk	CR	Risk	CR	Risk	CR
25	$3.84\pm 3.53$	$58.9\pm 17.4$	infeasible		infeasible		infeasible
50	$3.86\pm 2.67$	$61.9\pm 12.3$	$1.99\pm 1.92$	$38.9\pm 12.2$	infeasible		infeasible
100	$5.02\pm 2.29$	$68.2\pm 8.8$	$2.91\pm 1.68$	$46.3\pm 8.4$	$0.99\pm 0.97$	$25.6\pm 8.6$	infeasible
200	$4.89\pm 1.49$	$68.5\pm 5.7$	$2.43\pm 1.05$	$44.6\pm 5.7$	$1.53\pm 0.88$	$31.3\pm 5.7$	infeasible

Appendix

Table 13: Effect of the calibration-set size

n=|{\mathcal{D}}_{n}|

on CIFAR-10 (ResNet-110,

\sigma=0.5

\alpha=5\%

). Proxy risk and certified ratio (CR) in %, mean

\pm

std over

500

random calibration splits; the test set is all images not used for calibration. Infeasible:

1/(n+1)>\alpha_{r}

, so the proxy approves nothing.

Certified Robustness

Certified robustness develops formal guarantees that model predictions remain reliable under specified input or system perturbations.

See all 94 papers

Jun 1, 2026

RRISE: Robust Radius Inference via a Surrogate Estimator

Randomized smoothing (RS) uses a smoothed classifier to provide architecture-agnostic certificates of

\ell_2

classification robustness, but its dependence on per-input Monte Carlo (MC) sampling undermines its use in real-time systems. We argue that this cost is structural rather than fundamental, such that it can be significantly reduced by sharing information across the deployment stream. We introduce RRISE, an RS framework that compresses certification into a single forward pass through a learned surrogate. RRISE trains the surrogate against precomputed MC class-count targets via a soft-label cross-entropy loss and converts surrogate predictions into provably conservative certified radii through a one-time conformal calibration step. The resulting certificate is deployment-verifiable: whenever the calibrated radius is positive, the surrogate's prediction provably matches the smoothed classifier's and the smoothed classifier is constant on a ball of that radius around the input. Across image classification benchmarks, RRISE matches fixed-budget MC certified accuracy within

0.84

percentage points while replacing up to

10^4

noisy base-model evaluations per query with a single surrogate forward pass, recouping MC training cost after

\approx 10^5

deployment queries. On CIFAR-100 and Tiny ImageNet, where the only prior offline-surrogate method collapses, RRISE achieves

1.23

1.91\times

higher certified accuracy, establishing efficient randomized smoothing as a practical path to certified robustness in repeated-deployment settings.

Jong-Ik Park, Shreyas Chaudhari, Carlee Joe-Wong +1

Carnegie Mellon University

Randomized Smoothing Neural Network Robustness Certified Robustness

Ask PDF

Apr 27, 2026

Laplace-Bridged Randomized Smoothing for Fast Certified Robustness

Randomized Smoothing (RS) offers formal

\ell_2

guarantees for arbitrary base classifiers but faces two key practical bottlenecks: (i) it often relies on noise-augmented training to achieve nontrivial certificates, which increases training cost, can reduce clean accuracy, and weakens RS as a genuinely post-hoc defense; and (ii) certification is computationally expensive, typically requiring tens of thousands of noisy forward passes per input, which hinders deployment, especially on resource-constrained edge devices. To address both limitations, we propose Laplace-Bridged Smoothing (LBS), an analytic reformulation of RS that replaces high-dimensional input-space Monte Carlo (MC) sampling with efficient computations in a low-dimensional probability space. LBS preserves formal robustness guarantees without requiring noise-augmented training while substantially reducing certification burden. On CIFAR-10 and ImageNet, LBS attains stronger certified robustness than RS and reduces per-sample certification cost by nearly an order of magnitude. Notably, on NVIDIA Jetson Orin Nano and Raspberry Pi 4, LBS achieves speedups of up to

494\times

, enabling practical certified deployment on real-world edge devices. Finally, we provide theoretical justification for the analytic formulation and certificate validity of LBS.

Miao Lin, MD Saifur Rahman Mazumder, Feng Yu +2

Department of Computer Science, Old Dominion University, Norfolk, VA, USA · Department of Mathematical Sciences, University of Texas at El Paso, El Paso, TX, USA · School of Cybersecurity, Old Dominion University, Norfolk, VA, USA

Randomized Smoothing Neural Network Robustness Certified Robustness Noise Robustness

Ask PDF

Jun 26, 2026

Halt Fast! Early Stopping for Certified Robustness

Randomized Smoothing (RS) provides rigorous robustness guarantees for neural networks without architectural constraints, yet its adoption is limited by extreme computational costs. Standard RS requires tens of thousands of model evaluations per input and forces practitioners to commit to fixed sample sizes a priori. In this work, we present a novel meta-learning framework for anytime-valid certified robustness that adaptively deploys computational resources. By using a lightweight meta-learner to predict image-specific priors for a sequential E-process, we achieve a 20-fold reduction in sample complexity compared to traditional methods while maintaining rigorous statistical guarantees. Beyond raw efficiency, we demonstrate how anytime-validity enables adaptively allocating compute based upon application-specific risk thresholds, a form of resource triage impossible under classic certification frameworks. That this is achievable while also providing similar certification performance demonstrates that our approach provides a pathway for real-time, safety-critical certification deployments.

Andrew C. Cullen, Paul Montague, Benjamin I. P. Rubinstein

University of Melbourne · DST Group, Adelaide

Efficient Neural Network Inference Early Stopping Randomized Smoothing Anytime-Valid Inference Neural Network Robustness Certified Robustness

Ask PDF

Abstract

Certified Robustness

Explore similar work

RRISE: Robust Radius Inference via a Surrogate Estimator

Laplace-Bridged Randomized Smoothing for Fast Certified Robustness

Halt Fast! Early Stopping for Certified Robustness