{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,29]],"date-time":"2026-07-29T21:02:35Z","timestamp":1785358955666,"version":"3.55.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2026,8,1]]},"abstract":"<jats:p>E-graphs, originally developed for use in automated theorem provers, are data structures that compactly represent a large number of expressions and the equalities between them.<\/jats:p>\n                  <jats:p>Recently, a technique called equality saturation adapted e-graphs for program optimization. Equality saturation can ameliorate issues with traditional, destructive term rewriting since e-graph rewriting only adds information to the e-graph. After rewriting, the e-graph represents a large space of equivalent terms (including the original term), and a final extraction procedure selects the best term according to a user-provided cost function.<\/jats:p>\n                  <jats:p>\n                    The\n                    <jats:monospace>egg<\/jats:monospace>\n                    library is a fast and flexible open-source implementation of e-graphs and equality saturation. Unlike solvers,\n                    <jats:monospace>egg<\/jats:monospace>\n                    is a white-box library for programmatic use. Users can easily define their own languages, rewrites, and analyses, and they can inspect and manipulate the e-graph directly. It incorporates novel techniques such as\n                    <jats:italic toggle=\"yes\">e-class analysis<\/jats:italic>\n                    , a mechanism for integrating program analyses modulo equality; and\n                    <jats:italic toggle=\"yes\">rebuilding<\/jats:italic>\n                    , a deferred invariant restoration algorithm.\n                    <jats:monospace>egg<\/jats:monospace>\n                    has been used in hundreds of academic and industrial projects for program optimization, synthesis, and verification in many domains; some are briefly highlighted in this article.\n                  <\/jats:p>","DOI":"10.1145\/3815481","type":"journal-article","created":{"date-parts":[[2026,7,29]],"date-time":"2026-07-29T20:18:56Z","timestamp":1785356336000},"page":"105-113","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["egg: Fast and Extensible Equality Saturation"],"prefix":"10.1145","volume":"69","author":[{"given":"Max","family":"Willsey","sequence":"first","affiliation":[{"name":"University of California, Berkeley, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chandrakana","family":"Nandi","sequence":"additional","affiliation":[{"name":"Certora Inc., Seattle, Washington, USA, WA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yisu Remy","family":"Wang","sequence":"additional","affiliation":[{"name":"University of California Los Angeles, Los Angeles, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oliver","family":"Flatt","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zachary","family":"Tatlock","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pavel","family":"Panchekha","sequence":"additional","affiliation":[{"name":"University of Utah, Salt Lake City, UT, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,7,29]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"Barrett C. Fontaine P. and Tinelli C. The Satisfiability Modulo Theories Library. SMT-LIB (2016); https:\/\/www.SMT-LIB.org."},{"key":"e_1_3_1_3_2","doi-asserted-by":"crossref","unstructured":"Cai Y. et al. Smoothe: Differentiable e-graph extraction.\u00a0In Proceedings of the 30th ACM Intern. Conf. on Architectural Support for Programming Languages and Operating Systems 1 Association for Computing Machinery\u00a0(2025) 1020\u20131034.","DOI":"10.1145\/3669940.3707262"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3571207"},{"key":"e_1_3_1_5_2","doi-asserted-by":"crossref","unstructured":"Chen C. et al. E-morphic: Scalable equality saturation for structural exploration in logic synthesis. arXiv (2025); arXiv:2504.11574","DOI":"10.1109\/DAC63849.2025.11133110"},{"key":"e_1_3_1_6_2","unstructured":"Coward S. Constantinides G.A. and Drane T. Abstract interpretation on e-graphs. arXiv (2022); arXiv:2203.09191."},{"key":"e_1_3_1_7_2","doi-asserted-by":"crossref","unstructured":"Coward S. Drane T. and Constantinides G.A. Rover: RTL optimization via verified e-graph rewriting. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems\u00a0(2024) 1\u20131.","DOI":"10.1109\/TCAD.2024.3410154"},{"key":"e_1_3_1_8_2","doi-asserted-by":"crossref","unstructured":"de Moura L. and Bj\u00f8rner N. Efficient e-matching for SMT solvers. In Proceedings of the 21st Intern. Conf. on Automated Deduction \u00a0 \u00a0F. Pfenning (Ed.) Springer Berlin Heidelberg\u00a0(2007) 183\u2013198.","DOI":"10.1007\/978-3-540-73595-3_13"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/1066100.1066102"},{"key":"e_1_3_1_10_2","unstructured":"Developers C. Cranelift; https:\/\/cranelift.dev\/."},{"key":"e_1_3_1_11_2","unstructured":"Developers C. CubeSQL API. (2025); https:\/\/github.com\/cube-js\/cube\/tree\/master\/rust\/cubesql\/cubesql."},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3720474"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322228"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90002-3"},{"key":"e_1_3_1_15_2","doi-asserted-by":"crossref","unstructured":"Nandi C. et al. Synthesizing structured CAD models with equality saturation and inverse transformations.\u00a0In Proceedings of the 41st ACM SIGPLAN Conf. on Programming Language Design and Implementation Association for Computing Machinery\u00a0(2020) 31\u201344.","DOI":"10.1145\/3385412.3386012"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.5555\/909447"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/357073.357079"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2813885.2737959"},{"key":"e_1_3_1_19_2","first-page":"223:1888","article-title":"Slotted e-Graphs: First-class support for (bound) variables in e-graphs","volume":"9","author":"Schneider R.","year":"2025","unstructured":"Schneider, R. et al. Slotted e-Graphs: First-class support for (bound) variables in e-graphs. Slotted E-Graphs Artifact\u00a09, PLDI\u00a0(Jun. 2025), 223:1888\u2013223:1910.","journal-title":"Slotted E-Graphs Artifact"},{"key":"e_1_3_1_20_2","unstructured":"Singher E. and Itzhaky S. Colored e-graph: equality reasoning with conditions.\u00a0arXiv (May 2023)."},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"e_1_3_1_22_2","doi-asserted-by":"crossref","unstructured":"Tate R. Stepp M. Tatlock Z. and Lerner S. Equality saturation: A new approach to optimization. In Proceedings of the 36th Annual ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages ACM\u00a0(2009) 264\u2013276.","DOI":"10.1145\/1480881.1480915"},{"key":"e_1_3_1_23_2","doi-asserted-by":"crossref","unstructured":"Wang Y.R. et al. SPORES: Sum-product optimization via relational equality saturation for large-scale linear algebra. In\u00a0Proceedings of the VLDB Endowment ACM\u00a0(2020).","DOI":"10.14778\/3407790.3407799"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356518"},{"key":"e_1_3_1_25_2","unstructured":"Yang Y. et al. Equality saturation for tensor graph superoptimization. In Proceedings of Machine Learning and Systems\u00a0(2021)."},{"key":"e_1_3_1_26_2","doi-asserted-by":"crossref","unstructured":"Zhang Y. et al. Better together: Unifying datalog and equality saturation. In\u00a0Proceedings of the ACM on Programming Languages\u00a07 PLDI\u00a0(Jun. 2023).","DOI":"10.1145\/3591239"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3815481","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,29]],"date-time":"2026-07-29T20:19:25Z","timestamp":1785356365000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3815481"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,29]]},"references-count":25,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2026,8,1]]}},"alternative-id":["10.1145\/3815481"],"URL":"https:\/\/doi.org\/10.1145\/3815481","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,29]]},"assertion":[{"value":"2026-07-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}