mlsanityData to 7 Oct 2026

Solving Probabilistic Verification Problems of Neural Networks using Branch and Bound

arXiv 2405.17556 ↗First posted 27 May 2024cs.LG cs.AIcited by 4

Not on the map. Why?

Abstract (arXiv)

Probabilistic verification problems of neural networks are concerned with formally analysing the output distribution of a neural network under a probability distribution of the inputs. Examples of probabilistic verification problems include verifying the demographic parity fairness notion or quantifying the safety of a neural network. We present a new algorithm for solving probabilistic verification problems of neural networks based on an algorithm for computing and iteratively refining lower and upper bounds on probabilities over the outputs of a neural network. By applying state-of-the-art bound propagation and branch and bound techniques from non-probabilistic neural network verification, our algorithm significantly outpaces existing probabilistic verification algorithms, reducing solving times for various benchmarks from the literature from tens of minutes to tens of seconds. Furthermore, our algorithm compares favourably even to dedicated algorithms for restricted probabilistic verification problems. We complement our empirical evaluation with a theoretical analysis, proving that our algorithm is sound and, under mildly restrictive conditions, also complete when using a suitable set of heuristics.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 41 of its 63 references that are in the map. First posted on arXiv 27 May 2024.

Builds on

41 of 63 references.

References · 41

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  2. 2013Intriguing properties of neural networkscited by 5,114
  3. 2019Optuna: A Next-generation Hyperparameter Optimization Frameworkcited by 2,455
  4. 2019Natural Adversarial Examplescited by 1,401
  5. 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 739
  6. 2014Certifying and removing disparate impactcited by 715
  7. 2017Provable defenses against adversarial examples via the convex outer adversarial polytopecited by 564
  8. 2021Retiring Adult: New Datasets for Fair Machine Learningcited by 443
  9. 2018Efficient Neural Network Robustness Certification with General Activation Functionscited by 439
  10. 2018Towards Fast Computation of Certified Robustness for ReLU Networkscited by 254
  11. 2019Towards Stable and Efficient Training of Verifiably Robust Neural Networkscited by 204
  12. 2018Formal Security Analysis of Neural Networks using Symbolic Intervalscited by 185
29 more
  1. 2020Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifierscited by 183
  2. 2019Branch and Bound for Piecewise Linear Neural Network Verificationcited by 138
  3. 2020NNV: The Neural Network Verification Tool for Deep Neural Networks and Learning-Enabled Cyber-Physical Systemscited by 128
  4. 2017Fairness Testing: Testing Software for Discriminationcited by 123
  5. 2017Maximum Resilience of Artificial Neural Networkscited by 97
  6. 2018Reachability Analysis of Deep Neural Networks with Provable Guaranteescited by 93
  7. 2020Verification of Deep Convolutional Neural Networks Using ImageStarscited by 75
  8. 2020Learning Certified Individually Fair Representationscited by 69
  9. 2019Quantitative Verification of Neural Networks And its Security Applicationscited by 56
  10. 2018Probabilistic Verification of Fairness Properties via Concentrationcited by 45
  11. 2019Perfectly Parallel Fairness Certification of Neural Networkscited by 42
  12. 2020Probabilistic Safety for Bayesian Neural Networkscited by 41
  13. 2017Google's Cloud Vision API Is Not Robust To Noisecited by 37
  14. 2019Statistical Guarantees for the Robustness of Bayesian Neural Networkscited by 35
  15. 2017Towards Proving the Adversarial Robustness of Deep Neural Networkscited by 26
  16. 2019Guaranteeing Safety for Neural Network-Based Aircraft Collision Avoidance Systemscited by 26
  17. 2018Robustness Guarantees for Bayesian Inference with Gaussian Processescited by 23
  18. 2022Fairify: Fairness Verification of Neural Networkscited by 22
  19. 2023The #DNN-Verification Problem: Counting Unsafe Inputs for Deep Neural Networkscited by 19
  20. 2023Enumerating Safe Regions in Deep Neural Networks with Provable Probabilistic Guaranteescited by 19
  21. 2021Make Sure You're Unsure: A Framework for Verifying Probabilistic Specificationscited by 18
  22. 2023Provable Preimage Under-Approximation for Neural Networks (Full Version)cited by 13
  23. 2023BNN-DP: Robustness Certification of Bayesian Neural Networks via Dynamic Programmingcited by 8
  24. 2023Adversarial Robustness Certification for Bayesian Neural Networkscited by 7
  25. 2021SpecRepair: Counter-Example Guided Safety Repair of Deep Neural Networkscited by 6
  26. 2022Provable Fairness for Neural Network Models using Formal Verificationcited by 6
  27. 2024Tight Verification of Probabilistic Robustness in Bayesian Neural Networkscited by 5
  28. 2022FETA: Fairness Enforced Verifying, Training, and Predicting Algorithms for Neural Networkscited by 4
  29. 2023Scaling #DNN-Verification Tools with Efficient Bound Propagation and Parallel Computingcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 2; 2026: 1.

4 papers.

  1. 2024SAVER: A Toolbox for Sampling-Based, Probabilistic Verification of Neural Networkscited by 2
  2. 2025Efficient Preimage Approximation for Neural Network Certificationcited by 2
  3. 2025BaB-prob: Branch and Bound with Preactivation Splitting for Probabilistic Verification of Neural Networkscited by 0
  4. 2026Verified SHAP: Provable Bounds for Exact Shapley Values of Neural Networkscited by 0