LLM Formal Proof Evaluation: Metrics, Cost-Effectiveness, and Production Workflows

1. Why formal proof has become a hard test for LLM capability

Evaluating LLMs on natural-language generation or code completion is highly subjective: output can look fluent and plausible, making it difficult to quantify correctness. Formal proof is valuable because it turns evaluation into a machine-checkable binary problem—a proof script is either accepted or rejected by a checker, with no middle ground.

When a model is asked to formalize research-grade statements such as Fermat’s Last Theorem, what is exposed is more informative than merely whether it can produce a proof:

• Verifiability: The result is determined by the checker rather than a human reviewer, eliminating scorer bias.
• Long-range consistency: A proof may contain hundreds or thousands of steps. The model must remain consistent across previous lemmas, names, and type constraints. This is a realistic stress test for long-context handling and reasoning.
• Reproducibility: The same proof script can be checked repeatedly by any compliant checker, allowing third parties to rerun the experiment independently.

In other words, these tasks provide a rare clean reward signal. This is also why the evaluation itself must be rigorous—if metrics are defined vaguely, conclusions become distorted.

2. Turning “actual capability” into measurable metrics

Do not judge a model upgrade by a vague sense that it feels stronger. Break capability into the following measurable dimensions.

2.1 Pass-rate metrics

• pass@1: The proportion of single-sample attempts accepted by the checker. It reflects out-of-the-box usefulness and is most closely related to real cost.
• pass@k: The proportion of tasks for which at least one of k attempts passes. It reflects the capability ceiling.
• Tiered pass rates: Results should be reported separately by task difficulty bucket to prevent averages being inflated by easy tasks.

Reporting only pass@k is self-deceptive: as k increases, cost increases, and success may come from brute-force guessing. Any pass-rate number must be reported together with the sampling budget.

2.2 Proof-quality metrics

Even among proofs accepted by the checker, quality can vary widely:

Metric	Meaning	Why it matters
Script length	Number of proof steps or characters	Longer scripts are harder to maintain and may contain redundant enumeration.
Unclosed goals	Remaining placeholder goals	Some checkers may tolerate placeholder goals, so they must be counted explicitly.
Axiom / assumption dependencies	Which external assumptions the proof relies on	A proof that passes by relying on strong assumptions may not have practical meaning.
Retrieval-hit style	Whether existing lemmas in the library are reused	Reflects real mathematical organization ability.
Manual edit effort	How many lines a human must change before acceptance	Directly affects practical deployment.

It is better to elevate “accepted by the checker” to a composite criterion: accepted + zero placeholder goals + axiom-dependency allowlist validation. Otherwise, metrics can easily be gamed.

2.3 Stability metrics

Sample the same task 5–10 times and record the variance of pass rates. Models with high variance create unpredictable retry costs in pipelines, and these hidden costs are often ignored during pilot testing.

2.4 Version drift

Theorem-prover library APIs evolve. A historical proof that passed yesterday may fail to compile today because a lemma was renamed or a type class changed. The evaluation environment must pin the exact versions of the checker and dependency libraries, and rerun the full baseline whenever the model changes. Otherwise, you are comparing two different problems.

3. Evaluation experiment design: making conclusions reproducible

3.1 Tiered task set

Construct a task set along an obtainable difficulty gradient, with at least 30 tasks per tier for statistical significance:

1. L1 basic lemmas: Algebraic rewriting, simple inequalities, and set operations.
2. L2 textbook theorems: Standard results such as the Fundamental Theorem of Calculus and basic isomorphism theorems in group theory.
3. L3 competition or selection problems: Problems requiring multi-step constructions and technique combinations.
4. L4 research-grade targets: Statements such as Fermat’s Last Theorem, requiring thousands of lines and multiple layers of abstraction. These are mainly used to observe long-range organization ability rather than to pursue a high pass rate.

3.2 Variable isolation

When comparing models, everything except the compared item must remain the same:

• Sampling temperature, top-p, and maximum output length.
• Context budget for a single session and history-trimming strategy.
• Checker timeout, ideally set separately by task tier.
• Retry strategy and prompt-template version.
• Whether retrieval augmentation is allowed. If allowed, both sides must connect to the same retrieval corpus.

3.3 Evaluation execution skeleton

def evaluate(model, task_set, prover, k=5, timeout=600):
    records = []
    for task in task_set:
        attempts = []
        for i in range(k):
            resp = model.generate(
                prompt=render_prompt(task.statement, task.context),
                temperature=0.7,
                max_tokens=8192,
            )
            proof_path = write_sandbox(resp.text, task.id, i)
            verdict = prover.verify(
                path=proof_path,
                timeout=timeout,
                require_no_placeholder=True,   # reject residual placeholder goals
                axiom_allowlist=task.axioms,   # validate axiom dependencies
            )
            attempts.append({
                "task": task.id, "try": i,
                "ok": verdict.ok,
                "steps": verdict.step_count,
                "prompt_tokens": resp.usage.input,
                "completion_tokens": resp.usage.output,
                "latency_s": resp.latency,
                "error_class": verdict.error_class,  # type error / timeout / lemma not found / logical failure
            })
        records.extend(attempts)
    return aggregate(records)   # tiered pass@1, pass@k, variance, and cost

Three important design points are easy to skip:

