💻 computer science

Pseudo-Formalization for Automatic Proof Verification

This paper introduces Pseudo-Formalization, a hybrid proof format combining natural language flexibility with formal modularity, and a corresponding Block Verification algorithm that significantly outperforms existing LLM-as-judge baselines in accurately verifying mathematical proofs across olympiad and research-level benchmarks.

Original authors: Slim Barkallah, Luke Bailey, Kaiyue Wen, Mohammed Abouzaid, Tengyu Ma

Published 2026-05-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Slim Barkallah, Luke Bailey, Kaiyue Wen, Mohammed Abouzaid, Tengyu Ma

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a senior editor at a prestigious math journal. You receive a 50-page proof written by a brilliant but slightly chaotic mathematician (or an AI). The proof is written in natural language, full of "it follows that," "clearly," and "as we know." Your job is to find the one tiny logical error that ruins the whole thing.

Doing this is like trying to find a single typo in a novel while reading it at 100 miles per hour. If you miss the error, you publish nonsense. If you read too slowly, you never finish.

This paper, "Pseudo-Formalization for Automatic Proof Verification," proposes a new way to solve this problem. It suggests a middle ground between the messy, flexible way humans write math and the rigid, robotic way computers check math.

Here is the breakdown of their solution using simple analogies:

1. The Problem: The "Wall of Text"

Currently, when we ask an AI to check a math proof, we usually just feed the whole thing to the AI and say, "Is this right?"

The Issue: This is like asking a human to read a 100-page legal contract and find a single contradiction in one breath. The AI gets confused, forgets the beginning by the time it reaches the end, and misses the errors. This is called "context rot"—the more text you feed it, the dumber it gets at finding mistakes.

2. The Solution: "Pseudo-Formalization" (The LEGO Analogy)

The authors introduce a new format called Pseudo-Formal (PF).

The Analogy: Imagine the messy proof is a giant, tangled ball of yarn. Pseudo-Formalization is the process of cutting that yarn and re-knitting it into neat, individual LEGO bricks.
How it works: Instead of one long paragraph, the proof is broken down into small, self-contained "blocks" (like Lemmas, Propositions, and Theorems).
The Rules: Each block must clearly state:
1. Premises: What assumptions are we starting with?
2. Conclusion: What are we trying to prove in this specific block?
3. Proof: The steps to get from 1 to 2.
The Benefit: Now, instead of checking the whole ball of yarn, the AI only has to check one LEGO brick at a time. It's a tiny, manageable task.

3. The Process: The "Factory Assembly Line"

The paper describes a four-step assembly line to verify a proof:

Translation (The Architect): An AI takes the messy, natural-language proof and rewrites it into these neat LEGO blocks (Pseudo-Formal format). It's like a translator who takes a rambling speech and turns it into a structured outline.
Block Verification (The Quality Inspectors): Now, the AI acts like a team of quality inspectors. Each inspector looks at one LEGO brick. They check: "Does the proof inside this brick actually prove the conclusion, given the premises?" They don't worry about the rest of the building; they just check their specific brick.
Calibration (The Manager): Sometimes an inspector might get too picky (flagging a typo) or miss something. A "Manager" AI looks at all the inspectors' reports and decides: "Okay, we have a real error here, or was that just a false alarm?" It aggregates the findings into a final verdict.
Parallel Scaling (The Crowd): To be extra sure, they run this whole process 8 times (like 8 different teams of inspectors). If any team finds an error, the proof is rejected. This ensures they catch almost everything.

4. The Results: Better than the Baseline

The authors tested this method on two types of math:

Olympiad Math: Hard competition problems (like the International Math Olympiad).
Research Math: Real, published academic papers from arXiv that the authors themselves admitted had errors in them.

The Findings:

The "Pseudo-Formal" method was better at finding errors than the standard method of just asking an AI to read the whole proof.
It found more errors (higher Recall) without making up fake errors (higher Precision).
In the world of math verification, this is a "Pareto improvement"—meaning they got better results without having to sacrifice one quality for another.

5. The New Benchmark: "ArxivMathGradingBench"

To prove their method works on real-world research, the authors built a new test dataset.

They took 35 real math papers that had been updated by their authors to fix mistakes.
They used these "known errors" to test if their AI could find the specific mistakes the authors had fixed.
This is like a "driving test" where the examiners know exactly where the potholes are, and they see if the new car (the AI) can hit them.

Summary

The paper argues that we don't need to force AI to speak "robot language" (like Lean or Isabelle) to check math. Instead, we can teach the AI to organize human math into neat, small chunks. By breaking a giant, confusing proof into small, clear LEGO blocks, the AI can check each piece with laser focus, finding errors that it would have missed if it tried to read the whole thing at once.

What they did NOT claim:

They did not claim this replaces human mathematicians.
They did not claim this works for non-mathematical fields (though they speculate it might).
They did not claim the AI is perfect; they just showed it is better at finding errors than previous methods.

Technical Summary: Pseudo-Formalization for Automatic Proof Verification

Problem Statement

Reliable automatic verification of mathematical proofs remains a critical bottleneck for training and evaluating AI systems on complex mathematical reasoning. While fully formal proofs (e.g., in Lean or Isabelle) are easy to verify due to their semantic precision and modularity, most proofs—particularly those generated by AI or written by humans in natural language—lack these properties. Translating natural language proofs into fully formal languages is often infeasible for frontier mathematics due to incomplete formal libraries and the immense expert effort required. Consequently, current verification methods, such as "LLM-as-judge" (direct evaluation of natural language proofs), struggle with precision and recall, often failing to identify specific errors in long, complex arguments.

