acceptodds
Under review as a conference paper at ICLR 2027

Efficient Formally Verified Code Generation via Specification Quality Estimates

Abstract

Large language models have become a ubiquitous element of software development workflows, but the code they generate may diverge from user intent or contain bugs. Formal verification has shown promise for addressing the correctness gap: instead of simply generating executable code, an LLM-based agent is tasked with producing a specification, an implementation, and a formal language proof of correctness. Generating the artifacts required for formal verification, though, is difficult: synthesized specifications are often incorrect, and generating implementations and proofs is computationally expensive. In this paper, we ask whether variation in specifications can be harnessed to improve agents' performance on verified code generation tasks. We first find that the downstream cost of implementation and proof generation can be accurately predicted given a specification as input. We then show that these cost estimates are useful: they can guide a verified code generation agent in selecting a specification that reduces the downstream cost of implementation and proof writing without diverging from user intent. We realize our approach as a tool, SPEQUEST, and find that it makes implementation and proof generation more than faster on a standard benchmark set.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
verified code generation, formal specifications, cost prediction, large language models, program synthesis

Reviews

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

This paper proposes SPEQUEST, a framework for improving verified code generation by estimating the downstream cost of a candidate formal specification before generating the implementation and proof. The core idea is that different formal specifications for the same natural-language intent, or different syntactic encodings of the same specification, can have very different downstream proof costs. SPEQUEST predicts this cost using LLM-based or conventional estimators, and then uses the estimate to select or improve specifications before invoking the implementation/proof-generation agent.

The paper evaluates SPEQUEST on Lean-based verified code generation and proof benchmarks, including Verina, AlgoVeri, and miniCodeProps. The results suggest that downstream generation/proving cost is predictable from the specification text and that cost-guided specification selection can substantially reduce proving time in the evaluated pipeline. The idea is interesting and relevant, but I have several concerns about what is actually being optimized and how broadly the conclusions can be interpreted.

Critical strengths

Overall, I like the core idea: specification choice can strongly affect downstream implementation/proof cost, and estimating this cost before proof generation is a practical and interesting direction.

I would be happy to raise my score if the authors can convincingly rule out weak-spec reward hacking and clarify the generality of the cost estimates beyond the evaluated workflow.

  • The paper identifies an important bottleneck in verified code generation that is less explored than implementation or proof search.

  • SPEQUEST is simple and potentially useful: generate/select candidate specs, estimate downstream cost, and use the estimate to guide the verified-code-generation pipeline.

  • The evaluation covers several estimator types, including LLM-based estimators and lightweight conventional models.

  • The empirical results suggest meaningful efficiency gains in the evaluated setup, especially that simple non-LLM estimators can be competitive.

Critical weaknesses

Potential reward hacking through weak specifications

SPEQUEST optimizes for specifications that reduce downstream implementation/proof cost. However, once the system is allowed to generate or select the specification, a faster proof may come from choosing a weaker or under-specified obligation rather than from genuinely improving verified code generation. For example, if the intended task is to implement sorting, a selected specification might only require a very weak property such as “the output is non-empty” or “the output length is positive.” Such a specification could pass limited benchmark checks, be much easier to implement and prove, and yet fail to capture the intended sorting behavior. Passing compilation or finite tests is therefore not sufficient to ensure that the selected specification preserves the user intent. This creates a possible reward-hacking path: select an easy-to-prove specification that satisfies the benchmark checks, then prove an implementation against this weaker spec.

Insufficient evaluation of specification correctness and completeness

The paper mainly evaluates downstream cost, solve rate, and speedup, but does not sufficiently evaluate whether the selected specifications are semantically comparable to the intended or reference specifications. To make the efficiency gains meaningful, the authors need stronger evidence that selected specs are not systematically weaker, incomplete, or vacuous. For example, they could compare selected specs with reference specs via implication/equivalence checks, mutation-based tests, stronger property tests, or human audits.

Efficiency results may be specific to one downstream workflow

The ground-truth cost labels appear to come mainly from a agent workflow: Claude Code, Lean tooling, and the authors' prompts. Thus, the estimator may learn what is easy for this particular agentic workflow rather than a general notion of specification difficulty. The paper would be stronger if it evaluated whether the learned rankings transfer across different downstream agents, prompts, or proof generation workflows.

