Lookahead Branching for Neural Network Verification

“Lookahead Branching for Neural Network Verification” by Liam Davis, Duo Zhou, Huan Zhang, Guy Katz, Clark W. Barrett, and Haoze Wu. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence and the 29th European Conference on Artificial Intelligence, IJCAI/ECAI 2026, Bremen, Germany, 15-21 August 2026, 2026, pp. 518-526. Bremen, Germany.

Abstract

In this work, we investigate the effect of lookahead branching strategies in neural network verification. We present a general recipe to integrate lookahead into any branch-and-bound verifier and demonstrate how one of the current state-of-the-art branching heuristics, FSB, can be viewed as a special instantiation of the lookahead branching strategy. We also describe how, in addition to improving the quality of branching decisions, lookahead can generate additional lemmas that accelerate verification. We instantiate the method in two representative branch-and-bound-based verifiers (Marabou and α-β-CROWN), and demonstrate that lookahead leads to consistent speedups in verification time and up to 57% more solved instances. Code is available at https://github.com/ai-ar-research/lookahead-branching.

BibTeX entry:

@inproceedings{DZZ+26,
   author = {Liam Davis and Duo Zhou and Huan Zhang and Guy Katz and Clark
	W. Barrett and Haoze Wu},
   title = {Lookahead Branching for Neural Network Verification},
   booktitle = {Proceedings of the Thirty-Fifth International Joint
	Conference on Artificial Intelligence and the 29th European
	Conference on Artificial Intelligence, {IJCAI/ECAI} 2026, Bremen,
	Germany, 15-21 August 2026},
   pages = {518--526},
   publisher = {ijcai.org},
   year = {2026},
   doi = {10.24963/IJCAI.2026/59},
   note = {Bremen, Germany},
   url = {https://doi.org/10.24963/ijcai.2026/59}
}

(This webpage was created with bibtex2web.)