<figure><img src="image_1.png" /></figure>

HAL
open science

# Fast and Flexible Robustness Certificates for Semantic Segmentation

Thomas Massena, Corentin Friedrich, Franck Mamalet, Mathieu Serrurier

<figure><img src="image_2.png" /></figure>

## To cite this version:

Thomas Massena, Corentin Friedrich, Franck Mamalet, Mathieu Serrurier. Fast and Flexible Robustness Certificates for Semantic Segmentation. 2025. hal-05393092

HAL Id: hal-05393092

https://hal.science/hal-05393092v1

Preprint submitted on 2 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Fast and Flexible Robustness Certificates for Semantic Segmentation

Thomas Massena<fnref n="1" />,<fnref n="3" />

Corentin Friedrich<fnref n="2" />

Franck Mamalet<fnref n="2" />

Mathieu Serrurier<fnref n="1" />

## Abstract

Deep Neural Networks are vulnerable to small perturbations that can drastically alter their predictions for perceptually unchanged inputs. The literature on adversarially robust Deep Learning attempts to either enhance the robustness of neural networks (e.g., via adversarial training) or to certify their decisions up to a given robustness level (e.g., by using randomized smoothing, formal methods or Lipschitz bounds). These studies mostly focus on classification tasks and few efficient certification procedures currently exist for semantic segmentation. In this work, we introduce a new class of certifiably robust Semantic Segmentation networks with built-in Lipschitz constraints that are efficiently trainable and achieve competitive pixel accuracy on challenging datasets such as Cityscapes. Additionally, we provide a novel framework that generalizes robustness certificates for semantic segmentation tasks, where we showcase the flexibility and computational efficiency of using Lipschitz networks. Our approach unlocks real-time compatible certifiably robust semantic segmentation for the first time. Moreover, it allows the computation of worst-case performance under $l_2$ attacks of radius $\epsilon$ across a wide range of performance measures. Crucially, we benchmark the runtime of our certification process and find our approach to be around 600 times faster than randomized smoothing methods at inference with comparable certificates on an NVIDIA A100 GPU. Finally, we evaluate the tightness of our worst-case certificates against state-of-the-art adversarial attacks to further validate the performance of our method.

## 1. Introduction

Deep Neural Networks (DNNs) have transformed the landscape of machine learning, driving breakthroughs across perception, reasoning, and decision-making tasks. Yet, their remarkable expressivity comes at the cost of a vulnerability to carefully crafted adversarial perturbations [8]. These weaknesses raise critical concerns when deploying Machine Learning (ML) systems in safety-critical contexts such as

autonomous driving or healthcare, where guarantees on the reliability of decisions are crucial [44].

While obtaining robustness certificates for tasks other than classification has been attempted in the context of formal verification methods [10] and randomized smoothing [7, 12]. Lipschitz-by-design methods, introduced in Tsuzuku et al. [39], were never adapted to provide downstream certificates for more complex tasks than classification or regression. Our contributions are as follows:

* First, we introduce a general class of robustness certificates for segmentation tasks, tailored to certify the robustness of a variety of performance measures to general adversarial degradation objectives. We propose certificates for worst case performance under attack and minimum adversarial budgets required to satisfy an adversarial objective.

* Then, using this framework, we build certificates for the Pixel Accuracy, FNR or Class IoU performance measures under attack using the Lipschitz constant of a model.

* Additionally, we develop the first efficiently trainable Lipschitz-constrained neural network models for safety-critical semantic segmentation tasks using a DeepLabV3-like architecture, suitable for challenging tasks like the Cityscapes dataset.

* Leveraging our framework along with Lipschitz networks, we compute robustness certificates for several safety-critical scenarios. Most importantly, our networks are suitable for real-time inference and we provide the first certifiably robust method that allows the computation of robustness certificates in less than 0.1 seconds on 1024 by 1024 images from the Cityscapes dataset.

Additionally we provide a code-base available on GitHub, that allows the training and certification of Lipschitz-constrained neural networks in $l_2$ norm on segmentation tasks.

## 2. Background on Adversarial Robustness

In this section, we will introduce some key concepts and their formulations in the context of classification tasks. Then, we will present relevant certifiable robustness works in the context of semantic segmentation.

<footnote n="1">¹Institut de Recherche en Informatique de Toulouse</footnote>

<footnote n="2">²IRT Saint-Exupery</footnote>

<footnote n="3">³SNCF, DTIPG</footnote>
**Notations** In our settings, we will denote $\mathcal{X}$ as the input space, $\mathcal{Y}$ as the output space, $\mathcal{K}$ as the label space and $\Omega$ as the coordinate space (e.g the images, masks, classes and pixel indexes respectively). In the following sections, we denote a general semantic segmentation model as $f: \mathcal{X} \to \mathcal{Y}$, with $\mathcal{X} := [0, 1]^{|\Omega|}$, $\mathcal{Y} := \mathbb{R}^{|\mathcal{K}| \times |\Omega|}$ and $|\cdot|$ the cardinality measure of a set. More specifically, in certain cases, we will refer to dimension sizes $K$, $H$ and $W$ which stand for the class, height and width dimensions of images respectively. Also, we denote $\mathcal{B}_p^\epsilon(x)$ as the $p$-norm ball of radius $\epsilon$ around $x$. Finally, we denote the output of a segmentation model as $f(X)$, its coordinate-wise predictions (e.g for pixels) as $f(X)_\omega \in \mathbb{R}^{|\mathcal{K}|}$ and $f^k(X)_\omega$ as the output associated to class $k \in \mathcal{K}$ for coordinate $\omega \in \Omega$. Finally, we denote the predicted class by a semantic segmentation network at coordinate $\omega \in \Omega$ as $\tilde{Y}_\omega = \arg\max_{k \in \mathcal{K}} f^k(X)_\omega$, which becomes $\tilde{Y}_\omega = \arg\max_{k \in \mathcal{K}} f^k(\tilde{X})_\omega$ for an attacked input $\tilde{X} \in \mathcal{B}_p^\epsilon(X)$.

## 2.1. Adversarial Robustness in the Classification Setting

Seminal adversarial deep learning works originally mostly focused on designing adversarial attacks to fool deep neural classification models [8]. To this day, a sizeable proportion of adversarial deep learning works still focus on designing maximally efficient attacks on classification tasks. In the following paragraphs, we define the key concepts surrounding certifiable adversarial robustness in the context of classification tasks.

**Definition 1** (Robustness radius - classification). For any predictive model, $f: \mathcal{X} \to \mathbb{R}^{|\mathcal{K}|}$ and any test point $(X, Y)$, we define:

$$R(X, Y) = \inf \{ \epsilon \in \mathbb{R}^+ | \exists \tilde{X} \in \mathcal{B}_p^\epsilon(X), \\ \qquad \arg \max_{k \in \mathcal{K}} f^k(\tilde{X}) \neq Y \}. \quad (1)$$

as the robustness radius of the model prediction.

This definition is widely adopted in the context of certifiably robust classification and allows to characterize how “invariant” a neural network’s prediction is to local perturbations. In practice, there are multiple ways of obtaining a lower bound on the value of the robustness radius as defined in Definition 1. We can distinguish three main competing approaches to lower-bound the robustness radius of a DNN’s prediction locally. Namely, formal-verification methods, randomized smoothing based variants, and Lipschitz neural networks stand out as the most popular approaches.

* **Formal verification methods:** allow for the computation of worst-case logit variations under $\epsilon$-bounded $\ell_p$-norm attacks [38] at inference by using formal-based solvers.

* **Randomized smoothing methods:** which define a smoothed classifier $g$ that is estimated via Monte-Carlo methods [9, 19]. This smooth classifier is then certifiable probabilistically when using well-chosen sampling distributions [42].

* **Lipschitz neural networks:** which leverage a by-design Lipschitz upper bound to compute worst-case logit variations with no inference time overhead.

Importantly, all of these methods allow the user to find a conservative lower bound $\underline{R}(X, Y) \le R(X, Y)$ such that no adversarial attack inferior to $\epsilon$ in $\ell_p$ norm could misclassify the originally correctly classified sample $X$. These robustness lower bounds are usually coined as robustness certificates.

## 2.2. Lipschitz Certificates for Classification

A function $f: \mathbb{R}^m \to \mathbb{R}^n$ is said to be $L$-Lipschitz in $\ell_p$ norm if it verifies:

$$\forall (X_1, X_2) \in \mathbb{R}^m, \|f(X_1) - f(X_2)\|_p \le L \cdot \|X_1 - X_2\|_p \quad (2)$$

with $L > 0$. This property effectively bounds how “stable” a predictor’s decision remains under perturbations. Moreover, Lipschitz continuous neural networks are universal approximators like their unconstrained counterparts on tasks other than regression (c.f Section 6 of Anil et al. [1]).

**Proposition 1** (Classification robustness bound). For any $L$-Lipschitz predictive model in $\ell_p$ norm, $f: \mathbb{R}^d \to \mathbb{R}^{|\mathcal{K}|}$, we have the following lower bound on $R(X, Y)$:

