One Sample is Enough to Make Conformal Prediction Robust
Authors: Soroush H. Zargarbashi
Mohammad Sadegh Akhondzadeh
Aleksandar Bojchevski
Venue: NeurIPS 2025 poster ()
Keywords: Conformal Prediction
Robust Conformal Prediction
Uncertainty Quantification
Primary area: probabilistic_methods
TL;DR: Without Monte Carlo sampling and with a single augmented sample we propose a smoothing-based robust conformal prediction.

Abstract: For any black-box model, conformal prediction (CP) returns prediction *sets* guaranteed to include the true label with high adjustable probability. Robust CP (RCP) extends the guarantee to the worst case noise up to a pre-defined magnitude.
For RCP, a well-established approach is to use randomized smoothing since it is applicable to any black-box model and provides smaller sets compared to deterministic methods. However, smoothing-based robustness requires many model forward passes per each input which is computationally expensive.
We show that conformal prediction attains some robustness even with *a single forward pass on a randomly perturbed input*. Using any binary certificate we propose a single sample robust CP (RCP1). Our approach returns robust sets with smaller average set size compared to SOTA methods which use many (e.g. $\sim 100$) passes per input. 
Our key insight is to certify the conformal procedure itself rather than individual conformity scores. Our approach is agnostic to the task (classification and regression).  We further extend our approach to smoothing-based robust conformal risk control.

One Sample is Enough to Make Conformal Prediction Robust
Soroush H. Zargarbashi' Mohammad Sadegh Akhondzadeh Aleksandar Bojchevski² CISPA Helmholtz Center for Information Security, 2 University of Cologne [zargarbashi, akhondzadeh, bojchevski] @cs. mni-koeln.co de
Abstract
For any black-box model, conformal prediction (CP) returns prediction sets guar- anteed to include the true label with high adjustable probability. Robust CP (RCP) extends the guarantee the worst case noise up to pre-defined magnitude. For RCP, a well-established approach is to use randomized smoothing since it is appli- cable to any black-box model and provides smaller sets compared to deterministic methods. However, smoothing- passes per each input which is computationally expensive. We show that conformal prediction attains some robustness even with single forward pass a randomly perturbed input. Using any binary certificate we propose a single sample robust CP (RCP1). Our approach returns robust sets with smaller average set size compared to SOTA methods which use many (e.g. ~ 100) passes per input. Our key insight to certify the conformal procedure itself rather than individual conformity scores. Our approach is agnostic to the task (classification and regression). We further extend our approach to smoothing- based robust conformal risk control.
robustness requires many model forward
Introduction
Modern neural networks return uncalibrated probability estimates [14), and other uncertainty quan- tification methods (like Bayesian and ensemble models, Monte-Carlo dropout) are computationally expensive. Additionally, these methods do not usually provide formal statistical guarantees. Instead, conformal prediction (CP) is a post-processing method returning prediction sets with distribution- free and model-agnostie coverage guarantee, ensuring that the answer in the with an adjustable high probability. To apply CP, we need a conformity score function s(x, y) capturing the agreement between œ, and y (e.g. softmax). We compute conformal threshold over holdout set of calibration points, and for the test points, we form the set as all labels with scores exceeding that threshold. These sets are guaranteed to include (cover) the true label with a probability 21.
As shown in Fig. left (the red dashed line), this guarantee breaks by an unnoticeably small natural or adversarial noise the test points the empirical coverage drastically decreases by imperceptible perturbation. Note that from this point forward, we call adversarial or natural noises as "perturbations" be confused with the noise we the defender) introduce on purpose. Robust CP (RCP) extends this guarantee to worst case bounded perturbations, ensuring that the perturbed input E is covered with the same or higher probability the clean æ, if perturbed up to known magnitude (e.g. | | --xlly < r). Previous RCP approaches find the highest/lowest possible conformity score within the perturbation ball, and replace the score with the worst-case bound[12 16] 26 27). These bounds can be computed either analytically (Lipschitz bound or verifiers) or through randomized smoothing. Here, the trade-off is between the computational cost and the guaranteed robust radius analytical methods are robust to very smaller magnitudes of perturbation, while they only require single forward pass
Many works define CP via non-conformity (disagrcement) score. The setups equivalent with change the score's sign. Our robustness results are invariant this definition.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

