VERITAS: 제로샷 형식 정리 증명 (Zero-Shot Formal Theorem Proving)을 위한 검증기 가이드 증명 탐색

LLM 기반의 형식 증명기 (formal provers)는 풍부한 검증기 신호(verifier signals)(구문 오류, 타입 불일치, 부분적인 목표 진행 상황 등)를 단순히 통과/실패(pass/fail)의 이진 비트로 축소하여 처리하는 경우가 많습니다. 우리는 모든 검증기 신호를 2단계 프로토콜을 통해 증명 탐색 (proof search)으로 다시 전달하는 제로샷 (zero-shot) 프레임워크인 VERITAS를 제시합니다. 이 프로토콜은 먼저 Best-of-N 샘플링을 수행한 후, 1단계의 실패 사례를 명시적인 부정적 예시 (negative examples)로 흡수하는 비평가 가이드 MCTS (critic-guided MCTS) 단계를 거칩니다. 이 프로토콜은 자체적인 1단계 스윕 (sweep)을 통해 해결된 모든 정리를 보존하므로, 2단계에서 추가로 해결된 정리들은 피드백 기반 탐색 (feedback-driven exploration)의 결과로 간주할 수 있습니다. VERITAS는 miniF2F에서 40.6%를 달성하였으며 (독립적으로 실행된 Best-of-5의 36.9%, Portfolio의 26.2% 대비), 우리가 공개하는 55개 정리 규모의 조합론 벤치마크인 VERITAS-CombiBench에서 7.3%를 달성했습니다. 해당 벤치마크에서 Best-of-5 (1.8%)는 Portfolio (3.6%)보다 낮은 성능을 보였는데, 이는 검증기 피드백으로부터 올바른 보조정리 (lemma) 이름을 반복적으로 복구해야 할 때 가이드 없는 샘플링이 성능을 저해한다는 점을 드러냅니다. 관련 결과물은 GitHub에서 확인할 수 있습니다.