Methodology: Pseudo-Formalization and Block Verification

The authors propose Pseudo-Formalization (PF) combined with Block Verification (BV) as a framework to bridge the gap between the flexibility of natural language and the verifiability of formal proofs.

1. Pseudo-Formal Proof Format

A Pseudo-Formal proof decomposes a natural language argument into a sequence of self-contained modules (lemmas, propositions, claims). Each module is a tuple $(P, c, \pi)$ representing:

Premises ( $P$ ): Explicitly stated assumptions and inherited context.
Conclusion ( $c$ ): The specific claim being proved.
Proof ( $\pi$ ): The natural language argument establishing $c$ from $P$ .

The structure is governed by two graphs:

Dependency Graph ( $G$ ): A Directed Acyclic Graph (DAG) where an edge exists if a module invokes the conclusion of another. This prevents circular reasoning.
Scope-Inheritance Forest ( $T$ ): A forest structure organizing modules hierarchically (e.g., lemmas within a proposition), allowing context (definitions, assumptions) to be inherited without restatement.

The authors define "Good Pseudo-Formal Proofs" as those adhering to two desiderata: conciseness (short proofs invoking few other nodes) and bounded scope depth (shallow inheritance trees). Theoretically, verifying such proofs allows the context length required for each verification step to remain independent of the total proof size, mitigating "context rot" (the degradation of LLM performance with increasing input length).

2. The Verification Pipeline (PF+BV)

The verification process involves four steps, all utilizing off-the-shelf LLMs without fine-tuning:

Translation: An LLM translates the original natural language proof $\Pi$ into a Pseudo-Formal proof $\hat{\Pi}$ . An optional self-repair loop checks $\hat{\Pi}$ against $\Pi$ to ensure faithfulness.
Block Verification: A verifier LLM checks each module of $\hat{\Pi}$ independently. It receives the module's full premises (including inherited context), conclusion, proof, and the verified conclusions of any invoked child modules. It outputs an accept verdict or a specific error description.
Calibration: A calibrator LLM aggregates per-module error reports into a final verdict. It can apply configurable strictness thresholds and map block-level errors back to the original proof's structure (e.g., identifying specific steps or lemmas).
Parallel Scaling: The entire pipeline is run $k$ times independently. A proof is accepted only if all $k$ runs accept it (pessimistic aggregation). This allows trading off precision and recall by varying $k$ .

Key Contributions

Pseudo-Formalization (PF): A new proof format that retains natural language flexibility while enforcing the modularity and explicit premise-conclusion structure necessary for reliable verification.
Block Verification (BV): An algorithm that verifies proofs by decomposing them into independent blocks, theoretically reducing context requirements and empirically improving error detection.
ArxivMathGradingBench: A new benchmark comprising 35 research-level mathematics papers from arXiv that contain known, author-corrected errors. This dataset fills a gap in existing benchmarks by testing verification on real-world research proofs rather than competition-level problems.
Theoretical Justification: The authors provide a theorem (Theorem 1) demonstrating that for "Good" Pseudo-Formal proofs, block-wise verification can be simulated by a fixed-size Transformer with context length independent of the proof size, contrasting with the linear context growth required for whole-proof verification.

Experimental Results

The method was evaluated on two benchmarks: Hard2Verify (Olympiad/Putnam level problems) and ArxivMathGradingBench (Research-level papers).

Performance vs. Baselines: Across both benchmarks, PF+BV Pareto-dominates the "LLM-as-judge" baseline. This means that for any given level of recall (ability to find errors), PF+BV achieves higher precision (fewer false alarms), and vice versa.
Hard2Verify: PF+BV matched the baseline in recall (~90%) but significantly reduced the number of false errors flagged per proof (over 40% fewer false positives at $k=8$ ).
ArxivMathGradingBench: The benchmark proved challenging, with both methods leaving ~50% of annotated errors uncaught at $k=8$ . However, PF+BV consistently outperformed the baseline in recall, false alarm rates, and the fraction of papers where all annotated errors were caught.
Qualitative Analysis: Case studies (e.g., IMO 2024 P6) illustrate that PF+BV succeeds by isolating logical jumps into local blocks. This allows the verifier to detect when a proof incorrectly strengthens a premise (e.g., inferring "same sign" from "no $d$ and $-d$ ") without needing to re-evaluate the entire global argument.

Significance and Claims

The paper claims that Pseudo-Formalization offers a practical alternative to autoformalization (translation to Lean/Isabelle) for verifying modern mathematical research. While autoformalization provides stronger correctness guarantees, it is often intractable for current research due to library incompleteness. PF+BV sacrifices the absolute certainty of formal verification in exchange for applicability to a broader range of mathematical domains, leveraging the rich vocabulary and standard techniques of natural language while imposing a structure that makes errors easier to localize.

The authors position this work as a step toward scalable oversight of AI reasoning, providing a mechanism to generate trustworthy reward signals for training LLMs on hard math and assisting human mathematicians in reviewing proofs. They acknowledge limitations, noting that producing a faithful Pseudo-Formal rewrite is non-trivial and that future work could involve training models to generate proofs directly in this format.