Scalable Neural Network Verification with Branch-and-bound Inferred Cutting Planes
Authors: Duo Zhou
Christopher Brix
Grani A. Hanasusanto
Huan Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: Neuron Network Verification; AI Safety; Robustness; Formal Methods
Primary area: safety_in_machine_learning

Abstract: Recently, cutting-plane methods such as GCP-CROWN have been explored to enhance neural network verifiers and made significant advancements. However, GCP-CROWN currently relies on ${\it generic}$ cutting planes ("cuts") generated from external mixed integer programming (MIP) solvers. Due to the poor scalability of MIP solvers, large neural networks cannot benefit from these cutting planes. In this paper, we exploit the structure of the neural network verification problem to generate efficient and scalable cutting planes ${\it specific}$ to this problem setting. We propose a novel approach, Branch-and-bound Inferred Cuts with COnstraint Strengthening (BICCOS), that leverages the logical relationships of neurons within verified subproblems in the branch-and-bound search tree, and we introduce cuts that preclude these relationships in other subproblems. We develop a mechanism that assigns influence scores to neurons in each path to allow the strengthening of these cuts. Furthermore, we design a multi-tree search technique to identify more cuts, effectively narrowing the search space and accelerating the BaB algorithm. Our results demonstrate that BICCOS can generate hundreds of useful cuts during the branch-and-bound process and consistently increase the number of verifiable instances compared to other state-of-the-art neural network verifiers on a wide range of benchmarks, including large networks that previous cutting plane methods could not scale to.

