Automating Thought of Search: A Journey Towards Soundness and Completeness

## Abstract

Abstract Planning remains one of the last standing bastions for large language models (LLMs), which now turn their attention to search. Most of the literature uses the language models as world models to define the search space, forgoing soundness for the sake of flexibility. A recent work, Thought of Search (ToS), proposed defining the search space with code, having the language models produce that code. ToS requires a human in the loop , collaboratively producing a sound successor function and goal test. The result, however, is worth the effort: all the tested datasets were solved with 100% accuracy. At the same time LLMs have demonstrated significant progress in code generation and refinement for complex reasoning tasks. In this work, we automate ToS (AutoToS), completely taking the human out of the loop of solving planning problems. AutoToS guides the language model step by step towards the generation of sound and complete search components, through feedback from both generic and domain specific unit tests. We achieve 100% accuracy, with minimal feedback iterations, using LLMs of various sizes on all evaluated domains.

## 1 Introduction

Large language models have shown great promise across countless domains and fields, especially as their architectures become more advanced. Spurred by their abilities in natural language tasks, several recent works have studied AI planning in Large Language Models (LLMs) as a subset of code generation and code refinement. The approaches vary from giving a planning problem to an LLM and asking it to output an entire plan in a single call (Silver et al. 2022; Kambhampati et al. 2024a; Pallagani et al. 2022) to asking an LLM to generate a planning model to be given to an automated planner (Guan et al. 2023; Oswald et al. 2024; Gestrin, Kuhlmann, and Seipp 2024). Between these two extremes, lies a body of work on using language models to plan by performing a combinatorial search (Hao et al. 2023a; Yao et al. 2023a; Besta et al. 2024; Sel et al. 2023). Among these, Thought of Search (ToS) (Katz et al. 2024) stands out; it uses the language models to define the search space for the entire domain at once. It is done simply by soliciting two crucial search components, successor function and goal test. These components are then plugged into a standard search algorithm, such as
Breadth-First Search (BFS) or Depth-First Search (DFS) (Cormen, Leiserson, and Rivest 1990).

Figure: Figure 1: An overview of AutoToS.
Refer to caption: /html/2408.11326/assets/figs/AutoToSv2.png

ToS has an impressive accuracy of 100% on all tested benchmarks and it produces a symbolic model whose soundness and completeness can be verified. However, ToS has a limitation - it requires a human expert in the loop, providing a feedback to the model on the produced code. Our contribution is precisely there.
We automate the iterative feedback and exception handling process through the use of unit tests and printed debugging statements for use with few shot and Chain of Thought (CoT) prompting (Brown et al. 2020; Wei et al. 2022; Kojima et al. 2022), limiting the human expert involvement with the language model.
We test the search components for soundness and completeness and provide feedback to the model when a violation is detected. We use a mixture of domain-independent and domain-specific tests, based on a small number of held out instances.

We exemplify our proposed approach on five representative search problems from the recent literature and test with a variety of large language models of different sizes.
Through automated feedback, we find that the accuracy of the code generated by language models consistently increases to reach 100% across all tested domains. We show that the total number of calls to the language model is typically small, comparable to the results of ToS with human feedback. In an ablation study, we justify the importance of soundness and completeness feedback for obtaining the highly accurate final code.
Finally, we investigate the errors in the code generated by the language models and find that they differ significantly in error distribution.

## 2 Related Works

#### Planning with LLMs

Recently, several works have leveraged LLMs for plan generation.
Valmeekam et al. (2023b) analyzed LLMs ability to generate plans for classical planning problems described in natural language. Raman et al. (2022) generated task plans and used precondition errors as feedback to revise the generated plan. In the same vein, various works have used external verifiers or validators as feedback for LLMs to generate better plans (Stechly, Valmeekam, and Kambhampati 2024; Kambhampati et al. 2024b). Pallagani et al. (2023) investigate training approaches to improve plan generation abilities.
All these approaches use LLMs to solve one problem at a time–essentially treating LLM as a policy. Another line of work has tried to extract policies or generalized plans from LLMs.
Silver et al. (2024) synthesized generalized plans as Python programs from LLMs for planning domains described in a formal language (PDDL).
Further, LLMs have also been used to extract planning problems and models in formal language from their natural language description. Liu et al. (2023) used LLMs to translate natural language planning problems to PDDL problems, and Zuo et al. (2024) proposed a benchmark for such evaluating this ability while Xie et al. (2023) use LLMs to translate natural language goals to PDDL.
Recently, Guan et al. (2023), Gestrin, Kuhlmann, and Seipp (2024) and Oswald et al. (2024) leveraged LLMs to convert natural language domain description to PDDL domains. However, the LLM generated PDDL remains less reliable and difficult to evaluate.

#### Planning with LLMs using Search

A burgeoning research field utilizes LLM’s to conduct a search via structured prompting and feedback for planning and reasoning problems.
Hao et al. (2023a) used LLMs in the loop for Monte Carlos Tree search by treating LLMs as world models to generate next state as well as treating them as reasoning agents to pick the next state to expand. Similarly, Tree of Thoughts (Yao et al. 2023b) used LLMs to generate a search tree—to expand each node in the search tree—and also used LLMs for evaluating the choices and selecting the next best state. Graph of Thoughts (Besta et al. 2024) modeled LLM generated output as a graph instead of a tree and reduces the number of LLM calls. Similar approaches with integration to search are also proposed for interactive domains (Zhou et al. 2023; Shinn et al. 2023). While these approaches have shown some success, their significant reliance on LLMs for generating successors makes them not only extremely inefficient but also very unreliable.
Thought of Search (ToS) (Katz et al. 2024), on the other hand, proposed using LLMs to generate code for the successor and goal functions for problems described with natural language. Once these functions are available, any offline search algorithm can be used to solve any problem in the domain. This approach is significantly more efficient than approaches which use LLMs in the loop during search. However, it requires human expert for the feedback. Our work focuses on alleviating the requirement of human in the loop feedback.

#### Code Generation with LLMs

LLM’s abilities are rapidly advancing in program synthesis.
Various benchmarks have been established to evaluate correctness of code generated by LLMs (Chen et al. 2021; Puri et al. 2021; Li, Parsert, and Polgreen 2024), and subsequent
approaches have demonstrated human level performance on coding benchmarks (Zhong, Wang, and Shang 2024; Muennighoff et al. 2024). Chen et al. (2024) and Zhang et al. (2023) use errors from execution as feedback to LLMs so they can refine the code.
Madaan et al. (2023), Gou et al. (2024) and Huang et al. (2024) discussed the use of external verifies to curate feedback for LLMs.
Jiang, Wang, and Wang (2023) introduced unit test results and error messages to LLMs.
Recently, LLMs code generation has also shown to help in mathematical reasoning problems (Zhong, Wang, and Shang 2024).
Inspired by successes in these works, we propose to automate the feedback for ToS by using both generic and domain-specific unit tests and validators.

## 3 Background

In this work we follow the notation of Katz, Moshkovich, and Karpas (2018), slightly adapting it for our purposes.
A deterministic planning problem over a state space is a tuple
$\Pi=\langle S,A,s_{0},S_{G},f\rangle$, where $S$ is a finite set of states, $A$ is a finite set of action labels, $s_{0}\in S$ is the initial
state, $S_{G}\subseteq S$ is the set of goal states, and $f:S\times A\rightarrow S$ is the transition function, such that $f(s,a)$
is the state which applying action $a$ in state $s$ leads to. A triplet $\langle s,a,f(s,a)\rangle$ is called a transition.
A solution to such a problem is a sequence of states and action labels (also called a trace) $\rho=\langle s_{0},a_{1},s_{1},a_{2},\ldots a_{n},s_{n}\rangle$, such that $f(s_{i},a_{i+1})=s_{i+1}$ for $0\leq i<n$ and $s_{n}\in S_{G}$.
In cases when the action labels are not important, they can be dropped from the definition.

