BernBRS: Certified Backward Reachability for Deep Bernstein Neural Networks
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
| BernBRS | CROWN | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Data set | Bernstein network | Size | Radius | # param | IR | OR | T (s) | Patterns | Splits | IR | OR | T (s) | Elements | Splits |
| MNIST | 1 | 113,810 | 0.634 0.076 | 0.715 0.038 | 16.3 0.2 | 1,259 47 | 400 0 | 0.000 0.000 | 0.501 0.004 | 13.8 0.0 | 8,192 0 | 8,191 0 | ||
| 521,410 | 0.543 0.028 | 0.656 0.035 | 34.2 1.0 | 2,809 237 | 400 0 | 0.000 0.000 | 0.500 0.007 | 31.5 0.0 | 8,192 0 | 8,191 0 | ||||
| 1,169,010 | 0.482 0.086 | 0.625 0.021 | 72.6 3.4 | 4,278 273 | 400 0 | 0.000 0.000 | 0.501 0.006 | 55.6 0.3 | 8,192 0 | 8,191 0 | ||||
| 0.02 | 91,610 | 0.845 0.011 | 0.851 0.019 | 6.2 0.5 | 803 25 | 400 0 | 0.000 0.000 | 0.499 0.005 | 5.2 1.1 | 3,413 1,182 | 3,412 1,182 | |||
| 0.02 | 102,710 | 0.794 0.009 | 0.835 0.034 | 9.8 0.8 | 1,020 32 | 400 0 | 0.000 0.000 | 0.498 0.003 | 7.3 0.0 | 4,096 0 | 4,095 0 | |||
| Sentence | Student | TinyBERT |
|---|---|---|
| i just loved every minute of this film . | proud, enjoyed, loving, amazing | proud, enjoyed, loving, amazing |
| my thoughts were focused on the characters . | concentrate, focus, focusing | concentrate, focus, focusing |
| jones . . . does offer a brutal form of charisma . | ruthless | ruthless |
| a warm but realistic meditation on friendship , family and affection . | accurate, perfection, luxury, positive, progressive, true, uniquely, uncanny, imaginative, solid, beautiful, vision, fine, magnificent, splendid, squared, flawless, exquisite | accurate, perfection, luxury, positive, progressive, true, uniquely, uncanny, imaginative, solid, beautiful, vision, fine, magnificent, splendid, squared, flawless, exquisite |
| one of the most significant moviegoing pleasures of the year . | leisure, enjoy, joy, treat, enjoyable, rewards, happiness, beneficial, delight, belle, charm, pleasure, touch, benefits | leisure, enjoy, joy, treat, enjoyable, rewards, happiness, beneficial, delight, belle, charm, pleasure, touch, benefits |
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
| Experiment | Network | Inputs | Training | Runs |
|---|---|---|---|---|
| 2-D, random | MLP, up to width 500, depth 6, degree 15 | 2 | none | 859 |
| Images | MLP, width 100–500, depth 2–4 | 784; 3,072 | Appendix E | 108 |
| Case study 1, closed loop | MLP, width 128, depth 1, merged up to 40 layers | 17 | Appendix F | 200 |
| Case study 2, transformer | Last block of TinyBERT, 3 heads | 312 | Appendix G | 43 |
| Data set | Width | Depth | Rule | Target | Floor | Robust from | Kept from |
|---|---|---|---|---|---|---|---|
| MNIST | 100 | 2 to 4 | ramp | 0.01 | 0 | 2 | 16 |
| MNIST | 300 | 4 | ramp | 0.002 | 0.5 | 2 | 16 |
| MNIST | 500 | 4 | ramp | 0.001 | 0.5 | 2 | 16 |
| GTSRB, CIFAR-10 | 100 | 2 to 4 | adaptive | 0.004 | 0.5 | 7 | 21 |
| GTSRB, CIFAR-10 | 300 | 4 | adaptive | 0.002 | 0.5 | 7 | 21 |
| GTSRB, CIFAR-10 | 500 | 4 | adaptive | 0.001 | 0.5 | 7 | 21 |
| episode | target step | start steps | logged pitch at (rad) |
|---|---|---|---|
| 11 | 450 | 430 to 449 | 1.27 |
| 24 | 504 | 484 to 503 | 1.43 |
| 25 | 254 | 234 to 253 | 1.39 |
| 23 | 491 | 471 to 490 | 1.10 |
| 49 | 350 | 330 to 349 | 1.51 |
| coordinates | unit | |||
|---|---|---|---|---|
| height | m | 0.005 | 0.02 | 0.08 |
| pitch | rad | 0.01 | 0.04 | 0.16 |
| six joint angles | rad | 0.002 | 0.008 | 0.032 |
| forward speed | m/s | 0.1 | 0.4 | 1.6 |
| vertical speed | m/s | 0.1 | 0.4 | 1.6 |
| pitch rate | rad/s | 0.05 | 0.2 | 0.8 |
| coordinates | wide box | thin box |
|---|---|---|
| height | ||
| pitch | ||
| six joint angles | ||
| forward speed | ||
| vertical speed | ||
| pitch rate |
Neural Network Verification
Neural network verification develops methods to prove whether networks satisfy properties such as robustness, safety, and bounded output behavior.
See all 141 papers