Solving VeriContest with a Lean-Backed Rust Verifier
Traian Serbanuta, Jun Xu, Andrei Stefanescu, Cosmin Radoi
cs.LO
Oct 2, 2026 · v1
cs.AI cs.SE
TL;DR
Translates Rust code and Verus specifications into Lean 4 theorems, which LLM agents prove with Lean's kernel as the final check.
Abstract
VeriContest is a benchmark of 1007 competitive-programming problems in Rust, each with a Verus specification, a judge-accepted solution, and a Verus proof. Its authors report that proof generation is the bottleneck for frontier models: given the specification and the code, the best model produces an accepted Verus proof for 13.95% of the problems on the first attempt. We report on solving the same proof-generation task with Rust-Prover, a verifier for Rust backed by Lean 4. The Verus specification and the Rust code are restated and translated into Lean, each specification becomes a theorem, and agents prove the theorems with Lean's kernel as the final check. All 1325 theorems of all 1007 problems were proved. 1259 of them were proved in one run of under 32 hours on Claude Opus 5.5, at a median of 3.2 minutes and $1.17 per proof, and 70% of them on the first iteration. The restated specifications were checked against the benchmark's test suites, and reviewed where no suite applies. None was wrong or weakened. The translated Lean programs were run on 21,413 of the benchmark's test cases and produced the same output as the Rust programs on every one. Across four Claude and four GPT models at five reasoning-effort settings, every current frontier model proves nearly all of a ten-theorem sample at every setting, and more effort raises the cost without raising the number of proofs. The cheapest Claude setting, Sonnet 5.5 at low effort, proves all of the 50 hardest theorems. We also rerun the benchmark's own Verus protocol with Claude Opus 5.5 on the 50 problems with the longest reference proofs. Opus 5.5 alone fails to prove one of them.
Problem
VeriContest is a benchmark of 1007 Rust competitive-programming problems with Verus specifications. Its authors report proof generation as the bottleneck, with the best model reaching 13.95% pass@1 on ProofGen.
Approach
Rust-Prover restates each Verus specification as an executable Rust spec, using a transpiler where possible and an agent otherwise. It then translates the code and spec into Lean 4, where each spec becomes a theorem. Automated tactics and LLM agents prove the theorems, and Lean's kernel checks them. The restated specs are validated against the benchmark test suites or by review, and the translated Lean programs are differentially tested against the Rust programs.
Results
All 1325 theorems across 1007 problems were proved using only Lean's standard axioms. In one run, 1259 proofs took a median of 3.2 minutes and $1.17 each, with 70% accepted on the first iteration. Most frontier models prove nearly all of a 10-theorem sample, and Sonnet 5.5 at low effort proves all 50 hardest theorems.
| Per proof | Median | Mean | 90th pct | Max |
|---|
| Time | 3.2 min | 4.1 min | 7.7 min | 69.7 min |
| Iterations (budget 40) | 1 | 1.47 | 3 | 7 |
| Cost | $1.17 | $1.28 | $2.22 | $5.67 |
Per-proof statistics for the main Claude Opus 5.5 run