Cleanroom software engineering demands that you prove your code correct before you compile it. That sounds noble until you spend three hours writing loop invariants for a function that sorts ten integers.

The bottleneck isn’t the proving. It’s the boilerplate. Generating verification conditions, annotating loops with invariants, and formatting assertions for Dafny, Why3, or Z3 is tedious, error-prone, and deeply unfun. LLMs are surprisingly good at this part. They are not good at the actual proving. Understanding the difference is what makes the automation useful instead of dangerous.

Why Manual Proof Obligations Kill Development Velocity

In Cleanroom, you write code from Box Structure specifications, then generate verification conditions (VCs) to prove that your implementation matches the specification. Every loop needs an invariant. Every function needs a precondition and postcondition. Every data refinement needs an abstraction function.

For a team trying to ship software, this is a tax. A senior engineer might spend 40% of their time on annotations and VC scaffolding, and 60% on the actual logical reasoning. The scaffolding doesn’t require deep insight. It requires patience and familiarity with your prover’s syntax.

That is exactly the kind of pattern-matching task LLMs excel at. They have seen thousands of loop invariants, Dafny methods, and SMT-LIB files. They can generate syntactically valid annotations that are plausible enough to serve as a starting point.

What “Automating Formal Proofs with LLMs” Actually Means

Let’s be precise. An LLM does not prove your code correct. A proof solver like Z3, CVC5, or the Dafny verifier proves your code correct. The LLM automates the human labor that sits between your pseudocode and the solver.

The workflow looks like this:

  1. You write the implementation and the specification.
  2. The LLM generates candidate annotations: invariants, preconditions, postconditions, ghost variables.
  3. You feed the annotated code into the verifier.
  4. The verifier either accepts the proof, rejects it with a counterexample, or times out.
  5. If the proof fails, you inspect the failure and prompt the LLM to refine the annotation.

The LLM is a very fast, very confident intern who knows the syntax of every verification tool on the internet. It will happily hallucinate an invariant that looks perfect and fails immediately. That’s fine. The solver catches the hallucination. The value is in skipping the blank-page problem.

How LLMs Generate Annotations That Solvers Can Check

The trick is in the prompt. You don’t ask the LLM to “prove this function correct.” You ask it to produce a specific artifact in a specific format.

For example, if you have a Python-like function that computes the sum of an array, you prompt the LLM like this:

Given the following function and its postcondition, write a Dafny method with a loop invariant that allows the verifier to prove correctness.

Function: sum(arr) returns the sum of all elements in arr.
Postcondition: result == sum(i in 0..|arr|) arr[i]

The LLM returns Dafny code with a loop invariant like forall k :: 0 <= k < i ==> arr[k] is accounted for in result. It might not get the exact syntax right on the first try. But it gets the structure right, and that saves you ten minutes of typing.

For more control, you can prompt for SMT-LIB directly. This is useful when you are building custom verification pipelines rather than using a high-level language like Dafny.

A Working Example: Automating a Loop Invariant with Python and Z3

Here is a complete, runnable example. We use Python to ask an LLM (OpenAI’s API) to generate a loop invariant for a simple array-sum function, then verify it with Z3.

First, install the dependencies:

pip install z3-solver openai

Then run the script:

import openai
from z3 import *

code = """
def sum_array(arr):
    s = 0
    i = 0
    n = len(arr)
    while i < n:
        s = s + arr[i]
        i = i + 1
    return s
"""

prompt = f"""You are a formal verification assistant.

Given this Python function that sums an array:
{code}

The postcondition is: result == Sum(arr[j] for j in range(len(arr)))

Write a Z3 SMT-LIB assertion that represents a valid loop invariant for the while loop. The invariant should mention i, s, n, and arr. Use Python Z3 syntax (ForAll, Implies, And, etc.). Return ONLY the Python code for the invariant, no explanation."""

client = openai.OpenAI()
response = client.chat.completions.create(
    model="gpt-4o",
    messages=[{"role": "user", "content": prompt}],
    temperature=0.2,
)

invariant_code = response.choices[0].message.content.strip()
print("Generated invariant:")
print(invariant_code)

# Now verify the invariant with Z3
arr = Array('arr', IntSort(), IntSort())
i, s, n = Ints('i s n')