Questions for authors

How do the authors ensure that SPEQUEST does not select weaker or under-specified specifications that are easier to prove but fail to capture the intended behavior?

How is the quality of selected specifications evaluated beyond compilation and benchmark tests, especially their correctness and completeness with respect to the natural-language intent or reference specification?

Do the learned specification-cost rankings transfer beyond the fixed Claude Code workflow, e.g., to other downstream agents, prompts, or proof generation approaches?

1 comment
AuthorsOpenReview ↗

Response to Reviewer n9Kx

We thank the reviewer for the detailed and thoughtful questions, and provide answers below.

Q1. How do the authors ensure that SPEQUEST does not select weaker or under-specified specifications that are easier to prove but fail to capture the intended behavior?

Answered in our general rebuttal above.

Q2. How is the quality of selected specifications evaluated beyond compilation and benchmark tests, especially their correctness and completeness with respect to the natural-language intent or reference specification?

Answered in our general rebuttal above.

Q3. Do the learned specification-cost rankings transfer beyond the fixed Claude Code workflow, e.g., to other downstream agents, prompts, or proof generation approaches?

Answered in our general rebuttal above (subsection 2).

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

The paper is about verified code generation, where an LLM agent turns an NL intent into a Lean specification, an implementation, and a proof. The authors generate about ten candidate specifications, keep those that pass the correctness checks, and measure how long a Claude Code agent takes to implement and prove each one. They train estimators (random forests, ridge regression, pairwise classifiers over structural, TF-IDF, etc.) to predict that cost from the specification text alone, and compare them to zero-shot LLM judges. The estimators are then used to pick the cheapest candidate, to guide a refinement loop, or as a tool for a proof-search agent, and the resulting time and solve rate are compared against reference specifications.

Critical strengths

I feel that the idea is simple and practical. A specification that leads to quicker implementation and shorter proofs is better, and the authors show that this cost can be predicted just from the specification text using cheap models, which helps in picking a better specification and saving time on the benchmarks.

Critical weaknesses

To be honest, I liked the core idea that a specification leading to a quick implementation and a shorter proof is better. However, I feel the evidence provided for their methodology is weak. Several of the experimental designs are flawed. Here is my detailed feedback:

  • Faithfulness is checked only by the benchmark's tests or just compilation, with no equivalence or implication check against the reference specification. A specification that does if-else on the test cases, with an if-else implementation, would pass the check and also be very cheap to prove, so the metric can be gamed. See the CLEVER benchmark (which you already cite), where they check equivalence between the generated specification and the ground-truth specification. If not that, then at least manual inspection of a subset of the specifications generated is a must. The appendix states that AlgoVeri has no test cases and candidates are only compiled (page 18 (line 929), "For AlgoVeri, which has no test cases..."; and page 16 (849), "compiled but not tested"). This is also inconsistent with Section 3.2, which says a golden test set is used for both benchmarks. So any gains on AlgoVeri could partly come from weaker specifications, and the paper never reports how often the selected specification is weaker than the reference.

  • The feedback loop shows the model counterexamples from failing tests (up to three failing checks, three attempts per candidate) and also tells it to minimize predicted difficulty. Over a few rounds, the tests can leak, and the model can fit to them. On Verina, the same tests are later used to judge faithfulness. This enables the branching loophole from my first point, and the authors do not measure how much leaks.

  • The 3x faster claim seems like an overclaim since everything is tested in-distribution: same benchmarks, same generator, same Opus 4.8 agent for training and testing. There is no test on a new benchmark, a different agent, or a real project. The cost of labeling training data with full agent runs (about 10 specifications per task) is also not accounted for in the 3x speedup.

  • The comparison with LLM as judge does not isolate anything, since trained models see measured costs and the LLM is zero-shot. A fair comparison needs few-shot or fine-tuned LLM judges. Also, the simple postcondition-length baseline matches or beats most trained models on AlgoVeri, so the models may be learning only "shorter is cheaper".

  • Cost is measured from a nondeterministic agent, but there is no noise ceiling (rerunning the same specification and checking how stable the cost is), no repeats, and no significance tests. The correlations are modest (at best less than 0.6 from Table 1).

  • The proof-search result is weak: single runs, no repeats or significance tests, no control test, and no report of whether the agent actually used the estimator in its plan.

