LLMs Make Formal Verification Practical: A Zstandard Case Study

The News

Adam Langley — a well-known security engineer and former Google cryptographer — published a striking experiment on his personal blog on July 26: he built a complete Zstandard decompressor in Lean, a dependently-typed programming language, and used LLMs to automatically prove the correctness of complex algorithms. The result: proofs that used to take experts days or weeks now take about 20 minutes on a $20/month subscription plan.

This is not an academic paper. It is a real engineer testing whether formal verification is actually viable for everyday work — and the answer is yes.

Background: From "Too Expensive" to "Affordable"

Formal verification is the technique of mathematically proving that code behaves exactly as specified — no tests needed, no luck required. The classic problem: the proof effort has always dwarfed the implementation effort by an unreasonable margin.

The seL4 project — a fully verified operating system kernel — is the clearest example. According to the project's retrospective, the team spent roughly 10 times as long proving as they did designing and implementing, and produced more than 20 times as many lines of proof code as C code. A ratio that made even well-resourced organizations think twice.

Tools like F* attempt to automate this with SMT solvers, but create a different problem: solvers can run indefinitely, forcing users to develop a "sixth sense" for writing code that keeps them happy. As Langley puts it: "You end up serving a complex and fickle god."

LLMs change the game for one crucial reason: proof irrelevance. Once a statement is true, the contents of its proof don't matter — only that it exists and type-checks. This makes LLMs the ideal tool: as long as the proof compiles, its internal quality is irrelevant.

The Experiment: Zstandard Decompressor in Lean

Zstandard (or zstd) is the compression algorithm steadily replacing gzip as the standard. It belongs to the LZ77 family but uses a superior entropy encoder and is designed for extremely fast decompression. RFC 8878 defines the entire format.

Langley chose Zstandard for two reasons: he was curious about the algorithm, and it was complex enough to test the limits of LLM-powered formal verification.

The Standout Result: Proving FSE Table Construction

FSE (Finite State Entropy) is Zstandard's entropy encoder — a state machine where each symbol is assigned a fraction of states proportional to its probability of occurrence. The algorithm for building the FSE table from symbol probabilities is described in RFC 8878, which includes three sample test vectors.

Instead of writing unit tests, Langley used an LLM to prove four universal properties of the ofDistribution function:

Correct table size: t.entries.size = 2 ^ accuracyLog
Correct state allocation: the number of states per symbol matches its probability
Read safety: for every state, reading nbBits bits and adding the baseline always yields a valid state
Uniqueness of paths: for every symbol with non-zero probability and every target state, there is exactly one state for that symbol that can reach the target

These are the subtle invariants that an optimized decoding inner-loop demands. In conventional languages, they can only be comments — or worse, implicit assumptions nobody verifies.

The outcome: LLMs automatically proved all of this in about 20 minutes, using a fraction of a $20/month subscription quota. As Langley wrote: "It'll probably be table-stakes next year."

Lean: A Language That Turns Proofs Into Types

Lean is a purely functional language with a dependent type system. The core difference: types can depend on values, allowing complex invariants to be encoded directly in the type system.

For example, a readExact function in Lean returns {ba : ByteArray // ba.size = n} — a byte array that the type system guarantees is exactly n bytes long. When accessing an array element, Lean forces a proof that the index is in bounds — otherwise the code doesn't compile.

Langley noted some practical aspects:

Strict evaluation (unlike Haskell's laziness) makes performance reasoning easier
Do-notation with for loops, return, and break — imperative-style programming is possible
Reference-counting optimization allows in-place mutation when there is exactly one reference

However, his decompressor ran about 10x slower than the zstd CLI — a reminder that Lean is still a high-level language, not yet competitive on raw performance.

The Current Boundary: Assembly Verification Doesn't Scale Yet

A more ambitious direction: proving equivalence between optimized assembly code and verified Lean code. AWS has developed LNSym — an AArch64 semantics and simulator in Lean.

Langley tested this path. The result: the simple popcount example in the LNSym repo, which uses bv_decide (a certifying SAT solver), consumed more memory than his machine had. Tiny functions work, but both he and the LLMs could not scale to larger functions.

This is the clearest current boundary: high-level code proofs work, but optimized assembly proofs don't.

What This Means for Developers

Short-term: No Longer Academic-Only

LLMs have lowered the proof barrier from "10x effort" to something an individual developer can experiment with. Invariants that previously existed only as comments (or in a maintainer's head) can now be mathematically proven at an acceptable cost.

Medium-term: A New Class of Programming Language

The most exciting line in Langley's post: "we, practically speaking, have a new type of programming language available to us." Dependent types have existed for decades but have been confined to academia by the proof burden. LLMs may change that equation.

Long-term: Bug-Free Code, No Tests Required?

Not so fast. The big open questions remain:

Can proofs scale to systems with hundreds of thousands of lines?
What if an LLM generates a proof that type-checks but proves the wrong thing?
How much does maintaining proofs cost when the code changes?

But the question has shifted from "is this feasible?" to "when will it be good enough?"

Takeaways

LLMs have reduced formal verification proof costs from "10x effort" (seL4) to individual-level feasibility — 20 minutes for a complex proof, $20/month subscription.
Adam Langley verified Zstandard's entire FSE table construction algorithm in Lean using LLMs — four universal properties, not just unit tests.
Dependent types still carry a performance penalty (10x slower) but LLMs are making them dramatically more practical to use.
Assembly verification still doesn't scale — this is the current frontier, even with LLM assistance.
This doesn't replace testing — it's an additional assurance layer for code where bugs have catastrophic consequences: crypto, kernels, safety-critical systems.

Content assisted by AI (Amy 🌸). Reviewed by the author.