Paper deep dive
Streamliners for Answer Set Programming
Florentina Voboril, Martin Gebser, Stefan Szeider, Alice Tarzariol
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 98%
Last extracted: 4/26/2026, 11:04:49 PM
Summary
The paper introduces an adaptation of the StreamLLM approach to Answer Set Programming (ASP) to automatically generate 'streamliner' constraints. These constraints, such as symmetry-breaking or implied constraints, are proposed by Large Language Models (LLMs) to reduce the search space of combinatorial problems. The authors use a pipeline that prompts multiple LLMs to generate candidate constraints, filters them based on syntax and performance on small training instances, and evaluates them using a Virtual Best Encoding (VBE) metric. Experimental results on three ASP competition benchmarks (Partner Units Problem, Sokoban, and Towers of Hanoi) demonstrate that the approach can achieve speedups of up to 4–5x over original encodings, showing that LLMs can capture genuine problem structures.
Entities (8)
Relation Signals (4)
StreamLLM → adaptedto → Answer Set Programming
confidence 100% · We adapt the StreamLLM approach... to Answer Set Programming (ASP).
Large Language Models → generate → Streamliner Constraints
confidence 100% · We adapt the StreamLLM approach, which uses Large Language Models (LLMs) to generate streamliners...
Clingo → implements → Answer Set Programming
confidence 100% · We consider first-order ASP programs in the modeling language of Clingo [3, 11].
Streamliner Constraints → reduce → Search Space
confidence 100% · Streamliner constraints reduce the search space of combinatorial problems by ruling out portions of the solution space.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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--5x over the original encoding. Different LLMs produce semantically diverse constraints, not mere syntactic variations, indicating that the approach captures genuine problem structure.
Tags
Links
- Source: https://arxiv.org/abs/2604.19251v1
- Canonical: https://arxiv.org/abs/2604.19251v1
Trouble viewing inline? Open PDF directly →
Full Text
57,007 characters extracted from source content.
Expand or collapse full text
Submitted to: ICLP 2026 © F. Voboril, M. Gebser, S. Szeider & A. Tarzariol This work is licensed under the Creative Commons Attribution License. Streamliners for Answer Set Programming Florentina Voboril TU Wien Vienna, Austria florentina.voboril@tuwien.ac.at Martin Gebser University of Klagenfurt Klagenfurt, Austria Martin.Gebser@aau.at Stefan Szeider TU Wien Vienna, Austria sz@ac.tuwien.ac.at Alice Tarzariol University of Klagenfurt Klagenfurt, Austria Alice.Tarzariol@aau.at 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× 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 representa- tion [3]. Modern ASP solvers like CLINGO [13] combine grounding with conflict-driven clause learning, enabling the solution of hard combinatorial problems. However, solver performance remains highly sen- sitive 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 [16]. 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 [39], which remove equivalent solutions arising from problem symmetries, and implied constraints, which make implicit problem structure explicit to the solver. In the Constraint Pro- gramming (CP) community, Spracklen et al. [28] recently demonstrated that portfolios of automatically generated streamliners can match or exceed hand-crafted constraints. In ASP, systems like SBASS [9] and BREAKID [7] automatically generate propositional symmetry-breaking constraints, while learning- based approaches derive first-order constraints from small instances [31]. Inductive logic programming methods such as conflict-driven constraint learning [20] and core-guided reformulation [21] also aim to discover useful constraints automatically. These methods either operate at the propositional level (of- arXiv:2604.19251v1 [cs.LO] 21 Apr 2026 2Streamliners for Answer Set Programming ten causing grounding bottlenecks on larger instances) or require carefully designed language biases (limiting generality). Voboril et al. [38] recently demonstrated that Large Language Models (LLMs) can generate stream- liner 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 [42] and differentiable ASP solvers [27] integrate neural components with ASP reasoning, but assume the logic program is manually written. For automated program generation, Ishay et al. [19] prompt LLMs to produce complete ASP programs from natural language, and Coppolillo et al. [6] fine- tune LLMs for ASP syntax. However, one-shot generation often yields flawed programs [26]. Agentic approaches address this through iterative refinement with solver feedback: the MCP-Solver [30] exposes ASP capabilities to LLMs via the Model Context Protocol, and evaluation on ASP-Bench [29] 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 de- grade 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 [4] - Partner Units Problem, Sokoban, and Towers of Hanoi - observing speedups of up to 4–5× 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 stream- liner 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 adap- tation of StreamLLM to ASP. Section 4 presents the experiments and analyzes the generated streamliners. Section 5 concludes with limitations and future directions. F. Voboril, M. Gebser, S. Szeider & A. Tarzariol3 2 Preliminaries 2.1 Answer Set Programming We consider first-order ASP programs in the modeling language of Clingo [3, 11]. 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, (i) variables, i.e., tokens starting with an uppercase letter or the anonymous variable “_”, and (i) functions of the form f(t 1 ,...,t n ), for a function symbol f (a token starting with a lowercase letter) and terms t 1 ,...,t n , or arithmetic expressions composed of integers, variables, operators “+”, “-”, “*”, “/” and parentheses. Atoms can be of three forms: (i) symbolic atoms p(t 1 ,...,t n ), for a predicate symbol p (a token starting with a lowercase letter), terms t 1 ,...,t n , and just written p in case n = 0, (i) built-in atoms t 1 ◦ t 2 composed of terms t 1 ,t 2 and a comparison operator ◦∈<,<=,>=,>,=,!=, and (i) aggregate atoms t 1 ◦ 1 #aggre 1 ;... ; e k ◦ 2 t 2 , where t 1 ,t 2 are terms, ◦ 1 ,◦ 2 are comparison operators, #aggr ∈ #count,#sum,#min,#max is an aggregate function, and each e i , for 1 ≤ i ≤ k, is an aggregate ele- ment t 1 i ,...,t n i : ℓ 1 i ,...,ℓ m i over terms t 1 i ,...,t n i and basic literals ℓ 1 i ,...,ℓ m i such that each ℓ j i , for 1 i ≤ j i ≤ m i , is a, not a or not not a for some symbolic or built-in atom a. Basic literals as well as a, not a and not not a over an aggregate atom a are literals. A choice element c i is an aggregate element t 1 i : ℓ 1 i ,...,ℓ m i such that the (constant or function) term t 1 i has the form of a symbolic atom, and t 1 ◦ 1 c 1 ;... ; c k ◦ 2 t 2 with choice elements c 1 ,..., c k is a choice. Either or both of the comparison operators◦ 1 ,◦ 2 can be omitted for a choice or an aggregate atom, in which case they default to “<=”, and if t 1 or t 2 is skipped in addition, #inf resp. #sup is taken as the corresponding default value. An ASP program is a set of rules of the form h :- b 1 ,...,b m ., where h is a symbolic atom or a choice, and b 1 ,..., b m are literals. The rule head h may be omitted, in which case we call the rule a constraint. In order to be processed by Clingo, an ASP program has to be safe [3], roughly meaning that all variables must have positive occurrences (outside of arithmetic expressions) in symbolic atoms belonging to the rule body b 1 ,...,b m . The semantics of an ASP program is given by stable models [10], which are sets of (true) ground atoms that satisfy and are derivable from the instances of its (first-order) rules. We say that an ASP program is satisfiable if it has some stable model, and unsatisfiable otherwise. Moreover, proper first-order rules are called an ASP encoding, and the rules without variables a problem instance. 2.2 Related Works Although the term streamliner is not widely used in the ASP literature, many works have investigated the identification of constraints that prune the search space to improve solving performance. Regard- ing symmetry breaking, research in ASP has focused on automatically producing Symmetry Breaking Constraints (SBCs), inspired by techniques from the SAT community that generate propositional SBCs based on properties of permutation groups [25]. The systems SBASS [9] and BREAKID [7] analyse the ground ASP program to identify symmetries and add propositional SBCs, which can speed up solving on small, highly combinatorial instances but often do not scale to large ones. The work of Devriendt et al. [8] analyses predicates for interchangeable argument values and adds propositional SBCs imposing lexicographical orderings; however, this approach handles only local domain symmetries. Moreover, propositional SBCs can negatively affect solver performance through redundant constraints, and users gain no insight into the symmetry structure. These shortcomings are addressed by Tarzariol et al. [31], who exploit symmetries identified by 4Streamliners for Answer Set Programming SBASS to define an Inductive Logic Programming task that learns first-order constraints applicable to all instances from a given distribution, for both decision problems [33] and optimization problems [32]. The constraints are obtained by lifting propositional symmetries from small representative instances and validated on a test set, but not formally proved; thus, this approach generates streamliners that are not necessarily SBCs. However, it requires providing a language bias specifying building blocks for the constraints, which makes learning efficient constraints almost as challenging as optimizing an encoding by hand. Domain-specific streamliners have been developed for particular applications: Yli-Jyrä et al. [43] incorporate pruning constraints into preventive maintenance scheduling, while Husár et al. [18] design pruning strategies for multi-agent pathfinding on large instances. Cappanera et al. [5] adopt logic-based Benders decomposition for healthcare scheduling. These approaches rely on domain expertise and do not transfer to other problems. Studies on generalising conflict clauses [14] have been conducted for ASP encodings [41, 12, 34] and temporal domains [24]. Our approach differs in not being limited to streamliners derived from a particular constraint type (e.g., conflict clauses) but generating constraints from diverse sources. 3 Streamlining ASP The pipeline in Figure 1 illustrates our approach, which is based on StreamLLM [38]. It runs fully automated without human interaction. As input, it requires the ASP encoding and a few satisfiable training instances that can be solved within a few seconds. First, we run the original encoding on the training instances to obtain baseline run times. Then, we provide the LLM with the encoding and the prompt in Figure 2. Find baseline Obtain 5 streamliners from LLM Evaluate streamliners & store good ones 30m passed ? Return 3 best streamliners No Yes Figure 1: Fully automated pipeline of the approach The prompt is divided into three components: First, it states the objective, namely, to generate five additional Clingo constraints that improve solving efficiency by eliminating symmetries or redundant solutions. Second, it provides a step-by-step description of how the LLM should analyze the encoding and derive suitable constraints. This procedural guidance follows the principles of the Chain-of-Thought technique [40]. Finally, the prompt specifies compliance rules that enforce syntactic correctness of the generated Clingo code and encourage diversity and creativity in the proposed constraints. This prompt is similar to the one used for the original StreamLLM approach. The main differences are the following: • Our approach asks for Clingo constraints, while the other approach uses MiniZinc. • We only ask for well-studied streamliners in ASP, namely symmetry-breaking and implied con- straints. On the other hand, the original StreamLLM approach is also interested in streamliners that might make some instances unsatisfiable. F. Voboril, M. Gebser, S. Szeider & A. Tarzariol5 Objective Analyze the given ASP problem in Clingo and suggest five additional symmetry-breaking or implied constraints to enhance the problem-solving process. Steps 1. Analyze Content: Read the provided ASP encoding. Understand the problem being ad- dressed, including its facts, predicates, rules and constraints. 2. Generate additional constraints: Based on your analysis, create five unique constraints. These should eliminate equivalent solutions in a search space to reduce redundancy and improve solver efficiency. 3. Always return your constraints as a JSON object, adhering to the structure: “constraint_- 1”: “<Clingo constraint>”, ..., “constraint_5”: “<Clingo constraint>”. Your final output should exclusively be the JSON object containing the five constraints. DO NOT include any comments. Compliance Rules 1. Code Quality: All Clingo code provided must be syntactically correct and functional. 2. Creativity: You’re encouraged to be innovative in proposing constraints, keeping in mind their purpose: to narrow down the search space efficiently by eliminating equivalent solu- tions. Figure 2: Used prompt • The prompt for the original StreamLLM approach tells the LLM how to deal with feedback on previously provided constraints. Since their experiments showed that this adaptive variant is not working significantly better than a variant without feedback, we omitted this part. Typically, the LLM returns single constraints. However, it is also possible that it returns multiple constraints or new rules. In our procedure, we treat them the same as a single constraint. The obtained streamliners are individually added to the original encoding and tested on the training instances independently. A streamliner that leads to syntax errors, unsatisfiability, or has a longer running time than the original encoding on all training instances is discarded. The remaining streamliners that improve running time on at least one training instance are stored. We repeat this procedure for 30 minutes. After that, the program stops and returns the three streamliners that form the best combination under a VBE criterion on the training instances. Specifically, for each training instance, we consider the minimum runtime across the original encoding and the selected streamliners, and the chosen triple minimizes the sum of these per-instance minimum running times. The selected streamliners can be applied to larger instances. For our experiments, we individually 6Streamliners for Answer Set Programming run the three streamlined encodings, as well as one encoding with all three streamliners and the original encoding, and report the VBE, i.e., the fastest runtime achieved by any of the considered variants for each instance. This allows us to analyze the extent to which different streamliners provide complementary performance improvements. 4 Experiments The experiments were conducted on compute nodes with 2.40GHz, 10-core 2×Intel Xeon E5-2640 v4 processors. We used Clingo 5.8.0 as the ASP solver, which was invoked via its Python API with Python 3.11.5. In every iteration, we randomly decided for one of the following LLMs: Claude 4.5 Sonnet (anthropic/claude-sonnet-4.5), GPT-5 Mini (openai/gpt-5-mini), Gemini 3 Pro (google/gemini-3-pro- preview), Mistral Large (mistralai/mistral-large-2512), and Deepseek V3.2 (deepseek/deepseek-v3.2). All models were accessed via the OpenRouter API using identical prompts and generation parameters to ensure comparability across runs. Our repository [36] provides the original and streamlined encodings, instances, and a table of running times for each problem, together with the code used for our approach. For testing our method, we investigate its application on three combinatorial problems derived from the 2011 ASP competition [4], namely, Partner Units Problem (PUP), Sokoban and Towers of Hanoi, focusing on the decision version of these problems. Our results compare three individually streamlined encodings, their combined version, the original encoding, and a VBE that picks the fastest encoding per instance. For each problem, we did two runs to examine how much the streamliners generated by our approach vary. To account for unsolved instances, we aggregate running times using penalized average running times. Specifically, timeouts are penalized by a factor of 2 (PAR2), where a timeout corresponds to 20 minutes. Instances on which all encodings led to timeouts are excluded from the aggregated running times to avoid large offsets due to their PAR2 times. In the following subsections, we present and discuss the results for each problem and overall. 4.1 Partner Units Problem The Partner Units Problem (PUP) is an abstract representation of configuration problems occurring in railway safety or building security systems [35]. Its input consists of a set of units U and a bipartite graph G = (S, Z, E), where S is a set of sensors, Z is a set of security/safety zones, and E is a relation between S and Z. The task is to find an assignment of vertices v∈ S∪ Z into unit u i ∈ U , such that the following requirements hold for each unit and integers UCAP and IUCAP: (i) the unit contains at most UCAP many sensors and UCAP many zones; and (i) the unit has at most IUCAP adjacent units, where the units u 1 and u 2 are adjacent whenever v i ∈ u 1 and v j ∈ u 2 for some (v i , v j )∈ E. For this problem, we used the benchmark described by Aschinger et al. [1], focusing on the double instance collections with UCAP = IUCAP = 2, extracting 7 instances for training and 26 for testing. Listing 1 shows the streamliners that we obtained with our approach in two runs, the former pro- ducing constraints P1, P2, and P3 and the latter producing constraints P4, P5, and P6. Note that the constraints P2 and P5, obtained in separate runs, coincide and are redundant in the sense that they re- assert a condition already implied by the given encoding: no sensor can be assigned to multiple bags. The constraints P3 and P6 break symmetries on the assignment of sensors and zones to units, without impairing satisfiability because the identifiers/integers for bags u i ∈ U are interchangeable. Unlike that, the constraints P1 and P4 impose the non-trivial conditions that each bag must contain some zone or that two zones belonging to the same bag must have some sensor in common, respectively. These two F. Voboril, M. Gebser, S. Szeider & A. Tarzariol7 1 % Constraint P1 2 :- comUnit(U), #countZ: unit2zone(U,Z) = 0, #countS: unit2sensor(U,S) > 0. 3 4 % Constraint P2 5 :- unit2sensor(U1,S), unit2sensor(U2,S), U1 > U2. 6 7 % Constraint P3 8 :- unit2zone(U+1, _), not unit2zone(U, _), comUnit(U), comUnit(U+1). 9 10 % Constraint P4 11 :- comUnit(U), unit2zone(U,Z1), unit2zone(U,Z2), Z1 < Z2 , 12 #countS : zone2sensor(Z1,S), zone2sensor(Z2,S) = 0. 13 14 % Constraint P5 15 :- unit2sensor(U1,S), unit2sensor(U2,S), U1 > U2. 16 17 % Constraint P6 18 :- comUnit(U1), comUnit(U2), U1 < U2 , sensor(S), 19 S = #minS’: sensor(S’), unit2sensor(U2,S), #countZ: unit2zone(U1 ,Z) = 0. Listing 1: PUP Streamliners streamliners preserve the satisfiability of our training instances (and the test instances as well), while their general validity is not obvious and would necessitate a formal proof. Figure 3: Results for PUP for run 1 (left) and run 2 (right) Figure 3 contains two cactus plots showing the performance obtained on the testing set by the con- straints resulting from two runs of our approach. Each plot shows the number of instances solved by (i) the baseline encoding (original), (i) the baseline encoding combined with each single constraints, (i) the baseline encoding combined with the union of all the constraints produced in the single run and (iv) the VBE, i.e., the best-performing result per instance across all considered variants. While the VBE could solve 22, respectively 20 instances, the original encoding could only solve 17 instances within the time limit. This indicates that different streamlined encodings contribute complementary strengths, as no single encoding strictly dominates across all instances. Table 1 shows the accumulated running times for the two runs, using PAR2 for timeouts. In particular, we observe that most constraints improve 8Streamliners for Answer Set Programming Table 1: Sum of aggregated running times in seconds for all PUP instances. P1P2P3 P1+P2+P3 original VBE run 113,81312,09118,66016,26513,9383,302 P4P5P6 P4+P5+P6 original VBE run 212,88012,09111,69613,62713,9387,412 the accumulated running time on the test instances. Only P3 performed worse overall than the original encoding, since it improved only a few test instances. The VBE indicates a potential reduction by 76% (resp. 47% in run 2). Out of the 26 test instances, 4 instances could not be solved with any encoding and we exclude their PAR 2 times in Table 1. Lifting Symmetry Breaking with Inductive Logic Programming. The work of Tarzariol et al. [33] has a similar target to our approach, namely, to learn first-order constraints preserving the satisfiability of instances drawn from a certain distribution. In particular, one of the problems tackled is PUP, where the instances of the family double showed more difficulty, specifically on satisfiable instances. The con- straints obtained in the work of Tarzariol et al. [33] outperformed our VBE for the first 15 test instances, yielding an improvement of 87% over the original encoding, whereas the VBE achieved improvements of 64% (resp. 62% for the second run). However, they did not manage to return any solution within the considered timeout for the remaining 7 instances. When aggregating running times over all instances using PAR2, the approach performs 22% worse than the original encoding. It is worth noting that our constraints were generated by LLMs without specifying any restrictions in their structure, whereas for the work of Tarzariol et al. [33], a language bias must be provided. As a result, the constraints we learned have a richer structure (e.g., aggregates and mathematical directives such as the increment of numerical variables, built-in comparison operators like “<”, etc.). 4.2 Sokoban Sokoban is a planning problem, where each instance defines the (grid) layout of a room, consisting of walls and locations (possibly designed for storage), and a starting situation describing the position of the agent, called sokoban, and boxes in the room, where each location can hold at most one box. The sokoban can walk on locations (unless occupied by some box), and push single boxes onto unoccupied locations, and the solution of the problem is a sequence of n actions that move all boxes onto storage locations. For this problem, we split the benchmark suite by Bomanson et al. [2] into 10 training instances and 18 test instances. The streamliners obtained in two separate runs, denoted by S1, S2, and S3 or S4, S5, and S6, respec- tively, are shown in Listing 2. The majority of them, namely, S1, S2, S5, and S6, redundantly assert that different kinds of push actions cannot be performed simultaneously. Similarly, the condition expressed by S3, i.e., the target of a push action must contain a box in the next state, is redundant, where also taking the next push action (at time T+1) into account is actually unnecessary. While the constraint S4, which states that a push action should not be immediately reversed, may seem straightforward too, it amounts to a satisfiability-preserving policy rather than a strictly necessary condition. Similar to PUP in the previous subsection, Figure 4 contains two cactus plots showing the perfor- mance obtained on the testing set by the constraints resulting from two runs of our approach. The original encoding could solve 12 instances within the timeout, while we managed to solve 2 more instances when F. Voboril, M. Gebser, S. Szeider & A. Tarzariol9 1 % Constraint S1 2 :- push(X1,Y1,X2,Y2,DX ,DY ,T), push(X3,Y3 ,X4 ,Y4 ,DX,DY,T), X1 < X3. 3 4 % Constraint S2 5 :- push(X1,Y1,X2,Y2,DX ,DY ,T), push(X3,Y3 ,X4 ,Y4 ,DX,DY,T), X1 = X3, Y1 < Y3. 6 7 % Constraint S3 8 :- push(X1,Y1,X2,Y2,DX ,DY ,T), push(X3,Y3 ,X4 ,Y4 ,DX,DY,T+1), X1+Y1 > X3+Y3, 9 not box(X2,Y2 ,T), X2 != X3 , Y2 != Y3. 10 11 % Constraint S4 12 :- push(X1,Y1,X2,Y2,DX ,DY ,T), push(X2,Y2 ,X1 ,Y1 ,ODX ,ODY ,T+1). 13 14 % Constraint S5 15 :- push(X1,Y1,X2,Y2,DX ,DY ,T), push(X1,Y1 ,X3 ,Y3 ,DX,DY,T), X2 = X3, Y2 < Y3. 16 17 % Constraint S6 18 :- push(X1,Y1,X2,Y2 ,1,0,T), push(X3,Y3,X4 ,Y4 ,-1,0,T), X2 = X4 , Y2 < Y4. Listing 2: Sokoban Streamliners Figure 4: Results for Sokoban for run 1 (left) and run 2 (right) Table 2: Sum of running times in seconds for all Sokoban instances. S1S2S3 S1+S2+S3 original VBE run 15,8313,0263,6483,0518,8372,178 S4S5S6 S4+S5+S6 original VBE run 26,9487,19711,7278,1448,8373,758 10Streamliners for Answer Set Programming 1 % Constraint T1 2 :- moved(D1,T-1), moved(D2 ,T), D2 <= D1 , disk(D1+1). 3 4 % Constraint T2 5 stable(1,P,T) :- on(1,P,T), goal_on(1,P), time(T). 6 stable(D,P,T) :- on(D,P,T), goal_on(D,P), stable(D-1,P,T), disk(D), disk(D-1), 7 time(T). 8 :- move(D,P,T), stable(D,P_prev ,T-1), on(D,P_prev ,T-1). 9 10 % Constraint T3: a comment 11 12 % Constraint T4 13 :- disk(D), move(D,P1 ,T1), move(D,P2,T2), move(D,P1,T3), T1 < T2, T2 < T3, 14 T3 = T2 + 1, P1 = P2. 15 16 % Constraint T5 17 :- move(D1,P1,T), move(D2 ,P2,T+1), D1 < D2, on(D1,Px ,T-1), on(D2,Py,T), 18 Px = Py, P1 != Py, P2 = Px. 19 20 % Constraint T6 21 :- time(T), T > 2, move(D,P1,T-1), move(D,P2,T-2), P1 = P2, move(D,P1 ,T). Listing 3: Towers of Hanoi Streamliners considering S2, S3, or the combination of all three constraints from the first run. Regarding the second run, only the VBE solved 14 instances. Table 2 shows the accumulated running times in seconds for the instances solved with at least one encoding; thus leaving out 4 of the 18 test instances. In particular, the table shows that the VBE in the first run indicates a 75% reduction in running time compared to the original encoding, while in the second run it indicates a 57% reduction. 4.3 Towers of Hanoi The Towers of Hanoi is a puzzle where the input is the initial configuration of n disks of different sizes in 3 pegs. Usually, in the initial configuration, the disks are all placed in the first peg. The goal is to find a sequence of movements of the disks, such that all disks are moved from the first peg to the third one. Only the topmost disk of a peg can be moved at a time, and a disk cannot be moved to a peg already containing a disk of a smaller size. We synthetically generated 11 trivial instances for training, while 46 test instances were drawn from the work of Gebser et al. [13]. Listing 3 presents the streamliners T1, T2, and T3, obtained in the first run, and the streamliners T4, T5, and T6 from the second run. Notably, T3 is not an actual constraint but merely a comment (thus violating the instructions of Step 3 in Section 3). Adding such a comment does not affect the solver performance. However, due to minor measurement noise in the running times of the training instances, selecting T1 and T2 (along with a comment T3) was apparently better for the performance than selecting a third proper constraint. While the constraints T4, T5, and T6 seem complex, all three reject redundant null moves placing a disk back on its current peg, which is already prohibited by the encoding because the current peg is not a valid target for moving a disk. The constraint T1 is also redundant yet less straightforward by asserting the implied condition that a disk cannot be moved when the two other pegs are already occupied by smaller disks. 1 Interestingly, T2 constitutes a subprogram 1 If D1 = D2, T1 asserts the policy that a disk should not be moved and immediately placed back on its previous peg. F. Voboril, M. Gebser, S. Szeider & A. Tarzariol11 Figure 5: Results for Towers of Hanoi for run 1 (left) and run 2 (right) defining the auxiliary predicate stable to identify disks that have reached their goal configuration. Along with a constraint rejecting further moves of such disks, the streamliner T2 imposes the policy to preserve already established parts of the goal configuration. 2 The cactus plot in Figure 5 and the accumulated running times in Table 3 clearly show that the original encoding performed worse than all streamlined encodings and the VBE in particular. While the original encoding only solved 31 instances within the timeout, the VBE could solve all 46 test instances in both runs. Further, it could reduce the running time by 79%, resp. 71% in the second run. 4.4 Analysis of Streamliners Within the 30 minutes allocated to training, our pipeline (cf. Figure 1) performed between 10 and 29 LLM calls. The amount of LLM calls in each run primarily depends on the number and size of training instances. Comparing the generated streamliners, 52% resulted in performance improvements on the training instances. In contrast, 19% produced syntax errors, 9% led to unsatisfiability on all training instances, and a further 8% rendered some (but not all) training instances unsatisfiable. The remaining 12% neither caused unsatisfiability nor improved upon the baseline performance. While the selected streamliners empirically improve the performance of Clingo, at least on the train- ing instances, we find that they often have quadratic grounding size or can be strengthened by dropping unnecessary side conditions. The PUP constraint P2 is an example of quadratic grounding size, as it is formulated over pairs U1 > U2 of units. Its manual reformulation, denoted by P2r, achieves linear 2 Similar ideas have been incorporated, e.g., in Blocksworld planning encodings [11], but we are unaware of any Towers of Hanoi encoding in the ASP literature from which the LLM could have directly retrieved T2. Table 3: Sum of running times in seconds for all Towers of Hanoi instances. T1T2T3T1+T2 original VBE run 115,10849,494-13,70256,71011,833 T4T5T6 T4+T5+T6 original VBE run 220,85323,83242,56924,75556,71016,053 12Streamliners for Answer Set Programming Table 4: Comparison of original and revised constraints for PUP, Sokoban, and Towers of Hanoi. P1P1rP2P2rP6P6r PUP13,813 13,810 12,091 13,862 11,696 12,077 S1S1rS2S2rS3S3rS5S5rS6S6r Sokoban 5,83113,5783,02610,1013,6489,0107,1979,532 11,727 10,422 T1T1rT2T2rT4T4rT5T5rT6T6r Hanoi15,108 34,236 49,494 56,211 20,853 52,795 23,832 57,188 42,569 52,795 grounding size by using a #count aggregate to express the same condition as P2. Side conditions are, e.g., dropped from the Sokoban constraint S3, where omitting the reference to a second push action yields the stronger, manually revised constraint S3r. Our manually revised versions of generated streamliners, pro- vided whenever the grounding size or side conditions can be reduced, are detailed in our repository [36]. Table 4 contrasts the sum of running times in seconds obtained with the original and our manually revised constraints. Although the revised constraints should have generally better scaling behavior, we observe a deterioration of Clingo’s running times in almost all cases. This comes unexpectedly and shows that the StreamLLM pipeline effectively selects streamliners that empirically improve the solver performance on the training and test instances. On the one hand, #count aggregates in our grounding size-oriented revisions can be more demanding to propagate than (a quadratic number of) “flat” integrity constraints. On the other hand, adding redundant constraints that are also implied by a problem encoding may negatively affect the solver’s internal heuristics, so that strengthening them does not guarantee better performance. From the negative results for our manually revised constraints, we conclude that the empirical approach of the StreamLLM pipeline manages to tune the solver performance better than general scaling considerations. 5 Conclusion This paper presented the first approach of LLM-based streamliner generation to ASP. Overall, the results demonstrate that our approach is a viable and powerful tool for improving ASP solving performance. We showed that LLMs can propose syntactically valid and semantically meaningful constraints that ef- fectively prune the search space. By filtering candidate streamliners and selecting the best-performing ones, we obtain a set of complementary variants. Evaluating these using a VBE shows runtime reduc- tions of 47%-79%, with most cases exceeding 70%, indicating substantial potential speedups if the best encoding can be selected per instance. Moreover, in line with earlier findings by Voboril et al. [38], our results suggest that only a small number of simple training instances is sufficient to guide effective streamliner generation, which is particularly encouraging for ASP where large curated training sets are costly. Several directions for future work remain. First, the approach should be evaluated on a broader range of ASP benchmarks, including larger instance families and additional domains, to better under- stand its generality and limits. Second, the quality of generated streamliners may be improved through model adaptation techniques such as fine-tuning or knowledge distillation, as well as more advanced prompt-optimization methods (e.g., by prompt learning or a combination with symbolic methods). Fi- nally, extending the method to optimization problems, in line with recent work by Voboril et al. [37], is a natural and important next step for ASP. F. Voboril, M. Gebser, S. Szeider & A. Tarzariol13 6 Acknowledgment This research was funded by the Austrian Science Fund (FWF) projects 10.55776/PAT1599524, 10.55776/COE12 and 10.55776/P36420. References [1] Markus Aschinger, Conrad Drescher, Gerhard Friedrich, Georg Gottlob, Peter Jeavons, Anna Ryabokon & Evgenij Thorstensen (2011): Optimization Methods for the Partner Units Problem. In: Integration of AI and OR Techniques in Constraint Programming, CPAIOR 2011, Lecture Notes in Computer Science 6697, Springer, p. 4–19, doi:10.1007/978-3-642-21311-3_4. [2] J. Bomanson, M. Gebser, T. Janhunen, B. Kaufmann & T. Schaub (2016): Answer Set Programming Modulo Acyclicity. Fundamenta Informaticae 147(1), p. 63–91, doi:10.3233/FI-2016-1398. [3] Francesco Calimeri, Wolfgang Faber, Martin Gebser, Giovambattista Ianni, Roland Kaminski, Thomas Krennwallner, Nicola Leone, Marco Maratea, Francesco Ricca & Torsten Schaub (2020):ASP- Core-2 Input Language Format.Theory and Practice of Logic Programming 20(2), p. 294–309, doi:10.1017/S1471068419000450. [4] Francesco Calimeri, Giovambattista Ianni & Francesco Ricca (2014):The third open answer set programming competition.Theory and Practice of Logic Programming 14(1), p. 117–135, doi:10.1017/S1471068412000105. [5] Paola Cappanera, Marco Gavanelli, Maddalena Nonato & Marco Roma (2023): Logic-Based Benders De- composition in Answer Set Programming for Chronic Outpatients Scheduling. Theory and Practice of Logic Programming 23(4), p. 848–864, doi:10.1017/s147106842300025x. [6] Erica Coppolillo, Francesco Calimeri, Giuseppe Manco, Simona Perri & Francesco Ricca (2024): LLASP: Fine-tuning Large Language Models for Answer Set Programming. In: Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning, KR 2024, doi:10.24963/kr.2024/78. [7] Jo Devriendt & Bart Bogaerts (2016): BreakID: Static Symmetry Breaking for ASP (System Description). CoRR abs/1608.08447. arXiv:1608.08447. [8] Jo Devriendt, Bart Bogaerts, Maurice Bruynooghe & Marc Denecker (2016): On local domain sym- metry for model expansion.Theory and Practice of Logic Programming 16(5-6), p. 636–652, doi:10.1017/S1471068416000508. [9] Christian Drescher, Oana Tifrea & Toby Walsh (2011): Symmetry-breaking answer set solving. AI Commun. 24(2), p. 177–194, doi:10.3233/AIC-2011-0495. [10] M. Gebser, A. Harrison, R. Kaminski, V. Lifschitz & T. Schaub (2015): Abstract Gringo. Theory and Practice of Logic Programming 15(4-5), p. 449–463, doi:10.1017/S1471068415000150. [11] M. Gebser, R. Kaminski, B. Kaufmann & T. Schaub (2012): Answer Set Solving in Practice. Morgan and Claypool Publishers, doi:10.1007/978-3-031-01561-8. [12] Martin Gebser, Roland Kaminski, Benjamin Kaufmann, Patrick Lühne, Javier Romero & Torsten Schaub (2016): Answer Set Solving with Generalized Learned Constraints. In: Technical Communications of the 32nd International Conference on Logic Programming, ICLP 2016, OASIcs 52, Schloss Dagstuhl - Leibniz- Zentrum für Informatik, p. 9:1–9:15, doi:10.4230/OASIcs.ICLP.2016.9. [13] Martin Gebser, Roland Kaminski, Benjamin Kaufmann & Torsten Schaub (2019): Multi-shot ASP solving with clingo. Theory and Practice of Logic Programming 19(1), p. 27–82, doi:10.1017/S1471068418000054. [14] Martin Gebser, Benjamin Kaufmann & Torsten Schaub (2012): Conflict-driven answer set solving: From theory to practice. Artif. Intell. 187, p. 52–89, doi:10.1016/j.artint.2012.04.001. [15] Michael Gelfond & Vladimir Lifschitz (1991): Classical Negation in Logic Programs and Disjunctive Databases. New Gener. Comput. 9(3/4), p. 365–386, doi:10.1007/BF03037169. 14Streamliners for Answer Set Programming [16] Carla P. Gomes & Meinolf Sellmann (2004): Streamlined Constraint Reasoning. In Mark Wallace, editor: Principles and Practice of Constraint Programming - CP 2004, Lecture Notes in Computer Science 3258, Springer, p. 274–289, doi:10.1007/978-3-540-30201-8_22. [17] Holger H. Hoos, Roland Kaminski, Marius Lindauer & Torsten Schaub (2015): aspeed: Solver schedul- ing via answer set programming.Theory and Practice of Logic Programming 15(1), p. 117–142, doi:10.1017/S1471068414000015. [18] Matej Husár, Jirí Svancara, Philipp Obermeier, Roman Barták & Torsten Schaub (2022): Reduction- based Solving of Multi-agent Pathfinding on Large Maps Using Graph Pruning. In: 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022, IFAAMAS, p. 624–632, doi:10.5555/3535850.3535921. [19] Adam Ishay, Zhun Yang & Joohyung Lee (2023): Leveraging Large Language Models to Generate Answer Set Programs. In: Proceedings of the 20th International Conference on Principles of Knowledge Represen- tation and Reasoning, KR 2023, p. 374–383, doi:10.24963/kr.2023/37. [20] Mark Law (2023): Conflict-Driven Inductive Logic Programming. Theory and Practice of Logic Program- ming 23(2), p. 387–414, doi:10.1017/S1471068422000011. [21] Kevin Leo, Graeme Gange, Maria Garcia de la Banda & Mark Wallace (2024): Automatic Core-Guided Reformulation via Constraint Explanation and Condition Learning. In: Proceedings of the AAAI Conference on Artificial Intelligence, AAAI 2024, AAAI Press, p. 8065–8072, doi:10.1609/aaai.v38i8.28645. [22] Vladimir Lifschitz, Patrick Lühne & Torsten Schaub (2019): Verifying Strong Equivalence of Programs in the Input Language of gringo. In: Logic Programming and Nonmonotonic Reasoning - 15th International Con- ference, LPNMR 2019, Lecture Notes in Computer Science 11481, Springer, p. 270–283, doi:10.1007/978- 3-030-20528-7_20. [23] Marco Maratea, Luca Pulina & Francesco Ricca (2014): A Multi-Engine Approach to Answer-Set Program- ming. Theory and Practice of Logic Programming 14(6), p. 841–868, doi:10.1017/S1471068413000094. [24] Javier Romero, Torsten Schaub & Klaus Strauch (2025): On the Generalization of Learned Constraints for ASP Solving in Temporal Domains. Theory and Practice of Logic Programming 25(2), p. 197–224, doi:10.1017/s1471068424000462. [25] Karem A. Sakallah (2009): Symmetry and Satisfiability. In Armin Biere, Marijn Heule, Hans van Maaren & Toby Walsh, editors: Handbook of Satisfiability, Frontiers in Artificial Intelligence and Applications 185, IOS Press, p. 289–338, doi:10.3233/978-1-58603-929-5-289. [26] Manuel A. Borroto Santana, Irfan Kareem & Francesco Ricca (2024): Towards Automatic Composition of ASP Programs from Natural Language Specifications. In: Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI 2024, ijcai.org, p. 6198–6206. Available at https: //w.ijcai.org/proceedings/2024/685. [27] Arseny Skryagin, Daniel Ochs, Phillip Deibert, Simon Kohaut, Devendra Singh Dhami & Kristian Ker- sting (2024): Answer Set Networks: Casting Answer Set Programming into Deep Learning.CoRR abs/2412.14814, doi:10.48550/arXiv.2412.14814. arXiv:2412.14814. [28] Patrick Spracklen, Nguyen Dang, Özgür Akgün & Ian Miguel (2023): Automated streamliner portfolios for constraint satisfaction problems. Artif. Intell. 319, p. 103915, doi:10.1016/j.artint.2023.103915. [29] Stefan Szeider (2025): ASP-Bench: Problems, Ground Truths, and Solutions, doi:10.5281/zenodo.18062939. Available at https://doi.org/10.5281/zenodo.18062939. [30] Stefan Szeider (2025): Bridging Language Models and Symbolic Solvers via the Model Context Protocol. In: 28th International Conference on Theory and Applications of Satisfiability Testing, SAT 2025, LIPIcs 341, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 30:1–30:12, doi:10.4230/LIPIcs.SAT.2025.30. [31] Alice Tarzariol, Martin Gebser & Konstantin Schekotihin (2022): Lifting symmetry breaking constraints with inductive logic programming. Mach. Learn. 111(4), p. 1303–1326, doi:10.1007/s10994-022-06146-3. [32] Alice Tarzariol, Martin Gebser, Konstantin Schekotihin & Mark Law (2023): Learning to Break Symmetries for Efficient Optimization in Answer Set Programming. In Brian Williams, Yiling Chen & Jennifer Neville, F. Voboril, M. Gebser, S. Szeider & A. Tarzariol15 editors: Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI 2023, AAAI Press, p. 6541– 6549, doi:10.1609/aaai.v37i5.25804. [33] Alice Tarzariol, Konstantin Schekotihin, Martin Gebser & Mark Law (2022): Efficient Lifting of Symmetry Breaking Constraints for Complex Combinatorial Problems. Theory and Practice of Logic Programming 22(4), p. 606–622, doi:10.1017/S1471068422000151. [34] Richard Taupe, Antonius Weinzierl & Gerhard Friedrich (2020): Conflict Generalisation in ASP: Learning Correct and Effective Non-Ground Constraints. Theory and Practice of Logic Programming 20(5), p. 799– 814, doi:10.1017/S1471068420000368. [35] Erich Christian Teppan, Gerhard Friedrich & Georg Gottlob (2016): Tractability frontiers of the partner units configuration problem. J. Comput. Syst. Sci. 82(5), p. 739–755, doi:10.1016/j.jcss.2015.12.004. [36] Florentina Voboril, Martin Gebser, Stefan Szeider & Alice Tarzariol (2026): Code and Instances for the Paper: Streamliners for Answer Set Programming, doi:10.5281/zenodo.18378760. [37] Florentina Voboril, Vaidyanathan Peruvemba Ramaswamy & Stefan Szeider (2025): Balancing Latin Rectan- gles with LLM-Generated Streamliners. In Maria Garcia de la Banda, editor: 31st International Conference on Principles and Practice of Constraint Programming, CP 2025, LIPIcs 340, Schloss Dagstuhl - Leibniz- Zentrum für Informatik, p. 36:1–36:17, doi:10.4230/LIPIcs.CP.2025.36. [38] Florentina Voboril, Vaidyanathan Peruvemba Ramaswamy & Stefan Szeider (2025): Generating Streamlin- ing Constraints with Large Language Models. J. Artif. Intell. Res. 84, doi:10.1613/jair.1.18965. [39] Toby Walsh (2012): Symmetry Breaking Constraints: Recent Results. In: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2012, AAAI Press, doi:10.1609/AAAI.V26I1.8437. [40] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Richter, Fei Xia, Ed Chi, Quoc V Le & Denny Zhou (2022): Chain-of-Thought Prompting Elicits Reasoning in Large Language Models. In: Advances in Neural Information Processing Systems, 35, Curran Associates, Inc., p. 24824–24837. [41] Antonius Weinzierl (2013): Learning non-ground rules for answer-set solving. In: 2nd Workshop on Ground- ing and Transformations for Theories With Variables (GTTV’13), p. 13. [42] Zhun Yang, Adam Ishay & Joohyung Lee (2020): NeurASP: Embracing Neural Networks into Answer Set Programming. In: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, ijcai.org, p. 1755–1762, doi:10.24963/ijcai.2020/243. [43] Anssi Yli-Jyrä, Masood Feyzbakhsh Rankooh & Tomi Janhunen (2023): Pruning Redundancy in Answer Set Optimization Applied to Preventive Maintenance Scheduling. In: PADL 2023, Lecture Notes in Computer Science, Springer, p. 279–294, doi:10.1007/978-3-031-24841-2_18. 16Streamliners for Answer Set Programming A Encodings This section illustrates the encodings used for the three domains studied in the paper; in particular, it provides an intuition for the meaning of the predicates appearing in the streamliners returned by our approach. Partner Units Problem (PUP). The baseline PUP encoding is derived from Aschinger et al.[1] and is illustrated in Listing 4. The instance provides atoms of the form zone2sensor/2, representing the bi- partite input graph, and atoms of the form comUnit/1 representing the ID of the (communication) units. Morevoer, the constants UCAP and IUCAP are defined via the atom maxElements(M) with M=UCAP and maxPU(M) with M=IUCAP. The encoding then defines the assignments of units to zones via unit2zone/2 and units to sensors via unit2sensors/2, as well as the condition for two units to be partners with atoms of the form partnerunits/2. The constraints introduced guarantee that the conditions specified in the problem hold. 1 zone(Z) :- zone2sensor(Z,D). 2 sensor(D) :- zone2sensor(Z,D). 3 4 1 unit2zone(U,Z) : comUnit(U) 1 :- zone(Z). 5 1 unit2sensor(U,S) : comUnit(U) 1 :- sensor(S). 6 :- comUnit(U), maxElements(M), M+1 unit2zone(U,Z): zone(Z) . 7 :- comUnit(U), maxElements(M), M+1 unit2sensor(U,S): sensor(S) . 8 partnerunits(U,P) :- unit2zone(U,Z), zone2sensor(Z,S), unit2sensor(P,S), U!=P. 9 partnerunits(U,P) :- partnerunits(P,U), comUnit(U), comUnit(P). 10 :- comUnit(U), maxPU(M), M+1 partnerunits(U,P): comUnit(P) . Listing 4: Baseline Encoding for PUP. 1 time (1..T) :- moves(T). 2 on(D,P,0) :- init_on(D,P). 3 4 move(D,P,T) : disk(D), peg(P) = 1 :- time(T). 5 6 moved(D,T) :- move(D,P,T). 7 8 blocked(D,P,T) :- on(D,P,T-1), time(T). 9 blocked(D,P,T) :- blocked(D+1,P,T), disk(D). 10 11 :- move(D,P,T), blocked(D,P,T). 12 :- moved(D,T), on(D,P,T-1), blocked(D+1,P,T). 13 14 on(D,P,T) :- move(D,P,T). 15 on(D,P,T) :- on(D,P,T-1), time(T), not moved(D,T). 16 17 :- goal_on(D,P), moves(T), not on(D,P,T). 18 19 #show move /3. Listing 5: Baseline Encoding for Towers of Hanoi. F. Voboril, M. Gebser, S. Szeider & A. Tarzariol17 Towers of Hanoi. The baseline encoding for Towers of Hanoi is illustrated in Listing 5. The instance provides atoms of the form disk/1 and peg/1 representing the identifier of disks and pegs, respectively; atoms of the form init_on/2 and goal_on/2 indicating the initial positions (i.e. disk) in which the pegs are arranged, and their goal positions, respectively. Moreover, an atom of the form moves/1 represents the maximal time horizon considered. The encoding defines the output predicate move/3 representing the possible action for the problem, specifically move(D,P,T) means that at time T, the disk D is moved to peg P. A set of auxiliary predicates defines useful relations used in constraints to produce a plan that respects the rules of the problem. Among them, moved/2 projects the atoms of the form move/3, by removing the argument representing the target peg; on(D,P,T) means that at time T the disk D is placed on peg P; while lastly time/1 contains all the possible values included in the interval from 1 to T where is the argument of the input atom moves(T). Sokoban. The baseline encoding for Sokoban is illustrated in Listing 6. The instance provides atoms of the form square/2, initial_box/2, and target_square/2, representing the grid coordinates, the initial positions of the boxes, and their goal positions, respectively. Moreover, an atom of the form steps/1 represents the maximal time horizon considered. The Sokoban encoding defines the output predicate push/7 representing the possible action of the Sokoban where push(X1,Y1,X2,Y2,DX,DY,T) means that at time T, the agent pushes a box placed in the coordinate (X1,Y1) into an adjacent coordinate (X2,Y2) by pushing it with a direction (DX,DY) (where e.g., (0,1) means up, (1,0) means right, etc.). A set of auxiliary predicates (e.g., next/6, from/5, from/3, etc.) defines useful relations used in constraints to produce a plan that respects the rules of the problem. Among them, box(X,Y,T) represent that at time T a box is placed in the coordinate (X,Y). B Manual Revision of Streamliners Tables 5, 6, and 7 contrast the streamliners for PUP, Sokoban, or Towers of Hanoi, respectively, with our manual reformulations, experimentally compared in Section 4.4. The primary objective of these reformulations is to reduce the grounding size, e.g., by turning constraint P2 / P5 over pairs U1 > U2 of units into P2r / P5r, where a #count aggregate lists each unit U only once (cf. Table 5). 3 For each sensor S, this reformulation yields linear rather than quadratic grounding size in terms of the number of units. In some cases, our reformulations also strengthen the original streamliners by dropping unnecessary side conditions. For example, the reformulation S3r of constraint S3 expresses that the target of a push action in Sokoban always contains a box in the next state, while S3 unnecessarily takes another push action into account as well (cf. Table 6). Similarly, the reformulations T2r, T4r / T6r, and T5r eliminate redundancies in constraints T2, T4, T5, and T6 for Towers of Hanoi, where the a priori different streamliners T4 and T6 are condensed to the same revised constraint T4r / T6r (cf. Table 7). We do not reformulate constraints P3, P4, and S4 as neither the grounding size nor redundancies can be cut down for them, and T3 is not listed in Table 7 because it is a comment that was produced by the LLM. 3 The streamliners P2 and P5, generated in separate runs for PUP, are identical and thus have the same reformulation. 18Streamliners for Answer Set Programming 1 diff (0,1;1,0;0,-1;-1,0). 2 3 next(X1 ,Y1 ,X2,Y2,DX,DY) :- square(X1,Y1), diff(DX,DY), 4 square(X2 ,Y2), X2 = X1+DX , Y2 = Y1+DY. 5 next(X2 ,Y2 ,DX,DY) :- next(X1 ,Y1,X2,Y2,DX,DY). 6 7 path(X1 ,Y1 ,X2,Y2,DX,DY) :- next(X1,Y1,X2 ,Y2 ,DX ,DY), next(X1 ,Y1 ,DX ,DY). 8 path(X1 ,Y1 ,X2,Y2,DX,DY) :- path(X1,Y1,X3 ,Y3 ,DX ,DY), next(X3 ,Y3 ,X2 ,Y2,DX,DY). 9 10 step (1..T) :- steps(T). 11 12 box(X,Y,0) :- initial_box(X,Y). 13 14 push(X1 ,Y1,X2,Y2,DX,DY ,T) : path(X1,Y1 ,X2 ,Y2 ,DX,DY) 1 :- step(T). 15 16 from(X1 ,Y1 ,DX,DY,T) :- push(X1,Y1,X2,Y2 ,DX ,DY ,T). 17 from(X1 ,Y1 ,T) :- from(X1 ,Y1 ,DX,DY,T). 18 19 :- from(X,Y,T), not box(X,Y,T-1). 20 21 todo(T) :- target_square(X,Y), step(T), not box(X,Y,T-1). 22 23 :- todo(T), not from(X,Y,T) : square(X,Y). 24 25 box(X2 ,Y2 ,T) :- push(X1 ,Y1 ,X2,Y2,DX,DY,T). 26 box(X1 ,Y1 ,T) :- box(X1 ,Y1 ,T-1), step(T), not from(X1,Y1 ,T). 27 28 :- target_square(X,Y), steps(T), not box(X,Y,T). 29 30 free(X2 ,Y2 ,DX,DY,T) :- next(X1,Y1,X2,Y2 ,DX ,DY), from(X1,Y1 ,DX ,DY ,T). 31 free(X2 ,Y2 ,DX,DY,T) :- next(X1,Y1,X2,Y2 ,DX ,DY), free(X1,Y1 ,DX ,DY ,T), 32 not box(X1,Y1 ,T). 33 34 :- free(X,Y,DX,DY,T), box(X,Y,T-1). 35 36 reach(X1 ,Y1 ,1) :- initial_at(X1,Y1), step (1). 37 reach(X1 ,Y1,T) :- from(X1 ,Y1,T-1), step(T). 38 reach(X2 ,Y2,T) :- next(X1 ,Y1,X2,Y2,DX,DY), reach(X1,Y1,T), not box(X2,Y2,T-1). 39 40 :- next(X1,Y1,X2,Y2,DX ,DY), from(X2,Y2,DX ,DY ,T), not reach(X1 ,Y1 ,T). 41 42 boxes(N) :- N = #countX,Y : initial_box(X,Y). 43 44 :- step(T), boxes(N), #countX,Y : box(X,Y,T) != N. 45 46 #show push /7. Listing 6: Baseline Encoding for Sokoban. F. Voboril, M. Gebser, S. Szeider & A. Tarzariol19 Table 5: Manually revised versions of streamliners for PUP. Constraint(Re)formulation P1 :- comUnit(U), #countZ: unit2zone(U,Z) = 0, #countS: unit2sensor(U,S) > 0. P1r :- unit2sensor(U,_), not unit2zone(U,_). P2 / P5 :- unit2sensor(U1,S), unit2sensor(U2,S), U1 > U2. P2r / P5r :- sensor(S), #countU: unit2sensor(U,S) > 1. P3 :- unit2zone(U+1,_), not unit2zone(U,_), comUnit(U), comUnit(U+1). P4 :- comUnit(U), unit2zone(U,Z1), unit2zone(U,Z2), Z1 < Z2, #countS : zone2sensor(Z1,S), zone2sensor(Z2,S) = 0. P6 :- comUnit(U1), comUnit(U2), U1 < U2, sensor(S), S = #minS’: sensor(S’), unit2sensor(U2,S), #countZ: unit2zone(U1,Z) = 0. P6r mark(U):- comUnit(U), unit2sensor(U+1,S), S = #minX: sensor(X). mark(U):- comUnit(U), mark(U+1). :- mark(U), not unit2zone(U,_). Table 6: Manually revised versions of streamliners for Sokoban. Constraint(Re)formulation S1 :- push(X1,Y1,X2,Y2,DX,DY,T), push(X3,Y3,X4,Y4,DX,DY,T), X1 < X3. S1r :- diff(DX,DY), step(T), #countX1 : push(X1,Y1,X2,Y2,DX,DY,T) > 1. S2 :- push(X1,Y1,X2,Y2,DX,DY,T), push(X3,Y3,X4,Y4,DX,DY,T), X1 = X3, Y1 < Y3. S2r :- diff(DX,DY), step(T), square(X,Y), #countY1 : push(X,Y1,X2,Y2,DX,DY,T) > 1. S3 :- push(X1,Y1,X2,Y2,DX,DY,T), push(X3,Y3,X4,Y4,DX,DY,T+1), X1+Y1 > X3+Y3, not box(X2,Y2,T), X2 != X3, Y2 != Y3. S3r :- push(X1,Y1,X2,Y2,DX,DY,T), not box(X2,Y2,T). S4 :- push(X1,Y1,X2,Y2,DX,DY,T), push(X2,Y2,X1,Y1,ODX,ODY,T+1). S5 :- push(X1,Y1,X2,Y2,DX,DY,T), push(X1,Y1,X3,Y3,DX,DY,T), X2 = X3, Y2 < Y3. S5r :- path(X1,Y1,X1,Y,DX,DY), step(T), #countY2 : push(X1,Y1,X1,Y2,DX,DY,T) > 1. S6 :- push(X1,Y1,X2,Y2,1,0,T), push(X3,Y3,X4,Y4,-1,0,T), X2 = X4, Y2 < Y4. S6r stop(X2,Y2,DX,0,T):- push(X1,Y1,X2,Y2,DX,0,T). :- stop(X,Y1,1,0,T), stop(X,Y2,-1,0,T), Y1 < Y2. 20Streamliners for Answer Set Programming Table 7: Manually revised versions of streamliners for Towers of Hanoi. Constraint(Re)formulation T1 :- moved(D1,T-1), moved(D2,T), D2 <= D1, disk(D1+1). T1r mark(D,T):- moved(D,T-1), time(T), disk(D+1). mark(D,T):- mark(D+1,T), disk(D). :- mark(D,T), moved(D,T). T2 stable(1,P,T):- on(1,P,T), goal_on(1,P), time(T). stable(D,P,T):- on(D,P,T), goal_on(D,P), stable(D-1,P,T), disk(D), disk(D-1), time(T). :- move(D,P,T), stable(D,P_prev,T-1), on(D,P_prev,T-1). T2r stable(1,P,T):- on(1,P,T-1), goal_on(1,P). stable(D,P,T):- on(D,P,T-1), goal_on(D,P), stable(D-1,P,T). :- moved(D,T), stable(D,P,T). T4 :- disk(D), move(D,P1,T1), move(D,P2,T2), move(D,P1,T3), T1 < T2, T2 < T3, T3 = T2 + 1, P1 = P2. T4r / T6r :- move(D,P,T), move(D,P,T+1). T5 :- move(D1,P1,T), move(D2,P2,T+1), D1 < D2, on(D1,Px,T-1), on(D2,Py,T), Px = Py, P1 != Py, P2 = Px. T5r :- move(D,P,T), on(D,P,T-1). T6 :- time(T), T > 2, move(D,P1,T-1), move(D,P2,T-2), P1 = P2, move(D,P1,T).