Robust Conformal Prediction with a Single Binary Certificate
Authors: Soroush H. Zargarbashi
Aleksandar Bojchevski
Venue: ICLR 2025 Poster (2025)
Keywords: Conformal Prediction
Uncertainty Quantification
Robust Conformal Prediction
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: We define binarized conformal prediction sets for which we can gain robustness to worst case (adversarial) noise with a single certificate. Our approach produces small prediction set even with very few Monte-Carlo samples.

Abstract: Conformal prediction (CP) converts any model's output to prediction sets with a guarantee to cover the true label with (adjustable) high probability. Robust CP extends this guarantee to worst-case (adversarial) inputs. Existing baselines achieve robustness by bounding randomly smoothed conformity scores. In practice, they need expensive Monte-Carlo (MC) sampling (e.g. $\sim10^4$ samples per point) to maintain an acceptable set size. We propose a robust conformal prediction that produces smaller sets even with significantly lower MC samples (e.g. 150 for CIFAR10). Our approach binarizes samples with an adjustable (or automatically adjusted) threshold selected to preserve the coverage guarantee. Remarkably, we prove that robustness can be achieved by computing only one binary certificate, unlike previous methods that certify each calibration (or test) point. Thus, our method is faster and returns smaller robust sets. We also eliminate a previous limitation that requires a bounded score function.

Published as a conference paper at ICLR 2025
ROBUST CONFORMAL PREDICTION WITH A SINGLE BINARY CERTIFICATE
Soroush H. Zargarbashi
Aleksandar Bojchevski University of Cologne bo jchevski kicss uni koo de
CISPA Helmholtz Center for Information Security za rga rggarbasii @cs. uni-kuo de
ABSTRACT
Conformal prediction (CP) converts any model's output to prediction sets with a guarantee cover the true label with (adjustable) high probability. Robust CP ex- tends this guarantee to worst-case (adversarial) inputs. Existing baselines achieve robustness by bounding randomly smoothed conformity scores. In practice, they need expensive Monte-Carlo (MC) sampling (e.g. ~ 10 samples per point) to maintain an acceptable set size. We propose robust conformal prediction that produces smaller sets even with significantly lower MC samples (e.g. 150 for CIFARIO). Our approach binarizes samples with an adjustable (or automatically adjusted) threshold selected to preserve the coverage guarantee. Remarkably, we prove that robustness can be achieved by computing only one binary certificate, unlike previous methods that certify each calibration (or test) point. Thus, our method faster and returns smaller robust sets. We also eliminate a previous lim- itation that requires bounded score function.
INTRODUCTION
Despite their extensive applications, modern neural networks lack reliability as their output prob- ability estimates are uncalibrated (Guo al. 2017). Many uncertainty quantification methods computationally expensive, lack compatibility with black-box models, and offer no formal guaran- tees. Alternatively, conformal prediction (CP) is a statistical post-processing approach that returns prediction sets with a guarantee to cover the true label with high adjustable probability. CP only requires held-out calibration set and offers distribution-fret (Vovk et al. 2005 Angelopoulos & Bates 2021). The model is used as a black box to compute con- formity scores which capture the agreement between inputs æ and labels y. These prediction sets are shown to improve human decision-making both in terms of response time and accuracy (Cresswell) ct al. 2024). CP assumes exchangeability between the calibration and the test set (a relaxation of the L..dd assumption), making it broadly applicable to images, language models, etc. CP also applies graph node classification (Zargarbashi er al.) 2023 Huang et al. 2023) where uncertainty quantifi- cation methods are limited. However, exchangeability. and therefore the conformal guarantee, easily breaks when the test data is noisy or subjected to adversarial perturbations.
annos--g coverage guarantee
Robust conformal prediction extends this guarantee to worst-case inputs 0 within maximum radius around the clean point œ, e.g. Vē s.t. @ - æ1|2 S r. In the evasion setting, we assume that the cali- bration set clean, and test datapoints can be perturbed. Building on the rich literature of robustness certificates (Kumar et al., 2020), recent robust CP baselines (Gendler et al. 2021 Zargarbashi et al., 2024 Jeary et al.) 2024) use conservative score at test time that is a certifted bound on the con- formity score of the clean unseen input. This maintains the guarantee even for the perturbed input since "if CP covers æ then robust CP certifiably covers .". However, the average set size increases, especially if the bounds are loose. The certified bounds can be derived through model-dependent verifiers (Jeary et al. 2024) or smoothing-based black-box certificates (Zargarbashi et al. 2024).
For the robustness of black-box models, established approach is to certify the confidence score through randomized smoothing (Kumar et al., 2020), obtaining bounds on the expected smooth score. The tightness of these bounds depends on the information about the smooth score around the given input, e.g. the mean Yan et al.) (2024). or the CDF Zargarbashi et al. (2024). Such methods: (i) assume the conformity score function has bounded range, (ii) compute several certificates for

---

