mlsanityData to 7 Oct 2026

PRIMA: General and Precise Neural Network Certification via Scalable Convex Hull Approximations

arXiv 2103.03638 ↗First posted 5 Mar 2021cs.AI cs.LGcited by 77

Not on the map. Why?

Abstract (arXiv)

Formal verification of neural networks is critical for their safe adoption in real-world applications. However, designing a precise and scalable verifier which can handle different activation functions, realistic network architectures and relevant specifications remains an open and difficult challenge. In this paper, we take a major step forward in addressing this challenge and present a new verification framework, called PRIMA. PRIMA is both (i) general: it handles any non-linear activation function, and (ii) precise: it computes precise convex abstractions involving multiple neurons via novel convex hull approximation algorithms that leverage concepts from computational geometry. The algorithms have polynomial complexity, yield fewer constraints, and minimize precision loss. We evaluate the effectiveness of PRIMA on a variety of challenging tasks from prior work. Our results show that PRIMA is significantly more precise than the state-of-the-art, verifying robustness to input perturbations for up to 20%, 30%, and 34% more images than existing work on ReLU-, Sigmoid-, and Tanh-based networks, respectively. Further, PRIMA enables, for the first time, the precise verification of a realistic neural network for autonomous driving within a few minutes.

Key facts. Cited by 77 papers in the map (data through 7 Oct 2026). Builds on 30 of its 74 references that are in the map. First posted on arXiv 5 Mar 2021.

Builds on

30 of 74 references.

References · 30

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  2. 2013Intriguing properties of neural networkscited by 5,114
  3. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
  4. 2016End to End Learning for Self-Driving Carscited by 1,000
  5. 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 739
  6. 2018Certified Robustness to Adversarial Examples with Differential Privacycited by 462
  7. 2018Efficient Neural Network Robustness Certification with General Activation Functionscited by 439
  8. 2019Provably Robust Deep Learning via Adversarially Trained Smoothed Classifierscited by 328
  9. 2016Safety Verification of Deep Neural Networkscited by 262
  10. 2018Towards Fast Computation of Certified Robustness for ReLU Networkscited by 254
  11. 2017Formal Verification of Piece-Wise Linear Feed-Forward Neural Networkscited by 241
  12. 2020Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifierscited by 183
18 more
  1. 2018Semidefinite relaxations for certifying robustness to adversarial examplescited by 178
  2. 2018Efficient Formal Safety Analysis of Neural Networkscited by 165
  3. 2018Scaling provable adversarial defensescited by 141
  4. 2019Branch and Bound for Piecewise Linear Neural Network Verificationcited by 138
  5. 2019A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networkscited by 124
  6. 2018Strong mixed-integer programming formulations for trained neural networkscited by 115
  7. 2017Output Reachable Set Estimation and Verification for Multi-Layer Neural Networkscited by 79
  8. 2020Learning Certified Individually Fair Representationscited by 69
  9. 2020Enabling certification of verification-agnostic networks via memory-efficient semidefinite programmingcited by 65
  10. 2018CNN-Cert: An Efficient Framework for Certifying Robustness of Convolutional Neural Networkscited by 50
  11. 2020The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verificationcited by 50
  12. 2019Neural Network Branching for Neural Network Verificationcited by 45
  13. 2020Scaling Polyhedral Neural Network Verification on GPUscited by 43
  14. 2019Optimization and Abstraction: A Synergistic Approach for Analyzing Neural Network Robustnesscited by 40
  15. 2019Fastened CROWN: Tightened Neural Network Robustness Certificatescited by 39
  16. 2020Efficient Certification of Spatial Robustnesscited by 11
  17. 2020An efficient nonconvex reformulation of stagewise convex optimization problemscited by 7
  18. 2016Computing the Approximate Convex Hull in High Dimensionscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 16; 2023: 20; 2024: 20; 2025: 10; 2026: 10.

77 papers.

Sort:

By area:

  1. 2022Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Boundcited by 92
  2. 2024Marabou 2.0: A Versatile Formal Analyzer of Neural Networkscited by 81
  3. 2022Certified Training: Small Boxes are All You Needcited by 51
  4. 2024Neural Network Verification with Branch-and-Bound for General Nonlinearitiescited by 47
  5. 2024Scalable Neural Network Verification with Branch-and-bound Inferred Cutting Planescited by 33
  6. 2022VeriX: Towards Verified Explainability of Deep Neural Networkscited by 30
  7. 2023Understanding Certified Training with Interval Bound Propagationcited by 26
  8. 2023Formally Explaining Neural Networks within Reactive Systemscited by 24
  9. 2023Expressive Losses for Verified Robustness via Convex Combinationscited by 23
  10. 2023A DPLL(T) Framework for Verifying Deep Neural Networkscited by 23
  11. 2022Neural Network Verification with Proof Productioncited by 22
  12. 2022IBP Regularization for Verified Adversarial Robustness via Branch-and-Boundcited by 21
38 more
  1. 2022Toward Certified Robustness Against Real-World Distribution Shiftscited by 16
  2. 2023From Robustness to Explainability and Back Againcited by 14
  3. 2024Vehicle: Bridging the Embedding Gap in the Verification of Neuro-Symbolic Programscited by 14
  4. 2024NLP Verification: Towards a General Methodology for Certifying Robustnesscited by 14
  5. 2023TAPS: Connecting Certified and Adversarial Trainingcited by 11
  6. 2024Verifying message-passing neural networks via topology-based bounds tighteningcited by 10
  7. 2026Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guaranteescited by 10
  8. 2023Architecture-Preserving Provable Repair of Deep Neural Networkscited by 9
  9. 2025Clip-and-Verify: Linear Constraint-Driven Domain Clipping for Accelerating Neural Network Verificationcited by 9
  10. 2022Tighter Abstract Queries in Neural Network Verificationcited by 8
  11. 2023Expressivity of ReLU-Networks under Convex Relaxationscited by 8
  12. 2024Robustness Assessment of a Runway Object Classifier for Safe Aircraft Taxiingcited by 8
  13. 2024Formal Verification of Graph Convolutional Networks with Uncertain Node Features and Uncertain Graph Structurecited by 8
  14. 2022On Optimizing Back-Substitution Methods for Neural Network Verificationcited by 6
  15. 2023Optimization and Optimizers for Adversarial Robustnesscited by 6
  16. 2023Fully Automatic Neural Network Reduction for Formal Verificationcited by 6
  17. 2024Set-Based Training for Neural Network Verificationcited by 6
  18. 2024DeepCDCL: An CDCL-based Neural Network Verification Frameworkcited by 6
  19. 2025Out of the Shadows: Exploring a Latent Space for Neural Network Verificationcited by 6
  20. 2022(De-)Randomized Smoothing for Decision Stump Ensemblescited by 5
  21. 2022Chordal Sparsity for SDP-based Neural Network Verificationcited by 4
  22. 2022A Scalable, Interpretable, Verifiable & Differentiable Logic Gate Convolutional Neural Network Architecture From Truth Tablescited by 4
  23. 2023Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustnesscited by 4
  24. 2023Precise and Generalized Robustness Certification for Neural Networkscited by 4
  25. 2024Towards Formal Verification of Deep Neural Networks for Object Detectioncited by 4
  26. 2024Efficiently Computing Compact Formal Explanationscited by 4
  27. 2025Faster Verified Explanations for Neural Networkscited by 4
  28. 2023Reliability Assurance for Deep Neural Network Architectures Against Numerical Defectscited by 3
  29. 2023Efficient Certified Training and Robustness Verification of Neural ODEscited by 3
  30. 2023DelBugV: Delta-Debugging Neural Network Verifierscited by 3
  31. 2024Compiling High-Level Neural Network Specifications into VNN-LIB Queriescited by 3
  32. 2025PICID: Proof-Driven Clause Learning in Neural Network Verificationcited by 3
  33. 2023A Tale of Two Approximations: Tightening Over-Approximation for DNN Robustness Verification via Under-Approximationcited by 2
  34. 2023Pixel-wise Smoothing for Certified Robustness against Camera Motion Perturbationscited by 2
  35. 2024Monitizer: Automating Design and Evaluation of Neural Network Monitorscited by 2
  36. 2024Expressiveness of Multi-Neuron Convex Relaxations in Neural Network Certificationcited by 2
  37. 2025Adaptive Branch-and-Bound Tree Exploration for Neural Network Verificationcited by 2
  38. 2021Abstract Interpretation of Fixpoint Iterators with Applications to Neural Networkscited by 1

50 most cited of 77 All 77 (JSON)