Clever : A Curated Benchmark for Formally Verified Code Generation
Amitayush Thakur †, Jasper Lee †, George Tsoukalas †, Meghana Sistla †, Matthew Zhao †, Stefan Zetzsche ‡, Greg Durrett †, Yisong Yue ⋆, Swarat Chaudhuri †, ‡ Amazon, ⋆ Caltech · 2025
Read Clever : A Curated Benchmark for Formally Verified Code Generation by Amitayush Thakur †, Jasper Lee †, George Tsoukalas †, Meghana Sistla †, Matthew Zhao †, Stefan Zetzsche ‡, Greg Durrett †, Yisong Yue ⋆, Swarat Chaudhuri †, ‡ Amazon, ⋆ Caltech (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-13938.txt.
Introduction
Amitayush Thakur and co-authors set a hard test for code tools that must not just work but be proved to work. Their 2025 set, CLEVER, holds just over one hundred and sixty tasks in a proof tongue. Each task asks two things: write the spec in form, and write code a proof check can crown as true to that spec. Kept truth specs stay hid; test cases and tool-wrote marks are barred, and specs that leak the code path are cast out.
All outs face the tongue's own check post run. Top chat tools and crew forms all fail to clear the bar whole. Proof-true code is thus a far shore, not a near step. The set gives the field a clean yard stick.
Catalog record
| CREATOR | Amitayush Thakur †, Jasper Lee †, George Tsoukalas †, Meghana Sistla †, Matthew Zhao †, Stefan Zetzsche ‡, Greg Durrett †, Yisong Yue ⋆, Swarat Chaudhuri †, ‡ Amazon, ⋆ Caltech |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 92 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-13938
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Clever : A Curated Benchmark for Formally Verified Code Generation Amitayush Thakur †, Jasper Lee †, George Tsoukalas †, Meghana Sistla †, Matthew Zhao †, Stefan Zetzsche ‡, Greg Durrett †, Yisong Yue ⋆, Swarat Chaudhuri †, ‡ Amazon, ⋆ Caltech Abstract We introduce Clever 1 1 1 CLEVER: Curated Lean Verified Code Generation Benchmark , a high-quality, curated benchmark of 161 problems for end-to-end verified code generation in Lean. Each problem consists of (1) the task of generating a specification that matches a held-out ground-truth specification, and (2) the task of generating a Lean implementation that provably satisfies this specification. Unlike prior benchmarks, Clever avoids test-case supervision, LLM-generated annotations, and specifications that leak implementation logic or allow vacuous solutions. All outputs are verified post-hoc using Lean’s type checker to ensure machine-checkable correctness. We use Clever to evaluate several few-shot and agentic approaches based on state-of-the-art language models. These methods all struggle to achieve full verification, establishing it as a challenging frontier benchmark for program synthesis and formal reasoning. Our benchmark can be found on GitHub as well as HuggingFace . All our evaluation code is also available online . 1 Introduction Interactive theorem-provers (ITPs) [ 11 , 29 , 6 ] are an established technology for engineering high-assurance software, leading to success stories like the CompCert verified C compiler [ 21 ] and the seL4 [ 16 ] verified microkernel. However, writing formal specifications and correctness proofs for software systems can take tremendous effort — for example, the development of seL4 was reported to take 20+ person-years. These costs are a key impediment to the broad deployment of ITP-based formal verification. Recent progress in autoformalization and neural theorem-proving [ 30 , 22 ] has raised hopes of scaling up formal verification [ 37 ] . Most existing work in this area has focused on formalizing and proving statements in pure mathematics [ 38 , 32 ] . However, the software verification setting opens up the challenge of generating code that is formally verified by construction , a problem without a well-studied analog in the mathematics setting. To date, there are a handful of benchmarks [ 9 , 27 , 26 ] for formally verified code generation. However, the formal specifications in these benchmarks tend not to capture the full (natural-language) intent behind the target program and sometimes hint at ways to implement the program. This ambiguity allows a code generator to “cheat” by generating trivial programs or copying code from the specification (see Section A.1 ). In this paper, we address this gap in the prior art with Clever , a high-quality benchmark for formally verified AI-based code generation. Clever includes hand-crafted Lean specifications of 161 programming tasks from the HumanEval benchmark [ 4 ] . It evaluates models in two stages: (1) Specification certification: Given a natural language specification, the model is required to generate a Lean specification and prove that it is semantically equivalent to the ground-truth specification. (2) Implementation certification: Once the model has correctly generated the specification, it is required to generate a Lean implementation and prove that it satisfies the ground-truth specification. A synthesis attempt is deemed successful only when both the proofs generated in the two stages are fully verified by Lean’s type checker. This rigorous pipeline avoids the pitfalls of both automatically generated specifications and test-based supervision. We use Clever to evaluate several state-of-the-art LLMs prompted in a few-shot manner and show that they can only solve up to 1/161 end-to-end verified code generation problem, establishing Clever as a challenging frontier benchmark for program synthesis and formal reasoning. In summary, our contributions include: 1. We introduce Clever , the first curated benchmark for evaluating the generation of specifications and formally verified code in Lean. The benchmark comprises of 161 programming problems; it evaluates both formal specification generation and implementation synthesis from natural language, requiring formal correctness proofs for both. All specifications are manually written to be complete, implementation-agnostic, and free from exploitable artifacts, preventing models from shortcutting the intended semantics. 2. We present an empirical evaluation of several state-of-the-art LLMs and agentic approaches on Clever and show that they all struggle at meeting the benchmark’s goals, establishing the challenging nature of the benchmark. Figure 1 : The two tasks of the Clever benchmark pipeline. Task 1 requires first generating a specification \psi from the natural language statement \nu , then proving an isomorphism between the generated specification and a human-written specification \psi^{*} . Task 2 requires first generating a Lean implementation \pi , then proving its correctness according to the human-written specification. Both of these tasks must be completed correctly (reaching both QED 1 and QED 2) in order for a success to be counted. 2 The Clever Benchmark Clever builds on HumanEval [ 4 ] by adapting 161 2 2 2 Not all problems could be formalized due to limitations in Lean 4 and its supported libraries. of its 164 programming problems for formal verification in Lean 4. Each problem includes a natural language description ( \nu ), a human-authored formal specification ( \psi^{*} ), a Lean function signature ( \pi_{\text{sig}} ) for the implementation, and Lean theorems for both specification equivalence and implementation correctness. All formal specifications are written as non-computable logical propositions — i.e., they use quantifiers and logical connectives that cannot be directly evaluated — ensuring that models cannot copy implementation logic from specification syntax. During evaluation, a model being evaluated on the benchmark starts with the natural-language description \nu . Given this text, the model must generate: (1) a formal Lean specification \psi , expressed as a predicate (a function that returns a Lean 4 proposition i.e. Prop ), (2) a proof that \psi is semantically equivalent to a hidden ground-truth Lean specification \psi^{*} , (3) a Lean implementation 3 3 3 Here, we use the fact that Lean is not just a language for mathematical specifications and proofs but a full-fledged functional programming language. \pi that matches the function signature ( \pi_{\text{sig}} ) and is designed to satisfy \psi^{*} (and hence \psi ), and (4) a formal proof establishing that \pi satisfies \psi^{*} . These steps ( Figure 1 ) form two certification goals: (1) Specification certification: Steps 1–2 verify that the model correctly inferred the intended behavior. (2) Implementation certification: Steps 3–4 verify that the generated implementation satisfies the formal intent. Our staged reasoning setup allows fine-grained diagnosis: models may fail at generating specifications, proving equivalence between the generated and ground-truth specifications, synthesizing implementations, or proving implementation correctness. For example, note that we require the generated implementation \pi to satisfy the ground-truth specification \psi^{*} instead of the model-generated specification \psi . This is because we want the evaluation of \pi to be independent of the ability of the model to generate the correct specification. More generally, failures at the various stages of our pipeline are independently diagnosed using Lean’s type checker. (a) ⬇ -- computable spec def problem_spec -- function signature ( implementation : Nat → Nat ) -- inputs ( n : Nat ) : Prop := -- spec let spec ( result : Nat ) := match n with | 0 => result = 0 | 1 => result = 1 | n