The “black box” approach encodes the state space with a tuple $\Pi_{bb}=\langle s_{0},\mathit{succ},\mathit{isgoal}\rangle$, where $s_{0}$ is the initial state,
$\mathit{succ}:S\rightarrow 2^{A\times S}$ is a successor generator, and
$\mathit{isgoal}:S\rightarrow\{T,F\}$ is the goal test function.

A solution to the black-box problem is a sequence of states and action labels (a trace) $\pi=\langle s_{0},a_{1},s_{1},a_{2},\ldots a_{n},s_{n}\rangle$, such that $\langle a_{i+1},s_{i+1}\rangle\in\mathit{succ}(s_{i})$ for $0\leq i<n$ and $\mathit{isgoal}(s_{n})=T$.
Here as well, if action labels are not important, they can be dropped.

We now establish the correspondence between the black-box encoding and the planning problem.

###### Definition 1 (Soundness and completeness)

We say that $\mathit{isgoal}$ is sound if $\mathit{isgoal}(s)=F$ for all $s\not\in S_{G}$ and $\mathit{isgoal}$ is complete if $\mathit{isgoal}(s)=T$ for all $s\in S_{G}$.
We say that $\mathit{succ}$ is sound if $\mathit{succ}(s)\!\subseteq\!\{\langle a,s^{\prime}\rangle\!\mid\!f(s,a)\!=\!s^{\prime}\}$ and $\mathit{succ}$ is complete if $\mathit{succ}(s)\supseteq\{\langle a,s^{\prime}\rangle\mid f(s,a)=s^{\prime}\}$.

Sound and complete successor generator and goal test provide the “black box” description of the state space of the planning problem $\Pi$. In such cases, a solution to $\Pi_{bb}$ is guaranteed to be a solution to $\Pi$, and if no solution for $\Pi_{bb}$ exists, then $\Pi$ also must be unsolvable.

If the successor generator and goal test are sound, but not necessarily complete, it is still the case that a solution to $\Pi_{bb}$ is guaranteed to be a solution to $\Pi$ and therefore soundness allows us to reliably use $\Pi_{bb}$ for producing solutions for $\Pi$.

###### Definition 1 (Soundness and completeness)

## 4 Proposed Approach and Methodology

We build upon the previous work that proposed producing a code implementation of $\mathit{succ}$ and $\mathit{isgoal}$ functions (Katz et al. 2024), taking the human out of the feedback loop. Similar to that work, we care about two properties, soundness and completeness.
As we deal with planning problems described in a natural language, we do not have the formally defined planning task $\Pi$. Albeit not stated formally, previous work on generating $\mathit{succ}$ and $\mathit{isgoal}$ with language models assumes the existence of a human expert with the ability to access $\Pi$ (often in their mind). Examples of such access include a feedback on the code of $\mathit{succ}$ and $\mathit{isgoal}$ produced by the LLM (Katz et al. 2024) or validating a solution obtained from the LLM in cases when $\mathit{succ}$ and $\mathit{isgoal}$ are implemented through LLMs (Hao et al. 2023a; Yao et al. 2023a; Besta et al. 2024; Sel et al. 2023). Here, we make a similar assumption, but request a different access to $\Pi$. In order to challenge the soundness and completeness of the produced functions, the human expert is asked to produce unit tests, information which can provide evidence of unsoundness or incompleteness. The evidence can then be used to automatically feedback the model with the information needed to fix the code. We deal with three types of information, exemplified on the 24 Game (Yao et al. 2023a).

- •
Examples of inputs to $\mathit{isgoal}$ for which the correct output is known. For instance, we know that $\mathit{isgoal}([24])$ should be true and $\mathit{isgoal}([24,1])$ should be false.
- •
Examples of inputs to $\mathit{succ}$ for which some of the correct outputs are known. For instance, we know that [24], [2], and [-2] are valid successors of [6,4] and therefore should be in $\mathit{succ}([6,4])$.
- •
A partial soundness check for a transition $\langle s,a,t\rangle$ quickly invalidating (obviously) incorrect transitions. For instance, in 24 Game we know that the successor state $t$ must be of length exactly one less than $s$.

