💬 NLP

VeriSoftBench: Repository-Scale Formal Verification Benchmarks for Lean

This paper introduces VeriSoftBench, a repository-scale benchmark of 500 Lean 4 proof obligations from open-source software verification projects, revealing that current LLMs struggle to transfer from mathematical to code-centric settings and highlighting the critical impact of cross-file dependencies on proof automation success.

Original authors: Yutong Xin, Qiaochu Chen, Greg Durrett, Işil Dillig

Published 2026-02-23

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yutong Xin, Qiaochu Chen, Greg Durrett, Işil Dillig

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a brilliant but inexperienced apprentice how to fix a complex machine.

The Old Way (Math Benchmarks)
For a long time, researchers tested these AI "apprentices" using Mathlib. Think of Mathlib as a giant, perfectly organized library of universal math facts. It's like giving the apprentice a single, massive textbook where every definition is standard, every chapter is numbered, and the answers to problems are always found in the same predictable places.

The Problem: Real-world software isn't like a math textbook. It's more like a messy, sprawling construction site where every building has its own unique blueprints, custom tools, and weird local rules that don't exist anywhere else.

The New Challenge: VeriSoftBench
The authors of this paper realized that AI was getting great at solving math problems but failing miserably at real-world software verification. So, they built VeriSoftBench.

Think of VeriSoftBench as a giant, chaotic warehouse containing 500 different "proof puzzles."

Each puzzle is a specific task from a real, open-source software project (like a secure blockchain or a compiler).
To solve a puzzle, the AI can't just look up a standard rule. It has to wander through the warehouse, find the specific, custom-made tool the project invented yesterday, understand how it connects to a tool from three files away, and then figure out how to use it to fix the current problem.
It's the difference between solving a Sudoku puzzle (standard rules) and trying to fix a car engine where the manual is written in a secret code specific to that one car model.

The Experiment: Two Ways to Help the Apprentice
The researchers tested the AI under two different conditions to see how it handles this chaos:

The "Curated" Box (The Helpful Mentor):
Imagine a mentor who looks at the puzzle, finds only the exact tools and blueprints the AI needs, and hands them a neat, small box.
- Result: The AI did okay (about 40% success). It could solve the puzzle when the hard work of finding the right tools was done for it.
The "Full Warehouse" (The Overwhelming Dive):
Imagine dumping the AI into the entire warehouse with millions of other tools, blueprints, and random parts, telling it, "Good luck, find what you need!"
- Result: The AI got confused. Success rates dropped significantly. The sheer volume of "noise" made it hard to find the signal.

Key Discoveries (The "Aha!" Moments)

Math Experts aren't Software Experts: The AI models that are champions at solving math problems (like the ones trained on Mathlib) completely crashed when faced with these software puzzles. They were like a chess grandmaster trying to play poker; the skills didn't transfer.
The "Domino Effect" of Difficulty: The harder the puzzle, the more "transitive dependencies" it had.
- Analogy: Imagine a recipe. A simple recipe needs flour and eggs. A complex recipe needs flour, but the flour depends on a specific type of wheat, which depends on a specific fertilizer, which depends on a specific rain pattern.
- In VeriSoftBench, to solve a problem, the AI often had to trace a chain of 10 or 20 custom definitions deep into the code. The longer the chain, the more likely the AI was to get lost.
Context is a Double-Edged Sword: Giving the AI too much information (the full warehouse) was worse than giving it just enough (the curated box). However, even with the "perfect" box of tools, the AI still struggled. This means the problem isn't just about finding the right information; it's about reasoning through complex, custom logic that the AI hasn't seen before.

Why This Matters
Currently, AI is great at "textbook" math but terrible at "real-world" engineering. This paper sounds an alarm: if we want AI to help us write safe, bug-free software (like for self-driving cars or medical devices), we can't just train it on math problems. We need to teach it how to navigate messy, custom codebases where the rules are made up on the fly.

In a Nutshell:
The paper says, "We built a new test that mimics real software engineering. We found that current AI is like a student who aced the final exam but can't fix a leaky faucet because the faucet uses a custom part they've never seen. We need to teach them how to navigate the messy workshop, not just the clean classroom."

1. Problem Statement

While Large Language Models (LLMs) have shown significant promise in interactive theorem proving (ITP), particularly within the Lean ecosystem, current benchmarks suffer from a critical domain mismatch.

The Gap: Most existing benchmarks (e.g., MiniF2F, ProofNet, PutnamBench) are derived from mathematics (Mathlib), where proofs rely on a shared, stable ecosystem of standard abstractions.
The Reality: Proofs in software verification and programming language meta-theory are developed within large, open-source repositories. These tasks involve:
- Project-specific definitions: Custom datatypes, operations, and invariants unique to the codebase.
- Complex dependencies: Proofs often hinge on non-trivial cross-file structures and multi-hop dependency closures.
- Context noise: The relevant context is buried within massive codebases, making retrieval difficult.
The Question: How well do current provers, tuned for mathematical benchmarks, generalize to repository-scale verification tasks where the "library" is a bespoke, project-specific codebase?