• Error classification: Classify failures into four categories: “syntax/API unfamiliarity,” “wrong search direction,” “mathematical reasoning error,” and “timeout.” The optimization paths are completely different. Syntax/API unfamiliarity is addressed through retrieval augmentation and few-shot examples; only mathematical reasoning errors suggest changing models.
• Persist raw artifacts: Save prompts, outputs, and full checker logs for each attempt to support later attribution and regression.
• Sandboxed execution: Proof scripts generated by models are untrusted code and must be executed inside restricted containers with limits on CPU, memory, and runtime, and with no external network access.

4. Cost-effectiveness modeling: low unit price is not always low cost

4.1 Cost per valid proof

The objective function that should actually be optimized is:

Cost per valid proof = total spend / number of accepted and qualified proofs
Total spend = inference cost + retry amplification + retrieval and orchestration overhead + storage and compute + manual fallback labor

Retry amplification is the most frequently underestimated item. If pass@1 is 30%, obtaining one qualified proof requires about 3.3 attempts on average, amplifying inference spend by more than threefold. If multiple sampling and verification loops are also enabled, the amplification stacks further.

4.2 A demonstrative example

The following values are assumed numbers for illustration only and do not represent any real product performance:

Plan	Unit price (relative)	pass@1	Average attempts	Inference cost per proof
A	1.0	45%	2.2	2.2
B	0.35	12%	8.3	2.9
C	2.4	62%	1.6	3.8

The conclusion is counterintuitive: plan B has a unit price of only 35%, but because of excessive retries, its cost per valid proof is higher than plan A. Plan C has the highest unit price and is cost-effective only when manual review costs are very high or when rework costs after failures on long proofs are substantial.

Therefore, cost-effectiveness must be decided by task-value tiers: for high-volume lemma completion on L1/L2 tasks, optimize for the lowest cost per valid proof; for L4 research-grade targets, failure itself is informative, so cost-function metrics are not necessary.

4.3 Hidden cost of manual intervention

A proof that requires a human to edit 20 lines before acceptance differs dramatically from one that passes in a single attempt, and the value difference in a pipeline far exceeds the token-price difference. It is advisable to include “average manual edit lines” and “average manual intervention time” in the cost model rather than only accounting for API bills.

5. Engineering deployment: connecting models to verification loops

Single-turn generation has a low upper bound on success rate. Real gains come from closed loops.

5.1 Generate-check-repair loop

Error messages returned by the checker are a natural, high-density feedback signal. Feeding them back into the model usually improves effective pass rates significantly:

def prove_with_loop(model, task, prover, max_rounds=4):
    history = [{"role": "user", "content": render_prompt(task.statement)}]
    for rnd in range(max_rounds):
        answer = model.generate(messages=history, temperature=0.6)
        path = write_sandbox(answer.text, task.id, rnd)
        verdict = prover.verify(path=path, timeout=task.timeout,
                                require_no_placeholder=True)
        if verdict.ok:
            return {"success": True, "rounds": rnd + 1, "proof": answer.text}
        # Feed back only the minimal necessary feedback: error location + error type + relevant goal status
        history.append({"role": "assistant", "content": answer.text})
        history.append({"role": "user",
                        "content": summarize_errors(verdict.diagnostics)})
    return {"success": False, "rounds": max_rounds}

Feedback should be compressed and structured. Do not feed back thousands of lines of raw logs—this wastes context and can distract the model with irrelevant information. Set both a maximum number of rounds and a cumulative cost cap to prevent unlimited spending on the hardest tasks.

5.2 Retrieval augmentation

Build an index over formalized mathematical libraries, and inject similar lemmas, definitions of the same type, and common strategies as context. This addresses the most frequent failure mode—“the library already has this lemma, but the model does not know its name.” Improvements in retrieval quality often come faster than switching to a stronger model.

5.3 Caching and batch processing

• Cache generation results and verification conclusions by the hash of normalized statements to avoid paying repeatedly.
• Put verification tasks into a message queue for asynchronous decoupling. Write proof scripts to object storage and consume them with a stateless worker pool on a container platform for elastic scaling during peaks.
• Use a logging service to collect invocation and verification records centrally, and use monitoring alerts to track cost slope, sudden pass-rate changes, and abnormal timeout rates.

6. Common pitfalls

1. Looking only at pass@k: Pass rates without a sampling budget have no decision-making value.
2. Ignoring placeholder goals and axiom dependencies: Passing the checker while relying on strong assumptions or leaving unproven goals is effectively no result.
3. Not locking baseline versions: Changing both the model and the library version invalidates attribution.
4. Skipping failure classification: The four error categories have different optimization paths; mixing them leads only to the ineffective conclusion “try another model.”
5. Executing generated code outside a sandbox: Proof scripts are executable code and must be assumed to potentially infinite-loop, exhaust memory, or attempt external network access.
6. Treating a demonstration as capability: A single demonstration on a research-grade statement cannot be extrapolated to “this class of tasks is generally usable.”

7. Deployment checklist

• Build a tiered task set and a version-locked evaluation baseline, and include periodic regression in continuous integration.
• Define a “valid proof” using a composite criterion: accepted + zero placeholders + axiom allowlist + manual edit lines.
• Use cost per valid proof as the core metric for selection, and match plans by task-value tiers.
• Deploy generate-check-repair loops, compress feedback structurally, and enforce dual caps on rounds and cost.
• Add retrieval augmentation, result caching, asynchronous verification, and full-chain observability.
• Treat untrusted execution, cost alerting, and data-retention policies as mandatory pre-launch checks.

In one sentence: whether progress in formal proof generation is real depends on how strict your evaluation is. Vague metrics make upgrades illusory; clear metrics turn every iteration into a measurable reduction in cost per valid proof.