acceptodds
Under review as a conference paper at ICLR 2027

Taming Equality Saturation by Synthesizing Reusable Strategies

Abstract

Equality Saturation (EqSat) compactly represents equivalent program variants in an e-graph and explores them through rewrite rules, exposing optimization opportunities overlooked by heuristic pass pipelines in conventional compilers. However, retaining these alternatives can cause exponential e-graph growth, incurring prohibitive runtime and memory overhead. Consequently, practical EqSat requires carefully engineered search control to orchestrate rewrite applications and constrain e-graph growth, which demands extensive manual effort. Large Language Models (LLMs) offer a promising way to automate this process, yet existing formulations typically optimize EqSat control separately for each input, causing domain-level optimization insights to be repeatedly rediscovered. Moreover, LLM-based EqSat search remains difficult because of the low-level controls, risky candidate evaluation, and weak refinement feedback exposed by existing systems. We present EGGMIND, a framework that addresses these issues by reformulating EqSat optimization as offline synthesis of reusable strategies followed by online reuse. EGGMIND introduces EqSatL, an executable structured representation of saturation strategies that exposes high-level decisions over rewrite interactions and simplification. Its synthesis process combines proof-derived structural feedback with tractability guidance to efficiently refine candidate strategies across representative program instances. The resulting strategies can be reused for unseen related programs without LLM calls. Evaluations show that EGGMIND consistently improves both solution quality and resource efficiency. Compared with unguided EqSat, it reduces expression cost by 54.6%, while achieving a runtime speedup and a 91.8% reduction in peak memory. It also achieves an speedup over an expert-designed strategy while matching or improving its solution quality.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Equality Saturation, Large Language Models, Compiler Optimization, E-Graphs, Strategy Synthesis, LLM for Compilers

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_wMrgOpenReview ↗
Rating
3
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The problem being studied is optimizing programs, and one way to do that is to via equality saturation.

Equality saturation refers to the saturation (in terms of computing the closure) of a set of starting states (programs) with respect to a set of (equivalence preserving) rewrite rules.

The idea is that one can do equality saturation to generate all possible equivalent programs, and then pick the one that is most efficient.

The challenge is that the process of saturation (computing the closure) can explode the space of programs. This can be partly solved by using e-graphs: an exponentially large number of programs can be efficiently represented using a small, shared representation called e-graphs. However, even e-graphs can explode in size when doing equality saturation.

The solution then is to apply only certain rewrite rules, and eagerly prune (simplify) the e-graph -- this can lead to incompleteness (loss of information), which is the prize one pays to maintain feasibility.

Earlier work had done this strategizing using LLM agents; however, the agent was used afresh for each new program optimization instance. This paper proposes a meta-learning framework where the agent is used to learn a general strategy (in a strategy language designed in this paper). The agent-generated strategy is then used to optimize programs (without any further LLM calls).

There is a clear benefit to reusing the agent's work via meta learning -- the experiments also establish this fact.

Critical strengths
  • The paper is the first to use meta-learning to learn strategies for equality saturation.
  • Evaluation also clearly demonstrate the benefits of using the proposed framework
  • Most evaluation is on one domain (program vectorization), but there is a mention of the approach working on two other domains.
Critical weaknesses
  • Most learning-related ideas -- using agents and the design of the agentic system -- is now fairly standard, and the paper just reuses the known machinery. Of course, one needs domain-specific details to make it work-- proof-derived feedback (which is basically tracking provenance and abstracting the sliced chain of rules into abstract tags); dependency-based ruleset partitioning and knowledge-guided simplification. These ideas are good, but they are domain-specific and it remains unclear if they would be of broader interest.

  • The results are likely to be more appealing to a specific audience, and those venues may be better suited to appreciating the significance of the results and evaluating its potential impact.

Questions for authors
  1. Is the claim here that using an agent to learn a strategy yields better results than an expert-crafted strategy? Lines 404-410 provide some intuition- what was the expert's response to the synthesized strategy?
  2. How much of the work was reused across the 3 domains? The question is whether the additional work -- for e.g., for setting up the knowledge-guided simplification -- is factored in while making conclusions.

Line216- What is "extract-and-rebuild contraction"?

2 comments
AuthorsOpenReview ↗

Response to Reviewer wMrg

Is the claim here that using an agent to learn a strategy yields better results than an expert-crafted strategy? Lines 404-410 provide some intuition- what was the expert's response to the synthesized strategy?

