Adam Langley Says Lean Proof Automation Is Here. The Hard Part Just Moved

Adam Langley says Lean proof automation crossed a practical threshold after several large language models completed a difficult software proof in about 20 minutes. The claim comes with an important qualification. AI generated the proof, but Lean checked every step against a formal specification.

That distinction separates this experiment from another story about AI producing plausible code. Langley built a Zstandard decompressor in Lean, then asked models to prove universal properties of its entropy-decoding table. The models reportedly finished without unresolved proof holes, although they also changed parts of his implementation.

The experiment points toward a different bargain for software teams. Developers might spend less time constructing proofs and more time deciding exactly what their systems must guarantee. AI coding assistants generate an answer and ask humans to find mistakes. Lean reverses that relationship by rejecting any answer that fails a machine-checkable statement.

This is not proof that formal verification has become cheap, easy, or suitable for every application. Langley described the decompressor as a toy, withheld its source, and measured it at one-tenth the speed of the standard zstd command. Independent research also shows that AI provers struggle when proofs depend on large, unfamiliar repositories.

The more defensible conclusion is still significant. AI can now absorb enough repetitive proof labor to make verification worth testing outside its traditional niches. For knowledge workers, the broader lesson reaches beyond software: automation becomes more trustworthy when the acceptance criteria are explicit and independently checked.

A Zstandard Experiment Put Lean Proof Automation to Work

The news is not that an AI wrote another program. It is that AI-generated work passed a checker designed to reject logical errors.

Langley, a security engineer known for his work on cryptography and internet infrastructure, published the experiment on July 26, 2026. His proof automation account describes building a Zstandard decompressor in Lean and formalizing several properties of its decoding tables.

Lean is both a functional programming language and a proof assistant. A proof assistant checks whether a formal argument establishes a precisely stated proposition. Lean’s small kernel validates the resulting proof term, so users do not need to trust the model that produced it.

The test focused on Finite State Entropy, or FSE, which Zstandard uses to encode some values efficiently. FSE assigns symbols across a table of states according to their probabilities. Each state identifies a symbol, the number of bits to read, and a baseline for calculating the next state.

A correct table must preserve several relationships. It needs the expected number of entries, the correct allocation for every symbol, and valid transitions for every possible state. Each nonzero-probability symbol must also have exactly one route to every target state.

Unit tests can check selected examples from the Zstandard specification. They cannot establish that these properties hold for every valid input. Langley instead wrote one theorem covering the complete table-construction function.

Several LLMs reportedly produced a proof in about 20 minutes. Langley confirmed that Lean accepted the result and that the files contained no sorry declarations, which Lean developers use as placeholders for missing proofs.

The models did not simply fill in an isolated blank. They changed the table-generation code because Langley had used too much imperative-style structure. That structure was harder for the proof machinery to analyze.

This detail matters because it reveals both the attraction and the cost. AI handled proof construction, but the implementation still needed a form that supported reasoning. Verification did not arrive as a final quality-control button applied to arbitrary code.

Langley also avoided presenting the project as production evidence. The code remains unpublished, the decoder covered a bounded experiment, and its performance lagged the established implementation. His claim concerns the availability of proof automation, not the readiness of this particular decompressor.

A related project offers a broader reference point. Lean creator Leonardo de Moura highlighted an AI-assisted zlib implementation that passed tests and proved round-trip correctness across every compression level. Together, these examples move AI proving closer to ordinary systems code.

They still leave a gap between an impressive artifact and a repeatable engineering process. Closing that gap will determine whether Lean proof automation becomes a common development tool or remains an expert demonstration.

The Old Barrier Was Proof Labor, Not Proof Checking

Formal verification already offered strong guarantees. Its economic problem was the human effort required to state and maintain them.

A normal test asks whether software behaved correctly for the examples that ran. Formal verification asks whether a mathematical model satisfies a stated property for every input within that model. That larger promise creates a much larger workload.

The seL4 microkernel remains one of the clearest historical examples. Its verification team produced a machine-checked proof connecting the kernel’s implementation to its formal specification. The project showed that high-assurance, production-scale software could be verified.

It also documented the cost. According to the team’s project retrospective, verification required roughly ten times the effort spent designing and implementing the C code. Proof material exceeded the implementation by more than twenty times its lines.

