Learned Interventions Boost Lean 4 Theorem Prover Performance

The `grind` tactic in Lean 4, an automated theorem prover, combines congruence closure, E-matching, and case-splitting, relying on hand-tuned heuristics for its decisions. While these heuristics are prime candidates for machine learning improvements, the non-monotone nature of `grind`'s search means that a learned heuristic might help one proof but break another, often resulting in no net gain if applied universally. To circumvent this, researchers devised a "learned intervention" strategy that is only invoked after the standard `grind` tactic has already failed. This failure-triggered cascade ensures that the learned heuristic cannot negatively impact proofs that `grind` would have already solved. The intervention was applied to two internal decisions within `grind`. Specifically, a cost-aware E-matching filter was developed, which not only solved slightly more problems but also ran approximately 5% faster. Additionally, a lookahead step enabled `grind` to prove five theorems that it previously timed out on. The research also reported a negative finding: statically predicting the correct case split using feature-based models was no better than random, indicating that the explosiveness of a split is a runtime property not captured by static features. These results suggest that integrating learning into theorem-proving tactics is most effective when used to strategically allocate bounded search resources, always backed by a reliable symbolic fallback.