# LLM-Guided Strategy Synthesis for Scalable Equality Saturation

arXiv: https://arxiv.org/abs/2604.17364 · HTML: https://mlsanity.com/paper/2604.17364/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 42 references that are in the map.
- First posted on arXiv 19 Apr 2026.

## Builds on (most cited first, 18 of 18)

- [Meta Large Language Model Compiler: Foundation Models of Compiler Optimization](https://mlsanity.com/paper/2407.02524/) (2024)
- [Equality Saturation for Tensor Graph Superoptimization](https://mlsanity.com/paper/2101.01332/) (2021)
- [babble: Learning Better Abstractions with E-Graphs and Anti-Unification](https://mlsanity.com/paper/2212.04596/) (2022)
- [Rewrite Rule Inference Using Equality Saturation](https://mlsanity.com/paper/2108.10436/) (2021)
- [MCTS-GEB: Monte Carlo Tree Search is a Good E-graph Builder](https://mlsanity.com/paper/2303.04651/) (2023)
- [Magellan: Autonomous Discovery of Novel Compiler Optimization Heuristics with AlphaEvolve](https://mlsanity.com/paper/2601.21096/) (2026)
- [Small Proofs from Congruence Closure](https://mlsanity.com/paper/2209.03398/) (2022)
- [Agentic Code Optimization via Compiler-LLM Cooperation](https://mlsanity.com/paper/2604.04238/) (2026)
- [Implementation and Synthesis of Math Library Functions](https://mlsanity.com/paper/2311.01515/) (2023)
- [Target-Aware Implementation of Real Expressions](https://mlsanity.com/paper/2410.14025/) (2024)
- [e-boost: Boosted E-Graph Extraction with Adaptive Heuristics and Exact Solving](https://mlsanity.com/paper/2508.13020/) (2025)
- [TensorRight: Automated Verification of Tensor Graph Rewrites](https://mlsanity.com/paper/2511.17838/) (2025)
- [Pushing Tensor Accelerators Beyond MatMul in a User-Schedulable Language](https://mlsanity.com/paper/2512.02371/) (2025)
- [Beyond Pass-by-Pass Optimization: Intent-Driven IR Optimization with Large Language Models](https://mlsanity.com/paper/2602.18511/) (2026)
- [Sketch-Guided Equality Saturation: Scaling Equality Saturation to Complex Optimizations of Functional Programs](https://mlsanity.com/paper/2111.13040/) (2021)
- [The Maude strategy language](https://mlsanity.com/paper/2402.00275/) (2024)
- [SkyEgg: Heterogeneity-Aware Hardware Synthesis via Equality Saturation](https://mlsanity.com/paper/2511.15323/) (2025)
- [E-Graphs as a Persistent Compiler Abstraction](https://mlsanity.com/paper/2602.16707/) (2026)

## Abstract (arXiv)

Equality saturation (EqSat) is a powerful optimization paradigm that compactly represents many equivalent programs in an e-graph and delays commitment until extraction selects a lowest-cost program. Making EqSat effective, therefore, requires not only domain-specific rewrite rules but also domain-specific strategies. Today, much of this strategy design is still manual, making it a major obstacle to automating e-graph-based compilers. Recent rule-synthesis frameworks can automatically infer large rewrite vocabularies from semantic specifications, but they also enlarge the rewrite space and further exacerbate e-graph explosion. Although large language models (LLMs) make automated strategy synthesis plausible, directly evolving backend code remains ineffective in practice. The search lacks reusable strategy abstractions and actionable feedback, and can easily trigger e-graph explosion or converge to poor designs. We present EggMind, an LLM-guided, end-to-end framework for synthesizing reusable EqSat strategies. At its core, EggMind introduces a domain-specific language, EqSatL, to represent EqSat strategies as explicit and inspectable artifacts. It then proposes an LLM-guided agentic workflow, equipped with novel techniques including proof-derived rewrite motif caching and tractability guidance, to search efficiently for high-quality strategies while keeping synthesis stable under e-graph growth. Evaluation shows that EggMind substantially improves the resource-quality trade-off on vectorization benchmarks, reducing final cost by 45.1% and peak RAM by 69.1% relative to full EqSat. We further show that the same methodology transfers effectively to an XLA-based tensor compiler, and demonstrate its practical potential in a logic-synthesis case study with augmented rewrite spaces.