Learned Interventions in Lean 4 grind
Evan Wang, Simon Chess, Sophie Szeto, Theodore Meek
cs.LG
Jul 25, 2026 · v1
TL;DR
Integrates learned interventions into Lean 4's grind tactic via a failure-triggered cascade with a cost-aware e-match filter and split lookahead.
Abstract
Lean 4's \grind{} tactic combines congruence closure, \ematch{}ing, 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 \ematch{} 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 e-match instantiation and case-splitting. Because its search is non-monotone, an always-on learned replacement helps some proofs while breaking others, netting near zero.
Approach
Learned interventions are invoked only after stock grind has already failed, forming a failure-triggered cascade that cannot lose proofs grind already solves. A cost-aware e-match filter (a small MLP over 135 features) drops low-value instantiations. A bounded lookahead probe tries alternative split candidates when grind's chosen split leads to timeout. All components are Lean-native with sub-millisecond latency.
Results
The e-match filter runs about 5% faster and recovers +2 solves on an 855-theorem held-out suite. The lookahead cascade proves five theorems that stock grind times out on, with zero regressions. Static feature-based split prediction across four models performs no better than random on high-impact decisions.
| Policy | rescue rate |
|---|
| grind (stock) | 0% |
| GBM cost model | 30–46% |
| failure-aware classifier | 46–53% |
| uniform random | 57% |
| 1-step lookahead | 100% |
Rescue rate of split policies on rescuable split-failures
| theorem | stock | lookahead | cascade | depth |
|---|
| 000125 | timeout | solve | solve | 9 |
| 000281 | timeout | solve | solve | 9 |
| 000470 | timeout | solve | solve | 5 |
| 000027 | solve | timeout | solve | 57 |
Theorems rescued by lookahead cascade