Lipschitz-aware Linearity Grafting for Certified Robustness

## Abstract

Abstract Lipschitz constant is a fundamental property in certified robustness, as smaller values imply robustness to adversarial examples when a model is confident in its prediction. However, identifying the worst-case adversarial examples is known to be an NP-complete problem. Although over-approximation methods have shown success in neural network verification to address this challenge, reducing approximation errors remains a significant obstacle. Furthermore, these approximation errors hinder the ability to obtain tight local Lipschitz constants, which are crucial for certified robustness.
Originally, grafting linearity into non-linear activation functions was proposed to reduce the number of unstable neurons, enabling scalable and complete verification.
However, no prior theoretical analysis has explained how linearity grafting improves certified robustness.
We instead consider linearity grafting primarily as a means of eliminating approximation errors rather than reducing the number of unstable neurons, since linear functions do not require relaxation. In this paper, we provide two theoretical contributions: 1) why linearity grafting improves certified robustness through the lens of the l ∞ l_{\infty} local Lipschitz constant, and 2) grafting linearity into non-linear activation functions, the dominant source of approximation errors, yields a tighter local Lipschitz constant.
Based on these theoretical contributions, we propose a Lipschitz-aware linearity grafting method that removes dominant approximation errors, which are crucial for tightening the local Lipschitz constant, thereby improving certified robustness, even without certified training. Our extensive experiments demonstrate that grafting linearity into these influential activations tightens the l ∞ l_{\infty} local Lipschitz constant and enhances certified robustness.

## 1 Introduction

The local Lipschitz constant is a fundamental property in neural network verification, as smaller values imply greater robustness to adversarial examples. It characterizes the network’s sensitivity to input perturbations within a small region. The local Lipschitz constant has been widely used for certified robustness Weng et al. (2018a); Jordan & Dimakis (2020); Zhang et al. (2019b); Shi et al. (2022); Zhang et al. (2022); Huang et al. (2021). However, computing the exact Lipschitz constant is too costly, and even approximate estimates are often loose Jordan & Dimakis (2020). Moreover, identifying the worst-case adversarial examples Szegedy et al. (2014) is also known to be NP-complete Katz et al. (2017). Consequently, despite its theoretical importance, effectively leveraging the local Lipschitz constant for improving certified robustness remains challenging.

On the one hand, relaxation-based verification approaches Wong & Kolter (2018); Raghunathan et al. (2018); Mirman et al. (2018); Zhang et al. (2019a; 2018); Weng et al. (2018a); Gowal et al. (2018), have been proposed to reduce computational complexity. However, approximation errors remain a significant obstacle for providing provable guarantees. These errors mainly arise when relaxing unstable ReLUs whose pre-activation intervals contain zero. To mitigate such errors, two major approaches have been broadly explored. The first is branch-and-bound (BaB) methods Bunel et al. (2018); De Palma et al. (2021); Shi et al. (2025), which split unstable activation functions into sub-domains for complete verification. The second is certifiably robust training methods Shi et al. (2021); De Palma et al. (2023); Lee et al. (2021); Mao et al. (2023), which incorporate bound information, including unstable activations Xiao et al. (2018); Shi et al. (2021); De Palma et al. (2022), into the training objectives. Ultimately, both verification and training approaches aim to reduce the approximation errors introduced by unstable ReLUs, which remain the primary bottleneck in tightening output bounds.

On the other hand, Linearity Grafting (LG) Chen et al. (2022) is a prior method that directly replaces ReLUs likely to be both unstable and insignificant with linear functions, aiming to reduce the number of unstable ReLUs rather than stabilizing them. Consequently, LG successfully reduces the number of unstable neurons and enables scalable and complete verification, while improving certified robustness. However, it primarily focuses on identifying such neurons, and lacks theoretical insight into how this introduction leads to certified robustness improvements even without certified training.
We instead consider linearity grafting primarily as a means of eliminating approximation errors rather than reducing the number of unstable neurons, since linear functions do not require relaxation.

Intuitively, reducing approximation errors narrows the gap between the upper and lower bounds of neural networks. This not only tightens the local Lipschitz constant but also improves certified robustness. Despite their impact on certified robustness, little attention has been paid to identifying and removing neurons that contribute significantly to approximation errors. Ideally, targeting ReLUs that have the greatest impact on the local Lipschitz constant would be most effective, especially when only a limited number of neurons can be modified.

Motivated by this intuition, we propose a Lipschitz-aware linearity grafting method that introduces linearity into ReLUs which produce dominant approximation errors —crucial for tightening the $l_{\infty}$ local Lipschitz constant— and thereby improves certified robustness.

Our contributions are summarized as follows:

- •
We theoretically analyze why grafting linearity into non-linear unstable ReLUs improves certified robustness through the lens of $l_{\infty}$ local Lipschitz constant. Since active and inactive ReLUs do not require relaxation, grafted ReLUs similarly bypass the need for relaxation.
- •
We demonstrate that grafting linearity into non-linear activation functions which are dominant source of approximation errors tightens the local Lipschitz constant further by considering the intervals between the upper and lower bounds of activation functions. Replacement of these activation functions with linear functions reduces the local Lipschitz constant and further improves certified robustness.
- •
We introduce a linearity grafting criterion, weighted interval score, to identify influential neurons with large weighted intervals that significantly affect the local Lipschitz constant in the next layer. Because the local Lipschitz constant measures the maximum sensitivity to input perturbation, reducing the contribution of such neurons is critical for tightening Lipschitz bounds. Grafting linearity into these neurons identified by the weighted interval score reduces the $l_{\infty}$ local Lipschitz constant to a level comparable to that of certifiably robust models.
- •
Additionally, we propose a novel slope loss, designed to stabilize unstable neurons by leveraging the slope of the upper bounds of ReLUs, and a backward neuron selection algorithm that considers the relationship between neurons in the consecutive layer in terms of the Lipschitz constant.

Our extensive experiments demonstrate that grafting linearity into influential ReLUs, identified by the weighted interval score, tightens the $l_{\infty}$ local Lipschitz constant and improves certified robustness.

## 2 Related Works

### 2.0 Notations

Let $f(\theta;x):\mathbb{R}^{d_{0}}\rightarrow{}\mathbb{R}^{d_{L-1}}$, $W^{(\ell)}\in\mathbb{R}^{d_{\ell}}\times\mathbb{R}^{d_{\ell-1}}$, $b\in\mathbb{R}^{d_{l}}$, and $\sigma$ be a parameterized $L$-layer neural network, weight matrix, bias, activation function, respectively.
Given an input $x\in\mathbb{R}^{d_{0}}$, we define pre-activation values $z$, post-activation values $h$ as follows:
$z^{(\ell)}=W^{(\ell)}h^{(\ell-1)}+b^{(\ell)}$, $h^{(\ell)}=\sigma(z^{(\ell)})$ $\forall{\ell}\in\{1,...,L-1\}$
where $h^{(0)}(x)=x$.
We refer a lower and upper bound of $z_{i}^{(\ell)}$, pre-activation values of $i$-th neurons in $\ell$-th layer, as $lb_{i}^{(\ell)}$ and $ub^{(\ell)}_{i}$.

### 2.1 Relaxation of neural networks

Neural network verification ensures that a network satisfies given specification under all possible inputs within a defined perturbation. However, computing the exact worst-case adversarial examples is NP-complete Katz et al. (2017). To mitigate this problem, various relaxation methods such as Interval Bound Propagation (IBP) Gowal et al. (2018); Mirman et al. (2018), linear relaxation Zhang et al. (2019a), semi-definite programming Raghunathan et al. (2018) are proposed.

Linear relaxation methods approximate non-linear functions (e.g. ReLU) to certify neural networks by providing the linear bounds of neural networks:

$$ $A^{L}(x+\Delta)+b^{L}\leq f_{i}(x+\Delta)\leq A^{U}(x+\Delta)+b^{U}$ (1) $$

where $A=W^{L}D^{L}W^{L-1}D^{L-1}\dots D^{1}W^{1}$, $W$ is weight matrices, $D$ is diagonal matrices of relaxed ReLUs Zhang et al. (2019a). $D$ consists of upper and lower bounds of non-linear activation. In practice, neural networks verify whether the lower bound of the target class exceeds the upper bounds of all other classes for perturbed inputs. These lower bounds are computed by summing up upper and lower bounds from neurons in the previous layer, multiplied by negative and positive weights, respectively. This can be formulated as described below:

$$ $lower^{(\ell+1)}_{i}=\sum_{j}w^{-}_{j,i}\cdot upper^{(\ell)}_{j}+w^{+}_{j,i}\cdot lower^{(\ell)}_{j}$ (2) $$

This method is computationally efficient but incomplete, as it often produces “unknown” answer instead of “yes” or “no” answers. To achieve complete verification, branch-and-bound (BaB) method is used Bunel et al. (2018); De Palma et al. (2021); Shi et al. (2025). Complete verifiers with BaB method split unstable neurons into sub-domains and proceed verification on these sub-domains recursively. However, the effectiveness of this complete verifier is heavily constrained by the number of unstable neurons, making verification infeasible for larger neural networks.

