Pith. sign in

REVIEW 3 major objections 2 minor 13 references

Answer Set Programming for Egg Extraction and More

T0 review · 3 major / 2 minor · reviewed 2026-06-27 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A naive ASP encoding for e-graph term extraction matches the efficiency of optimized ILP methods and finds additional optimal solutions on complex instances.

desk verdict They got a naive ASP encoding to match the ILP baseline on extraction-gym and recover extra optima on some cases, but the jump to real compiler e-graphs is untested. read the letter →

arxiv 2606.10644 v1 pith:YBR6LUIF submitted 2026-06-09 cs.PL cs.LO

Ziyi Yang , Ilya Sergey This is my paper
classification cs.PLcs.LO
keywords answersetprogramminge-graphextractiontermILPcomparisonDatalogintegrationeggcompileroptimizationDAG
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes that answer set programming can be made to work effectively for extracting terms from e-graphs, a task that is NP-hard. It shows through direct comparison that even a straightforward ASP encoding performs on par with a well-optimized ILP-based exact DAG extractor used in extraction-gym benchmarks. On more difficult instances the ASP method additionally recovers several optimal extractions that the ILP approach misses. The authors then outline a broader research direction of treating ASP as a more expressive form of Datalog that could be combined with existing e-graph tools.

What carries the argument

ASP encoding that directly models e-graph terms and the extraction objective as answer-set constraints.

What would settle it

Running the same naive ASP encoding on e-graphs drawn from production compiler workloads that exceed the size and complexity of the extraction-gym suite and measuring whether solution times remain competitive without any changes to the encoding or solver configuration.

Watch

Extended reading notes

Core claim

A naive ASP encoding for e-graph extraction achieves efficiency on par with well-optimized ILP-based DAG extraction and discovers several extra optimal extractions on complex instances.

Load-bearing premise

The chosen ASP solver and encoding will continue to scale to the sizes of e-graphs encountered in real compiler workloads without requiring solver-specific tuning or additional heuristics.

Editorial extensions

If this is right

  • ASP can serve as a practical alternative to ILP for exact optimal extraction from e-graphs.
  • The approach opens the possibility of treating ASP as a more powerful Datalog layer on top of egg.
  • Combined egg-plus-ASP systems could support richer reasoning over equality saturation results than current Datalog integrations allow.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the scaling assumption holds, ASP extraction could be embedded directly inside existing equality-saturation loops without external solver calls.
  • The extra optima found on complex instances suggest that ASP may expose different trade-offs between extraction cost and solution quality that ILP encodings miss.
  • A practical next step would be to measure wall-clock extraction time on representative compiler IRs rather than on synthetic benchmark graphs.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 2 minor

Summary. The paper claims that a naive ASP encoding for optimal term extraction from e-graphs achieves efficiency comparable to the well-optimized ILP baseline in the extraction-gym, recovers additional optimal solutions on complex instances, and motivates a broader agenda of using ASP as a more expressive Datalog layer alongside egg for compiler workloads.

Significance. If the empirical comparability holds and the approach scales, the work would supply a declarative, solver-based alternative to ILP extraction that could simplify encoding of complex cost functions and enable tighter integration between e-graph rewriting and logic programming in program optimizers.

major comments (3)
  1. [§4] §4 (Experimental Results): The central claim of comparability to ILP and discovery of extra optima is stated without any table of per-instance runtimes, costs, benchmark names, or e-graph sizes, so the evidence cannot be assessed or reproduced.
  2. [§6] §6 (Discussion): The manuscript pivots to an integration agenda for real compiler e-graphs, yet provides no scaling experiments, instance-size analysis, or argument addressing whether the naive encoding remains competitive when e-node counts grow by the factors typical in production workloads.
  3. [§3] §3 (ASP Encoding): The paper describes the encoding as 'naive' yet offers no formal definition or listing of the rules, making it impossible to judge whether hidden solver-specific tuning or modeling choices explain the reported performance.
minor comments (2)
  1. [Abstract] Abstract: The LaTeX rendering of 'na"ive' should be corrected to 'naive'.
  2. The manuscript would benefit from an explicit list of the extraction-gym instances used and a pointer to the ASP source files for reproducibility.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive feedback. We address each major comment below and will revise the manuscript to improve transparency and completeness of the presented evidence.

