NTH

Scaling Lean Theorem Proving for Real-World Code Verification

AuthorsDebargha Ganguly, Divya Raghunathan, Dejan Jovanović, Vikash Singh, Soonho Kong, Aaron Tomb, Aman Goel, Ferhat Erata, Sam Bayless

AffiliationsCase Western Reserve University · Amazon Web Services

November 8, 2026 2 min read
Watch on YouTube
The one-line take

EasyProver tackles Lean proofs at scale and introduces harder verification challenges grounded in real Rust code.

Key results

99.6%
PutnamBench

EasyProver proves 669 of 672 problems.

99.5%
NTP4VC

EasyProver resolves 597 of 600 verification conditions by proof or refutation.

189
VERINA tasks resolved

EasyProver resolves all tasks in the benchmark.

2,045
Validated Rust–Lean program pairs

Generated and differentially validated by the AEGIS pipeline.

11,533
Candidate specifications

Generated by AEGIS for translated program instances.

52.7%
AEGIS sample proof rate

EasyProver proves 1,054 of 2,000 statements within a 30-minute per-statement budget.

What the paper found

Scaling Lean Theorem Proving for Real-World Code Verification introduces EasyProver, a Lean 4 proving runtime that uses Anthropic’s off-the-shelf Fable-5 model without fine-tuning. Its search combines recursive agents with isolated contexts, asynchronous delegation, parallel tactic probing, and InfiniLean, a stateless, elastic elaboration service; accepted proofs are independently checked by Lean’s kernel. EasyProver reaches 99.6% on PutnamBench, resolves 99.5% of NTP4VC verification conditions, and resolves all 189 VERINA tasks, by proving claims or their negations. The paper’s second contribution, AEGIS, automatically turns competitive-programming solutions into verification tasks: it translates safe Rust into Lean with Aeneas, differentially validates program behavior, and assigns frozen specifications kernel-checked proofs or refutations. The pipeline produces 2,045 validated Rust–Lean program pairs and 11,533 candidate specifications, with implementation-level obligations involving fixed-width arithmetic, explicit failures, loop invariants, casts, and mutation. On a stratified sample of 2,000 statements, EasyProver proves 1,054, a 52.7% success rate within a 30-minute budget per statement. This contrast shows that AEGIS creates challenging tasks even where established benchmarks are nearly saturated; its checked labels can also support prover evaluation and reinforcement learning from verifiable rewards.

Original abstract

We present EasyProver, a Lean proving system built from recursive agents with isolated contexts, asynchronous search, parallel tactic probing, and an elastic elaboration service. Using an off-the-shelf frontier model with no additional training, it proves 669/672 PutnamBench problems and all six IMO 2026 formalizations and resolves 597/600 NTP4VC verification conditions and all 189 VERINA tasks by proof or refutation. Because these benchmarks are close to saturation, we also introduce Aegis, which converts competitive programming problems into much harder verification tasks over real implementations. The pipeline writes safe Rust solutions, translates them into Lean with Aeneas, generates specifications, and labels each frozen statement with a kernel-checked proof or refutation. It produces 2,045 differentially validated Rust-Lean program pairs and 11,533 candidate specifications. Unlike hand-written benchmarks, these tasks carry implementation-level obligations from fixed-width arithmetic, explicit failure, generated loops, casts, and functionalized mutation. On a stratified sample of 2,000 statements, EasyProver proves 1,054 (52.7%) within a 30-minute budget per statement. The same tasks can also be used to benchmark other provers and as rewards for reinforcement learning.

Read the original paper

More in AI Reasoning

Browse all 51 papers →