acceptodds
Under review as a conference paper at ICLR 2027

ULPBench: Autonomous Formal Verification of Numeric C

Abstract

Machine-checked verification of critical C code, from cryptographic routines in OpenSSL to the seL4 microkernel, has historically demanded months to years of expert effort per component. Large language models (LLMs) are now capable of reasoning about C code and producing proofs in proof assistants such as Lean and Rocq, however these capabilities have largely been demonstrated for isolated pieces of the verification pipeline, such as synthesizing assertions or proving verification conditions, rather than for true end-to-end verification. In this paper, we explore the degree to which autonomous agents can perform end-to-end formal verification for numeric C code. To facilitate this, we introduce ULPBench, our custom verification benchmark consisting of 560 tasks drawn from production numeric C code. For each task, an agent is given a formal C semantics inside a proof assistant and must (i) write an executable functional model, (ii) prove that the C source refines it under that semantics, and (iii) prove a property of the model, such as a bound on floating-point error in terms of unit in last place (ulp). Completing all three stages of a task results in a full end-to-end proof, and each task is provided in both Lean and Rocq. To support the Lean side, we release a port of the CompCert Clight semantics and IEEE-754 binary32/binary64 floating-point semantics to Lean, providing the foundation needed to verify each real-world C program. We evaluate frontier agents, measuring success in end-to-end formal verification, and show that agents are able to autonomously formally verify challenging properties of C code in 36% of our test cases. Finally, we present a case study showing the use of this approach in practice which led to uncovering an unreported defect in CPython's atanh function as well as a defect in a major geospatial algorithm library.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
formal verification, program verification, benchmark, autonomous agents, agentic evaluation, proof assistants, Lean 4, Rocq (Coq), neurosymbolic, libm

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_B5NHOpenReview ↗
Rating
1
Confidence
4
Informativeness
3
Presentation
2
Soundness
1
Read review
Paper summary

This paper introduces ULPBench, a benchmark for evaluating autonomous agents on end-to-end formal verification of production numerical C code. Each task requires an agent to construct an executable functional model, prove that the C implementation refines that model under formal C semantics, and prove a specified property, such as a floating-point error bound. The benchmark contains 560 tasks, each available in Lean and Rocq. The authors also provide a Lean port of CompCert's Clight semantics and IEEE-754 floating-point semantics, together with supporting proof automation. Experiments evaluate three agents on a 100-task subset with a five-hour budget per task, reporting a highest end-to-end success rate of 34% in Lean and 32% in Rocq. The paper analyzes stage-level performance and computational costs, and presents case studies in which verification attempts led to identifying numerical defects in CPython and GeographicLib.

Critical strengths

The benchmark focuses on verification tasks drawn from real production C programs. Establishing the correctness of numerical software used in practice is an important problem, and a benchmark grounded in such programs is a meaningful direction for evaluating verification agents.

Critical weaknesses
  1. Limited contribution beyond the benchmark. The Lean tooling appears primarily to port and integrate established infrastructure, with limited explanation of its technical novelty. The evaluation and case studies are insufficiently supported by the comparisons and methodological details provided below.

  2. Insufficient justification for the proof decomposition. The required executable model and refinement proof may add obligations beyond those needed to establish the target property directly. For the integer square-root example in Figure 1, the intended floor-square-root behavior can be specified by r2≤n<(r+1)2r^2 \le n < (r+1)^2, where nn and the returned value rr are nonnegative and the arithmetic is over mathematical integers. This gives a direct contract without real-valued square roots or rounding conversions. The paper does not explain why the model-based route illustrated with Real.sqrt is preferable, or whether this direct formulation would reduce verification effort.

  3. Insufficient specification detail. Section 4.1 identifies source comments, documentation, and algorithm-derived claims as specification sources, but does not adequately explain how they were formalized and validated. This also makes it difficult to assess whether the case-study findings establish violations of the intended library behavior. At minimum, the relevant specifications and input assumptions should be presented to allow readers to assess these claims.

  4. The evaluation does not separate task difficulty from workflow overhead. Why not let the same agent use VeriFast or Frama-C/WP to express the required behavior as a concise source-level contract and supply the annotations needed to verify it? Such a workflow could avoid an explicit executable model and refinement proof while preserving the target property. Without this comparison on supported tasks under matched budgets and semantic assumptions, failures at refinement may reflect the imposed workflow rather than an inability to verify the requested property.

  5. Incomplete experimental reporting. The number of attempts per task and the treatment of failed runs in cost comparisons are unclear. Appendix F (Full Results) and Appendix G (Successes) contain only headings. Per-task outcomes and a worked verification example would make the results easier to assess.

