Probabilistically Tightened Linear Relaxation-based Perturbation Analysis for Neural Network Verification

Luca Marzari, Ferdinando Cicalese, Alessandro Farinelli · 2025

Read Probabilistically Tightened Linear Relaxation-based Perturbation Analysis for Neural Network Verification by Luca Marzari, Ferdinando Cicalese, Alessandro Farinelli (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-05405.txt.

Introduction

Luca Marzari, Ferdinando Cicalese, and Alessandro Farinelli tighten the bounds used to verify neural networks, in a 2025 paper. Checking a network means proving its output stays in range under small input tweaks. Loose bounds make that proof slow or out of reach. Their method blends bound math with sampling to guess the true reach of each layer.

Sampled reach sets sharpen the straight-line bounds for the output at near no extra cost. The catch is that the proof now holds with high chance rather than with full force. On contest-grade test sets, certified tolerance to tweaks rose by more than two to three times over prior work. Hard cases that beat exact tools fell to this method.

Catalog record

CREATORLuca Marzari, Ferdinando Cicalese, Alessandro Farinelli
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE102 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-05405

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Probabilistically Tightened Linear Relaxation-based Perturbation Analysis for Neural Network Verification Luca Marzari, Ferdinando Cicalese, Alessandro Farinelli Abstract We present P robabilistically T ightened Li near R elaxation-based P erturbation A nalysis ( PT-LiRPA ), a novel framework that combines over-approximation techniques from LiRPA-based approaches with a sampling-based method to compute tight intermediate reachable sets. In detail, we show that with negligible computational overhead, PT-LiRPA exploiting the estimated reachable sets, significantly tightens the lower and upper linear bounds of a neural network’s output, reducing the computational cost of formal verification tools while providing probabilistic guarantees on verification soundness. Extensive experiments on standard formal verification benchmarks, including the International Verification of Neural Networks Competition, show that our PT-LiRPA -based verifier improves robustness certificates by up to 3.31X and 2.26X compared to related work. Importantly, our probabilistic approach results in a valuable solution for challenging competition entries where state-of-the-art formal verification methods fail, allowing us to provide answers with high confidence (i.e., at least 99%). 1 Introduction Deep neural networks (DNNs) and recently large language models (LLMs) have revolutionized various fields, from healthcare and finance to natural language processing, enabling remarkable capabilities, for instance, in image recognition [ 33 ] , robotic tasks such as manipulation [ 36 , 27 ] and navigation [ 41 , 28 , 13 ] . Nonetheless, their opacity and vulnerability to the so-called “adversarial inputs" [ 40 , 1 ] have also raised significant concerns, especially when deployed in safety-critical applications such as autonomous driving or medical diagnosis. Consequently, developing methods to certify the safety aspect of these models is crucial. Achieving provable safety guarantees involves employing formal verification (FV) of neural network techniques [ 23 ] , which mathematically ensures that a system will never produce undesired outcomes in all configurations tested. In this work, we focus on robustness verification, which aims to guarantee that a model’s output remains consistently robust under small predefined input perturbations around a given point {\bm{x}}_{0}, typically defined as an \ell_{\infty} ball of \varepsilon radius around the input {\bm{x}}_{0}, i.e., the set \mathcal{C}=\mathcal{C}_{{\bm{x}}_{0},\epsilon}=\{{\bm{x}}|\;||{\bm{x}}-{\bm{x}}_{0}||_{\infty}\leq\epsilon\}. A standard approach to proving the robustness property is to first encode the desired output of the classifier as the sign of the value f computed by a single (output) node, i.e., so that the correct classification in {\bm{x}}_{0} corresponds to f({\bm{x}}_{0})>0. Then, the robustness verification becomes equivalent to checking that \min\limits_{{\bm{x}}\in\mathcal{C}}f({\bm{x}}) , is positive [ 44 ] . However, due to the non-linear and non-convex nature of the DNN, solving this problem is, in general, NP-hard [ 22 , 47 ] . A recent line of works called linear relaxation-based perturbation analysis (LiRPA) algorithms [ 54 , 52 , 44 , 51 ] proposes a formal analysis based on a sound linear relaxation of the DNN. The idea is to compute relaxations of all sources of non-linearity in the network so as to obtain two linear functions providing respectively a lower and an upper bound of the DNN’s output, which are then used in the robustness certification. Nonetheless, these methods use overapproximation techniques to satisfy the worst-case setting, where no exceptions are allowed. While this strict approach ensures absolute safety within the certified input space, it faces crucial limitations. In fact, the efficiency of LiRPA approaches, and, in general, any FV methods, scales poorly with the size of the model. Additionally, formal methods fail to offer meaningful robustness information when input perturbations exceed the certified bounds. As discussed in [ 48 ] , relying solely on formal verification can lead to overly conservative outcomes, particularly when adversarial examples are rare or when prior knowledge of the input distribution is available. This stems from the exact nature of formal solvers, which treat all violations equally: even a single adversarial input—such as a one-pixel change—invalidates the entire region, without distinguishing between isolated, low-probability cases and large, semantically significant unsafe regions. Similar to recent approaches [ 48 , 12 ] , to overcome these critical limitations, we propose a probabilistic perspective that allows for an infinitesimal trade-off in certainty while providing the likelihood of such violations, enabling more nuanced and practical assessments of robustness that better reflect real-world risks. Importantly, the goal of this work is not to compare probabilistic methods with provable ones, as they are fundamentally different in nature. Rather, our objective is to propose a novel, complementary solution that enhances formal methods by offering additional safety information about the models under evaluation for particular challenging instances to be verified. Building on this foundation, we explore Xu et al. 2021 speculation that estimates as tightly as possible reachable sets, i.e., the range of possible values at each hidden node given bounded inputs, could significantly enhance verification efficiency by yielding sharper final linear bounds. In this perspective, we address two key research questions: (i) How can we compute reachable sets trading off (probabilistically measurable) tightness and computational tractability? (ii) What theoretical guarantees can we establish for linearized layers using (probabilistically sound) reachable set? Our Contributions. We propose P robabilistically T ightened Li near R elaxation-based P erturbation A nalysis ( PT-LiRPA ), a novel framework for computing tight linear lower and upper bounds combining existing LiRPA methods with a sampling-based reachable set estimation strategy. Unlike other related probabilistic works [ 48 , 12 ] , our approach does not rely on specific input distributions or attacks. Specifically, in this work, we start considering statistical results on tolerance limits [ 50 ] to provide probabilistic guarantees on estimating the minimum and maximum values of a neural network’s output. Using the approach of Wilks 1942 , we are guaranteed that, for any R,\psi\in(0,1), with probability \psi , at most, a fraction (1-R) of points from a possibly infinitely large sample in the perturbation region \mathcal{C} may violate the estimated bounds obtained from an initial sample, whose size n is explicitly computable from the desired parameters \psi and R . Hence, our intuition is to extend this approach to also compute an estimation of reachable sets with a specified confidence level. Nonetheless, while the result of [ 50 ] quantitatively bounds the error of the sample-based procedure by predicting the fraction of potential violations in future samples, it results in "weaker" guarantees with respect to other known probabilistic approaches. In particular, this approach does not provide information on the magnitude of these violations with respect to the estimated bounds. Specifically, in any estimated reachable set for a possibly existing fraction (1-R) of points drawn from \mathcal{C} , the probability of violating the bound might in principle be uncontrollably large. To address such an issue, following results on extreme value theory (EVT) [ 19 , 15 ] , we extend Wilks 1942 ’ probabilistic guarantees and present two novel bounds on the magnitude of potential errors between the true minimum (Theorem 3.5 ) and the sample-based estimated one (Theorem 3.7 ). Notably, our final result proves that with negligible computational overhead, each node’s reachable set computed using random samples represents with high probability the actual domain of that node for any x\in\mathcal{C} . Hence, we show that by employing this sampling-based procedure to compute probabilistically tight reachable set bounds in the neural network and integrating these into the linearization used by LiRPA-based formal

Read the complete text