CS Paper Radar

BernBRS: Certified Backward Reachability for Deep Bernstein Neural Networks

Ibrahim Albool, Yasser Shoukry

cs.LG ·submitted 2026-11-17 02:10 UTC · v1
hot direction

Abstract

Ensuring the safety of complex neural network systems requires mathematically rigorous verification. While backward reachability analysis is a critical tool for identifying safe initial states, computing tight, formal bounds remains notoriously difficult to scale. Recent advancements have demonstrated that DeepBern-Nets neural networks utilizing Bernstein polynomial activation functions possess advantageous mathematical properties that enable exceptionally fast and tight forward reachability analysis. Building upon this efficiency, this paper introduces BernBRS, a highly accurate and scalable framework for the backward reachability analysis of DeepBern-Nets. BernBRS simultaneously computes certified inner and outer approximations of the Backward Reachable Set (BRS). Rather than relying on single convex bounding, our method intelligently refines a cover of the input space by analyzing activation patterns, splitting the input domain precisely where an exact decomposition of the relaxation gap predicts the most significant reduction in error. This targeted refinement enables high levels of scalability to highly complex and massive architectures that remain intractable for existing certified methods. We demonstrate the efficacy of our framework on high-dimensional models, including a linearized closed-loop approximation of the Half-Cheetah controller and a distilled Bernstein student of a Transformer block and we empirically study how these model-level guarantees relate to the original Half-Cheetah and TinyBERT classifier, respectively.

Comment
18 pages, 6 figures, 7 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Scalable Neural Safety Certification via Monotonicity

eess.SY cs.LGmath.OC ·2026-11-08 ·Amirreza Alavi, Majid Zamani, Saber Jafarpour
similarity 0.64
Abstract

Learning-based safety certification offers a promising route for verifying complex dynamical systems when explicit models are unavailable, but existing data-driven methods often scale poorly: they treat the system as a black box, rely on dense discretizations or Lipschitz bounds, and consequently suffer from sample complexity that grows exponentially with dimension. This paper shows that a common structural property of dynamical systems--monotonicity--can be used to break this curse of dimensionality. We develop a data-driven framework for robust safety verification and safe controller synthesis for unknown monotone systems using only simulator queries. Our main theoretical result proves that, for monotone systems with upper-closed unsafe sets, safety is completely characterized by the existence of monotone inductive barrier certificates. This structure reduces certificate verification over continuous state spaces to localized boundary checks over finitely many cells. To learn such certificates, we introduce Max-Monotone Networks, a monotone neural architecture with universal approximation guarantees for monotone functions. We then propose a training and refinement algorithm that, upon successful termination, returns formally valid neural barrier certificates and, under mild partition assumptions, requires only $O(n)$ simulator queries. Across high-dimensional benchmarks, including oscillator networks with up to $13{,}659$ states and traffic networks with $1{,}000$ states, our method certifies safety in regimes where prior approaches either do not converge or exceed memory limits. These results demonstrate that exploiting order structure can make neural safety certification both scalable and formally sound.

0.13

Implicit DeepReach Without Implicit Differentiation

eess.SY math.OC ·2026-11-09 ·Xingjian Li, Kelvin Kan, Deepanshu Verma, Krishna Kumar, Hayden Schaeffer +1 more
similarity 0.63
Abstract

We consider the problem of approximating backward reachable and reach-avoid tubes for high-dimensional nonlinear systems whose Hamiltonians require numerical optimization over constrained controls and disturbances. Existing neural Hamilton-Jacobi (HJ) reachability methods alleviate the dimensionality bottleneck of grid-based solvers, but evaluating Hamiltonians without closed-form expressions introduces an additional computational challenge. We show that, under suitable assumptions, the gradients required for value-function training can be computed without differentiating through the inner optimization problem. Specifically, we establish an envelope-type gradient identity for the saddle point Hamiltonian, under which the optimal control and disturbance enter backpropagation as constants without gradient tracking. This enables end-to-end neural HJ reachability with numerically evaluated Hamiltonians while avoiding both solver unrolling and implicit differentiation. We demonstrate the accuracy and computational efficiency of the proposed approach on nonlinear reachability and reach-avoid problems of different scales.