Questions for authors
  1. Why require agents to construct an executable functional model and prove refinement, rather than let them verify the same target property directly through source-level contracts using VeriFast、Frama-C/WP or even VST? What benefit does this decomposition provide over the agent-plus-verifier alternative?

  2. On tasks supported by both approaches, can the same agent verify properties directly that it fails to establish through the required refinement workflow? A comparison under matched budgets, input domains, target properties, and semantic assumptions would help determine whether the reported refinement bottleneck is intrinsic to the tasks or introduced by the evaluation design.

  3. How were the benchmark specifications constructed, and what evidence supports their correctness as formalizations of the intended behavior? Please explain how the claims and input assumptions were derived and independently checked, with a concrete example connecting the original requirement to its formal specification.

2 comments

Thank you for the detailed review. The revision supplies the missing material you identified, though not the controlled comparison: a worked example, and the specifications and how they were validated. On the decomposition we concede part of your point and defend the rest, below.

Why require a model and a refinement proof at all?

We state a few reasons. The immediate reason is that the extracted Clight AST is often monstrously large and cumbersome to directly reason with for nontrivial functions. This wasn't possible to see in the initial submission as we didn't include many examples nor the dataset, but indeed the median AST (through the typical clightgen generation path) is over 700 lines in our dataset. A model allows for a simplified lean-native object to be used. Also, this model can serve to prove further properties of the same function, or later be composed with other functional models.

Our data do not measure the cost of the no-refinement route. Two observations are relevant. Runs that proved the property of their model but not the refinement are the clearest candidates for a direct proof, and there are two to four per agent and prover. And in the two solved submissions where an agent used the specification's own reference function as its model, the nearest thing in our data to a direct proof, the property became trivial and the refinement proof grew several-fold. We state in Limitations that we ran no direct baseline.

Task difficulty versus workflow overhead: why not Frama-C/WP or VeriFast?

We have not run this comparison, so we cannot answer the second question empirically, and the revision says so in Limitations. A contract-based baseline without a model would be informative, especially for the integer and byte-level half of our tasks, where automated solvers are strong, and we regard it as a valuable next experiment.

How were the specifications built and validated?

We agree this was missing and have added it. Each specification records its source: a statement in the library's own comments or documentation, quoted with its location, or a standard or mathematical definition. Specifications were drafted by AI agents following a written protocol, which the revised AI use statement now says, and validated mechanically. An executable transcription is tested against the compiled C, exhaustively for input spaces up to 2³² and on large samples otherwise. The Lean and Rocq statements are checked for agreement on shared inputs. Every precondition needs an input on which the statement fails without it. A second agent then tries to show the statement false or trivial. We did not review every statement by hand.

As an example, openlibm documents floor as "Return x rounded toward -inf to integral value". Our property statement is that for every finite x the result is finite and equals ⌊x⌋; finiteness is its only assumption. The appendix shows this statement and its proof. Fifteen tasks deliberately state a weaker bound than their source claims, and four are false by construction; the appendix identifies both groups.

Do the case-study findings establish violations of intended behaviour?

We agree that the paper did not divulge the full information on these claims, so we state each one exactly in the appendix.

For cmath.atanh, we prove in Lean that our model of the function returns infinity at 1 + 2⁻⁵¹¹i and that the correctly rounded result there is finite. The only assumption is a finite input away from the poles. The proof concerns a Lean model validated against CPython, since complex arithmetic falls outside the C fragment our benchmark covers; we now say this in the text. For GeographicLib, we prove under the Clight semantics, assuming only that the math-library calls return the values glibc returns, that the library's solver exits without meeting its own convergence threshold on a specific input, and returns a specific distance. That this distance differs from the true one by 227 micrometres, against a documented bound of 15 nanometers, is a separate high-precision computation and not part of the proof. Since the initial submission, the author of GeographicLib has confirmed the issue and planned a fix.

Incomplete experimental reporting

Each task was run once per agent and prover. Runs that did not solve the task are excluded from the time and token figures, which plot each solved task at the cost of its successful run.

Limited contribution beyond the benchmark; novelty of the Lean tooling

The benchmark and its evaluation are the primary contribution. The tooling exists because we knew of no infrastructure for verifying C against a formal semantics in Lean. It is a port only at the level of the semantics, which follows CompCert's deliberately, so that the two can be compared definition by definition. The proof layer above it is not ported from Rocq: an executable interpreter for Clight, proved sound against the semantics, and tactics that perform symbolic execution by evaluating it.

