acceptodds
Under review as a conference paper at ICLR 2027

PV-Bench: Specification and Verification of Competition-Level Algorithmic Programs

Abstract

Automating the verification of existing code requires both formalizing its intended behavior and proving that the implementation satisfies it. Many existing benchmarks let models generate the implementations they verify, while fixed-program benchmarks often supply the specifications. We present PV-Bench, a benchmark for specifying and verifying fixed C programs that require reasoning about both algorithms and explicit memory manipulation. It contains 233 programs, including 147 accepted Codeforces solutions to problems rated from 800 to 2800, alongside classic algorithms, data structures, and library routines. Each program comes with an expert-reviewed reference specification and reference verification artifacts built with QCP. PV-Bench evaluates three tasks independently: specification generation, annotation generation, and completion of residual Rocq proofs. The latter two tasks receive the reference artifacts from preceding stages, allowing each capability to be assessed separately. Candidate specifications are checked for semantic equivalence to the reference through machine-checked proofs and refutations, distinguishing equivalent, too-weak, too-strong, and incomparable contracts while leaving unresolved judgments undecided. Annotation and proof submissions are checked against the fixed program and specification. Our evaluation reveals complementary strengths across stages and substantial gaps in specification and annotation generation, even when proof completion with reference specifications and annotations succeeds. These findings show why proof completion alone gives an incomplete picture of a model's ability to verify an existing program.

Primary area:
datasets and benchmarks
Keywords:
benchmark, program verification, formal specification, AI for formal methods, separation logic, algorithm verification

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_i8BjOpenReview ↗
Rating
3(+1)
Confidence
3(−1)
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper presents PV-Bench, a benchmark for evaluating LLMs on the formal specification and verification of fixed C programs. The benchmark consists of 233 programs with expert-reviewed reference specifications, annotations, and proofs. Using QCP and Rocq, PV-Bench evaluates three tasks: specification generation, annotation generation and proof generation. For specification evaluation, the authors introduce a proof-based judging mechanism that checks semantic equivalence against reference specifications and categorizes incorrect specifications as too weak, too strong, or incomparable. Experiments on frontier LLMs show that specification and annotation generation remain challenging, with the best models achieving pass@1 rates of 39.3% and 20.0%, respectively, compared to 65.5% for proof completion. The papers concludes that writing specifications and annotations is the main bottleneck in verification.

Critical strengths
  1. Challenging benchmark with comprehensive verification artifacts. PV-Bench provides 233 fixed C programs, including competition-level algorithmic problems, accompanied by expert-reviewed specifications, annotations, and verification proofs. The inclusion of explicit memory reasoning and nontrivial algorithms introduces additional verification challenges beyond those typically covered by safe Rust-based benchmarks.

  2. Fine-grained evaluation of verification capabilities. The benchmark separately evaluates specification generation, annotation generation, and proof completion, enabling a more detailed analysis of LLM verification capabilities. Its proof-based specification evaluation also provides a mechanism for assessing semantic equivalence and identifying different types of specification errors.

Critical weaknesses

W1: Limited novelty and insufficiently justified motivation. The benchmark largely combines evaluation tasks and methodologies already explored in prior work, including VERINA [1], VeriContest [2], and LiveFMBench [3]. Moreover, the motivation overstates the limitations of existing benchmarks. For example, the authors suggest that joint specification and code generation can lead to degenerate solutions, overlooking the independent correctness checks employed by VERINA and VeriContest. While extending verification benchmarks to C programs with explicit memory reasoning is valuable, the paper does not sufficiently distinguish its methodological contributions from prior work or justify the need for a separate benchmark.

W2: Insufficient experimental evaluation and limited discussion. The experimental evaluation is limited in breadth and depth, with relatively few models and insufficient analysis of benchmark reliability. In particular, T2 evaluation depends on an LLM judge successfully proving the generated verification conditions, potentially conflating annotation quality with the judge's proving capabilities. The paper does not adequately quantify this effect or report unresolved judgment rates. Moreover, the paper provides insufficient discussion of key benchmark-quality concerns, including dataset distribution diversity, potential data contamination, and threats to validity. In particular, although the reference specifications are reportedly manually reviewed, the authors do not clarify the review criteria, number of reviewers, or procedures for handling disagreements and potential errors. These limitations weaken the reliability and comprehensiveness of the evaluation.

[1] Ye, Zhe, et al. Verina: Benchmarking verifiable code generation. 2026.

[2] Xie, Zichen, et al. VeriContest: A Competitive-Programming Benchmark for Verifiable Code Generation. 2026.

[3] Xu, Dong, et al. LiveFMBench: Unveiling the Power and Limits of Agentic Workflows in Specification Generation. 2026.

Questions for authors

