Learned Interventions in Lean 4 grind
Evan Wang, Simon Chess, Sophie Szeto, Theodore Meek
cs.LG
Jul 25, 2026 · v2
TL;DR
Learned interventions are integrated into Lean 4's grind tactic to filter e-matching instances and select case splits via failure-triggered lookahead.
Abstract
Lean 4's grind tactic combines congruence closure, E-matching, and case-splitting into a single automated solver, and like any such solver, it relies on hand-tuned heuristics to decide what to instantiate and where to case-split. These heuristics are tempting targets for learning, but there is a catch: because grind's search is non-monotone, a learned heuristic that helps one proof can break another, and an always-on replacement usually nets out near zero. We avoid this by invoking a learned intervention only after stock grind has already failed: a failure-triggered cascade that, by construction, cannot lose a proof grind already had. We apply it to two of grind's internal decisions. A cost-aware E-matching filter solves slightly more problems and runs about 5% faster. A lookahead step proves five theorems it otherwise times out on. We also report the negative result that motivated the design: across four feature-based models, statically predicting the correct case split is no better than random, because whether a split explodes is a runtime property that the features do not capture. Our results suggest that learning within theorem-proving tactics is most effective as a mechanism for deciding when and how to spend bounded search, backed by a reliable symbolic fallback.
Problem
Lean 4's grind tactic relies on hand-tuned heuristics for lemma instantiation and case-splitting. Because its search is non-monotone, an always-on learned replacement helps some proofs but breaks others, netting near zero.
Approach
Learning is invoked only after stock grind fails, forming a failure-triggered cascade that cannot lose a proof grind already had. A cost-aware e-match filter (a small MLP over 135-dimensional per-instance features) drops low-value instantiations. A bounded lookahead executes candidate case-splits under a budget rather than statically predicting them. All components are Lean-native with sub-millisecond latency.
Results
The e-match filter runs about 5% faster and recovers +2 solves on 855 held-out theorems. The lookahead cascade proves five theorems stock grind times out on, with zero regressions. Statically predicting the correct case split from features performs no better than random across four models.
| Policy | Rescue rate |
|---|
| grind (stock) | 0% |
| GBM cost model | 30–46% |
| failure-aware classifier | 46–53% |
| uniform random | 57% |
| 1-step lookahead | 100% |
Rescue rates of policies on rescuable split-failures
| theorem | stock | lookahead | rescue depth |
|---|
| 000125 | timeout | solve | 9 |
| 000281 | timeout | solve | 9 |
| 000470 | timeout | solve | 5 |
| 000530 | timeout | solve | 4 |
| 000619 | timeout | solve | 3 |
Theorem outcomes: stock vs lookahead cascade