acceptodds
Under review as a conference paper at ICLR 2027

Lacerta-Bench: Evaluating Provably Correct and Efficient Binary Generation

Abstract

Code-generation benchmarks typically evaluate programs using finite test suites, while formal-verification benchmarks usually prove properties of source code. We study the joint evaluation of executable efficiency and machine-checked correctness of the emitted binary. We introduce Lacerta, a Lean 4 framework for reasoning about binary programs, alongside Lacerta-Bench, a benchmark built on Lacerta for evaluating binary generation from high-level specifications. Lacerta-Bench comprises 400 tasks derived from competitive-programming problems, each with a formal specification; batch tasks use a target-independent byte-stream interface. Models generate a binary program together with a machine-checked proof of its correctness, while deterministic gas ranks programs on their efficiency. We evaluate six language models on 100 problems under a 30-minute budget: only one system produces any accepted proof, on 20 problems. On ten of these problems with five eight-hour attempts each, 98% of attempts pass the public samples but only 55% yield a proved, scoreable artifact. Accepted binaries can differ in gas by orders of magnitude, so proof completion and execution efficiency distinguish different aspects of generated programs.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Formal verification, Lean 4, binary program synthesis, machine-checked proofs, LLM benchmark, code generation, proof-carrying code

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_FyWJOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces LACERTA, a Lean framework for reasoning about WASM binaries, and LACERTA-BENCH, 400 formalized CSES tasks. Models submit a binary with a correctness proof, and accepted submissions are compared by deterministic gas. Six models are tested on 100 tasks with 30-minute budgets and ten tasks with repeated eight-hour attempts. The results distinguish sample passing, proof completion and execution efficiency.

Critical strengths
  1. Requiring a proof about the submitted WASM module and its byte interface is a useful angle. Keeping the specification and codec fixed allows different implementations to be judged against the same requirement.
  2. The task formulation is clear. Section 2.1 separates the semantic specification, byte codec and binary behavior, and the Missing Number example helps explain what the model must establish.
Critical weaknesses
  1. The long-budget evaluation provides limited support for the model comparisons. The 100-task study provides breadth, but the detailed efficiency, cost and repeated-attempt comparisons cover ten tasks. Five runs per task help characterize repeatability, but do not establish how the comparisons extend across the benchmark. Figure 6 provides useful timing information, yet the paper does not summarize each model’s average completion time alongside its completion rate and final gas quality. This makes it difficult to assess the eight-hour allowance and understand the trade-off between completing quickly and producing a better solution. These limitations reduce my confidence in the main empirical comparisons.
  2. The proposed leaderboard score is not evaluated in the empirical study. Section 3.2 and Eq. (8) define logarithmic per-test scores that are averaged over tests, while the experiments use total and relative gas. Appendix A.6 acknowledges this distinction, but does not show whether it changes the comparisons. These aggregations can produce different orderings. Since the scoring protocol is part of the contribution, leaving its relationship to the reported results unresolved is a substantive gap in the benchmark evaluation.
Questions for authors
  1. Completion time and quality: What is each model’s mean time to a complete, scoreable solution among successful attempts, with its completion rate reported alongside that average? On shared tasks, how does completion time relate to final gas quality, and do these observations support the eight-hour allowance?
  2. Task coverage: Using the existing results, what task-level uncertainty can be attached to the ten-task comparisons? How sensitive are the main differences between models to the tasks included?
  3. Does applying Eq. (8) to the evaluated submissions preserve the main comparisons? Please clarify why total and relative gas were used instead of the proposed leaderboard score.
  4. Failure interpretation: Do the existing evaluation records show how unproved binaries perform on the full functional tests? Separating incorrect outputs, execution-limit failures and binaries that pass those tests but lack proofs would help explain the sample/proof gap.
4 comments

Thank you for the careful review and for your kind words on the task formulation and the worked example. We found your questions precise and constructive, and we have revised the paper accordingly. We answer each point below.

Weakness 1 and Question 1.