$$R(X, Y) \ge \mathbf{1}_{\hat{Y}=Y} \cdot 2^{\frac{1-p}{p}} \cdot \mathcal{M}_X(f)/L. \quad (3)$$

with $\mathcal{M}_X(f) = f^{\text{top1}}(X) - f^{\text{top2}}(X)$, as explicated in [20]. Here, the $\mathbf{1}_{\{\hat{Y}=Y\}}$ term ensures that the robustness radius of originally misclassified samples is zero.

We have that Lipschitz-constrained networks allow for easily computable robustness radius lower bound computations by using the global Lipschitz constant of a specially designed neural network.

## 2.3. Related Works on Robust Segmentation

While adversarial robustness has been extensively investigated for image classification, the robustness of semantic segmentation models has received comparatively less attention. Early work by Arnab et al. [2] provided one of the first systematic analyses of adversarial examples on modern semantic segmentation architectures, showing that dense prediction exhibits vulnerability patterns that differ from standard classification. Building on segmentation-specific threat models, Rony et al. [33] introduced a
proximal-splitting-based adversarial attack that directly optimizes dense pixel-wise perturbations and yields substantially stronger white-box baselines than attacks adapted from classification, providing a stronger benchmark for assessing segmentation robustness. These works underline that semantic segmentation robustness remains relatively underexplored compared to the classification case and motivate further study in safety-critical domains such as automated driving perception, for which broader surveys of certified robustness have recently been proposed [44]. In the context of certifiably robust Semantic Segmentation the overall approaches to certification remain the same as for classification. However, the high dimensionality of the neural segmentation network's outputs complicate the analysis. We can denote two main existing approaches to robust semantic segmentation tasks.

**Formal verification methods** While some formal-verification methods allow for the verification of a segmentation network's predictions on toy datasets [38], formal-based certifiable methods lack scalability or end up providing vacuous bounds which are not applicable to over-parametrized networks that segment high resolution images. Indeed, these methods usually have time complexities that grow quadratically with the number of neurons and layers of the model [15]. Therefore, even the most prestigious neural network verification competitions only include verification tasks for simple semantic segmentation networks with less than a million parameters [26]. Currently, specific approaches to robust semantic segmentation using formal-based methods include patch-based attack defenses [24] and approaches that can segment MNIST-like images with pixel-wise certificates [28].

**Randomized Smoothing** In the context of semantic segmentation, Fischer et al. [12] first applied randomized smoothing to certify subsets of pixel-wise predictions up to a unique robustness radius $R$ with probability $1 - \alpha$. Indeed, the authors find that applying randomized smoothing naively to the $H \times W$ classifications provided by the segmentation network requires too many samples to certify the validity of all pixel classifications with probability $1 - \alpha$. Therefore, they approach certification as a multiple-testing problem where the SEGCERTIFY method controls the family-wise error rate at level $\alpha$ using a step-down procedure to ensure the validity of the segmentation of a whole image up to a user-chosen error probability $\alpha$. To improve empirical performance while preserving the global confidence level, pixels whose smoothed predictions do not achieve the required confidence are assigned to an abstention set. Unfortunately, this method requires running multiple forward passes for the model, which is even more cumbersome than in the classification setting, given that the

memory requirements of segmentation models are usually high. Moreover, the computation of statistical processes for each pixel in the image also add a significant runtime overhead. Therefore, these methods are currently unusable for systems where predictions need to be inferred in generally less than a second.

More recently, the LOCALIZEDLP method was introduced in Schuchardt et al. [36]. This method improves on the SEGCERTIFY method by leveraging the local dependencies of semantic segmentation networks via isotropic Gaussian smoothing. Unfortunately, this improvement comes at a price in terms of sample complexity as LOCALIZEDLP uses around $15 \times$ more MC iterations that SEGCERTIFY, as explicit in Section 7.1 of [36]. For reference, the implementation of Schuchardt et al. [36] uses a DeepLabV3 architecture similar to ours on the Cityscapes dataset, and reports 1204 seconds of runtime per image by using 153600 Monte Carlo iterations. Therefore, we do not compare the efficiency of our method to the LOCALIZEDLP method given that it is clearly not suited for fast inference scenarios.

## 3. Unifying Semantic Segmentation Robustness Metrics

The notion of adversarial robustness in semantic segmentation is not clearly defined, and relies on sparse metrics introduced throughout the literature. Adversarial attacks usually aim to increase a proxy loss function with a fixed perturbation budget $\epsilon$, in order to decrease the pixel accuracy and the mIoU. In contrast, the attack introduced in [33] seeks the minimal budget to successfully perturb at least $\gamma\%$ of pixels. Regarding defenses, some works focus on certifying pixel-wise classification [12, 38], whereas others ensure collective robustness certificates for the classification of pixel subgroups [36]. In this section, we present a general framework that unifies the notion of robustness, especially for semantic segmentation.

**Two paradigms of robustness** In a safety-critical setting, robustness at a given sample $(X, Y)$ can be addressed from two different perspectives. We express these perspectives as the following questions.

**Q1** — Given an adversarial budget $\epsilon$, what is the worst performance I could reach?

**Q2** — If I want to degrade the performance metric to satisfy a degradation objective $\kappa$, what adversarial budget do I need?

Most attacks and certifiable defenses try to answer **Q1** by degrading the usual segmentation metrics (i.e. pixel accuracy or mIoU) with a fixed budget. Answering **Q2** is less common. For example, Rony et al. [33] consider the degradation of the pixel accuracy metric with the objective of less
than γ%. In the following, we present two novel definitions to answer both questions: we define the worst-case performance for Q1, and the generalized robustness radius for Q2.

**Definition 2 (Worst-case performance).** For any predictive model $f: \mathcal{X} \to \mathcal{Y}$, and performance metric $h: \mathcal{Y} \times \mathbb{R}^{[\Omega]} \to \mathbb{R}$, we define the $\epsilon$ worst-case performance measured on a data point $(X, Y)$ as:

$$h_{\epsilon}(X, Y) = \min_{\tilde{X} \in \mathcal{B}_{p}^{\epsilon}(X)} h(f(\tilde{X}), Y). \quad (4)$$

In our setting, we assume that $h$ is positively correlated with system performance, i.e "higher is better".

For example with $h$ being the pixel accuracy measure, $h_{\epsilon}$ is the minimum reachable pixel accuracy on an image and mask pair $(X, Y)$ under fixed adversarial budget $\epsilon$.

**Definition 3 (Generalized robustness radius).** For any predictive model $f: \mathcal{X} \to \mathcal{Y}$, performance metric $h: \mathcal{Y} \times \mathbb{R}^{[\Omega]} \to \mathbb{R}$, and degradation objective $\kappa: \mathbb{R} \to \{0, 1\}$, we define the generalized robustness radius on a data point $(X, Y)$ as:

$$R_{\kappa}(X, Y) = \inf\{\epsilon \in \mathbb{R}^{+} \mid \exists \tilde{X} \in \mathcal{B}_{p}^{\epsilon}(X), \\ \kappa[h(f(\tilde{X}), Y)] = 1\}. \quad (5)$$

The degradation objective $\kappa$ on performance metric $h$ is either unsatisfied (0=failure) or satisfied (1=success).

This definition allows us to define a robustness radius for any desired adversarial degradation objective $\kappa$ on performance measure $h$ in a variety of different scenarios<fnref n="1" />. For example, with $h$ being the pixel accuracy, and $\kappa(z) = 1_{\{z \le \gamma\}}$ the degradation objective, the radius $R_{\kappa}$ is the minimum budget to reach a pixel accuracy below $\gamma\%$ under attack.

Computing exactly $h_{\epsilon}$ and $R_{\kappa}$ is infeasible in practice. In certified robustness, we answer Q1 and Q2 by computing lower bounds (also called certificates) on $h_{\epsilon}$ and $R_{\kappa}$. Section 4.1 will illustrate how to compute those certificates for the pixel accuracy metric.

## 4. Fast Estimation of Robustness Certificates

In the following Section, we show how to use Lipschitz certificates to give lower-bound approximates for questions Q1 and Q2 efficiently.

**Computing certificates** In order to compute the worst-case performance variations of an L-Lipschitz predictor under $\epsilon$-bounded attacks, we leverage:

$$\begin{align} h_{\epsilon}(X) &= \min_{\delta \in \mathcal{B}_{p}^{(0)}} h(f(X + \delta), Y) \tag{6} \\ &\ge \min_{\alpha \in \mathcal{B}_{p}^{L\epsilon}(0)} h(f(X) + \alpha, Y). \nonumber \end{align}$$

This conversion from input space perturbations in $\mathcal{B}_{p}^{\epsilon}(X)$ to output perturbations in $\mathcal{B}_{p}^{L\epsilon}(f(X))$ comes directly from the L-Lipschitz property of the neural network $f$ (for the sake of completeness a proof is given in Appendix A). Note that this lower bound is pessimistic, since not every output perturbation $\alpha$ is attainable from an input in $\mathcal{B}_{p}^{\epsilon}(X)$. Therefore, the bounds we propose in this paper do not account for local feasibility constraints in the neighborhood of $X$ (as previously discussed in Section 3.2, Eq. 1 of Schuchardt et al. [36]). However, using this assumption allows our method to operate with negligible computational overhead, as opposed to concurrent computationally intensive approaches.