Reviewer_RhuzOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper introduces ULPBench, a benchmark comprising 560 tasks for evaluating autonomous end-to-end formal verification of production numerical C code in Lean and Rocq. A key distinguishing feature of this benchmark is its focus on program refinement, a well-established verification technique used in large-scale interactive theorem proving (ITP) projects, including the formal verification of operating system kernels. Specifically, each task requires an agent to construct a functional model, prove that the original C implementation refines the model, and establish a specified correctness property, such as a floating-point error bound. The authors also develop supporting verification infrastructure for Lean and evaluate frontier coding agents on a 100-task subset, with the best-performing agent achieving a 34% end-to-end success rate in Lean. Finally, the paper presents case studies demonstrating how this verification approach can uncover previously unreported numerical defects in real-world software libraries, including CPython and GeographicLib.

Critical strengths
  1. The benchmark offers a useful complement to existing benchmarks. Despite the relatively unfocused narrative in the Introduction, I am convinced that this benchmark is distinct from existing benchmarks in its focus on program refinement, a standard technique used in practice to verify complex software systems (e.g., operating systems). In particular, the benchmark evaluates agents' capabilities in proposing functional models and conducting refinement proofs, following the conventional verification approach in the field. The adoption of VST, CompCert semantics, and open-source C repositories is representative of established refinement-based verification practices.
  2. Valuable engineering side products. The port of the CompCert Clight semantics and IEEE-754 binary32/binary64 floating-point semantics to Lean, as well as the discovery of large numerical errors in CPython’s math library, are valuable contributions in their own right.
Critical weaknesses
  1. Limited analysis of the general capabilities evaluated by the benchmark. The paper does not sufficiently discuss what general capabilities of LLMs/agents are required to solve the benchmark tasks, beyond proficiency with specific verification tools (e.g., VST) and techniques for verifying numerical C programs. In particular, it remains unclear which general capabilities ULPBench evaluates that are not already substantially covered by existing benchmarks. While the experimental results break down performance across functional modeling, refinement proofs, and property proofs, this analysis remains at the level of verification subtasks rather than identifying the underlying general capabilities of LLMs/agents being evaluated. Such an analysis would help clarify the broader significance of ULPBench as an evaluation of LLM/agent capabilities beyond this particular formal verification setting for numeric C programs over the specific tools.

  2. The C-centric presentation may understate the broader value of the work. The Introduction seems to place excessive emphasis on the C language, whereas ULPBench "explicitly evaluates model construction, C-to-model refinement, and property proofs," which are general capabilities widely required in established verification workflows, rather than techniques specific to C. I understand that the benchmark focuses on C programs partly due to the practical constraints of existing tooling. Nevertheless, I would encourage the authors to discuss, at least conceptually, the broader implications of this work for evaluating LLMs/agents' capabilities in general program refinement techniques beyond the C language.

Questions for authors

The authors list the port of CompCert Clight semantics to Lean as one of their contributions, but it seems unclear how this port was produced. Was it done manually, or was it automated using LLMs/coding agents? In the Limitations section, the authors mention the absence of a VST-like separation-logic-based reasoning system in Lean. If the Clight semantics port was automated using LLMs/agents, could a similar approach be used to automate the porting of VST's reasoning system to Lean? Or are there particular challenges that would make such an effort more difficult?

1 comment

Thank you for the review and for your comment in the discussion. We agree with these two weaknesses you identify and have revised the introduction and the analysis in response. Also, your question about the port is answered below.

Limited analysis of the general capabilities evaluated

We agree, and the revision adds this analysis. Each stage exercises a different capability, none specific to C. The model requires restating low-level code as a pure function; agents mostly transcribed the C, and this stage rarely failed. The refinement requires exact reasoning about program semantics at scale: for a function of about 40 lines, the syntax tree the agent must reason about is 571 lines long. The property requires a mathematical argument and its formalization. A fourth capability runs through all three: the agent is not told that the specification is true, and must decide whether to prove or refute it. All of this has to be sustained in one unassisted run of tens of minutes to hours.

The C-centric presentation understates the broader value

We agree, and have revised the introduction to present refinement as the subject and C as the setting. A task is a program under a mechanized semantics, a specification, and three artifacts to produce; C enters only through the semantics and the front end. We chose it because a trusted semantics already existed and the code is widely deployed, but the same task can be posed for any language with a mechanized semantics. The evaluated tasks already go beyond numerical code: about half are integer and byte-level routines such as hashing, parsing and compression.

How was the Clight port produced? It was largely automated. The port was written primarily by AI coding agents under the direction of one author. The definitions and theorem statements were reviewed by hand, and the proofs were left to the agents. We then validated the result by differential testing against CompCert (Appendix B.1).

Could VST's reasoning system be ported the same way?

