DEEPSPLIT: An Efficient Splitting Method for Neural Network Verification via Indirect Effect Analysis

Patrick Henriksen, Alessio Lomuscio

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.

Performance comparison of DEEPSPLIT against state-of-the-art verifiers on MNIST benchmarks.

Furthermore, DEEPSPLIT proved more reliable, reducing timeouts by 21% to 34%. The effectiveness of the individual components was confirmed through an ablation study.

Ablation study on the MNIST 256x2 benchmark, highlighting the impact of indirect effect analysis and RSIP on the number of branches explored.

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

Abstract

We propose a novel, complete algorithm for the verification and analysis of feed-forward, ReLU-based neural networks. The algorithm, based on symbolic interval propagation, introduces a new method for determining split-nodes which evaluates the indirect effect that splitting has on the relaxations of successor nodes. We combine this with a new efficient linear-programming encoding of the splitting constraints to further improve the algorithm’s performance. The resulting implementation, DeepSplit, achieved speedups of 1–2 orders of magnitude and 21-34% fewer timeouts when compared to the current SoA toolkits.
BibTeX
@inproceedings{henriksen2021deepsplit,
  author = {Patrick Henriksen and Alessio Lomuscio},
  title = {{DEEPSPLIT: An Efficient Splitting Method for Neural Network Verification via Indirect Effect Analysis}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/351},
}
Figure