TL;DR
Whiel is a neurosymbolic platform that automates the formal verification of complex database programs by combining the creative "guessing" power of Large Language Models (LLMs) with the rigorous "checking" of symbolic theorem provers. By generating Lean-certified proof certificates, it provides a high-trust solution for mathematically demanding and often undecidable problems like query equivalence and incremental view maintenance.
What Problem Does This Paper Address?
In modern data management, developers frequently face "hard" problems: Is this optimized recursive query equivalent to the original? Does this incremental update algorithm correctly maintain a complex view? While LLMs are increasingly good at proposing solutions to these problems, they are notorious for "hallucinating" or producing subtly incorrect code.
Verifying these solutions manually is a bottleneck, requiring significant mathematical expertise and time. Furthermore, many of these database problems are "coRE-complete," meaning there is no single algorithm that can always prove a solution is correct. The authors address this by creating a system that can not only find proofs for these difficult relational programs but also provide an independent, machine-checked guarantee (a certificate) that the proof is valid.
Methods
Whiel (a contraction of Whi(le-R)el) treats database operations as imperative programs. It encodes database problems as Hoare triples—a standard formal logic framework that defines how a program transforms a starting state (precondition) into a final state (postcondition).
The system uses a "guess-and-check" neurosymbolic pipeline:
- Proposer (AgentHoudini): An LLM agent proposes candidate loop invariants (logical statements that remain true throughout a program's execution) or counterexamples.
- Verifier (LeveledHoudini): A novel symbolic algorithm that organizes these candidate statements into "ladder invariants." It uses the Vampire first-order theorem prover to prune incorrect guesses and provide feedback to the LLM.
- Prophecy Variables: To overcome the expressive limits of standard logic (like the inability of first-order logic to define transitive closure), Whiel introduces variables that "predict" the terminal state of the program, allowing for more powerful inductive reasoning.
- Certifier: Once a valid invariant is found, Whiel automatically constructs a formal proof in the Lean theorem prover. This ensures the final result is verified by a small, trusted kernel, removing the need to trust the LLM or the intermediate symbolic tools.
Datasets
The authors introduced a new, curated benchmark of 86 relational verification tasks. These tasks are drawn from:
- Classical database theory: Naive vs. semi-naive Datalog evaluation, query containment, and the "chase" algorithm.
- Real-world systems: Code and logic from PostgreSQL, Soufflé, and network analysis tools.
- LLM-generated programs: Challenging cases where AI-generated code needs verification.
The suite includes 69 valid and 17 invalid tasks, providing a ground-truth baseline for evaluating verification performance.
Key Insights and Ideas
- The Power of Iteration: Simply asking an LLM to write a proof (the "DirectLean" approach) is largely ineffective for hard problems. Whiel’s iterative loop, where the symbolic verifier provides concrete counterexamples back to the LLM, is crucial for success.
- Ladder Invariants: The authors found that complex proofs often require "leveled" reasoning, where simple properties established early in a loop support more complex properties later. The LeveledHoudini algorithm automates this structuring.
- Prophecy as a Bridge: By using prophecy variables to represent the "future" terminal state of a database, Whiel can reason about properties (like reachability in a graph) that are otherwise difficult to express in the first-order logic used by automated provers.
- Trust but Verify: By separating the search for a proof (which can be messy and AI-driven) from the certification of that proof (which is strictly logical), Whiel achieves high automation without sacrificing mathematical certainty.
Key Results
Whiel significantly outperformed baseline methods using GPT-5.5:
- Success Rate: Whiel solved 85% (73/86) of the benchmark tasks. In contrast, asking the LLM to write Lean proofs directly (DirectLean) solved only 23%.
- Efficiency: Whiel was not only more effective but also cheaper, costing an average of **$0.49 per task** compared to $2.08 for the DirectLean baseline.
- Scaling: When upgraded to stronger models like GPT-6 Astra, the system solved 85 out of 86 tasks, demonstrating that the symbolic harness effectively scales with model capability.
- Certification: The system successfully generated Lean certificates for 86.2% of the solutions accepted by the verifier, providing a high-trust "seal of approval."
Limitations and Future Work
While powerful, Whiel has some noted limitations:
- Finite vs. Infinite: The underlying prover (Vampire) checks validity over arbitrary structures, while databases are finite. This makes the system sound but theoretically incomplete for some edge cases.
- Language Scope: The current version focuses on core relational algebra. The authors plan to extend it to support arithmetic, aggregation (like SUM or COUNT), and the creation of new values.
- Certification Overhead: Generating and checking large Lean proofs can be memory-intensive, sometimes leading to timeouts during the final certification step. Improving the resource efficiency of the certifier is a target for future development.
Summary updated