# Equality Saturation for Tensor Graph Superoptimization

arXiv: https://arxiv.org/abs/2101.01332 · HTML: https://mlsanity.com/paper/2101.01332/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 35 references that are in the map.
- First posted on arXiv 5 Jan 2021.

## Builds on (most cited first, 9 of 9)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Rethinking the Inception Architecture for Computer Vision](https://mlsanity.com/paper/1512.00567/) (2015)
- [Aggregated Residual Transformations for Deep Neural Networks](https://mlsanity.com/paper/1611.05431/) (2016)
- [Neural Architecture Search with Reinforcement Learning](https://mlsanity.com/paper/1611.01578/) (2016)
- [Learning Transferable Architectures for Scalable Image Recognition](https://mlsanity.com/paper/1707.07012/) (2017)
- [SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and <0.5MB model size](https://mlsanity.com/paper/1602.07360/) (2016)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Souper: A Synthesizing Superoptimizer](https://mlsanity.com/paper/1711.04422/) (2017)

## Built on by (most cited first, 27 of 27)

- [Mirage: A Multi-Level Superoptimizer for Tensor Programs](https://mlsanity.com/paper/2405.05751/) (2024)
- [Hidet: Task-Mapping Programming Paradigm for Deep Learning Tensor Programs](https://mlsanity.com/paper/2210.09603/) (2022)
- [HeuriGym: An Agentic Benchmark for LLM-Crafted Heuristics in Combinatorial Optimization](https://mlsanity.com/paper/2506.07972/) (2025)
- [MPK: A Compiler and Runtime for Mega-Kernelizing Tensor Programs](https://mlsanity.com/paper/2512.22219/) (2025)
- [Automap: Towards Ergonomic Automated Parallelism for ML Models](https://mlsanity.com/paper/2112.02958/) (2021)
- [MCTS-GEB: Monte Carlo Tree Search is a Good E-graph Builder](https://mlsanity.com/paper/2303.04651/) (2023)
- [Neural Architecture Search using Property Guided Synthesis](https://mlsanity.com/paper/2205.03960/) (2022)
- [Neptune: Advanced ML Operator Fusion for Locality and Parallelism on GPUs](https://mlsanity.com/paper/2510.08726/) (2025)
- [A Data-Centric Optimization Framework for Machine Learning](https://mlsanity.com/paper/2110.10802/) (2021)
- [Learned Graph Rewriting with Equality Saturation: A New Paradigm in Relational Query Rewrite and Beyond](https://mlsanity.com/paper/2407.12794/) (2024)
- [REASONING COMPILER: LLM-Guided Optimizations for Efficient Model Serving](https://mlsanity.com/paper/2506.01374/) (2025)
- [Collage: Seamless Integration of Deep Learning Backends with Automatic Placement](https://mlsanity.com/paper/2111.00655/) (2021)
- [X-RLflow: Graph Reinforcement Learning for Neural Network Subgraphs Transformation](https://mlsanity.com/paper/2304.14698/) (2023)
- [FedHQ: Hybrid Runtime Quantization for Federated Learning](https://mlsanity.com/paper/2505.11982/) (2025)
- [e-boost: Boosted E-Graph Extraction with Adaptive Heuristics and Exact Solving](https://mlsanity.com/paper/2508.13020/) (2025)
- [AGO: Boosting Mobile AI Inference Performance by Removing Constraints on Graph Optimization](https://mlsanity.com/paper/2212.01005/) (2022)
- [Canvas: End-to-End Kernel Architecture Search in Neural Networks](https://mlsanity.com/paper/2304.07741/) (2023)
- [Nautilus: An Auto-Scheduling Tensor Compiler for Efficient Tiled GPU Kernels](https://mlsanity.com/paper/2604.14825/) (2026)
- [Prism: Symbolic Superoptimization of Tensor Programs](https://mlsanity.com/paper/2604.15272/) (2026)
- [ALT: Boosting Deep Learning Performance by Breaking the Wall between Graph and Operator Level Optimizations](https://mlsanity.com/paper/2210.12415/) (2022)
- [Verify Distributed Deep Learning Model Implementation Refinement with Iterative Relation Inference](https://mlsanity.com/paper/2508.09505/) (2025)
- [Verifying Computational Graphs in Production-Grade Distributed Machine Learning Frameworks](https://mlsanity.com/paper/2509.10694/) (2025)
- [nncase: An End-to-End Compiler for Efficient LLM Deployment on Heterogeneous Storage Architectures](https://mlsanity.com/paper/2512.21571/) (2025)
- [VTC: DNN Compilation with Virtual Tensors for Data Movement Elimination](https://mlsanity.com/paper/2604.09558/) (2026)
- [LLM-Guided Strategy Synthesis for Scalable Equality Saturation](https://mlsanity.com/paper/2604.17364/) (2026)
- [Axon: A Synthesizing Superoptimizer for Tensor Programs](https://mlsanity.com/paper/2606.26344/) (2026)
- [Meganeura: Portable GPU Training and Inference through Vulkan and Metal](https://mlsanity.com/paper/2608.01563/) (2026)

## Abstract (arXiv)

One of the major optimizations employed in deep learning frameworks is graph rewriting. Production frameworks rely on heuristics to decide if rewrite rules should be applied and in which order. Prior research has shown that one can discover more optimal tensor computation graphs if we search for a better sequence of substitutions instead of relying on heuristics. However, we observe that existing approaches for tensor graph superoptimization both in production and research frameworks apply substitutions in a sequential manner. Such sequential search methods are sensitive to the order in which the substitutions are applied and often only explore a small fragment of the exponential space of equivalent graphs. This paper presents a novel technique for tensor graph superoptimization that employs equality saturation to apply all possible substitutions at once. We show that our approach can find optimized graphs with up to 16% speedup over state-of-the-art, while spending on average 48x less time optimizing.