A Robust Optimisation Perspective on Counterexample-Guided Repair of Neural Networks

David Boetius, Stefan Leue, Tobias Sutter

This paper provides a rigorous theoretical foundation for a popular but poorly understood technique: repairing neural networks using counterexamples. By framing the problem as a form of Robust Optimization, the authors move beyond empirical "trial and error" to prove when these algorithms are guaranteed to work and when they might loop forever.

TL;DR

The authors show that "Counterexample-Guided Repair" (CEGR) is essentially a robust optimization algorithm. They prove that while CEGR is guaranteed to terminate for simple models like linear classifiers and single neurons, it can fail for general neural networks. Yet, surprisingly, "sub-optimal" search strategies often yield the fastest results in practice.

What Problem Does This Paper Address?

As neural networks (NNs) move into safety-critical roles—like autonomous flight or medical diagnosis—we need mathematical guarantees that they won't fail. One way to achieve this is repair: if a network violates a safety specification (e.g., "never turn left when an obstacle is on the left"), we find an input that triggers the failure (a counterexample) and tweak the network to fix it.

This process is usually iterative: find a counterexample, remove it, and repeat until no more violations exist. This is known as Counterexample-Guided Repair (CEGR). The big unanswered question has been: Is this process guaranteed to end? Or could we spend eternity fixing one bug only to create another?

Methods

The authors bridge the gap between formal verification and optimization theory. Their key methodological steps include:

  1. Robust Optimization (RO) Mapping: They formally prove that CEGR is a specific type of RO algorithm. In RO, you try to minimize a cost function while ensuring constraints hold for all possible values in an uncertainty set (the input space).
  2. Scenario Optimization: They view the collection of counterexamples as a "scenario set." Each repair step adds a new constraint to a growing list, turning a hard infinite-constraint problem into a series of manageable finite-constraint problems.
Algorithm 1: Counterexample-Guided Repair
  1. Theoretical Proofs: They analyze termination by looking at the geometry of the input space. For linear models, they show that the "most violating" counterexamples always occur at the vertices (corners) of the input set. Since a polytope has a finite number of corners, the algorithm must eventually run out of new counterexamples and terminate.
  2. Quadratic Programming (QP) Repair: Leveraging their theoretical insights, they developed a new repair algorithm for linear regression models. Instead of iterative fixing, it uses a QP solver to satisfy constraints at all input vertices simultaneously.

Datasets

The authors evaluated their findings and the new QP algorithm using four distinct benchmarks:

  • MNIST: The classic handwritten digit dataset, used here to test adversarial robustness.
  • ACAS Xu: A real-world benchmark for airborne collision avoidance systems.
  • CollisionDetection (CD): A dataset simulating particle dynamics to predict collisions.
  • Integer Dataset RMIs: Recursive Model Indices used in high-performance database indexing.

Key Insights and Ideas

  • The Vertex Principle: For linear models and single ReLU neurons, the "worst" errors are always at the corners of the input box. This is the "aha moment" that allows for a termination guarantee: you can't have more unique "worst" errors than you have corners.
  • The "Early-Exit" Paradox: Theoretically, if you don't find the most violating counterexample (the "optimal" one) and instead just grab the first error you find (an "early-exit"), the algorithm might never terminate.
  • Theory vs. Reality: Despite the negative theoretical result for early-exit verifiers, the authors found they are actually superior in practice. For complex NNs like those in ACAS Xu, early-exit verifiers were consistently faster and more successful than optimal ones.
  • Falsifiers are Essential: The paper demonstrates that using "falsifiers" (fast, heuristic searchers like Projected Gradient Descent or BIM) to find easy-to-spot errors before calling a heavy-duty "verifier" can speed up the repair process by an order of magnitude.

Key Results

  • Termination Disproven: The authors proved that for general NNs with unbounded input sets, CEGR is not guaranteed to terminate.
  • New State-of-the-Art for Linear Repair: Their QP-based algorithm for repairing linear regression models achieved a 97% success rate, significantly outperforming existing specialized tools.
  • Efficiency Gains: In experiments, using "sub-optimal" early-exit verifiers and falsifiers (like BIM) resulted in much lower total runtimes, even if they occasionally required more iterations. The cost of finding the "perfect" counterexample is rarely worth the effort.
Runtime comparison of Optimal vs. Early-Exit and BIM strategies

Limitations and Future Work

The biggest remaining mystery is whether CEGR terminates for general neural networks when the input set is bounded (like a standard image pixel range). While they couldn't disprove it, they also couldn't prove it, as the "vertex principle" doesn't apply to the non-linear, non-monotone landscapes of deep networks.

Future research directions suggested include:

  • Finding tighter conditions for NN termination that reflect real-world architectures.
  • Developing a more refined taxonomy of verifiers to understand why "worse" counterexamples sometimes lead to "better" repairs.
  • Extending the robust optimization framework to handle more complex, non-linear safety properties.

Summary updated

Abstract

Counterexample-guided repair aims at creating neural networks with mathematical safety guarantees, facilitating the application of neural networks in safety-critical domains. However, whether counterexample-guided repair is guaranteed to terminate remains an open question. We approach this question by showing that counterexample-guided repair can be viewed as a robust optimisation algorithm. While termination guarantees for neural network repair itself remain beyond our reach, we prove termination for more restrained machine learning models and disprove termination in a general setting. We empirically study the practical implications of our theoretical results, demonstrating the suitability of common verifiers and falsifiers for repair despite a disadvantageous theoretical result. Additionally, we use our theoretical insights to devise a novel algorithm for repairing linear regression models based on quadratic programming, surpassing existing approaches.
BibTeX
@inproceedings{boetius2023robust,
  author = {David Boetius and Stefan Leue and Tobias Sutter},
  title = {{A Robust Optimisation Perspective on Counterexample-Guided Repair of Neural Networks}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=FaljhR7qHe},
}
Figure