The long-budget evaluation provides limited support for the model comparisons. The 100-task study provides breadth, but the detailed efficiency, cost and repeated-attempt comparisons cover ten tasks. Five runs per task help characterize repeatability, but do not establish how the comparisons extend across the benchmark. Figure 6 provides useful timing information, yet the paper does not summarize each model's average completion time alongside its completion rate and final gas quality. This makes it difficult to assess the eight-hour allowance and understand the trade-off between completing quickly and producing a better solution. These limitations reduce my confidence in the main empirical comparisons.

Completion time and quality: What is each model's mean time to a complete, scoreable solution among successful attempts, with its completion rate reported alongside that average? On shared tasks, how does completion time relate to final gas quality, and do these observations support the eight-hour allowance?

We appreciate this point. We agree that the eight-hour comparisons characterize ten tasks, and the revised paper states this more plainly. The 100-problem evaluation provides breadth, while the ten-problem evaluation provides depth through repeated attempts. As requested, Appendix B.6 now reports for each system the number of scoreable artifacts, their mean and median completion time, and their gas quality (Table 10). Completion time and relative gas are essentially unrelated (Spearman ρ=0.05\rho = 0.05), so longer attempts do not yield more efficient solutions. The eight-hour allowance therefore matters for completion rather than quality, since about a fifth of the scoreable artifacts were completed after four hours, mostly by the systems with lower completion rates. In revising Section 4.1, we also corrected an error in the submitted description. The ten problems were not sampled at random but selected to span eight CSES sections and a range of difficulty, and the ten-task comparisons should be read in that light. No reported number changes.

Question 2.

Task coverage: Using the existing results, what task-level uncertainty can be attached to the ten-task comparisons? How sensitive are the main differences between models to the tasks included?

We appreciate this question. Appendix B.6 now reports paired task-bootstrap intervals for the main comparisons, resampling the ten tasks with replacement while keeping all attempts and systems for each sampled task (Table 11), together with leave-one-task-out checks. The differences among the three leading systems lie within the task-level uncertainty, and removing a single task can change their order. Their separation from DeepSeek and GLM, by contrast, is robust to the choice of tasks. The main comparative claims of the paper are of this second kind, and Section 5.2 now states this limitation explicitly.

Weakness 2 and Question 3.

The proposed leaderboard score is not evaluated in the empirical study. Section 3.2 and Eq. (8) define logarithmic per-test scores that are averaged over tests, while the experiments use total and relative gas. Appendix A.6 acknowledges this distinction, but does not show whether it changes the comparisons. These aggregations can produce different orderings. Since the scoring protocol is part of the contribution, leaving its relationship to the reported results unresolved is a substantive gap in the benchmark evaluation.

Does applying Eq. (8) to the evaluated submissions preserve the main comparisons? Please clarify why total and relative gas were used instead of the proposed leaderboard score.

We appreciate this point and see that the distinction was not stated clearly enough. The quantity the benchmark measures is gas. Eq. (8) is the rule by which the public leaderboard converts gas into a score, so that submissions made at different times can be ranked against an evolving best. The experiments instead compare a fixed cohort of systems, and for this purpose we report gas directly, as total gas and as gas relative to the lowest observed total. Both are derived from the same measurements and differ only in how they are aggregated. Relative gas keeps the comparison in directly interpretable units and shows the full profile across allowances (Figure 5a), which a single averaged score would conceal.

Question 4.

Failure interpretation: Do the existing evaluation records show how unproved binaries perform on the full functional tests? Separating incorrect outputs, execution-limit failures and binaries that pass those tests but lack proofs would help explain the sample/proof gap.

We appreciate this suggestion, which we found very useful. We ran the final binary of every attempt without an accepted proof through the hidden tests under the same gas cap, and Table 8 separates the outcomes into the three categories you describe. Most unproved binaries pass every hidden test, the remainder mostly exceed the gas cap, and incorrect outputs are rare. Counting proved and unproved binaries together, 84% of eight-hour attempts end with a binary that is correct on every hidden test within the cap, while 63% have an accepted proof. The sample/proof gap therefore consists mostly of correct binaries that lack a proof. We now report this in Section 4.3.