Q1: Novelty and motivation. What fundamentally new evaluation capabilities does PV-Bench provide beyond existing benchmarks such as VERINA, VeriContest, and LiveFMBench? In particular, the authors argue that joint specification and code generation may lead to degenerate solutions. However, both VERINA and VeriContest independently check the correctness of generated specifications. How does the authors' concern apply to these benchmarks?

Q2: Reliability of the judging process. Since T2 evaluation depends on an LLM judge successfully proving the generated verification conditions, could the authors report the proportions of refuted and undecided submissions for each model? Additionally, how reliably can the judge verify known-correct annotations, and how sensitive are the reported success rates to the judge's proving capabilities?

Q3: Validity of reference specifications. The paper provides insufficient details about how reference specifications are manually reviewed. How many reviewers are involved, what review protocol is followed, and how are disagreements resolved? Since manual review cannot guarantee correctness, how do the authors assess potential errors in reference specifications and their impact on benchmark validity? Moreover, Section 2 says specifications "should state this property without describing how the program computes it", but the boundary between mathematical definitions and implementation details is unclear for complex DP and greedy problems. For example, Climbing Stairs can be specified using a mathematical recurrence, while greedy problems may have multiple equally valid solutions. how do the authors ensure that reference specifications capture the intended problem behavior rather than the specific algorithms used in their implementations? Additionally, Appendix C.2 appears to impose an implementation-specific output-buffer constraint not required by the original problem. Could the authors clarify this discrepancy?

Q4: Experimental coverage and reliability. Why is annotation generation evaluated on only 50 programs, with different subsets of models evaluated across tasks? Moreover, the evaluation covers only a limited number of proprietary models, lacking diversity in model families and architectures. Could the authors expand the evaluation to include more models, particularly open-source models, and analyze how verification performance varies with model size? A broader evaluation would provide stronger evidence of the benchmark's generalizability and enable more comprehensive insights into LLM verification capabilities.

Q5: Dataset diversity and contamination. Given that a substantial portion of the benchmark programs are generated by only two LLMs, how do the authors assess potential biases or limited distribution diversity in the benchmark? Additionally, there is no data contamination discussion since the benchmark contains publicly available competitive-programming problems and classical algorithms. Can the authors provide such discussions?

10 comments
AuthorsOpenReview ↗

Response(1/2)

We thank the reviewer for the careful reading. Our general response describes what PV-Bench adds and what we changed; here we answer this review's points.

Q1. Novelty and motivation

The general response clarifies our main contribution: explicit memory reasoning and harder problems. Among the benchmarks the reviewer names, VERINA works on immutable Lean values and VeriContest on safe Rust, so neither asks a model to reason about pointers and aliasing. LiveFMBench does target C, but it relies on automated solvers, so it cannot support competition-level algorithms and does not evaluate proving verification conditions.

Our concern about degenerate solutions is about who writes the program. VERINA and VeriContest do check generated specifications, but when the model also writes the code, it may pick an algorithm that is easy to verify. In VeriContest's October 2026 End2End release, 35 of the 107 problems with a fully correct answer have an accepted answer that does not implement the reference algorithm. PV-Bench does not let the model that verifies a program write its code: the program is given and fixed in all three tasks.

Memory also changes how specifications must be judged, so PV-Bench introduces a different judging method. The follow-up comment explains it.

Q2. Reliability of the judging process

Point 3 of the general response gives the proportions of accepted, refuted, undecided (Unresolved), and invalid submissions for each model, under pass@1 and the improved pass@2 judging.

For known-correct annotations, the judge is given the reference annotations, their verification conditions, and the Rocq proofs of those conditions (Section 4.1). With these, it can complete the proofs for the reference annotations of all 50 programs within the time limit. For correct annotations that differ from the reference, we believe the improved pass@2 judging is reliable. The three models' submissions contain 53 correct annotations in total. After the one-hour pass@2, 48 of them are verified (23 in pass@1 and 25 more in pass@2), and extending the second limit to three hours verified the other 5. Human review of the submissions still undecided found no further correct annotation.

Regarding how sensitive the reported success rates are to the judge's proving capabilities: even a weak judge gives a sound range for the success rate. Invalid submissions are detected mechanically and need no proving capability. Every Accepted verdict carries a Rocq-checked proof and every Refuted verdict a Rocq-checked counterexample, so the accepted submissions give a lower bound on the success rate, and the accepted plus undecided ones give an upper bound. A weaker judge only widens this range; it cannot make either bound wrong. So the range a weaker judge gives remains useful, and even the partial proof scripts it leaves on undecided submissions can support further analysis.

Q3. Validity of reference specifications

