Scaling Data-Driven Probabilistic Robustness Analysis for Semantic Segmentation Neural Networks
Authors: Navid Hashemi
Samuel Sasaki
Ipek Oguz
Meiyi Ma
Taylor T Johnson
Venue: NeurIPS 2025 poster ()
Keywords: Robustness Verification
Semantic Segmentation Neural Network
Reachability Analysis
Primary area: deep_learning

Abstract: Semantic segmentation neural networks (SSNs) are increasingly essential in high-stakes fields such as medical imaging, autonomous driving, and environmental monitoring, where robustness to input uncertainties and adversarial examples is crucial for ensuring safety and reliability. However, traditional probabilistic verification methods struggle to scale effectively with the size and depth of modern SSNs, especially when dealing with their high-dimensional, structured inputs/outputs. As the output dimension increases, these methods tend to become overly conservative, resulting in unnecessarily restrictive safety guarantees. In this work, we propose a probabilistic, data-driven verification algorithm that is architecture-agnostic and scalable, capable of handling the high-dimensional outputs of SSNs without introducing conservative and loose guarantees. We leverage efficient sampling-based reachability analysis to explore the space of possible outputs while maintaining computational feasibility. Our methodology is based on Conformal Inference (CI), which is known for its high data efficiency. However, CI tends to be overly conservative in high-dimensional spaces. To address this, in this paper, we introduce techniques to mitigate these sources of conservatism, enabling us to provide less conservative yet provable guarantees for SSNs. We validate our approach on large segmentation models applied to CamVid, OCTA-500 and Lung\_Segmentation, and Cityscapes datasets, showing that it can offer reliable safety guarantees while lowering the conservatism inherent in traditional methods. We also provide a public GitHub repository for this approach, to support reproducibility.

