LLMs

Can LLMs Make Formal Verification Practical?

Anthropic is exploring LLMs for formal software verification, where machine-checkable proofs offer stronger guarantees than passing tests. The approach could reduce manual trial and error, but specification quality, proof planning, and verification costs remain major barriers.

Font size

Anthropic is applying LLMs to formal software verification. The technology can reduce trial and error, but specifications, proof planning, and verification costs remain hard barriers.

Anthropic Uses LLMs to Write Proofs: Can Formal Verification Turn the Tide?

Anthropic recently published research on LLMs and formal software verification. The available source material confirms the research direction but does not provide complete experimental figures that can be checked in this article.

The work has a direct bearing on how coding agents are evaluated: whether the standard can move beyond "passing tests" toward "satisfying machine-checkable specifications."

Original research: https://www.anthropic.com/research/formal-verification

From Copilot to Formal Proofs: LLMs Change the Problem

Copilot, Devin, and many coding agents primarily address the following question:

Given a task, can the system generate runnable code that ideally passes tests?

Formal verification asks a different question:

Given a specification, can the system construct a machine-checkable proof that confirms the program satisfies it?

Take ITPs (interactive theorem provers) such as Lean, Coq, and Isabelle. Developers may need to work with:

  • spec: the properties the program must satisfy;
  • proof script: a sequence of steps that derives the conclusion;
  • tactic: a command that directs the prover to search for a particular subgoal;
  • auxiliary definitions and lemmas: rewriting the program into a form that is easier to reason about.

A correctness proof for a sorting algorithm might need to establish properties such as "the result is ordered," "the length is unchanged," and "the elements are only rearranged." In the past, formal methods experts typically handled this work by hand, sometimes taking weeks.

LLMs have a specific role to play here. They can generate proof drafts, complete tactics, rewrite failed steps, and attempt to turn natural-language specifications into formal expressions.

Ordinary code completion predicts whether "the next segment of code looks plausible." Proof completion predicts whether "the proof prover will accept the next step." The latter has clear machine feedback, but its search space is far more punishing.

Why Formal Verification Is Hard, and Where LLMs Fall Short

Systems such as Lean, Coq, Isabelle, and Dafny are already highly mature.

Three issues usually stand between teams and successful formal verification.

1. Writing a spec is harder than writing code

Code can be written first and tested later. Specifications cannot. Developers must first define precisely what "correct" means.

"The password must be secure" is not a verifiable specification. Developers also need to define input length, permitted characters, the validation algorithm, failure behavior, and boundary conditions.

Worse, if a specification is wrong, a machine may diligently prove an incorrect claim.

2. Proof search suffers from combinatorial explosion

A prover does not follow a straight line; it explores a vast search tree. Each step may introduce new lemmas or intermediate goals.

Developers must also decide whether to unfold definitions, reuse existing theorems, or change the induction strategy.

A failed tactic does not mean that no proof exists. The current path may simply be a dead end. LLMs are prone to mistaking a local failure for evidence that the overall approach is wrong.

3. Failure messages are not always human-friendly

When Coq or Lean reports an error, it typically provides the goal state, local hypotheses, and unresolved subgoals.

The information is precise but not necessarily easy to understand. LLMs can help at the tactic level by explaining errors, proposing candidate steps, and passing them back to the prover for checking.

They are still not necessarily good at high-level proof planning. Consider questions such as:

  • Why does this invariant hold?
  • Does the specification cover the real requirements?
  • Would a different induction method produce a shorter proof?

Adding a few more tactics will not automatically resolve these questions.

Models can also hallucinate. They may invent theorems, cite nonexistent lemmas, or use irrelevant proofs to conceal gaps in a specification.

Formal verification can check the proof itself. It cannot automatically prove that the specification is correct.

What Was Actually Done, and Can It Be Reproduced?

The source material confirms that Anthropic's research uses LLMs to assist with formal specifications, proof drafts, and verification-related code.

However, the available draft does not include enough information for readers to verify the experimental tasks, sample size, success rate, human interventions, or benchmarks. Those figures cannot be invented.

The draft also cites a Hacker News link: https://news.ycombinator.com/item?id=50202217.

Its 11 points and 1 comment are dynamic page data and should be checked again before publication. If they cannot be verified, the specific figures should be removed and replaced with wording such as "limited public discussion."

Reproducible material should include at least:

  • the task set;
  • pass@k;
  • model and sampling configurations;
  • permitted human interventions;
  • failure trajectories;
  • whether novel tasks were used to prevent training-data contamination.

At present, this work is better viewed as an engineering direction worth following than a validated product capability.

If It Works, How Will AI Programming Be Evaluated?

Coding agents are currently compared largely by how much code they generate, how many files they cover, and whether they pass SWE-bench.

These metrics require results to pass specific tests. Uncovered branches, concurrency races, memory issues, and specification ambiguities can still remain in the code.

SWE-bench and HumanEval mainly test whether code runs and passes specified tests. They do not require complete formal correctness.

If LLMs can participate reliably in proof development, evaluations may gain another layer: satisfaction of machine-checkable specifications.

This would weaken some interpretations of existing benchmarks, but it would not simply replace them.

SWE-bench measures issue resolution in real repositories. Formal verification requires developers to supply precise specifications first. The two serve different purposes.

The most useful product is also unlikely to be a standalone chat interface that "writes Lean." It is more likely to integrate with IDEs and CI systems:

  1. Read code and issues, then generate candidate specifications;
  2. Search for proofs in Lean or Coq;
  3. Return failure logs to the model for repair;
  4. Store successful proof artifacts in the repository;
  5. Continuously check in CI whether the specifications still hold.

Three Questions Will Determine Whether It Becomes Practical

1. Will experts guide the LLM, or will the LLM work independently?

The difference is substantial.

If experts continually select theorems, break down goals, and correct failed approaches, the resulting efficiency gains cannot all be attributed to the model.

When reading the research, readers should examine the intervention protocol before looking at the final pass rate.

2. Is the training data contaminated?

Public corpora of formal proofs are far smaller than natural-language code datasets.

Popular theorems and proofs from Lean, Coq, and Isabelle may appear repeatedly in training sets. Testing only on existing theorems can inflate estimates of the model's ability to handle new tasks.

3. What will ordinary engineering teams gain?

Academic ITP users have already spent substantial time writing specifications and proofs, so automated assistance is a natural extension of their workflow.

Ordinary engineering teams, however, often struggle to define requirement boundaries. For them, the bottleneck may not be proof search, but deciding what needs to be proved in the first place.

Verification costs will not disappear either. Reducing manual trial and error does not mean that the costs of proof checkers, build environments, and theorem libraries will fall at the same rate.

Editorial Perspective

This work matters not because LLMs have already replaced formal verification experts, but because it pushes the endpoint for coding agents beyond "the code runs" toward "the proof can be checked." Copilot primarily accelerated code generation, with reviewers and tests providing safeguards. Proof provers now offer harder feedback, but specifications, proof planning, and human intervention remain unsolved.

In the near term, cryptography, compilers, and other safety-critical code are likely to benefit first. Whether the broader development workflow follows will depend on whether LLMs can reduce human planning rather than merely trying more tactics.

The key distinction is that formal verification does not accept claims that merely look reasonable; it accepts only machine-checkable derivations. The strength of the original experiments under strict human-intervention conditions remains unclear. The paper's data and the dynamic Hacker News figures should be verified before publication.

Source: https://www.anthropic.com/research/formal-verification