Deep neural networks are notoriously difficult to formally verify. If we want to guarantee that an autonomous vehicle won't misclassify a stop sign under slight lighting changes, or that a credit-scoring model is strictly fair, we cannot rely on empirical testing alone. We need mathematical proofs.
For years, the formal verification community found a comfortable haven in networks that exclusively use Rectified Linear Units (ReLUs). However, modern deep learning relies on a much richer vocabulary of activations: Sigmoid, Tanh, Softmax, and Swish. Extending verification guarantees to these general nonlinearities introduces a fundamental mathematical hurdle: the transition from predictable, flat surfaces to continuous, non-convex curvature.
The Piecewise Linear Comfort Zone
To understand why general nonlinearities are challenging, we must first look at why ReLU networks are uniquely cooperative. A ReLU function ($f(x) = \max(0, x)$) is piecewise linear. It operates in one of two states: either it multiplies the input by zero (inactive), or it multiplies it by one (active).
This simple structure allows verifiers to treat the network's behavior as a search over a discrete set of linear states. As pioneered by Guy Katz et al. in their work on Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks, the non-convexity of a ReLU network can be managed by iteratively splitting the problem at the activation threshold of zero. If a verifier can reason about the bounds of a neuron's input, it can determine whether the neuron is strictly active, strictly inactive, or ambiguous.
When an activation is ambiguous, frameworks like the one proposed by M. Pawan Kumar et al. in A Unified View of Piecewise Linear Neural Network Verification use a Branch-and-Bound (BaB) strategy. They split the input space into two linear sub-problems (where the ReLU is forced to be either active or inactive) and use efficient linear programming (LP) solvers to check for safety violations within those bounds.
The Curvature Crisis of Smooth Activations
When we replace ReLUs with smooth, transcendental functions like Sigmoid ($\sigma(x) = \frac{1}{1 + e^{-x}}$) or Tanh, this discrete state space vanishes. There is no single threshold point like zero where the function suddenly changes from a flat line to a slope. Instead, the function exhibits continuous curvature across its entire domain.
ReLU Activation: Sigmoid Activation:
| / | ...--''
| / | .-'
______| / ____..-'|
|/ |
------+------ ------+------
| |
This continuous curvature breaks standard verification tools in two primary ways:
- Relaxation Error Accumulation: To use efficient linear solvers, verifiers must "relax" nonlinear functions into linear upper and lower bounds (creating a bounding envelope or zonotope around the function). For a straight line, this envelope can be perfectly tight. For a curved function, any linear envelope introduces a gap—an over-approximation of what the network can actually output. As signals propagate through dozens of layers, these gaps compound exponentially, leading to loose bounds that fail to prove safety properties even when the network is perfectly safe.
- Transcendental Incompatibility: Functions like Softmax introduce exponential terms ($e^{x_i}$) that cannot be natively encoded into standard Mixed-Integer Linear Programming (MILP) or Satisfiability Modulo Theories (SMT) solvers without introducing severe computational bottlenecks.
Early attempts to resolve this, such as the linear inclusion relaxations proposed by Wang Lin et al. in Robustness Verification of Classification Deep Neural Networks via Linear Programming., demonstrated that while smooth activations could be bounded linearly, the resulting safety guarantees were often too conservative due to this rapid error accumulation.
Bridging the Gap: Arbitrary Branching and Convex Relaxations
To verify modern architectures like Vision Transformers and LSTMs, recent research has shifted toward two main paradigms: dynamic, arbitrary branching and custom non-linear convex bounds.
1. Branching at Arbitrary Points
In a ReLU network, branching always happens at zero. For a smooth function, splitting the domain at zero is rarely optimal. To solve this, Zhouxing Shi et al. introduced GenBaB in Formal Verification for Neural Networks with General Nonlinearities via Branch-and-Bound.
Instead of relying on fixed thresholds, the authors developed a framework that computes pre-optimized branching points tailored to the specific curvature of the activation function. By splitting a smooth curve into smaller, localized intervals, the linear upper and lower bounds drawn over those intervals become significantly tighter. This drastically reduces the over-approximation error and allows standard branch-and-bound heuristics to scale to general computational graphs.
2. Tighter Convex Envelopes for Transcendental Functions
For multivariate transcendental operations like the Softmax function—which is critical for verifying the attention mechanisms in Transformers—standard linear relaxations are often too loose to be useful.
Dennis Wei et al. tackled this bottleneck in Convex Bounds on the Softmax Function with Applications to Robustness Verification. Rather than forcing the Softmax function into flat linear constraints, the authors derived novel, nonlinear convex lower bounds and concave upper bounds. By capturing the mathematical essence of the exponential terms without resorting to crude linear approximations, they provided a mechanism to certify deep ensembles and attention layers with unprecedented precision.
Why General Verification Matters
Expanding verification beyond ReLUs isn't just an academic exercise in handling tougher math; it unlocks the ability to formally certify high-stakes properties across diverse domains:
- Individual Fairness: Certifying that a model treats similar individuals similarly requires tracking complex, non-linear distance metrics across the network. Elias Benussi et al. demonstrated in Individual Fairness Guarantees for Neural Networks how over-approximating these non-linearities with piecewise-linear bounds allows MILP solvers to guarantee fairness across a model's entire input domain.
- Explanation Stability: Explainable AI (XAI) algorithms often generate counterfactual explanations to justify a model's decision. However, these explanations can be highly unstable if the model is slightly retrained. By developing interval abstractions capable of handling diverse non-linear layers, Junqi Jiang et al. (Interval Abstractions for Robust Counterfactual Explanations) created a way to guarantee that user recourses remain valid over time.
- Zero-Knowledge Proofs: Verifying that a neural network was trained correctly without revealing the proprietary training data requires translating activations into cryptographic arithmetic circuits. As shown by Hao-Chen Sun et al. in zkDL: Efficient Zero-Knowledge Proofs of Deep Learning Training, avoiding polynomial approximations of activations in favor of exact arithmetic checks allows for lightning-fast, zero-knowledge verification of high-dimensional training steps.
By moving beyond the piecewise linear restriction, the field of formal verification is transforming from a specialized tool for simple ReLU networks into a generalized framework capable of providing rigorous safety, fairness, and privacy guarantees for real-world AI architectures.