Scaling Data-Driven Probabilistic Robustness Analysis for Semantic Segmentation Neural Networks
Navid Hashemi Samuel Sasaki Ipek Oguz Meiyi Ma Taylor T. Johnson Department of Computer Science, Vanderbilt University, Nashville, TN 37235 (navid.hashemi. hashemi, samuel. sasaki, ipek. iguk. meiyi.ma, taylor. t joa.jiaoooooraaeerbb...e..e
Abstract
Semantic segmentation neural networks (SSNs) are increasingly essential in high- stakes fields such as medical imaging, autonomous driving, and environmental monitoring, where robustness to input uncertainties and adversarial examples is crucial for ensuring safety and reliability. However, traditional probabilistic verifi- cation methods struggle scale effectively with the size and depth of modern SSNs, especially when dealing with their high-dimensional, structured inputs/outputs. As the output dimension increases, these methods tend to become overly conservative, resulting in unnecessarily restrictive safety guarantees. In this work, we propose a probabilistic, data-driven verification algorithm that is architecture-agnosii and scalable, capable of handling the nigh-dimensional outputs of SSNs without intro- ducing conservative and loose guarantees. We leverage efficient sampling-based reachability analysis to explore the space of possible outputs while maintaining computational feasibility. Our methodology based on Conformal Inference (CI), which is known for its high data efficiency. However, CI tends to be overly con- servative high-dimensional spaces. To address this, in this paper, we introduce techniques to mitigate these sources of conservatism, enabling to provide less conservative yet provable guarantees for SSNs. We validate our approach on large segmentation models applied to Cid OCTA-500 and Lung Segmentation, and Cityscapes datasets, showing that it can offer reliable safety guarantees while lowering the conservatism inherent in traditional methods. We also provide public GitHub repository for this approach, to support reproducibility.
Introduction
Deep Neural Networks (DNNs) have demonstrated remarkable performance in numerous domains, including image classification, speech recognition, medical diagnosis, and autonomous systems. De- spite their widespread adoption, DNNs remain highly vulnerable to input perturbations and adversarial comnples-sublee changes inputs that can drastically alter network outputs. This vulnerability raises serious concerns, particularly for safety-critical applications such as autonomous driving, medical imaging, and robotics, where incorrect predictions may lead to catastrophic outcomes.
The study neural network robustness primarily falls into two categories: falsification-ban based methods, which focus discovering adversarial examples [Madry et al., 2017 Goodfellow et al.) 2014 Kurakin et al.] 2016), and verification-based methods, which aim formally certify network's robustness under certain input perturbations (Zhou al. 2024 Lemesle al. 2024 Wu et al. 2024). The former is useful for finding failure modes, but it lacks formal guarantees. On the other hand, the latter offers provable guarantees but often suffer from severe scalability limitations.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Reachability analysis malysis-computingg computing the set of all possible outputs of system given a bounded set of inputs-hat has emerged as powerful tool for robustness verification. In neural networks. it can characterize how input perturbations propagate through the network and impact the final prediction. Nonetheless, reachability analysis is computationally intractable for large-scale networks or high-dimensional outputs. For instance, semantic segmentation networks (SSNs), which output pixel-level class labels, are particularly challenging due to their high-dimensional output spaces and complex architectures, often involving layers like transposed convolutions, max-pooling, and dilated convolutions. Traditional reachability-bann methods struggle with such models, becoming overly conservative failing to scale.
To address these limitations, probabilistic verification offers a compelling alternative (Fischer et al., 2021 Anani et al. 2024 Hao et al. [2022] Marzari et al. 2024). Rather than verifying properties for all possible perturbations, it focuses on verifying them with high probability under given distribution of input uncertainty. Probabilistic methods can scale better and provide meaningful statistical guarantees, especially when exact bounds or Lipschitz constants are unavailable or overly conservative. However, existing probabilistic approaches also face significant challenges; they often struggle with nontrivial output specifications, and fail to scale to large and deep networks like those used in semantic segmentation. In this work, we propose scalable, architecture-agnosti and low- conservatism probabilistic verification algorithm and introduce it for verifying semantic segmentation neural networks. Our method does not rely on restrictive assumptions about network structure or layer types and is well-suited to nigh-dimensional output spaces.
Related Works
Probabilistic verification of Neural Networks. Neural networks extremely nonlinear. This poses significant challenges for establishing probabilistic guarantees. Unlike deterministic techniques, the probabilistic methods for classification task do not directly extend to segmentation tasks. A key obstacle arises from the use of the union bound which causes the guarantees to deteriorate rapidly in high-dimensional segmentation settings. prominent research direction in probabilistic verification is randomized smoothing, first introduced for classifiers [Cohen et al. [019] and later adapted to segmentation models [Fischer al., 2021]. with subsequent improvements in Anani iet al. [2024). Hao et al. [2022). More recently, conformal inference has also been explored as a way to provide probabilistic guarantees in classification tasks (Jeary et al. 2024]. In this work, we extend this line of research by applying conformal inference to the segmentation task. Although the guarantee formulation may differ, we numerically show that our method can significantly reduce the conservatism compared to existing SOTA on segmentation tasks.
Deterministic verification of Neural Networks. Deterministic verification of neural networks seeks to establish formal guarantees that a network's output satisfies a desired specification for all inputs within a certain set. This task has been approached through several established methods, including Duong et al. [2023], Katz et al. [2017). Anderson et al. 2022). Cheng et al.) [2017). [Tran et al. 2020a A large subset of these verification approaches can be interpreted within the broader scope of branch-and-bound
algorithms [Bunel et 2020). Leading tools in this category, such as or, B- CROWN [Zhou al. [. PyRAT [Lemesle et al. 2024), and Marabou [Wu et al. 2024], have shown strong performance in recent VNN-COMP challenges Brix et al. [2024]. Techniques like interval arithmetic [Cheng et al. 2017 Pulina and Tacchella 2010 are also popular in the literature.
Conformal Inference. Conformal Inference has been also used for verification in a variety of applications. For instance, Lindemann et al. [2033] /Zecchin et al. [2024] employ CI to guarantee safety in MPC control and Hashemi et al.
[2023] 2024] employs CI for reachability of stochastic
dynamical systems, see Lindemann et al. 2024 for recent survey article.
2 Preliminaries
Notations. Boldface symbols (X) represent sets, while calligraphic letters (X)) denote distributions. The expression x ~ X' indicates that the random variable x is drawn from the distribution X,, whereas
x X X means that æ is sampled from the set X according to X. A feedforward neural network with input dimension no. hidden layers of sizes mi....,7h ni, and output dimension N, using the ReLU
Pr [P A A A... ....AAA P. 1 - E (1 -Pr[P]])

---

activation function, is written as Ino. .i..... ny, N (ReUU). For an input tensor I' E R its vectorized form is given by vec(z) E IRo, where no nc x w h. We denote the Minkowski sum by @ and the ceiling operator by [æ:.. which returns the smallest integer greater than or equal to x E TR. Finally, an l ball with radius r E Re centered at x E R is denoted as (x)...
Semantic Segmentation Neural Networks A semantic segmentation neural network (SSN) is a nonlinear function that assigns a class label to each pixel x(i; in multichannel input image 2, producing a target class label mask(i,))
j) from a predefined set of classes L {1,2,...,44
SSN i E R hxxxxnc + mask EL* ixw
where h, w, and ne denote the height, width, and number of channels of the input image, respectively, and (i, E L...., h x I,..., w are pixel coordinates. In this paper, we denote the logits of SSNs by y E Axxxx,, where the target class label mask(i, is given by mask(t, )) = arg max J, IEL Here, we also define the function f R + R as a nonlinear map between the flattened images and the flattened logits. Formally,
vec(x) E R + vecly) E RR, no = h x w X nc, n = h x w L.
Conformal Inference Consider a collection of i.dd and positive scalar random variables M = {Ri Rg...., Rm J sampled from Rt D, where Ri < R2 < ... < Rm- Given new draw Rm+1 from the same distribution and a miscoverage level E (0, 1), conformal inference
et al. 2005) constructs prediction interval C(Rm+1) Pr[ Rm-1 E +()++1) 2 - In this paper, we refer to these scalar random variables as nonconformity scores and refer to M as the calibration dataset. To compute the threshold d, use the empirical distribution of nonconformity scores R, for E 1, 1.2...., m, and define a rank L := [m 1)( <) A valid choice for the threshold dl is then Re, the 8-th smallest element of the augmented set R1,.... Rm, 0o, as defined in (Tibshirani et al. 2019]. which yields the following marginal guarantee:
[0, d such that
Pr [Rm+1 S Re] 2 1
where the probability is over the joint randomness of both the calibration and test samples (Tibshirani let al. 2019 Vovk et al. 2005). The test sample Rm+1 typically refers to an unseen example drawn Trom the same distribution for which we aim to provide a coverage guarantee. In this paper, we also refer to this sample as the umseen, and denote it by Runseen
Given a sampled calibration dataset, the coverage level 5 Pr Rumseen < Re is itself random
variable following a Beta(f, m + - f) distribution |Angelopouoss and Bates 2021 The following equations shows the mean value and the variance of the beta distribution terms of m, E:
E m m+1
((m + 1-
E
Var [6]
(2)
(m 1)²(m 2)
that shows by appropriately tuning m and L, we can significantly reduce the variance Var(d], to achieve tighter bounds. For instance, when m 8000 and L = 7999, the variance of the corresponding Beta distribution is 3.123 x 10-8, which is extremely small.
However, to present this in a completely formal way, we only consider low variance scenarios (Var(ā) < 1) and we also include this source of uncertainty by reformulating this guarantee with double-step probabilistic guarantee. To include this uncertainty, we can utilize the cumulative density function, CDF, of beta distribution- function known the regularized incomplete beta function- and propose the following guarantee based on the definition of the CDF.
Pr Pr[ punseen < R4 | >> 1 - e }> 1 - betacdf m + -1
(3)
where betacdf m +1 11-6) E) the regularized incomplete beta function that characterized by the choice of m and é evaluated at point 81 = 1 -c. The one-step marginal guarantee in ( holds only when the rank set to é := [(m + 1) - <)]. However, as shown in Appendix A key advantage of the double-step probabilistic guarantee is its fiexibility: the strict relationship among m, l, and can be relaxed. Therefore, this paper, we focus on the double-step guarantee and do not enforce the constraint { = [(m + 1)(1 - e)7. Instead, tune E, and such that betacdf
3

---

becomes negligibly small. Henceforth, for any logical statement P(é. m) {true, false), defined over the syper-parameters m, S m, we refer to the double-step guarantee.
Pr| Pr[ P(e, m) ] }> - > betacdf
as the (e, e, m) guarantee and say the statement P(C, satisfies (e, C, m) guarantee. We also refer to c as the miseoverage level, 81 := 1-11-,, c, as the coverage level and 02 == betacdf (f, 1 f) the confidence of guarantee. Appendix provides a clarifying example on this topic.
Deterministic and Probabilistic Reachability Analysis on Neural Networks Given neural network f R0 IR and an input set I I", deterministic reachability analysis aims to construct a set (I) c IR" such that, æ E I implies f(x) E (I)
In contrast, probabilistic reachability analysis assumes distribution W over the input set I, denoted W x I, and for given miscoverage level e, proposes a set R2 (W) C IR such that
W x
Pr[f(x) E RG()) 2 -
(4)
In this paper, we detail how to compute a probabilistic reach set with miscoverage level and sampling distribution x X by constructing suitable calibration set M size m, and selecting an appropriate rank f. Therefore, to keep the terminologies consistent, we reformulate the probabilistic reach set in (4) using the (e, e, m) guarantee, and we denote it by (;W e, m). which satisfies
Pr[Pr [f(x) E RGW,; ;e, m)] 2 1 - 2 betabeddf
f).
Adversarial Examples and Robustness of SSNs An adversarial attack on an image involves perturbing the input using a set of noise images x+ ,., and corresponding coefficients
(A(1),... X(r)] These perturbations are applied through a parameterized function A A (+),
generating the adversarial image as:
(x) = (()a.!uie
(5)
We focus on evaluating the robustness of semantic segmentation networks (SSNs) under such adversarial settings, particularly under the unknown, bounded adversarial examples (2-ady E D where the coefficients in vector À are unknown but bounded within specified ranges, i.e., [ X] RT.
A pixel (i),j) is deemed attacked if it faces perturbation. is also considered robust if, for all ad- (z)) versarial examples, the predicted label remains unchanged: SAN(Ax. (xx),)x(())))(
SSN (i,
Consider another scenario where there exists perturbations such that the label at (i, changes. In this
the pixel is non-robust if for all perturbations have SSN A goii (i)) * (i.(
The pixel is also unknown if for some perturbations we have SSN A aptii (x) (t, = (i,
and for some other perturbations we have SSN pmoe (i, * SSN
(i,5)
To quantify robustness of SSN we consider two different metrics:
Robustness Value: The Robustness Value (RV) of network is the percentage of pixels that remain
robust under attack: RV 100 (Nrewest //ana//pppiikk pixees); where Npixels h x w.
Problem Formulation Let + SSN(x) denote semantic segmentation network:
Problem 1.
The task involves classifying every pixel x(i.j) into robust, non-robust, or unknown
categories with respect to adversarial samples adv W I, ensuring compliance with miscoverage level e under strong probabilistic guarantees.
We aim obtain the average robusiness value RVV across K test images (z), xxx evaluated against adversarial examples ady W I, ensuring validity under a miscoverage level e.
Problem 2.
Scaling Probabilistic Reachability Analysis on SSN with Strong Guarantees
Given a specific distribution x W I for sampling inputs x from the input set I, reasoning about the resulting output distribution y is infeasible due to the high degree of nonlincarity in

---

neural networks. As a result, providing probabilistic coverage guarantees over the network's output space becomes significant challenge. key advantage of conformal inference its distributional robustness- it produces valid guarantees that are robust to all family of distributions that can well represent the samples collected in the calibration dataset. This property makes conformal inference particularly well-suited for reachability analysis of neural networks, which are known for producing complex and often intractable output distributions.
However, a major challenge arises when applied to high-dimensional datasets: The scalar elements R in calibration dataset are defined over the outputs y ~ y and the space of all possible distributions ) that can udequately represent the calibration dataset is significantly larger in higher dimensions and thus conformal inference tends to be overly conservative. This poses a significant obstacle when applying CI to semantic segmentation networks (SSNs), which are known for producing extremely high-dimensional outputs. In this paper, we propose a novel learning- baaeid neural network reachability analysis method for SSNs, that leverages deflative principal component analysis (PCA) [Mackey, 2008] to address the dimensionality challenges inherent in conformal inference when applied to provide coverage guarantees on neural network with high dimensional outputs.
In this section, we present our reachability technique in an incremental manner to clearly illustrate both the contributions and the challenges involved in applying conformal inference to SSNs. We begin by introducing a naive baseline approach. then highlight its limitations on high -igeedimensional spaces. Subsequently, we describe the enhancements we propose to overcome these challenges, culminating in the final version of our reachability algorithm.
3.1 Naive Reachability Technique via Conformal Inference
The first step to find a probabilistic reachset on neural networks with conformal inference (CI) is to generate calibration dataset M of size and training dataset T of size t.
Generating train dataset. We sample different inputs araain . 1,2, .,.. from with any
distribution of interest, W' I, and compute their corresponding outputs vec(y)jam= -s [(ve(())()) This gives us the training dataset, T = { (z.) ( (ar2ain Irain ...... (1.
yt train }
Generating Calibration dataset. We sample the input dataset with m different inputs aealih, 2,2...., m from the distribution x W I and their corresponding set of outputs (ea(y, ((veca,(all)),, i) = 1, 1.2,.... m. This gives the input/output dataset IO {agqllih, )faalii), (agalih, 1/2 ) )...., ...... (I:mlii ym ) We next attempt use IO to compute suit- able nonconformity score, R E Rzg. To that end, inspired by recent work on using conformal inference in time-series [Cleaveland et al. 2024],
design the nonconformity scores fol- lows in Equation (6). This design provides us a hyper-rectanglular set. Assuming the output vec(y) = (vec(y) (1)...., (e)] RR, we propose, the nonconformity scores Realib as,
R.calib = max |Ivec( (1) - c(1) (vec(y - -d))) i= 1,,,,.... m (6)
where e E R" is the average of the members in the train dataset T, and for k = 1, 1, n, the normalization factor тı is proposed to normalize the elements of the random vectors |vec(y) cl which can also be obtained using the train dataset as,
Th max T" .axx ( |vec(>) (rain) c(k)),
c(kk)
where we set T" = 10 (Σ 1 (ec(), - c(k)) /nt, to avoid facing zero as our normalization factor. We then propose the calibration dataset as M = [Haallih, Realth, ..... Reallib ).
miin
The next step is to sort the nonconformity scores in M based on their magnitude. Without loss of generality let's assume Rtalib Rgalib < <... < Realih Given a new draw x unseen from the distribution
X and the architecture of the neural network, the output vec(y"nseeny f (vec(a: follows specific distribution. We call this distribution compute the nonconformity scores, the i.i.d random variables,
y. Furthermore given the map we proposed to
(y
unseen (1) c(1)
( unseen (n) - c(n)
R Runseen_ max
(7)
TI
5

---

inflating adopt another distribution where we call it R ~ D. Here R and the elements Ri R Re are all sampled from the distribution D. This means that we can apply conformal inference. Therefore, for the new draw Runseen given desired rank, l S m and desired miscoverage level 6, we can propose the following (c, E, m) guarantee.
Pr Pr[ Runseen <
Riplib
}> 1>1-c] <>>>>>>> betacdfi-c(E,
1)-
Following the definition in Equation 77. the logical statement Pi(e,m) = [Rumeen R is logically equivalent to
P2(l,m) = A [c(k) - Th Rg S vec(yyuseea (Ak) S c(k) + Rg
which defines a hyper-rectangular set as the reachset for any unseen output of the neural network generated by x W I. Since Pi (f, m) satisfies the (e, f, m) guarantee, this reachset also provides the same coverage guarantee on the unseen outputs of the neural network. Appendix C a clarifying example on this technique demonstrating that it is effective even on very deep neural networks. offering strong probabilistic guarantees with a reasonable number of required sampling. As the architecture of a deep neural network becomes more complex, the distribution of its output can exhibit increasingly intricate behavior. Conformal inference remains robust any output distribution that represents the calibration dataset, allowing it to handle such complexities reliably. However, the tightness of the reachset does not persist when the dimensionality of the network's 's output increases.
provides
The first issue is that the naive technique can only produce a hyper-rectangular reachset, that can be a significant source of conservative in high-dimensional spaces.
The second issue is that the space of distributions y that provide some distribution D which well represent the calibration dataset is significantly larger in high dimensional space.
3.2 From Rectangae Reachsets Generalized Zonotopic Representations
Starset [Bak and Duggirala 2017 is an extension of zonotopes that we utilize here to represent our probabilistic reachsets. Our approach to constructing a general starset as the reachset is based on approximating the original deep neural network f with a smaller and more computationally tractable ReLU network g 10 + R". The model g is trained on the training dataset T, which implies is valid only for inputs sampled from the set 1 The core idea is to apply deterministic reachability analysis to this simplified model using state-of-the-un art tools such as NNV [Tran et al.) 2020b), and then inflate its reach set to account for approximation error between f and its surrogate g. thereby obtaining a probabilistic reachset for the original model f with an (,,, guarantee.
Training the surrogate model g serves dual purpose: it not only provides better approximation for S. but also defines the shape of convex hull which when inflated serves tighter over- approximation of the probabilistic reachset of f. Once is trained, this convex shape can be computed as a starset via deterministic reachability via NNV toolbox. To inflate this surrogate reachset, we follow the procedure outlined in the naive technique (Section 3.T to generate a hyper- rectangle that bounds the prediction error with a provable (c, f, m) guarantee. In other words, we define q( q(ve((z)) f(vec(z)) g( g(vec(z)) and apply the naive technique on g( g(vec(x)) to compute its hyper-rectangular reachset with (c, f, m) guaranted") We refer to this hyper-rectangee sef.
In conclusion, if we denote the deterministic reachset of surrogate model the starset R,y().
IEI + g( (z)) E (I) x
and for some parameers (e, m) and distribution W I, the (e, guaranteed probabilistic reachset for prediction errors by R2:W: m).
x I Pr Pr[ ((vec(x)) E R 2.m) 1 - > 1 - betacdf m + E).
II' the set I is very small, linear map can be used as alternative to the surrogate model 9. since the input/output relationship of f becomes easier to approximate in such cases. 'The naive technique can be viewed as simplified version of the surrogate- based technique. where the training dataset is approximated by simple average computation, (g(vec(z)) c, R1 = {c} )

---

Algorithm 1: Learning-Basee Principal Component Analysis through Deflation Algorithm
Initialize 21 22,
< ve vec(y2 (
vec(y! - [].
for index 0, o.1,,..,AN
do // Train the principal direction using stochastic gradient ascent
Gindex
f arg max
: E a 2z32
s.t. |d]2= =1
Aappend((ndde)
// collect the principal direction in A
J (āindex) I then
L break
1/ Stop if the variance falls below threshold.
// Update the dataset by component removal along principal direction.
21, ... - 21 (oi Øindex: [0 22 @index: .... (d Rt Tindex
then the probabilistic reachset of the model f with the same (e, (,),m) guarantee is obtainable by (WW; = R, (I) @ (WW; E, m),. where denotes the Minkowski sum,
I Pr Pr( f(vec(z)) (. }> 1 - ] betacdf m C).
This technique offers two key improvements over the naive approach presented in Section 3.1
The reachset no longer constrained to hyper-rectangle, eliminating the first source of conser- vatism inherent in the naive method.
The calibration dataset is now defined using prediction emror rather than the network's 's raw outputs. Since prediction errors are typically much smaller magnitude than the outputs of model f. this significantly reduces the conservatism of conformal inference in high-dimensional spaces.
Despite the improvements introduced in this section, the reachability analysis remains unscalable in high-dimensional settings. The core challenge that training the surrogate model g-even when kept relatively small-ofter fails to converge its loss function to good solution due to the high dimensionality of the output space. This implies that the magnitude of the prediction errors may not remain small relative to the output of the neural network. To mitigate this, we incorporate scalable version of Principal Component Analysis (PCA), known as deflation algorithm, during the training process for g. technique known to be effective for handling PCA in high- sigh-dimensional spaces. The next section provides a detailed explanation of this enhancement.
3.3 Training the Surrogate Model for SSNs via Principal Component Analyis
In this section, we present our methodologies to mitigate the dimensionality challenges to train the surrogate model g R0 + RR, and present our technique for the robustness analysis SSNs.
In our robustness analysis of SSNs, as indicated by equation (5). adversarial perturbations are confined an r-dimensional subspace of the input space, with r < ng. Although input images are high-dimensional, the perturbations are not. Thus, we reformulate the surrogate g'(A) R + R"
g' (A) = g( vec( x + Σ A(i)a )) g ( and AE A X C CR,
1=1
and also the deterministic reachset Rg (I) based on the vector as R. (L,, A)) R. (I).
Diggs-Dimensionalityy of Output Space. To address this challenge, we divide the training process into two separate stages i.e., for choice of N & n, train for two models 91 R - R" and 82 Rº + RN and we define g' (A) = 91 (g2 (A)). The first stage trains 91 and operates in a high-dimensional space; however, it is free of local optima, which ensures convergence to global solution. The second stage trains the model f22 within a non-convex optimization, but it operates in a low-dimensional space, making it easier converge good solution.
The first stage performs dimensionality reduction. Let's sample training images =.iiin, for j L. t, from the adversarial set I, using sampling the coefficient vectors M form [A, AJ. Then the
7

---

corresponding logits ") form a point cloud in R This stage aims to train the top N principal directions of cloud, which are stored columns of the matrix A (āo: á₁ .... ax-1] E R
We utilize this matrix to represent the high dimensional logits s/ with a lower dimensional representative v. E RN where v/ = AA" ve Principal Component Analysis is a technique to reduce the dimensionality, but it does not scale to high dimensional spaces. To address this issue, deflation algorithms have been proposed (see Algorithm|] [ that compute principal components iteratively, in order of significance [Mackey] 2008]. At each iteration, once the most dominant principal component is identified. the dataset is projected onto the orthogonal complement of that direction-eefecctiveee removing its cnurribttionbeforre computing the next principal direction.
In this paper, we adopt a learning based deflation algorithm that is presented in Algorithm || In this algorithm we set the components of the principal direction as trainable parameters and maximize the variance of the dataset in the direction of this vector. At each iteration of this algorithm, the optimization to train the principal direction have one global maxima one global minima and n saddle points, which n is the dimension of logits vec(y) (rai |Mackey| 2008 Therefore, although the training operates in a high-dimensional space, convergence global maxima is guaranteed.
The second stage trains a relatively small RcLU neural network 92 between the coefficient vectors Alain and the low dimensional representatives of logit jj: I,..., L. This optimization operates in a low-dimensional space and can converge to a good solution. In conclusion we present the surrogate model for ʃ as g(x"d)) g (A) (A) which is a scalable choice for SSNs.
Detecting Robust, Non-robust and Unknown Pixels with Strong Probabilistic Guarantees Once the reachset over the SSN logits y E II" is constructed as a starset, we project it onto each logit component. This allows us to determine the range of values for each class label / E L at every pixel location (i.j) E (I,...,hh
h x {I,..., w. Consequently, each pixel (i, is associated with L logit
intervals, one for each class. Let 1" E L denote the class whose logit interval has the highest lower bound at pixel ji. If this lower bound is not strictly greater than the upper bounds of all other classes' intervals, the pixel is labeled as unknown as it can obtain more than one labels under UBAA. In case it is greater, then if (* (i. the prediction that pixel labeled as robust and if 1* + (z)(()) it is labeled as non-robust. The Algorithm 2 explains this procedure in detail.
4 Experiments
In our numerical evaluation, we pose four different research questions and address each of them using numerical results. The main RQs are available in this section and the rest of them are in Appendix G We utilized Linux machine, with 48 GB of GPU memory, 512 GB of RAM, and 112 CPUs.
How Does the Performance of our Methodology Compare to Existing Probabilistic Verification Methods for Neural Networks in the Literature? In this section, we present
RQI:
comparison with the works Fischer et al. [2021), Anani et al. 2024) on the Cityscapes dataset
[Cordts al., 2016). Since the formulation of verification guarantees differs slightly across these
approaches, we first provide general overview of the techniques proposed in Fischer et al. [2021] Anani al. [2024), followed by brief deseription of our own method in Appendix D This will clarify how the comparison can be meaningfully established.
Comparison. The unknown pixels in our method conceptually equivalent to the abstained pixels in Fischer et al. [2021]. Anani et al. [2024]. Thus, given the same input set (,) where is provided by Fischer al. 2021]. the comparison focuses to show which technique results in fewer uncertifiable mask pixels. To this end, we replicate the setup of Table 1 from Anani et al. 20244,, using the same HnNetV2 model [Wang et al.) traineed on the Cityscapes dataset with the V2-Net backbond Our findings are summarized in Table I which shows the average over 200 test images. Please note that the much lower rate of unknown mask pixels reported for our
'This model is considered large with 65,859,379 parameters, an input space of dimension 1024 x 2048 x 3 and output space of dimension 256 x 512 19
8

---

Table 1: Percentage of uncertifiable pixels under different (o, K. settings for Fischer al. [2021].
Anani et al. [2024], and our Naive approaches. Here 62 = 0.999 in all experiments. See Appendix [ for additional details on the parameters (a, K; r). Our verification runtime is 210 seconds, and we set
51 0.99 and W to be uniform distribution, for all our CI based experiments.
Fiiccerr
2021 (+)
Anani al.
2024
(%)
Ours (%)
0.25
0.75
0.1686
0.0642
0.33
0.75
0.2226
10
0.0676
0.50
0.75
0.3372
15
0.0705
0.25
0.95
0,4112
12
9
0.0727
0.33
0.95
0,5428
22
18
0.0732
0.50
0.95
0.0758
Table 2: Illustrates the model configurations and probabilistic guarantees. For each experiment,
given hyperparameters m, and coverage 81 1 e, the confidence 82 is computed. The reported verification runtime is averaged over all experiments and mainly depends on inference time and
hyperparameters (f, m), with minor sensitivity perturbation magnitude and dimension (e, r)-
Per-experiment runtimes are shown in Figure of Appendix G
Dataset
Model
Input dimension
Ousput
Number of
E
coverage
confidence
Average
name
dimcasion
Parameters
runtime
MENIST
minist de
64x x1
64x84 x11
6,788 107
(1ea, 11
0.9999
0.9095
5.4 minutes
M2NIST
m2nist,
64x 84
64x84 x11
4,579.723
(1e5.
0.9999
0.9995
3.8 minutes
M2NIST
m2nist ap ie
64x84
64x84 x11
11.664,779
(165. 1)
0,9999
0.9995
4.4 minutes
Lung Segmentation
UNetl
512x 512x
512x512x1
14,779,841
(8e3. 1]
0.999
0.997
4 minutes
OCTA 500
104x304x1
5,478,785
0.997
3.75 minutes
CamVid
BiSeNet
720x960x3
720x960
12,511,081
(863,
0.999
0.997
9 minutes
method stems from considering prior distribution. Thus we do not view this an advantage, but rather as part of a trade-off between the two approaches, not a sign of superiority
RQ2 (1st Ablation Study): How does the technique scale with model size, number of perturbed pixels, and perturbation level? To assess scalability, we test our surrogate- based verification method on an r-dimensional darkening adversary (see Figure []. where r' pixels in an image x with intensity above 150/255 in all channels are randomly selected for perturbation (r = nc x r'). Each direction a:poise corresponds to darkening channel of one such pixel, and 2 is parameterized by an r-dimensional coefficient vector À [A, A]. Here, λ induces full darkening (intensity zero), while A applics partial darkening. This bound defines the perturbation space add E I. The main motivation for this choice of threat model is that it offers greater flexibility adjust the sparsity and magnitude of perturbations, allowing for a more thorough and detailed evaluation of our method's performance.
Per request of RQ2, in these experiments, we studied high- ligh--imensional datasets (e.g., Lung Segmenta- tion [Jaeger et al. 2014, Candemir et al.) 2014), OCTA-500 (Li et al. 2019], Cam [Brostow et al.) 2009] using large pre-trained models. We evaluate performance on a subset of 200 test images across varying perturbation dimensions and magnitudes, with results shown in Figure 2 Model details and probabilistic guarantees are summarized in Table where we show the following (e, (.) guarantee:
Pr [Pr P] 2 51 2 82, where P = Given an image z, the perturbation magnitude and dimension e, P. the computed robustness value RV from our technique is valid.
We also present a demo for the status of all pixels in the segmentation mask in Figures
and
To assess the conservatism, we examine the projection bounds [y. y] introduced in Algorithm Specifically, we sample 10th adversarial examples from nd X I and use them to report:
Empirical miscoverage é, that is the percentage of events, where (x) $ [y. V).
Empirical bound G M via component-vv minima/maxima of [(vee(x across samples.
The degree of conservatism can assessed by comparing [ú. T with [v. T). To visualize it, we plot, bound_ bound_ratiockk) (0(k) j(k)) (T(() - y(k)), k == 1,...,, h w xwwk L
for logit components in Figure ( (Appendix E as histogram. Since 10t inferences is costly, we study the conservatism on three cases from Figure spanning our smallest to largest configurations.
'Compared to our approach, techniques based on randomized smoothing have the advantage of providing guarantees without assuming any prior distribution. The downside, however, is that their guarantees are derived for an approximate version of the model that implicitly assumes prior Gaussian distribution (see Appendix D)

---

Algorithm 2: Detection of the pixel status
Input: I, x. f. W, c, Plyper-parameters. m) Output: The status of pixels
1/ Project the Starset
[y- R,,,e,
foreach (1.5) E {1:h} (1:w) do
1" + arg max; 1,)
Figure 1: Illustration of the perturbation set I associated with an r-dimensional darkening adversary applied to image x. The set is con- structed by applying independent perturbations all nc channels across r' selected pixels (r nc X r'), each having R, G, and B intensities above 150/255. The lower bound LB corre- sponds to the maximum darkening case (channel intensities set zero), whereas the upper bound UB represents the minimum darkening limit.
if (*) V maxi 7(i.j, then
Label pixel (i,j) as unknown
else if 1 (2)(())(1,) then
Label pixel (i, j) as robust
else
Label pixel (f non-robust
return Pixel-wise labeling
344
144
Figure 2: Shows RV versus perturbation level (top row) and perturbation dimension r (bottom
row). In the top row, r 102 x 3 for Cam 102 x for Lung Segmentation and OCTA-500, and 17 x 1 for M2NIST experiment. In the bottom row, e is fixed at 3/255 across all experiments. The average robustness value RV is averaged over 200 test images.
5 Limitations, Future Works & Conclusion
Limitation. The first limitation of our technique is the assumption of prior distribution W, which may not hold in all deployment scenarios. However, this issue can be addressed at low cost by replacing CI with robust-CI [Cauchois et al. 2024], which preserves our guarantees even when the deployment distribution shifts within a known -ddivergence ball [Cauchois et al. 2024 The second limitation of our technique is the need to recompute the calibration set for each test point, which accounts for the majority of the computation time in approach. Finally, while replacing the naive technique with the surrogate-base based technique improves accuracy, it also introduces some brawbacks. It increases runtime, it requires performing PCA, training, and deterministic reachability analysis, and it also limits scalability with respect to input dimensionality, since higher-dimensionall settings make both training and deterministic reachability more challenging. Therefore, in cases where the perturbation dimension is very large, we fall back to the naïve technique for scalability.
Future Work. The main advantage of the surrogate-based technique is that its guarantees also capture the interrelations among mask pixels, offering the potential to verify spatial specifications over SSNs-an aspect not emphasized in this work. In addition, incorporating robust-CI can address the issue of distribution shift in deployment settings. Therefore, we consider and explore both of these mentioned extensions in our future research this topic.
Conclusion. We do not provide deterministic guarantees, and our reachable set remains susceptible to violations; however, it offers provable probabilistic assurances, evidenced in Appendix F Despite this limitation, our approach is both scalable and data-efficient, delivering meaningful safety assurances in regions where existing deterministic methods are computationally infeasible. We demonstrated these capabilities through a series of numerical experiments presented this paper.
10

---

6 Acknowledgement
This material is based upon work supported by internal funding from Vanderbilt University for medical imaging research and the National Science Foundation (NSF) under Award Numbers FMitF- 2220401, 2220426, and 2443803. Any opinions, findings, and conclusions recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of Vanderbilt or NSF.
References
Alaa Anani, Tobias Lorenz, Bernt Schiele, and Mario Fritz. Adaptive hierarchical certification for segmentation using randomized smoothing. arXiv preprint (.XXi:24402.8-0000 2024.
Ross Anderson, Joey Huchette, Will Ma. Christian Tjandraatmadja, and Juan Pablo Vielma. Strong mixed-integer programming formulations for trained neural networks. Mathematical Programming, 183(1):3-39, 2020.
Anastasios N Angelopoulos and Stephen Bates. A gentle introduction to conformal prediction and distribution-fri uncertainty quantification. arXiv preprint arXiv:2107.07511 2021.
Stanley Bak and Parasara Sridhar Duggirala. Simulation-cquivalees reachability of large linear systems with inputs, In International Conference on Computer Aided Verification, pages 401-420. Springer, 2017.
Christopher Brix, Stanley Bak, Taylor T Johnson, and Haoze Wu. The fifth international verifi- cation of neural networks competition (vnn-comp 2024): Summary and results. arXiv preprint arXiv:2412.19985 2024.
Gabriel J. Brostow, Julien Fauqueur, and Roberto Cipolla. Semantic object classes in video: A high- definition ground truth database. Pattern Recognition Letters, 30(2):88 97, 2009. ISSN 0167-8655. doi: https://doi.orr/1000/ wr. wttp::/0.........e.0......... p0000c 005. httpss:ss:// / /www. sciencedirect. com/ Video-based Object and Event Analysis.
Rudy Bunel, Jingyue Lu, Ilker Turkaslan, Philip HS Torr, Pushmeet Kohli, and M Pawan Kumar. Branch and bound for piecewise linear neural network verification. Journal of Machine Learning Research, 21(4):1139, 2020.
Sema Candemir, Stefan Jaeger, Kannappan Palaniappan, Jonathan P Musco, Rahul K Singh, Zhiyun Xue, Alexandros Karargyris, Sameer Antani, George Thoma, and Clement McDonald. Lung segmentation in chest radiographs using anatomical atlases with nonrigid registration. IEEE Trans. Med. Imaging, 33(2):577-590, February 2014.
Maxime Cauchois, Suyash Gupta, Alnur Ali, and John Duchi. Robust validation: Confident predictions even when distributions shift. Journal of the American Statistical Association, pages 1-66, 2024.
BONFERRONI CE. Pubblicazioni del instituto superiore di scienze economiche commerciali di firenze. Teoria statistica delle classi ecalcolo delle probabilità, 8:3-62, 1936.
Chih-Hong Cheng, Georg Nührenberg, and Harald Ruess. Maximum resilience artificial neural networks. In Automated Technology for Verification and Analysis: 15th International Symposium, ATVA 2017, Pune, India, October 3-6. 2017, Proceedings 15, pages 251-268. Springer, 2017.
Matthew Cleaveland, Insup Lee, George Pappas, and Lars Lindemann. Conformal prediction regions for time series using linear complementarity programming. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 20984 -29922, 2024.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In international conference on machine learning, pages 1310-1320. PMLR, 2019.
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 Proceedings of the IEF.E conference on computer vision and pattern recognition, pages 3213-3223, 2016.

---

Herbert A David and Haikady N Nagaraja. Order statistics. John Wiley & Sons, 2004.
Hai Duong, Vu Nguyen, and Matthew Dwyer. A dpll (1) framework for verifying deep neural networks. arXiv preprini urXiv:2307.10266 2023.
Mirko Fiacchini and Teodoro Alamo. Probabilistic reachable and invariant sets for linear systems with correlated disturbance. Automatica, 132: 109808, 2021.
Marc Fischer, Maximilian Baader, and Martin Vechev. Scalable certified segmentation via randomized smoothing. International Conference on Machine Learning, pages 3340-3351. PMLR, 2021.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6577 2014.
Zhongkai Hao, Chengyang Ying. Yinpeng Dong, Hang Su, Jian Song, and Jun Zhu. Gsmooth: Certified robustness against semantic transformations via generalized randomized smoothing. In International Conference on Machine Learning, pages 8465-8483, PMLR, 2022.
Navid Hashemi, Xin Qin, Lars Lindemann, and Jyotirmoy V Deshmukh. Data-driven reachability analysis of stochastic dynamical systems with conformal inference. In Proc. of CDC, pages 3102-3109, 2023.
Navid Hashemi, Lars Lindemann, and Jyotirmoy V Deshmukh. Statistical reachability analysis of stochastic cyber-physical systems under distribution shift. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 43(11):4250 4261, 2024.
Sture Holm. A simple sequentially rejective multiple test procedure. Scandinavian journal of statistics, pages 65-70, 1979.
Stefan Jaeger, Alexandros Karargyris, Sema Candemir, Les Folio, Jenifer Siegelman, Fiona Callaghan, Zhiyun Xue, Kannappan Palaniappan, Rahul Singh, Sameer Antani, George Thoma, Yi-Xiang Wang, Pu-Xuan Lu, and Clement J McDonald. Automatic tuberculosis screening using chest radiographs. IEEE Trans. Med. Imaging, 33(2):233-245, February 2014.
Linus Jeary, Tom Kuipers, Mehran Hosseini, and Nicola Paoletti. Verifiably robust conformal prediction. Advances in Neural Information Processing Systems, 37:4295 4314, 2024.
Guy Katz, Clark Barrett, David Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In Computer Aided Verification: 29th International Conference, CAV 2017, Heidelberg, Germany, July 24-28, 2017, Proceedings, Part 30, pages 97-117. Springer, 2017.
Alexey Kurakin, lan Goodfellow, and Samy Bengio. Adversarial machine learning at scale. arXiv preprint 161:::/611.0055::: 2016.
Augustin Lemesle, Julien Lehmann, and Tristan Le Gall. Neural network verification with pyrat. arXiv preprint arXhv:2410.23900 2024.
Mingchao Li, Songtao Yuan, and Qiang Chen. Octa-500, 2019. /tt.
1016/j media. 2024. 103092
Lars Lindemann, Matthew Cleaveland, Gihyun Shim, and George Pappas. Safe planning dynamic environments using conformal prediction. IEEE Robotics and Automation Letters, 2023.
Lars Lindemann, Yiqi Zhao, Xinyi Yu, George J Pappas, and Jyotirmoy V Deshmukh. Formal verification and control with conformal prediction. arXiv preprins arXiv:2409.005366 2024.
Lester Mackey. Deflation methods for sparse pea. Advances in neural information processing systems, 21, 2008.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: I 1706 06083, 2017.
12

---

Luca Marzari, Davide Corsi, Enrico Marchesini, Alessandro Farinelli, and Ferdinando Cicalese. Enumerating safe regions in deep neural networks with provable probabilistic guarantees. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 21387-21394, 2024.
Luca Pulina and Armando Tacchella. An abstraction-refinemen approach to verification of artificial neural networks. In Computer Aided Verification: 22nd International Conference, CAV 2010, Edinburgh, UK, July 15-19, 2010. Proceedings 22, pages 243-257. Springer, 2010.
Ryan J Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal prediction under covariate shift. Advances in neural information processing systems, 32, 2019.
Hoang-Dune Duang Tran, Stanley Bak, Weiming Xiang, and Taylor Johnson. Verification of deep convolutional neural networks using imagestars. In International conference on computer aided verification, pages 18 42. Springer, 2020a.
Hoang-Dung Tran, Xiaodong Yang. Diego Manzanas Lopez, Patrick Musau, Luan Viet Nguyen, Weiming Xiang, Stanley Bak, and Taylor T Johnson. Nnv: the neural network verification tool for deep neural networks and learning-enablee cyber-physical systems. In Proc. of CAV, pages 3-17, 2020b.
Hloan--Dung Tran, Neelanjana Pal, Patrick Musau, Diego Manzanas Lopez, Nathaniel Hamilton, Xiaodong Yang, Stanley Bak, and Taylor T Johnson. Robustness verification of semantic segmen- tation neural networks using relaxed reachability. In International conference computer aided verification, pages 263-286. Springer, 2021.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in random world, volume 29, Springer, 2005.
Jingdong Wang, Ke Sun, Tianheng Cheng, Borui Jiang, Chaorui Deng, Yang Zhao, Dong Liu, Yadong Mu, Mingkui Tan, Xinggang Wang, et al. Deep high-resolution representation learning for visual recognition. IFEE transactions on pattern analysis and machine intelligence, 43(10):3349-3366 2020.
Haoze Wu, Omri Isac, Aleksandar Zeljié, Teruhiro Tagomori, Matthew Daggitt, Wen Kokke, Idan Refaeli, Guy Amir, Kyle Julian, Shahaf Bassan, et al. Marabou 2.0: a versatile formal analyzer of neural networks. In International Conference Computer Aided Verification, pages 249-264. Springer, 2024.
Matteo Zecchin, Sangwoo Park, and Osvaldo Simeone. Forking uncertainties: Reliable prediction and model predictive control with sequence models via conformal risk control. IEEE Journal on Selected Areas in Information Theory, 2024.
Duo Zhou, Christopher Brix, Grani A Hanasusanto, and Huan Zhang. Scalable neural network verification with branch-and-bong bound inferred cutting planes. arXiv preprint arXiv:2501.0020 002000, 2024.
13

---

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]
We propose new method that is more scalable and less conservative than existing techniques for verifying semantic segmentation neural networks. We build up the paper with theoretical contributions regarding our method throughout sections 2 and 3 and address the claims in the abstractiintroduction through research questions and corresponding experiments for those research questions described in section 4.
Justification:
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 can be expected to generalize other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Generally, we our work directly discusses the limitations of probabilistic verification techniques and using conformal inference specifically. Developing the final algorithm was also iterative approach. We build up the theory and describe the naive ap- proach, its limitations, and then proceed to describe how we addressed those limitations. We additionally recognize the shortcomings of our method being unable to provide formal guarantees like some other existing verification methods can, but at the cost of scalability.
probabilistic method, therefore
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 a separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on 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 few datasets with 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 is low images are taken in low lighting. Or speech-to-text system might not 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 seale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
14

---

While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren'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 theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
For our proposed method, we rely on the application of conformal inference. We acknowledge the necessity of the samples being i..d. for method to work. Additionally, we provide complete proofs for conformal inference in the preliminaries.
Justification:
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but 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 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 to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We describe in detail the theory relevant to the proposed method. Additionally, Algorithm aand Algorithm 2 provide detailed pseudocode for reproducing the proposed
method.
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 to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are 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.
15

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is 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 welcome describe 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: At submission, we are not providing open access to the data or code. Through- out the paper, we provide sufficient references to the datasets and models being used, as well as pseudocode for reproducing our algorithm.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co 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 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 for more details.
/ /nnps.cc/ppblll wttpc//pwwccgguuuueeeeeeeep
SondeSubmissiinnoolccc
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 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 (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper does not focus on new architecture, optimizer, training strategy, but we still provide details in (labll the models used such as number of parameters, input shape, output shape, etc. In Section 4, we provide a breakdown of each experiment, the datasets being used, the models being verified, what variables are being controlled for the specific experiment, and other details.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
16

---

The full details can be provided either with the code, in appendix, or as supplemental
material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
The proposed method in our paper is rooted in the probabilistic guarantees that we show through theoretical contributions or that have been shown from other works. We do not provide error bars or confidence intervals on our results.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
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, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should 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 1-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 out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
The first paragraph of Section describes the kinds compute that was available for running the experiments. It includes details such number of CPU cores, RAM, GPUs and GPU memory.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount 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 ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
17

---

Our method cannot be used in a way that is harmful as it is technique for verifying neural networks rather than performing some task using neural network. We do not violate any of the rules with regards to data being used in our experiments as well.
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration 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: [Yes]
Justification: Positive societal impacts are discussed as applying the proposed method is useful for having trust when applying neural networks in safety-critical systems. However, because the method is only for verifying neural networks, the proposed technique cannot be used in a way that is harmful. We do, however, acknowledge throughout the paper that our method is probabilistic, which is shortcoming particularly when verifying NNs used in safety-critical systems.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeet 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an 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 a 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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to 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]
The models used in this work do not fall under the described criteria and we have not used scraped datasets. Our method also is not concerned with describing new model architecture that could be potentially harmful.
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
18

---

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 are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All sources (datasets, models) are properly cited and licenses properly re- spected.
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 or dataset.
The authors should state which version of the asset is used and, if 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.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset'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]
We do not release new assets. The code and data are not released as part of the submission.
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was 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. Crowdsourcing and research with human subjects
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)?
Question:
Answer: [NA]
19

---

Justification: As described below, 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 NeurlPS 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/teview based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: As described below, the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor 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.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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 the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality the research, declaration is not required.
Answer: [NA]
Justification: As described below, the core method described in the paper does not involve L. as any important, original, or non-standard component.
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 htt////ripps.cccmmffeeeeeeeeeeee wttpc//feeeencc///225/////////// for what should or should be described.
20

---

A Double-Step Probabilistic Guarantee
The necessary steps to establish the two-sided probabilistic guarantee, along with the flexibility in choosing the dataset size m, rank L, and failure probability c, begin with the theory of order statistics [David and Nagaraja [004]. This flexibility means that the double-step probability constraint remains valid regardless of the particular values chosen for m, S m, and E [0, 1]. The following lemma introduces the concept of order statistics.
Lemma A.1 (From David and Nagaraja 2004]) Consider independent and identically dis- tributed (L..d.), real-valued data points [0,1] drawn from uniform distribution x U. Sup- pose we sort them ascending order and denote the 8th smallest number by veliiee we have Iı < I2 .... < Tm). Let Beta(a, 3) denote the Beta distribution" Then the uniform random variable at rank E follows:
xt Beta(E, m 1-
In the context of conformal inference Lemma A.1 has been extended from a uniform and domain- bounded distribution to general distribution follows:
Lemma A.2 (From Vovk et (2005) Consider m independent and identically distributed (i.i.d.), real-valued data points R. drawn from some distribution R ~ D. Suppose we sort them in ascending order and denote the gth smallest number by Ra, (i.e., we have R₁ <. Rn ... Rm). Let
Beta(o, (3 denote the Beta distribution. Then, for an arbitrary Rm+t1 drawn from the same distribution D, the following holds:
Pr Bm < RR] Beta(f, m m1 1S85 m.
(8)
This result is motivated by two key observations: (1) for continuous distribution ~ D, the cumulative probability Pr[R < r] is uniformly distributed on [0, and (2) sorting the samples R1 < Rg <... < Rm implies that the corresponding cumulative probabilities Pr(R S R&] are also ordered, i... Pr[R S R1] < Pr[R R S R2] ... Pr[R < Rm.] These observations implies that for all f 0, 1, 2, . . the random variable == Pr[R Re] satisfies the conditions outlined in Lemma A.I
In simple terms, this means that while a fixed dataset R1, R2..... Rm not sufficient determine the exact value of 5 = Pr[R < Re), we can infer that the value of 5 must follow a Beta distribution that is solely defined based on m and This allows us to tune the parameters m and to provide strong guarantees for the coverage R < R2 where R2 is obtained from our fixed sampled dataset.
This guarantee can be equivalently expressed betacdf (f. m + 1 f) denote the cumulative distribution function (CDF) of the Beta distribu- 8. Then, based on the
two-sided probabilistic bound. Specifically, let
tion-also known as the regularized incomplete beta function-evaluate definition of cumulative density function, CDF, for any confidence dj E [0, 1] and any arbitrary D, the following inequality holds:
distribution
Pr Pr[ S Re ] & > betacdf 5; (f, m + E).
Note that the key assumption is that all variables R. R1, R2...., Rm are independently drawn from the same distribution D, and that the previously sampled values sorted such that Rı Ra < < Rm. Importantly, the resulting probabilistic guarantee remains valid for any arbitrary choice of sample size m. rank e, and confidence level 51, provided they lie within appropriate bounds.
B A Clarifying Example for Conformal Inference
Assume an arbitrary distribution R D. We sample a calibration dataset of size m = 100, 000, we sort the samples as R₁ < R2 < < Rio0,our and we select the sample at rank l = 999. In
The Beta distribution is family of continuous probability distributions defined on the interval 0 S with shape parameters a and B, and with probability density function f(r; a, B8 (1-=))=-- where B(a.d)
[(m)r()) and 1'(z) 1o --- -'tt dt is the Gamma function. constant B(a, B) Tl++B)
21

---

-145
-155
1
S
-165
-175
-185
-195
-205
-75
-65
-55
-45
-35
Figure 3: Shows two Reachsets with different (e, l, m) guarantees.
this case, given an unseen draw /uuseen from D for miscoverage level 0.0001, the (e, m) guarantee for logical statement (e,, m) = Punseen < Re] is:
Pr Pr[ Runseen Rg9,999 > 0.9999 0.9995008
which is valid for any calibration dataset M {R1, R R100,000 sampled from distribution D if and only if Runseen is also sampled from D, and R99,999 the 99, 999 smallest member of M.
C A Clarifying Example on Naive Approach
Since the naive technique is ceanteetuur-agnnstte we apply that for the reachability analysis of feedforward ReL.U neural network with 60 hidden-layers of width 100, input layer of dimension 784 and an output layer of dimension 2. The set of inputs is I == [0, 1711 and we generate both calibration and train datasets by sampling uniformly. e.g., W, W are both uniform distributions.
We firstly generate calibration dataset of size m = 200, 000 and a train dataset size = 10, 000, we also consider the rank & 199, 998 and we target the miscoverage level of e 0.0001. In this case we compute a reachable set, S with the following (e, E, m) guarantee.
I Pr Pr[ f(x) E S1 0.9999 > 0.9999995.
2: Secondly, we set m 8464287, 8464286 and 0.000002 which results in another reachset
S2 with the following (c, é, m) guarantee.
W x + Pr Pr[ f(x) E S2 0.999998 0.9999992.
Figure 3 shows the reachable sets S and S, in the presence of 106 new simulations, ( x W I, for validttion. Our calculations show that the proportion of points lying outside of S and S2 are 0,000013 and 0.000001, respectively, which aligns well with the proposed (e, e, m) guarantees.
D Additional material for RQ1
In this section, present overview of conformal pitrrence-bassee technique and contrast it with methods based on randomized smoothing, using a unified terminology to make the comparison clearer for readers.
Overview Fischer et al. 2021), the authors introduced a probabilistic method verify Semantic Segmentation Neural Networks. Inspired by Cohen et al. [2019] they introduced randomness via
22

---

Gaussian noise y ~ (0 R applied to the input, and constructed smoothed version of the segmentation model, denoted (i, for each mask pixel (i,
() c arg max <ET.
[SSN(x + v)) = (0,0))
Pr
They then established that, with confidence level 82. the smoothed prediction SSN is robust within an l ball Br,,, (x) of radius Th = の (p where PA(i, lower bound on the class probability: (i) = Pro (sSN(z + (i, ci Here, (.) is the inverse CDF of normal distribution. The corresponding probabilistic guarantee becomes:
Yz' B (z) Pr SSN((2) ca(i.))) 2
However, certifying all mask pixels simultaneously challenging. enable global guarantees, more conservative definition of smoothing is adopted: a fixed threshold x. E [0.5. 1] is used for all mask locations (i which implies:
SSN (z) ca( ca(Et),,
where
[SSN + (0,20)
This leads a unified radius o (xx) for the input space. While this simplifies the formulation, introduces the concept of abstained or uncertifiable pixels-those that cannot meet the desired confidence threshold. To mitigate the issue of multiple comparisons (i.e., union bounds), the authors propose statistical corrections such as the Bonferroni and BollmBBonferroii methods [CE 1936 Holm 1979]. Assuming the set of certifiable pixels is defined as CERT {(i.j) (i,j) certifiable). they propose the final guarantee in the following form:
Va' E (x) Pr[ A P(i.)) ] 62, P(I.)) = (i.JECERT
=ca(,)))
This method is referred to as SEGCERTIFY. A key limitation of this technique is the presence of abstained pixels. The authors in Anani et al. 2024) addressed this by proposing an adaptive approach, ADAPTIVECERTIFY which reduces the number of uncertifiable pixels. However, the guarantees proposed in Fiacchini and Alamo [202T) Anani et al. [2024) apply only to the smoothed model, not the base model. To express this in terms of the base model, we define the following problem:
Problem 1. For given image r, noise v/ NO o²), and a threshold E [0.5, 1), define ca(i.)) L such that: Præ-N((0.0)) [SSN( + (i, = (i. 2 K. Then for any x' E B,((r) with r = の - and confidence level 82, we want to show the following guarantee, where CERT will be also determined through the verification process:
Pr[ A
Pr [SSN(2' ()((,)) - caai.)) | d2 (CJ)CCERT 22
Overview 2. In our approach, for a given image & and input set B,(x), we perform a probabilis- tie reachability analysis with a (,, m) guarantee. Due to the presence of conservatism in our reachability technique, some mask pixels are marked as robust (i.e., certifiable), while others cover multiple classes and considered unknown or uncertifiable. Let CONFORMAL, CERT ((i.5) (i.j) is certifiable). Then our verification objective is:
B (z)) for coverage level & = 1-c E [0. 1]. hyper-parameters é, m and confidence level &, = 1 betacdf,, (4, m-11()) we aim to show the following E, m) guarantee where CONFORMAL CERT will be also
Problem 2. Given an image x, input set (x). and sampling distribution x' w
determined through the verification process:
[P A
SSN(=')(L.)) = SSN(x)(I.1) ] 2 25
(LJ)ECOFORMAALCOM) CERT
23

---

Both guarantee formulations have their respective advantages and limitations. An advantage of our guarantee formulation is that is defined directly on the base model (i)(2)) while randomized smoothing considers SSN + ( j) To make the randomized smoothing formulation operate directly on the base model, one must set v O, which implies a 0 and consequently r a 1 0. As a result, the perturbation ball B, (ar) collapses to a singleton, leaving no space for verification. On the other hand, the advantage randomized smoothing lies in its consideration of the worst-case
distribution x' (2),,, whereas methodology assumes prior distribution x! W (2).
E
Additional material for RQ2
Here, we present the additional graphs and visualizations referenced in RQ2.
CLEAR
(a) Image, 0001 /01//P_000790ppng
(b) Predicted Mask from BiSeNet
(c) 102 different perturbed pixels.
(d) Unknown and non-robust pixels for 10/255.
(e) Unknown and non-robust pixels for = 150/255.
Figure 4: Visualization for verification on BiSeNet for a specific test image from the Cam Vid dataset. (a) The test image used for verification. (b) The segmentation mask predicted by BiSeNet for this image. (c) The pixels selected for perturbation (in black) on the image (We sampled 102 pixels where the R, G, and B intensities were all above 150/255, forming a perturbation set C R 102x3). (d,e) Display the robust (white), non-robust (red), and unknown (black) pixels for the perturbation set I as described in Figure [] with perturbation magnitudes 10/255 and e 150/255, respectively. The figure illustrates that the model is not sufficiently robust on the borders between different classes.
24

---

(a) Image, CHNCXR_OWE Ce.RR__0000_ppppp p0pg
(b) Predicted Mask from UNetl
(c) 102 different perturbed pixels.
(d) Unknown and non-robust pixels for = 10/255. (c) Unknown and non-robust pixels 150/255.
Figure 5: Visualization for verification UNetl for specific test image from the Lung Segmentation
dataset. (a) The test image used for verification. (b) The segmentation mask predicted by UNetl for this image. (c) The pixels selected for perturbation (in black) the test image (We sampled 102 pixels where the Gray intensities were above 250/255, forming perturbation set C 1u12x1). (d.e) Display the robust (white), non-robust (red), and unknown (black) pixels for the perturbation set as described in Figure I with perturbation magnitudes & = 10/255 and 150 250/ respectively.
25

---

(a) Image, 10491.bpp
(b) Predicted Mask from UNet2
(c) 102 different perturbed pixels.
(d) Unknown and non-robust pixels for 10/255. (e) Unknown non-robust pixels 150/255.
Figure 6: Visualization for verification UNet2 for specific test image from the OCTA-500 dataset.
(a) The test image used for verification. (b) The segmentation mask predicted by UNet2 for this image.
(c) The pixels selected for perturbation (in black) on the test image (We sampled 102 pixels where the Gray intensities were above 150/20 15/255, forming a perturbation set C 1102x1). (d,e) Display the
robust (white), non-robust (red), and unknown (black) pixels for the perturbation set I as described in Figure with perturbation magnitudes e = 10/255 and e = 150/255, respectively.
Averne retiicatie mumeee Foturaabee Veed
Aveniol PETIC
Figure 7: Shows the average run time versus perturbation level e (top row) and perturbation dimension r (bottom row). In the top row, 102 for Cam 102 x 1 for Lung Segmentation and OCTA-500, and 17 x for M2NIST experiment. In the bottom row, e is fixed at 3/255 across all experiments. The runtimes are averaged over 200 test images in each experiment. This graph shows our verification runtime is only slightly sensitive the perturbation magnitude and direction e, r.
26

---

1855
Staree Ganvie
alater canvie
20080
3050
3000
0.00
125
A.5
0.20
A35
93 0.4 04
bood, 190
bound pade
Figure 8: Histogram of n h w L numbers (called bound_ (ound_ratio) rratio) shown to present conservatism analysis for our technique. These numbers are the ratio between the length of the empirical bounds and the length of our proposed bounds, bound_ratio//
(b)) (k))) (T(k) - v(k) where k = 1, .,. The empirical bounds (i(k), ({k]] are estimated using 10 random samples. We conduct conservatism analysis across three experiments from Figure 2 one experiment with the m2nist_de de model trained on M2NIST dataset where the experiment considers perturbation magnitude
e = 10/ /5,, and dimension r = 17 x 1; and two experiments with the BiSeNct model trained on Vid dataset where the experiment considers perturbation magnitute e = 10/255 & 150/255 and dimension r = 102 x 3. These cases span the smallest to the largest configurations we addressed in case studies in Figure 2 The empirical miscoverage was é = 7 10-6 for M2NIST experiment and = 0 for both experiments on Cam Vid dataset. This shows in all cases < c where c = 10 for M2NIST and 10 for Cam as outlined in Table 2 In this histogram,
omit components k whose normalization factors T are smaller than r", since their magnitudes are negligibly small compared to the other components, and their conservatism has little effect on the volume difference between the sets.
F Looking at Violating Samples Obtained in Our Experiments
Our probabilistic guarantees inherently imply that small probability of violation exists; however, the key contribution of our approach is that it provides formal guarantees on the likelihood of such violations. One example of these events appears Appendix C where the red and black boundaries are violated by 13 and 1 output samples, respectively, out of a total of 10 generated outputs. Another instance is shown in Figure 8 where out of 10 sampled outputs violate the reachable set computed for the M2NIST experiment. Importantly, all of these violations remain consistent with the probabilistic bounds established by our theoretical guarantees.
G Additional Research Questions
RQ3 (2nd Abblation Study): How Do Surrogate Models Affect the Level of Conservatism in our method? To investigate this, we conducted a classification-based verification task using a model submitted to VNN-COMP 2024 (Brix et al. 2024 by the a-3-CROWN team, trained on the CIFAR-100 100 dataset. We refer to this model as ResNet large, which contains 8 residual blocks, 19 convolutional layers, and 2 linear layers. We sample calibration dataset of size m 100,000, set the rank to L = 99,999, and choose a miscoverage level = 10-1, which corresponds to a 0.9999. This setup yields a confidence level of d2 0.9995. In
coverage level of 6₁ 1 this experiment, given an image & E R32x32x3 with label e. E 1..... 100 corresssnggn to a logit vector f (vec(x)) (z)) e R we
we aim to verify the following specification:
Pr Pr [P] 2 8, 82, where P
Given image perturbed within an &z ball of radius e/255 and label é. . the predicted label remains unchanged for all penurbations within the ball f
Our reachability- verification method inherently introduces some conservatism. In this experi- ment, we investigate how incorporating surrogate models- saddel--speefficallyy.. a ReLU-based surrogate- can reduce that conservatism compared to a naive approach. Lower conservatism enables verification under larger perturbation magnitudes e/ e/255. To evaluate this, we vary e across 1 1/255 to 30/255 and test both methods on 200 sampled images. The naive method fails to verify beyond certain pertur- bation levels, while the surrogate-based approach continues to succeed under larger perturbations, achieving the same probabilistic guarantee. Thus given unique perturbation magnitude we run the verification on 200 events (200 images) and count the percentage of successful verification for both methods. Figure 9 presents this percentage of successful verifications for each technique across
27

---

perturbation levels, demonstrating that the ReLU surrogate substantially improves the method's applicability by reducing the level of conservatism. As previously mentioned, our verification run- times vary minimally across different images and perturbation levels, so report average values. The naive method took an average of seconds per verification, while the ReLU surrogate method required 44 seconds.
Weriicalion with NO Surogate Veification with Relil
10
10
12 13
Perturbation Magnitute e/55 for
Figure 9: This figure compares the conservatism of verification with and without the ReLU surrogate. We evaluated classification robustness over perturbations bounded by ts balls with magnitudes 1/255, 2/255. ..... 30/ 30/255, across 200 images. Each block represents the percentage of cases where the verified label remained unchanged under perturbation. The results show that using a ReLU surrogate significantly improves verification at larger perturbation levels, due to reduced conservatism the reachability analysis.
RQ4: Do State-of-the-Art Deterministic Verification Techniques Scale to the Level Achieved by Our Method on Complex and High-Diment High-Dimeensioal SSN Models? We applied techniques such as a-B-CROWN [Zhou et al. (024) and NNV (Tran al. 2021 to our segmentation experiments using the UNer1, UNet2, and BiSeNet models in RQI. However, due to the size of these models and the high perturbation levels considered, both methods encountered out-of-memory errors and failed to complete verification on the same hardware used for our approach. This highlights that while deterministic guarantees are often preferable, they may not always be computationally practical. In such cases, our probabilistic verification method for SSNs offers scalable and effective alternative.
28


Reviews:
[{"review_id": "9TRMFr3r3W", "reviewer": "Reviewer_Xbuv", "summary": "This paper addresses the challenge of verifying robustness in Semantic Segmentation Neural Networks (SSNs), particularly under input perturbations and adversarial attacks, where formal verification approaches are often computationally intractable due to the high-dimensional output space of SSNs. The authors propose a scalable, architecture-agnostic probabilistic verification framework that leverages conformal inference (CI) for data-driven reachability analysis with formal probabilistic guarantees.\n\nA naive baseline is introduced that applies CI to SSNs by constructing hyper-rectangular reachsets, which are provably correct but overly conservative. The authors then improve this baseline by: 1. Incorporating surrogate ReLU networks to approximate complex SSNs, 2. Using zonotopic (star-set) representations instead of axis-aligned boxes, 3. Applying a scalable Principal Component Analysis (PCA) technique (via a deflation algorithm) to handle high-dimensional output.\n\nExperiments on benchmark datasets (M2NIST, CamVid, Lung Segmentation) and models (U-Net, BiSeNet, ResNet) demonstrate the practicality of the proposed method, showing its capability to provide provable guarantees with lower conservatism and scalability to large-scale networks.", "questions": "1. You assume that a small ReLU network can accurately approximate the SSN under the input distribution. What happens when this approximation fails? Could you provide an error bound or confidence estimate for the surrogate's fidelity?\n\n2. The paper emphasizes that the proposed method is less conservative than the naive baseline, but does not quantify this. Can you provide a metric (e.g., volume ratio, false positive rate) to quantify the reduction in conservatism introduced by surrogate-based starsets over hyper-rectangles?\n\n3. You use learning-based PCA for output compression. Does this technique scale to more complex SSNs with class imbalance or highly correlated outputs (e.g., medical segmentation)? Could more sophisticated dimensionality reduction (e.g., autoencoders) offer advantages?\n\n4. These tasks also produce structured, high-dimensional outputs. What changes would be needed for your approach to work on non-semantic segmentation tasks?\n\n5. The framework relies on users tuning calibration size and miscoverage thresholds. Is there a principled way to choose these values to balance runtime and conservativeness, or are they empirically tuned?", "limitations": "Yes (but partially). The paper discusses the limitations of conformal inference in high-dimensional settings and the lack of deterministic guarantees. However, some critical points are underexplored, including: 1. How approximation errors in the surrogate model affect guarantees; 2. Potential failure of the method when calibration distributions are not representative; 3. No discussion of societal impact, e.g., false security in safety-critical applications like medical imaging.", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n\nThe framework is designed to scale to large segmentation models and high-dimensional output spaces, a major bottleneck in prior work on neural network verification.\n\nThe method builds on conformal inference, with sound statistical foundations. The paper offers a formal double-layer probabilistic guarantee, balancing confidence and miscoverage.\n\nThe authors start from a transparent, naive CI-based technique and systematically address its limitations via star-set reachability, surrogate modeling, and dimensionality reduction.\n\nThe use of learning-based PCA (via deflation) to address high output dimensionality in robustness analysis is innovative and effective.\n\nThe experiments target relevant questions (e.g., scalability, conservatism, runtime), are run across diverse datasets and models, and demonstrate superior scalability compared to deterministic methods like αβ-CROWN and NNV.\n\nThe formalization of the probabilistic reachsets via ⟨ϵ, ℓ, m⟩ tuples is precise and instructive, making it easier to interpret coverage and confidence.\n\nWeaknesses\n\nThe key technical building blocks (conformal inference, surrogate modeling, PCA) are individually well-established. The contribution lies in their combination and adaptation to SSNs rather than a fundamentally new technique.\n\nWhile the authors emphasize scalability, there’s no formal analysis of conservativeness versus exactness. The surrogate model approximation is only loosely justified, and the inflation method may introduce nontrivial looseness.\n\nTraining a ReLU surrogate model assumes a sufficiently accurate approximation of the original SSN. But the conditions under which the surrogate is guaranteed to succeed are not discussed, especially for very deep or complex architectures.\n\nThe method is evaluated under a synthetic \"darkening\" attack and UBAA noise models. More standard threat models (e.g., FGSM, PGD, spatial transformations) are not used, which limits generalizability.\n\nWhile pixel-level robustness is central, it's not always clear how the user should interpret “unknown” regions in practice—especially when aggregated over classes or images.", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your detailed feedback.\n\n---\n\n***Response to Comments on Weaknesses***\n\n**On the Use of Established Techniques:**  As noted, the core techniques used in our framework—conformal inference, surrogate modeling, and PCA—are individually well-established. However, our contribution lies in their novel integration and adaptation to the verification of semantic segmentation networks (SSNs), a high-dimensional and structured output setting where existing methods struggle with scalability or conservatism. This combination results in an efficient and practically useful verification algorithm. As requested by Reviewer 2, we have included additional experiments comparing our method with several baselines from the literature. These results, discussed in our responses to Reviewer 2, demonstrate a significantly reduced level of conservatism in our method relative to existing approaches.\n\n**On Conservatism vs. Exactness:** Appendix E (RQ4) already provides a numerical comparison showing that the ReLU-based surrogate leads to less conservative estimates than the naive baseline. However, you are correct that we did not previously include a numerical evaluation of conservatism relative to exact reach sets. To address this, we have added a new experiment in the revised version of the paper. Specifically, we perform 10^6 random forward passes through the model to empirically lower-bound the true reachable set. We then compare these empirical bounds with the reach set computed by our method. The results show that, on average, the bounds produced by our method are only 10% larger than the empirical lower bound in the M2NIST experiment, and approximately 20% larger in the CamVid experiment. This demonstrates that while our method is conservative, the gap from exactness remains moderate and practical.\n\n**On Assumptions about Surrogate Model Accuracy:** We do not assume an accurate approximation of the original SSN. The main motivation for introducing the surrogate technique is to improve upon the naive method. The more accurate the ReLU surrogate, the lower the conservatism compared to the naive technique. We discuss this in more detail in our responses to your questions.\n\n\n**On the Use of Attack Models:** We acknowledge that FGSM and PGD are widely used in adversarial robustness literature. However,PGD and FGSM attacks are essentially one-dimensional, as they identify a single critical direction to which the model is most vulnerable. Verifying robustness against such attacks does not require reachability techniques. Since pixel values are discrete (e.g., $1/255, 2/255, \\ldots, 1$), verification along a one-dimensional perturbation can be efficiently performed with a finite number of forward passes through the model. In contrast, consider a 102-dimensional perturbation with a magnitude of $3/255$. Verifying robustness in this setting would require $3^{102}$ model evaluations, which is computationally infeasible. This complexity motivates the need for reachability-based analysis. For this reason, we focused on darkening attacks in our experiments.\n\n**On the Interpretation of Unknown Pixels:** We agree that pixels labeled as “unknown” (i.e., not certifiably robust) can pose a challenge in interpretation. The unknown pixels are not certifiable, meaning we do not provide guarantees for them due to the conservatism inherent in our reachability analysis. Addressing uncertifiable pixels is a common and active area of research in the verification community. However, as requested by Reviewer 2, we described a recent experiment demonstrating that the number of uncertifiable pixels produced by our method is at least 100 times lower than those reported by other probabilistic techniques in the literature.\n\n---\n\n***Answer to the Questions:***\n\nQ1: \n\nWe do not assume that a small ReLU network accurately approximates the SSN across the entire input distribution. Instead, we use the network to enhance the naive technique in two ways:\n\n**Improved Output Estimation:** In the naive method, we estimate the outputs using a fixed value (typically the mean), which can result in high approximation error. By contrast, we use a small ReLU model to learn a more expressive approximation of the outputs, which reduces this error. The better the surrogate model, the more accurate the output estimates, resulting in a tighter reachable set.\n\n**Better Reachable Set Geometry:** We apply ApproxStar reachability analysis to the ReLU model, which yields a convex hull over the output space. This provides a more informative and compact approximation of the cloud of outputs than the hyper-rectangular (box-shaped) reachable sets used in the naive approach. To ensure formal coverage guarantees, we then use conformal inference to appropriately inflate this convex hull, ensuring the true outputs lie within it with provable probabilistic guarantee.\n\nIn summary, even if the small ReLU model is not a perfect surrogate for the SSN, it still leads to tighter and more meaningful reachable sets than the naive mean-based method.\n\n**Proof:** One can initialize the surrogate model such that it outputs a constant value equal to the mean of the training dataset and define the loss function as the $\\delta_1$-quantile of the prediction errors (i.e.,**Quantile Regression**). Regardless of how accurately the surrogate is trained, the resulting error quantile will be lower than that of the initialized model. This is sufficient to claim that the new reachable set has been tightened.\n\nHowever, due to the high dimensionality of SSN, we were unable to start training it, primarily because of gradient-related computational issues. To address this, we applied PCA to reduce dimensionality, allowing the training process to get started.\n\nQ2:\n\nYes, we addressed this through a numerical experiment presented in RQ4 of Appendix E (Page 14), where we evaluated the conservatism of our method. The experiment compares three approaches: (1) the naive technique, (2) reachability analysis with a linear surrogate model, and (3) reachability analysis with a ReLU-based surrogate model.\n\nIn the original experiment, we varied the perturbation bound $e$ from $1/255$ to $10/255$. The ReLU-based method verified robustness of the classification up to $e = 9/255$, while the linear surrogate method did so up to $6/255$, and the naive method only up to $3/255$. This clearly demonstrates the improved performance of the ReLU surrogate, which we attribute to its ability to produce less conservative reachable sets. We recently extended this analysis to $200$ images and expanded the range of $e$ values from $1/255$ to $30/255$.\n\nQ3:\n\nBefore addressing it directly, we would like to highlight that, due to the accuracy and data efficiency of CI, our baseline (naive) technique performs better compared to SOTA. This is supported by new experimental results requested by Reviewer 2, which show it significantly outperforms existing probabilistic methods. However, our overarching goal is to reduce conservatism of naive technique, which is why we incorporate ReLU-based surrogate models in reachability.\n\nWe terminate our SGD-based PCA algorithm once a specific amount of principal directions are extracted. When outputs are highly correlated, that amount may be insufficient. This can degrade the accuracy of the ReLU surrogate model. Nonetheless, even in these cases, the ReLU-based reachability analysis still outperforms the naive approach, as learning from the data distribution using a ReLU model is more effective than relying on approximation with a mean-value (naive technique).\n\nWe appreciate the suggestion to explore autoencoders for dimensionality reduction and we plan to investigate this direction in future work.\n\nQ4:\n\nOur method is centered on computing the reachable set of the output space. Once this set is obtained, it can be used to reason about a variety of tasks—not just SSN. While our current paper focuses on challenges posed by high-dimensional outputs in SSN, the proposed approach is general and can be applied to other high-dimensional tasks as well.\n\nAccordingly, we have decided to revise the title if the paper is accepted. The updated title will be:\n\n\"Probabilistic Robustness Analysis in High-Dimensional Space: Application to Semantic Segmentation Networks\"\n\nQ5:\n\nYes, our framework provides a principled approach for selecting these parameters. The user specifies a target coverage level $\\delta_1$ and confidence level $\\delta_2$, and we use a binary search to efficiently determine the appropriate calibration size $m$ and rank $\\ell$.\n\nIn the common case where $\\ell = m - 1$, increasing $m$ monotonically increases $\\delta_2$ for a fixed $\\delta_1$. This property allows binary search to efficiently identify the optimal $m$ that satisfies the desired level for $\\delta_2$. Our toolbox includes this module that retuens optimal $m$ based on desired statistical guarantees.\n\n---\n\n***Response to Limitation Comments:***\n\nWe would like to again encourage the reviewer to revisit Appendix A, where we provide a detailed explanation of why CI is distribution-free. \n\nYou raised three important points, and we address them below: \n\n1- Importantly, the formal guarantee in our method is entirely derived from CI; the surrogate model is introduced solely to reduce the conservatism of this guarantee, without affecting its validity.\n\n2- It’s important to emphasize that CI is distribution-free—this is thoroughly discussed in Appendix A. The distribution-free nature of CI is precisely why we adopt it for reachability analysis of neural networks, whose output distributions is complex. Therefore, the validity of our method does not depend on how exact the calibration distribution is captured. As long as the calibration dataset is sampled from the same distribution that guarantee holds and this is the **magic** of CI. \n\n3- We add a paragraph on societal impact, and the importance of verification in safety-critical domains such as medical imaging."}, {"review_id": "Hb7saFIvwc", "reviewer": "Reviewer_uuuW", "summary": "The paper proposes a new certification method to prove the robustness of semantic segmentation models against adversarial perturbations. In contrast to precise methods based on reachability analysis, the authors propose to instead compute probabilistic guarantees using conformal inference. This is inspired by the high output dimensionality of segmentation models (one classification per pixel), which makes them more expensive to certify. The approach is validated on segmentation models up to ResNet18-size for CamVid, Lung_Segmentation, and M2NIST datasets.", "questions": "1. Is there any way to get results on Cityscapes or ACDC? Since you mention self-driving cars as motivation, this would complete the paper, make it relevant to practical datasets, and comparable to prior work\n\n2. Can you please compare to the related work listed above [a, b, c, d] - both conceptually and empirically?\n\n3. L53: what do you mean by \"low-conservatism\"?\n\n4. L292: In 2025, a 64x64 pixel dataset cannot really be described as \"high-dimensional\". I understand that the method has limited scalabliliy in terms of image resolution, but please be upfront about it.\n\n5. L294: Same for \"large and complex pre-trained models\" - the largest mode lis ResNet18, which in 2025 cannot be considered large or complex.\n\n6. L297: What is the reason for this particular threat model? Why is the method especially applicable in this setting?", "limitations": "The paper does not address limitations, even though there are many. For example, guarantees are only probabilistic and could fail; it is limited to very small models and datasets; Evaluation does not compare to any baselines; the method is not applicable to the real-time requirements of some of the motivating examples (e.g., self-driving cars); etc.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. It has been well established that neural networks - and semantic segmentation models in particular - are vulnerable to small perturbations. Provable worst-case guarantees are therefore highly desired, which makes this work a very valuable contribution.\n\n2. To the best of my knowledge, the approach is novel in the context of semantic segmentation. While scalability and practical applicability currently seem limited (see below), I believe that the space of certified robustness methods still requires significant exploration. I therefore appreciate the novel perspective on certified robustness guarantees.\n\n3. The mathematical guarantees appear sound to me, although I am not an expert on conformal predictions and statistics, and therefore may have missed subtle problems.\n\n**Weaknesses**\n\n1. The paper lacks comparisons to prior work and baselines, both in related works and experiments. There are at least two lines of work that can certify the robustness of segmentation models: (i) based on sound reachability analysis [a], and (ii) based on randomized smoothing, which also computes probabilistic certificates [b, c, d]. Even if the proposed approach does not outperform SOTA methods, it would be important to understand the differences in the threat model, precisely what is guaranteed, and the performance in terms of certified accuracy, robust radius, and model and dataset sizes.\n\n2. The evaluation is limited in several aspects:\n - The evaluation is limited to 10/20 test data points. This is insufficient to reach statistically relevant results. Based on the runtimes in Table 3, it should be feasible to run the experiments on at least ~500 - 1000 datapoints in a few days. (2) \n - The threat model considered is non-standard for the adversarial robustness literature. Typically, prior work assumes either $\\ell_p$-norm perturbations or patch attacks. Why was this particular threat model chosen? If sparsity is a requirement, $\\ell_0$ perturbations would be the standard setting that makes the work comparable to prior work. Otherwise, there should be a discussion and justification of the particular threat model.\n\n3. The authors do not provide code for evaluation and extension of the proposed method.\n\n\n**Conclusion**\n\nIn its current form, the paper's weak evaluation and lack of comparison to prior work outweigh its significant contribution and interesting approach. If these two points are addressed, I would be willing to change my rating to acceptance, even if the results fall behind SOTA.\n\n\n[a] Tran, HD. et al. (2021). Robustness Verification of Semantic Segmentation Neural Networks Using Relaxed Reachability. In: Silva, A., Leino, K.R.M. (eds) Computer Aided Verification. CAV 2021\n[b] Scalable Certified Segmentation via Randomized Smoothing. Marc Fischer, Maximilian Baader, Martin Vechev Proceedings of the 38th International Conference on Machine Learning, 2021\n[c] GSmooth: Certified Robustness against Semantic Transformations via Generalized Randomized Smoothing\nZhongkai Hao, Chengyang Ying, Yinpeng Dong, Hang Su, Jian Song, Jun Zhu Proceedings of the 39th International Conference on Machine Learning, 2022\n[d] Adaptive Hierarchical Certification for Segmentation using Randomized Smoothing. Alaa Anani, Tobias Lorenz, Bernt Schiele, Mario Fritz Proceedings of the 41st International Conference on Machine Learning, 2024", "was_revised": true, "final_justification": "The authors addressed all of my major concerns during the rebuttal. In particular, they clarified many details and provided additional results and comparisons to prior work. I therefore recommend acceptance with the following changes, to which the authors agreed:\n\n- The additional results and comparisons to related works (including the extended [b] and [d] table and the Cityscapes/HRNetV2 experiments) are included in the paper.\n- The clarifications and additional details from the author responses are integrated, including the distinction between the naive and surrogate methods, and the justification for the chosen threat models.\n- The major limitations are explicitly discussed in a limitations section, including (1) the distributional assumption, which may not hold in an adversarial setting, (2) the requirement of recomputing the calibration set for each test point, and (3) the scalability limitations wrt the input dimension of the surrogate approach.", "rebuttal": "We appreciate your detailed feedback.\n\n---\n---\n\n***Response to Reviewer’s Comments on Weaknesses***\n\nComparison with SOTA:\n\nWe were aware of paper [a]. In RQ2 (Appendix E, page 13), we showed NNV encountered out-of-memory issues in all experiments presented in RQ1. However, we were not previously aware of the other three papers [b, c, d], and we have now added them to related works and also have a comparison with them in the updated paper. The guarantee formulations are slightly different from ours. However, we found a meaningful way to compare, and our numerical results show our technique is 100 times less conservative. We also provide the details of this comparison below for your review.\n\n**Overview:**  Papers [b, c, d] are based on randomized smoothing. Paper [b] introduces a method called $\\mathsf{SEGCERTIFY}$.  Lets assume  $\\overline{\\mathsf{SSN}}(x)(i,j)$ is the smooth version of $\\mathsf{SSN}(x)(i,j)$ on pixel $(i,j)$, generated by a zero mean gaussian random noise:\n$$\n\\overline{\\mathsf{SSN}}(x)(i,j)=c_A(i,j)=\\underset{c\\in\\mathbf{L}}{\\arg\\max}\\Pr_{\\nu\\sim\\mathcal{N}(0,\\sigma^2)}\\left[\\mathsf{SSN}(x+\\nu)(i,j)=c\\right]\n$$\nwhere $\\mathbf{L}$ is the set of classes. Assuming a coverage level $\\tau\\in[0.5,1]$, they redefine the top class $c_A(i,j)$ in a more conservative yet practically more convenient manner, and specify it as the class that satisfies:\n$\n\\Pr_{\\nu\\sim\\mathcal{N}(0,\\sigma^2)}\\left[\\mathsf{SSN}(x+\\nu)(i,j)=c_A(i,j)\\right]\\ge\\tau\n$\n, and then given a confidence guarantee $\\delta_2$, they then propose the following guarantee for the smooth approximation of the model:\n$$\n\\forall x'\\in\\mathbf{B}_r(x):\\Pr\\left[\\overline{\\mathsf{SSN}}(x')(i,j)=c_A(i,j)\\right]\\ge\\delta_2\n$$\nwhere $\\mathbf{B}_r(x)$ is a ball with radius $r=\\sigma\\Phi^{-1}(\\tau)$ and center $x$. They also argue that by allowing a portion of pixels to be abstained from (i.e., remain uncertifiable), they  define:\n$$\n\\mathbf{CERT}=\\\\{(i,j)|(i,j)\\mathsf{\\ is\\ certifiable}\\\\}\n$$\nand extend this guarantee over output space of $\\mathsf{SSN}$ as:\n$$\n\\\\forall x'\\\\in\\\\mathbf{B}\\_r(x):\\\\Pr\\\\big[\\\\bigwedge\\_{(i,j)\\\\in\\\\mathbf{CERT}}\\\\overline{\\\\mathsf{SSN}}(x')(i,j)=c_A(i,j)\\\\big]\\\\geq\\\\delta_2\n$$\nwhich can be rephrased for the base model as:\n\n$$\n\\\\forall x'\\\\in\\\\mathbf{B}\\_r(x):\\\\Pr\\\\big[\\\\bigwedge\\_{(i,j)\\\\in\\\\mathbf{CERT}}\\\\Pr_{\\\\nu\\\\sim\\\\mathcal{N}(0,\\\\sigma^2)}\\\\left[\\\\mathsf{SSN}(x'+\\\\nu)(i,j)=c_A(i,j)\\\\right]\\\\ge\\\\tau\\\\big]\\\\ge\\\\delta_2\n$$\nOn the other hand, the authors in [d] enhance this work using adaptive techniques to reduce the number of abstained (uncertifiable) pixels, and call it $\\mathsf{ADAPTIVECERTIFY}$.\n\n**Comparison:**  We adopt the perturbation set $\\mathbf{B}_r(x)$ identical to what considered above and present our guarantee for certifying the robustness of the output pixels. Due to the conservative nature of our reachability analysis, some bounds for certain mask pixels may span multiple classes, which we label as unknown. These unknown pixels are in fact uncertifiable, and thus we define the following set accordingly:\n$$\n\\mathbf{Conf\\\\_CERT}=\\\\{(i,j)|(i,j)\\mathsf{\\ is\\ certifiable}\\\\}\n$$\nand given a coverage level $\\delta_1 $ and confidence $\\delta_2 $ and a sampling distribution, $x'\\stackrel{\\mathcal{W}}{\\sim}\\mathbf{B}_r(x)$, we generate the following guarantee:\n\n$$\n\\\\mathbf{If}\\\\ x'\\\\stackrel{\\\\mathcal{W}}{\\\\sim}\\\\mathbf{B}\\_r(x):\\\\ \\\\  \\\\Pr\\\\big[\\\\Pr\\\\big[\\\\bigwedge\\_{(i,j)\\\\in\\\\mathbf{Conf\\\\_CERT}}\\\\mathsf{SSN}(x')(i,j)=\\\\mathsf{SSN}(x)(i,j)\\\\big]\\\\ge\\\\delta_1\\\\big]\\\\ge\\\\delta_2\n$$ \nTherefore, given an identical perturbation set $\\mathbf{B}_r(x)$ the comparison aims to determine which method produces fewer uncertifiable pixels under its proposed guarantee.  We use Table 1 from [d] as a benchmark, which sets $\\tau=0.75,0.95$, $\\sigma= 0.25,0.33,0.5$, and $\\delta_2=0.999$ (6 experiments totally, 200 images each). Their experiments are conducted using this configuration on an HRNetV2 model with a W48 backbone, trained on the **Cityscapes** dataset, and they compare the number of uncertifiable pixels achieved against [b]. Accordingly, we use our naive technique and extend this table by reporting the number of uncertifiable pixels we obtained under the setting $\\delta_1=0.99,\\delta_2=0.999$ and $\\mathcal{W}$ to be uniform for all of those 6 experiments. The code is available online anonymously and can be shared upon your request during the author-reviewer discussion period.\n\n**Results**:  The number of uncertifiable pixels produced by our technique was 100 times smaller than the values reported in that table, **clearly demonstrating the effectiveness of incorporating conformal inference into the verification of SSNs**.  Our average runtime was 210 seconds, with a calibration dataset size of $m=920$ for all experiments. However, Table 1 in [d] does not report any runtime information.\n\n---\n\nLimitation in Evaluation:\n\nIn response to the reviewer's concerns, we have significantly expanded and improved our evaluation. Specifically, inspired by prior works \\[b, d], we increased the number of test images to 200 across all experiments and added several new evaluations, as detailed below:\n\n1. In the original submission, some parts of verification were conducted on CPU; all experiments are now executed solely on GPU for improved efficiency.\n2. We added a new experiment on another UNet trained on the OCTA-500 dataset.\n3. While the original submission focused on a fixed perturbation size with varying perturbation dimensions (ranging from $17\\times 3$ to $102\\times 3$), the revised version includes an additional experiment where we fix the perturbation dimension and vary the perturbation size from $3/255$ up to $150/255$.\n4. We included analyzing the conservatism of our method by comparing our reachable set bounds to a lower-bound estimated via Monte Carlo simulation.\n5. Per your suggestion, we performed a new comparative study with \\[b, d] on the **Cityscapes** dataset, targeting an **HRNetV2-W48** backbone with 66M parameters.\n6. We extended the experiment in RQ4 (Appendix E, page 14) to a broader range of perturbation sizes ($e = 1/255, ..., 30/255$), using 200 test images.\n7. We included several visualizations of our verification results across different datasets to enhance interpretability.\n\nRegarding the threat model, we have incorporated both:\n\n* $\\ell_\\infty$ perturbations were used in the original RQ3 and RQ4 experiments on the CIFAR-100 dataset (Appendix E).\n* A new experiment on the **Cityscapes** dataset, in comparison with \\[b, d], uses $\\ell_2$ perturbations.\n\nOur primary motivation for using the darkening attack was also as follows:\n\n1. It was the primary threat model considered in \\[a], and widely used in several other papers on adversarial training.\n2. It introduces sparsity in the input space.\n3. It allows easy control over both perturbation size and dimension, enabling us to thoroughly test the scalability of our technique.\n\nFinally, the code and updated manuscript are available online via an anonymous link. We are happy to share access upon your request during the author-reviewer discussion period.\n\n---\n---\n\n***Answer to the Questions***\n\nQ1:\n\nFollowing your suggestion, we conducted experiments on the Cityscapes dataset to compare our results with methods [b] and [d].\n\nQ2: \n\nWe previously compared our method with [a] in RQ2 (Appendix E). Method [d], as an extension of [b], offered a coherent narrative for comparison, and we included both conceptual and empirical comparisons against [b,d]. In contrast, [c] focuses on transformations with a focus on classification tasks, and we only cited that in Related works.\n\nQ3:\n\nWe revised this sentence as follows:\n\" In this work, we propose a scalable, architecture-agnostic,  probabilistic verification algorithm tailored for semantic segmentation neural networks and we demonstrate through numerical experiments that it is less conservative than existing statistical methods in the literature.\".\n\nQ4:\n\nWe have addressed this by removing the mention of \"M2NIST\" from the sentence. One comment here is:\n\n * Our naïve approach remains scalable to high-resolution input images for SSN, as it does not require training a surrogate model. For example, in our comparison with [b, d], the naïve technique completes verification in 210 seconds for an image with a resolution of 1024×2048. \n* As noted in Lines 269–274, when the SSN input is high-dimensional, our surrogate-based method remains efficient under the assumption of sparsity in the input perturbation. \n\nTherefore, in cases where the perturbation dimension is very large, we fall back to the naïve technique for scalability.\n\nQ5:\n\nWe agree with your observation. Like methods [b, c, d], our approach is architecture-agnostic and should generalize to larger models. While the models used in RQ1 were not representative of large-scale architectures, as you suggested, we have now added an experiment using the HRNetV2-W48 backbone—which has 66 million parameters—to compare our technique with methods [b,d].\n\nQ6:\n\nOur goal in RQ1 was mainly to evaluate the surrogate-based technique. While PCA enables the surrogate method to scale to SSNs with high-dimensional outputs, it does not address scalability when the input dimensionality is high. As noted in the manuscript, the surrogate approach requires sparsity in the perturbation set when dealing with high-dimensional inputs. This motivated our choice of the darkening attack, which introduces structured, sparse perturbations.\n\n---\n---\n\n***Response to Limitation Comments***\n\n* We clearly stated in the conclusion section that our method provides probabilistic guarantees, and we also emphasized on this in the title of the paper. \n* Regarding model size, our approach is not limited to small models—we successfully performed verification on HRNetV2 with 66 million parameters in just 210 seconds, achieving significantly lower conservatism compared to methods [b] and [d] on the Cityscapes dataset.\n\n---\n---"}, {"review_id": "0enc9BFGPj", "reviewer": "Reviewer_PV2T", "summary": "The paper presents a probabilistic verification method, based on conformal inference, which is scalable when used in complex semantic segmentation neural networks and lowers conservativism inherent in traditional methods. Experiments are presented with benchmark datasets such as CamVid and Lung segmentation.", "questions": "- Please explain and discuss how the values (confidence of guarantee)  in Table 3 relate to the values shown in Figure 1.\n- Explain and discuss the differences in average runtimes especially in CamVid and Lung Segmentation shown in Table 3.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "S\n- Good theoretical paper for mitigating conservatism in large scale networks such as SSNs.\n- Well written, especially section 3, where the reachability technique for robustness verification of SSNs is developed.  \n\nW\n- It would be good to see more and detailed experimental results (confidence, runtime) in other real life applications, such as the ones represented by CamVid and Lung segmentation.\n- It would be good to explore a bit more the way in which the probabilistic framework could be used in safety-critical systems.", "was_revised": true, "final_justification": "Based on my original review comments and my positive evaluation, and the authors' replies both to myself, as well as to the other reviewers' comments, my rating is accept.", "rebuttal": "We appreciate your detailed feedback\n\n---\n---\n\n***Response to Reviewer’s Comments on Weaknesses***\n\n**Extension of Experiments:** We have significantly expanded the experimental section in the revised version. Reviewer 2 also suggested comparisons with two additional methods, which we have now included. The new comparison is described in detail in our response to Reviewer 2, and we would greatly appreciate it if you could take a moment to review that result as well. Below is a summary of the new experimental additions:\n\n1. In the original submission, parts of the verification process were executed on CPU. We have now migrated all experiments fully on GPU to improve efficiency. For example, our updated experiments on the CamVid dataset now complete in 14 minutes—significantly faster than the 60-minute runtime previously reported.\n2. We added a new experiment using a different UNet model trained on the OCTA-500 dataset and we analyzed it on a darkening attack like the other experiments in RQ1.\n3. While the original submission used a fixed perturbation size with varying perturbation dimensions (ranging from $17 \\times 3$ to $102 \\times 3$) in RQ1, we now include an additional experiment in RQ1 where the perturbation dimension is fixed and the perturbation size is varied from $3/255$ to $150/255$.\n4. We conducted a conservatism analysis by comparing our reachable set bounds against a Monte Carlo–estimated lower-bound.\n5. Following the suggestion of reviewer 2, we performed a new comparative study with two other methods on the **Cityscapes** dataset, using an **HRNetV2-W48** backbone with 66 million parameters.\n6. We extended the experiment in RQ4 (Appendix E, page 14) to cover a broader range of perturbation sizes ($e = 1/255, \\ldots, 30/255$) using 200 test images.\n7. We added several visualizations of verification results across different datasets to improve interpretability.\n8. We increased the number of test images per experiment to 200 to strengthen statistical confidence in our robustness evaluations.\n\n**Application in Other Domains:** Thank you for this valuable suggestion. We agree that our probabilistic framework has a potential for application in various scientific and engineering domains. In scenarios where deterministic guarantees are difficult or impossible to obtain, our method can be applied and offer  probabilistic but strong guarantees that support reliable decision-making under uncertainty. We believe this is particularly relevant for safety-critical settings and plan to explore such applications further in future work.\n\n---\n---\n\n**Answer to Questions**\n\nQ1:\n\nThank you for the question. Below, we first explain how the Robustness Value (RV) is computed and then clarify how it relates to the Table3 e.g. the hyper-parameters $\\ell,m$ and the coverage and confidence $\\delta_1, \\delta_2$.\n\nLet us begin by describing the process for computing RV:\n\nAssume that $\\mathbf{S}$ is the reachable set obtained using our conformal inference method. When we input this reachable set into **Algorithm 2** (Page 8), the output mask is partitioned into three categories: **robust**, **non-robust**, and **unknown** pixels. The **Robustness Value (RV)** is then defined as the fraction of all pixels that are classified as **robust**:\n\n$$\n\\text{ RV } = \\frac{\\text{Number of robust pixels}}{\\text{Total number of pixels}}\n$$\n\nNow, let’s relate this to the parameters in Table 3. Suppose we perturb an image from the CamVid dataset over a perturbation set $\\mathbf{I}$, we sample a calibration set of size $m = 8000$, and set the rank to be $\\ell = 7999$. Using this configuration, we generate a reachable set $\\mathbf{S}$ via conformal inference as explained in the paper. We can now define the following logical statement $\\mathsf{P}$ based on a coverage level $\\delta_1$:\n\n$$\n\\mathsf{P} :=  \\text{\"} \\Pr[y \\in \\mathbf{S}] > \\delta_1 \\text{\"}\n$$\n\nHere, $y$ denotes the vector of logits for all pixels in the SSN output that can be generated from perturbed images in $\\mathbf{I}$. The confidence of guarantee, $\\delta_2$, then implies:\n\n$$\n\\Pr[ \\mathsf{P} = \\text{True}] > \\delta_2\n$$\n\nwhere since $\\mathbf{S}$ is generated via conformal inference using a pre-defined configuration ($ell,m$) we can say,\n\n$$\n\\delta_2 = 1 - \\mathsf{betacdf}_{\\delta_1}(\\ell, m + 1 - \\ell)\n$$\n\nFor example:\n* If we set $\\delta_1 = 0.995$, then $\\delta_2 = 1 - \\mathsf{betacdf}_{0.995}(7999, 2) = 0.99999999999999994$\n* If we set $\\delta_1 = 0.999$, then $\\delta_2 = 1 - \\mathsf{betacdf}_{0.999}(7999, 2) = 0.997$\n* If we set $\\delta_1 = 0.9995$, then $\\delta_2 = 1 - \\mathsf{betacdf}_{0.9995}(7999, 2) = 0.9085$\n\nUsing the pair $(\\delta_1, \\delta_2) = (0.999, 0.997)$, we can formally state that:\n\n$$\n\\Pr\\big[ \\underbrace{\\Pr[y \\in \\mathbf{S}] > 0.999}_{\\mathsf{P:=}} \\big] > 0.997\n$$\n\nNow suppose we input this reachable set $\\mathbf{S}$ into Algorithm 2 and find that 691,100 pixels are classified as **robust**, 100 as **unknown**, and 0 as **non-robust**. The RV is then computed as:\n\n$$\n\\text{RV} = \\frac{691{,}100}{720 \\times 960} \\approx 99.98\\%\n$$\n\nThis means the guarantee\n\n$$\n\\Pr\\left[ \\Pr[y \\in \\mathbf{S}] > 0.999 \\right] > 0.997\n$$\n\ntranslates directly into the guarantee:\n\n$$\n\\\\Pr\\\\left[ \\\\Pr[\\\\text{RV} = 99.98\\\\%] > 0.999 \\\\right] > 0.997\n$$\n\nIn other words, verifying the former implicitly verifies the latter. Therefor, if we generate a reachable  $\\mathbf{S}$, with that provable level of guarantee and introduce it to algorithm 2 and find out 691,100 pixels are robust then we have verified the correctness of the following guarantee:\n\n$$\n\\\\Pr\\\\left[ \\\\Pr[\\\\text{\" RV is }  99.98 \\\\% \\\\text{\" } ] > 0.999 \\\\right] > 0.997\n$$\n\nQ2:\n\nThank you for your question. Below, we explain the factors that influence the average runtimes, particularly in the CamVid and Lung Segmentation experiments shown in Table 3.\n\n**Factors Affecting Runtime:**\n\nWhen using the **naïve technique**, the runtime is primarily influenced by four factors:\n\n1. The **size of the calibration dataset** $m$,\n2. The **size of train dataset** $t$,\n3. The **inference time** of the model, and\n4. The **memory footprint** on each output vector on the GPU or CPU memory.\n\nThe rest of the computation—such as statistical post-processing—has a negligible impact on runtime.  However, inference speed can vary significantly depending on how it is executed. Performing inference on a **GPU with batch processing** is considerably faster than using a **CPU with parallel processing**. Additionally, we collect a training dataset to compute normalization factors used in the definition of the nonconformity score, and this data collection time must also be accounted for.\n\nWhen using the **surrogate-based technique**, all the factors mentioned above still apply, but there are additional components that impact runtime:\n\n* The time required to compute the **top principal directions** (PCA),\n* The time to **train the surrogate model**, and\n* Although relatively minor, the time required for **deterministic reachability analysis** on the surrogate model (since the surrogate is intentionally kept small and efficient).\n\n**Why CamVid Has Higher Runtime Than Lung Segmentation:**\n\nThe runtime for the CamVid dataset is noticeably higher than for Lung Segmentation due to several factors:\n\n* **Model complexity:** CamVid uses **BiSeNet**, which has a more complex architecture and higher inference time compared to **UNet**, used in Lung Segmentation.\n* **Output dimensionality:** The output mask of UNet in the Lung Segmentation task is significantly smaller than that of BiSeNet in CamVid. Smaller outputs reduce memory requirements for each vector and enable more efficient batch processing during inference. As a result, we can process larger batches in the Lung Segmentation setting, which leads to a substantial reduction in overall verification time.\n\n**Additional Notes:**\n\n* The **verification runtime is independent of perturbation size**. That is, verifying for $e = 3/255$ takes approximately the same amount of time as verifying for $e = 155/255$.\n* In the updated version of the paper, we include a chart in the appendix visualizing the runtime across all experiments introduced in RQ1.\n* Although increasing the perturbation size $e$ does not increase runtime, it does increase the conservatism of the reachable set if the size of training dataset is not also increased. While the probabilistic guarantee still holds in such cases, the conservatism may become more pronounced. Thus we suggest increasing the size of training dataset if the perturbation size is larger.\n\n---\n---"}, {"review_id": "6PGC3M49Cs", "reviewer": "Reviewer_BgoC", "summary": "The paper proposes a three-stage pipeline that delivers pixel-level robustness certificates with finite-sample calibration for full-resolution semantic segmentation networks (SSNs). First, in the naïve conformal reachability stage, a calibration set of size m is used to construct an axis-aligned hyper-rectangle that, with user-defined risk level ϵ, contains the SSN’s logits under an input-uncertainty distribution. Second, in the surrogate + star-set inflation stage, a small ReLU surrogate model g is trained; its exact star-set reach set is computed using NNV and then expanded via a Minkowski sum with an error-bound hyper-rectangle derived through conformal inference, resulting in a significantly tighter reach set. Third, deflation-based PCA is used to address the extremely high dimensionality of SSN outputs: the top-N principal directions are learned, allowing g to operate in a low-dimensional latent space and be lifted back linearly to the original space. The final reach set is projected onto per-pixel logits to determine whether each pixel is robust, non-robust, or uncertain. Experiments on M2NIST, Lung_Segmentation, CamVid, and a CIFAR-100 classifier show that the method certifies ≥99.9% robustness value (RV) at ≥0.999 confidence, with runtimes ranging from 3 seconds to 60 minutes on a single 48 GB GPU.", "questions": "Hyper-parameter sensitivity: Please sweep calibration size *m* and PCA rank *N*; plot RV vs. runtime.  How fast does the guarantee degrade if *m* is cut 10×? How sensitive is the model to m and N?\n\nDataset coverage: Would the model also work on Cityscapes and ADE20K since those are important datasets in the field?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Quality:\n+ S: Runtime scales to 960 × 720 outputs where deterministic tools have difficulties.\n+ S: Empirical study uses three metrics (RV, RS, RIoU) and reports per-experiment (ℓ, *m*) choices (Table 3).\n- W: The choice of the number of PCA components N is treated as a fixed hyperparameter without a principled selection method, which may affect generality and reproducibility. No ablation on PCA rank N and hyper-parameter sensitivity is unknown.\n\nClarity:\n+ S: Incremental step by step explanation naïve - surrogate - PCA.\n- W: Minor issues—Algorithm 1 lacks a stop-criterion.\n\nSignificance:\n+ S: The method significantly reduces runtime compared to pixel-wise conformal prediction, while scaling to high-dimensional outputs using PCA and star sets\n- W: Evaluation omits standard datasets Cityscapes/ADE20K used in prior CP work  and smoothing papers. At least they should appear in the discussion regarding their applicability due to their importance.\n\nOriginality:\n+ S: Novel integration of CI with star-set reachability via combining these techniques for segmentation.\n+ S: PCA-deflation surrogate training adapts sparse-PCA ideas to verification.\n- W: The individual ingredients (CI, star sets, PCA) exist; novelty stems from synergy more than new theory.", "was_revised": true, "final_justification": "After considering the authors' rebuttal and the discussions, I maintain my original evaluation. Here is a summary of the issues that were resolved and of those that remain:\n\nThe authors clarified that Algorithm 1 includes two principled stopping criteria in practice—variance threshold and a hard cap on the number of directions. This resolves my concern about clarity in algorithmic description and adds confidence in the implementation robustness.\n\nThe authors committed to adding an ablation study on hyperparameters such as calibration size m and PCA rank N. Even though not present in the original submission, this plan addresses the concern.\n\nThe authors provided a new evaluation on the Cityscapes dataset. This strengthens the significance and applicability of the method.\n\nHowever, The core techniques—CI, PCA, and surrogate modeling—are not new. The paper’s value lies in their integration and adaptation to the challenging SSN setting. While effective, this limits the theoretical novelty.\n\nMy Recommended Score: 4 (Borderline Accept)", "rebuttal": "We appreciate your detailed feedback\n\n---\n---\n\n***Response to Reviewer’s Comments on Weaknesses***\n\n**W (Quality):**\nAlgorithm 1 is presented in a simplified form for clarity, but in our implementation, the SGD-based deflationary PCA procedure includes two termination criteria:\n\n1. The first criterion is based on variance: the algorithm stops when the optimal variance captured in the current iteration falls below 1% of the optimal variance recorded in the first iteration. Since each iteration involves an optimization with no local maxima, it is guaranteed that the optimal variance captured in each subsequent iteration decreases monotonically.\n\n2. The second criterion is a fixed upper bound on the number of principal directions, which we set to $N = 1000$. If the number of extracted directions exceeds this value, the algorithm terminates automatically.\n\nThe PCA process stops as soon as **either** of these conditions is satisfied.\n\nWe agree that a principled analysis of sensitivity to the PCA rank $N$ is valuable. Therefore, we will include an ablation study in the appendix to evaluate the effect of this and other hyperparameters (e.g., $m$, $N$) on the performance and robustness of our method.\n\nRegarding the choice of $N = 1000$: In case the correlation matrix of logit dimensions is not approximately sparse, this number may sometimes be insufficient for achieving an accurate surrogate model. However, this does **not** pose a significant problem for our framework. The goal of the surrogate model is **not** to perfectly approximate the SSN but rather to **reduce the conservatism** that exists in the naïve technique. In practice, even a moderately trained surrogate model yields a tighter reachable set than the naïve approach, which is consistent with our experimental observations and we have provided a justification here for your review.\n\n**Supporting Justification:**\nIn the naïve technique, the outputs collected in the training set are approximated using their mean-value, and conformal inference is applied to the prediction errors, resulting in a hyperrectangular reachable set. In contrast, the surrogate-based method fits a small ReLU network to better approximate the outputs. One can, for example, initialize the surrogate model to output a constant equal to the mean of the training data in the beginning of the training process. This initialized model performs exactly as the naive technique and results in the same hyper-rectangular reachset. They also can use **quantile regression**—specifically, the $\\delta_1$-quantile of prediction errors—as the loss function. Regardless of how well the surrogate is trained, the quantile of prediction errors will be **strictly lower** than in the initialized model. This ensures that the resulting reachable set is tighter than that produced by the naïve method.\n\nHowever, due to the high output dimensionality of SSNs, directly training the surrogate without dimensionality reduction was computationally infeasible due to gradient-related challenges. PCA was therefore used to reduce the dimensionality of the output space, enabling us to start training the surrogate model and reduce the quantile of the prediction errors. Thus we achieve a tighter probabilistic reachable set that has the same level of guarantee with the naive technique.\n\n---\n\n**W (Clarity):** Algorithm 1, in its current form on the submission, is implemented as a for-loop with a fixed number of iterations $N$, and therefore terminates automatically after $N$ steps.\n\n---\n\n**W (Significance):**\nAs suggested by Reviewer 2, we conducted new experiments comparing our method with two recent works that perform probabilistic verification via randomized smoothing. Specifically, we compared our technique with these methods on the verification of an **HRNetV2 model with a W48 backbone** (66M parameters) trained on the **Cityscapes** dataset. Our numerical results show that our approach is approximately **100 times less conservative** than the baselines.\n\nDetails of this experiment are provided in our response to Reviewer 2, and we would greatly appreciate it if you could take a look. We have also cited these works in the **Related Work** section of the updated manuscript.\n\n---\n\n**W (Originality):** As noted, the core techniques used in our framework—conformal inference, surrogate modeling, and PCA—are individually well-established. However, our contribution lies in their novel integration and adaptation to the verification of semantic segmentation networks (SSNs), a high-dimensional and structured output setting where existing methods struggle with scalability or conservatism. This combination results in an efficient and practically useful verification algorithm.\n\n---\n---\n\n***Answer to Questions***\n\nQ1:\n\n**Hyper-parameter sensitivity:** \n\n---\n\nQ2:\n\n**Dataset coverage:** Our verification algorithm is architecture-agnostic and should work on both the Cityscapes and ADE20K datasets. As previously mentioned, we conducted a new experiment on the Cityscapes dataset, which has now been included in the updated manuscript. The average runtime for this experiment was 210 seconds, and the model we analyzed had 66 million parameters.\n\n---\n---"}]

Author rebuttal:

Meta-review: This paper explores probabilistic verification of the robustness of semantic segmentation networks (SSN). To this end, the paper mainly leverage conformal prediction over reachsets, providing robustness guarantees.


**Strengths**:
* handling an important problem – robustness of SSNs
* novel perspective on certified robustness guarantees – leveraging conformal prediction for probabilistic verification on SSNs
* scalable compared to deterministic verification

**Weaknesses**:
* narrow evaluation 
* lack of interpretation on qualitative results

This is a borderline paper but the strengths outweigh the weaknesses, so I and most reviewers  agree for acceptance. 

Please update the final manuscript, including, but not limited to, the following promised points:

* The additional results and comparisons to related works (including the extended [b] and [d] table and the Cityscapes/HRNetV2 experiments) are included in the paper.
* The clarifications and additional details from the author responses are integrated, including the distinction between the naive and surrogate methods, and the justification for the chosen threat models.
* The major limitations are explicitly discussed in a limitations section, including (1) the distributional assumption, which may not hold in an adversarial setting, (2) the requirement of recomputing the calibration set for each test point, and (3) the scalability limitations wrt the input dimension of the surrogate approach.
Decision: Accept (poster)