Proof Sharing Limits for Neural Network Robustness Verification

Robustness verification of neural networks is crucial for their deployment in safety-critical applications. One technique to accelerate incomplete verification is "proof sharing," which reuses intermediate-layer abstract states, or templates, across different queries. However, the consistent effectiveness of this template-based acceleration across diverse network architectures, properties, datasets, and training methods has been unclear. This research conducts a comprehensive study to explore the boundaries of template-based acceleration. The findings reveal significant variability in template subsumption rates across different scenarios. To explain this variation, the authors introduce a new metric called "jointly stable neurons," demonstrating that in certain cases, template-based methods are unlikely to provide any speedup. To address these limitations, the paper introduces FastCert, a novel technique designed to automatically distribute templates across neural network layers. Crucially, FastCert can also decide to forgo templates entirely if they are not expected to yield performance benefits. Across a wide range of L0-verification tasks, FastCert achieved an average speedup of 1.13x compared to existing template-based reuse techniques, indicating a more intelligent and adaptive approach to leveraging proof sharing.