We are thankful again for these precise questions, which have helped us clarify the scope of the experiments and the role of each measure. We hope the revised paper addresses your concerns, and we would welcome your view on whether the distinction between gas and the leaderboard score is now clear. We are happy to discuss any point further.

Reviewer_FyWJOpenReview ↗

Review of rebuttal

Thank you for the additional experiments. The hidden-test results and the new timing and uncertainty analyses address several of my earlier concerns.

I still have two questions after reading the revision.

1. The interpretation of the new results.

Table 8 shows that most binaries without accepted proofs still pass the full hidden tests. This seems to be an important finding: the main difficulty is often completing the proof, not producing a working program.

However, the abstract and conclusion remain largely unchanged. I wonder whether the new results should play a larger role in the paper's main argument. The original motivation focuses on the limitations of test-based evaluation, while the new experiments seem to reveal more about the difficulty of proof construction. How do the authors see these findings affecting the paper's main contribution and conclusions?

2. The evaluation choices.

I appreciate the clarification that the ten long-budget tasks were selected rather than randomly sampled. But what were the specific selection criteria? Covering eight categories and a range of solver counts does not fully explain why these ten tasks were chosen, particularly given how much of the analysis depends on them.

I also remain curious whether using the proposed leaderboard score in Eq. (8), instead of total gas, would change the main model comparisons.

I appreciate the revisions and would be interested in the authors' views on these points.

Thank you for the follow-up and for reading the revision closely. We address each point below.

1. The interpretation of the new results.

We agree, and we have revised the paper so that this finding is part of its main argument. We see it as evidence for the original motivation rather than a departure from it. The motivation is that passing tests does not establish correctness. The new results show that current models already write programs that pass the hidden tests in most attempts, but often cannot prove them correct. A test-based benchmark would count most of these programs as successes and, as the new Table 1 shows, would also rank the models differently. The benchmark measures precisely the step from a working program to a proved one, which test-based evaluation cannot observe. The abstract, the contributions, Section 4.3 and the conclusion now state this, and Section 4.2 shows that the same pattern holds across the 30-minute evaluation.

2. The selection of the ten tasks.

The ten problems were selected by hand, before any evaluation was run, with two aims: problems from different CSES sections whose solutions rely on different core techniques, such as dynamic programming, range queries, string matching, maximum flow, geometry and trees, and a range of recorded solver counts. Section 4.1 and Appendix B.2 now state this, and Table 10 now reports each problem's rank in the corpus by recorded solvers, so that the difficulty of the selection can be judged directly. Because the problems were fixed before any results were available, the choice could not favour any system. The 90 problems drawn at random complement this selection, and the main finding of the eight-hour evaluation, that most binaries without a proof still pass every hidden test, holds on them as well (Section 4.2).

3. The leaderboard score of Eq. (8).

We applied Eq. (8) to all 165 scoreable eight-hour artifacts, taking the evaluated cohort as the leaderboard snapshot. Averaged over the 50 attempts of each system, with failures scored zero, it ranks the systems in the same order as the number of scoreable artifacts, and within each problem it orders 94% of pairs of artifacts in the same way as total gas. The main comparisons are therefore unchanged under the leaderboard score.

We thank you again for these questions, which have helped us make the main finding of the paper explicit. We are happy to discuss any point further.

Reviewer_Q5EsOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces Lacerta, a Lean 4 framework for reasoning about WASM binaries, and Lacerta-Bench, where models must generate a WASM binary plus a Lean proof that the exact binary satisfies a fixed high-level specification and byte codec. Scoreable submissions must also pass hidden tests under a deterministic gas limit, so the benchmark compares both proof completion and executable efficiency.

The idea of evaluating proof-carrying executable artifacts is interesting. The spec/codec/binary decomposition is clean, and the experiments show that passing public samples, completing a proof, and producing an efficient artifact are distinct. However, I am not fully convinced that the benchmark design choices are sufficiently justified.

