Proof Checking Continuous Reachability
Long Qian, André Platzer
cs.LO
Nov 18, 2026 · v1
math.LO
TL;DR
Implements a reflection-based proof checker in Lean4, built on a deep embedding of differential dynamic logic, to certify Taylor-model ODE reachability traces.
Abstract
This paper introduces a proof format and proof checker for certifying reachability computations of ordinary differential equations (ODEs) with polynomial vector fields. Establishing a proof checking framework for certifying ODE reachability is similar to the checking of UNSAT proofs for propositional satisfiability solving, but it is even more important due to the challenges inherent in dealing with ODEs, and even more challenging due to the numerical nature of ODE reachability algorithms. The proofs are expressed in differential dynamic logic (dL), and can be independently verified with symbolic theorem provers for dL (e.g. KeYmaeraX). Such proofs are naturally generated by reachability algorithms based on Taylor models, a popular technique to obtain rigorous bounds on approximations of ODEs. This paper proves the completeness of such proofs - if an approximation was correctly computed by some (possibly untrusted) reachability algorithm via Taylor models, then a corresponding proof in dL can be automatically generated and checked to be correct in dL's proof calculus. A dedicated proof checker is implemented in Lean4 for improved performance, which is capable of formally verifying benchmarks in the ARCH competition.
Problem
Reachability computations for polynomial ODEs come from numerical, possibly untrusted tools, and their results need independent certification, much as UNSAT proofs are checked for SAT solvers.
Approach
Defines a proof format in differential dynamic logic (dL) generated from Taylor-model reachability traces, and proves completeness: any correctly computed Taylor-model approximation yields a checkable dL proof. Two checkers are implemented, one in KeYmaera X and one in Lean4. The Lean4 checker uses reflection over a deep embedding of dL and Lean4's verified floating-point arithmetic.
Results
On ARCH competition benchmarks, the Lean4 checker rejected all Picard certificates extracted from Flow* and JuliaReach as unsound. It certified all 8 Ariadne runs. KeYmaera X was far slower and mostly could not complete a single trace step.