Hybrid Compilation-based ASP solving Carmine Dodaro, Giuseppe Mazzotta and Francesco Ricca Department of Mathematics and Computer Science, University of Calabria, Rende, Italy Abstract Answer Set Programming (ASP) is a widely recognized formalism for Knowledge Representation and Reasoning. State-of-the-art ASP systems, based on the well-known Ground&Solve approach, are subject to the grounding bottleneck problem that, in some cases, makes the computation of answer sets practically unfeasible. Compilation- based approaches have recently demonstrated how grounding can be effectively bypassed by compiling rules into propagators, but, compiling an entire ASP program is not always advantageous. In the paper titled “Blending grounding and compilation for efficient ASP solving”, presented during the “Twenty-First International Conference on Principles of Knowledge Representation and Reasoning (KR 2024)”, we proposed a hybrid approach that allows for unrestricted blending of grounding and compilation. In this paper, we investigate the advantages of using ad-hoc hybrid solvers and discuss future directions in this line of research. Keywords Answer Set Programming, Compilation-Based ASP Solving, Grounding Bottleneck, Hybrid Solving 1. Introduction Answer Set Programming (ASP) [1, 2] is a well-known declarative AI formalism for KRR. Thanks to the availability of efficient implementations, ASP finds extensive applications in several AI sub-areas [3], such as Planning [4], Scheduling [5, 6], Natural Language Processing [7, 8, 9], and Databases [10, 11, 12]. Traditional ASP systems, such as CLINGO [13] and DLV [14], are based on the Ground&Solve approach [15]. Intuitively, an input program is first “grounded” to compute a variable-free equivalent propositional program; and subsequently, the grounded program is “solved” by employing a CDCL-like algorithm [16] that computes its answer sets. However, such an approach intrinsically suffers from the so-called grounding bottleneck, i.e., getting rid of variables already consumes all the computational resources (i.e., time and/or space) in several cases of practical interest [17, 18]. The grounding bottleneck [19] has been approached from several perspectives. These include hybrid formalisms [20, 13, 18, 21], lazy grounding architectures [22, 23, 24, 25, 26], complexity-driven program rewritings [27, 28], and program compilation into propagators [29, 30, 31, 32]. Among these, compilation-based approaches demonstrated that the grounding can be skipped in some relevant cases by compiling rules in propagators able to ground rules’ inferences. Such techniques were first proposed for subprograms acting as constraints [30, 31]. More recently, the ProASP system [32] has been proposed. ProASP demonstrated that it is possible to devise a compiler also for rules “generating” answer sets (i.e., involving non-stratified negation). In ProASP, a tight [33] non-ground input program is first pre-processed by applying a rewriting encompassing program completion [34] and normalization (i.e., it produces rules of two kinds). Then, the compiler generates code for both Herbrand base generation and rule propagators. That code is injected in the CDCL solver Glucose [35] to initialize variables and simulate the presence of ground rules, respectively. In this way, the ProASP compiler produces a solver specific for the non-ground program in input that needs no grounder. Clearly, ProASP implements an approach that is basically at the antipodes of Ground&Solve, since it compiles all rules of the program. However, empirical evidence showed that compiling all rules of an ASP program does not pay off in all cases w.r.t. traditional approaches [31]. This is not surprising. It is well-established that there is no free lunch in ASP solving [36], i.e., no single algorithm is the best in all cases. Under typical operational AIxIA 2024 Discussion Papers - 23rd International Conference of the Italian Association for Artificial Intelligence, Bolzano, Italy, November 25–28, 2024 $ carmine.dodaro@unical.it (C. Dodaro); giuseppe.mazzotta@unical.it (G. Mazzotta); francesco.ricca@unical.it (F. Ricca)  0000-0002-5617-5286 (C. Dodaro); 0000-0003-0125-0477 (G. Mazzotta); 0000-0001-8218-3178 (F. Ricca) © 2025 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings scenarios, it is plausible that certain rules of the program can be efficiently grounded and, thus, are amenable to be processed using the traditional architecture; whereas, for the remaining part of the program, which is made of rules that are subject to the grounding bottleneck, a compilation-based system could offer a viable solution for their evaluation. This latter case, which is very common in practice, cannot be approached in the best possible way with current state-of-the-art ASP systems, that either ground or compile everything. In the paper “Blending grounding and compilation for efficient ASP solving”, we presented a compilation-based architecture, built on top of the ProASP system, for blending grounding and compi- lation. This novel approach allows for an unrestricted blending of both methods and aims at achieving superior performance by combining the advantages of both approaches. In this paper, we overview hybrid ASP solving, outline its strengths, and discuss future directions of this line of research. 2. Hybrid ProASP: Blending Grounding and Compilation In this section we describe the extended architecture of the ProASP system that exploits an optimized rewriting strategy and allows for the compilation of a program into a hybrid ASP solver (i.e. mixing Ground&Solve and Compilation) without any compilability restrictions that existing compilation-based approaches [30, 31] are subject to. The ProASP system implements two different stages, namely Compilation and Solving stages. The former is used to build a hybrid solver starting from a non-ground program Π, while the latter employs the obtained ad-hoc hybrid solver to compute an answer set Π ∪ 𝐹 , where 𝐹 is a set of facts representing a specific problem instance. At Compilation Stage ProASP system takes as input a non-ground program Π and compiles it into a hybrid solver. To this end, the input program Π is fed into the Compiler module that analyzes Π, identifies the rules that should be compiled and those that should be grounded, and then compiles them properly. More precisely, the Compiler first applies a pre-processing step that extends the normalization of ProASP to allow grounded rules to coexist with propagators, no matter if they are involved in a recursive definition. Then, the rules to be compiled follow the usual path of ProASP, i.e., they are compiled in propagators; whereas the remaining rules are compiled in a code that performs grounding, i.e., code that generates propositional clauses that are stored in the Glucose data structures. As a result, we obtain an ASP system that blends compilation and grounding. At Solving Stage, instead, ProASP takes as input a set of facts 𝐹 denoting a specific instance of the program Π that should be solved, and computes an answer set of Π ∪ 𝐹 , if any, or proves its incoherence. First of all, the input instance 𝐹 is given as input to the Hybrid Generator module that generates the set of relevant atoms [32] for computing the answer set of Π ∪ 𝐹 together with the ground instantiations of rules of Π that should be grounded. Produced ground rules are successively transformed into a set of clauses [33] that, together with generated atoms, are used to initialize the Glucose SAT solver at the core of the ProASP system. At this point, Glucose starts the CDCL for computing an answer set of Π ∪ 𝐹 . At each step of the CDCL algorithm, Glucose chooses a branching literal 𝑙 and performs the unit propagation by (i) considering the generated clauses encoding the ground rules and (ii) using the Propagator module, for simulating the inferences of the remaining rules. During the CDCL, as soon as the current interpretation becomes inconsistent, the conflicting literals are analyzed according to the propagation clauses that derived them. More precisely, for all those literals that have been derived from compiled propagators, Glucose uses the Propagator module to reconstruct the propagation clauses, while, for all other literals, Glucose analyzes its internal clauses that caused the propagation. As soon as the current interpretation is total or the consistency cannot be restored, then the CDCL stops. At this point, if such total interpretation 𝑀 has been found, then 𝑀 is an answer set of Π ∪ 𝐹 , otherwise ProASP returns ⊥, denoting that Π ∪ 𝐹 has no answer sets. Figure 1: Comparison between Ground&Solve and hybrid ASP solving 3. Scalability of hybrid ASP solving We report here about the final experiment performed in [37], where the ProASP system with hybrid solving enabled has been compared to the state-of-the-art Ground&Solve ASP system CLINGO on well- established benchmarks featuring 2366 instances from 14 application domains. In this evaluation, we considered eight variants of ProASP representing different ways of blending grounding and compilation by splitting programs by rule type. More precisely, we identified the following three types of rules: (CS) constraints not containing aggregates; (AG) rules containing aggregates; (RL) normal rules; and also their combinations, i.e., RL+CS, RL+AG, and CS+AG. Additionally, we also consider the two versions of ProASP in which the whole program is compiled or grounded. Finally, we label HYBRID-PROASP the ProASP version obtained by considering the best split for each benchmark. Obtained results are reported in Figure 1 where the two cactus plots report, respectively, time and memory consumption. Recall that, in a cactus plot, instances are sorted by memory (or time) usage, and a point (𝑖, 𝑗) indicates that a solver is capable of solving the 𝑖-th instance with a memory (or time) limit of 𝑗 megabytes (or seconds), respectively. As it is evident from the plots, the hybrid solving results in significant performance improvements w.r.t. the state-of-the-art by solving 513 more instances and consuming much less memory (roughly 60%). For further details, we refer reader to [37]. 4. Discussion ASP systems based on Ground&Solve approach are generally effective, but they can struggle with the grounding bottleneck. On the other hand, compilation-based ASP systems have shown that, in certain cases, grounding can be avoided. However, neither approach pays off in all cases. By developing a technique that seamlessly combines grounding and compilation, we achieved notable improvements over existing compilation-based methods and current state-of-the-art implementations. This is a very promising result, expanding the applicability of ASP as an AI tool for solving complex combinatorial problems. As far as future work is concerned, since the ProASP system does not support the entire ASP-Core 2 standard, it would be interesting to extend the benefit of the blending also to a wider class of programs such as non-tight programs and disjunctive ones. Another promising avenue is the exploration of a more fine-grained—and possibly automated—procedure for selecting which rules to ground or compile. However, this presents a significant challenge arising from the unique nature of compilation, which must be performed prior to executing any instance of the problem. Acknowledgments This work has been partially supported by MISE under project EI-TWIN n. F/310168/05/X56 CUP B29J24000680005, and MUR under projects: PNRR FAIR - Spoke 9 - WP 9.1 CUP H23C22000860006, Tech4You CUP H23C22000370006, and PRIN PINPOINT CUP H23C22000280006. References [1] G. Brewka, T. Eiter, M. Truszczynski, Answer set programming at a glance, Commun. ACM 54 (2011) 92–103. [2] M. Gelfond, V. Lifschitz, Classical negation in logic programs and disjunctive databases, New Gener. Comput. 9 (1991) 365–386. [3] E. Erdem, M. Gelfond, N. Leone, Applications of answer set programming, AI Mag. 37 (2016) 53–68. [4] T. C. Son, E. Pontelli, M. Balduccini, T. Schaub, Answer set planning: A survey, Theory Pract. Log. Program. 23 (2023) 226–298. [5] C. Dodaro, M. Maratea, Nurse scheduling via answer set programming, in: LPNMR, volume 10377 of Lecture Notes in Computer Science, Springer, 2017, pp. 301–307. [6] M. Cardellini, C. Dodaro, G. Galatà, A. Giardini, M. Maratea, N. Nisopoli, I. Porro, Rescheduling rehabilitation sessions with answer set programming, J. Log. Comput. 33 (2023) 837–863. [7] A. Mitra, P. Clark, O. Tafjord, C. Baral, Declarative question answering over knowledge bases containing natural language text with answer set programming, in: AAAI, AAAI Press, 2019, pp. 3003–3010. [8] P. Schüller, Modeling variations of first-order horn abduction in answer set programming, Fundam. Informaticae 149 (2016) 159–207. [9] Z. Yang, A. Ishay, J. Lee, Coupling large language models with logic programming for robust and general reasoning from text, in: ACL (Findings), Association for Computational Linguistics, 2023, pp. 5186–5219. [10] T. Eiter, M. Fink, G. Greco, D. Lembo, Repair localization for query answering from inconsistent databases, ACM Trans. Database Syst. 33 (2008) 10:1–10:51. [11] M. Arenas, L. E. Bertossi, J. Chomicki, Consistent query answers in inconsistent databases, in: PODS, ACM Press, 1999, pp. 68–79. [12] M. Manna, F. Ricca, G. Terracina, Taming primary key violations to query large inconsistent data via ASP, Theory Pract. Log. Program. 15 (2015) 696–710. [13] M. Gebser, R. Kaminski, B. Kaufmann, M. Ostrowski, T. Schaub, P. Wanko, Theory solving made easy with clingo 5, in: ICLP (Technical Communications), volume 52 of OASICS, Schloss Dagstuhl, 2016, pp. 2:1–2:15. [14] M. Alviano, F. Calimeri, C. Dodaro, D. Fuscà, N. Leone, S. Perri, F. Ricca, P. Veltri, J. Zangari, The ASP system DLV2, in: LPNMR, volume 10377 of Lecture Notes in Computer Science, Springer, 2017, pp. 215–221. [15] B. Kaufmann, N. Leone, S. Perri, T. Schaub, Grounding and solving in answer set programming, AI Mag. 37 (2016) 25–32. [16] J. Marques-Silva, I. Lynce, S. Malik, Conflict-driven clause learning SAT solvers, in: Handbook of Satisfiability, volume 336 of Frontiers in Artificial Intelligence and Applications, IOS Press, 2021, pp. 133–182. [17] F. Calimeri, M. Gebser, M. Maratea, F. Ricca, Design and results of the fifth answer set programming competition, Artif. Intell. 231 (2016) 151–181. [18] M. Ostrowski, T. Schaub, ASP modulo CSP: the clingcon system, Theory Pract. Log. Program. 12 (2012) 485–503. [19] M. Gebser, N. Leone, M. Maratea, S. Perri, F. Ricca, T. Schaub, Evaluation techniques and systems for answer set programming: a survey, in: IJCAI, ijcai.org, 2018, pp. 5450–5456. [20] M. Balduccini, Y. Lierler, Constraint answer set solver EZCSP and why integration schemas matter, Theory Pract. Log. Program. 17 (2017) 462–515. [21] B. Susman, Y. Lierler, Smt-based constraint answer set solver EZSMT (system description), in: ICLP (Technical Communications), volume 52 of OASIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, pp. 1:1–1:15. [22] J. Bomanson, T. Janhunen, A. Weinzierl, Enhancing lazy grounding with lazy normalization in answer-set programming, in: AAAI, AAAI Press, 2019, pp. 2694–2702. [23] C. Lefèvre, P. Nicolas, The first version of a new ASP solver : Asperix, in: LPNMR, volume 5753 of Lecture Notes in Computer Science, Springer, 2009, pp. 522–527. [24] Y. Lierler, J. Robbins, Dualgrounder: Lazy instantiation via clingo multi-shot framework, in: JELIA, volume 12678 of Lecture Notes in Computer Science, Springer, 2021, pp. 435–441. [25] A. D. Palù, A. Dovier, E. Pontelli, G. Rossi, GASP: answer set programming with lazy grounding, Fundam. Informaticae 96 (2009) 297–322. [26] A. Weinzierl, Blending lazy-grounding and CDNL search for answer-set solving, in: LPNMR, volume 10377 of Lecture Notes in Computer Science, Springer, 2017, pp. 191–204. [27] V. Besin, M. Hecher, S. Woltran, On the structural complexity of grounding - tackling the ASP grounding bottleneck via epistemic programs and treewidth, in: ECAI, volume 372 of Frontiers in Artificial Intelligence and Applications, IOS Press, 2023, pp. 247–254. [28] V. Besin, M. Hecher, S. Woltran, Body-decoupled grounding via solving: A novel approach on the ASP bottleneck, in: IJCAI, ijcai.org, 2022, pp. 2546–2552. [29] B. Cuteri, C. Dodaro, F. Ricca, P. Schüller, Partial compilation of ASP programs, Theory Pract. Log. Program. 19 (2019) 857–873. URL: https://doi.org/10.1017/S1471068419000231. doi:10.1017/ S1471068419000231. [30] B. Cuteri, C. Dodaro, F. Ricca, P. Schüller, Overcoming the grounding bottleneck due to constraints in ASP solving: Constraints become propagators, in: IJCAI, ijcai.org, 2020, pp. 1688–1694. [31] G. Mazzotta, F. Ricca, C. Dodaro, Compilation of aggregates in ASP systems, in: AAAI, AAAI Press, 2022, pp. 5834–5841. [32] C. Dodaro, G. Mazzotta, F. Ricca, Compilation of tight ASP programs, in: ECAI, volume 372 of Frontiers in Artificial Intelligence and Applications, IOS Press, 2023, pp. 557–564. [33] E. Erdem, V. Lifschitz, Tight logic programs, Theory Pract. Log. Program. 3 (2003) 499–518. [34] K. L. Clark, Negation as failure, in: Logic and Data Bases, Advances in Data Base Theory, Plemum Press, New York, 1977, pp. 293–322. [35] G. Audemard, L. Simon, Predicting learnt clauses quality in modern SAT solvers, in: IJCAI, 2009, pp. 399–404. [36] M. Gebser, M. Maratea, F. Ricca, The seventh answer set programming competition: Design and results, Theory Pract. Log. Program. 20 (2020) 176–204. [37] C. Dodaro, G. Mazzotta, F. Ricca, Blending Grounding and Compilation for Efficient ASP Solving, in: Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning, 2024, pp. 317–328. URL: https://doi.org/10.24963/kr.2024/30. doi:10.24963/kr. 2024/30.