### 4.1. Application to the Pixel Accuracy Metric

For a subset $S \subseteq \Omega$, we define the pixel accuracy on $S$ by $h: \mathcal{Y} \times \mathbb{R}^{[S]} \to \mathbb{R}$ as:

$$h(f(X), Y) = \frac{1}{|S|} \sum_{\omega \in S} \mathbf{1}_{\hat{Y}_{\omega} = Y_{\omega}} \quad (7)$$

with $\hat{Y}_{\omega}$ the decision at the pixel $\omega$. Note that $S = \Omega$ is the classical pixel accuracy measure on the full image. We define the Robust Pixel Accuracy (RPA) $h_{\epsilon}(X) = \min_{\tilde{X} \in \mathcal{B}_{\epsilon}(X)} h(f(\tilde{X}), Y)$ as the exact worst-case pixel accuracy under attack. In practice, following Eq. (6), we consider the Certifiably Robust Pixel Accuracy CRPA$_{\epsilon}(X)$ which is a lower bound to RPA.

**Deriving an answer to Q1** Here, we aim to answer the following question: What is the maximal degradation of pixel accuracy that can be achieved given an adversarial budget $\epsilon$?

We can start with the Lipschitz certificates introduced in Proposition 1. Indeed, we recover a certificate for any particular pixel of coordinate $\omega \in \Omega$:

$$R^{\omega}(X, Y) := \mathbf{1}_{\hat{Y}_{\omega} = Y_{\omega}} \cdot 2^{\frac{1-p}{p}} \cdot \mathcal{M}_{X}^{\omega}(f)/L, \quad (8)$$

with $\mathcal{M}_{X}^{\omega}(f) = f^{\text{top1}}(X)_{\omega} - f^{\text{top2}}(X)_{\omega}$. Thus, $L \cdot R^{\omega}(X, Y)$ represents the minimal norm of the perturbation $\alpha_{\omega}$ on the logs of pixel $\omega$ such that $f(X)_{\omega} + \alpha_{\omega}$ is misclassified. Note that $R^{\omega}(X, Y)$ is equal to zero for pixels already misclassified by $f(X)$.

We propose to reformulate the CRPA$_{\epsilon}(X)$ computation as a Knapsack Problem [34]. Let $p_{\omega}$ be a binary variable

<footnote n="1">¹Note that $\kappa$ could also be defined as $\kappa: \mathbb{R} \times \mathbb{R} \to \{0, 1\}$ with $\kappa[h(f(\tilde{X}), Y), h(f(X), Y)]$ to ensure robustness to degradations that are relative to the performance of the network on a clean point (e.g the accuracy must be at least half of the original accuracy).</footnote>
that equals 1 when pixel $\omega$ is in the set of misclassified pixels under attack. We consider the evaluation of the maximum number of perturbed pixel under constraint:

$$ N_{\text{PA}}(X, \epsilon) = \max \sum_{\omega \in S} p_{\omega} \\ \text{s.t.} \quad \sum_{\omega \in S} L^p c_{\omega} p_{\omega} \le (L\epsilon)^p \quad (9) $$

with $c_{\omega} = R^{\omega}(X, Y)^p$ the cost for a given pixel $\omega$. Here, the linear constraint $\sum_{\omega \in \Omega} L^p c_{\omega} p_{\omega} \le (L\epsilon)^p$ corresponds to the condition $\alpha \in B_p^{L\epsilon}(0)$ in Eq. (6) coupled with the disjoint support of output perturbations that induce pixel misclassifications. We can thus derive the following lower bound for the certification of Q1:

$$ \text{CRPA}_{\epsilon}(X) = 1 - \frac{N_{\text{PA}}(X, \epsilon)}{|S|}. \quad (10) $$

The unidimensional Knapsack Problem described in Eq. (9) can be solved optimally in $O(|S|)$ time by sorting pixels by ascending contribution $c_{\omega}$ and greedily adding them until the capacity is exhausted [34]. This corresponds to the selection of less robust pixels first (already misclassified pixel having a null robustness).

By denoting $\pi_X : |S| \to S$ as a map that sorts pixel coordinates of $X$ in ascending order of robustness according to the value of $R^{\omega}(X, Y)$, we define:

$$ N_{\text{SUP}}(X, \epsilon, S, R^{\omega}) = \sup \left\{ n \in \mathbb{N} \mid \sum_{k=1}^{n} R^{\pi X(k)}(X, Y)^p \le \epsilon^p \right\}. \quad (11) $$

The solution of the Knapsack problem in Eq. (9), is given by $N_{\text{PA}}(X, \epsilon) = N_{\text{SUP}}(X, \epsilon, S, R^{\omega})$. This estimation process can be efficiently parallelized and run on GPU architectures which results in negligible overhead for the certification process compared to the forward pass of a DNN.

**Deriving an answer to Q2** We now seek to answer the question: What is the maximum attack level $\epsilon$ under which the pixel accuracy is guaranteed to remain above or equal to $\gamma$?

First, we can translate the question into a degradation criterion as defined in our framework using the previously defined pixel accuracy measure $h$:

$$ \kappa[h(f(\tilde{X}), Y)] = \mathbf{1}_{h(f(\tilde{X}), Y) \le \gamma}. \quad (12) $$

This corresponds to assessing the minimum norm perturbation under the constraint that at least $\lceil \gamma \cdot |S| \rceil$ pixels are misclassified. We define $n_{\gamma} := \lceil \gamma \cdot |S| \rceil$. Once more, this can be formulated as a Knapsack Problem<fnref n="2" />:

<figure><img src="image_4.png" /><figcaption>Figure 1. (Left) The $\epsilon$ budget required to attack dense segmentations to make all but $N_{\text{min}}$ pixels change. (Right) We display only the groups of predictions where $\epsilon \ge 0.1$, non-robust pixel groups are in white.</figcaption></figure>

$$ R_{\kappa}(X, Y)^p \ge \min \sum_{\omega \in S} c_{\omega} p_{\omega} \\ \text{s.t.} \quad \sum_{\omega \in S} p_{\omega} \ge n_{\gamma}. \quad (13) $$

As for Q1, the solution of Eq. (13) can be solved using the sorted pixels by:

$$ \underline{R}_{\kappa}(X, Y, S, R^{\omega}, n_{\gamma})^{p} = \sum_{k=1}^{n_{\gamma}} R^{\pi X(k)}(X, Y)^{p}. \quad (14) $$

$\underline{R}_{\kappa}$ defines the Generalized Robustness lower-bound radius for the $\gamma$ pixel accuracy over a subset $S \subseteq \Omega$ of the pixels of image $X$. Note that if the clean accuracy is inferior to the threshold $\gamma$, the solution $\underline{R}_{\kappa} = 0$, since $c_{\omega} = 0$ for all misclassified pixels.

## 4.2. Application to FNR and Stability Metrics

In this section, we consider the certification of other prediction-based performance robustness measures.

**FNR** To compute the robustness certificates for the FNR measure on a binary semantic segmentation task, we consider the subset $S_1 = \{\omega \in \Omega, Y_{\omega} = 1\}$, and the performance measure

$$ h_{\text{FNR}} = \frac{1}{|S_1|} \sum_{\omega \in S_1} \mathbf{1}_{\hat{Y}_{\omega} = Y_{\omega}} = 1 - \text{FNR}(\hat{Y}, Y). \quad (15) $$

We can derive an answer to Q1 for FNR: “Which maximum level of FNR can we attain under bounded noise level $\epsilon$?” Similarly to PA, we can compute the maximum number of misclassified pixels in $S_1$ under an $\epsilon$ budget by

$$ N_{\text{FNR}}(X, \epsilon) = N_{\text{SUP}}(X, \epsilon, S_1, R^{\omega}) \quad (16) $$

This provides a lower bound:

$$ \text{FNR}(\hat{Y}, Y) \le N_{\text{FNR}}(X, \epsilon)/|S_1| $$

<footnote n="2">²the reformulation as a maximization problem is classical by setting $q_{\omega} = 1 - p_{\omega}$.</footnote>
Considering the question **Q2**, “What minimum perturbation level is required to achieve a FNR above $\gamma$?”, we consider the degradation criterion

$$ \kappa_{\text{FNR}}[h(f(\tilde{X}), Y)] = \mathbf{1}_{\{h(f(\tilde{X}), Y) \le 1 - \gamma\}}. \quad (17) $$

We can derive a threshold index $n_{\gamma} = \gamma \cdot |S_1|$ over the less robust pixels in $S_1$. We can use Eq. (14), and obtain:

$$ R_{\kappa}(X, Y) \ge \underline{R}_{\kappa}(X, Y, S_1, R^{\omega}, n_{\gamma}) \quad (18) $$

