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 standardpass@32sampling. - 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.3Bmodel 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