EggMind outperforms Isaria's expert-tuned schedule on the evaluated vectorization workloads. This result does not establish superiority over expert schedules in every domain. EggMind's goal is to automatically synthesize reusable optimization strategies for each domain.

We discussed EggMind's synthesized strategy with a domain expert, who highlighted both its useful insights and potential limitations. Comparing the schedules highlights the value of alternating short expansion phases with frequent contraction. EggMind repeatedly exposes useful rewrite opportunities while limiting accumulated alternatives, suggesting that contraction placement deserves attention alongside rule selection. However, early contraction may discard alternatives that enable later improvements, and fixed repetition counts may need adjustment for different workloads.

How much of the work was reused across the 3 domains? The question is whether the additional work -- for e.g., for setting up the knowledge-guided simplification -- is factored in while making conclusions.

Strategy synthesis is fully automated in all three domains. Beyond the rewrite rules, cost model, and programs required for egglog-based EqSat, EggMind requires no manually designed schedules or simplification preferences. The same synthesis framework is reused across the three domains. Knowledge-guided simplification is also reused, with its placement and pattern preferences generated automatically during synthesis. Domain setup is excluded from the reported synthesis overhead.

Line216- What is "extract-and-rebuild contraction"?

Extract-and-rebuild extracts a low-cost expression and uses it to initialize a fresh e-graph for subsequent rewriting. This reduces graph size by discarding accumulated alternatives, although some discarded alternatives could enable later improvements. We added the explanation at its first occurrence in Section 3.

Reviewer_wMrgOpenReview ↗

Acknowledging the author response

I have read the author's response to the review as well as the global response and responses to the other reviews. I have no further questions for the authors at the moment.

Reviewer_QQMBOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper shifts EqSat search control from per-program online optimization to offline strategy synthesis and reuse. It proposes EqSatL, proof-derived rewrite feedback, and two tractability-guided techniques. Experiments across vectorization, XLA, and EqMap show 54.6% cost reduction, 69.5× speedup, and 91.8% lower peak memory than unguided EqSat, plus an 8.7× speedup over Isaria without quality loss. Key weaknesses include insufficient analysis of reuse costs, transferability, backend dependence, and the lack of an online LLM baseline.

Critical strengths

EqSatL is a strong, well-designed abstraction. It structures EqSat control into three orthogonal dimensions, making backend strategies searchable by LLMs while retaining enough expressiveness to reproduce expert strategies (Fig. 3b).

Proof-derived motif feedback is technically insightful and well-validated. It extracts reusable rewrite patterns from proof trees, bridging the gap between coarse metrics and large e-graphs. Experiments across three domains, five baselines, and consistently low variance provide convincing evidence.

Critical weaknesses

Limited evidence for reuse and transferability. Offline synthesis is costly (15.1 minutes, 4.94M tokens), but no break-even analysis is provided. Evaluation is limited to the same benchmark families, leaving cross-scale generalization and out-of-distribution robustness unclear.

Backend dependence and missing baseline. Proof-derived feedback depends on egglog proofs and manual tags, without fallback or tag-granularity ablations. The absence of an online LLM baseline weakens the central offline-vs-online claim.

Questions for authors

No further questions

1 comment
AuthorsOpenReview ↗

Response to Reviewer QQMB

Limited evidence for reuse and transferability.

Evaluation is limited to the same benchmark families, leaving cross-scale generalization and out-of-distribution robustness unclear.

As clarified in the Global Response, EggMind reuses strategies within a domain and transfers its synthesis framework across domains. Our held-out evaluation includes kernel sizes beyond the synthesis range, providing evidence of cross-scale generalization. Regarding out-of-distribution robustness, EggMind learns shared optimization experience from similar programs. Programs with different computation patterns and optimization logic are fundamentally incompatible with the same strategy.

Offline synthesis is costly (15.1 minutes, 4.94M tokens), but no break-even analysis is provided.

We added a break-even analysis in Section 5.3 and Appendix C.2. Run 1 takes 790 seconds to synthesize. Across the 14 test programs, the mean optimization time saved per program is 235.91 seconds relative to Full EqSat and 77.05 seconds relative to Isaria. These give break-even points of 4 and 11 program optimizations, respectively, assuming a workload mix matching the test set. Such optimization needs are common in practice. For example, neural network deployment involves convolution and matrix-multiplication kernels of different sizes across layers and input configurations. Reusing the synthesized strategy across these kernels allows optimization-time savings to offset the initial synthesis time. When a related kernel with a new size arrives, the same strategy enables fast optimization without further LLM calls.

