ESACO: Fast E-Graph Extraction via Orchestrated Simulated Annealing-based Local Search and Ant Colony Optimization-based Global Search

Equality graphs (E-graphs) offer a compact representation for vast sets of equivalent implementations, proving invaluable in hardware synthesis and program optimization. Nevertheless, extracting the optimal implementation from an e-graph constitutes an NP-hard challenge. Current extraction methods face critical limitations: heuristic-based approaches fail to produce high-quality solutions, GPU-accelerated techniques lack determinism and demand excessive memory, exact ILP methods struggle with scalability, and specialized solvers only function for particular e-graph types. To address this, we present ESACO, a novel deterministic framework that rapidly and consistently converges to high-quality solutions across diverse benchmarks by effectively combining Simulated Annealing (SA) for local refinement with Ant Colony Optimization (ACO) for global search. First, we develop a synergistic hybrid-heuristic framework that orchestrates complementary search paradigms, harmonizing ACO’s global exploration capabilities with SA’s targeted local exploitation mechanisms. Second, we introduce an SA-based local search method that employs novel rip-up and repair moves for efficiently refining promising solutions. Third, we propose an ACO-based global search algorithm incorporating strategic restart mechanisms to effectively explore the complex solution space while escaping local optima. Experimental results demonstrate that ESACO achieves up to 42× speedup using a single thread compared to state-of-the-art GPU-accelerated methods while maintaining or improving solution quality.