Two human experts review each reference against the problem statement, and it enters the benchmark only after passing both. They apply three criteria: the specification is independent of the algorithm; it admits every result the problem allows; and it states the mathematical result and the memory resources on both the success and the failure path. So Climbing Stairs is specified by counting step sequences, not by the recurrence, and an optimization problem by the optimum over the valid solutions. The reviewer is right about Appendix C.2; points 1 and 2 of the general response describe the correction, the audit of input ranges, and the T1 rerun.

AuthorsOpenReview ↗

Response(2/2)

Q4. Experimental coverage and reliability

All 223 programs have complete materials for all three tasks. T2 is evaluated on 50 programs because it is the most expensive task: each submission needs a generation session and a separate judge session, so we evaluated a stratified sample. T1 no longer uses a subset. The rerun in point 2 of the general response covers all 223 programs, including the 12 graph programs previously left out, for each model. The models also show how performance varies with model size within a family: Equivalent specifications rise from 98 (Luna) to 115 (Terra) to 118 (Sol) for GPT-5.6, and from 116 (Sonnet 5) to 136 (Opus 5) for Claude. We also evaluated an open-source model, Hy4. In T1 it produces Equivalent specifications for 105 of the 223 programs (47.1%), and in T3 it completes the proofs for 112 of the 223 programs (50.2%). Its T2 evaluation is in progress.

Q5. Dataset diversity and contamination

Only the 147 Codeforces programs are model-generated. Each follows the problem's standard solution, so the diversity comes from the problems, which span six algorithm families and ratings from 800 to 2800. The programs may appear in training data, but PV-Bench does not evaluate whether a model can solve these problems or write their solutions. The program is given and the model must specify and verify it, so having seen a solution in training gives little advantage.

AuthorsOpenReview ↗

how PV-Bench judges specifications with memory reasoning (supplement to Q1)

For specifications, prior work compares preconditions and postconditions separately, as implications between propositions over values, and neither method can compare function specifications that involve memory reasoning. Let P,QP, Q be the ground-truth precondition and postcondition and P^,Q^\hat{P}, \hat{Q} the generated ones, over inputs xx and output rr.

VERINA checks four implications, by proof first and by tests otherwise: ∀x. P(x)⇔P^(x),∀x,r. P(x)∧Q^(x,r)⇒Q(x,r),∀x,r. P(x)∧Q(x,r)⇒Q^(x,r).\forall x.\ P(x) \Leftrightarrow \hat{P}(x), \qquad \forall x, r.\ P(x) \land \hat{Q}(x,r) \Rightarrow Q(x,r), \qquad \forall x, r.\ P(x) \land Q(x,r) \Rightarrow \hat{Q}(x,r).

VeriContest proves the precondition equivalence and tests the postcondition on correct pairs T+T^{+} and mutated pairs T−T^{-}: ∀x. P^(x)⇔P(x),∀(x,r)∈T+. Q^(x,r),∀(x,r)∈T−. ¬Q^(x,r).\forall x.\ \hat{P}(x) \Leftrightarrow P(x), \qquad \forall (x,r)\in T^{+}.\ \hat{Q}(x,r), \qquad \forall (x,r)\in T^{-}.\ \lnot\hat{Q}(x,r).

With explicit memory reasoning, comparing preconditions and postconditions separately is no longer correct. A precondition also states which memory the function owns, the two conditions share logical variables quantified over the whole contract, and the postcondition must be related to the memory the precondition left untouched. For example, let SS require and return an array of nn cells, and S^\hat{S} one of n+1n+1 cells. Neither precondition implies the other, yet every implementation of SS also meets S^\hat{S}, because the extra cell is left untouched (Section 4.2).

PV-Bench judges a candidate S^\hat{S} against the reference SS by function specification derivation, one entailment per direction, over the logical variables xx and yy of the two contracts (Section 4.2):