Scalable Neural Network Verification with Branch-and-bound Inferred Cutting Planes
Duo Zhou'
Christopher Brix²
Grani A Hanasusanto'
Huan Zhang'
Uniiersitty of Illinois (tbana-Champaign 2RWTH Aachen University
(duozhou2, gilliiiio edu brix#cs. wwt.-aachen........aaaaaaa de mann@huan-zhange com
Abstract
Recently, cutting-plane methods such GCP-CROWN have been explored enhance neural network verifiers and made significant advances. However, GCP- CROWN currently relies on generic cutting planes ("cuts") generated from external mixed integer programming (MIP) solvers. Due to the poor scalability of MIP solvers, large neural networks cannot benefit from these cutting planes. In this paper, we exploit the structure of the neural network verification problem to generate efficient and scalable cutting planes specific for this problem setting. We propose a novel approach, Branch-and and--ound Inferred Cuts with COnstraint Strengthening (BICCOS), which leverages the logical relationships of neurons within verified subproblems in the aanch-and-bound search tree, and we introduce cuts that preclude these relationships in other subproblems. We develop a mechanism that assigns influence scores neurons in each path to allow the strengthening of these cuts. Furthermore, we design multi-tree search technique to identify more cuts, effectively narrowing the search space and accelerating the BaB algorithm. Our results demonstrate that BICCOS can generate hundreds of useful cuts during the branch-and-ban anduudu process and consistently increase the number of verifiable instances compared to other state-of-the-an neural network verifiers on a wide range of benchmarks, including large networks that previous cutting plane methods could not scale to. BICCOS is part of the 0r,3-RRWN verifier, the VNN-COMP 2024 winner. The code is available at/htps::/// gig.gtthuuu..... Booo//Leuiisnt sm//BICCO/BSSSS /BICCOS
Introduction
Formal verification of neural networks (NNs) has emerged as critical challenge in the field of artificial intelligence. In canonical settings, the verification procedure aims to prove certified bounds on the outputs of neural network given specification, such as robustness against adversarial perturbations or adherence safety constraints. As these networks become increasingly complex and are deployed in sensitive domains, rigorously ensuring their safety and reliability is paramount. Recent research progress on neural network verification has enabled safety or performance guarantees in several mission-critical applications [55 53
57
The branch and bound (BaB) procedure has shown great promise a verification approach 12] 59 21]. In particular, the commonly used ReLU activation function exhibits a piecewise linear behavior, and this property makes ReLU networks especially suitable for branch and bound techniques. During the branching process, one ReLU neuron is selected and two subproblems are created. Each subproblem refers to one of the two ReL.U states (inactive or active) and the bounds of the neurons' activation value are tightened correspondingly. BaB systematically branches ReLU neurons, creates search tree of subproblems, and prunes away subproblems whose bounds are tight enough to guarantee the verification specifications. Although our work focuses on studying the canonical ReLU settings, branch-and-boumd has also demonstrated its power non-ReLU cases [48]. Despite its success in many tasks, the efficiency and effectiveness of the depend on the number of subproblems that can be pruned.
procedure heavily
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Recent work has explored the use of cutting plane methods in neural network verification. Cutting planes ("cuts") are additional (linear) constraints in the optimization problem for NN verification to tighten the bound without affecting soundness. By introducing carefully chosen cuts, they can significantly tighten the bounds in each subproblem during BaB, leading to more pruned subproblems and faster verification. However, it is quite challenging to generate effective cutting planes for large-scale NN verification problems. For example, GCP-CROWN [6]] relied on strong cutting planes generated by mixed integer programming (MIP) solver, which includes traditional generic cutting planes such as the Gomory cuts (24), but its effectiveness is limited to only small neural networks. The key to unlocking the full potential of BaB lies in the development of scalable cutting planes that are specifiic to the NN verification problem and also achieve high effectiveness.
In this paper, we propose a novel methodology, Branch-and bound Inferred Cuts with COnstraint Strengthening (BICCOS), that can produce effective and scalable cutting planes specifically for the NN verification problem. Our approach leverages the information gathered during the branch-and- bound process to generate cuts on the fly. First, we show that by leveraging any verified subproblems (e.g., subproblem is verified when neurons A and B are both split to active cases), we can deduce cuts that preclude certain combinations of ReLU states (e.g., neurons A and B cannot be both active). This cut may tighten the bounds for subproblems in other parts of the search tree, even when neurons and B have not yet been split. Second, to make these cuts effective during the regular BaB process, we show that they can be strengthened by reducing the number of branched neurons in verified subproblem (e.g., we may conclude that setting neuron B to active is sufficient to verify the problem. drop the dependency on A, and remove one variable from the cut). BICCOS can find and strengthen cuts on the fly during the BaB process, adapting to the specific characteristics of each verification instance. Third, we propose pre-solving strategy called "multi-tree search" which proactively looks for effective cutting planes in many shallow search trees before the main BaB phase starts. Our main contributions can be summarized as follows:
We first identify the opportunity of extracting effective cutting planes during the branch-and-bound process in NN verification. These cuts are specific to the NN verification setting and scalable to large NNs that previous sate-of-thee-a cutting plane methods such as GCP-CROWN with MIP-cuts cannot handle. Our cuts can be plugged into existing BaB-based verifiers to enhance their performance.
We discuss several novel methods to strengthen the cuts and also find more effective cuts. Strength- ening the cuts is essential for finding effective cuts on the fly during the regular BaB process that can tighten the bounds in the remaining domains. Performing a multi-tree search allows us to identify additional cuts before the regular BaB process begins.
We conduct empirical comparisons against many verifiers on a wide range of benchmarks and consistently outperform sfate-of-the-ar baselines in VNN-COMP 4 40 [0. Notably, we can solve the very large models like those for cifar100 and tinyimagenet benehmarks and outperform all tfth--of-theart tools, which GCP-CROWN with MIP-based cuts cannot scale.
2 Background
Notations Bold symbols such as (+) denote vectors; regular symbols such as zr indicate scalar components of these vectors. [N] represents the set [l....,N] and (:()) is the j-th column of the matrix ( A calligraphic font X' denotes set and IR represents the dimensional real number space.
An I--layer ReI.U-based DNN can be formulated as f x -> x (L)), s.t. {z(() = (00) + b(0, (+0) (z))),, (0) x;; i E [L]}, where o represents the ReLU activation function, with input æ (0) E Rd and the neuron network parameters weight matrix ( E xd(f)) and bias vector ((0) E (d for each layer i. This model sequentially processes the input through each layer by computing linear transformations followed by ReLU (6)
The NN Verification Problem
activations. The scalar values a(4) and z; represent the post-activation and pre-activation values of the j-th neuron in the i-th layer, respectively. We write f/50 (z) and ff (x) for 2600 and (1) respectively, when they depend on specific x.
In practical applications, the input x confined within a perturbation set X, often defined as an Ep norm ball. The verification task involves ensuring specified output property for any x E X. For example, may be required to verify that the logit corresponding to the true label fa(x) is consistently higher than the logit for any other label fy (z). thus ensuring f(( fz( > O, Vj # i. By

---

integrating the verification specification as an additional layer with only one output neuron, we define the canonical verification problem as an optimization problem:
min f(x); #EA
(I)
where the optimal value f* 2 0 confirms the verifiable property. We typically use the eo norm to define X' == (=: || To II Σ <) with Do as a baseline input. However, extensions to other norms and conditions also possible 44 58). When we compute lower bound [' f", label the
problem UNSAT if the property was verified and I O, i.e. the problem of finding concrete input that violates the property unsatistiable, or in other words infeasible. If f 0, it is unclear whether the property might hold or not. We refer to this as unknown.
MIP Formulation and LPP Relaxation that the network can be verified. However, due to the non-linearity of ReLUU neurons, this problem is non-convex, and ReLU neurons are typically relaxed with linear constraints to obtain a lower bound for fr, One possible solution is to encode the verification problem using Mixed Integer Programming (MIP), which encodes the entire network architecture. using Rd to denote the pre-activation neurons, & E Rdd")) to denote post-activation neurons for each layer, and binary ReLU indicator 23 E 10 to denote (in)active neuron for each unstable neuron. A lower bound can be computed
the optimization problem (T. a non-negative f indicates
by letting 2/ E [0.1] and therefore relaxing the problem to LP formulation. There is also an equivalent Planet relaxation [20]. We provide the detailed definition in Appendix A In practice, this approach is computationally too expensive be scalable.
Branch-and-boun Instead of solving the expensive LP for each neuron, most existing NN verifiers
use cheaper methods such as abstract interpretation (49 [3 or bound propagation [16 62
54
59]
due to their efficiency and scalability. However, because of those relaxations, the lower bound for f* might eventually become too weak to prove f* 0. To overcome this issue, additional constraints need to be added to the optimization, without sacrificing soundness.
The branch-and-bound (BaB) framework, illustrated in Figure 1 is a powerful approach for neural network verification that many state-of-the-art verifiers are based 12 54 16 29 21. BaB
Split x
2.0 Spling
-1.5
systematically tightens the lower bound of f by splitting unstable ReLU neurons into two cases: 2z 2 and xy S 0 (branching step), which defines two subproblems with additional constraints. In each subproblem, neuron I, does not need to be relaxed, leading to a
Split zy
-0.3
Spline
Siplit
.n.7
1.0
tighter lower bound (bounding step). Note that {2/) < ;
(1)
(1) 0}
Split
Split
and (zx (1) 2 1/0 0} in the Planet relaxation are equivalent to
0.2
0.2
(=))) }} and {= 1} in the LP relaxation, respectively, see Lemma A. in Appendix [A] Subproblems with a positive lower bound are successfully verified, and no further splitting is required. The process repeats on subproblems with negative lower bounds until all unstable neurons are split, or all subproblems are verified. If there are still domains with negative bounds after splitting all unstable neurons, counter-example can be constructed.
Figure I: Each node repre- sents subproblem in the BaB process by splitting unstable ReLU neurons. Green nodes indicate paths that have been verified and pruned, while blue nodes represent domains that are still unknown and re- quire further branching.
General Cutting Planes (GCP) in NN verification A (linear) cutting plane ("cut"") is linear inequality that can be added to MIP problem, which does not eliminate any feasible integer solutions but will tighten the LP relaxation of this MIP. For more details cutting plane methods, refer readers to the literature on integer programming 14). In the NN verification setting, it may involve variables z:()) (pre-activation), ( (post-activation) from any layer i, and z00 (binary ReLU indicators) from any unstable neuron. Given N cutting planes in matrix form 661:
Σ H 200 + ((22()) < d
where (1), GO,, and @ are the matrix coefficients corresponding to the cutting planes. Based on this formulation, one can introduce arbitrary valid cuts to tighten the relaxation. GCP-CROWN [6]]
3

---

allows us to lower bound ① with arbitrary linear constraints in (2) using GPU-accelerated bound propagation, without relying on an LP solver.
In [61], the authors propose to find new cutting planes by employing an MIP solver. By encoding (T MIP problem, the MIP solver will identify potentially useful cutting planes. Usually, these cuts would be used by the solver itself to solve the MIP problem. Instead, [61] applied these cuts using GPU-accelerated bound propagation. This approach shows great improvements on many verification problems due to the powerful cuts, but it depends on the ability of the MIP solver to identify relevant cuts. As the networks that are analyzed increase in size, the respective MIP problem increases in complexity, and the MIP solver may not return any cuts before the timeout is reached. In the next chapter, we will describe a novel approach to generate effective and scalable cutting planes.
3 Branch-and-bound Inferred Cuts with Constraint Strengthening (BICCOS) 3.1 Branch-and- Inferred Cuts
The first key observation in our algorithm is that the UNSAT subproblems in the BaB search tree include valuable information. If the lower bound of subproblem leads this subproblem to be UNSAT (e.g., subproblems with green ticks in Fig. [T). it signifies that restricting the neurons along this path to the respective positive/negative regimes allows us to verify the property. A typical BaB algorithm would stop generating further subproblems at this juncture, and continue with splitting only those nodes that have not yet been verified. Crucially, no information from the verified branch is transferred to the unverified domains. However, sometimes, this information can help a lot.
Example. As shown in Fig. D assume that after splitting 31 S 0 and 23 S 0, the lower bound of this subproblem is found to be greater than 0, indicating infeasibility. From this infeasibility, we can infer that the neurons I and za cannot simultaneously be in the inactive regime. To represent this relationship, we use the relaxed ReLU indicator variables æ1, 23 E [0. 1] in the LP formulation and form the inequality 21 + 23 2 1. This inequality ensures that both 21 and 23 cannot be 0 simultancously. we were to start BaB with a fresh search tree, this constraint has the potential to improve the bounds for all subproblems by tightening the relaxations and excluding infeasible regions.
We propose to encode the information gained from verified subproblem as a new cutting plane. These cutting planes will be valid globally across the entire verification problem and all generated subproblems. We present the general case of this cutting plane below:
Proposition 3.1. For verified, or UNSAT, subproblem in a BaB search tree, let 2_ and 2_ be the set of neurons restricted to the positive and negative regimes respectively. These restrictions were introduced by the BaB process. Then, the BaB inferred cut can be formulated as:
Σ 2 IEZ
Σ iEZ
2 S 1+1--
Proof deferred to Appendix B.I The BaB inferred cut (3) will exclude the specific combination of positive and negative neurons that were proven to be infeasible in the respective branches. An example is shown in Fig. 2a
Note that while similar cuts were explored in [9) they were not derived from UNSAT problems within the BaB process. In our framework, these cuts can theoretically be incorporated as cutting planes in the form of (2) and work using GCP-CROWE
However, a limitation exists: all elements in our cut are ReLU indicator z, although GCP-CROWN applies general cutting planes during the standard BaB process. It was not originally designed to handle branching decisions on ReLU indicator variables that may have (partially) been fixed already in previous BaB steps. When cuts added, they remain part of the GCP-CROW may be fixed to 0 due branching, effectively turning them into constants This situation poses challenge because the original GCP-CROWN formulation presented in 611 does not accommodate constraints involving these fixed variables, potentially leading incorrect results. To address this issue, we need to extend GCP-CROWN to handle BaB on the ReLU indicators x, ensuring that the constraints and cuts remain valid even when some variables are fixed during branching.
formulation. However, during the BaB process, some z variables
Extension of GCP-CROWN To address this limitation, we propose an extended form of bound propagation for BaB inferred cuts that accommodates splitting variables. In the original GCP- CROWN formulation, I(0) represents the set of initially unstable neurons in layer i, for which cuts

---

were added due to their instability. However, during the branch-and-bon neurons may be split, fixing their corresponding 2 variables to 0 or 1, and thus their 2 variables no longer exist in the original formulation. While updating all existing cuts by fixing these variables is possible, it is costly since the cuts for each subproblem must fixed individually, as the neuron splits in each subproblem is different. Our contribution is to handle these split neurons by adding them to the splitting set Z in the new formulation below, without removing or modifying the existing cuts (all subdomains can still share the same set of cuts). This approach allows us to adjust the original bound propagation in [6]] Theorem 3.1] to account for the fixed = variables and their influence on the Lagrange dual problem, without altering the existing cuts. Suppose the splitting set for each layer i is 2+(0) U 2 2+) == 2(6) C I(0), and the full split set is 2 = Uie|L-1i Z(0, The modifications to the original GCP-CROWN theorem are highlighted in brown in the following theorem.
process, some of these
Theorem 3.2. [BaB Inferred Cuts Bound Propagation] Given any BaB split set 2, optimizable
(8) parameters 0 dj S 1 and 3, p. 2 0, jj (6)* is a function of Q.
0(a,3,14, (1T
Σ
EcOTbO - B3 d
E E (B)
E
1=1 jEZO
where variables u are obtained by propagating n (L) = -1 throughout all i E 1]:
2 (0) = (6+11 ((++))T((6t1)) 3 H (
+ G(0)
3) JEI
(2) = (1+1T (6+1) - 3 (H + + +1 jE
(9)
49
(0) = -B HO! :. JEI (
10 = B H - -, j jE2-
2 ( = 19 +a f B H. j I z
Here, (58) Tj and 7
(1)*
(0) are defined for each initially unstable neuron that has not been split:
j E z())) 20, and h (B) is defined for all unstable neurons j I
(6)
[0/")1+ 1+ == ( W (6+1)
3T ( 0), 10,01- = -inn ((11)
w(++)
B C .)
(1) + B Q
10" == max min
15(0 .0)
J - (2
(1) 100
(0) ( 3
is (0) 10 (0)
+ < 3 ST
JJ S (0) 10 1+ and j E I(0 2
(3)=
if B Q
M u "
or 2
B
BTQ.
1 1 I+ or 2-
Proof in Appendix B.2 The brown- higgh-higllihttedd modifications ensure that the bound propagation correctly accounts for the influence of the fixed ReLU indicator variables- rreulling from branching decisions in the BaB process-O0 on each layer's coefficients and biases. Notably, if we remove all cutting planes, this propagation method reduces 8-CROWN (54. In this context, the new dual variables μa and T correspond to the dual variable 3 used for x splits in (3-CRONN. To handle splits, - (8) for each layer. By adjusting the dual variables and functions to reflect the fixed states of certain neurons, the extended bound propagation maintains tightness and correctness in the computed bounds.
we only need to specify the sets +1) and 2
3.2 Improving BaB Inferred Cuts via Constraint Strengthening and Multi- Multi-Tree Search
Theorem 3.2 allows us to use the cheap bound propagation method to search the BaB tree quickly to discover UNSAT paths to generate BaB inferred cuts by Proposition 3.] However, our second key observation is that naively inferred cuts will not be beneficial in regular BaB search process, illustrated in Fig. 2a for example, all the subproblems after the split x1 2 O (all nodes on the right after the first split) imply 2 = 1, and thus + 23 2 always holds. Thus, we have to strengthen these cuts to make them more effective. We propose the rranch-anddboume Inferred Cut with COnstraint Strengthening (BICCOS) to solve this.
5

---

(b) Starting from the UNSAT path {2) 0, 2b 0, 27 0}. { 0} not actually needed, as (2c 0. 2 0} is sufficient to prove that this subproblem is UNSAT. We can infer new 27 2 1,
Z8
27
A veriffed path
2 Splia 25
A verified path
Remove the split 2 then Re-verify
2g 2
2
+
2g
Inferred cut 2 + 2! already satisfied!
4 0
Search multi-tree simultaneously Each verified path infers cut.
Bounds do not improve!
25 S
2g
(c) The root node is split multiple ways. In the sub-tree where the root node is split
2
(a) Based on the UNSAT path infer
2z S 0
21, extract the + z3 2 This cut is then applied to all other sub-Irees as well. In the sub-tree with the root node split on 2s. inducing another cut 2s 2 1 that will be shared across sub-trees.
(ar 0. 33 0}.
the cut 3 as 21 23 S -1 +
If the reduced path still verifiable,
1. However, none of the other subproblems would vio- late this constraint anyway, the bounds do not improve.
+
new cut is inferred
Figure 2: (2):: Inferred cut from UNSAT paths during BaB and why it fails in regular BaB, 2b): Constraint strengthening with Neuron Elimination Heuristic. (2 Multi-tree search.
In a known UNSAT subproblem with multiple branched neurons, it is possible that subser of the branching neurons sufficient to prove UNSAT, shown in Fig. 26 By focusing on this subset, we strengthen the BaB inferred cuts by reducing the number of variables involved. From optimization perspective, each cut corresponds to a hyperplane that separates feasible solutions from infeasible ones. Simplifying the cut by involving fewer variables reduces the dimensionality of the hyperplane, making it more effective at excluding infeasible regions without unnecessarily restricting the feasible space. Thus, we can draw corollary:
Corollary 3.3. Formally, consider the two cuts from Eq.
Σ
2
Σ
2
(3.1)
iEZ
iE2T
Σ 24 Σ
(3.2)
1E
If either z C 25 and 2T C Zz, 2 C z and 2 C 2j. then any assignment {zc} satisfying the cul associated with the smaller split Z also satisfies the other cut. This implies that the cut with the smaller set is strictly stronger than the one with the larger set.
Proof deferred to Appendix B.3 This demonstrates that cuts with fewer variables can be more power- ful because they operate in lower-dimensional spaces, allowing the hyperplane to more effectively position itself to exclude infeasible regions.
Now, the challenge is determining which unnecessary branches to remove to produce a cut with as few z variables as possible. An important observation from Theorem 3.2 that the dual variables μ and r, associated with the fixed ReLU indicators ++)) and E Z (4) respectively, reflect the impact of these fixed activations on the bound. Specifically, a positive dual variable μa >> for some z E (+) indicates that the fixed active state of these neurons contributes significantly to tightening the bound. Similarly, positive influential in optimizing the bound. However, neurons with zero dual variables (μ 0 or 0) may not contribute to the current bound optimization. This observation suggests that these neurons might be candidates for removal to simplify the cut. But it's important to note that zero dual variable does not guarantee that the corresponding neuron has no impact under all circumstances-in only indicates no contribution in the current optimization context. Simply removing all neurons with zero dual
for some 2 2 -() signifies that the fixed inactive neurons are

---

variables might overlook their potential influence in other parts of the search space or under different parameter settings. Therefore, the challenge lies in deciding which neurons with zero or negligible dual variables can be safely removed without significantly weakening the cut. This decision requires a careful heuristic that considers not only the current values of the dual variables but also the overall structure of the problem and the potential future impact of these neurons. By intelligently selecting which & variables to exclude, we aim to produce a stronger cut that is both effective in pruning the search space and efficient in computing. To do this, we use a heuristic to determine whether each neuron should be tentatively dropped from the list of constraints. Algorithm T shows the constraint strengthening with the neuron elimination heuristic.
Neuron Elimination Heuristic for Constraint Strengthening First, we compute a heuristic influence score for each neuron to assess its impact on the verification objective. This score is based on the improvement in the lower bound of f before and after introducing the neuron's 's split in the BaB tree. By recording the computed lower bounds at each node, we can measure how beneficial each constraint is to the verification process. Second, we rank the neurons according to their influence scores and tentatively drop those that contribute least to improving the lower bound. We will retain neurons whose corresponding Lagrange multipliers, 1s or т, are greater than zero. For neurons with J or equal to zero, we remove certain percentile of neurons with the lowest scores, as indicated by the
parameter in Algorithm [ When a neuron is dropped, its split is canceled. Then, perform re-verification step using only the reduced subset of constraints. This involves recomputing the lower bound on f based solely on the selected constraints. If the verification still succeeds that is, the lower bound remains non-negative--th the reduced set induces new cutting plane. This new cutting plane is applied to all subproblems within the BaB process after further strengthening. Finally, we can iteratively repeat the process of reducing the constraint set, aiming to generate even stronger cuts. The process terminates when the property can no longer be verified with the current subset of constraints. This iterative refinement is designed to focus the most influential neurons, potentially enhancing the efficiency of the verification. Once the new cuts determined, we merge pairs of cuts if possible (e.g. merging 21 + 22 2 0 and
22 2 0 to 21 2 0).
Algorithm 1 Constraint Strengthening
Require: f: model; f:
lower bound; D: Domain
2 D UNSAT split constraints set; T.M E D set for å_ and j set for 2
Cout : current set of known cuts; drop hop_peerentage Percentage of splits to be dropped
1: crrroon_nnfuunce__ng scores + Neuron ietiimaatoonHeuusttiiiee D)
2: coore_trreshole <- cetpennilleeeuuooonnttteeeee
drop_percentage)
3: Znew =0 0
4: for M [lneuron influence_ | do
5: if 2, BETUMM f 0 or neuron_ sttpn__iinnneeooooreeee > threshlh then
6: Znew <- Z new U Σ
7: f
< GoolveBBound[] Cent U Znew)
vereifificatio
8: if' re-verification 2 0 then
9:
strengthened cut + Infer_Cut( Znew)
10: Cent < C.u U (strengthened_cre _ctt
11: Ceut <- Coontraint_Sttrengheenne
J,D, Zoow, Ceut: drop_peccenttaee)))
12: Cout < Cterge_Cuts(Coul)
13:
return Cent
Multi- Search Traditionally, the BaB process generates a single search tree. We propose augmenting this approach by performing multiple BaB processes in parallel as a presolving step, with each process exploring different set of branching decisions. At each branching point, initialize multiple trees and apply various branching decisions simultaneously. While this initially increases the number of subproblems, the cutting planes generated in one tree are universally valid and can be applied to all other trees. These newly introduced cuts can help prove UNSAT for nodes in other trees, thereby inducing additional cutting planes and amplifying the pruning effect across the entire search space, illustrated in Fig. 2c
Since computational resources must be allocated across multiple trees, we prioritize nodes for further expansion that have the highest lower bound on the optimization objective. This strategy ensures that more promising trees receive more computational resources. After predefined short timeout,
7

---

consolidate our efforts by pruning all but one of the trees and proceed with the standard BaB process augmented with BICCOS on the selected tree. We choose the tree that has been expanded the most frequently, as this indicates that its bounds are closest to verifying the property.
BaB Tree Searching Strategy In the standard BaB process (e.g.. in 3-CROWN), branches operate independently without sharing information, so the order in which they are explored does not affect the overall runtime. For memory access efficiency, there is a slight preference for implementing BaB as a depth-first search (DFS). where constraints are added until unsatisfiability (UNSAT) can be proven 66 54]. This approach focuses the search on deeper branches before returning to shallower nodes.
However, in the context of BICCOS, our objective is to generate strong cutting planes that can prune numerous branches across different subproblems. To maximize the generality of these cutting planes, they need to be derived from UNSAT nodes with as few constraints as possible. While constraint strengthening techniques can simplify the constraints, this process is more straightforward when the original UNSAT node already has minimal set of constraints. Even if only a few constraints are eliminated, the resulting cutting plane can significantly impact many other subproblems. To facilitate this, propose performing the BaB algorithm using breadth-firss search (BFS) strategy. By exploring nodes that are closest to the root and have the fewest neuron constraints, we can generate more general and impactful cutting planes carlier in the search process.
Algorithm 2 Branchh-am and bound Inferred Cuts with Constraint Strengthening (BICCOS).
Require: f: model; n: batch size; time out threshold D Dunknown: f < Init(f,0) ()
2: Punknown: , Cinteree_ cuts < Multi Teee_eeeeee__ee_eee Search(f, 0)
3: while UDunnownl > 0 and not timed out do
4:
(ZI...., )n t Batch Pick B (D Unkkowwn 11)
5: (ZT ..... Zn Z + Batch Batch_Splitt S ZI.....
Zn)
6: (f ( l.t.......... 2. S f f Solve_Bound(J, Cinereed cuts, 27 Zt, ,...,
2t.,....., Zn 2zt
7:
DUNSAT D-DDDain_Fiteruussssss
Domain FilteruNsA 2, 27 111 2t .l...... ......1 2s 2
8:
for all Dj E DUNSAT do Cintereed_ou t Constraint StrariitnSreggggnnnnnggg f, Di (rop_perceetage)
9:
10: Dunknown f- Unkknown U D Filter (L2z
2t). ..... 2111 2;11
11:
return UNSAT if Unkknww! = 0 clse Unknown
3.3 BICCOS Summary
summarizes our proposed BICCOS algorithm, with the modifications to the standard BaB algorithm highlighted in brown. First (line 2), instead of exploring a single tree, we explore multiple trees in parallel as a presolving step. This process may involve constraint strengthening and utilizes cut inference analogous to the procedures in lines 3-15 of the algorithm. After several iterations, prune all but one of the trees. From this point forward, only the selected tree is expanded further, following the regular BaB approach.
Algorithm 2
Until all subdomains of this tree have been verified, BICCOS selects batches of unverified subdomains add additional branching decisions, and attempt to prove the verification property. Unlike regular BaB, it then applies constraint strengthening to all identified UNSAT nodes and infers the corresponding cutting planes. These cutting planes are added to all currently unverified subdomains, potentially improving their lower bounds enough to complete the verification process. If BICCOS fails to identify helpful cutting planes, it effectively behaves like the regular BaB algorithm. We have implemented BICCOS in the a,3-CROWN toolbox. Notably, the cuts found by BICCOS are compatible with those from MIP solvers in GCP- GCP-CROWN, and all cuts can be combined in cases where MIP cuts are beneficial.
4 Experiments
We evaluate our verifier, BICCOS, on several popular verification benchmarks from VNN-COMP 4
40, 10 and on the SDP-FO benchmarks used in multiple studies [[]] 54 41. In the following discussion, C.B-CCROW refers to the verification tool that implements various verification techniques, while 3-CROWN and GCP-CROWN denote specific algorithms implemented within a N-RONC.OWN To ensure the comparability of our method's effects and to minimize the influence of hardware and equipment advances, we rerun 3-CROWN and GCP-CROWN with MIP cuts for each experiment. Additionally, we use the same BaB algorithm as in B-CROWN and employ filtered smart branching
8

---

Table 1: Comparison of different toolkits and BICCOS VNN-COMP benchmarks. Results non-CROWN or BICCOS were run on different hardware. "_" indicates that benchmark was not supported.
oVa122
ci www.ooottiaannntttttoooo 2022
S1far100-2024
timyinagenet 2024
Mothod
timers)
verified
timets)
verified
timets)
verifed
timets)
* verified
mneriam
3
6330.06
Maraboui
429. 13
186,11
27
0
(1
233.55
OVAL-"
[
To
393.
11
Venus2
14
386.71 71
17
VeriNect
73.65
69
MN-BaBlt
21
137.13
19
40.27
36
PyRATT
225]
42.38
68
55.64
-49
3-CROWN
(22)
59151
11.95
69
15/18
119
GCP.CROWN with MIP cuts [
32:12
25
18.42
69
19.32
119
31.60
134
BICO0S
19.84
26
13.38
72
13.58
125
16.33
140
Upper Bound
27
94
168
157
Results
VNN-COMP 2021 report
Resolts VNN-OUMP report
4X I Results VNN-COMP 2024 website
Table 2: Veritied accuracy (Ver.5) and avg. per- per-example verification time (s) on 7 models from 15
Datroet
Model
PRIMA
J-CROWN
[4]
MN-BaR 21T
Venua2
0
GCR-CROWN (MIP cnts) [S]
RICCOS
Upper
0.5 aand <- 2/255
Ver.%
Time
Vee%
Timels)
Ver%
Timels)
Vee%
Timelst
Ver:%
Time's)
Ver:%
Timels)
bound
MNIST
CNN-A-Ady
44.5
135.9
71.0
7.34
13.37
76.5
CNN-A-Ally
213
4.8
45.5
5.77
42.5
68.3
47.5
26.0
18.3
4.75
40.00
8.54
301"
ChN-A-Adv-44
25.0
4.9
46.5
0.78
46.0
37.7
47.5
13.1
48.0
1.47
48.5
1.81
49.5
CIFAR
CNN-A-Min-4
CNN-A-Miix
48.5
37.5
24.3
7.0
51.0
42.5
0.70
4.78
35.0
49.0
140.5
70.9
49.0
33.5
37.3
72.4
47.5
54.5
9.70
3.82
56.0
48.5
10.34
5.23
53.0
57.5
CNN-B-Adl
38.0
349.5
47.5
6.99
40.0
10.07
54.5
17.75
65.0
CNN 1 Adv
53.5
43.8
56.0
3.20
58.5
9.61
62.0
8.27
63.5
MN Ball with cliss timeout threshold for all models. 11" indicates that we could not run model due unsupported model stracture or other strons We run 5 CROWN. GUP-CROWN with MIP cuts and BICCDS with shotter 200h timtont fix models. The increased timcout Exr MN--BBB may incresse the perconaage varilled instances. However, we can still acilieve better verified accurccy than all other basclines. Other results are reported from [6]]
(FSB) [16] as the branching heuristic in all experiments. Note that in experiments GCP-CROWN refers to CCP-CROWN solver with MIP cuts. We also conduct ablation studies to identify which components of BICCOS contribute the most, including analyses of verification accuracy & time, number of cuts generated, and number of domains visited. Experimental settings are described in Appendix[C..l
Results on VNN-COMP benchmarks We first evaluate BICCOS on many challenging bench- marks with large models, including two VNN-COMP 2024 benchmarks: cifar100-2000 and tinyimagenet-2024 two VNN-COMP 2022 benchmarks:
and ova122. Shown in Table [ our proposed method, BICCOS, outperforms most other verifiers on the tested benchmarks, achieving the highest number of verified instances in four benchmark sets. BICCOS consistently outperforms the baseline a, 3-CROWN verifier (the 3-CROWN and GCP- CROWN (MIP cuts) lines), verifying more instances across almost all benchmark sets. In particular, GCP-CROWN with MIP cuts cannot scale to the larger network architectures in the cifar100 100 and tinyimagenet benchmarks with network sizes between 14.4 and 31.6 million parameters, due to its reliance on an MIP solver. BICCOS, on the other hand, can infer cutting planes without the need for MIP solver and noticeably outperforms the bascline on cifar 100 and tinyimagenet. Note that the increase in average runtime (e.g., on the cifar 1rr-tr000niinniii www_nyiiagenet--20 expected. The instances that could not be verified at all previously but can be verified using BICCOS tend to require runtimes that are below the timeout but above the baseline's 's average runtime.
benchmark) is
Results on SDP-FO benchmarks We further evaluated BICCOS, on the challenging SDP-FO benchmarks introduced in previous studies 15 These benchmarks consist of seven predom- inantly adversarial trained MNIST and CIFAR models, each containing numerous instances that are difficult for many existing verifiers. Our results, detailed in Table 2 demonstrate that BICCOS significantly improves verified accuracy across all the tested models when compared to current state- of-the-art verifiers. On both MNIST and CIFAR dataset, BICCOS not only surpasses the performance of methods like 3-CROWN and CCO-N empirical robust accuracy upper bound, leaving only a marginal gap. A slight increase in average time in some cases is attributed to the higher number of solved instances.
the CNN-A-Ady model but also approaches the
Ablation Studies on BICCOS Components. To evaluate the contributions of individual com- ponents of BICCOS, we performed ablation studies summarized in Table 3 The BICCOS base version with BaB inferred cuts and constraint strengthening already shows competitive performance in many models. Cuts from MIP solvers are compatible with BICCOS and can be added for smaller models that can be handled by MIP solver. Integrating Multi-Tree Search (MTS) significantly boosts performance. On the CIFAR CNN-B CNN-B-Ady model, verified accuracy rises to 54.5%, outperforming
9

---

Table Ablation Studies on Verified accuracy (Var.%), avg. per-example verification time (s) analysis for all
method verified instances on different BICCOS components.
Danaset
Model
A-CROWN 64
GCP.CROWNOMIP cuts)
61
BICCOS (base) Timeis)
BICCOS (with MTS)
BICCOS (outo) Time(s)
Upper
2/255
(s)
Ver
Timels)
Ver
Ver
Timets)
MNIST
CNN-A-Ade
71.0
3.53
70.5
7.34
76.5
5.61
76.5
8.66
75.5
13.37
76.5
CNN-A-Ade
15.3
5.17
18.5
4.76
17.3
4.58
47.3
5,01
49.0
4.25
50.0
CNN-A-Adv-4
16.5
0.78
48.0
1.47
18.0
1.27
47.5
1.15
48.5
1.81
49.5
CUFAR
CNN-A
UNN-A-Mix
51.0
0.70
3.82
6.68
2.87
56.0
48.5
53.0
CNN-B-Ads
47.5
6.39
18.0
10.07
52.0
8.14
52.5
10.13
54.5
17.75
65.0
CNK-B- B-K---Adu-4
36.0
3.20
58.5
8.27
60.0
3.18
60.5
4.38
62.0
9.63
63.5
oval23
66.07
23.20
83.33
32.12
73.33
18.25
70,00
17.25
86,06
59.84
90.0
2014
35.3
15:48
61.3
62.5
inyimagenct- 2024
67.5
28.87
67.0
31,00
70.0
13.84
70.0
17.8
70.0
16.32
78.5
We run our BICCOS in diffirrntt ablation stulies with shorter 200s timcout For all models and compure it J-CROWN and GCRCCCOONN. achievess better verified accuracy than all other baselines.
GCP-CROWN with MIP cuts's 's 49%. We also design an adaptive BICCOS configuration (BICCOS auto), which automatically turns on MTS and/or MIP-based cuts according to neural network and verification problem size and quantity, achieves the highest verified accuracies across most of models and is used as the default option of the verifier when BICCOS is enabled. A detailed table with the numbers of cuts and domains visited is provided in Appendix C.2
5
Related work
Our work is based on the branch and bound framework for neural network verification [12] 17
159
28
54
16, 37 21I, which is one of the most popular approaches that lead to state-of-the-an
10 Most BaB-based approaches do not consider the correlations among subproblems for example, in 3-CROWN (54), the order of visiting the nodes in the BaB search tree does not change the verification outcome as the number of leaf nodes will be the same regardless of how the leaves are split. Our work utilizes information on the search tree and can gather more effective cuts when shallower nodes are visited first.
results
Exploring the dependency correlations among neurons has also been identified as potential avenue to enhance verification bounds. While several studies have investigated this aspect 16 42 50). their focus has primarily been on improving the bounding step without explicitly utilizing the relationships among ReLUs during the branching process. Venus [ considers the implications among neurons with constraints similar to our cutting planes. However, their constraints were not discovered using the verified subproblems during BaB or multi-tree search, and cannot be strengthened. On the other hand, cutting plane methods encode dependency among neurons as general constraints [61 35). and our work developed a new cutting plane that can be efficiently constructed and strengthened during BaB, the first time in literature.
In addition, some NN verifiers are based on the satisfiability modulo theories (SMT) formula- tions 32 46 19 36), which may internally use SAT-solving procedure [8] such DPLL 22 or CDCL 38 These procedures may discover conflicts in boolean variable assignments, corresponding to eliminating certain subproblems in BaB. However, they differ from BICCOS in two significant aspects: first, although DPLL or CDCL may discover constraints to prevent some branches with neurons involved in these constraints, they cannot efficiently use these constraints as cutting planes that may tighten the bounds for subproblems never involving these neurons; second, DPLL or CDCL works on the abstract problem where each ReLU is represented as a boolean variable, and cannot take full advantage of the underlying bound propagation solver to strengthen constraints as we did in Alg. Based on our observation in Sec. 3, the constraints discovered during BaB are often unhelpful without strengthening unless in a different search tree, so their effectiveness is limited. However, the learned conflicts can be naturally translated into cuts 3 making this a future work.
More related works on SMT, MIP solvers, nogood learning and cutting plane method in VNN
18
45
26
19
47
52
30
61 35 are diseussed in Appendix D
6
Conclusion
We exploit the structure of the NN verification problem to generate efficient and scalable cutting planes, leveraging neuron relationships within verified subproblems in a branch-and-bound search tree. Our experimental results demonstrate that the proposed BICCOS algorithm achieves very good scalability while outperforming many other tools the VNN-COMP, and can solve benchmarks that existing methods utilizing cutting planes could not scale to. Limitations are discussed in Appendix E
10