Critical strengths
  • Strong evaluation object: a concrete executable binary plus a kernel-checked proof about that exact binary.
  • The experimental design is reasonable: the paper separately evaluates short-budget broad coverage and longer-budget repeated attempts, and distinguishes binary generation, proof acceptance, gas feasibility, and efficiency.
  • The experimental results seems strong: passing public samples, completing a proof, satisfying gas limits, and producing an efficient artifact are empirically shown to be different axes.
Critical weaknesses

Binary-level boundary is not sufficiently justified The paper asks models to prove submitted WASM binaries directly, but does not clearly explain why this is the right evaluation boundary. A natural alternative is to ask models to generate high-level verified Lean/Verus/Dafny-style programs, then compile/extract them to WASM and measure gas. That would evaluate verified algorithm generation more directly while avoiding much of the WASM-specific proof burden. The paper should clarify whether the goal is to avoid trusting compilers, support source-language-agnostic submissions, evaluate binary optimization, or model final-artifact certification.

Corpus novelty is unclear The Lacerta framework is technically nontrivial, but the benchmark corpus consists of manually authored high-level Lean specs for CSES problems plus byte codecs. It is unclear why a new 400-task CSES corpus was necessary, rather than adapting existing Lean/formal-verification benchmarks by adding codecs and WASM wrappers. The paper should better separate the novelty of the WASM verification framework from the novelty of the newly authored corpus.

Missing high-level baselines make failures hard to interpret When an attempt fails to produce an accepted proof, it is unclear whether the model failed at the algorithm, WASM generation, byte-level representation reasoning, Lacerta proof engineering, or tool use. A high-level verified-program baseline on the same tasks, even on a subset, would help disentangle algorithmic reasoning from binary-level proof burden.

Results may depend strongly on the agent setup All models use the same OpenCode harness, prompt, tool setup, and prover-agent configuration. This is controlled, but the results measure a model-agent-prompt system rather than the base model. Some models may be better adapted to this harness or Lean feedback loop. The paper should discuss sensitivity to prompting, harness design, and model-specific coding environments.

Spec quality need more details

Although the specs are human-reviewed, this is still a weak guarantee for 400 manually written formalizations. The benchmark would benefit from test-based validation/filtering, e.g., ground-truth tests, differential testing against accepted CSES solutions, randomized/property-based codec tests, and adversarial edge cases, to better catch mismatches between the formal specs and intended problem semantics.

Questions for authors
  1. What makes direct proof of the submitted WASM binary necessary for this benchmark, instead of evaluating high-level verified generation and then compiling the verified program to WASM?

  2. Could Lacerta reuse existing Lean/formal-verification benchmarks by adding codecs and WASM wrappers? If not, why is a new CSES corpus necessary?

  3. Can the authors provide a high-level verified-program baseline or ablation to separate algorithmic reasoning from binary-level proof engineering?

  4. How are the manually written specs validated beyond human review, and would test-based filtering/differential testing catch spec mismatches?

3 comments

(1/2)

Thank you for the careful and constructive review. We appreciate that you recognise the value of the evaluation object and the experimental design. We are especially grateful for your questions on the design choices: they made clear to us that the paper did not state its motivation explicitly enough. We have revised the paper accordingly and answer each point below.

Weakness 1 and Question 1.

Binary-level boundary is not sufficiently justified The paper asks models to prove submitted WASM binaries directly, but does not clearly explain why this is the right evaluation boundary. A natural alternative is to ask models to generate high-level verified Lean/Verus/Dafny-style programs, then compile/extract them to WASM and measure gas. That would evaluate verified algorithm generation more directly while avoiding much of the WASM-specific proof burden. The paper should clarify whether the goal is to avoid trusting compilers, support source-language-agnostic submissions, evaluate binary optimization, or model final-artifact certification.

What makes direct proof of the submitted WASM binary necessary for this benchmark, instead of evaluating high-level verified generation and then compiling the verified program to WASM?

We appreciate this question. LACERTA was designed to avoid trusting a compiler, to accept submissions from any source language, and to verify exactly what the executed binary does. To our knowledge, no verified compiler from Lean, Rust or C targets WebAssembly, and the closest one, CertiCoq-Wasm, covers only Coq programs. A proof about a source program would therefore not cover the binary we run and measure. The benchmark then uses this setting to evaluate whether an agent can derive a solution to a problem together with a formal proof of its correctness. We now discuss this better in Section 2.