Those figures do not mean every verified project inherits the same ratio. seL4 pursued unusually extensive guarantees across a substantial operating-system kernel. They do explain why most software organizations chose tests, reviews, static analysis, and operational monitoring instead.

Traditional automation reduced some of this burden. Tools such as SMT solvers, which search for solutions to logical constraints, can discharge routine proof obligations. They work well when the problem fits the solver’s supported theories and expected structure.

The experience becomes less predictable when a goal sits outside that comfortable zone. Developers may wait without knowing whether a solver needs more time or will never finish. Teams also learn implementation patterns that make the solver behave, creating another specialized engineering discipline.

LLMs approach the task differently. They can read definitions, error messages, nearby lemmas, and informal explanations. They can propose intermediate results, revise failed tactics, and reorganize code when the current representation blocks progress.

That flexibility makes proof generation a natural target for language models. A model does not need to be trusted as the final authority. It needs to produce an artifact that the proof kernel accepts.

This is a better fit than many office automation tasks. A generated strategy memo has no complete checker for truth, relevance, and judgment. A Lean proof has a narrow acceptance condition that software can evaluate deterministically.

The result changes the expected division of labor. Humans specify the property, select the assumptions, and decide whether the model represents reality. AI searches for a proof, while Lean verifies the proposed result.

That does not eliminate human work. It moves effort toward specification, architecture, and review. Those activities are harder to automate because they require deciding which outcomes matter.

For knowledge workers, this is the deeper productivity story. The strongest automation does not merely produce more material. It connects generated material to explicit conditions that determine whether the result is acceptable.

That principle also applies to research and operational work. A team using a personal knowledge base can retrieve evidence before generating an answer. The result still needs criteria covering source quality, scope, and freshness.

Lean makes those criteria unusually strict. Its lesson is not that every task needs a theorem prover. It is that automation becomes more dependable when the organization can define a checkable contract.

AI Changes the Cost of Proof, Not the Meaning of Correctness

Lean proof automation can verify that code meets a specification, but it cannot decide whether the specification captures the right problem.

This is the central reversal in Langley’s experiment. The models’ uncertain reasoning does not automatically undermine the proof because Lean checks their final output. Yet the same checker cannot rescue a theorem that formalizes the wrong requirement.

Suppose a decompressor theorem proves that every generated state transition remains inside the table. That is valuable, but it does not establish compatibility with every Zstandard file. It also says nothing about denial-of-service behavior, memory limits, side channels, or implementation performance.

Each additional guarantee needs a corresponding statement and a connection to the actual program. If that connection omits an assumption, Lean can prove the formal statement while the deployed system remains vulnerable.

The issue resembles a well-written contract that governs the wrong transaction. Perfect internal consistency cannot repair a missing obligation. Verification increases confidence inside the boundary that people defined.

Langley’s FSE theorem illustrates the better case. The properties map directly to assumptions needed by the optimized decoding loop. Table size, symbol allocation, valid transitions, and unique reachability are concrete invariants rather than broad claims about quality.

Once those invariants exist, the compiler and kernel can enforce them throughout the program. A future edit that violates one of them will fail to type-check until the implementation or proof changes.

This creates a different review surface. Engineers do not need to examine thousands of generated proof steps with equal attention. They need to audit the theorem, its assumptions, and the code-to-model connection.

That is where scarce expertise moves. A senior engineer who once spent days guiding tactics might instead spend those days refining the formal contract. AI handles much of the mechanical search, while human reviewers evaluate whether the contract deserves trust.

The approach can also make disagreements more productive. Product, security, and engineering teams often use the same word, such as “valid,” while carrying different definitions. A formal specification forces those definitions into visible conditions.

Knowledge work suffers from the same hidden-invariant problem. A market analysis might need current sources, a defined region, and a fixed reporting period. Teams often leave those constraints in comments, meeting notes, or one employee’s memory.

AI can generate a polished report while silently violating any of them. A better workflow represents important constraints before generation begins. Some conditions can become automated checks, while others remain explicit review questions.

That is why knowledge blending matters in AI-assisted work. Generated output becomes easier to assess when it remains connected to the relevant records, decisions, and evidence. The check is less absolute than Lean’s kernel, but the operating principle is similar.

