LRAT-Catcher: Importing SAT Solver Certificates into Lean4 by Reflection

Bridging the Gap Between Automated and Interactive Theorem Proving

The release of LRAT-Catcher represents a significant technical contribution to the formal verification ecosystem. The tool addresses a longstanding friction point: SAT solvers can efficiently solve enormous combinatorial problems, but their results are typically opaque to interactive theorem provers (ITPs) like Lean4. LRAT-Catcher provides a reflection-based mechanism to import DIMACS formulas alongside their LRAT certificates directly into Lean4, enabling formal verification of SAT solver outputs within a trusted proof assistant environment.

Why This Matters

The core innovation here is not in the SAT solving itself—LRAT certificates have been a standard output format for years—but in the reflection approach. Instead of requiring Lean4 to trust an external SAT solver or replay an entire search procedure, LRAT-Catcher translates the certificate into Lean4's native proof language. This means the verification burden shifts from trusting the solver's implementation to checking a relatively compact proof object within Lean4's trusted kernel.

For the broader AI and formal methods community, this is a practical step toward hybrid reasoning systems. SAT solvers handle NP-complete problems that ITPs cannot feasibly solve by brute force, while ITPs provide the foundational rigor that automated solvers lack. LRAT-Catcher acts as a verified bridge, allowing practitioners to use the best tool for each subproblem without sacrificing end-to-end correctness.

Implications for AI Practitioners

For those building AI systems that rely on formal verification—such as safety-critical controllers, protocol verification, or hardware design—this tool reduces the engineering overhead of integrating SAT solving into Lean4 workflows. Previously, one would need to either trust the solver blindly or implement a custom verification layer. Now, the import path is standardized and general-purpose.

The reflection technique also has implications beyond SAT solving. It demonstrates a pattern that could be extended to SMT solvers, constraint programming, or even machine learning-based reasoning tools that produce verifiable certificates. As AI systems increasingly incorporate formal guarantees, having a clean interface between automated reasoning engines and interactive proof assistants becomes essential.

However, practitioners should note limitations: LRAT-Catcher only handles SAT problems, not quantified Boolean formulas or SMT theories. The tool's performance depends on certificate size, which can be large for hard problems. Additionally, the current implementation targets Lean4 specifically, though the architecture could inform similar bridges for Coq, Isabelle, or Agda.

Key Takeaways

• LRAT-Catcher enables importing SAT solver results into Lean4 via reflection, eliminating the need to trust external solvers blindly.
• The tool bridges automated and interactive theorem proving, allowing practitioners to combine the strengths of both approaches.
• The reflection technique offers a template for integrating other certificate-producing automated reasoners into interactive proof assistants.
• Practical adoption requires attention to certificate size and is currently limited to SAT problems, but the approach is extensible to other domains.