💻 computer science

Answer Set Programming for Egg Extraction and More

This paper demonstrates how to optimize Answer Set Programming (ASP) for efficient e-graph term extraction, showing it can match or exceed traditional ILP-based methods and exploring the potential of integrating ASP with Datalog to enhance e-graph capabilities.

Original authors: Ziyi Yang, Ilya Sergey

Published 2026-06-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ziyi Yang, Ilya Sergey

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Finding the Best Recipe in a Giant Library

Imagine you have a massive library of recipes (these are called e-graphs in the paper). In this library, many different recipes actually result in the exact same dish. For example, "2 + 2" and "1 + 3" are different ways of writing the same number.

The goal of E-Graph Extraction is to look at this messy library and pick out the single, most efficient recipe to make a specific dish. The problem is that the library is huge, and finding the perfect (cheapest/fastest) recipe is a mathematically difficult puzzle (known as NP-hard).

Three years ago, a programmer named Philip Zucker tried to use a special logic tool called ASP (Answer Set Programming) to solve this puzzle. It was a clever idea because ASP is great at logic, but it was too slow to be useful on big problems.

This paper is like a "remix" of that old idea. The authors (Ziyi Yang and Ilya Sergey) say, "We found the right settings and a few tricks to make ASP fast and powerful again."

The Two Ways to Look for the Recipe

The paper compares two different strategies for finding the best recipe:

1. The Bottom-Up Approach (The "Build from Scratch" Method)

How it works: You start with the tiny ingredients (like flour and eggs) and build up to the final dish. You check every possible way to combine ingredients to see which path is cheapest.
The Problem: In the old ASP version, this was like trying to build a skyscraper by testing every single brick combination. It took forever.
The Fix: The authors realized that if you use a specific "optimization engine" inside the ASP tool (called UNSAT-core), it becomes much faster. It's like having a super-efficient foreman who instantly knows which brick combinations are useless and throws them away before you even try to lay them.

2. The Top-Down Approach (The "Order from the Top" Method)

How it works: You start with the final dish you want (e.g., "I need a cake") and work backward. You ask, "What do I need to make a cake? Flour and eggs. What do I need for flour? Wheat..."
The Problem: This method is usually faster, but it has a dangerous flaw. Sometimes, the recipe instructions loop back on themselves (e.g., "To make flour, you need a cake"). This creates a cycle (a loop), which is impossible in real life. The old ASP version couldn't easily stop these loops from happening.
The Fix: The authors used a special "custom rule" (called a propagator) inside the ASP tool. Think of this as a bouncer at a club. If the recipe tries to create a loop (a cycle), the bouncer immediately kicks it out. This allows the Top-Down method to be fast and correct.

The Results: Who Won the Race?

The authors tested these methods against other tools using a standard set of puzzles (called the "extraction-gym").

The Old Way (Naïve ILP): This was like using a standard calculator. It was slow and often missed the best solution.
The New ASP (Top-Down with the "Bouncer"): This was the winner. It found high-quality solutions (the cheapest recipes) very quickly. It was a great balance between speed and accuracy.
The New ASP (Bottom-Up with the "Foreman"): This was also very good. Interestingly, on a few very specific, weirdly complex puzzles, this method actually found better solutions than the Top-Down method. It seems that sometimes, starting from the bottom is better, but usually, starting from the top is faster.

The Verdict: By tweaking the settings and adding a "bouncer" to stop loops, they made ASP a serious competitor. It's now fast enough to be useful in real-world software optimization.

The Future: Mixing Two Superpowers

The paper ends with a vision for the future. They compare two powerful tools:

Datalog: Great at organizing information and finding all possible connections (like a librarian who knows every book in the library).
ASP: Great at making hard choices and finding the absolute best option (like a chef who picks the perfect recipe).

The "Better Together" Idea:
Currently, these tools work in two separate steps: First, the librarian organizes the books (Datalog), and then the chef picks a recipe (ASP).
The authors suggest merging them. Imagine a chef who is also a librarian. As they are cooking, they can instantly ask the library, "Is there a faster way to chop these onions?" and the library instantly updates the recipe.

They propose a new system where the "search" for the best solution and the "organization" of the possibilities happen at the same time. This could make computer programs that optimize code (like making software run faster) much smarter and more efficient.

Summary in One Sentence

The authors took a slow, promising logic tool (ASP), gave it a "bouncer" to stop bad loops and a "foreman" to speed up calculations, and proved it can now find the best solutions for complex computer problems faster than before, while also dreaming up a way to mix it with other tools for even greater power.

Technical Summary: Answer Set Programming for Egg Extraction and More

Problem Statement