Weakness 2 and Question 2.

Corpus novelty is unclear The Lacerta framework is technically nontrivial, but the benchmark corpus consists of manually authored high-level Lean specs for CSES problems plus byte codecs. It is unclear why a new 400-task CSES corpus was necessary, rather than adapting existing Lean/formal-verification benchmarks by adding codecs and WASM wrappers. The paper should better separate the novelty of the WASM verification framework from the novelty of the newly authored corpus.

Could Lacerta reuse existing Lean/formal-verification benchmarks by adding codecs and WASM wrappers? If not, why is a new CSES corpus necessary?

We appreciate this question. LACERTA can reuse existing benchmarks: any specification with a byte codec defines a task. We built a new corpus because the efficiency comparison needs what competitive programming provides: explicit input bounds, official hidden tests with large inputs, and a graded difficulty signal. Existing Lean benchmarks specify functions over Lean values, so adapting them would still mean writing the codecs and validity conditions, which is most of the work. Related work such as VeriContest (Xie et al., 2026) also draws on competitive-programming problems, with a focus on verifying Rust source programs with Verus rather than on the cost of execution. We now discuss this in Section 2.

Weakness 3 and Question 3.

Missing high-level baselines make failures hard to interpret When an attempt fails to produce an accepted proof, it is unclear whether the model failed at the algorithm, WASM generation, byte-level representation reasoning, Lacerta proof engineering, or tool use. A high-level verified-program baseline on the same tasks, even on a subset, would help disentangle algorithmic reasoning from binary-level proof burden.

Can the authors provide a high-level verified-program baseline or ablation to separate algorithmic reasoning from binary-level proof engineering?

We appreciate this suggestion. Our existing results already allow algorithmic failure to be separated from proof failure. We ran every binary that ended without an accepted proof on the hidden tests, and most of them are correct. In most failed attempts, the model therefore found a working algorithm but did not complete the proof. We now report this in Section 4.3. A comparison with high-level verified programs would be valuable future work. However, it would evaluate a different object, since a proof about source code does not establish the correctness of the compiled binary, which is the artifact this benchmark executes and measures.

(2/2)

Weakness 4.

Results may depend strongly on the agent setup All models use the same OpenCode harness, prompt, tool setup, and prover-agent configuration. This is controlled, but the results measure a model-agent-prompt system rather than the base model. Some models may be better adapted to this harness or Lean feedback loop. The paper should discuss sensitivity to prompting, harness design, and model-specific coding environments.

We appreciate this point and agree that the results describe models operating within a specific agent configuration. This was a deliberate choice. Our aim is to introduce an evaluation object and a protocol, and a single, unmodified configuration shared by all models keeps the comparison controlled, so that the observed differences arise under identical conditions rather than from choices tailored to individual providers. The benchmark itself does not depend on this configuration. A submission is judged only by its binary and its proof, so any agent, prompt or scaffold can be evaluated under the same criteria. A systematic study of how agent design affects proof completion is, in our view, a study in its own right, and one that Lacerta-Bench is designed to enable. Such a study would also be substantial in cost. The eight-hour stage alone required about 1,450 hours of agent time and about $13,000 in model charges, and each additional configuration would repeat it in full. Within our budget, we chose to invest these resources in repeated attempts for every model, which make the comparisons between models more reliable than a broader but shallower design would. Section 5.2 notes this as future work.

Weakness 5 and Question 4.

Spec quality need more details. Although the specs are human-reviewed, this is still a weak guarantee for 400 manually written formalizations. The benchmark would benefit from test-based validation/filtering, e.g., ground-truth tests, differential testing against accepted CSES solutions, randomized/property-based codec tests, and adversarial edge cases, to better catch mismatches between the formal specs and intended problem semantics.

How are the manually written specs validated beyond human review, and would test-based filtering/differential testing catch spec mismatches?

