{"id":"7710b3e2-1a79-454f-86bf-6fab6b7712bb","arxiv_id":"2606.10644","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Answer set programming encodings for e-graph extraction match ILP efficiency on benchmarks and recover additional optimal solutions on complex instances.","lead":"The paper shows how to encode e-graph term extraction as an answer set program that runs as fast as optimized ILP solvers and sometimes finds better solutions than prior methods. A smart generalist might read it to see how logic programming can be made practical for hard optimization tasks inside compilers and program synthesizers.","discovery_kind":"new_application","skeptic_critique":{"model":"grok-4.3","headline":"Claim of comparability rests on extraction-gym results whose representativeness for real compiler e-graphs is untested.","rationale":"The reader's weakest_assumption directly identifies the gap between gym-scale results and the intended application domain; no stronger internal inconsistency or encoding flaw is visible from the given material.","tokens_in":1622,"tokens_out":302,"duration_ms":29305,"concrete_test":"Take the largest extraction-gym instances that ASP solved, scale them by a factor of 5–10 in e-node count while preserving the same cost model, re-encode and re-solve with the identical ASP program and solver settings, and check whether optimal solutions are still obtained within the same timeout used for the gym results.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim asserts that a naive ASP encoding matches well-optimised ILP extraction on extraction-gym instances and recovers additional optimal solutions on complex cases. This claim is internally about those specific benchmarks. However, the paper immediately pivots to an agenda of integrating ASP with egg for compiler workloads, where e-graph sizes, density, and cost functions differ. Nothing in the presented results demonstrates that the same encoding and off-the-shelf solver will remain competitive once instance size grows by the factors typical in production compilers (e.g., tens of thousands of e-nodes). The scaling assumption is therefore the least secure link between the reported numbers and the broader utility the authors themselves advertise.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","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.","tokens_in":1754,"tokens_out":469,"duration_ms":22421,"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":[{"comment":"§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.","section":"§4"},{"comment":"§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.","section":"§6"},{"comment":"§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.","section":"§3"}],"minor_comments":[{"comment":"Abstract: The LaTeX rendering of 'na\"ive' should be corrected to 'naive'.","section":"Abstract"},{"comment":"The manuscript would benefit from an explicit list of the extraction-gym instances used and a pointer to the ASP source files for reproducibility.","section":null}],"recommendation":"major_revision","confidential_remarks":"The work reads as an early exploration rather than a finished study; it may be better suited to a workshop or short paper track than a full journal article until the empirical section is expanded."},"author_rebuttal":{"model":"grok-4.3","summary":"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.","responses":[{"response":"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_made":"yes","referee_comment":"[§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."},{"response":"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_made":"partial","referee_comment":"[§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."},{"response":"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_made":"yes","referee_comment":"[§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."}],"tokens_in":1237,"tokens_out":507,"duration_ms":22770,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main point is that a straightforward ASP encoding now handles e-graph extraction at roughly the same speed as the tuned ILP solver in extraction-gym and turns up a few additional optimal solutions on the harder instances.\n\nThey improve on the earlier Zucker attempt by working out the modeling details that let the solver finish in reasonable time. The head-to-head numbers against extraction-gym give the claim some grounding, and the extra optima are concrete evidence that the approach can be useful rather than just equivalent.\n\nThe soft spot is the scaling step. All the reported results stay inside the extraction-gym suite. The paper then shifts to an agenda of pairing ASP with egg for actual compiler workloads, yet supplies no data on what happens when e-node counts grow by the factors common in production optimizers. The assumption that the off-the-shelf solver and encoding will stay competitive without further tuning is the part that still needs checking.\n\nThis is for people already working on e-graph extraction or looking for solver alternatives inside program optimizers. A reader who wants to see a working encoding plus benchmark numbers will find something usable here.\n\nIt is worth sending to peer review. The comparison is real and the extra optima are verifiable, even if the compiler-scale claim will need more evidence.","headline":"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.","tokens_in":2202,"tokens_out":338,"would_cite":false,"duration_ms":20689,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"A naive ASP encoding for e-graph term extraction matches the efficiency of optimized ILP methods and finds additional optimal solutions on complex instances.","keywords":["answer set programming","e-graph extraction","term extraction","ILP comparison","Datalog integration","egg","compiler optimization","DAG extraction"],"falsifier":"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.","tokens_in":2522,"feed_emoji":"","tokens_out":577,"duration_ms":18777,"temperature":0.7,"pith_summary":"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.","feed_headline":"ASP encoding rivals ILP for e-graph term extraction","feed_subtitle":"Naive approach matches optimized ILP and recovers extra optima on complex instances","key_machinery":"ASP encoding that directly models e-graph terms and the extraction objective as answer-set constraints.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["ASP matches ILP on e-graph extraction","Naive ASP rivals optimized ILP on e-graphs","ASP recovers extra optima on complex instances","ASP encoding rivals ILP term extraction efficiency","Naive ASP matches ILP e-graph optima discovery"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["ASP matches ILP on e-graph extraction","Naive ASP rivals optimized ILP on e-graphs","ASP recovers extra optima on complex instances","ASP encoding rivals ILP term extraction efficiency","Naive ASP matches ILP e-graph optima discovery"]},"model":"grok-4.3","cost_usd":0.005381,"raw_usage":{"total_tokens":2527,"prompt_tokens":534,"num_sources_used":0,"completion_tokens":60,"cost_in_usd_ticks":53812000,"prompt_tokens_details":{"text_tokens":534,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1933,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":534,"tokens_out":60,"duration_ms":17920,"temperature":1.0,"reasoning_tokens":1933,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-27T11:03:42.007301+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"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.","supporting_citations":[],"review_version":1}