read point-by-point responses

  1. Referee: [§4] §4 (Experimental Results): The central claim of comparability to ILP and discovery of extra optima is stated without any table of per-instance runtimes, costs, benchmark names, or e-graph sizes, so the evidence cannot be assessed or reproduced.

    Authors: We agree that the experimental results section would benefit from greater detail. In the revised manuscript we will add one or more tables reporting, for each benchmark instance, the benchmark name, e-graph size (number of e-classes and e-nodes), runtime for both the ASP and ILP solvers, the cost of the extracted term, and whether the ASP encoding recovered an additional optimum. This will make the comparability claim and the discovery of extra optima directly verifiable. revision: yes

  2. Referee: [§6] §6 (Discussion): The manuscript pivots to an integration agenda for real compiler e-graphs, yet provides no scaling experiments, instance-size analysis, or argument addressing whether the naive encoding remains competitive when e-node counts grow by the factors typical in production workloads.

    Authors: The discussion section is prospective and does not contain scaling experiments on production-scale e-graphs. We will revise §6 to include a qualitative scaling argument based on the known complexity of the extraction problem and the performance characteristics of modern ASP solvers, together with references to observed e-graph sizes in the compiler literature. We acknowledge that new empirical scaling studies lie outside the scope of the present work, which focused on the extraction-gym suite; this limitation will be stated explicitly. revision: partial

  3. Referee: [§3] §3 (ASP Encoding): The paper describes the encoding as 'naive' yet offers no formal definition or listing of the rules, making it impossible to judge whether hidden solver-specific tuning or modeling choices explain the reported performance.

    Authors: We will expand §3 to present the complete set of ASP rules in a formal listing. The revised section will show the exact encoding used, making clear that it relies on standard Clingo features without undisclosed solver-specific tuning. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: empirical head-to-head on external extraction-gym baseline

full rationale

The paper's central claim is an empirical observation that a naive ASP encoding performs comparably to an existing ILP solver on the extraction-gym benchmark suite and recovers additional optima on some instances. This rests on running off-the-shelf solvers against an independently maintained external benchmark collection rather than any derivation, fitted parameter, or self-referential definition. No equations, ansatzes, uniqueness theorems, or self-citations appear as load-bearing steps in the provided text. The forward-looking discussion of ASP+Datalog integration with egg is presented as an open agenda, not as a derived result.

Assumptions & free parameters 0 free parameters · 0 assumptions · 0 invented entities

No free parameters, axioms, or invented entities are introduced; the contribution is an encoding of an existing NP-hard problem into an off-the-shelf ASP solver.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Answer Set Programming for Egg Extraction and More." pith.science (2026). https://pith.science/paper/YBR6LUIF

@misc{pith2026260610644,
  author       = {Pith},
  title        = {Pith review of: Answer Set Programming for Egg Extraction and More},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YBR6LUIF}},
  note         = {Machine review of arXiv:2606.10644}
}
read the original abstract

Three years ago, Philip Zucker posted an attempt to use answer set programming (ASP) for term extraction from e-graphs Although the task is NP-hard and ASP offers a natural modelling of e-graph terms, the initial attempt did not yield convincing results. From the aspect of practical ASP users, we first pinpoint the way to make ASP work and work well on the task of e-graph extraction. The initial results show the na\"ive ASP encoding is comparable on efficiency to the well-optimised ILP-based exact DAG extraction in the extraction-gym, and find several extra optimal extraction on the complex instances. This leads us to a further agenda: with the "better together of egg+Datalog", is there a better "better together" by having ASP as a more powerful Datalog? We discuss the potential benefit from each other.

Figures

Figures reproduced from arXiv: 2606.10644 by the authors.

