Weekly Paper Notes — one of the top picks from the 2026-11-21 CS paper digest. Area: Programming Languages / Verification.
Authors: Cong Wang (Tsinghua University), Zhiyang Chen and Fan Long (University of Toronto), Martin Rinard (MIT) arXiv: 2611.21084 · PDF · Code
TL;DR #
CompCert is the C compiler with a machine-checked proof that the assembly it emits behaves like the source program. The proof lives in Rocq (formerly Coq). This paper moves the verified core of CompCert 3.17, from typed CompCert C down to x86-64 assembly, into Lean 4. One author did it in about six weeks by directing parallel coding agents (Codex, running GPT-5.6 Sol and then GPT-6-astra).
The port closes all 4,908 recorded proof obligations, and a transitive audit of 75,348 declarations finds nothing beyond Lean’s three standard axioms. It builds working Linux binaries and passes all 139 applicable CompCert small-tests at O0 and O2. Against the original compiler, the RTL is byte-identical after each of the nine RTL stages on all 18,807 programs compared at O2.
Of 1,071 human messages in the project, 951 were coordination and only 3 supplied technical direction. The authors then gave an agent 24 active hours to make the compiler’s output faster without breaking the end-to-end theorem. In Lean it got 11.7% lower runtime on small-tests. Starting from the Rocq original with the same budget, it got 2.3%.
What problem is the paper actually attacking? #
A lot of program-verification infrastructure lives only in Rocq. CompCert (Leroy, CACM 2009) is the best-known piece. Its semantics and memory model underpin work on relaxed-memory concurrency, compositional compilation (CompCertO), the Verified Software Toolchain program logics, the Verasco static analyzer and the CertiKOS kernel. None of that can be imported into Lean, which is where Mathlib and most of the current proof-agent work now sit.
Porting between proof assistants has a history, and none of it scales to this. HOL4-to-Isabelle imports replay primitive inferences, which only works between closely related logics. The Mathlib move from Lean 3 to Lean 4 used Mathport, a semi-automatic translator, and then a lot of manual repair. Iris-Lean, the closest relative, took years of work by a large group. The ITPEval benchmark the paper cites reports 5.2% proof-translation pass@1 for its strongest model on real-library theorems. For scale, the first verified CompCert was 42,000 lines of Rocq and about three person-years. The 154 modules in scope here are 149,038 lines.
Agents add a problem of their own. Throughput comes from parallelism, and a verified development is a dense web of dependencies. Hand different modules to different agents, and a mistake in one shared definition or theorem statement spreads into every proof that depends on it. A clean Lean build does not catch it either. If a statement has been translated into something weaker, Lean will happily check a proof of the weaker statement. The paper’s sharpest example: the first audit found 1,091 theorem statements that had been reduced to True, all of which compiled.
The mechanism: definitions first, audit, then parallel proofs #

