mlsanityData to 7 Oct 2026

Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Robustness Verification

arXiv 2103.06624 ↗First posted 11 Mar 2021cs.LG cs.AI cs.CRcited by 224

Not on the map. Why?

Abstract (arXiv)

Bound propagation based incomplete neural network verifiers such as CROWN are very efficient and can significantly accelerate branch-and-bound (BaB) based complete verification of neural networks. However, bound propagation cannot fully handle the neuron split constraints introduced by BaB commonly handled by expensive linear programming (LP) solvers, leading to loose bounds and hurting verification efficiency. In this work, we develop β-CROWN, a new bound propagation based method that can fully encode neuron splits via optimizable parameters β constructed from either primal or dual space. When jointly optimized in intermediate layers, β-CROWN generally produces better bounds than typical LP verifiers with neuron split constraints, while being as efficient and parallelizable as CROWN on GPUs. Applied to complete robustness verification benchmarks, β-CROWN with BaB is up to three orders of magnitude faster than LP-based BaB methods, and is notably faster than all existing approaches while producing lower timeout rates. By terminating BaB early, our method can also be used for efficient incomplete verification. We consistently achieve higher verified accuracy in many settings compared to powerful incomplete verifiers, including those based on convex barrier breaking techniques. Compared to the typically tightest but very costly semidefinite programming (SDP) based incomplete verifiers, we obtain higher verified accuracy with three orders of magnitudes less verification time. Our algorithm empowered the α,!β-CROWN (alpha-beta-CROWN) verifier, the winning tool in VNN-COMP 2021. Our code is available at http://PaperCode.cc/BetaCROWN

Key facts. Cited by 224 papers in the map (data through 7 Oct 2026). Builds on 28 of its 56 references that are in the map. First posted on arXiv 11 Mar 2021.

Builds on

28 of 56 references.

References · 28

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  3. 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 739
  4. 2017Provable defenses against adversarial examples via the convex outer adversarial polytopecited by 564
  5. 2018Efficient Neural Network Robustness Certification with General Activation Functionscited by 439
  6. 2018On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Modelscited by 322
  7. 2016Safety Verification of Deep Neural Networkscited by 262
  8. 2017Formal Verification of Piece-Wise Linear Feed-Forward Neural Networkscited by 241
  9. 2020Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observationscited by 235
  10. 2019Towards Stable and Efficient Training of Verifiably Robust Neural Networkscited by 204
  11. 2018Formal Security Analysis of Neural Networks using Symbolic Intervalscited by 185
  12. 2020Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifierscited by 183
16 more
  1. 2018Semidefinite relaxations for certifying robustness to adversarial examplescited by 178
  2. 2018Efficient Formal Safety Analysis of Neural Networkscited by 165
  3. 2017Robust Deep Reinforcement Learning with Adversarial Attackscited by 152
  4. 2018Scaling provable adversarial defensescited by 141
  5. 2019Branch and Bound for Piecewise Linear Neural Network Verificationcited by 138
  6. 2021Robust Reinforcement Learning on State Observations with Learned Optimal Adversarycited by 133
  7. 2018A Dual Approach to Scalable Verification of Deep Networkscited by 125
  8. 2019A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networkscited by 124
  9. 2019Safety Verification and Robustness Analysis of Neural Networks via Quadratic Constraints and Semidefinite Programmingcited by 100
  10. 2020Robustness Verification for Transformerscited by 76
  11. 2020Enabling certification of verification-agnostic networks via memory-efficient semidefinite programmingcited by 65
  12. 2020The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verificationcited by 50
  13. 2019Neural Network Branching for Neural Network Verificationcited by 45
  14. 2019Optimization and Abstraction: A Synergistic Approach for Analyzing Neural Network Robustnesscited by 40
  15. 2020Lagrangian Decomposition for Neural Network Verificationcited by 35
  16. 2019Fast Neural Network Verification via Shadow Pricescited by 17

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 30; 2023: 39; 2024: 42; 2025: 48; 2026: 62.

224 papers.

Sort:

By area:

  1. 2022General Cutting Planes for Bound-Propagation-Based Neural Network Verificationcited by 102
  2. 2022Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Boundcited by 92
  3. 2024Marabou 2.0: A Versatile Formal Analyzer of Neural Networkscited by 81
  4. 2022Certified Training: Small Boxes are All You Needcited by 51
  5. 2022Rethinking Lipschitz Neural Networks and Certified Robustness: A Boolean Function Perspectivecited by 48
  6. 2021Improved deterministic l2 robustness on CIFAR-10 and CIFAR-100cited by 47
  7. 2024Neural Network Verification with Branch-and-Bound for General Nonlinearitiescited by 47
  8. 2022Efficiently Computing Local Lipschitz Constants of Neural Networks via Bound Propagationcited by 45
  9. 2022Don't Lie to Me! Robust and Efficient Explainability with Verified Perturbation Analysiscited by 38
  10. 2022DensePure: Understanding Diffusion Models towards Adversarial Robustnesscited by 33
  11. 2024Scalable Neural Network Verification with Branch-and-bound Inferred Cutting Planescited by 33
  12. 2022VeriX: Towards Verified Explainability of Deep Neural Networkscited by 30
38 more
  1. 2021Boosting the Certified Robustness of L-infinity Distance Netscited by 24
  2. 2022Open- and Closed-Loop Neural Network Verification using Polynomial Zonotopescited by 24
  3. 2023Formally Explaining Neural Networks within Reactive Systemscited by 24
  4. 2023A DPLL(T) Framework for Verifying Deep Neural Networkscited by 23
  5. 2024Local vs. Global Interpretability: A Computational Complexity Perspectivecited by 23
  6. 2023DiffSmooth: Certifiably Robust Learning via Diffusion Models and Local Smoothingcited by 20
  7. 2022PRoA: A Probabilistic Robustness Assessment against Functional Perturbationscited by 19
  8. 2023The #DNN-Verification Problem: Counting Unsafe Inputs for Deep Neural Networkscited by 19
  9. 2023Enumerating Safe Regions in Deep Neural Networks with Provable Probabilistic Guaranteescited by 19
  10. 2023Certified Robustness via Dynamic Margin Maximization and Improved Lipschitz Regularizationcited by 19
  11. 2021ScaleCert: Scalable Certified Defense against Adversarial Patches with Sparse Superficial Layerscited by 15
  12. 2022Efficient Global Robustness Certification of Neural Networks via Interleaving Twin-Network Encodingcited by 15
  13. 2022Double Bubble, Toil and Trouble: Enhancing Certified Robustness through Transitivitycited by 15
  14. 2023Logic of Differentiable Logics: Towards a Uniform Semantics of DLcited by 15
  15. 2025RvLLM: LLM Runtime Verification with Domain Knowledgecited by 15
  16. 2024NLP Verification: Towards a General Methodology for Certifying Robustnesscited by 14
  17. 2023Provable Preimage Under-Approximation for Neural Networks (Full Version)cited by 13
  18. 2024Harnessing Neuron Stability to Improve DNN Verificationcited by 13
  19. 2025Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanationscited by 13
  20. 2022Toward Robust Spiking Neural Network Against Adversarial Perturbationcited by 12
  21. 2022Certifiable 3D Object Pose Estimation: Foundations, Learning Models, and Self-Trainingcited by 12
  22. 2023POLAR-Express: Efficient and Precise Formal Reachability Analysis of Neural-Network Controlled Systemscited by 12
  23. 2024Shield Synthesis for LTL Modulo Theoriescited by 12
  24. 2024Verification of Neural Control Barrier Functions with Symbolic Derivative Bounds Propagationcited by 12
  25. 2025Neural Network Verification is a Programming Language Challengecited by 12
  26. 2023TAPS: Connecting Certified and Adversarial Trainingcited by 11
  27. 2025Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasonscited by 11
  28. 2023Robust One-Class Classification with Signed Distance Function using 1-Lipschitz Neural Networkscited by 10
  29. 2024Verification of Neural Networks' Global Robustnesscited by 10
  30. 2026Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guaranteescited by 10
  31. 2022Improved techniques for deterministic l2 robustnesscited by 9
  32. 2023Efficient Interaction-Aware Interval Analysis of Neural Network Feedback Loopscited by 9
  33. 2024Certifying Counterfactual Bias in LLMscited by 9
  34. 2025Hadamard product in deep learning: Introduction, Advances and Challengescited by 9
  35. 2025Systems Security Foundations for Agentic Computingcited by 9
  36. 2025Clip-and-Verify: Linear Constraint-Driven Domain Clipping for Accelerating Neural Network Verificationcited by 9
  37. 2022Provably Tightest Linear Approximation for Robustness Verification of Sigmoid-like Neural Networkscited by 8
  38. 2023Asymmetric Certified Robustness via Feature-Convex Neural Networkscited by 8

50 most cited of 224 All 224 (JSON)