which is also an easily computable lower bound for the $R_{\kappa}$ answering **Q2** with a degradation criterion $\kappa$ that aims to drive the FNR above a certain threshold $\gamma$.

**Stability** Importantly, both PA and FNR require the ground-truth $Y$ values. At inference, we propose the stability measure $h_{\text{stab}}$ on subsets of pixels $S \subseteq \Omega$ to ensure their robustness independently from the ground truth.

$$ h_{\text{stab}}(f(X), \hat{Y}^*) = \frac{1}{|S|} \sum_{\omega \in S} \mathbf{1}_{\hat{Y}_{\omega} = \hat{Y}_{\omega}^*} \quad (19) $$

The only difference with the pixel accuracy defined in Eq. (7), is that the reference is the clean decision $\hat{Y}^*$ when output perturbation $\alpha = 0$ (in Eq. (6)). Similarly to Eq. (8), we denote the stability certificate for any particular pixel of coordinate $\omega \in \Omega$ (the factor $\mathbf{1}_{\hat{Y}_{\omega} = \hat{Y}_{\omega}^*}$ is omitted since it is ensured by $top_1 = \hat{Y}^*$).

$$ R_{\text{stab}}^{\omega}(X, Y) := 2^{\frac{1-p}{p}} \cdot \mathcal{M}_{X}^{\omega}(f)/L. \quad (20) $$

We can now provide answers to **Q1** and **Q2** regarding the stability performance measure. The Certified Robustness Stability is defined as $CRS_{\epsilon}(X) = 1 - N_{\text{stab}}(X, \epsilon)/|S|$ where

$$ N_{\text{stab}}(X, \epsilon) = N_{\text{SUP}}(X, \epsilon, S, R_{\text{stab}}^{\omega}). \quad (21) $$

We can also address **Q2**, which concerns the generalized stability radius for a given threshold $\gamma$. Setting $n_{\gamma} = [\gamma \cdot |S|]$, we obtain the following lower bound:

$$ R_{\kappa}(X, Y) \ge \underline{R}_{\kappa}(X, Y^*, S, R_{\text{stab}}^{\omega}, n_{\gamma}). \quad (22) $$

As an illustration, we provide a visualization of robust segmentations on the Cityscapes dataset in Fig. 1 where we ensure the stability of dense subsets of predictions up to a radius $\epsilon$ such that all but a fixed number of pixels (set by the user) of said objects could change class under attack. Additionally, we also provide robustness certificates for more complex performance measures such as the class IoU. We detail our computations in Appendix B.

# 5. Experimental Validation

In this section, we provide more context on Lipschitz network training and apply our methods to certify various objectives. We compare our methods certificates against the SEGCERTIFY method, and evaluate the tightness of Lipschitz bounds by using adversarial attacks. Finally, we demonstrate the flexibility of Lipschitz-based certification in a safety-critical scenario.

## 5.1. Lipschitz by design networks

The exact computation of a network’s Lipschitz constant (see Def. 2) is known to be NP-hard [40]. As a practical alternative, Anil et al. [1] introduced architectures in which every linear layer is constrained such that $\|\nabla_x f(x)\|_2 = 1$ almost everywhere. As a result, the multiplicative bound $L_f = \prod_{i=1}^L L_{f_i}$ of layer wise Lipschitz constants $L_{f_i}$ becomes a meaningful certificate on the network’s global Lipschitz constant.

Importantly, most of these orthogonality constraints are ensured by differentiable re-parametrization on the neural networks weights, which can be performed efficiently, resulting in networks with limited training overhead w.r.t their standard unconstrained counterparts (see Appendix E). Moreover, constraining the Lipschitz constant of a neural network exhibits several other benefits, such as explicit control of the network’s position on the accuracy-robustness tradeoff [4], or even ensuring training stability [3, 27] for state-of-the-art deep learning tasks.

We use DeepLabV3 [6] as our baseline architecture for semantic segmentation, since, to the best of our knowledge, it achieves state-of-the-art performance among convolutional neural network (CNN)-based methods. Additionally, this architecture is perfectly compatible with real time inference. Attention-based architectures were excluded since standard attention layers are not Lipschitz-continuous, and only very recent works have started to address this limitation [17]. DeepLabV3 employs dilated convolutions and pooling operations to capture multi-scale contextual information. To design a Lipschitz-constrained version of DeepLabV3, we leverage the ORTHOGONIUM and DEEL-LIP libraries introduced in Boissin et al. [5] and Serrurier et al. [37] respectively. More details on this network architecture are provided in Appendix D.

## 5.2. Comparing LipNet certificates to SegCertify

In order to compare Randomized Smoothing based approaches with our proposed Lipschitz approach, we must define a shared performance metric. In the setting of Lipschitz constrained networks, we are able to directly compute:

$$ \text{CRPA}_{\text{Lip}} = 1 - \frac{N(X, \epsilon)}{|\Omega|}, \quad (23) $$
<table><caption>Table 1. CRPA values across methods on the Cityscapes dataset [11] using 1024 × 1024 images. We choose α = 0.001 as the failure probability of SEGCERTIFY and tune σ ∈ {0.15, 0.2, 0.25, 0.3, 0.4, 0.5} for each run. Finally, given the very long computation time of smoothing based methods, evaluations are run on only 100 images of the dataset, as done in [12]. We report the mean and standard deviation of results across 5 runs that use the best performing σ value. We also report the mean runtime for each evaluation divided by the number of samples. The results using Lipschitz bounds are obtained on the whole test set.</caption><thead><tr><th>ε</th><th>Method</th><th>CRPA</th><th>Time (total / nb samples)</th><th># forward passes / sample</th></tr></thead><tbody><tr><td>0.1</td><td>Lipschitz bound (ours)</td><td>81.80%</td><td>≈ 0.1 s</td><td>1</td></tr><tr><td>0.1</td><td>SEGCERTIFY (σ = 0.3)</td><td>53.48 ± 0.59%</td><td>59.8 s <span style="color:red;">×594</span></td><td>60</td></tr><tr><td>0.1</td><td>SEGCERTIFY (σ = 0.2)</td><td>83.13 ± 0.33%</td><td>62.1 s <span style="color:red;">×624</span></td><td>80</td></tr><tr><td>0.17</td><td>Lipschitz bound (ours)</td><td>77.34%</td><td>≈ 0.1 s</td><td>1</td></tr><tr><td>0.17</td><td>SEGCERTIFY (σ = 0.4)</td><td>38.91 ± 0.53%</td><td>60.3 s <span style="color:red;">×594</span></td><td>60</td></tr><tr><td>0.17</td><td>SEGCERTIFY (σ = 0.2)</td><td>84.84 ± 0.73%</td><td>63.3 s <span style="color:red;">×683</span></td><td>120</td></tr></tbody></table>

<figure><img src="image_5.png" /><figcaption>Figure 2. We evaluate the certified pixel accuracy of SEGCERTIFY on the same L-Lipschitz neural network that performs Semantic Segmentation on the Oxford-IIIT Pet dataset [29]. For SEGCERTIFY we carefully select σ from {0.035, 0.05, 0.08, 0.1, 0.15, 0.2, 0.3} for each number of MC samples. Here, we certify the pixel accuracy against ε = 0.1 in ℓ₂ norm. We pick α = 0.01 as the failure probability for CRPARRS.</figcaption></figure>

In order to enable fair comparison between methods, we should penalize abstentions as they still impede the decision making process of downstream systems that might depend on the segmentation network. We adopt the following metric to compare Lipschitz and Randomized Smoothing based certificates:

$$CRPA_{RS} := \frac{1}{|\Omega|} \times \sum_{\omega \in \Omega} \mathbf{1}_{\hat{Y}_{\omega} \neq \emptyset \land \hat{Y}_{\omega} = Y_{\omega}} \quad (24)$$

which recovers the standard pixel accuracy formulation with abstentions considered as misclassifications.

### 5.2.1. Using Different Networks

Using the common comparison metric we defined in Section 5.2, we compare a Lipschitz constrained DeepLabV3 architecture to its unconstrained counterpart on which we run the randomized smoothing method of Fischer et al. [12]. We train our unconstrained model with a noise level that is similar to the σ value we will choose for the smoothing process according to Salman et al. [35]. The CRPA certificates given by both Lipschitz constraints and the SEGCERTIFY

method are presented in Table 1. We also report the time each evaluation took divided by the number of evaluated samples. It does not scale linearly in MC iterations since the computation time of SEGCERTIFY depends on both the MC estimation runtime (which can be partially batched, but not fully due to memory limits) and the p-value computation times which are dependent of the image size. More experimental details are given in Appendix F.

We observe that Lipschitz-constrained networks allow for blazingly fast inference and certification with performance that remains competitive with that of randomized smoothing methods. Crucially, the performance obtained by using a LipNet is only matched by randomized smoothing methods when they require approximately 600 times more time per inference.

### 5.2.2. Comparing CRPAs on the Same LipNet

We might wonder how tight our Lipschitz bounds are, and whether the better performance of Randomized Smoothing methods for higher computational budgets at inference (e.g. for 120 forward passes at ε = 0.17) stems from tighter approximations of the local Lipschitz constant or just better base model accuracy of the unconstrained model.

