HunyuanProver : A Scalable Data Synthesis Framework and Guided Tree Search for Automated Theorem Proving

Yang Li, Dong Du*, Linfeng Song*, Chen Li*, Weikang Wang, Tao Yang, Haitao Mi · 2024

Read HunyuanProver : A Scalable Data Synthesis Framework and Guided Tree Search for Automated Theorem Proving by Yang Li, Dong Du*, Linfeng Song*, Chen Li*, Weikang Wang, Tao Yang, Haitao Mi (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-20735.txt.

Description

Abstract We introduce HunyuanProver , an language model finetuned from the Hunyuan 7B for interactive automatic theorem proving with LEAN4. To alleviate the data sparsity issue, we design a scalable framework to iterative synthesize data with low cost. Besides, guided tree search algorithms are designed to enable effective “system 2 thinking“ of the prover.

Catalog record

CREATORYang Li, Dong Du*, Linfeng Song*, Chen Li*, Weikang Wang, Tao Yang, Haitao Mi
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-20735

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

HunyuanProver : A Scalable Data Synthesis Framework and Guided Tree Search for Automated Theorem Proving Yang Li, Dong Du*, Linfeng Song*, Chen Li*, Weikang Wang, Tao Yang, Haitao Mi Abstract We introduce HunyuanProver , an language model finetuned from the Hunyuan 7B for interactive automatic theorem proving with LEAN4. To alleviate the data sparsity issue, we design a scalable framework to iterative synthesize data with low cost. Besides, guided tree search algorithms are designed to enable effective “system 2 thinking“ of the prover. HunyuanProver achieves state-of-the-art (SOTA) performances on major benchmarks. Specifically, it achieves a pass of 68.4% on the miniF2F-test compared to 65.9%, the current SOTA results. It proves 4 IMO statements ( imo_1960_p2 , imo_1962_p2 , imo_1964_p2 and imo_1983_p6 ) in miniF2F-test. 1 Introduction Recent advancements in large language models (LLMs) have profoundly impacted mathematical reasoning and theorem proving in artificial intelligence. Despite notable progress in natural language domains, language models still encounter substantial challenges in formal theorem proving (e.g., using LEAN ( Moura & Ullrich 2021 ) or Isabelle ( PAULSON 1994 ) ) probably due to the massive search space of Olympiad-level theorem proving and limited data in such scenario. As the results, even the most advanced models like GPT-4o Hurst et al. 2024 struggle with complex formal-statement proving ( Xin et al. 2024a ) . A formal theorem-proving model should be capable of understanding both the syntax and semantics of a formal system, enabling it to generate valid next steps within the system. More critically, it must integrate this capability with its abstract mathematical reasoning skills to perform effective and efficient deductions. We propose HunyuanProver , an LLM-based automatic theorem prover obtained by a pragmatic framework for addressing the aforementioned challenges. The framework takes two core modules: a scalable prover-data generator and guided tree-search algorithms. The prover-data generator only takes open-source data for theorem proving to train the initial autoformalizer and prover. The autoformalizer then converts a large amount of existing math questions into the format of the target prover (e.g., LEAN4). The prover is lastly iteratively improved on such data where new proof data is generated at each iteration to train the prover. At testing time, tree-search algorithms and multiple critic models are designed to perform “slow thinking” that is empirically essential for solving complex theorem-proving tasks. Evaluations show that HunyuanProver yields an accuracy of 68.4% on the miniF2F benchmark. In addition, we also observe several key findings: 1) using explicitly trained critic for tree-search guidance is helpful; 2) the scale of finetuning data for theorem proving is critical, thus designing efficient data scaling framework is important; 3) data curation and selection is important as well when there is sufficient amount of training data. Our key contributions includes: • We introduce a scalable pipeline that utilizes open-source data for theorem proving and massive math problems in natural language to generate a large number of new training data for automatic theorem proving. • We develop several critic models and evaluate their effectiveness using two widely adopted search algorithms: best-first search and Monte Carlo tree search. 2 Scalable Data Generation for Prover Improving One major bottleneck for automated theorem proving is the lack of training data. For example, as one of the largest open-source LEAN4 datasets, mathlib4 ( Moura & Ullrich 2021 ) only contains around 50k theorems(with tactics) for training. This is far from sufficient to train a stronger prover given the difficulty of automatic theorem proving. On the other hand, massive high-quality math problems in natural language have been released in recent years ( Yu et al. 2024 ; Luo et al. 2023 ) . Our efforts fall into two critical aspects to scale the training data for automatic theorem proving: autoformalization (Section 2.1 ) that maps a natural language problem (Section 2.2 ) into LEAN format statement, and tactic generation for iterative theorem proving. 2.1 Autoformalization Data Generation For autoformalization, we start with 130k high-quality natural language to LEAN statement pairs, which includes 50k from lean workbook ( Ying et al. 2024 ) and 80k from MMA ( Jiang et al. 2024 ) . We first translate the natural language part of the 130k data into Chinese to double the dataset size, and with such data we train a autoformalization model, it can translate both English and Chinese problems to lean4 format statement. In the next step, 30 million internal math problems in natural language are converted into formal statement by the autoformalization model. For each natural language problem, we sample 8 outputs with different temperatures.We obtain a dataset D^{q} of 20 million LEAN statements after filtering out these do not conform with LEAN grammar or do not satisfy other rules adopted by previous practices ( Ying et al. 2024 ) . In addition to using internal data, we also utilized open-source natural language mathematical data NuminaMath CoT ( LI et al. 2024 ) . 2.2 Prover Improving via Iterative Tactic-Level Proving Data Generation We design a iterative framework that takes a LEAN engine \mathbf{\Gamma} and statement dataset D^{q} from autoformalization to generate new tactic data for prover improving. Specifically, in iteration t , we leverage best-first search (Section 3.1 ) algorithm with the prover from the previous iteration \pi_{t-1} on all unsolved statements so far in D . We collect the proving trajectories (e.g., \tau ) for newly solved statements (e.g., q ) if there is any: D_{t}=\{(q,\tau)~|~q\in D^{q}-D_{t-1},\tau\sim\textsc{Bfs}(q),\tau\neq null\}\cup D_{t-1} (1) Then the prover is updated using rejection finetuning (RFT) with the proving trajectories in D_{t} after filtering out easy statements solved in early iterations. The initial prover \pi_{0} is trained on public data including mathlib4. After more than 10 rounds of iteration, more than 20 million tactic-level data is obtained. Enhancing Diversity As indicated by previous work ( Xin et al. 2024c ) , prover diversity is important due to the massive search space of theorem proving. We further develop two methods to enhance the prover diversity within the iterative data-generation framework. For the first method, we design rules to convert the last state of an unfinished proving trajectory into a new statement. In this way, more diverse proving data is obtained for prover training. For the second method, we collect data from proving more challenging statements, including those Olympiad-level algebraic inequalities Wei et al. 2024 and lean workbook Ying et al. 2024 . Figure 1: Comparing best-first search (BFS) with Monte-Carlo tree search (MCTS). BFS only takes Selection and Expansion in one iteration, while MCTS takes all four steps. The numbers represent critic-assigned scores. 3 Guided Tree Search As described in Section 2 , our task involves iterative interaction with LEAN as the environment, where for each iteration the policy predicts a new tactic given from a state in the proving process. We abstract this process as tree search where a state s_{i} in the proving process corresponds to a tree node n_{i} with the input statement q being the root n_{0} . An edge that points from n_{i} to n_{j} represents applying a tactic on node (state) n_{i} to yield node (state) n_{j} . To handle this problem, we design two major tree search algorithms as described in Section 3.1 . We also design several critics, as shown

Read the complete text