{"ID":2881185,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.13020","arxiv_id":"2508.13020","title":"e-boost: Boosted E-Graph Extraction with Adaptive Heuristics and Exact Solving","abstract":"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.","short_abstract":"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 bottl...","url_abs":"https://arxiv.org/abs/2508.13020","url_pdf":"https://arxiv.org/pdf/2508.13020v2","authors":"[\"Jiaqi Yin\",\"Zhan Song\",\"Chen Chen\",\"Yaohui Cai\",\"Zhiru Zhang\",\"Cunxi Yu\"]","published":"2025-08-18T15:38:12Z","proceeding":"cs.AI","tasks":"[\"cs.AI\",\"cs.AR\"]","methods":"[]","has_code":false,"code_links":[{"ID":610781,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_id":2881185,"paper_url":"https://arxiv.org/abs/2508.13020","paper_title":"e-boost: Boosted E-Graph Extraction with Adaptive Heuristics and Exact Solving","repo_url":"https://github.com/Yu-Maryland/e-boost","is_official":false,"mentioned_in_paper":false,"mentioned_in_github":true,"github_stars":0}]}