E-boost: Boosted E-Graph Extraction with Adaptive Heuristics and Exact Solving (ICCAD'25; Best Paper Nomination)

January 7, 2026 · View on GitHub

arXiv

E-graph extraction is a challenging NP-hard optimization problem that serves as the primary bottleneck in e-graph based applications. Traditional methods face a critical trade-off between speed and optimality.

E-boost bridges this gap through three key innovations: (1) parallelized heuristic extraction for efficient multi-threaded performance, (2) adaptive search space pruning to reduce solution space while preserving quality, and (3) initialized exact solving with warm-start ILP capabilities for faster convergence to optimal solutions, as described in our ICCAD'25 paper.

📄 Paper

If you use e-boost in your research, please cite our paper:

@article{yin2025boost,
  title={e-boost: Boosted E-Graph Extraction with Adaptive Heuristics and Exact Solving},
  author={Yin, Jiaqi and Song, Zhan and Chen, Chen and Cai, Yaohui and Zhang, Zhiru and Yu, Cunxi},
  journal={arXiv preprint arXiv:2508.13020},
  year={2025}
}

🚀 Quick Start

Overview

E-boost consists of several key components:

  1. Parallelized Heuristic Extraction: Multi-threaded DAG cost computation with optimized data structures
  2. Adaptive Search Space Pruning: Parameterized threshold mechanism for candidate selection
  3. Initialized Exact Solving: ILP formulation with warm-start capabilities
  4. Solver Backends: Support for Gurobi, CPLEX, and CP-SAT solvers
  5. Benchmark Suite: Comprehensive test datasets for evaluation

📋 Prerequisites

System Requirements

  • Operating System: Linux (tested on Linux x86_64)
  • Compiler: GCC with C++17 support
  • Build Tool: Make
  • Language Runtime: Rust (for E-graph components)

Required Software

  • Rust: Latest stable version with Cargo
  • At least one solver:
    • Gurobi Optimizer (commercial/academic license)
    • IBM CPLEX (commercial/academic license)
    • Google OR-Tools (free, includes CP-SAT)

⚙️ Installation & Environment Setup

1. Install Required Rust Environment

Make sure you have Rust installed (recommended: stable toolchain):

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

After installation, ensure cargo and rustc are in your PATH:

rustc --version
cargo --version

2. Build E-boost

Once Rust is installed, build e-boost:

cargo build --release

3. Solver Setup

Gurobi Setup

  1. Download Gurobi from gurobi.com
  2. Extract the package: 
    tar -xzf gurobi12.0.1_linux64.tar.gz
  3. Set environment variables: 
    export GUROBI_HOME=/path/to/gurobi1201/linux64
export PATH="${PATH}:${GUROBI_HOME}/bin"
export LD_LIBRARY_PATH="${LD_LIBRARY_PATH}:${GUROBI_HOME}/lib"
  4. Install license file (gurobi.lic) in $GUROBI_HOME/ or $HOME/

CPLEX Setup

  1. Download IBM CPLEX Studio from IBM website
  2. Install CPLEX: 
    chmod +x cplex_studio2211.linux_x86_64.bin
./cplex_studio2211.linux_x86_64.bin
  3. Set environment variables: 
    export CPLEX_HOME=/path/to/cplex
export CONCERT_HOME=/path/to/concert

OR-Tools Setup (CP-SAT)

  1. Download OR-Tools: 
    wget https://github.com/google/or-tools/releases/download/v9.7/or-tools_amd64_ubuntu-22.04_cpp_v9.7.2996.tar.gz
tar -xzf or-tools_amd64_ubuntu-22.04_cpp_v9.7.2996.tar.gz
  2. Set environment variables: 
    export ORTOOLS_HOME=/path/to/or-tools
export LD_LIBRARY_PATH="${LD_LIBRARY_PATH}:${ORTOOLS_HOME}/lib"

4. Build the Project

Build Solvers

# Build Gurobi solver
cd gurobi/
g++ -std=c++17 main.cpp -o gurobi_solver -I$GUROBI_HOME/include -L$GUROBI_HOME/lib -lgurobi_c++ -lgurobi120 -lstdc++fs

# Build CPLEX solver  
cd ../cplex/
g++ -std=c++17 main.cpp -o cplex_solver \
    -I$CONCERT_HOME/include -I$CPLEX_HOME/include \
    -L$CPLEX_HOME/lib/x86-64_linux/static_pic \
    -L$CONCERT_HOME/lib/x86-64_linux/static_pic \
    -lilocplex -lcplex -lconcert -lpthread -ldl

# Build CP-SAT solver
cd ../cpsat/
g++ -std=c++17 main.cpp -I./include \
    -L$ORTOOLS_HOME/lib -Wl,-rpath=$ORTOOLS_HOME/lib \
    -lortools -o cpsat -O3

Build E-syn2 Components

cd E-syn2/
make

🧪 Benchmarks

The benchmark/ directory contains test datasets organized by source:

  • BoolE/: BoolE benchmarks

    • mul32.json, mul32_map.json: 32-bit CSA multiplier
    • mul48.json, mul48_map.json: 48-bit CSA multiplier

  • E-morphic/: E-morphic benchmarks

    • adder.json: Adder circuit
    • log2.json: Logarithm computation
    • sin.json: Sine function approximation

  • E-syn/: E-Syn benchmarks

    • c2670.json: ISCAS benchmark circuit
    • qdiv.json: Quotient division circuit

  • SmoothE/: SmoothE benchmarks

    • direct_recexpr_root_18.json: Direct recursive expression
    • fir_8_tap_7iteration_egraph.json: FIR filter
    • large_mul2048.json: Large multiplier
    • nasneta.json: Neural architecture search
    • vector_2d_conv_2x2_2x2_root_36.json: 2D convolution

Complete benchmarks

Note: some benchmark files (particularly the large BoolE datasets) are too large to host directly in this GitHub repository. The complete benchmark collection is hosted on Hugging Face and can be found here:

https://huggingface.co/datasets/SeaSkysz/eboost_dataset/tree/main

You can download individual files from that page, or load the dataset programmatically using the Hugging Face datasets library (for example, load_dataset("SeaSkysz/eboost_dataset")).

🔧 Usage

Running Benchmarks

E-boost provides flexible command-line options for different extraction scenarios. The basic command structure is:

cargo run -- --bound <threshold> --solver <solver> --timeout <seconds> --extractor <algorithm> --pre <mode> <benchmark_file>

Command-Line Parameters

  • --bound <value>: Threshold parameter for adaptive search space pruning (e.g., 1.25)

    • Values > 1.0 retain more candidates while increasing search space
    • Lower values (closer to 1.0) are more aggressive in pruning

  • --solver <name>: Choose optimization solver backend

    • gurobi: Commercial solver (requires license)
    • cplex: IBM CPLEX solver (requires license)
    • cpsat: Google OR-Tools CP-SAT (free)

  • --timeout <seconds>: Maximum execution time in seconds

  • --extractor <algorithm>: Heuristic extraction algorithm variant

    • faster-greedy-dag-mt1: Multi-threaded parallelized extraction (recommended)
    • faster-greedy-dag-mt2: Alternative multi-threaded variant
    • faster-greedy-dag: Single-threaded version

  • --pre <mode>: Preprocessing and execution mode (0-5)

    • 0: Solver only (skip LP generation)
    • 1: Generate LP file only, no warm start
    • 2: Generate LP file only, with warm start (default)
    • 3: Full run without warm start
    • 4: Full run with warm start (recommended for best results)
    • 5: Heuristic extraction only

Usage Examples

Basic optimization with warm start:

cargo run -- --bound 1.25 --solver gurobi --timeout 1800 --extractor faster-greedy-dag-mt1 --pre 4 benchmark/BoolE/mul32_map.json

Quick heuristic-only extraction:

cargo run -- --bound 1.25 --solver gurobi --timeout 300 --extractor faster-greedy-dag-mt1 --pre 5 benchmark/BoolE/mul32.json

Generate optimization files without solving:

cargo run -- --bound 1.50 --solver cplex --timeout 3600 --extractor faster-greedy-dag-mt1 --pre 2 benchmark/SmoothE/fir_8_tap_7iteration_egraph.json

Using free CP-SAT solver:

cargo run -- --bound 1.25 --solver cpsat --timeout 1800 --extractor faster-greedy-dag-mt1 --pre 4 benchmark/E-syn/c2670.json

🔧 Real-World Applications: E-syn2 Logic Synthesis Integration

Note: Make sure you have built e-boost using cargo build --release before using the E-syn2 integration.

E-boost demonstrates its practical impact through integration with E-syn2, a complete logic synthesis optimization workflow. This integration showcases how e-boost's optimal extraction capabilities significantly improve real-world circuit optimization tasks.

E-syn2 Scripts

process_test.sh

Automated batch processing script that runs optimization on all EQN files in the test directory.

Usage:

cd E-syn2/
./process_test.sh

Features:

  • Processes all .eqn files in the test/ directory
  • Tests multiple bounds (1, 1.05, 1.25, 1.50) and solvers
  • Compares original vs. optimized results
  • Generates comprehensive logs in logs/ directory
  • Provides progress tracking and runtime statistics

run_test.sh

Interactive script for single circuit optimization.

Usage:

cd E-syn2/
./run_test.sh

Integration Examples

Example 1: Basic Circuit Optimization

# First, ensure e-boost is built
cargo build --release

# Place your circuit in E-syn2/e-rewriter/circuit0.eqn
cd E-syn2/
cp test/adder.eqn e-rewriter/circuit0.eqn

# Run optimization with Gurobi, bound 1.25
echo -e "5\narea\nfaster-bottom-up\nnew\n1.25\ngurobi\n" | bash run_test.sh

Example 2: Batch Processing

# First, ensure e-boost is built
cargo build --release

# Process all test circuits with multiple configurations
cd E-syn2/
./process_test.sh

# Results will be in logs/ directory
ls logs/
# Output: # Output: adder/ bar/ c2670/ ... (one directory per circuit)

📧 Contact

For questions or feedback, please reach out to the authors listed in the paper or open an issue in this repository.

📜 License

This project is licensed under the MIT License.

Enjoy boosted E-graph extraction with e-boost!