There also exists a line of work based on randomized smoothing Cohen et al. (2019); Rekavandi et al. (2024) that certifies classification robustness by adding Gaussian noise to inputs, offering scalable probabilistic guarantees under perturbations. However, since the randomized smoothing methods do not explicitly address unstable neurons, we do not further investigate this line of work in this paper.

### 2.2 Lipschitz constant for robustness

The Lipschitz constant $L$ of $f$ is defined as the smallest value such that for all $x,y\in\mathbb{R}^{n}$,

$$ $\|f(x)-f(y)\|\leq L\|x-y\|.$ $$

This constant measures the maximum rate of change of the function over the entire input space. However, computing the global Lipschitz constant—i.e., the supremum of the norm of the Jacobian over all inputs—is often computationally infeasible, and the resulting bound is typically too loose to capture meaningful behavior. In contrast, the local Lipschitz constant provides a tighter measure within a neighborhood of a given input, but computing it exactly is NP-complete and thus computationally intractable.

To overcome this, various works aim to compute tighter upper bounds for the local Lipschitz constant. CLEVER score Weng et al. (2018b) uses random gradient sampling and extreme value theory to estimate local Lipschitz values. Other approaches such as Fast-Lip Weng et al. (2018a) and RecurJac Zhang et al. (2019b) compute conservative Jacobian bounds through recursive layer-wise analysis. Furthermore, leveraging Jacobians with bound propagation and branch-and-bound refinement Shi et al. (2022) achieves near-MIP-level tightness while it is scalable to relatively larger models.

Beyond analysis, the Lipschitz constant has been used in certifiably robust training Huang et al. (2021); Zhang et al. (2022). Lipschitz-margin training, for example, directly incorporates bounds into the loss function. Alternatively, Lipschitz-constrained architectures are designed to be 1-Lipschitz by construction using orthonormal weights or GroupSort activations. On the other hand, clipping upper bound of ReLUs with a trainable parameter tightens the local Lipschitz bound Huang et al. (2021), while improving certified robustness.

In this paper, we focus on the $l_{\infty}$ local Lipschitz constant over $x$ in $\ell_{\infty}$-ball, $B(x_{0},\epsilon)=\{x\in\mathbb{R}^{n}:\|x-x_{0}\|_{\infty}\leq\epsilon\}$. The local Lipschitz constant is then given by

$$ $Lip_{\infty}(f(x_{0}),\epsilon)=\sup_{\begin{subarray}{c}x,x^{\prime}\in B(x_{0},\epsilon)\\ x\neq x^{\prime}\end{subarray}}\frac{\|f(x)-f(x^{\prime})\|_{\infty}}{\|x-x^{\prime}\|_{\infty}}.$ $$

### 2.3 Grafting and pruning for robustness

Pruning has been used to remove insignificant neurons or weights for model compression Han et al. (2015); Liu et al. (2018).
Network pruning is to remove neurons, themselves. On the other hand, Weight pruning can be categorized into unstructured pruning and structured pruning. Unstructured pruning, also known as weight pruning, cuts connections between neurons by zeroing out individual weightsHan et al. (2015). The unstructured pruning does not help reducing inference time or model size. In contrast, structured pruning removes more structured weights (e.g. filter, channel). With structured pruning, inference acceleration and model size reduction can be achieved He et al. (2017). As the granularity of pruning increases, the model size can be reduced more significantly, but the information loss also becomes greater. To take advantages of the both filter pruning and channel pruning, clustering-based pruning methods Zhong (2022) are proposed. This pruning method not only improves inference time, but also remove model size simultaneously. Pruning neurons in a backward manner Yu et al. (2018) is also studied that minimizes the reconstruction error of important responses based on final response layer.

From the perspective of removing insignificant neurons, pruning methods also used to improve robustness of neural networksWang et al. (2018); Sehwag et al. (2020); Ye et al. (2019); Vemparala et al. (2021); Liu et al. (2022). HYDRA Sehwag et al. (2020) uses a gradient-based approach to iteratively identify and remove less important connections based on a robust loss with risk minimization, rather than relying on simple magnitude heuristics. HARP Zhao & Wressnegger (2024) learns per-layer pruning masks and rates to maximize robustness retention. By gradually increasing the sparsity and optimizing layer-specific pruning during fine-tuning, HARP achieves extreme compression (up to $99\%$ parameter removal) with only minimal impact on adversarial accuracy. However, pruning for certified robustness has not been broadly explored Sehwag et al. (2020); Lahav & Katz (2021); Zhangheng et al. (2022); Zhao & Wressnegger (2024).

Linearity grafting Chen et al. (2022) is aligned with network pruning in that it identifies target neurons to control. This approach replaces them with linear functions with learnable slope and bias parameters. Especially, pruning can be viewed as a special case of linearity grafting when the slope and bias parameters are set to zero. However, it lacks theoretical insight into how this introduction leads to certified robustness improvement.

## 3 The relationship between grafting linearity and l ∞ l_{\infty} local Lipschitz constant

In this section, we demonstrate why linearity grafting improves certified robustness through the lens of the $l_{\infty}$ local Lipschitz constant, and show that grafting linearity into non-linear activation functions, the dominant source of approximation errors, yields a tighter local Lipschitz constant. It is worth noting that linearity grafting was originally proposed to reduce the number of unstable ReLUs without any theoretical insights.

###### Lemma 1 (Local Lipschitz constant of grafted network)

Let $f:\mathbb{R}^{d_{0}}\rightarrow\mathbb{R}^{d_{L-1}}$ be a feedforward neural network, $x\in\mathbb{R}^{d_{0}}$ be an input, and $\epsilon$ be a perturbation budget. Suppose that we identify a set of unstable ReLUs for $\ell$-th layer, ${\mathbb{U}}^{(\ell)}=\{j\mid\mathrm{lb}^{(\ell)}_{j}<0<\mathrm{ub}^{(\ell)}_{j}\}$, and apply linearity grafting by replacing the ReLU of $j$-th neuron in $\ell$-th layer, $j\in{\mathbb{U}}^{(\ell)}$, with a linear function with slope $\gamma\leq 1$, then the $l_{\infty}$ local Lipschitz constant of the grafted network $f_{\text{graft}}$ satisfies:

$$ $Lip_{\infty}(f_{\text{graft}}(x),\epsilon)\leq Lip_{\infty}(f(x),\epsilon).$ $$

