On the Trade-off Between Efficiency and Precision of Neural Abstraction

Alec Edwards, Mirco Giacobbe, Alessandro Abate

Abstract

Neural abstractions have been recently introduced as formal approximations of complex, nonlinear dynamical models. They comprise a neural ODE and a certified upper bound on the error between the abstract neural network and the concrete dynamical model. So far neural abstractions have exclusively been obtained as neural networks consisting entirely of $ReLU$ activation functions, resulting in neural ODE models that have piecewise affine dynamics, and which can be equivalently interpreted as linear hybrid automata. In this work, we observe that the utility of an abstraction depends on its use: some scenarios might require coarse abstractions that are easier to analyse, whereas others might require more complex, refined abstractions. We therefore consider neural abstractions of alternative shapes, namely either piecewise constant or nonlinear non-polynomial (specifically, obtained via sigmoidal activations). We employ formal inductive synthesis procedures to generate neural abstractions that result in dynamical models with these semantics. Empirically, we demonstrate the trade-off that these different neural abstraction templates have vis-a-vis their precision and synthesis time, as well as the time required for their safety verification (done via reachability computation). We improve existing synthesis techniques to enable abstraction of higher-dimensional models, and additionally discuss the abstraction of complex neural ODEs to improve the efficiency of reachability analysis for these models.

Introduction

In safety-critical domains such as autonomous driving or medical device design, formal verification is essential to ensure a system never enters a hazardous state. This typically involves analyzing the system's underlying Ordinary Differential Equations (ODEs). However, real-world systems often exhibit highly nonlinear or non-Lipschitz behavior—characterized by sharp, sudden changes—which can cause standard verification tools like Flow* to fail.

"Neural Abstraction" addresses this challenge by training a neural network to approximate a complex system, coupled with a formally certified error bound. If the simplified neural model is proven safe within this error margin, the original system is guaranteed to be safe. While previous work focused on ReLU-based (piecewise affine) models, this research explores whether alternative neural network "shapes" can optimize the trade-off between verification efficiency and approximation precision.

Methodology: Abstraction Templates

The authors propose a framework for synthesizing three distinct types of neural abstraction templates, each offering a different balance of complexity and analyzability.

Comparison of neural abstraction templates across different activation functions, training procedures, and verification tools.
  1. Piecewise Constant (PWC): Utilizing Heaviside (step) functions, these models result in Linear Hybrid Automata with constant flows. They are extremely fast to verify using tools like PHAVer but are the least precise.
  2. Piecewise Affine (PWA): The standard approach using ReLU activations. These models are more complex and precise than PWC, verified via SpaceEx.
  3. Nonlinear/Sigmoidal (Sig.): Using Sigmoid activations, these models regularize dynamics into smooth functions. This allows tools like Flow* to analyze systems that were previously mathematically incompatible due to non-Lipschitz properties.

To generate these abstractions, the researchers employ Counterexample-Guided Inductive Synthesis (CEGIS). This iterative process involves training a model, using an SMT solver (like Z3 or dReal) to find error bound violations, and refining the training set. Notably, because PWC models lack gradients, the authors utilized Particle Swarm Optimization (PSO) for their synthesis.

Experimental Evaluation

The framework was tested on several benchmarks designed to stress-test verification tools:

  • Non-Lipschitz Models: 1D and 2D systems (e.g., Water Tank, NL1, NL2) containing square or cube root terms that typically break verification tools.
  • High-Dimensional Scaling: 4D and 6D variants of the Water Tank model to evaluate scalability.
  • Neural ODE (NODE1): A pre-trained complex neural network abstracted into a simpler form to accelerate its own reachability analysis.

Key Results

The experiments confirmed a clear Efficiency-Precision Spectrum. In the Water Tank benchmark, PWC models verified in a mere 0.01 seconds (with a 0.22 error bound), whereas Sigmoidal models took 4.40 seconds but achieved a much tighter error of 0.07.

Furthermore, the method successfully scaled to a 6D Water Tank model using PWA templates. In the meta-use case of abstracting an existing Neural ODE (NODE1), the sigmoidal abstraction reduced verification time from 205 seconds to 126 seconds, demonstrating significant efficiency gains for a minimal loss in precision.

Discussion and Insights

A major contribution of this work is the ability to verify the unverifiable. By abstracting non-Lipschitz systems into sigmoidal neural ODEs, researchers can apply standard reachability tools to systems that were previously inaccessible. Additionally, the introduction of local refinement—calculating error bounds per region of the state space rather than globally—markedly improved the success rates of verification tools, particularly for PWA models.

However, limitations remain. The synthesis of PWC models via PSO is computationally expensive and struggles to find low-error solutions in higher dimensions compared to gradient-based methods.

Conclusion

This research demonstrates that there is no "one size fits all" for neural abstractions. The choice between piecewise constant, piecewise affine, or sigmoidal templates allows practitioners to tune their models based on whether they prioritize rapid verification or high-fidelity approximation. Future work will focus on improving PWC synthesis scalability and developing specialized tools to handle the non-determinism inherent in neural abstraction error bounds.

Summary updated

Abstract

Neural abstractions have been recently introduced as formal approximations of complex, nonlinear dynamical models. They comprise a neural ODE and a certified upper bound on the error between the abstract neural network and the concrete dynamical model. So far neural abstractions have exclusively been obtained as neural networks consisting entirely of $ReLU$ activation functions, resulting in neural ODE models that have piecewise affine dynamics, and which can be equivalently interpreted as linear hybrid automata. In this work, we observe that the utility of an abstraction depends on its use: some scenarios might require coarse abstractions that are easier to analyse, whereas others might require more complex, refined abstractions. We therefore consider neural abstractions of alternative shapes, namely either piecewise constant or nonlinear non-polynomial (specifically, obtained via sigmoidal activations). We employ formal inductive synthesis procedures to generate neural abstractions that result in dynamical models with these semantics. Empirically, we demonstrate the trade-off that these different neural abstraction templates have vis-a-vis their precision and synthesis time, as well as the time required for their safety verification (done via reachability computation). We improve existing synthesis techniques to enable abstraction of higher-dimensional models, and additionally discuss the abstraction of complex neural ODEs to improve the efficiency of reachability analysis for these models.
BibTeX
@inproceedings{edwards2023trade,
  author = {Alec Edwards and Mirco Giacobbe and Alessandro Abate},
  title = {{On the Trade-off Between Efficiency and Precision of Neural Abstraction}},
  booktitle = {QEST},
  year = {2023},
  doi = {10.1007/978-3-031-43835-6\_12},
}
Figure