What Is an AI Formal Proof in Lean 4?

An AI formal proof in Lean 4 is a mathematical argument, generated by an AI model, that a piece of code correctly satisfies a written specification. Every logical step is verified by Lean's trusted kernel rather than accepted on the model's word. The kernel either accepts the proof or rejects it. There is no partial credit and no plausible-sounding-but-wrong answer, which is the failure mode that defines ordinary AI code generation.¹²

That distinction matters more than it sounds like it should. Most AI-generated code is judged by whether it compiles, passes a few tests, and looks reasonable to a reviewer skimming a pull request. A formal proof is judged by something much stricter: a small trusted program checks the logic line by line and returns a binary verdict, pass or fail.¹

What does 'formal proof' actually mean?

In everyday engineering, "we tested it" means someone ran the code against a handful of inputs and it behaved. A formal proof makes a different kind of claim entirely: the code behaves correctly for every input the specification covers. That claim is established the way mathematicians prove theorems, through a chain of logical steps, each one following necessarily from the last, checked by a system that has no opinion and no incentive to be agreeable.

This is also where formal proof diverges sharply from how large language models normally operate. An LLM asked whether a function is correct will give you an answer that sounds confident whether or not it's true. A formal proof strips that ambiguity out. Either the kernel verifies the argument, or it doesn't.¹

What is Lean 4, specifically?

Lean 4 is two things at once: a general-purpose programming language, and an interactive theorem prover.¹ You can write ordinary code in it, write a formal specification of what that code is supposed to do, and write a proof connecting the two, all inside one system, all checked by the same trusted kernel. That's unusual. In most software stacks, the code, the spec (if one exists at all), and the testing are three separate artifacts maintained by different processes with no guaranteed relationship between them.

Lean started as a tool for research mathematicians, and it's still used that way. It's also the language behind a 13-million-line formalization of Fermat's Last Theorem, which gives a sense of the scale Lean proofs can reach when the underlying mathematics is this hard, as we covered in our explainer on how LLMs actually work. What's new is AI models using that same machinery on software.

How do AI models generate Lean proofs today?

The basic loop looks like this: a model proposes a proof, Lean's kernel checks it, and if it fails, the model revises and tries again. This generate-check-correct cycle is what lets these systems improve without a human manually verifying each step.

A few concrete examples show how far this has come:

• DeepSeek-Prover-V2-671B reached 88.9% pass rate on the MiniF2F-test theorem-proving benchmark and solved 49 of 658 problems from PutnamBench, using a pipeline that recursively decomposes hard theorems into smaller subgoals.³
• AlphaProof, Google DeepMind's reinforcement-learning system, combined with AlphaGeometry 2 to score 28 out of 42 possible points at the 2024 International Mathematical Olympiad, matching silver-medal-level human performance and marking the first time an AI reached that bar on formal mathematics.⁴
• Harmonic AI's Aristotle formally verifies its own math answers in Lean before showing them to a user. Its CEO describes the goal directly: "we actually do guarantee that there's no hallucinations."¹
• Leanstral, an open-source model from Mistral built specifically for Lean proof engineering, beat Claude Sonnet's score on the FLTEval benchmark at roughly 1/15th the cost, reaching a pass@2 score of 26.3 against Sonnet's, for about $36 versus $549 to run.⁵

These systems aren't proving arbitrary business logic yet. They're mostly proving math theorems and, increasingly, small verified programs. But the machinery generalizes, and that's the part worth paying attention to.

Why does this matter more than typical AI code testing?

Testing samples cases. Proof covers every case by construction.⁶ That single fact explains why formal verification is getting renewed attention right as AI-generated code volume explodes.

The status quo is not reassuring. Veracode's 2025 GenAI Code Security Report tested over 100 LLMs across 80-plus coding tasks and found that 45% of AI-generated code samples introduced OWASP Top 10 security vulnerabilities.⁷ That's not a rare edge case. That's nearly half. Testing and code review catch some of that, but both are sampling exercises, run by people or processes with limited time, against a code volume that keeps growing.

Lean's creator, Leonardo de Moura, now at AWS, makes the case plainly: as AI increasingly writes critical infrastructure code, only mathematical proof scales verification at the speed AI generates code, because testing only samples inputs while proof covers all of them.⁶ AWS has already formally verified its Cedar authorization policy engine, and Microsoft is using Lean to verify its SymCrypt cryptographic library. This is not a research curiosity anymore. It's shipping in production security infrastructure.⁶

It's also worth being honest about how hard full end-to-end verified code generation still is. On the Clever benchmark, 161 curated formal verification tasks derived from HumanEval, frontier models including GPT-4o, Claude 3.7, and DeepSeek-R1 solved essentially one problem out of 161 when required to produce a valid spec, a valid implementation, and proofs for both.⁸ Models are fluent at writing code that compiles. They are still bad at writing code that's fully proven correct end to end.