In order to answer this question, we devise the following experiment: on the same L-Lipschitz DeepLabV3 network, we compare the CRPA certificate of the SEGCERTIFY method with a varying number of MC samples with the CRPA certificate provided by our Lipschitz bound. Indeed, since increasing the number of MC samples improves the performance of randomized smoothing methods this will allow us to determine the minimum number of MC samples that is necessary for probabilistic methods to match our deterministic bound on the same base model. Our results are reported in Fig. 2. These results show that randomized smoothing methods need more that 1000 MC samples to become beneficial over using a Lipschitz certificate. On the IIIT Pets dataset with 128 × 128 images, equates to an ≈ 2000 times slower runtime per image. Thus the
<figure><img src="image_6.png" /><figcaption>Figure 3. Here, we attack 500 images from the Oxford-IIIT Pet dataset, for each different adversarial budget, we plot the CRPA and the actual empirical pixel accuracy under attack.</figcaption></figure>

CRPA<sub>Lip</sub> method evaluated on the same neural network is more than 2000 times faster at equal robustness levels.

## 5.3. About the Empirical Robustness of LipNets

In order to obtain an upper-bound for the worst-case performance of Semantic Segmentation networks under $\epsilon$ bounded adversarial attacks, we apply segmentation specific adversarial attacks from various different works on the Oxford-IIIT Pet dataset. Here, we use the ALMA, ASMA and PDPGD attacks from [25, 32, 41] respectively, as implemented in [31]. For every image, we choose the best-performing attack from the previously mentioned subset of methods and compile the overall worse pixel accuracy we could get from attacking the test images. As shown in Fig. 3, our networks are very robust to adversarial perturbations. Moreover, the gap between certificates and empirical instantiations seems to grow larger when $\epsilon$ gets bigger. The reason behind this is threefold: Firstly, our Lipschitz bounds are tight in low $\epsilon$ settings, and ensuring robustness in higher $\epsilon$ regimes requires more robust but less accurate networks. Secondly, as $\epsilon$ grows, output perturbations described in Eq. 6 become less and less feasible. Finally, empirical adversarial attacks only provide an upper-bound for the worst-case performance under attack which is be overly optimistic regarding the worst-case adversarial robustness.

## 5.4. A Safety Critical Use-Case

In this section, we will further demonstrate how Lipschitz-constrained networks allow for fast and practical worst-case bound in Safety-Critical scenarios. In this setting, we will be interested in a binary segmentation task that handles the detection of polyps from endoscopically capture images. To this end, we use the Kvasir-SEG dataset introduced in Jha et al. [14]. Typically, this is a safety-critical scenario as misdetections might lead to harmful consequences on the patient. Importantly, the deployment of such a detection model must satisfy some real-time constraints given the time-sensitive nature of the assisted surgeon's task.

<table><caption>Table 2. Here, we present the lower-bounds obtained as answers to Q1 and Q2 type certification processes.</caption><thead><tr><th colspan="2">Q1</th><th colspan="2">Q2</th></tr><tr><th>&epsilon;</th><th>Certified FNR</th><th>&gamma;</th><th>Required &epsilon;</th></tr></thead><tbody><tr><td>0.1</td><td>0.612</td><td>0.7</td><td>0.423</td></tr><tr><td>0.2</td><td>0.768</td><td>0.85</td><td>0.563</td></tr><tr><td>0.3</td><td>0.871</td><td>0.95</td><td>0.675</td></tr></tbody></table>

**Defining meaningful robustness certificates** Here, we want to certify the worst-case False Negative Rate of our segmentation network under adversarial noise bounded by $\epsilon$. In the following, we use $h$ and $\kappa$ defined as in Equation 15 and 17 respectively. We expose our robustness certificates in the setting of both Q1 and Q2 in Table 2. Our Q1 certificates can be read as “given budget $\epsilon$, I cannot attack images so that FNR $\ge \gamma$”. For Q2, we can understand “To ensure FNR $\ge \gamma$ on the test set, I need a mean $\epsilon$ budget across test images”. Most importantly, the forward pass of our Lipschitz segmentation network only requires $\approx 0.05$ s which ensures compatibility with real-time applications.

## 6. Perspectives and Conclusion

In this paper, we propose Lipschitz neural networks for semantic segmentation tasks, which enables real-time compatible certifiably robust segmentation for the first time. Also, we show how to train and use Lipschitz neural networks to obtain general robustness certificates efficiently in a variety of different scenarios.

**Limitations and Future Research Directions** While Lipschitz networks allow for an efficient certification process for robustness certificates on semantic segmentation predictions. They struggle to match the performance of smoothed state-of-the-art semantic segmentation networks that leverage a high number of MC iterations or even diffusion models [18]. Indeed, if we consider the performance to inference time compute Pareto frontier, we have that Lipschitz constrained neural networks are at one end of the spectrum, whereas randomized smoothing based methods are on the other end, offering impressive performance in high compute scenarios. Future work could focus on developing hybrid alternatives that leverage model architecture and input dependencies (such as receptive fields [23, 36]), in order to make the bound of Equation 6 tighter by incorporating feasibility constraints into Eq. (6), while keeping real-time compatibility. Also, adding considerations on the distributions of inputs could be useful to allow fast and meaningful certificates [13, 45].
# 7. Acknowledgements

This work was carried out within the DEEL project,³ which is part of IRT Saint Exupéry and the ANITI AI cluster. The authors acknowledge the financial support from DEEL's Industrial and Academic Members and the France 2030 program – Grant agreements n°ANR-10-AIRT-01 and n°ANR-23-IACL-0002. This work was granted access to the HPC resources of IDRIS under the allocation 2025-AD011016850 made by GENCI.

Additionally, the authors thank Thibaut Boissin for his valuable input regarding figures and phrasing, as well as Tom Rousseau and Laurent Gardès for their guidance and continued support of the project.

# References

[1] Cem Anil, James Lucas, and Roger Grosse. Sorting out lipschitz function approximation. In *International conference on machine learning*, pages 291–301. PMLR, 2019. 2, 6

[2] Anurag Arnab, Ondrej Miksik, and Philip H.S. Torr. On the robustness of semantic segmentation models to adversarial attacks. In *Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)*, 2018. 2

[3] Nitin Bansal, Xiaohan Chen, and Zhangyang Wang. Can we gain more from orthogonality regularizations in training deep networks? In *Advances in Neural Information Processing Systems*. Curran Associates, Inc., 2018. 6

[4] Louis Béthune, Thibaut Boissin, Mathieu Serrurier, Franck Mamalet, Corentin Friedrich, and Alberto Gonzalez Sanz. Pay attention to your loss: understanding misconceptions about lipschitz neural networks. *Advances in Neural Information Processing Systems*, 35:20077–20091, 2022. 6, 13, 14

[5] Thibaut Boissin, Franck Mamalet, Thomas Fel, Agustin Martin Picard, Thomas Massena, and Mathieu Serrurier. An adaptive orthogonal convolution scheme for efficient and flexible cnn architectures. In *Forty-second International Conference on Machine Learning*, 2025. 6, 15

[6] Liang-Chieh Chen, George Papandreou, Iasonas Kokkinos, Kevin Murphy, and Alan L Yuille. Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs. *IEEE transactions on pattern analysis and machine intelligence*, 40(4):834–848, 2017. 6, 14

[7] Ping-yeh Chiang, Michael Curry, Ahmed Abdelkader, Aounon Kumar, John Dickerson, and Tom Goldstein. Detection as regression: Certified object detection with median smoothing. *Advances in Neural Information Processing Systems*, 33:1275–1286, 2020. 1

[8] Szegedy Christian, Zaremba Wojciech, Bruna Joan, Erhan Dumitru, Goodfellow Ian, Fergus Rob, et al. Intriguing properties of neural networks. In *ICLR*, 2014. 1, 2

[9] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In

*International Conference on Machine Learning*, pages 1310–1320. PMLR, 2019. 2

[10] Noémie Cohen, Mélanie Ducoffe, Ryma Boumazouza, Christophe Gabreau, Claire Pagetti, Xavier Pucel, and Audrey Galametz. Verification for object detection–ibp iou. *arXiv preprint arXiv:2403.08788*, 2024. 1

[11] 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 IEEE conference on computer vision and pattern recognition*, pages 3213–3223, 2016. 7

[12] Marc Fischer, Maximilian Baader, and Martin Vechev. Scalable certified segmentation via randomized smoothing. In *International Conference on Machine Learning*, pages 3340–3351. PMLR, 2021. 1, 3, 7

[13] Navid Hashemi, Samuel Sasaki, Diego Manzanas Lopez, Ipek Oguz, Meiyi Ma, and Taylor T Johnson. Probabilistic robustness analysis in high dimensional space: Application to semantic segmentation network. *arXiv preprint arXiv:2509.11838*, 2025. 8

