FVSpec: Real-World Property-Based Tests as Lean Challenges

arXiv:2606.01008 · cs.SE, cs.AI · Submitted 2026-05-31 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "FVSpec: Real-World Property-Based Tests as Lean Challenges".

Jane: The paper was written by Quinn Dougherty, Max von Hippel, Simon Henniger, Hazel Shackleton and Mike Dodds from Forall R&D, Galois Inc and Benchify and Harvard University.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Jane: We also have Lu with us today — senior AI researcher at Tsinghua.

Tom: We also have Meng with us today — lead engineer at a mysterious AI startup.

Jane: We also have Lalam with us today — the in-house Large Language Model.

Tom: Alright, let's get started.

Title: Tom: So, let’s talk about the title and what it means to really ground formal methods in messy reality. FVSpec: Real-World Property-Based Tests as Lean Challenges is a huge project because it bridges that gap between actual code and mathematical rigor.

Jane: It’s not just academic problems; it's the actual messy code used by practicing software developers, which makes the scope of this work truly impressive.

Lu: And I think that’s the real genius of the whole project, because traditional benchmarks usually use curated or synthetic problems, which are too simple to be useful.

Meng: This isn't just a handful of simple tests; it’s a representative sample of the entire diversity of real-world software development, and that scale is what makes it impactful.

Lalam: It represents a democratization of verification, moving beyond specialized experts to using the logic written by everyone who codes in industry.

Tom: The authors give us eleven thousand thirty-nine PBTs across three hundred thirty-three repositories—a number that speaks volumes about the breadth of this project.

Jane: And it’s comforting to think that this method isn't just about academic exercises but about applying genuine engineering logic that mirrors how developers actually build things in practice.

Lu: The sheer variety of these projects is what Lu finds most exciting, because it proves we are moving away from artificial environments toward a true reflection of software development.

Meng: That scale shows us this is not just a proof-of concept; it’s a foundational dataset ready to be used by AI agents in production environments.

Lalam: This is about moving the conversation from perfect theory to achievable reality, making the potential for reliable systems truly tangible.

Tom: And we’ll discuss how they are going to make this data actionable in our next segment, where we look at the summary of what they achieved.

Summary: Tom: In the last segment we looked at the scope, and now we want to talk about the actual findings of FVSpec: Real-World Property-Based Tests as Lean Challenges. The sheer volume of data is staggering.

Jane: They found eleven thousand thirty-nine PBTs across three hundred thirty-three different repositories, and that’s just a snapshot of the real world.

Lu: And I think that’s the real genius—that this collection captures all those weird edge cases and complex interactions that synthetic examples simply cannot replicate.

Meng: Seeing how diverse these tests are, it shows us this isn't a homogeneous set; it’s a comprehensive sample reflecting the entire spectrum of software needs.

Lalam: This represents a massive shift in how we define what is verifiable, moving beyond specialized logic to using the collective wisdom of all programmers.

Tom: The authors describe this process as FVSpec:PBT, and it successfully capturing all that complexity within a single database structure.

Jane: It’s important to remember that this isn' not just about the number of tests, but the quality and variety they is capturing in real-world scenarios.

Lu: The fact that these are real-world examples means the AI agents are being trained on data far out of distribution from what they usually see.

Meng: That diversity ensures that when we start using this dataset, we aren't just getting a few simple passes; we’re testing against true industry complexity.

Lalam: This is about making verification accessible to the moving forward, allowing us to trust the systems that shape our daily lives with genuine certainty.

Tom: And we’ll talk about the technical brilliance of how they move this data into a verifiable challenge in Segment four.

Improvements: Tom: Now we are talking about the technical meat of the paper, specifically how they turn those raw PBTs into a Lean specification. The authors call this "agentic transpilation," which is an advanced way of using AI to perform this complex translation.

Jane: It’s not just automated translation; it’s an iterative process where an agent repeatedly types its work and then checks it against the Lean compiler using a loop that can run up to sixteen times. This is how they handle the messy details.

Lu: And I find this fascinating, especially how they manage side effects in real code—like when a function talks to a database or uses a clock. They treat those external systems as uninterpreted interfaces, which is such an elegant way to maintain mathematical purity while dealing with messy reality.

Meng: That's critical for implementation; if the AI agent can handle these interaction points robustly, it means it isn't just proving theoretical code but actual running software. The structural faithfulness metric they use to measure this translation is a key indicator of quality.

Lalam: This method ensures that as we move towards autonomous verification, the AI isn't forced to ignore the real-world context; it allows us to formalize the behavior even when the underlying infrastructure is unpredictable.

