VERITAS: Verifier-Guided Proof Search for Zero-Shot Formal Theorem Proving

2026-06-17 · Source: Machine Learning · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Automated Reasoning & Formal Methods · Depth: Expert, quick

Summary

VERITAS is a zero-shot framework designed to enhance LLM-based formal theorem proving by integrating comprehensive verifier signals into the proof search process. Unlike traditional methods that simplify verifier feedback to a binary pass/fail, VERITAS routes all signals back through a two-phase protocol. The first phase involves Best-of-N sampling, followed by a second phase featuring a critic-guided Monte Carlo Tree Search (MCTS) that explicitly incorporates failures from Phase 1 as negative examples. This approach significantly improves performance, achieving 40.6% on miniF2F, surpassing an independently run Best-of-5 at 36.9% and Portfolio at 26.2%. On the newly released VERITAS-CombiBench, a 55-theorem combinatorics benchmark, VERITAS scores 7.3%, outperforming Best-of-5 (1.8%) and Portfolio (3.6%), demonstrating its effectiveness in scenarios requiring iterative lemma name recovery. Artifacts are available on GitHub.

Key takeaway

For AI Scientists and Machine Learning Engineers developing formal theorem provers, VERITAS demonstrates that fully utilizing verifier signals significantly boosts performance. If you are struggling with LLM-based provers that collapse feedback, consider implementing a multi-phase search protocol that explicitly incorporates failed attempts as negative examples. This approach can improve proof success rates, especially for complex problems requiring iterative lemma discovery, as shown by its 40.6% on miniF2F.

Key insights

VERITAS improves LLM theorem proving by integrating all verifier signals into a two-phase, feedback-driven search.

Principles

• Integrate all verifier signals.
• Use failed attempts as negative examples.
• Guided search outperforms unguided sampling.

Method

VERITAS employs Best-of-N sampling, then a critic-guided MCTS pass. This MCTS phase ingests Phase 1 failures as explicit negative examples to refine proof search.

In practice

• Apply two-phase search to LLM tasks.
• Use verifier feedback for iterative refinement.
• Explore MCTS with negative examples.

Topics

• Formal Theorem Proving
• LLM-based Provers
• Verifier-Guided Search
• Monte Carlo Tree Search
• miniF2F Benchmark
• VERITAS-CombiBench

Best for: AI Scientist, Machine Learning Engineer, Research Scientist

Related on AIssential

• VecCISC: Improving Confidence-Informed Self-Consistency with Reasoning Trace Clustering and Candidate Answer Selection — VecCISC improves LLM self-consistency by semantically filtering reasoning traces, reducing critic calls and token usage.
• Escaping the Verifier: Learning to Reason via Demonstrations — RARO enables LLMs to learn robust reasoning from expert demonstrations alone, even without task-specific verifiers or human preferences.
• Evaluation of LLMs for Mathematical Formalization in Lean — Iterative refinement significantly boosts LLM performance in formal mathematical proof generation.
• LEAP: Supercharging LLMs for Formal Mathematics with Agentic Frameworks — Agentic frameworks like LEAP enable LLMs to achieve state-of-the-art formal theorem proving by bridging informal reasoning with verifiable proofs.
• Doubly Saturated Ramsey Graphs: A Case Study in Computer-Assisted Mathematical Discovery — Integrating SAT solving, LLMs, and formal verification accelerates mathematical discovery of complex graph structures.
• TLA-Prover: Verifiable TLA+ Specification Synthesis via Preference-Optimized Low-Rank Adaptation — Verifier-guided LLM training for formal specifications necessitates mutation-sensitive validation to prevent reward hacking.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Machine Learning.