Questions for authors

Here are a few questions besides those mentioned in the weakness section:

  1. Did you check the selected specifications against the reference specifications for equivalence or implication? How often is the selected one weaker, especially on AlgoVeri, where the appendix says candidates are only compiled and not tested?

  2. How noisy is the cost of one specification? If you rerun the same specification several times, how stable is the time, and do your Table 2 and Table 3 results hold over repeated runs with significance tests?

  3. In the miniCodeProps proof search, how often did the agent actually call the estimator, and did it change the plan? I want to know whether estimates play any role in the agent's decision.

In my opinion, I like the idea, but the current evidence does not support the usefulness claims. Addressing the faithfulness audit against reference specifications, the noise and significance analysis, the proof-search controls, and a transfer experiment would require substantial new experiments.

2 comments
AuthorsOpenReview ↗

Response to Reviewer YKYE

We thank the reviewer for the detailed and thoughtful questions, and provide answers below.

Q1. Did you check the selected specifications against the reference specifications for equivalence or implication? How often is the selected one weaker, especially on AlgoVeri, where the appendix says candidates are only compiled and not tested?

Answered in our general rebuttal above.

Q2. How noisy is the cost of one specification? If you rerun the same specification several times, how stable is the time, and do your Table 2 and Table 3 results hold over repeated runs with significance tests?

In our experiments, we rely on averages over large scale benchmarks to account for noise in any particular specification. Our results show that the measured effects are large and consistent across different sets of benchmarks. While this doesn't rule out the effect of noise completely, it increases confidence in the stability of our results.

Q3. In the miniCodeProps proof search, how often did the agent actually call the estimator, and did it change the plan? I want to know whether estimates play any role in the agent's decision.

We thank the reviewer for pointing out this avenue of investigation. The average number of calls per problem was 1.33 (on Opus 4.8), but the calls were heavily concentrated in the tail of difficult problems when the agent had freedom to call the estimator or not: on 129 problems, the agent did not call the estimator at all, but on the remaining problems, it called it on average 2.7 times. The average speedup does not meaningfully differ between the two groups, which suggests that prompt differences may be a significant contributor to the results. During a revision, we would add a description of this limitation to Section 5 and describe how future work could more deeply investigate the difference.

Thank you for your honest rebuttal. You conceded on all the issues I raised. This paper has serious experimental design flaws. The central thesis is undermined even more by the author's honest admissions in the rebuttal. You can think of flipping the core thesis into a negative-result paper. A useful follow-up would test whether cheaper-to-prove selected specifications are weaker than the reference, which could turn this into a negative result. Good luck!

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

This paper introduces SPEQUEST, which enhances the efficiency of large language models in generating verifiable code by predicting the subsequent implementation and proof generation costs of formal specifications. The authors construct a cost estimator and leverage prediction results through three mechanisms: candidate specification selection, loop feedback, and free-form agent. Experiments show that the method reduces the time required for subsequent implementation and proof generation while maintaining or improving task completion rates.

Critical strengths

Introducing a specification scoring mechanism before code and proof generation is a valuable design in this paper. The choice of formal specifications affects the difficulty of subsequent implementation and verification, while attempting full generation for every candidate specification is computationally expensive.

Critical weaknesses

Preservation of the original intent during specification optimization is not sufficiently validated. The paper distinguishes variation in the intent space from variation in the syntax space, allowing not only equivalent reformulations but also different interpretations of natural-language requirements. In this setting, strengthening preconditions or weakening postconditions can make implementation and proof generation easier, but whether these changes remain faithful to the original requirements needs adequate validation.

Questions for authors
  • Could authors clarify whether the estimators are intended to predict absolute generation costs or primarily rank candidate specifications? Spearman and Pearson correlations measure association but do not establish calibration or absolute predictive accuracy. Would “difficulty scoring” better describe some estimators, particularly the LLM-based ones, or could you provide evidence supporting their interpretation as cost predictors?

  • How exactly does the estimator’s output influence the generator’s revisions in the feedback loop? Does the generator receive only a numerical score and relative ranking, or also actionable explanations? A concrete iteration example would help clarify how the feedback guides specification changes.

