To guarantee that a deep neural network is safe—for instance, ensuring that an autonomous vehicle won't misclassify a stop sign due to a few pixels of adversarial noise—we must compute the exact range of possible outputs for a given set of inputs. However, because neural networks are composed of highly non-linear activation functions like ReLUs, Sigmoids, and MaxPool layers, tracking the exact propagation of an input set through the network is an NP-hard problem.
To make verification computationally tractable, frameworks often replace these non-linearities with convex outer bounds, transforming the complex adversarial search space into a mathematically manageable convex polytope (Wong et al., 2018; Li et al., 2019). While this relaxation makes the optimization scalable, it introduces a fundamental challenge: looseness.
Intuition Behind the Relaxation Gap
Imagine trying to wrap a complex, curved sculpture tightly using only flat sheets of cardboard. The cardboard sheets represent a linear relaxation. Because the cardboard cannot bend smoothly along the sculpture's contours, it leaves empty pockets of air inside the box.
In neural network verification, these empty pockets represent unreachable states—mathematical artifacts that the network can never actually produce, but which are included in the relaxed bounds.
Actual Non-linear Function (Curve) --> ~~~~~~\______/~~~~~
Linear Relaxation (Outer Envelope) --> [-----------------]
^ ^
Unreachable States (Slack)
As signals propagate layer by layer through a deep network, these empty pockets compound exponentially (Wang Lin et al., 2019; Fatnassi et al., 2022). If the resulting outer approximation grows too large, it may overlap with an unsafe region, such as an incorrect classification label. When this happens, the verifier fails to prove safety and issues a false alarm, even if the underlying model is perfectly robust (Anderson et al., 2020; Zhang et al., 2021). This phenomenon is known as the incompleteness of convex relaxations.
The Convex Relaxation Barrier
For a long time, it was hoped that simply finding better or more optimized single-neuron linear envelopes would solve this issue. However, Salman et al., 2019 demonstrated a fundamental convex relaxation barrier: even a theoretically "perfect" layer-wise convex relaxation fails to close the gap between fast approximate verifiers and slow exact ones on standard or adversarially trained networks.
Why is this barrier so persistent? Researchers have pinpointed several mathematical ceilings:
- The Multivariate Blindspot: Most standard relaxations treat each neuron as an isolated, univariate function. However, Baader et al., 2024 proved that single-neuron relaxations are fundamentally incapable of precisely representing simple multivariate functions like $\max(x, y)$. This creates a massive bottleneck in convolutional networks that rely heavily on multivariate operations like MaxPool (Yuan et al., 2025).
- Non-Invertibility: As Mirman et al., 2022 show, propagating intervals through non-invertible functions like ReLUs inherently discards relational information between neurons, forcing the bounding box to include massive zones of unreachable states.
- The Curse of Depth: Even advanced methods like Semidefinite Programming (SDP) relaxations face limitations. Richard Y. Zhang (2020) proved that while SDP relaxations can be perfectly tight for single-layer networks, they inherently become conservative and loose as more layers are added, failing to capture the complex, irregular curvature of deep decision boundaries (Kuvshinov et al., 2022).
Breaking the Barrier: Strategies for Tightness
To overcome this conservative approximation error, researchers have developed several clever strategies to shrink the over-approximation zone:
Penalizing Slack and Optimizing Zones
Instead of accepting the loose envelope as given, James Ferlez (2021) formulated verification as a convex optimization problem that explicitly penalizes the "slack"—the $L_1$-norm distance between a neuron's linear relaxation and its true ReLU behavior. Similarly, Yuan et al., 2025 introduced methods to minimize the "over-approximation zone" by mathematically integrating the difference between the upper and lower bounding hyperplanes.
Context-Aware and Multivariate Relaxations
To shatter the single-neuron barrier, Tjandraatmadja et al., 2020 looked at the multivariate affine function preceding the ReLU activation rather than treating the ReLU in isolation. By accounting for the interactions between a neuron and its multiple inputs, they derived the tightest possible convex relaxation for a single neuron.
Geometric Partitioning
If a single box over an entire input space is too loose, the space can be broken down into smaller, more manageable pieces. Anderson et al., 2020 demonstrated that intelligently partitioning the input uncertainty set along optimally chosen hyperplanes drastically reduces relaxation error while maintaining polynomial-time efficiency.
Hybrid and Dual Propagation
Rather than relying on a single relaxation type, modern frameworks combine methods to exploit their complementary strengths. For example, Chiu et al., 2025 combined the scalability of linear bound propagation with the tightness of SDP, avoiding the massive error introduced when bounding an $\ell_2$ ball inside an $\ell_\infty$ hypercube. Meanwhile, Yunruo Zhang (2025) proposed propagating two distinct sets of linear relaxations simultaneously, using their intersection to dynamically tighten neuron bounds.
Key Foundational Work
Robustness Verification of Classification Deep Neural Networks via Linear Programming. (2019) — contributed 2 concept elements to this direction.
A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks (2019) — contributed 2 concept elements to this direction.
POPQORN: Quantifying Robustness of Recurrent Neural Networks (2019) — contributed 1 concept elements to this direction.