[14] Debesh Jha, Pia H Smedsrud, Michael A Riegler, Pål Halvorsen, Thomas de Lange, Dag Johansen, and Håvard D Johansen. Kvasir-seg: A segmented polyp dataset. In *MultiMedia Modeling: 26th International Conference, MMM 2020, Daejeon, South Korea, January 5–8, 2020, Proceedings, Part II*, pages 26, 451–462, 2020. 8

[15] Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In *International conference on computer aided verification*, pages 97–117. Springer, 2017. 3

[16] Hans Kellerer, Ulrich Pferschy, and David Pisinger. Knapsack problems. In *Knapsack problems*, pages 235–283. Springer, 2004. 11

[17] Hyunjik Kim, George Papamakarios, and Andriy Mnih. The lipschitz constant of self-attention. In *International Conference on Machine Learning*, pages 5562–5571. PMLR, 2021. 6

[18] Othmane Laovy, Alexandre Araujo, Guillaume Chassagnon, Nikos Paragios, Marie-Pierre Revel, and Maria Vakalopoulou. Certification of deep learning models for medical image segmentation. In *International Conference on Medical Image Computing and Computer-Assisted Intervention*, pages 611–621. Springer, 2023. 8

[19] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In *2019 IEEE symposium on security and privacy (SP)*, pages 656–672. IEEE, 2019. 2

[20] Qiyang Li, Saminul Haque, Cem Anil, James Lucas, Roger B Grosse, and Joern-Henrik Jacobsen. Preventing gradient attenuation in lipschitz constrained convolutional networks. In *Advances in Neural Information Processing Systems*, 2019. 2

[21] Jonathan Long, Evan Shelhamer, and Trevor Darrell. Fully convolutional networks for semantic segmentation. In

³https://www.deel.ai/
Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3431–3440, 2015. 14

[22] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019. 15

[23] Wenjie Luo, Yujia Li, Raquel Urtasun, and Richard Zemel. Understanding the effective receptive field in deep convolutional neural networks. Advances in neural information processing systems, 29, 2016. 8

[24] Yonggang Luo, Jinyan Ma, Sanchu Han, and Lecheng Xie. Benchmarks: Semantic segmentation neural network verification and objection detection neural network verification in perceptions tasks of autonomous driving. In Bridging the Gap Between AI and Reality: First International Conference, AISoLA 2023, Crete, Greece, October 23–28, 2023, Proceedings, page 279–290, Berlin, Heidelberg, 2023. Springer-Verlag. 3

[25] Alexander Matyasko and Lap-Pui Chau. Pdpgd: Primal-dual proximal gradient descent adversarial attack. arXiv preprint arXiv:2106.01538, 2021. 8

[26] Mark Niklas Müller, Christopher Brix, Stanley Bak, Changliu Liu, and Taylor T Johnson. The third international verification of neural networks competition (vnn-comp 2022): Summary and results. arXiv preprint arXiv:2212.10376, 2022. 3

[27] Laker Newhouse, R Preston Hess, Franz Cesista, Andrii Zaporodnii, Jeremy Bernstein, and Phillip Isola. Training transformers with enforced lipschitz constants. arXiv preprint arXiv:2507.13338, 2025. 6

[28] Neelanjana Pal, Seojin Lee, and Taylor T. Johnson. Benchmark: Formal verification of semantic segmentation neural networks. In Bridging the Gap Between AI and Reality: First International Conference, AISoLA 2023, Crete, Greece, October 23–28, 2023, Proceedings, page 311–330, Berlin, Heidelberg, 2023. Springer-Verlag. 3

[29] Omkar M Parkhi, Andrea Vedaldi, Andrew Zisserman, and CV Jawahar. Cats and dogs. In 2012 IEEE conference on computer vision and pattern recognition, pages 3498–3505. IEEE, 2012. 7

[30] Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In International Conference on Medical image computing and computer-assisted intervention, pages 234–241. Springer, 2015. 14

[31] Jérôme Rony and Ismail Ben Ayed. Adversarial Library, 2023. 8

[32] Jérôme Rony, Eric Granger, Marco Pedersoli, and Ismail Ben Ayed. Augmented lagrangian adversarial attacks. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 7738–7747, 2021. 8

[33] Jérôme Rony, Jean-Christophe Pesquet, and Ismail Ben Ayed. Proximal splitting adversarial attack for semantic segmentation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 20524–20533, 2023. 2, 3

[34] Harvey M Salkin and Cornelis A De Kluyver. The knapsack problem: a survey. Naval Research Logistics Quarterly, 22 (1):127–144, 1975. 4, 5

[35] Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2019. 7

[36] Jan Schuchardt, Tom Wollschläger, Aleksandar Bojchevski, and Stephan Günnemann. Localized randomized smoothing for collective robustness certification. In The Eleventh International Conference on Learning Representations, 2022. 3, 4, 8

[37] Mathieu Serrurier, Franck Mamalet, Alberto González-Sanz, Thibaut Boissin, Jean-Michel Loubes, and Eustasio Del Barrio. Achieving robustness in classification using optimal transport with hinge regularization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 505–514, 2021. 6, 14

[38] Hoang-Dung Tran, Neelanjana Pal, Patrick Musau, Diego Manzanas Lopez, Nathaniel Hamilton, Xiaodong Yang, Stanley Bak, and Taylor T Johnson. Robustness verification of semantic segmentation neural networks using relaxed reachability. In International conference on computer aided verification, pages 263–286. Springer, 2021. 2, 3

[39] Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-margin training: Scalable certification of perturbation invariance for deep neural networks. Advances in neural information processing systems, 31, 2018. 1

[40] Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. Advances in Neural Information Processing Systems, 31, 2018. 6

[41] Cihang Xie, Jianyu Wang, Zhishuai Zhang, Yuyin Zhou, Lingxi Xie, and Alan Yuille. Adversarial examples for semantic segmentation and object detection. In Proceedings of the IEEE international conference on computer vision, pages 1369–1378, 2017. 8

[42] Greg Yang, Tony Duan, J. Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In Proceedings of the 37th International Conference on Machine Learning, pages 10693–10705. PMLR, 2020. 2

[43] Greg Yang, James B Simon, and Jeremy Bernstein. A spectral condition for feature learning. arXiv preprint arXiv:2310.17813, 2023. 13

[44] Huilin Yin, Ziming Zhao, Jun Yan, and Daniel Watzenig. Certified robustness in automated driving perception: A review. Automotive Innovation, 8:817–837, 2025. 1, 3

[45] Soroush H Zargarbashi, Mohammad Sadegh Akhondzadeh, and Aleksandar Bojchevski. One sample is enough to make conformal prediction robust. arXiv preprint arXiv:2506.16553, 2025. 8
## A. Proof

In this section, we provide some theoretical context on the certification processes described in Section 4.2 of the paper.

### A.1. Proof of Equation 6

For sake of readibility, we copy here the equation, given $f$ an $L$-Lipschitz function with respect to the $\ell_p$ norm, we have:

$$ 
\begin{aligned}
h_{\epsilon}(X) &= \min_{\tilde{X} \in \mathcal{B}_{p}^{\epsilon}(X)} h(f(\tilde{X}), Y) \\
&\geq \min_{\alpha \in \mathcal{B}_{p}^{L^{\epsilon}}(0)} h(f(X) + \alpha, Y).
\end{aligned} 
\quad (25) $$

*Proof.* By definition,

$$ h_{\epsilon}(X) = \min_{\tilde{X} \in \mathcal{B}_{p}^{\epsilon}(X)} h(f(\tilde{X}), Y), $$

where $\mathcal{B}_{p}^{\epsilon}(X) = \{\tilde{X} \in \mathcal{X} : \|\tilde{X} - X\|_{p} \leq \epsilon\}$.

For any $\tilde{X} \in \mathcal{B}_{p}^{\epsilon}(X)$, the Lipschitz condition on $f$ implies

$$ \|f(\tilde{X}) - f(X)\|_{p} \leq L \|\tilde{X} - X\|_{p} \leq L\epsilon. $$

Thus, for each such $\tilde{X}$, $\alpha = f(\tilde{X}) - f(X)$ satisfies $\|\alpha\|_{p} \leq L\epsilon$. In other words, $f(\tilde{X}) \in f(X) + \mathcal{B}_{p}^{L^{\epsilon}}(0)$.

Therefore, we can write

$$ \{f(\tilde{X}) : \tilde{X} \in \mathcal{B}_{p}^{\epsilon}(X)\} \subseteq f(X) + \mathcal{B}_{p}^{L^{\epsilon}}(0). $$

Applying the monotonicity of the minimum over subsets, we get

$$ \min_{\tilde{X} \in \mathcal{B}_{p}^{\epsilon}(X)} h(f(\tilde{X}), Y) \geq \min_{\alpha \in \mathcal{B}_{p}^{L^{\epsilon}}(0)} h(f(X) + \alpha, Y). $$

Hence,

$$ h_{\epsilon}(X) \geq \min_{\alpha \in \mathcal{B}_{p}^{L^{\epsilon}}(0)} h(f(X) + \alpha, Y), $$

which completes the proof. □

### A.2. About Equation 11

