Search papers, labs, and topics across Lattice.
This paper introduces VERITAS, a novel zero-shot framework for formal theorem proving that enhances the utilization of verifier signals through a two-phase protocol. By employing Best-of-N sampling followed by a critic-guided Monte Carlo Tree Search (MCTS), VERITAS effectively incorporates feedback from failed attempts to improve proof search outcomes. The framework achieves a notable 40.6% success rate on the miniF2F benchmark, outperforming traditional methods and highlighting the importance of leveraging negative examples in theorem proving.
VERITAS reveals that incorporating verifier feedback can boost theorem proving success rates by over 10%, challenging the efficacy of traditional binary pass/fail approaches.
LLM-based formal provers often collapse rich verifier signals (syntax errors, type mismatches, partial goal progress) into a binary pass/fail bit. We present VERITAS, a zero-shot framework that routes every verifier signal back into proof search through a two-phase protocol: Best-of-N sampling first, then a critic-guided MCTS pass that ingests Phase 1 failures as explicit negative examples. The protocol preserves every theorem solved by its own Phase 1 sweep, so Phase 2's additional solves are attributable to feedback-driven exploration. VERITAS reaches 40.6% on miniF2F (vs. an independently run Best-of-5 at 36.9%, Portfolio 26.2%) and 7.3% on VERITAS-CombiBench, a 55-theorem combinatorics benchmark we release on which Best-of-5 (1.8%) falls below Portfolio (3.6%), exposing that unguided sampling hurts when correct lemma names must be recovered iteratively from verifier feedback. Artifacts are available on GitHub.
