# CompCert4Lean: Porting a Verified C Compiler to Lean in Six Weeks with Parallel Coding Agents

> CompCert4Lean ports CompCert's verified C compiler to Lean in six weeks via parallel LLM agents, discharging all 4,908 proofs and enabling 11.7% faster agent-driven optimizations.

- **Source:** [arXiv](https://arxiv.org/abs/2611.21084)
- **Published:** 2026-11-21
- **Permalink:** https://picx.dev/p/uvy32A
- **Whiteboard:** https://picx.dev/p/uvy32A/image

## Summary

# CompCert4Lean: Porting a Verified C Compiler to Lean in Six Weeks with Parallel Coding Agents

## Summary (Overview)

- **CompCert4Lean** is a large-scale port of CompCert 3.17's verified compiler core from Rocq (Coq) to Lean, completed in approximately six weeks by one expert directing parallel LLM coding agents
- The port covers the full typed CompCert C abstract syntax through x86-64 assembly, discharging all **4,908 recorded proof obligations** without project-specific axioms, and produces executable Linux binaries
- The migration workflow partitions the development along dependencies, audits translated definitions and theorem statements before large-scale proof reconstruction, then reconstructs proofs in parallel against stable interfaces
- Optimization campaigns show the Lean port enables better agent-driven improvements: GPT-6-astra achieved **11.7% lower runtime** on Lean versus 2.3% on Rocq across 29 small-tests programs, while preserving the end-to-end correctness theorem
- Only **3 of 1,071 human interactions** supplied technical direction; 88.8% concerned workflow and coordination

## Introduction and Theoretical Foundation

The paper addresses the challenge that while Lean has made substantial progress as a platform for formalized mathematics, a substantial body of mature program-verification infrastructure remains available only in Rocq. CompCert is the prominent example: an optimizing C compiler with a machine-checked proof of semantic preservation from C to assembly, embodying years of proof engineering.

**Key motivation:** Bringing CompCert to Lean would make existing verification work reusable within the Lean ecosystem, enabling new developments to build on its language semantics, memory model, and correctness theorems without reconstructing those foundations.

**The correctness obligation** is formally specified as:

$$
\begin{array}{c} \forall p: \text { Csyntax.program }, a: \text { Asm.program }, \xi , \\ \text { compile } (p) = \text { OK } (a) \implies \text { BackwardSim } \big (\mathcal {C} _ {\xi} (p), \mathcal {A} _ {\xi} (a) \big). \end{array}\tag{1}
$$

where $C_{\xi}$ and $\mathcal{A}_{\xi}$ are the source C and target assembly operational semantics under the same external-call interface $\xi$.

**Trusted computing base:** The Lean kernel and its standard axioms (propext, Classical.choice, Quot.sound) replace the Rocq kernel. The source and target semantics, external-call interface, and unverified code (preprocessor to linker) remain in the trusted base.

## Methodology

### Migration Workflow (Seven Stages)

1. **Resolve migration gates**: Investigate representation and interface choices with broad consequences; risk discovery identified 30 issues informing 5 feasibility gates
2. **Migrate definitions in parallel**: Partition dependency graph into 166 units (154 source components, 12 shared providers) with canonical owners
3. **Audit & repair definitions**: Independent parallel agents compare translated definitions/statements with Rocq source; first audit found 1,091 statements reduced to True
4. **Reconstruct proofs in parallel**: Automated agents work from an inventory of 4,908 obligations with bounded attempts and partial acceptance
5. **Finalize remaining proofs**: Human-guided agent sessions handle difficult obligations (471 remained when automatic reconstruction stopped)
6. **Integrate, validate, and optimize**: Connect verified core to executable toolchain producing Linux x86-64 binaries

### Key Technical Decisions

**Infinite trace representation** (due to Lean 4.33's coinductive mechanism supporting predicates in Prop, not data in Type):

```lean
abbrev TraceInf (Event : Type) := Nat -> Event
def head (stream : TraceInf Event) : Event := stream 0
def tail (stream : TraceInf Event) : TraceInf Event := fun index => stream (index + 1)
def cons (event : Event) (stream : TraceInf Event) : TraceInf Event
| 0 => event
| index + 1 => stream index
```

**Algorithm 1** handles parallel definition migration with iterative correspondence auditing, using integration checks enforcing canonical ownership and restrictions on proof escapes. **Algorithm 2** handles automated proof grinding with partial acceptance and bounded retries, grouping up to four related proof obligations per batch.

## Empirical Validation / Results

### Implementation Size

| Component | Lean files | Lines | Completed obligations |
|---|---|---|---|
| Foundations and libraries | 34 | 64,557 | 1,266 |
| Floating-point development (Flocq) | 24 | 51,178 | 554 |
| Common semantics and infrastructure | 18 | 44,081 | 799 |
| Typed-C frontend and proofs | 17 | 46,383 | 437 |
| Backend transformations and proofs | 56 | 136,448 | 1,516 |
| x86-64 backend and configuration | 21 | 47,439 | 324 |
| Pipeline composition and correctness | 3 | 1,877 | 12 |
| **Migrated core subtotal** | **173** | **391,963** | **4,908** |

### Correctness Results

All 139 applicable CompCert small-tests pass at both O0 and O2, plus 20 correctness executions across six SPEC CPU2026 programs. Differential testing shows:
- **Identical RTL after all nine stages** for 18,807 programs at O2 and 18,808 at O0
- **Bit-identical results** on 37.4 million specification-function inputs
- 37 output discrepancies explained (2 undefined-behavior cases, 35 mixed-compiler ABI cases)

### Performance Results

| Benchmark | Inputs | Program runtime (Lean/CompCert) | GCC/CompCert | Compilation O0 | Compilation O2 |
|---|---|---|---|---|---|
| Small-tests | 29 | 1.004 | 0.796 | 2.16 | 2.18 |
| LBM | 2 | 0.977 | 0.651 | 1.96 | 1.61 |
| SQLite | 1 | 1.001 | 0.990 | 1.71 | 1.84 |

### Optimization Campaign Results

| Model | Small-tests runtime (Rocq/Lean) | SPEC runtime (Rocq/Lean) | Compilation time (Rocq/Lean) | New verified passes (Rocq/Lean) |
|---|---|---|---|---|
| GPT-6-astra | 0.977 / 0.883 | 0.978 / 0.931 | 1.054 / 2.054 | 0 / 3 |
| DeepSeek 4.1 Flash | 0.992 / 0.950 | 0.977 / 0.911 | 1.055 / 1.866 | 0 / 0 |
| Kimi K3.1 | 0.994 / 0.977 | 0.981 / 0.985 | 1.051 / 2.001 | 0 / 0 |

### Migration Cost

- 12,435 distinct sessions, 83.53 billion recorded tokens (93.75% cached input)
- Review and repair accounted for ~59% of recorded tokens
- Only 29,565 tokens of human-authored prompts across six weeks

## Theoretical and Practical Implications

**Theoretical contributions:**
- First compiler implemented and verified in Lean covering full typed CompCert C abstract syntax to x86-64 assembly
- Demonstration that dependency-based partitioning with semantic review before large-scale proof reconstruction reduces error propagation in parallel migration
- Evidence that workflow coordination (88.8% of interactions) rather than technical direction enables large-scale migration

**Practical implications:**
- The Lean port enables agents to produce 106 candidate variants completing full compiler and proof builds (vs. 40 in Rocq), giving more opportunities to evaluate and refine optimizations
- New verified passes (path splitting, loop unrolling, instruction scheduling) were developed autonomously by agents in Lean
- The workflow could make other Rocq-based tools available in Lean with manageable human effort

## Conclusion

CompCert4Lean demonstrates that one expert directing parallel LLM agents can migrate a verified compiler from Rocq to Lean in approximately six weeks, with only three messages supplying technical direction. The workflow combines dependency-based parallelism, correspondence audits, and proof reconstruction against stable interfaces.

The optimization campaigns show that all three models achieved larger small-tests runtime reductions in Lean while retaining the end-to-end correctness theorem, suggesting that agent-assisted migration could make other Rocq-based tools available in Lean while opening opportunities to extend their verified infrastructure. The authors note that one campaign per environment cannot separate the effects of model capability, proof automation, repository structure, and search choices—a limitation that invites future investigation.

---

_Markdown view of https://picx.dev/p/uvy32A, served by PicX — AI-generated visual whiteboard summaries of research papers._
