Click any tag below to further narrow down your results
Links
The author argues that AI has pushed formal verification into the mainstream, but "formally verified" is a misleading label because proofs only cover what's specified, and the trusted base (definitions, models, provers) is still hard to check. He's optimistic about proving specific properties of software, especially single-threaded code, and thinks random testing will help validate the models used.
- Formal verification is now economically valuable and widely discussed, with AI generating large volumes of proofs, but that volume makes it more important to scrutinize what is actually trusted.
- Testing produces reviewable bug reports, while proofs rely on hard-to-verify components like specifications, machine models, and provers, so "formally verified" should always come with caveats about what's proven and what's assumed.
- Software with user-facing, "bouba" layers resists uniform correctness proofs, but specific properties of single-threaded programs are likely provable within years, with random testing helping to validate the models.
Google DeepMind used a multi-agent AI system called AlphaProof Code to mathematically prove security properties of the actual compiled code behind Signal's encryption protocol, a task that usually takes expert teams years. The whole verification took four weeks, with humans reviewing only about one percent of the generated proofs.
- Formal proofs were generated for the real Signal implementation, not just its design, covering over six million lines of Lean code.
- The system was tested by reintroducing two previously fixed bugs, and in both cases it produced a machine-checked proof that the buggy version was insecure.
- Human experts only needed to review about one percent of the codebase, since Lean automatically checks the rest.
Axiom has released a Lean formalization of the Stacks Project, the open-source algebraic geometry reference, as a single machine-checked library of about 16 million lines. It is meant for researchers and AI agents to import definitions and theorems into new formal proofs.
- The library covers the full Stacks Project, roughly 7,500 pages, and is described as the largest integrated, reusable formalized mathematics library built so far.
- Each Lean declaration links back to the permanent Stacks tags, so readers can compare the code side by side with the original text and a dependency graph.
- Formalization surfaced dozens of statements in the Stacks Project needing fixes, including missing hypotheses and claims that fail in full generality, with agents building counterexamples.
This paper argues that verifying AI-generated mathematical proofs through formal languages like Lean doesn't actually validate the original natural language argument, because translating math text faithfully from English to formal logic is computationally harder than solving the Halting problem. The authors demonstrate this with concrete examples, including OpenAI's claimed proof of Navier-Stokes blow-up, showing the formalized version doesn't match what was originally stated.
- Resolving ambiguities in mathematical natural language to enable semantically faithful translation has infinite complexity in the Solvability Complexity Index hierarchy — harder than any computable problem including the Halting problem.
- A Lean proof can pass mechanical verification while the formalized statement diverges from the original natural language proof, creating a false sense of security.
- OpenAI's announced Navier-Stokes blow-up proof is used as a concrete case where the Lean formalization doesn't correspond to the natural language version.