Streamliners for Answer Set Programming
Source: arXiv:2604.19251v1
Type: Cross
Abstract: Streamliner constraints reduce the search space of combinatorial problems by ruling out portions of the solution space. We adapt the StreamLLM approach, which uses Large Language Models (LLMs) to generate streamliners for Constraint Programming, to Answer Set Programming (ASP).
Introduction
Answer Set Programming (ASP) is a prominent paradigm in the field of artificial intelligence that is particularly suited for solving combinatorial problems. The efficiency of ASP can often be hampered by the vastness of the solution space. To address this challenge, researchers have devised innovative techniques aimed at reducing the search space. One such technique involves the use of streamliner constraints, which effectively eliminate certain portions of the solution space, thereby streamlining the problem-solving process.
Methodology
The recent adaptation of the StreamLLM approach employs Large Language Models (LLMs) to generate these streamliners specifically for ASP. This process begins with an ASP encoding along with a few small training instances. The methodology can be summarized as follows:
- Prompting multiple LLMs to propose candidate constraints based on the provided ASP encoding.
- Discarding candidates that lead to syntax errors, make satisfiable instances unsatisfiable, or degrade performance across all training instances.
- Evaluating the surviving streamliners alongside the original encoding to assess their efficacy.
Results
The results obtained from this methodology were promising. A Virtual Best Encoding (VBE) was introduced, which for each instance selects the fastest option among the original encoding and its streamlined variants. Notably, the VBE achieved remarkable speedups of up to 4–5 times over the original encoding when evaluated on three well-known ASP Competition benchmarks:
- Partner Units Problem
- Sokoban
- Towers of Hanoi
This significant enhancement in performance indicates that the streamliner constraints have positively impacted the efficiency of the ASP solving process.
Discussion
One of the intriguing findings from this research is that different LLMs produced semantically diverse constraints rather than simply generating syntactic variations. This suggests that the approach effectively captures genuine structural insights into the problem, paving the way for more sophisticated and efficient ASP solutions.
Conclusion
The adaptation of Large Language Models for generating streamliner constraints marks a significant advancement in the field of Answer Set Programming. By reducing the search space and improving problem-solving efficiency, this approach not only enhances the performance of ASP solvers but also underscores the potential of integrating AI with traditional programming paradigms. Future work will likely explore further refinements to the methodology and its application to a broader range of combinatorial problems.