S\Rightarrow \hat{S}:&\quad \forall y.\ \hat{P}(y) \vdash \exists x.\ P(x) * \bigl(Q(x) \mathrel{-\!\!*} \hat{Q}(y)\bigr)\\ \hat{S}\Rightarrow S:&\quad \forall x.\ P(x) \vdash \exists y.\ \hat{P}(y) * \bigl(\hat{Q}(y) \mathrel{-\!\!*} Q(x)\bigr) \end{aligned}$$ A caller holding $\hat{P}$ splits off $P$ for the call, and the wand returns the rest to give $\hat{Q}$. Each direction is proved in Rocq or refuted by a Rocq-checked counterexample on a concrete memory state, giving the Equivalent, Too Weak, Too Strong, and Incomparable verdicts. A candidate is accepted only on proof, and what the judge cannot settle is reported as Undecided. **Example: two specifications that differ only in the memory they own.** In Codeforces 1139B, `main` declares a buffer larger than any single input uses, and `solver` reads only its first `n` cells: ```c static long long solver(const int *a, int n) { /* reads a[n-1] down to a[0] */ } int main(void) { int n; scanf("%d", &n); static int a[200005]; for (int i = 0; i < n; i++) scanf("%d", &a[i]); printf("%lld\n", solver(a, n)); } ``` The reference precondition owns the cells that `solver` reads. The precondition written by Sonnet 5 also owns the unused tail of the buffer: ``` Reference P : 1 <= n <= 200000 && IntArray::full(a, n, l) Sonnet 5 P̂ : 1 <= n <= 200000 && IntArray::full(a, n, l) * IntArray::undef_seg(a, n, 200005) ``` **PV-Bench judges Sonnet's specification Too Weak, where VERINA and VeriContest would accept it as equivalent.** The two specifications state the same propositions over values: the bounds are the same, and the judge proved the output relations equivalent. They differ only in the memory they own, which the derivation detects: - $S\Rightarrow\hat{S}$ is proved. A caller holding $\hat{P}$ passes the first `n` cells to the call and keeps the tail as the frame. - $\hat{S}\Rightarrow S$ is refuted by a Rocq-checked memory state with `n = 1` that owns the one array cell required by $P$ but not the next cell, which $\hat{P}$ also requires. A caller that owns exactly `n` cells therefore cannot call a function with Sonnet's specification. The derivation generalizes the pure criteria. When the assertions mention no memory and the logical variables are just the inputs, * becomes $\land$ and $-*$ becomes $\Rightarrow$, and $\hat{S}\Rightarrow S$ reduces to $$\forall x.\ P(x) \Rightarrow \hat{P}(x) \quad\text{and}\quad \forall x, r.\ P(x) \land \hat{Q}(x,r) \Rightarrow Q(x,r),$$ which are exactly VERINA's two soundness conditions. In the same way, $S\Rightarrow\hat{S}$ reduces to $$\forall x.\ \hat{P}(x) \Rightarrow P(x) \quad\text{and}\quad \forall x, r.\ \hat{P}(x) \land Q(x,r) \Rightarrow \hat{Q}(x,r).$$ The first is VERINA's completeness of $\hat{P}$. The second is VERINA's completeness of $\hat{Q}$ with the assumption $P(x)$ replaced by $\hat{P}(x)$: a candidate that accepts fewer inputs is compared with the reference only on the inputs it accepts. Since the first condition gives $\hat{P} \Rightarrow P$, VERINA's condition implies ours, and the two coincide whenever $P \Rightarrow \hat{P}$ also holds. In particular, a pure candidate is judged Equivalent, with both directions proved, exactly when it satisfies all four of VERINA's conditions.
Reviewer_9d45OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

PV-Bench is a verification benchmark of a set of fixed C programs. It evaluates specification generation, annotation generation, and residual proof completion. A generated specification is accepted when a judge model proves it equivalent to the reference; T2 is judged by a model proving the VCs regenerated from the annotations.

Critical strengths

Target an emerging problem.

Critical weaknesses
  1. The benchmark is built on QCP, a customized verifier without an established user base, instead of the standard tools and setup for C program verification, such as Frama-C and VST. The only stated reason for QCP is its separation logic support. Yet ACSL (used by frama-c) already expresses separation and frame conditions, WP discharges VCs by external provers Why3 and handles residual goals in a proof assistant, and VST provides separation logic in Rocq over CompCert semantics.

    A benchmark on a tool-specific setup adds little to the community. For instance, no number in the paper can be compared with LiveFMBench, DafnyBench, or the VeriFast study, and low scores cannot be separated from the models' unfamiliarity with QCP's annotation dialect. I suggest the authors port the benchmark, or at least the 86 non-Codeforces programs, to ACSL/Frama-C or VST and report at least T2 and T3 there.

  2. T1 accepts a specification equivalent to the reference, but such equivalence is not correctness wrt. the intended behavior. The references were co-authored by AI agents and reviewed by experts. A certificate of non-equivalence therefore establishes disagreement between two contracts, not necessarily an error in the candidate. Report the review process, i.e., how specifications were ensured to be correct and reflect the indended behaviors documented in informal problem descriptions; the authors should at least check the reference postconditions against the available tests. Or weaken the claim/conclusion from T1.

  3. The T1 and T2 judges are LLMs with a time budget. Hence unresolved judgments could either due to a failed submission or a failure by the judge. A low score may simply reflect only the judge's unsuccessful proof search. Yet the paper reports neither the outcome nor the judge's ability to recognize correct submissions. Please report per-model counts of each outcome, e.g., Equivalent, Too Weak, Too Strong, Incomparable, Undecided, Invalid, and Timeout for T1 and of Proved, Refuted, Unresolved, and Invalid for T2; calibrate the T2 judge on the reference annotations of the same 50 programs; and judge all T2 under one setup.

  4. The evaluation setup is different across tasks: (1) 211 programs for T1, 223 for T3, and 50 for T2; (2) time limits of 30, 60, and 120 minutes; and (3) different model sets, with Opus leading T1 but absent from T2 and T3, and Sol absent from T1. Tool access is not uniform either. No time breakdown or timeout count is reported, so whether failures are due to the model, QCP, SMT solving, or Rocq is unknown; the bottleneck is unclear.

