mlsanityData to 14 Oct 2026

Faster Verified Explanations for Neural Networks

arXiv 2512.00164 ↗First posted 28 Nov 2025cs.LG cs.PLcited by 4

Not on the map. Why?

Abstract (arXiv)

Verified explanations are a principled way to explain the decisions taken by neural networks, which are otherwise black-box in nature. However, these techniques face significant scalability challenges, as they require multiple calls to neural network verifiers, each of them with an exponential worst-case complexity. We present FaVeX, a novel algorithm to compute verified explanations. FaVeX accelerates the computation by dynamically combining batch and sequential processing of input features, and by reusing information from previous queries, both when proving invariances with respect to certain input features, and when searching for feature assignments altering the prediction. Furthermore, we present a novel and hierarchical definition of verified explanations, termed verifieroptimal robust explanations, that explicitly factors the incompleteness of network verifiers within the explanation. Our comprehensive experimental evaluation demonstrates the superior scalability of both FaVeX, and of verifier-optimal robust explanations, which together can produce meaningful formal explanation on networks with hundreds of thousands of non-linear activations.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 44 of its 74 references that are in the map. First posted on arXiv 28 Nov 2025.

Builds on

44 of 74 references.

References · 44

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  2. 2016Grad-CAM: Visual Explanations from Deep Networks via Gradient-based Localizationcited by 6,733
  3. 2017A Unified Approach to Interpreting Model Predictionscited by 6,555
  4. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
  5. 2016"Why Should I Trust You?": Explaining the Predictions of Any Classifiercited by 5,070
  6. 2013Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Mapscited by 2,371
  7. 2017Towards A Rigorous Science of Interpretable Machine Learningcited by 1,416
  8. 2018A Survey Of Methods For Explaining Black Box Modelscited by 973
  9. 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 744
  10. 2017Provable defenses against adversarial examples via the convex outer adversarial polytopecited by 567
  11. 2018Efficient Neural Network Robustness Certification with General Activation Functionscited by 445
  12. 2017Formal Verification of Piece-Wise Linear Feed-Forward Neural Networkscited by 242
32 more
  1. 2021Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Robustness Verificationcited by 228
  2. 2020Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifierscited by 187
  3. 2018Efficient Formal Safety Analysis of Neural Networkscited by 165
  4. 2018Abduction-Based Explanations for Machine Learning Modelscited by 160
  5. 2019Branch and Bound for Piecewise Linear Neural Network Verificationcited by 138
  6. 2018A Symbolic Approach to Explaining Bayesian Network Classifierscited by 131
  7. 2017An approach to reachability analysis for feed-forward ReLU neural networkscited by 127
  8. 2018A Dual Approach to Scalable Verification of Deep Networkscited by 125
  9. 2018Strong mixed-integer programming formulations for trained neural networkscited by 115
  10. 2022General Cutting Planes for Bound-Propagation-Based Neural Network Verificationcited by 103
  11. 2020On The Reasons Behind Decisionscited by 100
  12. 2021PRIMA: General and Precise Neural Network Certification via Scalable Convex Hull Approximationscited by 77
  13. 2021Introduction to Neural Network Verificationcited by 63
  14. 2023First Three Years of the International Verification of Neural Networks Competition (VNN-COMP)cited by 58
  15. 2021On Guaranteed Optimal Robust Explanations for NLP Modelscited by 54
  16. 2022Logic-Based Explainability in Machine Learningcited by 48
  17. 2023Robust Counterfactual Explanations for Neural Networks With Probabilistic Guaranteescited by 45
  18. 2021Improved Branch and Bound for Neural Network Verification via Lagrangian Decompositioncited by 44
  19. 2021Explanations for Monotonic Classifierscited by 39
  20. 2020Lagrangian Decomposition for Neural Network Verificationcited by 35
  21. 2021A Review of Formal Methods applied to Machine Learningcited by 33
  22. 2024Scalable Neural Network Verification with Branch-and-bound Inferred Cutting Planescited by 33
  23. 2022VeriX: Towards Verified Explainability of Deep Neural Networkscited by 30
  24. 2024Robust Counterfactual Explanations in Machine Learning: A Surveycited by 29
  25. 2019Analyzing Deep Neural Networks with Symbolic Propagation: Towards Higher Precision and Faster Verificationcited by 28
  26. 2016Interpretation of Prediction Models Using the Input Gradientcited by 24
  27. 2023Expressive Losses for Verified Robustness via Convex Combinationscited by 23
  28. 2024Distance-Restricted Explanations: Theoretical Underpinnings & Efficient Implementationcited by 21
  29. 2023Provably Robust and Plausible Counterfactual Explanations for Neural Networks via Robust Optimisationcited by 20
  30. 2023Promoting Counterfactual Robustness through Diversitycited by 17
  31. 2023Incremental Verification of Neural Networkscited by 14
  32. 2021Scaling the Convex Barrier with Sparse Dual Algorithmscited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guaranteescited by 11
  2. 2026Unifying Formal Explanations: A Complexity-Theoretic Perspectivecited by 2
  3. 2026Provably Explaining Neural Additive Modelscited by 1
  4. 2026Beyond L2: Generalizing Abductive Latent Explanations to Diverse Prototype-Based Architecturescited by 0