Organizations should therefore resist the easiest interpretation of proof automation. The benefit is not permission to stop reviewing AI output. It is an opportunity to review at a more valuable layer.

Proof generation becomes cheaper. Defining correctness becomes more central. Teams that cannot agree on requirements will not gain strong guarantees by adding Lean or an AI prover.

Lean Formal Verification Now Pressures Testing-Only Workflows

The immediate pressure falls on teams building security-sensitive code that still treat tests as their highest available assurance.

Testing remains essential because it evaluates real executions, integrations, performance, and environmental behavior. Formal verification addresses a different question. It checks whether a model satisfies a property across all cases covered by the proof.

Neither method subsumes the other. Langley used Zstandard test vectors as ordinary unit tests while proving broader properties of the table generator. The tests checked compatibility examples, while the theorem covered universal structural invariants.

The change is economic. Formal verification previously demanded enough specialized labor that many teams could dismiss it before evaluating its benefits. If AI reduces proof construction time, that automatic dismissal becomes harder to defend.

Cryptographic software offers an early proving ground. Small arithmetic mistakes can invalidate larger security systems, and many important functions already have mathematical specifications. The value of universal guarantees is unusually clear.

A May 2026 experience report described a Rust verification pipeline that translates production cryptographic code into Lean. It combines Rust extraction tools, formal specification libraries, and AI provers such as Aristotle and Aleph.

The researchers applied the pipeline to components from Plonky3 and RISC Zero. Targets included field arithmetic, Merkle inclusion verification, polynomial evaluation, and FRI operations used by zero-knowledge systems. Every submitted proof still passed through Lean’s kernel.

The paper also records engineering friction. Toolchain versions drifted, translation tools supported only portions of Rust, and missing lemmas blocked automation. AI provers closed some obligations, while others still required manual work.

This evidence supports a measured forecast. Verification will probably enter production through narrow, high-value components rather than entire business applications. Teams can start with parsers, authorization rules, cryptographic operations, and state-transition logic.

These components have three useful properties. Their behavior can often be specified precisely, failures carry high costs, and their boundaries are small enough for current tools to understand.

The pressure will also reach vendors selling AI coding systems. Generating more code is becoming less distinctive. Producing code with independently checkable properties creates a stronger claim.

A coding agent might eventually return three connected artifacts: an implementation, a formal statement of required behavior, and a kernel-checked proof. Reviewers could focus on whether the statement matches the product requirement.

Testing-focused platforms will respond rather than disappear. Expect stronger combinations of fuzzing, property testing, symbolic execution, and proof. Generated tests will continue finding mismatches between formal models and messy deployment environments.

Formal verification vendors also face pressure. Their traditional advantage includes scarce expertise in proof construction. AI reduces the value of repetitive tactic work while increasing demand for specification design, integration, and assurance architecture.

Managers should not interpret this shift as an immediate hiring reduction. Early adoption usually creates integration work before it removes maintenance work. Teams will need people who understand both the application domain and the proof boundary.

The useful question is therefore not whether Lean replaces conventional programming. It is which expensive assumptions can now move from comments and review checklists into machine-enforced contracts.

What the Zstandard Result Does Not Prove

One unpublished toy decoder cannot establish that current AI provers scale across production repositories, frequent changes, or poorly specified systems.

Langley stated these limitations directly. His decoder ran about ten times slower than the zstd command on his machine. He also warned that strong types can amplify changes because revised assumptions propagate through derived types.

That propagation can be a benefit. It exposes every dependent component that needs attention. It can also turn a small product change into a large proof-maintenance project.

Performance creates another tradeoff. Lean can make in-place updates when an object has a single reference. A minor code change that retains another reference can therefore damage performance without changing functional correctness.

Proof automation does not automatically detect that regression. The theorem must include an appropriate performance model, or another benchmark must catch it. Correctness and efficiency remain separate engineering claims.

Repository scale presents the most important challenge. Langley’s example had a focused implementation and a theorem connected to nearby definitions. Production systems spread meaning across packages, generated code, build configurations, databases, and external services.

The 2026 VeriSoftBench study tested this problem using 500 proof obligations from 23 open-source Lean repositories. Its repository benchmark preserved project-specific definitions and cross-file dependencies.

