Skip to content

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

Aug 2026 · 0 citations · 29 references
Computer Science

TL;DR

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 is proposed.

Abstract

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.

View source

Similar papers

#artificial intelligence Preprint Sep 2026

Direct Optimization of Generators for Search in Automated Theorem Proving

This work extends Compute-Aligned Training to this setting through an abstraction of policy-guided search, deriving tractable, trace-supported losses and introduces a search-agnostic uniform-allocation (UA) loss that accounts for the budget without specifying the specific search.

Adam Ousherovitch, A. Tewari · 0 citations
Preprint Aug 2026

Constraint-First Reasoning: A Training-Free Protocol for Exploiting Answer-Space Constraints in Mathematical Problem Solving

This work introduces Constraint-First Reasoning (CFR), a training-free two-stage prompting protocol that improves direct CoT on multiple backbones and positions CFR as a targeted test-time intervention whose benefit depends on recoverable constraints and reliable Stage 1 extraction.

Hongbo Ma, Bang Yang, Y. Cheng et al. · 0 citations
Preprint Sep 2026

ProofGap: Benchmarking Step-Level Formal Reasoning with Local Obligations Derived from Natural-Language Solutions

ProofGap is a fine-grained benchmark for step-level formal reasoning constructed through a natural-language proof-processing pipeline that decomposes each reasoning step into one or more aligned proof gaps, enabling more precise localization of model failures.

Li-Han Xie, Zhi-Cheng Hui, Ying-Jun Lan et al. · 0 citations
Preprint Aug 2026

From Errors to Proofs: Minimal-Core-Guided Repair for Neuro-Symbolic Constraint Solving

On a new benchmark of 77 problems with an exact oracle, translation to Answer Set Programming is faithful on six of seven domains and fails only on aggregate coverage scheduling, which concentrates the translation tax in one diagnosable pattern.

Dipankar Sarkar · 0 citations
Preprint Aug 2026

Self-Correcting Long-Horizon Search Agents via Tree-Structured Memory

Experiments establish ReTree as an effective self-correcting memory abstraction for long-horizon search, and show that ReTree consistently outperforms Full-Trajectory ReAct in question-answering and search benchmarks.

Aijun Yang, Qianxue Guo, Ziyi Huang et al. · 0 citations

Related blog posts

MIT News · Artificial Intelligence Sep 29, 2026

Who we become when we talk to machines

Professor Sherry Turkle’s new book, “Artificial Intimacy,” offers a withering critique of chatbots and the antisocial dynamics she believes they encourage.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.