Abstract
This paper introduces a compilation-based approach to handle aggregates (such as #sum and #count) in Answer Set Programming (ASP). By translating complex logic rules into efficient C++ "propagators" instead of expanding them into massive propositional formulas, the authors effectively bypass the "grounding bottleneck." This methodology enables solvers to handle problems that were previously intractable due to memory limitations.
Introduction: The Grounding Bottleneck
Most modern ASP systems follow a ground&solve strategy. A "grounder" first translates high-order logic (with variables) into a massive set of propositional rules. Subsequently, a "solver" finds a solution.
The "grounding bottleneck" occurs when the first step produces a combinatorial explosion. A simple rule involving several variables might expand into millions of ground rules, consuming all available RAM before the solver even begins its search. Aggregates—constructs that perform mathematical operations over sets of atoms—are particularly prone to this explosion. While previous research explored compiling simple constraints, this paper provides the first formal framework and implementation for compiling aggregates to mitigate this bottleneck.
Methodology
The authors propose a system that identifies "compilable" sub-programs and transforms them into custom procedural code (propagators) that are dynamically linked to the solver, WASP.
- Syntactic Analysis: The system identifies sub-programs that meet specific conditions, such as being acyclic in the dependency graph and following specific variable-sharing patterns, ensuring they are safe to compile.
- Normalization: Rules are rewritten into a standardized format. For instance, a rule with a complex aggregate is decomposed into intermediate steps that define the aggregate's set and its guard condition separately.
- Compilation to Propagators: The normalized rules are translated into C++ code. The system implements two types of propagators:
- Eager: These run during the solver's search process to prune the search space immediately.
- Lazy: These run only after a potential solution is found to verify its validity.
- Compiler Optimizations: To ensure the generated C++ is high-performance, the system applies classic compiler techniques like loop unrolling and dead code elimination to the generated propagator code.
Experimental Setup
The approach was evaluated using three distinct settings:
- Setting (i): A synthetic, ground-intensive benchmark designed to push the limits of the grounding process.
- Setting (ii): Standard benchmarks from ASP Competitions (e.g., Bottle Filling, Partner Units) to ensure the method maintains performance on "normal" problems.
- Setting (iii): Three grounding-intensive benchmarks from recent literature: Component Assignment, Dynamic In-Degree Counting, and Exponential-Save.
Key Results and Discussion
Scalability and Memory Efficiency
In synthetic benchmarks, the advantages of WASP-COMP are stark. While industry-standard solvers like CLINGO and the original WASP failed (due to timeouts or memory exhaustion) at a scale of $k=8000$, WASP-COMP successfully handled instances up to $k=40000$.
WASP-COMP consistently used orders of magnitude less memory on ground-intensive tasks because it avoids storing the massive grounded program, representing the logic as procedural code instead.
Performance on Standard and Ground-Intensive Benchmarks
On the Dynamic In-Degree Counting benchmark, WASP-COMP solved instances in 48 seconds that took the standard version 1374 seconds. Furthermore, in the Component Assignment task, WASP-COMP solved 188 instances, significantly outperforming CLINGO (118) and the original WASP (70).
On standard competition benchmarks that are not grounding-heavy, the overhead of compilation was found to be negligible. This suggests that the compilation approach provides a significant safety net for complex problems without penalizing performance on simpler ones.
Conclusion
The core innovation of this work is the realization that logic rules do not always need to be represented as data (propositional rules) if they can be represented as functions (code). By treating the logic solver as a compiler target, the authors leverage decades of programming language theory to optimize AI reasoning.
Future work will focus on expanding the class of "compilable" programs to include more complex recursive structures and further optimizing the interface between the solver and the dynamically generated propagators.
Summary updated