Proof-derived feedback depends on egglog proofs and manual tags, without fallback or tag-granularity ablations.

EggMind needs structural feedback that captures how rewrite rules contribute to optimization and interact with one another. With the egglog backend, we derive this feedback from proofs. Other backends could record rule applications and their dependencies, then trace or sample paths leading to lower-cost expressions to identify useful rule interactions. Evaluating this alternative remains future work.

Tags are generated by an LLM without manual editing and remain fixed during synthesis, as clarified in Section 3. The new study in Section 5.4 and Appendix C.4 compares the original 34 semantic tags for 355 rules with 8 coarse tags and 355 individual-rule tags. Each added setting uses one synthesis run with the same eight programs and 50-round budget. On the 14 test programs, the original grouping achieves 54.59% cost reduction, compared with 46.09% for fine tags. Coarse tags lead to six timeouts. Fine tags use 4.708M tokens compared with 4.149M for the original grouping, while achieving lower cost reduction. Fine tags offer more scheduling flexibility but may make useful combinations harder to identify within a fixed budget. Coarse tags restrict scheduling choices and activate many interacting rules together. This can cause substantial e-graph growth without reducing cost. The original grouping balances these effects in this experiment.

The absence of an online LLM baseline weakens the central offline-vs-online claim.

The raw egglog coding agent in Section 5.3 is an online, program-specific LLM baseline. Each script contains an input program and its optimization schedule, which the agent modifies and evaluates. Compared with this baseline, EggMind achieves greater cost reduction with lower mean search time and token usage, while producing a strategy reusable across related programs.

Reviewer_As1HOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

EggMind synthesizes equality-saturation strategies offline and reuses them on related programs without further LLM calls. Its EqSatL representation exposes rule partitioning, scheduling, repetition, and simplification. Strategy search combines proof-derived rewrite motifs with guidance intended to control e-graph growth. The main evaluation uses vectorization workloads, with additional studies in tensor-graph optimization and logic synthesis.

Critical strengths
  1. EqSatL exposes the control decisions that directly affect e-graph growth, while proof-derived motifs provide feedback richer than a final cost alone. The resulting explicit strategy is a useful artifact that can be reused without further LLM calls.

  2. The primary evaluation freezes a strategy synthesized on eight programs and tests it on fourteen held-out programs. Improvements over Isaria, additional synthesis runs, and coding-agent/evolutionary controls provide meaningful evidence of practical value.

Critical weaknesses
  1. The structural scope of strategy reuse is not fully established. The main held-out programs are different sizes of two kernel families, convolution and matrix multiplication. This supports reuse within related kernels, but leaves open how much the synthesized strategy relies on their shared rewrite structure. Section 5.5 synthesizes a new strategy in each additional domain, which demonstrates adaptability of the methodology rather than cross-domain reuse of one strategy. Unlike the vectorization experiment, the XLA and EqMap studies do not clearly identify separate synthesis and evaluation workloads. Please specify whether any of the 17 XLA or nine EqMap evaluation programs informed strategy selection. If so, those results remain useful adaptation studies, but should be distinguished from held-out reuse. A clear account of the existing workload splits would address this concern without requiring unrelated benchmarks.

  2. The search-efficiency comparison uses different budget units. Appendix C gives the coding agents a one-hour budget, limits evolutionary search to 80 underlying EqSat executions, and gives EggMind 50 search steps. These are not directly interchangeable: a search step may evaluate multiple programs, and the evolutionary baseline uses staged evaluation. Table 2 establishes that EggMind finds useful strategies quickly under the stated setup, but it is harder to isolate the efficiency of its search procedure without the actual candidate and evaluator-call counts, stopping rules, and selection histories. The component ablations should also state their synthesis repetitions and budget matching. In addition, the online speedup varies from 27.03× to 69.49× across the three complete runs despite nearly identical extraction-cost reductions. The paper discloses this variation, but the headline should be read as the first-run result rather than a typical speedup. Evaluator runtime, offline synthesis cost, and the runtime of the generated program are distinct quantities.

Questions for authors
  1. What are the synthesis, strategy-selection, and evaluation splits for XLA and EqMap? How do the held-out vectorization cases differ structurally from the synthesis cases?

  2. How many candidate evaluations and underlying EqSat executions does each search method actually perform, and what stopping and repetition protocols are used for the ablations?