1 comment
AuthorsOpenReview ↗

Response to Reviewer 3D7Q

We thank the reviewer for the detailed and thoughtful questions, and provide answers below.

Q1. Could authors clarify whether the estimators are intended to predict absolute generation costs or primarily rank candidate specifications? Would "difficulty scoring" better describe some estimators, particularly the LLM-based ones, or could you provide evidence supporting their interpretation as cost predictors?

The estimators primarily rank specifications rather than predicting absolute costs, since choosing among specifications is always the more important task in practice (we formulate this in Task 1). Table 1 therefore reports within-task Spearman ρ. We agree that "difficulty scoring" may be a better word to describe what we originally called "estimators", but the two are closely related, since any absolute estimator can readily be converted into a ranking.

Q2. How exactly does the estimator's output influence the generator's revisions in the feedback loop? Does the generator receive only a numerical score and relative ranking, or also actionable explanations? A concrete iteration example would help.

In our current implementation of SPEQUEST, the generator receives only a score and a relative ranking, with no explanation (see Appendix A). We design our approach in this way for two reasons: first, it allows us to compare the conventional regression model estimators, which provide no reasoning, with LLM-based estimators on equal footing; second, it isolates the effect of quality estimates without the confounding factor of additional feedback being passed back and forth between the estimator agents and the generation agents.

As a concrete example, on verina_advanced_1 (find the element that appears exactly once in a list), the Opus 4.8 estimator's scores for the loop's five faithful candidates were 55, 45, 40, 40, and 40 (lower is easier). The loop stopped after two consecutive candidates that did not improve on the best score and passed the third candidate to implementation and proof generation. That specification has precondition ∃ r ∈ nums, nums.count r = 1 and postcondition nums.count result = 1. By comparison, one of the ten independently generated specifications for the same task requires every other element to appear exactly twice, in both its precondition and its postcondition.

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

This paper proposes a method for improving the efficiency of verified code generation by predicting the downstream cost of generating an implementation and proof from a formal verification. The predictions are then used to select and refine specifications. The authors study four classes of estimators: LLM-based, structural-feature, text-based and graph-based. Experiments on Verina and AlgoVeri show correlations between predicted and observed costs, and reductions in downstream implementation/proof generation cost. The authors also demonstrate the used of estimators to guide proof search on miniCodeProps.

Critical strengths

This paper studies an important problem: how specification choices affect the cost of implementation and proof synthesis. Selecting a specification based on its predicted cost is an interesting direction.

Critical weaknesses
  1. It is unclear how the selected specifications are validated against the intended requirements. For AlgoVeri specs, according to Appendix A, these candidates are compiled but not tested. If selected specs are weaker, the resulting cost reductions would be less meaningful. The authors should assess whether selected specifications preserve the properties captured by the reference specifications.
  2. Insufficient experiment descriptions and reporting. Task1 defines the objective as expected cost, but the paper does not clearly state whether experimental costs are averages over independent runs or measurements from a single run per specification. Without repeated measurements, it is difficult to distinguish reliable improvements from stochastic variation. Table 3 does not report how often the agent invokes the estimator. Table 2 reports only the downstream cost without end-to-end measure. These results are needed to interpret the computational savings of the proposed method.
Questions for authors
  1. How is distinctness checked during spec generation? How many meaningfully distinct specs are obtained per task and how many candidates differ only cosmetically. Consider using examples to illustrate candidate diversity and cost differences.
  2. How many independent runs are performed per spec to measure implementation-and-proof generation cost? If only one run is used, how do you establish that the reported improvements persist across fresh runs rather than reflecting favorable proof-search outcomes?
  3. Have you investigated whether selected specifications preserve the requirements of the reference specifications, particularly on AlgoVeri? How do you detect e.g. weakened postconditions?
  4. Which benchmark is used in Figure 3, and are the task sets and downstream evaluation settings identical across the two modes? The Gen-in-loop procedure has substantially lower downstream cost than plan-then-gen mode. What explains the difference?
1 comment
AuthorsOpenReview ↗

Response to Reviewer CPya

We thank the reviewer for the detailed and thoughtful questions, and provide answers below.

