Neuro-Formal Verification: Agentic Language-Agnostic Formal Program Reasoning
AuthorsShuvendu K. Lahiri
AffiliationsMicrosoft Research
Resources
NFV uses AI agents to translate ordinary code into machine-checkable formal proofs, making software verification more accessible while revealing the limits of end-to-end soundness.
Key results
Balanced Python program-specification entries used for evaluation.
Share of all entries correctly resolved by the combined machine-checked pipeline.
Precision among the verdicts issued by the combined pipeline.
Share of buggy programs for which CBMC produced a counterexample.
Precision of the baseline that answered every entry without a checkable artifact.
Precision when the agent-verifier combination proved 98% of both correct and buggy programs.
What the paper found
Neuro-formal verification, or NFV, extends formal reasoning to mainstream languages by having an AI agent translate a Python program, its natural-language specification, and environment assumptions into a verification-aware representation, then submit the result to a sound backend such as Dafny or CBMC. Its central safeguard is staged, goal-blind transformation: library models and preconditions are frozen before the specification is exposed, source lines receive provenance tags, and proof search may add only checked lemmas, invariants, and tactics. This prevents an agent from quietly rewriting the program or weakening the goal to obtain a proof, although NFV cannot guarantee end-to-end soundness when environment assumptions or translations are wrong. On the balanced nl2post-safe dataset of 206 Python program-specification entries, using OpenAI’s gpt-5.6-sol, the Dafny pipeline issued 128 machine-checked verdicts, correctly resolving 57% of all entries at 92% precision. A CBMC backend refuted 63% of buggy programs at 90% precision, while an LLM-as-judge baseline reached only 72% precision and produced no checkable artifact. The unstaged agent-verifier baseline proved 98% of both correct and buggy programs, yielding just 50% precision, demonstrating that proof search alone is insufficient without artifact isolation and staging. The main failure source was incorrect precondition synthesis, showing that intent formalization remains the bottleneck. The results position NFV as empirical, auditable formal program reasoning rather than a complete correctness guarantee, with applicability envisioned beyond Python to languages such as C#, Java, and JavaScript.
Original abstract
Formal verification provides the strongest correctness guarantees for software, and verification-aware languages can produce sound, machine-checked proofs. Recent AI coding agents have sharply lowered the cost of constructing such proofs. Yet few mainstream developers benefit: most use languages without formal-verification support, and formalizing properties and modeling execution environments demand formal-methods expertise. Proof therefore remains reserved for a few notable artifacts, while production software is attested mainly through review and testing. We introduce neuro-formal verification (NFV), which brings this automation to mainstream languages. An AI coding agent formalizes a source-level verification problem into a proof obligation in a verification-aware language, discharged by an established sound verifier aided by agentic proof search. Staged, goal-blind transformations reduce the risk of proving an artifact that does not faithfully represent the source program, property, or environment. Since NFV cannot ensure the soundness of this formalization, it optimizes for empirical accuracy rather than end-to-end soundness, while insisting on machine-checked evidence for every verdict. Experiments with current frontier models on a balanced dataset of correct and buggy Python solutions demonstrate the effectiveness of our approach. NFV with Dafny correctly resolves 57% of all entries, at 92% precision among its verdicts; with a CBMC backend, it produces a counterexample for 63% of the buggy programs at 90% precision. In contrast, an LLM-as-judge baseline achieves only 72% precision while answering every entry without any checkable artifact, and an unstaged agent-verifier combination proves 98% of both the correct and the known-buggy programs, yielding only 50% precision. Together, they confirm that both proofs and staging benefit an AI agent's formal program reasoning.
Read the original paperMore in AI Reasoning
Browse all 39 papers →Knowing When Thinking Is Not Enough: Teaching Small Reasoning Models to Reason Beyond Their Parametric Knowledge
Chanuk Lee, Minki Kang, Sangwoo Park, Woongyeong Yeo, Jinheon Baek, Sung Ju Hwang
FlyBy teaches small reasoning models to recognize when more internal thinking will not help and instead ask a stronger model for missing knowledge.
On Language Drift during RLVR Post-Training
Michael Sullivan, Alexander Koller
RLVR can make reasoning models increasingly use strange internal languages, and preventing that drift may require sacrificing some performance.
Principled Thoughts for Latent Recursive LLM Systems
Fahd Seddik, Fatemeh Fard
REST teaches latent LLM agents to form more causal, minimal, separable, and stable internal thoughts, improving reasoning accuracy and interpretability.