Counterexample Guided Branching via Directional Relaxation Analysis in Complete Neural Network Verification

Jingyang Li, Fu Song, Guoqiang Li · 2026

Read Counterexample Guided Branching via Directional Relaxation Analysis in Complete Neural Network Verification by Jingyang Li, Fu Song, Guoqiang Li (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-14823.txt.

Introduction

Li, Song and Li sharpen neural network verification by branching on counterexample clues. Dataflow verifiers refine loose relaxations with branch-and-bound search. Static rules pick branch points blind, ignoring why a check failed. Their DRG-BaB frame recasts the search as a counterexample-guided loop. A failed case yields a closed-form fake counterexample from linear bounds. A directional relaxation gap score ranks neurons by their role in the failure. Targeted splits then replace blind search on high-dimensional tests, they report.

Catalog record

CREATORJingyang Li, Fu Song, Guoqiang Li
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51542
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.14823

Browse the full library · About the Tower of Babel

Full text

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

Counterexample Guided Branching via Directional Relaxation Analysis in Complete Neural Network Verification Jingyang Li, Fu Song, Guoqiang Li Abstract Deep Neural Networks demonstrate exceptional performance but remain vulnerable to adversarial perturbations, necessitating formal verification for safety-critical deployment. To address the computational complexity of this task, researchers often employ abstraction-refinement techniques that iteratively tighten an over-approximated model. While structural methods utilize Counterexample-Guided Abstraction Refinement, state-of-the-art dataflow verifiers typically rely on Branch-and-Bound to refine numerical convex relaxations. However, current dataflow approaches operate with blind refinement processes that rely on static heuristics and fail to leverage specific diagnostic information from verification failures. In this work, we argue that Branch-and-Bound should be reformulated as a Dataflow CEGAR loop where the spurious counterexample serves as a precise witness to local abstraction errors. We propose DRG-BaB, a framework that introduces the Directional Relaxation Gap heuristic to prioritize branching on neurons actively contributing to falsification in the abstract domain. By deriving a closed-form spurious counterexample directly from linear bounds, our method transforms generic search into targeted refinement. Experiments on high-dimensional benchmarks demonstrate that this approach significantly reduces search tree size and verification time compared to established baselines. 1 Introduction Deep Neural Networks (DNNs) have demonstrated unparalleled performance in perception and control tasks. However, their deployment in safety-critical systems (e.g., autonomous driving and avionics) remains cautious due to their vulnerability to adversarial perturbations [ 27 , 11 ] , where imperceptible input changes can lead to catastrophic failures. Consequently, Formal Verification , which provides mathematical guarantees of network properties, has emerged as a fundamental requirement for trustworthy AI [ 14 ] . The complete verification of ReLU networks is known to be NP-complete [ 15 ] . To address this complexity, the principle of abstraction-refinement [ 6 ] is generally adopted. By reasoning over an over-approximated (abstract) model of the network, verifiers can efficiently prove safety. However, due to information loss, the abstraction may fail to prove a valid property. To recover completeness, the verifier must iteratively refien the abstract model to eliminate precision erros. In the landscape of neural network verification, two distinct paradigms are observed: structural and dataflow abstraction-refinement. Sturctural abstraction-refinement is exemplified by methods that simplify the network topology (e.g., neuron clustering). Such paradigm often follows the classif Counterexample-Guided Abstraction Refinement (CEGAR) framework [ 5 ] that uses the spurious counterexample to refine specific parts of the abstract structure. As for dataflow abstraction-refinement, it is widely adopted in state-of-the-art complete verifiers [ 31 , 29 ] . The abstraction is numerical rather than structural, using convex relaxations [ 26 , 36 ] to bound intermediate values. Refinement is achieved via Branch-and-Bound (BaB), which splits input or activation domains to tighten the relaxation. While structural methods explicitly leverage CEGAR, the dataflow paradigm operates with a blind refinement process. Existing branching heuristics refine either on static geometric properties (e.g., interval width) or average-case sensitivity (e.g., BaBSR [ 3 ] ). These heuristcs fail to adequately utilize the diagnostic information from the verification failure in the abstract domain, that is, the specific state of the relaxed network when it violates the property. Our Insight: We argue that efficient BaB should be reformulated as a Dataflow CEGAR loop. When a relaxation-based verifier fails to prove a property, the underlying solver either implicitly finds a specific point x^{*} where the relaxed network violates the specification. x^{*} is either a true counterexample that falsify the property on the concrete network, or a spurious counterexample to the concrete network. The latter is not merely a byproduct of failure, but a precise witness to the abstraction error. x^{*} pinpoints exactly where the convex relaxation is too loose relative to the safety specification. Based on this insight, we propose DRG-BaB, a novel framework that integrates CEGAR-sytle guidance into the BaB process. Instead of branching on neurons that are merely "wide" or "sensitive", we introduce the Directional Relaxation Gap (DRG) heuristic. DRG analyzes the spurious counterexample to identify the specific neurons whose relaxation errors activaly contribute to the falsification in abstract domain. By prioritizing these neurons for branching, we transform the refinement step from a generic search into a targeted correction of the abstraction, significantly pruning the search tree. • A Dataflow CEGAR Framework for Neural Network Verification. We formalize the Branch-and-Bound search as a Counterexample-Guided Abstraction Refinement loop. Unlike existing approaches that treat verification failure as a generic signal to branch, we interpret the spurious counterexample as a precise witness to local abstraction errors. This paradigm shift allows us to transform the branching strategy from a static heuristic into a dynamic, goal-driven refinement process. • Directional Relaxation Gap Heuristic. To address the "attribution problem" of identifying which neurons are responsible for the spurious witness, we propose the DRG metric. By quantifying the relaxation error conditioned on the gradient direction of the safety loss, DRG effectively distinguishes active errors (which enable the violation) from inactive ones (which are geometrically loose but harmless). This resolves the "Wide but Tight" dilemma that misleads traditional width-based heuristics. • Generalization and Performance. We integrate our framework into the state-of-the-art GPU-accelerated verifier, \alpha - \beta -CROWN. Crucially, we derive a closed-form construction of spurious counterexample directly from the linear bounds (CROWN), eliminating the need for computationally expensive exact slolution. Extensive experiments on high-dimensional benchmarks (CIfAR-10 and MNIST) demonstrate that DRG-BaB reduces the search tree size and verification time compared to established baselines, confirming the efficacy of witness-guided refinement in large-scale verification. 2 Preliminaries In this section, we formalize the neural network verification problem and provide the necessary background on linear relaxation techniques and the Branch-and-Bound (BaB) framework. 2.1 Neural Networks and Verification Problem We consider an L -layer feed-forward neural network f:\mathbb{R}^{n_{0}}\to\mathbb{R}^{n_{L}} . Let z^{(i)} denote the pre-activation vector and \hat{z}^{(i)} denote the post-activation vector at layer i . The propagation is defined as: z^{(i)}=W^{(i)}\hat{z}^{(i-1)}+b^{(i)},\quad\hat{z}^{(i)}=\sigma(z^{(i)}),\quad i=1,\dots,L (1) where W^{(i)} and b^{(i)} are weights and biases, \hat{z}^{(0)}=x is the input, and \sigma(\cdot) is the element-wise activation function. In this work, we focus on the Rectified Linear Unit (ReLU), i.e., \sigma(y)=\max(0,y) . Given an initial input domain \mathcal{D}_{0}\subseteq\mathbb{R}^{n_{0}} (typically a hyper-rectangle defined by x_{L}\leq x\leq x_{U} ), the verification problem asks whether the output f(x) satisfies a safety property \mathcal{P} for all x\in\mathcal{D}_{0} . Without loss of generality, we consider robustness properties defined by a set of linear constraints on the output logits. This is equivalent to verifying that the margin function m(x) is strictly positive: \forall x\in\mathcal{D}_{0},\quad m(x):=Cf(x)>0 (2) where C is a specification matrix. If the global lower bound \min_{x\in\mathcal{D}_{0}}m(x)>0 , the property holds (Safe). If there exists a concrete input x^{*}\in\mathcal{D}_{0} such that m(x^{*})\leq 0 , then x^{*} is a valid counterexample (Unsafe). 2.2 Linear Relaxation and Branch-and-Bound Verification To circumvent the NP-completeness of exact reachability [ 15 ] , state-of-the-art verifiers employ Linear Relaxation to over-approximate network behavior for efficient bound propagation [ 36 , 26 ] . Consider a neuron j in layer i with pre-activation bounds [l_{j}^{(i)},u_{j}^{(i)}] . If the neuron is unstable (i.e., l_{j}^{(i)}<0<u_{j}^{(i)} ), the non-linear constraint \hat{z}=\text{ReLU}(z) is relaxed into a convex region defined by a linear upper bound connecting (l_{j}^{(i)},0) and (u_{j}^{(i)},u_{j}^{(i)}) , and a linear lower bound \hat{z}_{j}^{(i)}\geq\alpha_{j}^{(i)}z_{j}^{(i)} , where \alpha_{j}^{(i)}\in[0,1] is an optimizable parameter [ 34 ] . The geometric

Read the complete text