Self-Guiding Exploration for Combinatorial Problems
Authors: Zangir Iklassov
Yali Du
Farkhad Akimov
Martin Takáč
Venue: NeurIPS 2024 poster (2024)
Keywords: combinatorial problems
combinatorial optimization
LLM  prompting strategies
LLM thought exploration
Primary area: other
TL;DR: We introduce Self-Guiding Exploration (SGE) for LLMs, boosting combinatorial problem-solving by 27.84% and increasing reasoning task accuracy by 2.46%.

Abstract: Large Language Models (LLMs) have become pivotal in addressing reasoning tasks across diverse domains, including arithmetic, commonsense, and symbolic reasoning. They utilize prompting techniques such as Exploration-of-Thought, Decomposition, and Refinement to effectively navigate and solve intricate tasks. Despite these advancements, the application of LLMs to Combinatorial Problems (CPs), known for their NP-hardness and critical roles in logistics and resource management remains underexplored. To address this gap, we introduce a novel prompting strategy: Self-Guiding Exploration (SGE), designed to enhance the performance of solving CPs. SGE operates autonomously, generating multiple thought trajectories for each CP task. It then breaks these trajectories down into actionable subtasks, executes them sequentially, and refines the results to ensure optimal outcomes. We present our research as the first to apply LLMs to a broad range of CPs and demonstrate that SGE outperforms existing prompting strategies by over 27.84% in CP optimization performance. Additionally, SGE achieves a 2.46% higher accuracy over the best existing results in other reasoning tasks (arithmetic, commonsense, and symbolic).

