acceptodds
Under review as a conference paper at ICLR 2027

VeriBench-Infinity: Detecting Verification Hallucinations, Valid Proofs of the Wrong Program

Abstract

Formal verification aims to prove that a program satisfies its specification for every valid input, using an interactive theorem prover such as Lean 4. Yet AI agents can produce valid proofs about mistranslated programs or weakened requirements, creating false confidence in software that still contains bugs. We introduce **VeriBench-Infinity**, a benchmark and evaluator that detects these *verification hallucinations* by checking whether AI-generated program translations and specifications preserve the source program's behavior and intended requirements. For each Python program, we independently construct a reference implementation and specification in Lean. We cross-check the reference against Python through execution tests and independent review. Rather than accepting LLM judgment or agreement on finite tests, a separate prover must **formally establish** that the agent and reference agree on observable behavior and requirements for **every valid input** represented by the reference. These comparisons accommodate different data representations and produce machine-checked proofs or concrete counterexamples; incomplete proof searches remain unresolved. We evaluate three agents on 48 program instances pairing correct and buggy versions of competition problems and repository functions. Our analysis exposes translation and specification errors that survive LLM review, while separate case studies identify bugs in CPython's standard library and `intervaltree`. VeriBench-Infinity shifts evaluation from rewarding valid proofs in isolation toward measuring whether AI-generated correctness claims justify trust in the software developers actually use.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Formal Verification, Code Autoformalization, Lean, Program Equivalence, LLM Agents, Benchmarks, Formal Methods

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

This paper studies verification hallucinations: formally valid proofs that establish properties of mistranslated programs or weakened specifications. VeriBench-Infinity separates translation, specification, and proof or refutation stages. It evaluates submissions against independently curated Lean references and contracts, combining semantic judgments with proof obligations that relate potentially different data representations and observable behaviors. Evaluation uses 24 tasks drawn equally from programming competitions and repository functions, with correct and buggy variants yielding 48 instances and 144 runs across three agents. Results and case studies expose fidelity errors missed by semantic review and distinguish them from proof difficulty.

Critical strengths
  1. Well-motivated problem identification. implementation-fidelity (Python-to-Lean translation) is indeed a key issue in LLM-based program verification. The paper does a good job of raising this problem and revealing the potential hallucinations it may introduce.
Critical weaknesses
  1. Bad writing. The paper is filled with a large amount of concrete implementation details rather than abstracted methodology, making it read like a technical blog. The examples in the Introduction and Section 3.2 are overly detailed, and the paper repeatedly mentions specific LLM version numbers (e.g., GPT-6 Astra, Claude Fable 5.1). These could all be abstracted to a higher level to improve readability.

  2. The correctness of the golden reference package cannot be guaranteed. Section 3.1 states that the reference code of the benchmark is generated using GPT-6. Even after LLM-as-a-judge, the semantic equivalence between these model-generated Lean implementations and the Python implementations cannot be guaranteed—which is insufficient for a formal-verification benchmark. Since the entire benchmark contains only 24 tasks, the authors could ensure semantic equivalence through manual inspection.

Questions for authors
  1. What is Figure 2 trying to convey? It is too complex to understand.
Reviewer_rPiiOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

Despite being framed in terms of "verification hallucinations," this paper essentially discusses a classical problem in the Programming Languages (PL) research community: semantic preservation in the formalization of programs and specifications.

For the semantic preservation of specification formalizations, the paper largely follows the approach of BEq, augmented with data-refinement-style relations that accommodate different representations of program states in the agent-generated and ground-truth formalizations.

For the semantic preservation of program formalizations, however, the paper assumes a hypothetical verification workflow that differs substantially from conventional approaches in the PL community. It then identifies problems that arise specifically under this hypothetical workflow and constructs a benchmark to evaluate them. See Weakness 1 for details.

Critical strengths

The semantic preservation of specification formalizations is an important problem in this field. However, the other problem discussed in this paper, semantic preservation in program formalization, is largely an artificial problem that arises only under the particular, hypothetical program verification workflow assumed by the authors.

Critical weaknesses
  1. The proposed benchmark is based on a hypothetical verification workflow that is not representative of established practice in the field.