The workflow keeps statements and proofs apart so that parallel work happens only against interfaces that have already been checked.
Gates first. Before any broad translation, six rounds of risk discovery turned up 30 issues, grouped into five feasibility gates: representations, floating point, memory and injections, compiler services, and a backend slice. One example is CompCert’s infinite event traces. These are coinductive data, and Lean 4.33 only supports coinductive predicates. The gate settled on representing an infinite trace as a total function Nat -> Event and showed, with checked proofs, that CompCert’s behavior-existence argument still goes through. It also surfaced a quieter problem. Function extensionality identifies streams that are bisimilar, while Rocq’s equality on coinductive data does not. So the port kept CompCert’s named bisimulation relations and proved how they correspond to pointwise equality, rather than assuming the two notions were interchangeable. The paper says the agents proposed and implemented the solutions to all of the gates themselves.
Migrate definitions in parallel. The dependency graph is cut into 166 units: 154 source components and 12 shared providers. Every declaration has one canonical owner. Each agent works in an isolated checkout of a pinned baseline with a disjoint set of writable files. It translates executable definitions, semantic relations and exact theorem statements, and leaves most proofs as recorded obligations. That way downstream translation can run before upstream proofs exist, without any consumer skipping the proof evidence it needs.
Audit before proving. Independent reviewer agents compare definitions, statements, binders and premises against the Rocq source. Repairs happen in parallel against a common snapshot. Any review evidence that depends on a changed provider is invalidated, so a consumer gets re-reviewed even if its own file never changed. This ran for 11 broad rounds. The authors say the last issue with broad downstream consequences turned up in round three, so they probably could have stopped sooner. The audits also catch subtler slips than True. One reviewer found that SetoidList.InA, an inductive relation in Rocq, had been translated as a logically equivalent existential. The proofs still went through, but the constructor and induction interface that downstream proofs relied on was gone.
Grind proofs against frozen targets. Workers take batches of up to four related obligations from the same file. The acceptance check requires the exact target type, no changes to existing definitions, a successful build, and no axioms beyond propext, Classical.choice and Quot.sound. Partial progress is kept. When the human stopped this automatic phase, 471 obligations were left. Those went to human-guided, one-file-per-session work in which, per the paper, the expert managed context and timeouts but supplied no proof ideas. Only two statements needed repair in this phase. For one, the agents built a kernel-checked counterexample: a floating-point theorem had lost its 0 < prec and prec < emax assumptions. Having that counterexample is what justified reopening a frozen statement instead of weakening it.
The practical claim: same trust boundary, same compiler #
The correctness obligation is CompCert’s own backward simulation: whenever compile(p) = OK(a), every observable behavior of the target program is allowed by the source semantics under the same external-call interface. The trusted base stays mostly the same. The parser, assembly printer, assembler and linker are still outside the theorem. The register allocator is still unverified and checked by a verified validator. Three things change. The Lean kernel and its axioms replace Rocq’s. The Lean compiler and runtime replace extraction to OCaml. And there is a new, unverified serialization bridge to the reused OCaml front end.
The proof itself relates the Lean compiler to Lean semantics, so the authors back up fidelity to the original with differential testing. They report three levels of agreement:
- Byte-identical RTL after all nine stages on 18,807 programs at O2 (18,808 at O0). Every mutant pass they built was caught at its own stage.
- Bit-identical results from 202 executable specification functions on 37.4 million inputs, including floating point, which the port models with Lean’s
Float.Modelinstead of Flocq. - 37 output discrepancies, all explained: two undefined-behavior cases and 35 mixed-compiler ABI cases that go away when caller and callee are built by the same compiler.
Generated code runs at parity: the runtime ratio against CompCert on small-tests is 1.004, and GCC sits at 0.796. Compilation itself is about 2.2× slower, which the paper attributes to definitions written for ease of proof. Lean’s @[csimp] mechanism, which swaps in a faster implementation proved equal to the original definition, has already recovered part of that.
Results #
Cost. The project recorded 83.5 billion tokens over 12,435 sessions, 93.75% of them cached input, and coverage is admittedly incomplete. External parallel workers used about 79% of that. Phase 4, review and repair, took about 59%: the definitions-first discipline put most of the spend into auditing. The human wrote 29,565 tokens of prompts over six weeks.
Human role. The authors hand-classified all 1,071 human messages. 951 (88.8%) were workflow: assigning tasks, scheduling reviews, moving between phases. 117 (10.9%) were technical review or discussion. Three (0.3%) gave technical direction. One of the three was a suggestion the agent later corrected, and the other two came from the same register-allocator episode.
Does Lean help agents? Each environment got one 24-active-hour optimization campaign per model (Table 7):
- GPT-6-astra: small-tests runtime 0.977 in Rocq and 0.883 in Lean, SPEC 0.978 and 0.931. In Lean it designed, implemented and proved three new verified passes: path splitting and loop unrolling, which share one RTL code-copying transformation and simulation proof, plus an RTL instruction scheduler. In Rocq it added none. It also completed 106 full compiler-plus-proof builds in Lean against 40 in Rocq, with similar token use.
- DeepSeek 4.1 Flash: 0.992 vs 0.950 on small-tests and 0.977 vs 0.911 on SPEC, from inlining and layout heuristics rather than new passes.
- Kimi K3.1: a small Lean edge on small-tests (0.977 vs 0.994) and a slight Rocq edge on SPEC (0.981 vs 0.985).
The authors are careful about what this shows. With one campaign per model per environment, they cannot separate model capability, proof automation, repository layout and search luck. The Lean candidates also compile about twice as slowly. Some of the tuning (a Lean-only unrolling of division-containing loops, say) was informed by the benchmark workloads, though inspection found no benchmark-name or input matching.
Why this matters #
The headline number is six weeks. The more reusable result is the shape of the workflow: freeze interfaces, audit statements independently, and only then scale proof search. That is the same discipline a careful team lead would impose on human contributors, and it was needed for the same reason. In this setting, the expensive failures were translations that compiled but said less than the original, and proofs that failed outright were the cheap ones. 1,091 statements quietly turned into True is a figure anyone running agents on a large codebase should remember, verified or not.
Two follow-ups are obvious. The first is a mechanized equivalence between the Rocq and Lean developments, which would replace the differential-testing argument with a theorem. The second is pointing the same workflow at the other Rocq systems built on CompCert’s semantics, such as VST, CompCertO and CertiKOS. If agents really do extend verified code faster in Lean, those ports compound. The optimization campaigns hint at that, but with only three models and one run each, they don’t establish it.
Read alongside #
- Xavier Leroy, “Formal verification of a realistic compiler”, CACM 2009: the original CompCert.
- Koenig and Shao, CompCertO, PLDI 2021: compositional compilation built on CompCert’s semantics, a natural next port.
- de Medeiros et al., Iris in Lean, 2026: the multi-year, mostly human Rocq-to-Lean port to compare against.
- Ringer et al., Proof repair across type equivalences, PLDI 2021: the pre-LLM approach to keeping proofs alive when definitions change.
- Partial Borrows in Rust, same week: another mechanized-semantics paper (Aeneas in Rocq) that a Lean port of this kind would affect.
Links #
📄 arXiv abstract · 📄 PDF · 💾 fanlong/compcert4lean
Part of the Weekly CS Paper Digest series. Summary written from a close read of the preprint; figures cropped from the arXiv PDF and reproduced here under fair use for educational commentary.