RCP1
BinCP
10
$ Cr
Average Ser Size
g Co
Coverage
C,
10
ResNet
0.5
E Co
ViT
Vanilla
y
Co
10'
Ce
0.0
0.0
0.2
0.4
10
10
10
Unit Time (ms)
Figure 1: [[eft]] Coverage of vanilla CP, our robust RCP1, and the SOTA BinCP under adversarial attack ( B). C, denotes sets with robustness guarantee up to radius r, and Co guaranteed only for clean points but still using same process only with r O. Even sets from Co show significantly higher coverage compared to vanilla due to randomization. [Middle] The average time to compute, and the average set size for both RCPI and BinCP, with ResNet and ViT models on the ImageNet dataset; both axis are log-scaled and pareto-optimal points are at the lower-left. RCP1 is more efficient. Both plots with 0.5. [Right] Smoothing based robust conformal risk control. We show the coverage and miscoverage of the RCP1 mask for the class "car" in the segmentation task. Here risk is set to false negative rate.
per input. In contrast, while randomized smoothing needs many model forwards per single input, provides robustness to significantly larger radii, and it applies over any black-box model.
Smoothing is to augment the input with random noise and inference from the distribution of the model's 's output over smooth inputs instead. For example, consider adding isotropic Gaussian noise (O, o² I) the input æ, and defining the smooth score as the mean of the distribution [s[s( + e, y)]. Regardless of the original model, the smooth model changes slowly near as the two distribution x + e, and + have large overlap. This leads to model-agnostic upper bounds on the score, around æ. The upper bound is then used to decide whether label is added to the prediction set. An important drawback here the computational overhead. The score function (e.g. the expectation of the smooth scores) must be estimated via Monte-Carlo sampling. By reducing the number of samples, the confidence intervals for the mean widen, and the size of the prediction sets quickly increases.
We answer this question: Can we design smoothing- based RCP without introducing computational overhead? Interestingly, we show the vanilla CP combined with noise-augmento inference already has robust behavior (green dashed line in Fig. HHeft). With that, we define RCP1 (robust gonformal prediction with one sample) that returns robust sets using single inference per point. In practice, the resulting sets have the same guarantee, and similar size, to the previous SOTA which needs around 100 samples per input instead. By nullifying the need for sampling, we can use even larger models (like vision transformers) to return even smaller sets (see Fig. mmiddlle. Importantly, we do not compete with the SOTA equipped with unlimited sampling (compute) budget. Instead, propose a compute- compute-friendly friendly alternative that still produces small prediction sets in regimes infeasible for the other smoothing- maase based RCP methods (large models and limited computational power).
RCP1 is similar to vanilla CP only with two changes: (i) we use noise- ausimeeee input (from the smoothing) to compute the scores, and (ii) we calibrate with conservative - a' nominal coverage chosen such that our certified lower bound (in 3) remains above a. RCP1 works with any binary certificate (see 3.1.. is agnostic to the model, the distribution of inputs, and score function, and interestingly. it is task independent - same binary certificate works for both classification, or regression. We use similar process to define a smoothing-basee conformal risk control (Fig. right).
2 Background
CP requires a holdout set of labeled calibration points D,, (2;; V/ 1L that are exchangeable with the future test point F From the model's 's output, we define a score function X' x y + IR where it quantifies the agreement between æ, and y, e.g. softmax; see C for other scores. Vovk et al.

---

22
show that under exchangeability (vanilla setup) the set Co(#x+1) = {y: s(#n+1, v) 2 q) for
q
(a: {s(z, Mi) (z), Vz) Dn}) contains the true label Mh411 at least with 1 - a probability.
Pr [M++1 E Co(xn41)] Pr [s(xn+ Mo+1) 2 dl 2 a Du-1
(1)
Dotl
Here Du+1 = Dr, (2 1. and Q Aa) is the (1-1)) 11) quantile the set A. While the coverage guarantee is agnostic to the model (and the score), better model score functions reflects in properties like the prediction set size ( (a.kaa efficiency). While methods like [27] require bounded score, our results are also agnostic the choice of the score function (bounded unbounded).
Threat model. We consider the worst case (or adversarial) perturbation, which yields a more powerful guarantee compared to probabilistic robustness c.g. from Ghosh et al. [13. In our threat model, the adversary aims to decrease the empirical coverage below the guaranteed 1 --a a by adding an imperceptible noise to the test points (evasion). The set of all possible perturbations is defined
ball B: + 2 around the clean input. We define an inverted ball B-1 as the smallest set that contains the original (clean) point from any possible perturbation; i.e. V/z B (z)) =
(3-1(a) (ā)) For images, a common threat model is 22 fn-nom: B, (z) = { [ x 22 S r} where r is the radius of the perturbation. For symmetric balls like & we have B 1--1, but this does not hold in general (e.g. (5)).
B
Robust Conformal Prediction (RCP), Robust CP extends the guarantee in Eq. to the worst case noise. For B, prior works define a robust (conservative) prediction set CB satisfying the following
Pr Un+1 E Cs( vēn+1 E B(xn+11) 2 1-a Du+1
Eq. 2 is only meaningful for deterministic sets. We discuss this subtle point in $ and S D. Earlier smoothing-based RCP methods implicitly remove all inherent randomness, which makes the definition applicable to them. These methods can be summarized with the following two arguments: (i) for the exchangeable x CP covers the true label with a probability, (ii) the clean xn+1 I was originally covered by (vanilla) CP, robust CP also covers Tn+ I, because if a clean score is above q its upper bound (over any perturbed input) is also above q 26). Thus, the vanilla set for # is subset of the robust set for 2n+1. This results in robust coverage of at least 1 - a. To account for the inherent randomness in CP, in $ 3 we redefine the threat model, and replace the argument (ii) by the following: "the perturbed x,, has a higher probability to be in the robust prediction set compared to 1 being in the vanilla set". The new formulation still addresses the worst-case perturbation.
Certified bounds. For any function f and ball (xx) define the certified lower bound as ct [f. x. B) S inf( = E }. and similarly e [[ as the upper bound (with sup). With this definition, for each æ we have Vä E B(xr), c+) [s(: y), ar; B] S s( y) S c² [s( y), æx, B] where we plug in the score function for f. Zargarbashi et al. (27 show that given these certified bounds within B, the conservative sets defined either as C5(# = (v [f(s(- (s(())++1)) 1: B-1)
[] 2 q) (test-time RCP),
or similarly, (3( = {y= s(#x+1, 2 Φ for q = Q (a; [c+[s( (.). x; B] : (Z. 9:) E P.J) (calibration-time RCP) attain - robust coverage.
Randomized smoothing. One approach to compute these upper/lower bounds for any black-box model, or score is randomized smoothing. A smoothing scheme { X' + X' adds a random noise to the input- maps it random point close to it. A common smoothing for continuous data (e.g. images) is the Gaussian smoothing {(x) = x + e where e is an isotropic Gaussian noise e ~ (O0 o²1 I).. While our method works for any smoothing, for easier notation we further
instead of {(x))
For any score function s, the distribution of the smooth scores s(x y) changes slowly. This enables us to compute tight bounds on the smooth statistics (mean, quantile, etc.) within B, or B-1, RSCP 12 224, and CAS (27 set the score function directly to the mean of the distribution. BinCP (26). uses the p-quantile instead. These statistics are often intractable to compute and therefore estimated using Monte- Carlo sampling, followed by a finite sample correction. RCP1 however nullifies the need to estimate these statistics. We discuss the related work further in A
3 RCP1: Robust CP with One Sample
High level view. We prove that when the scores are computed on noise-augmented inputs, i.e. using s(æ:++,,) y) instead of sa y) for both calibration and prediction (see/Alg. 1), vanilla CP already yields robust prediction sets and its coverage under perturbation can be bounded. We provide sketch of
3

---

Prob, of covering clean point A- Prips 6 6/au + e))
Algorithm 1. RCPI; the colored part shows the difference with vanilla CP.
expectution
Require: Calibration set 2,, { V: ) M nomi-
Prob. of covering pertured point
nal coverage 1 - a E (0, 1): score
A Pila. C(R; <]]
I: potentially perturbed test point 0x+1
1: Compute + s(z, w1) (æ,, Ms) E D.
Covered
TV
1V
1V 18,,
8)
Set 1
c
B-1 p.g. Gaussian
Uncovered
2 c1 a. expectation
smoothing with B, 2. ( (--- -0) +r).
3: Set q.. = Q (a {s+)=.).
Figure 2: Illustration of the theory behind RCP1. The probabilities 3, never need be computed, since due to the convexity of ct we can directly work with 1 a. Further description in
4: For input #x+1 return
(+ (y s( -e e,y) 2 ta)
arguments. To prove it we first assume abstract value 8 the coverage probability of specific clean point #n+11 which over the random noise and the inherent randomness the score. With 3p+1 as the coverage probability for _n (again over augmented input) we show that 8 be lower bounded using the randomized smoothing certificates. By showing the convexity of the certificate w.r.t. Ba+1, we can directly lower bound the expected coverage over all inputs which is
1 1- 1-a. a. We never need to compute the abstract B or Bn+1. This sketch is illustrated in Fig.
fraction of test points, all øn+1 must be deterministically covered, including the clean Ix+1- However, many CP methods (like APS (2)) incorporate internal stochasticity (e.g. break ties), making the coverage event random variable rather than a binary indicator. This is true even before we add our noise on top. Hence, Eq. does reduce Eq. 1 for O. For random sets, adversary can reduce the coverage probability for each In+1- With u encoding all the (inherent) randomness in the sets, Co as the vanilla set, and C. the robust set for ball B,,, rewrite the guarantee
Limitation of Eq. 2] The universal quantifier in Eg. 2 implies that for
Pr min
Pr[ye+1 E C, (Zn+ 2
Pr Wa+1 E Co( w)] 2 Dut1.a
(3)
Do-1 2. (.
General worst-case guarantee. We prove the lower bound coverage guarantee in RCPI, as imple- mented in Alg. We state the result in terms of random variables, which have a specific realization [n [n++1 1] be n + 1 exchangeable random variables, where Z; (X,, Y,) for X, X (e.g. X Rd,, and Y; E y (e.g. y [K]). Let X ) RR be any measurable score function. Let E, : E 11] be i.i.d. random variables from a distribution supported on X' (e.g. E, ~ N/0, T)). We define S; s(X,, Y,), and S; = s(X, E,, Yi). Let 5 E B, be any arbitrary pertur- bation up radius define X.+1 = X,+1 + 5, and 5a+1 s(X + E Yn+1) accordingly. Proposition 1. Let q = Q (a: s X; + E,, Y)): (X,, Y2) E 1) Given a certified lower bound c Bi as later defined in Eq. and En+1 = EE un+1 . for any perturbation E B, we have
in practice. Let 2,
Pr D 1.
[s( (( + E Yn+1) 2 ql 2 et[1 c
Proof. Adding i.i.d. noise E, is permutation equivariant, thus using S, Ss doesn't break exchangeability 2 From Vovk et al. [22) we have Pr[Sn+1 2 g) > 1 a for = @ (a: {5.}
(..,,,). 1), where the
probability over Da+1. and Ent1. We can rewrite this
Pr [S.41 2 9) ED Dn+1.8441
Pr [Sa+1 q) En En ED,,,.E, [8 2 Ent1
where we define Bn+1: Pre. [S 2 q Dr+1, En Here, Pn41 is only probability over the last noise Ex+1 (and any other internal randomness in the score) for a fixed D and &,. We call Ba+1 the clean instance-wise coverage. Similarly for X we define Bn+I.
We can bound any smooth binary function with an existing certified lower bound ct B). Formally,
Pr [S Ent1
Dr+1, En] = Bu+1
Pr 1Sn41 2 q Dn+1, En] 2 et (d1Bt B] Ent1

---

Note that here both Bx+1 and Bu+1 share the same Dn-1, and En, and both are over the random variable En+1 and the inherent randomness of the score. Later in Lemma I we show that the function
ct [8, B) is convex and increasing in 3. This helps us to bound the adversarial coverage guarantee as
Pr|Xx+1 E c(Xx+1)) = Pr[Sn+1 2 q] ED,,1
Pr [3++1]]
Eg-1
(from certificate) 2 ED. [c Ba+1, 1,+1,B]] BB [3, =]] 2 ct [B[S), 2 ct [Ep,, e [a+1] B) 2
(from convexity Lemma
e+(1 a, B
where the last inequity holds due to vanilla CP and monotonicity.
Just like with any other CP with any kind of randomness in the score (e.g. APS), the guarantee only holds marginally over Ex+1 and the internal randomness. In other words, the coverage probability is higher than c+ (+ B] for specific X and c+[1
B] on average, if we draw random +n+1- we instead fixed en+1 and the adversary knows the noise, the guarantee can easily break. Note that 8n-1 is abstract quantity, the probability that Xn+1 En+1 is covered. In principle we can not estimate Sn+1. since the label is not known. Nonetheless, due to the convexity, we can lower bound the coverage guarantee directly without that information.
Instance-wise worst case coverage. Prop. I relies on lower bounding the worst-case (adversarial) Ba+1 = Pre.+1 [s@n+1 + 6n+1, 2 4). for the perturbed La41 = In+1 + 8 (xx,+1) given 3,+1 == Pre,. [s( 1, 2 v]- Here, 1In+11,u++)) and 6n+1 are realiza- tions of (X++1, Yu+1) and Pn+1. This is conditional to q: and hence to Dn and & Formally, we define a binary classifier, [(2 T[s(2, Un+1) 2 q] and g(2) = Be.., [f(2 + cn+1)] for which we have Ba+1 9(Ex+1). Note that X' is convex subset of Rd and the score s(., v) is continuous everywhere, therefore our classifier is measurable [19]. We can lower bound B,+1 = (binary) classification certificates, c.g. Cohen al. 77.
g(mm+1) and therefore g (()x+1) for the given In+1 using the existing
Certified lower bound B. A smoothing binary certificate computes the bound (+ En+11 B3] re- gardless of the original definition of f mechanics of the score function or model - and only as a func- tion of the value 9 g(x,,+)) ). We the [3, B3] notation, following Zargarbashi and Bojchevski [26] For the known 2n-11, a (pointwise) certified lower bound on g(Tn++) :in+1 E (())+1)) is
obtained by searching for the worst measurable binary function h X - {0, in H (set of all
measurable functions) such that h has the same smooth output as f 2,+1- Formally:
c² [8, 13] = min Pr[h(E + c) = s.t. Pr|h(t + c) 1] E. (g NCH
(4)
The pair (t, E) are called canonical points. Cohen et 77.. Yang al. 25 discuss this in detail. Intuitively, the optimization in Eq. iss translation (and in some cases rotation) invariant, and with the symmetries in the ball and the smoothing scheme, for any æ, and we can use a fixed set of canonical points. For Ep balls, and symmetric additive smoothing (including isotropic Gaussian noise) these points are one at the center, and the other at the edge (or vertex) of the ball; i.e. t [0, o...,....., 0). and [r. ......0 0). For a detailed discussion also see section D.1 from Zargarbashi and Bojehevski [26] Since the function f itself is feasible solution to Eq. 4 it is valid lower bound for g(#x+1).
The mean-constrained binary certificate in Eq. 4 is common problem in the randomized smoothing literature. It is efficiently solvable and in many cases has a closed form solution. For the isotopic
Gaussian smoothing with &g (and { ball the lower bound is 3 = 2 (+= (3) r) where 4, is the
CDF of the Gaussian distribution (O, σ) 17.. Using the recipe from Yang et al. (25 3.1 we discuss how to compute ct [p, B3] for other smoothing schemes.
Lemma 1. [3, B] the solution to Eg. 4 is convex and monotonically increasing w.r.t. B.
We defer the proofs to S D.2 There we rigorously prove Lemma directly from the definition of Eq. via duality. Here we provide a sketch of an alternative proof that is insightful. Lee et al. [8] show that to solve Eq. 4. the space X' can be divided (finite or infinite) regions of constant likelihood ratio Pi|==tte = c. }. If we can sort these regions in descending order w.r.t ct the problem reduces to the following linear program which is fractional knapsack problem:
R. {z Pr[z-ttr]
(3, B3]
min TT q S.L. h p , he(0.11
5

---

where T is number or regions, h2 is the average value of h(z) inside the region R2 Pt = Pr(t + R2]. 9: Pr(t + E R2], and the vectors h. P, q gather all 3e, Pt. 's (see Lee et al. [8] for the derivation). W.I.o.g assume that the p. and q are sorted decreasingly w.r.. ct. The optimal solution is h" = [ l....... m. ...... 0], for some m E (0. 1) which is to fill regions in order up to when h reaches B. Each index of h' is one region being filled and by setting h; = the h q. and h p increase by 4t, and pt. Therefore [ B h" q is a continuous piecewise linear function with slope of qt/pt which is increasing across regions. A piecewise linear function with an increasing slope in each piece is convex. This convexity directly helps us to bound [[c+ B3] 2 c c+[[))
Note that in Prop. I] the guarantee is over the coverage probability and independent of the setup; therefore, without any change, one can use it to make conformal regression robust. Regardless of the downstream task the certificate is always for binary classification. Furthermore, the result is not restricted to a specific scheme and can be used for any smoothing and perturbation ball (see 3.1p.
Coverage distribution. The expected coverage probability is itself a random variable with expectation higher than 1-a. a. Under mild assumptions, Pr[Sn+1 2 q D,. ~ Beta((1-a)-(n- That is, for any given fixed calibration set, the coverage fluctuates around 1 a-a, with variance inversely proportional to the size of the calibration set. Since in practice we only have one calibration set, understanding this distribution, and its variance, is important. While we do not know the distribution of the robust coverage. we can compute a conservative estimate by convolving the CDF of Beta and the function ct B3] (see Fig. 3 left). Similarly, convexity helps to bound the mean of this new distribution as shown in Prop. I Note, our method does not take into account the distribution of the scores or inputs (unlike BinCP (26)) and as a result it is very conservative. In Fig. 3-middle we show comparison of our guaranteed lower-bound coverage and the empirical coverage under adversarial attack, highlighting that our guarantee accounts for significantly more damage.
a(n+1)) (2].
Maintaining 1 a coverage. Prop. 1 says that under perturbation, the coverage guarantee of CP calibrated with 1 - a over augmented inference decreases at most by ct - a, BJ. A simple
solution to attain
a robust coverage to set the nominal coverage to a value 1 a' such that
c11- a', [3] 2 a. In general, we can find 1 - a' using binary search, however, from (26] we know that in smoothing schemes like Gaussian, we have ct [c+[pp [p. B), B
1 = p (see $ D.3 Lemma 2
Therefore, to attain 1 1- a robust coverage, we only need to set the threshold as the c a, B quantile of the calibration scores (see Fig. right..
3.1 Robust Conformal Sets with Randomized Smoothing of All Shapes and Sizes
Both RCP1, and BinCP work with any smoothing and ball B. However, some binary certificates are given a robust radius r* the radius up to which the prediction remains the same, i.e. at (p. B,-] = 0.5. Yang et al. 25 provide a recipe to compute the r" for general lp certificate under additive randomized smoothing. We tweak their "differential" method to derive probability bounds. in a notation close to (25] and far from our own, however the takeaway is simple: in short define (p) such that 1/s((p) encodes the minimum perturbation to make infinitesimal in- crease in the worst case classifier with expected value B. We use line integral to find the cf for the worst
We phrase/Prry
20
1.0
Clean
Worst
Coverage
Density
0.8
0.8
Gaussian
0.7
Emp.
Laplace
5
0.6
Theo.
1
0
0.6
0.8 Coverage
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Figure 3: [Left] Samples from the Beta distribution of clean coverage, and worst-case coverage. The dashed line the empirical average, and the overlapping solid line is ct a, B). [Middle] The empirical, and theoretical worst-case coverage. [Right] The robust 1 - a' for two smoothing schemes.

---

case classifier at radius r; formally sup S3 (i dp We can find this supremum either ana- lytically (see $ D.4) or via binary search using the existing closed forms provided by Yang et al. [25]. Proposition 2. For a binary classifier f(x), and an additive smoothing function E, Let U = { f(x) = 1] be the decision boundary and U - z as the same set translated by -2, such that goes to the origin. Let E(U)) = PTenglE ( E EU] be the expectation of the decision boundary under smoothing. and B E(U x) = Elf(x + +c)]. Define:
E(U - ((u)- -p
(pp))
sup 6:||6||=
sup [ER-=
lim r-0
Assuming s1p) is strictly positive p E
B, and defining F(7) = =sy²
1 dp: 1)
c²13, B,] = sup {3" F(8)) 2 F(3) -
(5)
Similarly, we have (+3 B3) = inf {3' F(8) - F(3) +r).
3.2 Extension to Conformal Risk Control
We use robustness certificates to define smoothing- robust risk control for the first time. Let (x(-) be a conformal set, where S Amax controls the set size. For a risk function L( yei A) E [a, b) that is right-continuous and non-increasing w.r.t. X, if L(x,, Voi Amax) a, Angelopoulos et al. []] show:
ED [L(x 9a A²]] S for X =nf E [(x;, ys: A) + b
S a}
Here a [a, b] is any user adjusted risk level. Similar conformal prediction, we can also define a randomly augmented risk function L(x; + 6;, Mz; A). The noise does not break the exchangeability and therefore [x + 6x+1, 1: x*]] S a for the X computed on the randomly augmented calibration set. Due to the continuous nature of the risk function, we now use confidence certificates:
c3 B) = max [[)(@+++)) NEH
s.l. B[h((nn+1)) ) S B
Here h X' + [0. 1]. Similarly, Eq. can be efficiently solved, and for the Gaussian distribution it has a closed form solution of b- 4 ( +r) a(1 4 ( + +r). With (a, bj = [0, 1]
(e.g. for the false negative rate risk) the closed form is identical to the classification certificate 17
4 Experiments
Metries and Baseline. We evaluate average set size (lower better), and empirical coverage (exceed- ing 1 - average). Note that in RCPs the empirical coverage conservatively exceeds 1 by in- creasing r. Under perturbation this decreases at worst to 1-a. As BinCP [26) outperforms other robust CP approaches 271, set it as main comparison bascline. All recent smoothing- based RCPs return non-informative sets (C(x) = y) for low number of samples (e.g. < 32). Note that our main contribution is return efficient sets with inference per input; therefore we do not expect RCP1 to outperform BinCP for a large sample-rate. Our reported results are over 100 iterations with calibration set randomly sampled from the data. Further details are in
E and the code is in our GitHub
Since we certify the coverage guarantee (instead of scores), we can use the same binary certificate for both classification and regression tasks. We discuss the classification here, and defer the regression task to $ E The algorithm remains the same, only for the regression we use the absolute distance from the ground truth as the score. To the best of our knowledge, this is the first conformal regression certificate based on randomized smoothing.
Classification. We compare methods for the CIFAR10, and ImageNet datasets. We have two inference pipelines The original pipeline from BinCP, and CAS (computationally cheap setup): we use the ResNet models trained with noise augmentation from Cohen et al. [7]. Because of the model size, large sample-rates, although inefficient, are not unrealistic. We also evaluate on an alternative more expensive pipeline outlined by Carlini et al. 6 the input is first denoised by diffusion model and then classified by a vision transformer. For CIFAR-10 10 we combine a 50M- -0r-paraeeter diffusion model from Dhariwal and Nichol 9 with ViT-B/16 from Dosovitskiy et al. [00], pretrained
7

---

RCPI
BinCP-64
BinCP-128
BinCP-256
5
10
0.99
32
Sample Rate
50
Coverage
60
64
80
90
70
128
0
100
150
256
-2
0.97
0.6
0.8
0.06
0.12
0.18
0.25
0.37
00.
0.75
0.06
0.12
0.18
0.25
0.37
0..
0.75
Proportion
Figure 4: [Left] Proportion, and coverage of the prediction sets with & 5, and < 10 elements for the ViT model. [Middle] [C,,BinCP| - [C,,R for the CIFAR-10 dataset with a ResNet model. [Right] ImageNet dataset and ViT models (r = 0.25). In all plots 0.5 and RCPI uses single sample.
BinCP-64
BinCP-128
BinCP-256
RCPI
RCPI-VIT
10a
Empirical Coverage
1.000
0.8
Averag Set Size
0.975
0.6
10a
0.950
VI
0.4
0.925
0.2
10'
0.900
0.0
0.06
0.25
0.50
0.75
0.06
0.25
0.50
0.75
0.06
0.25
0.50
0.75
Figure 5: On ImageNet, cheap setup with o 0.5: [Left] Compares the average set size of BinCP with various sample rates RCP1. [Middle] the empirical coverage. [Right] proportion prediction sets with size less than 5 elements. Dashed line is the result of the ViT model with the same σ.
ImageNet 224 224 resolution and finetuned CIFARIO with 97.9% accuracy for the
HuggingFace implementation. For ImageNet we use a 552M-parameter class-unconditional diffusion model followed by BETT-L model (305M parameters) from Bao et al. B achieving 88.6% top-1 validation accuracy. We use the implementation provided by the timm library 23
Smaller set sizes. Increasing the sample-rate (number of model forwards) in BinCP decreases the set size. Fig. m-iddlee compares the set size and computation time for BinCP and RCP1 on the ImageNet dataset. Here, RCP1 shows similar set size BinCP with 64 to 128 inferences per point. We also compare set size per radii for CIFAR- 10 in Fig. 7, and for ImageNet in Fig. 5 A single inference the larger pipeline (diffusion and ViT) for RCP1 takes significantly less time compared to the cheaper pipeline with enough samples for BinCP. Therefore we can easily achieve a considerably better set size with unnoticeably more computation only by using better model. In Fig. middle, and right we compare BinCP and RCP1 in set size per sample rate (for BinCP) and radius for the CIFAR-10 10 and ImageNet datasets. Our complete comparison significantly inefficient to run 2 100 forwards passes per image on the ViT models. Additionally, use the results 3.1 to show that the method works similarly for any smoothing scheme and threat model. For that we show the performance of BinCP (under two sample rates) and RCP1 for the & ball under uniform smoothing distribution in Fig. riight.
this experiment in S E Note that
For a dataset like ImageNet (with 1000 classes), the average set size alone not a measure of usability. Consider CP returning 50% singleton sets and } for the rest, compared to CP returning sets of size 100 for all inputs. Surely, the latter option not usable even though it has smaller average set size. Hence, Fig. right (also see $ E). This metric is only trustworthy if the we don't sacrifice the coverage in smaller sets. Fig. left show that these sets have coverage larger than
also report the proportion of the prediction sets with less than 5 elements in
Small radii. Jeary et [66, and Massena et al. [19 propose RCP using verifiers and Lipschitz constant of the network. Although their result is for one order of magnitude smaller radii (c.g. 0.02

---

RCPI
BinCP
0.12
0.06
10.0
Average Set Size
Average Set Size
BinCP-60
2.5
lip-rep VRCP-I VRCP-C
BinCP-100
2.5
0.02
0.04
0.06
0.02
0.04
0.06
0.00
0.12
0.25
0.50
Figure 6: Performance on smaller radii in comparison with non-smoothing RCPs 16 19 for CIFAR- 10 and VIT model. [Left] a 0.9, and [Middle] 1 a 0.95. Smoothing is better. [Right] Performance of the methods for a Uniform-ly certificate for e Uniform[-1// 111//3//////////// 1/v3..
BinCP-60
BinCP-80
BinCP-100
BinCP-150
RCPI
RCPI-VIT
1.000
1.00
Empirical Coverage
Average Set Size
8
0.975
0.75
6
0.950
VI
0.50
0.925
0.25
2
0.900
0.00
0.06
0.25
0.50
0.75
0.06
0.25
0.50
0.75
0.06
0.25
0.50
0.75
Figure 7: On CIFAR-10, ResNet model with a = 0.5: [Left] The average set size compared to BinCP (with various sample rates), RCP1 [Middle] the empirical coverage. and [Right] proportion of sets with less than labels. Dashed line shows the ViT model (with a = 0.25).
instead of 0.25), their methods are efficient by using one forward per input. With RCP1 being the same in that metric, compare with them in Fig. left and middle reporting performance smaller radii. Aside better performance, RCP1 has a black-box access and works for any model. Intuitively, shown in Fig. 1 left, smooth (or augmented) inference is significantly more robust perturbations.
Time-comparison. With fcert. and t as the time for computing bounds, and for the model's 's inference time, other smoothing based RCPs at best require O D, x xt, teett) for calibration where Amo the number of MC samples. For each test point they also require ( x <ty) time. RCPI takes the same time the normal model's inference plus additional (fceert for calibration. Similarly, RCP1 takes Due less memory compared to other smoothing RCPs. We show the runtime of the ViT pipeline for the used datasets in Table Note that this only the time compute logits the other processes (including certificates) are negligiable compared to it. The runtime of BinCP with sample rate com- parable RCP1 is significantly high for large models like ViT; for instance, RCPI and comparable BinCP (with 128 samples on ImageNet) need ~2 466", 66", and 5h 55' to process 5000 images.
Robust conformal risk control. We use the model from Fischer et al. ||I the CityScapes dataset 8 which is a scene segmentation task. We mask the regions where a target class (c.g. car) might be present. The error function is the false negative ratio (FNR) the portion of the pixels from the
Table 1: Estimated runtimes (in SS: for 1000 inputs using H- 100 GPU. Results scaled from a full experimental run assuming a linear cost in both the number of inputs and samples.
Pipeline Dataset
Sample
64 Samples
128 Samples
256 Samples
CIFAR-10
0:00:01
0:01:09
0:02:19
0:04:39
VIT
ImageNet
0:00:33
0:35:30
1:11:00
2:22:01

---

Robust Fuil
Smooth Fail
Robust
Smooth
Truc
Figure 8: Performance of vanilla and robust risk control. From lighter to darker the colors robust region, vanilla (non-robust) region, and the ground truth region. Here a = 0.25, and r = 0.06.
Set Size
10
0.5
0.12
0.25
10
0.0
1.0
Set Size
41
1
5
0.5
0.12
0.25
10
0.0
Figure 9: Randomness in set sizes for a CIFAR-10 dataset and ResNet model. The æ-axis sorts datapoints in a fixed order (same across all plots), and the y axis shows the set size. The intensity of pixels shows the probability of a specific set size for that point over e. [Top] shows RCPl, and [Bottom] BinCP (150 samples). RCPI has larger variance compared BinCP.
target class that is not masked. We take the exp(f(x)), the score of the class and we set the mask as I[exp(f(z)), 2 A]. Note that here the classes could possibly overlap. We calibrate by finding À that results in FNR loss less than the user adjusted tolerable risk. So far, this is the first result for smoothing -rase based robust conformal risk control. Similar to RCPI, we first smooth the image data (one sample), then compute the that results in ca(a, B) risk. We report the results in Table 2] and show an example
Fig.
Limitation: Increased variance. In Fig. RCP1 shows considerably more randomness in the prediction sets compared BinCP. This is essentially due to the random definition the prediction set and the score function the prediction set in RCP1 is function of the random variable This randomness does not affect the final robust vanilla coverage.
Conclusion
While offering small sets for larger radii, smoothing-base RCP methods need many forward passes per input. Instead, we show that noise-augmented inference combined with CP is inherently robust, and with that, propose RCPI which needs only one forward pass per input. Our approach returns sets with size similar to state of the art while nullifying the need of many MC samples. Prior smoothing RCPs provide their guarantee by lower bounding the scores, hence they need to estimate (some statistic about) the distribution of score for each individual input. Alternativeyy we only apply the lower bound on the coverage guarantee which known in prior be a.
Table 2: Risk and mask size for the Cityscapes dataset. Risk level is 0. 0.15, with 100 calibration points. The variance is not over calibration sampling but over the images and 0.06.
Class
Risk
Robust Risk
(True) Class Prop.
Mask Prop-
Robust Mask Prop-
Pedestrian
0.1474 1 0.2797
0.2588
0.0160 0.0279
0.1891 0.1257
0.2522 1 0.1312
Car
0.1466 1 0.2582
0.0833 1 0.2032
0.0539 1 0.0545
0.0832 0.0733
0.1101 = 0.0807
10

---

Acknowledgements
We thank Guiliana Thomanck, and Jimin Cao for their feedback on our paper.
References
[1] Anastasios N Angelopoulos, Stephen Bates, Adam Fisch, Lihua Lei, and Tal Schuster. Confor- mal risk control. arXiv preprint wrXiv:2208.02814 2022.
[2] Anastasios N Angelopoulos, Rina Foygel Barber, and Stephen Bates. Theoretical foundations of conformal prediction. arXiv preprint arXiv:2411.1188 2024.
[3] Hangbo Bao, Li Dong, Songhao Piao, and Furu Wei. Beit: Bert pre-training of image transform- ers. arXiv preprint arXiv:2106. 08254, 2021.
[4] Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp. Prasoon Goyal, Lawrence D Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, et al. End to end learning for self-driving cars. arXiv preprint arXiv:1604.077 07316, 2016.
[5] Aleksandar Bojchevski, Johannes Gasteiger, and Stephan Günnemann. Efficient robustness certificates for discrete data: Sparsity- aware randomized smoothing for graphs, images and more. In International Conference on Machine Learning, pages 1003-1013. PMLR, 2020.
[6] Nicholas Carlini, Florian Tramer, Krishnamurthy Dj Dvijotham, Leslie Rice, Mingjie Sun, and J Zico Kolter. (certified!!) adversarial robustness for free! arXiv preprint arXiv:2206. 10550, 2022.
[7] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In international conference on machine learning, pages 1310-1320, PMLR, 2019.
[8] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele. The cityscapes dataset for semantic urban scene understanding. In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
[9] Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. Advances in neural information processing systems, 34:8780-8794, 2021.
[10] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x 16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.1 1929, 2020.
[11] Marc Fischer, Maximilian Baader, and Martin Vechev. Scalable certified segmentation via randomized smoothing. In International Conference on Machine Learning, pages 3340-3351.
PMLR, 2021.
[12] Asaf Gendler, Tsui- Weng, Luca Daniel, and Yaniv Romano. Adversarially robust conformal prediction, In International Conference on Learning Representations, 2021.
[13] Subhankar Ghosh, Yuanjie Shi, Taha Belkhouja. Yan Yan, Janardhan Rao Doppa, and Brian
Jones. Probabilistically robust conformal prediction. In Conference Uncertainty in Artificial Intelligence, 2023. URL https://p///ppp www.seeemanincolleeeeeeeeeeeeeee http://///pp..ssmttiiiiiiiiiii
org. Satgg/CrrpssD:::: :ttp:/oopusii::60347775.. 260334753
[14] Chuan Guo, Geoff Pleiss, Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. In International Conference on Machine Learning, 2017. URL https
//api. www.smtiiccccchllaat org/ hegg/CorpusDD ID: 28671436
[15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-778, 2016.
[16) Linus Jeary, Tom Kuipers, Mehran Hosseini, and Nicola Paoletti. Verifiably robust conformal prediction. 2024.

---

[17] Aounon Kumar, Alexander Levine, Soheil Feizi, and Tom Goldstein. Certifying confidence via randomized smoothing. Advances in Neural Information Processing Systems, 33:5165-5177, 2020.
[18] Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. Advances in Neural Information Processing Systems, 32, 2019.
[19] Thomas Massena, Léo Andéol, Thibaut Boissin, Corentin Friedrich, Franck Mamalet, Mathieu Serrurier, and Sébastien Gerchinovitz. Efficient robust conformal prediction via lipschitz- bounded networks. 2025.
[20] Yaniv Romano, Matteo Sesia, and Emmanuel J. Candès. Classification with valid and adaptive coverage. arXiv: Methodology, 2020.
[21] Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. Advances in neural information processing systems, 32, 2019.
[22] Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random
world. 2005.
[23] Ross Wightman. Pytorch image models. pytorch-image-modell 2019.
https://gtthhub.com/m/..gg
[24] Ge Yan, Yaniv Romano, and Tsui-War Weng. Provably robust conformal prediction with improved efficiency. arXiv preprint 1iXxx:2444.19633 2024.
[25] Greg Yang, Tony Duan, Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing all shapes and sizes. In International Conference on Machine Learning, pages 10693-10705.. PMLR, 2020.
[26] Soroush H Zargarbashi and Aleksandar Bojchevski. Robust conformal prediction with single binary certificate. 2025.
[27] Soroush H Zargarbashi, Mohammad Sadegh Akhondzadeh, and Aleksandar Bojchevski. Robust yet efficient conformal prediction sets. In Forty-first International Conference Machine Learning, 2024.
[28] Dinguuai Zhang, Mao Ye, Chengyue Gong, Zhanxing Zhu, and Qiang Liu. Black- box certifi- cation with randomized smoothing: functional optimization based framework. Advances in Neural Information Processing Systems, 13:2316-2326, 2020.
12

---

A Related Work
Gendler et al. 12] initially proposed robust CP resilient to adversarial examples (worst-case noise) without accounting for finite samples (asymplotically valid setup). Yan et al. [24] added finite sample correction and proposed new score to return (set size) efficiency. Both mentioned works were using randomized smoothing and the mean of the smooth score to bound the worst case perturbations. Zargarbashi et al. [27] (CAS) proposed to use the CDF information of the smooth score a more restrictive constraint and therefore returned smaller prediction sets. All of these methods required unrealistically expensive setup with 10s MC samples to be able to return acceptably small sets. Zargarbashi and Bojchevski (26] (BinCP) defined quantile-based score over the distribution of the smooth scores, that allowed same set size as CAS with orders of magnitude less samples (e.g. 200 would be sufficient). In contrast with all of the methods RCP1 works with a single augmented sample and without involving finite sample correction, which lies at the computation efficiency side of this trade-off.
Orthogonal to randomized smoothing. Jeary et al. 16.. and Massena et al. [9] use verifiers and Lipschitz continuity of the networks to bound the score function. Their robust radii are one order of magnitude smaller than smoothing RCP, but instead they do not require many forward passes per input. In Fig. 6 we show that approach (with the same computational efficiency) provides smaller prediction sets outperforming their results; plus, our approaches works for any black-box -bx model. Notably all mentioned works provide robustness to the worst-case noise which is orthogonal to probabilistically robust CP Ghosh et al. 13
B Additional Description of Figures
Fig. left. We report how the empirical coverage of C. (dashed lines) breaks for smooth prediction in BinCP and randomized augmented score in RCP1, compared to the vanilla conformal prediction (red dashed line). In all cases, we calibrate over clean calibration set and for radii r we return the prediction set of 1 which is In++ perturbed with adversarial attacks. Specifically attack from (21) for smooth methods and conventional PGD attack for vanilla CP. Compared to PGD, the PGDSmooth attack performs stronger for smooth scores. The solid lines are shows the empirical coverage of C, from BinCP and RCP1 on the same adversarial data. The main takeaway of the figure show the robustness of C,,, and the inherent resilience of smooth and augmented inference the adversarial (worst-case) noise. The result is for CIFAR-10 dataset, ResNet model and a = 0.5.
the PGDSmooth
Fig. middle. We compared the robust set size of BinCP and RCP1; plotted [C,,BinCP| RCr1 for which lower is better. The plot is for CIFAR- 10 dataset, ResNet model and o = 0.5.
Fig. rrggtt. Each point is computation of C, shown both in time and set size. All times are divided by single inference of the ResNet model. Here we evaluated two forward pipelines of cheaper ResNet model, and more time costly diffusion + vision transformer (as discussed in $ 4) Both axis are log-scale and the plot is for the ImageNet dataset. Here a = 0.5.
Fig. left. We took samples from the Beta distribution of the coverage each sample is then number 3. We computed the [3, B] and draw distribution of the new values. For the Beta distribution, we have 200, and 1
0.9. For the ct function we used
0.5, and 0.25
Fig. middle. We show the empirical coverage value under the PGDSmooth attack with a = 0.5 over various radii. We use the same sigma to show the theoretical lower bound coverage.
Fig. 3righh.. We reported the et function for Gaussian and Laplace smoothing both with 0.5.
The plots are not empirical.
Fig. right. Here use the l certificate from Yang et al. [25] Here the smoothing scheme is Uniform(-o//33o//55
C More on Conformal Prediction
Our default score function in the manuscript is TPS (threshold prediction sets) where the score function directly set to the softmax; a(ær, y) = Softmax,, (z)) for the prediction model f. Another choice is to use the logits of the model as the conformity score s(x, y) f(x),, Similar to BinCP we
13

---

2
Sample Rate
64
1.4
1.3
1.2
1.2
1.2
64
1.3
1.3
1.3
1.4
4.6
128
0.65
0.55
0.41
0.23
-0.19
-0.42
-3.4
0.54
0.49
0.4
0.24
0.16
-0.15
256
0.25
0.12
0.026
-0.33
-0.73
-1.2
0.12
0.022
0.00077
-0.24
-0.63
-0.91
4.
0.06
0.12
0.18
0.25
0.37
0.5
0.75
0.12
0.18
0.25
0.37
0.5
0.75
Figure 10: Comparison of BinCP and RCP1 for [Left] TPS, and [Right] APS score function on
CIFAR-10 dataset with a 0.9.
Table 3: Set size of RCPI for TPS and APS score across radii (r) and target coverage guarantees.
Coverage
TPS
APS
Avg Set Size
Emp. Cov.
Avg Set Size
Emp. Cov.
0.06
0.85
2.17 + 0.02
0.88 0.00
2.52 0.03
0.88 0.00
0.90
+.00
0.92
2.98 = 0.02
0.92 = 0,00
0.95
3.04
0.97
3.91 0.04
0.97 0.00
0.12
0.85
0.03
0.90 +
2.76 0.02
0.90 + 0.00
0.90
0.04
0.94
3.23 0.01
0.94 0.00
0.95
0.06
0.00
4.07 = 0.04
0.97 = 0.00
0.18
0.85
0.04
2.99 = 0.01
0.92 = 0.00
0.90
0.05
0.00
3,44 = 0.03
0.95 = 0.00
0.95
0.09
0.00
4.48 = 0.02
0.98 0.00
0.25
0.85
0.01
0.00
3.33 0.04
0.94 = 0.00
0.90
0.00
0.00
3.89 = 0.03
0.97 0.00
0.95
0.01
0.00
4.82 = 0.04
0.99 = 0.00
0.37
0.85
0.06
0.96
3.91 - 0.01
0.97 0.00
0.90
0.00
1.98+000M
4.55 0.09
0.98 0.00
0.95
0.14
0.99 +
6.49 = 0.04
1.00 0.00
0.50
0.85
0.03
0.98
4.55 0.11
0.98 0.00
0,90
0.04
0.99
5.34 = 0.03
0.99 - 0.00
0.95
1.000
1.00
10.00 0.00
1.00
0.75
0.85
6.28 0.19
0.90
6.31 - 0.11
0.11
0.99 0.00
0.90
0.000
1.00
10.00 + 0.00
1.00 0.00
0.95
10.00 0.00
0.00
10.00 = 0.00
1.00 = 0.00
using a single binary certificate which do not rely on bounded score function. Another conformal prediction method called as adaptive prediction sets (APS) uses the accumulated softmax to label
[ y as the conformity score; formally s(x, y) -I [ y) u + k=1 л( v) -I[[ [[[ y&) n <<x y)]] where म (æ, y) = Softmax, (x))) and ~ Uniform 00, 1]. While this score results in larger sets, it increases adaptivity approximate conditional coverage.
We report the result using these score functions in Fig. 10 (comparison of BinCP and RCP1 for each score) and Table 3 (the set size of RCP1 for both score functions). As expected, similar trend as TPS observed for APS as well.
Same as BinCP we also do not need the score function to be bounded. However in the end, using an unbounded score function (like using logits directly) did not show to improve over the existing APS and TPS.
14

---

D Supplementary to Theory
D.1 Robust Conformal Prediction Guarantee
The guarantee Eq.
doesn't take the randomness in score function and prediction set into account.
This is while many conformal scores have random variable inside, for instance APS (00 multiplies the probability of each class by uniform random value break the ties (and enable the exact a coverage). The original guarantee taken from [3 27 is:
Pr Da Pa-PntinD Pr Dn Va (8(+++4)))
Un+1 (5s(nn41)) Vän+i E ((En41) )
inf
M/ Cz(@n+1) = 1| 2 -
This formulation fails to capture the stochasticity in the score function (and hence in the prediction set). Since with very small probability to miscover a point (which is non-zero in methods like APS) the indicator evaluates false. The worst-case indicator infys,, 18, (1) I[yn+1 Cg()n+1) = 1] becomes zero whenever there exists any probability that -n is not covered. Consider the non-robus case where no perturbations are applied: i.e., evaluating the coverage guarantee of standard conformal prediction. Using the APS score function and shrinking the perturbation space to an infinitesimal ball B, as r + 0+ (and therefore #a+1 - 1n, the coverage probabílity should exceed APS already satisfies this guarantee. However many of the datapoints that have small probability to exclude the true class from the prediction set will not pass the worst-case indicator. Consider a datapoint with one hot conditional probability, still the top label will be in the prediction set with probability -9 where q is the threshold.
a, since
While the shortcoming in Eq. 2] excludes any CP with randomness in the score, still previous smoothing-basee basedd RCP methods (at least in assymptotically valid setup) satisfy its conditions inde- pendent of the score function used. This is since all previous methods systematically remove all the randomness from the score and return a deterministic prediction set. Given any base score function, these methods defined their own score as statistic (e.g. mean, or quantile) over the distribution of the base score on x + E. As the distribution already includes the inherent randomness in the base score itself, the statistics like mean [12 27 and the quantile (26) are deterministic (excluding any randomness). This is an orthogonal to the probabilistic nature of estimating these statistics from Monte Carlo samples (the validity of confidence intervals). As result the final set based on these scores exclude the inherent randomness of the base score function.
D.2 Proofs
Proof of Lemma 1
The Lagrangian form of Eq. 4 is:
((3 min Pr[M(t + c) 1] - 11
()](h((())=1) -x 3)
hef0,1f1a1
min he(0.1)la)
Egzgltie [h(2)] A E2 (h(z)
B] x x + min
Egmalh(2)] - -Eznpl [2(2)
NE(U,1) A1
/ (9(2) A xx.)))))p()))) h(z)dz AE(0.1)
= = 3
min
where p and q are smoothing distributions centered and i respectively. The worst classifier (the minimizer of the problem) can be derived as follows
h(z) = { otherwise
((=) p(z) 2
Intuitively, to minimize the term fx (1(2) - A p(=)) h(z)dz we look at each point independently. For each point the term (q(z) - A p(=)) is positive we cancel by h = 0 and if negative we keep it to decrease the total integral value. The resulting dual with the dual variable À 0 is then:
C(B,A) B+ m p(=) X ((z)d2) X- ((A))
15

---

Here I(x) : min X {(z)<z} is only a function of X. Maximizing over À we get the optimal dual soltuion which equals the optimal primal since it was shown that strong duality holds 28
[ B] max À - 3 ((A)
Which is pointwise maximum of affine functions and therefore convex in
The monotonicity w.r.t. 3 directly follows from the definition. By increasing 3 the feasible space reduces to nested subset of the previous problem which means that the solution will be greater than or equal to the original solution.
D.3 Choosing the conservative 1 a²
In general to obtain - a robust coverage guarantee, we should choose the nominal a' in Alg. 1 such that et a, B3] to the non-decreasing nature of ct, But in many cases including the Gaussian distribution, where the canonical points can be used interchangeably (choosing (t, as the pair clean, and noisy canonical points doesn't tt differ from the opposite (f, t), the following lemma allows us set the 1- a' = c1 a,B
This nominal probability can be found via binary search due
Lemma 2. for a smoothing scheme, and a perturbation ball B, canonical points t, and can be used interchungeably; then we have ct cC 3-, p. Using the canonical points interchangeably means that for ct, and (similarly et both of the optimizations
max Pr(h(E + +c =1] kgH
c)
and
max Pr[h(t + 6) = =1] s.1. Pr(M(t+e) 6) = =1|1pp bER
yield the same solution.
Proof. The term (p B,, B-1] is expressed as the following optimization problem:
Pnigh = max Pr[li(t E) 1] s.t. Pr( + <) =1] = piow
(7)
hER
Plow min Pr(h'(E c) 1] s.t. Pr[h'(t + c) 1] Prif(t +c] =p
M'H
We swap i, and since we can use the canonical points interchangeably. We have
Phigh max hEH
Pr(h(t + =1 s.t. Pr(h(E + c) 1] = Piow
how the solution to the inner problem in Eq. 7 (defining Plow) is feasible solution to the outer optimization (the first line); therefore
Phigh = max (t + + = 2 (t = = NEW
Both functions ct, and ct (and therefore both minimization and maximization) are non non-decreasing the value in their constraint. Assuming Phigh > P (Pligh * p), we have p c [p B that
Piow < Piow (due to non-decreasing nature of c.). We have
p max Pr hEH
s.t. Pr[h(E+ cc) = 1] = Plow
with maximizer function Wiigh ; i.e. p Pre Prelhhigh E) 1). We rewrite inner problem in Eq.
Piow min (r(h'(t+e)) =1] Pr(h'(m + +e) = =
NEH
The maximizer function Mygg satisfies the constraint, and therefore Piow << plow which is contradic- tion. Therefore Phigh p.
16

---

D.4 Lower and Upper Bounds for All Shapes and Sizes
Lemma 3. For a binary classifier f(x), let g(x) Prelf(# + c) = 1] and
g( 2 cglp, B] == : min Pr [h( c) = 1] s.t. Pr(h(c c) = --]==[[ =(x) =
hEH e
Similarly lei
g(ā) S c)lp,
max Pr[h(@ + =1 s.t. Pr[h(a + t) e)= 1] = g(x)) p
kER
Both be obtainable at the same canonical points. We have c/jnn, B] = - -cgl [ p. 13..
Proof. For simpler notation let g(x) c) - c2
B).
B]. then we have
1 1 g(x) = 1- max Pr (h( c + E) = 1]
NEH
Let h'(x) = 1 h(z) then
1 max Pr[1 H 6) 1] min Pr[h (+ + 6) = I]
N'E
NEW
The constraint also translates similarly
Pr[h(x + c) = -
Pr(h' c) 1] =11=11
c
And the new problem is by definition same as 1 - ct - p, B)
Certified Upper and Lower bounds for all Shapes and Sizes. In Prop. we rephrased the Theorem 4.1 from Yang et al. (25) to return the upper bound probability instead of the robust radius. Here we prove Prop. 2. using the original proof from Yang et al. (25
Let g := [e[f(x + E)] for any binary decision function f and any e ~ & where {(x) oc (xp(=t/(1) If g()) is continuous in X, for any point = x + one can compute the g(x + 5) through line integral as
L' d τi Lo( + t. o')]et
o(क) g(x + 8)= =(x)
where 8' [لīl the unit vector in the same direction as ô and r == |0||| In other words, we add all
the infinitisimal changes on the path from x to ã to compute the value of g(Ø) given g(x))
With the decision boundary 2/ = {x f(x) 1}. and 2 as the decision boundary translated by - z, consider the following function
E(U (8) p
f(p)
sup 5:||6|=1
sup HER-E(()-
lim -0+ r
Proposition F.8 from Yang et 25 show that anywhere in X, we have di [g([)] S (gg(2)). This means that one can upper bound the growth of g(x) while shifted by 5 by integrating over (z)())) instead. For casier notation let h(t) g(x +t 8') which implies h'(t) de h(t) < M(h(t).. Notably, the function (pp) is always non-negative See the equivalent Definition H. from Yang et (25 where the function is denoted as (pp) and it is written as expectation of maximum over a value that is always non-negative. For positive (non zero) ((h(t)), including but not limited to h(t) S 1/2 (see the definition of the function in Appendix F from Yang et al. (25) It follows:
1'(1)
L
M(1) dt -
/-' 1dt =r
< <1=
((h(t))
((h(())
We set = h(()) = du = ht(t)dt which implies
ITa)= /
(tt)) di pumh(r) 1 du S
((h(())
1(u
-==(())
17

---

Here h(0) - g(x 0 --'00))) 8*) = g(x) B, and h(0) - g(x +r. 8') - ( 3. With the reference
function F(7) - S Bip) dp we have
3 dp- /
1/2 1
1/2 1 a(p)
dp-
dp - -
((B)
11())
1(p)
which is F(B) 2 F(3) -r
The authors already computed R(p) (in their paper is called 4) for following several distributions, including:
Isotropic Gaussian smoothing against & ball (a 1): I(u) 00(0 (1-=)) implies:
u)) which
Gaussian (1) = //²
1 du {
3 1 du
(?(u)
10'(0-1() u))
With c 2-1((1 u) we have dp- = - (c)dde, and (c) = 4' (o- u)). Therefore
(1-
1 du
- du = $ 5- - 3) - x - B) r
D ( (1 u))
1b 1(1-))
--- (1 B) 2 ② (1 8) - 1 -- 3 2 1 (6) -
x- ( < <0><a>>0 +r
3 3 +r)
Which completely aligns with the aforementioned closed form fz certificate.
Laplace smoothing against & ball (a = 22A): 22()) = X which implies:
II Haplace (2) lo 1 du x- Alog 8 Sr
3
S 2-12
= B < 2
+ 3
Note that in both cases, the function (1p) is positive in (0,
E
Supplementary Experiments
Compute resources. We ran our experiment using Nividia A-100 and H-100 Tensor Core GPUs. For each experiment only one GPU was used. We use the A-100 GPU for the CIFAR-10 10 dataset under ResNet setup, and the conformal risk control experiment. The rest of the results use H-100 as the compute resource.
Experimental setup. For the CIFAR-10 10 datasets evaluate the results over 2048 test samples for ResNet model and 10000 images for the ViT models. For the ImageNet since the number of classes 1000, we report our results over 5000 images for ViT models and 50000 images on ResNet models. Ultimately the number of samples does not influence the empirical results. The number of Monte Carlo samples are initially set to 500 for CIFAR and 300 for ImageNet. For each experiment, and for the reported sample rate we cut the precomputed samples, from the reported number.
Our results are reports over 100 runs (except the conformal risk control which is over run. In each run we sample the 10% of the points as the calibration set. For conformal risk control we report the result 300 images where 100 random images from it is taken for the calibration. Ultimately the size of the calibration set does not effect the final performance. As the calibration set gets larger the distribution of the coverage probability concentrates around 1 a.
The time to compute the logits for the CIFAR-10 10 500 samples), and for the ImageNet dataset it is 13:52:11 I (ViT with 5000 datapoints and 300 MC samples). For the ImageNet, and the ResNet model this number is 2:52:11 1 (for 50000 datapoints and 1000 samples).
dataset is 1:30:56 (ViT with 10000 datapoints and
18

---

Table 4: Empirical coverage and average size for different radii (r), for CIFAR-10 10 dataset with ResNet model and a 0.25.
Table 5: Empirical coverage and average set size for different radii (r), for CIFAR-10 dataset with ResNet model and 0.5.
Empirical Coverage
Avg Set Size
r
Empirical Coverage
Avg Set Size
0.06
0.936 + 0.018
2.156 + 0.241
0.06
0.921 = 0.020
2.684 = 0.244
0.12
0.961 + 0.014
2.646 0.306
0.12
0.937 0.018
2.937 = 0.285
0.18
0,981 = 0.010
3.315 = 0.478
0.18
0.951 = 0.016
3,236 + 0.356
0.25
0.990 + 0.008
4.178 = 0.798
0.25
0.966=00000
3.741 + 0.530
0.37
1.000 = 0.000
10,000 + 0.000
0.37
0.980
4.500 + 0.560
0.50
1,000 + 0.000
10.000 + 0.000
0.50
4.990=00000
5,300 = 0.712
0.75
1.000 + 0.000
10.000 + 0.000
0.75
1.000 + 0.000
10.000 + 0.000
7.3
6.2
1.3
7.3
6.7
2.3
2.7
6.2
4.7
50
0.87
6.7
5.8
1.8
1.7
1.9
1.8
5.6
4.6
60
0.73
0.65
0.38
5.8
1.4
1.5
1.4
1.3
1.2
4.7
70
0.57
0.39
0.083
-0.021
1.2
1.3
1.1
0.93
0.82
1.1
80
0.39
0.2
-0.13
-0.34
1.1
0.95
0.67
0.55
0.51
90
0.36
0.16
-0.18
-0.48
0.95
0.86
0.79
0.54
0.26
0.39
100
0.31
0.051
-0.37
-0.71
0.88
0.77
0.63
0.43
0.055
-0.16
150
0.067
-0.17
-0.62
-1.1
-6.1
0.56
0.46
0.32
0.084
-0.31
-0.74
-4.1
200
-0.016
-0.33
-0.7
-1.3
-6.4
0.38
0.29
0.071
-0.26
-0.55
-0.86
-4.6
0.06
0.12
0.18
0.25
0.37
0.5
0.75
0.06
0.12
0.18
0,25
0.37
0.5
0.75
Figure 11: Comparison of BinCP and RCP1 in terms of [Cr, Bin.Blr |C,,CCr (higher (green) shows better performance for RCP1) across various radii and sample rates. Results are the ResNet model and for the CIFAR-10 dataset. [Left] a = 0.25, and [Right] a = 0.5. Note that the numbers are in terms of difference and compute the absolute numberTable and Table can be used as reference.
Set size experiment. Tables Table and Table rjeppttt the empirical coverage and average prediction set size of RCPI for different radíi on the CIFAR-10 dataset using ResNet model under two noise levels, a 0.25 and 0.5, respectively. We also report the result of the ImageNet dataset (for the ResNet model) in Table Specifically for this dataset, because of the large number of classes we also reported the proportion of the sets below specific sizes (1, 3, 5, and 10). As expected, increasing the radius results in more conservative setup and hence higher coverage on the clean points. For CIFAR-11 dataset[Fig II and for the ImageNet dataset Fig. 12 visualize the comparative performance between BinCP and RCPI across various radii and sampling budgets. These results are on the ResNet model. The heatmaps show the difference in set sizes |Cr,Rincp| - |C,,RCPI I. where positive (green) values indicate that RCP1 provides smaller or more efficient sets. RCP1 generally outperforms BinCP across low sample rates, especially for smaller radii and moderate sampling budgets. The reference tables (Tables Table 4 and Table 5 Table 6) can be used interpret these differences in absolute terms.
Proportion of small sets. As also discussed in although the proportion of sets with size less than threshold shows how applicable a CP algorithm is, it can be misleading CP framework can return many false prediction sets with very small set size. Therefore alongside the proportion of these sets we should also report their coverage. We show these results in Fig. 13 Our observation is that all setups result in sets with coverage higher than the determined level. Note that in terms of proportion RCPI stands somewhere between BinCP with 64 and 128 samples which aligns with our aforementioned intuition.
19

---

98. .99
98 981.75
975.91
966.05
942.20
724.78
0.00
-0.63
-0.56
-0.50
-0.43
-0.34
-0.25
-0.11
0.00
985.99
98 981.75
975,91
966.05
942.20
724.78
0.00
.0.63
-0.56
-0.50
-0.43
-0.34
-0.25
-0.11
0.00
128
4.02
1.59
-1.94
-
942.20
901.54
724.78
0.00
-0.18
-0.14
-0.10
-0.07
-0.34
-0.25
-0.11
0.00
236
0.52
-2.59
-7.32
-66.77
-36 89
-70.74
724.78
0.00
-0.13
-0.08
-0.04
0.02
0.08
-0.11
0.00
0.06
0.12
0.18
0.25
0.75
1.0
0.06
0.12
0.18
0.25
0.75
1.0
Figure [Left] Comparison of the average set size BinCP - RCPII and [Right] the proportion of the sets with size < 10 expressed in BinCP RCP1. In both plots green shows that RCP1 is performing better. convert relative difference to absolute number Table caan be used as reference.
0.8
0.9
0.9
0.9
0.6
0.8
0.7
0.7
0.7
0.4
0.6
0.6
0.6
1.000
0.975
0.975
0.975
0.975
0.950
0.950
0.950
0.950
0.925
0.925
0.925
0.925
0.900
0.900
0.900
0.900
RCPI
BinCP-64
BinCP-128 12
RCPI
BinCP-64
BinCP-122 28
RCP1
BinCP-64
BinCP. 18
RCP1
BinCP 64
BinCP-1 128
Figure 13: [Up] The proportion and [Bottom] the coverage of the prediction sets with size [From left.
right] |C|
1, |C|
3. |C]
<
5,
C < 10.
20

---

Table 6: Statistics from RCPI across various radii. The results are for ImageNet dataset and the ResNet model.
Avg Set Size
Emp. Coverage
5
C C 3
$ 5
C S 10
0.06
14.013
1.787
0.921 0.008
0.139 0.010
0.311 + 0.018
0.430
0.025
0.626 0.035
0.12
18.246
2.606
0.936 0.009
0.120 0.010
0.019
0.383 0.024
0.560 0.032
0.18
24.095 3.645
0,951 0.008
0.010
0.239
0.018
0.336
0.501 0.031
0.25
33,953
0,964 0.007
0.082 0.008
0.201 0.017
0,432 0.033
0.37
57.802 +: 10.753
0,979 0.005
0.151 0.058 1: 0.008
0.219
0.337 0.031
0.50
98.464
19.136
0.989 0.003
0.036 0.006
+.104+00016
0.160
0,252 0.029
0.75
275.222
88.968
0.998 0.002
0.012 0.006
0.036 + 0.016
1003
0.115 0.039
1.00
1000.000 + 0.000
1.000 0.000
0.000 0.000
0.000 + 0.000
0.000
0.000 0.000
Table 7: RCPI for conformal regression. We report the empirical coverage and the interval length across varius radii.
Empirical Coverage
Interval Width
0.00
0.900 = 0.005
0.371 + 0.012
0.12
0.920 = 0.005
0,426 = 0.014
0.25
0.938 + 0.004
0.494 + 0.018
0.50
0.963 + 0.003
0.667 + 0.026
Regression Experiment For robust conformal regression with RCP1 we use the Udacity and originates from Nvidia's DAVE-2 system[4] The input of this task is scene, and the task is to estimate the steering angle of the car. The output range is from -1 (completely steering right) to (left). For this task we finetune a ResNet18 model [15] images augmented with isotopic Gaussian noise with = 0.5. We run finetuning for 200 epochs. We use the same for augmenting the input in RCPI. We set result is the first robust conformal prediction with randomized smoothing for regression task. (Talle 7 compares the interval length and empirical coverage across various radii.
0.9, and evalute
(0.12, 0.25, 0.5). To the best of our knowledge
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Other claims that are already proven in prior works we prove every new claim.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discussed the limitation of our work at the end of S
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each thcoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
22

---

Justification:
We dedicated D.2 and S D.4 for our proofs and referenced them in the
manuscript.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Ys]]
Justification: Both in the last paragraph of the introduction and S the procedure explained. Datasets, models, and evaluation criteria are also discussed in
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
23

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Our code is uploaded as zip file in the supplementary materials. After acceptance we also share the code in GitHub. All datasets are well-know the literature. and all models are pretrained and open source. We also cited the original work introducing that dataset or model.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https wtw.odeeuumiissoooooooloooo
//nips. ptsipss.ccpubllccguuudeeess
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
We discussed the parameters in B and in the caption of the figures.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Ys]]
Justification: We show the confidence intervals as error bars the plots. Later Table 3 we represent the results in form of mean + std.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
24

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are of range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: We discussed the compute resources in $ E For the wall-clock time report in Table we explicitly reported the resource in the caption.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect. with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We did not involve any human participation in the experiments. All datasets and models are open source and known to the literature.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., . if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The work a fundamental reseach and does not have potential societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
25

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The work a fundamental AI research and poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We have cited all the datasets and models used in the work.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
26

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, latasets,papersstt www.ppppppsshhhocc
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
27

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: We only used LLMs some parts improve the quality of the text.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: //pppri///eurpp..... http///rpppscccoooeeeeeeeeee//// cc/Connferencce//2255/LLL for what should or should be described.
28


Reviews:
[{"review_id": "pQnqFnLc62", "reviewer": "Reviewer_ABhm", "summary": "The paper claims that robust conformal prediction can be achieved by using a single sample for each example in the calibration set. \nRobust conformal inference is a method for providing a super-set of classes in a classification task that with high probability \n(on average over test points) includes the correct class, even when an adversary is allowed to locally perturb the feature vector. \nAs with (many) other robust conformal prediction, the key to robustness is adding random noise to the input before applying the score function, thereby negating the specific choice of perturbation. However, this cannot overcome the fact that the (smoothed) calibration set is no longer exchangeable with the (smoothed) perturbed feature vector, but rather only with the (smoothed) original vector. Methods that were proposed to bound this extra decay (or extra radius) used many samples (per calibration point) to estimate the post-smoothing mean score or the post-smoothing quantiles. This paper presents an argument that the multi-sample approach is not necessairy to maintain conformal coverage, and therefore reasonably-sized robust conformal set can be estimated with far fewer forward passes. This can make robust conformal prediction much more affordable even when using large prediction models. The experiments compare the conformal prediction levels under adversarial feature choice, and find that for small samples, the new sets are competitive in terms of size and coverage (though have higher variance).", "questions": "See above, there are many things I did not understand upon reading the paper. \nI think this at least partly reflects on the clarity of the current writup. \nBut also I would like to better understand the answer to these questions, \nand clarifications, especially if they manifest in the text of the paper as well, could definitely result in the increase of scores.", "limitations": "I thought the discussion of the added variance in using one sample (discussed in two samples in the limitations) should be expanded;\n more generally, \nwhat do we lose when we only use a single sample?\nDoes it mean that our conformal coverage is less or more uniform \n(i.e. is the conditional coverage more or less similar across samples)?", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\nSignificance: \nFor ML algorithms based on large NN, the number of calls to the prediction function is often budgeted due to time, \ncompute or even monitory constrains. Therefore identifying a robust-conformal algorithm that can be run with considerably less \nfunction calls per sample with only limited impact on the efficiency (e.g. the adversarial radius) can be very important for adoption of these ideas.\n\nOriginality: \nI think the argument itself for providing much more efficient (in terms of samples) conformal sets is potentially a step forward for the field. \nIt is hard for me to assess how much is new in the argument or method due to issues of clarity in which I struggled with the paper. \n\nWeakness: \nClarity / Quality: \nI admit that I did not manage to understand the main theoretical argument of the paper.\nNamely, what are the method by which they claim to change methods that use multiple samples (to estimate lower bounds on the mean region or the quantiles of the distribution) into a method that uses a single sample. \n\nHere are the specific questions I did not have answers to, after multiple readings of this manuscript: \n- What are the main reason that other papers state for using multiple samples to estimate the bound-adjustment for robust Conf-Sets, \nand how does this paper elevate or pass over those reasons.  \n- Does the paper introduce \"only\" a new claim and proof, or also a new robust-conformal prediction algorithm (inc a new way to estimate the bounds c^{arrow down}). \n- Moreover, it is not clear what is the precise *algorithm* or bound that used to compute the Conformal Set and in what specific ways is it different from, say, Zargarbashi and Bojchevski bound or Cohen et al or other previous works. \n- Do the claims of success of a single sample based bound refer to the empirical or to the theoretical worst-case coverage (e.g. to which one of the curves in the middle of Figure 2). \n\nMore generally, I found it very hard to distinguish the trees from the forest: \nFor examples, in Prop 1 the papers runs through proof without explaining the ideas behind it, \nand uses in the statement of the result and the proof an important concept / notation (the lower certified bound c^{down-arrow}) that is  defined in Eq 4 almost one page below. \n\n[This could be my fault here; I am not an expert in the litrature of robust Conformal sets\nI am well read in conformal prediction generally, and have manged to read and mostly understand the main cited papers including Yang et al, Cohen et al, and Zargarbashi and Bojchevski; I failed on this paper. ]\n\nAlso, in clarity, it is not helpful that the full explanations of the figures is in the appendix; many of these figures where hard to understand without the longer version of the legend, and I did not know the longer legends are in the appendix until I went there to check.", "was_revised": true, "final_justification": "I think I now understand the main claims of the paper, \nhelped by the discussion with the authors. \nI think the ideas are interesting and worth presenting in the conference. \nI have therefore increased my score. \n\nHowever, the paper has substantial clarity issues, \nand these surfaced in our discussion. \nImportant aspects of the methods and the proofs are hidden within the proofs. \nThe high-level ideas were almost not discussed: \n- How the methods works with one sample (an upper bound on the effect of smoothing)\n- What are the downstream effects of using a universal but worse case upper bound \ninstead of estimating a local statistic as the other methods do. \n[There are both positive and negative effects. the positive are in the title; the negative, \nin potentially reducing the conditional coverage, increased variance, and potentially increased samples sizes, \nare only partially discussed in the limitations and are somtimes hidden). \n  \nFurthermore, the writing of proofs and the figures / legends can be improved for clarity. \n\nI hope that if the paper is accepted the authors try to fix the final version so to increase clarity and\nto reflect our discussions.", "rebuttal": "We thank the reviewer for reading our paper; we understand that the writing was difficult to follow; and surely we’ll update the camera ready to enhance the readability. Here we discuss the questions and unclear parts. If the results remains yet unclear, we are more than happy to discuss further:\n\n**RCP1 vs other smoothing-based robust CP approaches.** Consider the robustness certificate (Eq 4) as a black-box that receives a probability (or generally any bounded value) and returns a lower (and upper) bound for that probability. Now among the previous methods (RSCP+, CAS, BinCP) all applied this bound on the score function. RSCP+ defines the new score as the mean of the smooth score distribution, CAS does the same only through the CDF of that distribution finds a better bound (a better black-box), and BinCP applies the lower bound on the quantile of the scores. This work derives a lower bound on the coverage probability itself. Then it reverse engineers a higher $1 - \\alpha’$ such that its lower bound is above $1 - \\alpha$.\n\n*What is different?*  All three prior methods are bounding the score function. Since the robustness certificate works with exact probabilities, we need to estimate that value from Monte Carlo examples (estimate the mean of some smooth scores from m samples), and since we are estimating with finite samples we should account for final sample correction. This correction creates a trade-off: more samples per point results in tighter confidence interval (smaller sets), so we should either get large sets, or run many forward passes.\n\nOppositely, since we apply the lower bound on a given probability $1 - \\alpha$, we do not need to estimate it. Therefore, with only one (noise augmented) inference, we can compute the robust prediction sets.\n\n*What are the challenges?* The proof is generally different, and since this $1 - \\alpha$ is the expectation of a Beta distribution itself, we should prove that the smoothing-based lower bound can move from each run to the total expectation. For that we needed to prove that robustness certificates are convex.\n\nAlso from the description, we answered that we do not propose a new robustness certificate. We change the way we are using it in conformal prediction to improve the computational efficiency. Same applies to all three mentioned prior works.\n\n*Why we need sampling in prior works?* Since in prior works the object which we wanted to bound within the threat model is the mean (quantile, or any other statistics) of a distribution which we don’t know. And computing that statistics exactly is intractable. Therefore, we need to estimate it via samples, and more samples result in a more precise estimation of that value.\n\n**Figure 2.**\nThe solid line is the theoretical lower bound, derived in Proposition 1, which should be (and is) lower than the empirical line which is the dashed line (both are for single sample). So the empirical coverage should be higher than what we compute as a lower bound. The figure shows that indeed the lower bound holds. Note, that this solid line is computed for a target of 1-alpha = 90% — lower bounding the worst-case coverage if it is calibrated with 90%. For example, for r=0.2 we get worst-case coverage of ~81%. If we want worst-case coverage of 90%, as a defense to the perturbations, we find an initial higher 1-alpha=95% which after the lower bound becomes 90%.\n\n**Algorithm.**\nYou are right. Although we discuss the general algorithm in the introduction (lines 81-83), still nowhere else we explicitly define the algorithm. In following we bring the pseudocode, and later we will add it to the camera ready version. The algorithm is to do both calibration and defining prediction set same as vanilla CP with two differences: (1) instead of inference over $x$, we should apply inference over one sample from $x + \\epsilon$. (2) Instead of $1 - \\alpha$ we should aim for coverage guarantee of $c^\\uparrow[1- \\alpha, \\mathcal{b}]$ to attain $1 - \\alpha$.\n\n---\n**Algorithm 1: RCP1 – Single Sample Robust Conformal Prediction**\n\n- **Input:**  \n\nThe calibration set\n$\\mathcal{D} _ {\\mathrm{cal}} = \\{(x_i, y_i)\\}_{i=1}^n$\n  \nThe score function\n$s: \\mathcal{X} \\times \\mathcal{Y} \\to \\mathbb{R}$\n  \nthe test point\n$x_{n+1}$\n\ntarget coverage level $1 - \\alpha$\n\nperturbation ball $\\mathcal{B} _ r$  \n\nsmoothing scheme $\\xi$\n\n- **Output:**  \n  $\\mathcal{C} _ r(x_{n+1}) \\subseteq \\mathcal{Y}$\n\n1. **Step 1.** Draw noise from the smoothing scheme, compute conformity scores for augmented calibration data:  \n   ```\n   for i = 1 to n do\n       \\epsilon_i ∼ \\xi  \n       s_i \\gets s(x_i + \\epsilon_i, y_i)\n   end for\n   ```\n\n2. **Step 2.**  \n   - Compute corrected level:  \n     $$1 - \\alpha' = c^{\\uparrow}[1 - \\alpha, \\mathcal{B}_r]$$\n   - Compute the $$ (1 - \\alpha') $$ quantile with correction:  \n     $$q \\leftarrow Q(\\alpha'; \\{s_1, \\dots, s_n\\})$$\n\n\n3. **Step 3.** Construct the prediction set for the test input:  \n\n$$\\mathcal{C} _r (x _{n+1}) = \\{ y \\in \\mathcal{Y} : s(x _{n+1} + \\epsilon _{n+1}, y) \\ge q \\}$$  \n\n4. **Return** $$\\mathcal{C} _r(x _{n+1})$$\n\n---\n\n**Idea behind the proof of Prop 1.**\nWe answered this question in the beginning of our response. If the intuition is not yet clear we would be very happy to introduce it again. Thank you for pointing this out. We would definitely add a similar description before the proof of the proposition in the camera ready. \n\nAlso we borrowed Zargarbashi and Bojchevski’s definition of $c^\\downarrow$ and $c^\\uparrow$ without rigorously defining it.  $c^\\downarrow[f, x, \\mathcal{B}]$ is the certified lower bound for function f in the nearby points around the point x which is $c^\\downarrow[f, x, \\mathcal{B}] = \\lambda \\Leftrightarrow \\forall x’ \\in \\mathcal{B}(x): \\lambda \\le f(x’)$. \n\nWe are very thankful for the reviewer’s comment on the readability of the paper. We will surely add descriptions and intuitions to make it more clear. If there is any part that is not yet clear we would be more than happy to further introduce it."}, {"review_id": "BvXUj3f0WC", "reviewer": "Reviewer_MZPH", "summary": "The paper studies robust conformal prediction (RCP) by randomized smoothing. The authors show that with a single forward pass on randomly perturbed input can already attain robustness. Interestingly, the empirical findings support that RCP1 produces smaller set sizes compared to BinCP when sample rates are small. Additionally, RCP1 is agnostic to the distribution of inputs and scores.", "questions": "1.\tIs the computation of the certified lower bound for RCP1 the main difficulty comparing to methods such as BinCP? If so, is the limitation on the choice of smoothing methods or assumptions?\n2.\tIt is interesting to see when sample rate is low, RCP1 consistently produces smaller prediction size. Is it purely a consequence of randomness in sampling for BinCP by Monte Carlo? Can the authors provide more insights, or whether it is possible to improve prediction set size when sample size is moderate (e.g., between 1 to 100).", "limitations": "See \"Strengths and Weakness\".", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1.\tThe paper is well-written, clearly organized and easy to follow. \n2.\tThe theorems are well presented and are sound for the parts that I checked.\n3.\tThe experiments indeed show favorable properties of RCP1 especially in terms of computational time, and comparable quality when sample size is small. In particular, the empirical findings support that RCP1 generate smaller prediction set size when sample rate is low.\n\nWeakness:\n\n1.\tThe comparison of RCP1 and previous methods using multiple samples is obscure. For example, a parallel comparison between RCP1 and BinCP can be beneficial.", "was_revised": true, "final_justification": "The authors clarified some of my initial confusion. The work is interesting and requires some final touch-ups for the presentation and clarity. I remain my recommendation for the paper.", "rebuttal": "We are very thankful that you read the paper, and very grateful that you liked it.\n\n**Parallel comparison with BinCP**. If by parallel comparison you refer to running both up to the same wall-clock time, indeed BinCP returns full sets if limited to the time RCP1 returns its result. Besides the sampling, BinCP and RCP1 both apply a single binary certificate; which means that although the binary certificate is negligible in computational time, they both have same cost in terms of calling the certificate. The only difference is that BinCP needs more than one forward pass and with only one forward pass (equal or parallel setup) it returns trivial sets of $\\mathcal{C}(x) = \\mathcal{Y}$.\n\nThis also answers the first question. Additionally the bottleneck in BinCP is independent to the choice of the smoothing scheme. It is only due to several runs of the model on the same data. As shown empirically. \n\n**Second question.** We think the reviewer refers to when sample rate is low in BinCP — otherwise what we show is that RCP1 only works with a single sample. The set size for BinCP increases up to returning all possible classes. Here we provide an intuitive reason behind it:\n\nWhen the score is defined as some statistical term over the model and smooth input, since the certificate works with exact probabilities, we should estimate that statistics. For example consider the case where the score function is defined as the mean of the score distribution (over smooth input). There is a ground truth value, but finding that value is intractable. Instead we compute an interval which covers that true score with a very high probability (e.g. 0.999) — known as confidence interval.  The size of this confidence interval decreases by introducing more MC samples. For correctness of robust CP we should (conservatively) take the lower bound of this interval and that is what contributes to increasing the size of the prediction set. \n\nThe main contribution of this work is to find another variable to apply the robustness certificate over — a variable that is not needed to be estimated and that is the coverage probability. What we show is that the expected coverage probability (which is already given despite the number of MC samples) is lower bounded. Prior works showed similar for the score function (or quantile of scores which is a function of scores) and scores should be estimated."}, {"review_id": "1CkYhwIhUc", "reviewer": "Reviewer_cNni", "summary": "This paper uses the binary certificate technique to develop a single sample robust CP (RCP1), which reduces model forward passes in constructing the prediction set. The experiments show that RCP1 achieves robust prediction sets with comparable sizes to state-of-the-art methods while reducing computational overhead.", "questions": "1. In Line 41, what does \"vanilla CP combined with noise-augmented inference\" mean?\n\n2. What is the proposed prediction set and coverage guarantee?\n\n3. How can you make sure the lower bound in Proposition 1 is greater than $1-\\alpha$? If this lower bound is large, how can we say \"conformal prediction combined with single randomized augmented inference already shows robustness\"?\n\n4. What is the form of $\\mathcal{C}_r$ in Line 108?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 1, "clarity": 1, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\nThis paper introduces a new technique for robust CP under adversarial noise.\n\n**Weaknesses**\n\n**1. Notations are heavy, confusing, and not easy to follow.**\n\nFor example, from Lines 115 to 121, there are multiple definitions for $q$. In addition, Lines 80-85 are a recap of previous work [24], and the notations are not necessary here. Moreover, some notations are not explained here, such as $c$ with arrows. \n\n**2. The writing is not clear.**\n\nThe authors should provide a clean algorithm or definition for the proposed prediction set. After the first read, I didn't know what the final prediction set is, not to mention the implementation.\n\n**3. Potential theoretical error.**\n\nIn Line 119, if $q$ is defined in Proposition 1, $P(S_{n+1} > q | E_+) \\ge 1-\\alpha$ seems wrong because given $E_1,...,E_{n+1}$, the quantile $q$ is not symmetric to $(X_1,Y_1),...,(X_{n+1},Y_{n+1})$.", "was_revised": true, "final_justification": "The authors have clarified that the error can be fixed.", "rebuttal": "We thank the reviewer for the constructive feedback. First we respond to the technical flaw, then we address other raised concerns and questions.\n\n**Potential Theoretical Error.** Thanks for pointing that out. Turns out the reviewer is right about the flaw in line 119, however since the conclusion is about coverage probability marginal over noise and data, the rest of the proof holds independently of this statement.\n\n*First - Example of why the reviewer is right:* Assume a one dimensional data x randomly in range of [0, 1], and the noise to be also uniform random from the same range. And the score to be S = X + E. Then one set of fixed $E_i$’s is $E_1 = 0, E_2 = 0.1, \\dots, E_{10} = 1$. From the definition of the score function the $1 - \\alpha$ quantile is the addition of the two quantiles over the X’s and E’s. While the quantile over X’s holds the same, the one over E’s introduces a bias since the noises are ordered, leaving the overall quantile inequality invalid. \n\n*Importantly the proof remains valid even without this argument.* This is intuitive assuming that the noises augmentation is a part of the model inference. Moreover, for other randomized score functions like APS the guarantee similarly holds over the marginalization of the noise. We refer to Chapter 9.1 of [2] showing the same argument applies for any randomised score function — a random noise augmentation of the input is essentially a randomised score function. In short, the 1 - alpha guarantee holds because noise-augmentation with i.i.d. noise is symmetric. The rest of the proof does not rely on the second half of the line 119. Thank you for pointing that out. In the next version, we’ll remove this part and the other occurrences of the same argument which is line 129 and the footnote in page 4. \n\n**Heavy and Hard-to-Understand Notations.** In light of the reviewer’s comment we found some typos that made it harder to read:\n\n- The first half of line 119: The equation is $\\Pr[\\hat{S}_{n+1} \\ge \\hat{q}] \\ge 1 - \\alpha$ for $\\hat{q} = ...$.\n- The first half of line 83: The equation is $\\mathcal{C} _{\\mathcal{B}}(\\boldsymbol{x} _{n+1}) = \\{y:s(\\tilde{\\boldsymbol{x}} _{n+1}, y) \\ge \\bar{q}\\}$.\n\nAlso regarding the notations $c^\\uparrow$, and $c^\\downarrow$, we adapted them from [24] and defined in line 81 as certified upperbounds and lowerbounds of the score, although we agree that it is necessary to bring the rigorous notation which says: $c^\\downarrow[f, x, \\mathcal{B}]$ is the certified lowerbound for function $f$ in $\\mathcal{B}(x)$. We’ll surely add modifications in the camera-ready version. If the reviewer has a concrete suggestion on how to improve the notation we would gladly consider it. We also try to reduce the quantity of the variables in a way that doesn’t affect the mathematical rigor.\n\n**Unclear Writing and Algorithm.** We agree that an algorithm would enhance the understandability of the paper. We ask the reviewers attention to the lines 51 to 54 where we discuss the high level implementation. In general the algorithm is exactly same as conventional CP, only with applying noise before computing the score functions and finding the upper bound $1 - \\alpha’$. We will add the following peudocode to the camera ready paper.\n\n**Algorithm 1: RCP1 – Single Sample Robust Conformal Prediction**\n\n---\n\n- **Input:** \n \nThe calibration set\n$\\mathcal{D} _{\\mathrm{cal}} = \\{(x _i, y _i)\\} _{i=1}^ n$\n\nThe score function\n$s: \\mathcal{X} \\times \\mathcal{Y} \\to \\mathbb{R}$\n  \nThe test point\n $x_{n+1}$,  \n \ntarget coverage level $1 - \\alpha$\n  \nperturbation ball $\\mathcal{B}_r$\n\nsmoothing scheme $\\xi$  \n\n- **Output:**  \n  $$\\mathcal{C} _r(x _{n+1}) \\subseteq \\mathcal{Y}$$\n\n1. **Step 1.** Draw noise from the smoothing scheme, compute conformity scores for augmented calibration data:  \n   ```text\n   for i = 1 to n do\n       \\epsilon_i ∼ \\xi  \n       s_i \\gets s(x_i + \\epsilon_i, y_i)\n   end for\n   ```\n\n2. **Step 2.**  \n   - Compute corrected level:  \n     $$1 - \\alpha' = c^{\\uparrow}[1 - \\alpha, \\mathcal{B}_r]$$\n   - Compute the $$ (1 - \\alpha') $$ quantile with correction:  \n     $$q \\leftarrow Q(\\alpha'; \\{s_1, \\dots, s_n\\})$$\n\n3. **Step 3.** Construct the prediction set for the test input:  \n   $$\\mathcal{C} _r(x _{n+1}) = \\{y \\in \\mathcal{Y} : s(x _{n+1} + \\epsilon _{n+1}, y) \\ge q\\}$$  \n\n4. **Return** $$\\mathcal{C} _r(x _{n+1})$$\n\n---\n\n**Questions:**\n\n1. It means if you do not apply any robustness guarantee, and use vanilla CP, only if instead of inference over $x$, we forward the model with $x + \\epsilon$, the resulting CP shows some robustness. This robustness means that the amount by which the empirical coverage deviates from the guarantee is significantly less than the case where we only apply the forward on $x$. As you see in Figure 1 - left, the dashed lines (which are CP without changing the quantile level) do not drastically drop as the red line drops.\n2. The proposed prediction set for the potentially perturbed $\\tilde{x}$ is $\\mathcal{C} _r(x _{n+1}) = \\{y \\in \\mathcal{Y} : s(x _{n+1} + \\epsilon _{n+1}, y) \\ge q\\}$, where   $q \\leftarrow Q(\\alpha'; \\{s_1, \\dots, s_n\\})$ with  $1 - \\alpha' = c^{\\uparrow}[1 - \\alpha, \\mathcal{B}_r]$. And here the guarantee is the same $1 - \\alpha$ for any worst-case adversarial perturbation up to radius $r$.\n3. The lower-bound in Prop 1 is not greater than $1 - \\alpha$. It is lower, but using the randomized smoothing (and in our case noise augmentation) helps us for this lower-bound not to get too deviated. For further clarification: we show that vanilla CP over noise augmented inference leads to a coverage guarantee $c^\\downarrow[1-\\alpha, \\mathcal{B}]$, which means that by calibrating to $c^\\uparrow[1-\\alpha, \\mathcal{B}]$ allows us to achieve $1 - \\alpha$ coverage. This is via lemma 3 in [24].\n4. It can be of any form, including the definition from [24] or our definition. The argument in line 108 is a generalised version of this argument: “if the clean point $x$ is covered by vanilla CP not accounting for perturbation radius $r$, then robust CP also covers the perturbed point $\\tilde{x}$. Notably there, the argument is 0/1 here we discuss that the argument should say that the robust prediction set $C_r$ has a higher probability to cover the perturbed point compared to the vanilla set $C_0$ for the clean point.\n\nOnce again we thank the reviewer for pointing out the mistake, we surely remove it from the proof, but nevertheless the proof holds even without that statement."}, {"review_id": "31KIqHSe1f", "reviewer": "Reviewer_p6ny", "summary": "The paper introduces RCP1, a robust conformal prediction method that overcomes the computational hurdles present in smoothing-based RCP approaches. By leveraging randomized smoothing, the proposed method achieves robustness against adversarial perturbations using only a single forward pass per input. The experiments are conducted on CIFAR-10 and ImageNet for classification and cityscapes for risk control settings.", "questions": "See above.", "limitations": "NA", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n- The paper aims to address the computational bottleneck in existing smoothing-based robust conformal prediction methods, which is well-motivated.\n\n- The integration of noise-augmented inference with robust conformal prediction offers an easy-to-implement solution.\n\n- The paper is well written.\n\nWeaknesses\n\n- The robustness guarantee in RCP1 is marginal over the randomness introduced by the smoothing process. Coverage is only guaranteed on average over the added noise, rather than under worst-case scenarios as in prior work. Specifically, the guarantee depends on the type of added noise (e.g., Gaussian perturbations), and does not hold uniformly across all inputs or perturbations. This also weakens the comparison with baselines that aim to certify worst-case robustness, potentially leading to unfair or misleading results.\n\n- The authors primarily focus on Gaussian smoothing, which limits the practicality of the approach, as real-world noise settings are often more complex and structured.\n\n- The study heavily builds upon prior work, making its theoretical contribution insufficiently novel.", "was_revised": true, "final_justification": "The reviewer is not fully convinced by the paper's technical assumptions as well as its theoretical novelty; also, some notations are hard to follow.", "rebuttal": "We thank the reviewer for reading our paper and for the comments. Here we discuss the raised weaknesses:\n\n1. The are two terms that should be distinguished: (1) the guarantee holds marginal over augmented noise. (2) The guarantee (marginal over noise) holds for the **worst case perturbation**. So here the noise is what the defender adds to any (including perturbed) input, the perturbation is what the adversary introduces to the clean data. Our guarantee holds marginal to the noise we introduce not the perturbations the adversary applies. This is a very important distinction of a certified worst-case robustness (ours) and an average-case robustness like [12] (in our references). We discussed this further in line 377. Formally for $\\tilde{x} = x +  \\delta$ we provide a guaranteed prediction set using $\\tilde{x} + \\epsilon = x + \\delta + \\epsilon$ which is marginal over $\\epsilon$ for the worst case $\\delta$. This means that our comparison with BinCP[24] is fair as we both target the same worst-case guarantee. Moreover, being marginal over random noise is not uncommon in the literature. For example the highly popular APS score function introduces uniform random noise, and there the 1-alpha guarantee is also only marginal over the introduced noise. See Chapter 9.1 in [add reference].\n\n1.  We draw the reviewer’s attention to Fig 2-right and Fig 5-right where we discuss noises other than isotropic Gaussian, specifically Laplace and Uniform noise. Indeed Section 3.1 modifies the result from Yang et al [22] to adapt RCP1 with smoothing of all shapes and sizes. RCP1 itself is independent to the noise type — any smoothing scheme, and threat model can be adapted to RCP1 for free.\n2. **In terms of result:** Existing worst-case CP guarantees are categorized into two main regimes: (1) smoothing based approaches which are robust for large radii while requiring may MC samples (computationally expensive), and (2) verification and Lipschitz based approaches which are efficient but only support very small radii. Our work is computationally efficient and works for large radii which is the first method which has both benefits.\n    \n    **In terms of theoretical novelty:** In order not to use MC sampling, we need to rely on the non-exact (probabilistic) setup which is unique to the case of conformal prediction — we can not apply the same method to have a certified top-class prediction. Similarly other methods did not need to prove that the certificate is convex. Notably, the proof that allows us to work with a single sample is completely orthogonal to the other smoothing based CP approaches, as they redefine the score function and show the score changes are bounded; that is basically why the need to estimate the score by MC sampling. Here we prove it by leveraging and lower bounding the coverage probability which is not needed to be estimated."}, {"review_id": "nb4ALu8Bqj", "reviewer": "Reviewer_vsiq", "summary": "The paper tackles the high computational cost of current smoothing‐based robust conformal prediction (RCP) methods and shows that in fact a single noise‐augmented inference suffices. Their key insight is to “certify the conformal procedure itself” rather than individual model scores: by applying any binary robustness certificate (e.g. Gaussian or Laplace smoothing bounds for ℓ₂ or ℓ₁ threats) directly to the coverage probability of the vanilla conformal predictor, one can adjust the calibration quantile to restore a 1–α worst‐case coverage guarantee. This yields **RCP1**, a black‐box, score‐agnostic method that needs only one perturbed forward pass per test point.\n\n**Contributions**\n\n1. **Method**: Introduce RCP1, which uses a single randomly perturbed sample plus an off‐the‐shelf binary certificate to attain robust coverage, eliminating the need for costly Monte Carlo sampling.\n2. **Generality**: Works with any model, any conformity score (classification or regression), and any smoothing/distributional threat model (Gaussian, Laplace, uniform; ℓ₂, ℓ₁, etc.).\n3. **Extension**: Show how to convert smoothing‐based RCP1 into a robust *conformal risk control* procedure, demonstrated on semantic segmentation (Cityscapes) to control false‐negative rate.\n4. **Empirical validation**: On CIFAR-10 and ImageNet with both ResNets and ViTs, RCP1 matches the set‐size vs. coverage trade-off of state-of-the-art methods like BinCP (which use 64–128 samples) while being orders of magnitude faster (one vs. ∼100 inferences) (Fig. 1-middle) and achieving the same 1–α robust coverage under adversarial attacks (Fig. 1-left).", "questions": "- typo in the equation below line 121\n- Another slight clarity issue is that the paper introduces many acronyms (CP, RCP, RCP1, BinCP, CAS, etc.) and shorthand notations for different methods. While it does define them (often by citing the relevant references), a concise table or summary of methods might have helped the reader keep track. That said, the authors do consistently remind the reader of what each baseline is (e.g. noting that BinCP uses p-quantiles or that CAS uses CDF information), which mitigates confusion. \n- The writing could have been further improved with a bit more exposition on the certificate calculations and perhaps by explicitly contrasting RCP1’s procedure with standard conformal prediction in a step-by-step manner. These are minor suggestions; the core ideas and results are still clearly conveyed.\n- The method is described as agnostic to the setup (classification vs. regression), but all experiments are on image classification. It would be valuable for the authors to discuss or demonstrate the applicability of RCP1 in other settings – for example, conformal prediction for regression tasks or other data modalities. Even a brief discussion or a toy experiment (perhaps in the appendix or supplemental material) showing how robust conformal prediction works for a regression problem would strengthen the paper’s claim of generality\n- The proposed RCP1 method relies on the availability of a “binary certification” for model predictions (for example, the paper uses randomized smoothing to certify robustness of a classifier). A question arises about how practical and general this requirement is. The authors should clarify to what extent RCP1 depends on a specific certification technique and whether any robust model certificate can be used interchangeably", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n- This paper proposes RCP1, a novel robust conformal prediction method that requires only a single model inference per input, yet still guarantees the desired coverage under worst-case perturbations. The theoretical contribution is solid – the authors prove that by adding one instance of random noise to each example (both in calibration and at test time) and leveraging a robustness certificate, the conformal coverage guarantee can be maintained even for an adversarially perturbed input. In particular, they choose a slightly more conservative nominal coverage level $1-\\alpha'$ such that the certified lower bound on coverage under perturbations is at least $1-\\alpha$. This key insight – “certify the conformal procedure itself rather than individual scores” – is innovative and allows RCP1 to inherit some robustness from even a single noise-augmented forward pass.\n- The paper provides formal propositions (e.g. Proposition 1) and defers detailed proofs to the appendix, indicating a rigorous theoretical underpinning. All assumptions and theoretical results appear to be clearly stated (per the checklist), lending credibility to the claims (thought I did not have time to check all the details - I have read in detail the proof of proposition 1).\n- Empirically, the evaluation is thorough and convincing. The authors test RCP1 on multiple datasets and models, including CIFAR-10 and the large-scale ImageNet with both ResNet and Vision Transformer backbones, as well as a challenging semantic segmentation task for conformal risk control. The experiments demonstrate that RCP1 achieves robust prediction sets of comparable size to state-of-the-art multi-sample methods while using dramatically less computation. For example, on ImageNet, RCP1’s average prediction set size is similar to that of the prior BinCP method when BinCP uses about 64–128 Monte Carlo samples per input. This is a remarkable improvement in efficiency – RCP1 attains essentially the same set size and coverage as BinCP with ~100 forward passes, using only one forward pass. The paper quantifies computational gains: for instance, processing 5000 ImageNet images with a ViT model takes ~2.8 minutes with RCP1 versus ~5.9 hours with an equivalent BinCP (128-sample) approach – a huge speedup that underscores the practical value of the method. \nWeaknesses: \n- One concern is that RCP1’s reliance on a single random draw per input introduces higher variance in the prediction sets. The authors acknowledge this limitation: “RCP1 shows considerably more randomness in the prediction sets compared to BinCP”, due to the inherently random one-sample procedure. In other words, the exact set of labels returned by RCP1 can vary across different runs (or different noise instantiations) on the same input, more so than methods that effectively average over many samples. While the coverage probability is still guaranteed in expectation, this increased variability might be undesirable in certain applications that demand deterministic or highly stable predictions.\n- the paper does cover a lot of technical ground, which can make certain portions dense. A reader not already acquainted with randomized smoothing certificates might find it challenging to parse the certificate optimization (Equation 4) and related discussion without consulting the appendix. The authors rely on references (e.g. to Yang et al. [22]) for some of the certificate details, which is appropriate, but it means that part of the argument is somewhat terse in the main text. For example, the statement “the optimization in Eq. 4 is translation invariant... we can use a fixed set of canonical directions” hints at non-trivial results from prior work that are not fully explained. Similarly, Section 3.1 briefly mentions how to compute certified probabilities $c_{\\downarrow}[p,B]$ for various smoothing schemes by “small changes” to Yang et al.’s recipe, which could be hard to grasp without familiarity with [22].\n- While the idea is novel, it builds heavily on prior work, and in some respects could be seen as an incremental improvement. The paper itself references BinCP (Zargarbashi & Bojchevski, ICLR 2025) as a state-of-the-art robust CP method that introduced the concept of using a “single binary certificate” to reduce sample complexity. In fact, the authors of this submission appear to be extending their own previous work (BinCP) – the terminology and some methodology overlap (e.g. use of Clopper-Pearson confidence intervals, references [23] and [24] which are prior methods by presumably the same group). From that standpoint, RCP1’s novelty is mainly in eliminating the remaining Monte Carlo sampling that BinCP still required.\n- -A final point is that the method’s correctness assumes access to a reliable robustness certificate for the base model (e.g. the ability to lower-bound the probability $P(f(x+\\epsilon)$ predicts class $y$) for all $\\epsilon$ in a perturbation ball). The approach is only as good as these certificates – if a model cannot be certified for a meaningful radius (or if the certificate probability $c_{\\downarrow}$ is too low), the resulting prediction sets could become trivially large.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for reading our paper and we are happy that the reviewer liked it.\n\n1. Thank you for pointing out the typos, surely we would modify it in the camera ready version.\n2. The reviewer is right. We should definitely add a section on a summary of how each prior method is functioning. We would definitely add that to the camera ready. We also agree that the paper is introducing many term and notations which makes it uneasy to read.\n3. Of course; we will add a section in the appendix with a brief discussion on how robustness certificates, and how CP work. Hopefully that would make the reading of the paper easier.\n4. Sure. We have discussed its adaptability to regression while showing something like that is definitely helpful in illustrating it. By the time of publication we did not find a good example of smoothing based regression on a large data. But for the camera ready we would try to add such experiment at least with a synthetic dataset. We also like to draw your attention to the image segmentation certificate in Figure 7 which uses single-sample robust conformal risk control.\n5. Indeed any smoothing-based certificate is directly applicable to both RCP1, and BinCP for free. If the reviewer refers to the more practical smoothing noises, we can use the recipe from [22] in combination prop 2. If the question is whether RCP1 adapts with other types of robustness guarantees including verifiers, it is not adaptable. But randomized smoothing shows to be very strong in terms of certifiable radii, and in our case efficiency of the set size. And since this method is model (and score) agnostic in can easily adapt to any machine learning model."}]

Author rebuttal:

Meta-review: This paper proposes RCP1 (Robust Conformal Prediction with one sample), a method that significantly reduces the computational overhead of robust conformal prediction. Standard RCP methods require many model evaluations per input, whereas RCP1 demonstrates that robustness can be certified with a single randomly perturbed input and a binary certificate. Empirically, RCP1 achieves smaller average prediction set sizes compared to state-of-the-art smoothing-based RCP methods, while reducing cost substantially.

After discussion, all reviewers lean towards acceptance, although the majority still consider that the paper remains borderline.

Strengths

* Novel methodological contribution with clear empirical benefits
* General approach, applicable to any conformity score

Weaknesses

* Writing is dense and presentation/notation is sometimes unclear
* An error was identified in one proof (acknowledged and satisfactorily addressed by the authors)

The authors provided clarifications on the proof, acknowledged typos, and committed to improving presentation. These corrections are expected to address most concerns.
Decision: Accept (poster)