---

Acknowledgment Huan Zhang is supported in part by the A12050 program at Schmidt Sciences (AI2050 Early Career Fellowship) and NSF (IIS-2331667.. Grani A. Hanasusanto is supported in part by NSF (CCF-234) CCCF-2343869 and ECCS-2404413) Computations were performed with computing resources granted by RWTH Aachen University under project rwth1665, We thank the anonymous reviewers for helping us improve this work.
References
[1] VNN-COMP 2024 website. 10-30.
http://ogggg...oo//////////m222 Accessed: 2024-
[2] Ross Anderson, Joey Huchette, Will Ma, Christian Tjandraatmadja, and Juan Pablo Vielma. Strong mixed-integer programming formulations for trained neural networks. Mathematical Programming. 183(1-2):3-33) 2020.
[3] Stanley Bak. nnenum: Verification of relu neural networks with optimized abstraction refinement. NASA Formal Methods Symposium, pages 19-36. Springer, 2021.
[4] Stanley Bak, Changliu Liu, and Taylor Johnson. The second international verification of neural networks competition (vun-comp 2021): Summary and results. arXiv preprint arXiv:2199000498, 2021.
[5] Stanley Bak, Hoang- Dung Tran, Kerianne Hobbs, and Taylor T. Johnson. Improved geometric path enumeration for verifying relu neural networks. In Proceedings of the 32nd International Conference on Computer Aided Verification. Springer, 2020.
[6] Egon Balas and Robert Jeroslow. Canonical cuts on the unit hypercube. SIAM Journal on Applied Mathematics, 23(1):61-69) 1972.
[7] Dimitris Bertsimas and Robert Weismantel. Optimization over integers. Athena Scientific, 2005.
[8] Armin Biere, Marijn Heule, and Hans van Maaren. Handbook of satisfiability, volume 185. IOS press, 2009.
[9] Elena Botoeva, Panagiotis Kouvaros, Jan Kronqvist, Alessio Lomuscio, and Ruth Misener. Efficient verification of relu-based neural networks via dependency analysis. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3291-3299 2020.
[10] Christopher Brix, Stanley Bak, Changliu Liu, and Taylor T Johnson. The fourth international verification of neural networks competition (ynn-comp 2023): Summary and results. arXiv preprint arXiv:2312.16766) 2023.
[11) Rudy Bunel, Jingyue Lu, Ilker Turkaslan, Philip HS Torr, Pushmeet Kohli, and M Pawan Kumar. Branch and bound for piecewise linear neural network verification. Journal of Machine Learning Research, 21(42):1-39, 2020.
[12] Rudy R Bunel, Ilker Turkaslan, Philip Torr, Pushmeet Kohli, and Pawan K Mudigonda. A unified view of piecewise linear neural network verification. Advances in Neural Information Processing Systems, 31, 2018.
[13] Shaoru Chen, Lekan Molu, and Mahyar Fazlyab. Verification-aided learning of neural network barrier functions with ternination guarantees. arXiv preprint arXiv:2403.07300 2024.
[14] Michele Conforti, Gérard Coruuéjos,, and Giacomo Zambelli. Integer programming. Graduate texts in mathematics, 271. Springer, Cham, 2014.
[15] Sumanth Dathathri, Krishnamurthy Dvijotham, Alexey Kurakin, Aditi Raghunathan, Jonathan Uesato, Rudy R Bunel, Shreya Shankar, Jacob Steinhardt, Ian Goodfellow, Percy S Liang, al. Enabling certification of verification-agnosti networks via memory-efficient semidefinite programming. Advances in Neural Information Processing Systems (NeurIPS), 2020.

---

[16] Alessandro De Palma, Harkirat Singh Behl, Rudy Bunel, Philip H. S. Torr, and M. Pawan Kumar. Scaling the convex barrier with active sets. International Conference on Learning Representations (ICI.R). 2021.
[17]
Alessandro De Palma, Rudy Bunel, Alban Desmaison, Krishnamurthy Dvijotham, Pushmeet Kohli, Philip HS Torr, and M Pawan Kumar. Improved branch and bound for neural network verification via lagrangian decomposition. arXiv preprini arXiv: 104.000044066 2021.
[18] Rina Dechter. Enhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition. Artificial Intelligence, 41(3):273-312, 1990.
[19] Hai Duong, Linhan Li, Vu Nguyen, and Matthew Dwyer. dpll (t) framework for verifying deep neural networks. arXiv preprint arXiv:2307 10266, 2023.
[20] Ruediger Ehlers. Formal verification of piece-wise linear feed-forward neural networks. In Automated Technology for Verificution and Analysis: 15th International Symposium, ATVA 2017, Pune, India, October 3-6, 2017, Proceedings 15, pages 269-286. Springer, 2017.
[21] Claudio Ferrari, Mark Niklas Muller, Nikola Jovanovic, and Martin Vechev. Complete verifica- tion via multi-neuron relaxation guided branch-and-bound. arXiv preprint 4rXiv:2205.0026: 2022.
[22] Harald Ganzinger, George Hagen, Robert Nieuwenhuis, Albert Oliveras, and Cesare Tinelli. Dpll (t): Fast decision procedures. Computer Aided Verification: 16th International Conference, CAV 2004, Boston, MA, USA, July 13-17, 2004. Proceedings 16, pages 175-188. Springer, 2004.
[23] Timon Gehr, Matthew Mirman, Dana Drachsler- Petar Tsankov, Swarat Chaudhuri, and Martin Vechev. Ai2: Safety and robustness certification of neural networks with abstract interpretation. In 2018 IEEE Symposium on Security and Privacy (SP). IEEE, 2018
[24] Paul C Gilmore and Ralph Gomory, A linear programming approach to the cutting stock problem- -artt ii Operations research, 1 11(6):833-888, 1963.
[25] Julien Girard-Satabin, Michele Alberti, Francois Bobot, Zakaria Chihani, and Augustin Lemesle. Caisar: platform for characterizing artificial intelligence safety and robustness. arXiv preprint arXiv:2206.0304 2022.
[26] Carla P Gomes, Bart Selman, Henry Kautz, et al. Boosting combinatorial search through randomization. AAAA/AAI, 98(1998):411-437, 1998.
[27] LLC Gurobi Optimization. Gurobi optimizer gurobi, 2022.
[28] Patrick Henriksen and Alessio Lomuscio. Efficient neural network verification via adaptive refinement and adversarial search. In ECA/ 2020, pages 2513-2520. IOS Press, 2020.
[29] Patrick Henriksen and Alessio Lomuscio. Deepsplit: An efficient splitting method for neural network verification via indirect effect analysis. In Proceedings of the 30th international joint conference on artificial intelligence (ICCAI2I), pages 2549-2555, 2021.
[30] Joey Huchette, Gonzalo Muñoz, Thiago Serra, and Calvin Tsay. When deep learning meets polyhedral theory: A survey, arXiv preprint Xii.:2335.0022:: 2023.
[31] IBM. Ibm ilog cplex optimizer, 2022.
[32] Guy Katz, Derek A Huang, Duligur lbeling. Kyle Julian, Christopher Lazarus, Rachel Lim, Parth Shah, Shantanu Thakoor, Haoze Wu, Aleksandar Zeljić, et al. The marabou framework for verification and analysis of deep neural networks. In International Conference on Computer Aided Verification (CAV), 2019.
[33] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations (ICLR), 2015.
[34] Panagiotis Kouvaros and Alessio Lomuscio. Towards scalable complete verification of relu neural networks via dependency- branching. In IJCAI, pages 2643-2650, 2021.
12

