Introduction
Formal verification of neural networks is essential for safety-critical applications, such as autonomous driving, where "probabilistic correctness" is insufficient. The primary challenge in verifying networks with Rectified Linear Unit (ReLU) activations is the combinatorial explosion caused by branching. Each ReLU unit introduces a non-linearity that verifiers must "split" into positive and negative cases, potentially leading to $2^n$ sub-problems for $n$ nodes.
In their IJCAI-21 paper, researchers from Imperial College London present DEEPSPLIT, a framework designed to mitigate this complexity by optimizing node selection and problem encoding.
Methodology
DEEPSPLIT introduces three core innovations to accelerate the verification process:
1. Indirect Effect Analysis
Traditional heuristics for node splitting often focus on the "direct effect"—the immediate reduction in error at a specific node. DEEPSPLIT introduces a novel scoring function that accounts for indirect effects. By splitting a node, the verifier improves its bounds, which sequentially tightens the linear relaxations for all downstream nodes. The scoring function $s = s_{dir} + s_{indir}$ prioritizes nodes that offer the greatest cumulative benefit to the entire network's mathematical approximation.
2. Hybrid Symbolic Propagation
To maintain tight bounds during analysis, DEEPSPLIT employs a hybrid approach combining Error-based Symbolic Interval Propagation (ESIP) and Reversed SIP (RSIP). This dual-tracking method yields tighter bounds than either technique used in isolation, reducing the search space for the solver.
3. Succinct LP Encoding
When checking for counterexamples, the problem is encoded for a Linear Programming (LP) solver. DEEPSPLIT utilizes a novel encoding scheme that introduces auxiliary variables to represent dependencies between constraints. This ensures the resulting optimization problem remains small and efficient to solve, preventing solver bottlenecks.
Experimental Evaluation
The authors evaluated DEEPSPLIT against state-of-the-art tools including VeriNet, Venus, nnenum, ERAN, and Marabou. Benchmarks were drawn from the VNN-COMP competition, covering:
- MNIST FC: Fully-connected networks.
- MNIST Conv: Convolutional networks.
- CIFAR10 Conv: Large-scale convolutional networks.
Key Results
DEEPSPLIT demonstrates significant performance improvements across all tested benchmarks. On fully-connected MNIST networks, the tool achieved speedups of 90x to 157x compared to the next best performing verifiers.
Furthermore, DEEPSPLIT proved more reliable, reducing timeouts by 21% to 34%. The effectiveness of the individual components was confirmed through an ablation study.
As shown in the ablation results, removing the "indirect effect" analysis causes the number of branches to explore to jump from 8,643 to 174,040, a nearly 20-fold increase in complexity. Similarly, disabling RSIP leads to a massive increase in both time and branch count, underscoring the importance of tight symbolic propagation.
Conclusion
DEEPSPLIT represents a significant advancement in neural network verification by shifting focus toward the downstream impact of node splitting. By combining indirect effect analysis with efficient LP encoding and hybrid propagation, it achieves orders-of-magnitude speedups. Future work will explore extending these heuristics to non-linear activations like Sigmoid and Tanh, as well as scaling to larger foundation models.
Summary updated