2. Methodology: VeriSoftBench

The authors introduce VeriSoftBench, a new benchmark designed to evaluate provers in realistic repository settings.

Dataset Construction

Source: 500 Lean 4 proof obligations extracted from 23 diverse open-source formal-methods repositories (covering compilers, type systems, zero-knowledge circuits, and protocols).
Selection Criteria:
- Tasks must have valid, hole-free ground-truth proofs.
- Theorems must reference at least one repository-local definition.
- Trivial goals solvable by standard automation (e.g., simp, omega) are excluded.
Packaging: Unlike previous benchmarks that normalize tasks into a shared library, VeriSoftBench preserves the original local file context and cross-file dependencies.
Difficulty Metrics: Tasks are scored based on proof complexity (tactic script length) and contextual dependency (number of distinct definitions/lemmas drawn from the repo).

Contextual Configurations

To isolate the challenges of context retrieval vs. reasoning, the benchmark evaluates provers under two regimes:

Curated Context: The prover receives the local file context plus a focused set of necessary repository dependencies (definitions and lemmas directly or transitively invoked by the ground-truth proof). Proof bodies are elided to prevent leakage. This represents a "best-case" retrieval scenario.
Full Repository Context: The prover receives the entire repository library (all files, definitions, and lemmas). This simulates a realistic deployment scenario where the model must identify relevant facts from a massive search space. Some repositories exceed hundreds of thousands of tokens, necessitating truncation for current models.

3. Key Contributions

VeriSoftBench Benchmark: A dataset of 500 repository-scale Lean 4 tasks that explicitly models cross-file dependencies and project-specific abstractions, filling the gap between mathematical benchmarks and real-world verification.
Comprehensive Evaluation: An evaluation of frontier general-purpose LLMs (GPT-5.2, Claude Opus 4.5, Gemini-3-Pro) and specialized provers (Gödel-Prover-V2, Aristotle) under both curated and full-context settings.
Dependency Analysis: A structural analysis revealing that transitive dependency depth (multi-hop reasoning chains) is a primary bottleneck, more so than the sheer volume of dependencies.

4. Experimental Results

The evaluation yielded three primary observations:

Poor Transfer from Math to Verification: Provers optimized for Mathlib-style mathematics perform poorly in repository settings.
- Example: Gödel-Prover-V2, a state-of-the-art specialized prover for math, achieved 0% success on the Full Repository context and only 5.6% on Curated context.
- Best Performer: Gemini-3-Pro achieved the highest success rate at 41.0% (Curated) and 34.8% (Full), but these numbers remain low compared to math benchmarks.
Transitive Dependency Correlation: Success is strongly negatively correlated with the complexity of the dependency graph.
- Tasks requiring reasoning over long chains of project-local definitions (transitive depth $\ge$ 5) are significantly harder.
- Direct dependency count showed no significant correlation with success, suggesting the difficulty lies in navigating layered abstractions rather than just finding symbols.
Context Retrieval vs. Reasoning:
- Curated > Full: Providing a curated set of dependencies improves performance over the full repository (e.g., Gemini-3-Pro: 41.0% vs. 34.8%).
- Unexpected Insight: The performance gap between Curated and Full contexts is smaller than expected. The authors hypothesize that the "noise" in the Full Repository provides structural hints (recurring abstraction patterns, similar proof structures in other files) that help models anticipate necessary lemmas, even if the exact dependency isn't explicitly retrieved.
Proof Pattern Shift: Proofs in VeriSoftBench rely less on automation tactics (21% vs. 51% in Verina) and more on case analysis and branching structures, indicating a shift from "definition unfolding + automation" to complex structural reasoning.

5. Significance and Impact

Redefining Benchmarks: VeriSoftBench demonstrates that success in mathematical theorem proving does not guarantee success in software verification. The latter requires capabilities to navigate large, heterogeneous codebases and reason through project-specific abstractions.
Identifying Bottlenecks: The paper highlights that current models struggle with multi-hop reasoning through layered project definitions, not just context retrieval.
Future Directions: The results suggest that future proof automation systems need:
- Better mechanisms for handling transitive dependency closures.
- Architectures capable of leveraging structural patterns across a full repository, not just isolated dependency graphs.
- Training data that reflects the density and complexity of real-world verification codebases rather than just mathematical theorems.

In conclusion, VeriSoftBench establishes a new standard for evaluating formal verification tools, revealing that while current LLMs have made progress, significant challenges remain in automating proofs within the complex, interconnected ecosystems of real-world software verification.