Quick Intro to E-Graphs

Have you ever wanted to have an intermediate representation where you can have two definitions for a particular node? Remember the debate over whether we should represent a Linear operator as a single node or a matrix multiply followed by a bias addition? E-Graphs are a particularly elegant way to to do this. Max Willsey et al. (https://egraphs-good.github.io) provide a high-performance simple implementation in their paper and codebase.

I put together a notebook in Python that walks through provides an executable implementation of the core algorithm. I think EGraphs may prove useful for ML applications, so even though it might be premature to shove e-graph implementation into our compilers, it is good to know the tool is out there.

5 Likes