~/talk

Incremental Equality Saturation

on YouTube 24m
Talkat EGRAPHS 2025 · 2025-06-16..06-17· [compilers-and-language-design]

speakers

name:Rupanshu Soi
links:none on file
name:Benjamin Driscoll
links:none on file
name:Ke Wang
speakerdeck:kevinwang15
name:Alex Aiken
bluesky:alexaiken.bsky.social

resources

video:https://youtu.be/pbda2mTyHnQ
slides:none on file

summary

Introduces an incremental egraph with per–e-class versions and a top-K analysis (K=2) so rewrites only target e-classes created by the current version and inner matches pick from the lowest-cost K enodes. Implementation reuses egg, uses a node-limit budget, and a local cost analysis; on 1,000 randomly generated algebraic terms (sizes 11/13) incremental ESAT becomes Pareto-optimal versus standard ESAT as budget grows, runs about 3x faster at 6,400 enodes but misses better results for 40/1,000 terms; requires a local cost function.

AI-written summary · about

chapters (11)

  1. 0:00Incremental equality saturation intro
  2. 1:03Batched saturation limits
  3. 2:50Core idea of incremental ES
  4. 4:16Example walkthrough
  5. 6:22Versions and e-matching
  6. 7:23Top K for runaway e-class
  7. 9:11Soundness and coverage of EKSAT
  8. 11:00Version policies for performance
  9. 13:06Performance results
  10. 14:54Limitations and future work
  11. 15:34Q&A

related talks

~/search
type to search 6,249 conferences, 138,987 speakers and 185,172 talks
~/help
cmdctrl k
search every conference, speaker and series
/
focus the filter search
h
home
c
conferences
s
speakers
e
series
t
light / dark — the status bar button does the same
?
this help
esc
close this, then clear every filter — or just the search, while you are typing in it

Ignored while you are typing. Pages without a filter rail have no search to focus.