Tom: It’s a massive methodological improvement over previous work, so we have to wrap up and look at what this means for all in Segment five.

Conclusion: Tom: So, we’ve seen how FVSpec: Real-World Property-Based Tests as Lean Challenges tackles the real complexity of software by turning real-world property-based tests into verifiable Lean challenges, which provides such a solid foundation for testing AI models.

Jane: It's comforting to think that this method isn't just about academic exercises but about applying genuine, messy engineering logic that mirrors how developers actually build things in practice.

Lu: I'm particularly excited by the idea that this opens up a whole new frontier where autonomous agents are being trained on real-world code, moving beyond the limitations of synthetic problems to is truly possible.

Meng: This will push the boundaries of what AI can do in a professional setting; it’s moving from handling simple tasks to tackling complex, industrial problems.

Lalam: The cultural impact is the possibility that automated verification could become the norm, ensuring that AI-generated systems are not just functional but provably trustworthy.

Tom: We're going to close up and say goodbye to all of you now.

Lu: This work by the authors has truly opened a new avenue for AI proof generation, setting a standard for how we should evaluate these systems moving forward.

Meng: I think the practical implications for building safer software are just enormous, giving us confidence in designs we've never been able to verify before.

Lalam: It is a beautiful convergence of engineering practice and mathematical certainty, truly reflecting the potential of AI to deliver flawless reliability.

Tom: That's all for today everyone, we hope you enjoyed this discussion on FVSpec: Real-World Property-Based Tests as Lean Challenges, and we'll see you next time.

Forall R&D, Galois Inc · Benchify · Harvard University

cs.SE, cs.AI

Submitted: 2026-05-31

Updated: 2026-09-14

Code: https://github.com/scality/runner-manager

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 76/100

The gist: As AI systems generate an increasing share of global code, formal verification offers a principled method to ensure correctness, yet current benchmarks are largely synthetic or curated.

Key concepts

Property-Based Tests (PBTs)
These are tests derived from actual industry codebases rather than simple synthetic examples. They capture the full diversity of real-world software needs, including complex interactions and difficult edge cases that traditional testing methods often miss.
Agentic Transpilation
This is an advanced AI process used by the authors. An AI agent iteratively translates raw property-based tests into a verifiable format (Lean specification) through a loop, checking the result against the Lean compiler.
Lean Specification
This represents formal mathematical rigor applied to code. It allows researchers to translate complex, messy real-world behaviors into a verifiable structure, ensuring systems are provably trustworthy and reliable.

Terminology

Summary

As AI systems generate an increasing share of global code, formal verification offers a principled method to ensure correctness, yet current benchmarks are largely synthetic or curated. This paper addresses this gap by presenting FVSpec, a comprehensive benchmark designed for evaluating AI models and agents on real-world formal software verification tasks. By deriving challenges from publicly available property-based tests (PBTs), FVSpec provides a dataset that is genuinely out of distribution relative to existing training data, offering a critical test case for the future of autonomous proof generation in industry.

The FVSpec Corpus Generation

The foundation of the benchmark is FVSpec:PBT, which consists of 11,039 deduplicated Python PBTs scraped from 333 open-source repositories. The scraping process involved several stages:

  • Discovery: Crawling the Hypothesis dependency graph.

  • Licensing: Filtering out non-permissive licenses to ensure a usable environment for the researchers.

  • Extraction: Shallow-cloning and parsing the Python code to recover the transitive closure of locally-defined functions called therein. This resulted in 11,039 PBTs across 303 distinct projects.

Translating PBTs into Lean Challenges

The core difficulty lies in translating these practical tests into formal specifications. The authors utilize an agentic transpilation pipeline to convert the Python code and its associated assertions into Lean 4 specifications (FVSpec:FV). This process involves three phases:

  1. Function Discovery: Using tree-sitter to extract the function under test and its dependencies, creating a stubs when dynamic dispatch occurs.

  2. Agentic Transpilation: A formalization agent translates the PBT into Impl.lean (a computable port of the the function) and Spec.lean (one theorem per Hypothesis assertion, with proofs left as sorry). The process includes an iterative LSP-repair self-loop to ensure type checking success.

  3. Post-processing: Validating and grading the output based on metrics like structural faithfulness and deduplication.

Handling Real-World Side Effects

A major challenge in real-world software is that PBTs often interact with messy real-world environments involving databases, sockets, or the system clock. The authors address this complexity through axiomatization:

  • The formalization agent treats the effectful world as an uninterpreted interface.

  • Core entities and operators are translated into Lean structures.

  • Pure plumbing—such as a database or queue—is introduced as opaque axiom declarations and threaded through the theorem, ensuring the contract holds over all interpretations of those axioms.

