Formal verification ensures that a neural network behaves safely under all possible inputs within a given domain—for instance, guaranteeing that an adversarial perturbation cannot trick an autonomous vehicle's perception system. However, verifying deep neural networks is notoriously difficult. Because networks are composed of hundreds of layers and non-linear activation functions, treating them as monolithic mathematical functions leads to an exponential explosion of states, causing verification tools to run out of memory or time.
To overcome this bottleneck, a prominent research direction focuses on modular decomposition. Instead of analyzing a network as a single black box, these techniques break the global verification problem down into smaller, independent, and locally solvable sub-problems. By leveraging optimization theory, structural branching, and compositional reasoning, modular decomposition allows formal verification to scale to complex, deep architectures.
Verification as Dual Optimization
To understand why modularity works, we must first reframe the verification problem. Proving that a network satisfies a safety property is equivalent to searching for a "worst-case" input that violates that property. This can be naturally cast as a constrained optimization problem: maximize the network's violation objective subject to the exact mathematical equations of the network's layers.
Directly solving this optimization problem is intractable due to non-linearities like ReLUs or Sigmoids. To bypass this, Dvijotham et al. and Gowal et al. proposed reframing the task using Lagrangian relaxation. Instead of strictly enforcing the complex, non-linear dependencies between layers globally, these constraints are relaxed and moved into the optimization objective using Lagrange multipliers.
The mathematical beauty of this dual approach is that it completely decouples the network. Once relaxed, the global optimization problem decomposes into a series of entirely independent sub-problems for individual layers or even individual neurons. Solving this dual optimization problem provides a provable upper bound on the network's maximum possible violation. If this upper bound shows that even the worst-case scenario cannot violate safety limits, the network is formally certified.
The Branch-and-Bound Unification
While relaxation methods provide fast upper bounds, they are inherently "incomplete"—meaning that if the bound is too loose, the verifier cannot determine whether a true violation exists or if the mathematical approximation was simply too pessimistic. To achieve exact, "complete" verification without an exhaustive global search, researchers integrate these bounds into a Branch-and-Bound (BaB) framework.
As demonstrated by Kumar et al. and Bunel et al., diverse verification techniques can be unified under a single, modular BaB architecture consisting of two alternating steps:
- Bounding: A fast, relaxed method (such as abstract interpretation or the dual approach) computes local bounds on a specific sub-problem.
- Branching: If the bounds are too ambiguous to prove or disprove the safety property, the problem is split into smaller sub-domains (for example, splitting a ambiguous ReLU neuron into its active and inactive states) to be analyzed independently.
[ Global Verification Problem ]
|
(Compute Bounds)
|
/--------------+--------------\
/ \
[Sub-problem A: ReLU < 0] [Sub-problem B: ReLU >= 0]
| |
(Prove Safety) (Prove Safety)
By modularly separating the bounding method from the branching rule, developers can systematically swap in different linear approximations and search heuristics to optimize efficiency. To extend this paradigm beyond standard piecewise-linear networks, Shi et al. formulated branching frameworks around the input nodes of a general computational graph rather than restricting them to specific activation layers. This abstraction allows BaB to natively support multi-input and multi-output non-linear operations across diverse architectures like LSTMs and Vision Transformers.
Compositional Reasoning and Subnetwork Decomposition
As networks grow to over a hundred layers, even layer-wise relaxation can hit a "memory wall." To scale further, the verification process must be broken down into larger, self-contained blocks or subnetworks.
Duong et al. addressed this by introducing assume-guarantee reasoning to neural network verification. Instead of loading an entire deep network into memory, their framework decomposes the model into sequential subnetworks. Each subnetwork is analyzed independently: it assumes certain bounds on its inputs and guarantees a set of bounds on its outputs. By iteratively passing these summarized assumptions and guarantees between segments, memory usage remains stable regardless of network depth, allowing the verification of exceptionally deep models.
This structural modularity manifests across several verification domains:
- Pruning Search Spaces: Narodytska et al. demonstrated that decomposing binarized neural networks into modular components for layer-wise analysis allows SAT solvers to aggressively prune the search space, making verification tractable for larger models.
- Property Certification: Liu et al. showed that global network properties, such as monotonicity, can be certified by decomposing the network into smaller, independently certifiable blocks, drastically reducing the computational burden of global verification.
Balancing Speed, Precision, and Trust
A core challenge in modular verification is balancing the speed of loose abstractions with the precision of exact mathematical optimization. Singh et al. showed that integrating exact mathematical optimization directly into abstract interpretation frameworks allows verifiers to achieve high precision without incurring the exponential cost of an exhaustive search.
However, as verification algorithms become more complex and rely heavily on simplified abstractions, ensuring that the verifier itself hasn't made a mistake becomes critical. To bridge the gap between scalable abstraction and absolute reliability, Elboher et al. proposed a modular proof-production framework. Their approach explicitly separates the verification process into two independent components:
[Verification Task] ---> [Part 1: Verify property on abstract, simplified network]
---> [Part 2: Formally prove soundness of the abstraction]
By decoupling the proof of the property from the proof of the abstraction's faithfulness, existing proof-producing verifiers can be seamlessly integrated with novel abstraction methods, yielding trustworthy and scalable correctness proofs.
Extensibility to Non-Standard Architectures
Because modular verification frameworks decouple the core mathematical solver from the specific network operations, they are highly extensible to non-traditional domains.
For instance, Lorenz et al. designed a modular framework where specialized geometric relaxations for 3D point cloud transformations (like rotation and shearing) interface directly with general-purpose abstract interpretation back-ends. Similarly, on the software engineering side, toolboxes like the one developed by Wei et al. leverage modular interfaces and multiple dispatch to handle diverse layer types, skip connections, and complex structures like Neural Ordinary Differential Equations.
By treating neural networks as collections of interacting, local constraints rather than monolithic functions, modular decomposition provides the mathematical flexibility required to make formal safety guarantees a practical reality for modern deep learning.
Key Foundational Work
A Dual Approach to Verify and Train Deep Networks (2019) — contributed 2 concept elements to this direction.
A Unified View of Piecewise Linear Neural Network Verification (2018) — contributed 2 concept elements to this direction.
Boosting Robustness Certification of Neural Networks (2019) — contributed 1 concept elements to this direction.