cs.LGNov 17, 2026

BernBRS: Certified Backward Reachability for Deep Bernstein Neural Networks

Authors: Ibrahim Albool, Yasser Shoukry

Organizations: University of California, Irvine Irvine, CA, USA

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.

Figures & tables

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

May 11, 2026

Hierarchical End-to-End Taylor Bounds for Complete Neural Network Verification

Reachability analysis of neural networks, which seeks to compute or bound the set of outputs attainable over a given input domain, is central to certifying safety and robustness in learning-enabled physical systems. Since exact reachable set computation is generally intractable, existing methods typically rely on tractable overapproximations. Examining the state of the art for smooth, twice-differentiable networks, we observe that existing approaches exploit at most second-order information and do not systematically leverage higher-order information. In this work, we introduce HiTaB, a novel verification framework that exploits second-order smoothness through both the Hessian, ∇2f\nabla^2 f, and its Lipschitz constant, L∇2fL_{\nabla^2 f}. We further develop a unified hierarchy of zeroth-, first-, and second-order bounds, together with precise conditions under which higher-order approximations yield provable improvements. Our main technical contribution is a compositional procedure for efficiently bounding L∇2fL_{\nabla^2 f} in deep neural networks via layerwise propagation of curvature bounds. We extend the framework to both ℓ2\ell_2- and ℓ∞\ell_\infty-constrained input sets and show how it can be integrated into branch-and-bound verification pipelines. To our knowledge, this is the first practical reachability analysis framework for smooth neural networks that systematically exploits Lipschitz continuity of curvature, leading to tighter and more informative safety certificates.
Jun 6, 2024

Provable Bounds on the Hessian of Neural Networks: Derivative-Preserving Reachability Analysis

We propose a novel reachability analysis method tailored for neural networks with smooth activations. Our method relies on constructing an end-to-end first-order Taylor expansion of the network and bounding the remainder. To enable this, we develop a scalable algorithm for computing closed-form bounds on both the gradient norm and Hessian norm of the network. A key component is a loop transformation of the activation functions, which leverages their monotonicity to sharpen the bounds. This yields a local abstraction that preserves the network's value and gradient at the expansion point. For larger input domains, we integrate this local model into a branch-and-bound scheme, recursively refining the overapproximation. We validate our approach through extensive experiments and demonstrate scalability and accuracy improvements over state-of-the-art verification baselines.
Aug 25, 2026

(DNN)2(\text{DNN})^2: Doubly Non-Negative Relaxations for Deep Neural Networks

Existing linear program (LP) and semidefinite program (SDP) relaxations for rectified linear unit (ReLU) neural network (NN) verification yield overly-conservative safety guarantees due to significant relaxation gaps. While the completely positive program (CPP) formulation closes this gap, it is NP-hard to solve. Its cheapest tractable relaxation, the doubly non-negative program (DNN), retains critical constraints as an SDP, but one whose size exceeds the reach of interior-point methods at practical scale. While Burer-Monteiro (BM) factorization has been applied to make SDP-based verification scalable, no such result exists for the strictly tighter DNN formulation. A key obstacle is that additional non-negativity constraints in the DNN cause dual multipliers for optimality certification to be non-unique, making standard certification methods inapplicable. We propose a novel eigenvalue maximization procedure that searches the non-unique multiplier space for a valid certificate, i.e. a global optimality guarantee. Experiments demonstrate that our approach (DNN)2(\text{DNN})^2 produces bounds consistently tighter than the standard SDP method, often matching the exact solution, and that our certification procedure confirms global optimality when a valid certificate exists. These results are a key step toward providing tight, certifiable, and computationally scalable verification guarantees needed to deploy neural network controllers and perception modules in safety-critical autonomous systems.