Other points:

  • Contribution 3 overstates novelty: CLEVER already accepts a specification only through a proof of equivalence to a reference, and VERINA attempts both directions by proof.
  • The paper describes the programs as real-world code; yet 147 of 233 are model-generated contest solutions of about 50 lines.
Questions for authors
  1. What is the per-verdict breakdown of T1 and T2 failures per model, and what fraction is Undecided?
  2. How were the references reviewed, how many were corrected, and how many Too Strong candidates are satisfied by the fixed program?
  3. Why QCP rather than Frama-C/WP or VST, and do the specifications and annotations port to ACSL?
  4. Why do program sets, time limits, model sets, and tool access differ across tasks, and how many sessions ended at the time limit?
3 comments
AuthorsOpenReview ↗

Response (1/2)

Thank you for carefully reviewing PV-Bench and for your specific comments on the choice of verification tools, reference specifications, and evaluation setup. We address your questions in order below, explaining the technical rationale behind our design and clarifying aspects that were insufficiently explained in the paper.

Q1. Unresolved judgments

Points 2 and 3 of our general response report the per-model T1 and T2 outcomes. Across the five models in the T1 table, 151 of 1,115 submissions (13.54%) were initially Undecided. Human review with LLM-assisted proofs assigned them to the other four categories; all 33 newly accepted submissions have complete Rocq proofs in both directions.

For T2, we use the one-hour pass@2 protocol described in point 3. After this second attempt, 10 of Sonnet 5's submissions (20%), 8 of Sol's (16%), and none of Luna's remain Unresolved. The table keeps these outcomes separate from Refuted and Invalid submissions and also reports the results with a three-hour limit.

The judge can verify the reference annotations within the time limit. The judge is given the reference annotations, their verification conditions, and the Rocq proofs of those conditions (Section 4.1). With these artifacts available, it can complete the proofs for the reference annotations of all 50 programs within the allotted time. For model-generated annotations, it may adapt the reference proofs but must still prove the conditions generated from the candidate's own annotations.

Q2. Reference specifications

Two human experts review each reference against the original problem statement. A specification enters the benchmark only after passing both reviews. They apply three criteria: it describes the required result independently of the algorithm; it allows every valid output; and it states both the mathematical result and the memory resources.

The references went through several rounds of internal review. At each round, we checked that the fixed program satisfied its specification and corrected issues found during review. Since these changes were made throughout development, the exact number of corrections is difficult to reconstruct. Each final reference is accompanied by verification that the fixed program satisfies it.

Points 1 and 2 of our general response explain the corrections after submission. We corrected the reference in Appendix C.2 and will add a new Too Weak example in the revised paper. We also aligned input ranges that differed between problem descriptions and reference specifications, reran T1, and reviewed the initially Undecided submissions with LLM-assisted proofs.

A Too Strong specification excludes an input-output case allowed by the reference. T1 asks models to express the problem's requirements, including all valid answers. A fixed program may choose one of several valid answers, but our reference specification admits all valid solutions allowed by the problem. T1 therefore checks equivalence to the reference specification: proving that the fixed program satisfies a candidate alone does not establish that the candidate admits all these solutions.

Consider an implementation that scans the array from left to right and updates the selected index only when it encounters a strictly larger element. It therefore returns the first occurrence of the maximum. The specification should still allow any maximum index, since the problem does not require the first one. The following contracts have the same precondition and memory requirements.

The reference allows any index of a maximum element:

int argmax(int *a, int n)
/*@ With (values : list Z)
    Require
      0 < n &&
      Zlength(values) == n &&
      IntArray::full(a, n, values)
    Ensure
      0 <= __return && __return < n &&
      (forall k, (0 <= k && k < n) =>
        values[k] <= values[__return]) &&
      IntArray::full(a, n, values)
*/;

The Too Strong candidate requires the first such index:

int argmax(int *a, int n)
/*@ With (values : list Z)
    Require
      0 < n &&
      Zlength(values) == n &&
      IntArray::full(a, n, values)
    Ensure
      0 <= __return && __return < n &&
      (forall k, (0 <= k && k < n) =>
        values[k] <= values[__return]) &&
      (forall k, (0 <= k && k < __return) =>
        values[k] < values[__return]) &&
      IntArray::full(a, n, values)
*/;

