Guided Equality Saturation
summary
Guided equality saturation splits a hard e-graph search into sequences of smaller equality-saturation runs guided by human-provided intermediate sketches, shrinking guide size by about 90% and using at most three guides for complex cases. Integrated with Lean 4 integration it turns multi-minute proof searches into under a second; in the Rise compiler and TVM matrix benchmarks unguided search exceeds 8 GB and times out while guided runs finish within seconds using <1 GB memory and report up to 582x faster and 116x less memory.
AI-written summary · about