Formal Verification is Not Verifiable
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.
Formal verification has gone mainstream over the past year, according to the author, Alperen Keles. Startups in the space have multiplied, Claude reportedly wrote a billion lines of Rocq for one verification project, and people like the Vercel CEO and leads on Codex and Cursor are talking about it. Early firms like Theorem (working with Anthropic on binary verification) and Harmonic (verifying C programs and hardware designs) are showing the work has economic value beyond academic proofs. The author's framing is that AI is pushing "verifiability" to the center of how we build software, and he is optimistic about formal verification overall. His core worry is about what "formally verified" actually means. A proof only holds relative to its trusted components: the definitions, the models of machine and process semantics, the provers, and the compilers. Test failures produce a concrete bug report a human can check, while a formal proof makes a universal claim that collapses if any trusted piece is wrong.
The main technical idea is shrinking that trusted base. Binary verification, which proves facts about compiled machine code rather than source programs, removes the need to model each high-level language separately and sidesteps compiler correctness, which he notes is shaky since compilers have many bugs. He argues this still leaves a large trusted surface, including machine semantics and Linux process semantics, so the gain is partial. He also says the phrase "formally verifying X" is sloppy and should be "formally verifying X properties of Y." Past landmark projects like CompCert and seL4 were trusted to prove non-trivial properties because the field's reputation depended on it. AI has changed that by multiplying the volume of formally verified work, perhaps by around a thousand times by his estimate, so the old assumption no longer holds. He wants every verification claim to come with explicit caveats about what is trusted, what is proven, and what is not. Some of this is already happening: Lean proofs are checked against possible kernel soundness bugs, a tool called comparator is becoming a standard validator, and recent announcements from Anthropic/Theorem and Google DeepMind's Signal work spell out their limits.
Keles separates software into "kiki" layers, like databases and engines, which have clean mathematical abstractions, and "bouba" layers, like user interfaces, where correctness is fuzzy and no single formal notion applies. Claims of "formally verifying everything" or "bug-free software" don't hold for the bouba parts, though specific properties can still be proven there. He is most optimistic about proving general properties of single-threaded programs, and he mentions a personal bet that single-threaded code translation might be solved by 2030. The post is a follow-up to his earlier essay "Test, don't (just) verify," and the verifiability theme runs through both.