Streamliners for Answer Set Programming

📄 arXiv: 2604.19251v1 📥 PDF

作者: Florentina Voboril, Martin Gebser, Stefan Szeider, Alice Tarzariol

分类: cs.LO, cs.AI

发布日期: 2026-04-21

备注: To appear in Technical Communications of the 42nd International Conference on Logic Programming (ICLP 2026)

💡 一句话要点

利用大语言模型为解答集编程生成Streamliner约束，提升求解效率。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 解答集编程 约束优化 大语言模型 自动约束生成 Streamliner约束

📋 核心要点

  1. 解答集编程（ASP）求解器面临组合优化问题搜索空间大的挑战，现有方法难以有效缩小搜索范围。
  2. 借鉴StreamLLM思想，利用大语言模型（LLM）自动生成并筛选Streamliner约束，以缩小ASP的搜索空间。
  3. 实验表明，该方法在多个ASP竞赛基准上实现了显著的加速，最高可达4-5倍，证明了其有效性。

📝 摘要（中文）

Streamliner约束通过排除解空间的部分区域来减少组合问题的搜索空间。本文将StreamLLM方法（该方法使用大型语言模型（LLM）为约束编程生成streamliner）应用于解答集编程（ASP）。给定一个ASP编码和一些小的训练实例，我们提示多个LLM来提出候选约束。丢弃那些导致语法错误、使可满足的实例变得不可满足或降低所有训练实例性能的候选约束。将剩余的streamliner与原始编码一起评估，并报告虚拟最佳编码（VBE）的结果，对于每个实例，VBE选择原始编码及其streamlined变体中最快的。在三个ASP竞赛基准（Partner Units Problem、Sokoban、Towers of Hanoi）上，VBE实现了高达4-5倍于原始编码的加速。不同的LLM产生语义上不同的约束，而不仅仅是句法上的变化，表明该方法捕获了真正的问​​题结构。

🔬 方法详解

问题定义：解答集编程（ASP）是一种声明式编程范式，用于解决组合优化问题。然而，随着问题规模的增大，ASP求解器的搜索空间会呈指数级增长，导致求解效率降低。现有的约束优化方法往往需要人工设计约束，耗时且依赖专家知识。

核心思路：本文的核心思路是利用大型语言模型（LLM）的强大生成能力，自动生成Streamliner约束，这些约束可以排除解空间中不必要的部分，从而缩小搜索范围，提高求解效率。通过训练LLM生成有效的约束，并结合筛选机制，最终得到能够提升ASP求解器性能的约束集合。

技术框架：该方法主要包含以下几个阶段：1) 数据准备：准备ASP编码和少量训练实例。2) LLM提示：提示多个LLM生成候选约束。3) 约束筛选：根据语法正确性、可满足性保持和性能提升三个标准，筛选候选约束。4) 性能评估：将筛选后的Streamliner约束与原始编码结合，评估整体性能。5) 虚拟最佳编码（VBE）：对于每个实例，选择原始编码及其streamlined变体中最快的。

关键创新：该方法最重要的创新点在于将大型语言模型（LLM）引入到ASP约束生成过程中，实现了约束的自动生成。与传统的手工设计约束相比，该方法能够更快速、更高效地生成有效的约束，并且可以发现人工难以设计的约束模式。此外，通过筛选机制，保证了生成的约束的有效性和可靠性。

关键设计：在LLM提示阶段，使用了多个不同的LLM，以增加约束的多样性。在约束筛选阶段，采用了三个标准：语法正确性（确保生成的约束没有语法错误）、可满足性保持（确保生成的约束不会使可满足的实例变得不可满足）和性能提升（确保生成的约束能够提高求解效率）。虚拟最佳编码（VBE）的设计是为了评估Streamliner约束的上限性能，即在理想情况下，选择最优的约束组合所能达到的性能。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，该方法在三个ASP竞赛基准（Partner Units Problem、Sokoban、Towers of Hanoi）上取得了显著的性能提升。虚拟最佳编码（VBE）实现了高达4-5倍于原始编码的加速。此外，不同的LLM生成了语义上不同的约束，表明该方法能够捕获问题的内在结构。

🎯 应用场景

该研究成果可应用于各种组合优化问题，如规划、调度、资源分配等领域。通过自动生成Streamliner约束，可以显著提高ASP求解器的效率，从而解决更大规模、更复杂的实际问题。未来，该方法有望推广到其他约束编程范式，并与其他优化技术相结合，进一步提升求解性能。

📄 摘要（原文）

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). Given an ASP encoding and a few small training instances, we prompt multiple LLMs to propose candidate constraints. Candidates that cause syntax errors, render satisfiable instances unsatisfiable, or degrade performance on all training instances are discarded. The surviving streamliners are evaluated together with the original encoding, and we report results for a virtual best encoding (VBE) that, for each instance, selects the fastest among the original encoding and its streamlined variants. On three ASP Competition benchmarks (Partner Units Problem, Sokoban, Towers of Hanoi), the VBE achieves speedups of up to 4--5x over the original encoding. Different LLMs produce semantically diverse constraints, not mere syntactic variations, indicating that the approach captures genuine problem structure.