Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Authors: David Boetius
Stefan Leue
Tobias Sutter
Venue: ICML 2025 poster (2025)
Keywords: neural network verification
probabilistic verification
fairness
safety
branch and bound
Primary area: deep_learning->everything_else
TL;DR: A sound and complete branch and bound algorithm for solving probabilistic verification problems of neural networks significantly outpacing existing algorithms.

Abstract: Probabilistic verification problems of neural networks are concerned with formally analysing the output distribution of a neural network under a probability distribution of the inputs. Examples of probabilistic verification problems include verifying the demographic parity fairness notion or quantifying the safety of a neural network. We present a new algorithm for solving probabilistic verification problems of neural networks based on an algorithm for computing and iteratively refining lower and upper bounds on probabilities over the outputs of a neural network. By applying state-of-the-art bound propagation and branch and bound techniques from non-probabilistic neural network verification, our algorithm significantly outpaces existing probabilistic verification algorithms, reducing solving times for various benchmarks from the literature from tens of minutes to tens of seconds. Furthermore, our algorithm compares favourably even to dedicated algorithms for restricted probabilistic verification problems. We complement our empirical evaluation with a theoretical analysis, proving that our algorithm is sound and, under mildly restrictive conditions, also complete when using a suitable set of heuristics.

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
David Boetius'
Stefan Leue
Tobias Sutter
Abstract
neural networks being fragile with respect to various types of input perturbations (Szegedy et al., 2014; Hosseini et al., 2017; Bibi et al., 2018; Ebrahimi et al., 2018; Hendrycks et al., 2021). In contrast, neural network verification ana- lyses neural networks with mathematical rigour, facilitating the faithful auditing of neural networks.
Probabilistic verification problems of neural net- works are concerned with formally analysing the output distribution of neural network un- der a probability distribution of the inputs. Ex- amples of probabilistic verification problems in- clude verifying the demographic parity fairness notion or quantifying the safety of a neural net- work. We present a new algorithm for solving probabilistic verification problems of neural net- works based on an algorithm for computing and iteratively refining lower and upper bounds on probabilities over the outputs of neural net- work. By applying state-of-the -frte-r-- bound propaga- tion and branch and bound techniques from non- probabilistic neural network verification, our al- gorithm significantly outpaces existing probab- ilistic verification algorithms, reducing solving times for various benchmarks from the literature from tens of minutes to tens of seconds. Further- more, our algorithm compares favourably even to dedicated algorithms for restricted probabilistic verification problems. We complement our empir- ical evaluation with a theoretical analysis, proving that our algorithm is sound and, under mildly re- strictive conditions, also complete when using a suitable set of heuristics.
In this paper, we consider probabilistic verification prob- lems of neural networks, which are concerned with proving statements about the output distribution of a neural network given a distribution of the inputs. We refer to solving probab- ilistic verification problems as probabilistic verification. An example of probabilistic verification is proving that a neural network net making a binary decision affecting a person (for example, hire/do not hire, credit approved/denied) satis- fies the demographic parity fairness notion (Barocas et al., 2023) under a probability distribution Fx of the network inputs representing the person
x is disadvantaged x [nne((x) yes
7
(1)
Px net (x) = yes x is advantaged]
where 'x is disadvantaged" could, for example, refer to person not being male and 7 E [0, 1] with y = 0.8 being common choice (Feldman et al., 2015). A closely related problem to probabilistic verification is computing bounds on probabilities over a neural network. An example of this is quantifying the safcty of a neural network by bounding
IP [net(x)) is unsafe).
(2)
In this paper, we introduce a novel algorithm for comput- ing bounds probabilities such Equation (2) using branch and bound framework (Land & Doig, 2010; Mor- rison et al., 2016; Bunel et al., 2020). These bounds allow us to verify probabilistic statements like Equation (1) using bound propagation (Moore et al., 2009; Albarghouthi et al., 2017). Our algorithm PROBABILIS TIC V VERIFICATION (PV) is fast and generally applicable probabilistic verification algorithm for neural networks based on massively parallel branch and bound neural network verification (Xu et al., 2021) using linear relaxations of neural networks (Weng et al., 2018: Zhang et al., 2018; Singh et al., 2019). Our the- oretical analysis shows that PV sound and, under mildly restrictive conditions, complete when using suitable branch- ing and splitting heuristies.
1. Introduction
As deep learning spreads through society, becomes in- creasingly important to ensure the reliability of artificial neural networks, including aspects of fairness and safety. However, manually introspecting neural networks is infeas- ible due to their non- non-trand transparent nature. Furthermore, em- pirical assessments of neural networks are challenged by
Department of Computer and Information Science, University of Konstanz, Konstanz, Baden- Würtemberg, Germany. Corres- pondence to: David Boetius <david. boetius buni-konstanz.de>.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Our experimental evaluation reveals that PV significantly outpaces the probabilistic verification algorithms FAIR- SQUARE (Albarghouthi et al., 2017) and SPACESCAN- NER (Converse et al., 2020). In particular, PV solves benchmark instances that FATRSQUARE. can not solve within 15 minutes in less than one minute and solves the ACAS Xu (Katz et al., 2017b) probabilistic robustness case study of Converse et al. (2020) a mean runtime of 22 seconds, compared to 33 minutes for SPACESCANNER.
ing (Katz et al., 2017b), Mixed Integer Linear Program- ming (MILP) (Tjeng et al., 2019; Cheng al., 2017), and reachability analysis (Bak et al., 2020; Tran et al., 2020a;b). Many of these approaches can be understood as branch and bound algorithms (Bunel et al., 2020). Branch and bound (Land & Doig, 2010; Morrison et al., 2016) also powers the ar u,3-CROWN (Zhou et al., 2024) verifier that leads the table in recent international neural network verifier competitions (Brix al., 2023; 2024). A critical component of a branch and bound verification algorithm is computing bounds on the output of a neural network. Approaches for bounding neural network outputs include interval arithmetic (Pulina & Tacchella, 2010), dual ap- proaches (Wong & Kolter, 2018), and linear bound propaga- tion techniques (Weng et al., 2018; Singh et al., 2019; Xu et al., 2021), such as CROWN (Zhang et al., 2018).
Applying PV to #DNN verification (Marzari et al., 2023a), a subset of probabilistic verification, reveals that PV also compares favourably to specialized algorithms, such as PROVE_SLR (Marzari et al., 2023b). It even compares favourably to F (Marzari et al., 2024) that relaxes #DNN verification to computing a confidence interval on the solution and PREIMGAPPROO (Zhang et al., 2024) that only computes sampling approximations, In contrast to this, PV computes lower and upper bounds on probabilities like Equation (2) that are guaranteed to hold with absolute cer- tainty. Such bounds are preferable to confidence intervals in high-risk machine-learning applications, such as medical applications or autonomous driving and flight.
Probabilistic verification algorithms can be divided into sound algorithms that provide valid proofs, probably sound algorithms that provide valid proofs only with a certain predefined probability, and unsound algorithms that do not quantify their probability of providing invalid proofs. Prob- ably sound algorithms provide similar guarantees as prob- ably approximately correct (PAC) learning (Bishop, 2007). Faimesss verification is subset of probabilistic verification that studies problems such as Equation (1). Another subset of probabilistic verification is #DNN verification (Marzari et al., 2023a), corresponding to probabilistic verification under uniformly distributed inputs. Table I provides an overview of approaches for neural network verification.
To test the limits of PV, we introduce a significantly more challenging probabilistic verification benchmark: The Mini- ACSIncome benchmark is based on the ACSIncome data- set (Ding et al., 2021) and is concerned with verifying the demographic parity of neural networks for datasets of in- creasing input dimensionality. MiniACCInccme provides more complex input distributions of higher dimensionality than earlier probabilistic verification benchmarks. Our main contributions are
By sacrificing soundness, probably sound verification al- gorithms (Bastani et al., 2019; Baluta et al., 2019; Weng et al., 2019; Marzari et al., 2023a: 2024) obtain efficiency. One example is E- (Marzari et al., 2024), a prob- ably sound #DNN verification algorithm. Bastani et al. (2019), Converse et al. (2020), and Marzari et al. (2023b) compare sound and probably sound approaches for probabil- istic verification. We study sound algorithms since certainly valid results are preferable in high-risk applications.
the PV algorithm for the probabilistic verification of neural networks,
theoretical analysis proving the soundness and com- pleteness of PV.
thorough experimental comparison of PV with ex- isting probabilistic verifiers for neural networks and tools dedicated to restricted subsets of probabilistic verification, and
Concerning sound approaches, FAIRSQUARE (Albarghouthi et al., 2017) is a sound fairness verification algorithm that partitions the input space into disjoint hyperrectangles and iteratively refines the input space partitioning using SMT solving. PROVE_SLR (Marzari et al., 2023b) is a sound #DNN verifier based massively parallel branch and bound algorithm. Converse et al. (2020) (SPACESSANNEER) and Borca- Tasciuc et al. (2023) divide the input space into disjoint polytopes using concolic execution and reach- able set verification, respectively. Both approaches are un- sound for fairness verification due to approximating con- tinuous probability distributions using histograms. SPACES- CA CANNER is sound for #DNN verification. PREIMGAP- PROX (Zhang al., 2024) divides the input space into dis-
MiniACSIncome: a new, challenging probabilistic veri- fication benchmark.
Our code is available at https://github. com/ sen-uni-kn/probee MiniACSIncome is avail- able as Python package at https://pypi.cor project/miniacsiinn
2. Related Work
Approaches for poo-rabbaii neural network verific- ation include Satisfiability Modulo Theories (SMT) soly-
2

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Table Comparison of Related Approaches. Sound approaches provide definite guarantees. Probably sound approaches only provide PyC-type guarantees. Approaches marked "unsound"' are sound in specific settings but neither sound nor probably sound in general.
Verification Problem
Non- Probabilistic
Group Fairness
General Probabilistic
Verifier
Approach
#DNN
Guarantee
Zhou et al. (2024); Tran et al. (2020b)
X
X
sound
Weng et al. (2019)
X
X
probably sound
Tasciuc et al. (2023)
X
X
X
unsound
Zhang et al. (2024)
X
X
X
unsound
Converse et al. (2020)
X
V
unsound*
Baluta et al. (2019); Marzari et al. (2023a; 2024)
X
X
X
probably sound
Bastani et al. (2019)
X
X
probably sound
Marzari et al. (2023b)
X
X
sound
Albarghouthi al. (2017)
X
X
sound
Morettin et al. (2024)
X
sound
Ours (PV)
X
sound
joint polytopes using ReLU branching (Bunel et al., 2020),
much higher dimensional probability distributions than we consider in this paper. Our restriction deterministic neural networks allows us to provide sound and complete yet practically scalable probabilistic verification algorithm.
but unsound due to using sampling approximate prob- abilities. However, offers post-verification soundness check for low-dimensional verification problems. Tran al. (2023) provide sound verifier based on reachability ana- lysis that is only applicable for truncated Gaussian input distributions. Morettin et al. (2024) use weighted model integration (Belle et al., 2015) to obtain a general sound probabilistic verification algorithm but neither provide code nor report runtimes.
Dependency fairness (Galhotra et al., 2017; Urban et al., 2020) is a -on-probabilistic individual fairness no- tion (Dwork et al., 2012). Approaches for verifying depend- ency fairness include (Ruoss et al., 2020; Urban et al., 2020; Biswas & Rajan, 2023; Mohammadi et al., 2023: Kim et al., 2024). We are concerned with probabilistic fairness notions.
From the above approaches, FAIRSQUARE and PROVE SLR are most closely related to our algorithm PV. However, PV is more general than FAIRSQUARE and PROVE_SLR, which are restricted to fairness verification and #DNN verification, respectively. Like FAIRSQUARE, PV iteratively refines bounds on probabilities to verify probabilistic statements like Equation (I). However, while FAIRSQUARE uses expensive SMT solving for refining the input space, we use computationally inexpensive input splitting and bound propagation techniques from non-probabilistic neural network verification. PROVE. SLR builds on similar techniques but computes probabilities exactly instead of iteratively refining bounds. These differ- ences allow PV significantly outpace both FAIRSQUARE and PROVE SLR, as demonstrated in Section 6.
3. Preliminaries and Problem Statement
Throughout this paper, we are concerned with computing (provable) lower and upper bounds.
Definition 3.1 (Bounds). For f R. - Rm we call E, RT lower, respectively, upper bound on f for X' C R" if < f(x) I u, for all x e X"
Neural Networks. In particular, we are concerned with computing bounds neural networks net X' - Rm where X' C R is the input space of the neural network. A neural network is a composition of linear functions and a predefined set of non-linear functions, such as ReLU and max pooling. We only study Lipschitz continuous neural networks, which includes many common architec- tures (Szegedy al., 2014; Ruan et al., 2018). Besides this, refrain from defining neural networks further, approach is not specific to any particular architecture.
A related problem to probabilistic verification of neural net- works is verifying Bayesian Neural Networks (BNNs) (Car- delli et al., 2019 9a;b; Wicker et al., 2020; 2024; Berrada et al., 2021; Adams et al., 2023; Batten et al., 2024). In BNNs, the network parameters follow probability distribution (Neal, 1996). Since neural networks typically have vastly more parameters than inputs, BNN verification is concerned with
Notation and Terminology. We use [ = {x E R"
x S x S x} to denote hyperrectangles and write [n] = [l...., n) for n E N. The term bounds generally refers to a pair of a lower and an upper bound in this paper. We
3

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
assume that all random objects are defined on the same abstract probability space (R, P) and that all continuous random variables admit probability density function.
the output of neural network from bounds on the network input. Assume x I x are bounds the network input x. We apply interval arithmetic to com- pute L S Isat ( net(x)) S Vx E [x, If the lower bound is large enough or the upper bound small enough, we can prove or disprove Equation (4) using > = Isat (x, nx)( 2 O, respectively, u < = Isar (X, nx)( 0. However, if the bounds are inconclus- ive, that is l < 0 u, Equation (4). Therefore, interval arithmetic is incomplete according to Definition 3.2.
3.1. Probabilistic Verification of Neural Networks
Let X' C R" be (potentially unbounded) hyperrectangle and let E N. We are concerned with proving disproving whether a neural network net: X' + RM is feasible for the probabilistic verification problem
neither prove nor disprove
{ [sat
Pu)) 2 O, (2) Pi = IP x Saa (x(1), net net (x(1)) 2 0] Vi [o),
Let f : R + R be a function that we want to bound for inputs x E [x.x]. Interval arithmetic and other bound propagation techniques rely on f = f(k) o o... o f()) be- ing a composition of more fundamental functions f(k) R + R for which we can already compute g()) I (z) S <x( given S z S z. Examples of such functions include monotone non-decreasing functions, for which ((()(2) S (z) S (())()) This bounding rule already allows us to bound addition, min, max, and ReLU, among others. Appendix contains further bounding rules. Given a bounding rule F(k) 1 x xR + R x R for each f(*), interval arithmetic computes bounds on f by computing (F(R) ....o ....) (x, x).
where x(0) i E [o], is an X'valued random variable with distribution x(i) and Ssat. : RR + R. PSat R x RT > R. i [o] are satisfaction functions that are compositions of linear functions, multiplication, division, and monotone functions. Appendix A expresses Equation (1) in the form of Equation (3) as a concrete example.
(8)
Probabilistic verification with a single uniformly distributed random variable corresponds to #DNN verification (Marz- ari et al., 2023a). As Marzari et al. (2023a) prove, #DNN verification is #P complete, implying that probabilistic veri- fication is #P hard. However, this does not determine which probabilistic verification problems are practically solvable.
Branch and Bound. Bound propagation approaches, such as interval arithmetic and CROWN (Zhang et al., 2018), are incomplete according to Definition 3.2. To obtain a complete verifier, bound propagation can be combined with branching to gain completeness. This algorithmic frame- work is called branch and bound (Land & Doig, 2010; Morrison et al., 2016). In branch and bound, the search space is split (branching) when the computed bounds are inconclusive (f < 0 S u). The idea is that splitting im- proves the precision of the bounds for each part of the split (each brunch). Bunel et al. (2020) provide an introduction to branch and bound for probbabbbiiiit neural network veri- fication. The next section introduces our branch and bound algorithm for probabilistic neural network verification.
3.2. Non-Probabillitii Neural Network Verification
Non-probabiliitii neural network verification determines whether net : X + Rm is feasible for
Isat (x, net(x)) 2 0 VX Ex,
(4)
where X' C X' is a bounded hyperrectangle, and Isat : R" x Tm - IR. is a satisfaction function that indicates whether the output of net is desirable (Asar (1, ne)(-)) > 0) or undesirable (Asat ne)())))) < 0). In neural net- work verification, Isat can generally be considered part of net (Bunel et al., 2020; Xu et al., 2020). Neural network verifiers are algorithms for proving or disproving Equa- tion (4). Two desirable properties of neural network verifiers are soundness and completeness.
4. Algorithm
This section introduces PROBABILISTTICEERIICCCCC (PV), our algorithm for probabilistic verification of neural networks as defined in Equation
Definition 3.2 (Soundness and Completeness). A verifica- tion algorithm sound if it only produces genuine counter- examples and valid proofs for Equation (4). It is complete if it produces counterexample or proof for Equation (4) for any neural network in a finite amount of time.
(3). The overall approach of PV is to iteratively refine bounds each p; from Equa- tion (3) until bound propagation approach allows us to prove or disprove fsac (PI...., PP) 2 O. For computing the bounds on pt. PV partitions the input space into hy- perrectangles since this allows for computing probabilities efficiently (A (Albarghouthi al., 2017). To compute tighter bounds on ps, PV uses a branch and bound algorithm that uses computationally inexpensive input splitting and bound propagation techniques from probabbbaiilistic neural net-
Analogous notions of soundness and completeness also ap- ply to probabilistic verification. Section 2 discusses prob- ably sound verification.
Interval Arithmetic. Interval arithmetic (Moore et al., 2009) is a bound propagation technique that derives bounds
4

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
S
S
S
S
S
S
Satisfaction Boundary
V
V
V
V
X2
X
V
S
S
V
S
S
V
V
V
S
S
V
S
S
(a) After four Splits.
(b) After 17 Splits.
(c) Probability Density Function.
Figure Computing bounds on probabilities. This figure illustrates steps computing bounds on p p= Fxx [Ssar. (x, net net (x)) ) 2 0].
Our algorithm successively splits the input space to find regions that do not intersect the satisfaction boundary Isar (x, (xt(x) 2 0
(orange/green line ). Green, orange, and grey rectangles D'=) denote regions for which we could prove Isat (x, net (x]) 2 0
(satisfaction) M. 9sai (x, (x)) < (violation) or neither I. respectively. By integrating probability density fx in (c) (darker
means higher density) over the green rectangles M. we obtain a lower bound on p. Similarly, can integrate over the orange rectangles to construct an upper bound on p. Refining the input splitting from (a) (b) tightens the bounds on p.
work verification for refining the input splitting.
Algorithm PROBBOUNDS
Algorithm describes the algorithm. The centrepiece of PV is the procedure PROBBOUNDS for computing bounds (()) < p; < (t) on a probability from Equa-
Require: Probability
Px Pxlosu net(x)) 2 0].
Batch
Size N
1: branches +- (X} g(0) 0, (0) t
(t), tion (3). Given e! S Ps S u, we apply bound propaga- (P1....,PPP) Po),
3: for t N do
tion technique to prove disprove
4: batch + SELECT N)
described in Section 3.2. If this analysis is inconclus-
5: (y, COMPUTBBONNSSSS ne)(.)), batch)
ive, PROBBOUNDS refines ((t) (1()) to obtain e((+1)) uf (++1)
6: (keep, x((1) x x + PRUNEE(atch,, y,
with ee0) < ((+))) Pi S ui (1+1) < uq (1) We again ap- ply bound propagation to (Pt.... this time us- ing o! e((+1) .u! ((+1)) If the result remains inconclusive, we iterate refining the bounds on each p. until obtain con- clusive result. PV applies PROBBOUNDE for each p; in par- allel, making use of several CPU cores several GPUs. Our main contribution is the PROB PROBBOUNDS algorithm for com- puting converging sequence of lower and upper bounds on ps.
7: g(t) + ((--1) + xPx
(1)) x- (1-1) -Ixx [x(()]
yield (e(1), u(1)) // Report new bounds PV
SPLIT(keep) I1: branches + (branches \ batch) U Unew
10:
12: end for
4.1. Bounding Probabilities
Our PROBBOUNDS algorithm for deriving and refining bounds probability is described in detail in Algorithm and illustrated in Figure 1. PROBBOUNDS is massively parallel input-splitting branch and bound algorithm (Bunel et al., 2020; Wang et al., 2018; Xu et al., 2020) that lever- ages a bound propagation algorithm for non-probabilistic neural network verification (COMPUTEBOUNDSS) Since we only consider single probability this section, we denote this probability
Algorithm PV
Require: Probabilistic Verification Problem as in Equa- tion (3), Batch Size N
1: for E [u] do // Launch v parallel instances
2: PB; <- Launch PROBBOUNDS(p::
3: end for
4: for E do
5: for E [u] do Gather 6. = (e(() from PB;
P [9 (x, net(x)) 2 0).
if g()) then return Satisfied ... (00)
(t))) <- COMPUTEBOUNDS/ (fsa (().....
6:
PROBBOUNDS receives and a batch size N E N input.
7:
8: if (1)
< 0 then return Violated
The algorithm iteratively computes g(t), (t) E [0. 1]. such
that ((t) < g(r') < & (t')) < u(t), Yt, E N, 2 f. The
9:
end for
following sections describe each step of PROBBOUNDS in detail.
5

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Initialisation. Initially, we consider single branch encom- passing net's is entire input space X' As in Section 3, we assume X' to be (potentially unbounded) hyperrectangle. We use the trivial bounds (00) = 0 < Σ 1= = (( as initial bounds on p.
one-hot encoded categorical variable A, we jointly split all indicators of A such that A takes the value encoded in d in one branch and does not take on this value in the other branch. Appendix B.1 defines these splitting rules formally.
Split Selection. We present three heuristics for selecting the dimension d for splitting. We generally select dimen- sions encoding unbounded variables first in order to ob- tain bounded branches, since COMPUTEBOUNDS usually computes vacuous bounds for unbounded branches. For bounded variables, the well-known LONGESTEDGE heur- istic (Bunel et al.. 2020) selects the dimension with the largest edge length X - X,z- Alternatively, we use a vari- ant of the BABSB heuristic (Bunel et al., 2020). BABSB estimates the improvement in bounds that splitting dimen- sion d yields by using a yet less expensive technique than COMPUTEBOUNDS. Our variant of BABSB uses INTER- VALARITHMETIC, assuming that we use CROWN for COMPUTEBOUNDS Appendix B.2 describes our BABSB variant in detail. While LONGESTEDGE is more theoret- ically accessible, BABSB is practically advantageous, as discussed in Appendix G. Combining the advantages of both approaches, we introduce MABSB-LONGESTEDGIE This heuristic alternates using BA BABSB and LONGESTEDGE, using LONGESTEDGE for every k-th split. If we visualise branches and their descendants from splitting in branching tree, the splits at level k, 2k, 3k.... use LONGESTEDGE while the splits at all other levels use BABSB
Selecting Branches. First, we select a batch of N E N branches. In the spirit of Xu al. (2021), we leverage the data parallelism of modern CPUs and GPUs to process sev- eral branches at once. In iteration t = 1, the batch only contains the branch X. Which branches we select determ- ines how fast we obtain tight bounds on p. We propose the SELECTPROB heuristic for selecting branches. Inspired by FAIRSQUARE (Albarghouthi et al., 2017). SELECTPROB selects the N branches B, with the largest Px [B.]. This heuristic is motivated by the observation that pruning these branches would lead to the largest improvement of (()) u())
Pruning. The next step is to prune those branches B3 E batch, for which we can determine that y/ = Isat (x, net net(x)) 2 0 is either certainly satisfied or certainly violated. For this, we first compute y S Isat (.ett())))))))) net())) < y
for the entire batch using a bound propagation algorithm for neural networks, such as CROWN (Zhang et al., 2018). If Y 2 0 (y3 2 0 is certainly satisfied) or y, < 0 (yj 2 0 is certainly violated), we can prune B,, meaning that we remove it from branches. We collect the branches with y, 2 O in the set x!') and the branches with y, 0 in the set x²(t) where E N is the current iteration. viol
Updating Bounds. Let P!00) = U and viol x1(()
4.2. Input Spaces and Input Distributions
U piol. where t E N is the current iteration. Then, g(() Pxx (x((() S p. Similarly, g(0) = Px ( (+) [3I9sat(* net (x)) < <0] = 1 p. Therefore,
This section discusses the concrete requirements that the in- put space X' and the input distributions 22))) in Equation (3) need to satisfy for applying PV. Appendix A.5 discusses how some of these requirements can be mitigated, for ex- ample, for using polytopes as input spaces.
S
A1))
w(t)) 2 p. Practically, we only have to maintain the current bounds g(t) and (1()) instead of the sets x(()) and (2(1)
PV requires X C IR" to be hyperrectangle, which can be unbounded. The dimensions of X' may encode discrete random variables. For each probability distribution P xx we require a terminating algorithm that computes the ex- act probability of a hyperrectangle. This requirement is satisfied by a large class of probability distributions, in- cluding discrete distributions with closed-form probability mass function and univariate continuous distributions with a closed-fon form cumulative density function, as well as Mixture Models and probabilistic graphical models (Bishop, 2007), such as Bayesian Networks, of such distributions.
Because Eele) and viol are union of disjoint hyperrect- viot] is feas- ible for large class of probability distributions, including most univariate distributions, Mixture Models, and Bayesian Networks. The precise class of supported probability dis- tributions is discussed in Section 4.2. While we do not account for floating point errors in this paper, our approach can readily be extended to this end.
angles, exactly computing xxx [2 and Tp (2()))
Splitting. Splitting refines a branch B = =x, x by select- ing a dimension d E [n] to split. We split based on the type of variable that is encoded in d. For bounded con- tinuous variables, we split by bisecting |x. x] along d. For unbounded variables, at max(2x,,) 1) if - X2 < x = x., and at min(2x... a. -1) -o = X < x For integer variables, we additionally round the split points to the next smaller, respectively, larger integer. For dimensions containing a binary indicator of a
5. Theoretical Analysis
split at zero if Xx = X, co,
In this section, we prove that PV is sound probabilistic verification algorithm when instantiated with a suitable COMPUTEBOUNDS procedure. We also prove that PV is complete under mild assumptions on the probabilistic
6

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
verification problem when instantiated with suitable SPLIT, COMPUTHBOUNDS, and SELECT procedures. Soundness and completeness are defined in Definition 3.2. As in Sec- tion 4.1, we omit indices and superscripts when considering only a single probability p = Px 19sar (x, net(x)) 2 0j. We defer all proofs to Appendix C. Our first result concerns the soundness of PROBBOUNDS.
Unfortunately, our completeness result does not apply to the BABSB heuristic, which provides the best empirical performance when used in PV. However, our result applies to LONBES--ONGES which yields comparable performance as BABSB, as we show in Appendix G.
6. Experiments
Theorem 5.1 (Sound Bounds), Let N E N be a batch size and assume COMPUTEBOUNDS produces be the iterates of PRORBOUNDS(Px (x, net (x)) 2 N). It holds that g(t) < 10 (x, nx)( 2 0] S u for all E N. Corollary 5.2 (Soundness). PV is sound when using COM- PUTEBOUNDS procedures that compute valid bounds.
We apply our algorithms to verify the demographic parity faimess notion, count the number of safety violations of neural network controllers in safety-critical systems, and quantify the robustness of a neural network. Table 2 gives an overview of our benchmarks. All verification problems are defined formally in Appendix A. For all benchmarks, PROBBOUNDS use the SELECTPROB and BABSB heur- istics and CROWN (Zhang et al., 2018) for COMPUTE- BOUNDS, while PV uses INTERVALARITHMETIC
valid bounds.
Let ((()),
Our remaining theoretical results are concerned with the completeness of PV. Concretely, we prove that PV instantiated with SELECTPROB, LONgESTEDGE or and INTERVALARITTMMTTIC or CROWN is complete under a mildly restrictive condition on Equation (3). Appendix C.2 defines a more general class of pruning and splitting heuristics for which PV is complete.
As our results show, PV (Algorithm 1) outpaces the probab- ilistic verification algorithms FAIRSQUARE (Albarghouthi et al., 2017) and SPACESCANNER (Converse et al., 2020). Additionally, we show that PROBBOUNDS (Algorithm 2) compares favourably to the PROVE (Marzari et al., 2023b), S (Marzari et al., 2024), and PREIMGAP- PROX (Zhang et al., 2024) algorithms for #DNN verifica- tion (Marzari et al., 2023a), which corresponds to probabil- istic verification with uniformly distributed inputs.
BABSB-LONGESTEDGER
Assumption 5.3. Let v. SSa Isat and (() be as in Equa- tion (3). Assume Ssat (PI..... .P)) * O and Vi E [v]
(i)
P P Saat (x()), net (x)) = 0] = 0.
Assumption 5.3 is only mildly restrictive, since for every verification problem that does not satisfy Assumption 5.3, there are similar problems that satisfy the assumption. Consider the case that (Pi.... case, Equation (3) does not satisfy Assumption 5.3. How- ever, a slightly stronger verification problem concerned with I' (Pi,..... ...,,,...,...................... .P)) = Ssaa (pI...... PPa) E for an arbit- rarily small æ >> 0 satisfies Assumption 5.3. Appendix C.2 discusses Assumption 5.3 in more detail.
While no code is publicly available for SPACESCANNER, running PROVE_SLR is very computationally expensive. To enable a faithful comparison, we run our experiments on less powerful hardware (HW1) compared to the hardware used by Converse et al. (2020) and Marzari et al. (2023b) and compare the runtime of our algorithms to the runtimes reported by these authors. All other results reported in this paper were obtained on HW1, including the results for FAIRSQUARE, e E,ROOEE, and PREIMGAPPROX.
= 0. In this
To prove the completeness of PV, we first establish that PROBBOUNDS produces sequence of lower and upper bounds that converge towards each other.
To test the limits of PV, we introduce a new, challenging benchmark: MiniACSIncome is based on the ACSIncome dataset (Ding et al., 2021). It consists of datasets of vary- ing input dimensionality, probability distributions for these datasets, and neural networks trained on these datasets. Be- ing based on real-world US census data, MiniACSIncome offers more complex input distributions with higher input dimensionality than existing probabilistic verification bench- marks. PV solves seven of eight instances in MiniACS- Income within an hour.
Lemma 5.4 (Converging Probability Bounds). Let N E N be batch size. Ler {(e(), u( SEN be the iterates of PROBBOUNDS([P I9saa (x, net 2 0j, .V) instantiated with SELECTPROB, LONGESTEDGE or LABSB-LONGESTEDGER and INTERVALARITHHETTI or CROWN. Assume P (x, (x, nx) 0] 0 as in Assumption 5.3. Then,
Hardware and Implementation. We implement PV in Python, leveraging PyTorch (Paszke et al., 2019) and aut LuiPAA (Xu et al., 2020). We run all experiments on Ubuntu 22.04 desktop with an Intel i7-4820K CPU, 32 GB of memory, and no GPU (HW1). Appendix F.I com- pares our hardware the hardware used by Converse et al. (2020) and Marzari et al. (2023b).
lim ((t) >iim (1()= =P [9sat (x, net (x)) ))=)))))) 2 0). 1-000
t-000
Theorem 5.5 (Completeness). When instantiated with PROBBOUNDS as in Lemina 5.4 and INTERVALARITH- METIC or CROWN for COMPUTEBOUNDS, PV is com- plete for verification problems satisfying Assumption 5.3.
7

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Table 2. Our henchmarks, Network size is the size of the neural network given as #layers x layer size.
Benchmark
Input Dimension
Input Distributions
Network Size
Source
independent
FairSquare
2-3
1x1, 1x2
(Albarghouthi et al., 2017)
2 Bayesian Networks
ACAS Xu
uniform
6x50
(Katz al., 2017b)
VCAS
4
uniform
1x21
(Zhang al., 2024)
1x 10-10000
MiniACSIncome
1-8
Bayesian Network
Own
1x 10 - 10x 10
TO
collisions. We reproduce the ACAS Xu safety experiments of Marzari al. (2023b), the ACAS Xu robustness experi- ments of Converse et al. (2020), and the VCAS correctness experiment of Zhang et al. (2024).
FAIRSQUARE"
PV (Ours)
Runtime (s)
10a
10a
ACAS Xu Safety. In this experiment, we seek to quantify the number of violations (violation rate) of sev- eral ACAS Xu networks (Katz et al., 2017b). This cor- responds to computing bounds on Equation (2) under a uniform distribution of x. We compare PROB BOUNDS to the PROVE SLR and E-ROVEE algorithms for #DNN veri- fication. PROVE.SI E_RR computes the violation rate exactly, while e- PROVE computes an upper bound on the violation rate that is sound with a certain predefined probability. In contrast, PROBBOUNDS provides sound bounds on the viol- ation rate at any time during its execution.
10
4
8
10
12
14
16
18
# Solved Instances
Figure 2. FairSquare benchmark results.
The timeout (TO) is
15min. "Alharghouthi et al. (2017)
6.1. FairSquare Benchmark
Table 3 compares PROB
PROVE_SI.R and PROVE for the ACAS Xu networks investigated by Marzari et al. (2023b). For all three networks, tighten the bounds to a margin of less than 0.7% within one hour, while PROVE. SLR requires at least four hours to com- pute the exact violation rate. In comparison to e-PROVE, PROBBOUNDS produces tighter sound bounds within 10 seconds in two of three cases, while E-PROVE requires at least 57 seconds to derive probably sound upper bound for these cases. The extended comparison in Appendix F.3 reveals that in 12 from a total of 36 cases, PROBBOUNDS computes a tighter sound bound faster than E-RROVE com- putes a probably sound upper bound.
Albarghouthi et al. (2017) evaluate their FAIRSQUARE al- gorithm on application derived from the Adult data- set (Adult, 1996). In particular, they verify whether three small neural networks satisfy two fairness notions with re- spect to a person's 's sex under three different distributions of the network input: a distribution of entirely independent uni- variate variables and two Bayesian Networks. Appendix F.2 describes the FairSquare benchmark in more detail.
can
Figure 2 compares the runtimes of PV and FAIRSQUARE on the FairSquare benchmark. PV significantly outperforms FQIRR In particular, PV solves four more instances than FAIRSQUARE within the timeout of 15 minutes. For the instances that both tools solve, the median runtime of PV is 4s (mean: 5s, max: 17s) compared 44s for FAIR- SQUARE (mean: 109s, max: 657s). Appendix F.2 contains the detailed results of this experiment.
ACAS Xu Robustness. We replicate the experiments of Converse et al. (2020) who apply SPACESCANNER quantify the robustness of ACAS Xu network N1,1 (Katz et al., 2017b) under adversarial perturbations. Overall, the experiment consists of 125 verification problems that con- cern the probability of obtaining a particular class for uni- formly distributed perturbed inputs close to one of 25 refer- ence input points.
6.2. Aireraft Collision Avoidance
The ACAS Xu networks (Katz al., 2017b) are suite of 45 networks, together forming collision avoidance system for crewless aircraft. Each ACAS Xu network predicts a horizontal turning direction to avoid collision with another aircraft. VCAS (Julian & Kochenderfer, 2019) is a similar system that predicts vertical steering directions for avoiding
The mean runtime of PROBBOUNDS for these 125 instances is 22 seconds (median: 6s, maximum: 213s). In contrast, Converse et al. (2020) report a mean runtime of 33 minutes per instance for SPACESCANNER while running their exper-
8

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Table Comparison of PROBBOUNDS, PROVE_SI.R, and E-PROVE. We PROBBouNDS with different time budgets (10s, Im, Ih) and report the lower and upper bounds (e, u) computed within this time budget. In contrast, PROVE.SLR computes the exact probabilities (VR), and E-PROVE computes 99.9% confidence (confid.) upper bound. The probabilities and probability bounds are given percentages. The runtimes (Rt) of PROVE. ELR are taken from Marzari et al. (2023b).
PROBBOUNDS (Ours)
PROVE.SLR
8- E-PROVE
10s
Im
1h
Exact
99.9% confid.
net
L, u
a
E, u
VR
Rt
Rt
N4.3
0.17%, 2.92%
0.61%, 2.27%
1.12%, 1.75%
1.43%
8h 46m
3.61%
65s
N4.0
0.00%, 3.36%
1.55% 0.00%,
0.08%, 0.29%
0.15%
12h 21m
0.73%
20s
N5.8
0.89%, 4.16%
1.55%, 3.10%
1.97%, 2.57%
2.20%
4h 35m
4.52%
57s
Marzari et al. (2023b)
Marzari et al. (2024)
iments superior hardware. Appendix F.4 contains more details on this experiment.
TO
Runtime (min)
50
Enumerate
40
PV (Ours)
VCAS Correctness. Zhang et al. (2024) study whether a VCAS network correctly predicts to maintain course in a scenario where there is no risk of collision. Concretely, they verify whether the VCAS network provides the correct
30
20
10
output at least 90% of the time. PV is able to prove this within 0.13s. In contrast, PREIMGAPPROX requires 16.42s for computing an unsound empirical lower bound on the probability of obtaining correct outputs.
1
2
3
7
8
# Input Variables
Figure 3. MiniACSIncome results. The timeout (TO) is one hour.
6.3. MiniACSIncome
a baseline approach for verifying the demographic parity of a MiniACSIncome network is to enumerate all values in the input space. Figure 3 displays the runtime of PV and the baseline enumeration approach for shallow 10-neuron neural networks with increasing input size. While enumer- ation is faster than PV when the network can be evaluated for all discrete values in one batch, enumeration falls behind PV as soon as this becomes infeasible. PV can solve Mini- ACSIncome for up to seven input variables in less than 30 minutes, only exceeding the timeout of one hour for eight input variables. While we only consider a small network here, the runtime of PV is largely unaffected by network size this benchmark. This unexpected result can be at- tributed to both large and small networks learning similar decision boundaries for MiniACSIncome. Appendix F.5.5 discusses this result in more detail.
To test the limits of PV, we introduce the MiniACSIncome benchmark. MiniACSIncome is derived from the ACSIn- come dataset (Ding et al., 2021), a replacement of the Adult dataset (Adult, 1996) that is better suited for fair machine learning research. The task is to predict whether a person's is yearly income exceeds $50000 using features such as the person's age, sex, and education. Our benchmark provides probabilistic verification problems of various degrees of dif- ficulty. We apply PV to MiniACSIncome and compare it to a baseline approach for solving MiniACSIncome.
Benchmark. To create probabilistic verification problems of increasing difficulty, we consider an increasing number of input variables from ACSIncome. The smallest instance, MiniACSIncome-11. only contains the binary 'SEX' variable. In contrast, the largest instance, MiniACSIncoom--8, con- tains 'SEX' and seven more variables from ACSIncome, including age, education, and working hours per week. Our benchmark's 's task is to verify the demographic parity of neural networks with varying input dimension under Bayesian Network as input distribution. These Bayesian Networks provide complex multi-modal input distributions, as they fit the real-word world US census data in ACSIncome. Appendix F.5 describes MiniACSIncome in detail.
7. Conclusion
Our PV algorithm for the probabilistic verification of neural networks significantly outpaces existing algorithms for prob- abilistic verification. We achieve this speedup by applying a massively parallel branch and bound algorithm based on bound propagation algorithms for neural networks. Our MiniACSIncome benchmark provides challenging testhed for future probabilistic verification algorithms.
Results. Since all variables in MiniACSIncome are discrete,

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Impact Statement
Bastani, O., Zhang, X., and Solar-Lezama, A. Probabilistic
verification of fairnsss properties via concentration. Proc. ACM Program. Lang., 3000SSLA 2019, URL http::://oo..org/10.1111
This work concerned with providing mathematical guar- antees on the output distribution of neural network given distribution of the inputs. Since mathematical guarantees enhance the transparency of neural networks and facilit- ate their faithful auditing, we anticipate that our work will have a predominantly positive societal impact. However, obtaining an input distribution for probabilistic verification requires significant domain expertise and careful design. For example, a poorly designed input distribution may lead to certifying an unfair classifier as fair. Therefore, verifica- tion results are only meaningful if the concrete probabilistic verification problem that was solved is reported and made available alongside the verification result, including the in- put distribution. Ideally, verification should be conducted by a separate certification body for critical applications.
Batten, B., Hosseini, M., and Lomuscio, A. Tight veri- fication of probabilistic robustness in Bayesian neural networks. In AISTATS, volume 238 of Proceedings of Machine Learning Research, pp. 4906-4914. PMLR, 2024. URI. h/tp:///r/eedeeeee http:httepp//rroeeeeddeee 338/patten24a.hte.
Bauer-Marquart, F., Boetius, D., Leue, S., and Schilling, C. SpecRepair: Counter-example guided safety re- pair of deep neural networks. In SPIN, volume 13255 of Lecture Notes in Computer Science, pp. 79-96. Springer, 2022. URL attpss://oi.oon /10.1007/978- 3 3--03-115077111
References
Belle, V., Passerini, A., and den Broeck, G. V. Probabilistic inference in hybrid domains by weighted model integra- tion. In IJCAI, pp. 2770-2776. AAAI Press, 2015, URL / http:///jjaa..ooo/Abarraat//////
Adams, S., Patane, A., Lahijanian, M., and Laurenti, L.
BNN-DP: Robustness certification of Bayesian neural networks via dynamic programming. In ICML, volume 202 of Proceedings of Machine Learning Research, pp- 133-151. PMLR, 2023. URL https: https::/prroeeeeeeeeeeee /proceedon gs.mlr.press/ /vtps/ss/vv////////// http///admmm2aa.ttt.. hm..
Berrada, L., Dathathri, S., Dvijotham, K., Stanforth, R., Bunel, R., Uesato, J., Gowal, S., and Kumar, M. P. Make sure you're unsure: A framework for verifying probabil- istic specifications. In NeurlPS, pp. 11136-11147, 2021. URL https::/prreeecinng...oooopppppp er/200//haaa//chhoooff2277222222 4 4752b644b-Abttractttttt
Adult. The Adult dataset. UCI Machine Learning Repos- itory, 1996. URL
/ml/datasets/Aauul//
Akiba, T. Sano, S., Yanase, T., Ohta, T., and Koyama, M. Optuna: A next-generation hyperparameter optimization framework. In KDD, pp.
Bibi, A., Alfadly, M., and Ghanem, Analytic expres- sions for probabilistic moments of PL-DNN with Gaus- sian input. In CVPR, pp. 9099-9107. Computer Vis- ion Foundation / IEEE Computer Society, 2018. URL
ACM, 2019. URL https://doi.orr/// wtt../orro11.111.111 httpp://ooa.orr//..../22222220.0
Albarghouthi, A., D' Antoni, L., Drews, S., and Nori, A. V. FairSquare: Probabilistic verification of program faimess. Proc. ACM Program. Lang., (0005LA)):0:1800:00 2017. URL URL.htp:::/bbb.or///1111/////3/3
Bishop, C. M. Pattern recognition and machine learn- ing. Information science and statistics. Springer, 5 edi- tion, 2007. URL https://nnkspringggee
Bak, S., Tran, H., Hobbs, K., and Johnson, T. T. Improved geometric path enumeration for verify- ing ReLU neural networks. In CAV (I), volume 12224 of Lecture Notes in Computer Science, pp. 66-96. Springer, 2020. URL bttps://doi.on /10.1007/978 3 11-0030-3300 53288-8288888 8.4.
Biswas, S. and Rajan, H. Fairify: Fairness verifica- tion of neural networks. In ICSE, pp. 1546-1558. IEEE, 2023. htt.ttss://d..ogggggeeee E48619.2023.00134
Baluta, T., Shen, S., Shinde, S., Meel, K. S., and Saxena, P. Quantitative verification of neural net- works and its security applications. In CCS, pp. 1249-1264, ACM, 2019. URL https://doi.org /10.14553319535.3554
Borca-Tasciue, G., Guo, X., Bak, S., and Skiena, S. Prov- able fairness for neural network models using formal verification. In EWAF, volume 3442 of CEUR Work- shop Proceedings. CEUR-WS.org, 2023. URL https: diceur-ws.orr//ool..
Barocas, S., Hardt, M., and Narayanan, A. Fairness and Machine Learning. MIT Press, 2023. URL https: //fat rml book.org/
Brix, C., Bak, S., Liu, C., and Johnson, T. T. The fourth international verification of neural networks com- petition (VNN-COMP 2023): Summary and results.
10

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
CoRR, abs/2312.16760, 2023. URL https://doi.o
Feldman, M., Friedler, A., Moeller, J., Scheidegger, C., and Venkatasubramaniinn, S. Certifying and removing dis- parate impact. In KDD, pp. 259-268. ACM, 2015, URL https://oo..rrr//111444
Brix, C., Bak, S., Johnson, T., and Wu, H. The fifth international verification of neural networks com- petition (VNN-COMP 2024): Summary and results. CoRR, abs/2412.19985, 2024. URL https:
Galhotra, S., Brun, Y., and Mcliou, A. Faireess testing: testing software for discrimination. In ESEC/SIGSOFT FSE, pp. 498 510. ACM, 2017. URL https://doi. Tg/10.11455 00055/3116627731622222
Bunel, R., Lu, J., Turkaslan, L,, Torr, P. H. S., Kohli, P., and Kumar, M. Branch and bound for piecewise linear neural network verification. Mach. Learn. Res., 21: 42:1-42:39, 2020. URL http:// http::///n...rg/////. s/v21/19 11t///19-466.ht...
Hendrycks, D., Zhao, K., Basart, S., Steinhardt, J., and Song, D. Natural adversarial examples. In CVPR, pp. 15262-15271. Computer Vision Foundation / IEEE, 2021. URL https: /ttp://///ttt///ooooo///10111110
Cardelli, I.., Kwiatkowska, M., Laurenti, I.., Paoletti, N., Patane, A., and Wicker, M. Statistical guarantees for the robustness of Bayesian neural networks. In IJCAI, pp- 5693-5700. ijcai.org, 2019a. URL https://doi.onr
Hosseini, H., Xiao, B., and Poovendran, Google's cloud vision API is not robust to noise. In ICMLA, pp. 101-105, IEEE, 2017. URL ht htttps://doi.org/1..111111 1A.2017.0-172.
Cardelli, L., Kwiatkowska, M., Laurenti, L., and Patane, A. Robustness guarantees for Bayesian inference with Gaussian processes. In AAAI, pp. 7759-7768. AAAI Press, 2019b. URL https: https:://bi.oog///.0/// http///b...rgg1.110999//// AAI.V33I DAI.V33IC1.33 11..3111111177511
Julian, K. D. and Kochenderfer, M. Guaranteeing safety for neural network-based aircraft collision avoidance systems. CoRR, abs/1912.07084, 2019. URL http:
/ ///arii.orr/ab//1112.000
Katz, G., Barrett, W., Dill, D. L.. Julian, K., and Kochenderfer, M. J. Towards proving the adversarial robustness of deep neural networks. In FVAV@iFM, volume 257 of EPTCS, pp. 19-26, 2017a. URL https: //doi.org/10.4200 /tw.44400/0PP255.....
Cheng, C., Nührenberg, G., and Ruess, H. Maximum resilience of artificial neural networks. In ATVA, volume 10482 of Lecture Notes in Computer Science, 251-268. Springer, 2017. URL :/ttt::://ddorrgggg 110.1007/978-3-333 68167-2.18.
Katz, G., Barrett, C. W., Dill, D. L., Julian, K. D., and Kochenderfer, M. J. Reluplex: An efficient SMT solver for verifying deep neural networks. In CAV (I), volume 10426 of Lecture Notes in Computer Science, pp. 97-117. 9p-nee, 2017b. URL htwps::tt///ee.. htt.httpss://oo..rrr /10.1007/970 3- 319 63387-9.5.
Converse, H., Filieri, A., Gopinath, D., and Pasareanu, C. S. Probabilistic symbolic analysis of neural networks. In ISSRE, pp. 148-159. IEEE, 2020. URL stttps://dot .org/10.1100 0ttp::01110//1555000000.2..
Ding, F., Hardt, M., Miller, J., and Schmidt, L. Re- tiring Adult: New datasets for fair machine learn- ing. In NeurlPS, pp. 6478-6490, 2021. URL https://proeedinngsuurss..../// 7700//aah//2254444663227777 450059 350059-Abstract.htmll
Kim, B. H., Wang, J., and Wang, C. FairQuant: Certi- fying and quantifying faimess of deep neural networks. CoRR, abs/2409.032200 2024. URL https: //doi.o
| 100.0446550/2X1122440....2 rq/10.48550
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. In ICLR, 2015. URL https: //opi://doiiorg
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. S. Fairness through awareness. In ITCS,
pp. 214-226. ACM, 2012. URL https://doi.org /10.1145/2090236.200
Land, A. H. and Doig, G. An automatic method for solving discrete programming problems. In 50 Years of Integer Programming 1958-2008 From the Early Years to the State-of-the-Art, pp. 105- 132. Springer, 2010. URL https: https://doi.org
Ebrahimi, J., Rao, A., Lowd, D., and Dou, D. Hot- Flip: White-box adversarial examples for text classific- ation. In ACL (2), pp. 31-36. Association for Compu- tational Linguistics, 2018. URL https: attps://doi.org /10.18553/v1/p18-2 2006.
/10.1007/978-354444 000---3--0---69---10 lished in Econometrica 28 (1960).
First pub-

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Marzari, L.., Corsi, D., Cicalese, F., and Farinelli, A. The #DNN-verrffiattion problem: Counting unsafe inputs for deep neural networks. In IJCAI, pp. 217-224, ijcai.org, 2023a. URL https://doi.org/10..e I IJCAI 20223/25.
Pulina, L. and Tacchella, A. An abstraction-refinemem
approach to verification of artificial neural networks. In CAV, volume 6174 of Lecture Notes in Computer Science, pp. 243-257. Springer, 2010. URL https: /tttp:::///.oorrpp doi.org 01 00.1007/99 97707/997-3111 0222--44-111-22-
Marzari, I.., Roncolato, G., and Farinelli, A. Scaling #DNN-verification tools with efficient bound propagation and parallel computing. In AIRO@AI AI*IA, volume 3686 of CEUR Workshop Proceedings, pp. 92-106. CEUR- WS.orr, 2023b. URL http:::/cceurwws.rgg.. 36866/pppr22.pp
Ruan, W., Huang, X., and Kwiatkowska, M. Reachability analysis of deep neural networks with provable guaran- tees. IJCAI, pp. 2651-2659, ijcai.org, 2018. URL /ttt:://bol.orr/102449/////33/13
Ruoss, A., Balunovic, M., Fischer, M., and Vechev, M. T. Learning certified individually fair representations. In NeurIPS, 2020. URL https: https::/prrcceeddggg..omm r rippccc//pperr/022///////555444 htt.:/7111.1.2aaattttrrttttttt
Marzari, L., Corsi, D., Marchesini, E., Farinelli, A., and Cicalese, F. Enumerating safe regions in deep neural networks with provable probabilistic guarantees. In AAAI, pp. 21387-21394. AAAI Press, 2024. URL https: ///dii.ozg/1.166000 0tt.:1/099/AAA..8111...00.0
Singh, G., Gehr, T.. Püschel, M., and Vechev, M. T. An
abstract domain for certifying neural networks. Proc. ACM Program. Lang,, 3(POPL)44:1111:300 2019, URL https: /tt.b//..rrr/1111////9/99/0
Mohammadi, K., Sivaraman, A., and Farnadi, G. FETA: Faimess enforced verifying, training, and predicting algorithms for neural networks. In EAAMO, pp- 23:1-23:1 ACM, 2023. URL https://abi.org /10.115/336176943322
Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow. I. J., and Fergus, R. Intriguing properties of neural networks. In ICLR (Poster), 2014. URL http s: s:// ht///doioorg/////// http://....0550//./11111220
Moore, R. E., Kearfott, R. B., and Cloud, M. J. Introduction to Interval Analysis. SIAM, 2009.
ISBN 978 018-0-0-8777-66-666 URL https://dbi.org /10.1137/1.97803997777
Tjeng, V., Xiao, K. Y., and Tedrake, R. Evaluating robust- ness of neural networks with mixed integer programming. In ICLR (Poster). OpenReview.net, 2019. URL https: //openrevis ew.net / forum? d= I Rqtm.
Morettin, P., Passerini, A., and Sebastiani, R. A unified framework for probabilistic verification of Al systems via weighted model integration. CoRR, abs/2402.04892, 2024. URL https:/ http:///o/ol.or/0005055550 22402.4892.
Tran, H., Bak, S., Xiang, W., and Johnson, T. T. Verification deep convolutional neural networks using ImageStars. In CAV (I), volume 12224 of Lecture Notes in Computer Science, pp. 18-42. Springer, 2020a. URL htth:t//: oi.org/10.1007
Morrison, D. R., Jacobson, S. H., Sauppe, J. J., and Sewell, E. C. Branch-and aud-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discret. Optim., 19:79-102, 2016. URL attps://doi.org http:///.ddiopp.211155.
Tran, H., Yang. X., Lopez, D. M., Musau, P., Nguyen, L. V., Xiang, W., Bak, S., and Johnson, T. T. NNV: The neural network verification tool for deep neural networks and learning-enabled cyber-physical systems. In CAV (1), volume 12224 of Lecture Notes in Computer Science, pp. 3-17. Springer, 2020b. URL https://doi.orr /10.1007/978-1 000-7-8--0000088---111
Neal, R. M. Bayesian learning for neural networks, volume 118 of Lecture Notes Statistics. Springer Science & Business Media, 1996. URL http::ttttii.ooog////s ps: ps::/6cl.org//001000//
Paszke, A., Gross, S., Massa, F,, Lerer, A., Bradbury.
Tran, H., Choi, S., Okamoto, H., Hoxha, B., Fainekos, G., and Prokhorov, D. V. Quantitative verification for neural networks using ProbStars. In HSCC, pp. 4:1-4:12 ACM, 2023. URL https://doi.org /101145/357587035577
J. Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Köpf, A., Yang, E., Vetito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L,, Bai, J., and Chintala, S. PyTorch: An imperative style, pigf-peeformance deep learning library. In NeurlPS, pp. 8024-8035, 2019.
Urban, C., Christakis, M., Wüstholz, V., and Zhang, F. Per- fectly parallel faimess certification of neural networks. Proc. ACM Program. Lang., 400P0000 2020. URL ULLL:tttss///oooooo/////11111333
URL as/220/9/aaa///aac22tteeeees2s22 7012727740-bbstrect..t
12

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Wang, S., Pei, K., Whitehouse, J., Yang. J., and Jana, S. Formal security analysis of neural networks using symbolic intervals. In USENIX Security Symposium, pp. 1599-1614, USENIX Association, 2018. URL https: http::/wwww..eeee..occcooooooooe wwwer//ccccceeceeeeee/eee / / shiqi.
Zhang, H., Weng. T., Chen, P., Hsieh, C., and Daniel, L. Efficient neural network robustness certification with general activation functions. In NeurIPS, pp. 4944-4953, 2018. URL .ce cccpppppe//001a/aaaa///088808000 1rtGell19550aee0-bbttaaeeee
Weng. T., Zhang, H., Chen, H., Song, Z., Hsieh, C., Daniel, L., B.Binngg D. S., and Dhillon, I. Towards fast computa- tion of certified robustness for ReLU networks. In ICML, volume 80 of Proceedings of Machine Learning Research, pp. 5273-5822. PMLR, 2018. URL htt.:://proceet Angg.mlr.prees / wa......a.....m.. 1a.hmml..
Zhang. H., Chen, H.. Xiao, C., Gowal, S., Stanforth, R., Li, B., Boning, D. S., and Hsieh, C. Towards stable and efficient training of verifiably robust neural networks. In ICLR. OpenReview.net, 2020. URL https: httpss///pp eview.net wtt.rrrmmmmiiiiokkkkuoo------aea
Zhang, X., Wang, B., and Kwiatkowska, M. Provable preim- age under-approximation for neural networks. In TACAS, volume 14572 of Lecture Notes in Computer Science, pp. 3-23. Springer, 2024. URL httpps://doi.e /10.1007 00100/99788--01-725---2211-
Weng, T., Chen, P., Nguyen, L. M., Squillante, M. S., Boopathy, A., Oscledets, I. V., and Daniel, L. PROVEN: Verifying robustness of neural networks with a probab- ilistic approach. In ICML, volume 97 of Proceedings of Machine Learning Research, pp. 6727-6736. PMLR, 2019. URL http::////.. http///coceedngg.... ml r.press/v 97/wenqq 9a.html.
Zhou, D., Brix, C., Hanasusanto, G. A., and Zhang, H. Scal- able neural network verification with branch-and -ound inferred cutting planes. In NeurlPS, 2024, URL https: h //openreview.net/ fort://rmmmm weeprummmi-dwfii Fd= Wwy.hh12pyft.
Wicker, M., Laurenti, I.., Patane, A., and Kwiatkowska, M. Probabilistic safety for Bayesian neural net- works. In UAI, volume 124 of Proceedings of Ma- chine Learning Research, pp. 1198-1207, AUAI Press, 2020. URL http::/proceed 124 124/wicker20a.htm..
r.press/v
Wicker, M., Patane, A., Laurenti, I.., and K Kwiatkowska, M. Adversarial robustness certification for Bayesian neural networks. In FM, volume 14933 Lecture Notes in Com- puter Science, pp. 3-28. Springer, 2024. URL https: 000--11--00 71162-6.1.
//601..://10.1007/9111
Wong, E. and Kolter, J. Z. Provable defenses against adversarial examples via the convex outer adversarial polytope. In ICML, volume 80 of Proceedings of Machine Learning Research, pp. 5283-5292. PMLR, 2018. URL http::/ts// httt:::/pproceeinggee 80 80/won. 10/wongl8a.html.
r.press/v
Xu, K.. Shi, Z., Zhang, H., Wang. Y., Chang, K., Huang, M., Kailkhura, B., Lin, X., and Hsieh, C. Automatic perturba- tion analysis for scalable certified robustness and beyond. In NeurlPS, 2020. URL https: www.uuiisscom /paupppscc/ppper//////aaaa////
Xu, K., Zhang, H., Wang, S., Wang, Y., Jana, S., Lin, X., and Hsieh, C. Fast and complete: Enabling complete neural network verification with rapid and massively par- allel incomplete verifiers. In ICLR. OpenReview.net, 2021. URL https::/ https://opaneeviewnet/toooo d=nVZtXB 6LNn.
13

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
A. Probabilistic Verification Problems
This section contains the formal definitions of all probabilistic verification problems in this paper.
Example A.1. We express the demographic parity faimess notion from Equation (1) as probabilistic verification problem. Let X' C IR" be an input space that encodes information about a person, including a categorical protected attribute, such as gender, race, or disability status that is one-hot encoded at the indices A C [n]]. We assume a single historically advantaged category encoded at the index a E A. Consider neural network net I + R² that acts as a binary classifier making a decision affecting a person, such as hiring or credit approval. The neural network produces score for each class and assigns the class with the higher score an input. We rewrite Equation (1) as
P x [nee(x)) yes
x is disadvantaged]
27
P [nne((x) = yes x is advantaged]
Xx [net(xx) net(x); 2 0 x, 2 0
27
Px [nee(xx)) - net nxt( 2 0 x, 2 1
x [ee((x) net(x); 2 - x, I <0/PP//x, S
Px [x)e net(x)) 2 A x, 2 11/PpxX,, 2 21
Fx [min(net (x), net(x) xx) 2 0//Pxx [xxxxx22 2]
21
Px [min(net(x);, net(x) x, - 1) 2 0 PPx x
[x, 1 0]
Px PxloSat (1)
USst (x, net
0 Msat (x, net (x)) 2 0]
(2)
720
Px [Asa xx, nx)) 2 0]/ |ssa Xx net (x)) 2 0]
(3)
fsat xxx
9sat (x, nx)( 2 0/ ,..., ,P Isat (x, net(x)) 2 0) 20
where, Ssat (PI, P2, P1) = (PiP1) - 7, Isat (x, net(x))
= min(net(x), - net((e))))) - xx)= ISa (x, net(x))
-x Isa (x, net(x)) min(net(x), - net net(x), (x)x: X, 1), and g (x, net(x)) = -x,
A.1. Parity of Qualified Persons
The following probabilistic verification problem concerns verifying the parity of qualified persons, a variant of demographic parity that only considers the subpopulation of persons qualified for, for example, hiring (Albarghouthi et al., 2017). Let X C R", A C [m)], a E A, and net RR + R be as in Example 1. Additionally, let q E [m] \ and R, such that persons with x 2 q are considered to be qualified. In their extended set of experiments, Albarghouthi et al. (2017) consider that encodes age and q = 18 so that only persons who are at least 18 years old are considered to be qualified. The parity of qualified persons fairness notion is
P [x) = yes x is disadvantaged A x is qualified]
2 7
P
x [net(x) = yes x is advantaged A is qualified]
Px [ne ne) 2 0 x, < 0 x, 2 9]
2 r
x |net (net()), [x), net )2 2 0 x, 2 1Ax x, 2 1
P. [net(x); - nxt(x), 2 min(-x,. X, 4) 2 0]
Px [net(xx) net(x)) 2 0 min(x, 1, 9) 2 0] 29
Ssat [Px
Isat (x, (x)) 2 .)....,.IP 1xx Asaa (x, net(x)) 2 01) 2 0
(1)
where 7 E [0, 1], Ssa (pr. Ps. Pa)= = (pIPa)/ (P2P)) - 7, I8ml (x, net (x)) = min(net(x), - net(x) -x,: - 4). (2) Isat (x, net(x)) = min( - -x,: q). ISat (ل) (x, nx)) = min(net(x), - net(x)); x, - -1, - 4). and gsat (x, net(x)) = min(x, 1, 4).
(3)
(4)
A.2. ACAS Xu Safety
Next, we consider Equation (2) for an ACAS Xu network, where to be safe means satisfying property d2 of Katz et al. (2017b). For quantifying the number of violations, we first define what it means for an ACAS Xu neural network net R - R to
14

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
violate Φ2- Using the satisfaction functions of Bauer-Marquart et al. (2022), violating d2 means
Isat (x, nx)( max net (x); net(x), 0 Vx E Xx n
(5)
where X is the bounded hyperrectangular imput space of net and
Xd [55947.96 so] x IR? [1145, oc [-00,000,0000 60).
We refer Katz al. (2017b) for an interpretation of Φ2 in the application context. Quantifying the number of violations with respect to 22 corresponds to computing
8 S P (9sa (x, net(x)) 0] = Pxl- Isar (x, net(x)) 2 0 S u,
where Isat in Equation (5) and is uniformly distributed on XØ2 O X with all points outside Xx2 n nX having zero probability.
A.3. ACAS Xu Robustness
For the ACAS Xu robustness experiment in Section 6.2, solve five probabilistic verification problems for each reference input one for each of the five classes. Our goal is to bound the probability of net classifying input x' class i [5]. where x' is close to the reference input in the first two dimensions and identical to x in the remaining dimensions.
Let net be the ACAS Xu network N1,1 of Katz et al. (2017b) with input space X' X x]. Let x be a reference input. Note that the ACAS Xu networks assign the class with the minimal score to an input instead of using the maximal score. For bounding the probability of obtaining class E [5] for inputs close to x, we compute bounds on
Xx 1xsaa (x', nen((x))) 2 0):
5
Isat (x, nen((x)) = min net(x'),, - net (xt'x;
jfi
where x' is uniformly distributed on the set X' ([x1.2 - 0.05 W1.2 X12 + 0.05 W1:2] x (x3s)), where w = x x and Zz: the vector containing the elements ij of a vector
A.4. VCAS Correctness
In the VCAS correctness experiment in Section 6.2, the goal is to prove whether the VCAS network net R4 + R9
of Zhang et al. (2024) satisfies
[gsat (x, net (x)) 0] 0.9,
where Usat (x, net (x)) net(x), min net(x), which encodes that the network predicts 'Clear Of Conflict', and is uniformly distributed on the set [-8000, 0) x [o, 100j x (-30} [0, 40J. We refer to Zhang et al. (2024) for an interpretation of this specification in the application context.
A.5. Usefuul Modelling Techniques
As discussed in Section 4.2, PV requires the input space X' to be hyperectangle. Further, it requires that each input distribution Px allows for computing the probability of a hyperrectangle in closed form. This section shows how some of these restrictions can be mitigated. Concretely, we show how to use multivariate normal distributions as input distributions and polytopes as input spaces.
We first show how we can apply PV to multivariate normal distributions by transforming the input distribution and the network to verify. Consider a multivariate normal distribution P,, with mean μ and covariance Σ AAT.. If Σ is diagonal, the probability of a hyperrectangle has a closed-form solution, so that we can compute it efficiently. Here, we are interested in the case where Σ is not diagonal, so that we can not compute the probability of a hyperrectangle directly. In this case, let P be a standard multivariate normal distribution. Now, z = Ax + is distributed according to P Therefore, by prepending the linear transformation Ax + μ to net, we can apply PV to general multivariate normal distributions, since the probability of hyperrectangle under standard multivariate normal distribution has closed- form solution.
15

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Second, we show how to apply PV polytopal input spaces, even though they can not be used as input space directly, Let P {x E I Ax < b) be polytope and let X' 2 P be hyperrectangle enclosing P. By using X' as the input space and using
Ix Ix (x, net (x)) 2 0 Ax = b
Px PasSa (x, net (x)) 2 0 Ax bj
Px [Ax < b]
we can apply PV to polytopes as input spaces. However, before applying PV, we should check whether Px [Ax = > 0. since, otherwise, the verification problem is ill-defined. We can apply PROBBOUNDS for this purpose by computing bounds on Px [Ax < b].
B. Additional Details on PROBBOUNDS
This section contains additional details on PROBBOUNDS (Algorithm 2). It includes a detailed description of our procedure for splitting dimensions and a motivation and additional details on our BABSB SPLIT heuristic.
B.1. Splitting
Section 4.1 describes how to split a dimension d E [n|] to refine a branch. This section formally defines the splitting procedure that PROBBOUNDS applies. A dimension can encode several types of variables. We consider continuous variables, such as normalised pixel values, integer variables, such as age, and dimensions containing one indicator of one-hot encoded categorical variable like gender. The type of variable encoded in d determines how we split d.
For continuous variables, we further diffcrentiate whether is bounded, unbounded in one direction, or unbounded in both directions in dimension d.
If B is bounded in dimension d, we bisect B along d resulting in two new branches [ and [x" xx) Concretely, Xtx = =x Xx and x'x = =xy- Xx for all d' E [n]] (d) while X x xxa X and x² Xa.
If is unbounded in both directions in d, we split at zero, so that X = x²1 = 0. The remaining bounds of the new branches [x', x'] and [x", x"] are as in the bounded case.
If B is bounded from below but unbounded from above in d, that is -00 < X < x = xo, we split at X X" max(2x.,, 1), all else being as above. Effectively, this split rule performs an exponential search over unbounded dimensions until the remaining unbounded branches are no longer selected by SELECT, for example, because they have diminishing probability in the case of SELECTPROB. We handle the case where d is bounded from above but unbounded from below analogously.
For integer variables, we split d as for a continuous variable to obtain [x', x1}, [x,,x" and round x', to the next smaller integer while rounding x" to the next larger integer.
For a one-hot encoded categorical variable V encoded in the dimensions A C [n] with d A, we create one split where V is equal to the category represented by d and one where V is different from this category. Formally, X²- x and X/x = X'y 0 for d' E A {d) defines [x', x'). For [x", x"), we set x" = x" = 0 and leave the remaining values are they are in x and X. This splitting procedure eventually creates new branch where all dimensions are set to zero. This branch has zero probability and can be discarded immediately.
In any case, need to ensure not to select d xf, Xd-
B.2. BABSB
Our BABSB split selection heuristic is variation of the BABSB heuristic for pon-brbbabiilstic neural network verification of Bunel et al. (2020). One difference is that Bunel et al. (2020) use the method of Wong & Kolter (2018) for estim- ARITHMET... Another difference is that while Bunel et al.
ating the improvement in bounds, while we use (2020) are mainly interested in lower bounds, we are equally interested in lower and upper bounds. Let (d.1), x(d.1) and [x)) x(4.2)] be the two new branches originating from splitting dimension d E [n] and let yfd.1), be the bounds that INTERVALARITHMERN
(0d.))/(d.11) y(d.1) (d.2), ((d2) computes on Isat (-, net())) for these branches. Our BABSB heuristic se- lects d arg max j(0), where j(d)) max (max(g (d.1). (yd.1) ( (d.2)), min (yiny(e (d.1), ( (d)2))). In other words, we select the
16

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
dimension d that yields the largest lower bound smallest upper bound in any of the new branches, while Bunel et al. (2020) select the dimension d with the largest lower bound among the smaller lower bound for the two branches originating from splitting d. We found this variant to be the most successful for our application. Bunel et al. (2020) discuss further variants.
Implementation. We round all bounds to four decimal places to mitigate floating point issues. If several dimensions yield equal improvements in bounds, we randomly select one of these dimensions. Without this random tie- ie-breakingg we might split single dimension repeatedly if the ANTERVALARITMMEICC bounds are very loose. We use a separate pseudo-random number generator with a fixed seed for this tie-breaking so that BABSB remains entirely deterministic.
C. Extended Theoretical Analysis
This section contains the proofs of the theorems in Section 5. We also give a more general completeness analysis of PV than presented in Section 5.
C.1. Soundness
This section contains the proofs for our soundness results from Section 5.
Proof of Theorem 5.1. Let & E N and let x(() and x.(() be as in Algorithm 2. PROBBOUNDS computes g(t) as the total
probability of all previously pruned satisfied branches .P(1) Uk=1 xe(t). Similarly, (0)) (²)) where (1) is the total
sat
probability of all previously pruned violated branches {((0) = _ x((") Since we assumed that COMPUTEBOUNDS produces valid bounds, PRUNE only prunes branches that are actually satisfied or violated. Therefore,
2(t)) sat C (x E
Isat (x, nxt( 2 0} and p(1) viot S {x E X' Isat (x, nx)( < 03. From this, it follows directly that
((t) = Px [p(0]
< Px Pll (x, net(x)) 2 0]
((9) = Px
Raad
I Pxx P (x, nx) < O],
which implies (1)) = - RR(1) 2 1 - Px Pxlas (x, nx)( is sound.
< 0] = Ixx nx)( 2 0]. This shows that PROBBOUNDS
Proof of Corollary 5.2. Corollary 5.2 follows from Theorem 5.1 and the soundness of the COMPUTEBOUNDS procedure applied by PV.
C.2. Completeness
This section concerned with proving our completeness result from Section 5. We first discuss in more detail why Assump- tion 5.3 is only mildly restrictive. Next, we define conditions on the SPLIT, SELECT, and COMPUTEBOUNDS procedures that ensure the completeness of PV. We then prove that the SELECTPROR, LONGESTEDGE, heuristics and INTERVALÅRITIMETI,, as well as CROWN satisfy these conditions. Finally, we prove the completeness of PV.
Discussion of Assumption 5.3. The proof of Theorem 5.5 is based on Lemma 5.4 that states that PROBBOUNDS produces a sequence of lower and upper bounds that converge towards each other. Intuitively, we require Assumption 5.3 since converging bounds on (P)...)..... PP)) are insufficient for proving (Pi..... PP.) 2 0 if [s (Pi,..., Pn)) = 0 (Albarghouthi et al., 2017). Note that Pl.
P...... .......P Py and fset (P1..... (Pi....,Pu) Pe) are unknown but fixed values in Equation (3).
For illustration, assume we want to show y 0, where y R is an unknown constant. We are provided with converging sequences of bounds (ft),ENs and (ut)en with l, < y S for each E N and lim la = lim U4 = y. If y 0, the sequences of bounds that only converge in the limit do not suffice to prove 2 0, since there may not be a T E N with f = O. However, if the y + O, obtaining a finite number of iterates of (fx) and (ue).e always suffices for proving or disproving y 2 O. Concretely, there will be a T E N, such that either ég > or ur < O, that proves, respectively, disproves y 20 The assumption that fsar ..,....,,.............. ,P)) # 0 corresponds assuming y o 0 in this example.
17

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
In Section 5, we describe studying ...................... Pn) SSat (P1.... ........PP...................... that Ssat (Pa.....PPPP) O. If Jsac(P "apa.-..-PPP Pn.) O, the probabilistic verification problem with S'sac in place of fsat satisfies Assumption 5.3 and is only marginally stronger than the original verification problem.
for some e O, if we suspect
The motivation for requiring F- xx(0) Isat (x(*), net(x!")) 0] Vi [t] is similar as for requiring (P1....... Pn) + O. (4) If P x (9sa (x(1), net(x(()) 0] # O, there can be region of the input space with positive probability that we can never prune, since the bounds computed by interval arithmetic CROWN may only converge in the limit for this region. However, if this is the case, we can tighten ISat (x(1), n))( 2 to ISat (x(*), net (x())))) 2 E for some & > such that P x Sac (x(*), net(x(()) E] 0. Such E 0 exists because P [9sas (x, net(x)) ) 0J 0 means that the satisfaction boundary has positive volume but any neural network has only finitely many flat regions that can produce a satisfaction boundary of positive volume. We now define conditions on the COMPUTEBOUNDS, SPLIT, and SELECT procedures that ensure the completeness of PV.
(6)
(6)
(1)
Definition C.1 (Convergent Bounds). Let f R= + R". We call COMPUTEBOUNDS procedure that computes y S f(x) y for x E [x. x convergent if |l yl + a0 |X -E-xl x|| + 0 and |yy yll = Of | x =.
Definition C.2 (Dimension Alternation). Let X R". A splitting procedure SPLIT is dimension-allermating if for every d E [n]] with X # Xa
Et N: 3(x', x
branches (t) :X' X's < xdd X
where branches (t) SPLIT(branches' (1-1)) for t N and branches (0) [x x
Definition C.3 (Branch Alternation). A branch selection procedure SELECT is branch-alternating if
Vt E N: VB E branches (1) PPx > 0 = At 2 t: B E SELECT(branches NN;
where N E N and branches (1) is the value of the branches variable of PROBBOUNDS in iteration t where PROBBOUNDS instantiated with SELECT and COMPUTEBOUNDS procedure satisfying Definition C.I.
In the following, we prove that SELECTPROR, LONGESTEDGE, and LABSB-LONGESTEDOEEE as introduced in Section 4.1 are branch alternating and dimensional alternating, respectively. It is well-known that INTERVALARITHMETIC satisfies Definition C.1 (Moore et al., 2009). We provide proof in Appendix D.2. We show that CROWN satisfies Definition C.1 in Appendix E.
Proposition C.4. LONGESTEDGE satisfies Definition C.2.
Proof. Let [x, x C R", d E [n] with x # Xd, and let branches (f) for t E No be in Definition C.2. We call X,- X, the edge length of in x).
If xa= X
max dd Xxy x the dimension d is selected for splitting immediately. In the following, we not only show that x X decreases when split but also that X, xx + 0 in at least one branch when we split d repeatedly. This result is required for the second part of this proof. We differentiate several cases based on the variable encoded in d.
Bounded Contimuous Variable. Let encode a continuous variable with X X,, < cc. As described in Section 4.1 we split such dimensions by bisecting [x, x] along Bisecting decreases the edge length of d in the resulting branches so that we have X¹a x'a < Xa X for all [x' x E branches (1) = SPLIT((X X x)). Furthermore, the edge length of d converges towards zero if we bisect along d repeatedly.
Continuous Variable Bounded from Below but Unbounded from Above. Let d encode a continuous variable with -00 X, < X = 30. Since splitting such a dimension creates one branch where d is bounded, we have X'a X's < Xx X, for the bounded branch [x', x'] E (1a Furthermore, repeatedly splitting the bounded branch along d lets the edge length of d converge towards zero, discussed above.
Continuous Variable Bounded from Above but Unbounded from Below. This case proceeds analogously to the previous case.
18

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Continuous Variable Unbounded from Both Sides. Splitting along such variables creates two branches that are bounded from one side. Therefore, after two splits, we obtain two bounded branches, such that X X X Xx for two ,',x' x E branches (2) SPLIT(branches")) Similarly, repeatedly splitting the bounded branches along lets the edge length of d converge towards zero.
Integer Variable. Let d encode an integer variable. Splitring d proceeds for continuous variable, except for excluding non-integer values from the new branches. This decreases the edge length of d at least as much as if we were splitting a continuous variable. Therefore, we have that X2 - X'a < Xa - X for at least one branch [x', x E branches (1) Furthermore, the edge length of reaches zero after finitely many splits in all bounded branches since we exclude non-integer values.
One-Hol Encoded Categorical Variable. Let d contain an indicator of a one-hot encoded categorical variable. Splitting d decreases the edge length of d to zero, so that we have X, - X = 0 < Xd X for all [ x E branches())
Overall, Definition C.2 is satisfied if dimension d is selected for splitting immediately.
Now consider the case that d is not selected for splitting immediately. In this case, different dimension d' E [n]. d' o d with X - Xxx 2 X Xx is selected for splitting by LONGESTEDGE. As we have argued above, repeatedly splitting d' lets the edge length of d' decrease towards zero in at least one branch. Therefore, we eventually obtain [x', xx''"| branches with X'O 1 < Xd X Since this holds for all d" E [ni], d" & d with Xạ" Xa"" 2 X,- Xx. we eventually obtain branch where LONGESTEDGE splits d. Therefore, Definition C.2 is also satisfied if dimension d is not selected for splitting immediately. Overall, LONGESTEDGE satisfies Definition C.2.
Corollary C.5. Proposition C.6. SELECTPRoB satisfies Definition C.3.
satisfies Definition C.2.
Proof. Let branches (4) be the value of the branches variable of PROBBOUNDS (Algorithm 2) in iteration f E N, where PROBBOUNDS instantiated with SELECT and a COMPUTEBOUNDS procedure satisfying Definition C.I. Let N, I e and B branches with P2x [B] >> O. Our goal is to show
Et 2 t: B SELECTPRRO((raacches NN
(6)
B E SELECTPROB(Dranchhe .N), Equation (6) holds immediately. Otherwise, there are at least N branches Bi in iteration with Px [B]]= 2 1B). We show
3t > t: VB,,
> P [B] YB,, B; ~ B, Px < P
where B;- ~+ B,, B,, is a branch in iteration E N that originates from splitting By, meaning that By, C B/.
Let B. be branch in iteration with Px[ [B]]] 2 P [B.] First of all, if B is pruned by PROBBOUNDS in iteration t, then there are no new branches originating from By, so that (+) holds vacuously. Otherwise, PROBBOUNDS splits By.
We first consider the special case where the input space only contains categorical and bounded integer variables. Dimen- sions encoding such variables can only be split finitely often. Therefore, splitting B eventually produces a finite set of branches [x. x with x = X. Since we assumed COMPUTEBoUNDS to satisfy Definition C.I, COMPUTEBOUNDS computes the bounds y = y for branches with x = x. Branches with = y are certainly pruned by PROB BOUNDS. Therefore, if we choose L' > large enough, Equation (7) holds with (+) holding vacuously, since all branches originating from Bi have been pruned.
Otherwise, let the input space contain at least one continuous unbounded integer variable. We show that there is an iteration L' > / such that (*) holds for By. Without loss of generality, assume that the dimension selected for splitting encodes continuous variable or an unbounded integer variable. This does not harm generality since categorical variables and bounded integer variables can only be split finitely often and, therefore, will eventually become unavailable for splitting,
First, consider splitting along a dimension encoding bounded continuous variable. Since we split continuous variables by bisection, the volume of all branches B,, originating from B' decreases towards zero as we split d repeatedly. As stated
19

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
in Section 3, we assume that all continuous random variables admit probability density function. This implies that the probability in all branches By originating from splitting B, decreases towards zero as the volume decreases towards zero.
Now, consider splitting along dimension d encoding an unbounded variable. Without loss of generality, assume that B; is bounded in d in at least one direction. This does not harm generality since dimensions unbounded in both directions are split into two parts, each bounded in one direction. Given this, splitting along d creates a bounded and an unbounded part. If d encodes an integer variable, the bounded part contains only finitely many discrete values. Therefore, as argued above, all branches originating from this bounded part are eventually pruned. If d encodes a continuous variable, the bounded part behaves as described above with the probability of all branches By originating from B,, decreasing towards zero. Therefore. we only have to show that the probability remaining in the unbounded part decreases towards zero continue splitting to show (+). In fact, this follows from the properties of probability measure.
Above, we have shown that splitting repeatedly either leads to pruning the resulting branches or the probability of all resulting branches decreases towards zero. Therefore, there is a t', such that (*) is satisfied for B,, Since there are only finitely many branches in any iteration of PROBBOUNDS, the above implies that Equation (7) is satisfied. In turn, this directly implies that B is eventually selected by PROB proving Proposition C.6.
Next, we prove a generalised version of Lemma 5.4.
Lemma C.7 (Converging Probability Bounds), Let N E N be a batch size. Let ((e(),u())) (ul))) IEN be the iter- ates of PROBBOUNDS (9 (x, net(x)) 2 N) instantiated with a SELECT procedure satisfying Definition C.2, a sound COMPUTEBOUNDS procedure satisfying Definition C.I and a SPLIT procedure satisfying Definition C.3. As- sume P, I9sa (x, nx)( = 0] = 0 as in Assumption 5.3. Then,
lim g(t) +
lim (() = =Px Passa (x, net(x)) 2 0).
Proof. We first prove that li (00) P
Issat (x, net(x)) 2 0). The convergence of the upper bound, lim u(t)
Pxx 10sai netxxxx))
2 0) follows analogously.
Let Xtat = {x E X' | Isat (x, nx)) > 0}. where X' is the input space of net. Note that Px (x
Px Ixl(x E Usat (x, net(x)) 2 0}] due Assumption 5.3. Further, let flll be as in the proof of Theorem 5.1 and recall g(() = PxPP [2((0]]
First, we give an argument why the limit lim g09 exists. Due to Theorem 5.1, the sequence {ee) hen is bounded from above. Furthermore, (E()) JeEN is non-decreasing in l since PROBBOUNDS only adds elements to sat fore, lim {(t) exists. Now, we can equivalently rewrite
p(t) There-
((t)
x Isst (x, nx)) 2
1
[(t)]
P
x
1-000
P
{(t]
P2 [x
0
(-200
IP
Xrat
\
0.
(8)
1-000
We now argue why (8) holds. Consider the case that the input space does not contain a continuous variable. Let B, be a bounded branch in iteration t E N for an input space containing only discrete variables. As discussed in the proof of Proposition C.6, there is an iteration t' > t so that all branches B, that originate from splitting B, are pruned. Due to the properties of a probability measure, the probability of the unbounded branches B, that remain decreases towards zero as + co. Therefore, (8) holds if the input space does not contain a continuous variable.
sat Now, assume the input space contains at least one continuous variable. Let (0) = X 200 With the goal of
eat-
obtaining a contradiction, assume li P. (+(0 > 0. Since we assumed in Section 3 that every continuous probability distribution admits a density function, vol(2 sat) > 0, where vol denotes the volume. Let t E N. Since the branches maintained by PROBBOUNDS form a partition of the input space, there is a branch B, in iteration of PROBBOUNDS such that v 0 B.)= > 0.
20

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
t Due to SPLIT satisfying Definition C.2 and SELECT satisfying Definition C.3, we eventually obtain By in iteration (' >
with By C X n Bt. Additionally, since SPLIT satisfies Definition C.2, have that || x - 0 for all not yet
+ Since COMPUTEBOUNDS satisfies Definition C.I, we have that the bounds y S Isat (x, net(x)) - y produced by COMPUTEBOUNDS converge towards Isat (x, net(x)). Note that 9SRt (x, net(x)) > 0
pruned branches [ x]
for all x E [x, x] since [x, x] C By C Xaat- This implies that there is an iteration t" > 1' in which PROBBOUNDS considers a branch B C Leat for which y > O, which means that PROBBOUNDS prunes B This contradicts the construction of (2(0) sat. With this contradiction, we have shown lim g(() continuous variable.
Px Igsar (x, net(x)) 2 0] when the input space contains a
Overall, we have shown lim;-roc g(() xxx Sd (x, nx) 0] for all possible compositions of the input space. The convergence of the upper bound (+) follows from an analogous argument on (t) as in the proof of Theorem 5.1 where u(() 1- 1-h(9) (4) This establishes Lemma C.7.
Lemma 5.4 follows from Lemma C.7 by inserting SELECTPROB for SELECT, LONGESTEDGE BABSB- LABSB-LONGESTTEGEER for SPL.T, and INTERVALARITHMER LONGESTEDGE-K satisfy the requirements of Lemma C.7 due to Proposition C.6. Proposition C.4 and Corollary C.5, respectively. We show that INTERVALARITIMETU and CROWN satisfy the requirements of Lemma C.7 in Appendix D and Appendix E, respectively. We now prove a generalised version of Theorem 5.5.
or CROWN for COMPUTEBOUNDA SELECTPROB, LONGESTÈDGE, and BABSB-
Theorem C.8 (Completeness), When instantiated with PROBBOUNDS as in Lemma C.7 and COMPUTEBOUNDS procedure that satisfies Definition C.I, PV is complete for verification problems satisfying Assumption 5.3.
(1) Proof. Let net, fsat: ISat.... ISat be as in Equation (3). First, consider (p..... Pv) > O. As a consequence of Lemma C.7, the bounds f S fsat (PI..... .P) S u produced by COMPUTEBOUNDS converge towards f (Pi. .,, .P.), since COMPUTEBOUNDS satisfies Definition C.I. This implies that eventually > 0, meaning that PV eventually proves fsa (P1,... P.) 2 0.
(v)
If fsat (PI....,PP) < 0 we eventually obtain u < 0 with the same argument as above. Since < 0 dis-
proves Ssat (Pi,,..,Pe. Po) 2 0, PV is complete for probabilistic verification problems satisfying Assumption 5.3.
Similarly to Lemma 5.4 and Lemma C.7, Theorem 5.5 follows from Theorem C.8 by inserting INTERVALARITHMETI or CROWN for COMPUTEBOUNDS.
D. Interval Arithmetic
This section introduces additional interval arithmetic bounding rules for linear functions, multiplication, and division, com- plementing the interval arithmetic bounding rules for monotone functions in Section 3.2. Furthermore, we provide Theorems 5.1 and 6.1 Moore et al. (2009) for reference and provide a proof that INTERVALARITHMEII satisfies Definition C.I. These results provide the foundation for the theoretical analysis of CROWN in Appendix E.
D.1. Bounding Rules
Let (k)) be as in Section 3.2. First, consider the multiplication of two scalars, that is. ((() w) = zw where S S and w S w < w. We have
min(zw, 2w0 210, zw) < #1 A max gw, zw, 210)
For the element-wise multiplication of vectors, we apply the above rule to each element separately. Multiplication of several arguments can be rewritten as several multiplications of two arguments.
Now, consider computing bounds of the reciprocal (() with <25 z. We differentiate the following cases
1
if & (E,z) - 1
< - if0 $ (2,z)
i
0x < 2 if0 [2,7)
0 if0 (2,
21

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Using bounds the reciprocal, can compute bounds on division by rewriting division as multiplication by the reciprocal. Lastly, for affine function ((8) (()(()) (z) Wz + b where z S have
[w] + [
Wz b
W
W z+b. b,
(9)
where [WIT] ma w and [W min(O, W.,).
D.2. Theoretical Properties
We include Theorems 5.1 and 6.1 of Moore et (2009) and relevant definitions for reference. Let H
(x, x
x, x
I" x S x
be the set of hyperrectangles in IR" Let 2 R20 with
(xX) max (max X,
min x2) max x
||x x'
1100
rE[n] xEA
x.x'EX
be the width of the R We denote the image hyperrectangle [x, x under R2"
RM
f((x,
{f(x) x.]
D.2.1. DEFINITIONS
Theorem 5.1 of Moore et al. (2009) applies to inclusion isotonic interval extensions as defined below. Definition D.1. Let F; HI" - T and f I R
F is an interval extensions of f if Vx R" F(xx, x)) (x). f(x)].
F is inclusion isotonic if V X
X X HH"
x C x X F([x' C F(x,x)),
Theorem 6.1 of Moore al. (2009) requires inclusion isotonic Lipschitz interval extension.
H H be an interval extension of f RR R Lipschitz there exists an such Definition D.2. Let
that v(x, x] E HI" wo ( x < [xx[[xX] x).
INTERVALARITHMETIC, as introduced in Section 3.2. corresponds natural interval extensions Moore al. (2009). As Moore et al. (2009) show, natural interval extensions and, therefore, INTERVALARITMMENT satisfy Definitions D.1 and D.2.
D.2.2. THEOREMS AND PROPOSITIONS
Theorem 5.1 of Moore et al. (2009) is known as the fundamental theorem of interval analysis. It proves that INTER- VALARITHMETIC is sound. We also provide proof for the well-known property that INTERVALARITHMETE satisfies Definition C.1. This result is closely related to Theorem 6. of Moore al. (2009), which we also include for reference.
Theorem D.3 (Theorem 5.1 of Moore et al. (2009)). If F : IH + H is an inclusion isotonic interval extension of R" + RT. have f(x, x)) S ()) for every [xxx] HI.
Theorem D.4 (Theorem 6. of Moore et al. (2009)). Let F : H + H be an inclusion isotonic Lipschitz interval extension of f R >> Rmm. Let X xx x] H define the M-step uniform subdivision of [x. x] with M E N
(w(2 (([x,,,,)) x,I) M
x, + w (0((,,, x,))
X1, x; + (j 11)
j [M].
Further, let
M
F(M ((M) (1x x)) = U
F(Xi,, x ... x Xn.sa).
=1=1
It holds that
s 2L w(X)
w(F (MM)
[x, x()) - w w(f(xxxx))
M
where L. is the Lipschitz constant of F.
22

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Proposition D.5. Every Lipschitz interval extension satisfies Definition C.I.
Proof. Let F; H" + H" be Lipschitz interval extension with Lipschitz constant L. We write (y Xxxxx y xxxx| F(xx, x)
for X x H", Using that F' is Lipschitz, we obtain
lim
x
y
x
||
lim w w(F((xxx))) x
S lim 1x-211~00
Lw((x [x, x]) - O.
| 1x-xxl
-0
Further, since F is an interval extension, we have 1y (x.x) Definition C.I.
Y Xxxx]] = 0 for any x E R This proves that F satisfies
Corollary D.6. INTERVALARITHMETIE satisfies Definition C.I.
E. Theoretical Analysis of CROWN
In this section, we prove that CROWN (Zhang et al., 2018) satisfies Definition C.I. In fact, we provide a slightly stronger result showing that CROWN possesses the properties of INTFRVALARRTHMEETE that follow from Theorem 5.1 and 6. of Moore et al. (2009). Concretely, we prove that the bounds computed by CROWN are always contained in the bounds computed by an inclusion isotonic Lipschitz interval extension, such that Proposition D.5 and Theorems D.3 and D.4 apply. Since the bounds computed by this interval extension converge and they contain the bounds computed by CROWN, the bounds computed by CROWN also need to converge, establishing that CROWN satisfies Definition C.1. We first revisit CROWN, discuss why CROWN itself is not inclusion isotonic, and finally provide the inclusion isotonic Lipschitz interval extension that is guaranteed to compute looser bounds than CROWN.
In the following, we restrict our attention to Rel.vaactie cullecconeected neural networks since these are the most relevant for this paper. However, similar arguments to the arguments we make below can also be made for other architectures and activation functions.
E.I. CROWN
We revisit CROWN for ReLU-activated fully-connected neural networks. Applying CROWN for other activation functions and architectures is described by Zhang et al. (2018); Xu et al. (2020). Let net : : Rm be a ReLU-activated fully-
connected neural network with E N layers, that is, net = f(K) o o... f(1), where f(() : R + R is either an affine function or ReLU. We use f(()- (R) ....o o f()) and ( f(K) ....g o f(k) to denote partial evaluation of net. Further, let [x x C X. CROWN computes a linear lower bound and linear upper bound on net
Ax + d net Ax
VX e
These linear bounds can be concretised into constant bounds
YCROWN A
d S net(x)
A
X
A
x + d YCROWN:
where are bounds on the input, [x x], [ max (0, A, and [A] min A.,))
CROWN computes the linear bounds by a backwards walk over the network net, starting from f(K) and propagating linear bounds backwards until reaching (()), Algorithm 3 defines CROWN for feed-forward neural networks, such as net. The algorithm iteratively computes linear bounds
(1) z
(k)
(k() S (((+1:)2 (1) < AAA (R) + +d
Yz(k)
[z (k))
where Iz (k) z(! [K)] are bounds on ((( (x) for E x that are computed before invoking CROWN, for example, using INTERVALARITHMETU (Zhang al., 2020). The bounds (k)) (k) are sometimes known pre-activation bounds. Altemn atively to using INTERVAIARITHMERT
we can compute (8)) z (8)) by invoking Algorithm 3 iteratively for f(:1) ..... (:K)
and use the concretised bounds on f et al., 2018). Algorithm 4 describes this approach in more detail. Applying Algorithm 3 with the layer bounds computed by INTERVALARIHMETIC is known as CROWN IBP (Zhang et al., 2020), while using Algorithm 4 is referred to as just CROWN. To avoid confusion, in this section, we use CROWN to only refer to Algorithm 3.
...., f(1-1) as the layer bounds for the k-th invocation of Algorithm 3 (Zhang
23

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Algorithm 3 CROWN
Require: Neural Network net f(K) .... f()) Input Bounds [x. x), Layer Bounds [2 = (k-,,,,, ;(k-)),z'u x[K-1)]
1: A [K) < I, A K)
//1 E m is the identity matrix
2: ( <- 0, d ()
<-
//0 T. is the all-zero vector
(00 + x, O) + X
4: for (K, (K.,,,,
1 do
(A (A-11) A (k-1)
A A 1 (k) .z (k-1)) 2(k-1))
5:
A. <- CROWNRULE(FCH,
6:
d (k d
(k)
7:
+
8: end for
9: return (A (0)
(0)
(0)
Algorithm 4 CROWN with CROWN Layer Bounds
Require: Neural Network net = f(K) ....o f(), Input Bounds [x. x
for i [K] do // Below, CROWN refers to Algorithm
2:
(k) z [k] CONCRETISE(CROWN, (sk), [x. x), (2) (0))) ..... 1=*-1, 22--1111))
3: end for
4: return CROWN(net, |x, x], [ z(1)
1 k- 1"-1,zk-11
Similarly to ANTERVALARITIMETIC, Algorithm 3 uses CROWNRCLES to propagate linear bounds through more fundamental functions, such as affine layers or ReLU layers. Specifically, the CROWNRULE for an affine func- tion (z) = Wz + b computes
A ik = A A W.
A (k-1) = W,
A (k-1)
= A D.
A (--1)
A b.)b b.
(10)
The CROWNRUL. for ReLU layer (kk (z)= |2]+ is
A (k-1) = A [k) +
diag(ax) + [ (k)
diag(a))
A (k-1) =
A (k)
B
(11)
A k-- 1) A (k)]
+
diag(a)
| (1))
diag(a:.
(k-1)
A (ki) +
B,
where diag(a) is a diagonal matrix with the vector a on its diagonal and a aF B E Ru have
(k-1) 1)
z
2
(A
1) 0
2
B
0 o (z)
(K-1) z(tt
(k a
otherwise,
otherwise,
x
z
1-- 00
2
k-1)
1
2
2
2 (k-1)
(k-1)
and 2 ( 2 (1(1111
0
<
2
1
otherwise,
for every E [ng]- Instead of the last two cases for ag, we can also optimise each a, using gradient descent to improve the linear bounds on the network (Xu et al., 2021), as long as we maintain Q E [0, 1].
CROWN is not Inclusion-Isotonic.. We demonstrate that CROWN is not cillussionissotoii. according to Definition D.I
using an example. Consider a single ReLU neuron [x] with input bounds क] = [-3, 2]. The CROWN bounds are 0 < [x]]
+ gg so that the concretised lower bound MccoWN 0. However, the CROWN bounds for [a', .'
[- [a. ø are [x=]
2 3 which yields the concretised lower bound y/ L'RowN - 1. Since L'cROwN MRRoww
3
although (x' xa) =... CROWN not mnclsioonissoooncc
24

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
E.2. CROWN Interval Extension
In this section, we introduce the CROWN INTERVAL EXTENSION (CIE). CIE is a theoretical device that we use to prove that the width of the concretised CROWN bounds linearly converges to zero as the width of the input bounds converges to zero, analogously to Theorem D.4. Concretely, CIE is inclusion-isotonic Lipschitz interval extension according to Definition D.1 and Definition D.2 that is guaranteed to contain the concretised CROWN bounds. Since Theorem D.4 applies to CIE and the concretised CROWN bounds are always contained in the CIE bounds, the convergence properties of Theorem D.4 also apply to CROWN. In the following, we first define CIE, show that it is an inclusion-isotoni Lipschitz interval extension, show that the bounds computed by INTERVALARITHMEN CIE, and finally prove that the concretised CROWN bounds are contained in the bounds computed by CIE.
are contained in the bounds computed by
CIE Algorithm. To define CIE, we define a bounding rule for ReLU, We use the same bounding rule for affine functions as INTERVALARITHMETTE bounds on a ReLU-activated feed-forward neural network net = f(x) o...o o f(1) by computing (4:(R) .... o ( (x, x), where [
introduced in Appendix D.1. Similarly to INTERVALARITHMENS
CIE then computes
x C X' and F The x R Re
Re is the CIE bounding rule for (() The CIE bounding rule for
ReLU layers (k) (v) = [v] is (()) V W. w|. where
O otherwise,
0
Vi V
W
W;
(12)
V.
otherwise,
where i E [ma]] Comparing this bounding rule to the CROWNRULE for ReLU, we can see that the bounds computed by CIE always contain the concretised CROWN bounds for ReLU neuron. The remainder of this section aims to show that this is also the case for complete neural network.
Proposition E.1. Let net f(x) .... f()) be ReLU-activated fully-connected neural network. The CIE interval function F(K) .... F(I) is mnclusion-isotonie Lipschitz interval extension of net.
Proof. We first show that the CIE bounding rule for ReLU is an mnclusion-isotonii Lipschitz interval extension of ReLU. Let F()) be the CIE bounding rule for the ReLU layer (k) ([()))) + ((w)) according to Equation (12).
Interval extension. Let V E Rh* and [w, w| = F()) ([v, v(). Let i E [mx]. Vf S 0, we have w; = -- (v]]] Otherwise, if v, > 0, we have w,
v; = [v]
w,
Inclusion-isotonic. Let [ v C v]
1 S 1 [w', w'| [*() ([V' Vl) and [,, w = (x(()((xx)))))) v)). Let E [nw].
Vf 0, we have Ww w. = [0, 0]
w since V S v.. On the other hand, if V. O, we have [W,,, w.l
Ly, Vi]. If v < O, W/ w = [0
C [ w:] since V. S v < v. Otherwise, [w'. w/] [v' v'l C [W w.).
Therefore, ((k) is meclsion-isooooic
Lipschitz. Let vV C Re* and [w. w] ( v]). For all i E [mg] with w, 0 we have w([w, w.)) 0 and, therefore, trivially w([,,, Wz)) I w((,, V)) For E [mx] with w. > O, we have [W,, W. [y, v.). Overall, w([w, w)) = maxtejm] W; W, S maxie[ma) V. Yi w([x, v)). Therefore, F(k] is Lipschitz with Lipschitz constant 1.
For affine functions, CIE uses the same bounding rule INTERVALARITHMER that is an inclusion-isotonie Lipschitz interval extension (Moore et al., 2009). Lemma 6.3 Moore et al. (2009) now gives us that the composition F-( o.. FX of inclusion -isotonicc Lipschitz interval extensions is also inclusion inclusion-isotone and Lipschitz. Clearly, a composition of interval extensions is also interval extension.
Let net = (K) o o f()) be a ReLU-activvated fully neural network. Let [y.J] and [w, w be the bounds on nx) [x, x] computed by INTERVAL.ARTHMETIC and CIE, respectively. It holds that [y,y]
Proposition E.2.
w. W
Proof. Let net (R² ....o f(1) and [x, x be as in Proposition E.2. We prove Proposition E.2 by finite induction over k E {O..... KJ. Let compute on (x) for x E x).
and (v v() be the bounds that INTERVALARITIMENNT and CIE respectively
25

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Induction start. For A O, we consider the identity function net x, for which both CIE and INTERVALAARITMMETIC
compute (x) - [v(0)) - [
Induction step. Now, let E [K] and assume [y ( 1), 1) -((1111 C [v(k-1), b/l-1)) We show (k), y [1] C [v(A), v(ki]. We
differentiate two cases:
If f(h)) is an affine function, both INTERVALARITHMETES and CIE use the INTERVALARITHMETI bounding rule for affine functions from Appendix D.1 to compute (y()) y y(k) and [v(k), v(0) Since this bounding rule is inclusion- isotonic (Moore et al., 2009), we have (y (k) C (k), v.
Otherwise, ((A) is ReLU. The INTERVALARITMMETIC bounding rule for ReLU computes (y((0, y()) [y((-11]]* 15(
Since the CIE rule for ReLU is an inclusion-isotonic interval extension (Proposition E.I),
follows that [y (k 11 11 S [v((), v.
Overall, this shows that [y, = [y((), y((k] S (x(K), v(k)]= - Yx v).
Proposition E.3. Let net = f(K) o f(l) be a ReLU-activated fully-connected neural network, let [x R" and x), vk E [K]. Further, let [k))k, [/ also be bounds on f(()
let (v( [() be the CIE bounds on f(sk) (x) for
for E x with (x), 12( [(ki| S [v((), v(ki], vk E [K]. It holds that
v(k) Ax and Ax + d S v(K)
VX E [X,
where Ax + d and Ax + d are the bounds on net for x E [x. x computed by CROWN (Algorithm 3) using the layer bounds (1), z (1) b.... (K(K-1) -.)]
Proof. Let net f(k)
f(), x). (,()), and [v((), v(()] for all k [K] be as in Proposi-
tion E.3. Let A (k) A (R) (k) d kk) for all k E (0..... K} be as in Algorithm 3 for the inputs net, [x,x]
and| 12 (1) z "
(K),, z {)) Further, let (0) _0 [v(0)] [001 = [x In the following, we prove
A (k) / (b) + (k) (K) and (k) z (k) (k) I (k)
[ (k) (())
(13)
for every & E (O.................. K}. Note that 12( z( { C [v( v( by assumption in Proposition E.3. Proving Equation (13) also proves Proposition E.3 when k = 0. We proceed by finite induction over k from K to 0, following the backwards walk performed by Algorithm 3.
Induction start. We consider & = K. In this case, A (k) = A identity matrix and E RR the all-zero vector. Therefore, we have
(K) = and d (k) = - = 0, where I E Ra* X is the
(K) (K) + -dd (K) (K) + 0 2 (K) A (k) (K) - d (K) (K) + 5 (kk) for z (R) E (x(,), v(K] This proves Equation (13) for is K.
Induction step. Let l [K] and assume Equation (13) holds for k. We show that it also holds for l 1. We differentiate two cases, based on whether f(k) is affine function or ReLU,
Affine function. If (kk (z) = Wz + b, CROWNRULE computes the linear bounds on (kx) as in Equation (10), so that we obtain
A (k- 1) (
A (k) Wz A (1)b + d (*) A (R) (Wz + b) + (k) (k)
where z E (k- 1), ((k- 11.. The final inequality is due to the induction assumption that Equation (13) holds for k
which we can apply since Wz + b E (k)), v())), since CIE computes (k),, v()) from (v( v(K-1)) using Equation (9). Similarly, we obtain
A (--1) z z (k-1) - A (A)
Wz+ + A (bD b d (K) -A (k) (Wz + b) dd (K) 5 ((K))
again by using the induction assumption.
26

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
ReLU. Letz E ( D( and E [mg]] CROWN computes the linear bounds on f(k) according to Equation (11),
which yields
A (k-1) 1)
2; + d [k-1)
(8)
(8)
A (k)
3, =./t)
2
04
Z4
A (k-1)
Zi + d. 1)
(k)
(8)
B. + d. (8)
ai
+
23
where A denotes the i-th column of matrix A. We now differentiate three cases based on the signs of z! z(1-1) and ((k (k-1) 1) 2
(i) Consider 2;
(1-1) O. We have a; a; 3, = 0. Therefore, A (R-1) 2; + d d =d! 2 (K) (k-1) A 3, 2, + d
(1-1) d S v(k),
where both inequalities are due to the induction assumption with (R) = 0 in Equation (13). We can apply the
induction assumption since 0- |
+ (
(k) [x() and, therefore, 0 E [x)(k), ((() since Iz (k) _ S
(k), {.))
(ii) Consider zf (k- 0 and zi
11-1) 0. First, we find that (v( v!!t [v((-1) v (1-1)) according to Equa-
tion (12) since :! (1) 2 2;
1) > 0. Regarding CROWN, we have at; a. = 1 and B = 0. Therefore.
A (k-1) 2: + d
[A
[k)
A (k)
2, d((a)
A i 2 d {1)) RR)
(k)
A (k-1) 2, d
(k-1)
A (M)
A
2, + d
A
(k)
o, 2,
d
(k)
S v(k)
where the inequalities are due the induction assumption that can apply since z; (1( v((-111]
[y!
(k)
(iii) Finally, consider 2:
(k-1) <0
< z
With the same argument as in the previous case, we have [V. (k) x(11)
(1-1)1. We have
(k- 1)
(k-1)
1|
(k-1) 1)
2
(k-
z
z
a
(k-
(k 1)
B. =
Zi
a,
(k-1)
(k- 1)
2:
2
Z,
z
and a; E [0, 1]. Now,
A (k-1) 1)
2i + d (1-1)
1,8
C1 +
A 1
0i
Zi +
A (k)
3 - +
(14a)
2
(0) +
(k-1)
1)
V.V.
(k-1) 1)
[
B + ah))
(14b)
(A (h 1)
k-- 1) (k-1) 1)
(8)
(K)
z
z
d (k)
(14c)
[-
1)
2
(k --1)
(k- V.
(k-1)
A
(8)
1)
(k)
+ d (1)
(14d)
k- 1)-1)
Z
+
(R)
V
(1-) 1)
+ (k)
i1
(K)
(k-1)
<0 Ve 11(-11) + (k)
20 V
1 (0)00
(K)
(14e)
27

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
where 1 A 20 E {(0,1) (0,
with
A
3.6 20
otherwise
for j E [ma] and 1 ( <o is defined equivalently. Above, the inequality in Equation (14b) is by choosing z; [y(k-1), v(k=1)| as the minimiser of Equation (14a). The inequality in Equation (14c) is by choosing a; = 1
(1-1) < 0. To justify the inequality in Equation (14d) we note which minimises Equation (14b) since v (k-1) S 2
since 2 (*-1) 0 and, further v (()11) 2 2 ((-11), Finally, Equation (14e) follows from the induction assumption that we can apply since
that- -2 ( )
(1 12
A = v) E (v(t-1), vlt-1)
For the upper bound, we apply similar steps to obtain
1,2
(--1)
1) 2
d.
=
ai
+
A 1,
a2
Zi +
(k)
1,
3. + a
<
A
(1-1) 1)
A
1,
(k)
a
(k-1) 1)
+
A
(k)
3 + ạ!
(k)
V
(k (--1) 1)
2
[k
Z
(K (k-1) 1)
(k-1) + ब (4)
(-1))
(1-1)
z
z
(M)
2
V.
(k 1)
(k-
1) V.
1)
(k)
(k-1) 1) d (k)
A
A
+
A
yi
(-1))
k-1)
z
Zi
V.
(k-1) 1) +
A ;,{
(K)
V
(k-1) 1)
+ d;
(8)
(K)
[ [x v
11- +
<0 v (k-1)
+ +
(c)
A k1)
(
By this induction, we have shown Equation (13). Proposition E.3 now follows for k = 0, where A (0) = A, A ())
A. d (0) = d. d = d and (v("), v( = [x, x].
Proposition E.3 requires layer bounds (2), z " ]..... L2 11) ((K-1)) which may not be looser than the CIE bounds. As
we have shown in Proposition E.2, this applies for INTERVALARTHMETIC, A consequence of Proposition E.3 is that this also applies to Algorithm 4. Corollary E.4. Let net, xx,x and [v(K), v(K) be as in Proposition E.3. It holds that
((K) Ax and Ax +x+0 +dd d ((K),
Vx e
where Ax + dl and Ax + d are the bounds on net(x).oo x E x] computed by Algorithm 4.
Proof. Corollary E.4 follows from Proposition E.3 by an inductive argument over k E [K]. Let net = pik) (1)), [x, x and (1), v()), ().,,,,((k),, v(K] be as in Proposition E.3.
Induction start. Applying Algorithm 3 to f(:1) (() does not require layer bounds, so that Proposition E.3 holds for the (concretised) CROWN bounds on f((:))
Induction step. Let k E ( KJ.
Assume the concretised CROWN bounds (1) " (b-)) (00-,,),<---0 ( 1]
on f(:1), ,.... , (c) satisfy Proposition E.3, that is, (2((), ~(() C [v((), (()) for every k E [k - 1]. Since we only require layer bounds on f(11), f..,, f(c-1) to apply CROWN to f(sk) Proposition E.3 applies to the (concretised) CROWN bounds we obtain for f(tk)
We are now able to prove that CROWN satisfies Definition C.1 as a corollary of Proposition D.5 and Proposition E.3.
28

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
GENERAL INFO
GENERAL INFO
BENCHMARKS
PERFORMANCE
FEATURES
PERFORMANCE
FEATURES
MEMORY
MEMORY
BENCHMARKS
(S)
52 Points
39 Points
72 Points
26 Points
(a) HW1 vs. Converse et al. (2020)
(b) HW1 vs. Marzari et al. (2023b)
Figure 4. Hardware
comparison
from versus com.
The figures and
are
taken from
https://
versus. cow wwwmm////mddddeeooeeeeeeee 7401 --ttto-----nee-orr--------- 1-0--17-7000
https: //vervvuuus wwwerrus.cooe.e............ com/en/
intel-core- / 4820k. respectively, Accessed on the 17th of May 2024.
Corollary E.5. CROWN satisfies Definition C.I.
Proof. Since CIE Lipschitz interval extension according to Proposition E.1, Proposition D.5 applies. Therefore, CIE satisfies Definition C.I. Now, due to Proposition E.3, CROWN also satisfies Definition C.1.
F. Experiments
This section contains additional details on the experiments from Section 6 and additional experimental results. A reproducib- ility package containing all datasets, networks, and raw data from our experiments is available at https: doi org/10. 5281/ zenodo. 5.521583, Our code also available at https: /g/ thub, com/ sen-unii-k/ppooonneee
E1. Hardware
We run all our experiments on a workstation running Ubuntu 22.04 with an Intel i7 17-4820K CPU, 32 GB of memory and no GPU (HWI). This CPU model is ten years old (introduced in late 2013) and has four cores and eight threads.
In comparison, Converse their tool to use 46 threads and most 4GB of memory. AMD EPYC 7401P introduced in mid-2017, targeting servers. Marzari et al. (2023b) use Ubuntu 22.04 workstation with an Intel i5 1360330KKF CPU and Nvidia GeForee RTX 4070 Ti GPU. This CPU was introduced in end-2022 and has 14 cores with 20 threads.
(2020) use an AMD EPYC 7401P CPU for their ACAS Xu robustness experiments, limiting
Figure 4 contains the CPU comparison from versus. com. As the figure shows, our HW1 is less performant when considering both the theoretical performance according to the hardware specification and the actual performance on a series of computational benchmarks. Therefore, HW1 is inferior computation power to the hardware used by Converse et al. (2020) and Marzari al. (2023b).
F.2. FairSquare Benchmark
provide additional details on the FairSquare benchmark and present additional results.
29

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
sex
cg
age
edu
Figure FairSquare Bayes Net 1. The network structure of the Bayesian Network from the FairSquare benchmark. In this figure, 'eg" denotes the capital gain variable and 'edu" denotes the number of years of education.
F.2.1. EXTENDED DESCRIPTION OF THE BENCHMARK
The input space in the FairSquare benchmark consists of three unbounded continuous variables for the age, the years of education ('edu'), ), and the yearly gain in capital of person ('capital gain'), ) respectively, well additional discrete protected variable indicating person's 's (assumed binary) sex. The neural networks use "age" and 'edu' or "age', 'edu' and "capital gain', depending on the network architecture, to predict whether person has high salary (higher than $50 000). The three input distributions used by the FairSquare benchmark are
1. the combination of three independent normal distributions for the continuous variables and a Bernuulli distribution for the person's 's sex,
2. a Bayesian Network with the structure in Figure 5 introducing correlations between the variables that are similarly distributed as for the independent input distribution ('Bayes Net I'), and
3. the same Bayesian Network augmented with a constraint that the years of education may not exceed person's 's age ("Bayes 2").").
The integrity constraint is implemented by Albarghouthi et al. (2017) as a post-processing the samples from the Bayesian Network. In particular, person's 's years of education are set to the person's 'ss age if the sampled years of education are larger than the sampled age. We introduce pre-processing layer before the neural network we want verify to implement this integrity constraint in our setting. This pre- prrcceeccssing layer computes edu' min(edu, age) and leaves the remaining inputs unchanged.
Besides experiments on the demographic parity fairness notion, the extended FairSquare benchmarks also include experi- ments on the parity of qualified persons fairness notion as defined in Appendix A.1. For both fairness notions, the FairSquare benchmark uses a fairness threshold of y = 0.85.
F.2.2. EXTENDED RESULTS
Table 4 contains the comparison of PV and FAIRSQUARE the extended set of FairSquare benchmarks from Albarghouthi et al. (2017). The runtime from this table is visualised in Figure 2.
E3. ACAS Xu Safety
We provide comparison of PROBBOUNDS with E-RROVE (Marzari et al., 2024) all 36 ACAS Xu networks which property &2 of Katz et al. (2017b) applies. These results are contained in Table 5, revealing that the networks in Table 3 are outliers. However, PROBBOUNDS still computes tighter sound bounds faster than e- P- computes probably sound bounds for 12 of the 36 networks.
Table 6 contains additional results for rumning PROBBOUNDS with a finer grid time budgets on the networks from Table and two additional challenging instances from Katz et al. (2017b).
30

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Table FairSquare benchmark results. The first columns indicate the neural network that is verified and the input probability distribution Px. respectively. We verify two fairness notions: demographic parity and parity of qualified persons. For each faireess notion, the first two columns contain the runtime PV and FAIRSQUARE seconds. Here, 'TO" indices timeout (900s). The last column contains the result of the verification with PV.
Parity of Qualified Persons
Demographic Parity
Benchmark Instance
Runtime (s)
Runtime (s)
net
Px
PV
FairSquare
Fair?
PV
FairSquare
Fair?
NN
independent
2
2
2
3
2N
Bayes Net
4
76
/
8
38
2N
Bayes Net 2
5
51
V
12
26
NN
independent
4
7
2.2
Bayes Net
33
11
60
NN
Bayes Net 2
6
59
17
61
NN32
independent
2
451
1
657
NN
Bayes Net
TO
40
TO
NN
Bayes Net
TO
57
TO
F.4. ACAS Xu Robustness
We first provide a more detailed description of the ACAS Xu robustness benchmark. As Converse al. (2020), we consider 25 reference inputs five for each class and allow these reference inputs to be perturbed in the first two dimensions by at most 5% of the diameter of the input space in the respective dimension. To compute bounds on the output distribution, we bound the probability of each of the five ACAS Xu classes for each of the 25 inputs. Since the ACAS Xu training data is not publicly available, we sample the reference inputs randomly.
Table 7 contains the bounds computed by PROBBOUNDS for each reference input and each output class: COC (Clear-of- Conflict), WL (steer Weak Left), WR (steer Weak Right), SL (steer Strong Left), and SR (steer Strong Right). The table reveals that the ACAS Xu network Ni,1 could tend classify inputs Clear-of-Conflie (COC), regardless of the class assigned to the reference input. This insight does not agree with the insight drawn by Converse al. (2020). However, both results are based on tiny sample of the input space of only 25 points. Obtaining valid results requires considering significantly larger sample of the input space or quantifying global robustness (Katz et al., 2017a).
F.5. CSincome
We provide additional details on the MiniACSIncomee benchmark, including how we construct the dataset and train the networks.
1. BENCHMARK
To create probabilistic verification problems of increasing difficulty, we consider an increasing number of input variables from ACSIncome. The smallest instance, MiniACSIncome-lI 1, only contains the binary 'SEX' variable. In contrast, the largest instance, MiniACSIncome-8, contains 'SEX' and seven more variables from ACSIncome, including age, education, and working hours per week. We train neural network with single layer of ten neurons for each Mini MiniiCCSneom--i, i E [8]. For MiniACS Income-4, we additionally train deeper and wider networks to investigate the scalability of PV with respect to the network size. We fit a Bayesian Network to the MiniACSIncome-& dataset to obtain an input distribution. The process is described in detail in Appendix F.5.3. We use this distribution for all MiniACSIncome-i instances by taking the variables not contained in MiniAACIncoom-i as latent variables. The verification problem is then to verify the demographic parity of a neural network with respect 'SEX' under this input distribution.
31

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Table 5. Comparison of PROBBOUNDS and E-PROVE for ACAS Xu safety. A PROBBOUNDS column is marked with an arrow (+) if PROBBOUNDS computes lighter upper bound than e-PROVE within certain time budget. If this not the case for any time budget. the e- E-PROVE entry is marked with an arrow (+). In total, PROBBOUNDS computes tighter upper bounds within 60s in 16 cases. In 12 cases, even computes tighter bound faster than 8- PROVE.
PROBBOUNDS
E-PROVE
10s
30s u.
60s
99.9%
confid.
net
É,
f,
a
Rt
IP2
N2
0.03%, 3.19%
0.09%, 2.50%
0.16%, 2.09%
2.58%
64s
N2.2
0.00%, 3.86%
0.08%, 2.93%
0.24%, 2.64%
2.49%
44s
N2,3
0.51%, 3.46%
0.85%, 2.98%
1.00%, 2.68%
3.58%
55s
N2.4
0.00%, 2.72% +
0.03%, 2.13%
0.04%, 2.06%
2.78%
66s
N2.5
0.03%, 4.23%
0.12%,
0.34%,
3.06%
47s
N2.6
0.01%, 3.67%
0.16%, 2.89%
0.30% 2.50%
2.32%
45s
N2,7
0.28%, 5.56%
0.84%, 4.87%
1.26% 4.32%
4.04%
47s
N2.8
0.96%,
1.23%,
2.79%
3.28%
53s
N2.9
201%,2885%
0.08%, 1.65%
0.10%,
0.58%
11s
N3.1
0.23%, 4.25%
0.46%, 3.41%
0.88%,
2.84%
40s
N3,2
3.57%
0.00%, 1.49%
0.00%
0.00% +
1s
Na.3
2.0%,
0.00%,1.91%
0.00%,0.87%
0.00%
1s
N3.4
3.27%
2.07%
1.13%,1.337
1.36% + 31s
Na.5
2331%,2909%
2.29%
0.63%, 2.02%
2.67%
42s
N3.6
100%,6.23%
5.42%
0.01%, 5.19%
2.69%
32s
Na.7
2.00%,,.76%%
0.00%, 4.59%
3.36%
0.91%
30s
N3.8
0.15%,5.455
0.21%, 4.43%
3.48%
2.79%
61s
N3.9
228%,4.83%
1.0%%
3.72%
3.52% + 32s
N4.1
3.0%%,
1.96%
0.04%, 1.57%
1.16% + 26s
N4,2
0.00%,2.625 2.62%
0.00%,1.699 1.69%
0.00%, 1.36%
0.00% + 1s
N4.3
0.17%, 2.92%
0.34%, 2.65%
0.61%, 2.27%
2.43%
41s
N4.4 0.05%,2.47%
0.17%. 2.22%
0.27%. 1.98%
1.94%
40s
N4,5
0.00%, 4.52%
0.14%, 3.50%
0.46%, 3.04%
2.85%
41s
N4.6
0.32%, 4.54%
0.89%, 3.54%
1.16%
3.22%
39s
N4.7
4.19%,4.7%%
0.31%, 3.32%
0.55%, 2.92%
2.58%
30s
N4.8
3.91%
0.56%, 3.20% +
2.84%
3.51%
52s
N4,9
0.00%,
0.00%, 0.00%,1.969 1.96%
0.00%, 1.55%
0.39% +
11s
No.1
102%%2260%%
0.30%, 2.13%
0.42%, 1.99%
2.14%
35s
N5,2
217%,,266%%
0.47%, 2.03%
0.52%, 1.92%
3.22%
678
No.3
0.00%, 1.72%
0.00%, 0.73%
0.00%, 0.56%
0.00% +
1s
Ns.4
2.01%,29949
0.14%, 2.34%
0.22%. 2.08%
2.31%
54s
N5.5
1774%,3299%
1.32%, 2.68%
1.37%, 2.62%
2.77%
33s
N5.6
0.18%,
4.46%
0.78%. 0.78% 3.19%
0.98%. 3.02%
4.82%
74s
No.7
1.19%, 4.63%
1.74%, 4.02% +
1.99%, 3.75%
4.27%
45s
No.8
4.16% 0.89%,
1.31%. 3.39%
1.55%. 3.10%
3.38%
42s
N5.9
3.75%
1.24%. 3.06%
1.41%, 2.89%
3.06%
36s
# +
4
8
5
20
32

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Table Extended PROBBOUNDS results for ACAS Xu safety.
Timeout
10s
30s
1m
Φ
net
u
t, u
422
N4.3
0.17%, 2.92%
2.74%
0.34%, 2.62%
2.30%
0.61%, 2.27%
1.66%
N4.9
0.00%, 3.36%
3.36%
0.00%, 1.96%
1.96%
0.00%, 1.55%
1.55%
N5.8
0.89%, 4.16%
3.26%
1.31%, 3.39%
2.08%
1.55%, 3.10%
1.55%
N1.9
0.00%, 98.71%
98.71%
0.00%, 94.18%
94.18%
0.00%, 87.62%
87.62%
N2.9 48
0.00%, 76.39%
76.39%
0.00%, 65.83%
65.83%
0.00%, 58.11%
58.11%
10m
1h
net
ł, u
u
ł, u
u
N4.3
0.95%, 1.93%
0.98%
1.12%, 1.75%
0.63%
N4.9
0.03%, 0.52%
0.48%
0.08%, 0.29%
0.21%
Ns.8
1.90%, 2.66%
0.76%
1.97%, 2.57%
0.60%
Φ7
N1.9
0.00%, 51.93%
51.93%
0.00%, 30.71%
30.71%
Q8
N2.9
0.00%, 34.60%
34.60%
0.00%, 15.33%
15.33%
F.5.2. DATASET
The MiniACSInccmee benchmarks are built by sampling about 100000 entries from the ACS PUMPS 1-Year horizon data for all states of the USA for the year 2018 using the folktables Python package (Ding al., 2021). In line with ACSIncome (Ding et al., 2021), only sample individuals older than 16 years, with yearly income of least $100, reported working hours per week of at least 1, and "PWGTP' (more details in Ding et al. (2021)) of at least 1. In total, our dataset contains 102 621 samples.
Variable Order. For obtaining the benchmark MiniACSInnomeeii E [8], we select input variables in the following order: 'SEX', 'COW', 'SCHL', 'WKHP", 'MAR', 'RACIP", 'RELP', 'AGEP'. We choose 'SEX' the first variable so that we verify the faimess with respect 'SEX' on every benchmark instance. The order of the remaining variables is chosen based on each variable's expected predictive value and the number of discrete values. In particular, we select 'COW" (class of work), 'SCHL' (level of education), and 'WKHP' (work hours per week) first, as we consider these variables to be more predictive than 'MAR' (marital status), 'RACIP' (races of a person), 'RELP' (relationship), and 'AGEP' (age of a person). The variables are ordered by their number of discrete values within these groups of expected predictive value. For example, 'COW" has nine categories, while 'WKHP' has 99 possible integer values.
Table 8 contains the number of input dimensions and the total number of discrete values in each MiniACSIncome-i input space. The input space contains more dimensions than input variables due to the one-hot encoding of all categorical variables.
F,5.3, INPUT DISTRIBUTION
The Bayesian Network input distribution of MiniACSIncome has the network structure depicted Figure For using 'AGEP' as a parent node, we summarised the age groups 17-34, 35-59, and 60-95. This means that the conditional probability table of 'MAR' does not have 78 entries for 'AGEP', but three, corresponding the ranges 17-34, 35-59, and 60-95.
To fit the Bayesian Network, we walk the network from sources to sinks and fit each conditional distribution to match the empirical distribution of the data subset that matches the current condition. For example, for fitting the conditional distribution 'SCHL' given 'SEX=1', 'RACIP=1', we select the samples the dataset having 'SEX=1' and 'RACIP=1' and fit the conditional distribution of 'SCHL' to match the empirical distribution of these samples. We use categorical distributions for all categorical variables and 'WKHP". For 'AGEP', we fit mixture model of four truncated normal
33

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Table 7. ACAS Xu robustmess results. We report the lower and upper bounds (2, u) PROBBOUNDS computes for the probability that perturbed input is classified the target label. and the runtime in seconds (RU) of PROBBOUNDS for computing these bounds. For each combination of unperturbed label, input, and target label, we run PROBBOUNDS until the difference netween the lower and the upper bound is 0.1%% %%.
Rt
Os
1s
48
Os
0s
1s
Is
2s
65s
1s
12s
Is
123s
Is
4s
138s
16s
28s
58%
39%
34s
88s
96
41s
68
SR
0.0%
0.0%. 0.0%
2.8%. 2, 2.8%
0.0%. 0.0%
0.0%. 0.0%
0.0%. 0.0%
0.2%. 0.3%
0.8%. 0.9%
3.5%, 3. 3.6%
0.1%. 0.2%
18.5 185%% 18.6%
0.0%. 0.1% 1s
3 3.2%. 3.3%
0.0%, 0.1%
0.7%. 8%
6. 6.7%. 6.8%
0.5%. 0.6%
5.0%. 5.1%
4.0%, 4.1%
4.8% 4.9%
3.6%. 3.7%
5.0%. 5.1%
1.5%. 1.6%
1.4%. 1.5%
7.4%. 7.5%
u
0.0%.
Ri
Os
1s
12s
0s
0%
39
3s
11s
60
5s
28
12s
64s
11s
12s
85
266
2s
68
15s
30s
56
15.8 15.8% 15.9%
SL
0.0% 0.0%
0.0% 0.0%
2.2%
0.0%. 0.0%
0.0%. 0.0%
3 3.6% 3.7%
1.4%, 1.5%
3.8% 3.9%
4.6%. 4.7%
0.0% 0.0%
0.0% 0.1%%
0.0%, 0.1%
0.3% 0.4%
3.0% 3.1%
4.8%, 4.9%
0.7%, 0.8%
2.1% 2.2%
5.6%. 5.7%
3.0% 3.1%
0.0% 0.1%%
1. 1.2%, 1.3%
2. 2.6%, 2.7%
1.0% 1.1%
3.7%, 3.8%
2.1
Target Label
Os
1s
48
Os
0s
2s
3s
4s
524
198
2s
213s
2s
95
155s
44s
41s
135
65%
71s
95
119s
10s
WR
0.0%
0.0%, 0.1%
1.9% 2.0%
0.0%, 0.0%
0.0%, 0.0%
4.7%. 4.8%
3.0%, 3.1%
3.6%, 3.7%
2.6%. 2.7%
1s 0.0%. 0.1%
3.4%. 3.5%
1.7% 1.8%
1.9% 2.0%
3.4 3.4%, 3.5%
4.2%, 4.3%
4.8%, 4.9%
3.7%, 3.8%
15s 6.5% 6.6%
5.2% 5.3%
5.4%, 5.5%
5.2%. 5.3%
5s 5.7%, 5.8%
4.7%. 4.8%
3.7%. 3.8%
9.1%. 9.2%
4 uu
0.0%.
Os
1s
6s
0s
0s
38s
2s
8s
52s
1s
1s
28s
2s
7s
77s
26s
948
25s
3s
9s
62s
2s
WL
0.0%, 0.0%
0.0%, 0.0%
1.3%, 1.4%
0.0%, 0.0%
0.0%, 0.0%
1.6%, 1.7%
2.3%, 2.4%
1.1%, 1.2%
5.4%, 5.5%
2.9%, 3.0%
18s 0.0%, 0.0%
1.5%. 1.6%
3s 0.0%. 0.1%
25 1.8%, 1.9%
0.8%, 0.9%
2.3%, 2.4%
1.1%, 1.2%
2.8% 2.9%
3.3%, 3.4%
13s 1.7%, 18%
5s 0.0%. 0.1%%
7s 0.9%, 1.0%
35 2.5%, 2.0%
0.7%, 8%
0.2%, 0.3%
8
3x
0s
0s
2s
3s
3s
18s
2x
1s
22s
3s
10s
18s
6s
COC
100%. 100%
99 9%,, 100%
91.7% 7%, 91.8%
100%. 100%
100%, 100%
9%, 090
92.9%. 93.09 03.0%
90 4%, 90.5%
83.6%. 83.7%
96. 8%, 96.9%
2%. 62.3%
96. 6%. 96.7%
94.8% 8%, 94.9%
94.3%, 94.4%
91. 01.1%, 1%, 91.1%% 1%
81.1%, 81.21 21
93.8%, 93.9%
(3.3%, 83.4%
81.8%. 81.9%
84. 1.00% 85.0%
91.0%. 91.0%
87.0%. 87.1%
88. 4%, 88.5%
93. 0%, 98
79.3% 39.3%, 79.4%
u,u
Reference Input
Input
3
4
5
2
3
4
5
2
3
4
2
2
3
Label
COC
COC
COC
COC
COC
WL
WL
WL
WI.
WI.
WR
WR
WR
WR
WR
SL
SL
SL.
SL.
SR
SR
SR
SR
SR
34

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Table MiniACSIncome details and verification results.
#Input Variables
1
2
#Input Dimensions
2
10
34
35
40
49
67
68
#Discrete Values
2
16
382
38K
190K
1.7M
31M
2B
PV Runtime
16s
44s
127s
231s
374s
699s
1383s
TO
10-Neuron Network Fair?
X
X
X
X
X
X
SEX
RACIP
SCHL
AGEP
MAR
WKHP
COW
RELP
Figure 6. MiniACSIncome Bayesian network structure.
35

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
distributions that we discretise to integer values.
Figure depict the marginal distributions of 10000 samples from the fitted Bayesian Network and the empirical marginal distributions of the MiniACCIIncome- dataset. Figure 8 contains the correlation matrix of the same sample compared to the correlation matrix of MiniACSInccom--8 The Bayesian Network approximates the empirical marginal distribution and the correlation structure of MiniACSInccoe-88 reasonably well.
Note that for real-world fairness verification, the input distribution should not be fitted to the same dataset on which the neural network to verify is trained on. Instead, the imput distribution needs to be carefully constructed by domain experts. For fairnsss audits, the input distribution could also be designed adversarially by fairness auditing entity.
F.5.4. TRAINING
All Mini Incoome neural networks are trained on 56% split of the MiniACSIncome- dataset into training, validation, and testing data. This split is identical for all MiniACSIncome-i datasets. All networks are trained using: the Adam optimiser (Kingma & Ba, 2015), cross entropy as loss function, no L2 regularisation (weight decay). 31 = 0.9, 82 = 0.999, E = 10 8 as suggested by Kingma Ba (2015), and a learning rate decay by 0.1 after 2000 and 4000 iterations. The learning rate and the number of training epochs are contained in Table 9, We perform five random restarts for each network and select the network with the lowest cross-entropy on the validation data.
Table 10 contains the accuracy, precision, and recall for the overall test set, the persons with female sex in the test set, and the persons with male sex in the test set. Additionally, the table contains whether a network satisfies the demographic parity fairness notion according to PV.
We used OPTUNA (Akiba et al., 2019) for an initial exploration of the hyperparameter space but did not apply automatic hyperparameter optimisation obtain the final training hyperparameters.
F.5.5, EXTENDED RESULTS
We provide concrete results the effect of the network size on the runtime of PV on the MiniACSIncome benchmark. Figure 9 displays the runtime of PV for Incomme networks of various sizes. The studied networks include wide single-layer networks of up to 10 000 neurons and deep networks of up to 10 layers of 10 neurons. As the figure shows, PV is largely unaffected by the size of the MiniACSIncome-4 networks. This is unexpected since the network size indirectly determines the performance of PV through the complexity of the decision boundary. However, larger networks need not necessarily have a more complex decision boundary, and large networks do not provide a performance benefit for MiniACSSncome-4, apparent from Table 10. Thoroughly exploring the impacts of network size requires more intricate datasets for which larger networks actually provide a benefit.
G. Heuristics for PROBBOUNDS
In this section, we experimentally compare the LONGESTEDGE, BABSB, and BABSD-LONGESTEDGER heuristics, as well as INTERVALARITHMETICC and CROWN to justify our decision to use BABSB and CROWN Section 6.
G.I. Experiments
We experimentally compare the LONGESTEDGE, BABSB and BABSB-LONGESTEIN heuristics to justify our selection in Section 6. Concretely, we study BABSS-LONGESTEDDEE 10. Additionally, we compare INTERVALARITMMETC to CROWN when used as COMPUTEBOUNDS procedure of PROBBOUNDS. To perform the comparison, we run the different variants of PV the FairSquare benchmark, as described in Section 6.1.
Figure 10 compares the LONGESTEDGE, BABSB and BABSB-LONGESTEDOE 10 heuristics. It contains the runtime of PV when using SELECTPROB, CROWN and either LONGESTEDGE. BABSB, or BABSB-LONGESTED EDGE- 10 as SPLIT heuristic. While using LONGESTEDGE is faster for four easy-to-solve benchmark instances, using it only allows solving eight instances from the FairSquare benchmark, while using BABSB allows solving all 18 instances. Using BABSB- LONGESTEDGE-1O 10 also allows us to solve all benchmark instances while requiring slightly more time per benchmark instance than using BABSB
Figure 11 contains the runtime of PV when using SELECTPROB, BABSB and either
or CROWN
36

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
SEX
COW
SCHL
50
60
20
40
50
15
Percent
Percent
40
Percent
30
30
10
10
10
0
0
0.0
0.5
1.0
0.0
2.5
5.0
7.5
10 RELP
20
MAR
RAC1P
80
50
40
60
40
Percent
Percent
Percent
30
30
20
20
20
10
2
4
0.0
2.5
5.0
7.5
0
5
10
15
AGEP
2.5
2.0
Percent
1.5
1.0
0.0
20
30
40
50
60
70
80
90
WKHP
dataset
40
generated
original
30
Percent
20
10
20
40
60
80
100
Figure 7. MiniACSIneome Bayesian network marginal distributions. The 'generated" data is sampled from the Bayesian Network, while the 'original' data is the MiniACSlncoom--8 dataset.
37

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Population Model
Training Data
Difference
0.75
COW
COW
COW
SCHL
SCHL
SCHL
WKHP
WKHP
RAC1P
-0 -0.29ACCP
-0.25
RELP
RELP
RELP
-0.50
-0.50
-0.50
COW
SCHL
MAR
MAC1P
RELP
AGEP
-0.75
SEX
COW
SCHL
Videe
MAR
PMC1P
-0075
SEX
COW
SCHL
WIOHP
MAR
RACIP
RELP
AGEP
-0.7
-1.00
-1.00
-1.00
Figure MiniACSIncome Bayesian network - correlation matrix. "Population Model' denotes the Bayesian Network, while
"Training Data" stands for the full MiniACSIncome-88 dataset.
Table MiniACSInncome training hyperparameters.
Dataset
Architecture
Learning Rate
Epochs
MiniACSIncome-11
1x 10
0.0001
1
MiniACSIncome-2
1x 10
0,001
2
MiniACSIncome-3
1x10
0.001
3
MiniACSInccome-4
1x10
0.001
4
MiniAACInncome-5
1x10
0.001
5
MiniAACInccome-6
1x10
0.001
3
MiniAACIIncome-7
1x10
0.001
3
MiniACSIIncome-8
1x10
0.001
3
MiniACSInccome4
X 1000
0.001
2
MiniACCSIncome4
X2000
0.001
2
MiniACCSIncome44
33000
0.001
2
MiniACSIncome-4
4x0000
0.001
2
MimiACSIncome-
5x0000
0.001
2
MiniACSInccome
1 6000
0.001
2
MiniACSIncome-4
1 7000
0.001
2
MiniACSIncome-4
8000
0.001
2
MiniACSIncome--
9X0000
0.001
2
MiniACSInccome44
X 10000
0.001
2
MiniACSIncome-4
2x 10
0.001
2
MiniACSIncome
3x 10
0.001
2
MiniACSInccome-4
4x10 10
0.001
2
MiniACSIncome-4
5x10
0.001
2
MiniACSIncome-4
6x10
0.001
2
MiniACSIncooe-4
7x10
0.001
2
MiniACSIncome
8x10
0.001
2
MiniACSIncome
9x10
0.001
2
MiniACSIncome-4
10
0.001
2
38

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Table 10. MiniACSIncome neural networks. The abbreviation 'mACSI-i' stands for MiniACSIncome-i. We report the accuracy (A), precision (P), and recall (R) of each trained network (Net) for the whole test dataset (Overall). the persons with 'SEX=2 in the test set (Female). and the persons with 'SEX=1' in the test set (Male). Additionally, report whether the network satisfies the demographic parity faimess notion according to PV (Fair?).
Overall
Female
Male
Dataset
Net
R
A
P
A
P
R
Fair?
1
1x10
57%
44%
63%
72%
0%
44%
44%
100%
X
MACSI-2
1x10
65%
55%
14%
71%
0%
58%
55%
23%
X
MACSI-3
1x10
73%
67%
48%
76%
65%
35%
69%
68%
55%
X
mACSI-4
1x10
75%
68%
60%
78%
66%
48%
72%
69%
66%
X
MACSI-5
1x10
76%
69%
63%
79%
65%
53%
74%
71%
69%
X
MACSI-6
1x10
77%
69%
63%
79%
65%
55%
74%
72%
68%
X
mACSI-7
1x10
77%
71%
64%
79%
67%
50%
76%
72%
72%
X
MACSI-8
1X10
78%
70%
68%
80%
67%
56%
76%
71%
75%
?
MACSI-4
100000
75%
71%
54%
79%
70%
44%
72%
71%
61%
X
MACSI-4
1X2000
75%
65%
67%
78%
61%
60%
72%
67%
71%
MACSI-4
1x0000
74%
63%
71%
77%
58%
67%
72%
66%
73%
MACSI-4
Xx000
75%
71%
55%
79%
69%
44%
72%
71%
61%
mACSI-4
5000
75%
69%
58%
78%
71%
39%
73%
68%
69%
MACSI-4
6000
75%
69%
59%
79%
69%
44%
72%
68%
67%
MACSI-4
1x7000
75%
66%
64%
78%
62%
55%
72%
68%
68%
MACSI-4
80000
75%
66%
64%
78%
63%
55%
72%
68%
69%
X
MACSI-4
1X9000
75%
70%
53%
78%
66%
47%
71%
72%
56%
X
MACSI-4
1x10000
75%
67%
63%
79%
69%
45%
72%
66%
73%
X
MACSI-4
2x10
75%
67%
59%
78%
65%
48%
72%
69%
65%
X
MACSI-4
3x10
75%
68%
58%
79%
67%
47%
72%
69%
65%
X
MACSI-4
4x10
75%
68%
58%
78%
66%
46%
72%
69%
66%
X
MACSI4
5x10
75%
68%
59%
78%
67%
47%
72%
69%
66%
X
MACSI-4
6x10
75%
67%
61%
78%
67%
46%
72%
67%
70%
X
mACSI-4
7x10
75%
65%
66%
78%
63%
52%
72%
65%
74%
X
mACSI-4
7x10
75%
67%
59%
78%
65%
46%
72%
68%
67%
X
MACSI-4
9x10
75%
67%
59%
78%
65%
47%
72%
68%
67%
X
MACSI-4
19x10
75%
67%
61%
78%
64%
49%
72%
68%
68%
X
10
PV (Ours)
Runtime (min)
10a
103
10a
10
# Parameters
Figure 9. MiniACSIncome network size results. The plot depicts the runtime of PV for MiniACSIncome-4 networks of varying sizes.
39

---

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound
Timeout
LONGESTEDGE
BABSS-LLNN
10a
BABSB
Runtime (s)
10a
109
2
4
6
8
10
12
14
16
18
# Solved Instances
Figure 10. SPL.TT heuristic comparison the FairSquare benchmark. The timcout for the FairSquare benchmark is 15min.
Timeout
INTERVALARTHMETIC
CROWN
102
Runtime (s)
10
10
2
4
6
8
10
12
14
16
18
# Solved Instances
Figure COMPUTEBOUNDS procedure comparison on FairSquare benchmark. The timeout FairSquare benchmark is 15min.
as COMPUTEBOUNDS procedure in PROBBOUNDS As the figure reveals, using CROWN allows PV to terminate faster on all benchmark instances from the FairSquare benchmark. Furthermore, using INTERVALARITHMER only allows PV to solve 14 benchmark instances, while CROWN enables PV solve all 18 benchmark instances.
40


Reviews:
[{"review_id": "TbniH4XZPX", "reviewer": "Reviewer_BFqm", "summary": "This paper proposes a probabilistic neural network verification method through lower and upper bounds of probabilities of outputs. By branch and bound and bound propagation, it can run faster than other verifiers.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer BFqm for their review. We believe there has been a misunderstanding of our definition of soundness that underlies most of the review. \n\n> The definitions of soundness [...] in this paper seem to be quite different from the commonly used ones in the neural network verification community [...]. In this sense, probabilistic verification seems to be a false proposition.\n\n**We actually use the standard definition of soundness**, as expressed by Definition 3.2 in our paper.\nThe review appears to assume that we provide what we call a \"probably sound\" algorithm, for which a verifier output of true means that the output specification *likely* holds, typically with a certain confidence level (PAC-style guarantee). \nWe instead provide a ***definite* guarantee for a *probabilistic* statement**. \n\nWe agree that the term \"probabilistic verification\" can be misleading.\nTherefore, we propose to change the title of our paper to \"Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound\" and similarly modify our abstract and introduction to avoid this source of confusion.\nIf there are further suggestions where our presentation can be improved in this regard, we would be happy to incorporate them.\n\nTo summarise, our paper provides a **sound algorithm** for solving **probabilistic verification problems** (PVPs), that is, proving statements involving probabilities over neural networks, such as fairness statements of the type of Equation (1).\nOther methods, like hypothesis testing, provide PAC-style guarantees for PVPs that only hold with a certain probability.\n**Unlike these methods, our guarantees hold with certainty.**\n\n> In Eq(3), I wonder whether each support of $P_{x^{(i)}}$ is assumed to be not overlapped.  \n> The proof of Theorem 5.1 seems to hold with the assumption of uniform distribution and disjoint support of each single-value distribution.\n\nWe do not require these assumptions. \nOur assumptions are summarized in Section 4.2\nIf you have concerns regarding particular steps of the proofs (Appendix C), we would be happy to discuss them in the second round of the author-reviewer discussions. \n\n> In Alg 1, it is not clear if $PB_i$ is also related to $t$ on Line 5\n\nIn Algorithm 1, $PB_i$ is not dependent on $t$.\nHowever, $PB_i$ is an instantiation of Algorithm 2 rather than a fixed value. \nNote that Algorithm 2 also has a loop counter $t$. \nWhile some $PB_i$ may advance faster than others in our implementation, the counters $t$ in Algorithms 1 and 2 are synchronized in our paper to simplify the exposition.\n\n> In Alg 2, Line 7 and Line 8 [...] conflicted with [...] Line 220.\n\nOur approach is **not based on the union bound** but rather on the third axiom of probabilities (the probability of a countable union of disjoint sets is the sum of the probabilities of these sets). \nThe third axiom of probabilities holds with equality.\n\n> Adversarial machine learning.\n\n**We consider adversarial machine learning tasks in our ACAS Xu robustness experiment.**\nUnlike probably sound verifiers, sound verifiers for PVPs (such as PV) do not currently scale to image datasets, but our work provides major advances in scaling to larger input spaces.\nWe discuss this in more depth in the rebuttal to reviewer SiXd.\n \n> [...] some important baselines are missing, e.g.[...] $\\alpha$-$\\beta$-CROWN, NNV, etc.\n\nSince **non-probabilistic verifiers can not be applied to PVPs**, it is not possible to compare our approach to these verifiers experimentally.\nFor example, it is impossible to apply $\\alpha$-$\\beta$-CROWN to MiniACSIncome, since $\\alpha$-$\\beta$-CROWN can not handle probabilities.\n\nTo position our work more clearly in the context of other verification approaches, we will add the following table to our related work section:\n\n| Method     | Deterministic Statements | Quantitative Statements (#DNN-Verification) | Group Fairness | General PVPs | Type of Verifier Guarantee | \n|---|---|---|---|---|---|\n| $\\alpha,\\beta$-CROWN, NNV | yes | no | no | no | sound |\n| Randomized Smoothing  | yes | no | no | no | probably sound (i.e., PAC-style) |\n| Hypothesis Testing | yes | yes | yes | yes | probably sound (i.e., PAC-style) |\n| ProVe_SLR (Marzari et al., 2023b) | no | yes | no | no | sound |\n| SpaceScanner (Converse et al., 2020) | no | yes | yes | yes | sound (quantitative statements), unsound (otherwise)\n| FairSquare (Albarghouti et al., 2017) | no | no | yes | no | sound |\n| PV (Ours)       | no | yes | yes | yes | sound |\n\nWe hope that this clarifies the relation between our method (PV) and other verifiers solving deterministic (non-probabilistic) verification tasks, as well as other methods mentioned in the review.\n\n>  key [...] literature is missing.\n\nThank you for mentioning this. \nWe will add the mentioned references to our discussion of probably sound approaches in Section 2 (third paragraph).", "claims_and_evidence": "The definitions of soundness and completeness in this paper seem to be quite different from the commonly used ones in the neural network verification community, where soundness usually means once the verifier gives true, the output specification will truly hold. In this sense, probabilistic verification seems to be a false proposition. I suggest the authors should clarify it clearly at the very beginning of the paper to avoid potential confusion.", "methods_and_evaluation_criteria": "- In Eq (3), I wonder whether each support of $P_{x^{(i)}}$ is assumed to be not overlapped. If so, the joint distribution is assumed to be invariant to the permutation of each distribution, which should be explicitly discussed.\n\n- In Alg 1, it is not clear if $PB_i$ is also related to $t$ on Line 5. It should be stated clearly on Line 2 as well.\n\n- In Alg 2, Line 7 and Line 8 seem to be conflicted with the statement of the right column on Line 220, where $l^t$ is the probability of a union of some sets. However, it should follow the union bound with inequality. At the same time, in Alg 2, the iteration of lower and upper bounds is assumed to be with the equality condition of the union bound, which may not hold and cause correctness issues.", "theoretical_claims": "The proof of Theorem 5.1 seems to hold with the assumption of uniform distribution and disjoint support of each single-value distribution. It holds in such special cases, however, more formal and general propositions should be derived based on formal arguments, e.g. through conformal prediction or hypothesis testing.", "experimental_designs_or_analyses": "As a neural network verification method in machine learning, experiments are expected to involve  adversarial machine learning tasks, e.g. mnist with adversarial perturbation. More can be found in VNN-COMP benchmarks in recent years. Besides, some important baselines are missing, e.g. several best non-probabilistic verifiers $\\alpha$-$\\beta$-CROWN, NNV, etc.", "relation_to_broader_scientific_literature": "Related to neural network verification.", "essential_references_not_discussed": "A key branch of probabilistic certification/verification methods in the literature is missing, i.e. randomized smoothing based neural network verification methods [1,2,3].\n\n[1] Cohen et al. Certified Adversarial Robustness via Randomized Smoothing, 2019\n\n[2] Yang et al. Randomized Smoothing of All Shapes and Sizes, 2020\n\n[3] Li et al. Sok: Certified robustness for deep neural networks, 2020", "other_strengths_and_weaknesses": "See above", "other_comments_or_suggestions": "See above", "questions_for_authors": "See above", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nMxkd4cET4", "reviewer": "Reviewer_GWj1", "summary": "The paper proposes a generic approach for the probabilistic verification of neural networks which can leverage pre-existing qualitative verification tools. To this end, the paper proposes to combine input space splitting with bound computation to compute bounds on (un)safe behavior. Purely safe/unsafe regions can then be probabilistically quantified. The paper also puts forward an argument for the completeness of the approach.\n\n## update after rebuttal\nThe authors managed to lift my concern about the theoretical assumptions and promised to clarify this misunderstanding in the paper's final draft. I trust this will happen and am thus in favour of accepting the paper.\n\nConcerning the comments from other reviewers, I believe it's important to emphasize that the verification guarantees derived in the paper are meant to hold *globally*, i.e. on large parts of the input space. It is common knowledge that NN verification for lage input spaces can (so far) only be scaled to small input dimensions and/or small NNs. Consequently, I am happy with the presented experiments. This can also be seen in other work that aims to derive global guarantees (e.g. [CAV24]).\n\n[CAV24] https://link.springer.com/chapter/10.1007/978-3-031-65630-9_17", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer GWj1 for their review, in particular their careful evaluation of our theoretical assumptions. \n\n> Theoretical Claims / Assumption 5.3\n\nIf the safe/unsafe region is not axis-aligned, indeed, Algorithm 2 can not compute the *exact* probability of safety. \nHowever, Algorithm 2 still computes a converging sequence of bounds on the unknown exact probability $p_i$. \nThe question that motivates Assumption 5.3 is when converging bounds are sufficient for solving a probabilistic verification problem. \n\nFor illustration, assume we want to show $y \\geq 0$ and have converging sequences of bounds ${(\\ell\\_t)}\\_{t \\in \\mathbb{N}}$ and ${(u\\_t)}\\_{t \\in \\mathbb{N}}$ with $\\ell_t \\leq y \\leq u_t$ for each $t \\in \\mathbb{N}$ and $\\lim_{t \\to \\infty} \\ell_t = \\lim_{t \\to \\infty} u_t = y$. \nIf the actual (exact) $y$ is zero, sequences of bounds that only converge in the limit do not suffice to prove $y \\geq 0$, since there may be no $T \\in \\mathbb{N}$ with $\\ell_T = 0$. \nHowever, if the actual value of $y$ is different from zero, knowing a finite number of iterates of ${(\\ell_t)}\\_{t}$ and ${(u_t)}\\_{t}$ always suffices to prove or disprove $y \\geq 0$. \nConcretely, there will be a $T \\in \\mathbb{N}$, such that either $\\ell_T > 0$ or $u_T < 0$, that proves, respectively, disproves $y \\geq 0$.\n\nUnfortunately, the situation does not change fundamentally if we study $y > 0$ instead of $y \\geq 0$. \nBefore, if $y = 0$, our specification actually held, but we were not able to ever prove this. \nNow, our specification $y > 0$ is actually violated if $y = 0$, but we will never be able to disprove it.\nConcretely, if ${(u_t)}_{t}$ only converges in the limit, there may be no $T \\in \\mathbb{N}$, such that $u_T = 0$.\n\nOur assumption that $f\\_{Sat}(p_1, \\ldots, p_v) \\neq 0$ corresponds to assuming $y \\neq 0$ in the discussion above. \nNote that $f\\_{Sat}(p_1, \\ldots, p_v)$ is a constant in Equation (3).  \nOur comment on studying $f\\_{Sat}(...) \\geq \\varepsilon$ instead of $f\\_{Sat}(...) \\geq 0$ means solving a different verification problem with $f'\\_{Sat}(...) = f\\_{Sat}(...) - \\varepsilon$. \nPractically, if you only want to show Equation (1) and PV seems not to be terminating for $\\gamma = 0.8$, you can run PV again with $\\gamma' = 0.81$ and find that your neural network either violates or satisfies a slightly stronger fairness specification. \n\nThe motivation for requiring $p = \\mathbb{P}[g\\_{Sat}(...) = 0] = 0$ is similar.\nHowever, the reason why it is not restrictive to assume $p = 0$ is different. \nUnlike $f\\_{Sat}(...)$, $g\\_{Sat}(...)$ is not a constant in Equation (3). \nHere, our argumentation why the assumption that $p = 0$ is not restrictive is concerned with the level sets $G\\_r = \\\\{\\mathbf{x} \\in \\mathbb{R}^n \\mid g\\_{Sat}(\\mathbf{x}, \\mathrm{net}(\\mathbf{x})) = r\\\\}$ of $g$ that have positive probability ($\\mathbb{P}[G\\_r] > 0$). \nIf $\\mathbb{P}[G\\_r] > 0$ for some $r$, $G\\_r$ also needs to have positive volume in $\\mathbb{R}^n$ (we assume a continuous probability distribution here; for discrete distributions we actually do not require the assumption p = 0 due to splitting differently). \nA set $G\\_r$ having positive volume means that the plot of $g\\_{Sat}(...)$ has a \"flat\" part where $g\\_{Sat}(...) = r$. \nUnless $g\\_{Sat}$ has a continuous range of \"flat parts\", we can find a small $\\varepsilon > 0$, such that $\\mathbb{P}[g\\_{Sat}(...) = \\varepsilon] = 0$.\nWhile there may be pathological functions that have continuous ranges of \"flat parts\", neural networks with finitely many neurons with standard activation functions can not have such continuous ranges.\n\nWe hope this discussion clarifies our assumption and why we consider it only mildly restrictive. \nWe will use your feedback and the above discussion to improve the description of Assumption 5.3 in our paper.\n\n> Unbounded Input Spaces (Q2)\n\nIndeed, qualitative verifiers rarely support unbounded input spaces. \nIn practice, we use $\\underline{\\mathbf{y}} = -\\infty$ and $\\underline{\\mathbf{y}} = \\infty$ for unbounded branches in line 5 of Algorithm 2.\nWith this, unbounded branches are never pruned, and LongestEdge always first selects dimensions that are unbounded in a branch.\nWe modify BaBSB to also first select dimensions that are unbounded in a branch. \nUnfortunately, this was not documented in our submission, but we will add this to the last paragraph in Section 4.1. \n\nThe FairSquare benchmark (Section 6.1) features an unbounded input space (discussed in Appendix F.2.1). \n\n> Related Work: Individual Fairness (Kim et al.)\n\nBesides what was already noted by the reviewer, Kim et al. study individual fairness, which is a non-probabilistic fairness specification. \nTherefore, the work of Kim et al. is more closely related to the papers of Marzari et al. (2023a, 2023b, 2024), than to our approach. \nNonetheless, this paper is important related work and we will incorporate it into our discussion of #DNN-verification in Section 2.", "claims_and_evidence": "The proposed approach comes with correctness and completeness claims (see Theoretical Claims) and is evaluated on multiple benchmark sets that compare the approach to competing techniques (see Methods and Evaluation Criteria).\nI find the empirical evaluation convincing, my concerns about the theoretical claims are discussed in below.", "methods_and_evaluation_criteria": "The benchmarks seem well chosen to me. The work does not reproduce all results from competing papers on the same machine, but instead reuses the numbers of other authors while using a weaker machine for the own experiments. While this is not ideal, it seems to me the evaluation is nonetheless sound and clearly demonstrates the superority of the approach at hand.", "theoretical_claims": "The paper makes two theoretical claims: Soundness (Corollary 5.2) and Completeness (Theorem 5.5).\nWhile I agree with the former, I am worried about the assumption necessary for completeness (Assumption 5.3).\nMy hope is that we can resolve this issue through the rebuttal in which case I'm happy to raise my score:\n\nThe verification problem as specified in (3) requires that $f(p_1,\\dots,p_v)$ must be non-negative where $p_i$ is the probability that some $g^{(i)}(\\dots)$ is non-negative. Assumption 5.3 now requires that $f$ is never zero and the probability of $g$ being zero is zero. It is then noted that this assumption is only \"mildly restrictive\" as we can strengthen (3) to be a constraint of the form $\\geq \\varepsilon$.\nIt seems to me, that this is beside the point: Of course, I can add $\\varepsilon$ to $f$, but in most cases (especially the ones discussed in the paper) $f$ and $g$ are continuous and then there will be other inputs for which $f$ becomes zero (of for which $g$ becomes zero and which do not have zero probability).\nMore intuitively: It seems to me that it is quite a natural phenomenon that the boundary between the safe and unsafe regions may not be axis-aligned. In this case, axis-aligned splitting as done in this paper *cannot* derive exact probability bounds but only approximate them.\nIt seems to me a more natural assumption for Theorem 5.5 might be simply that it is complete for open properties (i.e. $>$ in both equations in (3))? Alternatively, it seems to me at the very least this restriction warrants further discussion.", "experimental_designs_or_analyses": "From reading of Chapter 6 the experimental design and the derived conclusions seem sound to me.", "relation_to_broader_scientific_literature": "There is relatively little literature on probabilistic verification of neural networks which, in my view, makes this contribution all the more welcome. The few papers that do exist are cited and are used for comparison in Section 6. The presented approach clearly outperforms alternative techniques.", "essential_references_not_discussed": "While it should probably be deemed concurrent literature, a recent ICSE paper by Kim et al. [1] proposes the same approach of bounding probabilities [1]. In particular, just like PV (Algorithm 1) the paper also bounds probability by computing hyperrectangles which are fully safe/unsafe (see Algorithm 1 and Section IV in [1]). However, this paper is specific to fairness and hence less broad in its scope.\nMoreover, the paper was first published on arXiv on 5th September 2024...\n\n[1] https://arxiv.org/abs/2409.03220", "other_strengths_and_weaknesses": "A major strength of the paper is its generality:\nThe approach supports both discrete and continuous input spaces, a broad range of probability distributions and builds upon off-the-shelf tools for qualitative verification. In particular, this allows the approach to benefit from future improvements in verification technology.", "other_comments_or_suggestions": "In Example A.1 you reformulated demographic parity. It seems to me, that the problem would turn out to be computationally easier if the division was resolved by multiplying the divisor on both sides of the inequality (admissible due to non-negativity) and then subtracting $\\gamma$*divisor. Is there any particular reason you did not do this?", "questions_for_authors": "**(Q1)** Am I missing something about assumption 5.3. or is it indeed more restrictive than discussed in the paper? If so, might a focus on completeness for open properties be a more natural formulation?  \n**(Q2)** You mention support for unbounded hyberrectangles. I am under the impression that this is not something typically supported by the qualitative verification tools used by the approach. How do you handle this in practice? Did you have any benchmarks for this setting?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zGZgIVbTTo", "reviewer": "Reviewer_8dyc", "summary": "This paper proposed a branch & bound and interval propagation based probabilistic verification method for neural networks. This paper provides a sound verification methodology and speed up comparing to previous neural network verification techniques in mainstream neural network verification benchmarks.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer 8dyc for their review. We address the questions posed in the review below.\n\n> 1. The updating strategy for upper and lower bounds based on probabilistics need more clearification. Why we can directly use the probabilistic to refine the interval?\n\nWe assume that this question refers to Lines 7 and 8 of Algorithm 2. Please clarify in case the question is referring to a different part of our paper. We can add the probability of $\\mathcal{X}\\_{\\mathrm{Sat}}^{(t)}$ to the lower bound, since we know that $g\\_{\\mathrm{Sat}}(\\mathbf{x}, \\mathrm{net}(\\mathbf{x}) \\geq 0$ for $x \\in \\mathcal{X}\\_{\\mathrm{Sat}}^{(t)}$. This is, in turn, due to the soundness of ComputeBounds (concretely, CROWN or interval arithmetic in our paper). We can compute $\\mathbb{P}[\\mathcal{X}\\_{\\mathrm{Sat}}^{(t)}]$ directly, since $\\mathcal{X}\\_{\\mathrm{Sat}}^{(t)}$ is a union of disjoint hyperrectangles. Because of this, we can leverage the third axiom of probabilities (i.e. the probability of a countable union of disjoint sets is the sum of the probabilities of these sets). The probability of each hyperrectangle can be computed exactly due to our assumptions on the probability distributions that are described in Section 4.2.\n\n> 2. The branch-and-bound and interval propagation methods are widely used in neural network verification tools, and their properties have been explored a lot. This paper seems like merging them together, lacking of new insights.\n\nBranch and bound and bound propagation are indeed widely used for deterministic neural network verification. However, this is not yet the case for verifying *probabilistic* specifications for neural networks. \n**We use these tools and apply them to a new problem** (solving *probabilistic* neural network verification problems). \nIn this context, our paper provides the following new insights:\n 1. We apply branch and bound (BaB) and bound propagation (BP) for solving probabilistic neural network verification problems, a class of problems to which these techniques have not yet been applied to.\n 2. We conduct a thorough theoretical analysis of our BaB and BP-based approach. To the best of our knowledge, there are no previous results on the theoretical properties of BaB and BP for *probabilistic* verification problems.\n 3. Our experiments demonstrate that our proposed approach (based on BaB and BP) provides a substantial runtime advantage for solving *probabilistic* verification problems. The magnitude of this runtime advantage is a surprising novel insight.\n\n> 3. As previous listed, the paper experiment needs more ellaboration. I do not understand the experiment setting of table 2. What is the meaning of the percentages in neural network verifications? Why not use the same setting for the baselines?\n\nThe percentages in Table 2 are probabilities given as percentages. We will clarify this in the table caption. \nThe \"VR\" percentages in this table are the exact probabilities, that is, the verification result of quantitative verification. \nThe probabilities for ProbabilityBounds are pairs of lower and upper bounds on these values. \nThe percentages for $\\varepsilon$-ProVe are 99.9% confidence upper bounds on these values. \n**Overall, these percentages are *results*, not *settings* of the verifiers.** \n\nIf the remark regarding using the same settings for the baselines refers to the timeout for ProbabilityBounds (10s, 1m, 1h): these settings are not applicable for ProVe\\_SLR and $\\varepsilon$-ProVe, since these algorithms do not provide intermediate sound results. \nThis is one of the advantages of ProbabilityBounds that we seek to demonstrate in Table 2.\n\n> [Weakness:] Lack of comparisons of non-probabilistic verification tools.\n\nSince **non-probabilistic verifiers can not be applied to probabilistic verification problems**, it is not possible to compare our approach to them experimentally.\nFor example, it is impossible to apply $\\alpha$-$\\beta$-CROWN to the FairSquare benchmark, since $\\alpha$-$\\beta$-CROWN can not handle probabilities.\n\nTo position our work more clearly in the context of other verification approaches, we provide the following table:\n\n| Method     | Deterministic Statements | Quantitative Statements (#DNN-Verification) | Group Fairness | General Probabilistic Statements |  \n|---|---|---|---|---|\n| $\\alpha,\\beta$-CROWN, NNV | yes | no | no | no | \n| ProVe_SLR (Marzari et al., 2023b) | no | yes | no | no | \n| SpaceScanner (Converse et al., 2020) | no | yes | yes | yes | \n| FairSquare (Albarghouti et al., 2017) | no | no | yes | no | \n| PV (Ours)       | no | yes | yes | yes | \n\nThe rebuttal for reviewer BFqm includes an extended version of this table that we will add to our related work section.\nWe hope that this clarifies the relation between our approach and non-probabilistic verifiers.\nIf there remain further questions, we would be happy to address them in the second round of the author-reviewer discussion.", "claims_and_evidence": "The main claim of this paper is the soundness of its verification technique. As the branch and bound technique and interval propagation is widely used in nerual network verification, the soundness proof looks convincing to me.", "methods_and_evaluation_criteria": "Ths benchmark datasets are currently widely-used in neural network verification tasks, and shared by a group of work in this area. The benchmark is meaningful in this area. The proposed method follows the previous working diagram to perform the verification, which satisfies the current verification application.", "theoretical_claims": "The following parts are checked and I think they are ok:\n\n- Soundness of verirication.\n- Completeness proof under certain condition from 5.3.", "experimental_designs_or_analyses": "Yes, I have checked the experiment setting. \n\n1. The benchmark selections align with previous works, and are well-known in this area.\n\n2. The comparision of baseline and the new methods are confusing: I do not understand the data listed in the table, especially these percentages. This part need to be refined and more ellaboration.", "relation_to_broader_scientific_literature": "This paper is related to a group of work on neural network verification based on abstract interpretation and abstract refinement. The interval refinement can be viewed as a kind of abstract refinement.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\n\n- This paper proposed an efficient probabilistic verification technique for neural networks, which can exploit the parallism of GPUs.\n- This method can be proved to be sound and complete(under some reasonable assumptions).\n\nWeakness:\n\n- The proposed idea is quite straightforward based on interval propagation and branch-and-bound. \n- Lack of comparisons of non-probabilistic verification tools.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. The updating strategy for upper and lower bounds based on probabilistics need more clearification. Why we can directly use the probabilistic to refine the interval?\n\n2.The branch-and-bound and interval propagation methods are widely used in neural network verification tools, and their properties have been explored a lot. This paper seems like merging them together, lacking of new insights.\n\n3. As previous listed, the paper experiment needs more ellaboration. I do not understand the experiment setting of table 2. What is the meaning of the percentages in neural network verifications? Why not use the same setting for the baselines?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EuZm3sUzpD", "reviewer": "Reviewer_SiXd", "summary": "This paper is concerned with the quantitative (probabilistic) verification of neural network. It proposes PV, a branch-and-bound algorithm that is correct and (under reasonable assumptions) complete. Additionally, the paper proposes a fairness benchmark for the probabilistic verification of NNs that is more challenging than previous work.\n\n## update after rebuttal\n\nThe authors clarified some aspects and adequately addressed my concerns in the rebuttal, I raised my score to accept.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer SiXd for their review.\n\n> Q3. Closed-form inference.\n\nBy \"closed-form\", we wanted to express that **a terminating algorithm exists** for computing a probability exactly, not necessarily that this algorithm has polynomial runtime. \nWe will state this more clearly in our paper. \nFor example, we use a Bayesian Network (BN) in our MiniACSIncome experiment, for which exact inference is NP-complete, as you also pointed out. \nFor practical applicability, the assumption is that computing the probability of a hyperrectangle should be significantly faster than solving the overall verification problem.\nThis is the case for our BN (inference is NP-complete) and the MiniACSIncome probabilistic verification problem (#P-hard).\n\n> Q4. Expressiveness of the supported family of distributions.\n\n**Yes**, we are able to encode complex, multimodal distributions! \nFor example, consider Figures 7 and 8 in our Appendix, which visualise the BN of our MiniACSIncome benchmark.\nFigure 7 shows that this distribution is multimodal. \nFor example, the marginal distributions of \"SCHL\" and \"AGEP\" marginal distribution have several peaks.\nRegarding complexity, these figures also show that our BN is a reasonably good fit of real-world US census data (ACSIncome).\nTherefore, we believe that our MiniACSIncome experiment demonstrates that our approach **is applicable to complex, multimodal distributions.** \n \n> Multivariate normal distributions paragraph.\n\nWe will clarify this paragraph in the updated version of the paper.\nThe key point here is that while *general* multivariate normal distributions do not admit a closed-form solution, *standard* multivariate normal distributions (or, more generally, multivariate normal distributions with diagonal covariance matrices) do admit a closed-form solution.\nOr idea is to emulate a general multivariate normal distribution through a standard multivariate normal distribution and an additional linear layer in the network we want to verify. \nBy doing this, we can apply PV to a (general) multivariate normal distribution, although we can not use this multivariate normal distribution as an input distribution for PV directly.\n\n> Q2. How does PV compare with [1]?\n\nWe would like to point out that **[1] does not provide *sound* coverage ratios for MNIST**.\nThe coverage ratios they report are sampling approximations. \nWhile [1] also provides sound results in the \"Quantitative Verification\" section, these results are for 2d and 3d input spaces.\nDue to the unsoundness of the MNIST results, a comparison with our approach on this case study would be unfair, but we performed a comparison with [1] on the VCAS quantitative verification case study.\nOur PV algorithm is faster than the algorithm from [1] by two orders of magnitude for this case study.\n\n| Algorithm                | Runtime |\n|--------------------------|---------|\n| PreimageApproxForNNs [1] |  16.42s |\n| PV (Ours)                |   0.13s |\n\nBoth results were obtained on the hardware also used in our paper (HW1).\nThe code for running both tools is available at https://drive.google.com/drive/folders/1KBbBwzxLvCXeufo24A-cZhuvwhGTB2MD?usp=sharing.\n\n> ReLU Splitting\n\nThe problem with ReLU splitting for probabilistic verification is that it creates branches that are non-convex in the input space. \nThe approach of [1] to underapproximate these branches using linear relaxations is interesting.\nHowever, these underapproximations are still polytopes and computing the volume of a high-dimensional polytope is very costly.\nThe approach in [1] to use Monte Carlo estimates of such volumes is enticing, but it entails unsoundness. \n\n> Main criticism: only low-dimensional settings.\n\nEarlier works that consider non-uniform probability distributions (FairSquare and SpaceScanner) only scale to 2d input spaces.\nAlthough uniform input distributions significantly simplify verification, [1] and Marzari et al. (ProVe_SLR) only demonstrate sound #DNN-verification for up to 3 and 5 input dimensions, respectively.\nIn light of this, **our ability to handle 7 input variables** while not assuming uniform input distributions **is a major step forward**.\nWe would also like to point out that the actual input dimension of MiniACSIncome-7 is 67 (Table 7 in our Appendix). \n\n> Q1. Large networks for low-dim settings.\n\nACAS Xu (Julian et al., 2018) is a good example of a low-dimensional application requiring a medium-sized neural network (> 1000 parameters). \nOther examples are the neural network controllers in [1].\n\n> Satisfaction functions (Eq. 3)\n\nWe agree that Equation (3) is somewhat intricate. \nThis is because of the generality of our algorithm. \nThe satisfaction functions encapsulate, for example, the fraction in Equation (1). \nThe full satisfaction function for Equation (1) is given in Example A.1.\nOur $f_{Sat}$ function roughly corresponds to the formulae $\\varphi_{\\mathrm{post}}$ of Albarghouthi et al. (2017) and $\\Gamma$ of Morrettin et al. (2024).", "claims_and_evidence": "*\"Each probability distribution Px(i) needs to allow for computing the probability of a hyperrectangle in closed form. This requirement is satisfied by a large class of probability distributions...\"*\n\nThe class seems pretty small to me*.\n\n*\"...including discrete distributions with a closed-form probability mass function and univariate continuous distributions with a closed-form cumulative density function, as well as Mixture Models and probabilistic graphical models (Bishop, 2007), such as Bayesian Networks, of such distributions.\"*\n\n*=I think that I might be misinterpreting what \"closed-form\" means here, as I'm assuming it is a notion related to the complexity of the task. In  \"The computational complexity of probabilistic inference using Bayesian belief networks\", Cooper (AIJ, 1990) shows that SAT can be reduced to (a decision version of) inference on a binary BN. To the best of my understanding, each conditional can be computed in closed form given the parents, but the overall task is clearly NP-hard. Limiting inference to hyper-rectangles doesn't really fixes that, since the hyperrectangle could fully contain the support of the BN. Is there something I'm missing?\n\nI checked Section A.4 only to be even more confused by this paragraph on expressivity:\n\n*\"We first show how we can apply PV to multivariate normal distributions even though they do not admit a closed-form solution\nfor the probability of a hyperrectangle. Consider a multivariate normal distribution Pz with mean μ and covariance Σ =\nAAT . Let Px be a standard multivariate normal distribution. Now, z = Ax + μ is distributed according to Pz . Therefore,\nby prepending the linear transformation Ax + μ to net, we can apply PV to multivariate normal distributions, since the\nprobability of a hyperrectangle under a standard multivariate normal distribution has a closed-form solution.\"*\n\nIsn't the conclusion contraddicting the premise?", "methods_and_evaluation_criteria": "The overall idea behind PV makes sense to me, but I didn't check the details of the proofs. \n\nI am not very convinced by the emprirical evaluation (see below).", "theoretical_claims": "I did not carefully check the proofs.", "experimental_designs_or_analyses": "Despite introducing a novel benchmark, the empirical evaluation is not extremely convincing for a paper concerned with scalability.\n\nMy main criticism is that it consider low-dimensional settings only, with at most 8 input variables. \nIn their work [1], Zhang et al. argue that input splitting only works for low dimensional settings and propose ReLU splitting as a better alternative when the input dimensionality grows. Since PV is based on input splitting, one is left wondering what happens when the dimensionality is > 8. \n\nAlbeit restricted to uniform distributions, the experimental evaluation in [1] is more thorough, involving the verification of NN-based controllers (low input dimensionality) as well as MNIST classification robustness to patch attacks (up to 7x7 input variables).\n\nAnother problem is that, despite the focus on verification with meaningful input priors, how the approach scales to more complex priors is not analyzed. My guess is that this is somehow dictated by the approach being restricted to very simple distributions.\n\nWhile I appreciate the novel setting introduced by this paper (MiniACSIncome), it seems to be tailored to PV's working assumptions. I wish it provided a more \"neutral\" perspective on the challenges of probabilistic verification of NNs. To the best of my understanding, it cannot be used for generating instances with input dimensionality > 8 and it cannot be used to test how a probabilistic verification algorithm scales to more expressive/complex input distributions (the BN seems to be fixed).", "relation_to_broader_scientific_literature": "The related work section is well written and thorough, with one exception (see section below).", "essential_references_not_discussed": "[1] \"Provable preimage under-approximation for neural networks\" by Zhang et al. (TACAS24), is concerned with quantitative verification of NNs. Their scope is less general, focusing on uniformly distributed inputs and ReLU nets. The proposed approach, however, has many similarities with PV: \n1) They also consider input (as well as ReLU) splitting in their work and propagate linear relaxations of the volumes that need to be quantified. To the best of my understanding, they also leverage AutoLiRPA. \n2) They incrementally compute tighter approximations of the verification problem.", "other_strengths_and_weaknesses": "The paper tackles an important problem in ML verification and contributes with a novel algorithm as well as establishing new benchmarks.\nI appreciated the related work section, which pointed me to relevant work that I missed. \n\nI found the problem definition in Section 3.1 (Eq. 3) quite involved. What are these \"satisfaction functions\" useful for? How does the definition relates to the example in Eq. 1 or to other problem definitions in similar works?\n\nBetter characterizing the family of input distributions that is supported would be beneficial, the scope is not very clear at the moment.\n\nThe empirical evaluation is mostly concerned with showing scalability to larger NNs. I would assume that larger NNs are needed when the number of inputs grows and their distribution becomes very complex and multimodal. The paper doesn't make a case for adopting complex NNs in relatively simple / low-dimensional input spaces.", "other_comments_or_suggestions": "NA", "questions_for_authors": "1) The case for employing deep neural network in the settings considered in the paper is not clear. How crucial is scaling to networks with hundreds or thousands of parameters when limited to low-dimensional input spaces? Or, alternatively, how does your approach scale to higher dimensional input spaces?\n\n2) How does PV compare with [1] in uniform settings? Or is there anything preventing a direct comparison?\n\n3) Can you elaborate on the complexity of computing the probability of hyperrectangles in BNs? What do you mean by closed-form inference exactly? Can you provide some examples? \n\n4) Can you elaborate on the expressiveness of the supported family of distributions? Is it able to encode complex, multimodal distributions? Can you show that empirically?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a new algorithm for neural network probabilistic verification based on branch-and-bound and bound propagation. The  algorithm can compute and refine rigorous lower and upper bounds of probabilities satisfying some properties when model's input is following a probabilistic distribution. The positive sides are the novel application of branch-and-bound and bound propagation to the probabilistic verification problem, comprehensive evaluation showing effectiveness, and significant clarification efforts during rebuttal that address most of the reviewers' comments. The negative sides are limited applicability when input dimensionality is high and a relatively straightforward methodology. After thorough discussion among reviewers and AC, we recommend acceptance. Congratulations! Authors should incorporate the reviewer's feedback and discussion into the camera-ready version.
Decision: Accept (poster)