Fast and Optimal Extraction for Sparse Equality Graphs
summary
The paper proves e-graph extraction is NP-hard and hard to approximate by reduction from set cover, then gives a fixed-parameter tractable dynamic program over tree decompositions, implemented as a Rust implementation. Evaluated on Cranelift benchmarks, it optimally extracts most e-graphs with treewidth ≤ 10, beats ILP on 96% of those instances, and—discounting tree decomposition time—runs about 10x faster than ILP; cycle extraction and decomposition cost remain bottlenecks.
AI-written summary · about
chapters (9)
- 0:00e-graphs and equality saturation
- 1:49Optimal extraction challenges
- 3:56e-graphs as bipartite graphs
- 6:24Tree decomposition for e-graphs
- 8:31Dynamic programming extraction
- 12:52Complexity and Cranelift implementation
- 14:41Experimental results
- 15:23Future work
- 16:07Question and answer session
related talks
23mVersioned E-Graphs
25mDisequalities in E-Graphs: An Experiment
21mCut Tracing with E-Graphs for Boolean FHE Circuit Synthesis
30megg: Fast and Extensible Equality Saturation
19mA Joint Approach to Instruction Scheduling and Algebraic Rewriting with E-Graphs
25mLifting E-Graphs: A Function Isn’t a Constant
24mIncremental Equality Saturation
23mPerformant Dynamically Typed E-Graphs in Pure Julia