E-graphs：AI 如何同时保留一百种等价写法，最后挑出最好的？

很多程序优化看起来像是在“改写代码”：把一个表达式换成更短的表达式，把一串计算折叠成一个常量。但如果每改一步就丢掉旧方案，编译器很容易走进局部最优。E-graph 提供了另一种思路：先把等价的写法放在一起保存，等候选方案足够丰富后，再统一挑出成本最低的一种。

它解决的是什么问题

假设 a * 2 可以写成 a + a，而 a + a 又可以在某些硬件上变成一条更快的指令。传统重写会沿着一条路径不断替换，替换方向和顺序都会影响最终结果。E-graph 则把这些表达式放进同一个等价类，表示“它们在语义上可以互相替代”，但暂时不急着删除任何一个。

这也是 equality saturation 的关键：不断应用安全的重写规则，让等价类“长大”，直到没有值得继续加入的等价表达式；然后再用一个成本模型做 extraction，选择指令数量、延迟、能耗或寄存器压力更低的版本。

把 E-graph 想成一张不断扩张的地铁换乘图。不同路线可能经过不同站点，但它们都能把乘客送到同一个目的地。普通优化像是走到一个换乘站就删掉其他路线；e-graph 则保留多条路线，最后根据时间、票价或换乘次数选最合适的一条。

它并不等于“任何改写都安全”。重写规则必须维护等价关系，成本模型也必须符合目标平台。一个在桌面 CPU 上更短的表达式，可能在 GPU、向量指令或特定缓存层次上并不更快。

AI 编程经常会给出多种可行实现：递归、循环、批处理、缓存，甚至不同的数据结构。E-graph 提供了一个很有启发性的工程思路：不要让第一次生成的方案成为唯一方案，而是把可证明等价的候选集中管理，再按可解释的成本选择。

这类方法尤其适合查询优化、张量表达式、算术化简和编译器后端。它的代价是图可能快速膨胀，因此现实系统需要限制规则、控制节点数量，并把“更好”定义清楚。

E-graph 的核心不是一棵更复杂的语法树，而是“同时保存许多等价程序”。Equality saturation 则把“边改边丢候选”改成“先积累可能性，最后统一决策”。当 AI 能快速产生方案时，这种先保留、后选择的思路也能帮助人类避免过早锁定答案。