CS Paper Radar

FocusBranch: Combinatorial Branch-and-Bound for $\ell_0$ Neural Network Robustness Verification

Renwei Deng, Yang He, Linyi Li, Yuepeng Wang

cs.LG ·submitted 2026-11-09 08:00 UTC · v1
top venuecode/data

Abstract

Verifying the local robustness of neural networks under $\ell_0$ perturbations is inherently combinatorial, as it must reason over all sparse subsets of $ε$ perturbed pixels. This paper presents FocusBranch, a combinatorial branch-and-bound framework for $\ell_0$ robustness verification. The key insight is to make the $\ell_0$-ball decomposable and branchable using a node abstraction, which consists of a focus pixel set $\mathcal{S}$ and a level $l$, permitting at most $ε-l$ pixels outside $\mathcal{S}$. This abstraction unifies two branching mechanisms: concrete nodes branch through upper shadows to fix additional perturbed locations, while super nodes branch through covering designs to cover many perturbation cases with fewer child nodes. FocusBranch proves node safety by concretizing linear relaxations over node-constrained $\ell_0$-balls and recursively branches on unknown nodes. Rather than relying on a fixed verification plan, it samples nodes across levels to estimate safe rates and costs, then selects a starting level and branching strategy predicted to minimize verification time. Experiments on fully connected and convolutional classifiers for MNIST, Fashion-MNIST, and CIFAR-10 show that FocusBranch verifies $\ell_0$ robustness effectively across architectures and outperforms state-of-the-art verifiers. The code is available at: https://github.com/simpl-group/FocusBranch.

Comment
Accepted to NeurIPS 2026. 32 pages, 11 figures, 6 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Fit-LRP: Fitting Linear Relaxations to Polytopes for Neural Network Verification over Non-Convex Regions

cs.LG cs.AIeess.SYmath.OC ·2026-11-11 ·Brian Yarbrough, Jesse Wayment, Jingbo Wang, Philip E. Paré, Shreyas Sundaram
similarity 0.56
Abstract

State-of-the-art neural network verifiers evaluate linear relaxations over axis-aligned bounding boxes. However, verification domains in cyber-physical systems are rarely boxes. Reachability specifications, obstacle-avoidance constraints, and neural Lyapunov certificates typically yield oblique or non-convex polyhedral regions, over which box-based bounds become extremely loose. This paper proposes Fit-LRP (Fitting Linear Relaxations to Polytopes), a framework the implements exact optimization of affine bounds over non-convex domains (represented by unions of polytopes) by solving a sequence of small, low-dimensional linear programs. Our approach seamlessly enhances the final optimization step of LiRPA and $α,\! β$-CROWN branch-and-bound (BaB) algorithms. In BaB verification, approximating oblique constraints with axis-aligned splits causes severe combinatorial blowup and risks non-termination. By optimizing the final affine bound of a nonlinear function over the exact polyhedral state-space constraints our method eliminates box-induced over-approximations, enabling earlier search-tree pruning. On ARCH-COMP and neural Lyapunov benchmarks, Fit-LRP reduces branching on the hardest region by $47\times$, cuts worst-case verification time by $15\times$, and with region-wise partitioning, verifies on a single CPU $6.1\times$ faster than $α,\! β$-CROWN on a GPU.

0.38

CLAD: Constrained Abstract Domain for Neural Network Verification

cs.SE cs.LG ·2026-09-28 ·Hai Duong, Thanh Le, ThanhVu Nguyen
similarity 0.56
Abstract

Neural network verification (NNV) formally verifies that a network satisfies a specified property for all inputs within a defined region. Modern NNV tools employ abstract domains to compute a sound over-approximation of the network's behavior from the given input region, thus the tightness of these abstractions essentially determines efficiency. A long line of increasingly precise domains has been developed, but they all describe the valid input region in the same restrictive way, e.g., an Lp-norm ball. A practical input region is rarely a simple Lp ball, but rather a combination Lp ball with additional constraints. Verifying a network over such a region with existing abstraction produces a loose over-approximation, which results in either failing to verify a property or spurious counterexamples. We introduce Constrained Lagrangian Abstract Domain (CLAD), a new abstract domain that computes a sound over-approximation of neural networks over input regions defined by a combination of convex constraints. CLAD propagates these constraints and tightens bounds over the true feasible region. However, bounding a neuron over the intersection of these constraints has no closed-form solution, so CLAD relaxes each constraint into the objective with a Lagrange multiplier and solves the resulting max-min problem with a projected primal-dual method, alternating a projected gradient step on the input with a multiplier update. CLAD supports any convex constraint with a subgradient, e.g., from automatic differentiation. We evaluate CLAD on 1,944 instances across four convolutional networks with motion-blur structured perturbations with halfspace or L2-ball constraints. On standard unconstrained Linf property, CLAD verifies as many instances as GCPCROWN at a similar runtime. On constrained properties, CLAD verifies 60% more instances than GCPCROWN on L2-ball properties, and 22% more in total.

