> For the complete documentation index, see [llms.txt](https://neurosymbolicai.gitbook.io/neuro-symbolic-ai-in-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://neurosymbolicai.gitbook.io/neuro-symbolic-ai-in-practice/part-iii-core-approaches/chapter-4/4-2-neural-helps-symbolic/4-2-asp.md). # 4.2.3 Answer Set Programming **Definition:** Answer Set Programming (ASP) is a form of declarative logic programming under *stable model semantics*, designed specifically for non-monotonic reasoning — the ability to reason with defaults, exceptions, and incomplete information. While classical logic (and PDDL's Closed World Assumption, §3.1) assumes that anything not known to be true is false, real-world knowledge is full of exceptions: *birds fly* (except penguins), *employees work 9–5* (except on holidays), *medications are safe* (unless contraindicated). ASP handles these naturally through *negation as failure*: `flies(X) :- bird(X), not penguin(X)` — X flies if X is a bird and X has not been established to be a penguin. An ASP program consists of rules of the form: ``` head :- body_literals, not negative_literals. ``` The "answer sets" (stable models) are the consistent sets of beliefs that satisfy all rules. For planning, ASP is particularly useful for reasoning about constraints with exceptions and for encoding complex preference structures where the default applies but specific cases override it. ### NeurASP **NeurASP** (Yang et al., 2020) integrates ASP with neural networks by treating neural network outputs as *probabilistic observations* over ASP atoms. A neural component (e.g., a digit classifier) produces a probability distribution over categorical values; NeurASP treats these as probabilistic facts that seed ASP inference. ```prolog % Neural predicate: classifier assigns probabilities to digit classes nn(mnist_net, [X], Y, [0,1,...,9]) :: digit(X, Y). % ASP rule: two different images must show different digits (Sudoku constraint) :- digit(X, D), digit(Y, D), X != Y, same_row(X, Y). ``` The system is trained end-to-end: NeurASP inference propagates gradients back through the ASP reasoning into the neural network weights. The constraint `:- digit(X, D), digit(Y, D), X != Y, same_row(X, Y)` is an integrity constraint expressing that no two cells in the same row may have the same digit — an impossibility statement that drives the neural network toward predictions that produce globally consistent solutions. *Reference:* Yang, Zhun, et al. "NeurASP: Embracing Neural Networks into Answer Set Programming." *Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI)*, 2020. | Code: ### DeepStochLog and SLASH **DeepStochLog** (Winters et al., 2022) extends DeepProbLog to stochastic logic programs over ASP, enabling non-monotonic probabilistic reasoning with neural predicates — combining the expressiveness of ASP with the trainability of DeepProbLog. Where DeepProbLog handles probabilistic Horn clauses, DeepStochLog handles probabilistic programs with defaults and exceptions. **SLASH** (Skryagin et al., 2022) applies the NeurASP pattern to reinforcement learning: the agent's policy is expressed as an ASP program over symbolic state representations, with neural perception providing the grounding. SLASH achieves strong sample efficiency on structured environments by leveraging ASP's reasoning to constrain the action space — the agent does not need to learn that illegal moves are bad from reward signals alone, because the ASP program simply never proposes them. *References:* Winters, Thomas, et al. "DeepStochLog: Neural Stochastic Logic Programming." *Proceedings of AAAI*, 2022. Skryagin, Arseny, et al. "Neural-Probabilistic Answer Set Programming." *Proceedings of KR*, 2022. ### When to Use ASP vs. Other Symbolic Paradigms | Need | Recommended Tool | | ----------------------------------------------- | --------------------------- | | Monotonic constraints + differentiable training | LTN / DeepProbLog / Scallop | | Non-monotonic defaults and exceptions | NeurASP / DeepStochLog | | Learning from examples (crisp programs) | Popper / ILASP | | Hard constraints at inference time | Projection layers (§4.1.1) | | Combinatorial search (SAT, optimization) | NeuroSAT / SATNet | *** ## Summary of Section 4.2 The "Neural Helps Symbolic" pattern is the right choice when: * You have a symbolic framework that provides correctness guarantees you cannot compromise (safety-critical planning, formal verification, mathematical proof). * The symbolic framework's computational bottleneck is a function (heuristic estimation, policy selection, variable ordering) that can be learned from data. * Training data for the neural subroutine can be generated from the symbolic system itself (self-play, offline planning runs). The tradeoff: the neural subroutine must be trained and maintained. Distribution shift between training and deployment can degrade neural guidance quality, causing the symbolic system to fall back to its (correct but slower) default behavior. The symbolic fallback is exactly what makes this pattern safe: a bad neural heuristic means slower solving, not incorrect solving. *** ## References 1. Garcez, Artur d'Avila, and Luís C. Lamb. "Neurosymbolic AI: The 3rd Wave." *Artificial Intelligence Review* 56 (2023): 12387–12406. 2. Sheth, Amit, Kaushik Roy, and Manas Gaur. "Neurosymbolic Artificial Intelligence (Why, What, and How)." *IEEE Intelligent Systems* 38.3 (2023): 56–62. 3. Serafini, Luciano, and Artur d'Avila Garcez. "Logic Tensor Networks." *Artificial Intelligence* 303 (2022): 103649. | Code: 4. Manhaeve, Robin, et al. "DeepProbLog: Neural Probabilistic Logic Programming." *NeurIPS 2018 Workshop on Modeling and Decision-Making in the Spatiotemporal Domain* (2018); extended version in *Machine Learning* 110.7 (2021): 1637–1679. | Code: 5. Evans, Richard, and Edward Grefenstette. "Learning Explanatory Rules from Noisy Data." *Journal of Artificial Intelligence Research* 61 (2018): 1–64. 6. Shen, William, Felipe Trevizan, and Sylvie Thiébaux. "Learning Domain-Independent Planning Heuristics with Hypergraph Networks." *Proceedings of ICAPS*, 2020. 7. Silver, David, et al. "Mastering the Game of Go with Deep Neural Networks and Tree Search." *Nature* 529.7587 (2016): 484–489. 8. Selsam, Daniel, et al. "Learning a SAT Solver from Single-Bit Supervision." *ICLR 2019*. | Code: 9. Rocktäschel, Tim, and Sebastian Riedel. "End-to-End Differentiable Proving." *Advances in Neural Information Processing Systems (NeurIPS)*, 2017. 10. Richardson, Matthew, and Pedro Domingos. "Markov Logic Networks." *Machine Learning* 62.1–2 (2006): 107–136. | Code: 11. Wang, Po-Wei, et al. "SATNet: Bridging Deep Learning and Logical Reasoning Using a Differentiable Satisfiability Solver." *Proceedings of the International Conference on Machine Learning (ICML)*, 2019. | Code: 12. Vinyals, Oriol, Meire Fortunato, and Navdeep Jaitly. "Pointer Networks." *Advances in Neural Information Processing Systems (NIPS)* 28 (2015). 13. Kool, Wouter, Herke van Hoof, and Max Welling. "Attention, Learn to Solve Routing Problems!" *International Conference on Learning Representations (ICLR)*, 2019. | Code: 14. Lample, Guillaume, et al. "HyperTree Proof Search for Neural Theorem Proving." *Advances in Neural Information Processing Systems (NeurIPS)* 35 (2022). | Code: 15. Zhou, Andy, et al. "Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models." *Proceedings of the International Conference on Machine Learning (ICML)*, 2024. | Code: 16. Ellis, Kevin, et al. "DreamCoder: Bootstrapping Inductive Program Synthesis with Wake-Sleep Library Learning." *Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)*, 2021. | Code: 17. Cropper, Andrew, and Sebastijan Dumancic. "Learning Programs by Learning from Failures." *Machine Learning* 111.3 (2022): 801–856. | Code: 18. Law, Mark, Alessio Russo, and Krysia Broda. "The ILASP System for Inductive Learning of Answer Set Programs." *arXiv preprint arXiv:2005.00904*, 2020. | Code: 19. Yang, Zhun, et al. "NeurASP: Embracing Neural Networks into Answer Set Programming." *Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI)*, 2020. | Code: 20. Winters, Thomas, et al. "DeepStochLog: Neural Stochastic Logic Programming." *Proceedings of the AAAI Conference on Artificial Intelligence*, 2022. 21. Skryagin, Arseny, et al. "Neural-Probabilistic Answer Set Programming." *Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning (KR)*, 2022. 22. Li, Ziyang, et al. "Scallop: A Language for Neurosymbolic Programming." *Proceedings of the ACM on Programming Languages (OOPSLA)*, 2023. | Code: 23. Gulwani, Sumit. "Automating String Processing in Spreadsheets Using Input-Output Examples." *ACM SIGPLAN Notices* 46.1 (2011): 317–330. 24. Blaauwbroek, Lasse, Josef Urban, and Herman Geuvers. "The Tactician: A Seamless, Interactive Tactic Learner and Prover for Coq." *Proceedings of CICM*, 2020. | Code: 25. AlphaProof Team and AlphaGeometry Team, DeepMind. "AI Achieves Silver-Medal Standard Solving International Mathematical Olympiad Problems." *DeepMind Technical Report*, 2024. 26. Bengio, Emmanuel, et al. "Flow Network Based Generative Models for Non-Iterative Diverse Candidate Generation." *Advances in Neural Information Processing Systems (NeurIPS)* 34 (2021). | Code: --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter: ``` GET https://neurosymbolicai.gitbook.io/neuro-symbolic-ai-in-practice/part-iii-core-approaches/chapter-4/4-2-neural-helps-symbolic/4-2-asp.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.