Lemma 1 shows that grafting linearity into unstable ReLUs produces a tighter $\ell_{\infty}$ local Lipschitz constant when the slope of the grafted linear function is less than or equal to 1. The proof of Lemma 1 is provided in Appendix [C](https://arxiv.org/html/2510.25130v1#A3).

###### Theorem 1

Let $s_{i}^{(\ell)}=\max_{i}(|w_{i,j}|\cdot|f^{U(\ell)}_{i}-f^{L(\ell)}_{i}|)$ be the score for $i$-th neuron in $\ell$-th layer, $\epsilon$ be a perturbation budget, and ${\mathbb{G}}_{k}\subset{\mathbb{U}}^{(\ell)}$ be the top-$k$ scoring neurons in terms of score $s$. Then, for any other subset ${\mathbb{O}}_{k}\subset{\mathbb{U}}^{(\ell)}$ of equal size not selected by score, and input $x$, grafting linearity into neurons in ${\mathbb{G}}_{k}$ leads to a tighter $l_{\infty}$ local Lipschitz bound:

$$ $Lip_{\infty}(f_{\text{graft}}(x;{\mathbb{G}}_{k}),\epsilon)\leq Lip_{\infty}(f_{\text{graft}}(x;{\mathbb{O}}_{k}),\epsilon)$ $$

Theorem 1 demonstrates that applying linearity grafting with unstable ReLUs, which are the dominant source of approximation errors by the score function, tightens the $\ell_{\infty}$ local Lipschitz constant further than replacing randomly selected unstable ReLUs with linear functions. The proof is provided in Appendix [D](https://arxiv.org/html/2510.25130v1#A4).

###### Lemma 1 (Local Lipschitz constant of grafted network)

###### Theorem 1

## 4 Methods

Following the theorem, we propose a Lipschitz-aware linearity grafting method that introduces linearity into unstable yet influential ReLUs in a backward manner, aiming to reduce the local Lipschitz constants of neurons in the next layer. Additionally, we introduce a slope loss to stabilize unstable neurons by encouraging the slope of their upper bound to be close to zero or one.

### 4.1 Neuron selection criteria

We consider two criteria for neuron selection: weighted interval score $s_{wi}$, and instability score $s_{u}$.

Weighted interval score. Given a set of selected neurons $P^{(\ell+1)}$ in $\ell+1$ layer, the weighted interval score of $j$-th neuron in $\ell$-th layer, $s_{wi}^{(\ell)}(j)$, is defined as the maximum over inputs $\chi$ of the absolute value of intervals between the upper and lower bounds, multiplied by weights connected to the selected neurons only in the next layer. We refer neurons with high $s_{wi}$ scores as “influential” neurons to Lipschitz constant of neurons in the next layers in this paper.

$$ $s_{wi}^{(\ell)}(j)=\max_{i\in\chi}\max_{k\in P^{(\ell+1)}}|w_{j,k}^{(\ell+1)}|\cdot|ub_{j}^{(\ell)\{i\}}-lb_{j}^{(\ell)\{i\}}|$ (3) $$

To tighten Lipschitz constant, we take into account the term $|w_{j,k}^{(\ell+1)}|\cdot|ub_{j}^{(\ell)}-lb_{j}^{(\ell)}|$ composing the calculation of Lipschitz constant.
Especially, we presume that the upper and lower bound of the activation outputs are loosely their upper and lower bound values of pre-activations for the efficient calculation. Note that calculating the weighted interval score introduces negligible computational overhead, as it can be performed simultaneously with the instability score computation. All we need to do is solely keeps tracking minimum and maximum values of unstable neurons.

Instability score. The instability score of $j$-th neuron in $\ell$-th layer, $s_{u}(j,\ell)$, represents the number of inputs $\chi$ for which a neuron is unstable Chen et al. (2022).

$$ $s_{u}(j,\ell)=\sum_{i\in\chi}\mathds{1}[lb_{j}^{(\ell)\{i\}}<0,ub_{j}^{(\ell)\{i\}}>0]$ (4) $$

where $\mathds{1}$ is an indicator.

### 4.2 Neuron selection method

Since approximation errors propagate from previous layers, we identify neurons that are the most influential to the lower bounds of neurons in the next layer in a backward manner [1](https://arxiv.org/html/2510.25130v1#alg1). By considering the connections of the selected neurons in the next layer, our method helps minimize the influence of these neurons. Neurons in $\ell$-th layers, except the last layer, are selected based on the following criteria in a backward manner. In this work, we layer-wisely select the top $15\%$ of neurons based on $s_{wi}^{(\ell)}$ from within the $80\%$ most globally unstable neurons. If all neurons in the last layer are selected, we retain $70\%$ of them based on $s_{u}$ to maximize the effectiveness of our method. For the remaining neurons, we select those with the highest $s_{u}^{(\ell)}$ scores. This criteria prioritize influential and unstable neurons that contribute most to Lipschitz constant of neurons in the next layer, while neurons in the last layer are selected solely based on the instability score, $s_{u}$.

### 4.3 s ​ l ​ o ​ p ​ e slope loss functions for unstable ReLU

We propose $slope$ loss that is designed to stabilize unstable neurons by leveraging the slopes of ReLUs upper bounds.
The $slope$ loss makes the slopes deviate from $\frac{1}{2}$, encouraging them to be close to $1$ or 0 corresponding to slopes of active or inactive ReLUs, respectively. The $slope$ loss is also applied to slopes of the grafted neurons, since the slopes of the grafted neurons work similarly to the slopes of upper bound.

$$ $Loss_{slope}=1-tanh(k\times(1-s)^{2})$ (5) $$

where $k=2$ in this work, $s=\frac{ub}{ub-lb}$ for the unstable ReLUs and $s=\gamma$ for the grafted linearity ($\gamma x+c$). It is worth noting that $\alpha$-CROWN Xu et al. (2020b) adjusts the slopes of ReLU lower bounds. At first glance, this appears similar to our slope loss, since both methods utilize ReLU bounds. However, the key difference is that our slope loss leverages the upper bounds, whereas $\alpha$-CROWN relies on the lower bounds.

For training neural networks, we use Fast Adversarial Training (FAT) Wong et al. (2020) with Gradient Alignment (GA) Andriushchenko & Flammarion (2020) as LG did Chen et al. (2022). It is already been demonstrated that introducing weight sparsity via $l_{1}$ regularization, small weight pruning, and $RS$ loss, helps verification Xiao et al. (2018) and this can be applied to grafting linearity into ReLUs Chen et al. (2022). We take advantage of this, except for the $RS$ loss. Thus the total loss function is the followings:

$$ $loss=loss_{FAT}+\lambda\times R_{GA}+\beta\times loss_{Slope}+\gamma\times l_{1}reg.$ (6) $$

where hyper parameters $\lambda=0.2$, $\beta=0.00005$, and $\gamma=0.0001$.

## 5 Experiments

We train four different sizes of model: CNN-B Dathathri et al. (2020), ConvBig Mirman et al. (2018), ConvHuge (17M), and ResNet4B Bak et al. (2021). ConvHuge has $17M$ parameters so it may seldom produce “Out-Of-Memory” (OOM) error due to a large number of unstable neurons. Since the number of OOM we encountered is negligible ($<10$), we ignore the OOM errors. Our method is implemented based on Auto-LiRPA Xu et al. (2020a).

Datasets. These models are trained on MNIST Deng (2012), SVHN Netzer et al. (2011), and CIFAR-10 Krizhevsky et al. (2009) with $\epsilon=\frac{2}{255}$ except for the MNIST ($\epsilon=0.1$) under $l_{\infty}$ perturbation. Due to the high volume of computation, we set calibration datasets sampled from the training datasets only for the calculation of both scores based on the model size: $4000$ samples from MNIST dataset for ConvBig, and CIFAR10 dataset for CNN-B, $3000$ samples from SVHN dataset for ConvBig, CIFAR10 dataset for ResNet4B and ConvBig, and $2000$ samples from CIFAR10 for ConvHuge. Otherwise, we use the FULL training datasets to train models.

Training settings. We conduct all experiments on a single GPU, NVIDIA-RTX A6000 with 48GB memory. Except the hyper parameters for $slope$ loss, $l_{1}$ regularizer, and small weight pruning, we use the same configuration in Chen et al. (2022) including $0.2$ coefficient for GradAlign, SGD optimizer with $0.9$ momentum, and $5\times 10^{-4}$ weight decay: 0.1 learning rate which is reduced by a factor of ten at 100 and 150 epochs, 128 batch size, $0.001$ learning rate for the remaining parameters, and $0.01$ learning rate for the slopes and intercepts of grafted neurons. We set the initial slope and bias for the grafted neurons to $0.4$ and $0.0$ following Chen et al. (2022).

Evaluation metrics. We evaluate our method with five measurements: standard accuracy (SA %), robust accuracy (RA %), verified accuracy (VA %), unstable neuron ratio (UNR %), and verification time (Time, sec.). In more details, RA is measured by PGD-100 Madry (2017) with 100 restarts. UNR is the number of unstable neurons divided by the total number of neurons in the neural networks. Verification time is the amount of time to verify the datasets excluding misclassified or PGD-100 attacked. We set a wall time as 300 seconds, and $\alpha$$\beta$ CROWN Zhang et al. (2018); Xu et al. (2020b); Wang et al. (2021) is used to measure VA and UNR. VA is evaluated with the first 1000 test datasets due to the high computational cost.

### 5.1 Comparison of our method and LG

In this experiment, we evaluate our criteria without applying additional techniques such as $l_{1}$ regularization or small weight pruning. As shown in Table [1](https://arxiv.org/html/2510.25130v1#S5.T1), models trained with our masks outperform those trained with LG’s masks in terms of VA, UNR, and Time, except for the experiment on the MNIST dataset. Specifically, our approach achieves VA improvements of 10.90%, 3.50%, 22.90%, 4.80%, and 5.90% for ConvBig-CIFAR10, CNN-B-CIFAR10, ConvHuge-CIFAR10, ResNet4B-CIFAR10, and ConvBig-SVHN, respectively. However, the experiment on ConvBig-MNIST shows a decrease in verification performance (-9.80% VA), an increase in UNR (+2.73%), and a longer verification time (+28.69 sec.). Nevertheless, the average of SA and RA drops are only 0.75% and 1.22%, respectively. neural networks with our masks outperform in verification performance while decreasing only $0.75\%$ SA and $1.22\%$ RA. Overall, neural networks trained with our masks achieve superior verification performance while slightly reducing SA and RA.

**Table 1: We evaluate SA, RA, VA, UNR, and Time for neural networks trained with our masks and LG’s masks. Models trained with our mask outperform those trained with LG’s mask.**
| Method ($\epsilon=\frac{2}{255}$) | ConvBig, cifar-10 | CNN-B, cifar-10 | ConvHuge, cifar-10 |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| SA | RA | VA | UNR | Time | SA | RA | VA | UNR | Time | SA | RA | VA | UNR | Time |  |
| Baseline | 86.76 | 73.98 | 1.5 | 17.75 | 121.61 | 80.13 | 63.00 | 36.70 | 16.74 | 133.64 | 89.56 | 74.06 | 0.20 | 17.32 | 159.80 |
| LG^† Chen et al. (2022) | 77.73 | 61.52 | 35.30 | 5.99 | 135.17 | 73.49 | 57.40 | 48.10 | 5.44 | 51.57 | 78.65 | 62.17 | 9.40 | 9.21 | 270.49 |
| Ours | 74.31 | 58.33 | 46.20 | 5.57 | 65.06 | 73.16 | 57.17 | 51.60 | 5.08 | 29.44 | 79.62 | 62.62 | 32.30 | 8.80 | 182.30 |
| Method ($\epsilon=\frac{2}{255}$) | ConvBig, MNIST $\epsilon=0.1$ | ResNet4B, cifar-10 | ConvBig, SVHN |  |  |  |  |  |  |  |  |  |  |  |  |
| SA | RA | VA | UNR | Time | SA | RA | VA | UNR | Time | SA | RA | VA | UNR | Time |  |
| Baseline | 99.19 | 97.39 | 92.10 | 17.78 | 15.77 | 77.80 | 60.17 | 0.50 | 20.44 | 34.00 | 88.76 | 73.88 | 13.30 | 13.47 | 213.17 |
| LG^† Chen et al. (2022) | 99.38 | 97.79 | 94.90 | 5.05 | 8.65 | 68.61 | 52.36 | 34.50 | 7.10 | 108.49 | 88.28 | 73.56 | 55.00 | 4.05 | 74.53 |
| Ours | 98.96 | 93.79 | 85.10 | 8.33 | 37.34 | 67.33 | 51.15 | 39.30 | 7.49 | 71.38 | 88.25 | 73.63 | 60.90 | 4.49 | 55.97 |

### 5.2 Comparison of performances including s ​ l ​ o ​ p ​ e slope loss and R ​ S RS loss

We evaluate the performance of our approach with the $slope$ loss by comparing it to LG with the $RS$ loss. Additionally, we apply $l_{1}$ regularization and small weight pruning with a pruning ratio of 30% to introduce weight sparsity for further performance improvement. According to Table [2](https://arxiv.org/html/2510.25130v1#S5.T2), our method with the $slope$ loss outperforms models trained with LG and the $RS$ loss, except for the experiment on the MNIST dataset with the ConvBig model. VA improvements are 9.30%, 3.00%, 25.90%, 6.20%, and 8.00% for ConvBig-CIFAR10, CNN-B-CIFAR10, ConvHuge-CIFAR10, ResNet4B-CIFAR10, and ConvBig-SVHN, respectively. Moreover, the UNR decreases by 3.12%, 1.86%, 7.23%, 4.80%, 0.71%, and 2.38% for ConvBig-CIFAR10, CNN-B-CIFAR10, ConvHuge-CIFAR10, ConvBig-MNIST, ResNet4B-CIFAR10, and ConvBig-SVHN. Notably, for the ConvBig model on the MNIST dataset, the reduction in UNR is particularly significant, decreasing from 5.05% to 0.25% — a nearly complete stabilization.

**Table 2: Our method with $slope$ loss shows better VA compared to LG with $RS$ loss.**
| Method ($\epsilon=\frac{2}{255}$) |  | ConvBig, cifar-10 |  |  | CNN-B, cifar-10 |  |  | ConvHuge, cifar-10 |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| SA | RA | VA | UNR | Time | SA | RA | VA | UNR | Time | SA | RA | VA | UNR | Time |  |
| LG w/ RS loss | 77.04 | 61.60 | 41.30 | 6.06 | 104.15 | 71.89 | 57.71 | 49.00 | 5.66 | 38.08 | 75.50 | 60.35 | 25.50 | 8.44 | 181.24 |
| Ours w/ slope loss | 69.39 | 55.88 | 50.60 | 2.94 | 26.50 | 71.09 | 56.44 | 52.00 | 3.80 | 14.27 | 68.86 | 55.80 | 51.40 | 1.21 | 31.25 |
| Method ($\epsilon=\frac{2}{255}$) |  | ConvBig, MNIST $\epsilon=0.1$ |  |  | ResNet4B, cifar-10 |  |  | ConvBig, SVHN |  |  |  |  |  |  |  |
| SA | RA | VA | UNR | Time | SA | RA | VA | UNR | Time | SA | RA | VA | UNR | Time |  |
| LG w/ RS loss | 99.30 | 97.70 | 95.30 | 5.05 | 5.84 | 67.43 | 52.13 | 37.40 | 6.87 | 89.01 | 89.03 | 74.54 | 60.00 | 3.99 | 59.94 |
| Ours w/ slope loss | 97.65 | 86.65 | 81.80 | 0.25 | 14.34 | 65.30 | 50.73 | 43.60 | 6.16 | 45.99 | 88.34 | 74.68 | 68.00 | 1.61 | 25.86 |

### 5.3 l ∞ l_{\infty} local Lipschitz constant of different training methods

As illustrated in Table [3](https://arxiv.org/html/2510.25130v1#S5.T3), the CNN-B model trained with our method exhibits a tighter $l_{\infty}$ local Lipschitz constant compared to the model trained with adversarial training. In addition, Our Lipschitz constant obtained by our method is also smaller than that of the certifiably trained model, while still achieving higher VA. These results demonstrate that linearity grafting into influential ReLUs identified by our method not only tightens the local Lipschitz constant but also improves the certified robustness, thereby supporting the claim in Lemma [1](https://arxiv.org/html/2510.25130v1#Thmlemma1).

**Table 3: Comparison of other training methods w.r.t. $l_{\infty}$ Lipschitz constant of CNN-B models**
| Training method | $l_{\infty}$ local Lipschitz constant | VA |
| --- | --- | --- |
| Adversarial training | 65.95 | 36.70 |
| Certifiably robust training | 20.82 | 49.50 |
| Ours w/ slope | 16.63 | 52.00 |

### 5.4 Comparision between highest and lowest weighted interval scores w.r.t. l ∞ l_{\infty} local Lipschitz constant

As illustrated in the Table [4](https://arxiv.org/html/2510.25130v1#S5.T4), linearity grafting with the highest weighted interval scores $s_{wi}$ results in a tighter $l_{\infty}$ local Lipschitz constant than the model with the lowest weighted interval scores. This result aligns with the arguments in Theorem [1](https://arxiv.org/html/2510.25130v1#Thmtheorem1): grafting linearity into ReLUs that have a dominant source of approximation errors leads to a tighter Lipschitz constant. In this work, the dominant source of approximation errors is measured by the weighted interval score.

**Table 4: Comparison with grafting non-influential ReLUs w.r.t. $l_{\infty}$ Lipschitz constant of CNN-B models**
| Grafting criteria | $l_{\infty}$ local Lipschitz constant | VA |
| --- | --- | --- |
| Lowest $s_{wi}$ scores | 17.49 | 51.70 |
| Highest $s_{wi}$ scores (Ours) | 16.63 | 52.00 |

### 5.5 Comparison between s ​ l ​ o ​ p ​ e slope loss and R ​ S RS loss

For a fair comparison between our $slope$ loss and $RS$ loss, we conduct an ablation study by combining our masking with $RS$ loss and LG masking with $slope$ loss. In this experiment, we do not train the slopes of grafted neurons to ensure fairness, but we still apply $l_{1}$ regularization and small weight pruning with $30\%$ pruning ratio. As shown in Table [5](https://arxiv.org/html/2510.25130v1#S5.T5), models trained with $slope$ loss ②④ outperform those trained with $RS$ loss ①③ w.r.t. VA, UNR, and Time. Comparing results (①-③ and ②-④), our criteria demonstrate better verification performances than LG’s criteria. In terms of UNR, $slope$ loss effectively stabilizes unstable neurons more than the $RS$ loss, leading to a reduction in verification time.

**Table 5: Comparison of criteria with $slope$ loss and $RS$ loss**
| FAT ($\epsilon=\frac{2}{255}$) |  | ConvBig, cifar-10 |  |  |  |
| --- | --- | --- | --- | --- | --- |
| SA | RA | VA | UNR | Time |  |
| ① LG w/ RS | 77.04 | 61.60 | 41.30 | 6.73 | 104.15 |
| ② LG w/ slope | 75.37 | 60.52 | 45.40 | 4.60 | 76.03 |
| ③ Ours w/ RS | 71.55 | 56.71 | 49.70 | 5.83 | 37.95 |
| ④ Ours w/ slope | 69.14 | 55.88 | 50.60 | 2.94 | 26.50 |

### 5.6 Comparison with certifiably robust training methods

We compare our method with other certifiably robust training methods. As shown in the Table [6](https://arxiv.org/html/2510.25130v1#S5.T6), ours with $slope$ loss outperforms IBP Shi et al. (2021) w.r.t. SA, RA, and VA. However, the MTL-IBP De Palma et al. (2023) method shows better performance in terms of RA and VA. Interestingly, ours yields higher SA compared to other certifiably robust training methods.

**Table 6: Comparison with certifiably robust training methods on CNN-B, cifar-10.**
| Method ($\epsilon=\frac{2}{255}$) |  | CNN-B, cifar-10 |  |  |  |
| --- | --- | --- | --- | --- | --- |
| SA | RA | VA | UNR | Time |  |
| IBP Shi et al. (2021) | 61.47 | 51.78 | 49.50 | 1.45 | 4.45 |
| MTL-IBP De Palma et al. (2023) | 71.52 | 62.01 | 57.00 | 7.43 | 17.32 |
| Ours w/o slope | 73.16 | 57.17 | 51.60 | 5.08 | 29.44 |

### 5.7 Experiment on different ϵ \epsilon

Table [7](https://arxiv.org/html/2510.25130v1#S5.T7) shows that models trained with our method with $\epsilon=8./255$ outperform in terms of VA regardless of $slope$ loss. The results indicate that our method maintains its effectiveness at $\epsilon=\frac{8}{255}$.

**Table 7: Experiment on different target $\epsilon$ ($\frac{8}{255}$)**
| Method ($\epsilon=\frac{8}{255}$) |  | CNN-B, cifar-10 |  |  |  |
| --- | --- | --- | --- | --- | --- |
| SA | RA | VA | UNR | Time |  |
| LG (literature) Chen et al. (2022) | 58.87 | 31.34 | 4.70 | 12.35 | 257.59 |
| Ours w/o slope | 52.89 | 29.51 | 15.70 | 14.27 | 126.69 |
| Ours w/ slope | 49.81 | 29.62 | 21.40 | 3.71 | 56.85 |

### 5.8 Applicability to Non-ReLU activations

We observed that applying our method (w/o slope loss) with non-ReLU activations improves verified accuracy (VA) from 41.5% to 43.1% (+1.6%) on Sigmoid networks and from 40.2% to 46.1% (+5.9%) on Tanh networks, without performing any hyperparameter tuning. Although SA and RA dropped by about 2% in both cases, these initial results suggest that our method has the potential to generalize beyond ReLU-based architectures. The experiments are conducted on the CNN-B with cifar-10, under the same adversarial training setup as used in our paper.

**Table 8: Experiments on non-ReLU activations**
| Method ($\epsilon=\frac{2}{255}$) | Sigmoid | Tanh |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| SA | RA | VA | Time | SA | RA | VA | Time |  |
| Adversarial training | 62.39 | 50.82 | 41.5 | 1.32 | 65.59 | 52.15 | 40.2 | 10.29 |
| Ours | 60.38 | 48.06 | 43.1 | 2.96 | 63.1 | 50.43 | 46.1 | 5.24 |

## 6 Conclusion

In this paper, we provide two theoretical contributions, previously underexplored, for how linearity grafting improves certified robustness through the lens of the local Lipschitz constant and how grafting linearity into non-linear activation functions, which are the dominant source of approximation errors, helps tighten the Lipschitz constant.
Building on these theoretical insights, we propose Lipschitz-aware linearity grafting with weighted interval score to identify influential neurons with the greatest influence on the local Lipschitz constant. We further introduce slope loss to stabilize unstable neurons showing the reduced UNR, and backward neuron selection algorithm that considers the relationship between neurons in consecutive layers and the local Lipschitz constant.
Our experiments align well with our claims from both theoretical contributions. In addition, they confirm that our method reduces the $l_{\infty}$ local Lipschitz constant to a level comparable to that of certifiably robust models, while significantly improving certified robustness.

## References

- Andriushchenko & Flammarion (2020)
Maksym Andriushchenko and Nicolas Flammarion.
Understanding and improving fast adversarial training.
*Advances in Neural Information Processing Systems*, 33:16048–16059, 2020.
- Bak et al. (2021)
Stanley Bak, Changliu Liu, and Taylor Johnson.
The second international verification of neural networks competition (vnn-comp 2021): Summary and results.
*arXiv preprint arXiv:2109.00498*, 2021.
- Bunel et al. (2018)
Rudy R Bunel, Ilker Turkaslan, Philip Torr, Pushmeet Kohli, and Pawan K Mudigonda.
A unified view of piecewise linear neural network verification.
*Advances in Neural Information Processing Systems*, 31, 2018.
- Chen et al. (2022)
Tianlong Chen, Huan Zhang, Zhenyu Zhang, Shiyu Chang, Sijia Liu, Pin-Yu Chen, and Zhangyang Wang.
Linearity grafting: Relaxed neuron pruning helps certifiable robustness.
In *International Conference on Machine Learning*, pp. 3760–3772. PMLR, 2022.
- Cohen et al. (2019)
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter.
Certified adversarial robustness via randomized smoothing.
In *international conference on machine learning*, pp. 1310–1320. PMLR, 2019.
- Dathathri et al. (2020)
Sumanth Dathathri, Krishnamurthy Dvijotham, Alexey Kurakin, Aditi Raghunathan, Jonathan Uesato, Rudy R Bunel, Shreya Shankar, Jacob Steinhardt, Ian Goodfellow, Percy S Liang, et al.
Enabling certification of verification-agnostic networks via memory-efficient semidefinite programming.
*Advances in Neural Information Processing Systems*, 33:5318–5331, 2020.
- De Palma et al. (2021)
Alessandro De Palma, Rudy Bunel, Alban Desmaison, Krishnamurthy Dvijotham, Pushmeet Kohli, Philip HS Torr, and M Pawan Kumar.
Improved branch and bound for neural network verification via lagrangian decomposition.
*arXiv preprint arXiv:2104.06718*, 2021.
- De Palma et al. (2022)
Alessandro De Palma, Rudy Bunel, Krishnamurthy Dvijotham, M Pawan Kumar, and Robert Stanforth.
Ibp regularization for verified adversarial robustness via branch-and-bound.
*arXiv preprint arXiv:2206.14772*, 2022.
- De Palma et al. (2023)
Alessandro De Palma, Rudy Bunel, Krishnamurthy Dvijotham, M Pawan Kumar, Robert Stanforth, and Alessio Lomuscio.
Expressive losses for verified robustness via convex combinations.
*arXiv preprint arXiv:2305.13991*, 2023.
- Deng (2012)
Li Deng.
The mnist database of handwritten digit images for machine learning research [best of the web].
*IEEE signal processing magazine*, 29(6):141–142, 2012.
- Gowal et al. (2018)
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli.
On the effectiveness of interval bound propagation for training verifiably robust models.
*arXiv preprint arXiv:1810.12715*, 2018.
- Han et al. (2015)
Song Han, Jeff Pool, John Tran, and William Dally.
Learning both weights and connections for efficient neural network.
*Advances in neural information processing systems*, 28, 2015.
- He et al. (2017)
Yihui He, Xiangyu Zhang, and Jian Sun.
Channel pruning for accelerating very deep neural networks.
In *Proceedings of the IEEE international conference on computer vision*, pp. 1389–1397, 2017.
- Huang et al. (2021)
Yujia Huang, Huan Zhang, Yuanyuan Shi, J Zico Kolter, and Anima Anandkumar.
Training certifiably robust neural networks with efficient local lipschitz bounds.
*Advances in Neural Information Processing Systems*, 34:22745–22757, 2021.
- Jordan & Dimakis (2020)
Matt Jordan and Alexandros G Dimakis.
Exactly computing the local lipschitz constant of relu networks.
*Advances in Neural Information Processing Systems*, 33:7344–7353, 2020.
- Katz et al. (2017)
Guy Katz, Clark Barrett, David L 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 I 30*, pp. 97–117. Springer, 2017.
- Krizhevsky et al. (2009)
Alex Krizhevsky, Geoffrey Hinton, et al.
Learning multiple layers of features from tiny images.
2009.
- Lahav & Katz (2021)
Ori Lahav and Guy Katz.
Pruning and slicing neural networks using formal verification.
In *2021 Formal Methods in Computer Aided Design (FMCAD)*, pp. 183–192. IEEE, 2021.
- Lee et al. (2021)
Sungyoon Lee, Woojin Lee, Jinseong Park, and Jaewook Lee.
Towards better understanding of training certifiably robust models against adversarial examples.
*Advances in Neural Information Processing Systems*, 34:953–964, 2021.
- Liu et al. (2022)
Chen Liu, Ziqi Zhao, Sabine Süsstrunk, and Mathieu Salzmann.
Robust binary models by pruning randomly-initialized networks.
*Advances in Neural Information Processing Systems*, 35:492–506, 2022.
- Liu et al. (2018)
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell.
Rethinking the value of network pruning.
*arXiv preprint arXiv:1810.05270*, 2018.
- Madry (2017)
Aleksander Madry.
Towards deep learning models resistant to adversarial attacks.
*arXiv preprint arXiv:1706.06083*, 2017.
- Mao et al. (2023)
Yuhao Mao, Mark Niklas Müller, Marc Fischer, and Martin Vechev.
Understanding certified training with interval bound propagation.
*arXiv preprint arXiv:2306.10426*, 2023.
- Mirman et al. (2018)
Matthew Mirman, Timon Gehr, and Martin Vechev.
Differentiable abstract interpretation for provably robust neural networks.
In *International Conference on Machine Learning*, pp. 3578–3586. PMLR, 2018.
- Netzer et al. (2011)
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Baolin Wu, Andrew Y Ng, et al.
Reading digits in natural images with unsupervised feature learning.
In *NIPS workshop on deep learning and unsupervised feature learning*, volume 2011, pp.  4. Granada, 2011.
- Raghunathan et al. (2018)
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang.
Certified defenses against adversarial examples.
*arXiv preprint arXiv:1801.09344*, 2018.
- Rekavandi et al. (2024)
Aref Rekavandi, Farhad Farokhi, Olga Ohrimenko, and Benjamin Rubinstein.
Certified adversarial robustness via randomized $\alpha$-smoothing for regression models.
*Advances in Neural Information Processing Systems*, 37:134127–134150, 2024.
- Sehwag et al. (2020)
Vikash Sehwag, Shiqi Wang, Prateek Mittal, and Suman Jana.
Hydra: Pruning adversarially robust neural networks.
*Advances in Neural Information Processing Systems*, 33:19655–19666, 2020.
- Shi et al. (2021)
Zhouxing Shi, Yihan Wang, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsieh.
Fast certified robust training with short warmup.
*Advances in Neural Information Processing Systems*, 34:18335–18349, 2021.
- Shi et al. (2022)
Zhouxing Shi, Yihan Wang, Huan Zhang, J Zico Kolter, and Cho-Jui Hsieh.
Efficiently computing local lipschitz constants of neural networks via bound propagation.
*Advances in Neural Information Processing Systems*, 35:2350–2364, 2022.
- Shi et al. (2025)
Zhouxing Shi, Qirui Jin, Zico Kolter, Suman Jana, Cho-Jui Hsieh, and Huan Zhang.
Neural network verification with branch-and-bound for general nonlinearities.
In *International Conference on Tools and Algorithms for the Construction and Analysis of Systems*, pp. 315–335. Springer, 2025.
- Szegedy et al. (2014)
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.
Intriguing properties of neural networks, 2014.
URL [https://arxiv.org/abs/1312.6199](https://arxiv.org/abs/1312.6199).
- Vemparala et al. (2021)
Manoj-Rohit Vemparala, Nael Fasfous, Alexander Frickenstein, Sreetama Sarkar, Qi Zhao, Sabine Kuhn, Lukas Frickenstein, Anmol Singh, Christian Unger, Naveen-Shankar Nagaraja, et al.
Adversarial robust model compression using in-train pruning.
In *Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition*, pp. 66–75, 2021.
- Wang et al. (2018)
Luyu Wang, Gavin Weiguang Ding, Ruitong Huang, Yanshuai Cao, and Yik Chau Lui.
Adversarial robustness of pruned neural networks.
2018.
- Wang et al. (2021)
Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and J Zico Kolter.
Beta-crown: Efficient bound propagation with per-neuron split constraints for neural network robustness verification.
*Advances in Neural Information Processing Systems*, 34:29909–29921, 2021.
- Weng et al. (2018a)
Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon.
Towards fast computation of certified robustness for relu networks.
In *International Conference on Machine Learning*, pp. 5276–5285. PMLR, 2018a.
- Weng et al. (2018b)
Tsui-Wei Weng, Huan Zhang, Pin-Yu Chen, Jinfeng Yi, Dong Su, Yupeng Gao, Cho-Jui Hsieh, and Luca Daniel.
Evaluating the robustness of neural networks: An extreme value theory approach.
*arXiv preprint arXiv:1801.10578*, 2018b.
- Wong & Kolter (2018)
Eric Wong and Zico Kolter.
Provable defenses against adversarial examples via the convex outer adversarial polytope.
In *International conference on machine learning*, pp. 5286–5295. PMLR, 2018.
- Wong et al. (2020)
Eric Wong, Leslie Rice, and J Zico Kolter.
Fast is better than free: Revisiting adversarial training.
*arXiv preprint arXiv:2001.03994*, 2020.
- Xiao et al. (2018)
Kai Y Xiao, Vincent Tjeng, Nur Muhammad Mahi Shafiullah, and Aleksander Madry.
Training for faster adversarial robustness verification via inducing relu stability.
In *International Conference on Learning Representations*, 2018.
- Xu et al. (2020a)
Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai-Wei Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsieh.
Automatic perturbation analysis for scalable certified robustness and beyond.
*Advances in Neural Information Processing Systems*, 33:1129–1141, 2020a.
- Xu et al. (2020b)
Kaidi Xu, Huan Zhang, Shiqi Wang, Yihan Wang, Suman Jana, Xue Lin, and Cho-Jui Hsieh.
Fast and complete: Enabling complete neural network verification with rapid and massively parallel incomplete verifiers.
*arXiv preprint arXiv:2011.13824*, 2020b.
- Ye et al. (2019)
Shaokai Ye, Kaidi Xu, Sijia Liu, Hao Cheng, Jan-Henrik Lambrechts, Huan Zhang, Aojun Zhou, Kaisheng Ma, Yanzhi Wang, and Xue Lin.
Adversarial robustness vs. model compression, or both?
In *Proceedings of the IEEE/CVF International Conference on Computer Vision*, pp. 111–120, 2019.
- Yu et al. (2018)
Ruichi Yu, Ang Li, Chun-Fu Chen, Jui-Hsin Lai, Vlad I Morariu, Xintong Han, Mingfei Gao, Ching-Yung Lin, and Larry S Davis.
Nisp: Pruning networks using neuron importance score propagation.
In *Proceedings of the IEEE conference on computer vision and pattern recognition*, pp. 9194–9203, 2018.
- Zhang et al. (2022)
Bohang Zhang, Du Jiang, Di He, and Liwei Wang.
Rethinking lipschitz neural networks and certified robustness: A boolean function perspective.
*Advances in neural information processing systems*, 35:19398–19413, 2022.
- Zhang et al. (2018)
Huan Zhang, Tsui-Wei Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel.
Efficient neural network robustness certification with general activation functions.
*Advances in neural information processing systems*, 31, 2018.
- Zhang et al. (2019a)
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, and Cho-Jui Hsieh.
Towards stable and efficient training of verifiably robust neural networks.
*arXiv preprint arXiv:1906.06316*, 2019a.
- Zhang et al. (2019b)
Huan Zhang, Pengchuan Zhang, and Cho-Jui Hsieh.
Recurjac: An efficient recursive algorithm for bounding jacobian matrix of neural networks and its applications.
In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 33, pp. 5757–5764, 2019b.
- Zhangheng et al. (2022)
LI Zhangheng, Tianlong Chen, Linyi Li, Bo Li, and Zhangyang Wang.
Can pruning improve certified robustness of neural networks?
*Transactions on Machine Learning Research*, 2022.
- Zhao & Wressnegger (2024)
Qi Zhao and Christian Wressnegger.
Holistic adversarially robust pruning.
*arXiv preprint arXiv:2412.14714*, 2024.
- Zhong (2022)
Shaochen Zhong.
Revisit kernel pruning with lottery regulated grouped convolutions.
Master’s thesis, Case Western Reserve University, 2022.

## Appendix A The Use of Large Language Models (LLMs)

We acknowledge that LLMs were employed to polish the writing of our paper, primarily to improve grammar and readability. In line with the ICLR 2026 policy on LLM usage, we emphasize that such an assistant was limited to linguistic refinement, while all substantive ideas, analyses, and experiments are solely the work of the authors with full responsibility for the content presented herein.

## Appendix B Limitations

As shown in Table [6](https://arxiv.org/html/2510.25130v1#S5.T6), models trained with our method do not always outperform verifiably trained models. The main difference is that our method does not leverage lower bounds of worst-case adversarial examples during training. In contrast, state-of-the-art approaches incorporate both adversarial and certified losses to improve both empirical and certified robustness. Nevertheless, our method can be applied to adversarially pre-trained models, which are empirically robust but not verifiably robust. It is worth noting that our method enables such models to achieve verifiable robustness using only adversarial training. We leave a more thorough integration of our method with certified adversarial training as an important direction for future work.

## Appendix C Proof of Lemma 1

Proof.

Base case: $\ell=0$,

$$ $x_{0}-\epsilon\leq f^{(0)}=x_{0}\leq x_{0}+\epsilon$ (7) $$

$$ $Lip_{\infty}(f^{(0)}(x_{0}),\epsilon)=\frac{|f^{U(0)}-f^{L(0)}|}{|(x_{0}+\epsilon)-(x_{0}-\epsilon)|}=\frac{2\epsilon}{2\epsilon}=1$ (8) $$

$$ $Lip_{\infty}(f_{graft}^{(0)}(x_{0}),\epsilon)=\frac{|f_{graft}^{U(0)}-f_{graft}^{L(0)}|}{|(x_{0}+\epsilon)-(x_{0}-\epsilon)|}=\frac{2\epsilon}{2\epsilon}=1$ (9) $$

$$ $Lip_{\infty}(f_{graft}^{(0)},\epsilon)=Lip_{\infty}(f^{(0)},\epsilon)$ (10) $$

Base case: $\ell=1$,

$$ $\begin{split}Lip_{\infty}(f^{(1)},\epsilon)&=max_{j}\frac{|f^{U(1)}_{j}-f^{L(1)}_{j}|}{2\epsilon}\\ &=max_{j}\sum_{i}\frac{|W_{i,j}^{(1)}|\cdot|f^{U(0)}_{i}-f^{L(0)}_{i}|}{2\epsilon}\\ &=max_{j}\sum_{i}\frac{|W_{i,j}^{(1)}|\cdot|2\epsilon|}{2\epsilon}\end{split}$ (11) $$

$$ $\displaystyle\begin{split}&Lip_{\infty}(f_{graft}^{(1)},\epsilon)\\ &=max_{j}\frac{|f_{graft\;j}^{U(1)}-f_{graft\;j}^{L(1)}|}{2\epsilon}\\ &=max_{j}\sum_{i\notin{\mathbb{U}}^{(0)}}\frac{|W_{i,j}^{(1)}|\cdot|f_{graft\;i}^{U(0)}-f_{graft\;i}^{L(0)}|}{2\epsilon}\\ &\quad+\sum_{i\in{\mathbb{U}}^{(0)}}\frac{|W_{i,j}^{(1)}|\cdot|\gamma(y^{(0)}+\omega)-\gamma(y^{(0)}+\omega)|}{2\epsilon}\\ &=max_{j}\sum_{i\notin{\mathbb{U}}^{(0)}}\frac{|W_{i,j}^{(1)}|\cdot|2\epsilon|}{2\epsilon}+\sum_{i\in{\mathbb{U}}^{(0)}}\frac{|W_{i,j}^{(1)}|\cdot|2\gamma\epsilon|}{2\epsilon}\\ \end{split}$ (12) $$

Under the assumption: slope $\gamma\leq 1$,

$$ $\displaystyle\begin{split}&Lip_{\infty}(f^{(1)},\epsilon)-Lip_{\infty}(f_{graft}^{(1)},\epsilon)\\ &=max_{j}\sum_{i\notin{\mathbb{U}}^{(0)}}|W_{i,j}^{(1)}|\cdot|2\epsilon|-\sum_{i\in{\mathbb{U}}^{(0)}}|W_{i,j}^{(1)}|\cdot|2\gamma\epsilon|\\ &\geq 0\end{split}$ (13) $$

$$ $Lip_{\infty}(f_{graft}^{(1)},\epsilon)\leq Lip_{\infty}(f^{(1)},\epsilon)$ (14) $$

Assume that $\ell=k,\ Lip_{\infty}(f_{graft}^{(k)},\epsilon)\leq Lip_{\infty}(f^{(k)},\epsilon)$ holds.

Then,

$$ $\displaystyle\begin{split}Lip_{\infty}(f^{(k+1)}_{j},\epsilon)&=\max_{j}\frac{|f^{U(k+1)}_{j}-f^{L(k+1)}_{j}|}{2\epsilon}\\ &=\max_{j}\sum_{i}\frac{|W_{i,j}^{(k+1)}|\cdot|f^{U(k)}_{i}-f^{L(k)}_{i}|}{2\epsilon}\\ &\geq\max_{j}\sum_{i}\frac{|W_{i,j}^{(k+1)}|\cdot|f_{graft\;i}^{U(k)}-f_{graft\;i}^{L(k)}|}{2\epsilon}\\ &=\max_{j}\frac{|f_{graft\;j}^{U(k+1)}-f_{graft\;j}^{L(k+1)}|}{2\epsilon}\\ &=Lip_{\infty}(f_{graft\;j}^{(k+1)},\epsilon)\end{split}$ (15) $$

$$ $Lip_{\infty}(f_{graft}^{(k+1)},\epsilon)\leq Lip_{\infty}(f^{(k+1)},\epsilon)$ (16) $$

Thus, by the principle of mathematical induction, Lemma 1 holds for all $\ell\geq 1$.

## Appendix D Proof of Theorem 1

$$ $\displaystyle\begin{split}Lip_{\infty}(f_{graft\;j}^{(\ell)}(x;{\mathbb{G}}_{k}^{(\ell-1)}),\epsilon)&=\sum_{i\notin{\mathbb{G}}^{(\ell-1)}}\frac{|W^{(\ell)}_{i,j}|\cdot|f^{U(\ell-1)}_{i}-f^{L(\ell-1)}_{i}|}{2\epsilon}\\ &\quad+\sum_{k\in{\mathbb{G}}^{(\ell-1)}}\frac{|W^{(\ell)}_{k,j}|\cdot|f^{U(\ell-1)}_{k}-f^{L(\ell-1)}_{k}|}{2\epsilon}\end{split}$ (17) $$

$$ $\displaystyle\begin{split}Lip_{\infty}(f_{graft\;j}^{(\ell)}(x;{\mathbb{O}}_{k}^{(\ell-1)}),\epsilon)&=\sum_{i\notin{\mathbb{O}}^{(\ell-1)}}\frac{|W^{(\ell)}_{i,j}|\cdot|f^{U(\ell-1)}_{i}-f^{L(\ell-1)}_{i}|}{2\epsilon}\\ &\quad+\sum_{k\in{\mathbb{O}}^{(\ell-1)}}\frac{|W^{(\ell)}_{k,j}|\cdot|f^{U(\ell-1)}_{k}-f^{L(\ell-1)}_{k}|}{2\epsilon}\end{split}$ (18) $$

Assume that $Lip_{\infty}(f_{graft\;j}^{(\ell)}(x;{\mathbb{O}}^{(\ell-1)}_{k}),\epsilon)<Lip_{\infty}(f_{graft\;j}^{(\ell)}(x;{\mathbb{G}}^{(\ell-1)}_{k}),\epsilon)$.

$$ $\begin{split}\sum_{i\notin{\mathbb{O}}^{(\ell-1)}}|W^{(\ell)}_{i,j}|\cdot|f^{U(\ell-1)}_{i}-f^{L(\ell-1)}_{i}|+\sum_{k\in{\mathbb{O}}^{(\ell-1)}}|W^{(\ell)}_{k,j}|\cdot|f^{U(\ell-1)}_{k}-f^{L(\ell-1)}_{k}|\\ <\sum_{i\notin{\mathbb{G}}^{(\ell-1)}}|W^{(\ell)}_{i,j}|\cdot|f^{U(\ell-1)}_{i}-f^{L(\ell-1)}_{i}|+\sum_{k\in{\mathbb{G}}^{(\ell-1)}}|W^{(\ell)}_{k,j}|\cdot|f^{U(\ell-1)}_{k}-f^{L(\ell-1)}_{k}|\end{split}$ (19) $$

$$ $\sum_{k\in{\mathbb{O}}^{(\ell-1)}\backslash{\mathbb{G}}^{(\ell-1)}}|W^{(\ell)}_{i,k}|\cdot|f^{U(\ell-1)}_{k}-f^{L(\ell-1)}_{k}|<\sum_{k\in{\mathbb{G}}^{(\ell-1)}\backslash{\mathbb{O}}^{(\ell-1)}}|W^{(\ell)}_{i,k}|\cdot|f^{U(\ell-1)}_{k}-f^{L(\ell-1)}_{k}|$ (20) $$

Right-hand side of the summation consists of the smallest $N-k$ elements, whose summation is the smallest sum when $N$ is the total number of neurons. By this contradiction,

$$ $\mathrm{Lip}_{\infty}(f_{\text{graft}}(x;{\mathbb{G}}_{k}),\epsilon)\leq\mathrm{Lip}_{\infty}(f_{\text{graft}}(x;{\mathbb{O}}_{k};),\epsilon)$ (21) $$

## Appendix E Calibration dataset

We conduct ablation study on the size of the calibration dataset used to compute the weighted interval score and the instability score. As shown in the Figure [1](https://arxiv.org/html/2510.25130v1#A5.F1), SA, RA, and VA show consistent performances regardless of the size of the datasets.

Figure: Figure 1: Comparison of SA, RA, and VA w.r.t. the size of training dataset used to compute the weighted interval score and instailibty score.
Refer to caption: x1.png

## Appendix F Verification on FULL Test set

We measure VA on FULL test set for our CNN-B model. Table [9](https://arxiv.org/html/2510.25130v1#A6.T9) shows that VA of CNN-B model trained with our method decreases only $0.56\%$ for full test dataset. The results show that testing on $1000$ test dataset is sufficient to measure the performance of the methods we used in experiments.

**Table 9: Verification of Full test dataset on CNN-B, cifar-10.**
| Size | SA | RA | VA |
| --- | --- | --- | --- |
| 1000 | 71.09 | 56.44 | 52 |
| 10000 | 71.09 | 56.44 | 51.44 |

## Appendix G Average lower bound

As shown in the Figure [2](https://arxiv.org/html/2510.25130v1#A7.F2), models trained with our method yield tighter average lower bounds compared to models trained with LG method.

Figure: Figure 2: Average lower bounds of our models
Refer to caption: x2.png

## Appendix H Neuron selection algorithm

Figure: Algorithm 1 Neuron selection algorithm

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 2
presentation: 1
questions: Based on the concerns above, I think the current manuscript needs major editing before being considered for publication at a top-iter conference. Please consider the following questions:

1. Discuss about the role of several hyper-parameter, how to set them and conduct ablation studies.

2. Include more baselines and apply the proposed method on that to more comprehensively validate the performance.

3. Provide more justifications about the theoretical analysis in the proof of Lemma 1. Answer the third point in the weakness part.

4. Include the writing to make the manuscript nicer and the terminology consistent.

In addition, I have the following question:

5. When considering the effect of one particular neuron on the local Lipschitz constant, why do you use the criteria in Section 4.1 instead of directly considering the difference between the local Lipschitz if we graft this unstable neuron and the original local Lipschitz. I think this value (the change of local Lipschitz) is more straightforward and not difficult to compute or estimate. In addition, this will facilitate us to select neuron across different layers, as the current criteria in Section 4.1 have different numerical meanings for different layers.

6. Instead of considering the largest sensitivity and the number of unstable inputs in Equation (3) and (4), why don't we consider the average sensitivity among the training set for neuron selection? I believe this will decrease the number of hyper-parameters.

7. It would be better to give a formal definition of "local Lipschitz constant" in the task we consider in this work.
soundness: 2
strengths: ++ It is novel and interesting to consider verified robustness from the perspective of controlling Lipschitz constant and grafting.

++ The proposed method is generic and plug-and-play.

++ The intuition is theoretically justified to some degree.
summary: This paper investigate how different non-stable ReLU neurons affects the local Lipschitz constant of the model when we consider the adversarial perturbations. It proposes two metrics "weighted interval score" and "instability score" which enables us to select the unstable neurons more critical to model's Lipshcitz constant and thus verified robustness. By grafting such neurons by a linear function, we can improve the verified robustness of the model.
weaknesses: 1. The proposed framework introduces a lot of hyper-parameters, including the number of grafted neurons each layer, $k$ in Equation (5), $\lambda$, $\beta$ and $\gamma$ in Equation (6). I believe all these hyper-parameters will affect the performance to some degree. However, I did not see ablation studies or adequate discussions about them.

2. The experiments are weak in general. Comparisons with more robustness certification and the corresponding provable training algorithms should be included. For example, Table 6 considers MTL-IBP, its successors like alpha-beta-CROWN should be included.

3. Theoretical claims seem not rigorous. I have concerns in the proof of Lemma 1, it is unclear to have $|f_i^{U(k)} - f_i^{L(k)}| \geq |f_{graft, i}^{U(k)} - f_{graft, i}^{L(k)}|$ for **all values of $I$** in Equation (15). The induction assumption only indicates $max_i |f_i^{U(k)} - f_i^{L(k)}| \geq max_i |f_{graft, i}^{U(k)} - f_{graft, i}^{L(k)}|$, as indicated in Equation (11). However, I do not see why this can generalise to any value of $k$. The authors should provide more theoretical details about this.

4. The theoretical analyses only support $l_\infty$ perturbations.

5. The presentation of this manuscript is relatively poor. For example, (1) the authors should correctly use \citep and \citet to include references; (2) In Equation (1), the relationship between $A^L$, $A^U$ and $A$ is unclear, does this indicate $A^L = A^U$?; (3) You use $Loss_{slope}$ in Equation (5) and $loss_{Slope}$ in Equation (6), please pay attention to the terminology consistency.

Minor:

1. In addition to the linearizing the loss function and randomized smoothing, there are several other types of certified robustness methods, including (1) using geometry: "Provable robustness of relu networks via maximization of linear regions." (2019), "Training Provably Robust Models by Polyhedral Envelope Regularization" (2023) (2) Lipschitz-aware training: "Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks" (2018)

---

confidence: 3
contribution: 1
initial_rating: 4
presentation: 2
questions: 1.	My main concern is that the paper includes only one baseline. Although I have not reviewed every bound-propagation paper, it is difficult to believe that the most relevant baseline is from 2022. Could the authors include comparisons with more recent or stronger methods?  
2.	In Table 3, the paper should also report the trade-off between clean and robust accuracy. While tightening (or suppressing) the Lipschitz constant is straightforward, it often comes at the cost of model utility. Demonstrating improvement beyond this trade-off would be crucial to show the true value of the method.
3.	The OOM statement on line 304 is unclear. Does it mean that the proposed method encounters out-of-memory (OOM) errors with some probability, and the training is restarted each time? Please clarify this behavior.
4.	The dataset used is relatively small. For more practical usage, can the paper consider cifar-100 or tiny-imagenet? Bound-propagation methods are often known to have scalability issues; providing detailed results on larger datasets would address this concern.
5.	For each attack evaluation, results are reported at only one perturbation budget. Providing results across multiple budgets would help readers assess performance trends. In addition, the chosen budgets are quite small. Please report robustness under larger budgets to evaluate the method’s behavior in more challenging regimes.
soundness: 2
strengths: 1.	The paper is well organized and clearly presented.
2.	The paper conducted extensive ablation studies to evaluate the effectiveness of the proposed method.
summary: The main idea of this paper is to graft linearity into non-linear activation functions. This leads to lower approximate errors, make Lipschitz tight, and enhance certified robustness. In my onion, however, the paper still falls short of meeting the ICLR publication standard in its current form.
weaknesses: 1.	The improvement is not significant and inconsistent. (as shown in Table 1 and 2)
2.	The core idea and methodology lack sufficient insight and novelty. Given that Lipschitz neural networks, such as LiResNet++ (Hu, 2024), have already scaled certified robustness to ImageNet and billion-parameter models, the proposed approach appears less competitive. Therefore, I would expect either a substantial performance improvement or a more conceptually innovative contribution.
[1] Hu, Kai, et al. "A Recipe for Improved Certifiable Robustness." ICLR, 2024.

---

confidence: 4
contribution: 2
initial_rating: 4
presentation: 2
questions: What is the formal definition of verified accuracy (VA %), and how does it relate to robust accuracy (RA %)? VA % seems to be introduced for the first time around line 321 without a clear explanation.
soundness: 3
strengths: The proposed approach improves upon the existing Linearity Grafting method and demonstrates potential in further tightening local Lipschitz constants.
summary: This paper investigates how linearity grafting—replacing parts of nonlinear activation functions with linear components—can enhance certified adversarial robustness by tightening local Lipschitz constants. The proposed Lipschitz-aware linearity grafting method aims to eliminate dominant approximation errors, thereby achieving tighter local Lipschitz bounds and improved certified robustness without requiring certified training.
weaknesses: * The authors state at the beginning of the abstract that “Lipschitz constant is a fundamental property in certified robustness, as smaller values imply robustness to adversarial examples.” However, despite obtaining a tighter local Lipschitz constant, the empirical results (Table 1) show a drop in robust accuracy (RA %). This seems contradictory to the intended goal of improving robustness. Could the authors clarify whether this behavior aligns with their theoretical claims?

* The standard accuracy (SA %) decreases significantly in most experiments, which undermines the contribution of this work. In extreme cases, one could simply remove a large proportion of unstable neurons to achieve a tighter Lipschitz bound but at the cost of severely degraded accuracy. The key challenge in Lipschitz-based methods lies in balancing SA and RA. The authors should discuss how their approach maintains this balance and why the accuracy degradation occurs.

* The proposed methods in Sections 4.2 and 4.3 are introduced rather abruptly and lack sufficient explanation. For instance, it is unclear how the specific proportions (e.g., 15 %, 80 %, 70 %) were determined (lines 268–270). Similarly, the design rationale for Eq. (5) and the choice of hyperparameters in Eq. (6) need to be clarified and justified.

* Table 7 presents results for a larger perturbation radius (ε), but the discussion is minimal. It would be helpful to elaborate on whether the proposed method can be easily extended to handle larger ε values and how this impacts performance.

* The empirical evaluation is relatively limited. It would strengthen the paper to include comparisons with more existing Lipschitz-based robustness methods, providing a broader context for the improvements claimed.

[1] Yang, Yao-Yuan, et al. "A closer look at accuracy vs. robustness." Advances in neural information processing systems 33 (2020): 8588-8601.
[2] Zhang, Bohang, et al. "Rethinking lipschitz neural networks and certified robustness: A boolean function perspective." Advances in neural information processing systems 35 (2022): 19398-19413.

---

confidence: 3
contribution: 3
initial_rating: 2
presentation: 2
questions: - When unstable neurons are grafted and then verified, doesn't that mean that the original network remains unverified?
- Is the verified accuracy determined based on the computed Lipschitz bounds or is an external verifier used?
- Are the results solely on one evaluation run per method? If not, over how many runs are the presented training runs averaged? Can you also provide a standard deviation?
- How sensitive is your approach to the chosen hyperparameters (l.268-269, l.284, l.297)?
soundness: 2
strengths: - The topic is of certifying robustness is important in safety-critical systems.
- The paper presents theoretical results on grafting linearity w.r.t. to $\ell_\infty$ local Lipschitz bound.
- Obtaining neural networks with fewer unstable neurons generally greatly improves verifiably due to a reduced accumulated approximation error.
summary: The paper investigates how to improve local Lipschitz constants in ReLU neural networks.
This is done both theoretically as well as practical aspects are addressed.
The core components include identifying neurons using a weighted interval score and an instability score, as well as a slope loss encouraging unstable neurons to become more stable.
weaknesses: - It appears that the approach is mainly about the training process; however, this only becomes clear later in the paper and is not adequately addressed, e.g., in the abstract.
- While Theorem 1 provides a nice theoretical result, a different scoring system is used in Sec. 4.
- The paper would benefit from more formalism in Sec. 4, e.g.,  how are lb/ub determined, what is $\chi$, ...
- No standard benchmarks, e.g., from latest VNN-COMP [1] are used.
- The comparison to other certified training approaches could be improved. See, e.g., [2] for a good overview.
- The presentation could be improved using some figures illustrating the process.

[1] Brix et al. "The fifth international verification of neural networks competition (vnn-comp 2024): Summary and results." arXiv. 2024.
[2] Koller et al. "Set-based training for neural network verification." TMLR. 2025.

Minor points:
- I think the reference in l.266 is broken (should reference Alg. 1?)


Decision: Reject