We appreciate this suggestion and agree that human review alone would be a weak guarantee. The specifications are also validated in two stronger ways, which we now describe in Section 2.3. Every task has a reference implementation with a machine-checked proof that it satisfies the specification. In addition, the evaluation itself acts as a large-scale differential test. None of the 210 binaries with an accepted proof, produced independently by six systems, gave a wrong output on any official hidden test. A specification that misstated its problem would allow a proved binary to fail such a test. Randomized testing of the codecs would be a useful complement, and the released benchmark makes it straightforward to add.

We thank the referee again for these thoughtful questions, which have helped us state the motivation and scope of the work more clearly. We hope the revised paper addresses your concerns, and we would welcome your view on whether the binary-level design is now better justified. We are happy to discuss any point further.

Thank the authors' efforts. My concerns are largely resolved, but I still have reservations about the novelty. So, I will keep my score.

Reviewer_B8yzOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper introduced LACERTA, a Lean 4 framework for reasoning about binary programs, alongside with a dataset LACERTA-BENCH, to evalaute binary generation from high-level specifications. This dataset includes 400 tasks from complex programming problems. In experiments, six LLMs on 100 problems are evaluated.

Critical strengths
  1. it provides a useful benchmark to evaluate LLM's ability in solving and proof code competitive programming tasks with formal specifications.

  2. Experiments over 6 SOTA LLMs demonstrated the difficulty and complexity of the task, disclosing a very interesting findings on this problem.

Critical weaknesses
  1. I have to say this paper is really difficult to read and follow, especially for those reviewers like me who have little background knowledge about programming specifications. A good academic paper should clearly clarify the motivation, research questions and cases to help any readers understand the paper. However, the LARERTA benchmarks did not provide a motivation case to show the typical characteristics of this task.

  2. Lack of sufficient human validation on constructing the benchmark. in Line 164: "Every specification was audited by a human against the original problem statement. " only one human is assigned to check the problem is not enough. multiplie human checkers are required and their agreement should be considered.

Questions for authors
  1. What's the meaning for the name LACERTA?
  2. What's the challenging for the evaluation object proved binary? how would it affect LLM's performance in the code testing stage?
1 comment

Thank you for the review and for finding the benchmark useful and the findings interesting. We have uploaded a revised PDF, and we answer each point below.

Weakness 1.

I have to say this paper is really difficult to read and follow, especially for those reviewers like me who have little background knowledge about programming specifications. A good academic paper should clearly clarify the motivation, research questions and cases to help any readers understand the paper. However, the LARERTA benchmarks did not provide a motivation case to show the typical characteristics of this task.

Thank you for this feedback. We have revised the paper to address it: the introduction now illustrates the problem with a simple example, Section 2 begins with a plain description of what a model receives and must produce, Figure 1 walks through a complete task, and the outcome terms are defined in one place. In brief, in a task such as Missing Number the input is a list of distinct numbers from 1 to n with one number missing, and the program must print the missing one. An ordinary coding benchmark runs the program on a few inputs and checks the answers, whereas here the model must also submit a machine-checked proof that the compiled program is correct for every valid input. Among the programs whose proof is accepted, we then compare how much computation each one uses.

Weakness 2.

Lack of sufficient human validation on constructing the benchmark. in Line 164: "Every specification was audited by a human against the original problem statement." only one human is assigned to check the problem is not enough. multiplie human checkers are required and their agreement should be considered.

Thank you for raising this. We have addressed it in the revised paper; please see Section 2.3.

Question 1.

What's the meaning for the name LACERTA?

"LACERTA" is a placeholder name for double-blind review.

Question 2.

What's the challenging for the evaluation object proved binary? how would it affect LLM's performance in the code testing stage?

The difficulty is the proof, not the program. Models write binaries that pass the tests easily: 98% of eight-hour attempts pass the public samples, and most binaries without a proof also pass every hidden test. Only 63% obtain a proof. See revised paper Sections 1 and 4.3.

We hope the revised paper addresses your concerns, in particular its readability. We would welcome your view on whether the task is now clear, and we are happy to answer any further questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.