0.34

Closing the Loop: Branch-and-Bound for Scalable Verification of Nonlinear Neural Feedback Systems

cs.AI ·2026-09-14 ·I. Samuel Akinwande, Mykel J. Kochenderfer, Clark Barrett
similarity 0.56
Abstract

Despite recent advances in the verification of nonlinear neural feedback systems, scalability remains the central obstacle, as state-of-the-art solvers do not yet handle the network sizes and nonlinear dynamics of autonomy applications. Combinatorial solvers do not scale to large networks, whereas propagative solvers excessively sacrifice precision. This work seeks to improve the scalability of combinatorial solvers by formulating verification as branch-and-bound on an abstraction of the closed-loop system. We introduce \rail, an interface that exposes polyhedral enclosures of the dynamics to LiRPA-style bound propagation, and \clipper, a branch-and-bound algorithm that jointly refines enclosures and splits controller activations. This framework enables joint reasoning on the computational graph of the closed-loop system, preserving symbolic correlations across time steps. We present our construction and show that it yields significant improvements over the state of the art.

0.45

Fractal Gadgets for Neural Networks: The Complexity of the Narrow Regime

cs.CC ·2026-10-05 ·Olivier Bournez, Johanne Cohen, Laura Cohen, Adrian Wurm
published similarity 0.56
Abstract · 30 pages, 8 figures, Accepted at FSTTCS 2026

We study the verification problem for deep narrow ReLU neural networks: given a network of bounded width computing a piecewise-affine map on [0,1], does some input satisfy a prescribed output constraint? Classical NP-hardness proofs for ReLU verification use one neuron per Boolean variable and say nothing about networks of small constant width, while width-1 networks are easy to verify. We show that verification of ReLU networks is NP-complete at width 4 for arbitrary inputs in [0,1]. When inputs are restricted to a natural discrete encoding set, NP-completeness already holds at width 3. Together with polynomial-time decidability at width 1, this leaves open only width 2 on the encoding set, and widths 2 and 3 on [0,1]. The technical core is a fractal preprocessing gadget: a width-2 ReLU subnetwork whose iterate vanishes precisely near a finite Cantor-like subset of [0,1] with 2^n points. It reduces verification of a continuous function on [0,1] to verification on 2^n discrete points without increasing the width, and is the missing ingredient for width-bounded hardness reductions. The same construction yields further results at width 3 on the encoding set: the universal problem is coNP-complete, counting zeros is #P-complete, a majority variant is PP-complete, and approximating the minimum output within a constant gap inherited from Max-3Sat is NP-hard. The NP, coNP and inapproximability results lift to all of [0,1] at width 4; lifting counting and majority, and lifting at width 3, remain open.

0.53

Certified Robustness via Sparse Second-Order Cone Relaxations

cs.LG ·2026-10-12 ·Mohammadreza Maleki, Daniel Sadig, Rushendra Sidibomma, Mahyar Fazlyab, Arman Adibi +1 more
benchmark similarity 0.56
Abstract

Certified robustness is critical for deploying neural networks in safety-sensitive settings, but computing exact certificates typically requires solving nonconvex optimization problems. Practical verifiers use convex relaxations: linear programming (LP) relaxations are scalable but often too conservative, whereas semidefinite programming (SDP) relaxations can be substantially tighter but are computationally expensive. We introduce a hierarchy of second-order cone programming (SOCP) relaxations that provide stronger certificates than LP while avoiding the cost of global positive-semidefinite constraints. Our construction combines convex-hull relaxations of ReLU activations, selective McCormick lifting over certified variable bounds, and second-order cone constraints induced by 2-by-2 principal minors. Adding these constraints progressively yields a monotone hierarchy of increasingly tight bounds with a controllable computation-tightness trade-off. On fully connected and convolutional networks on MNIST and CIFAR-10, SOCP-based verification improves certified robust accuracy over LP-based verification and is competitive with alpha,beta-CROWN, while remaining orders of magnitude faster than SDP-based verification. These results position selective second-order constraints as a practical middle ground between scalable LP-based and tight SDP-based certification. Finally, we introduce class-optimized robust evaluation (CORE), which applies tighter relaxations only to target classes not certified by cheaper ones. On the fully connected MNIST benchmark, CORE variants match SDP-cert's certified robust accuracy while reducing average verification time by up to 86.30%.

