Answer Set Programming for Egg Extraction and More
summary
Answer set programming encodes e-graphs as facts and finds low-cost extractions; a naive ASP encoding running with clingo and a core-guided (answer-core) search matches and often beats an optimized ILP baseline on extraction-gym within a 10s timeout, producing several extra optimal terms on complex instances. Two encodings—bottom-up and top-down—trade pruning versus many-root overhead, and expensive grounding is mitigated by an ASP propagator for acyclicity (model-checking outside grounding), giving practical, competitive extraction performance.
AI-written summary · about
chapters (11)
- 0:00ASP for e-graph extraction
- 0:50Optimal terms from e-graphs
- 3:00Answer Set Programming background
- 7:34Prior ASP for e-graph extraction
- 8:56Bottom-up ASP approach
- 10:41Top-down ASP approach
- 12:27ASP vs greedy and ILP
- 14:57Solver performance outliers
- 15:39ASP and e-graphs future
- 18:52Takeaways and closing
- 19:59Q&A
related talks
26mModelling the Outlier Detection Problem in QASP
16mJust-in-Time Learning for Bottom-Up Enumerative Synthesis
39mUnlocking reasoning in Large language models
10mSATisfying answers to difficult questions!
06mCloud-Native GraphRAG: AI’s Logical Edge
30mBuilding a HybridRAG Document Question-Answering System
14mGeneralizable Synthesis Through Unification
26mThe geometry of Intelligence in a Large Question-Answering System