Bourbaki: Self-Generated and Goal-Conditioned MDPs for Theorem Proving

Matthieu Zimmer, Xiaotong Ji, Rasul Tutunov, Anthony Bordg, Jun Wang, Haitham Bou-AmmararXiv 2025 · DOI · arXiv

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.

Performance comparison of Bourbaki against other 7B-scale models on PutnamBench.

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.

Comparison of Bourbaki (7B) with existing tree search and whole-proof generation methods on PutnamBench.

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

Abstract

Reasoning remains a challenging task for large language models (LLMs), especially within the logically constrained environment of automated theorem proving (ATP), due to sparse rewards and the vast scale of proofs. These challenges are amplified in benchmarks like PutnamBench, which contains university-level problems requiring complex, multi-step reasoning. To address this, we introduce self-generated goal-conditioned MDPs (sG-MDPs), a new framework in which agents generate and pursue their subgoals based on the evolving proof state. Given this more structured generation of goals, the resulting problem becomes more amenable to search. We then apply Monte Carlo Tree Search (MCTS)-like algorithms to solve the sG-MDP, instantiating our approach in Bourbaki (7B), a modular system that can ensemble multiple 7B LLMs for subgoal generation and tactic synthesis. On PutnamBench, Bourbaki (7B) solves 26 problems, achieving new state-of-the-art results with models at this scale.
BibTeX
@misc{zimmer2025bourbaki,
  author = {Matthieu Zimmer and Xiaotong Ji and Rasul Tutunov and Anthony Bordg and Jun Wang and Haitham Bou-Ammar},
  title = {{Bourbaki: Self-Generated and Goal-Conditioned MDPs for Theorem Proving}},
  year = {2025},
  eprint = {2507.02726},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.02726},
}
Figure