Equality Saturation Guided by Large Language Models
summary
Introduces LLM-guided equality saturation (LGuess): LLMs propose sparse, high‑level rewrite checkpoints while e‑graphs supply the low‑level rewrite chains; a learned probabilistic model scores likely checkpoints extracted from saturated e‑graphs. Prototype targets multivariable polynomial factorization and beats both vanilla equality saturation and asking the LLM to produce full rewrite chains. Implements a dynamic‑programming extractor that minimizes string distance to the LM output and a final LM equivalence check; it solves the freshman’s‑dream and group‑theory examples under a strict three iterations per round resource limit.
AI-written summary · about
chapters (8)
- 0:00Introduction
- 1:26LLM limits in optimization
- 2:30Equality saturation with LLMs
- 5:04Models versus rewrite systems
- 8:16Query design for guidance
- 13:20Evaluation and case studies
- 16:56Future directions
- 19:26Question and answer session
related talks
13mMind the Abstraction Gap: Bringing Equality Saturation to Real-World ML Compilers
30megg: Fast and Extensible Equality Saturation
20mEquality Saturation and Joins
17mBetter Together: Unifying Datalog and Equality Saturation
24mOptimism in Equality Saturation
15mEquality Saturation Theory Exploration à la Carte
53mSemantics-based program manipulation in the age of LLMs
14mRewrite Rule Inference Using Equality Saturation