VERITAS Enhances Zero-Shot Theorem Proving with Verifier Feedback

This paper introduces VERITAS, a novel framework designed to enhance zero-shot formal theorem proving using large language models. Unlike previous methods that often simplify verifier feedback to a binary pass/fail signal, VERITAS incorporates rich verifier signals, such as syntax errors, type mismatches, and partial goal progress, directly into its proof search mechanism. The framework operates through a two-phase protocol. Initially, it employs a Best-of-N sampling approach to generate candidate proofs. Subsequently, a critic-guided Monte Carlo Tree Search (MCTS) pass refines these candidates, explicitly utilizing the failures from the first phase as negative examples to guide exploration. Empirical results demonstrate VERITAS's effectiveness, achieving a 40.6% success rate on the miniF2F benchmark, outperforming unguided sampling methods. The framework also shows strong performance on a new combinatorics benchmark, VERITAS-CombiBench, highlighting its ability to iteratively recover correct lemma names from detailed verifier feedback.