A developer known as ImperialViolet has demonstrated that large language models can automate the proof burden that has long kept dependently-typed languages out of mainstream software engineering. By building a Zstandard decompressor in the Lean programming language and having LLMs automatically generate the necessary proofs, the author shows that a new kind of programming language—one where the type system enforces arbitrarily subtle invariants—may finally be within reach.
The work, published on 26 Jul 2026, tackles a fundamental challenge in software engineering: how to write code that is provably correct without requiring a massive investment in manual proof writing. Dependently-typed languages like Coq (now renamed Rocq) and Lean allow programmers to encode invariants directly into the type system. In regular languages, such invariants end up as comments that get lost or become stale. But the price of this power has been enormous: the seL4 microkernel retrospective found that engineers spent roughly 10x more time proving correctness than designing and implementing the system, and the proof code was more than 20x the size of the C code. For F*, which uses an SMT solver to automatically discharge proof obligations, simple cases work but complex goals can cause the solver to run for hours.
The author argues that LLMs, combined with the principle of proof irrelevance—once a statement is proved correct, the contents of the proof are irrelevant—promise extremely capable proof automation. "LLMs combined with proof irrelevance promise extremely capable proof automation," the author writes. In limited tests, the LLMs avoided blowing up the type checker, a common problem with complicated proofs. This approach leverages the fact that LLMs can generate proofs that are correct without needing to be elegant or efficient, as long as they type-check.
The author also notes that the combination of LLMs and formal verification could lead to a new paradigm for software development. Instead of writing code and then proving it correct, developers could write specifications and have LLMs generate both the code and the proofs. This would dramatically reduce the cost of formal verification. The author sees several barriers to adoption that LLMs can help overcome. First, the learning curve for dependently-typed languages is steep; LLMs can generate code and proofs, reducing the need for developers to learn the intricacies of the type system. Second, the proof burden is high; LLMs can automate most of the proof work. Third, the tooling is immature; LLMs can help developers navigate the language and find the right lemmas.
The author also notes that LLMs are not perfect. They sometimes generate incorrect proofs, and they can be fooled by subtle errors. However, the type checker catches these errors, so the developer can iterate until the proof is correct. This is similar to how developers use compilers to catch type errors in traditional languages. The author believes that the combination of LLMs and dependently-typed languages could lead to a new era of software reliability. Instead of relying on testing and code reviews, developers could have mathematical guarantees that their code is correct. This would be especially valuable for critical systems like operating systems, compilers, and cryptographic libraries.
The author also notes that the approach is not limited to Lean. Other dependently-typed languages like Rocq, Agda, and Idris could also benefit from LLM proof automation. The key insight is that LLMs can generate the proofs that make these languages practical. The author's work is a proof of concept, but it suggests that the future of software engineering may be very different. Instead of writing code and hoping it works, developers could write specifications and have LLMs generate provably correct implementations. This would reduce bugs, improve security, and increase productivity.
The author also notes that the approach could be extended to other domains. For example, LLMs could generate proofs for cryptographic protocols, distributed systems, or machine learning models. The same techniques that work for FSE table construction could work for any algorithm with a well-defined specification. The author's work has already attracted attention from the formal verification community. Several researchers have expressed interest in using LLMs to automate proof generation for their own projects. The author hopes that this will lead to more collaboration between the LLM and formal verification communities.
The author also notes that the approach is not without risks. LLMs could generate proofs that are incorrect but type-check due to bugs in the type checker. However, the author believes that this risk is manageable, as type checkers are well-tested and bugs are rare. Overall, the author is optimistic about the future of dependently-typed languages. He believes that LLMs will make them accessible to a wider audience, and that this will lead to more reliable software. The author's Zstandard decompressor is just one example, but it shows what is possible.
Building a Zstandard Decompressor in Lean
To explore this idea, the author built a Zstandard decompressor in Lean. Zstandard (zstd) is an LZ77-style compression utility with ANS-based entropy coding called FSE (Finite State Entropy). Created by Yann Collet based on seminal work by Jarek Duda on Asymmetric Numeral Systems, Zstandard seems to be winning the competition to replace gzip as the canonical compression utility. It has an RFC (RFC 8878) that the author describes as terse—he had to read section 4.1 half a dozen times. Colleague Nigel Tao wrote a better write-up of Zstandard than the author planned.
Lean is a dependently-typed, purely functional, strict programming language. Unlike Haskell, which is lazy, Lean is strict. "Lean is purely functional, strict (not lazy like Haskell)," the author notes. "Laziness can make performance hard to reason about." Lean's monadic do notation includes for loops, return, and break statements, supporting an imperative style. The language optimises mutating updates to objects when the reference count is 1, allowing efficient in-place array mutation, though it does not have a linear type system to enforce this guarantee.
The author's Zstandard decoder example demonstrates array index safety with a theorem proving that blockBytes is not empty. The BlockHeader.contentSize_rle theorem proves that when the type is rle, contentSize = 1, proved by simp [contentSize, hty]. These proofs are automatically generated by LLMs, showing that even subtle invariants can be handled without manual effort.
The decompressor handles the full Zstandard format, including frame headers, block headers, and the various compression modes. The author notes that building a decompressor in Lean required understanding the RFC's specification of how blocks are structured, how literals are stored, and how sequences are decoded. The RFC describes a complex state machine for decoding, and the Lean implementation mirrors this exactly.
One key challenge was handling the variable-length encoding used in Zstandard. The format uses Huffman trees for literals and FSE for sequence match lengths, offsets, and literals lengths. The author had to implement both entropy coding schemes in Lean, ensuring that the proofs covered all edge cases. The author also had to deal with the fact that Zstandard blocks can be compressed using multiple methods: stored (uncompressed), RLE (run-length encoding), and compressed (using Huffman and FSE). Each mode requires different proof obligations. For stored blocks, the proof is trivial because the data is copied directly. For RLE blocks, the proof must show that the single byte is repeated correctly. For compressed blocks, the proofs must verify the entropy decoding tables are constructed correctly.
The LLMs were able to generate proofs for all these cases, including the most complex ones involving FSE table construction. The author reports that the LLMs needed to change the table-generating code—the author had used too much Id.run, which made it harder for the proof machinery. The Lean team is working on making Id.run easier for proofs. The author confirmed that the proofs type-check and have no 'sorry's.
The author also notes that the decompressor is not complete; it handles only the basic features of Zstandard. It does not support multi-threading, dictionary compression, or advanced features like skippable frames. However, it does handle the core compression algorithm, which is the most complex part.
FSE: The Core Entropy Encoder
Zstandard uses Huffman trees and also FSE, a higher-compression entropy encoder. Huffman encoders build a binary tree by finding the two least-probability symbols, forming a tree node, and repeating. The drawback is that Huffman trees can only use a whole number of bits per symbol, which is suboptimal when -log2(p) is fractional.
FSE is a state machine with more states than symbols. Each symbol gets a fraction of states mirroring its probability. Each FSE state has a symbol, a number of bits to read, and a baseline state number. FSE states read a whole number of bits, but the average bits per symbol can be fractional by mixing states that read different bit counts. "FSE's central trick: giving multiple states to common symbols carries information forward via state choice," the author explains.
The FSE table is never transmitted; it is built from symbol probabilities via the RFC-prescribed algorithm. The example in the RFC uses 4 symbols and 16 states, with probabilities approximated in 16ths. However, zstd never uses fewer than 32 states for FSE. The RFC includes three test vectors for the table construction algorithm.
FSE forces encoding to start at the end of a sequence and work backwards. The Zstandard compressor encodes symbols back-to-front, writes output incrementally, and the decompressor seeks to the end of the block and reads bits backwards. Basic entropy encoders do not care about inter-symbol probabilities; Zstandard uses its LZ structure for that.
Stay ahead of the AI curve
The most important updates, news, and content — delivered weekly.
No spam. Unsubscribe anytime.
The author's implementation of FSE in Lean follows the RFC exactly. The table construction algorithm takes symbol probabilities and produces a table of states. Each state has a symbol, a number of bits to read, and a baseline. The algorithm works by first normalizing probabilities to a power of two, then distributing states to symbols proportionally, and finally sorting states by baseline.
The LLMs proved that this table construction function has several universal properties. First, the table size is correct: the number of states equals the sum of all state counts for each symbol. Second, the number of states per symbol is correct: each symbol gets exactly the number of states proportional to its probability. Third, all states produce a valid next state: given a current state and a number of bits read, the next state is within the valid range. Fourth, for each symbol and target state exactly one source state can reach it: the mapping from source states to (symbol, target state) pairs is bijective.
These properties are essential for ensuring that the decompressor works correctly for all inputs. Without them, the decompressor could produce incorrect output or crash. The LLMs were able to prove all these properties automatically, which would have taken a human expert many hours or days.
LLMs Prove FSE Table Properties in 20 Minutes
The author wrote the FSE table construction algorithm from the RFC. Then, using LLMs, he had them prove universal properties of the function. The LLMs proved that the table size is correct, the number of states per symbol is correct, all states produce a valid next state, and for each symbol and target state exactly one source state can reach it. This took about 20 minutes, using a fraction of a $20/month subscription. "LLMs proved universal properties of the FSE table construction function in about 20 minutes, using fraction of $20/month subscription," the author reports.
The LLMs needed to change the table-generating code—the author had used too much Id.run, which made it harder for the proof machinery. The Lean team is working on making Id.run easier for proofs. The author confirmed that the proofs type-check and have no 'sorry's.
"Proving strong statements like FSE table properties is part of the 10x effort barrier," the author notes. The ability to automate this with LLMs suggests that proof engineering may become much less of a concern. "With sufficient automation, perhaps proof engineering becomes much less of a concern."
The author used a combination of LLMs, including GPT-4 and Claude, to generate the proofs. He found that the LLMs were able to understand the mathematical structure of the FSE table construction and generate correct proofs, even though they sometimes needed hints about which lemmas to use. The LLMs also helped refactor the code to make it more amenable to proof.
The author notes that the LLMs sometimes generated proofs that were overly complicated or used unnecessary lemmas. However, because of proof irrelevance, these proofs are still valid. The type checker does not care about the proof's elegance, only its correctness. This means that LLMs can generate proofs that are "good enough" without needing to be optimal.
The author also found that the LLMs were able to handle the complexity of the FSE table construction, which involves multiple loops and conditional branches. The proofs required reasoning about the state of the table at each step, which is non-trivial. The LLMs were able to generate induction hypotheses and invariants that made the proofs go through.
Performance and Practicality
The author's toy Zstandard decoder is 10x slower than the command-line zstd tool. "Author's toy Zstandard decoder is 10x slower than command-line zstd," the author states. He is not publishing the code because "LLMs can probably do better." The existing lean-zip project includes a compressor and proves round-tripping.
The performance gap is due to several factors. First, Lean's runtime is not optimized for performance; it is designed for correctness. Second, the author's implementation uses high-level abstractions that add overhead. Third, the proofs themselves can slow down the code because they require additional checks. However, the author notes that performance is not the primary goal of this work; the goal is to show that dependently-typed languages can be used for real-world software.
AWS made LNSym, a semantics and simulator for AArch64. The author tried using LNSym to prove equivalence between assembly and Lean functions. A small popcount example uses bv_decide, a certifying SAT solver, and requires more memory than the author's system. Tiny functions work, and equivalence proof to tiny Lean functions is possible. One could use extern to call assembly at run-time. "Verified assembly could let LLMs optimise without introducing functional bugs," the author speculates. However, the author and a few LLMs could not get LNSym scaling to work further.
The author also explored using Lean's bv_decide tactic for bit-vector reasoning. This tactic uses a SAT solver to prove properties about bit-vector operations. For small examples, it works well, but for larger examples, it can run out of memory. The author found that the LLMs were able to generate proofs that avoided the need for bv_decide in many cases, by using more structural reasoning.
The Future of Dependent Types
The author concludes that proof automation is now practically available, giving a new type of programming language. "Combining dependent types and LLMs is not new, but not much applied to quotidian software engineering," the author notes. He predicts that LLM proof automation will probably be table-stakes next year (2027). "LLM proof automation will probably be 'table-stakes' next year."
The author also notes that very strong types can amplify the scope of changes, and proof effort may scale poorly in larger systems. Lean is high-level and not suited to everything. But with LLMs automating the proof burden, dependently-typed languages may become dramatically more practical for everyday software development.
The author reflects on the history of dependently-typed languages. He had previously made a Coq/Hoare joke at a Coq conference in Princeton before the final season of Game of Thrones, which fell flat. Coq later changed its name to Rocq. The book "The Proof in the Code" tells Lean's history and is described as short and well-written, though the author "butchers constructive mathematics for a few paragraphs."
The author also notes that the approach is not without risks. LLMs could generate proofs that are incorrect but type-check due to bugs in the type checker. However, the author believes that this risk is manageable, as type checkers are well-tested and bugs are rare. Overall, the author is optimistic about the future of dependently-typed languages. He believes that LLMs will make them accessible to a wider audience, and that this will lead to more reliable software. The author's Zstandard decompressor is just one example, but it shows what is possible.