---

[35] Jianglin Lan, Yang Zheng, and Alessio Lomuscio. Tight neural network verification via semidefinite relaxations and linear reformulations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7272-7280, 2022.
[36] Zongxin Liu, Pengfei Yang. Lijun Zhang, and Xiaowei Huang. DeepCDCL: An CDCL-based neural network verification framework. arXiv preprini arXiv:2403.0799 2024.
[37] Jingyue Lu and M Pawan Kumar. Neural network branching for neural network verification. arXiv preprint (9ti:v:9912001999 2019.
[38] Joao Marques-Silva. Inés Lynce, and Sharad Malik. Conflict-driven clause learning SAT solvers. In Handbook of satisfiability, pages 182. ios Press, 2021.
[39] Christoph Müller, Francois Serre, Gagandeep Singh, Markus Püschel, and Martin Vechev. Scaling polyhedral neural network verification on gpus. Proceedings of Machine Learning and Systems, 3:733-746. 2021.
[40] Mark Niklas Müller, Christopher Brix, Stanley Bak, Changliu Liu, and Taylor T Johnson. The third international verification neural networks competition (ynn-comp 2022): Summary and results, arXiv preprint vrXiv:221..10377 2022.
[41] Mark Niklas Müllrr, Gleb Makarchuk, Gagandeep Singh, Markus Püschel, and Martin Vechev. Precise multi-neuron abstractions for neural network certification. arXiv preprint arXiv:2103.03638, 2021.
[42] Mark Niklas Müller, Gleb Makarchuk, Gagandeep Singh, Markus Püschel, and Martin Vechev. Prima: general and precise neural network certification via scalable convex hull approximations. Proceedings of the ACM on Programming Languages, 6(POPL):133, 2022.
[43] Mark Niklas Müller, Christopher Brix, Stanley Bak, Changliu Liu, and Taylor T. Johnson. The third international verification of neural networks competition (ynn-comp 2022): Summary and results, 2023.
[44] Chongli Qin, Brendan O'Donoghue, Rudy Bunel, Robert Stanforth, Sven Gowal, Jonathan Uesato, Grzegorz Swirszez, Pushmeet Kohli, et al. Verification of non-linear specifications for neural networks. arXiv preprint arXiv:1902.00 09592, 2019.
[45] Tuomas Sandholm and Robert Shields. Nogood learning for mixed integer programming. In Workshop Hybrid Methods and Branching Rules in Combinatorial Optimization, Montréal, volume 20, pages 21-22, 2006.
[46] Karsten Scheibler, Leonore Winterer, Ralf Wimmer, and Bernd Becker. Towards verification of artificial neural networks. In MBMV, pages 30-40, 2015.
[47] Thiago Serra and Srikumar Ramalingam. Empirical bounds on linear regions of deep rectifier networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pages 5628-568 5635, 2020.
[48] Zhouxing Shi, Qirui Jin, J Zico Kolter, Suman Jana, Cho-Jui Hsieh, and Huan Zhang. Formal 2nd Workshop
verification for neural networks with general nonlincarities via on Formal Verification of Machine Learning, 2023.
[49] Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for certifying neural networks. Proceedings of the ACM on Programming Languages (POPL), 2019.
[50] Harkirat Singh, M Pawan Kumar, Philip Torr, and Krishnamurthy Dj Dvijotham. Overcoming the convex barrier for simplex inputs. In Advances in Neural Information Processing Systems, 2021.
[51] Chuangchuang Sun, Dong-Ki Kim, and Jonathan P How. Romax: Certifiably robust deep multiagent reinforcement learning via convex relaxation. 2022 International Conference on Robotics and Automation (ICRA), pages 5503-5510, IEEE, 2022.
13

---

[52] Calvin Tsay, Jan Kronqvist, Alexander Thebelt, and Ruth Misener. Partition-based formulations for mixed-integer optimization of trained relu neural networks. Advances neural information processing systems, 14:3068-3080) 2021.
[53] Andreas Venzke and Spyros Chatzivasilciadis. Verification of neural network behaviour: Formal guarantees for power system applications. IEEE Transactions on Smart Grid, 12(1):383-397 2020.
[54] Shiqi Wang. Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and J Zico Kolter. Beta-crown: Efficient bound propagation with per-neuron Split constraints for neural network robustness verification. Advances in Neural Information Processing Systems, 34:29909-29921, 2021.
[55] Eric Wong. Tim Schneider, Joerg Schmitt, Frank R Schmidt, and J Zico Kolter. Neural network virtual sensors for fuel injection quantities with provable performance specifications. In 2020 IEEE Intelligent Vehicles Symposium (IV), pages 7758- IEEE, 2020.
[56] Haoze Wu, Omri Isac, Aleksandar Zeljić, Teruhiro Tagomori, Matthew Daggitt, Wen Kokke, Idan Refaeli, Guy Amir, Kyle Julian, Shahaf Bassan, al. Marabou 2.0: a versatile formal analyzer of neural networks. In International Conference Computer Aided Verification, pages 249-264. Springer, 2024.
[57] Junlin Wu, Andrew Clark, Yiannis Kantaros, and Yevgeniy Vorobeychik. Neural Iyapunov control for discrete-time systems. Advances in Neural Information Processing Systems, 36:2939
2955, 2023.
[58] Kaidi Xu, Zhouxing Shi, Huan Zhang. Yihan Wang, Kai- Kai-Wei Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsich. Automatic perturbation analysis for scalable certified robustness and beyond. Advances in Neural Information Processing Systems, 33:1 (19-1144) 2020.
[59] Kaidi Xu, Huan Zhang, Shiqi Wang. Yihan Wang. Suman Jana, Xue Lin, and Cho-Jui Hsieh. Fast and complete: Enabling complete neural network verification with rapid and massively parallel incomplete verifiers. International Conference on Learning Representations (ICLR), 2021.
[60] Lujie Yang, Hongkai Dai, Zhouxing Shi, Cho-Jui Hsieh, Russ Tedrake, and Huan Zhang. Lyapunov-stable neural control for state and output feedback: A novel formulation for efficient synthesis and verification. arXiv preprint arXiv:2404.07956 2024.
[61] Huan Zhang, Shiqi Wang. Kaidi Xu, Linyi Li, Bo Li, Suman Jana, Cho-Jui Hsich, and J Zico Kolter. General cutting planes for bound- propagation- based neural network verification. Ad- vances in Neural Information Processing Systems, 35:1656-16700 2022.
[62] Huan Zhang, Teu Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neu- ral network robustness certification with general activation functions. Advances in neural information processing systems, 31, 2018.
14

---

