Streamliners for Answer Set Programming

1. Problem Statement

Answer Set Programming (ASP) is a powerful declarative paradigm for solving combinatorial problems. However, solver performance is highly sensitive to the specific encoding used; logically equivalent formulations can yield vastly different grounding sizes and solving times.

• The Challenge: Improving performance often requires adding streamliner constraints—auxiliary constraints that prune the search space by ruling out portions of the solution space (e.g., symmetry-breaking or implied constraints) without rendering satisfiable instances unsatisfiable.
• Current Limitations: Existing automated methods for generating streamliners in ASP often rely on:
  • Propositional symmetry breaking (which does not scale well).
  • Inductive Logic Programming (ILP) requiring carefully designed language biases (limiting generality).
  • Manual hand-crafting by domain experts.
• The Gap: There is a lack of general, automated approaches that can generate diverse, semantically meaningful streamliners for ASP without heavy human intervention or rigid domain templates.

2. Methodology

The authors adapt the StreamLLM approach (previously used for Constraint Programming) to the domain of ASP. The pipeline is fully automated and relies on Large Language Models (LLMs) to propose constraints based on a problem encoding and a few small training instances.

The Pipeline:

1. Input: An ASP encoding (in Clingo syntax) and a set of small, satisfiable training instances.
2. LLM Prompting: The system prompts multiple frontier LLMs (e.g., Claude 4.5, GPT-5, Gemini 3, Mistral, Deepseek) to generate five candidate constraints.
   • Prompt Strategy: Uses Chain-of-Thought reasoning to analyze the encoding and generate constraints that eliminate symmetries or redundant solutions.
   • Output Format: Constraints are requested in JSON format to ensure syntactic structure.
3. Filtering & Validation:
   • Generated candidates are added to the original encoding.
   • Discarded if: They cause syntax errors, make satisfiable training instances unsatisfiable, or degrade performance on all training instances.
   • Retained if: They improve runtime on at least one training instance.
4. Selection: The process runs for 30 minutes. The system selects the top three streamliners that, when combined, minimize the sum of per-instance minimum runtimes (Virtual Best Encoding criterion) on the training set.
5. Evaluation: The selected streamliners are tested on a separate test set. Performance is measured using a Virtual Best Encoding (VBE), which selects the fastest variant (original or any streamlined version) for each specific instance.

3. Key Contributions

• First Application to ASP: This is the first systematic application of LLM-based streamliner generation specifically for Answer Set Programming.
• Adaptation to ASP Semantics: The authors successfully adapted the StreamLLM pipeline to handle ASP's non-monotonic semantics (stable models), where adding rules can subtly alter solution sets. The system filters out constraints that inadvertently break satisfiability.
• Diversity of Generation: The study demonstrates that different LLMs and runs produce semantically diverse constraints (not just syntactic variations), capturing genuine problem structures like symmetry breaking, implied constraints, and domain-specific pruning.
• Low-Data Requirement: The approach requires only a few small training instances to guide the LLM, avoiding the need for large, curated datasets or complex language biases.

4. Experimental Results

The approach was evaluated on three benchmarks from the ASP Competition 2011:

1. Partner Units Problem (PUP): A configuration problem.
2. Sokoban: A planning problem.
3. Towers of Hanoi: A puzzle problem.

Key Findings:

• Performance Gains: The Virtual Best Encoding (VBE) achieved speedups of 4–5× over the original encoding.
  • PUP: 47%–76% reduction in running time.
  • Sokoban: 57%–75% reduction.
  • Towers of Hanoi: 71%–79% reduction (solving all 46 test instances where the original only solved 31).
• Complementarity: No single streamlined encoding dominated all instances. The VBE analysis confirmed that different streamliners provide complementary strengths, solving different subsets of hard instances.
• Constraint Quality:
  • 52% of generated constraints improved performance on training instances.
  • 19% caused syntax errors, and ~17% caused unsatisfiability (filtered out).
  • Surprising Insight: When the authors manually "optimized" the LLM-generated constraints to reduce grounding size (e.g., converting quadratic constraints to linear aggregates), performance often degraded. This suggests the LLM's empirical selection of constraints (even if theoretically less efficient in grounding) aligns better with the solver's internal heuristics than manual theoretical optimization.

5. Significance

• Practical Impact: The method offers a practical, automated way to boost ASP solver performance without requiring deep domain expertise to manually craft constraints.
• Synergy with Solvers: The results highlight that "empirically good" constraints (selected by runtime) may differ from "theoretically optimal" constraints (selected by grounding size), providing new insights into solver behavior.
• Future Directions: The paper establishes a foundation for using LLMs not just for program generation (NL-to-ASP), but for program augmentation. Future work includes fine-tuning models for ASP, expanding to optimization problems, and testing on broader benchmark suites.

In conclusion, the paper demonstrates that LLMs can effectively act as "constraint engineers" for ASP, generating diverse and effective streamliners that significantly reduce solving times for complex combinatorial problems.