Formal verification aims to provide absolute mathematical guarantees about the safety and correctness of critical systems, such as neural networks, autonomous controllers, and hybrid systems. To prove these properties, verification tools must solve massive systems of numerical constraints.
Here lies a fundamental paradox: the fastest tools for solving these constraints—such as Linear Programming (LP), Mixed-Integer Linear Programming (MILP), and Semidefinite Programming (SDP) solvers—rely on hardware-accelerated floating-point arithmetic. However, floating-point arithmetic is inherently inexact due to rounding errors.
As Clark Barrett et al. observed in Leveraging Linear and Mixed Integer Programming for SMT, this reliance introduces a numerical soundness gap. A high-performance solver might suffer from accumulated roundoff errors that lead to mathematically incorrect results—falsely declaring an unsafe system safe, or failing to converge entirely. Conversely, relying purely on exact symbolic mathematics is often too computationally expensive for large-scale industrial models, as noted by Alessandro Abate and Dario Cattaruzza in Unbounded-Time Safety Verification of Guarded LTI Models with Inputs by Abstract Acceleration.
To resolve this tension, researchers have developed techniques that allow verifiers to leverage the speed of floating-point computation without sacrificing absolute mathematical certainty.
The Root of Unsoundness: Cascading Roundoff Errors
To understand why the soundness gap occurs, consider a verification tool trying to prove that a deep neural network never outputs an unsafe command. Many verifiers use a branch-and-bound algorithm to partition the input space, relying on an LP solver to compute bounds on neuron activations at each step.
If a tiny rounding error occurs near a sharp decision boundary, the solver might misclassify a region of the state space. In Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks, Guy Katz et al. encountered this exact tension, noting that specialized restoration techniques are required to ensure that efficiency gains do not undermine proof validity.
A meta-analysis of the International Verification of Neural Networks Competition by Christopher Brix et al. in First three years of the international verification of neural networks competition (VNN-COMP) highlighted that accounting for these precision errors without incurring prohibitive performance penalties remains a major open challenge across the field. When numerical errors go unmanaged, they can cause non-monotonic behavior where strengthening constraints fails to improve verification outcomes.
To bridge this gap, modern research focuses on three primary mechanisms: sound bound propagation, exact post-processing certificates, and delta-complete relaxations.
Mechanism 1: Sound Bound Propagation via Interval Arithmetic
Instead of computing exact points using standard floating-point operations, we can replace individual numbers with intervals that are guaranteed to enclose the true real-number result.
The foundational intuition traces back to constraint satisfaction. In Consistency Techniques for Numeric CSPs, Olivier Lhomme formalized interval propagation techniques like arc B-consistency. By tracking the upper and lower bounds of variable domains rather than individual values, a solver ensures that floating-point rounding errors never accidentally prune a valid solution.
To make this work efficiently, the solver dynamically alters the processor's hardware rounding modes:
- When calculating a lower bound, the processor is instructed to round down (towards $-\infty$).
- When calculating an upper bound, the processor rounds up (towards $+\infty$).
This creates an outward-rounded interval. Even if the exact real-value calculation drifts due to precision limits, it is mathematically guaranteed to remain inside the computed interval. Christoph Müller et al. scaled this intuition to massive parallel architectures in Scaling Polyhedral Neural Network Verification on GPUs, demonstrating that careful management of rounding modes and operation order allows sound polyhedral verification to run directly on highly parallel, floating-point-heavy GPUs.
Mechanism 2: Fast Approximation Followed by Exact Certification
A second strategy decouples the search for a proof from the validation of that proof. Finding a mathematical certificate (like a loop invariant or a safety envelope) within a massive search space is computationally brutal. However, verifying whether a specific candidate certificate is correct is much easier.
We can therefore use a fast, inexact floating-point solver to find a candidate certificate, and then use a rigorous symbolic tool to verify or "harden" it.
┌──────────────────────────────────────┐
│ Fast Floating-Point Solver (Inexact)│ ──> Generates Candidate Certificate
└──────────────────────────────────────┘
│
▼
┌──────────────────────────────────────┐
│ Exact Symbolic Verification (Sound) │ <── Validates or Adjusts Bounds
└──────────────────────────────────────┘
│
▼
Strict Mathematical Proof
For example, in polynomial optimization, proving that a multivariate polynomial is always non-negative can be achieved by finding a Sum-of-Squares (SOS) decomposition. In RealCertify: a Maple package for certifying non-negativity, Victor Magron et al. utilized fast, floating-point semidefinite programming to find approximate SOS certificates. They then applied exact symbolic rounding techniques to map these approximations back into rigorous, rational-coefficient proofs.
This same learner-verifier pipeline protects probabilistic verification against numerical noise. In Fixed Point Certificates for Reachability and Expected Rewards in MDPs, Maximilian Schäffeler et al. demonstrated that numerical imprecision in Markov Decision Process solvers can be neutralized. By applying smoothing techniques and safe rounding to mathematical operators, they generate lightweight fixed-point certificates that satisfy the required safety inequalities despite the underlying floating-point noise.
Mechanism 3: Delta-Completeness and Tolerance Thresholds
When an absolute, bit-perfect proof is mathematically unachievable or computationally intractable, we can relax the problem statement to match the realities of finite-precision hardware.
Sicun Gao et al. pioneered this approach via $\delta$-complete decision procedures in Proof Generation from Delta-Decisions. Instead of forcing a solver to answer whether a constraint is exactly satisfiable (which can fail due to rounding errors), a $\delta$-complete solver answers a perturbed question: is the constraint satisfiable under a tiny numerical wiggle room, $\delta$? By translating these numerical search steps into a first-order logic calculus, they generate checkable proofs that are fundamentally robust against floating-point artifacts.
Alternatively, verification tools can explicitly embed tolerance thresholds directly into their equivalence logic. In LCV: A Verification Tool for Linear Controller Software, Junkil Park et al. introduced defined tolerance thresholds when checking whether generated C code matches its high-level control model. This adjustment makes formal verification feasible for real-world software where bit-for-bit identity is impossible due to compiler optimizations and floating-point rounding.
Summary
The numerical soundness gap arises because formal logic requires absolute certainty, while modern hardware optimization relies on inexact floating-point approximations. Rather than abandoning fast numerical solvers, modern verification frameworks achieve soundness by bounding errors externally (via interval arithmetic), validating numerical outputs symbolically (via proof certificates), or embedding numerical limits directly into the proof definitions (via $\delta$-completeness).
Key Foundational Work
Consistency Techniques for Numeric CSPs (1993) — contributed 1 concept elements to this direction.
Structural filtering: A paradigm for efficient and exact geometric programs (1999) — contributed 1 concept elements to this direction.