For [5, 5], the reference allows indices 0 and 1, while the candidate allows only 0. A program that always returns the first maximum satisfies both contracts. The candidate is nevertheless Too Strong because it excludes an answer permitted by the problem.

Please see Appendix C.4 for a Too Strong example from our experiments. Whether the fixed program satisfies a Too Strong candidate is therefore insufficient to judge whether it fully captures the problem's requirements. The reference specification admits all valid answers allowed by the problem.

AuthorsOpenReview ↗

Response(2/2)

Q3. Why QCP?

QCP supports richer specifications than Frama-C/WP. To our knowledge, as of November 12, 2026, the supported first-order framework of ACSL/WP does not directly accommodate the higher-order specifications used here, such as specifications parameterized by functions and predicates. QCP directly supports Rocq's higher-order mathematical definitions. Porting to ACSL therefore requires re-encoding these specifications into its supported first-order framework.

QCP performs more efficient symbolic execution than VST. We are very familiar with VST, and this difference is our main reason for choosing QCP: VST performs symbolic execution inside Rocq, incurring substantial overhead for complex programs. Porting to VST is relatively straightforward: we can reuse the existing Rocq mathematical definitions and adapt the contracts and proof interfaces.

Q4. Experimental settings

The generation budgets were chosen from our experience with actual runs. Tasks not completed within the respective budgets typically required substantially longer runs or remained unsolved despite continued execution. We therefore set generation budgets of 30, 60, and 120 minutes for the three tasks to balance the opportunity for completion against evaluation cost. These empirical choices do not imply that every timed-out task is impossible to complete.

Model coverage and dataset subsets reflect our available compute and API budget. The selected subsets cover a range of problem categories. Point 2 of our general response reports the expanded T1 evaluation on all 223 test programs for the five models in its table.

Thank you again for taking the time to review our paper and share your feedback.

We hope our rebuttal helped clarify the points you raised. As the discussion period draws to a close, we would welcome any further feedback and would be happy to address any remaining questions.

Reviewer_w5ffOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents PV-Bench, a benchmark for formal specification and verification of fixed C programs. It contains 233 program instances with reference specifications, annotations, and proofs, and evaluates three tasks: specification generation, annotation generation, and proof completion. Using QCP and Rocq for verification, the experiments reveal substantial performance differences across these stages.

Critical strengths

The paper addresses a meaningful problem in automated program verification, particularly for fixed C programs involving algorithmic reasoning and explicit memory manipulation. The construction of reference specifications, annotations, and proofs represents substantial effort, and the proof-based evaluation provides a rigorous basis for assessing model outputs. The three-stage design and cross-task experiments also offer useful insights into the limitations of current models.

Critical weaknesses
  1. The semantic fidelity of reference specifications could be better justified. For example, Appendix C.2 requires the output buffer to retain the original input upon failure, although this behavior is not explicitly required by the original problem. This raises concerns about whether some valid, implementation-independent specifications might be rejected. Further clarification of the reference specification auditing process would be helpful.
  2. The impact of incomplete judging remains unclear. Semantically correct specifications or annotations may fail when the judge cannot complete the required proofs within its time budget. Since unresolved judgments count as failures, a more detailed breakdown of failure categories would help assess their influence on the reported results.
  3. The methodological novelty is somewhat incremental, as related benchmarks have already explored specification generation, annotation generation, and proof completion. A clearer analysis of the additional value provided by explicit memory reasoning would strengthen the contribution.
Questions for authors
  1. How were the reference specifications audited for consistency with the original task requirements, especially failure-path behavior such as the output-buffer condition in Appendix C.2? Can semantically valid alternative specifications be accepted?

  2. What proportion of failed judgments comes from incorrect candidate specifications or annotations versus proof-search timeouts or other unresolved cases, and how sensitive are the reported results to this distinction?

  3. What evidence most clearly distinguishes the insights enabled by explicit memory reasoning in PV-Bench from those already obtained in existing specification, annotation, and proof-completion benchmarks?

4 comments
AuthorsOpenReview ↗

Response (1/2)

Thank you for carefully reviewing PV-Bench and for your specific questions. We address them in order below.

Q1. Reference specifications

Each reference specification is reviewed by two human experts against the original problem statement and included in the dataset only after passing both reviews. The review follows three criteria:

  1. The specification describes the required result independently of the algorithm. Different algorithms solving the same problem should satisfy the same mathematical specification. The specification should not require the particular sequence of steps used by the implementation.

  2. The specification includes all valid results allowed by the problem. It should not prescribe implementation details, such as DP-table updates or internal workspace layouts. For counting problems, it defines what is counted; for optimization problems, it describes the best value among valid solutions without requiring a particular sequence of choices.

  3. The contract describes both the mathematical result and the memory resources. Reviewers check the required memory conditions on both success and failure paths, without adding requirements on buffer contents that the problem does not specify.

