一句话：提出 Statewalk DP，无需外部求解器即可高效完成有副作用 E-graph 的保序提取，并证明其按 statewalk width 可 tractable。
E-graph 已推动程序优化、合成与验证，但难以应用于内存和 I/O 等必须遵守执行顺序的有副作用程序；现有 effect-aware extraction 依赖整数线性规划（ILP），且往往主导总运行时间。本文提出 Statewalk DP，一种无需外部求解器即可执行副作用排序的提取算法。作者证明寻找任意 effect-safe extraction 是 NP-complete 的，但 Statewalk DP 在 statewalk width 这一度量副作用间数据流交互复杂度的参数下是 tractable 的。实践中 statewalk width 通常较小，因此该算法相较 ILP 提取取得数量级加速，生成程序在基准测试中与 LLVM 相当。作者在面向命令式 Bril 程序的原型 e-graph 编译器 EGGCC 中实现该算法，表明 effect-aware extraction 不再是瓶颈。
E-Graphs have enabled recent advances in program optimization, synthesis, and verification, yet remain difficult to apply to effectful programs whose memory and I/O operations must respect execution order. Existing effect-aware extraction algorithms rely on integer linear programming (ILP) and dominate total runtime. We introduce Statewalk DP, a new extraction algorithm that enforces effect ordering efficiently without external solvers. We prove that finding any effect-safe extraction is NP-complete, but show that Statewalk DP is tractable in statewalk width, a parameter that measures the complexity of dataflow interactions among effects. In practice, statewalk width generally remains small, enabling Statewalk DP to achieve order-of-magnitude speedups over ILP extraction while producing programs comparable to LLVM across our benchmarks. We implement the algorithm in EGGCC, a prototype e-graph-based compiler for imperative Bril programs, and demonstrate that effect-aware extraction is no longer a bottleneck.
@article{paperbot12161,
title = {Efficient Extraction for Effectful E-graphs},
author = {Oliver Flatt and Anjali Pal and Yihong Zhang and Ryan Tjoa and Kirsten Graham and Alex Fischman and Chandrakana Nandi and Eli Rosenthal and Zachary Tatlock and Haobin Ni},
journal = {Proceedings of the ACM on Programming Languages},
volume = {10},
number = {OOPSLA2},
year = {2026},
doi = {10.1145/3839530}
}