# e-boost: Boosted E-Graph Extraction with Adaptive Heuristics and Exact Solving

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 49 references that are in the map.
- First posted on arXiv 18 Aug 2025.

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

- [Equality Saturation for Tensor Graph Superoptimization](https://mlsanity.com/paper/2101.01332/) (2021)
- [Gamora: Graph Learning based Symbolic Reasoning for Large-Scale Boolean Networks](https://mlsanity.com/paper/2303.08256/) (2023)
- [babble: Learning Better Abstractions with E-Graphs and Anti-Unification](https://mlsanity.com/paper/2212.04596/) (2022)
- [FlowTune: End-to-end Automatic Logic Optimization Exploration via Domain-specific Multi-armed Bandit](https://mlsanity.com/paper/2202.07721/) (2022)
- [Combinatorial Register Allocation and Instruction Scheduling](https://mlsanity.com/paper/1804.02452/) (2018)
- [Pure Tensor Program Rewriting via Access Patterns (Representation Pearl)](https://mlsanity.com/paper/2105.09377/) (2021)
- [RESPECT: Reinforcement Learning based Edge Scheduling on Pipelined Coral Edge TPUs](https://mlsanity.com/paper/2304.04716/) (2023)
- [E-Syn: E-Graph Rewriting with Technology-Aware Cost Functions for Logic Synthesis](https://mlsanity.com/paper/2403.14242/) (2024)
- [Differentiable Combinatorial Scheduling at Scale](https://mlsanity.com/paper/2406.06593/) (2024)
- [Automating Constraint-Aware Datapath Optimization using E-Graphs](https://mlsanity.com/paper/2303.01839/) (2023)
- [DAG-aware Synthesis Orchestration](https://mlsanity.com/paper/2310.07846/) (2023)
- [Automatic Datapath Optimization using E-Graphs](https://mlsanity.com/paper/2204.11478/) (2022)
- [Better Together: Unifying Datalog and Equality Saturation](https://mlsanity.com/paper/2304.04332/) (2023)
- [Accelerating Exact Combinatorial Optimization via RL-based Initialization -- A Case Study in Scheduling](https://mlsanity.com/paper/2308.11652/) (2023)
- [MapTune: Advancing ASIC Technology Mapping via Reinforcement Learning Guided Library Tuning](https://mlsanity.com/paper/2407.18110/) (2024)
- [Small Proofs from Congruence Closure](https://mlsanity.com/paper/2209.03398/) (2022)
- [Datapath Verification via Word-Level E-Graph Rewriting](https://mlsanity.com/paper/2308.00431/) (2023)
- [BoolE: Exact Symbolic Reasoning via Boolean Equality Saturation](https://mlsanity.com/paper/2504.05577/) (2025)
- [E-morphic: Scalable Equality Saturation for Structural Exploration in Logic Synthesis](https://mlsanity.com/paper/2504.11574/) (2025)
- [HEC: Equivalence Verification Checking for Code Transformation via Equality Saturation](https://mlsanity.com/paper/2506.02290/) (2025)
- [SEER: Super-Optimization Explorer for HLS using E-graph Rewriting with MLIR](https://mlsanity.com/paper/2308.07654/) (2023)

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

- [Magellan: Autonomous Discovery of Novel Compiler Optimization Heuristics with AlphaEvolve](https://mlsanity.com/paper/2601.21096/) (2026)
- [LLM-Guided Strategy Synthesis for Scalable Equality Saturation](https://mlsanity.com/paper/2604.17364/) (2026)

## Abstract (arXiv)

E-graphs have attracted growing interest in many fields, particularly in logic synthesis and formal verification. E-graph extraction is a challenging NP-hard combinatorial optimization problem. It requires identifying optimal terms from exponentially many equivalent expressions, serving as the primary performance bottleneck in e-graph based optimization tasks. However, traditional extraction methods face a critical trade-off: heuristic approaches offer speed but sacrifice optimality, while exact methods provide optimal solutions but face prohibitive computational costs on practical problems. We present e-boost, a novel framework that bridges this gap through three key innovations: (1) parallelized heuristic extraction that leverages weak data dependence to compute DAG costs concurrently, enabling efficient multi-threaded performance without sacrificing extraction quality; (2) adaptive search space pruning that employs a parameterized threshold mechanism to retain only promising candidates, dramatically reducing the solution space while preserving near-optimal solutions; and (3) initialized exact solving that formulates the reduced problem as an Integer Linear Program with warm-start capabilities, guiding solvers toward high-quality solutions faster. Across the diverse benchmarks in formal verification and logic synthesis fields, e-boost demonstrates 558x runtime speedup over traditional exact approaches (ILP) and 19.04% performance improvement over the state-of-the-art extraction framework (SmoothE). In realistic logic synthesis tasks, e-boost produces 7.6% and 8.1% area improvements compared to conventional synthesis tools with two different technology mapping libraries. e-boost is available at https://github.com/Yu-Maryland/e-boost.