Scaling Natural-Language Graph-Based Test Time Compute for Automated Theorem Proving

A new framework called KG-prover uses knowledge graphs to help general-purpose large language models construct and formalize mathematical proofs, according to research posted on arXiv. The approach lifts performance on a key benchmark without requiring additional fine-tuning of the underlying models. The framework mines knowledge graphs from reputable mathematical texts and feeds them to LLMs during test-time computation, aiming to address persistent challenges in automated theorem proving such as identifying key concepts and understanding their interrelationships [1][2]. Vincent Li is listed as the corresponding author on the paper, which was first submitted in February 2025 and revised in May 2026 [1]. When combined with KG-prover, general-purpose LLMs improved by up to 21% on the miniF2F-test, a dataset widely used to measure formal mathematical reasoning [1][2]. The researchers also recorded consistent gains of 2–11% across the ProofNet, miniF2F-test, and MUSTARD datasets [1][2]. The strongest reported configuration paired KG-prover with the o4-mini model, achieving a 50% pass rate on miniF2F-test [1][2]. Language model benchmarks such as miniF2F provide standardized datasets and evaluation metrics that allow researchers to compare model capabilities in areas like reasoning and generation [4]. The gains reported for KG-prover suggest that structured external knowledge can complement the natural language processing strengths of LLMs, which already handle tasks including text classification and natural language understanding [5]. The paper also examines the effect of scaling graph-based test-time compute, showing that larger knowledge graph retrievals can further boost performance [1][2]. Unlike approaches that require retraining or fine-tuning, KG-prover operates at inference time, making it compatible with off-the-shelf models [1][2]. The framework does not depend on e-graphs, a separate data structure used in computer science to store equivalence relations over terms, but instead relies on mined relational knowledge from mathematical literature [3]. The authors describe the work as a step toward augmenting natural-language proof reasoning with structured knowledge, noting that the method sidesteps the cost and complexity of additional model training [1][2].