Results and Evaluation

The pipeline successfully generated 9,415 samples from 2,772 distinct PBTs (85% success rate). The resulting data is analyzed using several quality metrics:

  • Structural Faithfulness: The overall distribution shows a mode above 0.5, indicating that the majority of translations preserve the essential structure of the source PBT.

  • Difficulty: A calibrated difficulty predictor classified 62% of challenges as hard.

  • Model Performance: Evaluations on three frontier models (Claude Sonnet 4.6, Claude Opus 4.7, and GPT 5.4) showed mean success rates of 70% on easy problems and only mean [a] 49% on hards, confirming that the benchmark is far from saturated.

Improvements for AI systems

To improve AI systems in the domain of formal verification (FV), we must fundamentally change the nature of the training data and the complexity of the tasks used for evaluation. The FVSpec framework provides these critical improvements.

  1. Shift from Synthetic to Real-World Data Distribution:

  • Action: Replace curated, pedagogical, or purely mathematical verification datasets (e.g., APPS, PutnamBench) with the FVSpec corpus (11,039 real-world Python PBTs).

  • Specific Impact: This forces the AI model to learn from code written by practicing engineers that is not designed to be verifiable. The resulting AI agents will be trained on data exhibiting genuine, complex software engineering patterns.

  1. Mandatory Modeling of Real-World Side Effects via Axiomatization:

  • Action: Integrate the uninterpreted interface methodology used in FVSpec into the formalization pipeline (i.e., transforming external calls—databases, queues, system clocks—into opaque axiom declarations).

  • Specific Impact: This forces the AI to learn to verify contracts that hold across all interpretations of an external environment, rather than assuming a perfect or known internal state. The AI will no longer be expected to model the implementation details of black-box dependencies, only their behavioral constraints.

  1. Iterative Formalization and Error Recovery Training:

  • Action: Utilize the multi-agent, iterative process (Tree-sitter to Agentic Transpilation to LSP-Repair Self-Loop) as a training paradigm for AI agents attempting to formalize code.

  • Specific Impact: This teaches the AI to handle complex structural failures (e.g., dynamic dispatch, metaclasses) by forcing it to generate an initial stub and then iteratively refine the implementation (Impl.lean) while maintaining type safety via the Lean Language Server Protocol (LSP).

  1. Granular Difficulty-Aware Evaluation:

  • Action: Implement a dual difficulty grading system (Easy/Hard) based on both structural complexity and the resulting output characteristics (e.g., number of theorems, size of Lean output).

  • Specific Impact: AI performance is no longer measured by simple pass/fail rates. Instead, success is evaluated against the specific challenge level, allowing researchers to track whether an AI model is proficient at solving easy problems or if it genuinely possesses the reasoning capacity for hard real-world tasks (where 49% success rate currently exists).

The improved AI system will be capable of:

  1. Autonomous Formal Specification Generation: Generating Lean 4 specifications from arbitrary, complex source code written in natural programming languages (Python), achieving a high level of structural faithfulness (aiming for >0.85).

  2. Robust Verification under Non-Deterministic Conditions: Proving that a program maintains its invariant even when external, unmodeled systems behave according to defined axioms (e.g., proving that a system handles two sequential queue enqueues without exceeding the maximum allowed runner count).

  3. Targeted Performance Benchmarking: The system can be rigorously tested against the FVSpec corpus to determine if its capabilities match the frontier models' current modest performance (70% easy / 49% hard), or if it demonstrates a significant leap in capability, specifically in handling real-world complexity.

Abstract

We present a benchmark for evaluating AI models and agents on real-world formal software verification tasks. We first scrape 11,039 property-based tests (PBTs) from real-world Python repositories, then automatically translate 2,772 of them (25%) into 9,415 Lean 4 specifications with sorry placeholders (about 3 formalizations/PBT; we retain multiple attempts when none dominates on quality metrics). Translating PBTs into Lean specifications is challenging: it requires modeling Python semantics in Lean, inferring the logical property encoded in an imperative PBT, and handling the inherent difficulties of dependently-typed programming in a seldom-used language. We describe a three-agent LLM pipeline for transpiling PBTs into Lean specifications, evaluate coverage and quality metrics, and provide baselines for proof generation using several automated and model based approaches. All code (scraper and agents) and data (PBTs and Lean specifications) are open source. Our benchmark aims to drive progress on the underexplored problem of AI-assisted formal verification of real-world software, which is of increasing interest as AI produces more and more of the world's code.

Sources

Related papers