Term extraction in e-graphs is a critical component of equality saturation systems, aiming to find the lowest-cost term representation from a set of equivalent terms. This problem is known to be NP-hard. While Answer Set Programming (ASP) offers a natural, declarative modeling approach for e-graph terms, initial attempts (specifically Philip Zucker's formulation [10]) yielded unconvincing results regarding scalability. The primary challenge identified is that while ASP can compactly model the acyclicity constraints required for Directed Acyclic Graph (DAG) extraction via stable-model semantics, naive encodings struggle with large instances, often failing to solve within practical time limits compared to Integer Linear Programming (ILP) baselines.

Methodology

The authors revisit the e-graph extraction task using a solver-oriented ASP workflow, comparing two primary encoding strategies and leveraging specific solver features to overcome scalability barriers.

1. Encoding Strategies

Bottom-Up Encoding (Naïve): Based on Zucker's original work, this approach uses "support-style" choice rules. An enode is selected only if its child e-classes are selected. Cycles are avoided implicitly through the "foundedness" property of stable models (no self-supporting selection). While expressive, this encoding was found to be inefficient on large problems (e.g., the lambda function repeat instance).
Top-Down Encoding (Demand-Driven): This alternative marks root classes as "needed" and selects exactly one enode per needed class, propagating the "need" to child classes. While logically sound for tree extraction, this approach fails to inherently prevent cycles in e-graphs, leading to incorrect DAG extraction.

2. Solver-Oriented Solutions

To address the performance and correctness issues, the authors employed specific techniques within the Clingo solver:

UNSAT-Core Optimization: For the bottom-up encoding, the authors utilized Clingo's UNSAT-core (usc) based optimization. By enabling parallel solving (specifically using a second thread for the optimization process), the ASP encoding became competitive with optimized ILP-based exact DAG extraction, solving instances that previously timed out.
Custom Propagators for Top-Down: To fix the cycle detection issue in the top-down encoding without incurring the $O(n^3)$ cost of explicit transitive closure (which is too heavy for large Strongly Connected Components), the authors utilized Clingo's custom propagators. This allows for imperative procedures (specifically SCC elimination) to run outside the ASP solver's core logic, effectively handling reachability constraints efficiently.

Key Contributions

Solver Configuration for ASP: The paper demonstrates that with the correct solver configuration (specifically UNSAT-core optimization and parallel solving), ASP can achieve practical scalability for e-graph extraction, challenging the notion that it is inherently too slow for this NP-hard task.
Hybrid Top-Down Approach: The authors propose a top-down encoding augmented with a custom propagator for cycle detection. This approach balances solution quality and runtime, offering a viable alternative to the bottom-up method.
Empirical Benchmarking: The study evaluates these ASP encodings against the extraction-gym baselines (including faster-greedy-dag, naïve ILP, and optimized ILP variants) across three suites: babble, herbie, and rover.
Future Integration Agenda: The paper outlines a roadmap for "ASP modulo equivalence," proposing a deeper integration where ASP and e-graphs (specifically egg and Datalog) work together. This includes using ASP's CDCL engine to prune saturation and using e-graphs to provide congruence closure propagation during ASP search.

Results

Solution Quality: The top-down ASP encoding (asp-td) generally provides a good balance, preserving solution quality while remaining competitive in runtime.
Runtime Performance:
- The bottom-up ASP encoding (asp-bu) with UNSAT-core optimization is competitive with the latest ILP-based exact extraction.
- The top-down encoding (asp-td) is generally faster overall than the bottom-up approach.
- However, the bottom-up approach found strictly better DAG costs in three outlier instances (characterized by a high number of roots, ~400–1400), suggesting that search direction is case-sensitive.
- Naïve ILP baselines were found to be non-competitive. Optimized ILP variants were very fast on specific suites (e.g., rover) due to non-solver engineering choices (e.g., zero-cost simplifications), suggesting similar engineering hooks are feasible for ASP via Clingo's API.
Limitations: Current ASP encodings are limited to integer costs due to Clingo's weak constraint implementation. Parallel solving (4 threads) improved suboptimal results but did not yield better optimal results in the experiments.

Significance and Claims

The paper claims that the "two-phase" approach of equality saturation followed by extraction is effective and efficient when paired with the right ASP encoding and solver configuration. It positions ASP not just as a post-hoc extraction tool, but as a potential component for a richer, cost-aware saturation pipeline.

The authors emphasize that while the initial attempts at ASP for this task were discouraging, the barrier was largely due to solver configuration rather than the encoding itself. By leveraging modern solver features like custom propagators and UNSAT-core optimization, ASP can serve as a powerful "better together" partner to Datalog-based e-graphs, offering global optimization and constraint handling capabilities that complement the compact representation of e-graphs. The work opens an agenda for exploring "ASP modulo equivalence," where the two frameworks mutually enhance each other's search and pruning capabilities.