Proof Automation with LLMs in Lean: A Zstandard Decompressor Case Study

Proof Automation with LLMs in Lean: A Zstandard Decompressor Case Study

Takeaway

LLMs now provide sufficient proof automation to make dependently-typed languages like Lean practical for real‑world software, as evidenced by a Lean implementation of a Zstandard decompressor whose FSE table construction proofs were generated automatically in about twenty minutes.

Why proof automation matters

Dependent types allow encoding rich invariants, but historically the proof effort has been prohibitive. The seL4 retrospective found engineers spent about ten times as much time proving as designing and implementing, ending up with more than twenty lines of proof code for each line of C code. This overhead has kept dependent‑type programming niche.

How LLMs change the equation

Because proof irrelevance means only the existence of a proof matters, LLMs can search for proofs without human guidance. The author’s limited tests show LLMs can avoid blowing up the type checker while finding proofs. In the Zstandard project, the FSE table construction function was proved correct automatically, using only a fraction of a $20/month LLM quota.

Lean features used in the Zstandard decoder

Lean is a strict, purely functional language with do‑notation that supports imperative‑style programming, and it can mutate arrays in place when the reference count is one. The decoder illustrates these properties:

  • A function readExact returns a byte array whose size is known in the type (IO {ba : ByteArray // ba.size = n}).
  • When indexing into that array, a proof obligation arises that the array is non‑empty. The proof uses blockBytes.property (the size equality from readExact) and a lemma BlockHeader.contentSize_rle that shows contentSize = 1 for the RLE block type, allowing Lean to verify the index.

Zstandard background and the FSE entropy coder

Zstandard is an LZ77‑style compressor that uses Huffman coding for literals and a higher‑compression entropy encoder called Finite State Entropy (FSE) for back‑reference offsets and lengths. FSE builds a state table from symbol probabilities; the table size is a power of two determined by an accuracyLog parameter. Each state stores:

  • the symbol it emits,
  • the number of bits to read from the bitstream,
  • a baseline state that is added to those bits to obtain the next state. The RFC provides test vectors for the table construction algorithm, which the author turned into unit tests and then into universal properties proved in Lean.

Universal properties proved for the FSE table constructor

Assuming ofDistribution accuracyLog probs = some t, the following hold:

  1. t.entries.size = 2 ^ accuracyLog (the table has the correct size).
  2. For each symbol s, the number of states assigned to s equals probCells probs[s] (the count matches the probability).
  3. For every state, reading nbBits bits and adding the baseline yields a valid state number (< 2 ^ accuracyLog).
  4. For every symbol with non‑zero probability and every target state, there exists exactly one state of that symbol that can reach the target state. These properties are exactly the assumptions needed by an optimized decoding inner loop.

Verified assembly aside

The author notes AWS’s LNSym project, a semantics and simulator for AArch64, which could be used to prove equivalence between optimized assembly and Lean functions. If successful, LLMs could then optimize the assembly without introducing functional bugs, making verified assembly "cheap" in the same way proof automation has made dependent types cheaper.

Community reactions

  • One commenter observed that LLMs tend to overclaim unless forced to use libraries like Mathlib, and that without a proof obligation they will not "go the extra mile" to produce a genuine proof. {Jhsto}
  • Another agreed that LLMs + theorem provers could make formal methods cheap, but stressed the need for human supervision to prevent drift from specification. {nextos}
  • A commenter argued that proof engineering remains important: posing the problem well is as crucial as finding a proof, and that LLMs help when the foundations are right. {rtpg}
  • Someone noted that verified assembly is already being used in production (e.g., Google’s Fiat Crypto + CryptOpt work) and that a day of CPU time to explore many verified‑correct implementations is not impractically expensive. {keithwinstein}
  • A different viewpoint warned that dependent types do not scale for large systems because maintenance requires refining every type when a new invariant is added, suggesting a layered approach instead. {el_pollo_diablo}
  • Another commenter pointed out that the author’s Lean Zstandard decoder runs about ten times slower than the reference implementation, leaving room for optimization. {eru}

Limitations and outlook

The author acknowledges that the Lean decoder is currently ten times slower than the standard zstd tool, indicating that performance engineering is still needed. They also note that very strong types can cause proof effort to scale poorly in larger systems, and that Lean’s high‑level nature may not suit all domains. Nevertheless, the combination of dependent types and LLM‑driven proof automation is presented as a new, practically available point in the design space of programming languages.

Conclusion

Proof automation via LLMs has reached a stage where it can discharge non‑trivial proof obligations in Lean with modest cost, making dependent‑type programming feasible for everyday software engineering tasks such as implementing a Zstandard decompressor.

Sources