The paper presumes a program verification workflow in which LLMs translate a target program into Lean and construct an ad hoc semantic representation for each individual program. However, this is not the workflow typically adopted by the Programming Languages (PL) and Formal Verification (FV) communities.

In established verification practice (e.g., seL4 and CompCert), researchers first formalize the semantics of the programming language, ensuring that the formalization faithfully captures the behavior of programs written in that language. They then use rule-based parsers to to construct a formal representation of the target program, ensuring semantic preservation between the original source code and its formal representation. While this established approach faces only relatively minor faithfulness issues, the paper instead assumes an LLM-based, per-program, ad hoc formalization workflow that directly introduces much more serious faithfulness problems, and then proposes a benchmark to measure the extent of these faithfulness problems.

To better clarify the established practice in the PL/FV community, semantic formalizations are typically developed for programming languages or systems (e.g., operating systems, file systems, and hardware architectures), rather than separately for each individual program, as the authors do in this paper.

  1. Statements about program verification contain factual errors. The first two opening sentences of the Introduction contain 4 factual errors:
  • L36–39: "Formal verification aims to prove that a program’s output satisfies certain specifications describing its intended behavior, by modelling the program in an interactive theorem prover such as Lean, and proving statements about this model."

    1. Formal verification is not limited to programs. It is also widely used in other domains, such as hardware and chip design.
    2. Formal verification is not limited to interactive theorem proving. Many verification tools employ automated theorem provers, e.g., Frama-C.
    3. Not all properties concern program outputs. For example, liveness properties concern the behavior of a system over time.
  • L38–40: The second sentence states, "specifications are satisfied over an unbounded input domain." This is not necessarily true. The input domain is often constrained by a so-called precondition.

Questions for authors
  1. Given that established methods in PL research already use semantic formalizations and rule-based parsers to ensure semantic preservation in program verification pipelines more reliably than LLMs, why do the authors choose to use LLMs to construct ad hoc Lean representations of individual Python programs? Why not instead use LLMs to construct a semantic formalization of (a subset of) Python and then build a rule-based parser?

  2. In L63, the authors acknowledge that their method can only verify external behavior, not internal execution steps. How would the authors comment on conventional PL methods, which commonly establish semantic preservation at the level of execution traces?

  3. Conventional PL methods can cover the semantics of memory aliasing, concurrency, and even weak memory behaviors. How do the authors expect their method to handle these cases?

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

The paper introduces VeriBench-Infinity for evaluating source-to-Lean formalization and verification. It combines semantic review with formal comparisons against curated Lean implementations and specifications. A frozen three-stage protocol separates translation, specification, and proof. Experiments evaluate three code agents on 48 program instances derived from 24 tasks, each with correct and buggy variants.

Critical strengths
  • The paper addresses a meaningful risk.
  • Frozen artifacts and representation-aware formal comparisons provide auditable evidence and help distinguish formalization failures from proof-generation failures.
  • Differential testing, multi-model review, and human adjudication of disagreements provide useful safeguards.
Critical weaknesses
  1. Insufficient justification for the evaluation criteria.

The paper does not sufficiently justify why preserving internal algorithmic structure is necessary for evaluating program-verification ability. While the authors aim to verify the original source program rather than an arbitrary functionally correct implementation, this distinction does not establish why behaviorally equivalent translations with different algorithms should be rejected. If two implementations satisfy the same specification and their observable behaviors are formally proven equivalent, differences in internal algorithms do not necessarily invalidate the verification result. Moreover, algorithmic fidelity is assessed through LLM-based semantic judgments rather than formal guarantees, potentially introducing subjectivity into the evaluation. The authors should clarify the necessity of this criterion, distinguish behavioral fidelity from algorithmic fidelity, and justify why structural differences constitute verification failures.

  1. Limited benchmark diversity.

Although the benchmark contains 48 instances, these derive from only 24 underlying tasks: 12 IOI problems and 12 repository functions. Pairing correct and buggy variants is useful for studying bug preservation, but does not provide the diversity of 48 independent tasks. Broader coverage would strengthen conclusions across program structures, language features, and defect types.

Questions for authors

See Weaknesses.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.