Self-Guiding Exploration for Combinatorial Problems
Zangir Iklassov
Yali Du
MBZUAI zangir. ikl ikllassov@mzuua.. ac. ae
King's College London yali f.li.du@kcl.. ac. uk
Farkhad Akimov MBZUAI farkhad www.aawmmwuaii.....m..m ac
Martin Takáč MBZUAI
martin www.ttaaammmbuua...mm ac
Abstract
Large Language Models (LLMs) have become pivotal in addressing reasoning tasks across diverse domains, including arithmetic,, commonsense, and symbolic reasoning. They utilize prompting techniques such Decomposition, and Refinement to effectively navigate and solve intricate tasks. Despite these advancements, the application of L.MMs Combinatorial Problems (CPs), known for their NP-hardness and critical roles logistics and resource management remains underexplored. To address this gap, introduce novel prompting strategy: Self-Guiding Exploration (SGE), designed to enhance the performance of solving CPs. SGE operates autonomously, generating multiple thought trajectories for each CP task. It then breaks these trajectories down into actionable subtasks, executes them sequentially, and refines the results to ensure optimal outcomes. We present our research as the first to apply LLMs to a broad range of CPs and demonstrate that SGE outperforms existing prompting strategies by over 27.84% in CP optimization performance. Additionally, SGE achieves 2.46% higher accuracy over the best existing results other reasoning tasks (arithmetic, commonsense, and symbolic).
Introduction
Large Language Models (LLMs) have emerged as powerful tools capable of executing reasoning tasks across various domains, including arithmetic, commonsense, and symbolic reasoning 4 33 5 27 These models may leverage prompting techniques such as Exploration-of-Thool
[39 13
Decomposition [49 [2] and Refinement [19 to break down and solve various tasks in step-by-
step manner. Recent research has been directed towards extending these techniques to tackle more sophisticated optimization challenges [41. Combinatorial problems (CPs) may represent a category of these complex optimization tasks, associated with intricate computational challenges.
Combinatorial Problems are characterized by their NP-hardness and inherent complexity, which result an exponential growth in the number of potential solutions. This complexity presents substantial challenges in the research 26 25 [O]. CPs are especially crucial in sectors that require efficient logistics, planning, and scheduling. Currently, the dominant approach in these industries involves metaheuristic methods. These methods combine various simple but fast heuristics to effectively tackle CPs within specific constraints. Nonetheless, the effectiveness of these heuristics can vary significantly depending on the CP task and its associated constraints, necessitating customized selection of heuristies achieve optimal performance.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In the meantime, research on exploring LLMs to solve CPs reveals substantial gaps. While recent advancements indicate the effectiivnness of LLMs in various reasoning tasks G8
47
32 49 their
application to CPs has been minimal. The literature indicates that existing generative models can address smaller instances of the Traveling Salesman Problem (TSP) 16 23 However, as problem sizes increase, existing prompting strategies begin to yield inadequate responses, underscoring the need for more sophisticated prompting methods. Moreover, there is a notable scarcity of research addressing other complex CPs, particularly the Vehicle Routing and Job Scheduling Problems, which pose significant challenges in logistics, planning industries, and operations research.
In this work, we introduce a novel prompting strategy: self geff-guiding exploration (SGE), designed to enhance the coablem-solvingg process for CPs. This algorithm works as a combination of exploration- of- of-thought, decomposition, and refinement prompting methods. The SGE approach autonomously generates multiple thought trajectories for a given CP, each trajectory representing a specific heuristic to tackle the given task. Each trajectory is then decomposed into subtasks, which are executed one by one, and their outputs are refined and combined into a final solution. Unlike the task-specific prompts utilized in other methods, SGE employs general-puryy purposs prompts, allowing for the adaptive use of specific heuristic solutions tailored to various CPs, such as the Hungarian heuristic for the assignment problem and the Nearest Neighbor heuristic for the vehicle routing problem. Essentially, SGE acts as a versatile metaheuristic capable of identifying, combining, and refining task- susc-specific heuristics for individual CP tasks.
Our work makes following contributions. Firstly, we present a novel investigation into the appli- cation of large language models for solving combinatorial problems. Secondly, we introduce new prompting strategy, SGE, that autonomosly generates thought trajectories, splits them into subtasks and refines the answers. Thirdly, we demonstrate that SGE outperforms existing prompting strate- gies such as Chain-of of -ie---f-Tohuue Thought, Decomposition, and Self- Reff-Refinemnt,, improving CP optimization performance by 27.8 27.84%. Lastly, we validate the applicability of SGE across other reasoning tasks, including arithmetic, commonsense, and symbolic tasks, where our method achieves a 2.46% higher accuracy than the best existing results.
2 Related work
CP via classical approach. In classical research, combinatorial problems are predominantly tackled using heuristic and metaheuristic methods specifically crafted for particular tasks. Notable examples include the Ant-Colony Optimization and Tabu Search methods for addressing the Vehicle Routing Problem (28, g 15), the Shortest Processing Time and Most Work Remaining Heuristics for Job Scheduling Problems [30], and the Hungarian Algorithm for the Assignment Problem [.]. These approaches are favored in industrial settings due their simplicity and speed. However, they need to be individually tailored to each task and its constraints' setting. In contrast, exact solvers such as Google- OR-Tools g offer general and precise solutions, but their applicabílity is often limited to amaller-scale problems due to the inherent NP- -a-hardness of combinatorial problems.
CP via learning- approach. In Al literature, Reinforcement Learning (RL) has been a prominent approach for tackling combinatorial problems since the 1990s [21 20 45| 7 22. The integration of deep learning, particularly through innovations like Pointer Networks, has significantly enhanced RL's capability to handle more complex combinatorial tasks B5 3. Further advancements
involve the use of Transformer networks 34 14] with notable applications in solving the Vehicle Routing Problem [25] []] Despite these advances, RL-based methods often still do not exceed the performance of traditional heuristics, especially when scalability and accurate state representation are
required 36 22 44 31
CP with LLMs. Recent studies have leveraged large language models (LLMs), such as GPT-3.5 and GPT-4, to tackle combinatorial problems like the Traveling Salesman Problem using iterative prompting, where solutions are refined incrementally 23 41). Other works employ LLMs to autonomously generate executable code as novel heuristics for problems like the knapsack and 18 This promising approach enhances task-specific heuristies, specialized combinatorial tasks. In contrast, our focus is on leveraging I.IMMs to directly solve combinatorial problems in a generalizable manner, enabling a versatile approach applicable across wide range of complex tasks.
traveling salesman 29 17
potentially improving performance

---

Prompting strategies. The expressive capabilities of direct prompting in Large Language Models are theoretically limited the complexity class TC [24. To effectively address combinatorial problems with L.LMs, sophisticated prompting strategies are required. One basic approach is the Chain-of-Thought (CoT) prompting, introduced in [40], which encourages I.L.Ss to articulate intermediate "thoughts" that inform the generation of the final output. This technique has given rise to advanced variations,, including Self-consistency with CoT (CoT-SC), Thouuhhs (ToT), and Graph-of-Thour Thought methods [37 42 46). Additionally, decomposition prompting strategies can be employed 48 12], since they simplify complex tasks into smaller, manageable subtasks via symbolic programs structured algorithms, thus improving the performance of LLMs. In our experiments, found these techniques to be insufficient, leading us to propose the Self-Guiding Exploration method as more effective solution for tackling combinatorial problem tasks.
Preliminaries
We provide an overview of combinatorial problems, highlighting their inherent complexity with the classic example of the Traveling Salesman Problem (TSP) and an example of a combinatorial problem formulation in a prompt for use by a Large Language Model (LLM).
Combinatorial problems. Combinatorial problems involve Decision-making processes where the goal is to assign binary decision variables x E 0, 1 in order to optimize a cost function g(x,...,.Ta) subject task-specific constraints. A classic example of such a problem is the TSP. In the TSP, given a list of n cities and the distances dij between cities j. the objective is to determine the shortest possible route that visits each city exactly once and returns to the starting city. Ziy is used as the action variable, indicating whether the route progresses from city i to city j. The cost function to minimize in TSP is g(x) - -j=1 dejaaay under the condition that all cities visited exactly
once Σi= Tij = and Σÿ= TGj = for all i.j. Combinatorial problems are generally categorized as NP-hard due to their inherent computational complexity. For instance, a TSP with n cities presents (n-1)! possible routes, rendering the evaluation of all potential solutions impractical and exceedingly time-consuming as n increases.
Prompting combinatorial problems in LLMs. To use LLM for solving CP tasks, we define f as the interface function of generative LLM model, which accepts high- ligh-dimensional discrete input tokens and generates outputs within the same token space (f W + W). For each combinatorial problem task, the input Q to the LLM can be explicitly defined in a textual format. This description delineates the specific goal alongside a list of variables tailored to the task at hand. For instance, the objective of the Traveling Salesman Problem (TSP) can be textually articulated as "Find route that minimizes the total travel distance, visits each city exactly once, and starts and ends in the same city." Subsequently, the variables, such as the distances between cities dig. are provided in format such as "The distance between city and city j is [number]", laying out all necessary parameters for the model to process and generate solutions. The model will then process this structured input Q to produce the corresponding solution answer A, where both Q and are within token space W; formally, A {Q). Given the inherent complexity of combinatorial problems, direct zero-shot prompting f(Q) is insufficient. Consequently, we propose a self gelf-guiding exploration algorithm that employs metaheuristic-liee strategies to effectively solve CP tasks.
4 Method
In this section, we introduce Self-Guiding Exploration (SGE) method and provide detailed expla- nation of its algorithm designed to tackle combinatorial problems. The method (Fig [ inspired by metaheuristic approaches, synthesizes multiple heuristic methods. It generates various thought trajectories, with each trajectory representing a specific heuristic approach. These trajectories are then integrated form the final solution. To overcome the challenges of executing complex heuristics through LLMs in one step, our algorithm utilizes decomposition strategy. This approach breaks down each trajectory into smaller, more manageable subtasks, enabling the solution to progress through sequential, simpler steps. This general-purpose algorithm is tailored to adapt to a wide range of combinatorial problems without the constraints of task-specific exemplars for few-shot solution generation.
3

---

(GE
Loop oar michoos
Phases
Meta queries
Exploration
List methors aroblem
decorpsaed axitoakee
(2) Decomposition
List subtasks perform method
Combinatorial Problem Q
Solution A
Subtask Resolution
Perfo Perform subtask
(4) Feedback and Refinement
Give feedbback and refine
recorave call of (SR(aaokk))
(5) Integration
Integrate
Figure I: Self-Guiding Exploration. The generative model autonomously addresses combinatorial problem task Q through five-phase process: (1) Exploration of solution trajectories, where each trajectory offers potential solutions; (2) Decomposition of these trajectories into K subtasks,
outlining specific steps for each method: (3) Resolution each subtask, executing the outlined steps; (4) Feedback and Refinement, where feedback is gathered and used refine each subtask; (5) Integration of all trajectories into a consolidated final solution A. Distinct from traditional techniques, SGE(Q) functions entirely autonomously, eliminating the reliance on task-specific queries or manually created thought exemplars. This independence makes universally applicable all CP tasks without necessitating modifications.
exploration/eccoposttiae
Algorithm 1 Self-Guiding Exploration algorithm SGE(()
Require: query Q, model meta-prompts Z, maximum recursion depth D 1: Q = [Q, Zexplore)
b Explore method trajectories
2: for iteration n E 1,,....., do
3: Q - S(Q Q", Zdecomp)
>> Decompose trajectory subtasks
4: for iteration E 1,2,..... K do
5: if f(Q Zeheck) then 2T)
b Check if subtask is simple Execute subtask and get thought
6:
T
7:
else
8:
T SGE 1
Recursive call of subtask
end if 9:
QE feeebbcck F(Q, Th Z feedback)
Get feedback query b Refine thought
11:
T = I(Q, The Q (ecstack)
12: end for
end for
14:
A f(Q.T( K: ..... TN Zintegrate)
> Get answer
4.1
Algorithm
The proposed method's algorithm is segmented into five distinct phases, as outlined in Algorithm These phases include exploring thought trajectories, decomposing each trajectory into subtasks, resolving each subtask to generate thoughts, obtaining feedback and refining the thoughts, and finally integrating all thoughts to formulate the answer. Each thought here represents completed subtask.
Exploration. During the exploration stage, the model tackles the overarching problem Q by engaging with exploration meta-prompt. This prompt Zemplore is structured as: "List all possible methods to solve this problem. Return them separated by new lines." " This prompt stimulates the model to enumerate potential methodologies pertinent to Q. The sequence is then divided into tpsc-spe trajectories of queries Q" each incorporating a method to address Q:
Q = f(2, Zemplore)-
Decomposition. Following exploration, each trajectory query Q" is processed through the model to break down the trajectory into actionable steps. The decomposition meta-prompt Zdecomp formulated as: "List all steps to use the method. Return them separated by new lines." This leads to

---

the generation of subtask queries that operationalize the trajectory method:
Q fQQ Zecompp)
Subtask resolution. Post-decomposition, the subtask queries Q% are each split into K individual queries and processed by the model to generate thoughts. The model initially evaluates if the task is easily solvable using the meta- pecamppromp Zcheck: "Is this problem easily solvable? Return yes or no": f(2 Zcheck). If the response is affirmative, the model executes the subtask query Q% generate new thought:
T = (QQ.TT1-1
Otherwise, the model engages a recursive instance of the self-guiding exploration algorithm on Q instead of the main task Q to navigate and decompose the complex subtask, producing:
T = SQQ.TT (kymassaa))
Feedback and refinement. In this stage, the model utilizes an additional meta-prompp Z feedbacc "Give feedback to the proposed solution" to generate feedback queries @kfeettack f(Q, Qh: Th feedback)) This guides the model in refining the initial responses through reeval- uation and enhancement of the thoughts:
T f(Q, TH Pifecsbecc):
Integration. Upon completion of all trajectories and their associated subtasks, the model employs a final meta-prompt Zintegrate "Integrate previous findings and provide the final answer" to amalgamate the last thoughts into definitive solution answer.
A = I(Q.Tk ?integrate).
SGE draws inspiration from metaheuristic methods used to solve combinatorial problem tasks. Yet, due to its general-purposs nature and veeta-rromps. is also suitable for other tasks, beyond CPs. Essentially, integrates elements of exploration-of-tue thougtt, decomposition, and refinement prompting strategies, but it does without relying on task-specific prompts solution exemplars. For additional information on these prompting strategies, see Section A.I
Experiments
This section details the experimental setup and presents the results of our proposed method applied to combinatorial problem tasks, well as its performance other reasoning tasks commonly explored in LLM research.
5.1
Setup
CP tasks. The experiments were conducted on six combinatorial tasks: Assignment Problem, Knapsack Problem, Bin Packing Problem, Traveling Salesman Problem, Vehicle Routing Problem, and Job Scheduling Problem. The Assignment Problem, classified as P-complete, can be optimally solved using the Hungarian Algorithm. In contrast, the other tasks are hP-hard and ordered by increasing complexity. For a more detailed discussion of these CP tasks, refer to Section A.2 We included five distinct problem sizes, involving 5, 10, 15, 20, and 30 elements (nodes) such as cities in the TSP/VRP. To facilitate these experiments, dataset was created, comprising 100 randomly generated instances for each problem size. These instances were characterized by uniformly distributed variables, such as the positioning of cities TSP/VRP or bin volume in the Bin Packing Problem, over interval from 0 to 100. The experiments utilized NVIDIA A A100 SXM 40GB GPU, paired with two AMD EP4C CPUs (8 cores each) and 256GB RAM. Our implementation is available online !
httpss//gtthab.ccc/an///////
5

---

Table 1: Percentage performance improvement compared to 10 CP tasks using GPT-4 and Gemini-1.5 models. CoT uses majority voting, with the number candidates equal to the number of thoughts produced by SGE. The metrics is quantified percentage improvement in cost with respect to IO solution (the bigger it is the better).
GPT-4
Gemini-1.5 1.5
Task
CoT
Refine
Decomp
Ours
CoT
Refine
Decomp
Ours
Assignment
11,46
14.47
33.80
41.33
11.66
13.98
31.94
40.46
Knapsack
15.37
17.16
51.95
70.39
13.85
16.85
48.62
65.87
Bin Packing
14.06
17.12
39.57
74.72
11.89
15.43
35.74
67.63
Travelling Salesman
13.64
15.75
38.49
72.10
14.34
15,90
36.36
68.09
Vehicle Routing
14.27
16.94
36.73
71.92
11.88
15.13
33.59
68.02
Job Scheduling
13.84
16.37
38.20
75.33
13.41
15.75
36.36
67.89
Baselines. We utilized four baseline prompting methods: Input-Ouiput (IO) Direct Prompting, Chain-of-Thought Prompting. Self-Refine (Refine) Prompting, and Decomposition Prompting. The Input-Output (IO) approach involves single prompt where the model is asked to provide a solu- tion directly, without complex prompting. In this approach, we generate N sample candidates by repeatedly prompting the model with the same query Q, N times. The responses then aggregated through majority voting to identify the most common solution among the N outputs. We employ the Self-Refine (Refine) method [19], which includes feedback-refinennn closely with phase four of SGE. Additionally, we use the zero-shot Chain-of-Thougee method [13, which is the basic technique among cesplorationno--houuee Decomposition method as described in [49]. . In our experiments, these baseline methods were tested across range of five LLM models including GPT-4, GPT-3355 by OpenAI, Gemini- by Google, and the Llama-2 series from Meta, which includes models with 70 billion and 7 billion parameters. We did not include prompting methods previously used in [16 23 41,, their prompting strategies showed inferior results compared to the zero-shot Chain-of-Though approach when tested with our data.
procedure that aligns
methods. Lastly, we implemented the
Metrics. In our study, each method's performance evaluated relative to 10 (Input-Output) prompting. To quantify the improvement, we first measure the solution cost Gio for each combinatorial problem task using 10 prompting (e.g., for the TSP, gio = Σ Eド= dzy.,y). We then calculate the cost 9method using alternative methods. The percentage improvement is computed as 100 x Dio 9mechud For problems of smaller sizes, we are able to obtain optimal solutions using the Google- OR-Tools solver through brute force approach. In such instances, we measure the cost of the optimal solution Sops and determine the optimality gap as 100 x 9method -9pp
2to
9upt
5.2 Results CP tasks
To evaluate the general performance of SGE on combinatorial problems, we conducted experiments comparing performance improvement to IO of SGE and CoT, Decomposition, and Refinement baselines using GPT-4 and Gemini- LLM models. Table gives the results six combinatorial problem tasks. The results analysis shows that the SGE method consistently outperforms CoT, Refine, and Decomposition methods across all tasks. Notably, the magnitude of improvement escalates with the increasing complcxity of the problems, from polynomial to exponential. The margin with the second-best method, Decomposition, ranges from 7.53% for the Assignment Problem to 37. 37.13% for the JSP. This trend suggests that the IO method may struggle with the computational demands of NP-hard problems, where more sophisticated strategies like SGE provide significant advantages, For a comprehensive view of all experimental results, see Section A.4
To gualitatively evaluate the performance of the Exploration, Decomposition, and Refinement phases of SGE method, we assessed the LLM outputs for each phase across five random instances of each combinatorial problem task. Figure 2 Figure@iillssraaees illustrates an example of how our method addresses the TSP, showcasing outputs during each of the three phases of SGE. the Exploration phase, the first box of Figure 2 displays how LLM f generates a list of potential algorithms suitable for solving

---

Exumple Exploration
Prompt: You are given list of points with coordinates: (1): (0, 49); (2): (26. 41); (3): (2, 29); (49, 15): (0, 23); We to find the route that has minimum problem. [Return condilions).
total length.
possible methods
Exploration Output:
Nearest Neighbor Algorithm
Christofides'' Algorithm
Ant Colony Optimization
Integer Linear Programmiin
Exumple of Decompostion of TSP
Prompt: [Problem definition]. Nearest Neighbor Algorithm. steps
method. (Return conditions.
Decomposition Output:
Select Starting Point
Find the Nearest Neighbor
Update
Repeat
Return to the Starting Point
Example of Refinement of TSP
Prompt: |Problem definition]. [Nearest Neighbor candidate solution). Give feed- back to the proposed solution.
Refinement Output:
Choose two edges
Remove these edges and reconnect the two paths that were created in such way that the new connections do not cross over each other.
Check if the new tour has shorter distance than the previous tour. it does,
keep the change. Otherwise, revert to the previous tour.
Repeat this process until no improvements can be made.
Figure 2: Example of SGE inference across the Exploration, Decomposition, and Refinement phases for the Traveling Salesman Problem. The figure displays three boxes, each illustrating the prompt structure and corresponding example output for each phase.
the TSP, such as heuristic approaches like Nearest Neighbor, metaheuristic techniques like Ant Colony, and Mixed Integer Linear Programming (MILP) method. This phase adapts to different combinatorial problems by suggesting tailored algorithms, like the Hungarian algorithm for the Assignment problem, Greedy algorithms for the Knapsack problem, and Clustering methods for the Vehicle Routing Problem (VRP). Each list of algorithms forms the foundation for generating diverse candidate solutions tailored to each specific problem. The Decomposition phase, depicted in the second box of Figure breaks down each identified algorithm into specific subtasks. This example shows the decomposition of the Nearest Neighbor algorithm for the TSP, where the initial subtasks are simple enough for direct processing by model f. However, more complex tasks, such as loops, undergo further decomposition using SGE in recursive manner, with computational or programming tasks being handled using Python within models like GPT-4 and Gemini- 1.5 equipped with Code Interpreter. Finally, the Refinement phase, illustrated in the third box of Figure focuses on enhancing the candidate solutions developed the previous stage. This example pertains to refining solution derived from the Nearest Neighbor algorithm for the TSP by implementing the 2-opt algorithm. Renowned for its effectiveness in TSP and VRP contexts, the 2-opt algorithm optimizes the initial solution to find locally optimal solutions within specific neighborhood, thus improving the overall quality of the candidate solutions. This example shows that SGE method adapts its approach to suit different combinatorial problems, finding special set of heuristics for each task.
Effeet of problem size on SGE performance. To evaluate the effect of problem size on SGE performance, we conducted experiments on all six tasks with input sizes of 5, 8, 12, 15, and 20 nodes using the GPT-4 model. Figure gives the results of these experiments. The results analysis shows that generally, an increase problem complexity, as determined by the size of the problem input, negatively influences performance improvement; larger problem sizes result in diminished performance improvement of the SGE method compared to IO. Specifically, tasks with 20 input nodes consistently exhibit lower performance improvements relative to the 1O method than tasks with input nodes. However, when comparing less disparate sizes, such as 8 and 12 nodes, the differential impact performance is less pronounced and can occasionally be positive.
7

---

Table 2: Optimality gap of prompting methods using LLaMA-2- 2--7 The results are represented as performance percentage difference compared to optimal solutions (the smaller it is, the better).
Size
Method
Assignment
Knapsack
Bin Packing
TSP
VRP
JSP
10
45.45
90.10
108.2
100.3
102.0
105.3
NODES NODES
CoT
39.33
66.88
78.24
81.15
78.17
79.41
Refine
36.42
61.98
77.40
71.62
72.49
71.72
Decomp
14.66
21.56
40.00
43.62
40.65
44.15
Ours
2.500
8.050
9.060
8.27
11.92
9.300
I0
46.84
103.5
112.8
116.9
116.3
108.2
CoT
39.70
73.84
85.08
89.01
89.48
85.21
Refine
37.32
72.62
86.25
85.59
83.31
78.43
Decomp
18.49
26.43
52.73
53.48
54.43
49.81
Ours
8,290
14.88
20.95
15.19
19.65
21.26
NODES
10
49.11
101.5
120.7
121.6
118.5
117.6
CoT
41.70
79.33
93.84
86.84
90.05
89.29
Refine
40.35
77.09
82.23
88.57
88.40
87.02
Decomp
21.12
35.82
55.40
57.51
59.19
56.01
Ours
11.26
16,82
22.38
16.12
24.00
22.86
Problem Size Effect
Performance Improvement
12
20
13
Assign
Knapsack
Bin Pack
TSP
VRP
JSP
Figure 3: Effect of Problem Size Performance Improvement relative to the IO solution using gpt-4 w/ code interpreter. The analysis spans problem instances of varying sizes, systematically presented from the smallest the largest, specifically ranging from are organized to highlight the impact of increasing problem complexity on the effectiveness of the solution.
20 nodes. Results
Model Effect
Performance Improvement
GPT-4
Gemini-1.5
GPT-3.5
Ubmma--77bb
Uama-2-7b
41.4
20
Assign
Knapsack
Bin
ISP
Figure 4: Effect of Model Choice on Performance Improvement relative to the IO solution.

---

Table 3: Results for reasoning tasks using gpt-4 with code interpreter presented as accuracies on benchmark test sets.
Arithmetic
Commonsense
Symbolic LastLetter
Method
Avg.
AQUA
GSM8K SVAMP
ASDiv StrategyQA CSQA
ARC
10 Prompting
67.30
87.04
88.34
90.10
78.40
81.14
87.52
81.98
82.73
CoT Prompting
69.57
89.76
91.58
93.32
81.16
84.15
90.80
85.18
85.69
Refine Prompting
69.68
89.80
91.00
93.10
81.26
83,50
91.09
84.82
85,53
Decomp Prompting
69.99
91.85
92.16
94.08
82.08
84.88
91.76
85.64
86.43
Ours
74.63
97.35
98.16
97.24
83.49
85.68
93.28
86.96
89.60
Table 4: Performance efficiency of prompting methods using gpt-4 w/ code interpreter. The results are represented as performance percentage improvement compared to 10 solution and number of model f calls..
Method
Performance Improvement Function Calls
CoT
13.77
58.32
Refine
16.30
58.32
Decomp
39.79
31.04
Ours
67.63
58.32
Gap between SGE performance and the global optimum. To evaluate the gap between SGE solutions and global optimum solutions, we conducted experiments on small problem sizes involving 5, 8, and 12 nodes, utilizing the brute force method via Google-OR-Toole to determine the global optimum. Figure provides the results of these experiments terms of the percentage gap between the performance of SGE and optimal solutions. The results analysis shows that generally, the SGE method exhibits smaller optimality gap across all tasks when compared baseline methods. This advantage is particularly pronounced for more complex problems such as Bin Packing, TSP, VRP, and JSP. For instance, SGE achieves a 12. 12% smaller optimality gap on the Assignment task than the next best Decomposition method and 34.85% smaller gap on the JSP.
Effect of LLM selection on SGE performance. To evaluate the impact of model selection on SGE performance, we conducted experiments comparing different models, including GPT-4, Gemini- GPT-3.5, Llama-2-770, and Llama-2-7b models. Figure provides the results of these experiments. The results analysis shows that GPT-4 and Gemini- demonstrate significantly better performance compared other models across all tasks. A notable feature of both models is the integration of Code Interpreter (CI) tool, which appears crucial for combinatorial problem tasks as it enables the models to execute generated code and evaluate solution performance directly. In contrast, models lacking a CI tool, such as GPT-3.5, Llama-2-700,, and Llama-2-7b, exhibit poorer outcomes, with GPT-3.5 slightly outperforming the Ilama models. The comparison between Llama models indicates that the size of the model with 70 billion versus 7 billion parameters does not significantly influence performance. This suggests that model size alone does not guarantee substantial performance improvements in combinatorial tasks.
Trade-off' between performance and cost in SGE. To evaluate the cost-effectiveness of different methods, we conducted experiments compare the average performance improvement per method against the average number of LLM calls utilized to solve each combinatorial problem instance. Agives the results of these experiments, where the number of function calls in CoT and Refine methods was explicitly controlled to make them equal to SGE function calls. The results analysis shows that the SGE method achieves 27. 74% better performance compared to the Decomposition method but requires 87.895, more function calls. Thus, while SGE offers superior performance, does so at a marginally higher operational cost. Therefore, the application of this method is particularly justified in scenarios where performance gains prioritized over cost efficiency.

---

5.3 Results on reasoning tasks
To evaluate the versatility SGE in handling different types of tasks, we conducted experiments across eight datasets commonly referenced in LLM research, categorized into three distinct task types: arithmetic, commonsense reasoning, and symbolic reasoning. Table [ gives the results of these experiments, with each dataset comprising train and test splits where SGE and baseline methods were applied to the test splits. The results analysis shows that the SGE method demonstrates incremental but consistently superior performance across all task categories. Notably, the method shows particular strength in arithmetic tasks, where achieves an average improvement of 4.83%, compared to 1.24% in commonsense reasoning tasks and 1.32% in symbolic reasoning tasks. This demonstrates the method's s applicability and effectiveness across a diverse range of tasks, extending beyond combinatorial problems.
6
Conclusion
This study has explored the application of Large Language Models to combinatorial problems, a category of tasks known for their NP-hardness. Our research introduced 'Self-Guiding Exploration prompting strategy that effectively utilizes the inherent strengths of LLMs. By generating multiple thought trajectories tailored various CPs and autonomously decomposing them into manageable subtasks. Our findings confirm that SGE outperforms existing strategies, improving optimization performance by 27. 27.84% and achieving 2.46% higher accuracy in reasoning tasks. Notably, SGE shows 34.85% smaller gap with the global optimum on complex tasks like the Job Sheduling Problem compared to baseline methods. These results underline the potential of advanced LLM strategies in complex problem- soolvin scenarios, suggesting that the right techniques can enhance the utility of LLMs critical logistics and resource management applications.
Despite the performance improvements demonstrated by the SGE, several limitations have emerged that merit attention. Firstly, SGE performance depends the choice of language model. Secondly, the operational costs associated with SGE are notably higher; requires 87.89% more function calls than the Decomposition method. These issues present clear avenues for future research. Enhancing SGE's s computational efficiency while maintaining its high performance could broaden its applicability and make a more practical choice for wider range of problems.
10

---

References
[1] Samuel Kwame Amponsah, Dominic Otoo, Said Salhi, and Ebenezer Quayson. Proposed heuristic method for solving assignment problems. American Journal of Operations Research, 06:436-444
01 2016. doi: 10. 10.4236/ajor.22166.60 6.66040.
[2] M Emin Aydin and Ercan Öztemel. Dynamic job-shop scheduling using reinforcement learning agents. Robotics and Autonomous Systems, 33(2-3):169-178 2000.
[3] Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combina- torial optimization with reinforcement learning. arXiv preprint arXiv: 1.09940, 2016.
[4] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz I Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, llya Sutskever, and Dario Amodei. Language models are few-shot learn- ers. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- -ienn Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 12, 2020, virtual, 2020. URL https: httpp::/ http://ee/ccccc...////o.aaa http:/aaa--btttttt.t html
[5] Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope. James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Levskaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito. David Luan, Hyeontaek Lim, Barret Zoph. Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai. Marie Pellat, Aitor Lewkowycz, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Hellstern Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. Palm: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240):1-113, 2023. URL BRRLhttp://jmlr prg/papers/v24/222 1144.htm
[6] Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. Learning heuristics for the tsp by policy gradient. In International conference the integration of constraint programming. artificial intelligence, and operations research, pages 170-181. Springer, 2018
[7] Thomas Gabel and Martin Riedmiller. Adaptive reactive job-shop scheduling with reinforcement learning agents. International Journal of Information Technology and Intelligent Computing, 24(4):14-18, 2008
[8] Rajeev Kumar Goel, Raman Maini, and Sandhya Bansal. Vehicle routing problem with time windows having stochastic customers demands and stochastic service times: Modelling and solution. J. Comput. Sci., 34:1-10, 2019.
[9] Google. Or-tools, 2023. URL httttttt///eeellpeereeee google.......ooooooooooe com/ cwm.optimiiztiion
[10] Zangir Iklassov, Dmitrii Medvedev, Ruben Solozabal Ochoa de Retana, and Martin Takác, On the study of curriculum learning for inferring dispatching policies on the job shop scheduling. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China, pages 5350-5358. ijeai.org, 2023. doi: 10.2496/JCCA1.222/55444 URL https://dol: org/ 10/g//..01 24963 (1993/ijjcai hjciiicciiiiiaa..ia 2023/594
[11] Zangir Iklassov, Ikboljon Sobirov, Ruben Solozabal, and Martin Takáe. Reinforcement learning approach to stochastic vehicle routing problem with correlated demands. IEEE Access, 11: 77958-87969, 2023. doi: 10. /0A.109//CCESS222...000
URL. httpss//tt///oo. org//0
1109/ ACCESS. 3306076

---

[12]
Tushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson. Peter Clark, and Ashish Sabharwal. Decomposed prompting: A modular approach for solving complex tasks. arXiv preprini arXiv:2210.024004, 2022.
[13]
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022.
Large language models are zero-shot reasoners. In NeurIPS, URL http://papers: http::///pppprs..ns..... 0bbo2299aaddaccff1112200066111
files/ www.sslaweeee.eaaeeeaaaaaaaaeaee 2022/hashhhh/e// Centtract-Confeeeent .ttmll
[14] Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! 2018.
arXiv preprini
[15] Guoming Li and Junhua Li. An improved tabu search algorithm for the stochastic vehicle routing problem with soft time windows. IEEE Access, 8: 8:158115-158124, 2020.
[16] Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang. Evolution of heuristics: Towards efficient automatic algorithm design using large language mode, 2024.
[17] Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang. Evolution of heuristics: Towards efficient automatic algorithm design using large language model, 2024. URL http:://a/aaaa //axxvv org/ abs/ 02001.20511
[18] Shengcai Liu, Caishun Chen, Xinghua Qu, Ke Tang, and Yew-Soon Ong. Large language models as evolutionary optimizers, 2024. URL http:p::://a/xx../.o at/p/axxvvvv........ /tw.0 19046
[19] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Sean Welleck, Bodhisattwa Prasad Majumder, Shashank Gupta, Amir Yazdanbakhsh, and Peter Clark. Self-refine: Iterative refinement with self-feedback. ArXiv preprint, abs/2303.17651, 2023. URL aattps://arze org/ org/abs/2303. 17651
[20] Sridhar Mahadevan and Georgios Theocharous. Optimizing production manufacturing using reinforcement learning. In FLAIRS conference, volume 372, page 377, 1998.
[21] Sridhar Mahadevan, Nicholas Marchalleck, Tapas K Das, and Abhijit Gosavi. Self-improving factory simulation using continuous-time average-reward reinforcement learning. In Machine Learning Interantional Workshop, pages 202-210, 1997.
[22] Hongzi Mao, Malte Schwarzkopf, Shaileshh Bojja Venkatakrishnan. Zili Meng, and Mohammad Alizadeh. Learning scheduling algorithms for data processing clusters. In Proceedings of the ACM special interest group on data communication, pages 270-288. 2019.
[23] Mahmoud Masoud, Ahmed Abdelhay, and Mohammed Elhenawy. Exploring combinatorial problem solving with large language models: case study on the travelling salesman problem using gpt-3.5 turbo, 2024.
[24] William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log- (og-precision transformers. Transactions of the Association for Computational Linguistics, 11:531-545, 2023, doi: 10.1162/tacl_a a a_0tiaccc___006262.___
org/ 20///2023.. facl-1.31.
[25] Mohammadreza Nazari, Afshin Oroojlooy, Lawrence V Snyder. and Martin Takáë. Reinforce- ment learning for solving the vehicle routing problem. In Conference on Neural Information Processing Systems, NeuriPS 2018, 2018
[26] Afshin Oroojlooyjadid, Lawrence V Snyder, and Martin Takáë. Applying deep learning to the newsvendor problem. IISE Transactions. 52(4):444 463, 2020.
[27] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang. Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder. Paul F. Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback. In NewrlPS, 2022. URL http: //ppprrs.///ppp.eeeeeeeaa nips wwtpsic.epppeem.iiiiiiiicc www.fs//peppppe//222/2 2aat1/12efeea3300444794110550030 www.taat---aatat--eeee wwwfttoooooeeeencccmmemmm html
12

---

[28] Tantikorn Pichpibul and Ruengsak Kawtummachai. A heuristic approach based on clarke-wright algorithm for open vehicle routing problem. The Scientific World Journal, 2013, 2013.
[29]
Bernardino Comera-Paredeee Mohammadamin Barekatain, Alexander Novikov, Matej Balog. M Pawan Kumar, Emilien Dupont, Francisco J. R. Ruiz, Jordan S. Ellenberg, Pengming Wang. Omar Fawzi, Pushmeet Kohli, Alhussein Fawzi, Josh Grochow. Andrea Lodi, -ean-Baptiste Mouret, Talia Ringer, and Tao Yu. Mathematical discoveries from program search with large language models. Nature, 625:468 475, 2023. URL https://api commanticscool
org/Corpus 266223770
[30] Veronique Sels, Nele Gheysen, and Mario Vanhoucke. A comparison of priority rules for the job shop scheduling problem under different flow time-and tardiness-related objective functions. International Journal of Production Research, (0(15):4255-4277 2012.
[31] Penghao Sun, Zehua Guo, Junchao Wang, Junfei Li, Julong Lan, and Yuxiang Hu. Deepweave: Accelerating job completion time with deep reinforcement learning- -aasengg-baeddd coflow scheduling. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence. pages 3314-3320, 2021.
[32] Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoe V. Le, Ed Chi, Denny Zhou, and Jason Wei. Challenging big-bench tasks and whether Mhain-of--thouhh can solve them. In Anna Rogers, Jordan L. Boyd-Graber, and Naoaki Okazaki, editors, Findings of the Association for Computational Linguistics: ACL 2023, Toronto, Canada, July 9-14, 2023, pages 1 13003-13051. Association for Computational I Linguistics, 2023, doi: 10118653311222233 http://2...iinnngaal..... //doi.org/10. 18653881111000 findings--iiigiii acl. 824
URL https
[33] Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam M. Shazeer, Apoorv Kulshreshtha, Heng-Tze Cheng, Alicia Jin, Taylor Bos, Leslie Baker, Yu Du, Yaguang Li, Hongrae Lee, Huaixiu Zheng, Amin Ghafouri, Marcelo Menegali, Yanping Huang, Maxim Krikun, Dmitry Lepikhin, James Qin, Dehao Chen, Yuanzhong Xu, Zhifeng Chen, Adam Roberts, Maarten Bosma, Yanqi Zhou, Chung-Ching Chang, I. A. Krivokon, Willard James Rusch, Marc Pickett, Kathleen S. Meier-Hellstemm, Meredith Ringel Morris, Tulsee Doshi, Renelito Delos Santos, Toju Duke, Johnny Hartz Søraker, Ben Zevenbergen, Vinodkumar Prabhakaran, Mark Díaz, Ben Hutchinson, Kristen Olson, Alejandra Molina, Erin Hoffman-John, Josh Lee, Lora Aroyo, Ravindran Rajakumar. Alena Butryna, Matthew Lamm, V. O. Kuzmina, Joseph Fenton, Aaron Cohen, Rachel Bernstein, Ray Kurzweil, Blaise Aguera-Arcas, Claire Cui, Marian Croak, Ed Huai hsin Chi, and Quoe Le. Lamda: Language models for dialog applications. ArXiv preprint, abs/2201 002299, 2022. URL https:: arxiv. org/ abs /201. 08239
[34] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In NeurIPS, pages 5998-6008 2017.
[35] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015.
[36] Libing Wang, Xin Hu, Yin Wang, Sujie Xu, Shijun Ma, Kexin Yang. Zhijun Liu, and Weidong Wang. Dynamic job-shop scheduling in smart manufacturing using deep reinforcement learning. Computer Networks, 190:107969, 2021.
[37] Xuezhi Wang. Jason Wei, Dale Schaurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou Self-consisenncy improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171 2022.
[38] Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus. Emergent abilities of large language models. Transactions on Machine Learning Research, 2022. ISSN 2835-8856. URL, httpps //openreview http://///ee/rmmm////yyys/susda Survey Certification.
13

---

[39] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoe V Le, and Denny Zhou. fhain-of-thougee prompting elicits reasoning large language models. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances Neural Information Processing Systems, volume 35, pages 24824-24837, Curran Associates, Inc., 2022. URL Utk. 0000//111e5500013344444111110110
neur ips cc/ wctpappr_ffllleecceeeee waleee/rffleeeeeeeeeeeeeeeeeeeee /aper// Coneerr-onfeeeene.. pdf
[40] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc Le, Denny Zhou, et al. Chain-of-thouse prompting clicits reasoning in large language models. 2022.
Advances in Neural Information Processing Systems, 35:24824
[41] Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoe V. Le, Denny Zhou, and Xinyun Chen. Large language models optimizers, 2024.
[42] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. arXiv preprint arXiv:2305. 10601, 2023.
[43] Haoran Ye, Jiarui Wang, Zhiguang Cao, Federico Berto, Chuanbo Hua, Haeyeon Kim, Jinkyoo Park, and Guojie Song. Reevo: Large language models as hyper-heuristies with reflective evolution, 2024. URL http:/pss//aax...oggg////aa////a
0114
[44] Di Zhang, Dong Dai, Youbiao He, Forrest Sheng Bao, and Bing Xie. Rischeduler: an automated hpc batch job scheduler using reinforcement learning. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1-15. IEEE, 2020.
[45] Wei Zhang and Thomas G Dietterich. A reinforcement learning approach to job-shop scheduling. In IJCAI, volume 95, pages 1114-1120. Citeseer, 1995.
[46] Yizhou Zhang, Lun Du, Defu Cao, Qiang Fu, and Yan Liu. Prompting with divide-and-conquer program makes large language models discerning to hallucination and deception, 2024.
[47] Zhuosheng Zhang, Aston Zhang, Mu Li, and Alex Smola. Automatic chain of thought prompt- ing in large language models. In The Eleventh International Conference on Learning Rep- resentations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.nnt, 2023. URL https://openrevie:: wwt./eet/fffeee wdt.///ftfd-SS
[48] Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc Le, al. Least-to-most prompting enables complex reasoning in large language models. arXiv preprint arXiv:2205. 10625, 2022.
[49] Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc V. Le, and H. Chi. Least-to-most prompting enables complex reasoning in large language models. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL RRL ptttps://openrevieet net/ pdf http//dffddWWHTHH widdd2779999gfM
14

---

A Appendix
A.1 Baseline prompting techniques
Combinatorial problems are too complex for solving using direct approach. To solve in several shots, different methods can be used such as few-shot prompting, Ofain-of-thoughee exploration- of-thought, decomposition, and self-refine advanced prompting techniques. Traditional few-shot prompting involves teaching an LLM to derive an answer A to a query Q using a limited set of contextual examples D ...... EI where
[(Q. D). In the simplest few-shot setup, examples are formatted as E = Ay), where each Q2, A, are corresponding prompt and solution of example problem j. For Chain of Thought (CoT) prompting, the objective shifts to generating a sequence of intermediate reasoning steps, or "thoughts" T, and subsequently deriving the final answer from T. These in-context examples are structured as E, (Qj; (Tj....... Tzx)., A2). Exploration-of ThoThtttt techniques, such as those described in [3 problem Q into K subproblems and auto sutto-gnneratng thoughts T₁ through subproblem queries Qs with T f(xx, T- The ultimate answer then computed as = l(Q, T ). In addition to that, in Tree-of-Thought (ToT) and Grraph-of-Thoughe (GoT) prompting strategies, the problem is split into N thought trajectories Th. using pre-determined subqueries Q3 with the final answer determined by A = f(Q, ...., ) These strategies necessitate manually identifying effective subqueries Q for each specific task (e.g., arithmetic, commonsense, symbolic). Decomposition prompting strategies, as referenced [48 12] get Q7: subqueries through in-context examples formatted similarly to CoT exemplars: F, ((Q;: (Q,,1: T;,,),-., (Qj.k;: T3,s;) A₁)- Another prompting method called self-refinement [9] uses feedback and refine procedures to generate feedback queries Q7 fee
focus on dividing the
and subsequently refine thoughts 7 In our research we combined these advanced techniques and updated them into new method called self-guiding exploration to enhance performance of LLMss for CPs.
A.2 Combinatorial problems
Combinatorial problems are decision problems where solver needs to assign binary decision variable x E (0, }} to minimize some cost function or maximize reward function given input C.
Assignment problem. Despite not being classified as NP-hard and solvable in polynomial time using the Hungarian algorithm, the Assignment Problem remains fundamental combinatorial challenge. This problem entails optimally assigning n tasks to n workers, aiming to minimize the total cost or maximize the total efficiency of the assignments. The input array is represented as x n cost matrix, where the element at the 7th row and jth column represents the cost of assigning the jth task the ith worker. The goal is essentially about finding a one-to-one matching between workers and tasks with the objective of minimizing the total cost, i.c.
min g(z)=
CiyTij:
s.t.
Tij
1;
Σ
Zij
Diz E 10 Vi,j.
(2)
1=1
Knapsack problem. The knapsack problem is a classic combinatorial problem, focusing on resource allocation. It is decision problem in which the goal is to pack items from set of items with given weights w and values v into a container with a maximum capacity W. The input array C is represented as n x matrix with volume and value information of every item i. The goal is to maximize total value of packed items without exceeding container capacity, i.e.
max g(x)=
(3)
s.l.
Wyss 5 W; x; E (0,1) Vi.
(4)
15

---

Bin packing problem. The bin packing problem is combinatorial problem that involves efficiently packing n objects of different sizes w into finite number of k bin containers of fixed capacity W in way that minimizes the number of bins used. The input array C' is represented as n. x 1 vector with size information of every item i,
k
min g(x)
Zj
(5)
j
s.t.
Zij 1;
wayg S W; zij {0,1] Vi,j.
(6)
1=1
Travelling salesman problem. In the travelling salesman problem, given a list of cities and the distances between each pair of cities, what the shortest possible route that visits each city exactly once and returns to the origin city. The input array C' is represented as X n cost matrix, where the element at the jth row and jth column represents the cost dij of travelling between these two cities,
min g(z)
=
dijDij.
i=1 1=1
s.t.
Tij
1;
Σ j=1
mg = 1;
Tiz E 10, Vi,j.
(8)
1=1
Vehicle routing problem. The vehicle routing problem generalizes the TSP by incorporating multiple vehicles into the route planning. The VRP seeks to determine the optimal set of routes for fleet of K vehicles with maximum capacity P deliver goods customers, typically from central depot, with the objective of minimizing the total travel cost. In addition to TSP, the input C also includes the demand of each customer, i.e.
n
min g(x) =
diyWisk
(9)
i= j=1
s.t.
Tiyk = 1;
Σ Tisk = 1; Jija E 10,1} Vi,j,k
(10)
In cases when the capacity P is less than the customer's demand, the vehiele will go between the depot and the customer until the demand is satisfied.
Job scheduling problem. The job scheduling problem focuses on scheduling n jobs on m machines, where each job consists of a sequence of operations that need to be processed in specified order. Each operation requires a specific machine for a certain period of time, and each machine can handle only one operation at time. The input array C is represented as x x 2 cost matrix, which stores machine and completion time for every operation j of every job i. The primary objective is to minimize the makespan, which is the total time required to complete all jobs, effectively reducing the time from the start the first operation to the completion of the last operation across all jobs.
Challenges in solving combinatorial problems. The difficulty of the combinatorial problems like TSP, VRP, JSP, and Knapsack problem stems from several intrinsic and mathematical characteristics common among them. These problems are typically classified as NP-hard, which fundamentally contributes to their computational complexity. As the number of elements (cities, jobs, items, etc.) increases, the number of possible combinations or permutations explodes exponentially. For instance, the TSP with n cities has (n 1)! possible routes to evaluate. This exponential growth means that the time required to examine all possible solutions becomes impractically long even for relatively small In addition to that combinatorial problems involve decisions that are interdependent, where the choice for one element affects the options and costs for others. For example, in the JSP, the order in which jobs processed one machine can affect the scheduling for other machines.
16

---

Table 5: Percentage Performance Improvement Compared to 10 Prompting on Job Scheduling Problem. Columns Show the Number of n Jobs and m Machines.
n50m10
n50m20
n100m10
n100m20
LNS
57.2
59.1
59.6
60.8
OR-Tools
61.3
63.1
62.4
61.7
SGE
59.1
62.9
61.4
60.8
Table 6: Percentage Performance Improvement Compared to IO Prompting on Vehicle Routing Problem. Columns Show the Number of Nodes.
n100
n150
n200
LNS
57.8
58.7
58.1
OR-Tools
62.5
61.2
60.3
LKH3
65.3
64.4
65.8
SGE
59.6
60.1
59.8
Applicability of SGE to combinatorial problems. For combinatorial problems, obtaining exact solutions generally computationally prohibitive. Consequently, approximation algorithms and heuristic methods are frequently employed to tackle these challenges. Typically, these problems are broken down into more manageable subproblems. Initial solutions are then generated using heuristic functions, which are subsequently refined through additional heuristic techniques to enhance solution quality. The SGE approach is particularly well-suited for combinatorial problems as it embodies this multi-stage process: it systematically decomposes the problem, explores potential solving methods, and iteratively refines the solutions.
A.3 Additional experiments and results
To further strengthen our results and provide a comprehensive comparison of our method with well-established solvers and heuristics, we conducted additional experiments on larger instances of combinatorial problems. Specifically, we included experiments with Job Shop Scheduling Problems (Table 5) and Vehicle Routing Problems (Table (6. comparing our approach against well-known solvers and heuristics. The goal was to evaluate the scalability of our method and assess its perfor- mance relative to commonly used combinatorial optimization methods.
Recognizing the need for understanding computational overhead, we have also provided an analysis of the computational cost involved in running our algorithm (Table (7. We have introduced new baseline using large language models (LLMs) for heuristic generation, which is included in Table g We used the general version of EoH [7 (originally used for the Bin Packing problem). Specifically, in our case, for the Job Shop Scheduling task, EoH generated heuristics that scored the job nodes, and the algorithm then selected the job with the highest score as the next one in the schedule. However, we found that for more complex tasks than Bin Packing (e.g., TSP), EoH is better employed with Guided Local Search, where simple heuristics like swapping are used for local optimization, and EoH identifies a heuristic that can disturb the local optimum to explore better region of the solution space. We believe that EoH built this way, developing specific heuristic programs for each problem instance, would likely perform similarly to Google OR-Tools and achieve better performance. This approach effectively works as metaheuristic enhancer, providing state-of-the-arr results as seen in
17
Table 7: VRP Average Total Cost.
Number of Nodes
Total Cost
5
$0.0961
8
10.1676
12
$0.1964
20
$0.3515
17

---

Table 8: Percentage Performance Improvement Compared IO Prompting on Job Scheduling Problem with New Baseline. Columns Show the Number of Nodes.
150ml0
n50m20
n n100ml0
n100m20
EoH
57.8
59.6
56.4
57.1
SGE
59.1
62.9
61.4
60.8
Table 9: Effect of problem size SGE performance using gpt-4 w/ code interpreter. The results are represented as performance percentage improvement compared to 10 solution (the bigger it is the better).
Size
Assignment
Knapsack
Bin Packing
TSP
VRP
JSP
44.05
75.94
90.92
76.77
80.47
87.8T
8
42.03
77.14
75.92
80.12
80.78
71.68
12
42.65
72.50
80.36
79.93
76.18
77.08
15
41.78
71.70
71.61
73.24
78.41
79.73
20
40.24
67.21
69.78
67.14
65.19
76.29
25
39.83
67.07
66.35
60.17
60.87
69.52
30
38.75
61.15
68.13
67.32
61.55
65.20
Table 10: Effect of model selection on SGE performance using gpt-4 w/ code interpreter. The results are represented as performance percentage improvement compared to 10 solution (the bigger it is the better).
Task
GPT-3.5
GPT-4
Gemini-1.5 Llama-2-7b Llama-2-70b
Assignment
25.35
41.33
40.46
23.19
24.01
Knapsack
34.43
70.39
65.87
28.37
32.82
Bin Packing
35.83
74.72
67.63
29.78
33.76
Travelling Salesman
35.26
72.10
68.09
30.65
33.77
Vehicle Routing
36.28
71.92
68.02
30.55
33.65
Job Scheduling
35.02
75.33
67.89
30.39
34.42
Table 11: Results for reasoning tasks using gpt-3.5 with a code interpreter are presented as accuracies on benchmark test sets.
Arithmetic
Commonsense
Symbolic ARC LastLetter
Method
Avg.
AQUA GSM8K SVAMP ASDiv StrategyQA CSQA
10 Prompting
44.16
57.05
60.02
65.43
54.70
55,68
64.35
56.21
57.20
CoT Prompting
58.35
75.84
80.30
87.39
72.97
74.36
85,48
74.63
76.17
Refine Prompting
58.81
76.10
80.44
87.35
73.38
74.13
85.71
74.78
76.34
Decomp Prompting
71.64
82.11
84.34
89,83
76.16
78.84
87.48
77.89
81.11
Ours
72.84
86.18
86.44
90.17
77.44
79.09
87.83
78.78
82.27
18

---

A.4
Complete results of combinatorial problem experiments
Table 12: Comparison of various combinatorial problems based on their average cost problem size, using gpt-3.5, The Knapsack problem aims to maximize returns, while other problems focus on minimizing costs.
Size
Method
Assignment
Knapsack
Bin Packing
TSP
VRP
JSP
Avg.
102.23
710.53
13,480
679.26
809.67
3873.98
5 NODES
IO
119.25
604.83
15.220
784.98
951.89
4499.38
CoT
111.61
637.73
14.040
701.50
853.91
4032.66
Refine
96.350
750.91
14.150
711.28
828.42
4048.06
Decomp
94.350
738.32
12.920
643.25
746.36
3628.41
Ours
89.610
820.85
11.080
555.29
667.76
3161.4
Avg.
144.99
1053.98
23.080
1261.02
1436.94
8714.13
NODES
IO
166.38
870.54
26.850
1425.48
1634.52
9896.3
CoT
157.67
937.96
23.910
1341.56
1527.66
9202.0
Refine
137.22
1118.63
23.500
1293.09
1504.8
9068.51
Decomp
137.40
1122.79
21.670
1195.11
1327.99
8088.35
Ours
126.27
1220.0
19,450
1049.85
1189.73
7315.47
Avg.
218.82
1705.26
32.940
1695.44
2149.65
22142.9
12 NODES
I0
257.33
1462.01
37.420
1914.84
2424.01
24954.7
CoT
239.36
1553.15
34.380
1758.64
2305.24
23697.5
Refine
204.69
1798.81
34.020
1775.3
2219.27
22721.6
Decomp
205.31
1790.05
30.880
1589.09
1992.09
20553.1
Ours
187.44
1922.26
27.970
1439.32
1807.66
18787.4
Avg.
254.60
2412.26
37.230
2536.35
2704.09
38224.9
15 NODES
IO
294.53
2010.03
42.810
2855.74
3070.15
42092.4
CoT
281.95
2208.41
38.840
2743.79
2817.55
40660.3
Refine
242.95
2537.45
38.710
2625.05
2807.14
40123.6
Decomp
235.55
2606.89
34.770
2354.43
2584.13
36515.9
Ours
218.01
2698.54
31.040
2102.76
2241.5
31732.2
Avg.
323.14
2799.89
47.160
3122.83
3317.71
58569.7
20 NODES
I0
377.67
2433.27
53.060
3490.25
3798.23
66151.8
CoT
350.43
2523.88
50.330
3342.51
3504.49
62343.8
Refine
311.98
2867.08
48.550
3202.12
3356.6
61383.3
Decomp
298.35
2988.4
43.690
2924.58
3120.93
54426.8
Ours
277.27
3186.8
40.180
2654.7
2808.3
48542.6
Avg.
411.80
3732.26
14.640
3787.11
3991.53
103789.0
25 NODES
IO
467.70
3208.8
16.740
4246.8
4470.97
117662.0
CoT
449.08
3310.65
15.670
4023.17
4152.43
111329.0
Refine
387.31
3854.93
15.150
3943.46
4101.81
105411.0
Decomp
394.03
3988.58
13.560
3590.42
3832.48
97377.8
Ours
360.87
4298.35
12.060
3131.7
3399.95
87164.7
Avg.
512.38
4653.31
83.860
4995.58
5725.6
144036.0
30 NODES
IO
595.35
3957.27
92.660
5605.85
6501.08
162140.0
CoT
568.30
4162.98
88.780
5308.59
6051.78
147656.0
Refine
481.16
4796.2
88.280
5108.91
5853.66
152181.0
Decomp
476.20
5028.73
79.800
4762.89
5449.52
134230.0
Ours
440.87
5321.36
69.790
4191.68
4771.98
123974.0
19

---

Table 13: Comparison of various combinatorial problems based their average cost per problem size, using gpt-4. The Knapsack problem aims to maximize returns, while other problems focus on minimizing costs.
Size
Method
Assignment
Knapsack
Bin Packing
TSP
VRP
JSP
Avg.
198.69
370.00
7,4800
372.00
442.95
2131.42
5 NODES
10
267.83
267.03
9.5800
459.92
555.57
2701.22
CoT
234.43
300.42
8.2000
415.99
490.05
2360.95
Refine
174.66
400.32
8.1600
394.11
474.43
2259.75
Decomp
166.67
412.43
6.4400
329.82
386.85
1896.89
Ours
149.84
469.81
5.0200
260.18
307.84
1438.3
Avg.
278.35
571.94
13.030
710.49
821.54
4878.37
8 NODES
I0
365.34
415.19
16.160
890.27
1029.37
6024.32
CoT
324.71
456.91
14.050
775.93
901.69
5359.79
Refine
249.70
623.87
14.140
761.91
872.33
5163.49
Decomp
240.23
628.28
11.600
630.08
734.92
4335.16
Ours
211.78
735.45
9.1800
494.25
569.41
3509.08
Avg.
405.56
944.25
18.730
962.85
1238.87
12501.5
12 NODES
I0
534.81
680.40
23.640
1215.49
1537.63
15581.6
CoT
475.38
791.10
20.760
1024.87
1337.63
13557.7
Refine
359.52
1031.5
19.520
1034.36
1325.99
13395.1
Decomp
351.35
1044.55
16.640
864.00
1120.36
11173.7
Ours
306.72
1173.71
13.110
675.53
872.74
8799.38
Avg.
478.16
1349.74
21.780
1469.81
1555.83
21885.7
15 NODES
10
634.70
996.41
27.150
1822.75
1958.65
27565.6
CoT
561.76
1133.85
23.670
1608.72
1670.3
23247.9
Refine
415.50
1460.7
22.820
1567.79
1639.87
23778.5
Decomp
409.32
1446.91
19.420
1297.62
1412.5
19499.5
Ours
369.55
1710.83
15,820
1052.15
1097.85
15336.9
Avg.
587.33
1581.38
27.780
1822.89
1918.24
34243.4
20 NODES
I0
754.98
1189.83
34.320
2262.86
2356.68
42589.9
CoT
669.13
1326.23
30.270
1981.0
2065.07
36955.8
Refine
536.41
1678.17
29.380
1902.42
1998.58
36585.5
Decomp
525.00
1723.18
24.700
1614.36
1744.24
30926.3
Ours
451.14
1989.48
20.220
1353.84
1426.64
24159.4
Avg.
743.93
2148.32
8.6300
2249.6
2381.92
61530.6
25 NODES
10
959.89
1622.78
10.430
2690.03
2872.54
75770.1
CoT
843.97
1827.16
9.3000
2430.33
2563.55
67624.2
Refine
678.44
2238.86
9.3300
2445.45
2510.81
64490.3
Decomp
659.79
2341.61
7.8200
2002.71
2177.05
55070.7
Ours
577.56
2711.18
6.2700
1679.49
1785.68
44697.5
Avg.
912.48
2707.35
50.790
3070.36
3388.03
87633.7
30 NODES
10
1166.32
2079.35
62.520
3735.78
4104.37
104798.0
CoT
1049.36
2254.12
55.550
3296.34
3602.09
95887.8
Refine
844.18
2932.01
52.290
3278.37
3546.61
93372.0
Decomp
788.12
2920.33
46.390
2808.58
3146.44
80674.5
Ours
714.42
3350.95
37.180
2232.74
2540.65
63435.8
20

---

Table 14: Comparison of various combinatorial problems based their average cost per problem size, using gemini-1.8 The Knapsack problem aims to maximize returns, while other problems focus minimizing costs.
Size Method
Assignment
Knapsack
Bin Packing
TSP
VRP
JSP
Avg.
185.01
395.98
7.8900
392.96
475.25
2247. .28
5 NODES
10
249.50
293.42
9.7400
488.09
581.55
2781.78
CoT
212.33
325.58
8.6400
432.11
530.63
2460.15
Refine
161.90
424.53
8.4800
414.98
500.49
2410.6
Decomp
161.13
433.07
7.0600
346.36
432.60
2007.1
Ours
140.19
503.30
5.5400
283.29
330.98
1576.76
Avg.
262.29
596.51
13.650
739.72
853.62
5263.2
NODES
I0
348.38
450.87
17.040
917.04
1055.48
6532.72
CoT
296.24
489.46
14.860
803.14
938.79
5783.3
Refine
238.56
637.94
14.520
781.85
903.12
5646.28
Decomp
230.29
653.73
12.050
672.67
769.21
4636.82
Ours
197.98
750.57
9.7700
523.89
601.50
3716.89
Avg.
382.15
1005.24
19.690
1012.68
1291.47
13134.0
12 NODES
I0
490.19
729.67
24.330
1249.43
1583.87
15971.6
CoT
437.93
848.80
21.730
1080.36
1396.44
14301.9
Refine
346.04
1068.12
20.700
1077.78
1360.73
14185.8
Decomp
339.04
1129.44
17.490
927.75
1194.11
11726.4
Ours
297.53
1250.18
14.200
728.06
922.21
9484.31
Avg.
444.10
1449.26
23.150
1564.27
1653.6
23061.3
15 NODES
10
585.87
1090.76
27.950
1940.9
2036.78
28629.8
CoT
509.47
1216.37
25.330
1658.02
1801.66
25246.4
Refine
399.71
1541.78
24.940
1687.24
1715.89
23949.6
Decomp
385.44
1585.02
20.670
1416.65
1510.22
20343.8
Ours
340.02
1812.35
16.830
1118.55
1203.46
17137.1
Avg.
548.21
1678.75
29.180
1945.87
2009.98
3
20 NODES
I0
701.27
1280.46
35.360
2396.6
2438.29
44349.
CoT
620.99
1428.82
31.960
2111.46
2166.27
38059.4
Refine
497.49
1810.0
30.120
2025.49
2142.69
37385.7
Decomp
480.97
1800.23
26.790
1740.08
1806.83
32493.8
Ours
440.31
2074.24
21.690
1455.74
1495.83
26477.4
Avg.
708.54
2233.73
9.2200
2352.5
2496.48
64955.1
25 NODES
10
911.14
1694.31
11.280
2890.44
2978.91
77142.4
CoT
791.74
1878.46
9.9700
2504.54
2720.89
70181.8
Refine
642.79
2401.42
9.7100
2478.42
2670.85
69104.9
Decomp
634.67
2434.54
8.4200
2126.79
2266.56
60013.5
Ours
562.34
2759.92
6.7300
1762.3
1845.18
48333.0
Avg.
863.39
2855.59
52.430
3200.01
3534.72
91402.1
30 NODES
10
1108.6
2189.92
62.270
3807.69
4232.51
111716.0
CoT
1002.04
2442.99
56.720
3411.03
3757.36
96055.7
Refine
784.26
2991.77
55.310
3447.36
3764.56
95672.6
Decomp
751.20
3134.08
47.690
2886.03
3265.4
83939.4
Ours
670.85
3519.17
40.140
2447.95
2653.76
69626.6
21

---

Table 15: Comparison of various combinatorial problems based on their average cost per problem size, using ama-2-7b. The Knapsack problem aims maximize returns, while other problems focus on minimizing costs.
Size
Method
Assignment
Knapsack
Bin Packing
TSP
VRP
JSP
Avg.
89.950
802.42
13,550
775,06
926.24
4397.27
NODES
10
104.24
698.34
17.110
853.58
1041.09
4958.95
CoT
98.820
734.35
16.520
821.09
979.18
4575.45
Refine
84.600
845.41
15.890
787.03
939.69
4634.51
Decomp
82.460
839.18
14.810
745.98
873.03
4156.86
Ours
79.630
894.84
13.410
667.62
798.20
3660.59
Avg.
126.29
1197.13
26.320
1418.23
1645.42
9991.67
8 NODES
I0
147.10
1013.08
28.850
1566.87
1832.76
11162.0
CoT
136.66
1092.28
27.860
1498.77
1709.73
10389.7
Refine
119.83
1252.94
27.120
1499.56
1710.88
10509.7
Decomp
118.10
1274.02
25.100
1343.11
1572.56
9305.07
Ours
109.75
1353.31
22.700
1182.83
1401,16
8591.86
Avg.
191.22
1966.31
37.090
1921.87
2465.52
24978.0
12 NODES
IO
220.40
1731.58
40.930
2146.2
2697.85
27795.8
CoT
204.53
1810.85
39.550
1984.84
2596.84
25572.4
Refine
181.54
2045.48
38.930
1992.89
2594.67
26383.4
Decomp
178.63
2063.66
34.910
1834.9
2338.43
24007.4
Ours
170.98
2179.96
31.130
1650.52
2099.78
21131.3
Avg.
228.48
2739.37
42.610
2889.57
3017.02
43004.7
15 NODES
I0
256.26
2351.63
48.170
3212.82
3331.89
47876.6
CoT
250.10
2553.18
44.260
3025.74
3113.82
45938.3
Refine
220.66
2843.52
44.470
3039.47
3077.27
43884.0
Decomp
216.12
2896.08
40.350
2695.41
2901.24
41025.1
Ours
199.24
3052.45
35.790
2474.42
2660.9
36299.3
Avg.
287.07
3209.13
52.710
3548.1
3703.92
65481.9
20 NODES
IO
329.28
2836.21
58.190
3983.11
4240.29
72279.5
CoT
307.87
2933.81
54.780
3746.41
3837.66
69172.2
Refine
277.27
3249.57
55.810
3667.07
3743.99
69032.1
Decomp
268.09
3413.37
50.130
3373.55
3477.77
61580.1
Ours
252.84
3612.7
44.640
2970.35
3219.91
55345.8
Avg.
368.58
4255.19
16.310
4292.01
4503.47
116702.0
25 NODES
10
425.08
3693.28
18.060
4674.8
5083.89
127229.0
CoT
395.84
3938.03
16.780
4529.96
4718.81
121452.0
Refine
356.35
4438.0
17.280
4418.16
4667.3
123046.0
Decomp
344.61
4534.51
15.410
4140.85
4267.0
110997.0
Ours
321.02
4672.15
14.030
3696.27
3780.34
101586.0
Avg.
452.94
5279.99
93.580
5711.01
6309.75
160913.0
30 NODES
IO
504.64
4594.52
103.15
6409.08
7164.38
177461.0
CoT
502.24
4891.09
98.630
5995.11
6626.95
166083.0
Refine
431.79
5446.81
96.390
5957.74
6419.75
169324.0
Decomp
426.99
5619.47
89.550
5402.13
5940.75
153129.0
Ours
399.05
5848.08
80.200
4791.01
5396.94
138570.0
22

---

Table 16: Comparison of various combinatorial problems based on their average cost per problem size, using 11ama-2-70b. The Knapsack problem aims maximize returns, while other problems focus on minimizing costs.
Size
Method
Assignment
Knapsack
Bin Packing
TSP
VRP
JSP
Avg.
96.760
757.12
14.650
719.93
864.61
4130.53
NODES
I0
111.85
632.09
16.800
831.07
980.70
4706.85
CoT
105.51
700.25
15.590
744.12
917.25
4290.67
Refine
92.620
788.01
15.130
740.45
897.79
4297.34
Decomp
89.850
815.64
13.340
689.33
807.57
3915.78
Ours
83.980
849.63
12.410
594.70
719.74
3442.0
Avg.
134.41
1140.45
24.710
1321.35
1538.71
9429.18
8 NODES
I0
155.54
967.89
28.290
1477.89
1768.47
10645.8
CoT
145.07
1035.49
25.540
1399.97
1602.0
9988.41
Refine
128.91
1186.02
26.100
1355.37
1601.33
9835.02
Decomp
126.39
1209.13
23.090
1263.55
1424.77
8794.53
Ours
116.14
1303.73
20.560
1109.98
1296.99
7882.13
Avg.
201.99
1834.2
35.110
1805.11
2315.91
23294.2
12 NODES
IO
231.77
1562.82
40.340
2081.41
2610.96
26535.8
CoT
220.85
1690.42
36.560
1922.4
2462.96
24542.6
Refine
190.52
1865.06
36.340
1831.0
2363.75
23820.7
Decomp
192.52
1937.35
32.570
1666.65
2169.12
21807.0
Ours
174.27
2115.36
29.750
1524.11
1972.79
19764.7
Avg.
239.40
2575.28
40.140
2728.94
2902.12
40452.0
15 NODES
I0
271.97
2237.81
45.310
3091.61
3270.84
46491.8
CoT
255.93
2296.4
41.940
2852.78
3034.48
42731.8
Refine
234.52
2625.13
41.180
2850.11
2987.35
42280.3
Decomp
226.70
2761.56
37.990
2533.08
2736.93
37362.8
Ours
207.87
2955.51
34.280
2317.12
2480.98
33393.3
Avg.
301.13
2972.25
50.240
3334.42
3499.69
61957.2
20 NODES
IO
341.58
2565.48
56.260
3758.49
4025.37
69824.9
CoT
330.69
2705.18
51.940
3462.22
3620.96
63469.1
Refine
282.33
3031.65
52.210
3438.04
3567.26
64022.3
Decomp
287.94
3116.33
47.640
3167.42
3297.34
58800.7
Ours
263.10
3442.61
43.130
2845.92
2987.54
53669.1
Avg.
389.69
4024.08
15.510
4029.51
4184.99
110414.0
25 NODES
I0
443.99
3518.82
17.390
4600.6
4735.73
126686.0
CoT
418.18
3677.69
15.880
4148.72
4358.13
115617.0
Refine
373.97
4197.63
16.380
4136.03
4306.45
111541.0
Decomp
369.43
4170.69
14.700
3822.3
3975.41
104862.0
Ours
342.89
4555.58
13.180
3439.89
3549.23
93361.4
Avg.
490.92
5026.68
88.930
5310.47
5986.86
154018.0
30 NODES
IO
562.14
4332.75
99.580
5902.09
6848.47
171767.0
CoT
535.73
4629.8
92.530
5670.09
6113.72
158276.0
Refine
472.51
5217.75
92.730
5409.26
6165.51
160831.0
Decomp
455.30
5339.41
85.010
4948.58
5562.01
146910.0
Ours
428.95
5613.7
74.780
4622.34
5244.57
132308.0
23

---

Example of VRP Prompting
Task Description: You are given list of customers with coordinates:
(1): (87, 39);
(2): (1, 90);
(3): (28, 65);
(4): (85, 85);
and a list of customer demands:
(1): 12;
(2): 8:
(3): 16;
(4): 5.
There is depot with coordinates (50, 50) and one vehicle with a maximum capacity of 50. The goal is to find the route that has the minimum total length and go through all the customers, starting and ending the depot.
Example of VRP Exploration
[Task Description] List heuristic methods to solve this problem. Return only method names separated by new lines.
Prompt:
Exploration Output:
Nearest Neighbor Algorithm
Savings Algorithm
Sweep Algorithm
Clarke and Wright Algorithm
Genetic Algorithm
Simulated Annealing
Tabu Search
Ant Colony Optimization
Particle Swarm Optimization
Example of VRP Decomposition
[Task Description). Nearest Neighbor Algorithm. List the steps to use this heuristic method. Return only the steps, separated by new lines.
Prompt:
Decomposition Output:
*Initiiliiee at the Depot:** The starting point is the depot located at coordinates
(50, 50).
**Find the Nearest Customer:** Calculate the Euclidean distance from the depot each customer, and move the closest one.
**Mark the Customer as Visited:"* Once customer is visited, they should not be revisited.
"RRepeat Finding and Moving:" Continue finding the nearest unvisited cus- tomer from the current location until all customers have been visited.
*Rettrn to the Depot:** After visiting the last customer, calculate the distance back to the depot to complete the route.
'"Calculate the Total Length of the Route:"* Sum up all the distances traveled from start to finish.
24

---

Example of Subtask Resolution, Step One
Prompt: [Task Description]. [Apply the heuristic's step one].
Subtask Resolution Output:
Initialize at the Depot
Currentt location: Depot at (50, 50).
Example of Subtask Resolution, Step Two
Prompt: [Task Description]. [Apply the heuristic's step two].
Subtask Resolution Output:
Find the Nearest Customer
Distance to Customer at (87, 39): V(87 50) + (39 50)2
Distance to Customer 2 at (1, 90): v(1 - 50)2 + (90 -50)2
Distance to Customer at (28, 65): v(88 -0)2 + (65 50)2
Distance to Customer at (85, 85): v(85 -0)² + (85 50)2
The initial distances from the depot each customer are as follows:
Customer 1: 38.60
Customer 2: 63.25
Customer 3: 26.63 (nearest)
Customer 4: 49.50
Example of Subtask Resolution, Step Three
Prompt:
[Task Description]. [Apply the heuristic's step three).
Subtask Resolution Output:
Mark the Customer as Visited. The nearest customer is Customer 3 at coordinates (28, 65). We will visit Customer 3 first.
Example Subtask Resolution, Step Six
Prompt:
[Task Description]. [Apply the heuristic's step six].
Subtask Resolution Output:
Galculate the Total Length of the Route.
The complete route, following the Nearest Neighbor Algorithm from the depot, visiting all customers, and returning to the depot, totals distance of approximately 232.22 units.
Here's a summary of the route taken:
Start at Depot (50, 50)
Visit Customer (28, 65)
Visit Customer (1, 90)
Visit Customer 4 (85, 85)
Visit Customer (87, 39)
Return to Depot (50, 50)
25

---

Example of Feedback Prompting
[Task Description]. [Nearest Neighbor candidate solution]. Give feedback to the proposed solution.
Prompt:
Feedback Output:
Implement route optimization post-processing, such as 2-opt or 3-opt tech- niques, which iteratively refine the route by removing crossings and reducing travel distance.
Example of Refinement Prompting
[Task Description]. [Nearest Neighbor candidate solution]. [Feedback]] Improve the solution given feedback.
Prompt:
Refinement Output:
we'll apply a 2-opt optimization to the route. This will involve swapping seg- ments of the route to find a shorter path. Given the route '1 -> >> >> 4', we'll try different swaps and see if we can reduce the total distance further.
Let's simulate the 2-opt optimization on this route.
After applying the 2-opt optimization technique, the final optimized route has been adjusted to: Customer >> Customer 3 -> Customer -> Customer 4, then returning to the depot. This rearrangement was made to minimize the total distance traveled.
Example of Solution Integration
[Task Description). [All candidate solutions]. Integrate all previous findings and provide the final answer. Return the answer only as Python list of elements.
Prompt:
Refinement Output:
[1, 3, 2,
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The method, problem description, and key results are outlined in the abstract and introduction sections.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We examine the trade-off between higher costs and enhanced performance, as well as the dependency of the method's effectiveness on the choice of L.LM model.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
27

---

Answer:
[NA]
Justification:
The paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We detail the experiments conducted and provide link to the associated code repository.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
28

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code for the experiments, along with instructions, is provided in open access.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nnis.cc
mublic//qidees/Codeuubbii catpssiinooollyyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. wttps/cccppplcccuua.eeaeaecccuea Stteee///ooSSSeeissSioica www.ssssiicogoooooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have detailed the LLM models used, as well as the specific splits/details for reasoning and combinatorial problem tasks.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Error bars are not provided. The mean values of LLM few-shot generations are reported, consistent with the standard practice in similar research.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
29

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Details of the resources utilized are provided in the Experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: stctps://neurip.. www.eerrpps.cppuullielooocc http:///wbb..ttt.cccccceeee..e..
Answer: [Yes]
Justification: To the best of our knowledge, all research conducted in this paper fully conforms the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: At this stage of research on applying generative models to combinatorial problems, there are no identified societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
30

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We believe the paper does not pose such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
We have mentioned the companies that own the LLM models used in our experiments.
Justification:
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
31

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
batasets.papersstt
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The code produced represents asset developed during this research. Documentation is available in the corresponding repository.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
32

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "Q0tvD6NaKO", "reviewer": "Reviewer_zLRa", "summary": "This paper discusses \"Self-Guiding Exploration\" (SGE), a new prompting strategy designed to enhance the problem-solving capabilities of Large Language Models (LLMs) in addressing Combinatorial Problems (CPs). The authors demonstrate that SGE leverages the autonomy of LLMs to generate and refine solution paths, significantly improving the models' efficiency in dealing with NP-hard problems prevalent in logistics and resource management. SGE operates by generating multiple thought trajectories for each CP task, breaking these into manageable subtasks, and refining the outputs to optimize results. The proposed strategy surpasses existing methods, enhancing CP optimization performance by 27.84% and achieving a 2.46% higher accuracy in various reasoning tasks compared to the best existing results. This research marks a pioneering effort in applying LLMs comprehensively to a range of complex CPs and establishes new benchmarks in both performance and versatility.", "questions": "1. Can the authors elaborate on how the Self-Guiding Exploration strategy scales with varying sizes of LLMs and combinatorial problems? Specifically, how does SGE perform under constraints of lower computational resources or with compact models?\n2. How robust is the SGE strategy when applied to combinatorial problems outside the tested domains, such as logistics and scheduling? Are there specific types of CPs where SGE might not perform as well?\n3. While the focus has been on NP-hard problems, has there been any exploration of the applicability of SGE to problems that do not fall into this category? What modifications, if any, would be necessary to adapt SGE to such contexts?\n4. Could the authors compare SGE with other AI methods (such as approximation algorithms or heuristics) currently considered state-of-the-art in solving similar combinatorial problems?", "limitations": "1. The strategy's effectiveness relies heavily on large language models' capacities and specific configurations. This dependency could limit the applicability in environments where such models are not feasible due to resource constraints or accessibility issues.\n2. The paper primarily presents results for specific problem sizes. It would be beneficial to include an analysis of how well the SGE strategy generalizes across a broader range of problem sizes, particularly large state spaces common in real-world applications.\n3. While the paper provides quantitative improvements, the experimental setup could be expanded to include more diverse datasets and problem scenarios to validate the SGE method's robustness and consistency.\n4. A significant limitation is the lack of a detailed analysis of the computational, environmental, and operational costs of implementing SGE. \n5. The paper does not discuss how the SGE strategy adapts to evolving data or dynamic environments, which is critical for applications in rapidly changing fields such as logistics and real-time scheduling.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The Self-Guiding Exploration (SGE) strategy is a novel approach that significantly deviates from traditional LLM prompting methods. \n2. The paper introduces a new paradigm for using AI for complex problem-solving, enabling the model to generate and refine solution paths autonomously.\n3. The experiments are designed and described clearly, making the results seem replicable and understandable. The authors provide extensive empirical results demonstrating the advantages of the SGE approach over existing methods.\n4. Applying this new strategy to NP-hard combinatorial problems, critical in many industrial and logistical contexts, represents a substantial advancement. \n5. The method's ability to improve optimization performance by over 27% and increase accuracy in reasoning tasks by 2.46% compared to existing best results is statistically and practically significant.\n6. The SGE method has potential beyond the tested combinatorial problems, given its wide adaptability over different combinatorial problems.", "weaknesses": "1. Performance improvements are reported primarily in LLMs. The paper should address how the strategy scales with compact models, which are more accessible for practical applications and deployment.\n2. The paper could strengthen its argument by providing a broader comparative analysis with other state-of-the-art methods, especially those using different AI approaches to solve combinatorial problems (such as approximation algorithms or heuristics). This would help validate the superiority of SGE across a wider range.\n3. The paper occasionally glosses over deep technical details and assumptions within the SGE framework. More detailed explanations of the underlying mechanisms, particularly how the subtasks are autonomously generated and refined, would enhance the paper's transparency and reproducibility.\n4. The computational cost of running multiple explorations and refinements on LLMs is not addressed. A detailed cost-benefit analysis would be pertinent, especially for potential adopters who are weighing the economic and environmental implications of such advanced AI techniques.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__Comment:__ The computational cost of running multiple explorations and refinements on LLMs is not addressed.\n\n__Response:__ Thank you for bringing this important aspect to our attention. Regarding this comment, we have added a new analysis to address the computational cost of running multiple explorations and refinements on large language models.\n\nTo evaluate the cost-effectiveness of our approach, we conducted experiments on the Vehicle Routing Problem using the GPT-4 model. Table 3 (rebuttal) presents the average computational cost associated with these experiments. However, while the costs are substantial for large models like GPT-4, using open-source models such as LLaMA can significantly reduce expenses, particularly when running on personal hardware.\n\nWe have incorporated this new analysis into the main paper to strengthen the discussion on the economic implications of our approach. We hope this addresses your concern.\n\n__Comment:__ Can the authors elaborate on how the Self-Guiding Exploration strategy scales with varying sizes of LLMs and combinatorial problems?\n\n__Response:__ Thank you for your question. Regarding this comment, we acknowledge the importance of understanding how the SGE strategy scales with varying sizes of LLMs and different combinatorial problems.\n\nTo clarify, the performance of SGE does improve with larger models; however, the scale of improvement is not linear. For instance, while the LLAMA-7B model exhibits lower performance compared to the LLAMA-70B model, the difference in performance is not proportional to the difference in model size. This suggests that while larger models offer better results, smaller models like LLAMA-7B still perform reasonably well, though not as effectively.\n\nWe did not include results from smaller LLMs in our paper because open-source models smaller than LLAMA-7B generally perform worse. However, we believe that fine-tuning these smaller models using supervised learning with examples of methods to solve combinatorial problem tasks could potentially enhance their performance.\n\nRegarding larger models, as presented in Tables 1 and 2 (rebuttal), the results show that SGE performs comparably to other solvers even with larger problem sizes.\n\n__Comment:__ Are there specific types of CPs where SGE might not perform as well?\n\n__Response:__ Thank you for this thoughtful question. Regarding this comment, we acknowledge the importance of understanding the robustness of the SGE strategy across different combinatorial problem domains.\n\nIn our current study, SGE has shown performance improvements in the tested domains (Table 1, paper), including Vehicle Routing and Job Shop Scheduling problems. However, we recognize that real-world applications often involve more complex scenarios, such as stochastic or dynamic versions of these problems.\n\nWhile testing SGE on stochastic and dynamic combinatorial problems is indeed a valuable direction for future research, it is a distinct area within combinatorial optimization and is beyond the scope of our current work. We plan to explore this in subsequent studies.\n\n__Comment:__ What modifications, if any, would be necessary to adapt SGE to such contexts?\n\n__Response:__ Thank you for your question. Regarding this comment, our primary goal in designing the SGE method was to develop a general approach that could be applied across a broad range of problem types, such as both combinatorial and reasoning tasks.\n\nTo validate the robustness of our model, we extended our experiments to include reasoning tasks that are well-established benchmarks in the LLM research community. The results of these tests are presented in Table 3 of the paper. \n\nTo achieve this, we have employed the same algorithm without modifications across these contexts. This design choice was intended to ensure that SGE remains versatile and effective across various problem domains.\n\nWe acknowledge that specific modifications to SGE could potentially improve its performance for certain types of problems that do not fall into the NP-hard category. However, our main objective was to create an algorithm that balances generality with strong performance across a wide spectrum of problems, and we believe the current implementation of SGE achieves this balance.\n\n__Comment:__ Could the authors compare SGE with other AI methods?\n\n__Response:__ Thank you for your insightful comment. Regarding this comment, we already provided a comparison between SGE and Google OR-Tools in our original submission, as shown in Table 2. In these experiments, we focused on small-size problems where globally optimal solutions could be found using a full search via Google OR-Tools, employing depth-first search to exhaustively explore all possible solutions.\n\nHowever, to further clarify your comment and expand the breadth of our analysis, we have conducted additional experiments and included new comparative results. To evaluate the performance of SGE against other state-of-the-art methods, we conducted experiments on larger problem sizes against various combinatorial solvers. Table 1 (rebuttal) presents results on Job Shop Scheduling problems with 50 and 100 jobs, while Table 2 (rebuttal) shows experiments on the Vehicle Routing Problem with 100, 150, and 200 nodes. The results analysis shows that SGE performs better than LNS but falls short compared to LKH3 and Google OR-Tools, which are specifically tailored for combinatorial tasks. However, SGE remains applicable to a broader range of tasks (e.g. reasoning tasks). We believe that SGE's performance could improve further once libraries like LKH3 and Google OR-Tools are integrated into GPT-4's code interpreter, allowing our algorithm to leverage these tools within its solution trajectories.\n\nWe have incorporated these new tables into the main paper to provide a more comprehensive analysis. We hope this addresses your concern.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "phJMeAWiOE", "reviewer": "Reviewer_auHA", "summary": "The paper proposes an LLM-based solution for solving standard combinatorial search problems such as TSP and VRP. The proposed solution, called SGE, uses LLMs to (1) propose alternative approaches to solve the problem at hand, (2) decompose a chosen solution approach into subtasks, (3) identify if a given subtask is easy or hard, (4) if it’s easy, just do it, else (5) recursively call SGE to solve the given subtask. Finally, SGE also uses an LLM to integrate the results returned by the above queries. \nExperimental results compared to other LLM-based approaches show huge gains for SGE.", "questions": "1.\tDid you consider comparing SGE with a fast suboptimal algorithm for solving the evaluated CPs, e.g., LNS?\n2.\tWhy is the Integrate step done by the LLMs and not directly by parsing and analyzing the answer so far?", "limitations": "Not releavnt.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Solving combinatorial search problems is a core problem in AI\n- SGE performs well experimentally\n- The paper is, in general, well written\n- The concept of having the LLM identify if a substask is hard or not, is neat", "weaknesses": "1.\tIt is not very clear to me why would one want to use an LLM to solve combinatorial problems. \n2.\tIt seems that SGE is similar to prior work noted by the reviewers for solving these problems via intelligent prompting. The main difference I could see is the part where it checks if a task is easy or not and calls recursively afterwards, and the integration of all the results together.\n\nThe authors provide reasonable responses to both concerns.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__Comment:__ It is not very clear to me why would one want to use an LLM to solve combinatorial problems.\n\n__Response:__ Thank you for your comment. The use of large language models to solve combinatorial problems offers an advantage by choosing a specific set of heuristics/metaheuristics tailored to concrete situations. Essentially, LLMs can function as highly flexible metaheuristics that possess knowledge of various heuristics and metaheuristics. As LLMs continue to advance, we expect that their ability to produce effective solutions in this domain wil improve.\n\n\n__Comment:__ It seems that SGE is similar to prior work noted by the reviewers for solving these problems via intelligent prompting. The main difference I could see is the part where it checks if a task is easy or not and calls recursively afterwards, and the integration of all the results together.\n\n__Response:__ Thank you for your comment. Regarding this observation, we acknowledge that different papers have explored various high-level prompting strategies. In our paper, we combined three of these approaches into a unified framework. However, to clarify your comment further, our method differs from prior work in that it is fully self-guiding. Unlike previous methods that rely on in-context learning with specific examples or prompts tailored to each problem, our approach does not require such modifications from problem to problem. (Please refer to the differences in the answer $A$ equations in Section 4.1 and A.1 (our approach does not require exemplars $E$)).\n\nThe primary aim was to evaluate whether this self-guiding strategy could effectively improve performance on complex tasks while also maintaining strong results in reasoning tasks. We hope this addresses your concern and provides a clearer understanding of our approach.\n\n\n__Comment:__ Did you consider comparing SGE with a fast suboptimal algorithm for solving the evaluated CPs, e.g., LNS?\n\n__Response:__ Thank you for your question. Regarding this, we did consider comparing SGE with fast suboptimal algorithms, such as Large Neighborhood Search. To address this, we added two experiments to evaluate the performance of SGE against other well performing methods on larger problem sizes than considered in the paper. Table 1 (rebuttal) presents results on Job Shop Scheduling problems with 50 and 100 jobs, while Table 2 (rebuttal) shows experiments on the Vehicle Routing Problem with 100, 150, and 200 nodes. The results analysis shows that SGE performs better than LNS but falls short compared to LKH3 and Google OR-Tools, which are specifically tailored for combinatorial tasks. However, SGE remains applicable to a broader range of tasks (e.g. reasoning tasks). We believe that SGE's performance could improve further once libraries like LKH3 and Google OR-Tools are integrated into GPT-4's code interpreter, allowing our algorithm to leverage these tools within its solution trajectories.\n\n\n__Comment:__ Why is the Integrate step done by the LLMs and not directly by parsing and analyzing the answer so far?\n\n__Response:__ Thank you for your question. Regarding this comment, the Integrate step is handled by the LLMs because the task involves more than simply choosing one of the solution trajectories. Instead, the LLM may combine elements from different solution trajectories to potentially create a more optimized overall solution. By allowing the model to perform this integration, it can either select the best individual solution or combine parts from multiple solutions to enhance performance. We hope this explanation clarifies the rationale behind our approach.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Es7aF7PYyR", "reviewer": "Reviewer_8LKr", "summary": "This paper introduces a self-guiding exploration (SGE) framework that integrates exploration-of-thought, decomposition, and refinement prompting strategies to tackle NP-hard combinatorial optimization problems (COPs). The experiments, conducted on various COPs and several reasoning tasks, demonstrate improved performance compared to existing prompt strategies.\n\n*Based on my expertise, I will evaluate this paper from the perspective of combinatorial optimization.*", "questions": "N/A", "limitations": "Yes, the authors discuss the limitations, such as more function calls, and the sensitivity to the used LLMs.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The proposed SGE is general and innovative. \n* The paper is well-organized and clearly written.\n* The scope of empirical evaluation is extensive, including combinatorial optimization problems and various reasoning tasks.\n* The source code is provided.", "weaknesses": "* Figure 2 is lacking in detail. A comprehensive example, including detailed prompts and outputs, should be provided. \n* It appears that the decomposition process cannot be parallelized across subtasks due to the dependence on preceding $T_{k-1}^n$.\n* Limited review of related work:\n  * LLMs/FMs in CP: Many recent studies are missing. Please see [5] for a comprehensive review.\n  * Learning-based methods in CP: Numerous NCO studies, especially those published in the last three years, are missing as well, please see [6].\n* My main concern about this paper is the weak experiments, which significantly weaken the contribution of this paper.\n  * This paper only considers 5-30 nodes, which is **too small** for the NCO community. I would suggest generating code, like [2-4], in the decomposition or subtask resolution stages if the performance on large-scale instances is inferior.\n  * The optimality gap (w.r.t. the traditional solver, e.g., LKH3, OR-Tools) and inference time should be reported.\n  * Missing baselines, such as [1-4]. Only several prompt strategies are chosen as baselines.\n\n```tex\n[1] Large Language Models as Evolutionary Optimizers\n[2] Mathematical discoveries from program search with large language models\n[3] Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model\n[4] Large Language Models as Hyper-Heuristics for Combinatorial Optimization\n[5] https://github.com/ai4co/awesome-fm4co\n[6] https://github.com/Thinklab-SJTU/awesome-ml4co\n```", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "__Comment:__ Figure 2 is lacking in detail. A comprehensive example, including detailed prompts and outputs, should be provided.\n\n__Response:__ Thank you for your feedback. Regarding this comment, we aimed to provide a comprehensive textual example, including prompts and model outputs, exactly in Figure 3. To clarify this concern, the first box of Figure 3 shows the text of the prompt that includes the TSP problem definition and the exact output from the Exploration stage of our method. The [Return Condition] represents the prompt text specific to the exploration stage, as discussed in Section 4.1 of the paper. These [Return Conditions] are general prompts that can be applied to various problems without modifications.\n\nThe third box again repeats the problem definition, this time joined with the candidate solution. If this figure remains unclear, we added a new figure with detailed examples of prompts and outputs solving a VRP instance, both in the paper and in the rebuttal PDF. We hope this explanation clarifies the intent behind Figure 3 and addresses your concerns.\n\n\n__Comment:__ It appears that the decomposition process cannot be parallelized across subtasks due to the dependence on preceding Tk−1n.\n\n__Response:__ Thank you for your observation. Regarding this comment, the decomposition process is inherently sequential by design. The tasks within a single decomposition are meant to be executed in sequence, not in parallel. For example, Task $T_{k-1}^n$ might involve computing the distance from the current node to all other nodes, followed by Task $T_{k}^n$, which chooses the closest node as the next node to go to. \n\nThese steps are dependent on each other and thus cannot be parallelized. However, processes from different decompositions can be parallelized. For instance, if one trajectory solves the VRP using the Ant Colony Optimization method and another uses the Nearest Neighbor approach, these processes are independent and can be executed in parallel.\n\n__Comment:__ Limited review of related work:\n\n__Response:__ Thank you for pointing this out. Regarding this comment, we initially did not include certain papers in our review because we believed they focused on different approaches, specifically tuning heuristics to specific instances of combinatorial problems. We now recognize the importance of including these related works to provide a more comprehensive literature review. We have extended our review to include these papers [1-6], acknowledging their relevance and contributions to the field. We hope this expanded literature review addresses your concern and provides a more complete context for our work. Thank you again.\n\n\n__Comment:__ This paper only considers 5-30 nodes, which is too small for the NCO community. I would suggest generating code, like [2-4], in the decomposition or subtask resolution stages if the performance on large-scale instances is inferior.\n\n__Response:__ Thank you for your comment. We initially focused on small problem sizes due to lower computational costs and the ability to obtain optimal solutions. The models without code interpreter are indeed inferior on large scale, but GPT4 with code interpreter can still show  good results. Based on your feedback, we have extended our experiments to include larger instances. To evaluate the performance of SGE against other state-of-the-art methods, we conducted experiments on larger problem sizes across various combinatorial problem domains. Table 1 (rebuttal) presents results on Job Shop Scheduling problems with 50 and 100 jobs, while Table 2 (rebuttal) shows experiments on the Vehicle Routing Problem with 100, 150, and 200 nodes. The results analysis shows that SGE performs better than LNS but falls short compared to LKH3 and Google OR-Tools, which are specifically tailored for combinatorial tasks. However, SGE remains applicable to a broader range of tasks (e.g. reasoning tasks). We believe that SGE's performance could improve further once libraries like LKH3 and Google OR-Tools are integrated into GPT-4's code interpreter, allowing our algorithm to leverage these tools within its solution trajectories.\n\n\n__Comment:__ The optimality gap (w.r.t. the traditional solver, e.g., LKH3, OR-Tools) and inference time should be reported.\n\n__Response:__ We appreciate your suggestion. In our original submission, we provided a comparison between SGE and Google OR-Tools, as shown in Table 2, focusing on small-size problems where globally optimal solutions could be achieved through exhaustive depth-first search. However, to further address your comment and enhance our analysis, we have conducted additional experiments, as mentioned earlier. The results from these larger-scale experiments (Tables 1 and 2), now included in our paper.\n\n\n__Comment:__ Missing baselines, such as [1-4]. Only several prompt strategies are chosen as baselines.\n\n__Response:__ Thank you for pointing this out. Regarding this comment, we acknowledge the importance of including relevant baselines. We assume that [2,3] may perform better than our approach on the Bin Packing problem, but according to [2], this is possible when a diverse list of programs (heuristics) is available as a database to avoid local minima. However, our goal was to develop an algorithm that does not rely on pre-existing examples of good solutions.\n\nTo clarify further, we believe that using [3] (EoH) as a baseline is sufficient, as EoH is an improved version of [1,2]. We chose not to use [4] as a baseline, because it was published very recently, just before the NeurIPS deadline (although it's a good model). However, we have extended our paper to include the EoH baseline and have run its implementation on Job Shop Scheduling (JSP) problems. Table 4 (rebuttal) shows the results of SGE versus EoH. The analysis indicates that while the results are close, SGE achieved slightly better performance. We hope this additional comparison addresses your concern.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
__Response to All:__ We would like to extend our sincere thanks to all the reviewers for their valuable work and insightful comments. We carefully considered the feedback provided and made significant improvements to our paper based on your suggestions.

__Addressing Reviewer Concerns:__ One of the primary concerns shared by the reviewers was the lack of experiments with well-known solvers and heuristics designed for combinatorial problems, as well as the need for testing on larger CP instances. In response, we conducted additional experiments and compiled the results into two new tables, which include comparisons of our method against other solvers and heuristics on larger instances of Job Shop Scheduling and Vehicle Routing Problems (Tables 1 and 2 below). These tables have been incorporated into the revised paper. During our own review, we also identified some errors in the large tables in the appendix and in Table 2 of the paper. Specifically, while conducting experiments versus the global optimum found using the depth-first search method in Google OR-Tools, we mistakenly filled in the results from the LLaMA-2-70B model instead of GPT-4. We will correct this in the final version of the paper. Additionally, we have included new literature and a new baseline that utilizes large language models to create heuristics for CPs (Table 4 below). Recognizing the importance of understanding computational costs, we also added a table detailing the cost of running our algorithm (Table 3 below).

__Clarifying Our Objective:__ We want to clarify that our primary objective was to enhance existing prompting strategies, aiming to make them both generalizable and effective across different tasks. We initially chose combinatorial problems due to their inherent challenges and then extended our approach to demonstrate its generalizability on reasoning tasks. It is important to note that our goal was not to surpass state-of-the-art algorithms in CP research, as these are typically fine-tuned for specific tasks (like neurosolvers do not compete with exact methods). However, we believe that with the continued development of LLMs, they will eventually be able to incorporate both neurosolvers and exact methods in their solution trajectories.

__Research Focus:__ Our exploration focused on several approaches in large language model research: the structure of thought, decomposition, and refinement methods. These approaches are general and effective on simple reasoning tasks, so we aimed to explore whether a general algorithm could also work well on more complex tasks, such as CPs without task-specific modifications.

__Conclusion:__ Once again, we express our gratitude to all the reviewers and area chairs for their efforts and the organization of the review process. The modifications we made have greatly improved the quality of our paper.


__Table 1.__ Percentage performance improvement compared to IO prompting on Job Scheduling Problem. Columns show the number of n jobs and m machines. 
| | n50m10 | n50m20 | n100m10 | n100m20 |
| --- | --- | --- | --- | --- |
| LNS | 57.2 | 59.1 | 59.6 | 60.8 |
| OR-Tools | 61.3 | 63.1 | 62.4 | 61.7 |
| SGE | 59.1 | 62.9 | 61.4 | 60.8 |


__Table 2.__ Percentage performance improvement compared to IO prompting on Vehicle Routing Problem. Columns show the number of nodes.
| | n100 | n150 | n200 |
| --- | --- | --- | --- |
| LNS | 57.8 | 58.7 | 58.1 |
| OR-Tools | 62.5 | 61.2 | 60.3 |
| LKH3 | 65.3 | 64.4 | 65.8 |
| SGE | 59.6 | 60.1 | 59.8 |


__Table 3.__ VRP average total cost.
| Number of Nodes | Total Cost |
| -------- | ------- |
| 5 | $0.0961 |
| 8 | $0.1676 |
| 12 | $0.1964 |
| 20 | $0.3515 |


__Table 4.__ Percentage performance improvement compared to IO prompting on Job Scheduling Problem. Columns show the number of nodes.
| | n50m10 | n50m20 | n100m10 | n100m20 |
| --- | --- | --- | --- | --- |
| EoH | 57.8 | 59.6 | 56.4 | 57.1 |
| SGE | 59.1 | 62.9 | 61.4 | 60.8 |

Meta-review: The paper proposes an LLM prompting algorithm for solving combinatorial optimization problems (COP). Some reviewers had concerns about the importance of the problem. However, studying this subclass of reasoning problems turns out to be interesting. Among the weakness, the reviewers pointed out the lack of comparison with COP tools and not reporting inference time. The rebuttal answered these points, offering comparison with the direct approach of just asking the solution (dubbed IO in the paper). The consensus is that the problem and the algorithm are interesting. I agree with the consensus.
Decision: Accept (poster)