Abstract
Automated Theorem Proving (ATP) in formal environments like Lean 4 is hindered by the sparse reward problem, where agents receive feedback only upon completing a full proof. We introduce Bourbaki, a novel framework utilizing self-generated goal-conditioned Markov Decision Processes (sG-MDPs). In this framework, AI agents dynamically propose and solve their own mathematical subgoals to navigate complex search spaces. By ensembling 7B-parameter models within a Monte Carlo Tree Search (MCTS) structure, Bourbaki achieves a new state-of-the-art on the university-level PutnamBench benchmark, solving 26 out of 658 problems—more than doubling the performance of previous models at this scale.
The Challenge of Sparse Rewards in ATP
Automated Theorem Proving is notoriously difficult because of the sparse reward problem. In a formal environment like Lean 4, an agent might generate dozens of logical steps, but it receives no feedback until the entire proof is complete. If a proof requires 50 precise steps, the search space is astronomically large, and the probability of finding a valid solution through random or unguided search is near zero.
While Large Language Models (LLMs) have shown talent in informal mathematics, they struggle with the rigorous, multi-step reasoning required for university-level competition math, such as the Putnam Competition. Existing benchmarks like MiniF2F (high school level) are nearing saturation, but the newer PutnamBench remains a significant barrier. Bourbaki aims to bridge this gap by enabling models to decompose difficult problems into manageable, verifiable milestones.
Methodology: sG-MDPs and MCTS
The core contribution of this work is the sG-MDP (self-generated goal-conditioned Markov Decision Process) framework, which incorporates several key innovations:
- Dynamic Subgoaling: Unlike standard goal-conditioned reinforcement learning where goals are predefined, sG-MDP agents use an LLM to propose their own intermediate conjectures (subgoals) based on the current proof state.
- Modular Ensemble System: Bourbaki (7B) combines two strong 7B-scale models—DeepSeek-Prover-v2 and Kimina-7B—to act as the policy that suggests both proof tactics and new subgoals.
- MCTS without a Neural Critic: Most search-based provers rely on a pre-trained "critic" model to estimate state values. Bourbaki instead utilizes the formal verification of the subgoals themselves. Successfully proving a proposed subgoal in Lean provides a "dense" reward signal that guides the search deeper into promising branches.
- Pantograph Interface: The system employs Pantograph, a specialized tool for interacting with the Lean 4 proof assistant, allowing for efficient tracking of dependencies and goal state management.
Key Results and Performance
Bourbaki (7B) sets a new benchmark for 7B-scale models on PutnamBench, solving 26 out of 658 problems. This represents a significant leap over previous state-of-the-art models; for instance, Kimina-7B solved 10 problems, while DeepSeek-Prover-v2 (7B) solved between 11 and 15 depending on the configuration.
Beyond raw scores, the framework demonstrates high sample efficiency, outperforming models that utilize twice the sample budget. The sG-MDP approach also produces more varied and diverse proof strategies compared to "whole-proof generation" methods, which often suffer from repetitive patterns.
Insights and Future Directions
Bourbaki demonstrates that subgoals can serve as effective "internal feedback," mimicking the way human mathematicians break down complex theorems. By relying on Lean's compiler for verification rather than a fallible neural critic, the system maintains high logical soundness and avoids common LLM hallucination issues.
However, challenges remain. Some Lean tactics return sets of suggestions rather than single state changes, which the current system handles via fallbacks. Furthermore, while 26 solved problems is a record for this scale, it represents only ~4% of the total benchmark, highlighting the extreme difficulty of Putnam-level math. Future work will focus on training models specifically to be better "conjecturers" through reinforcement learning and integrating more sophisticated value-function formulations.
Summary updated