The researchers found that provers trained on mathematics-oriented Lean tasks transferred poorly to repository-centered software verification. Performance declined as proofs depended on larger, multi-step chains of local definitions.

Providing carefully selected context improved results compared with exposing an entire repository. It still left substantial room for improvement. Context retrieval helped, but it did not solve the reasoning problem.

That finding directly limits the strongest interpretation of Langley’s claim. LLMs can produce meaningful software proofs today. They cannot yet handle every proof obligation simply because a project uses Lean.

There is also a verification gap around the published experiment. Readers can inspect Langley’s explanation, theorem statement, and caveats. They cannot reproduce the complete result because he did not publish the decoder or proof files.

His confirmation that no sorry declarations remained is useful firsthand evidence. It is not the same as an independent build from a pinned repository. The result should be treated as a credible engineering report, not a benchmark.

Security teams must also examine the trusted computing base. Lean’s kernel is intentionally small, and independent kernel implementations can compare results. Yet deployments still rely on compilers, runtime behavior, hardware, and the accuracy of any external model.

The system can prove that a Lean function meets a Lean specification. Additional work is needed to show that optimized native code preserves those semantics. Langley suggested verified assembly as one possible direction.

These limits do not erase the result. They locate it. Lean proof automation appears useful for bounded components whose properties can be stated precisely and whose dependencies fit within available context.

That is already more practical than the old assumption that formal proof always requires a specialist to handcraft every step. It remains far from a universal “verify” button for generated software.

Three Signals Will Show Whether Proof Automation Is Really Here

The next phase depends on reproducibility, repository-scale maintenance, and adoption inside ordinary engineering workflows.

The first signal is a public, reproducible implementation matching Langley’s pattern. It should include source code, theorem statements, generated proofs, pinned dependencies, and an automated build that rejects unresolved holes.

A published artifact would let independent teams measure proof time, model dependence, and maintenance costs. It would also reveal how much human intervention occurred between the initial implementation and the accepted proof.

If several teams reproduce the workflow on parsers or compression libraries, Langley’s conclusion becomes stronger. If results depend on extensive hidden prompting or manual restructuring, the current productivity claim weakens.

The second signal is performance on changing repositories. A useful system must repair proofs after normal refactors, dependency updates, and altered requirements. Solving a theorem once is less valuable than keeping it solved across releases.

Repository-scale benchmarks should therefore add longitudinal tasks. An AI prover could receive consecutive commits and repair the affected proofs while preserving the original specification. Teams should track accepted repairs, elapsed time, compute use, and human edits.

Improvement on dense local dependencies would address the weakness identified by VeriSoftBench. Continued failure would confine AI proving to small modules with carefully curated context.

The third signal is integration into mainstream coding agents and continuous integration systems. Proof automation becomes operational when a pull request can state a required invariant, generate a proof, and have Lean verify it automatically.

This process also needs transparent failure modes. A model that cannot find a proof must distinguish among missing context, a difficult theorem, incompatible code, and a false statement. Otherwise, teams receive another opaque red build.

Adoption will likely start where organizations already write precise requirements. Cryptography, protocol implementations, compilers, financial controls, and access-control systems fit that description. Broader business software will move more slowly.

Knowledge workers should watch the same pattern in their own tools. Reliable automation needs explicit inputs, acceptance rules, traceable evidence, and a checker with authority to reject the result.

Most office tasks cannot reach mathematical certainty. They can still adopt narrower gates. A research brief can require dated sources. A sales analysis can require every account claim to map to a customer record. A project update can flag statements unsupported by recent work.

That shift turns AI from an unchecked author into a candidate generator operating inside a controlled process. People retain responsibility for defining the boundary and reviewing what the checks cannot cover.

Lean proof automation offers the clearest version of that future because its checker is exact. The model can be inconsistent, verbose, or wrong repeatedly during search. Only a valid proof reaches the program.

The question for the next few months is not whether LLMs can generate any formal proofs. They already can. The question is whether teams can repeatedly turn real requirements into maintained, machine-checked software without recreating the old tenfold labor burden.

Choose one costly assumption in your workflow and write down what would make it verifiably true. If the condition can be checked, automate that check before automating more output. That is the practical lesson behind Langley’s experiment, and the standard proof automation now has to meet.