BernBRS: Certified Backward Reachability for Deep Bernstein Neural Networks

Ibrahim Albool, Yasser ShoukryarXiv 2026 · arXiv

TL;DR

BernBRS is a novel, highly scalable framework for the certified safety verification of neural networks using Bernstein polynomial activations. By leveraging unique mathematical properties, it simultaneously computes tight inner and outer approximations of the Backward Reachable Set (BRS), enabling the verification of massive architectures like Transformers and RL controllers that were previously considered intractable.

What Problem Does This Paper Address?

As neural networks (NNs) are increasingly deployed in safety-critical cyber-physical systems—like autonomous vehicles or industrial robots—we need mathematically rigorous ways to guarantee their behavior. Backward reachability analysis is a key tool for this: it asks, "Which set of initial inputs will lead the system into a specific (potentially dangerous) output region?"

However, computing this Backward Reachable Set (BRS) is notoriously difficult. Unlike forward analysis (predicting outputs from inputs), backward analysis is plagued by the fact that NNs are non-invertible, non-convex, and topologically complex. Existing certified methods often struggle to scale beyond small networks or provide "loose" bounds that aren't useful for real-world safety guarantees.

Methods

The authors introduce BernBRS, a framework specifically designed for DeepBern-Nets—neural networks that use Bernstein polynomials as activation functions instead of the standard ReLU.

Figure 1: A Bernstein activation with its control points and an interval [𝑧,𝑧] inside its bounds.

The core of BernBRS is an iterative cycle of three main components:

  1. Forward Bounding: Using the "enclosure property" of Bernstein polynomials, the algorithm computes linear over- and under-approximations of the network's behavior. Because these polynomials are defined by control points, these bounds can be computed algebraically without expensive non-linear searches.
  2. Backward Contraction: The algorithm works in reverse, propagating constraints from the output back to the input to prune regions that definitely cannot reach the target. For neurons that are "monotone" (always increasing or decreasing), it uses a specialized inversion process to tighten bounds further.
  3. Gap-Driven Branching: When bounds are too loose ("undecided"), the algorithm must split the input space. BernBRS uses a "Gap Identity" to calculate exactly which neuron or input dimension contributes most to the error, allowing for highly targeted refinement.
Figure 2: The BernBRS algorithmic architecture, showing the iterative cycle of bounding, contraction, and branching.

Datasets

The framework was evaluated across several domains:

  • Synthetic 2D Networks: Used to validate mathematical correctness against exact ground truths.
  • Image Classifiers: Scalability tests on MNIST, GTSRB (Traffic Signs), and CIFAR-10, with networks containing up to 2.3 million parameters.
  • Reinforcement Learning: A closed-loop control case study using the MuJoCo Half-Cheetah environment.
  • Natural Language Processing: A case study on a distilled TinyBERT Transformer block using the SST-2 sentiment dataset.

Key Insights and Ideas

  • Algebraic Efficiency: Bernstein polynomials allow for certified linear relaxations to be computed purely through algebraic manipulation of control points. This is much faster than the optimization-based methods required for other activation functions.
  • The Gap Identity: The authors derived a mathematical identity that decomposes the total approximation error into contributions from individual neurons. This turns branching from a "best guess" into a precise surgical strike on the sources of uncertainty.
  • Joint Splitting: To handle high-dimensional inputs (like images or Transformer embeddings), BernBRS uses a statistical "joint split" strategy. Instead of bisecting every dimension (which leads to exponential explosion), it groups influential neurons to refine the space efficiently.
  • Certified Inner Bounds: Unlike many tools that only provide an "outer" bound (where the BRS might be), BernBRS provides an "inner" bound—a set of inputs guaranteed to reach the target.

Key Results

  • Superior Tightness: In 2D benchmarks, BernBRS achieved inner ratios of >0.97 and outer ratios of >0.98, meaning the approximations were nearly identical to the true, complex BRS.
  • Unprecedented Scalability: BernBRS successfully verified networks with millions of parameters. In head-to-head comparisons with a CROWN-based baseline, the baseline often failed to find any guaranteed safe region (inner ratio of 0), while BernBRS maintained high accuracy.
  • Real-World Application: The tool verified a 40-layer closed-loop controller for a legged robot and proved that specific word substitutions in a Transformer model would not change its sentiment classification.

Limitations and Future Work

  • Surrogate Dependency: The formal guarantees apply to the "Bernstein student" (a network trained or distilled to use Bernstein activations). While these students match the original models (like TinyBERT) with high accuracy (e.g., 99.2%), the original model itself remains technically uncertified.
  • Linearized Dynamics: For the robotics case study, the safety guarantees are relative to a linearized model of the simulator, not the full, non-linear MuJoCo physics engine.
  • Future Directions: The authors suggest extending the "joint split" logic and exploring tighter integration with non-linear system dynamics to provide end-to-end physical safety proofs.

Summary updated

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.
BibTeX
@misc{albool2026bernbrs,
  author = {Ibrahim Albool and Yasser Shoukry},
  title = {{BernBRS: Certified Backward Reachability for Deep Bernstein Neural Networks}},
  year = {2026},
  eprint = {2611.22083},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.22083},
}
Figure