Abstract
Modern theorem provers such as Vampire utilise premise selection algorithms to control the proof search explosion. Premise selection heuristics often employ an array of continuous and discrete parameters. The quality of recommended premises varies depending on the parameter assignment. In this work, we introduce a principled probabilistic framework for optimisation of a premise selection algorithm. We present results using Sumo Inference Engine (SInE) and the Archive of Formal Proofs (AFP) as a case study. Our approach can be used to optimise heuristics on large theories in minimum number of steps.
Introduction
In the field of Automated Theorem Proving (ATP), the primary challenge is managing the "search explosion." When a high-performance prover like Vampire attempts to verify a conjecture, it must navigate a vast library of existing axioms and lemmas, known as premises. Including every available premise in the search space often leads to infinite growth, causing the prover to stall.
To mitigate this, provers employ premise selection algorithms such as the Sumo Inference Engine (SInE). SInE filters the library to identify the most relevant premises. However, its effectiveness is highly sensitive to several parameters, including the "tolerance threshold" and "depth." Traditionally, finding the optimal configuration for a specific mathematical theory has been a manual, time-consuming process—often described as a "black art." This research proposes a machine learning-based approach to automate this configuration using Bayesian Optimization.
Methodology: Bayesian Optimization for Heuristics
The authors frame heuristic tuning as a black-box optimization problem. Rather than exhaustive grid searches or random guessing, they apply Bayesian Optimisation (BO). This method builds a probabilistic surrogate model—specifically a Gaussian Process (GP)—to map the relationship between parameter configurations and prover performance.
Probabilistic Modeling
The optimization process uses the Upper Confidence Bound (UCB) acquisition function. UCB allows the system to intelligently balance "exploitation" (refining known high-performing areas) with "exploration" (investigating uncertain regions of the parameter space). To handle the mix of continuous and discrete parameters, the authors utilized continuous surrogates for integer-valued variables, rounding them during the evaluation phase. The Matérn kernel was selected for the GP to define the covariance between different parameter sets, providing the necessary flexibility to model the performance landscape.
Objective Function Design
A critical innovation in this work is the design of the objective function. A simple binary metric (proof found vs. not found) is too sparse for effective optimization. Instead, the authors developed a granular metric based on precision and recall of the selected premises. This rewards the algorithm for capturing all necessary premises while penalizing the inclusion of irrelevant ones, creating a "smoother" landscape that the Gaussian Process can navigate more efficiently.
Experimental Evaluation
The framework was evaluated using the Archive of Formal Proofs (AFP), a comprehensive collection of formalized mathematics in the Isabelle theorem prover. The study focused on 10 diverse theories, such as "Polynomials," "MiniML," and "RefineMonadic," with conjecture counts ranging from 100 to over 1500. Ground truth for the required premises was extracted from logs of Sledgehammer, the tool connecting Isabelle to external ATPs.
Key Results and Discussion
The experimental results demonstrate that the Bayesian Optimization framework is both efficient and highly effective. On average, the system identified the global optimum for a given theory in just 4.3 minutes.
As shown in the results table above, the success rates were remarkably high. In the "RefineMonadic" theory, the optimized configuration enabled the prover to find 95% of the proofs. Across all tested theories, the success rate consistently exceeded 80%, demonstrating that the automated approach can match or exceed the performance of expert manual tuning.
The data also confirms that there is no universal "one size fits all" configuration. Different mathematical domains require distinct parameter settings for depth ($k$) and thresholds ($t, g$). The BO framework successfully adapted to these theory-specific requirements, proving its utility as a general-purpose tool for prover configuration.
Conclusion and Future Work
This work demonstrates that Bayesian Optimization can transform the "black art" of heuristic tuning into a principled, automated engineering process. By leveraging probabilistic modeling, researchers can find optimal configurations for complex ATP heuristics in minutes rather than hours.
Future research directions include more sophisticated handling of discrete parameters within the Gaussian Process and benchmarking the approach against other optimization frameworks like SMAC. Additionally, the authors suggest extending this framework to other internal prover heuristics, such as literal ordering or clause selection strategies, to further enhance the power of automated reasoning tools.
Summary updated