E-Stitch: Top-Down Library Learning for E-Graphs
summary
Extends Stitch’s top‑down search to operate over e‑graphs, so rewrites like commutativity are matched rather than missed, and introduces a better lower bound computed bottom‑up on the e‑graph to prune futile branches. Uses either exhaustive frontier search or stochastic Monte Carlo particles to avoid symmetry blowup. On Babble benchmarks E‑Stitch improves compression from 4.06× to 4.85× and cuts median time from about 60 seconds to 2.6 seconds, while on pure trees it matches Stitch quality with roughly 2× runtime overhead and greater robustness.
AI-written summary · about
chapters (19)
- 0:00E-Stitch intro and library learning
- 1:26Library learning importance
- 2:30Stitch and Babel limits
- 3:35Problem statement compression
- 4:18Stitch top-down search
- 5:42Stitch fails with rewrites
- 7:48Stitch over e-graphs
- 9:57E-graph compatibility changes
- 10:39Tighter e-graph bounds
- 13:47Computing compression bounds
- 15:09Search algorithms comparison
- 16:33Sequential Monte Carlo
- 17:17Results on program trees
- 17:57Rewrite rules and Babel
- 18:58Molecule benchmark SMILES
- 20:22Molecule compression gains
- 21:03SMC rewrites advantage
- 21:45Summary open questions
- 22:27Q&A extraction base order
related talks
25mEGSTRA: E-Graph-Based Strategy for Test Suite Reduction and Abstraction
30megg: Fast and Extensible Equality Saturation
24mPolynomial-Time Program Equivalence for Machine Knitting
31mA Tale of Breadth-First Search
26mTowards Efficient Model Comparison Using Automated Program Rewriting
38mCan we visualize software complexity?
01h 09mSCCharts Twelve Years Later: A Reflection on Sequential Constructiveness and(…)
32mSynthesis, Simplification and Analysis of Biological Networks Using Higher Order Topological Connect