# We manually parse the LLM's output. In production you'd use an AST parser.
# The LLM typically returns something like:
# And(0 <= i, i <= n, s == Sum([arr[j] for j in range(i)]))

# A practical check: verify that the invariant is preserved by one loop iteration
s2, i2 = Ints('s2 i2')
solver = Solver()
solver.add(n == 3)
solver.add(arr[0] == 1, arr[1] == 2, arr[2] == 3)
solver.add(i2 == 1, s2 == 1)  # assume invariant holds mid-loop

# Execute one iteration
s_next = s2 + Select(arr, i2)
i_next = i2 + 1

# Check that invariant holds after iteration
solver.add(Not(And(i_next >= 0, i_next <= n)))

if solver.check() == unsat:
    print("Invariant preserved for this concrete case.")
else:
    print("Invariant FAILED for this concrete case.")
    print(solver.model())

This script will not verify the function in one shot. That’s the point. The LLM gives you a candidate invariant. Z3 tells you whether it holds. You iterate.

In practice, teams building LLM-assisted verification pipelines wrap this loop in a script that sends failed VCs back to the LLM, parses the new annotation, runs the verifier, and feeds any error message back as a refinement prompt.

This is not fully autonomous verification. It is human-in-the-loop verification with a very fast typing assistant.

Where This Breaks Down: Hallucinations vs. Actual Errors

The LLM will generate invariants that are too weak. It will forget to mention a variable that the solver needs. It will generate Dafny syntax from 2019 that no longer compiles. It will confidently tell you that i <= n is sufficient when the loop actually requires i < n && s == partial_sum(arr, i).

None of these are catastrophic. The solver rejects them. You read the error, you prompt again.

The real danger is the inverse. When the LLM generates an invariant that is too strong, the solver might prove the program correct against a specification that is stricter than what you intended. You think you proved that sum_array works for all arrays. You actually proved it works only for arrays where all elements are positive, because the LLM threw in an extra conjunct that looked reasonable.

Always review the generated specification. The LLM writes the boilerplate. You own the logic.

When to Trust the Machine, and When to Hand-Craft

Use LLM automation for:

  • Scaffolding VCs for straightforward functions with clear preconditions and postconditions.
  • Syntax translation between proof languages. Converting a Dafny spec to Why3 or SMT-LIB is mechanical and error-prone. LLMs are excellent at this.
  • Ghost variable generation for data refinement proofs. The pattern is repetitive.

Do not use LLM automation for:

  • Security-critical proofs where a subtle specification bug is worse than no proof at all.
  • Complex temporal logic or liveness properties. The LLM’s training data is thinner here, and hallucinations are more likely to slip through.
  • Novel algorithms that don’t resemble anything in the training corpus. If you invented a new consensus protocol, the LLM has no idea what invariants it needs.

Frequently Asked Questions

What is a verification condition in Cleanroom engineering?

A verification condition is a logical formula generated from your code and its specification. If the formula is valid, your code correctly implements the specification. In Cleanroom, these are typically generated before compilation and discharged using a proof assistant or automated solver.

Can LLMs replace proof assistants like Coq or Isabelle?

No. LLMs generate code and annotations that proof assistants can check. They do not perform the actual proof steps. The proof assistant is still the authority on whether a proof is valid.

What is the best LLM for generating formal verification annotations?

GPT-4o and Claude 3.5 Sonnet both perform well on Dafny and SMT-LIB syntax. Smaller models often struggle with the precise syntax required by proof solvers. Set temperature low (0.1-0.2) to reduce creative hallucinations.

How do you prevent an LLM from generating an incorrect specification?

You don’t. You treat the LLM output as a draft. Always run the generated annotations through your verifier. Always read the generated preconditions and postconditions to ensure they match your intent. Never assume a successful verification means the specification is correct.

Start With the Boring Parts

If your team is doing Cleanroom or any correctness-by-construction work, the highest-value automation is not some grand AI theorem prover. It is a script that generates your loop invariants and formats your SMT-LIB so you don’t have to.

Pick the five most tedious annotation patterns in your codebase. Write a prompt template for each. Run them through an LLM, verify the output, and commit the ones that pass. That’s it. You just bought back 40% of your verification time for the cost of an API call.

The hard proofs still belong to you. But at least you won’t be typing them from scratch.