Figure 1
Figure 1. A commutativity example (𝑥 + 𝑦 ≡ 𝑦 + 𝑥) shown as ASP facts and as an e-graph from [10]. Philip’s bottom-up encoding 1 % choose an enode only if all child classes are selected 2 {sel(E,I)} :- enode(E,I,_,_), selclass(Ec): child(E,I,Ec). 3 4 % selecting an enode selects its class 5 selclass(E) :- sel(E,_). 6 7 % at most one enode per class 8 :- enode(E,_,_,_), #count { I : sel(E,I) } > 1. 9 10 % optimize extraction co… view at source ↗
Figure 2
Figure 2. ASP encoding of egg extraction (left: bottom-up from [10], right: top-down ignoring DAG acyclicity). selected enodes, and require that none of the selected nodes are reachable from themselves. A direct encoding is like % Selected dependency graph sel_edge(E,Ec) :- selnode(I), enode(E,I,_), echild(I,Ec). % Transitive closure of selected dependency graph sel_reach(E,Ec) :- sel_edge(E,Ec). sel_reach(E,Ez) :- sel_reach(… view at source ↗
Figure 4
Figure 4. Geometric-mean runtime ratio by suite from pair comparisons to the top-down asp-td encoding. Values below 1 indicate faster than asp-td. remains modest (for example, geo-mean ratio is only about 0.96 on herbie), so asp-bu is still slower overall. This indicates that search direction is strongly case-sensitive. There are several limitations to the current evaluation. First, the weak constraints for optimisation in Cl… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

13 extracted references · 10 canonical work pages

  1. [1]

    Answer Set Programming for E-Graph DAG Extraction

    Philip Zucker. Answer Set Programming for E-Graph DAG Extraction

  2. [2]

    Amir Kafshdar Goharshady and Chun Kit Lam and Lionel Parreaux , title =. Proc. 2024 , url =. doi:10.1145/3689801 , timestamp =

    work page doi:10.1145/3689801 2024

  3. [3]

    2011 , url =

    Michael Stepp , title =. 2011 , url =

    2011

  4. [4]

    2025 , url =

    Jiaqi Yin and Zhan Song and Chen Chen and Yaohui Cai and Zhiru Zhang and Cunxi Yu , title =. 2025 , url =. doi:10.1109/ICCAD66269.2025.11240719 , timestamp =

    work page doi:10.1109/iccad66269.2025.11240719 2025

  5. [5]

    CoRR , volume =

    Glenn Sun and Yihong Zhang and Haobin Ni , title =. CoRR , volume =. 2024 , url =. doi:10.48550/ARXIV.2408.17042 , eprinttype =. 2408.17042 , timestamp =

    work page doi:10.48550/arxiv.2408.17042 2024

  6. [6]

    EGRAPHS 2023 workshop , year=

    Improving term extraction with acyclic constraints , author=. EGRAPHS 2023 workshop , year=

    2023

  7. [7]

    Unsatisfiability-based optimization in clasp , booktitle =

    Benjamin Andres and Benjamin Kaufmann and Oliver Matheis and Torsten Schaub , editor =. Unsatisfiability-based optimization in clasp , booktitle =. 2012 , url =. doi:10.4230/LIPICS.ICLP.2012.211 , timestamp =

    work page doi:10.4230/lipics.iclp.2012.211 2012

  8. [8]

    doi:10.2200/S00457ED1V01Y201211AIM019 , isbn =

    Martin Gebser and Roland Kaminski and Benjamin Kaufmann and Torsten Schaub , title =. doi:10.2200/S00457ED1V01Y201211AIM019 , isbn =

    work page doi:10.2200/s00457ed1v01y201211aim019

Show all 13 references
  1. [9]

    Theory Pract

    Roland Kaminski and Javier Romero and Torsten Schaub and Philipp Wanko , title =. Theory Pract. Log. Program. , volume =. 2023 , url =. doi:10.1017/S1471068421000508 , timestamp =

    2023 doi

  2. [10]

    Theory Pract

    Martin Gebser and Roland Kaminski and Benjamin Kaufmann and Torsten Schaub , title =. Theory Pract. Log. Program. , timestamp =. doi:10.1017/S1471068418000054 , number =

    doi

  3. [11]

    Theory Pract

    Martin Gebser and Benjamin Kaufmann and Torsten Schaub , title =. Theory Pract. Log. Program. , volume =. 2012 , url =. doi:10.1017/S1471068412000166 , timestamp =

    2012 doi

  4. [12]

    Yihong Zhang and Yisu Remy Wang and Oliver Flatt and David Cao and Philip Zucker and Eli Rosenthal and Zachary Tatlock and Max Willsey , title =. Proc. 2023 , url =. doi:10.1145/3591239 , timestamp =

    2023 doi

  5. [13]

    Guided Equality Saturation , journal =

    Thomas Koehler and Andr. Guided Equality Saturation , journal =. 2024 , url =. doi:10.1145/3632900 , timestamp =

    2024 doi

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.