Streamliners for Answer Set Programming
Florentina Voboril, Martin Gebser, Stefan Szeider, Alice Tarzariol · 2026
Read Streamliners for Answer Set Programming by Florentina Voboril, Martin Gebser, Stefan Szeider, Alice Tarzariol (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-19251.txt.
Introduction
Voboril and three colleagues adapt a language-model method for finding extra constraints, called streamliners, from constraint programming to answer set programming. Candidate constraints are tested on small examples and dropped if they break syntax, kill valid answers, or slow every training case. Kept streamliners run beside the original encoding, and picking the fastest variant per instance speeds three competition benchmarks by up to four to five times.
Catalog record
| CREATOR | Florentina Voboril, Martin Gebser, Stefan Szeider, Alice Tarzariol |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 45483 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.19251
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Streamliners for Answer Set Programming Florentina Voboril, Martin Gebser, Stefan Szeider, Alice Tarzariol 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). 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–5 × \times over the original encoding. Different LLMs produce semantically diverse constraints, not mere syntactic variations, indicating that the approach captures genuine problem structure. 1 Introduction Answer Set Programming (ASP) has established itself as a powerful paradigm for declarative problem solving, with successful applications in planning, scheduling, configuration, and knowledge representation [ 4 ] . Modern ASP solvers like clingo [ 14 ] combine grounding with conflict-driven clause learning, enabling the solution of hard combinatorial problems. However, solver performance remains highly sensitive to problem encodings: two logically equivalent formulations can lead to vastly different grounding sizes and solving times. A well-known technique for improving solver performance is the addition of streamliner constraints [ 17 ] . These are auxiliary constraints intended to reduce the search space by ruling out parts of the solution space. They need not be logically implied by the original encoding and may remove some solutions, but should preserve satisfiability for the instances of interest. Streamliners include symmetry-breaking constraints [ 40 ] , which remove equivalent solutions arising from problem symmetries, and implied constraints , which make implicit problem structure explicit to the solver. In the Constraint Programming (CP) community, Spracklen et al. [ 29 ] recently demonstrated that portfolios of automatically generated streamliners can match or exceed hand-crafted constraints. In ASP, systems like sbass [ 10 ] and BreakID [ 8 ] automatically generate propositional symmetry-breaking constraints, while learning-based approaches derive first-order constraints from small instances [ 32 ] . Inductive logic programming methods such as conflict-driven constraint learning [ 21 ] and core-guided reformulation [ 22 ] also aim to discover useful constraints automatically. These methods either operate at the propositional level (often causing grounding bottlenecks on larger instances) or require carefully designed language biases (limiting generality). Voboril et al. [ 39 ] recently demonstrated that Large Language Models (LLMs) can generate streamliner constraints for CP problems. Their StreamLLM approach prompts an LLM with a problem encoding and asks it to propose constraints that reduce the search space. Candidate constraints are validated on small training instances and the best-performing ones are retained. This approach requires no hand-crafted language bias or domain templates; it only uses the encoding plus a few small training instances. The intersection of LLMs and ASP has been explored along two directions. Neural-symbolic hybrids like NeurASP [ 43 ] and differentiable ASP solvers [ 28 ] integrate neural components with ASP reasoning, but assume the logic program is manually written. For automated program generation, Ishay et al. [ 20 ] prompt LLMs to produce complete ASP programs from natural language, and Coppolillo et al. [ 7 ] fine-tune LLMs for ASP syntax. However, one-shot generation often yields flawed programs [ 27 ] . Agentic approaches address this through iterative refinement with solver feedback: the MCP-Solver [ 31 ] exposes ASP capabilities to LLMs via the Model Context Protocol, and evaluation on ASP-Bench [ 30 ] shows that feedback-driven agents can solve all 128 benchmark problems. Our work differs from NL-to-ASP translation: we do not generate entire programs, but propose auxiliary constraints that augment existing encodings. In this paper, we investigate whether LLM-based streamliner generation can be adapted to Answer Set Programming. ASP presents distinct challenges compared to CP: the non-monotonic semantics of stable models means that adding constraints or auxiliary definitions can have subtle effects on solution sets. LLMs may generate not only integrity constraints but also helper rules that introduce new atoms, which can interact non-trivially with the minimality condition of stable models. The rich syntax of ASP (aggregates, choice rules, conditional literals, optimization statements) also requires LLMs to generate syntactically valid and semantically meaningful code. We adapt the StreamLLM pipeline to ASP by (1) prompting multiple frontier LLMs to generate candidate streamliners for a given ASP encoding, (2) filtering candidates that cause syntax errors, make satisfiable training instances unsatisfiable, or degrade runtime performance on all training instances, (3) selecting the best-performing streamliners based on runtime improvements on training instances, (4) evaluating the original encoding together with the streamlined variants by considering, for each instance the fastest among them (virtual best encoding), which serves as an oracle-style analysis of complementarity. We evaluate our approach on three benchmark problems from the ASP Competition 2011 [ 5 ] - Partner Units Problem, Sokoban, and Towers of Hanoi - observing speedups of up to 4–5 \times under a virtual best encoding (VBE) analysis. Different LLMs and different runs produce semantically diverse constraints, not simple syntactic variations. This suggests the approach captures genuine problem structure rather than exploiting superficial patterns. Contributions. We present, to our knowledge, the first systematic application of LLM-based streamliner generation to ASP. We further analyze the complementarity of generated streamliners from a virtual best encoding perspective, highlighting their potential for instance-specific performance gains. Finally, we empirically evaluate our approach on three ASP competition benchmarks and analyze the generated constraints as symmetry-breaking, implied, or domain-specific pruning. Paper outline. Section 2 provides background on ASP and related work. Section 3 describes our adaptation of StreamLLM to ASP. Section 4 presents the experiments and analyzes the generated streamliners. Section 5 concludes with limitations and future directions. 2 Preliminaries 2.1 Answer Set Programming We consider first-order ASP programs in the modeling language of Clingo [ 4 , 12 ] . That is, terms include (i) constants , which can be tokens starting with a lowercase letter, integers, strings enclosed in double quotes, the least term # inf or the greatest term # sup , (ii) variables , i.e., tokens starting with an uppercase letter or the anonymous variable “ _ ”, and (iii) functions of the form f ( t 1 , \dots , t n ) , for a function symbol f (a token starting with a lowercase letter) and terms t {}_{1},\dots,{} t n , or arithmetic expressions composed of integers, variables, operators “ + ” , “ - ” , “ * ” , “ / ” and parentheses. Atoms can be of three forms: (i) symbolic atoms p ( t 1 , \dots , t n ) , for a predicate symbol p (a token starting with a lowercase letter), terms t {}_{1},\dots, t n , and just written p in case n=0 , (ii) built-in atoms t {}_{1}\circ{} t 2 composed of terms t {}_{1},{} t 2 and a comparison operator {\circ}\in\{ < , <= ,