miniCodeProps: a Minimal Benchmark for Proving Code Properties

Evan Lohn, Sean Welleck

Abstract

AI agents have shown initial promise in automating mathematical theorem proving in proof assistants such as Lean. The same proof assistants can be used to verify the correctness of code by pairing code with specifications and proofs that the specifications hold. Automating the writing of code, specifications, and proofs could lower the cost of verification, or, ambitiously, enable an AI agent to output safe, provably correct code. However, it remains unclear whether current neural theorem provers can automatically verify even relatively simple programs. We present miniCodeProps, a benchmark of 201 program specifications in the Lean proof assistant, aimed at the subproblem of automatically generating a proof for a provided program and specification. miniCodeProps contains specifications about simple, self-contained programs (e.g., lists, natural numbers, binary trees) with varied proof difficulty. Despite its simplicity, miniCodeProps is sufficient to break current LLM-based provers, with state-of-the-art methods showing promise on the easy properties in miniCodeProps, yet failing to prove nearly all of the medium and hard properties. We publicly release miniCodeProps as a benchmark for furthering automated theorem proving in the context of formally verified code.

Introduction

Formal verification—the process of mathematically proving that code meets a specific requirement—is the "gold standard" for software safety. However, it is notoriously labor-intensive. While AI agents have made strides in proving mathematical theorems using tools like the Lean proof assistant, it remains unclear how well they handle program verification.

Existing benchmarks usually fall into two extremes: pure mathematics (e.g., miniF2F) or complex software projects (e.g., the CompCert compiler). The authors argue for a "minimum level of competency" benchmark—the formal verification equivalent of a software engineering interview. Can an AI prove that a simple sorting function actually sorts? Can it prove that a recursive function will eventually stop? miniCodeProps fills this gap by providing a suite of 201 Lean 4 specifications for simple, self-contained programs.

Methods and Dataset

The researchers developed miniCodeProps by translating problems from the Tons of Inductive Problems (TIP) suite, originally in Haskell, into Lean 4. The benchmark is categorized into three difficulty levels:

  • Medley (Easy): 86 properties of lists, trees, and natural numbers (e.g., list zip/unzip properties).
  • Termination (Medium): 28 lemmas required to prove that non-standard recursive functions actually terminate.
  • Sorting (Hard): 87 properties of complex sorting algorithms (e.g., proving a Heapsort implementation is correct).
The components of a verification task in miniCodeProps: the program implementation (Code), the formal specification (Property), and the generated Proof verified by the Lean compiler.

To evaluate current capabilities, the study tested two primary proving modes: full-proof generation using GPT-4o (including a refinement loop) and tactic-by-tactic generation using ntp-ctx-1.3B, a specialized model fine-tuned on Lean’s mathematical library, Mathlib.

Key Results

The results reveal a stark "competency gap" between basic operations and real-world verification challenges. While models solved roughly 3 out of 4 "easy" problems, they failed nearly 90% of the medium and hard problems.

Performance breakdown showing that while models show promise on easy tasks, they struggle significantly with termination and sorting properties.

Interestingly, the much smaller 1.3B parameter model (ntp-ctx) performed comparably to (and sometimes better than) GPT-4o on the harder tasks, likely due to its specialized training on Lean tactics. This suggests that general-purpose LLM scale does not automatically translate to formal verification proficiency.

Discussion and Insights

The benchmark highlights several critical challenges for automated formal verification:

  • The "Math-to-Code" Transfer Gap: Models trained heavily on mathematical proofs do not automatically excel at program verification, which often requires specific induction strategies over custom data structures.
  • Termination is a Wall: In Lean, recursive functions require termination proofs. These lemmas proved incredibly difficult for LLMs, despite being essential for verified recursive code.
  • Structural Understanding: When GPT-4o fails on hard problems, it often resorts to invalid induction steps or placeholders, indicating a lack of deep structural understanding of the code logic.

While miniCodeProps is currently limited to self-contained functional programs, it serves as a vital diagnostic tool. The authors suggest that future progress will require "verification-style" synthetic data to help models bridge the gap between solving math puzzles and verifying real software.

Summary updated

Abstract

AI agents have shown initial promise in automating mathematical theorem proving in proof assistants such as Lean. The same proof assistants can be used to verify the correctness of code by pairing code with specifications and proofs that the specifications hold. Automating the writing of code, specifications, and proofs could lower the cost of verification, or, ambitiously, enable an AI agent to output safe, provably correct code. However, it remains unclear whether current neural theorem provers can automatically verify even relatively simple programs. We present miniCodeProps, a benchmark of 201 program specifications in the Lean proof assistant, aimed at the subproblem of automatically generating a proof for a provided program and specification. miniCodeProps contains specifications about simple, self-contained programs (e.g., lists, natural numbers, binary trees) with varied proof difficulty. Despite its simplicity, miniCodeProps is sufficient to break current LLM-based provers, with state-of-the-art methods showing promise on the easy properties in miniCodeProps, yet failing to prove nearly all of the medium and hard properties. We publicly release miniCodeProps as a benchmark for furthering automated theorem proving in the context of formally verified code.
BibTeX
@inproceedings{lohn2024minicodeprops,
  author = {Evan Lohn and Sean Welleck},
  title = {{miniCodeProps: a Minimal Benchmark for Proving Code Properties}},
  booktitle = {SafeGenAi @ NeurIPS},
  year = {2024},
  url = {https://openreview.net/forum?id=6QFe3vPbYZ},
}

Loading related content...

Figure