---
kind: concept
slug: neural-network-verification
title: Neural-network verification
summary: >-
  Checking a property of a neural network over a whole region rather than on sampled inputs. The main route here encodes the ReLU-type network as a mixed-integer program, which either certifies the property on a box or returns a worst-case counterexample. The counterexample can then drive training.
tags: [verification, control]
papers: ["2109.14152"]
related: [lyapunov-function, branch-and-bound, control-barrier-function]
status: draft
updated_at: 2026-11-12
---

## Overview

Testing a neural network on samples says little about the states it has not
seen. Verification asks whether a property holds for every input in a set. For
a neural controller, the property that matters is often stability, and the
authors note that such controllers usually come without a guarantee of it
[arxiv:2109.14152 §I]. The shared core of the approaches is the same. Encode the
network and the property as constraints, then search for an input that breaks
the property. If the search finds no violation, the property is certified on
that set. If it finds one, the counterexample is the useful output, because it
can be fed back to change the network [arxiv:2109.14152 §IV-A].

The invariant every variant relies on is that the certificate covers the whole
set and not only the sampled points, so the set must be stated explicitly.

## Variants

### Exact MIP verification of a Lyapunov condition

The verifier takes a network dynamics model, a controller network and a
candidate Lyapunov function, and maximises how far each Lyapunov condition is
violated over a bounded polytope. Each leaky-ReLU unit is encoded with big-M
constraints and one binary variable [arxiv:2109.14152 §III]. If both maxima are
zero and are attained at the target state, the condition is certified on the
box. Otherwise the worst violation is returned as a counterexample [arxiv:2109.14152 §IV-A].
Card: [Lyapunov-stable neural-network control](/papers/2109.14152).

Two details matter when porting this. The strict positivity condition is
replaced by a non-strict one with a margin, and the Lyapunov function carries a
1-norm term so that it is positive near the target. The paper argues that the
margin version is also necessary, not only sufficient [arxiv:2109.14152 §IV-A].
The 1-norm term needs a full-column-rank matrix, otherwise the certificate says
nothing along the null directions [arxiv:2109.14152 §IV-A].

### Counterexample-guided training (approach 1)

The verifier runs, every counterexample it finds is added to a growing pool of
sample states, and the networks are trained by gradient descent on a one-sided
loss over those pools. The loop repeats until the loss is zero or an epoch
budget is spent [arxiv:2109.14152 §IV-B]. The loss is evaluated on the stored
states, so the gradient does not pass through the verifier.

### Min-max through the verifier (approach 2)

The training objective is the sum of the two verifier optima, and the gradient
is taken through the MIP. The binaries and the active constraints are held fixed
at the solution, and the optimum then has a closed form that back-propagation
can differentiate [arxiv:2109.14152 §IV-B]. The gradient is defined only where
a small parameter change leaves the active set and the binaries unchanged. The
paper does not say what the training loop does at other points
[arxiv:2109.14152 §IV-B].

## When to use which

The paper gives a single comparison, on three systems with the same solver. Use
it as evidence for the regimes it covers and nothing wider.

| Situation | Use | Why |
|---|---|---|
| Smallest system (inverted pendulum) | Approach 1 | Average 8.4 s against 224 s for approach 2 [arxiv:2109.14152 tab. II] |
| Medium system (2D quadrotor) | Either; the paper finds them close | Average 948.3 s against 1004.7 s [arxiv:2109.14152 tab. II]. The authors call the loss-curve difference inconclusive [arxiv:2109.14152 §V-C] |
| Larger network (3D quadrotor) | Approach 2 | Approach 1 timed out after 5 days on average; approach 2 averaged 65.7 h [arxiv:2109.14152 tab. II]. Only 3 runs were made [arxiv:2109.14152 tab. II] |
| Activations other than leaky ReLU | No card covers this | The verifier encoding is for leaky-ReLU networks [arxiv:2109.14152 §III] |
| Tight verification budget | Shrink the verified region | The authors kept the region small to bound MIP time [arxiv:2109.14152 tab. II]. Worst-case MIP time grows exponentially with the number of binaries, which grow with the ReLU units [arxiv:2109.14152 §VI] |
| Need the basin of attraction, not the box | Take the largest sublevel set inside the box | The verified box is not invariant. The resulting set can be small, and joint search over the function and the level is left as future work [arxiv:2109.14152 §IV-C] |

## Implementation sketch

The common core is a verify-then-train loop. The sketch below is ours and
follows the paper's structure. It is not code from the authors' repository.

```pseudocode
# Verify the candidate over the box B. Each check is a MIP over the
# ReLU encoding. A maximum of zero means no violation was found [arxiv:2109.14152 §IV-A].
def verify(controller, lyap, box):
    counterexamples = []
    for condition in [positivity, decrease]:
        best, state = solve_mip(condition, controller, lyap, box)
        if best > 0 and state != TARGET:
            counterexamples.append(state)
    return counterexamples  # empty means certified on the box


# Counterexample-guided loop, approach 1 [arxiv:2109.14152 §IV-B]
pool = []
while True:
    found = verify(controller, lyap, box)
    if not found:
        return controller, lyap  # certified on the box
    pool.extend(found)  # keep the worst-case states
    # Gradient steps on the one-sided loss over the pool,
    # until the loss is zero or the epoch budget is spent
    controller, lyap = descend(controller, lyap, pool, budget)
```

Approach 2 replaces the last step with a gradient taken through the MIP optima
[arxiv:2109.14152 §IV-B]. In both cases the certificate is only as strong as the
solver's tolerance. The paper accepts optima below a small threshold as zero
[arxiv:2109.14152 app. E].

## Caveats

- **The guarantee holds for the learned model.** The paper certifies the learned
  dynamics. It reports that the Lyapunov function can increase along trajectories
  of the true system. Re-verify on the true dynamics before deploying
  [arxiv:2109.14152 app. D].
- **The verified box is not the basin.** A certificate on a box does not give a
  region of attraction. Take the sublevel set inside the box and check its size
  [arxiv:2109.14152 §IV-C].
- **Solver tolerances are part of the result.** The paper does not give solver
  tolerances, and the Gurobi version is not stated [arxiv:2109.14152 §V].

## Contradictions

None between papers, since this page has a single source. Within that source,
the network sizes in the paper's Table III differ from those in the authors'
demo scripts for several systems. The card records the differences
[arxiv:2109.14152 tab. III]. Check the sizes before reusing either.

## Papers

- [Lyapunov-stable neural-network control](/papers/2109.14152): trains a neural
  controller and a neural Lyapunov function together. An exact MIP verifier
  certifies the conditions on a box or returns counterexamples for retraining.

Named but not compiled, so nothing from them is used here: Chang et al. (neural
Lyapunov functions with tanh activations), Abate et al. (quadratic activations),
and the MIP verification of ReLU networks by Tjeng et al. and by Dai et al.
[arxiv:2109.14152 §I] [arxiv:2109.14152 §III].
