LLM-Guided Strategy Synthesis for Scalable Equality Saturation

• URL: http://arxiv.org/abs/2604.17364v1
• Date: Sun, 19 Apr 2026 10:21:26 GMT
• Title: LLM-Guided Strategy Synthesis for Scalable Equality Saturation
• Abstract summary: We present EggMind, an end-to-end framework for synthesizing reusable EqSat strategies.<n>At its core, EggMind introduces a domain-specific language, EqSatL, to represent EqSat strategies as explicit and inspectable artifacts.<n>We show 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.
• Score: 2.016500455428144
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Overcoming the Weakest-Link Effect in LLM-Driven Program Optimization via Heterogeneous Edit Recombination [59.679182823718556]
  HERO is a program that generates diverse, non-overlapping atomic edits and then systematically selects and composes them into coherent program improvements using evaluator scores.<n>We evaluate HERO across algorithmic problems, strategy games, the design of LLM-based agentic systems, and robotic path planning.
  arXiv  Detail & Related papers  (2026-07-31T02:05:45Z)
• GraphLoRA: Structure-Aware Low-Rank Adaptation for Large Language Model Recommendation [15.664889244642033]
  We propose a novel framework that generalizes low-rank adaptation from independent to structure-aware propagation.<n>GraphLoRA embeds a trainable graph message-passing network within the low-rank adaptation pathway, enabling structural signals to propagate through the parameter space.
  arXiv  Detail & Related papers  (2026-04-20T07:48:41Z)
• Understanding by Reconstruction: Reversing the Software Development Process for LLM Pretraining [66.89012795621349]
  Large Language Models (LLMs) often struggle with the deep, long-horizon reasoning required for complex software engineering.<n>We propose a novel paradigm: understanding via reconstruction.<n>We introduce a framework that synthesizes latent agentic trajectories using a multi-agent simulation.
  arXiv  Detail & Related papers  (2026-03-11T09:23:20Z)
• $\ abla$-Reasoner: LLM Reasoning via Test-Time Gradient Descent in Latent Space [71.23672814629448]
  $nabla$-Reasoner is an iterative generation framework that integrates differentiable optimization over token logits into the decoding loop.<n>$nabla$-Reasoner achieves over 20% accuracy improvement on a challenging mathematical reasoning benchmark.
  arXiv  Detail & Related papers  (2026-03-05T08:42:54Z)
• HELP: HyperNode Expansion and Logical Path-Guided Evidence Localization for Accurate and Efficient GraphRAG [53.30561659838455]
  Large Language Models (LLMs) often struggle with inherent knowledge boundaries and hallucinations.<n>Retrieval-Augmented Generation (RAG) frequently overlooks structural interdependencies essential for multi-hop reasoning.<n>Help achieves competitive performance across multiple simple and multi-hop QA benchmarks and up to a 28.8$times$ speedup over leading Graph-based RAG baselines.
  arXiv  Detail & Related papers  (2026-02-24T14:05:29Z)
• Quantum Circuit Generation via test-time learning with large language models [0.0]
  Large language models (LLMs) can generate structured artifacts, but using them as dependables for scientific design requires a mechanism for iterative improvement under black-box evaluation.<n>Here, we cast quantum circuit synthesis as a closed-loop, test-time optimization problem: an LLM proposes edits to a fixed-length gate list, and an external simulator evaluates the resulting state with the Meyer-Wallach (MW) global entanglement measure.<n>We introduce a lightweight test-time learning recipe that can reuse prior high-performing candidates as an explicit memory trace, augments prompts with a score-difference feedback, and applies restart-from-
  arXiv  Detail & Related papers  (2026-02-03T12:41:25Z)
• Semi-supervised Instruction Tuning for Large Language Models on Text-Attributed Graphs [62.544129365882014]
  We propose a novel Semi-supervised Instruction Tuning pipeline for Graph Learning, named SIT-Graph.<n> SIT-Graph is model-agnostic and can be seamlessly integrated into any graph instruction tuning method that utilizes LLMs as the predictor.<n>Extensive experiments demonstrate that when incorporated into state-of-the-art graph instruction tuning methods, SIT-Graph significantly enhances their performance on text-attributed graph benchmarks.
  arXiv  Detail & Related papers  (2026-01-19T08:10:53Z)
• Unleashing Degradation-Carrying Features in Symmetric U-Net: Simpler and Stronger Baselines for All-in-One Image Restoration [52.82397287366076]
  All-in-one image restoration aims to handle diverse degradations (e.g., noise, blur, adverse weather) within a unified framework.<n>In this work, we reveal a critical insight: well-crafted feature extraction inherently encodes degradation-carrying information.<n>Our symmetric design preserves intrinsic degradation signals robustly, rendering simple additive fusion in skip connections.
  arXiv  Detail & Related papers  (2025-12-11T12:20:31Z)
• SkyEgg: Joint Implementation Selection and Scheduling for Hardware Synthesis using E-graphs [2.363352915727704]
  We present SkyEgg, a novel hardware synthesis framework that jointly optimize implementation selection and scheduling.<n>SkyEgg achieves an average speedup of 3.01x over Vitis, with improvements up to 5.22x for complex expressions.
  arXiv  Detail & Related papers  (2025-11-19T10:39:45Z)
• GILT: An LLM-Free, Tuning-Free Graph Foundational Model for In-Context Learning [50.40400074353263]
  Graph Neural Networks (GNNs) are powerful tools for precessing relational data but often struggle to generalize to unseen graphs.<n>We introduce textbfGraph textbfIn-context textbfL textbfTransformer (GILT), a framework built on an LLM-free and tuning-free architecture.
  arXiv  Detail & Related papers  (2025-10-06T08:09:15Z)
• SymRTLO: Enhancing RTL Code Optimization with LLMs and Neuron-Inspired Symbolic Reasoning [30.938876549335067]
  This paper presents SymRTLO, a novel neuron-symbolic RTL optimization framework.<n>A symbolic module is proposed for analyzing and optimizing finite state machine (FSM) logic.<n> Experiments on the RTL-Rewriter benchmark with Synopsys Design Compiler and Yosys show that SymRTLO improves power, performance, and area (PPA) by up to 43.9%, 62.5%, and 51.1%, respectively.
  arXiv  Detail & Related papers  (2025-04-14T16:15:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.