CERES: Making Equality Saturation Memory-Scalable
summary
CERES is a rewrite scheduler that picks a small subset of equality saturation rewrites with a cross-entropy sampler and applies them to keep e-graphs under a node limit. Evaluated on Herbie’s Hamming benchmark and on synthesized rule sets, CERES reaches similar or better results while using 8–12× lower memory budget and, for fixed memory, often achieving 40–62% reduction in expression cost versus egg’s Backoff; it runs with extra scheduling overhead but lowers overall search and extraction time.
AI-written summary · about
chapters (14)
- 0:00CERES and equality saturation
- 1:04Equality saturation background
- 2:29Current equality saturation limits
- 6:45Rewrite schedulers limits
- 10:18Introducing CERES
- 13:49Important rewrites definition
- 15:53Finding important rewrites
- 17:17Evaluation setup
- 18:19Math benchmark results
- 19:22Herbie expert rules results
- 20:44Herbie synthesized rules results
- 22:08DSP vectorization results
- 23:30Summary
- 23:55Q&A
related talks
14mRewrite Rule Inference Using Equality Saturation
30megg: Fast and Extensible Equality Saturation
24mIncremental Equality Saturation
19meqsat: An Equality Saturation Dialect for Non-destructive Rewriting
20mEquality Saturation and Joins
13mMind the Abstraction Gap: Bringing Equality Saturation to Real-World ML Compilers
21mImproving Equality Saturation for EDA via Semantic E-Graphs
19mDestructive E-Graph Rewrites