# MCTS-GEB: Monte Carlo Tree Search is a Good E-graph Builder

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 15 references that are in the map.
- First posted on arXiv 8 Mar 2023.

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

- [Ray: A Distributed Framework for Emerging AI Applications](https://mlsanity.com/paper/1712.05889/) (2017)
- [Monte Carlo Tree Search: A Review of Recent Modifications and Applications](https://mlsanity.com/paper/2103.04931/) (2021)
- [Navigating to the Best Policy in Markov Decision Processes](https://mlsanity.com/paper/2106.02847/) (2021)
- [Equality Saturation for Tensor Graph Superoptimization](https://mlsanity.com/paper/2101.01332/) (2021)
- [Watch the Unobserved: A Simple Approach to Parallelizing Monte Carlo Tree Search](https://mlsanity.com/paper/1810.11755/) (2018)
- [SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra](https://mlsanity.com/paper/2002.07951/) (2020)

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

- [Learning Evolving Tools for Large Language Models](https://mlsanity.com/paper/2410.06617/) (2024)
- [Optimizing Tensor Computation Graphs with Equality Saturation and Monte Carlo Tree Search](https://mlsanity.com/paper/2410.05534/) (2024)
- [Automated Strategy Invention for Confluence of Term Rewrite Systems](https://mlsanity.com/paper/2411.06409/) (2024)
- [Verifying Computational Graphs in Production-Grade Distributed Machine Learning Frameworks](https://mlsanity.com/paper/2509.10694/) (2025)
- [LLM-Guided Strategy Synthesis for Scalable Equality Saturation](https://mlsanity.com/paper/2604.17364/) (2026)

## Abstract (arXiv)

Rewrite systems [6, 10, 12] have been widely employing equality saturation [9], which is an optimisation methodology that uses a saturated e-graph to represent all possible sequences of rewrite simultaneously, and then extracts the optimal one. As such, optimal results can be achieved by avoiding the phase-ordering problem. However, we observe that when the e-graph is not saturated, it cannot represent all possible rewrite opportunities and therefore the phase-ordering problem is re-introduced during the construction phase of the e-graph. To address this problem, we propose MCTS-GEB, a domain-general rewrite system that applies reinforcement learning (RL) to e-graph construction. At its core, MCTS-GEB uses a Monte Carlo Tree Search (MCTS) [3] to efficiently plan for the optimal e-graph construction, and therefore it can effectively eliminate the phase-ordering problem at the construction phase and achieve better performance within a reasonable time. Evaluation in two different domains shows MCTS-GEB can outperform the state-of-the-art rewrite systems by up to 49x, while the optimisation can generally take less than an hour, indicating MCTS-GEB is a promising building block for the future generation of rewrite systems.