Formally, the knapsack problem can be defined as follows: We are given an instance of the knapsack problem with item set $\Omega$, consisting of $n$ items $\omega$ with profit $p_{\omega}$ and weight $c_{\omega}$, and the capacity value $C$. Then, the objective is to select a subset of $\Omega$ such that the total profit of the selected items is maximized and the total weight does not exceed $C$, as per Kellerer et al. [16].

In our case, Eq. (11) is obtained via the simplest case of knapsack instances, where for each pixel coordinate $\omega \in \Omega$, we have $p_{\omega} = 1$ if we attack the correctly classified pixel $\omega$ by using budget $c_{\omega} = R^{\omega}(X, Y)^{p}$, we aim to keep the total minimum required adversarial budget under $C = \epsilon^{p}$. We denote $x_{\omega}$ the binary variable that represents the selection or not of the object in the knapsack (i.e. if the pixel $\omega$ is attacked or not). Our knapsack formulation is to find the optimal $\{x_{\omega}\}_{\omega \in \Omega}$ as:

$$ 
\begin{aligned}
\text{maximize} \quad & \sum_{\omega \in \Omega} p_{\omega} x_{\omega}, \\
\text{subject to} \quad & \sum_{\omega \in \Omega} c_{\omega} x_{\omega} \leq C, \\
& x_{\omega} \in \{0, 1\}, \quad \omega \in [1, |\Omega|].
\end{aligned} 
\quad (26) $$

Consequently, we have that our formulation recovers that of a classical knapsack problem. In the case of the pixel accuracy, $p_{\omega} = 1$ everywhere and $c_{\omega} = R^{\omega}(X, Y)^{p}$, which can be solved efficiently by sorting the items of the set $\Omega$ by ascending cost of $c_{\omega}$ and obtaining the index such that the cumulative sum of the sorted $c_{\pi(\omega)}$ is inferior to $C = \epsilon^{p}$. This corresponds to finding the optimal vector $x^{*} = (x_{1}^{*}, \dots, x_{|\Omega|}^{*})$ where the attack that perturbs the most correctly classified pixels misclassifies all $i$ such that $x_{i} = 1$.
## B. Worst-case Class IoU Computation

In this section, we provide an explicit description of the more complex computation of robustness certificates for the class IoU computation. Indeed, we have that computing the worst-case class IoU value under $\epsilon$-bounded adversarial attacks is equivalent to a fractional knapsack problem, which requires a greedy but yet still efficient certification process. We recall the class IoU performance measure as:

$$h_{\text{IoU}_k}(X, Y) := \frac{\sum_{\omega \in \Omega} \mathbf{1}_{(\hat{Y}_\omega = Y_\omega) \land (Y_\omega = k)}}{\sum_{\omega \in \Omega} \mathbf{1}_{(\hat{Y}_\omega = k) \lor (Y_\omega = k)}}. \qquad (27)$$

Importantly, the class IoU can be degraded in two (non-exclusive) ways:

* changing the prediction of true positive (TP) pixels to any class other than $k$, i.e. a smaller numerator in Eq. (27). The certificate to perturb a TP pixel is $R_{TP}^{\omega} = f_{\omega}^{k} - f_{\omega}^{\text{top2}}$.

* changing the prediction of true negative (TN) pixels to class $k$, i.e. a higher denominator in Eq. (27). The certificate to perturb a TN pixel is $R_{TN}^{\omega} = f_{\omega}^{\text{top1}} - f_{\omega}^{k}$.

We introduce $S_k = \{\omega \in \Omega : Y_\omega = k\}$, and the binary variable $p_\omega = 1$ for the set of pixels in $S_k$ misclassified under attack, i.e. $p_\omega = (\hat{Y}_\omega \neq c) \land (Y_\omega = c)$. We also denote $q_\omega$, the set of pixels in $\Omega \setminus S_k$ that are classified as $k$ under attack: $q_\omega = (\hat{Y}_\omega = k) \land (Y_\omega \neq k)$. We can derive a formulation of $h_{\text{IoU}_k}$ with $p_\omega$ and $q_\omega$:

$$h_{\text{IoU}_k}(X, Y) := \frac{|S_k| - \sum_{\omega \in S_k} p_\omega}{|S_k| + \sum_{\omega \in \Omega \setminus S_k} q_\omega}. \qquad (28)$$

We denote $c_\omega = (R_{TP}^\omega)^p$ for any $\omega \in S_k$, and $c_\omega = (R_{TN}^\omega)^p$ for any $\omega \in \Omega \setminus S_k$. We can reformulate the lower bound of $h_{\text{IoU}_k}$ as a Linear Fractional Programming problem:

$$\begin{align} \min \quad & \frac{|S_k| - \sum_{\omega \in S_k} p_\omega}{|S_k| + \sum_{\omega \in \Omega \setminus S_k} q_\omega} \tag{29} \\ \text{s.t.} \quad & \sum_{\omega \in S_k} L^p c_\omega p_\omega + \sum_{\omega \in \Omega \setminus S_k} L^p c_\omega q_\omega \le (L\epsilon)^p \nonumber \end{align}$$

Crucially, we solve this problem with a two-stage greedy strategy. For each possible amount of budget allocated to increasing the numerator (by misclassifying TP pixels in order of increasing $c_\omega$), we then greedily use the remaining budget to decrease the denominator (by misclassifying TN pixels as class $k$, again in increasing $c_\omega$). Among all such budget splits, we retain the configuration that yields the smallest IoU. The code for this process is provided in our codebase. Importantly, this method allows the certification of the worst-case IoU of the “pedestrian” class on the whole test set of the Cityscapes dataset in only 38 seconds (on 1024 × 1024 images), i.e 8 milliseconds per image on average. Our results our presented in Tab. 3.

<table><caption>Table 3. Here, we compute a certificate for the worst case class IoU of the “person” class on the Cityscapes dataset under $\epsilon$-bounded attacks using our algorithm. This is particularly difficult to certify given the small proportion of pixels that this class represents.</caption><thead><tr><th>ε</th><th>Worst Reachable Class IoU</th></tr></thead><tbody><tr><td>0.0</td><td>47.37</td></tr><tr><td>1.0 × 10<sup>-2</sup></td><td>31.76</td></tr><tr><td>2.5 × 10<sup>-2</sup></td><td>21.15</td></tr><tr><td>5.0 × 10<sup>-2</sup></td><td>11.43</td></tr><tr><td>7.5 × 10<sup>-2</sup></td><td>06.49</td></tr><tr><td>1.0 × 10<sup>-1</sup></td><td>03.83</td></tr></tbody></table>

## C. Segmentation Specific Adaptations

In this section, we provide more detail regarding our implementation of Lipschitz networks for segmentation tasks.
<figure><img src="image_7.png" /><figcaption>Figure 4. Visualization of test set segmentation results using our Lipschitz constrained neural networks trained using the cosine similarity.</figcaption></figure>

First, we scale the outputs of residual connections that add or concatenate the residual outputs accordingly to the Lipschitz constant of the operation being realized. We ensure the Lipschitz constant of the network remains unchanged by scaling the outputs of concatenations by $1/\sqrt{N}$ with N the number of different outputs that get concatenated (and $1/N$ when the outputs are added).

Also, to ensure that our Lipschitz network does not suffer from stability issues due to small activation values, we use the scaling method of Yang et al. [43]. This scaling factor ensures that the RMS norm of feature maps stays stable and therefore allows us to replace BatchNormalization layers by BatchCentering layers which exhibit 1-Lipschitz behavior.

To fairly characterize how expressive our DNNs architectures are we train the same DeepLabV3 architecture with both unconstrained and Lipschitz building blocks, we will refer to these models as AllNet and LipNet respectively. We train our Lipschitz network to maximize accuracy (i.e with a high temperature). We obtain the following results:

<table><caption>Table 4. Comparing the expressivity of Lipschitz-constrained blocks to standard unconstrained blocks on the Cityscapes dataset.</caption><thead><tr><td>Model</td><td>Pixel Acc.</td><td>mIoU</td></tr></thead><tbody><tr><td>LipNet</td><td>92.07%</td><td>51.80</td></tr><tr><td>AllNet</td><td>94.41%</td><td>64.55</td></tr></tbody></table>

In practice however, the decisions of this accurate LipNet model are too brittle to certify meaningful CRPA for non trivial $\epsilon$ values. In the rest of the paper, we use scaled temperature cross-entropy training to train networks that provide non vacuous robustness certificates while maintaining informative enough pixel accuracy values in a clean setting. As per Béthune et al. [4], we train Lipschitz neural networks with a temperature-scaled cross-entropy objective. This allows us to explicitly control the position of our trained neural networks on the accuracy-robustness tradeoff, as depicted in Fig. 5.