We believe so. VST has a mature reference implementation, and our experience with the semantics suggests agents can carry out this kind of translation. Both a program logic and a language's core semantics mostly have strong verification signals for correctness (which is important if one wants to automate their development.) The only difference lies in the validation of agents' work, with programming language semantics being executable, allowing for testing like ours against CompCert. A program logic on the other hand can be proven sound, which is a great guarantee, but only if the theorem statement is valid. Validating of formal theorem statements is a known hard problem [1], so that would require the most human attention.

[1] Robert Pollack. How to believe a machine-checked proof. In Giovanni Sambin and Jan M. Smith, editors, Twenty-Five Years of Constructive Type Theory, Oxford Logic Guides 36, pages 205–220. Oxford University Press, 1998.

Reviewer_HQ62OpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper introduces ULPBench, 560 tasks testing whether AI agents can build a model of real numerical C code, prove it matches the code, and prove specified correctness properties. It supports Lean and Rocq and adds Lean tools for C and floating-point reasoning. The best agent solves 34 of 100 evaluated tasks, while follow-up proof attempts help uncover bugs in CPython and GeographicLib.

Overall, I think this is an interesting paper with good contribution. However, the missing supplementary material (example tasks) and missing appendix (section F and G) made it impossible for me to assess the quality and question how "ready" / "polished" this paper is for publication.

Critical strengths

There have been a lot of efforts trying to formalize and prove properties of programs. The paper has already cited VERINA [1] and others, but this has been an ongoing topic since 2025 [2].

A clear strength of this paper is to measure the agent's ability to finish the entire pipeline, from C code to a functional code and then to the proof. As far as I know, most of the previous work [2] only focuses on a single phase.

[1] Ye, Zhe, et al. "Verina: Benchmarking verifiable code generation." International Conference on Learning Representations. Vol. 2026. 2026.

[2] Miranda, Brando, et al. "Veribench: End-to-end formal verification benchmark for ai code generation in lean 4." (2025).

Critical weaknesses
  1. The appendix is cut off -- Appendix section F and G are just empty. Is this paper rushed?
  2. Related, the author should show more details about this benchmark, such as its grading procedure, code, enough for the reviewers to perform some verification. A successful task + grading procedure could help.
Questions for authors
  1. Do the authors think this type of method can be extended to kernel programming, such as CUDA, Triton, etc.? What are the difficulties there?
  2. Can you provide the missing appendix for the reviewers to fully assess this paper?
1 comment

Thank you for the careful read. We agree the lack of appendices and missing supplementary material made the work very difficult to assess. Our revision adds a worked-out task and the grading procedure. Your question about GPU kernels is answered below.

The appendix is cut off: F and G are empty

We apologise; the two headings were left empty in the submitted PDF. The revision now includes a worked example for floor from openlibm: the C source, the task as the agent receives it, the model the agent wrote, its refinement proof, its property proof, and the size and cost of the run.

Show the grading procedure, code, and a successful task

The revision describes the grading procedure and adds an example task worked out end-to-end. The agent's work is graded by pulling the single Lean file it's told to finalize its solution in. The grader checks that every given part is unchanged (the Clight syntax tree and both theorem statements), compiles the file from scratch in a clean environment, and checks that the model and both theorems depend only on an allowed list of axioms. Comparator is used to check the proofs against the original theorem statements.

Can this extend to kernel programming (CUDA, Triton)?

We believe so, with some extra difficulty compared to C. Our approach needs a formal semantics of the source language, which for C we obtained from CompCert, and we are not aware of anything nearly as established for CUDA or Triton. Dealing with many parallel threads in the semantics would not be easy. We are most excited about the idea of semantics at the level of PTX, the assembly-like language that CUDA and Triton compile to. Verifying this long machine-level code would be very expensive, but the payoff could be great. For example, one could state a theorem that some kernel is batch-invariant (its output for one element does not depend on the rest of the batch). Also, you could compile a Triton and CUDA kernel to PTX and state a theorem that they are equivalent programs on all inputs, leaving the proof to autonomous agents!

Comments on the paper

2 comments

We have uploaded supplementary material with two parts. dataset/ contains the full benchmark, including the C source, specification, and the Lean and Rocq statements for each task, plus a manifest and a README describing the fields. semantics/ contains the Lean development, aka the port of CompCert's Clight semantics, the floating-point library, the executor and its soundness proofs, and a patch that allows clightgen to emit Lean. Build instructions are in the respective READMEs. Thank you for the insightful reviews!

Note Regarding Figure 1

In the last PDF version uploaded, the updated three-box figure showing the C source, Functional Model, and Spec boxes wasn't present. We are able to supply the fixed figure, with the only change being a subtle update to the spec section, it is meant to be illustrative anyway and does not contain experimental info.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.