“Efficiently Computing Compact Formal Explanations” by Min Wu, Xiaofu Li, Haoze Wu, and Clark W. Barrett. In Fortieth AAAI Conference on Artificial Intelligence, Thirty-Eighth Conference on Innovative Applications of Artificial Intelligence, Sixteenth Symposium on Educational Advances in Artificial Intelligence, AAAI 2026, Singapore, January 20-27, 2026, (Sven Koenig, Chad Jenkins, and Matthew E. Taylor, eds.), Jan. 2026, pp. 35857-35866.
Building on VeriX (Verified eXplainability), a system for producing optimal verified explanations for machine learning models, we present VeriX+, which significantly improves both the size and the generation time of formal explanations. We introduce a bound propagation-based sensitivity technique to improve the size, and a binary search-based traversal with confidence ranking for improving time — the two techniques are orthogonal and can be used independently or together. We also show how to adapt the QuickXplain algorithm to our setting to provide a trade-off between size and time. Experimental evaluations on standard benchmarks demonstrate significant improvements on both metrics, e.g., a size reduction of 38% on the GTSRB dataset and a time reduction of 90% on MNIST. We demonstrate that our approach is scalable to transformers and real-world scenarios such as autonomous aircraft taxiing and sentiment analysis. We conclude by showcasing several novel applications of formal explanations.
BibTeX entry:
@inproceedings{WLW+26,
author = {Min Wu and Xiaofu Li and Haoze Wu and Clark W. Barrett},
editor = {Sven Koenig and Chad Jenkins and Matthew E. Taylor},
title = {Efficiently Computing Compact Formal Explanations},
booktitle = {Fortieth {AAAI} Conference on Artificial Intelligence,
Thirty-Eighth Conference on Innovative Applications of Artificial
Intelligence, Sixteenth Symposium on Educational Advances in
Artificial Intelligence, {AAAI} 2026, Singapore, January 20-27,
2026},
pages = {35857--35866},
publisher = {{AAAI} Press},
month = jan,
year = {2026},
doi = {10.1609/AAAI.V40I42.40900},
url = {https://doi.org/10.1609/aaai.v40i42.40900}
}
(This webpage was created with bibtex2web.)