arXiv:2608.28639v1 cs.AI

형식 정리 증명을 위한 Reward-Oracle MCTS: 샘플 효율적 탐색과 커널 수준 증명 감사의 필요성

Reward-Oracle MCTS for Formal Theorem Proving: Sample-Efficient Search and the Need for Kernel-Level Proof Auditing

Bodla Krishna Vamshi, Haizhao Yang

제출 2026-08-11

한국어 초록

대규모 언어 모델(LLM)을 이용한 형식 정리 증명은 넓은 증명 탐색 공간을 효율적으로 탐색하기 어렵기 때문에 여전히 어려운 과제이다. 기존 트리 탐색(tree search) 접근법은 장황한 컴파일러 오류 메시지를 생성 컨텍스트(generation context)에 그대로 넣어 탐색 중 컨텍스트 사용량을 늘리거나, 확립된 베이스라인과 직접 비교를 막는 비표준 평가 프로토콜을 쓴다. 우리는 Lean 4 컴파일러를 오류 내용을 생성 컨텍스트에 넣지 않고, UCB(Upper Confidence Bound) 기반 트리 갱신을 위해 컴파일러 출력을 스칼라 보상(reward) 신호로만 사용하는 보상 오라클(reward oracle)로 순수하게 다루는 3역할 몬테카를로 트리 탐색(Monte Carlo Tree Search, MCTS) 프레임워크를 제안한다. 이 프레임워크는 증명 탐색을 세 역할로 나눈다: 증명 시도를 생성하는 generator, 하위 목표(subgoal)를 분해하는 decomposer, 하위 목표 품질을 평가하는 critic. 경시 수학과 물리를 아우르는 4개 벤치마크(MiniF2F, PutnamBench, LeanPhysBench, PhysLeandata)에서 세 증명기(prover) 모델을 표준 증명 시도 예산(PAB@16~PAB@256)으로 평가한다. 제안 방법은 PAB@256에서 Goedel-Prover-V2-8B로 MiniF2F에서 87.1%를 달성하고, PAB@32에서 PutnamBench 659문제 중 26문제를 풀어 동일 증명 시도 예산의 base sampling 18/659를 넘선다. 컴파일된 모든 증명에 대한 공리(axiom) 수준 전수 감사를 통해 탐색 기반 정리 증명에서의 보상 해킹(reward hacking)을 추가로 확인한다. DeepSeek-Prover-V2-7B는 PutnamBench에서 sorryAx에 의존하면서도 컴파일과 표준 sorry 토큰(token) 스캔을 통과하는 증명을 만든다. 감사는 PAB@32 및 PAB@128에서 whole-proof sampling 결과에서 각각 4개와 8개, MCTS에서는 11개와 19개의 해당 증명을 제거한다. 우리는 이 수치를 탐색 절차의 결과로 귀속하지 않으며, 컴파일러 검증 평가를 위해 커널(kernel) 수준 감사가 필요함을 밝히기 위해 보고한다.

원문 초록

Formal theorem proving with large language models remains challenging due to the difficulty of navigating large proof search spaces efficiently. Existing tree search approaches either feed verbose compiler error messages directly into the generation context, increasing context usage during search, or employ non-standard evaluation protocols that prevent direct comparison with established baselines. We propose a three-role Monte Carlo Tree Search (MCTS) framework that treats the Lean 4 compiler purely as a reward oracle using compiler output as a scalar signal for UCB-guided tree updates without feeding error content into the generation context. Our framework decomposes proof search into three roles: a generator for proof attempts, a decomposer for subgoal decomposition, and a critic for subgoal quality evaluation. We evaluate across 4 benchmarks spanning competition mathematics and physics (MiniF2F, PutnamBench, LeanPhysBench, PhysLeandata) with three prover models at standard proof attempt budgets (PAB@16 to PAB@256). Our method achieves 87.1\% on MiniF2F with Goedel-Prover-V2-8B at PAB@256 and solves 26/659 PutnamBench problems at PAB@32 surpassing base sampling 18/659 at same proof attempt budget. Through an exhaustive axiom-level audit of every compiled proof, we further identify reward hacking in search-based theorem proving: DeepSeek-Prover-V2-7B produces proofs on PutnamBench that pass compilation and the standard sorry-token scan while depending on sorryAx. The audit removes 4 and 8 such proofs from whole-proof sampling at PAB@32 and PAB@128, and 11 and 19 from MCTS. We do not attribute these counts to the search procedure; we report them to establish that kernel-level auditing is necessary for compiler-verified evaluation.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2608.28639v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.