Adaptive search finds better mathematical proofs with less cost
LEVER: Adaptive Cost-Aware Proof Search Over AND/OR Graphs
Artificial Intelligence
Summary
Finding mathematical proofs is not just about being correct; simpler and more focused proofs are often preferred. The authors introduce LEVER, a new strategy that actively searches for proofs optimized by various qualities like length or topic relevance, rather than just correctness. LEVER predicts the value of incomplete proofs and guides the search accordingly, making it cost-efficient and tunable to different goals. Tests show it solves more problems faster and produces cleaner proofs compared to earlier methods.
What this means in practice
- •For software verification teams: Automatically find and optimize program correctness proofs to improve verification efficiency and proof quality.
- •For automated reasoning developers: Enhance theorem proving software by integrating adaptive search to balance proof cost, length, and topic focus during proof generation.
Authors
Nihal Jain, Shuangjie Yao, Begum Cicekdag, Zhuo Zhang, Suman Jana
Abstract
Mathematicians value proofs for more than correctness: among correct proofs, simplicity, purity and the computational cost of finding them vary widely. Yet LLM-powered theorem provers largely search for any correct proof, and improve its quality only after it is found. We propose LEVER, a proof search algorithm that makes the objective over correct proofs programmable and optimizes it during search. LEVER scores partial proofs over an AND/OR proof graph, combining realized objective values with predictions for open subgoals, so the objective guides search before a proof is complete. The same mechanism optimizes computational cost, proof length, topical impurity, and even their weighted combinations, while the Lean kernel enforces correctness. On PutnamBench in Lean 4, under matched budgets, LEVER costs 34% less than a strong single-conversation agent while raising the solve rate from 80% to 96%. On reducing topical impurity, i.e., how far a proof strays from its theorem's subject, it improves over post-hoc refactoring (42% reduction against 33%) at two-thirds of the cost and more reliably; on proof length, the metric refactoring is built for, it approaches refactoring. Varying the objective's weights traces a quality-cost trade-off curve, so the user can choose how much a better proof is worth. Overall, LEVER is a performant, cost-efficient and tunable proof search algorithm for navigating the space of correct proofs.