Exact Verification of Neural Networks via Linear Programming

21 concepts21 papers1 proposal

Deep neural networks are often perceived as highly complex, non-linear black boxes. However, for architectures that rely on rectified linear units (ReLU) or max-pooling activations, this complexity possesses a highly structured geometric form. A ReLU network does not produce a smoothly curving decision surface; instead, it forms a piecewise linear function.

The input space is partitioned into a collection of convex polyhedral regions, often called activation regions. Within any single region, every neuron's activation state (whether it is active or inactive) is fixed. Consequently, inside that specific region, the entire network behaves exactly like a simple affine transformation ($y = Wx + b$).

This geometric insight is the foundation of exact verification. As Xin Zhang et al. demonstrate in Interpreting Neural Network Judgments via Minimal, Stable, and Symbolic Corrections, this piecewise linear nature allows us to mathematically prove that any input within a defined symbolic range will yield a desired outcome. If we can reason about these linear regions systematically, we can transform the intractable problem of verifying a non-linear model into a series of linear optimization tasks.

Encoding Non-Linearities as Mixed-Integer Constraints

To evaluate a network globally across multiple regions, we must mathematically encode the "switching" behavior of the activations. For a ReLU activation $y = \max(0, x)$, the relationship is non-linear. However, we can introduce a binary indicator variable $z \in \{0, 1\}$ to represent the state of the neuron: $z=1$ if the neuron is active ($x \ge 0$), and $z=0$ if it is inactive ($x < 0$).

Using a technique known as the "big-M" formulation, we can express the ReLU behavior using a set of linear inequalities:

$$y \ge x$$ $$y \ge 0$$ $$y \le x + M(1-z)$$ $$y \le Mz$$

where $M$ is a sufficiently large positive constant representing the upper bound of the neuron's input.

By applying this transformation to every non-linear node, the entire neural network can be represented as a Mixed-Integer Linear Program (MILP). As Vincent Tjeng et al. show in Evaluating Robustness of Neural Networks with Mixed Integer Programming, formulating verification as an MILP allows off-the-shelf optimization solvers to perform exact, complete verification. The solver searches for a global optimum within a defined perturbation space, either finding a concrete counterexample or providing a mathematical guarantee that no violation exists. This approach has been successfully applied to verify critical properties like local stability in industrial applications, such as aircraft predictive maintenance explored by Mélanie Ducoffe et al. in Surrogate Neural Networks Local Stability for Aircraft Predictive Maintenance.

The Geometry of Regions and Boundaries

Why does this formulation work so effectively? It reduces continuous verification over an infinite number of points to a discrete search over linear boundaries.

Inside a single activation region, the network is linear. Therefore, the extreme behaviors (such as the maximum or minimum output value) must occur at the boundaries or vertices of that polyhedral region. As Matthew Sotoudeh demonstrates in Provable Repair of Deep Neural Networks, verifying safety properties over an infinite set of inputs within a defined polytope can be reduced to checking a finite number of vertices at the boundaries of these linear regions.

Instead of treating the network as a global optimization problem, some approaches exploit this geometry directly by traversing adjacent polyhedra. For instance, Aymeric Fromherz et al. introduce an algorithm in Fast Geometric Projections for Local Robustness Certification that treats verification as a geometric search. By systematically moving across adjacent polyhedral regions, it calculates the exact minimum distance to a decision boundary without relying on heavy global optimization machinery. When analyzing safety boundaries, Hongchao Zhang et al. show in Exact Verification of ReLU Neural Control Barrier Functions that one can identify every linear segment intersecting a safety boundary and evaluate the safety conditions on those segments individually, even at the non-differentiable "seams" where the regions meet.

Managing Complexity via Relaxations and Decompositions

While exact verification is powerful, searching through every possible combination of binary activation states is computationally expensive. In fact, Marco Sälzer et al. prove in Reachability In Simple Neural Networks that non-deterministically selecting the active linear segment for each node reduces the problem to a standard linear program solvable in polynomial time, but the underlying global problem remains inherently difficult. When extended to finite-precision environments like quantized Graph Neural Networks, the authors show in Verifying Quantized Graph Neural Networks is PSPACE-complete that the complexity can rise to PSPACE-complete.

To scale to larger networks, researchers use linear relaxations. Instead of forcing a neuron to be strictly active ($z=1$) or inactive ($z=0$), we can bound the non-linear activation function within a convex linear envelope (an upper and lower linear bound). This converts the MILP into a standard Linear Program (LP).

As Wang Lin et al. demonstrate in Robustness Verification of Classification Deep Neural Networks via Linear Programming., transforming non-linear activations into linear inclusion relaxations allows standard LP solvers to provide formal guarantees: if the relaxed linear superset is proven robust, the original model is guaranteed to be safe. Similarly, Yi Zeng et al. utilize a two-stage framework in Towards Robustness Certification Against Universal Perturbations, combining linear relaxations to bound non-linearities before passing them to an MILP solver to search for shared dataset-wide perturbations.

Another scaling strategy involves decomposing the problem into discrete logic and continuous optimization. In Efficient Counterexample-Guided Fairness Verification and Repair of Neural Networks Using Satisfiability Modulo Convex Programming, Arya Fayyazi et al. isolate activation regions from numerical bounds by coordinating a SAT solver (for discrete logical constraints) with a convex solver (for continuous optimizations), enabling efficient detection of individual fairness violations.

Broad Applications of Linear Verification

The ability to exactly or relaxedly bound a neural network's output using linear programming has unlocked verification capabilities far beyond simple adversarial robustness:

Key Foundational Work

Evaluating Robustness of Neural Networks with Mixed Integer Programming (2019) — contributed 1 concept elements to this direction.
Output Range Analysis for Deep Feedforward Neural Networks (2018) — contributed 1 concept elements to this direction.
Interpreting Neural Network Judgments via Minimal, Stable, and Symbolic Corrections (2018) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_mixed_integer_linear_programming_verific_1961d49f,
  title = {mixed-integer linear programming verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/mixed-integer-linear-programming-verification/rdr_1961d49f12884edd89a43a32b49cf22c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_mixed_integer_linear_programming_verific_1961d49f_v1,
  title = {mixed-integer linear programming verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/mixed-integer-linear-programming-verification/rdr_1961d49f12884edd89a43a32b49cf22c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake