Concept · 1 paper · updated 2026-11-12
Neural-network verification
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.
verificationcontrol
Markdown4 min read
AI-compiled overview, updated 2026-11-12, not yet reviewed by a human. Every claim cites its source; check it when a detail matters.
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 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 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 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 2109.14152 §IV-A. Card: Lyapunov-stable neural-network control.
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 2109.14152 §IV-A. The 1-norm term needs a full-column-rank matrix, otherwise the certificate says nothing along the null directions 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 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 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 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 2109.14152 tab. II |
| Medium system (2D quadrotor) | Either; the paper finds them close | Average 948.3 s against 1004.7 s 2109.14152 tab. II. The authors call the loss-curve difference inconclusive 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 2109.14152 tab. II. Only 3 runs were made 2109.14152 tab. II |
| Activations other than leaky ReLU | No card covers this | The verifier encoding is for leaky-ReLU networks 2109.14152 §III |
| Tight verification budget | Shrink the verified region | The authors kept the region small to bound MIP time 2109.14152 tab. II. Worst-case MIP time grows exponentially with the number of binaries, which grow with the ReLU units 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 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.
# 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 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 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 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 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 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 2109.14152 tab. III. Check the sizes before reusing either.
Papers
- Lyapunov-stable neural-network control: 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. 2109.14152 §I 2109.14152 §III.
Source and license
Compiled from the papers listed on this page, all published under CC BY, CC BY-SA or CC0, with citations. See each paper's page for its authors and license.