Formal verification faces a persistent bottleneck: the trade-off between computational speed and absolute logical certainty. Interactive theorem provers (ITPs) like Coq, Lean, and Isabelle/HOL guarantee correctness by checking every logical step against a small, trusted foundational kernel. However, this extreme rigor makes them slow and unwieldy when dealing with complex algebraic manipulations, continuous optimization, or large-scale state spaces.
Conversely, external tools like Computer Algebra Systems (CAS), Satisfiability Modulo Theories (SMT) solvers, and numerical optimization engines are blisteringly fast but lack formal soundness guarantees. They rely on massive codebases, complex heuristics, and floating-point arithmetic prone to subtle bugs.
The naive solution—formally verifying these high-performance external tools from scratch—is an engineering impossibility due to their immense complexity and rapid evolution. Instead, a powerful design pattern has emerged across formal methods research: the skeptical verification architecture. This approach completely decouples the discovery of a solution from its verification, allowing developers to leverage untrusted, high-performance oracles without compromising logical soundness.
The Core Intuition: Verify the Witness, Not the Search
The fundamental reason this architecture succeeds is a core computational asymmetry: checking a solution is often significantly simpler than finding it.
Consider finding a valid invariant for a dynamical system, locating a global minimum for a non-linear polynomial, or finding a valid path through a massive graph. The search process requires navigating a massive or infinite space using complex heuristics, floating-point approximations, and aggressive optimizations.
However, if the external tool is treated as an untrusted oracle, it can be tasked with two things: finding the solution, and producing a mathematical certificate (or witness) that explains why the solution is correct.
+-------------------+ +-------------------------+
| Untrusted Finder | --Certificate--> | Verified Checker (ITP) | --> Absolute Guarantee
| (Fast, Complex) | | (Small, Foundational) |
+-------------------+ +-------------------------+
Once a candidate solution and its supporting certificate are produced, a lightweight, formally verified checker embedded directly within the theorem prover validates them. The checker does not care how the certificate was found—whether via a brilliant heuristic, a floating-point approximation, or pure luck. It only checks that the certificate satisfies strict mathematical criteria. If the untrusted oracle contains a bug or outputs an incorrect result, the certificate will simply fail validation, and the theorem prover will reject it. Soundness is preserved perfectly, while the engineering effort is shifted from verifying a complex solver to verifying a simple checker.
Mathematical Certificates in Action
This certificate-based paradigm has been successfully applied across a wide variety of mathematical and computational domains, bridging the gap between raw calculation and formal proof.
Symbolic and Algebraic Computation
Computer algebra systems excel at heavy symbolic calculations but occasionally gloss over logical edge cases like division by zero. To harness their speed safely, Wenda Li et al. demonstrated in Deciding Univariate Polynomial Problems Using Untrusted Certificates in Isabelle/HOL how Isabelle/HOL can import untrusted certificates from external symbolic engines to solve univariate polynomial problems. Similarly, Minchao Wu et al. designed an extensible interface in A bi-directional extensible interface between Lean and Mathematica that offloads complex symbolic tasks to Mathematica, verifying the results internally via Lean tactics to maintain full logical certainty.
Nonlinear Optimization
Numerical solvers are highly optimized but rely on floating-point approximations that threaten mathematical rigor. To bridge this gap, Victor Magron developed NLCertify: A Tool for Formal Nonlinear Optimization, which uses Sum-of-Squares (SOS) relaxations to generate certificates for nonlinear inequalities that Coq can formally check. Expanding on this, Xavier Allamigeon et al. showed in Formal Proofs for Nonlinear Optimization how a skeptical framework can safely convert floating-point results from external solvers into exact rational numbers, allowing proof assistants to leverage high-performance numerical heuristics safely.
Continuous Control and Invariants
Proving the safety of cyber-physical systems requires generating continuous invariants—mathematical shields showing a system cannot enter an unsafe state. In Pegasus: A Framework for Sound Continuous Invariant Generation, Andrew Sogokon et al. separated candidate generation from formal proof, allowing diverse, potentially unsound numerical solvers to propose invariants that are subsequently validated by a minimal trusted core. This pipeline was mirrored by Jonathan Hellwig et al. in From Zonotopes to Proof Certificates: A Formal Pipeline for Safe Control Envelopes, where unverified numerical tools compute zonotope-based safe regions, leaving the formal certification to a deductive theorem prover.
AI and Decision Processes
Modern AI verification demands scaling to massive state spaces where traditional internal verification fails. In Formally Verified Solution Methods for Markov Decision Processes, Maximilian Schäffeler et al. established that a certificate-based architecture allows verified software to achieve performance parity with unverified systems. By focusing verification efforts entirely on a lightweight certificate checker rather than a full optimization solver, the authors demonstrated in Formally Verified Approximate Policy Iteration that they could scale verification to factored Markov Decision Processes (MDPs) with up to $2^{40}$ states.
This paradigm also extends to deep learning: Robert Joseph George et al. introduced TorchLean: Formalizing Neural Networks in Lean, which validates certificates from external high-performance neural network verifiers against a formal intermediate representation inside Lean 4, bypassing the need to verify complex optimization code.
Logical Automation
Finally, this architecture enhances the core automation of proof assistants themselves. In Extending SMTCoq, a Certified Checker for SMT (Extended Abstract), Burak EKİCİ et al. detailed how Coq can safely offload logical goals to external SMT solvers like CVC4 by running the resulting solver-generated proofs through an internal, certified checker.
Why the Skeptical Architecture Wins
By shifting the verification burden from the process of discovery to the product of discovery, skeptical verification architectures resolve the historical tension between performance and trust:
- Minimal Trusted Computing Base (TCB): The external solver can consist of millions of lines of highly optimized C++ code. As long as the small, verified checker inside the ITP is correct, the overall system remains mathematically sound.
- Engineering Agility: Developers can continuously update, optimize, or replace external solvers and heuristics without needing to re-verify the entire system. Only the certificate format and the lightweight checker need to remain stable.
- Performance Parity: Verified systems can run at the speed of state-of-the-art unverified software, absorbing advancements in numerical optimization, SMT solving, and symbolic computation seamlessly.
Key Foundational Work
NLCertify: A Tool for Formal Nonlinear Optimization (2014) — contributed 2 concept elements to this direction.
Formal Proofs for Nonlinear Optimization (2014) — contributed 2 concept elements to this direction.
Extending SMTCoq, a Certified Checker for SMT (Extended Abstract) (2016) — contributed 2 concept elements to this direction.