1 comment
AuthorsOpenReview ↗

Response to Reviewer As1H

What are the synthesis, strategy-selection, and evaluation splits for XLA and EqMap? How do the held-out vectorization cases differ structurally from the synthesis cases?

We do not consider cross-domain transferability of learned strategies because different domains use different rewrite rules, making their strategies fundamentally incompatible. XLA uses 4 synthesis and 13 test programs, and EqMap uses 2 synthesis and 7 test programs. We select the best candidate by its performance on the synthesis programs and apply it unchanged to the test set. As discussed in the Global Response, the vectorization synthesis and test cases share the same convolution and matrix-multiplication patterns and differ in size. We have clarified the splits in Sections 5.2 and 5.5 and listed the program characteristics in Appendix C.1.

How many candidate evaluations and underlying EqSat executions does each search method actually perform, and what stopping and repetition protocols are used for the ablations?

We reran evolutionary search with a one-hour stopping budget, matching the coding agents. The table reports mean evaluation counts, search time, and token usage across three runs, with cost-reduction ranges over complete runs.

MethodCandidate evaluationsUnderlying EqSat executionsSearch time (min)LLM tokens (M)Cost reduction
EggMind15.061.315.14.9454.39–54.59%
Coding agent on EqSatL84.784.742.35.084.59–50.74%
Coding agent on raw egglog100.7100.748.46.4417.54–42.19%
Evolutionary search28.7112.760.2—−1.06–24.31%

EggMind achieves the highest cost reduction with the fewest candidate evaluations and recorded EqSat executions in the table. Its shorter search time and lower mean token usage further demonstrate the efficiency of finding high-quality strategies.

Each component ablation independently synthesizes one strategy using the same eight synthesis programs and 50-round stopping budget as full EggMind, then evaluates it on the same 14 test programs. Each ablation uses one synthesis run.

We updated the evolutionary comparison in Section 5.3 and Table 2. Section 5.4 now specifies the ablation protocol, and we added search accounting in Appendix C.2.

In addition, the online speedup varies from 27.03× to 69.49× across the three complete runs despite nearly identical extraction-cost reductions. The paper discloses this variation, but the headline should be read as the first-run result rather than a typical speedup.

We revised the Abstract and Introduction to report averages across three runs. The mean optimization speedup is 43.50 ± 24.20× relative to Full EqSat, with ± denoting sample standard deviation. Section 5.2 now presents per-program averages across the three synthesis runs, with error bars showing the minimum and maximum optimization times. We include the EggMind results from Table 6 in Appendix C.2 below for a more detailed comparison across runs.

RunCost reductionOptimization speedupSearch time (min)LLM tokens (M)
154.59%69.49×13.174.15
254.59%39.38×14.275.64
354.39%21.62×17.785.02

Comments on the paper

1 comment
AuthorsOpenReview ↗

Global Response

Scope of strategy reuse and framework transferability

EggMind aims to automate strategy design for each optimization domain, capturing domain knowledge and optimization experience in a strategy that efficiently optimizes related programs. Reusability refers to applying this strategy to different programs within the same domain. Transferability refers to applying the EggMind framework across domains to automatically synthesize a strategy for each domain, using its rewrite rules, cost model, and representative programs.

For example, our vectorization workloads contain convolution and matrix-multiplication kernels of different sizes. In manual kernel optimization, different sizes can require different choices about parallelism and hardware resource utilization, even when the computation pattern is unchanged. A shared EqSat strategy must likewise accommodate how optimization opportunities and search costs change with size. A rewrite schedule that exposes useful alternatives on a small kernel can cause excessive e-graph growth on a larger one, while a more restrictive schedule can miss useful transformations. EggMind searches for a strategy that balances these effects across instances, allowing optimization experience from representative kernels to be reused on additional programs.

Additional Experiments and Analysis

  • Performance across runs. Section 5.2 now presents per-program averages across three synthesis runs, with error bars showing the range of optimization times. The Abstract and Introduction report average optimization speedups across these runs.
  • Evolutionary search. We reran evolutionary search with the same one-hour budget as the coding agents and compared optimization quality and search overhead.
  • Tag granularity. We compared optimization efficiency and quality across different tag granularities.
  • Break-even analysis. We estimated how many program optimizations are needed for the time savings to offset one strategy synthesis run.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.