Whiel: A Neurosymbolic Platform for Certified Relational Program Verification
Organizations: Duke University, Durham, North Carolina, USA
Abstract
We present the Whiel (a contraction of Whi(le-R)el) system for Lean-certified reasoning about imperative relational programs. The system can encode containment and equivalence problems for Datalog, its extensions with negation, and the core fragment of graph query languages. It can also represent optimized or incremental evaluation algorithms that are not expressible in the original query language, as well as first-order specifications of integrity constraints, schema mappings, and views arising in data integration, exchange, and sharing. Whiel's program states are database instances, and its imperative structure enables compositional Hoare-style reasoning with first-order relational specifications, using prophecy variables and leveled invariants to support inductive arguments. Whiel supports neurosymbolic discovery of loop invariants whose verification conditions can be checked using the Vampire first-order theorem prover. Counterexamples are fed back into the neurosymbolic pipeline, while proposed solutions are translated into Lean proof certificates. To validate the Whiel system, we evaluate its performance on a curated benchmark suite. In summary, we envision the Whiel system as a tool for tackling mathematically demanding, typically undecidable problems involving complex query and constraint languages, with a high degree of trust in its output.
Figures & tables
| (3) | \begin{array}[]{@{}l@{\qquad}l@{\qquad}l@{}}\text{Query T}&\text{Views}&\text{Rewriting R}\\[4.0pt] \begin{aligned} T(x,y)&\;\leftarrow\;E(x,\mathit{red},y)\\ T(x,y)&\;\leftarrow\;E(x,\mathit{blu},y)\\ T(x,z)&\;\leftarrow\;E(x,\mathit{red},y),T(y,z)\\ T(x,z)&\;\leftarrow\;E(x,\mathit{blu},y),T(y,z)\end{aligned}&\begin{aligned} \mathit{RedPV}(x,y)&\;\leftarrow\;E(x,\mathit{red},y)\\ \mathit{RedPV}(x,z)&\;\leftarrow\;E(x,\mathit{red},y),\mathit{RedPV}(y,z)\\[4.0pt] \mathit{BluPV}(x,y)&\;\leftarrow\;E(x,\mathit{blu},y)\\ \mathit{BluPV}(x,z)&\;\leftarrow\;E(x,\mathit{blu},y),\mathit{BluPV}(y,z)\end{aligned}&\begin{aligned} R(x,y)&\;\leftarrow\;\mathit{RedPV}(x,y)\\ R(x,y)&\;\leftarrow\;\mathit{BluPV}(x,y)\\ R(x,z)&\;\leftarrow\;R(x,y),R(y,z)\end{aligned}\end{array}\vskip-10.00002pt |
| # Solved (%) | Per-task averages | |||||
|---|---|---|---|---|---|---|
| Method | Valid (69) | Invalid (17) | Total (86) | Time (s) | Rounds | Cost ($) |
| Whiel | 57 (83%) | 16 (94%) | 73 (85%) | 189 | 2.95 | 0.49 |
| Whiel - OneRound | 32 (46%) | 14 (82%) | 46 (53%) | 58 | 1 | 0.14 |
| DirectLean | 4 (6%) | 16 (94%) | 20 (23%) | 398 | – | 2.08 |
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
| ID | Task | Claim | V/I | P | E |
| Classic Datalog programs (21) | |||||
| 0001 | Naive TC is transitively closed | Cr | V | ||
| 0013 | Naive TC under the false bound | Cr | I | ||
| 0106 | Left-linear TC vs. lfp of nonlinear TC | Eq | V | ||
| 0107 | Nonlinear TC vs. lfp of left-linear TC | Eq | V | ||
| 0108 | Right-linear TC vs. lfp of left-linear TC | Eq | V | ||
| Source | Tasks | Valid | Invalid |
|---|---|---|---|
| Classical database problems | 42 | 34 | 8 |
| Classic Datalog programs | 21 | 20 | 1 |
| Query reformulation using views | 10 | 8 | 2 |
| Specification vs. procedure | 11 | 6 | 5 |
| Real systems | 33 | 27 | 6 |
| Production programs | 7 | 7 | 0 |
| Read-only MCP tools ( Whiel +Tools, Whiel +Tools+Skills) | |
|---|---|
| Countermodel | The finite database behind a refuted check, on which the check’s premises hold and its goal fails. |
| Strongest refutations | For one clause, the refutations whose premise sets are inclusion-maximal. |
| History | One clause’s record: its status, its levels, and every check with its outcome. |
| Ledger | The chronology of all checks in the run. |
| Validate clauses | Whether draft clauses parse and fit the schema, without spending a round. |
| Evaluate clauses | The truth value of draft clauses on retained countermodels or supplied finite instances. |
Formal Verification
Formal verification uses mathematical models and machine-checked proofs to establish whether software and systems satisfy precise specifications.
See all 374 papers