Published as a conference paper at ICLR 2025
Vanilla
CAS
RinCP
10.0
1.0
400
Average set size
Emp. coverage
Runtime (ms)
7.5
0.9
5.0
2.5
1
20
100
1000
10000
0.00
0.25
0.50
0.75
100
200
400
Sample size
Calibration nodes
[Left] Average size with different MC sample rates, [Middle] empirical coverage of vanilla and robust CPs under attack, and [Right] runtime of robust CP as function of calibration datapoints (after computing the MC samples which is the number of lower bound computations).
Figure I:
each calibration (or test) point, and (iii) need large number of Monte-Carlo samples to get tight confidence intervals. For the current SOTA method CAS (Zargarbashi et al. 2024), the accounting for sample correction inflates the prediction sets significantly for sample rates below 2000 (see IHl.f). This inefficiency increases to trivially returning ) as the prediction set when we run with higher coverage rates or higher radii (see 6). In contrast, we obtain robust and small prediction sets with only ~ 150 MC samples. Additionally, these methods require computing certified bounds for (at least) each calibration point which further show is wasteful computation.
BinCP. We observe that smooth inference is inherently more robust. Even without certificates, ran- domized methods show slower decrease in coverage under attack (see Fig. 6rright). Given any score function s(x, y) capturing conformity, Zargarbashi et al. (2024) and Gendler et al. (2021) de- E, v)]. Instead, we perform binarization via threshold i.e. 3(x, y) (o, [[((( v) r]] Pre~Nioo.rT)sse
fine the smooth score 5(x, y) (e=
c, 2 7] Both are valid conformity scores, and both change slowly around any x, however, our binarized CP (BinCP) method has several advantages. First, define robust CP that only computes single certificate. In comparison, CAS requires at least one certificate per calibration (or test) point. Sec- ond, our method can effortlessly use many existing binary certificates out of the box without any additional assumptions or modifications. A direct consequence is that we can use de-randomization techniques (Levine & Feizi| 2021 that completely nullify the need for sample correction under l norm. Third, when we do need sample correction, working with binary variables allows us to use tighter concentration inequalities (Clopper & Pearson 1934) (see S D.2) for detailed discussion). Thus, even with significantly lower MC samples, our method still produces small prediction sets (see Fig. Teeft). This improvement even more pronounced for datasets with large number of classes (e.g. ImageNet shown in Fig. 5). Finally, BinCP does not require the score function to be bounded which is a limitation in current methods. Our code is available on the BinCP Github repository
2 BACKGROUND
We assume holdout set of labeled calibration datapoints Deal ((x,, k- which is exchange- able with future test points (In+1 bn+1), both sampled from some distribution D. We have black- box access model from which we compute arbitrary conformity score X' 3 R. e.g. score s(x, y) TT((a) where (xx) is the predicted probability for class (other scores in A
Vanilla CP. For user-specified nominal coverage 1 a, let qa Q (a; [s(x; 91) 1m
(DO))
where Q (---) is the quantile function. The sets defined as C(xn+1) = { : s(In+1111)) v) go have 1-a guarantee include the true label 1 Formally, Pr[yn+1 C(x,,-)] 2 1-a Vovk al. 2005) where the probability is over Deal ~ DD In++1
D. This guarantee, and later our robust sets, are independent of the mechanies of the model and the score function the model's accuracy or the quality of the score function is irrelevant. A score function that better reflects input-label agreement leads more efficient (i.e., smaller) prediction sets. For noisy or adversarial inputs, the
Conformity scores quantify agreement and equivalent up sign flip non-conformity scores.
2

---

Published as a conference paper at ICLR 2025
exchangeability between the test and calibration set breaks, making the coverage guarantee invalid. Fig. middle, and Fig. right show that an adversary (or bounded worst-case noise) can decrease the empirical coverage drastically with imperceptible perturbations on each test point. As defense, robust CP extends this guarantee to the worst-case bounded perturbations.
Threat model. The adversary's 's goal is to decrease the empirical coverage probability by perturbing the input. Let : X' - 2 be a ball that returns all admissible perturbed points around an input. For images a common threat model is defined by the E2 norm: (xx { || æl|2 S rr] where the radius r controls the perturbation magnitude. Similarly, we can use the ε norm. For binary data and graphs. Bojehevski et al. (2000) define B, Br.... (ax) = { Σ T
a 1] S ra. > T[ 2; + 1] S } where the adversary is allowed to toggle at most ra zero bits, and ra one bits.
Inverted ball 8- At test time we are given a (potentially) perturbed a E B(x). However, to obtain robust sets, we need to reason about (the score) of the unseen clean æ. Naively, one might assume that x (( the clean point is in the ball around the perturbed point. However, this only holds in special cases such as the ball defined by the l2 norm. For example, if a binary I was obtained by removing ra bits and adding ra bits, to able reach the clean from the perturbed 7 we need to add ra bits and remove Ta bits instead since Br..r. unlike B, is not symmetric. We define the inverted ball B as the smallest ball centered at ã E B(x)) that includes the clean æ. Formally, B should satisfy VI E ((x)
E B- 1 (æ). For symmetric balls like e--norms, B-1 B. For the binary ball ra.t Bra.r, we need to swap Ta and ra to ensure this condition. Zargarbashi et al. 2024) also discuss this subtle but important aspect without formally defining B
Robust CP. Given a threat model, robust CP defines a conservative prediction set C that maintains the conformal guarantee even for worst-case inputs. Formally,
Pr |un+1 E C(# Vē.++ E B(xn++))] 2 -a (a.. 11p..111)000 -o
The intuition behind existing methods is as follows: (i) Vanilla CP covers #n++1 with 1 - a proba- bility (ii) if y E C(ma+1) then y E C(#,+1). Thus, robust CP covers Fn+1 with at least the same probability. Here, (ii) is guaranteed via certified lower bounds et [s, x B] or certified upper bounds clss, x, B B.
Theorem (Robust CP from Zargarbashi et al. (2024)). Define 8y() = s(:.).. With (s ãe, B_1 2 maxx' s(x', v). let Crest (Ān+1) (y cl [sy, B,+1,,-"1200 9). then Crest satisfies Eq. 7 (lest-time robustness). Alternatively, with ct [sy, x, B] S (min s(a', v).
define at = Q (a; { [+ I,, B)," Then (mmi(@n+1) = yy: ( y) 2 qy) also satisfies Eq. /calibaaiion-iine robustness).
In Theorem test-time robustness uses B-1 since it queries the clean point from the perspective of the perturbed test input. Alternatively, calibration-time robustness uses B since the clean calibration point is given and we are finding the lower bound for the unseen test point in the test. The intuition is that the lower bound scores from the clean calibration points exchangeable with the lower bound of the clean test input. The perturbed test input will surely have a higher score compared to this lower bound, hence it would be covered with higher probability.
We can obtain the ct, cº bounds through neural network verifiers Jeary et al. 2024) or randomized smoothing (Cohen et al. 2019). We focus on the latter since we get model-agnostic certificates with black-box access. The coverage probability is theoretically proved in CP. Similarly, (adversarially) robust CP also comes with a theoretical guarantee. In both cases we can compute the empirical coverage as a sanity check. Another metric of interest in both cases is the average set size (the efficiency) of the conformal sets.
Randomized smoothing. A smoothing scheme& & X + X' maps any point to a random nearby point. For continuous data Gaussian smoothing {(x) x + e adds an isotropic Gaussian noise to the input ~ (0, o I). For sparse binary data Bojchevski et al. (022)) define sparse smoothing as E(x) = x @ e where @ is the binary XOR, and | ~ Bernoull( (p Pwis)), where Pt. and po are two smoothing parameters to account for sparsity. To simplify the notation we write + instead of {(x) in the rest of the paper for both Gaussian and sparse smoothing, but our method works for any smoothing scheme beyond additive noise. Regardless of how rapidly score function s(x; y) changes, the smooth score s(x; y) = [,[s(x+ +. y)] changes slowly near æ. This enables us to com- pute tight ct, ct bounds that depend on the smoothing strength. See $ 4 B and $ D.1 for details.
3

---

Published as a conference paper at ICLR 2025
3 BINARIZED CONFORMAL PREDICTION (BINCP)
We define conformal sets by binarizing randomized scores. We first show that this preserves the conformal guarantee for clean data. Then in we extends the guarantee worst-case adversarial inputs. As we will see in ouu binarization approach has gains in terms of Monte-Carlo sampling budget, computational cost, and average size.
Proposition 1. For any two parameters the boolean function accept :: -P, T] and the prediction set C(:P,T) as
(0, 1), E IR, given smoothing scheme define
accept|æ V. [Pr[s( + e, v) 2 7] pl and C(x:p,T) {y accept(a v.P,T)
For any fixed p. let
n
Ta (p) sup
Cccept((z,.::..7) a1-a) (n
then the set C C( P; (a has 1
coverage guarantee. Alternatively, for any fixed v, let
Pa(T) sup p: accept(2.; (1- - (m+ (m+
(3)
p
again the prediction sel C(xn+ Po (T), has - a coverage guarantee.
The correctness of Prop. can be directly seen by noticing that we implicitly define new scores.
Quantile view. Let S; s(x, + e, e;); be the distribution of randomized scores for and the true class ye- Let (p) Q (p: S:), we have that Ta (p) = Q (a: (p)( )==)
quantile of quantiles. Similarly, define (T) Q- (T; S;) then Pa (T) Q (o; {pi(T) p is quantile of inverse quan- tiles. Both (p) for a fixed and (T) for a fixed r are valid conformity scores for the instance æ;, since exchangeability is trivially preserved. Therefore, Ta (p) and Pa (a(T) are just the standard quantile thresholds from CP on some new score functions. This directly gives the a coverage guarantee. This view via the implicit scores is helpful for intuition, but we keep the original formulation since it more directly amenable to certification as we show in | We provide an additional formal proof of Prop. via conformal risk control (Angelopoulos al. 2022 in S C.
Using either variant from Prop. let (Pa, Ta) equal (p. Ta (p)) or (Pa(T), as the final pair of parameters. For test points 1x+1 accept labels whose smooth score distribution has at least Po proportion above the threshold Ta i.e. accept(2 xx y/ Pa. Ta) = 1. The term "binarization" refers to mapping each score sample above increasing and continuous CDF (e.g. isotropic Gaussian smoothing) both variants are equivalent.
and all others O. For distributions with strictly
Lemma 1. Given distributions {S with strictly increasing and continuous CDFs, let Ta (p) be obtained from Eq. 2 with fixed p and (- (-) be as defined in Eq. We have Pa Pa(Ta(p)) p.
We defer all proofs to C For fixed Prop. 1 yields (p, To (p)). Fixing 7
(p) we get sets
with (po (T), 7) (pa To (P), To (p)) which also equals (p, To (p)) from from Lemma Fig. shows the accept(<; r) function for several examples. This function is non-inereasing in both parameters
1.0
0.5
0.5
0.5
0.5
0
0.5
0.5
0.5
0
0.5
0
0.5
Figure 2: [Left] Function accept(æ;; Mrp. 7) for different (p, 7) pairs for four random CIFAR-10 instances. Black equals and white equals 0. [Right] Empirical coverage for different (p, r) pairs. Any (p, T) pair on the dashed black line (the 0.9 contour) gives conformal sets with 90% coverage.
4

---

Published as a conference paper at ICLR 2025
p and In general, any arbitrary assignment of p, and 7, results in some expected coverage accept(;s p. 7) equals to for some number of (æ), yo (Fig. right.. Pairs (Pa: Ta) obtained from (rompProp..r 1 are placed on the 1 - contour of this expectation. The empirical coverage is close to this expectation due to exchangeability (Berti & Rigo 1997).
Remarks. The scores T; (p) (and similarly (r( remain exchangeable whether the quantile over the smoothing distribution is computed exactly or estimated from any number of Monte- samples. That is. Prop. holds regardless. However, when need to be more careful when consider the certified upper and lower bounds. In In 4
we first derive robust conservative sets that maintain worst- case coverage, assuming that we can compute probabilities and expectations exactly. Since this is not always possible, in S 5] we provide the appropriate sample correction that still preserves the robustness guarantee when using Monte-Carke samples. We also discuss a de-randomized approach that does not need sample correction.
4 ROBUST BINCP
From Prop. (either variant) we compute a pair (Po. Ta). Following Prop. for clean 2n+1, we have Pr [ x1 + 3x+11) 2 Ta] 2 Pa with probability a-a. We will exploit this property. Define fy(x) = [( v) 2 Ta). we have (2) = E. [Ts(( + e, 2 Ta] = Pr. [s(x + c, 2 Ta].
Conventional robust CP. One way attain robust prediction sets is apply the same recipe as Zargarbashi et al. (2024) (CAS) by finding upper or lower bounds on the new score function. CAS uses the smooth score 8y (x)) [s(s(<r E, v)]. Instead, we can bound fa which is smooth binary classifier. Note that discussed in $ (quantile of inverse quantiles), fy (x) is conformity score function itself. Therefore, following heorem the test-time, and calibration robust prediction sets are
Crest (ύn+1) = c
B pat. (Cn)()n+1) - tv: ty (Tn+1) 2 g+}
(4)
where gt - Q (a; (ctls æi, Tr, B)) In short, we replace the clean fe... - (xn+1) with either its certified upper c² or lower e+ bound. We elaborate on this approach before improving it.
Computing ct and ct. Computing exact worst-case bounds on f (fy for all y) is intractable and requires white-box box access to the score function and therefore the model. Following established tech- niques in the randomized smoothing literature (Lee al. 2019) we relax the problem. Formally,
c- (f, B
min Pr[h(ā + c)] s.t. Pr[h(= + c)] = Pr[f(x + c) f(z)
(5)
acB(x)
NCH
where H. is the set of all measurable functions h. Since f E H we have c+ x, B] < f(t) for all B(x). The upper bound cf xx is the solution to a similar maximization problem.
Closed form. For &g ball with Gaussian smoothing, Eq. 5) has a closed form solution (=))-r where D is the CDF of the normal distribution (O, a (O0,aI))Cohee Kumar et al., 2020). The upper bound is similarly computed by changing the sign of r. Yang et al. (2020) show the same closed-form applies solution for the & ball, and additionally, discuss other perturbation balls and smoothing schemes most of which are applicable. For sparse smoothing we
(f, (
al. 2019
can compute the bounds with simple algorithm with O(r, + ra) runtime (Bojchevski et al. 2020
which we discuss in S C For & ball and uniform smoothing the lower bound equals fy(
(2(XX
where 6 ~~ (0, 2Aja (Levine & Feizi 2021 This bound can also be de-randomized (see $
Single Binary Certificate. From the closed-form solutions we see that the bounds are independent of the definition of f. and the test point æ; i.c. their output is a function of the scalar p := (x). We defer the discussion for why this holds to [ B and $S D.I. in short the solution for any x can be obtained from alternative canonical points u, and u. Therefore, we write c [p, B = c x; B to show that ct depends only p and B, and the same for ct. We also notice that in common smoothing schemes and perturbation balls, holds that cC [p. B B] = p which allows us to reduce both calibration-time and test-time robustness to solving single binary certificate. We formalize this in Lemma
Lemma 2. If c- (ct [p, B B] for all p. then Cued((nn))) Cou((En+1) Coia( where Cain(#n (in+1) = {y accept( y o Pa. , Ba)Ta)) = {y Pr.(o(xn+1 + e, E.8n+1) 2 Tal 2 ct [Pa, }.
5

---

Published as a conference paper at ICLR 2025
c
Pa.
Pa, B
1.0
1.0
1.0
0.12
Certified pa
Bo.2
0.5
0.5
Bo,3
0.5
B1.3
0.25
0.5
0.0
0.0
0.0
0.5
0.5
1.0
0.0
Pa
Pa
Pa
Figure 3: [From left right] Certified bounds for sparse smoothing. ( ball with de- de-randomized uniform smoothing (Levine & Feizi 2021), and l (same as { ball with Gaussian smoothing.
To see why, let Pn+1 f (1)+1). The test-time robust coverage requires c pn+1, Pa- Since both ct, and ct are non-decreasing w.r.t. p. we have c
2 c B]. We have the equivalent condition Pn+1 2 et [P., .3.. This implies that we only need to compute single certificate et [Pa; B] once with the single Pa value given by Prop. This also allows us seamlessly integrate other existing binary certificates in a plug and play manner. In contrast, with Theorem fo Great or Ceal we need at least one certificate per test (or calibration) point. Notably, these prediction set are identical to our cheaper Cbin- For illustration, Fig. 3 shows the certified lower and upper bounds for various Pa values and various smoothing schemes.
holds due symmetry of the smoothing scheme w.r.t. B, and B and is satisfied by most smoothing schemes. In Lemma we prove that Gaussian, uniform, and sparse smoothing all have this property.
Intuitively ct --- 31'1,
Lemma 3. For Gaussian, and uniform smoothing under l, and & balls B, = B For sparse smoothing and Br..ra we have _ Bra.r. In all three cases have c ct [p. B '1 11 p.
To summarize, for robust BinCP, we first compute conformal thresholds (po: T.) from Prop. Then for a perturbation ball that satisfies o- [cT[p, B 1, = p. we compute ct [pa. B) and compute the prediction sets with (c+ Pac, B3, Ta.) instead. The resulting sets have 1 - robust coverage.
Corollary 1. With (p., Ta) from Prop. 1 on calibration set Deab let Øn+1 be exchangeable with
Denl and #. E 13 (( If for the smoothing scheme & and the threat model B and for all we have (t 1, = then the set Coin mi))) = {y Pr[ss(@n+1 + 6, Bn+1) 2 Tal Z
et (Pa } has 1 coverage (the pseudocode is in SA
5 ROBUST BINCP WITH FINITE SAMPLES
The certificate in Corollary relies on exact probabilities Pr[s(#.+11 e, 2 Ta] which is of- ten intractable compute. Instead,
either apply de de-randomization techniques estimate nigh-confidence bounds of these probabilities. We first describe the latter approach. For each cal- ibration point (6) compute
To Di=1 T[s(æ; v, 2 Ta. where is the number of Monte-Carlo (MC) samples. For each label of the (potentially perturbed) test point we compute g.+11 > [[s(@n+11 + y) 2 Ta]. We use the Clopper-Pearson confidence interval (Clop- per & Pearson 1934) to bound the exact probabilities via the MC estimates. To ensure the sets are conservative compute a lower bound for calibration points and upper bound for points. Collectively, all bounds are valid with adjustable 1 probability. To account for this, we set the nominal coverage level to a-a + 7) such that we have
coverage total. Similar to targarrabashhi et al. 2024), we compute each bound with 1 ///( + kl) probability where & is the number of classes. Let p: = Pr Pr[s(a;; + 6, w: 2 TaJ for E (1,.... ... n + 1) the exact probabilities. The final sample-corrected robust predictions sets are given in Prop.
Proposition 2. Let of S Pj hold with (D + k) for each calibration point {l..... where ls the number of target classes. For a given test point In+1 11 let i 1. 2 Patly with
1 n/ + kk) where Pntl, = Pr|s([an11 + +6, v) 2 va). With P = Q (a (ut Vi.)

---

Published as a conference paper at ICLR 2025
CAS
BinCP
Vanilla
10
Average set size
Fa
10a
10
0.06
0.25
0.50
0.75
0.06
0.25
0.50
0.75
2
F'
Figure 4: [Left right] Average prediction set size of robust CP for CIFAR-10, and ImageNet with Gaussian smoothing (a = 0.5), and CoraML with sparse smoothing. All results are for 2000 Monte- 0.85 for ImageNet, and a 0.9 for CIFAR-10 1- and CoraML.
Carlo samples. We set
[ph. we set the robust conformal threshold pair as (c+ B). Ta)) Then the prediction set defined as
C. (i B), Ta) = -ty gut1.,y 2 c+(p,, i BJ} has - a coverage probability.
Such sample correction a crucial step for smoothing- based robust CP, since the robustness certifi- cate is probabilistic. The failure of the certificate depends to the failure of the confidence intervals. In contrast, for deterministic and de-randomized certificates such DSSN (Levine & Feizi 2021). we do not need sample correction since we can exactly compute p: and Pa Q (a; {p: Note, vanilla non-robust) BinCP does not need sample correction maintain the guarantee (see
EXPERIMENTS
We show that: (i) We can return guaranteed and small sets for both image classification and node classification, with a significantly lower number of Monte Carlo samples. (ii) Our sets are computa- tionally efficient. (iii) There an inherent robustness in randomized methods. (iv) We can also use de-randomized smoothing-basee based certificates that do not require finite sample correction.
Setup. We evaluate our method on two image datasets: CIFAR-10 (Krizhessky] 2009) and Ima- geNet (Deng et al.] 2009), and for node-classification (graph) dataset we use Cora-ML Mora-MLMMCCallmmm McCallum jet al. (2004). For the CIFAR-10 dataset we use ResNet-110 and for the ImageNet dataset we use ResNer-50 pretrained models with noisy data augmentation from Cohen et al. (2019). For the graph classification task we similarly train a GCN model Kipf & Welling (2017) on CoraML with noise augmentation. The GCN is trained with 20 nodes per class with stratified sampling as the training set (and similarly sampled validation set). The size of the calibration set is between 100 and 250 (sparsely labeled setting) unless specified explicitly. Our reported results conformal predic- tion performance are averaged over 100 runs with different calibration set samples. We calibrated BinCP with p 0.6 fixed value, however small changes in p do influence the result. For the graph dataset we calibrated BinCP with = 0.9. Intuitively as ct jp, B3] has a sharp decay for sparse smoothing (see Fig. left), we set p number such that ct [p, B] still remains high.
We conducted our experiment using three different smoothing schemes. (i) Smoothing with isotropic Gaussian noise, 021 0.25, and 0.15. Our reported results for BinCP are valid for both 4, and & perturbation balls. (ii) De-randomized smoothing with splitting noise (DSSN) from Levine & Feizi 2021)) from which we attain & robustness. We examine two smoothing levels À = 0.25/ /3, and 0.5/ /3. (iii) Sparse smoothing from Bojchevski et al. 2020) with = 0.01, and = 0.6 on node attributes. We report robustness across r. E {0, 1). and rd {0. 1, 2,2.3). We compare our the result from BinCP to the SOTA method CAS (Zargarbashi et al. 2024). Previously it was shown that CAS significantly outperforms RSCP (Gendler et al.) 202 both with and without finite sample correction. In S 7 we discuss the other related works in detail. In the standard setup, we estimate the statistics (mean and CDF, or Bernoulli parameters) with 10 Monte-Carlo samples, and we set 1-a 0.9. This setup is picked in favor of the baseline since by increasing the nominal coverage decreasing the sample size BinCP outperforms the baseline with an even higher margin. Throughout the paper we report different nominal coverages and MC sampling budgets.

---

Published as a conference paper at ICLR 2025
CAS
BinCP
Vanilla
10a
10
10a
Average set size
Corrected
10a
10
10a
10a
10
10
500
1000
2000
2500
0.85
0.90
0.95
0.06
0.25
0.50
0.75
Sample rate
Figure 5: On ImageNet dataset, [left] average set size for 1 0.85 with various MC sampling budgets. [Middle] Set size across various levels of 1 -a for 2 10 samples. [Right] Set size without sample correction (asymptotically valid assumption). The sample-corrected variants are shown with a dotted line. In all plots y-axis is log-scaled.
Smaller set size. Fig. shows that for all datasets, and both smoothing schemes (isotropic Gaussian and sparse smoothing), BinCP produces smaller prediction sets compared to CAS. Our prediction sets computed with Gaussian noise are robust to both L, and l2 perturbation balls with the same radius (Yang et al. 2020 In Fig. 5) compare to CAS on ImageNet dataset over various sample rates, coverages, and radii. Since CAS with sample correction returns trivial sets for a 0.9 (see Fig. 5 in Fig. leef we compare the results for 1 Monte Carlo sample rate, the average set sizes of CAS and BinCP become closer - Fig. Ileett for CIFAR-10, 10. Fig. lelt for ImageNet, and Fig. 7eee for CoraML depict the impact of higher sam- pling budget. Intuitively as the number of classes increase (e.g. ImageNet dataset) the union bound classes result in larger prediction sets (looser confidence intervals). In S E (Fig. 9) show that BinCP is also consistently better for smaller radii (a setup similar to verifier based robust CP For the reported set size, we attain robust CP of significantly larger radii.
0.85. By increasing the
(Jeary al. 2024
Note that Fig. rigght, and Fig. leef show the performance on the transductive node classification setting where perfect robustness achievable for free through memorization (see discussion by Gosch et al. 2023)). Nonetheless, comparing BinCP to CAS is still meaningful. Constructing robust conformal sets for GNNs in realistic (inductive) setup is more challenging as discussed in D.3
Exact & robustness, Using the de-randomized DSSN certificate for & perturbation ball (eevine & Feizi, 202I) we derive the first smoothing based de-randomized robust CP. As shown Fig. 6 middle the de-randomized robust BinCP with uniform noise results in significantly smaller set size across all radii compared to Gaussian noise (Fig. leftt) Notably due to exactness of the computed statistics, for randomized DSSN-based certificate bypass the finite samples correction.
TPS
0.25
2.5
APS
Averuge set
0.5
Coverage
Vanilla Smooth
logits
2.0
0.5
2.0
1.5
0.0
0.06
0.12
0.18
0.25
0.06
0.25
0.50
0.75
0.0
0.2
0.4
Figure 6: [Left] Performance of BinCP on different score functions under Gaussian smoothing with 0.25. [Middle] Set size of BinCP with & robustness and derandomized DSSN smoothing (o \/V3). [Right] Vanilla non-smooth and smooth (a 0.25) prediction (solid and dashed colored lines show TPS and APS score function) under attack. All results are on CIFAR-10.
8

---

Published as a conference paper at ICLR 2025
10.0
4
MC samples
CAS
Average set size
2 10a
BinCP
7.5
0.12
G 10
1.8
0.25
5.0
0.5
2
1.7
2.5
3
10a
10a
0.06
0.25
0.50
0.75
Vd (To = 1)
Sample size
Figure 7: Comparison between BinCP and CAS for [Left] the effect of higher MC sample budget in CoraML dataset (sparse smoothing). [Middle] effect low samples without finite samples correc- tion for CIFAR-IO dataset (a 0.25), and [Right] various smoothing strengths
Ignoring sample correction. While unrealistic in practice, Gendler et al. (2021) report results with- out applying finite sample correction. Zargarbashi et al. (2024) maintain small set sizes (with large MC sample rate) for CIFAR-10. However, for ImageNet and CoraML they only report the results without correction, and therefore with an "asymptomatically valid" coverage guarantee - valid when sample rate approaches infinity. In In Seeeft applying sample correction to CAS on datasets like Im- ageNet, inflates the prediction sets up to y, likely due to union bound on a large number classes. for asymptotically
Fig. 5iighht shows that on ImageNet, both methods show similar prediction valid setup. Notably BinCP with sample correction is not far from the non-corrected setup, while CAS shows large gap. Similarly Fig. left shows that for sparse smoothing, increasing sample rate helps CAS considerably while its effect on BinCP is almost negligible. In D.2 we explore the intu- ition behind how binarization can mitigate the impact of finite sample correction with fewer samples.
Number of samples. The upperbound in CAS is obtained through two step process. First given the corrected CDF, we compute the worst case (adversarial) CDF. Then using upper bounded (or lower bounded) CDF, we apply the Anderson bound to obtain bound on the mean from the CDF ZZrgarbashii et al., 2024). Increasing the number of bins increases the computation slightly but produces tighter bounds. To observe this effect, without sample correction, we decrease the number of samples to a very low number (~ 10, however unrealistic) and in Fig. miidde we see that set without accounting for finite sample estimation.
size in CAS slightly increases
Effeet of o, and score function. The strength of Gaussian smoothing controlled by a in E(x) t, (O, o In Fig. right observe trade-off in choosing for both methods. Higher smoothing intensity results larger set sizes in the beginning, but by increasing the robustness radius the set size increases slowly. Still in all cases BinCP outperforms CAS. It best practice compute smooth prediction probabilities using a model trained with similar noise augmentation. We reported this result in S E Table 2). Interestingly, when training and inference does not match, BinCP shows good results while CAS is more sensitive.
We mainly focus on TPS score function, in addition Fig. 6-eeft compares APS, and logit as score functions. Here across all radii TPS is more efficient. We further report results for APS in S Since logits are unbounded, CAS is not applicable
Benefits of smoothing. The guarantee of robust CP breaks for adversarial (or noisy) inputs. In In 6 right we compare vanilla prediction and smooth prediction sets under adversarial attack. Notably, smooth models even without conservative certificate show an inherent robustness. As illustrated, the non-smooth model quickly breaks to near coverage guarantee for very small r. Relatedly, recent verifier-based robust CP (Jeary et al. 20244) report comparably larger prediction sets even for one order of magnitude smaller radius (compared to the certified radii by BinCP). This intuitively suggests that for robust CP it seems that randomization is inherently beneficial.
Limitations. While BinCP reduce the required MC sample rate significantly (e.g. from 2000 to 150 on CIFAR-10), still this number of inferences is computationally intensive. The robustness in the input space X' is not yet linked to robustness w.n.. distribution shift. Although BinCP applies on sparse smoothing, realistic threat model for graphs (inductive GNNs) still not addressed.

---

Published as a conference paper at ICLR 2025
7 RELATED WORK
Robust CP via smoothing. Gendler et al. (202T) introduced the problem and defined a baseline robust CP method, RSCP (randomly smoothed conformal prediction), which applies Theorem in combination with the weea-constrained upper bound for l2 perturbations and Gaussian smoothing.
This upper bound has a closed form solution: s(ir,)) y) Φ (p) + r) where p R[s((: + e, v. Originally, RSCP did not account for finite sample correction making its coverage guarantee only asymptomatically valid. Yan al. (2024) show that correcting for finite samples in RSCP leads to trivial prediction sets ((x) = V. As a remedy, they define a new score function based on temperature scaling which in combination with conformal training (Stutz et al., 2021) improves the average set size. So far both methods use test-time robustness. In E. we show that BinCP outperforms RSCP+.
In contrast Zargarbashi et al. (2024) utilizes the CDF structure of the score and instead apply the tighter CDF-based bound defining CDF aware sets (CAS). In combination with calibration-time robustness, they show that only [Deall certificate bounds should be computed maintain robust coverage guarantee as in E5q. T] In addition to a gain in computational efficiency, they show that in the calibration- time robustness, the error correction budget can be used more efficiently. On CIFAR- 10 they return a relatively small conformal set size. In all aforementioned methods, a large MC sampling budget (e.g. 10 samples) is assumed which is challenging for real-time applications. This issue is exacerbated for datasets like ImageNet where the large number of classes amplifies the effect of multiple testing corrections.
Robust CP via verifiers. Outside the scope of randomized smoothing Jeary et al. (202)) use neural network verification to compute upper (or lower) bounds. This requires white-box access to the model weights, while our proposed method works for any black-box model and randomized or exact smoothing-based certificate. Interestingly, in (Jeary et al.) 2024) (Table 1) the empirical evaluation is for 0.02 which is smaller than the minimum radius we reported. For completeness, we evaluated BinCP on very small radii in S E (Fig. leeft,, and for the same r our sets are 2x smaller. As discussed in 6 (ig. 6 in general, smooth prediction, even without accounting for the adversary, shows to have an inherent robustness.
Other robustness results. Alternatively Ghosh et al. (2023) introduce probabilistic robust cov- erage which intuitively accounts for average adversarial inputs. This is in contrast with our core assumption of worst-case adversarial inputs. In other words, instead of 1 a coverage for any point within the perturbation ball around In-1, "probabilisticall robust coverage" guarantees that the probability to cover the true label remains above consider the worst-case ă. Their "quantile of quantiles" method looks superficially similar to BinCP as they also compute n+ k+ quantiles. However there are two notable differences. Their first order of quantiles (on true calibration scores and the score for each class of the test point) is over random draws from the perturbation set. BinCP computes the first order quantiles (T:(p) in fixed setup) over the smooth score distribution. Their conservative quantile index is based on user-specified hyperparameter that accounts for conservativeness while BinCP finds the certified probability at [aa [3] for the worst case adversarial example. BinCP guarantees that any z E B(x)) is covered if x is covered. Furthermore, there are other works addressing distribution or covariate shift in general beyond the score of worst-case noise robustness (Barber et al. 2022 Tibshirani al. 2019).
on average over all I E B(x)), while we
CONCLUSION
We introduce BinCP, a robust conformal prediction method based on randomized smoothing that produces small prediction sets with a few Monte-Carlo samples. The key insight is that we bina- rize the distribution of smooth scores, by a threshold (or thresholds) that maintains the coverage guarantee. We show that both calibration and test-time robustness approaches (discussed B 2) are equivalent to computing a single binary certificate. This directly enables us to use any certificate that returns a certified lower-bound probability right out of the box; including de-randomized certificate for & norm. The binarization enables us to use tighter Clopper-Pearson confidence intervals. This leads directly to faster computation of prediction sets with significantly lower Monte Carlo sample- rate (compared to the SOTA), and therefore less forward passes per input. Interestingly, we show that even without accounting for an adversarial setup, CP with smooth score shows more robustness to adversarial examples in comparison with the conventional vanilla CP.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENT
We thank Giuliana Thomanek and Jimin Cao for their feedbacks on our initial draft.
ETHICS STATEMENT
In this paper, we study the robustness of conformal prediction. The main focus of our work is to increase the reliability of conformal prediction in presence of noise or adversarial perturbations. Therefore, we don't see any particular ethical concern to mention about this study.
REPRODUCIBILITY STATEMENT
To ensure the reproducibility of our results, we have provided the algorithm is in S and the implementations are available at the BinCP Github repository The models we used are also pre- trained and all accessible from the cited works. We specified the setup including parameter selections in 6
REFERENCES
Anastasios N Angelopoulos, Stephen Bates, Adam Fisch, Lihua Lei, and Tal Schuster. Conformal risk control. arXiv preprint arXiv:2208. 02814, 2022.
Anastasios Nikolas Angelopoulos and Stephen Bates. A gentle introduction conformal prediction and distribution-free uncertainty quantification. ArXiv, abs/2107.07511, 2021. URL https:
7/api. www.smeeinnncchoaaammmmo htt.:aaa..c..eoopos...2233333331
Rina Foygel Barber, Emmanuel J. Candès, Aaditya Ramdas, and Ryan J. Tibshirani. Conformal
prediction beyond exchangeability. The Annals of Statistics, 2022. URL https://api.
Patrizia Berti and Pietro Rigo. glivenko-cantelli theorem for exchangeable random variables.
Statistics & probability letters, 32(4))385-391, 1997.
Aleksandar Bojchevski, Johannes Gasteiger, and Stephan Günnemann. Efficient robustness certifi- cates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In International Conference on Machine Learning, pp. 1003-1013, PMLR, 2020.
Charles J Clopper and Egon S Pearson. The use of confidence or fiducial limits illustrated in the case of the binomial. Biometrika, 26(4):404-413, 1934.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In international conference on machine learning, pp. 1310-1320. PMLR, 2019.
Jesse C. Cresswell, Yi Sui, Bhargava Kumar, and Noël Vouitsis. Conformal prediction sets
improve human decision making. ArXiv, abs/2401. 2005/4441,,744,, 2024. URL https://api.
ietpaatncscchoooo owwp:oopg/orruuuu TD: 267216 902]
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, K. Li, and Fei-Fei. Imagenet: A large-scale hier- archical image database. 2009 IEEE Conference Computer Vision and Pattern Recognition, pp. 248-255, 2009. URL httth::////// //api semant i cscho ar org or..aaooorooo......o...
ID: 5724
Asaf Gendler, Teui-Wei Weng, Luca Daniel, and Yaniv Romano. Adversarially robust conformal prediction. In International Conference on Learning Representations, 2021.
Subhankar Ghosh, Yuanjic Shi, Taha Belkhouja. Yan Yan, Janardhan Rao Doppa, and Brian Jones. Probabilistically robust conformal prediction. Conference on Uncertainty in Artificial Intelli- gence, 2023. UtL.https://aat /api. commanticscholaln orgg coo.ussSD::2 2603::2::263773
Lukas Gosch, Simon Geisler, Daniel Sturm, Bertrand Charpentier, Daniel Zügner, and Stephan Günnemann. Adversarial training for graph neural networks: Pitfalls, solutions, and new direc- tions. In 37th Conference on Neural Information Processing Systems (Neurips), 2023.

---

Published as a conference paper at ICLR 2025
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural
networks, In International Conference on Machine Learning, 2017. URL https: //aii.
semanticschole
org/ wtw.:aaaw....ooooourr.oooo
Kexin Huang, Ying Jin, Emmanuel J. Candès, and Jure Leskovec. Uncertainty quantification over graph with conformalized graph neural networks. ArXiv, abs/2305,14553 2023. URL https:
7/api.
Linus Jeary, Tom Kuipers, Mehran Hosseini, and Nicola Paoletti. Verifiblyy robust conformal pre- diction, 2024.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ArXiv, abs/1609.02907, 2017.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009. URL https:
//api. htt.eeetttiiaecclaaa.rroooororaa
Aounon Kumar, Alexander Levine, Soheil Feizi, and Tom Goldstein. Certifying confidence via randomized smoothing. Advances in Neural Information Processing Systems, 33:5165-5111 2020.
Guang-He He Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certificates of adversarial ro- bustness for randomly smoothed classifiers. Advances in Neural Information Processing Systems, 32, 2019.
Alexander J Levine and Soheil Feizi. Improved, deterministic smoothing for 1_1 certified robustness. In International Conference on Machine Learning, pp.
PMLR, 2021.
Andrew McCallum, Kamal Nigam, Jason D. M. Rennie, and Kristie Seymore, Automating the construction of internet portals with machine learning, Information Retrieval, 3:127-163, 2004.
Yaniv Romano, Matteo Sesia, and Emmanuel J. Candès. Classification with valid and adaptive coverage. arXiv: Methodology, 2020.
Mauricio Sadinle, Jing Lei, and Larry A. Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 114:223 234, 2018.
David Stutz, Ali Taylan Cemgil, Arnaud Doucet, et al. Learning optimal conformal classifiers. arXiv preprint wtxxv:2210009199: 2021.
Ryan J Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal pre- diction under covariate shift, Advances in neural information processing systems, 32, 2019.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world. 2005.
Ge Yan, Yaniv Romano, and Tsui-Wei Weng. Provably robust conformal prediction with improved efficiency. arXiv preprint arXiv:2404. 19651, 2024.
Greg Yang. Tony Duan, J Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing all shapes and sizes. In International Conference on Machine Learning, pp. 10693- 10705. PMLR, 2020.
Soroush H Zargarbashi and Aleksandar Bojchevski. Conformal inductive graph neural networks. arXiv preprint arXiv:2407.09173, 2024.
Soroush H. Zargarbashi, Simone Antonelli, and Aleksandar Bojchevski. Conformal prediction sets for graph neural networks. In International Conference on Machine Learning, 2023. URL
https: //ttss://ap... semant icschol ar. wrg/CorrpssID... 22: 6260297888
Soroush H Zargarbashi, Mohammad Sadegh Akhondzadeh, and Aleksandar Bojchevski. Robust yet
efficient conformal prediction sets. In Forty-furst International Conference on Machine Learning, 2024.
12

---

Published as a conference paper at ICLR 2025
A ALGORITHM FOR ROBUST (AND VANILLA) BINCP
Here we provide the algorithm for BinCP in both p-fixed, and 7-fixed setups. The two setups differ in calibration and finite sample correction, while computing the certificate, and returning prediction sets is similar both. Note that in p-fixed version after computing the quantile Ta we correct for finite samples which results in a lower Pa.
Note that in both algorithms we set m, and 1) as fixed hyper paremetarsesss defining the number of random samples per each datapoint and the collective failure probability of the confidence intervals. Therefore SlopperPeasson (p) actually refers to the Clopper-Pearson interval with p m success out of samples and failure probability of n/(k: + (Deat)).
Algorithm 1: BinCP with r-fixed setup
Input: Score function X' y IR; Calibration set D ( V/ ;=1+ Smoothing scheme Threat model B satisfying the assumption in Lemma Fixed threshold т, and (potentially perturbed) test point Fn-1.
Output: A prediction set Chin( with 1 - robust coverage probability
for each calibration point (æi, Ve) E Deal do
Sample from + for times;
Compute qi 2z=1 [[s( + e, 2 r]: if Exact Certificate then
g: = q3
else
9:
ClopperPearson (q:);
end
end
Set pd = Q (o:: {gt (
Compute [ph, B) from Eq. 5 (Lower bound minimization);
for each class y E y do
Sample from {(ān+1) for m times;
Compute qa+11. E5=1 [(( + E, 2 r]:
m
if Exact Certificate then
g In+1;
else
end 9 == ClopperPearsonhig!! (grreeeeerssonngggggg1.).) (9n+1.y);
end
return Cly of g [tt, [.pt.BBB. B}}
Score functions. Throughout the paper we reported results for TPS score directly setting the softmax values as the score s(x,, y) = x (æx, y) (Sadinle et al. 2018) In vanilla CP (r = 0). TPS tends to over-cover casy examples and under-cover hard ones (Angclopoulos & Bates 202I). Alternatively "adaptive prediction sets" (APS) aiming for conditional coverage uses the score function defined as s(xr, y) (p(ar, y) + ((x),, where p(æ,y) y) : >n (x)))1 [m()), π T()),, is the sum of all classes predicted as more likely than y, and u E [o, 1] is uniform random value that breaks the ties between different scores to allow exact 1 a coverage (Romano et al. 2020). Another approach is to directly use the logits of the model as the score. This is not applicable in CAS and RCSP+ Zargarbashi et al. 2024 Yan al. 2024) as they work with bounded scores. BinCP can also work with unbounded score, hence, we also report the results on CP with logits. All three score functions are reported in Fig. 6-left for BinCP. Interestingly we do not see any significant difference in set size between APS and TPS when smoothed. We report BinCP with APS score in E over all and radii. Orthogonally, while RSCP with either scores quickly breaks to returning trivial sets, RSCP+ refines the score function through biased temperature scaling, This can also be considered as another score function (or transformation over any score function) tailored for robust setup. We compare BinCP with RSCP+ in Fig. 14
13

---

Published as a conference paper at ICLR 2025
Algorithm 2:
BinCP with p-fixed setup
Data, score function, smoothing, and same as allgoritmm Output: Same as aslaloort 1
Input:
Fixed probability Pa
Update Pex < Pa m mm/mm (accounting for discrete samples);
for each calibration point (æ,, 3/) Peal do
Sample from 2; + E for m times;
Compute T, = Q (Prs {s( + e. ())
Exact Certificate then Pa : Pai
else
p. == ClopperPearson (Pa);
end
end
Set To = Q (a; [T: h=))
Compute at (pt. B) from Eq. 5 (Lower bound minimization);
for each class y E e do
Sample from {(Āx+1)
for times;
Compute in+1.y
E [s (fn41 + E, 2 Ta]:
I := same as algorithm
end
return Cly u 2 (t B}}
B COMPUTING CERTIFICATE OPTIMIZATION
Canonical view. Turns out that for isotropic Gaussian and sparse smoothing, we can always attain this minimum at canonical points for any test point Tn+11 we can translate the function, and the points to the origin, and the worst case to the border of B(x,++1). Formally, there is pair (u, ü) such that Pu.ú Pa,, 1.11 for any In+11 1, and Øn+1 ((x,+1). Namely for the continuous ball B, the canonical vectors are canonical u = [O...., 0, .,,...J 1] and
0 and ū [r, 0, 0,0,.-. For the binary Bra.r we have the
u where ||uu|lo = Ta and | fū]|o = Ta- Intuitively due to the symmetry of the ball and the smoothing distribution. To avoid many notations, again use the æ, and in the rest of the discussion that refers to the canonical points.
To obtain upper or lower bound (Eq. as maximization minimization) we partition the space X to regions where the likelihood ratio between (æ, .)) is constant; formally X' = - R, where Vz E R, Pr(g(=) z1/ Pr(g(#) z] c₁. For any function h we find an equivalent piecewise- constant h where inside each region is assigned to the expected value of in that region. Let I Pr(g(x)) = z). and i, Pr(g(m) z] then Eq. simplifies to the following linear programming
min h hTt Pa AE[0,1]
Where h, f. and are vectors that include the values h1 f,. & for each region. The optimum solution the simplified linear programming obtained by sorting regions based on the likelihood ratio and greedily assigning h to the possible maximum in each region until the budget h Tt tt= Pa is met. The rest of the regions are similarly assigned to zero. This problem is equivalent to fractional knapsack. For isotropic Gaussian smoothing Cohen et al. (2019) show that the optimal solution has closed form Pa = d (pa) r) where &. is the Gaussian CDF function of the Gaussian distribution with standard deviation greedy program on at most r. + Ta + distinct regions. The runtime is linear w.r.. to the add and delete budget. For more detailed explanation (Lee al. 2019 Bojchevski al. 2020).
For sparse smoothing, following BBochhvski et al. (2020)
solve the
14

---

Published as a conference paper at ICLR 2025
C SUPPLEMENTARY TO THEORY
C.I VANILLA BINCP
Conformal risk control. We use conformal risk control (CRC) (Angelopoulos et al. 2022) to prove the coverage guarantee in BinCP, Here we succinctly recall it before the proof of Prop. 1
Theorem 2 (Conformal Risk Control rephrased), Let X be parameter (larger À yields more conservative oulput), and Li A + (-o0, B) for = 1,..., n. + 1 be exchangeable random functions. If (i) L8 are non-increasing right-conlinoous w.r.l. X, (ii) for Amax sup A have Lg( (.maxx)) S and (iii) sup, Li I B < oc, then we have:
E [[]m+1(A)] Sa for d ==inf] { E L(A))
B n n+1
S Sa
n n+1
In case that B 1, by simplifying Eq.
we have Å = inf {) Ei L₂(A) S a(n 1) -01 1} We
use this framework to prove the guarantee in BinCP.
Proof to Prop. We prove the theorem through re- e--aarameterizing of the conservativeness variable in each case. For fixed p we set = 1 - X; similarly for fixed we set - -. In both cases, the risk is defined as
[,(T,)) U..
which for simplicity we define (e;, 9;p,7) = accept a. (a., P. and by definition we
have (aj,ct(a,,, M/5,, 7) = [[Pr[s([ e,y) < 7] p] [[Pr[s( v) 2|] <. We show that the risk function satisfies the properties for a risk function feasible to the setup in Theorem
1. Non-increasing to X. In both cases the risk L, is non-inscreasing to X; for fixed p we have
X2 = Pr|s(x + + <1 - X1] 2 Pr(s(# <1 Aa] reject(2, p. - X1) reject(æ, y; 1 - X2)
A
Now for fixed T, let Pa Pr[s(x + E, e,y) 2 -| then we have
A1 < d2 - P1 P2 means that 1pp S pı] 2 Up S Pel = reject(æ, x -1.- r) 2 reject y; 22 T)
Intuitively by adapting the definition of the rejection (risk) function reject(æ,, Vi; P, [[Pr[s(æ + c. y) r] < p). we increase which means decreasing p. the chance of rejecting a label decreases. This is because, we require the same probability mass to be lower than a smaller value.
2. Right continuous. Formally the function accept is
(ccopt(x,.:p.77) f1 if Pr[s(x+ 2 otherwise
Across the domain (for either or T) this function has two values and it is just non- continuous in the jump between the values. For both p and r this function left continuous due to the 2 comparison. Therefore for fixed the function reject V. 1 - X) is right continuous to
- T. Similar argument follows for fixed T.
3. Feasibility of risks less than a. For fixed > O if we set X = 1 to xo (T = -o)), for all T;, we have (xc, yai 0) 1; i.c. the risk for every data. Similarly by approaching to zero in fixed 7 setup, we decrease the risk to 0 for everyone. To avoid corner cases we can restrict 7 to max s(x: e, for X' from above.
4. Limited upperbound risk. For any parameter and any input the highest possible risk is in case of rejection which is (B
15

---

Published as a conference paper at ICLR 2025
Fixed p. The risk function L2(A) reject(z1, Yrip, X) which means that the prediction set C(app, X) excludes yr. We have
(1 Mnt1:p 1- s for Ả inf X
Σ (ej, 9: 1- X) a(n
Setting back the T = 1 X, and rewriting the expectation as probability form, we have
Pr(ya+1 E ((xx+1:P:TT)) 2 1-a for Tp = sup
(cc 9GP,, 7) 2 (1)
In the above, we used the fact that if a test fails on a( + 1) - variables among the total of n variables, passes on n [a(n + 1) 1] and (1 on 1) = n [a(n + -
Fixed r. Similarly, we define the risk function as (A = reject (æ,, y:: - -..)). r). We have
C[reject(xx+11. Mn r)] S for inf x
yz; reject (1; - r) a(n
==1
Proof to Lemma | The function accept( p, T) is non-increasing in both and т. Therefore the term i accept y6 p, 7) is also non-increasing in p and and its range is the integer numbers between 0 and n (or [rz)). For fixed p, let Ta (p) be the solution to LooE.. 2 then by definition it satisfies that
ac, yc: P. Ta - a) +
This implies that p satisfies the same condition for Pa (T Therefore Pa (T.()))) 2 p as i feasible solution in Eq. The supremum search for Ta (p) directly implies that for any positive 8 we have
Σ accept((r; ys: Fa (p)) accept( Mr: P, To (p)
which intuitively means that increasing the T(p) by any small margin fails at least one more accept for calibration points. Since > accept( DGP, Ta (p)) is the sum of n non-increasing functions, there is one index for which
accept( yet p. Fa (p))
and accept( yst p. Ta 5)
For any small positive 8. Using the definition of the accept function we have
Pr|s(x;; c, (p) 2 p and Pr[s(2; + v, 2 (p) + 5] <p
Due to the continuous strictly increasing CDF for St we have Pr(s(ar; + vs) 2 [ There- fore for any small positive
accept( Vs p. P. (p))
and accept(z,, MsP 5, Ta (p))
which means that the accept function for æ; fails by adding small number p. Since all other accept functions are also non-increasing we have " i-- accept(æ; Miip, (p)) S (1-1)
This implies that p is also the supremum for Dg. with parameter (T).
C.2 ROBUST BINCP
Proof to Lemma 2 With firee (xx) [[s( vi) Tal for true yi, the calibration-time robust prediction set is defined as (Tn1)) = (p( (1( W; Ta) 2 Q (a; (z)) definition we have Pa Q (a; non-decreasing. As result, the ranks, and hence the quantile index in (x and {o+ (x:)), (3))), 1 are the same. Therefore, Q (a; [ermee (æ.)), B))) ct B)
J. By Both lower bound and upper bound functions
16

---

Published as a conference paper at ICLR 2025
Ta
Ta
Td
a
P+
P+ p-
1 1- p-
p-
p-
p+
P+
ti
1 p+
x
Figure 8: Illustration of likelihood ratio in sparse smoothing for both Br..ra and Brasr
The test-time robust prediction set is defined as Crest = tu c)):c((((nn41)))) B- 2 PaJ. let Py (#) then follows
B- Pa + ct (f 13 2 ct [p., B
(wn+1) ct Pex. B]
By definition accept yi c [pa, B), Ta) = I[f c [p.
In the above, we proved that BinCP results in a valid conformal prediction. Here we prove the validity of robust BinCP to adversarial data within the bounded threat model.
Proof to Lemma 3 For each of the mentioned smoothing schemes we have:
Gaussian smoothing. both cases since p norm is symmetric for any point & it holds that || =lI, < In other words, from any perturbed point the clean point is within (æ)). Therefore
B, = B,.
For simpler notation let p = [p, B,). Given the closed from solution e- [p, B,] 2 (0- r), and c B,] = 4, _ (p) r) we have
t ( (p) +
+ (p)
2 (T)
1 (p) + C B3] =
2o
Uniform smoothing. For the uniform smoothing from Levine & Feizi 2021 we have that the smooth classifier - continuous. From that the certified lower and upper bounds c"p
defined as c B, p r 1/(2)), and c (p, B,] p 1/(2X) Therefore
ct(e"
et 2X
B, [.,
= 2A 2X =P
A similar argument can be applied to any certificate that directly adds (or subtracts) the Lipschitz constant of the smooth classifier to the base probability.
Sparse smoothing, Any ã (x) has most r. zero bits, and ra one bits toggled from By toggling those bit back we can reconstruct æ. The maximum needed toggles therefore ra zero bits and r. one bits which is the definition of Bra.sa-
As discussed in canonical points for Br... are x = =0, [0..... 0, 0.1...., and á = - a where | = Fa and || = Ta- For B-,,, the canonical points are u. u where ||u||o = Ta- u, I and every other point in all regions
By applying permutation = æ. For computing both Br..ry. and B-1 r there are r. + ra + regions of constant likelihood ratio, each including all points that have the same number of total flips from the source x, u;
ø. and
17

---

Published as a conference paper at ICLR 2025
formally R₂ f2 || =|lu 7). The same region can also defined to preserve rd Ta
bits from ã. With Ey as the likelihood ratio of a point z in Bra.ra and = qa + qu as the number 8y of changes in and bit, we have 5q (p+ )a- (1 p+) ) 1.--9 (p_ )9 y and similarly 8q (w-) ( (1 p- )ra ya (p_ ) (1 p- )d Then the likelihood ratio is simplified to
g
p+
(8)
P+
As illustrated in Fig. regions for Br are same as Br..ra only with reverse order. In other word, let 4s. & be the probability of visiting region R2 from u and ú, then 4 = 8r. +rutry+1- and 7 Sra trattrat1g For a fixed the probability visit from æ the probability of toggling q = || x llo bits which is the same as toggling bits from ú as ū = æ.
Solutions e (p, Bra.ral and c² Br.t are obtained from the following optimization functions:
Br.ral
min h s.t. h tt =p helo trattt
max h á s.t. h h-spp c¹ [p, B hejo
The solution to the lower bound optimization is obtained by greedy algorithm. We visit each in increasing order w.r.t. 51 2, we assign h, = until the budget h s is met and we set h2 = 0 for the remaining regions (fractional knapsack problem). For the maximization we do the same but in decreasing order.
We want to prove ct 'p, D,B.raall Brairel p. This is the solution to
min he[
h h s.t. h h = (1 hT
Let be the vector in reverse order. Then t 5. From the problem definition we have that h (the solution from maximization problem in reverse order) is feasible solution. Given that the solution of the optimization (reduced to fractional knapsack problem) is always in form of [L...., 1, .,....Q 0] for some d E [0, 1]. any vector of this form that satisfies the constraint is optimal. Therefore h' is the solution to the maximization greedy problem. So the optimal solution T Ts
For any Ep with the same argument & ball we have B, = B,. Similar to isotropic Gaussian smoothing, the Lipschitz continuity in DSSN-smoothed distribution shows that Lemma 3 applies to & ball and this distribution as well.
C.3 CORRECTION FOR FINITE SAMPLE MONTE-CARLO ESTIMATION
Proof to Prop. 2 With p; = Pr[s(2; + e, vR) 2 Tal as the true probability of crossing Ta for each
true score distribution in calibration set. We have Pa = O (a; (pr);-). For all i we have of S Pa from which follows p: < Pa. The probability of failure in each calibration datapoint is n/ + k); result, from the union bound the probability of failure of < P; for all i E {l,..., n} and therefore the quantile is |Deall// ([aaa + k))
For all classes of the test point we have 7 2 Putl. with // (Deeal + k). Therefore, for the true class we have qn+1 2 pn+1 with kn/([[eeal + k).
Conformal guarantee implies that with a + 7) probability we have Px+1 2 Pa. The robustness certificate implies that Pn+1 2 ct(p., B). Following holds by using the mentioned inequality:
Pnt1 2 [pa, 1 B 1-a+1
2
et c B
1-24%
From the union bound it follows that the total failure probability is less than
18

---

Published as a conference paper at ICLR 2025
CAS
BinCP
Vanilla
1.3
1.6
4
Average set size
1.5
1.2
3
1.4
1.1
1.3
2
1.2
0.00
0.02
0.04
0.06
0.00
0.02
0.04
0.06
0.00
0.02
0.04
0.06
Figure 9: Comparison between BinCP and CAS on CIFAR-10 dataset with o = 0.25 and small values r. The nominal coverage a is set [From left right] 85%, 90%, and 95%.
We estimate the probabilities in alggorithh [ffollowiggPrrgg (eroop.]directtt diirecty There, we estimate the Pr. [ra[s(;; c. vi) 2 7] via Monte Carlo samples resulting in Q: m Iss + c. vi) r]. Via Clopper Pearson bounds find 9; for which we have of S p. with adjusted 1 7) probability.
For the p-fixed approach dalgorithm 2), we compute the discrete quantile т: = Q[Pp. ml/m;; {s(æ; + e, 6.): over the randomly sampled scores. By definition of discrete quantile function, without counting again, we have [[s + c, 2 T,] 2 Pa (Pa proportion of the binary variables T[s(x; + 6, y4) 2 Ti] are 1). Now, we bound Bernoulli parameter that is the proportion of the distribution exceeding Ti. Again we use Clopper Pearson bound but this time Po which is known. Therefore after computing To we use p instead which is minimum support for all 7 set as the Pa quantile of the sampled scores (with adjusted 1 r) confidence).
D SUPPLEMENTARY DISCUSSION
D.1 HIGH-LEVEL UNDERSTANDING OF ROBUSTNESS CERTIFICATES
certificate of robustness a formal guarantee that the model predicts the same class for any perturbation within the specified threat model within the ball around the input. In other words, the function f is certified to be robust for the point æ w.r.t. B, for any arg max, fy(x) arg maxy fy (T). This certificate ensures that the top label remains the same within the threat model (binary certificate). A similar (confidence, or soft) certificate guarantees lower (and upper) bound the model confidence within the threat model given the predictive probability. One way to attain such certificates is through verifiers. Verifiers need white-box access (knowledge about the model structure and weights) and they work efficiently only limited class of models. However, our robust conformal guarantee is black-box.
B(x) we have
common approach for black-box certification through randomized smoothing. randomly smoothed classifier results from inference given the input augmented with random noise. For ex- ample ((x) Ee==N(o,==1)]f' + <)] model g returns the expected output of f given randomly augmented where the noise comes from an isotropic Gaussian distribution with scale a. The ran- domization function smooth even if the original function changes rapidly, which the effect of the expectation. It is also Lipschitz continuous, meaning that we can bound the output based on the distance of ē from æ. The latter allows us to provide formal guarantees that the top class probability (or confidence) remains high (changes slowly) even if ă B is passed to the model instead of
Ultimately a randomized smoothing- certificate returns a lower (or upper) bound probability (or score) the expected output (given the randomized æ). In robust CP we use these bounds to answer "if instead of the clean input In+1 which is already exchangeable with the calibration set, the model received the worst case øn+1 B(æn+1) how much lower the conformity score has become". Or other words the model is queried with h,-1 E B(x (which has a lower conformity score in order not be covered) how much higher the conformity score of the clean
19

---

Published as a conference paper at ICLR 2025
Hoef.
Bern.
Cl-Pr.
Certified
0.75
Lower bound
Correction Err.
0.15
Correction Err.
0.04
0.50
0.10
0.25
0.05
0.02
0.00
0.00
0.00
0.25
0.50
0.75
0.0
0.5
1.0
0.0
0.5
1.0
True p
Threshold
Threshold
Figure 10: [Left] Confidence lower bound and the corresponding certified lower bound for scores derived from Beta and Bernoulli distributions. [Middle and right] Correction error (lower bound subtracted from the theoretical mean) of the scores distributed from the Gaussian distribution both in continuous case (mean lower bound) and binarized case (lower bound on the Bernoulli parameter) for [Middle] 100 and [Right] 1000 samples. Details of the experiments are in $ D.2
input can be". Technical details of smoothing- -based certificates are mentioned in For a more
detailed discussion see (Cohen et al. 2019 Kumar et al. 2020
D.2 COMPARISON OF CONFIDENCE INTERVALS
As discussed in 5 BinCP, CAS, and RSCP, all require true probability, CDF, and mean from the distribution of scores which is intractable to compute (except in the case of de-randomized BinCP). Therefore we use confidence bounds that are lower (or higher) than the true values with collective probability v (which is taken into account while calibrating). CAS, and RSCP are defined continuous scores that are bounded by Hoeffding, Bernstein, or DKW inequalities. BinCP is defined through binarized scores, and the final parameter is the success prohability of Bernoulli distribution which can bounded by the Clopper-Pearson Pearson interval which is exact (Clopper & Pearson 1934). The width of all mentioned confidence intervals decreasing w.r.t the sample size. Therefore tighter interval can result in the same or better efficiency (correction error) with fewer samples; e.g. For scores sampled from Gaussian (0.5, 0.1) Clopper Pearson error (for 2 0.6) with 100 samples is still lower than Bernstein's 's error with 250 samples.
To illustrate this we conducted two experiments. First, to compare the tightness of each concen- tration inequality, we sampled from a Beta distribution with mean to have continuous score values between [0, 1]. The distribution for fixed 3 is Beta( (eta(sripp - 3). Then for the continuous score, we computed both Hoeffding's 's and Bernstein's 's lower bound on the mean, alongside the Clopper-Pearson bound for the given parameter and the same sample size. As shown in InlF.. 10 (with B = 1) the binary lower bound is always higher (better). Since the certified lower bound is an increasing function of the given probability, the certified lower bound for the binary values again higher.
In another experiment shown in Fig. middle and right we sample scores from a Gaussian dis- tribution (0.55, 0.1), and computed the lower-bound mean given both Hoeffding and Bernstein's 's inequalities. Then for various thresholds, we computed the probability of scores passing that thresh- old and lower bounded this probability by Clopper Pearson concentration inequality. As shown in the figure for lower sample rates, binarization results in less error compared the theoretical mean. Even with higher sample rates Clopper Pearson interval is significantly tighter than the other two for low and high thresholds (which is parameter of BinCP).
Proposition Let X Beta(a, b) and Tı,... F. be m. i.i.d. samples of X. Given the empirical
2 24 the upper bound for the true mean μ E. is given by the Hoeffding's mean ā 1. 2m
Inf b)
inequality as l T + bhoot, where bhact
For any user-specified (0, 1), let Y
20

---

Published as a conference paper at ICLR 2025
Probability of worse performance
0.2
Probubility of worse performance
0.2
100
0.2
200
0.3
250
0.1
0.5
0.1
500
0.7
1000
0.0
0.8
0.0
100
250
500
750
1000
0.2
0.4
0.6
0.8
m
T
Figure 11: Probability of observing higher upper bound from Clopper Pearson confidence interval in comparison with Hoeffding's interval. The result for Beta(2, 2), and 0.01.
[[X r]. The Clopper-Pearson upper bound Pa. for the true p E[y] Pr[X 2 is:
m
Pu = $ Beta (1
+
Tam
T], m
[mm > Tul)
i=1
Each upper bound holds with probability 1/. For any number of samples m, and any significance
level the probability that the CP bound is tighther is Pr[pu [[[{] S. bhoef] and equals:
Prip
E[Y] S bhoet]
PBnoo (m: m, E
(9)
where in is defined in Eg. 11
Proof. The variable Y is distributed as Y ~ Bernoulli()) where Y = =1 Betta(T; ar;,a,1 and Beta the CDF the beta distribution with parameters and
Let m4 >m I| r]. We will compute the probability that the inequality
ln
B|
<
(10)
2m
holds. Substituting the definition of and Y we get:
In
1 Beta (1 77; 1 + m4, m m4) - (1 D (T;O, 5
43
2mm
1 5 PBta
+ 1 - & Beta (T;a,T);;)))) + m4, - m4
4
2m
In
77 2 Beta
1 Petaa(T; b); + m4 m m4
2m
Define m the break-point after which the Clopper-Pearson bound becomes looser than the Ho- effding bound:
In
1
m sup
m4 I n 2
BBta
1
BBeta (T: + m m m4
2m
(11)
21

---

Published as a conference paper at ICLR 2025
In other words, m4 > i Po
[[EE] bhoef- Since & is monotonic, it follows that:
Pr(p-- [| bhoet] Pr[m+ m] Binom (ri:; m, B[(])
(12)
Where Diinmm is the CDF of the Binomial distribution with the specified parameters.
Similarly, we can compare Clopper-Peansee bound with the Bernstein bound we use la S I + been where
In
2
7 In
bbem
2 m
m
3(m
By replacing bhoef with beera in Prop. 3 we can derive a similar result. We choose a Beta distribu- tion simulate the fact that conformity scores such as TPS and APS are bounded. Moreover, we need bounded scores to be able to apply Hoeffding's 's inequality. Any other distribution (after some transformation that ensures bounded scores) could used, as long as we can compute its CDF.
In Fig. 11 we show the probability of Hoeffding bound being tighter than Clopper-Pearsee (it's complement is defined Eqq 12) for X Bcta(2, 2) for different values of m and т. There is choice of r such that the probability is effectively 0 for all values of m. i.e. the CP bound is always better. Interestingly. at worst, both terms of the number of samples m and т, we see that it less than 25%. That is, Clopper-Pearson bound is better average for all configurations.
bound
To get some additional intuition, instead of the exact Clopper-Pearsee bound for p we can use the following bound derived from Normal approximation which approximately holds with probability 1- ?
Zq m
p PS0+
p(1
where -= m. Ein I[rm r] and Bny is the 1 quantile of the standard normal distribution. It is not difficult to verify that for all values ğ E [0, 1] we have that
1
1
P) <
m
2m
To see this, note that the /m term cancels, and for 7) 0.05 2, 1.64,
1.22. Since
vp( - p) E 0.5). even in the worst-case 1.64 0.5 < 1.22. This analysis again confirms that CP gives tighter bounds. Prop. can be analogues extended lower bounds.
Finite sample correction for fixed 7 setup. What we showed in Propp 2 adds MC sample correction BinCP with fixed 7 computation. We can correct for finite samples in a fixed setup in a similar way. First, we compute the (p) for each of the calibration points. In an asymptomatically valid setup this implies that for (p) we have Pr[s(nx; + <, (; 2 (p)) 2 p. account for finite samples we reduce pr (p+ < p). Again this holds for each calibration with 1/([Deail k) probability, and the conformal threshold (Tp= In the test time the setup identical the fixed-7 setup.
D.3 REALISTIC SETUP TO EVALUATE GNN ROBUSTNESS
Concurrent our work Gosch et al. (2023) shows that transductive setup is flawed to evaluate GNN robustness. This is since assuming that the clean graph is accessible to the defender during training, can lead to perfect robustness by simply remembering the clean graph. Many robust- and self-training GNNs proposed for robustness also exploit this flaw.
To evaluate GNN tive setup where the clean graph is given during the training and calibration. Specifically, assume that the defender trains, and computes the calibration scores on the clean graph. Perturbations in test nodes then applied after calibration (in evasion setup). This again is based similar assumption
for robust CP, following prior works, we assumed the transduc-
22

---

Published as a conference paper at ICLR 2025
0.92
0,950
Worst-Siie Worst-Slice Cov.
0.91
0.925
Coverage
0.90
0.900
0.89
0.875
0.88
0.850
0.87
0.825
TPS
STPS Method
BinCP
TPS
STPS
BinCP T= 0.25
Method
Figure 12: Comparison of coverage [Left] and worst-slice coverage [Right]. Here the STPS refers to the smooth TPS which is the average of 2000 randomly smooth inferences per point. The results for CIFAR-10 dataset and r= 0 unless specified.
made by many other GNN robustness works. Therefore robust node-classification results only representing the comparison of BinCP and other approaches on a sparse binary certificate.
A more realistic setup the inductive setup where the defender is given clean subgraph Gir for training (and calibration), and the adversary perturbs the rest of the graph upon arrival; i.c. the defender does not know the clean test graph. In vanilla setup, the conformal guarantee still valid in the inductive setting via re-computing calibration nodes (Zargarbashi & Bojchevski (024). However in evasion, robust CP is not easily applicable by recomputing the quantile and computing upper bounds on scores, since the calibration nodes are also affected by the adversarial test nodes through the message passing. Therefore robustness GNNs under realistic setups is challenging which we leave it to future works.
E ADDITIONAL EXPERIMENTS
Various models and smoothing maginitudes (o). In Table we compare the result between SOTA CAS and BinCP for CIFAR-10 dataset. The results are reported across various data smoothing a values, and models trained with different noise augmentations (data augmented during training with different æ values). We call them smoothing a, and model a respectively. In the robustness certificate for classification, it considered best practice to use the same both model's noise augmentation, and the smoothing process. Similarly, in robust conformal prediction mismatching smoothing and model results in larger prediction Interestingly this adverse effect is much less observed in BinCP although it remains present. Overall, across all smoothing parameters, model values, coverage rates, and perturbation radii, BinCP consistently outperforms CAS.
Performance on small radii. For completeness, in Fig. we report the performance of BinCP on small values of Jeary et al. (2024) reports 4.45 average set size for 0.02 (Table 1 in (Jeary et al.] (2244) our report shows more than twice smaller sets for the same As in Table 2 we observe same average set size for ~ 0.5 (> 20x higher radius) for smallest o 0.12. As we discussed, one effect of this eye-catching difference is the inherent robustness of the randomized smooth prediction. As shown in Fig. 6 the empirical coverage of non-smooth prediction drastically decreases to 0 for small radii, while in smooth prediction the coverage decreases slowly.
APS score function. Although we observe similar comparison between CAS and BinCP given APS score function, for completeness report the performance of both methods in Table 1
Conditional and class-conditional coverage. Following Romano et al. 2020). we approximated the conditional coverage gap the worst coverage among different slices. Each slice is defined as X. (x; E D a < x; v b} for the random vector v and random scalers a, (Romano et al, 2020
For that, we sampled 200 random vectors and among all the scalers randomly sampled o,
23

---

Published as a conference paper at ICLR 2025
Table 1: Comparison of smoothing-basee robust CP methods APS
a 0.9
0.95
CAS
BinCP
CAS
BinCP
Coverage
Set Size
Coverage
Set Size
Coverage
Set Size
Coverage
Set Size
0.06
0.954
1.635
0.946
1.529
0,990
4.022
0.980
2.151
0.12
0.971
1.939
0.963
1.757
0.996
6,435
0.985
2.389
0.18
0.987
2.879
0.978
2.076
1.000
9.745
0.991
2.876
0.12
0.25
0.998
7,454
0,986
2.510
1.000
10.000
0.995
3,405
0.37
1,000
10,000
1,000
10.000
1.000
10,000
1.000
10.000
0.50
1.000
10,000
1.000
10.000
1.000
10,000
1.000
10.000
0.75
1.000
10.000
1,000
10,000
1.000
10.000
1.000
10.000
0.06
0.955
2.108
0.944
1.894
0.986
3.316
0.976
2.677
0.12
0.964
2.309
0.954
2.054
0,989
3.682
0.980
2.857
0.18
0.970
2.495
0.961
2.227
0,993
5.038
0.986
3.181
0.25
0.25
0,980
2,900
0.972
2.537
0,997
6.004
0.989
3.444
0.37
0.991
3.795
0.982
3.047
1.000
9.360
0.994
4.035
0.50
0.999
7,430
0.991
3.729
1.000
10,000
0.997
4.850
0.75
1.000
10.000
1.000
10.000
1.000
10,000
1.000
10.000
0.06
0.956
2.738
0.942
2.479
0,981
3.864
0.975
3.342
0.12
0.962
2.890
0.951
2.635
0,984
4.077
0.978
3,508
0.18
0.968
3.078
0.959
2.801
0,986
4.277
0.981
3.658
0.50
0.25
0.973
3,304
0.966
2.994
0.989
4.546
0.984
3.899
0.37
0.980
3.684
0.974
3.302
0.993
5.193
0.988
4,300
0.50
0.986
4.153
0.979
3.663
0.996
5.868
0.991
4.733
0.75
0.995
5,441
0.989
4.584
0.999
8.026
0.995
5.542
from the set {a:; v, D2 E D). We report the result over 100 different calibration samplings. In each iteration of the experiment, exclude the slices with less than 200 points of support.
BinCP has smoothing, binarization and accounting for perturbation radius. For a better intuition we observe the effect of each step separately: vanilla TPS (without smoothing) the baseline score, vanilla smooth TPS (labeled as STPS) which is an average of TPS scores over randomized sampled (same CAS), BinCP without robustness (set
which reflects the effect of binarization (we did not correct for finite sample due to validity in vanilla setup), and robust CP via BinCP. As shown in Fig 12] the smooth model has better worst-slice coverage than vanilla TPS. Though binarization although the average worst-slice coverage remains the same, there is slight decrease in the variance of this metric. Note that sampling correction and making CP robust increases the empirical coverage guarantee, therefore the worst slice coverage is increased due to the inherent increase in marginal coverage.
We also reported the result of the class-conditional coverage in Fig. 13 Empirically in almost all classes, BinCP is closer to the nominal guarantee compared to normal smoothing. Ultimately both smooth prediction and BinCP not comparable with vanilla TPS.
Comparison with RSCP+. Yan et al. (2024) shows a flaw of RSCP (Gendler et al. 2021 indicating that the score function is not corrected for finite sample estimation. They show that by adding finite sample correction to RSCP, becomes significantly inefficient and produces trivial sets C(x,+1) =
Y. They remedy that by designing barking-based transformation top of the given score function which defines a new score as
b
Sppt (2c, v) (T rank rank(s(2,, y); (s(0;, (a)
(13)
Where Drune holdout tuning index, is the temperature parameter, b is bias parameter, and a is the sigmoid function. The original experiment from Yan et al. (2024) has several issues, which we resolved and compared with (i) The scores have possible ties; i.e. two different data points have the same score value. To remedy that we added unnoticeable random number Uniform 1//Dtunel] to the scores. (ii) The tuning set and the calibration set in the exper- 5250/10000 test datapoints calibration set. This unrealistic holdout labeled set contradicts the sparse labeling assumption. In reproduction of their results used total of 380 datapoints where 200 of them for
iments significantly large. Yan al. (2024)
tuning and
24

---

Published as a conference paper at ICLR 2025
0.9
0.8
0.8
TPS
STPS
BinCP
TPS
STPS
BinCP
TPS
STPS
BiuCP
TPS
STPS
BinCP
TPS
STPS
BinCP
Figure 13: Comparison of methods in class-conditional coverage for all classes of CIFAR-10 10, note that here BinCP is used without sampling correction. That because the correction slightly increases empirical coverage which can be misleading.
1.00
RSCP+(PTT)
BinCP
BinCP(PTT)
Avg. Set Size
Coverage
0.98
7.5
0.96
5.0
0.94
2.5
0.06
0.25
0.50
0.75
0.06
0.25
0.50
0.75
Figure 14: Comparison between BinCP and RSCP+ (PPT, Eq. 13) and BinCP with Eq. 13 The result on CIFAR-10 dataset with 0.25.
BinCP still outperforms RSCP+(PPT), As the score function in Eq. 13 also a valid score, we can use BinCP on top which shows slightly better efficiency for larger radii compared to BinCP combined with TPS score. Here we set b = 1 and T = 0.001, and report the results on 2000 MC samples. The reported result is on CIFAR-10 10 dataset.
tuning. As shown in Fig. 14
25

---

Published as a conference paper at ICLR 2025
a
0.9
a
0.95
BinCP
BinCP
Model
Data
Coverage
Set Size
Coverage
Set Size
Coverage
Set Size
Coverage
Ave Set Size
0.12
0.12
0.06
0,950
1.581
0.942
1,483
0.987
3.353
0.976
2,009
0.12
0,968
18899
0.959
1.671
0.996
6.731
0,986
2.387
0.18
0.985
2.761
0.974
1.966
0.999
9.417
0,990
2,666
0.25
0.997
7.078
0.985
2.369
1.000
10.000
0.994
3.213
0.25
0.06
1.000
10.000
0.943
4,911
1.000
10.000
0.977
6,500
0.12
1,000
10.000
5.328
1.000
10.000
6,880
0.18
1,000
10.000
0,961
5.711
1,000
10,000
0,991
7.366
0.25
1,000
10.000
0.974
6.323
1.000
10,000
0.994
7.628
0.37
1,000
10.000
0.988
7.133
1.000
10.000
0.998
8.387
0.50
1,000
10.000
0.996
7.990
1.000
10.000
0.999
9.049
0.75
1,000
10.000
1,000
10.000
1,000
10.000
1,000
10,000
0.50
0.06
1,000
10,000
0,950
8.836
1,000
10.000
0.980
9,310
0.12
1,000
10.000
0.960
8.985
1,000
10.000
0.984
9,402
0.18
1,000
10.000
0.965
9.075
1.000
10.000
0.986
9,450
0.25
1,000
10.000
0.974
9.222
1.000
10.000
0,990
9.535
0.37
1,000
10.000
0.983
9.403
1.000
10.000
0.996
9,656
0.50
1,000
10.000
9.557
1,000
10.000
9,789
0.75
1,000
10.000
0.999
9.820
1,000
10.000
1.000
9.947
0.25
0.12
0.06
0.954
2,570
0.937
2.232
0.991
7.016
0.968
2.992
0.12
0.969
3.049
0.949
2.395
0.998
9.042
0.976
3.301
0.18
0.984
4.573
0.956
2.562
1.000
9.845
0.981
3.567
9,510
10.000
3.895
0.25
0.06
0.953
2.051
0,941
1.836
0.984
3.307
0,974
2,551
0.12
0.960
2.183
0.950
1.951
4.077
0.981
2.832
0.18
0.969
2.411
0.959
2.126
0.994
5.242
0.984
3.054
0.25
0.979
2,790
0.969
2.394
0.997
6.749
0.988
3,295
0.37
0.991
3.867
0.981
2.858
1.000
9,660
0.994
3,888
0.50
0.999
7,824
3,480
1.000
9,948
0.996
4.564
0.50
0.06
1,000
10.000
6.762
10.000
7,837
0.12
1,000
10.000
0.956
7.024
1.000
10.000
0.983
8.016
0.18
1,000
10.000
0.960
7,212
1.000
10.000
0.988
8.221
0.25
1,000
10.000
0.969
7.523
1.000
10.000
0.992
8.430
0.37
1,000
10.000
0.981
7.935
1.000
10.000
0.996
8.763
0.50
1,000
10.000
8.350
1,000
10.000
9,040
0.75
1,000
10.000
0.997
9.008
1.000
10.000
0.999
9.494
0.50
0.12
0.06
0.948
3.701
0.923
3,060
0.994
8.485
0.965
4.196
0.12
0.961
4,230
0.929
3.159
0,999
9,564
0,971
4,457
0.18
0.980
5,843
0.937
3,330
1.000
9,960
0,973
4,538
0.25
0.998
9.329
0.947
3.550
1.000
10.000
4.753
0.25
0.06
0.943
3.152
2.792
7.254
4.013
0.12
0,951
3,417
0.933
2.929
0.995
7,818
0,973
4.172
0.18
0.961
3.771
0.942
3.112
0.996
8.476
0,976
4,276
0.25
0.970
4.095
0.948
3.246
0.998
8,916
0.978
4,416
0.37
0.987
5.773
0.959
3.586
1.000
9.958
0.984
4,753
0.50
9.121
0.50
0.06
0.957
2.767
0.943
2.428
0.984
3,995
0.974
3.288
0.12
0.964
2,948
0.949
2.558
0.986
4.165
0.977
3,405
0.18
0.968
3,071
0.955
2.673
0.988
4.351
0,980
3.542
0.25
0.974
3,272
0.962
2.835
0.991
4,850
0,983
3,806
0.37
0,982
3.721
0.973
3.182
0.993
5.160
0,986
4.044
0.50
0.987
4.215
0.980
3.524
6.439
4.511
0.75
0.996
5.708
0.987
4.285
1.000
9.287
0.994
5,316
Table 2: Comparison of CAS and BinCP for model trained with various smoothing 0, and input data with different smoothing a. Results are for CIFAR-10 dataset.
26


Reviews:
[{"review_id": "d4PLiqTJqJ", "reviewer": "Reviewer_3Npc", "summary": "This work attempts to solve the \"robust conformal prediction\" problem, where we seek to construct conformal sets that satisfy the desired coverage guarantee at test time under worse-case distribution shift  between calibration and test data (adversarial perturbation). The baseline in this direction (RSCP) uses test-time robustness, where in contrast, this paper builds on a previous result, Zargarbashi et al., which utilizes the CDF structure of the conformity scores and constructs CDF aware sets (CAS), outperforming RSCP. This work in particular, is able to improve on CAS by manipulating the distribution of \"smoothed\" conformity scores. \nThey are able to show improvements with respect to CAS in terms of 1. length-efficiency of the prediction sets, 2.  lower Monte Carlo sampling budget and faster computation of the prediction sets compared to CAS, 3. Removing the need for boundedness assumption on the conformity scores.", "questions": "1. Can the authors elaborate on the effect of binarizing the distribution of smooth conformity scores on class-conditional coverage. The results seem very attractive in that they reducing MC-sampling budget and give smaller prediction sets, and but there are no experiments showing the effects on class-conditional coverage. (Are there any inherent limitations posed when binarizing the distribution of smooth conformity scores? i.e any information lost?)\n\n2. How does BinCP perform compared to RSCP+ ( Yan et al. 2024) which also propose a transformation of the smooth score and achieve smaller prediction set sizes than RSCP. In addition to line 467 and 51, could you address whether/how the calibration-time robustness (binCP) can be applied on top of/combined with test-time robustness (RSCP+), and if that is not the case, could you elaborate further on comparing the two methods in terms of how efficient each are in improving the size of the prediction sets, or the consistency of the improvement trends observed for each.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Attempts an important problem: uncertainty quantification with CP in the presence of adversarial perturbations. \n\n2. This paper is able to address a major limitation of the SOTA methods ( CAS and RSCP ) by reducing the Monte-Carlo sampling budget. \n\n3. The sets under RSCP/CAS are trivially large. This work is able to construct smaller prediction sets, and hence taking a step towards mitigating this sub-optimality of the current methods. \n\n4. The experiments are extensive and support the author's claims. \n\n5. The binarization of the distribution of the smooth scores is theoretically grounded.", "weaknesses": "1. This paper does not address conditional coverage guarantees, which is of high relevance.\n2. limited in the scope of attacker motives. particularly this paper only addresses the problem when the attacker seeks to reduce empirical coverage, and does not consider alternative goals.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JqN7T22PfX", "reviewer": "Reviewer_w6Hb", "summary": "The paper introduces a new algorithm for robust conformal prediction. The algorithm boils down to a combination of monte-carlo sampling + binarization that yields a new conformal score; this score can then be inverted into a prediction set (also accounting for the fact that the test $\\tilde{x}$ may be noisy). Experiments show this approach is an order of magnitude more sample efficient and substantially faster than the previous state-of-the-art.", "questions": "“when we do need sample correction, working with binary variables allows us to use tighter concentration inequalities” This statement confuses me because this is rarely true. Binary random variables generally have the _worst_ concentration properties of all bounded random variables in [0,1], not the best.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "* Empirical results are compelling in terms of runtime and sample size improvement.\n* Well written.", "weaknesses": "* Paper readability could be improved for non-experts in TCS like myself, who are not acquainted with “certificates” and with the prior work of Zargarbashi et al.\n\nThe conditioning in (1) does not seem formally correct to me. (I’m aware there are some differences in language between TCS and statistics that may be at play here.) My understanding is that $\\tilde x_{n+1} \\in \\mathcal{B}(x_{n+1})$ holds deterministically (i.e., with probability 1). So what is the point of the conditioning? Why would you ever even allow the possibility that $\\tilde x_{n+1} \\notin \\mathcal{B}(x_{n+1})$ in your threat model?\n\nTheorem 1 comes way out of the blue in terms of notation.\n\n___\n\nZagarbashi et al. reference is broken (no year)\n\n“First, we get robust coverage with only a single certificate computation, while at least one certificate per calibration (or test) point.” Typo. Also, I did not fully understand this.\n\n“also satisfy Eq. 1 (calibration-time)” is this a typo in Theorem 1?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kC5Ov1QiDb", "reviewer": "Reviewer_mZko", "summary": "The work presents a conformal prediction that further ensures adversarial robustness. This can be done by modifying the use of the conformity scores in either the calibration or prediction procedures, by the means of upper/lower bounds on particular adversarial objectives combined with inference of means (e.g. by Monte Carlo). This work further proposes that this adversarial objective should be of binary nature. By doing so they achieve tighter intervals and more efficient inference of the means (as the binary nature of the samples makes this estimation easier), and thus more efficient calibration/prediction.", "questions": "- Lines 129-131: To be totally formal, this should use $\\mathcal{B}^{-1}$, right?\n- Line 238: what is $r$?\n- Could the authors clarify lines 246-250?\n\n*Score:* the paper carries a meaningful contribution and seems reasonably solid, and thus I lean towards acceptance. However, the presentation (and possibly a couple of paragraphs) need to be fixed/improved, which keep me from giving a higher score. Should they be fixed, I would be happy to increase my score accordingly.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 4, "strengths": "The paper's contribution is solid. The proposed method has favorable theoretical properties, is widely applicable, and is empirically shown to significantly outperform previously available methods.", "weaknesses": "The paper is strong overall. Its weaknesses are, essentially:\n(i) several typos, listed below;\n(ii) some notation that needs to be made more consistent;\n(iii) a couple of minor corrections necessary; and\n(iv) a couple of confusing paragraphs.\n\nOf these, of course, (iv) is the most severe.\n\n(i) Typos:\n- Line 088: 'finnaly'\n- Line 096 and 144: the authors seem to use `\\mapsto` for the 'function declaration' notation $f : X \\to Y$; usually one uses just `\\to`. (At least I don't think I've ever seen `\\mapsto` used in this context).\n- Line 161: missing a closing bracket on the indicator.\n- Line 189: 'differ' -> 'defer'\n- Line 223: missing an article before the $\\bar{s}\\_y(x) = [\\cdots]$\n- Lines 229-234: is the lack of the $y$ subscript intentional? I understand that what is being said in that paragraph is more general, but as far as I can tell it is then applied to $f_y$ (rather than some general $f$ or other function), and the lack of the subscript made this paragraph a bit confusing. Furthermore, the following paragraphs seem to act as if $f_y$ was used here...\n- Line 236: $c^\\uparrow$, not $c^\\downarrow$\n- Line 246: 'they are just need'\n\n(ii) Notation:\n- The paper currently mixes different notations for indicators (both $\\mathbf{1}$ and $\\mathbb{I}$). Pick one and stick with it.\n- Line 238: $r$ was not properly introduced, as far as I can tell\n- It's worth noting that the authors seem to use conformity scores 'flipped': in their use, a high conformity score would correspond to a high belief that $y$ conforms to $x$, whereas in the typical literature is the opposite. This doesn't need to be changed, but deserves to be explicitly said.\n\n(iii) Minor corrections:\n- The quantile calibration for Split Conformal Prediction requires a modified quantile, not just $\\mathbb{Q}(\\alpha; \\{s\\_i\\}\\_{i=1}^n)$. You need to either include $+\\infty$ ($\\mathbb{Q}(\\alpha; \\{s\\_i\\}\\_{i=1}^n \\cup {+\\infty})$) or modify the level ($\\mathbb{Q}(\\alpha (1/n + 1); \\{s\\_i\\}\\_{i=1}^n)$ when the conformity score is the other way around, if I am not mistaken).\n- Lines 129-131: perhaps could be a bit more formal? See the questions box.\n\n(iv) Confusing paragraphs:\n- I could not understand lines 246-250 (and thus the paragraphs that follow), and question their correctness -- or at least their presentation. Nevertheless, the work does seem not hinge on this particular point, so I don't consider this major (though it should be fixed/improved!).\n- Lines 173-181 were also a bit confusing to read, but seemed reasonable. Either way, the theoretical result they are alluding to is formalized in Lemma 1, which is satisfyingly proven by Conformal Risk Control.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xMWelVqfZr", "reviewer": "Reviewer_qz9Z", "summary": "The authors proposed a robust conformal prediction scheme using binarized smooth scores via thresholding. The binarized prediction sets are computationally efficient with fewer MC samples.", "questions": "See weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The binarized conformal prediction sets are easy to compute and takes simple form. The claim is supported with numerical experiments. Discussions and comparison with previous methods are sufficient.\n\nDiscussion: The authors addressed my concerns and I updated my score.", "weaknesses": "1. It is confusing in the abstract to use specific numbers (e.g. $10^4$ and $10^2$) without any given context. What is the dataset and experiment setup?\n2. It is not clearly explained why nonbinarized robust CP require significantly more MC samples. Can the authors provide a theorem? Or if there is intuitive explanation?\n3. The authors mentioned that working with binarized variables allows using the tighter concentration inequalities and Clopper & Pearson confidence intervals. However, this is not formally defined, and it's not clear why a good concentration bound will imply lower sample size.\n4. The numerical experiments seem to suggest the method is indeed superior requiring lower MC sample size. However, the paper lacks discussion of why this occurs nor theoretical guarantees for sample size are given.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)