TLDR: This research introduces Hybrid MILP, a novel deep neural network (DNN) verification method that significantly improves accuracy and efficiency for complex instances. It combines an initial quick check with α, β-CROWN and then uses a partial Mixed Integer Linear Programming (MILP) approach. The key innovation is Solution-Aware Scoring (SAS), which intelligently selects crucial ReLU activation functions to model precisely, drastically reducing the number of binary variables needed. This allows Hybrid MILP to reduce undecided verification cases by up to 40% and scale to large DNNs, outperforming existing state-of-the-art verifiers on challenging benchmarks.
Deep neural networks (DNNs) have become incredibly powerful, excelling in tasks from image recognition to natural language processing. However, their widespread use in critical applications, such as autonomous driving or medical diagnosis, demands a high level of trustworthiness. A key aspect of this trustworthiness is formal verification, which ensures that a DNN behaves as expected, even when faced with slight variations or ‘perturbations’ in its input. For instance, if a self-driving car’s vision system identifies a stop sign, verification ensures it will always identify it as a stop sign, even if the image is slightly blurry or has minor noise.
The Challenge of DNN Verification
One of the most efficient techniques for DNN verification is Branch and Bound (BaB). This method works by systematically exploring different possibilities to determine the range of values a neuron can take. While effective for many DNNs, BaB faces a significant hurdle: the number of possibilities it needs to explore can grow exponentially, especially for complex networks or when verifying non-local properties (like overall robustness, not just local changes). In such ‘complex instances,’ simply giving BaB more time doesn’t help much, as its progress is linear with time, while the problem complexity is exponential.
Existing alternative methods, such as those based on Mixed Integer Linear Programming (MILP) or LP relaxation, also struggle with these complex cases, often timing out or providing insufficient accuracy.
A New Approach: Partial MILP and Solution-Aware Scoring
To overcome these limitations, researchers have revisited a ‘divide-and-conquer’ strategy. Instead of making a few large, complex BaB calls, this approach relies on many smaller, ‘partial MILP’ calls. The core idea is to precisely model only a select few, but very important, ReLU (Rectified Linear Unit) activation functions using costly binary variables, while approximating others with simpler linear variables. The critical question then becomes: how do you choose these ‘very important’ ReLUs?
Previous attempts at selecting these ReLUs were suboptimal. This new research introduces a novel method called Solution-Aware Scoring (SAS). Unlike older ‘global scoring’ (GS) functions, which try to estimate the importance of a ReLU without knowing the specific context, SAS uses the solution from a single, fast LP (Linear Programming) call. This allows SAS to understand the ‘mode’ or behavior of the ReLU in the current context, leading to a much more accurate assessment of its importance. Theoretically, SAS is guaranteed to be an ‘over-approximation’ of the actual improvement, meaning if SAS says a ReLU is unimportant, it truly is. Experimentally, SAS proved to be significantly more efficient, requiring about 6 times fewer binary variables than previous methods and about 2 times fewer than global scoring functions to achieve the same level of accuracy.
Also Read:
- Robust AI Control: Verifying Neural Networks for Real-World Safety
- New Activation Function Boosts AI Model Robustness and Generalization
Hybrid MILP: Combining Strengths for Robust Verification
Building on the efficiency of SAS, the researchers developed a new verifier called Hybrid MILP. This system operates in two stages: First, it uses α, β-CROWN, a leading verification tool, with a short time-out to quickly handle easier verification instances. For any instances that α, β-CROWN cannot definitively verify or falsify within that time, Hybrid MILP then employs the partial MILP approach, leveraging the precise ReLU selection enabled by SAS.
The experimental results for Hybrid MILP are compelling. Compared to α, β-CROWN with a much longer time-out (2000 seconds), Hybrid MILP significantly reduced the number of ‘undecided’ instances—from 20-58% down to a low 8-15%. This was achieved while maintaining a reasonable average runtime of 46 to 417 seconds per instance. Crucially, Hybrid MILP demonstrated its ability to scale to fairly large convolutional neural networks (CNNs) with over 2 million parameters, a feat that many other verifiers struggle with.
The paper, titled “Solution-aware vs global ReLU selection: partial MILP strikes back for DNN verification”, highlights that for complex verification tasks, there is currently no alternative that matches the efficiency and accuracy of this partial MILP approach. This breakthrough opens new avenues for verifying more complex properties of DNNs, such as global robustness, which are essential for their safe and reliable deployment in real-world applications.