Thank you for identifying the problem in Appendix C.2. Point 1 of our general response explains its cause and correction. We also reran the specification comparison for this example using the corrected reference.

Alternative formulations can be accepted. The judge checks whether the candidate and reference specifications imply each other, rather than whether they use the same definitions. Appendix C.1 illustrates this with two different ways of counting stair-climbing paths. This comparison still relies on the reference specification matching the original problem.

Q2. Unresolved judgments

Point 2 of our general response reports the input-range corrections and the repeated T1 evaluation.

Of 1,115 submissions, 151 (13.54%) were initially Undecided. Human review assigned 33 to Equivalent, 14 to Too Weak, 16 to Too Strong, and 88 to Incomparable. All 33 accepted cases have complete Rocq proofs in both directions. The Incomparable group includes candidates whose definitions differ substantially from the reference. Neither specification implies the other.

The T2 judge receives the reference annotations, their verification conditions, and their Rocq proofs. As described in our general response, each submission is first judged with a 60-minute limit (pass@1), and unresolved submissions receive a second one-hour attempt (pass@2). We use this one-hour pass@2 as the evaluation metric, and the re-evaluation supports it: of the 66 submissions unresolved in pass@1, it settles 48 (25 Accepted, 23 Refuted with a counterexample). Of the 18 it leaves unresolved, a three-hour limit accepts only 5 more. We therefore consider this a reasonable evaluation protocol: the judge can adapt the reference proofs, but a submission passes only when all conditions generated from its own annotations are proved. Submissions still unresolved after the one-hour pass@2 count as failures under this setup.

Point 3 of our general response reports the updated T2 judging procedure and the outcomes.

Our original evaluation did not clearly distinguish incorrect annotations from correct annotations that the judge failed to prove within the time limit. For T1, human review with LLM-assisted proofs classified the initially Undecided submissions, as reported above. For T2, 127 of the 150 submissions failed under pass@1. Of these, 97 (76%) were incorrect and 30 (24%) were correct annotations the judge did not prove in time. We improved the judge and re-judged unresolved submissions. Under the one-hour pass@2, 48 submissions pass, and only 5 of the 102 failures (5%) are correct annotations the judge missed. Extending the second attempt to three hours proves these 5 without changing the model ranking. The longer attempt refutes 8 more with checked counterexamples, and human review identifies annotation errors in the remaining 5 unresolved submissions. This evidence supports our choice of the one-hour pass@2 as a reasonable evaluation protocol.

AuthorsOpenReview ↗

Response (2/2)

Q3. Explicit memory reasoning

Verifying a C program requires proving both its algorithmic result and the validity of the memory operations that produce it. AlgoVeri's tasks over mathematical objects do not evaluate concrete pointer operations. VeriContest's safe Rust setting excludes direct raw-pointer dereferences, so it does not evaluate models' ability to prove these accesses safe.

For example, PV-Bench evaluates graph algorithms across different memory representations. VeriContest's graph and tree examples use array-based representations, such as edge lists and parent arrays. PV-Bench includes DFS over a flattened adjacency matrix, a two-dimensional matrix accessed through row pointers, and linked adjacency lists. These implementations compute the same reachability result but require different memory proofs: the flattened matrix requires valid offset calculations, the two-dimensional matrix requires valid row pointers and array accesses, and the linked lists require valid nodes and links. In the linked-list version, DFS reads edge->data, follows edge->next, and updates visited[neighbor]. These raw-pointer accesses require unsafe in Rust and fall outside VeriContest's safe Rust setting. Models must prove that the accesses are valid and that updates to visited preserve the graph, together with the final reachability result. PV-Bench tests this ability in specifications, annotations, and proofs.

Thank you for the detailed response; it has addressed most of my concerns, so I will increase my score.

We really appreciate your thoughtful review, prompt follow-up, and constructive suggestions. We will include these changes and experimental results in the final version of the paper.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General response: what PV-Bench does and what we have improved (1/2)

We thank the three reviewers for their comments; each review is answered in its own response below. This general response clarifies our contribution and summarizes the changes we have made in response to your feedback.

What PV-Bench adds. PV-Bench evaluates how LLMs specify and verify fixed C programs that require explicit memory reasoning and competitive-programming algorithms. Its corpus differs from existing benchmarks in two main ways.

  • Explicit memory reasoning. The programs directly manipulate memory through pointers. For example, a graph algorithm may store its graph as an adjacency matrix or as linked adjacency lists, and the proof must relate each layout to the abstract graph. Some existing benchmarks target Lean programs, which work on immutable mathematical values, and thus cannot express in-place programs such as reversing a linked list by redirecting its pointers. Because memory is explicit, our specifications and annotations are written in separation logic.
  • Harder problems. The programs are classical algorithms, data structures, and Codeforces solutions. Verifying them requires the algorithmic argument, such as the optimality of a greedy choice, besides the memory reasoning. PV-Bench uses Rocq for proofs beyond automated solvers.

