arXiv:2604.17364cs.AIcs.MA2026-04

用大模型自动设计可复用的程序优化策略,解决编译器优化爆炸问题。

LLM-Guided Strategy Synthesis for Scalable Equality Saturation

  • 设计领域专用语言 EqSatL 表示策略,支持可检查与复用。
  • 通过大模型引导搜索,在向量优化中降低45.1%成本、69.1%内存峰值。
  • 支持跨编译器迁移,适合自动化编译器与逻辑综合场景。

等式饱和(EqSat)是一种强大的优化范式,通过在 e-graph 中紧凑表示多个等价程序,并在提取阶段选择最低成本方案延迟决策。实现高效 EqSat 需要领域特定的重写规则和策略。当前多数策略设计仍依赖人工,成为基于 e-graph 编译器自动化的瓶颈。尽管规则合成框架可从语义规范自动推导大规模重写词汇表,但进一步扩大了重写空间,加剧 e-graph 爆炸。虽然大语言模型(LLMs)使自动化策略合成成为可能,但直接演化后端代码在实践中效果不佳:搜索缺乏可复用的策略抽象与可操作反馈,易引发 e-graph 爆炸或收敛至劣解。本文提出 EggMind,一个大模型引导的端到端策略合成框架。其核心是引入领域专用语言 EqSatL,将 EqSat 策略表示为显式、可检查的实体。同时提出大模型引导的智能体工作流,结合证明衍生重写模式缓存与可处理性引导等新方法,实现高效搜索,保持合成稳定性。评估表明,EggMind 在向量化基准上显著改善资源-质量权衡,相比完整 EqSat,最终成本降低 45.1%,峰值内存减少 69.1%。进一步验证该方法在 XLA 基础张量编译器上的有效迁移,并在增强重写空间的逻辑综合案例研究中展示其实用潜力。

原文摘要 · Abstract (English)

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.

编译优化大模型等式饱和策略合成

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。