Software developers have long faced a frustrating paradox: the programs that must be made faster are often too complex to optimize by hand. Compilers, hardware-design systems, database engines and numerical tools all need to transform large, intricate programs into simpler versions that produce exactly the same results. Yet each field has traditionally relied on its own specialized optimizer, making improvement expensive, slow and difficult to generalize. A new open-source toolkit called egg is challenging that model by offering a common technical foundation for optimizing programs across very different domains.
Developed by University of Utah computer scientist Pavel Panchekha and collaborators at the University of Washington and other institutions, egg is designed to make a powerful optimization technique known as equality saturation practical. The approach represents many mathematically or logically equivalent versions of a program at the same time, rather than committing immediately to a single sequence of transformations. This allows a system to explore a broad space of possible implementations before selecting the version that best meets a chosen goal, such as speed, memory use, circuit size or numerical accuracy.
At the center of egg are data structures called e-graphs, short for equality graphs. An e-graph groups together expressions that are known to be equivalent while preserving the different ways those expressions can be constructed. For example, a mathematical expression can be represented in several algebraically equivalent forms, while a computer program may contain alternative instruction sequences that calculate the same result. Instead of repeatedly rewriting one expression and discarding previous versions, the e-graph stores the alternatives together. This makes it possible to apply many transformations without losing potentially valuable solutions.
The process continues through equality saturation. A developer supplies rewrite rules that describe valid transformations, such as replacing a multiplication by a constant with a sequence of additions, simplifying an algebraic identity or reorganizing operations to better match a processor. Egg applies these rules across the e-graph, adding equivalent forms until the system reaches a practical limit or no significant new information can be found. The result is not one optimized program but a compact representation of a large family of equivalent programs. A separate extraction step then evaluates the alternatives using a cost model and selects the most efficient candidate.
This design addresses one of the hardest problems in automated optimization: local improvements do not always produce the best global result. A transformation that appears beneficial in isolation may block a better transformation later. Traditional optimizers often depend on carefully ordered passes, extensive heuristics and years of engineering to manage these interactions. Equality saturation delays the final choice, allowing transformations to interact within a shared structure. According to Panchekha, this can reduce the amount of specialized infrastructure required to build a compiler, synthesizer or optimizer, allowing researchers to begin experimenting with only a relatively small amount of code.
The egg project began while Panchekha was a graduate student in the laboratory of Zachary Tatlock, a professor at the University of Washington’s Allen School of Computer Science and Engineering. Since its public release in 2020, the toolkit has attracted researchers and engineers working in areas ranging from deep learning and numerical computing to hardware design. Companies including Intel have explored e-graphs for chip optimization, where even modest reductions in circuit size or power consumption can have major consequences for the performance and cost of finished hardware.
One of the clearest demonstrations came from Herbie, a numerical-computing tool developed by Panchekha. Herbie searches for mathematically equivalent ways to evaluate floating-point expressions, with the goal of improving numerical accuracy. After egg was integrated into the system, Herbie reportedly became 3,000 times faster while also producing better results. The example illustrates why retaining many candidate forms can be useful: an expression that is mathematically equivalent to another may behave differently under the rounding and precision limits of computer arithmetic, so the fastest solution is not necessarily the most accurate one.
The toolkit’s reported impact extends beyond numerical software. Researchers have cited speedups of up to 50 times in neural-network optimization and reductions of 63 percent in hardware-circuit size. Egg has also influenced efforts to rebuild production compilers around e-graphs, suggesting that the technique is moving beyond an academic experiment. Its appeal lies partly in its extensibility. Developers can define domain-specific expressions, rewrite rules, analyses and cost functions, then use the same underlying machinery to explore optimization choices in a new field.
The method is not without limitations. Equality saturation can consume substantial memory because it intentionally preserves many alternatives instead of discarding them immediately. Panchekha says ongoing work in computer graphics at the University of Utah has exposed cases in which egg uses too much memory to serve as a complete replacement for a traditional optimizer. Even in those situations, however, the library can function as an experimental platform: researchers can test transformation ideas, identify promising strategies and later transfer them into a more specialized system. A paper describing the toolkit, “egg: Fast and Extensible Equality Saturation,” has been published in Communications of the ACM as a Research Highlight, marking the project as a notable contribution to computer science. Its rapid adoption suggests that a general-purpose optimization framework may have arrived at a moment when many different industries are ready to use it.
Subject of Research: Computer science and software optimization
Article Title: egg: Fast and Extensible Equality Saturation
News Publication Date: 29-Jul-2026
Web References: https://profiles.faculty.utah.edu/u6026564; https://egraphs-good.github.io/; https://egraphs.org/; https://cacm.acm.org/research-highlights/technical-perspective-egg-ridiculously-fast-and-extensible-equality-saturation/
References: Communications of the ACM, DOI: 10.1145/3815481
Keywords
e-graphs, equality saturation, egg toolkit, compiler optimization, software engineering, numerical computing, hardware design, program synthesis, computer science
