- 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?
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).