The catch: proofs only guarantee the spec, not your intent

Here's the part that gets glossed over in the excitement: a formal proof only tells you the code matches its written specification. It says nothing about whether that specification captures what you actually wanted.

Jeff Williams, founder of OWASP, put it directly: "A proof can establish that an implementation matches its specification, but it cannot establish that the specification reflects what the business really needed."² Researchers discussing AI-generated Lean proofs have their own name for the same problem: the "Mind-Reading Problem." Checking that a formal statement actually matches what you had in mind is not something that can be fully automated.⁹ A proof can even be technically valid while being vacuously true, or built on a definition that quietly diverges from the one you meant, and Lean itself has had rare kernel soundness bugs in its history.⁹

So the hard, expensive work doesn't disappear with AI-generated proofs. It moves. Instead of hand-writing proofs, PhD-trained verification specialists, and now AI systems, spend their effort writing specifications precise enough to be worth proving against. That's still work. It's just work that produces a durable guarantee instead of a probabilistic one.

Where is this realistic today, and where isn't it?

Given the Mind-Reading Problem and the current state of the tools, formal verification is not about to replace your whole codebase. It's realistic for a narrower set of targets, and security practitioners are fairly consistent about which ones:

1. Cryptographic primitives, where a single subtle bug can compromise everything built on top, and where Microsoft's SymCrypt work is already underway.⁶
2. Authorization and access control engines, the kind AWS verified in Cedar, where the cost of a logic error is a security breach, not a cosmetic bug.⁶
3. Parsers, historically a top source of memory-safety and injection vulnerabilities in mainstream software.
4. Financial calculations, where correctness has a direct dollar value attached and edge cases are unforgiving.

Rewriting an entire application stack in Lean is a different proposition, and not one that's close to happening. Mainstream languages have decades of libraries, frameworks, and hiring pools that Lean doesn't have, and probably won't have anytime soon.² The realistic path is targeted: identify the few components in your system where being wrong is catastrophic, and put proof effort there.

What's changing is the cost curve. The seL4 microkernel, a landmark formally verified system, took 20 person-years and roughly 200,000 lines of proof to verify just 8,700 lines of C code.¹⁰ That's the kind of cost that historically kept formal verification confined to a handful of PhD teams working on the highest-stakes systems. AI absorbing that cost, even partially, is what makes proof-backed code a plausible option for ordinary engineering teams rather than an academic exercise.¹⁰

What this means for the software your employees build with AI

Here's where this connects back to a problem most companies already have and haven't named. Employees across your organization are using AI coding tools to build internal dashboards, automation scripts, and small applications, often outside any formal review process. Almost none of that software has any verification behind it beyond "it ran when I tried it," and Veracode's numbers suggest that's a genuinely risky bar.⁷ We've written before about the governance playbook for auditing AI-generated code that most of this shadow AI output never goes through.

Formal proof in Lean is, right now, the strongest verification signal that exists for software. It's not going to show up in your expense-tracking spreadsheet built by AI over a weekend, and it doesn't need to. But if your organization is building or buying software you actually intend to own and depend on long-term, rather than software you'll quietly replace next quarter, the components that matter most, the authentication layer, the payment logic, the data validation at your system's edges, are exactly the places where asking "can we prove this" is a reasonable question to raise. Tools like Remy that help organizations build and reason about the software they own, rather than the software they merely rent from a SaaS vendor, are part of what makes that question answerable instead of theoretical.

The capability exists. DeepSeek, AlphaProof, Aristotle, and Leanstral all show that AI can generate proofs a trusted kernel will accept.³⁴¹⁵ The open question for most companies isn't whether the technology works. It's whether anyone is pointing it at the code that would actually benefit from it.

Key takeaways

• A formal proof in Lean 4 is a machine-checked argument that code matches its specification, verified by a trusted kernel that gives a binary pass or fail.¹
• AI systems like DeepSeek-Prover-V2, AlphaProof, and Leanstral can already generate Lean proofs that pass this check, at benchmark scores that were out of reach a few years ago.³⁴⁵
• Proof beats testing because testing samples inputs while proof covers every input the specification defines.⁶
• A proof only guarantees the code matches its spec, not that the spec matches your actual intent. Writing a good spec is now the hard part.²⁹
• Realistic near-term targets are narrow, high-stakes components: crypto, authorization, parsers, financial logic, not full application rewrites.²
• Most AI-written software inside companies today has no formal verification at all, which is a governance gap worth naming rather than ignoring.⁷