**Characterizing a LipNet's robustness** In order to characterize the robustness of a Lipschitz neural network independently from its accuracy, we denote the “stability” measure as a direct measure of a neural network prediction’s invariance. Its formulation is equivalent to that of Equation 8, except the correctness of the prediction is not accounted for. We use this metric along with the mIoU metric to demonstrate how training Lipschitz neural networks on segmentation tasks also allows us to control the placement of our trained model on the robustness-accuracy Pareto frontier (see Fig. 5). Here, we denote the stability@50 measure as a lower-bound on the minimum required adversarial budget $\epsilon$ to change at least 50% of the networks pixel-wise predictions.
<figure><img src="image_8.png" /><figcaption>Figure 5. Lipschitz neural networks allow for explicit control of their position on the robustness-accuracy tradeoff [4], as seen on this small network trained on the Cats & Dogs dataset. This property remains valid in the context of semantic segmentation.</figcaption></figure>

## D. About the DeepLabV3 architecture

In our paper, we use a DeepLabV3-like architecture across experiments. It is described in Figure 6.

<figure><img src="image_9.png" /><figcaption>Figure 6. The DeepLabV3 architecture relies on an extraction of fine and coarser features by leveraging the atrous convolutions in the ASPP modules, which each use a different dilation to capture finer or larger features.</figcaption></figure>

We provide different configurations for this architecture by changing $N_{re}$, $N_{rd}$, $d$ for each stages along with the number of stages $N_{se}$ ($N_{sd}$ is chosen to recover the original image's size).

**Why choose a DeepLabV3 architecture?** In order to choose a good architecture for our segmentation networks, we run an experiment on the Oxford-IIIT Pet dataset where we train a variety of different networks by varying: the parametrization (Lipschitz-constrained, orthogonally constrained or unconstrained), the loss function (Hinge Kantorovich-Rubinstein [37], cosine similarity or scaled cross-entropy [4]), and finally the neural network architecture: varying between FCN [21], UNet [30] and DeepLab [6]. We obtain a mean mIoU improvement of 3.3 and 1.9 points, respectively, in favor of the DeepLabV3 architecture w.r.t. the FCN and UNet architectures.

## E. Training Overhead of Lipschitz Neural Networks

Training Lipschitz neural networks introduces a computational overhead that is twofold: First, the Lipschitz layers must be parametrized with an efficient differentiable parametrization method, this ensures that the Lipschitz constant of the layer is at most 1. Secondly, the weight updates must be backpropagated through this parametrization in order to train the neural
network using the chain rule. While this extra overhead might seem costly, efficient parametrizations exist in order to parametrize Lipschitz convolutive layers that allow for tight certificates [5].

Also, the parametrization methods Lipschitz neural networks leverage only necessitate to be recomputed after every weight update, and their cost is not input dependant. Therefore, their cost is rather limited when using larger batch sizes, making Lipschitz neural networks more efficient at scale when batch sizes are increased. To demonstrate this phenomenon, we train the same DeepLab architecture with unconstrained and Lipschitz parametrized blocks for different batch sizes on the IIIT Pets dataset. We obtain the following results:

<table><caption>Table 5. Number of gradient steps per second for different batch sizes. We use the M1 config of our DeepLabV3 architecture on the Oxford-IIIT Pet dataset with 128 × 128 images and the parametrization from [5]. The last column reports the relative training speed of the Lipschitz-constrained LipNet compared to the unconstrained AllNet (higher is slower, AllNet = 1.00×).</caption><thead><tr><th>Network</th><th>Batch size</th><th>Training speed (batches/s)</th><th>Runtime overhead (vs AllNet)</th></tr></thead><tbody><tr><td>AllNet</td><td>30</td><td>12.58</td><td>1.00×</td></tr><tr><td>LipNet</td><td>30</td><td>5.33</td><td>2.36×</td></tr><tr><td>AllNet</td><td>100</td><td>3.94</td><td>1.00×</td></tr><tr><td>LipNet</td><td>100</td><td>3.62</td><td>1.09×</td></tr></tbody></table>

Therefore, while Lipschitz neural networks introduce a computational overhead at train time. That overhead becomes rather negligible in large batch size regimes. Moreover, offloading the parametrization cost to a single GPU can be beneficial in multi-GPU settings, further reducing the overhead of Lipschitz parametrizations.

## F. Experimental Settings

During our training runs, we use the following settings:

**Input sizes** We use the following image sizes on these datasets:

* Oxford-IIIT Pet: 128 × 128.

* Cityscapes: 1024 × 1024.

* Kvasir-SEG: 256 × 256.

**Model configuration** In our configuration, we propose the following configuration for our DeepLabV3 configurations:

* **S**: which uses $N_{re} = 3$ with three stages of dimensions 32, 64 and 128.

* **M1**: which uses $N_{re} = 5$ with three stages of dimensions 64, 128 and 256.

* **M2**: which uses $N_{re} = 5$ with four stages of dimensions 64, 128, 256 and 512.

* **L**: which uses $N_{re} = 7$ with four stages of dimensions 64, 128, 256 and 512.

We use the M1 config on the Oxford-IIIT Pet dataset and the M2 configuration on the Kvasir-SEG and Cityscapes datasets. We optimize the neural networks with AdamW [22] with a learning rate of $\eta = 10^{-3}$, a batch size of 8, and a weight decay of $10^{-4}$, we use a cosine annealing learning rate scheduler with $\eta_{min} = 10^{-6}$, our networks are trained for 100 epochs on the Oxford-IIIT Pet dataset and for 200 epochs on the Kvasir-SEG and Cityscapes dataset. We use data augmentations to crop, flip and rotate images during training. For the temperature parameter $\tau$ of the scaled cross-entropy during training, we use $\tau = 20.0$ on the Cityscapes dataset, on the Kvasir-SEG and Oxford-IIIT Pet dataset we use $\tau = 5.0$.

## G. Additional Experiments on the Kvasir-SEG Dataset

To further illustrate the different guarantees our framework allows on safety critical datasets, we provide segmentation results on the Kvasir-SEG dataset. Here, we use the S config of our DeepLabV3 architecture on the Kvasir-SEG dataset. For every image/label pair X/Y in the dataset, we answer **Q1** by first computing the predictions via a simple forward pass of the network. Then, we compute the worst-case segmentation that would maximize the FNR measure under budget $\epsilon$. Results are presented in Fig. 7.
<figure><img src="image_10.png" /><figcaption>Figure 7. (left) The segmented output using our Lipschitz network, the “polyp” class is depicted in bright overlay. (middle) The predicted “polyp” pixels are shown as either True Positives (TP) in green, False Positives (FP) in blue, or False Negatives (FN) in red. True Negatives (TN) are left in white. With very few FN, the FNR is very low (here, FNR = 0.01). (right) We depict the optimal output attack that maximizes the FNR for budget $\epsilon = 0.25$, which corresponds to the maximum number of attacked TP pixels. Therefore, we attack the less robust TP pixels in priority. We certify that we could not degrade the FNR more than 0.14. Note that this worst-case scenario is not necessarily feasible via an adversarial attack, however, it provides a useful tool for certification purposes.</figcaption></figure>

## H. Guarantees in the Absence of Ground Truth Labels

Previously, we showed how LipNets allowed for quick estimations of worst-case performance on semantic segmentation tasks. However, most of the guarantees provided by certifiable methods estimate the worst-case accuracy under attack. This requires access to ground-truth labels $Y$. We have to propose a way to convey a neural network’s robustness at inference time in real-world deployment scenarios. In the main paper, we propose a stability performance measure that allows for the computation of robust pixel subsets, where more than $\alpha\%$ (or $N_{max}$) predictions would not change under attacks with a budget inferior to a user-chosen $\epsilon$ in $l_2$ norm (see Sec. 4.2).

<figure><img src="image_11.png" /><figcaption>Figure 8. (left) We depict the subsets of adjacent pixel predictions of the class *polyp* (one subset here). We also compute the necessary adversarial budget $\epsilon$ to perturb at least 90% of pixel predictions from that subset of coordinates. (right) We display the worst-case vanishing attack under budget $\epsilon$, i.e, the perturbation that changes the maximum number of polyp predictions to benign predictions on the initial subset of identical predictions.</figcaption></figure>

Additionally, in terms of inference-time guarantees, we also provide a visual example of the stability of Lipschitz neural network predictions. In the same setting as Appendix G, we provide some guarantees on the robustness of dense subsets of
adjacent pixels that share the same classification (denoted $S_\omega$). We will measure their robustness to degradations with the following objective:

$$ \begin{gathered} \kappa(\tilde{Y}, \hat{Y}) = \mathbf{1}_{h(\tilde{Y}, \hat{Y}) \le \gamma_{\text{stab}}} \\ \text{with } h(\tilde{Y}, \hat{Y}) = \sum_{\omega \in S_\omega} \frac{\mathbf{1}_{\tilde{Y}_\omega = \hat{Y}_\omega}}{|S_\omega|} \end{gathered} \tag{30} $$

In Fig. 8, we provide a visualization of inference results without assuming ground truth access. In this context, we provide a visualization of the network’s predictions along with the worst-case outputs of the network under an attack of budget $\epsilon = 0.25$ that aims to eliminate pixels of the class *polyp*. We called it ”vanishing attack” with $S_\omega = \{\omega \in \Omega, \tilde{Y}_\omega = 1\}$.