Appendix
In Sec. A we introduce the Mixed Integer Programming (MTP) formulation for Neural Network Verification and explain how to get the lower bound by solving the LP relaxation and Planet relaxation. In Sec. [ provide the complete proof for Proposition [.1 and Theorem [.2] and Corollary [.3
Then, in Sec. [ we present the configuration, ablation study, and additional experimental results.
Finally in Sec. D andd Sec.
B
we discuss more related works and limitations of our method.
A MIP Formulation and LP & Planet Relaxation
The MIP Formulation The mixed integer programming (MIP) formulation is the root of many NN verification algorithms. Given the ReLU activation function's 's piecewise linearity, the model requires binary encoding variables, or ReLU indicators z only for unstable neurons. We formulate the optimization problem aiming to minimize the function f(æ), subject to a set of constraints that encapsulate the DNN's architecture and the perturbation limits around given input æ, as follows:
f = min f(x) s.t. f(x) (0))0000 E X; x az
(4)
x0
(0 iE [L),
(5)
I+0 = (i: ;
= u. ( 20) -0:100 s 50,
u
2 0}.
(6)
I+0 1z j())
(7)
(8)
8 222")ee0,,ie(L1
(9)
1 je
(10)
4 - [L- 1]
(11)
( [01])j]e77)
2
(12)
( [ij 1]
(13)
/ 0:j ii [1-1] 1].
(14)
Here, the set J(t comprises all neurons in the layer i, which are further categorized into three distinct classes: 'active' (I+()), 'inactive" (I-(1), and 'unstable' (I());; we further let ( - minaex minaxxx 11 (z), u. max 15 (x), Vj E J -]. The MIP approach initialized with pre-activation bounds (() << (() (i) for each neuron within the feasible set X, across all layers i. These bounds can be calculated recursively through the MIP from the first layer to the final layer. However, MIP problems are generally NP-hard as they involve integer variables.
The LP and Planet relaxation By relaxing the binary variables 12
E j E IO, i
[L. 1]. we can get the L.P relaxation formulation. By replacing the constraints in 10 11 12
with
10
10 100;
(E-
(15)
can eliminate the variables and get the well-known Planet relaxation formulation. Both of these two relaxations are solvable in polynomial time to yield lower bounds.
Lemma A.1. In the LP relaxation, splitting an unstable ReLU neuron (i.j) based on 2j 0 is
equivalent to setting 2 < ug) = 0 in the Planet relaxation with the relaxed variable z E [0. 1] projected out. Correspondingly, splitting based on 2 1 is equivalent to setting x)) 4
(1) 0.
Proof: An unstable neuron (i.j) one where the pre-activation bounds satisfy ((9) < 0 < u
could be represented as the following system in LP relaxation: g 10
12 and the system in Planet
15

---

We will now analyze the two cases of fixing 2) to 0 and in the LP relaxation and show their equivalence to modifying the bounds uj (i) and 1.00 in the Planet relaxation.
relaxation: 8
15
1.
0 in LP relaxation
U 0 in Planet Relaxation.
Assume 2/ = 0 LP relaxation. From 10
I
x
0
=
5j v 0. From
410)
z O. Combining the above, we get 4 O. From
11
S
x - 110 (1 0)
9 Since / = 0 and 9 this simplifies to 0
0 0 2 2 1
(0)
This is consistent with the pre-activation bounds of the neuron. Therefore, fixing 3j 0 in
the LP relaxation forces the activation 2 to be zero, effectively modeling the neuron as inactive.
(+) Assume u (8) 0 in the Planet relaxation. Set u ( 0. The constraint 15 becomes
(1) 1(0) O. From
N Combining the above, we get a:(0)
0-15
Thus, setting (i) O in the Planet relaxation also forces 154 to zero, mirroring the effect
of fixing 2g 0 in the LP relaxation.
(4)
2. (0)
1 + 10) 0. The proof follows similar step.
2
B Proof of Main Results
B.1 Proof of Proposition 3.1
Proof: Due to the relationship between the x and z in Lemma
A.I i.e. for any unstable neuron i,
J; 4 + 2; 1 and x; S u, = 0 < 2, = = (1 zi) 1, we have the following
equation to represent an UNSAT path:
Σ + 2
=1=
(16)
By taking negation of Eq
1o exclude this path, we have:
Σ
2
E - 2,)
2 + + 1
(17)
S
IE2
Σ +
Σ
(1 2))
+ 1
(18)
s
1E2
Notice that E [0, 1] implies that the sum of should be bounded by its cardinality, Σiez+
Eiez-(1-20 2) < |z + 11, and the binary indicator property, thus only consider inequality 18
Σ SEZ
+
Σ (1 = Σ -
Σ 2 M 2 +
(19)
Z
Z
Thus, the BaB inferred cut cutBcan can be used to exclude this UNSAT status.
B.2 Proof of Theorem
To derive the bound propagation, first, we assign Lagrange dual variables to each non- non-trivial constraint in LP relaxation with any BaB split set 2. Next, we analyze how splitting on the ReLU indicator influences the generation of these dual variables. This analysis helps us determine the impact of the splits on the dual formulation. Then, we formulate the Lagrangian dual as min-max problem. By applying strong duality and eliminating the inner minimization problem, we can simplify the dual formulation. Finally, this results in dual formulation that we use to perform bound propagation effectively.
16

---

Theorem 3.2. Given any BaB split set 2, optimizable parameters 0 S a 1 and B, T 2 0. (0)* Jj is function of Q.
1-1 EO - -3 d
(.,T) = -ellv (1) w xollı Σ
Σ
i=1 jezú)
where variables (+) are obtained by propagating v(L) = -1 throughout all E [T--1}
(1 (++1) ((+1)) 3 H G jEI+()
3 ( (++)T w (6+1) BT H +
+ + + jez
(1 B H 1 j E IEIT EI( (9)
11 99 B H 1 - 1j
(1) jez
(1) (0)* f B
H j E I z
Here o "j and 7/") are defined for each unstable and without split neuron E I(0 2 and
(t)* (1) (3) is defined for all unstable neurons j E I(O
10 I+ max max(x((+1) W (i+1) 3 G (0) .),00,, 0), 10 min( (i+1)((++)TT)
w( :1
3 B 0)
(8)
(1)
+ B TTQ
10 max
(0) 1+ .0) . E 2(1) 1(
min
(i) (/
u
( (a)*
if 10 + 2 B Q0 s ug
(1)
(1
10 laad j EI( 120,
1/9 (g)
if B Q 2 " D I+ orj
(1)
orj 3TQ. 0ri
Proof: First we write down the primal formulation, and assign the Lagrange multipliers:
f== min fxx
s.t.
f(x) x (
- S 3α +
(0) W (i-1) + bb,; [L)
+ 5 E ER4
For i ELL - 1]:
(1] 2 0; ((()
M1 E ER, j E I(1) \ 1--(1)
(
;
8) ( "² (
1j ERti E ((i) zz((
(
" jEZ
25 (0)
7j E ERt,j E T(1)
(
2
10
8) (0) S0, ( -1 ( jez(
(
ER,j (())
z
7j
$ = (1)
1 jerto
13
$ = =0
14
0 05 (1)
< 1 E z(0)
\ z(
12
2)
( =1,jj zt(0); 2/ = E z-
(20)
( 0000 (00) s
+
R
Note that for some constraints, their dual variables not created because they trivial to handle in the steps. And from Lemma some unstable neuron constraints g 10 during BaB with split on i.c. when 2,0 1, the unstable neuron constraints will be reduced to
will be eliminated
17

---

= + 10j E RR+ other dual variables for constraints 9
(0)
10 11 will not be generated,
and when 2/ 0, only 7j E R2 will be generated. Rearrange the equation and swap the min and
max (strong duality) gives us:
max min (w(L) + 1)ae()) - (a) P.I.i. B 2,
(() (())
Σ jET+()
(
B H (41)
w ()+
:.f + 3 ( o
( + B
H
(+11
# - x
JEZ+())
+
+ Σ Σ
(1))) + 13 H + + - a
JEZ- (i)
i=1 jEZ (1)
( + +
-
/ (1) 2
JEZG)
w( :0
(0)
+
+ (-u0
(1)
(0) T
(1)
L-1
(0)
+ Σ
Σ
-
[=1
1=1 jEZ (())
S.L.
Co - é S x S 30 +
0 0 }j
(i)
S 1, E I(0 z
3 -1jE 2f
-,
H 220 0; T 2 720: π 720: 0; 220 0
Here ((+1) denotes the j-th column of ( Note that for the term involving j E E U 2+()
(1) we have replaced (()) with (+)) to obtain the above equation. For the term a .j E u z it is always 0 so it does not appear. Then solving the inner minimization gives us the dual formulation:
=ell W()) Σ ( b 1 -
max p.
(21)
jEZ
s.t. (L)
(22)
5/0 = 2 (+11
W w((+1) - 3T -3 (HH (H ( + G for j jEI+())
iE [L -1] 1]
(23)
5/ - 11)T
w (++1) -3T (HH ( + c + u4
3 for j z+0)
i [L- 1]
(24)
(0) = BT H (0)
for jEI-0 iE L 1-1 1]
(25)
5/0 = B T H JJ
(
for jE Z 0 iE [L -1
(26)
(0) = T. T
( - H
(1) for j j | 1()), i -| (27)
1 1 9)
+ T
(1) (+DT 0+ B Cg. for j j \ 1((),
i [T. - 1]
(28)
18

---

where 1/9 in the objective 21 is:
min
1
- + B Q + 2
+
(-
(29)
(0)
if E Z+(0)
0
if TijE-1 Z-
(30)
00 3
ReI.U(u (0 + -
if E I 2
The RcLU(-) term comes from minimizing over 2j with the constraint 1 =2) S 1. And when
splitting on E z(0,, as we discussed above, based on Lemma A.1 there will be no zj 7 assigned for the constraints. The || -11 comes from the dual norm form minimizing over the infinite norm of the input æ with the constraint 26 E S Do c.
Thus, the rest of the proof follows from [6]] Lemma A.1, Theorem 3.1], which completes the proof of Theorem 3.2
B.3 Proof of Corollary 3.3
Proof. Let us consider any assignment of the variables {z:} where 2; E {0, 1} that satisfies cut 3.1 We aim to show that this assignment also satisfies cut 3.2
Since Z7 C z there exists at least neuron such that & 2 but & & 2tt Let 2 2
z denote the additional neurons in the larger cut 3.2 Similarly, define 2(4) 2g \ 2T.
In cut 3.2 the left-hand side (LHS) be expressed as:
LHS
3.
Σ 24 +
Σ
Σ 24 (E2(A)
iE2
iE2(()
(A)
iE2
Similarly, the right-hand side (RHS) of cut 3.2 is:
RHS
2 +
12
Subtracting Eq.
3.1 from cut
3.2
get:
LHS
Σ 2
Σ
Σ 2,
Σ 4
3
iEZ7
iEZT
(E2(
iEZ(
RHS 2
(1Z 1) = |
Therefore, the difference between the LHSS and RHS of the cuts is:
Σ 24
Σ
2
iE2(A) (
142(4)
Since each z; {0, 1). the maximum value of EiEz(a> Zz is ||(اح|, and the minimum value of
Eieg(a) 2; is 0. Thus, the maximum possible value of the LHS difference is 2({) which equals the RHS difference.
Therefore, regardless of the values of fori e z(A) U z(A) the inequality:
19

---

Σ iEZ
2
24
iEZ(
is always satisfied. This means that satisfying cut 3.1 ensures that cut 3.2 is also satisfied.
Conversely, consider an assignment where cut
3.2 is satisfied but cut 3.1 is violated. This can happen
if the additional variables in 2{4i and z!4 compensate for the violation in the original variables.
For instance, setting =i 1 for all i E 2(4) and 2; 0 for all i و can decrease the LHS of
cut 3.2 making it easier to satisfy even cut 3.1 is not satisfied.
Therefore, the feasible region defined by cut 3.1 is subset of the feasible region defined by cut 3.2 confirming that i. stronger.
C Experiments
C.1 Experiment Settings
Our experiments are conducted on a server with an Intel Xeon 8468 Sapphire CPU, one NVIDIA H100 GPU (96 GB GPU memory), and 480 GB CPU memory. Our implementation is based on the open-source a,3-CR R.B-CROWN verifier with cutting plane related code added. All experiments use 24 CPU cores and GPU. The MIP cuts acquired by the cplex (3 solver (version 22.1.0.0)
We use the Adam optimizer 3 to solve both a. f, jt, т. For the SDP-FO benchmarks, we optimize those parameters for 20 iterations with learning rate of 0.1 for and 0.02 for [3, 1. 7. We decay the learning rates with a factor of 0.98 per iteration. The timeout is 200s per instance. For the VNN-COMP benchmarks, we use the same configuration u,8-CROWN used in the respective competition and the same timeouts. During constraint strengthening, we set dtropppereettae 50%. We only perform round of strengthening, with recursive strengthening attempts. We perform constraint strengthening for the first 40 BaB iterations. For multi tree search, we perform branching iterations, where each time pick the current best 50 domains and split them to generate 400 new sub-domains.
C.2 Ablation Studies: Number of Cuts and Branch Visited Analysis
The ablation studies provide insights into the impact of different components of the BICCOS algorithm on the verification process, focusing on the average number of branches (domains) explored and the number of cuts generated, as shown in Table 4 A lower number of branches typically indicates a more efficient search process, leading to computational savings and faster verification times.
Across the benchmarks, we observe that the BICCOS configurations, particularly BICCOS (auto), often explore fewer branches compared to the baseline 3-CROWN and GCP-CROWN methods. For instance, on the CIFAR CNN-A-Ady model, BICCOS (auto) reduces the average number of branches from 63,809.77 (for 3-CROWN) and 28,558.70 (for GCP-CROWN) down to 9,902.96. This reduction attributed to the cutting planes introduced by the BICCOS algorithm, which tighten the relaxations and more effectively prune suboptimal regions of the search space.
The multi-tree search (MTS) strategy, which explores multiple branch-and-bould trees in parallel, demonstrates its effectiveness in improving verification efficiency. While MTS may increase the total number of branches explored since domains from multiple trees are counted -tee exploration within each tree is optimized, leading to faster convergence and reduced overall computation time. We also design an adaptive BICCOS configuration (BICCOS (auto)), which automatically enables MTS and/or Mixed Integer Programming (MiP)-based cuts based on the neural network and verification problem size. BICCOS (auto) achieves the highest verified accuracies across models and is used as the default option of the verifier when BICCOS is enabled.
20

---

Table 4: Ablation Studies on avg. # cuts and branches visited analysis for BaB verified (hard) instances on
different BICCOS components.
Dutaner
Model
5 CROWS S.
GCP CROWN
61
BICCOS (hose)
BICCOS (wit MTS)
BICCOS (suto)
0.3 and 2/233
domane vistte
CUE
domain visned e
CUT
(ommai sistted f
<Ut 9
.ommon vistted R
domaan visted ef
cut
MNIST
CNN-A-Adl
$145 14
0
5469 26
492-20
$330.67
113.56
3549.05
132.05
2857 255
611.50
CNN-A-Adl
63502
0
255558770
353.40
18611.88
107.00
3013427
159.64
0902356
518.83
ANN-A-Ade-4
14875.85
15515.58
565.27
7833,50
131.00
74100-00
132.09
6730.61
691.00
CNN-A--Mix
24865
27719.75
435.77
11832.11
118.00
122.88.0 09
131 151:25
15715
597.56
CNN.A-Mir--
1565
18371.2
601
26608
154.25
62
143.62
10019 78
752.10
19106.40
12309.6
273.78
163.06
198.54
12782.82
332.17
Adx
20987.00
207.71
91.2
11585.87
90.90
10589:31
175.30
25917755
5718.7
153K07
1934700
128.75
852.11
147.22
1216.49
145.55
Bay Emngeree different ablation with shorter nimeout models compare 50 B-CROWW and
912397
13439
890.31
199211
874705
151.20
achieves better verified accurnc
stan Posolines.
However, is worth noting that on certain benchmarks, such as the CIFAR CNN-A-Mix-4 model, the number of branches explored by different BICCOS configurations does not always decrease compared to the baselines. In some cases, the base BICCOS version explores more branches than 3-CROWN. This could be attributed to the models' inherent complexity and the nature of the verification problem, where the benefits of the cutting planes and MTS may be less pronounced.
Overall, the analysis of the average number of branches in the ablation studies highlights the effectiveness of the BICCOS algorithm and its components in improving the efficiency of the verification process. The combination of cutting planes, multi-tree search, and other optimizations enables BICCOS to achieve high verified accuracy while often exploring fewer branches compared to baseline methods, ultimately leading to computational savings and faster verification times.
C.3 Comparison with MIP based Verifier
To evaluate the performance of the BICCOS cuts in MIP-based solvers, Fig shows comparison with Venus2 99 34). We emphasize on making a fair comparison on the strengths of cuts. Since Venus2 uses an MILP solver to process its cuts, in these experiments we do not use the efficient GCP-CROWN solver. Instead, we also use an MILP solver to handle the BICCOS cuts we found. This ensures that the speedup we achieve is not coming from the GPU-accelerated GCP-CROW) solver. Since our cut generation relies on the process with BaB, we first run BICCOS to get the cuts, and then import the cuts into the MILP solver.
We note that Venus uses branching over ReLU activations to create multiple strengthened MILP problems. On the other hand, we only create one single MILP and do not perform additional branching. Therefore, our MILP formulation is weaker. The fact that we can outperform Venus2 anyway underlines the strength of the generated cuts by BICCOS.
C.4 Overhead Analysis
We note that the multi-tree search (MTS) and cut strengthening procedure incur additional overheads compared to the baseline verifiers shown as Fig 4 The MTS has about 2 - 10 seconds overhead in the benchmarks we evaluated, which may increase the verification time of very easy instances that can be sequentially immediately verified in branch and bound. The BICCOS cut strengthening is called during every Branch-and-bee instances in each benchmark, which run a few hundred rranch-and-boumd iterations. We note that typically, the performance of the verifier is gauged by the number of verified instances within fixed timeout threshold, thus when the threshold is too low, the added cutting planes may not have time to show their performance gains due to the lack of sufficient time for the branch-and-bont procedure.
iteration, but its accumulative cost is about 3 20 seconds for hard
We note that such shortcoming is also shared with other verifiers which require additional steps for bound tightening; for example, the GCP-CROWN verifiers have the extra overhead of few seconds of calling and retrieving results from the MIP solver, even when the MIP solver is running in parallel with the verifier. The final verified accuracy can justify whether the overhead is worth paying.
D More Related Works
Furthermore, nogood learning and conflict analysis techniques from constraint programming and SAT solving have been adapted to neural network verification to improve solver efficiency [18 45 26 19
21

---

Number Instances Verified Time
Number of Instances Verified vs. Time
venus2
venusz
MILP with BICCOS
MILP with BICCOS
Time Limit (200)
Time Limit (200)
T1me
Number Instarices Verified caaarr_nn____eee __svv
Number Instances Verified cifar cnn a addd
Number Instances Verified Time
Number of Instances Verified vs.
venus2
20
MILP with BICCOS
155
Time Limit (200)
venus2
Time
MILP with RICCOS
Time Limit (200)
Number instances Verified in cifar_cnn_e_ con_a__ix
Number Instances Verified in cifar_cnn_e aaar__nn_a__iiaaa
Figure 3: Comparison of Venus2 and MILP with BICCOS. For a fair comparison, we do not use GPU- accelerated bound propagation but a MILP solver (same as in Venus2) to solve the verification problem with our BICCOS cuts. In all 4 benchmarks, MILP with BICCOS cuts faster than Venus (MILP with their proposed cuts), illustrating the effectiveness. Note that Venus2 can hardly scale to larger models presented in our paper, such as those on cifar100 and tinyimagenet datasets.
11. These methods record conflicts encountered during the search- known nogoods to prevent revisiting the same conflicting states, effectively pruning the search space. While nogood learning can reduce redundant exploration, typically operates on discrete abstractions of neural networks, representing ReI.U activations as boolean variables. This abstraction limits their ability to leverage the properties of neural network activations. In contrast, our approach only identifies conflicts but also translates them into cutting planes within the continuous relaxation of the verification problem. This allows us tighten the bounds for unexplored subproblems, enhancing the overall efficiency of the verification process.
Mixed Integer Programming (MIP) solvers, such cplex 31 and gurobi 27 have also been applied to neural network verification by formulating the problem as a mixed-integer linear pro- gram 6 These solvers inherently utilize
algorithms and incorporate sophisticated cutting plane generation techniques to tighten the feasible region. However, in practice, applying general-purpose MIP solvers to large-scale neural networks presents significant challenges. For instance, in our experiments with benchmarks like CIFAR100 and Tiny-Imaeeeet-aa where network sizes range from 5,4 million to over 30 million parameters -eaeetterseelleex was unable solve the initial LP relaxation within the 200-second timeout threshold. As result, the branch-and-bont process and cut generation did not commence, underscoring the limitations of using off-the-shelf MIP solvers for large-scale neural network verification tasks.
In terms of cutting plane methods, prior work has explored integrating cuts derived from convex hull constraints within MIP formulations of neural networks (2 47 52 30, propose cutting planes that tighten the relaxation of ReLU constraints in MILP formulations, im- proving solution quality. While these methods can enhance optimization, they often incur significant computational overhead in generating and integrating cuts and rely heavily the capabilities of the underlying MIP solver. In contrast, our approach develops new cutting planes that can be effi- ciently constructed and strengthened during the branch-and-boume process, leveraging the problem's structure to achieve better scalability and performance.
61 35]. For example, 2
22

---

Number of Instances Verified vs. Time
Number of Instances Verifled vs. Time
Beta CROWN
Beta CROWN
29
Biccos base
175
Biccos base
Biccos
Biccos,
CROWN
GCP CROWN
Time
Biccos_ad autoo
Time
Biccos_aa cecos_auto
Time Limit [200)
time Limit (203)
Number of Instances Veniiid in cifar con. a. a_adv
Number of Instances Verified in cifar cnn, advu
Number of Instances Verified vs. Time
Number of Instances Verifled vs. Time
Beta CROWN
Beta CROWN
29
Biccos base
315
Biccos, base
Biccos,
CROWN
GCP CROWN
Time
Biccos_eade
Biccos_aule
Time Limit (200)
Time Limit (200)
Number of Instances Verfied cifar cnn. mix
Number of instances Verified cifar mix4
Number of Instances Verified Time
Number Instances Verified vs. Time
Beta CROWN
Beta CROWN
Biccos_ base
BICCOS Base
30
Biccos_ MTS
Biccos
GCP CROWN
Time
Biccos a_ttoo
Biccas, Auto
Time Limit (200)
Time Limit (200)
Number Instances Verified cifar_cnn_ b_adv
Number of Instances Verified cifar_cmm b_adv4
Figure 4: Slow down comparison on easier properties on BICCOS (base), BICCOS (MTS), GCP- CROWN with MIP cuts and BICCOS (auto) We plot the number of solved instances versus verification time for BICCOS and 3-CROWN (baseline). For easy instances that can be verified within a few seconds (bottom parts of the figures), the increase of verification time with BICCOS is negligible.
Our work bridges the gap between conflict analysis methods like nogood learning and cutting plane techniques by integrating conffict-derived constraints into the continuous relaxation the verification problem. This integration allows for both effective pruning of the search space and tightening of the problem relaxation, leading to improved verification efficiency. By tailoring our approach to the specifies of neural network verification, address the limitations observed in general-purpose MIP solvers when applied to large-scale networks, offering a scalable and efficient solution.
E
Limitations
The approach relies on the piecewise linear nature of ReLU networks (same as most other papers in BaB), and its applicability to other types of neural architectures requires further extension such as those in 48). Additionally, the effectiveness the generated cutting planes may vary depending on the specific structure and complexity of the neural network being verified, and there may be cases where the algorithm's performance gains are less pronounced.
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our claims match theoretical and empirical results. We present results across several benchmarks to demonstrate that they can generalize to other settings.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Limitations have been explicitly discussed in the conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

Justification:
Theoretical results have been proven.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proof' can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Algorithms have been clearly described with technical details discussed. Parameters for experiments have been included in the appendix. The code will be open- sourced.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
25

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: BICCOS has been added to the a,B-CROWN toolkit.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ praips.cc/ubblicgguuueee CoodeSumeeieeeeee ssi iessonPolll mollicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experimental details have been discussed in the Experiments section and also in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: Verification results are deterministic on the benchmarks, and no error bars need to be provided.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
26

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Time has been reported in tables and we only need one machine and one GPU to run all experiments. The specific hardware details reported in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
We have read and acknowledged the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Societal impacts have been discussed explicitly in Section 7.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
27

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No data models released.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
We've cited the sources of the benchmarks used, such those from the VNN-COMP.
Justification:
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
28

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets are introduced in this paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
29

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "twJXcCcCvg", "reviewer": "Reviewer_SS1K", "summary": "This work proposes a new approach to produce cutting planes in the context of branch-and-bound-based solvers for neural network verification. Whenever an infeasible subproblem is encountered in branch-and-bound, this method generates a cut from the conflicting assignment that led to the infeasible subproblem (initially redundant w.r.t. the remainder of the tree), and attempts to strengthen this cut by heuristically dropping some of the assignments and rechecking for infeasibility via the lower bound. This is further enhanced by using several parallel shallow trees to produce stronger cuts. This method is implemented on top of the $\\alpha,\\beta$-CROWN framework and provides meaningful computational improvements compared to various baselines on a set of benchmarks.", "questions": "General comments:\n\n1. I see that your variable-to-drop selection heuristic is based on their improvements to the lower bound in the tree. While this seems reasonable as a fast heuristic since you already have all the data, these improvements are not independent from each other since they are constrained over previous assignments, and thus there is some bias depending on the depth (i.e. if the assignments were done in a different order in the tree, you'd select different variables, but the constraint is the same). This makes me wonder if there is a better heuristic. Have you considered other approaches?\n\n2. It seems that you try to continue strengthening the cuts based on a fixed drop percentage. I am curious if you have tried something more like a binary search approach over the verification bound? You can also add some sort of tolerance on the bound to stop searching when you are close enough to zero.\n\n3. In Algorithm 1, lines 12-13, you add the cut, and then try to strengthen it again. It sounds like you could just add the best cut here, instead of adding all cuts throughout strengthening, since the best cut dominates the other ones.\n\n4. I appreciate the explanation of the differences between this method and [7] and DPLL/CDCL in the Related Work section, as both of these were in my mind as I was reading the paper. However, I'd like to comment that the reasoning for CDCL makes it sounds like it is impossible in practice to use learned clauses from CDCL as cuts; rather, I believe this is more of a challenging engineering task than not being practically viable. Much like branch-and-bound has been customized for NN verification in a more effective way than generic MIP solvers, I do not see a reason why one would not be able to customize ideas from CDCL for your cut generation procedure. The learned conflicts can be naturally translated to the type of cuts you have in Sec. 3.1 of this paper (except already stronger) and then further strengthened in the same way. Given that CDCL is a tried-and-true method to produce good conflicts, I suspect that this might lead to better cuts and may be interesting future work that would already fit very well with what you have so far.\n\n5. I would have liked to see some data to better understand the cuts generated. In particular, what is the fraction of infeasible nodes from which you were able to produce a (non-redundant) cut, and what was the total number of cuts? What was the average number of assignments that you were able to drop? This sort of data would reveal more information on the overhead of these cuts and how easy or hard it is to find them. I wonder if some cut selection procedure would make sense here, but I do not know if you have many or few cuts.\n\nComments on text:\n\n6. In the MIP section, it would be useful to mention that MIP is also based on branch-and-bound, and modify the last sentence to include why a custom branch-and-bound is more effective than MIP branch-and-bound in practice (e.g. because MIP is based on solving LPs which can be expensive, etc.).\n\n7. In Sec 3.1., I suggest preparing the reader to the fact that the cuts from Sec. 3.1 are redundant w.r.t. the tree until strengthened, instead of waiting until Sec. 3.2 to mention that. This is a question one would naturally have while reading Sec. 3.1, and it would make the reading easier if they already know the answer to that question.\n\n8. Figure 2 is a bit too small to read especially when printed out. If possible, please make it larger.\n\n9. Can you include in the text that your bound computation when strengthening a cut includes the global set of cuts? I see it in Algorithm 1, but I didn't see it in the text.\n\n10. Could you include exactly how the trees differ from each other in the multi-tree approach? The text mentions that they explore a different set of branching decisions, but not how.\n\n11. Could you expand on which methods/baselines use GPUs, and how they are used? This is important for a proper comparison.\n\n12. Typos: Remove \"BIC\" in line 139, capitalize \"we\" in line 208, \"instances\" and double period in caption of Table 4.", "limitations": "The Limitations section is reasonable, covering cases where this approach does not work well.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper provides a solid contribution to the area of neural network verification methods. It builds on top of cut-based branch-and-bound verification solvers by presenting a method to quickly infer cuts, which appear to be novel and computationally useful. In particular, they nicely leverage the fact that there are fast methods to produce bounds in NN verification, allowing us to quickly recheck cut validity. This makes for a clean and simple method, which has the advantage of not being too complicated to integrate with an existing cut-based BaB verification solver.\n\nBoth the set of benchmarks and baselines are reasonably extensive, and we can observe improvements in verifiability that are sufficient for a meaningful computational contribution, especially in the CIFAR instances in both VNN-COMP and SDP-FO, without much additional cost in computational time.  The paper is overall clearly written and the figures and algorithms are helpful.", "weaknesses": "In some of the benchmarks, the computational results may be somewhat incremental, but overall they are positive. There is potential room for improvement in parts of the methods (see Questions section below); in particular, it is not clear if the authors have explored variations of their constraint strengthening approach. In general, I do not see major weaknesses in this paper, though minor concerns are expanded on below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you very much for your constructive feedback and for correctly recognizing our key contributions. We appreciate your support and very helpful feedback. We provided additional experiments as requested and clarified the key questions below:\n\n* Q1: Do You Consider Other Drop Heuristics?\n\n    We acknowledge that while our current approach, based on improvements to the lower bound in the tree, is efficient given the available data, it does introduce dependency biases due to the constrained nature of previous assignments. There might exist better heuristics that can be explored in future work, but our work is the first of this kind and we want to start with a simple and effective heuristic. \n\n    We have considered and tested a random drop heuristic and KFSB score heuristic as alternatives. Our benchmark results across SDP and oval22 indicated no significant improvement in performance compared to beta-CROWN, please refer to the following table. These results suggest two heuristics do not provide a robust alternative in this context.\n\n    | Dataset | Beta CROWN | Random Drop | KFSB Score | Influence Score |\n    |------------------|------------|-------------|------------|-----------------|\n    | cifar_cnn_a_adv | 44.50% | 44.50% | 44.50% | 47% |\n    | cifar_cnn_a_mix | 41.50% | 41.50% | 41.50% | 45.5% |\n    | cifar_cnn_b_adv | 46.50% | 46.50% | 46.50% | 49% |\n\n* Q2: Exploring Binary Search Approaches for Cut Strengthening\n\n    It’s correct that our current method employs a fixed drop percentage. We did not investigate a binary-search-based approach, as this would increase the number of verification queries. Instead, we recursively tighten (line 205) the cut further should the first query succeed. If it fails, re-introducing constraints would reduce the benefit of BICCOS, while increasing the associated overhead. However, we do acknowledge that this could be tuned further in future research. We did explore dropping only 30% of the constraints at a time, with no immediate benefit. This demonstrates that we are not sensitive to this hyperparameter.\n\n* Q3: Optimizing Cut Addition in Algorithm 1 by Selecting Only the Best Cut\n\n    We agree the strengthened cuts make the previous cuts obsolete. We will replace lines 12 and 13 of the algorithm with\n    \n    ```\n    recursively_strengthened_cuts = constraint_strengthening(f, C_{new}, C_{cut}, drop_percentage)\n    if strengthening_was_successfull:\n        C_{cut} <- C_{cut} \\cup recursively_strengthened_cuts\n    else:\n        C_{cut} <- C_{cut} \\cup strengthened_cuts\n    ```\n    \n    Intuitively, if the next rounds of constraint strengthening produce a better cut, we use these better cuts rather than the currently inferred cuts.\n\n* Q4: Integrating CDCL Learned Clauses as Cuts for Enhanced Cut Generation\n\n    We agree that CDCL can be used to generate cuts even though this will be a challenging engineering task. This is an interesting future work and we will rephrase our paper accordingly. Our current approach focuses on generating cuts and then strengthening them, which has proven to be both easy to implement and effective. While CDCL could enhance the initial cut generation, it does not inherently provide a mechanism to strengthen these cuts using the solver, a novel step in our paper that is crucial for performance.\n\n* Q5: Data Analysis on Cut Generation Efficiency and Feasibility in Neural Network Verification\n    \n    We evaluated the UNSAT nodes and calculated the percentage that resulted in the generation of cuts. The table below provides a detailed breakdown:\n\n    | Dataset           | Avg. # Cuts Generated | Avg. UNSAT Nodes | Fraction of Cuts/UNSAT Nodes |\n    |-------------------|---------------------|------------------|------------------------------|\n    | cifar_cnn_a_adv   | 345.78              | 763.70           | 0.4528                       |\n    | cifar_cnn_a_adv4  | 86.33               | 2165.11          | 0.0399                       |\n    | cifar_cnn_a_mix   | 121.56              | 1766.77          | 0.0688                       |\n    | cifar_cnn_a_mix4  | 25.93               | 807.19           | 0.0321                       |\n    | cifar_cnn_b_adv   | 105.79              | 808.00           | 0.1309                       |\n    | cifar_cnn_b_adv4  | 106.14              | 1800.21          | 0.0590                       |\n    | mnist_cnn_a_adv   | 11.24               | 1351.67          | 0.0083                       |\n\n    Regarding the number of dropped assignments, this is related to the number of rounds of BaB (Branch and Bound) using our heuristic. Our setting has a drop ratio of 0.5 if the Lagrange factor of the neuron is 0, so the average number of dropped assignments will be less than 50%. This number decreases as BaB goes deeper and the domain becomes more refined. \n\n    Given this data, we agree with your suggestion that a cut selection procedure could be beneficial. We are implementing the new selection algorithm mentioned in **Q3** above and will report back.\n\n* Minor Issues\n\n    - Global set of cuts in strengthening: Thank you for noting this omission. We'll add explicit mention in the text that our bound computation during cut strengthening includes the global set of cuts, aligning with Algorithm 1.\n    - Introducing cut redundancy earlier: We agree this would improve readability. We'll revise Section 3.1 to briefly mention that the initial cuts are redundant until strengthened, providing context for Section 3.2.\n    - Multi-tree approach differences: We'll expand on how the trees differ in the multi-tree approach. Specifically, we'll clarify that in the first round, we select different neurons to start each tree, leading to diverse branching decisions. This will lead to different exploration paths.\n    - GPU usage in methods/baselines:\n        - CPU: nnenum, Marabou, Venus2.\n        - GPU: ERAN, OVAL, VeriNet, MN-BaB, PRIMA.\n    - Typos: we will fix typos and adjust the format according to the reviewer's feedback.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "YzHeejMAcb", "reviewer": "Reviewer_vA2E", "summary": "The paper extends GCP-CROWN, an existing toolkit for the verification of neural networks which is based on GPU-accelerated bound propagation combined with a branch-and-bound (BaB) approach. The strength of the existing algorithm is its ability to incorporate cutting planes into the bound propagation process. GCP-CROWN uses cutting planes generated by a Mixed Integer Linear Programming (MILP) solver which is run in parallel to the bound propagation, however, MILP solvers generally do not scale to large problems and only generate generic, problem-independent cutting planes.\nThe authors propose a new approach to generate cutting planes called BICCOS which works by exploiting information from verified branches in the BaB tree. Once a branch is verified, the idea is to remove a number of constraints from the branch in an attempt to obtain a subset of constraints that is sufficient for obtaining a \"verified\" result. If successful, a cut which is valid for all other branches in the BaB tree can be generated based on these constraints. The generation of cuts is run during the normal verification process, but the authors propose adding a presolve step that initially generates multiple shallow BaB trees in an attempt to create a pool of cuts before starting the standard BaB phase from GCP-CROWN.\nThe experimental evaluation shows that BICCOS scales well, is able to generate cuts for problems that the MILP solver employed in GCP-CROWN can't scale to, and outperforms many competing tools.", "questions": "- Table 3: Why does BICCOS with multi-tree perform worse than BICCOS (base) for CNN-A-Adv-4, do the authors have an explanation for this?\n- Why is BICCOS run with a shorter timeout compared to other algorithms? Also why is MN-BaB run with a 600s timeout and then $\\beta$-CROWN, GCP-CROWN and BICCOS are run with a 200s timeout in Table 2, but then in Table 3 the footnote seems to suggest that BICCOS is run with a 200s timeout while $\\beta$-CROWN and GCP-CROWN use a longer timeout? This seems inconsistent. The experiments would be more informative if all algorithms were run with the same time budget as is usual practice e.g. in VNNComp.\n- In Table 1/2 does BICCOS use cuts from a MILP solver (if the solver scales to the problem) or only the newly introduced cuts?\n- Table 3: For CNN-A-Mix-4 the BICCOS-MIP approach has a verified accuracy of 56.5% but BICCOS-all has 56%. What is the authors' intuition here regarding why adding the multi-tree approach worsens performance, do they think this is an issue/can be avoided?\n- Line 302-310: Could the authors clarify what each variant of the algorithm includes here? The text makes it sound a bit like the authors start from BICCOS (base) and then gradually add other components, but does BICCOS (with multi-tree) also include MIP cuts? If so, the performance drop from 52 to 51.5% on e.g. CIFAR CNN-B-Adv would be surprising, any explanations?", "limitations": "Limitations are sufficiently addressed.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Neural Network Verification is a relevant research topic\n- A cut generation method that scales to larger networks as well as cuts that are problem-specific and less generic than those generated by a MILP solver are useful contributions.\n- The method outperforms most other toolkits in the experimental evaluation", "weaknesses": "- The work is somewhat incremental compared to GCP-CROWN\n- When comparing the performance of GCP-CROWN and BICCOS (base) in Table 3, this seems to indicate that the newly introduced cuts are weaker than the MILP cuts. Including presolve (BICCOS(with multi-tree)) improves performance compared to GCP-CROWN in only some instances. It's good to have a cut generation method which scales to larger networks, but the method would be a lot stronger if the BICCOS cuts alone outperformed the generic MILP cuts.\n- A comparison with existing cuts, such as the ones from [1], is missing. In the related work section the authors only state that Venus (which implements the cuts from [1]) delivers weaker empirical results than their approach. However, the contribution of this paper are the new cuts and comparing the BICCOS cuts in a GPU-enabled bound propagation framework to the cuts by Botoeva et al. implemented in a MILP-based verifier (which can't make use of GPU acceleration) is not fair since it is well-known in the literature that bound propagation frameworks outperform MILP verifiers. To assess whether the BICCOS cuts are more effective than the cuts in [1] they should be implemented in the same general framework. Without this comparison it is hard to judge the contribution of this work.\n- Appendix A2: This part of the appendix is either very unclear or has a lot of typos. There are a lot of expressions like $\\sum_{i \\in \\mathcal{Z}^+} z_i + \\sum_{j \\in \\mathcal{Z}^-} (1 - z_i)$. Do the authors mean to write $\\sum_{i \\in \\mathcal{Z}^+} \\left ( z_i + \\sum_{j \\in \\mathcal{Z}^-} (1 - z_i) \\right )$? If so, the extra set of brackets should be added. If the authors actually do mean to write $\\sum_{i \\in \\mathcal{Z}^+} \\left ( z_i \\right ) + \\sum_{j \\in \\mathcal{Z}^-} (1 - z_i)$ then the $z_i$ in the second sum makes no sense, should this be $z_j$ then? This unclarity/mistake appears in the two equations between line 516 and 517 (which aren't labeled so I can't refer to them), in line 518, in the first equation between line 518 and line 519 and the second equation between line 518 and 519 (these also aren't labeled so I can't refer to them directly).\n\n### Minor points\n- Line 10-11: cutting planes constraints --> cutting **plane** constraints\n- Line 60: proposed --> **propose**\n- Line 67: discussed --> **discuss**\n- Line 98: The paper states \"If $f^* > 0$, it is unclear whether the property might hold\" --> Shouldn't this be \"If $f^* < 0$\" (i.e. the inequality being flipped?)\n- Line 98: proerty --> pro**p**erty\n- Line 109: Remove \"the\" (sentence should be \"most existing NN verifiers use cheaper methods such as (...)\")\n- Line 139: Remove **BIC** at the beginning of the line\n- Line 143: they --> **the authors**\n- Figure 2a): these subproblems already includes the constraint --> these subproblems already **include** the constraint\n- Line 194: along --> **alone**\n- Line 198-199: using as fewer variables as possible --> using as **few** variables as possible\n- Line 202: we performs a re-verification step, where it recomputes the lower bound --> we **perform** a re-verification step **which** recomputes the lower bound\n- Line 208: we propose --> **W**e propose\n- Table 3: For MNIST, CNN-A-Adv the \"Ver%\" for BICCOS (with MIP cuts) is $0.71$. Is this a typo, what is the correct number?\n- Appendix A.2: The authors derive two equations by \"taking a negation of this equation\". I find this part a bit unclear, do they mean that if the equation holds then this is equivalent to one of the two new equations holding? Or do both of the two new equations need to hold?\n- Line 547-549 in Appendix A4: The authors write \"on the CIFAR CNN-B-Adv model, BICCOS with multi-tree search explores $2.54 \\times 10^3$ branches, significantly lower than the $1.57 \\times 10^3$ branches explored by the base BICCOS version.\" However, as far as my understanding goes, $2.54 \\times 10^3$ is not a **smaller** but a **larger** number than $1.57 \\times 10^3$ so the sentence here makes no sense. I tried to double-check this but the same numbers are reported in the table below (I assume that \"BICCOS with multi-tree search\" in the text is the same as \"BICCOS (with Presolve)\" in the table). Could the authors clarify what their point is here?\n\n### References\n[1] Botoeva, E., Kouvaros, P., Kronqvist, J., Lomuscio, A. & Misener, R. (2020) Efficient Verification of ReLU-Based Neural Networks via Dependency Analysis. In: Proceedings of the AAAI Conference on Artificial Intelligence. 3 April 2020 pp. 3291–3299. doi:10.1609/aaai.v34i04.5729.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive comments and valuable questions. We hope the reviewer can reevaluate our paper based on our response below:\n\n* For Weakness.\n\n    - W1. The work is somewhat incremental compared to GCP-CROWN\n\n        GCP-CROWN and our work make orthogonal contributions. GCP-CROWN does not provide an efficient way to find cuts as we do.  GCP-CROWN primarily focuses on solving cuts provided to it without engaging in the cut-finding process. We just use GCP-CROWN as a solver to do bound propagation with constraints. On the other hand, our work introduces an efficient algorithm specifically designed to find these cuts. This distinction highlights a significant contribution of our method: the ability to identify and generate cuts, not just solve them. By developing an algorithm that efficiently finds cuts, we add a valuable tool to the existing framework, enhancing the overall effectiveness of neural network verification.\n\n    - W2. Performance Comparison of MILP cuts and BICCOS.\n\n        We agree that MILP solver cuts are inherently powerful due to the solver's comprehensive approach from a lot of previous works [1] during the past decades. However, a critical limitation of MILP solver cuts is their scalability. As the network size increases, i.e., above 4M parameters, the complexity and computational resources required for MILP solvers to generate cuts even initialize the model become prohibitively high. In our experiment, we found MILP could not scale to large networks like cifar100 (5.4-31.6 M) and tiny-imagenet (14.4 M).  This limits their practical applicability to larger neural networks.Our BICCOS method, while producing slightly weaker cuts compared to MILP, offers significant advantages in terms of scalability.\n\n        [1] Wolsey, L. A., & Nemhauser, G. L. (2014). Integer and combinatorial optimization. John Wiley & Sons.\n\n    - W3. Comparison with Venus2\n\n        **Fig. 1 in the PDF file** shows a comparison with Venus2. We emphasize on making a fair comparison on the strengths of cuts. Since Venus2 uses an MILP solver to process its cuts, in these experiments we do not use the efficient GCP-CROWN solver. Instead, we also use an MILP solver to handle the BICCOS cuts we found. This ensures that the speedup we achieve is not coming from the GPU-accelerated GCP-CROWN solver. Since our cut generation relies on the process with BaB, we first run BICCOS to get the cuts, and then import the cuts into the MILP solver.\n        \n        We note that Venus uses branching over ReLU activations to create multiple strengthened MILP problems. On the other hand, we only create one single MILP and do not perform additional branching. Therefore, our MILP formulation is weaker. The fact that we can outperform Venus2 anyway underlines the strength of the generated cuts by BICCOS.\n\n    - W4. Appendix A2 function typo.\n\n        A We apologize for the confusion caused by the typo. We intended to write         $$ \\sum_{i \\in \\mathcal{Z}^{+}} z_i + \\sum_{i \\in \\mathcal{Z}^{-}} (1 - z_i) \\leq |\\mathcal{Z}^+| + |\\mathcal{Z}^-| - 1 $$\n        \n* For minor issues\n\n    - Typos. Thank you for the detailed review, we will fix the typos. The correct number is 71, not 0.71.\n   \n    - Explanation in Appendix A.2. When we refer to \"taking a negation of this equation,\" we mean that if the original equation holds, it leads us to the two new conditions. However, given the context and the bounds on $z$, only the first equation needs to hold.\n   \n    - Explanation in Appendix A4. The sentence was meant to highlight the efficiency of the multi-tree search despite exploring a larger number of branches because **the multi-tree search domains are also counted in the total number of branches**. The multi-tree search method inherently examines multiple trees, thereby increasing the number of branches explored. These domains represent different subproblems that are explored simultaneously. Although this increases the branch count, the exploration within each domain is optimized, leading to faster convergence and overall reduced computation time. We will correct the text to reflect this explanation accurately. Thank you for your careful review and for helping us improve the clarity of our paper.\n\n* For questions\n\n    - Q1. Why does BICCOS with multi-tree perform worse than BICCOS (base) for CNN-A-Adv-4?\n\n        For the CNN-A-Adv-4 dataset, BICCOS with multi-tree search performs worse than BICCOS (base) primarily due to the additional time cost associated with the multi-tree search approach. This dataset contains 200 instances, and each instance has 10 predicted classifications, requiring us to validate 9 properties so in the worst case we have to perform a multi-tree search for each property.\n\n    - Q2. Timeout difference in comparisons\n   \n        We apologize for the confusion. The MN-BaB results were copied from the VNN-COMP 2022 report. We did not reproduce those ourselves, though we use the same hardware for our experiments as they did. In table 3, BICCOS, beta-CROWN and GCP-CROWN all have a timeout of 200s. We will update the table caption accordingly. The increased timeout for MN-BaB may increase the percentage of verified instances. However, we can still outperform it.\n\n    - Q3. Question in Table 1 \\& 2.\n\n        In Table 1/2,BICCOS uses cuts from BICCOS base + multi-tree search + MIP cuts from CPLEX\n\n    - Q4. Question in Table 3.\n\n        In table 3, the performance degradation by multi-tree search is caused by the associated computational overhead.\n\n    - Q5. Clarification what each variant of the BICCOS uses\n\n        - Biccos base: only contains the cut inference during regular bab, \n        - BICCOS (with multi-tree): includes BICCOS base but not MIP cuts, \n        - BICCOS (all): includes base multi-tree and MIP cuts.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "TQFItkaJx5", "reviewer": "Reviewer_1a6g", "summary": "The paper presents BICCOS: a method to derive cutting planes for use within a state-of-the-art neural network verification framework based on branch and bound (BaB). Given verified (UNSAT) subproblems, BICCOS tries to find a subset of the employed branching choices that led to the verification result, and applies a cutting plane that prunes this subtree from the rest of the BaB procedure. Engineering improvements (going over multiple BaB tree and branching choices in parallel as a pre-processing step) are also presented. The experimental results suggest moderate improvements upon the state-of-the-art over the considered benchmarks.", "questions": "1) It is repeatedly claimed that the procedure is specific to NN verification, but I think such an approach would apply more generally to any BaB procedure (finding subsets of branching decisions that led to a positive verification result and using that as cutting plane), or at least on any BaB procedure for MILPs. Could you please elaborate on this?\n2) As commonly done in previous work (for instance, Beta-CROWN), plots showing the number of verified properties within a given runtime are needed to fully assess the trade-offs associated to the proposed approach. For instance, how much does it slow verification down on easier properties?\n3) It seems to me that Table 2 reports the best configuration across those in Table 3, for each BICCOS row. Could the authors clarify this?", "limitations": "Limitations are appropriately addressed in the conclusions.", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The idea behind BICCOS is fairly simple, yet relatively novel in the context of neural network verification. Given the additional overhead linked to the \"strengthening\" procedure (recomputing bounds after removing branching decisions), which is required for the overall algorithm, one may think that the overall approach may not pay off. The experiments show that it does, although somewhat marginally, I would believe.", "weaknesses": "**Presentation.**\nThe paper feels quite rushed, and the quality of the presentation definitely needs to improve to meet the NeurIPS bar. \nThe figures are fairly small (especially Figure 2) and fairly hard to read on paper. I would suggest that the authors remove the shadows too, which make things harder. The Tables are also fairly hard to read on paper. The text still has some typos (e.g., \"BICwhere\" in line 139). The example from Figure 1 does not correspond to the text in lines 160-166 (x_3 >= 0 vs x <= 0) or to Figure 2a. In lines 308-310 the text suggests that the comprehensive BICCOS configuration performs the best in all cases: this is not what appears from Table 3.\n\n**Feasibility.**\nThis is linked to the presentation but it's important enough to stand as a separate point. Page 4 repeatedly speaks of infeasibility in a context where I think it's technically incorrect. I think that the fact that a subproblem lower bound is positive does not imply infeasibility: it could very well be that both its lower and upper bounds are positive (with UB > LB), simply suggesting that the minimum for that subproblem (but of course not necessarily for the original problem) is positive. This means that the counter-example search is infeasible, but not the variable assignment (the series of branching decisions). In order to prove infeasibility of the subproblem, one would need to either show that the local UB is smaller than the subproblem LB, or show that the subproblem LB would go to infinity in the limit for iterations (that is, the underlying dual problem is unbounded). All the arguments being made still apply even for feasible yet verified subproblems: the goal is simply to exclude BaB subregions which we know already will lead to positive lower bounds (hence pruning the tree). But this terminology should be adapted to avoid any confusions.\n\n**Results.**\nWhile the fact that the proposed approach works is interesting (see *strengths* above), I do not think the presented experimental results are particularly impressive. Most of the improvements over GCP-CROWN (or Beta-CROWN, when GCP-CROWN can't be applied because of scalability issues) are fairly small. Furthermore, more granularity in the results would be needed (see questions). While this should not be a problem for acceptance on its own, I think it is when combined with the presentation issues above.\n\n--------\n\n**Post-discussion.** I am increasing my score to 6 following the discussion with the authors. I encourage them to acknowledge the shortcomings of the proposed approach in the next version, and to improve the presentation as discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive comments and valuable questions. We want to clarify a few key misunderstandings about feasibility and results. We hope the reviewer can reevaluate our paper based on our response below:\n\n- For Weakness\n\n    * Presentation.\n\n        For presentation, we will fix typos and adjust format according to the reviewer's feedback and  revise the text to accurately reflect the results shown in Table 3, clarifying that the comprehensive BICCOS configuration does not perform best in all cases.\n\n    * Explanation of feasibility.\n\n        We realize the potential for confusion. Our formulation is in line with your last statement: We are only interested in the regions that may potentially contain adversarial examples, i.e. there exist inputs $x$ such that $f(x) <= 0$. Therefore, if the lower bound does become positive, the existence of adversarial examples in this subdomain can be excluded (infeasible).\n        Generally, in neural network verification, the safety property (non-existance of adversarial examples) is negated and posed as a satisfyability problem. Tools then report SAT if adversarial examples exist and UNSAT if the safety property holds. This implies that the input $x$ is restricted not only to the given input area, but also to those $x$ where $f(x) <= 0$. If no adversarial example exist, no $x$ with $f(x) <= 0$ exists, so the assignment becomes infeasible. Often, this constraint is only used indirectly: First, a lower bound of $f(x)$ is computed. Then, if it is positive, this implies that the underlying assignment is in fact infeasible, as the constraint $f(x) <= 0$ would always be violated. There is also work [1,2] on directly incorporating this constraint into the optimization process.\n        While the implicit conversion from “lower bound > 0” to “infeasible” is common in the neural network verification community, we recognize the need to make this step explicit. We will rewrite the respective sentences accordingly to avoid confusion, but we want to emphasize that the our existing theoretical results are sound and not affected by these changes.\n\n        [1] Kotha, S., Brix, C., Kolter, J. Z., Dvijotham, K., & Zhang, H. (2023). Provably bounding neural network preimages. Neurips 2023.\n\n        [2] Pengfei Yang, Renjue Li, Jianlin Li, Cheng-Chao Huang, Jingyi Wang, Jun Sun, Bai Xue, and Lijun Zhang. Improving neural network verification through spurious region guided refinement. Tools and Algorithms for the Construction and Analysis of Systems, 2021b.\n\n- Q1. Can BICCOS be applied to any BaB procedure?\n    \n    BICCOS is specialized to the branch-and-bound procedure of most SOTA neural network verification tools. While neural network verification constitutes a sub-problem of the more general MILP problem set, the respective tools have been tuned to its specific kind of problems.\n\n    Specifically, the ReLU activation functions in neural networks are difficult for regular MILP solvers to handle, as they require extensive branching to cover all possible combinations of assignments. Neural network verification tools have developed specialized techniques to deal with those non-linear activation functions by overapproximating them and - crucially - improving this overapproximation iteratively using GPU-acceleration.\n\n    However, by tuning the neural network verification tools toward this specific subset of tasks, they have become non-ideal (or impossible) to apply to regular general verification problems. Therefore, BICCOS cannot be directly applied to generic MIP problems not relavent to non-neural network verification.\n\n- Q2. How much does BICCOS slow down the verification on easier properties?\n\n    Thank you for pointing out the need for plots to demonstrate the trade-offs of our approach, in response to your query, **Fig.2 in the pdf** file illustrates the number of verified properties within various runtime thresholds. This visualization helps to clarify the performance trade-offs associated with our approach. As indicated in the figure, the slowdown experienced with our method is relatively minor for simpler properties, which are often verified before the implementation of cuts. For more complex instances, however, the benefits of our approach become more evident, with a notable improvement in time efficiency for verification. This trend suggests that while our method introduces a slight delay in simpler cases, it significantly enhances performance on more challenging properties, providing a net gain in efficiency across a diverse set of scenarios. We believe that this balanced approach is beneficial for practical applications where varying levels of difficulty are encountered.\n       \n- Q3 Does Table 2 report the best configuration?\n\n    Thank you for your observation. Table 2 indeed reports the best configuration for each BICCOS row as identified among those listed in Table 3. This approach ensures that the reported settings are optimal for each benchmark. For instance, large models perform best with MTS, while small models benefit from MIP cuts, etc., on each dataset. This methodology is consistent with common practices in the field. E.g. in the VNN-COMP, teams often fine-tune their tools for each benchmark set. Crucially, we note that we did not explore a large set of hyperparameters, and using all BICCOS features (MILP cuts, constraint strengthening, multi-tree search) is best for all but 2 benchmarks, where it is outperformed by the tuned version (multi-tree search disabled to avoid its overhead) by only 0.5 percentage points.\n\nWe thank you again for the valuable comemnts and we hope our weaknesses (especially on infeasibility) has been addressed. We hope you can reevaluate our paper based on our response. Thank you.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "nvFHX1rT70", "reviewer": "Reviewer_iWFh", "summary": "Following the discussion with the authors, I am increasing my score to weak accept.\n----\n\nThis paper presents a new branch-and-bound-based verification algorithm for neural networks with ReLU activation. The main idea is to produce additional constraints to the verification problem by identifying small combinations of neuronal states which would not lead to an adversarial input, so that these combinations are not explored again in another part of the branch-and-bound tree. Because smaller sets are always better, the authors develop an algorithm for reducing the number of neurons involved in such combinations. They also leverage multiple branch-and-bound trees explored in breadth-first search as a means of producing constraints involving fewer neurons.", "questions": "1) In light of the comments about nogood learning and restarts, can the authors please reframe their contribution in the paper in terms of the existing related work?\n\n2) Can you please qualify your discussion about MIP solvers by being more precise in what they can and cannot do?\n\n3) Are you branching on the output of the neurons (x) , or on the state of the neurons (z)?\n\n4) Can you simplify Proposition 3.1?\n\n5) Can you please describe what thresholds were used for Algorithm 1, and how they were obtained?\n\n6) Can you please rectify the discussion about cutting planes for neural networks by acknowledging prior work on this?\n\n7) Can you please comment on incorporating the major and minor corrections to writing?\n\n8) In lines 145-146, what do you mean by \"[49] solved these cuts using GPU-accelerated bound propagation\"? What is the concept of solving a cut? Do you mean generating the cut? Do you mean solving the LP relaxation after the cuts are included?", "limitations": "The authors were very upfront about limitations to their work.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The ideas presented by the authors are intuitively reasonable and unsurprisingly effective as a consequence. In fact, they have been studied in other contexts with other names. Most notably, the idea of producing a constraint based on a path of the branch-and-bound tree is commonly known as nogood learning (see [1] for an early use in constraint programming, such as with the concept of a conflict set in page 9; and [2] for the first application to mixed-integer programming). The canonical application has been to identify infeasible nodes, but it is not a big stretch to apply the same idea for when the objective function is likely suboptimal (positive objective function when what we need is a negative value). Moreover, the idea of exploring multiple branch-and-bound trees in parallel is not far from solver restarts [3], which have been widely used in constraint programming and subsequently adopted in mixed-integer programming as well.\n\nAll in all, this is a paper that speaks for itself because the right ideas were used and better numbers were obtained. Issues come next.\n\n[1] https://ftp.cs.ucla.edu/pub/stat_ser/r77-II-reprint.pdf\n\n[2] https://www.cs.cmu.edu/~sandholm/nogoodsForMip.techReport06.pdf\n\n[3] http://www.cs.cornell.edu/selman/papers/pdf/98.aaai.boost.pdf", "weaknesses": "One problematic omission in this paper is that nowhere it is said that MIP solvers also use branch-and-bound. Otherwise, it sounds as if MIP solvers are some sort of black box magic that tries to solve problems in some inefficient way. There is also some broad generalizations such as \"MIP solver may not return any cuts before timeout\" (149): Which solver? When? Under which conditions? All that a generic MIP solver needs to generate a Gomory cut is the solution of the LP relaxation and the corresponding tableau. \n\nThe fact that branches are defined in terms of neuron outputs is also problematic because there is an overlap between the two resulting subproblems when x=0. The effectiveness of branch-and-bound comes from partitioning the feasible set, and moreover from slicing off the parts of the LP relaxation that are not feasible according to the MIP formulation (such as when z=0 is one subproblem, z=1 is another subproblem, and 0<z<1 gets thrown away). Because your implementation is extending someone else's work, I believe that this might be a mismatch between the code and what the paper describes. Since the z variables are nevertheless a way to parameterize the LP problems to be solved along the way, there would be no problem in defining the constraints directly in terms of z instead of x. In fact, this is exactly what you do when you finally formalize the cut that you are using.\n\nWhen it gets to Proposition 3.1, the statement is unnecessarily complex: why define a diagonal matrix only to multiply it by a vector of ones immediately after? In terms of notation, it doesn't make sense to have output variables indexing which neurons should be removed. Instead, you could use only the corresponding indices. Hence, Z = {1, 3} instead of Z = {x_1, x_3}. Moreover, this is a commonly known cutting plane in MIP, perhaps first introduced in 1972 by [4] and at this point widely known and applied in the MIP community. It would have been better to use the conventional notation $\\sum_{i \\in Z^+} z_i - \\sum_{i \\in Z^-} z_i \\leq |Z^+| - 1$ directly in the paper rather than using it in the appendix and keeping a less readable version in the paper.\n\n[4] https://epubs.siam.org/doi/10.1137/0123007\n\nAlgorithm 1 relies on a threshold, but values or experiments to find the right one are not mentioned anywhere.\n\nThe paper also talks very briefly about prior work, to the point that it sounds as if specialized cutting planes for MIP problems involving neural networks were never proposed before. However, your reference 1 (Anderson et al.) does exactly that. The same is true about [5-6], and a broader perspective about this area can be found in Section 4 of the survey [7].\n\n[5] https://arxiv.org/abs/1810.03370\n\n[6] https://arxiv.org/abs/2102.04373\n\n[7] https://arxiv.org/abs/2305.00241\n\nOther major comments about the writing follow below.\n\nA) The \"The NN Verification Problem\" paragraph in Section 2 is not very precise because it confuses values with variables and do not properly qualify functions when values are dependent on inputs. What follows is a possible correction to that. In line 84, replace \"scalar values\" with \"scalar variables\". In line 85, add \"the values of\" after \"for\". In line 86, replace \", when they depend on a specific x\" with \"for a given input x\". In line 87, add to \"that limit [the post-activation values of] individual neurons\".\n\nB) The text talks about an example in which you no longer want to see both neurons 1 and 3 inactive at the same time, but the example in Figure 1 shows neuron 3 active.\n\nOther minor comments about writing follow below.\n\n10-11: \"cutting planes constraints\": this is not an adequate expression (all constraints define a plane); use either cutting planes, valid inequalities, constraints, or cuts. \n\n21-22: First sentence is a strong statement with no reference provided and never discussed again.\n\n32: \"statuses\"   ->   states (again in 53)\n\n67: \"discussed\"   ->   discuss (not past tense)\n\n98: \"> 0\"   ->   < 0?\n\n98: \"pro[p]erty\"\n\n125: \"status\"   ->   state\n\n139: remove \"BIC\"\n\n149: \"and [the] MIP solver\"\n\n162: \"positive regime\": active regime?\n\n163: \"in [the] LP formulation\"\n\nAuthors repeated twice in reference 11.\n\nReferences 13 and 14 are the same.\n\nUse {CDCL} instead of CDCL in reference 28 and {SAT} instead of SAT in reference 30 to keep the casing in the output, since otherwise what you get is cdcl and sat.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive comments and valuable questions. We hope the reviewer can reevaluate our paper based on our response below:\n\n- Q1: Reframe the contribution in the paper in terms of the existing related work about nogood learning and restarts.\n\n   Thank you for your valuable input, which allows us to view our research from a broader perspective. Other NN verification papers, such as beta-CROWN, have utilized branch-and-bound techniques specifically tailored to NN verification. While branch-and-bound is a general technique, its adaptation to the unique challenges and requirements of NN verification is what distinguishes our work. We will make sure to cite these works appropriately and discuss their relevance to our context.\n\n- Q2: Discussion about MIP solvers more precisely.\n\n    Thank you for your comments highlighting the need for a more detailed discussion regarding MIP solvers. We will clarify in our revision that MIP solvers, including CPLEX which we primarily used, employ branch-and-bound algorithms as a fundamental part of their operation. We found that in many of these large-scale benchmarks, the MIP solver fails to solve the initial (root) LP relaxation for the verification problem within the timeout threshold, so branch-and-bound has never started, and also no effective cuts can be generated. For instance, in the cifar100 benchmark with networks size between 5.4-31.6 M and tiny-imagnet with a network size of 14.4 M, CPLEX was unable to generate any cuts within 200 seconds (timeout threshold for this benchmark). These examples will illustrate the limitations more concretely and contextualize the generic statements we previously made, which we will add this discussion to our revised paper.\n\n- Q3: Clarification of  branching on the output of $x$ or $z$.\n\n    By definition (line 100) of $z$, $z=0$ is equivalent to $x \\leq 0$, and $z=1$ is equivalent to $x \\geq 0$. This is encoded in Appendix A1, Equation 12 and 13: By inserting z=0 (z=1), x is restricted to the respective non-negative (non-positive) domain. Therefore, branching over $x \\leq 0$ vs $x \\geq 0$ is equivalent to branching over $z=0$ vs $z=1$. Note that technically we cannot use strict inequality like $x > 0$ or $x < 0$, so the $x=0$ case is needed in both branches. The equvalence of the two formulations has been used in prior work such as GCP-CROWN.\n\n- Q4: simplify Proposition 3.1\n\n   We will remove the diagonal matrix and simplify the notation. Additionally, we acknowledge that this cutting plane is a commonly known concept in MIP, first introduced in 1972 by [4]. Here is the revised cut expression:\n\n   $$\\sum_{i \\in \\mathcal{Z}^{+}} z_i - \\sum_{i \\in \\mathcal{Z}^{-}} z_i \\leq |\\mathcal{Z}^{+}| - 1$$\n\n- Q5: Thresholds used for Algorithm 1 and how do we obtain it\n\n    The specific threshold value and its justification were detailed in Section A.3.1. The threshold, `drop_percentage`=50% was determined based on preliminary experiments during code development and empirical observations. We conducted multiple trials to assess the impact of different threshold values on the performance and effectiveness of the algorithm. Through these experiments, we observed that a 50% threshold provided a balanced trade-off between pruning weak constraints and maintaining a robust constraint set. We will ensure it is included in future revisions for clarity.\n\n- Q6: Discussion about cutting planes for neural networks by acknowledging prior work on references\n\n   We acknowledge that our discussion on prior work was brief, and we appreciate the opportunity to rectify this by acknowledging significant contributions in this area.\n\n   1. We will cite and acknowledge Prior Works:\n\n      - Anderson et al. propose cutting planes specifically designed for neural networks by leveraging convex-hull constraints.\n      - [5] explores empirical bounds on the linear regions of deep rectifier networks, contributing to the understanding of the behavior and optimization of neural networks.\n      - [6] discusses partition-based formulations for optimizing ReLU neural networks, providing a framework for mixed-integer optimization in this context.\n      - [7] Section 4.2.4 offers a comprehensive overview of cutting planes and related techniques applied to neural networks, situating our work within a broader context.\n    \n    2. Our work differs from Anderson et al. [1] in several key aspects:\n\n        - **Cutting Plane Design:** While Anderson et al. focus on selecting the most violated constraints among an exponential number of convex-hull constraints in **one layer**, our constraint can involve neurons from **any layer**, and our constraint can be easily found in infeasible subproblems during BaB.\n        - **Computational Expense:** Anderson et al. propose a linear-time method for constraint selection, which can still be computationally intensive for large-scale problems. In their experiments, they use neural networks within 2000 ReLUs, in contrast, we can scale to any network that beta-CROWN works, such as CIFAR100-ResNet-large, a network with 15.2M parameters and 286820 ReLU neurons.\n\n- Q7: Comment on Corrections to Writing\n\n    Thank you for your detailed feedback on the writing. We appreciate the opportunity to improve the clarity and precision of our paper. We will carefully review and revise the specified sections to incorporate these corrections.\n\n- Q8: What does \"solve these cuts\" mean?\n    \n    To clarify, we don’t mean to generate the cut,  the term \"solving cuts\" was intended to describe the process of incorporating generated cuts—as additional constraints—into the linear programming (LP) problem. This process involves re-solving the LP relaxation with these new constraints to tighten the bounds of the problem.\n\n    In our revision, we will replace the phrase \"solved these cuts\" with \"solving the LP relaxation with cuts included, which should more accurately reflect the process.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:
Submission of figures of added experimental results

Meta-review: The submission has received mixed ratings after extensive post-rebuttal discussions. One of the referees recommends rejection based on the weakness of the cuts that are generated by the proposed method, as well as incremental improvements over GCP-CROWN. However, the other referees recommend acceptance, and suggest acknowledging the aforementioned weaknesses in the revised version of the submission. The authors are advised to take into account the detailed reviews as well as the clarifications provided in the rebuttal when preparing the final manuscript.
Decision: Accept (poster)