The first two are are usually readily available and often come with the description of the problem. The third one might require some level of understanding of the problem being solved, but it is always possible to use a trivial partial soundness test that always reports that there are no issues. Figure [1](#S1.F1) presents an overview of our approach, describing how the provided information is used.

- Step 1
Following Katz et al. (2024), we start with the initial prompts asking for the successor function $\mathit{succ}$ and the goal test $\mathit{isgoal}$.
- Step 2
Then, we perform the goal unit tests, providing feedback to the model in cases of failure, repeatedly asking for a new $\mathit{isgoal}$ until all goal unit tests have passed or a predefined number of iterations was exhausted.
- Step 3
Once $\mathit{isgoal}$ has passed the unit tests, we perform a soundness check of the current $\mathit{succ}$ and $\mathit{isgoal}$
functions. We do that by plugging these functions in a BFS extended with additional checks and run it on a few example problem instances.
If BFS finished, we check whether the goal was indeed reached. If not, that means that $\mathit{isgoal}$ failed to correctly identify a state as a non-goal state and we provide that as feedback to the model, repeating Steps 2 and 3.
- Step 4
(Optional) Once the previous steps were finished, we perform the successor unit test, providing feedback to the language model in case of failure.

Every time a goal test fails, we go back to Step 2, every time the successor test fails, we go back to Step 3. After the first step,
we always have $\mathit{succ}$ and $\mathit{isgoal}$ that can be plugged into a blind search algorithm. However, if Step 3 fails, we have an indication that we cannot trust the solutions produced by that algorithm.

Example feedback produced in Steps 2, 3, and 4 can be seen in Listing [1](#listing1). In what follows, we provide detailed description of each step of AutoToS.

### 4.1 System prompt

We instruct the model to provide answers in convenient form for integrating as a search component. Thus, the produced code should consist of a single, self-contained function. Following existing work (Zhong, Wang, and Shang 2024; Yang et al. 2024), we devise the following system prompt.
{callout}
You are a Python coding assistant. Help me generate my Python functions based on the task descriptions. Please always generate only a single function and keep all imports in it. If you need to define any additional functions, define them as inner functions. Do not generate examples of how to invoke the function. Please do not add any print statements outside the function. Provide the complete function and do not include any ellipsis notation.

### 4.2 Step 1: Initial prompt

While the initial prompt is the primary source of information for the language model and therefore very important, we assume that we have very limited control over it. We therefore mostly take the existing initial prompt from previous work, only ensuring that it includes an example input to the requested function in the correct format (Katz et al. 2024).

### 4.3 Step 2: Goal function check

Goal unit tests assume the existence of a few known goal and non-goal states. If the goal function $\mathit{isgoal}$ incorrectly identifies a goal state, then it is incomplete, according to Definition [1](#Thmdefinition1). If it incorrectly identifies a non-goal state, then it is not sound. A search with a non-sound goal function can incorrectly report that a solution was found. One illustrative example from the 24 Game is a state [24, 1], which a goal test function may incorrectly identify as a goal state and stop before the actual solution was found – in this case, another arithmetic operation was needed. Whenever an issue with either goal function soundness or completeness was identified, we give feedback to the language model with the description of the failure and the state for which the failure occurred. See Listing [1](#listing1) (top) for an example feedback.
Here and later we use a chain of thought
style request, asking the model to discuss why a mistake was made and to come up with a fix.

### 4.4 Step 3: Successor function soundness check

A soundness check assumes the existence of example problem instances for which we know how to validate that a goal was reached.
We extend the BFS/DFS search with additional checks as follows.
First, both the successor and goal test functions are wrapped with a timeout of 1 second. These functions should be able to finish in a few milliseconds and therefore 1 second timeout is an indication of an issue with the function. An issue can be as simple as unnecessary computation or multiple successor steps performed instead of a single step or it can even be an infinite loop.
Second, successor function is wrapped with a check whether it modifies the input state. Such modifications often happen when successor states are copied from the input state and modified. Shallow copy of the input state was observed in the previous work (Katz et al. 2024).
Third, for every successor generated at the expansion step of BFS, a partial soundness check is performed, examining the validity of transitioning from the parent state to the successor state. An example of such a partial soundness check in 24 Game is that the successor state size must be one number less than the parent state. If that does not hold, the successor function is not sound according to Definition [1](#Thmdefinition1). It is worth emphasizing that this partial soundness check can be trivial, reporting True for every pair of parent and successor states.
If any of the checks did not pass, we feedback the language model with the respective error message, providing example input state and the unexpected (or expected and unobserved) output, until all tests are passed or a predefined number of iterations was exhausted. See Listing [1](#listing1) (middle) for an example feedback.

### 4.5 Step 4: Successor function completeness check

A successor function completeness check assumes the existence of a few known parent and successor states. These can include all successors for some parent state or a subset thereof. If the successor function does not produce some of the known successors, then it is not complete according to Definition [1](#Thmdefinition1). While completeness is not required for producing valid (sound) solutions, incomplete functions may not generate the part of the search space where goal states are located and therefore may not be able to find solutions. Improving completeness is therefore an optional step that may improve the accuracy of the produced code.
Here as well, we give feedback to the language model with the respective error message, providing example input state and the missing successors. See Listing [1](#listing1) (bottom) for an example feedback.

Figure: Listing 1 24 Game example feedback.

### 4.6 Automation, evaluation and validation

Since the expensive calls to large language models are not performed during search, there is no need to artificially restrict the algorithms to their incomplete variants ( e.g., Yao et al. (2023a)) and sound and complete algorithms BFS/DFS can be used for solving the search problems. Still, as the human feedback is before the feedback loop and the search components produced are not guaranteed to be sound, the solutions produced must be validated for soundness.

## 5 Experiments

In order to check the feasibility of our approach, AutoToS, we conduct experiments with a representative collection of
five search/planning problems: BlocksWorld (Gupta and Nau 1992), PrOntoQA (Hao et al. 2023b), Mini Crossword and 24 Game (Yao et al. 2023b), and Sokoban (Junghanns and Schaeffer 1997). Four of these domains appeared in ToS (Katz et al. 2024), while the Sokoban domain did not.
We test the performance of various LLMs from three families, using both the largest and smallest models from the same family. Specifically, we use GPT-4o and GPT-4o-Mini (Achiam et al. 2023), Llama3.1-70b and Llama3.1-405b (Dubey et al. 2024), as well as DeepSeek-CoderV2 (DeepSeek-AI et al. 2024). We additionally tested Llama3-70b (AI@Meta 2024), Mistral7x-8b (Jiang et al. 2024), and DeepSeek-CoderV2-Lite, finding these models to perform poorly and therefore excluded from consideration. We use Greedy decoding with maximum context length for each model.
For each domain, we restrict the number of calls to the language model per function to 10
(total maximum of 19 per domain).
We repeat each experiment 5 times.

Following ToS, we use a simple implementation of BFS and DFS search algorithms in Python. DFS is used for Mini Crosswords, while BFS is used for the other 4 domains. Each successor function execution is limited to 1 second and each overall search is limited to 600 seconds.
For each domain, a few (up to 10) instances are used for creating the unit tests. In one case, these instances are taken out of the available set of instances, in other cases we invent new instances. The rest are used for evaluating the accuracy of the generated code, where accuracy measures the percentage of the instances solved. In the case of BFS search, we also require the solution produced to be optimal. This is relevant to BlocksWorld and Sokoban  where the solution length matters, but irrelevant for PrOntoQA, where solution is a boolean answer, and 24 Game, where all solutions are of the same length.
It is important to emphasize again that if successor function and goal test are sound and complete, then the solution produced by BFS/DFS is guaranteed to be correct (and in the case of BFS optimal). However, since no such guarantees are available, we automatically validate every solution obtained.
Experiments were performed on a AMD Ryzen 7 4800H.
All models were accessed via API, except for Llama and Deepseek, which were interacted with through a chat interface.
Model correspondences logs across all 5 domains are provided in the Appendix.

Figure: Figure 2: Progression of accuracy values during AutoToS.
Refer to caption: /html/2408.11326/assets/figs/test_plot.png

The aim of our evaluation is to test the following hypotheses.
First,
whether a partial soundness test improves the accuracy of AutoToS.
Second, whether the (optional) completeness step improves the accuracy of AutoToS or not.
Third, whether the number of calls to the language model increases significantly compared to ToS.
Finally, whether the performance of AutoToS is consistent across different language models of varying sizes.

### 5.1 24 Game

The 24 Game (Yao et al. 2023b) takes 4 integers as an input that can be manipulated through the four most common arithmetic operations: addition, subtraction, multiplication, and division. The goal of the game is to produce a formula that evaluates to 24, if one exists. States are represented as lists of length 4 or less.

Data
We use the set of 1362 instances (Yao et al. 2023b; Katz et al. 2024) and we take out the first 10 instances for unit tests. Goal unit tests use [24] for goal and [], [3] ,[24, 1], [1, 6, 4], [1, 1, 4, 6] for non-goal examples. Successor completeness test uses the initial state with all its successors for each of the 10 instances, as well as a single transition along a known solution path for each of these instances.
For example, the successors of [6, 6, 6, 6] are [1, 6, 6], [6, 6, 12], [0, 6, 6], and [6, 6, 36]. Also, a successor of [6, 6, 12] along the known solution path is [6, 18] and of [6, 18] is [24].

Partial soundness test
For the partial soundness test we check whether the number of elements in a successor state is one less than for the parent state.

Solution validation A solution is a sequence of states $s_{0},s_{1},s_{2},s_{3}$, where $s_{0}$ is the initial state, $s_{3}=[24]$ is the goal state, and $\langle s_{0},s_{1}\rangle$, $\langle s_{1},s_{2}\rangle$, and $\langle s_{2},s_{3}\rangle$, are valid transitions. We check that all these hold for a given sequence.

**Table 1: The average number of calls to the language model per domain.**
|  |  | 24 Game | PrOntoQA | Sokoban | Crossword | BlocksWorld |
| --- | --- | --- | --- | --- | --- | --- |
| AutoToS | GPT-4o-mini | 8.8 | 4.8 | 6.4 | 9.6 | 10.0 |
| GPT-4o | 3.4 | 2.6 | 2.2 | 5.8 | 2.0 |  |
| Llama3.1-405b | 3.4 | 2.0 | 2.6 | 4.0 | 3.2 |  |
| Llama3.1-70b | 7.4 | 2.0 | 8.2 | 6.2 | 5.8 |  |
|  | DeepSeek-CoderV2 | 4.4 | 2.0 | 2.8 | 6.6 | 4.2 |
| ToS | GPT-4 | 2.2 | 2.6 | NA | 3.8 | 3.8 |

### 5.2 BlocksWorld

BlocksWorld is a classic AI planning domain, where the task is to rearrange blocks in towers (Gupta and Nau 1992).
There are 4 actions: stack a block on top of another block, unstack a block from another block, put a block down on the table, and pick a block up from the table. States are represented as dictionaries based on ‘clear’, ‘on-table’, ‘arm-empty’, ‘holding’, and ‘on’, describing whether a block is clear (no block above it in the tower), the block is on the table, whether the arm is not holding a block and which blocks are on which.

Data
The domain has a PDDL representation and a large collection of 502 instances was created by Valmeekam et al. (2023a) and used in the recent literature (Hao et al. 2023a). We use the entire collection for evaluation and invent 2 example states (and transitions along 2 plans) per unit test. The examples can be found in the Appendix.

Partial soundness test
For the partial soundness test we notice that in each tower there is a top block (that is clear) and there is a bottom block (that is on the table). Therefore we simply check that the number of blocks in the ‘clear’ list is the same as
in the ‘on-table’ list.

Solution validation
As the instances are given in PDDL, we simply translate the solution into a PDDL format and use an external validator VAL (Howey and Long 2003).

Figure: Figure 3: Average number of feedback calls for goal soundness, successor soundness, and successor completeness.
Refer to caption: /html/2408.11326/assets/x1.png

### 5.3 Mini Crosswords

The mini crosswords (Yao et al. 2023b) is a 5x5 crosswords dataset where the input describes the 5 horizontal and 5 vertical clues and the output is the full 25 letters board. We provide a list of horizontal and vertical clues which are strings of words. The verifier ensures that the size of each word in the rows or columns does not exceed 5.

Data
We use the existing 20 instances (Yao et al. 2023b; Katz et al. 2024), all used for evaluation, with the unit tests constructed based on 3 invented states each, with the successor completeness based on a state in which one horizontal and one vertical clue already filled, which limits the number of possible successors considerably.

Partial soundness test
The partial soundness test verifies that at most 5 new letters are filled in one transition, as well as that the number of unfilled letters does not get larger.

Solution validation
A crossword puzzle is solved if the end result is valid, meaning every vertical and horizontal clue is present in the list of possible clues.

### 5.4 PrOntoQA

Logical reasoning can be viewed as a search problem of finding a sequence of logical rules that when applied to the known facts, derive or disprove the target hypothesis. Previous work applies
MCTS
with successor function and rewards obtained by calling an LLM, to examples from the PrOntoQA dataset (Hao et al. 2023b) to derive the answer but also the proof, a sequence of reasoning steps. A state is therefore a set of the facts known to be true.

Data
We use the existing set of 4000 instances entirely for evaluation, inventing 3 examples per unit test.

Partial soundness test
A partial soundness test simply checks that each transition adds a single known fact to the state, ensuring that the state size increases by exactly 1.

Solution validation
In order to validate the solution, we compare to the known correct answer.

### 5.5 Sokoban

Sokoban (Junghanns and Schaeffer 1997) is a planning problem with PSPACE-complete complexity even for non-optimal planning. The problem, despite its simple conceptual rules, is a notoriously hard for generic AI planners and even for specialized solvers. We use a 2-D grid setup, in which, given equal number of boxes and goal squares, the player needs to push all boxes to goal squares without crossing walls or pushing boxes into walls. The player can only move upward, downward, leftward and rightward where many pushes are irreversible. The domain has a known planning model, described in PDDL of varying grid sizes and difficulties. States are represented as dictionaries with entries: ‘at-player,’ which represents a single pair of coordinates, and ‘at-stone’, a list of coordinates for the stones.

Data
We use the collection of PDDL problem instances from the International Planning Competition (IPC) 2008. Out of these instances, we select a subset that can be solved relatively quickly by using the blind search configuration of the efficient planner Fast Downward (Helmert 2006) and choose the instances that were solved in under 5 seconds. This resulted in 11 instances. We use the entire set for evaluation and invent 3 states per unit test.

Partial soundness test
The
test simply checks whether the locations of the player and the stones are all different.

Solution validation
Similar to BlocksWorld, we translate the solution to PDDL format and use VAL.

Figure: Figure 4: Partition of the errors in the generated code.
Refer to caption: /html/2408.11326/assets/figs/errors/Average_errors_DeepSeek-Coder-V2.png

Figure [2](#S5.F2) depicts the progression of accuracy values for three time points in the process, comparing using the partial soundness test (solid lines, ‘w/ val’) and not (dotted lines, ‘w/o val’). Same colors represent the same language model. The first point in the process corresponds to when the search components are first created, meaning no feedback at all. The second point in the process is when the goal and successor function soundness tests are not failing. The third and final point is the end of the process, when successor completeness tests are not failing. Each point is also annotated with the percentage of cases the step was reached. The aggregation is performed over such cases.
The figure allows us to find answers for both the first and the second hypotheses.
We can clearly see the benefit from using the partial soundness test, even as simple as the ones we described above. Going forward, we therefore restrict our attention to using the partial soundness test.
Further, we can clearly see the strong increase in accuracy when not stopping after the soundness test passes and performing the completeness tests, across all models.

Table [1](#S5.T1) shows the total number of calls to the language model until soundness and completeness tests pass. Note that the minimum number of calls is 2, one for each component, even without feedback. We see that the number of automated calls is comparable to the one when a human expert is giving the feedback to the model. To look deeper into how the feedback is partitioned among the three phases, Figure [3](#S5.F3) compares the numbers across language models and domains. We see that the larger models rarely require any feedback on the goal function and only a few iterations on the successor function, and more often than not on completeness.

Finally, we can observe that there is no single model that performs better than all other, according to all parameters and the performance is quite consistent across the large models. Interestingly, the smaller model GPT-4o-mini performs quite well in terms of accuracy.

## 6 Code Errors Discussion

To be able to improve the performance of the large language models in generating search components,
it is important to understand the errors in the code produced by these models. In what follows we first present the error categories and show the partitioning of the errors to these categories and then elaborate on a few interesting cases.

### 6.1 Error categories

AutoToS distinguishes 10 error categories and gives each a separate feedback.

| 1. $\mathit{succ}$ soundness test failed. | 6. $\mathit{isgoal}$ exception occurred. |
| --- | --- |
| 2. Input state changed by $\mathit{succ}$. | 7. Search timeout in $\mathit{succ}$ soundness test. |
| 3. $\mathit{succ}$ completeness failed. | 8. $\mathit{succ}$ execution took too long. |
| 4. $\mathit{isgoal}$ soundness failed. | 9. $\mathit{isgoal}$ execution took too long. |
| 5. $\mathit{succ}$ exception occurred. | 10. Response parsing error. |

Interestingly, we did not observe any errors in the last two categories. Further only 1, 2, and 3 errors in categories 6, 8, and 7, respectively. The partition of the errors to the other 5 categories (see Figure [4](#S5.F4)), shows just how much the models differ in the type of errors produced. Interestingly, the DeepSeek-Coder-V2 model rarely produces code that triggers exception or changes the input state and even typically passes the goal soundness test.
Other models, especially the smaller ones, are more diverse in errors produced. Across all models, the majority of the errors account for the failed successor soundness and completeness tests.

### 6.2 Bloopers

We noticed a few “bloopers,” interesting phenomena that occur during AutoToS. We share these observations in a hope of shedding some light onto future understanding of LLM code generation for planning and search problems.

The first blooper occurs in the 5x5 Crossword for Llama3.1-70b. The representation of a Crossword instance includes vertical and horizontal clues which are lists of 5 words each. The model handles horizontal clues well by simply checking whether a word in row i is in the ith list in horizontal clues. For vertical clues, however, the model checks whether the word in column i is at position i among the clues for every column. Indeed the initial prompt from obtaining successor function clearly states that:

[…] horizontal_answers is a list where element i is a list of possible answers to clue in row i, and vertical_answers is a list where element i is a list of possible answers to clue in column i.

The second blooper occurs in the GPT-4o-mini, Llama3.1-70b, and even in Llama3.1-405b on the BlocksWorld domain.
When generating successors for the unstack block from another block action, the models check if the block is clear,
but never actually check whether the arm is empty. The resulting code, in cases when a block is already held, can generate a successor state in which the held block is overwritten with the one that is unstacked, and therefore disappears from the state. On some instances in the evaluation set the situation does not occur. On others, invalid solutions are produced and the accuracy score falls far below 100%. The AutoToS feedback in the next iterations often solves the problem.

Another blooper occurs in Sokoban, when Llama3.1-70b generates the initial successor function and the goal test, and no partial soundness check is performed. The model generates a helper function is_clear that only checks whether the location on the grid is 0 0 or $2$ (not a wall), disregarding whether any of the stones are currently at the location. This allows the player to move and push stones to the locations of other stones, resulting in the accuracy score of 0. Since the unit tests pass in this case, no additional iterations were performed. The partial soundness check would catch the error the first time a faulty state is generated (a state where multiple stones are at the same location or a player and a stone are at the same location). The prompt explicitly states what it means to be clear:
{callout}
The maze is defined by a grid of values 0,1, and 2, where 2 means it is a goal location for a stone, 1 means the cell is blocked, and either 0 or 2 means that the cell can be occupied. A cell is clear if it can be occupied, but is not occupied by either the player or any stone.

Yet another blooper happens in 24 Game with GPT-4o-mini and DeepSeek-CoderV2 when no partial soundness check is performed. When creating a new state out of the input state, two numbers are chosen to perform an arithmetic operation and in order to obtain the remaining numbers, the code selects the numbers from the state that are different from the two chosen numbers. Thus in cases of duplicate numbers, the state size becomes more than one smaller than of the parent and on some instances the produced solutions would not be valid. The AutoToS completeness feedback eventually solves the problem in these cases.

## 7 Conclusions and Future Work

We automate the process of generating correct and sound code for the search components by leveraging debugging and exception handing with natural language, code feedback, iterative reprompting. We demonstrate the performance of our approach, AutoToS, across various sized models and across search problem domains used by the planning community. With just a few calls to the language model, we demonstrate that we can obtain the search components without any direct human in the loop feedback, ensuring soundness, completeness, accuracy, and nearly 100% accuracy across all models and all domains.

For future work it would be interesting to see if the language models could generate the unit tests as well as the partial soundness tests instead of relying on the user writing these for a specific domain. The partial soundness test is related to the notion of invariants in planning (Alcázar and Torralba 2015). It is worth exploring whether LLMs can help us derive such invariants.
Finally, seeing that smaller language models can achieve accuracy on par with the largest ones, begs the question of whether it would be possible to finetune an even smaller model and achieve a similar or better accuracy.

## References

- Achiam et al. (2023)
Achiam, J.; Adler, S.; Agarwal, S.; Ahmad, L.; Akkaya, I.; Aleman, F. L.;
Almeida, D.; Altenschmidt, J.; Altman, S.; Anadkat, S.; et al. 2023.
Gpt-4 technical report.
*arXiv preprint arXiv:2303.08774*.
- AI@Meta (2024)
AI@Meta. 2024.
Llama 3 Model Card.
- Alcázar and Torralba (2015)
Alcázar, V.; and Torralba, Á. 2015.
A Reminder about the Importance of Computing and Exploiting
Invariants in Planning.
In Brafman, R.; Domshlak, C.; Haslum, P.; and Zilberstein, S., eds.,
*Proceedings of the Twenty-Fifth International Conference on Automated
Planning and Scheduling (ICAPS 2015)*, 2–6. AAAI Press.
- Besta et al. (2024)
Besta, M.; Blach, N.; Kubicek, A.; Gerstenberger, R.; Podstawski, M.;
Gianinazzi, L.; Gajda, J.; Lehmann, T.; Niewiadomski, H.; Nyczyk, P.; et al.
2024.
Graph of thoughts: Solving elaborate problems with large language
models.
In *Proceedings of the AAAI Conference on Artificial
Intelligence*, volume 38, 17682–17690.
- Brown et al. (2020)
Brown, T.; Mann, B.; Ryder, N.; Subbiah, M.; Kaplan, J. D.; Dhariwal, P.;
Neelakantan, A.; Shyam, P.; Sastry, G.; Askell, A.; et al. 2020.
Language models are few-shot learners.
*Advances in neural information processing systems*, 33:
1877–1901.
- Chen et al. (2021)
Chen, M.; Tworek, J.; Jun, H.; Yuan, Q.; et al. 2021.
Evaluating Large Language Models Trained on Code.
*CoRR*, abs/2107.03374.
- Chen et al. (2024)
Chen, X.; Lin, M.; Schärli, N.; and Zhou, D. 2024.
Teaching Large Language Models to Self-Debug.
In *ICLR*. OpenReview.net.
- Cormen, Leiserson, and Rivest (1990)
Cormen, T. H.; Leiserson, C. E.; and Rivest, R. L. 1990.
*Introduction to Algorithms*.
The MIT Press.
- DeepSeek-AI et al. (2024)
DeepSeek-AI; Liu, A.; Feng, B.; Wang, B.; Wang, B.; Liu, B.; Zhao, C.; Dengr,
C.; Ruan, C.; et al. 2024.
DeepSeek-V2: A Strong, Economical, and Efficient Mixture-of-Experts
Language Model.
arXiv:2405.04434.
- Dubey et al. (2024)
Dubey, A.; Jauhri, A.; Pandey, A.; Kadian, A.; Al-Dahle, A.; Letman, A.;
Mathur, A.; Schelten, A.; Yang, A.; Fan, A.; Goyal, A.; et al. 2024.
The Llama 3 Herd of Models.
arXiv:2407.21783.
- Gestrin, Kuhlmann, and Seipp (2024)
Gestrin, E.; Kuhlmann, M.; and Seipp, J. 2024.
NL2Plan: Robust LLM-Driven Planning from Minimal Text Descriptions.
arXiv:2405.04215.
- Gou et al. (2024)
Gou, Z.; Shao, Z.; Gong, Y.; yelong shen; Yang, Y.; Duan, N.; and Chen, W.
2024.
CRITIC: Large Language Models Can Self-Correct with
Tool-Interactive Critiquing.
In *The Twelfth International Conference on Learning
Representations*.
- Guan et al. (2023)
Guan, L.; Valmeekam, K.; Sreedharan, S.; and Kambhampati, S. 2023.
Leveraging pre-trained large language models to construct and utilize
world models for model-based task planning.
*Advances in Neural Information Processing Systems*, 36:
79081–79094.
- Gupta and Nau (1992)
Gupta, N.; and Nau, D. S. 1992.
On the Complexity of Blocks-World Planning.
56(2–3): 223–254.
- Hao et al. (2023a)
Hao, S.; Gu, Y.; Ma, H.; Hong, J.; Wang, Z.; Wang, D.; and Hu, Z.
2023a.
Reasoning with Language Model is Planning with World Model.
In *Proceedings of the 2023 Conference on Empirical Methods in
Natural Language Processing (EMNLP 2023)*.
- Hao et al. (2023b)
Hao, S.; Gu, Y.; Ma, H.; Hong, J.; Wang, Z.; Wang, D.; and Hu, Z.
2023b.
Reasoning with Language Model is Planning with World Model.
In *Proceedings of the 2023 Conference on Empirical Methods in
Natural Language Processing*, 8154–8173.
- Helmert (2006)
Helmert, M. 2006.
The Fast Downward Planning System.
*Journal of Artificial Intelligence Research*, 26: 191–246.
- Howey and Long (2003)
Howey, R.; and Long, D. 2003.
VAL’s Progress: The Automatic Validation Tool for PDDL2.1 used in
the International Planning Competition.
In Edelkamp, S.; and Hoffmann, J., eds., *Proceedings of the
ICAPS 2003 Workshop on the Competition: Impact, Organisation, Evaluation,
Benchmarks*.
- Huang et al. (2024)
Huang, J.; Chen, X.; Mishra, S.; Zheng, H. S.; Yu, A. W.; Song, X.; and Zhou,
D. 2024.
Large Language Models Cannot Self-Correct Reasoning Yet.
In *The Twelfth International Conference on Learning
Representations*.
- Jiang et al. (2024)
Jiang, A. Q.; Sablayrolles, A.; Roux, A.; Mensch, A.; et al. 2024.
Mixtral of Experts.
arXiv:2401.04088.
- Jiang, Wang, and Wang (2023)
Jiang, S.; Wang, Y.; and Wang, Y. 2023.
SelfEvolve: A Code Evolution Framework via Large Language Models.
arXiv:2306.02907.
- Junghanns and Schaeffer (1997)
Junghanns, A.; and Schaeffer, J. 1997.
Sokoban: A Challenging Single-Agent Search Problem.
In *International Joint Conference on Artificial Intelligence*.
- Kambhampati et al. (2024a)
Kambhampati, S.; Valmeekam, K.; Guan, L.; Verma, M.; Stechly, K.; Bhambri, S.;
Saldyt, L. P.; and Murthy, A. B. 2024a.
Position: LLMs Can’t Plan, But Can Help Planning in
LLM-Modulo Frameworks.
In *Forty-first International Conference on Machine Learning*.
- Kambhampati et al. (2024b)
Kambhampati, S.; Valmeekam, K.; Guan, L.; Verma, M.; Stechly, K.; Bhambri, S.;
Saldyt, L. P.; and Murthy, A. B. 2024b.
Position: LLMs Can’t Plan, But Can Help Planning in
LLM-Modulo Frameworks.
In *Forty-first International Conference on Machine Learning*.
- Katz et al. (2024)
Katz, M.; Kokel, H.; Srinivas, K.; and Sohrabi, S. 2024.
Thought of Search: Planning with Language Models Through The Lens of
Efficiency.
arXiv:2404.11833 [cs.AI].
- Katz, Moshkovich, and Karpas (2018)
Katz, M.; Moshkovich, D.; and Karpas, E. 2018.
Semi-Black Box: Rapid Development of Planning Based Solutions.
In *Proceedings of the Thirty-Second AAAI Conference on
Artificial Intelligence (AAAI 2018)*, 6211–6218. AAAI Press.
- Kojima et al. (2022)
Kojima, T.; Gu, S. S.; Reid, M.; Matsuo, Y.; and Iwasawa, Y. 2022.
Large language models are zero-shot reasoners.
*Advances in neural information processing systems*, 35:
22199–22213.
- Li, Parsert, and Polgreen (2024)
Li, Y.; Parsert, J.; and Polgreen, E. 2024.
Guiding Enumerative Program Synthesis with Large Language Models.
In *CAV (2)*, volume 14682 of *Lecture Notes in
Computer Science*, 280–301. Springer.
- Liu et al. (2023)
Liu, B.; Jiang, Y.; Zhang, X.; Liu, Q.; Zhang, S.; Biswas, J.; and Stone, P.
2023.
LLM+P: Empowering Large Language Models with Optimal Planning
Proficiency.
*CoRR*, abs/2304.11477.
- Madaan et al. (2023)
Madaan, A.; Tandon, N.; Gupta, P.; Hallinan, S.; Gao, L.; Wiegreffe, S.; Alon,
U.; Dziri, N.; Prabhumoye, S.; Yang, Y.; Gupta, S.; Majumder, B. P.; Hermann,
K.; Welleck, S.; Yazdanbakhsh, A.; and Clark, P. 2023.
Self-Refine: Iterative Refinement with Self-Feedback.
In Oh, A.; Naumann, T.; Globerson, A.; Saenko, K.; Hardt, M.; and
Levine, S., eds., *Advances in Neural Information Processing Systems*,
volume 36, 46534–46594. Curran Associates, Inc.
- Muennighoff et al. (2024)
Muennighoff, N.; Liu, Q.; Zebaze, A. R.; Zheng, Q.; Hui, B.; Zhuo, T. Y.;
Singh, S.; Tang, X.; von Werra, L.; and Longpre, S. 2024.
OctoPack: Instruction Tuning Code Large Language Models.
In *ICLR*. OpenReview.net.
- Oswald et al. (2024)
Oswald, J.; Srinivas, K.; Kokel, H.; Lee, J.; Katz, M.; and Sohrabi, S. 2024.
Large Language Models as Planning Domain Generators.
In Bernardini, S.; and Muise, C., eds., *Proceedings of the
Thirty-Fourth International Conference on Automated Planning and Scheduling
(ICAPS 2024)*. AAAI Press.
- Pallagani et al. (2022)
Pallagani, V.; Muppasani, B.; Murugesan, K.; Rossi, F.; Horesh, L.; Srivastava,
B.; Fabiano, F.; and Loreggia, A. 2022.
Plansformer: Generating Symbolic Plans using Transformers.
arXiv:2212.08681 [cs.AI].
- Pallagani et al. (2023)
Pallagani, V.; Muppasani, B.; Murugesan, K.; Rossi, F.; Srivastava, B.; Horesh,
L.; Fabiano, F.; and Loreggia, A. 2023.
Understanding the Capabilities of Large Language Models for Automated
Planning.
*CoRR*, abs/2305.16151.
- Puri et al. (2021)
Puri, R.; Kung, D. S.; Janssen, G.; Zhang, W.; Domeniconi, G.; Zolotov, V.;
Dolby, J.; Chen, J.; Choudhury, M. R.; Decker, L.; Thost, V.; Buratti, L.;
Pujar, S.; Ramji, S.; Finkler, U.; Malaika, S.; and Reiss, F. 2021.
CodeNet: A Large-Scale AI for Code Dataset for Learning a
Diversity of Coding Tasks.
In *NeurIPS Datasets and Benchmarks*.
- Raman et al. (2022)
Raman, S. S.; Cohen, V.; Rosen, E.; Idrees, I.; Paulius, D.; and Tellex, S.
2022.
Planning With Large Language Models Via Corrective Re-Prompting.
In *NeurIPS 2022 Foundation Models for Decision Making
Workshop*.
- Sel et al. (2023)
Sel, B.; Al-Tawaha, A.; Khattar, V.; Wang, L.; Jia, R.; and Jin, M. 2023.
Algorithm of Thoughts: Enhancing Exploration of Ideas in Large
Language Models.
*CoRR*, abs/2308.10379.
- Shinn et al. (2023)
Shinn, N.; Cassano, F.; Gopinath, A.; Narasimhan, K.; and Yao, S. 2023.
Reflexion: language agents with verbal reinforcement learning.
In *Proceedings of the Thirty-Seventh Annual Conference on
Neural Information Processing Systems (NeurIPS 2023)*.
- Silver et al. (2024)
Silver, T.; Dan, S.; Srinivas, K.; Tenenbaum, J.; Pack Kaelbling, L.; and
Katz, M. 2024.
Generalized Planning in PDDL Domains with Pretrained Large Language
Models.
In Dy, J.; and Natarajan, S., eds., *Proceedings of the
Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI 2024)*.
AAAI Press.
- Silver et al. (2022)
Silver, T.; Hariprasad, V.; Shuttleworth, R. S.; Kumar, N.; Lozano-Pérez,
T.; and Kaelbling, L. P. 2022.
PDDL Planning with Pretrained Large Language Models.
In *NeurIPS 2022 Foundation Models for Decision Making
Workshop*.
- Stechly, Valmeekam, and Kambhampati (2024)
Stechly, K.; Valmeekam, K.; and Kambhampati, S. 2024.
On the Self-Verification Limitations of Large Language Models on
Reasoning and Planning Tasks.
*arXiv preprint arXiv:2402.08115*.
- Valmeekam et al. (2023a)
Valmeekam, K.; Marquez, M.; Olmo, A.; Sreedharan, S.; and Kambhampati, S.
2023a.
PlanBench: An Extensible Benchmark for Evaluating Large Language
Models on Planning and Reasoning about Change.
In *Proceedings of the Thirty-Seventh Annual Conference on
Neural Information Processing Systems (NeurIPS 2023)*, 38975–38987.
- Valmeekam et al. (2023b)
Valmeekam, K.; Marquez, M.; Sreedharan, S.; and Kambhampati, S.
2023b.
On the Planning Abilities of Large Language Models - A Critical
Investigation.
In *Proceedings of the Thirty-Seventh Annual Conference on
Neural Information Processing Systems (NeurIPS 2023)*.
- Wei et al. (2022)
Wei, J.; Wang, X.; Schuurmans, D.; Bosma, M.; Xia, F.; Chi, E.; Le, Q. V.;
Zhou, D.; et al. 2022.
Chain-of-thought prompting elicits reasoning in large language
models.
*Advances in neural information processing systems*, 35:
24824–24837.
- Xie et al. (2023)
Xie, Y.; Yu, C.; Zhu, T.; Bai, J.; Gong, Z.; and Soh, H. 2023.
Translating Natural Language to Planning Goals with Large-Language
Models.
*CoRR*, abs/2302.05128.
- Yang et al. (2024)
Yang, J.; Jimenez, C. E.; Wettig, A.; Lieret, K.; Yao, S.; Narasimhan, K.; and
Press, O. 2024.
Swe-agent: Agent-computer interfaces enable automated software
engineering.
*arXiv preprint arXiv:2405.15793*.
- Yao et al. (2023a)
Yao, S.; Yu, D.; Zhao, J.; Shafran, I.; Griffiths, T.; Cao, Y.; and Narasimhan,
K. 2023a.
Tree of thoughts: Deliberate problem solving with large language
models.
In *Proceedings of the Thirty-Seventh Annual Conference on
Neural Information Processing Systems (NeurIPS 2023)*.
- Yao et al. (2023b)
Yao, S.; Yu, D.; Zhao, J.; Shafran, I.; Griffiths, T. L.; Cao, Y.; and
Narasimhan, K. R. 2023b.
Tree of Thoughts: Deliberate Problem Solving with Large Language
Models.
In *Thirty-seventh Conference on Neural Information Processing
Systems*.
- Zhang et al. (2023)
Zhang, K.; Li, Z.; Li, J.; Li, G.; and Jin, Z. 2023.
Self-Edit: Fault-Aware Code Editor for Code Generation.
In *ACL (1)*, 769–787. Association for Computational
Linguistics.
- Zhong, Wang, and Shang (2024)
Zhong, L.; Wang, Z.; and Shang, J. 2024.
Debug like a Human: A Large Language Model Debugger via Verifying
Runtime Execution Step-by-step.
arXiv:2402.16906.
- Zhou et al. (2023)
Zhou, A.; Yan, K.; Shlapentokh-Rothman, M.; Wang, H.; and Wang, Y. 2023.
Language Agent Tree Search Unifies Reasoning Acting and Planning in
Language Models.
*CoRR*, abs/2310.04406.
- Zuo et al. (2024)
Zuo, M.; Velez, F. P.; Li, X.; Littman, M. L.; and Bach, S. H. 2024.
Planetarium: A Rigorous Benchmark for Translating Text to
Structured Planning Languages.
*CoRR*, abs/2407.03321.

## Appendix A Additional data for experimental domains

We provide additional information on the domains included in our experimental evaluation, such as examples used in unit tests, code for the partial successor soundness test, etc.

### A.1 24 Game

#### Goal Unit Test

Goal unit test cases are stored in two jsonl files, one for goal states and one for non-goal states.

Figure: Listing 2 24game_goal_states.jsonl

Figure: Listing 3 24game_non_goal_states.jsonl

#### Successor Unit Test

Successor unit test cases are stored in a jsonl file. The test cases used are depicted in Listing [4](#listing4).

Figure: Listing 4 24game_successors.jsonl

#### Partial Successor Soundness Test

The code for the partial successor soundness test is as follows.

### A.2 Blocksworld

#### Goal Unit Test

Goal unit test cases are stored in two jsonl files, one for goal states and one for non-goal states, depicted in Listings [5](#listing5) and [6](#listing6).

Figure: Listing 5 blocks_goal_states.jsonl

Figure: Listing 6 blocks_non_goal_states.jsonl

#### Successor Unit Test

Successor unit test cases are stored in a jsonl file, depicted in Listing [7](#listing7).

Figure: Listing 7 blocks_successors.jsonl

#### Partial Successor Soundness Test

### A.3 5x5 Crosswords

#### Goal Unit Test

Goal unit test cases are stored in two jsonl files, one for goal states and one for non-goal states.

Figure: Listing 8 crosswords_goal_states.jsonl

Figure: Listing 9 crosswords_non_goal_states.jsonl

#### Successor Unit Test

Successor unit test cases are stored in a jsonl file. The test cases used are depicted in Listing [10](#listing10).

Figure: Listing 10 crossword_successors.jsonl

#### Partial Successor Soundness Test

### A.4 ProntoQA

#### Goal Unit Test

Goal unit test cases are stored in two jsonl files, one for goal states and one for non-goal states.

Figure: Listing 11 prontoqa_goal_states.jsonl

Figure: Listing 12 prontoqa_non_goal_states.jsonl

#### Successor Unit Test

Successor unit test cases are stored in a jsonl file. The test cases used are depicted in Listing [13](#listing13).

Figure: Listing 13 prontoqa_successors.jsonl

#### Partial Successor Soundness Test

### A.5 Sokoban

#### Goal Unit Test

Goal unit test cases are stored in two jsonl files, one for goal states and one for non-goal states.

Figure: Listing 14 sokoban_goal_states.jsonl

Figure: Listing 15 sokoban_non_goal_states.jsonl

#### Successor Unit Test

Successor unit test cases are stored in a jsonl file. The test cases used are depicted in Listing [16](#listing16).

Figure: Listing 16 sokoban_successors.jsonl

#### Partial Successor Soundness Test

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 4
presentation: 2
questions: - Could you please verify the equation on line 112? Shouldn't it be $f(s_i, a_i) = s_{i+1}$?
- What does $T$ represent on line 115?
- Providing more details on the limitations and challenges of generating the unit tests, as well as possible coverage metrics for those tests, would help clarify the full extent of the remaining human effort.
soundness: 3
strengths: - The paper clearly motivates the need to automate the iterative feedback and exception handling process within the LLM-driven ToS paradigm, effectively shifting the burden from continuous human involvement to the specification of unit tests by humans.
- Evaluation is conducted across multiple domains of varying complexity, including classic (i.e. with BlocksWorld and Sokoban), logic (i.e. with PrOntoQA), and mini-crosswords, as well as with various LLMs of different sizes.
- AutoToS often achieves 100% accuracy and does so with a manageable number of LLM calls, usually on par with the original ToS approach involving human experts, especially when using larger LLMs.
summary: The paper introduces an adaption of the Thought of Search (ToS) framework: AutoTos, a system that seeks to sideline humans' involvement in the feedback loop for generated coding snippets. The automation relies on domain-specific and generic unit tests to iteratively provide feedback to LLMs on their code outputs, aiming for code that is sound and complete. Experiments are conducted across five benchmark domains and with multiple LLMs.
weaknesses: - Even though much of the process is automated, the framework assumes either existing or easily generated unit tests. Consequently, human involvement is not eliminated but rather shifted: from interacting directly with the LLM to designing or generating appropriate unit tests.
- The authors use examples from the 24 Game without providing sufficient explanations of the game itself. Including a brief description of the game in the Background section, ideally expanding the existing explanation on lines $275-277$, would help readers unfamiliar with the game better understand its rules and how states transition through arithmetic operations, thereby clarifying the relevance of the successor states used in the examples.
- The framework relies on soundness and completeness as feedback properties. While the experimental results show the benefits they bring, the paper itself does not include any comparison with other types of feedback or other feedback-guided approaches.

---

confidence: 4
contribution: 3
initial_rating: 4
presentation: 2
questions: - Please address the issues raised in the weaknesses section.
soundness: 3
strengths: - The main contribution, according to the authors, is that they can leverage all the existing approaches in software engineering and LLM-based code generation to create an automated feedback mechanism thus avoiding need for human intervention. (But it looks like the human still has to generate some unit tests, unless you are using formal specs of the environment?)
- They show that this approach leads to 100% accuracy (just like the manually intervened ToS models).
- The error analysis is good showing distinctions across the different models.
summary: This paper extends the so-caled thought-of-search (ToS) method which basically uses code to structure the search for solutions. Like a generic A* search algorithm this defines a successor function and a goal test function which can then be compared to any other search approach executed on the same environment.
weaknesses: - While I like the paper's approach this seems like a very minor contribution and primarily relies on test-based checks to achieve full 100% automation. The choice of problems might have been restricted to those where this is possible. I am not sure how this can be used as a general reasoning mechanism for LLM applications.
- While I commended the error analysis above, this also feels like an opportunity to use this to see what needs to be done so you can get uniform performance across models and domains.

---

confidence: 3
contribution: 1
initial_rating: 2
presentation: 2
questions: I don’t find any details in the paper on the human evaluation protocol details, since as the authors mentioned there’re human intervention in ToS method in Table 2. My guess is there’s some predefined functions as ground truth for ToS, but this is unclear from the text.

It is also better to include more baseline methods in Table 2 comparison to show your method’s practical value. For example, include the simplest search pipeline baseline.
soundness: 2
strengths: The paper is generally written clearly.

This direction of reducing LLM dependence on human feedback for complex reasoning has potential.
summary: The paper focuses on utilizing LLMs to solve planning problems that require search. Previous methods like ToS defined a search space with code, but required a human in the loop to inspect. The paper proposed AuthToS to achieve 100% accuracy on 5 synthetic tasks without human intervention.
weaknesses: I don’t see how this method can be really useful in more practical scenarios. Since the experiment setting is very toy, if you only focus on tasks with available `isgoal` and `succ` functions, you can actually replace the LLM call with very simple human-written functions, even simpler than the prompts you write. 

Besides, I don't believe the 100% accuracy in the experiment section is meaningful. It is trivial to write a simple search method to achieve 100\% accuracy on all of them, as long as you have access to the two above functions.

There are no indices for different sections, which I believe does not conform to the ICLR template’s requirement.

---

confidence: 4
contribution: 2
initial_rating: 4
presentation: 3
questions: - In line with my comment above about best-of-five trials when reporting accuracy, wouldn’t it be more meaningful to report average accuracy, since it is a more accurate reflection of the system’s performance when deployed in realistic settings without humans in the loop, as the paper aims to envision?
- In the discussion of results shown in Table 2, the authors claim that the number of LLM calls of their approach is comparable to that of ToS where human gives feedback, but the numbers in the table show that their approach consistently has higher number of calls compared to ToS. On what grounds are the authors making this claim? Are the authors considering feedback by humans in ToS as “pseudo” calls? This point should be clarified.
soundness: 2
strengths: - The paper is easy to follow, and the contributions of the paper in the context of existing works are clearly communicated.
- The paper presents an important step towards automation of ToS enabling automated planning without requiring humans in the loop.
- The paper’s focus on the necessity of soundness and completeness in the context of planning (which are often overshadowed in works that tend to use LLMs directly as planners) is well-appreciated, as they are key to achieving good and reliable planning performance.
- The paper presents comprehensive experimental evaluation in different planning problems with varying complexity.
summary: The paper is an extension of prior work, Thought of Search (ToS), in which an LLM is used to generate Python code for a successor function and a goal test function which are then used with standard search algorithms like BFS or DFS to solve the given planning problems. While ToS required human in the loop to iteratively generate a sound successor function and a goal test function using LLMs, the paper aims to automate this step by guiding LLMs to generate a sound and complete successor function and a correct goal test function by using generic and domain specific unit tests for these functions as feedback to LLMs.
weaknesses: - The paper is incremental as it takes one specific step of the prior approach, and automates that step with an LLM-in-the-loop mechanism replacing the human-in-the-loop mechanism of prior approach. While this is an important extension, this limits the novelty and impacts of the paper to the broader research community.
- The claim about 100% accuracy feels underwhelming since it is based on success in any of the 5 trials (using an external validator). It would be interesting to see what average success rates look like for these experiments to get a better idea of the effectiveness of the proposed approach.

---

confidence: 4
contribution: 2
initial_rating: 4
presentation: 4
questions: Could you easily run this on task which are harder and to challenge this method and find problem cases? Where does it fail? One weak point was the test-case quality but if you make a problem really hard how far can you get? What problems occure and what do you think how to fix?
soundness: 4
strengths: 1. It takes out the human in the loop for evaluation which makes it more usefull for practical application.
2. It allows for the use of smaller models since it splits to planning proplen into steps.
3. It is straigh forward to implement to replicated. 
4. Good evaluation with a number of models and good number of problems.
summary: The work builds on previous method Thought of Search. In ToS, the LLM is prompted for code on goal-testing function an a successor-generation function. These funkction can be used via search methods BFS or DFS, etc.  While ToS achieves 100% accuracy, in previous work,  it needs a  human expert in the loops for evaluation. This is applied to planning, games etc where a tree of alternatives can be searched / explored to find a solution. The method is straight forward to implement.
weaknesses: 1. It is expensive as each step needs a LLM call and this comes also with some latency. 
2.  The paper claims 100% accuracy on tested datasets. This is great but comes with the downside that it does not allow access to the limits too. Benchmarks marks would be preferable that provide some space. Especially, blocksworld that would be possible by using more blocks or needs more plannings steps to solve. 
3. The paper runs a best-of-5 as they have a validator so this seems to make it more expenstive but it can run in parallel, i belive. 
4. Dependency on Test-Case Quality as knowledged by the authors ... also a limit for humans, we miss things too.