Its evaluation also differs. Each PV-Bench task combines memory reasoning with algorithmic properties: specifications describe memory and results, invariants describe memory and progress, and proofs establish memory safety and algorithmic correctness.

What we have changed and improved. We apologize for the error in Appendix C.2 and thank the reviewers for identifying it. A version-management error put an unfinished historical specification into this example. We have corrected the reference, and the revised paper will add a new Too Weak example.

We also re-examined our reference specifications, found and corrected input-range mismatches with the problem descriptions, and reran T1.

We thank the reviewers for pointing out that our original results did not give a detailed enough breakdown of unresolved judgments. We reviewed the initially Undecided T1 submissions with human analysis and LLM-assisted proofs, and assigned them to the other four categories.

For T2, we decided to improve the evaluation method. Originally, each submission was judged once, with a 60-minute limit (pass@1). Now, each submission left unresolved in pass@1 is judged a second time (pass@2). We also slightly improved the judge's skill for constructing counterexamples: it now has a method for building the concrete memory state that violates a false verification condition. With pass@2, of the 66 unresolved submissions, 48 were settled within one hour (25 Accepted, 23 Refuted with a counterexample). When the limit was extended to three hours, 5 more were Accepted, and the remaining 13 were all rejected: 8 were Refuted with a counterexample, and 5 were left unresolved and then rejected by human review. Therefore, we believe 1h pass@2 is already good enough as an evaluation metric. These changes will be reflected in the paper.

AuthorsOpenReview ↗

General response: what PV-Bench does and what we have improved (2/2)

1. Appendix C.2, reference correction and a new Too Weak example. The reviewers are right: the original example imposed an output-buffer condition that the problem did not require. Our reference specifications went through several rounds of development and expert review, but an error in version management put an unfinished historical version into this example. We have corrected the reference: the failure branch retains ownership of the output buffer without requiring it to preserve the input. In the revised paper, we will keep the corrected reference in Appendix C.2 and withdraw its previous Too Weak judgment. We will also add a new Too Weak example: a candidate for Cake Division omits the upper bounds on interval endpoints and therefore admits an invalid answer. The example will display both complete specifications, with a proof in one direction and a checked counterexample in the other.

2. T1, input-range corrections and re-evaluation. We corrected mismatches between the input ranges in the problem descriptions and the reference specifications. For bubble sort, the description allowed arrays of arbitrary positive length, while the reference required 1 <= numsSize <= 50000. Since C uses bounded integers for array lengths, we made the reference's input bound explicit in the problem description. We reran T1 on 223 programs for each of five models.

Human review with LLM-assisted proofs assigned all 151 initially Undecided submissions to the other four categories: 33 Equivalent, 14 Too Weak, 16 Too Strong, and 88 Incomparable. All 33 newly accepted submissions have complete Rocq proofs in both directions. The table reports the results after review. Invalid submissions are rejected before judging: for example, a syntax error in the contract or a Rocq compilation error.

ModelEquivalentToo WeakToo StrongIncomparableInvalid
GPT-5.6 Luna9815265628
GPT-5.6 Terra11522284810
GPT-5.6 Sol1182425515
Claude Sonnet 511625343711
Claude Opus 51361828383
Total58310414123057

3. T2, 1-hour pass@2 judging and re-evaluation. The judge now reports four outcomes: Accepted (all verification conditions proved in Rocq), Refuted (a counterexample checked in Rocq), Unresolved (neither proved nor refuted), and Invalid (the submission changes the fixed program or specification, or its annotations fail symbolic execution). The 66 submissions unresolved in pass@1 were judged a second time (pass@2). We report pass@2 under two limits, one hour and three hours:

Model (of 50)JudgingAcceptedRefutedUnresolvedInvalid
Claude Sonnet 5pass@193326
pass@2, 1 hour2311106
pass@2, 3 hours261446
GPT-5.6 Solpass@11032710
pass@2, 1 hour2012810
pass@2, 3 hours2217110
GPT-5.6 Lunapass@147732
pass@2, 1 hour513032
pass@2, 3 hours513032

A 1-hour pass@2 settles 48 of the 66 and leaves 18 unresolved. Extending it to 3 hours settles 13 more and leaves 5. In total, pass@2 accepted 30 and refuted 31. The table counts only the judge's verdicts, so the last 5 appear as Unresolved. Human review of these 5 found wrong annotations in them and rejected them. We therefore take the 1-hour pass@2 as the evaluation metric. Among correct annotations, those whose verification conditions are far harder to prove are less useful, and the submissions that stay unresolved beyond it are mostly wrong.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.