0.07

Lipschitz Thinking: Ten Years of Certifiable-by-Design Robust Neural Networks

cs.LG ·2026-10-05 ·Fabio Brau, Giorgio Piras, Maura Pintor, Battista Biggio
similarity 0.63
Abstract

The Lipschitz property of a deep neural network provides a direct measure of its sensitivity to input perturbations and, when explicitly controlled, offers a principled way to limit the propagation of errors and improve robustness. Over the past decade, Lipschitz-bounded layers have been incorporated into increasingly expressive and high-performing deep models, narrowing the gap between empirical robustness and formal, by-design guarantees of stability. This article introduces the fundamental concepts underlying Lipschitz-bounded neural networks, explaining the principles behind Lipschitz-constrained layers, the mechanisms used to enforce their bounds, and how they yield robustness certificates at the cost of a single forward pass. The tutorial concludes by discussing emerging and open directions, highlighting Lipschitz control as a general framework for offering guaranteed, by-design stability.

0.07

Bern2Edge: A Neurosymbolic Compiler for Edge Deployment via Bernstein Polynomial Networks

cs.LG cs.AR ·2026-08-20 ·Malak Gamal El-Din, Yifan Zhang, Yasser Shoukry, Sitao Huang, Salma Elmalaki
published similarity 0.62
Abstract · 14 pages, 10 figures. Accepted at CODES+ISSS 2026, TCAD journal 2026

Deploying high-accuracy neural networks on resource-constrained edge devices remains challenging, as existing approaches treat training, compression, and hardware synthesis as separate stages, leaving a gap between software-trained models and efficient end-to-end deployment with limited support for interpretability. We propose Bern2Edge, an end-to-end framework that uses knowledge distillation to convert a pretrained teacher feed-forward network into hardware-efficient representations via Bernstein polynomial activations. This representation enables two deployment paths: (i) a high-fidelity LUT-based realization that preserves model fidelity under compression, and (ii) a symbolic rule-based representation derived from Bernstein activation geometry, enabling interpretable inference with explicit input-space constraints. The resulting BNNs achieve up to 2.12 percentage-point (pp) accuracy improvement over ReLU under identical compression constraints. At the system level, Bern2Edge achieves up to 99.8% latency reduction and 95.2% BRAM reduction relative to a W8A8 quantized teacher on an AMD Xilinx KV260 FPGA, while maintaining accuracy within 0.5 pp, and further deploys on a low-power Spartan-7 XC7S15 FPGA. The rule-based path reduces DSP usage by up to 89.0% at a cost of 1.5 pp in total accuracy.

0.32

ConDR: Conservative Reachability through Neural Hamilton-Jacobi Subsolutions

cs.RO cs.LGeess.SY ·2026-11-04 ·Kendra Givens, Taylor T. Johnson, Bryan C. Ward, Thomas Beckers
theoryhot direction similarity 0.62
Abstract · 8 pages, 4 figures