Q1. How is distinctness checked during spec generation? How many meaningfully distinct specs are obtained per task and how many candidates differ only cosmetically?

We rely on generation prompts to the specification generator agent to achieve a high likelihood of generating distinct specifications, and check that each of the 10 generated specifications have non-empty diffs excluding whitespace; in selection mode, therefore, we statically check that the specifications are all different. Some of these differences might be called cosmetic, for instance, we found one case where the agent modified the specification only by changing variable names. But it is exactly these differences that are useful for our method: our results show that arguably-cosmetic differences lead to a difference in agent proof-writing ability, and we exploit this fact to improve performance.

Q2. How many independent runs are performed per spec to measure implementation-and-proof generation cost? If only one run is used, how do you establish that the reported improvements persist across fresh runs?

We run each specification once; we agree that this is a limitation of our current experimental setup and would note this in Section 5 during a revision. Our experiments operate over three large benchmark sets, and we rely on the average results over each benchmark, rather than per-task, to reduce the effects of noise. The effects we observe are large (265 s to 63–68 s on Verina, 15.5 hours to 5 hours on miniCodeProps), and every estimator lowers cost in both regimes. These results suggest that, even with significant variation from run to run, at least some effect would persist.

Q3. Have you investigated whether selected specifications preserve the requirements of the reference specifications, particularly on AlgoVeri? How do you detect e.g. weakened postconditions?

Answered in our general rebuttal above.

Q4. Which benchmark is used in Figure 3, and are the task sets and downstream evaluation settings identical across the two modes? The Gen-in-loop procedure has substantially lower downstream cost than plan-then-gen mode. What explains the difference?

Both panels use Verina, the same tasks, and the same downstream evaluation (Opus 4.8 implements and proves the best of the n candidates, as in the oracle of Table 2). The two panels differ in how candidates are generated: in (a) an agent plans ten specifications and generates them in one go; in (b) it generates one at a time and is asked each time for a syntactically different specification. The gap in downstream cost between the two methods is caused by the fact that the plan-first prompt commits to ten different interpretations and logical forms, some harder to prove, while sequential generation yields a more homogeneous set of candidates. The total cost is lowest at n = 8 in (a), where candidate generation is cheap, and at n = 3 in (b), where it is expensive.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Response to all Reviewers

We thank the reviewers for their time and thoughtful comments. We answer here two general concerns shared by multiple reviewers and then address specific questions individually for each.

All four reviewers posed questions about whether SPEQUEST could pick weaker specifications because they are cheaper to prove. We agree with the reviewers that this is a potential limitation of our approach, but argue that (1) our conceptual contribution has significant merit even with this limitation and (2) the limitation does not detract from our experimental results. For (1), the implementation of SPEQUEST employs tests as the check of correctness because there is no formal reference specification for existing verified coding benchmarks in practice; it could just as easily employ a formal verifier to check that the generated specifications are equivalent, especially in "selection" mode (Figure 2a). Developing such a benchmark set, and ensuring that formal equivalence checking for it can be accomplished in practice is largely orthogonal to our contribution in this work. Regarding (2), on Verina, we ensure that the generated specifications are not too weak in practice by giving the generator at most three counterexamples per repair message and never the full suite (Appendix A). For AlgoVeri, we again use the correctness check provided by the benchmark set. In both cases, our experiments measure pass rates based on the provided test cases, and the results show that cost falls without a drop in solve rate: all 12 estimators lower cost in both regimes relative to the reference specification and Verina solve rates stay at 98.9–100%.

YKYE and n9Kx raised concerns that every cost label in our experiments comes from one agent (Claude Code with Opus 4.8 and Lean tools), with no test on an agent with a different model. We agree with the reviewers that the particular costs we measure are those of generating with Opus 4.8, but as we describe in Section 5, the method we use is general and can be applied to any model. Our key findings are that (a) it is possible to predict cost and (b) that having predictions is useful. Neither of these conclusions depends on a particular pattern of cost, and we evaluate our approach on the two independent benchmark sets Verina and AlgoVeri to ensure that quality estimates are feasible for multiple classes of problems. Our results on miniCodeProps, where the estimator guides a proof-search agent rather than a specification generator and reduces running time from 15.5 hours to 5.0 hours, further demonstrate that quality estimates are generalizable.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.