AI Improves Lean 4 Theorem Prover Efficiency

The Lean 4 theorem prover's `grind` tactic, an automated solver, traditionally relies on hand-tuned heuristics for decisions like instantiation and case-splitting. This paper explores using machine learning to enhance these heuristics. The key challenge is that a learned heuristic might help one proof but inadvertently break another due to the non-monotone nature of `grind`'s search. To overcome this, the researchers designed a "failure-triggered cascade" where learned interventions are only invoked if the stock `grind` tactic initially fails. This ensures that no proofs previously solvable by `grind` are lost. They applied this to two internal decisions: a cost-aware `ematch` filter, which slightly increases solved problems and speeds up execution by about 5%, and a lookahead step that enables solving five additional theorems that previously timed out. A notable negative finding was that statically predicting the correct case split using feature-based models was no better than random, suggesting that runtime properties are crucial for such decisions. The study concludes that learning in theorem-proving tactics is most effective for optimizing bounded search, with a reliable symbolic fallback.