Hamilton-Jacobi (HJ) Reachability identifies the unsafe states of a dynamical system from which it can be forced into failure under worst-case disturbance. However, classical grid-based solvers scale exponentially with state dimension. DeepReach improves scalability by replacing the grid with a neural value function trained on the HJ-Isaacs (HJI) variational inequality (VI), but penalizes both sides of the residual equally. This allows the learned value to lie above the true one and unsafe states to be misclassified as safe. We propose Conservative DeepReach (ConDR) which aims to learn a subsolution of the HJI VI such that the learned unsafe set contains the true one. ConDR enforces the obstacle branch and terminal condition by construction, pushes the HJI residual to a safety margin $ε$ below zero with a one-sided loss, and prevents the degenerate solution of classifying everything as unsafe. We prove that the exact solution of the margin-shifted VI that ConDR trains toward is a subsolution of the original VI so its unsafe set contains the true one and its value lies within $ετ$ of the true value function. We compare against DeepReach and MADR in the established systems of Air3D, Air6D, a 9D multi-vehicle system, and a 13D quadrotor. ConDR reports the lowest rate of unsafe state misclassified and the lowest closed-loop collision rates with at most a small increase in intervention. On Air3D and Air6D, ConDR tolerates model mismatch that scales with $ε$. At matched false-negative rates, ConDR's unsafe sets are smaller than the baselines showing the safety is not obtained by trivial over-approximation.

0.34

Training Mixed-Monotone Neural Networks for Verification Without Set Propagation

cs.LG ·2026-10-22 ·Jonas Fingerhut, Lukas Koller, Matthias Althoff
theory similarity 0.61
Abstract · 20 pages, 3 figures, 9 tables

Most formal verification approaches for neural networks conservatively enclose the output set of the neural network. However, computing a tight output enclosure is in general computationally hard. We sidestep this challenge with a novel neural network architecture that realizes mixed-monotone functions as the difference of monotone subnetworks. By utilizing the theory on mixed-monotone systems, this reduces the computation of a tight output enclosure from complicated set propagation to two simple forward passes of opposite corners of an input interval. Moreover, because the size of the resulting enclosure is a closed-form function of the weights of the neural network, we can directly minimize it during training. We prove a lower bound on the size of any such enclosure, given by the total variation of the represented function generalized to several inputs, which makes it possible to compare the tightness of the enclosure against the optimum. Our evaluation on regression and dynamical-system benchmarks demonstrates that our training reduces the enclosure size to within 0.5% of the lower bound without sacrificing prediction accuracy. Computing our enclosure is orders of magnitude faster than CROWN and $α$-CROWN and on deep networks it is also tighter than zonotope propagation and CROWN, while its size exceeds that of $α$-CROWN by only 5.1%.

0.18

CLAD: Constrained Abstract Domain for Neural Network Verification

cs.SE cs.LG ·2026-09-28 ·Hai Duong, Thanh Le, ThanhVu Nguyen
similarity 0.61
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.35

Certified Inference and Training for Deep Equilibrium Networks: A Continuation Framework with Polynomial Complexity Guarantees

cs.LG stat.ML ·2026-09-15 ·Alex Borisevich
similarity 0.61
Abstract · Python scripts and Lean formalization are included as ancillary files

We develop a certified continuation framework for inference and training in deep equilibrium networks (DEQs), with training posed as interpolation to accuracy $2^{-b}$. For inference, input homotopy selects an equilibrium branch from a supplied start root, and a rounded tracker follows it under quantitative conditioning, derivative, boundary, and tube-radius certificates. The framework includes structured factorized certificates, sequential block elimination, inheritance of contraction guarantees in adapted coordinates, and bordered continuation through simple folds. For smooth multidimensional DEQs, including tanh networks, rational local tests can construct and validate oriented continuation charts under explicit geometric promises. For training, programmable dormant bilinear rank-one channels provide output-preserving residual-aligned repairs. Loaded Tikhonov solves diagnose insufficient parameter-to-output directions, while certified gate realization, column stability, well-posed inference, and finite-update error budgets control each pass. Under polynomially bounded certificate, encoding, precision, and backend costs, both inference and training have bit complexity $O(\mathrm{poly}(L+b))$, where $L$ is the encoded instance length; training uses $O(b+\ell)$ passes and reserve channels from an initial residual bounded by $2^\ell$. A budgeted implementation returns either certified success or inconclusive termination. The quantitative core and local certificate machinery are machine-checked in Lean 4, while numerical experiments illustrate the training mechanism.

0.35