0.11

Branch and Bound for Relational Verification of Neural Networks

cs.LG ·2026-08-13 ·Kota Fukuda, Zhenya Zhang, Guanqin Zhang, Jianjun Zhao
published similarity 0.54
Abstract · The full version of the paper accepted by EMSOFT 2026

Verification of neural networks against relational specifications, such as global robustness, is crucial for safety-critical applications of cyber-physical systems (CPS), given their increasing adoption of AI components. Compared to simple trace properties (e.g., local robustness), verifying relational specifications requires reasoning about the relationship between multiple network inferences, which brings significant technical challenges. Existing research has explored abstraction techniques based on sound and convex over-approximation of neural network outputs; however, since these approaches are inherently incomplete and may raise false alarms, they further underscore the need of effective abstraction refinement. In this paper, we propose a branch-and-bound (BaB) framework to mitigate the issue, which iteratively splits the problem until all sub-problems are verified. Specifically, our BaB framework features splitting of relational neurons rather than individual neurons as prior works do, and as the core of our technique, we devise a relational neuron selection strategy based on the dual formulation of the verification problem, which allows us to efficiently select the (most likely) optimal relational neuron that maximizes the refinement brought by problem splitting. We evaluate SaBRe on 817 verification problems across ACAS Xu, MNIST-F, MNIST-C, CIFAR and GTSRB. The results show that SaBRe outperforms different baseline approaches, in terms of the number of solved instances and verification efficiency, which demonstrates the effectiveness of our proposed techniques.

0.19

NP-Hardness of Minimizing Neurons in Two-Hidden-Layer ReLU Neural Networks

cs.LG ·2026-10-08 ·Sangrock Lee
top venuetheory similarity 0.54
Abstract

A fundamental question in neural network architecture optimization is whether the minimum hidden-neuron count required to approximate a target function within a prescribed tolerance can be computed efficiently. This paper resolves this question for two-hidden-layer ReLU networks under an $L^p(\mathbb{R}^d,\mathbb{R}^m)$ approximation constraint. For every fixed $d \ge 1$, $m \ge 1$, and $1 \le p < \infty$, we prove that computing the optimum exactly is NP-hard. The result holds even when the target is represented by a rational ReLU network whose realization is nonzero, componentwise nonnegative, compactly supported, globally Lipschitz, and continuous piecewise affine. The polynomial-time reduction from 3-SAT produces an architecture gap in which unsatisfiable formulas yield an optimum of zero, whereas satisfiable formulas yield an optimum of at least $d+2$. The proof constructs compactly supported polyhedral frustum functions realized by two-hidden-layer ReLU networks and establishes the $L^p$-density of finite linear combinations of box-frustum functions. The results offer theoretical justification for employing heuristic approximation methods in the design of ReLU neural networks, illustrating that attaining a minimal configuration within polynomial time is computationally unachievable.

0.63

Sumset Structure in Local Computation

cs.CC ·2026-09-19 ·Alexander Golovnev, Mohit Gurumukhani
publishedtheory similarity 0.54
Abstract

We introduce and study a new model of decision trees that lies at the frontier of provable circuit lower bounds. We study $\ell$-local decision trees, in which each internal node queries an $\ell$-local function of the input. We show that sufficiently strong lower bounds for $\ell$-local decision trees would imply several breakthrough circuit lower bounds, including super-linear size lower bounds for log-depth circuits and improved bounds for unrestricted-depth circuits. Previously, such consequences were known to follow from strong lower bounds for depth-$3$ circuits, which has been the main prior approach in attempting to prove these results. Since local decision trees are strictly weaker than depth-$3$ circuits, this provides a formally easier route to the same circuit lower-bound consequences. We prove essentially optimal lower bounds for a weaker variant that we call oblivious $\ell$-local decision trees, where all nodes at the same depth query the same function. Our lower bounds follow from a new technique that uncovers sumset structure in local maps, and our hard functions are sumset dispersers, sumset condensers, and directional affine dispersers. Along the way, we give an explicit construction of a sumset condenser with small entropy loss. As an additional contribution, we initiate the study of degree-$2$ decision trees, in which each query is a quadratic polynomial of the input. We show that proving lower bounds in this model is a natural stepping stone toward constructing dispersers for degree-$2$ variety sources, which imply improved circuit lower bounds for unrestricted depth circuits. We prove nearly maximal lower bounds for the oblivious variant of the model.

0.35