- 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
- 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?
- 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
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.
Response to Reviewer wMrg
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.
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.
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.