miniCodeProps: a Minimal Benchmark for Proving Code Properties

Evan Lohn, Sean Welleck

TL;DR

While large language models (LLMs) show rising proficiency in formal mathematical theorem proving, verifying code correctness remains a major blind spot. The authors introduce miniCodeProps, a benchmark of 201 self-contained program specifications and termination proofs in Lean 4. Despite the problems being relatively simple, current frontier LLMs hit a wall—solving over 70% of basic properties but failing on more than 90% of medium- and hard-level code verification tasks.

What Problem Does This Paper Address?

Interactive proof assistants like Lean, Coq, and Isabelle allow software engineers to write code, state specifications, and construct machine-checked proofs that the code adheres to its spec. However, writing these formal proofs is tedious and time-consuming.

While AI agents have made rapid strides proving math competition problems (e.g., using benchmarks like miniF2F), automated formal code verification has lagged behind. Existing code verification benchmarks typically rely on massive, complex systems (such as CompCert in Coq) with deep dependency trees, making it difficult to isolate what models actually understand. The field lacks a "coding interview"-style benchmark: a concise, self-contained suite of software properties that tests whether models possess foundational program-proving abilities.

Methods

The paper evaluates two main proof-generation paradigms on the newly created benchmark:

  • Whole-Proof Generation: Models generate end-to-end proof scripts prompted with the code dependencies (deps) and theorem statements. Evaluated using GPT-4o with standard pass@32 sampling.
  • Whole-Proof with Refinement: A "many-to-one" iterative refinement baseline where 32 failed proof attempts are fed back into GPT-4o's context to prompt new attempts (evaluated across $T=2$ rounds with $k=16$ samples).
  • Tactic-by-Tactic Search: Step-by-step interactive proving using best-first search guided by ntp-ctx-1.3B (a DeepSeek-Coder 1.3B model fine-tuned on Lean's Mathlib to take proof states and code context as inputs).

Datasets

  • miniCodeProps (New): Composed of 201 theorem statements in Lean 4, manually translated and adapted from the Haskell Tons of Inductive Problems (TIP) suite. It spans 95 functions across three distinct categories:
  • Medley (Easy, 86 properties): Intuitive, inductive properties over basic data structures (lists, natural numbers, binary trees).
  • Termination Lemmas (Medium, 28 properties): Explicit termination proofs required by Lean for non-trivial recursive functions.
  • Sorting Properties (Hard, 87 properties): Correctness invariants (e.g., ordering, element counting, permutation preservation) for non-standard sorting algorithms.

Key Insights and Ideas

  • Math skills don't trivially transfer to code: Mathlib-trained models learn mathematical tactics (e.g., non-linear arithmetic) rather than structural program induction or domain-specific invariants. As a result, proving program properties requires distinct reasoning patterns.
  • Termination is a major bottleneck: In functional proof assistants like Lean 4, recursive functions must terminate. Proving termination for complex recursive patterns often requires intricate custom lemmas that take human experts hours to formalize; LLMs struggle severely here.
  • Hallucinated proof steps in code reasoning: When tackling complex algorithmic proofs (like heapsort correctness), models tend to generate plausible-looking structural steps but leave invalid placeholders, invent impossible induction hypotheses, or generalize inductive types incorrectly.
  • A lightweight 1.3B specialist matches a massive general LLM: The small, context-aware ntp-ctx-1.3B model performs competitively with (and slightly outperforms on harder tasks) GPT-4o, highlighting the value of interactive tactic search over pure autoregressive generation.

Key Results

Model / Approach Medley (Easy) Termination + Sorting (Med/Hard) Overall Accuracy
GPT-4o (pass@32) 75.6% (65/86) 4.34% (5/115) 34.8% (70/201)
GPT-4o (+ refinement) 77.9% (67/86) 6.96% (8/115) 37.3% (75/201)
ntp-ctx-1.3B (Best-First) 72.1% (62/86) 8.69% (10/115) 35.8% (72/201)
  • Easy properties are solvable: All methods succeed on over 70% of the Medley split, showing current models can handle short, straightforward inductive proofs over lists and trees.
  • Hard properties break current methods: Across all baselines, less than 9% of the medium/hard properties could be proven.
  • Feedback helps: Iterative refinement gave GPT-4o a modest boost (from 34.8% to 37.3%), showing that learning from failed proof candidates in-context is a viable direction.

Limitations and Future Work

  • Benchmark Size & Diversity: miniCodeProps comprises 201 problems primarily derived from functional list and tree algorithms; it does not cover imperative state, concurrency, or system-level code verification.
  • Data Scarcity: Unlike mathematical proofs (abundant in Mathlib), formal code verification repositories in Lean 4 are still nascent, limiting pre-training and fine-tuning corpora.
  • Future Directions: Developing dedicated verification-oriented training data, exploring agentic multi-turn proof repair, and establishing language-agnostic frameworks that bridge interactive provers with SMT-based program verification tools.

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 $\texttt{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. $\texttt{miniCodeProps}$ contains specifications about simple, self-contained programs (e.g., lists, natural numbers, binary trees) with varied proof difficulty. Despite its simplicity, $\texttt{miniCodeProps}$ is sufficient to break current LLM-based provers, with state-of-the-art methods showing promise on the easy properties in $\texttt{miniCodeProps}$, yet failing to prove nearly all of the medium and hard properties. We publicly release $\texttt{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