System 1.x: Learning to Balance Fast and Slow Planning with Language Models

## Abstract

Abstract Language models can be used to solve long-horizon planning problems in two distinct modes. In a fast ‘System- 1 1 1 1 ’ mode, models directly generate plans without any explicit search or backtracking, and in a slow ‘System- 2 2 2 2 ’ mode, they plan step-by-step by explicitly searching over possible actions. While System- 2 2 2 2 planning is typically more effective, it is also more computationally expensive, often making it infeasible for long plans or large action spaces. Moreover, isolated System- 1 1 1 1 or System- 2 2 2 2 planning ignores the user’s end goals and constraints (e.g., token budget), failing to provide ways for the user to control their behavior. To this end, we propose the System- 1 . x formulae-sequence 1 𝑥 1.x 1 . italic_x Planner , a controllable planning framework with language models that is capable of generating hybrid plans and balancing between the two planning modes based on the difficulty of the problem at hand. System- 1 . x formulae-sequence 1 𝑥 1.x 1 . italic_x consists of (i) a controller, (ii) a System- 1 1 1 1 Planner, and (iii) a System- 2 2 2 2 Planner. Based on a user-specified hybridization factor x 𝑥 x italic_x governing the degree to which the system uses System- 1 1 1 1 vs. System- 2 2 2 2 , the controller decomposes a planning problem into sub-goals, and classifies them as easy or hard to be solved by either System- 1 1 1 1 or System- 2 2 2 2 , respectively. We fine-tune all three components on top of a single base LLM, requiring only search traces as supervision. Experiments with two diverse planning tasks – Maze Navigation and Blocksworld – show that our System- 1 . x formulae-sequence 1 𝑥 1.x 1 . italic_x Planner outperforms a System- 1 1 1 1 Planner, a System- 2 2 2 2 Planner trained to approximate A ∗ search, and also a symbolic planner (A ∗ search), given an exploration budget. We also demonstrate the following key properties of our planner: (1) controllability : by adjusting the hybridization factor x 𝑥 x italic_x (e.g., System- 1.75 1.75 1.75 1.75 vs. System- 1.5 1.5 1.5 1.5 ) we can perform more (or less) search, improving performance, (2) flexibility : by building a neuro-symbolic variant composed of a neural System- 1 1 1 1 planner and a symbolic System- 2 2 2 2 planner, we can take advantage of existing symbolic methods, and (3) generalizability : by learning from different search algorithms (BFS, DFS, A ∗ ), we show that our method is robust to the choice of search algorithm used for training. 1 1 1 Code available at: https://github.com/swarnaHub/System-1.x

## 1 Introduction

A key feature of intelligence – both human and artificial – is the ability to plan.
Indeed, planning has been a major topic of research in AI for most of its history (Russell and Norvig, ), with applications ranging from navigation and robotics to manufacturing and story-telling. These days, auto-regressive Large Language Models (LLMs) are increasingly used for various long-horizon planning and reasoning tasks (Bubeck et al., ; Wei et al., ; Yao et al., ). Despite some initial promise, recent careful investigations have highlighted LLMs’ shortcomings on classical planning tasks (Pallagani et al., ; Valmeekam et al., , ; Momennejad et al., ).
Supervising models with correct plans has also led to limited success, especially for out-of-distribution generalization (Dziri et al., ).
Fundamentally, this issue is attributed to a lack of explicit search, backtracking, or learning from mistakes (Kambhampati et al., ; Bachmann and Nagarajan, ; Gandhi et al., ),
all of which are essential components of standard planning systems.
In other words, LLMs directly generating plans generally resemble humans’ *fast* ‘System-$1$’ decision-making process (Kahneman, ), characterized by quick, intuitive judgments rather than slow, deliberate planning (Kambhampati et al., ).

As potential remedies, *slow* ‘System-$2$’-inspired LLM planning approaches have emerged that either (1) augment LLMs during inference with symbolic search algorithms (Yao et al., ; Sel et al., ; Ahn et al., ) or (2) directly teach LLMs to carry out search themselves (Gandhi et al., ; Lehnert et al., ).
While the former approach of using external search tools can enhance test-time performance, the latter approach – training models to search – has the advantage of resulting in a single unified search model and also discovering better and more efficient search strategies (Gandhi et al., ).
However, such training-time approaches also face challenges due to *high computational demands and potential infeasiblity*.
For instance, one such recently proposed (trained) System-$2$ method, Searchformer, uses token sequences that verbalize entire search trajectories (Lehnert et al., ).
Consequently, during inference, based on the action space and the plan length, these models explore a large number of states, resulting in an increased number of generated tokens.
The cost of exploration is further exacerbated by the fact that Transformers (Vaswani et al., ) typically exhibit quadratic complexity w.r.t. the sequence length. Thus, as sequence length increases, the computational complexity grows, significantly impacting memory usage and speed, rendering many long-horizon tasks infeasible due to token limits.(^2^22For example, full System-$2$ on $5\times 5$ mazes with a plan length of 8 requires $\sim 1500$ tokens on average.)
A more promising alternative would thus be to avoid incurring a high cost on all samples and steps by training a planner with a smarter, more balanced allocation of compute, i.e. one that uses System-$1$ for easier (sub-)problems while reserving the more expensive System-$2$ for harder (sub-)problems based on the budget.

To this end, we propose the *System-$1.x$ Planner*, drawing inspiration from the Dual-Process Theory (Wason and Evans, ; Kahneman, ) that argues for the co-existence of fast and slow planning in humans.
The fast system relies on expertise and quick judgments that are learned from experience;
it can be cheaply and quickly applied either instinctively (e.g., withdrawing one’s hand from a hot object) or in areas where an individual has acquired expertise (e.g., avoiding an unexpected obstacle when driving).
The slow system is more costly, involving sequential processing and relying on working memory to formulate a more deliberate plan; it includes the consideration of hypothetical alternatives (Evans, ).
Crucially, people can switch between these two modes as determined by the task at hand (Kahneman, ). For example, imagine someone is taking a detour on their usual route home.
While on the detour, they might require System-$2$ planning to handle navigation in an unfamiliar area but can switch to System-$1$’s “autopilot” as soon as they are back on their familiar route.
Based on this distinction, we develop the System-$1.x$ Planner, a controllable framework for long-horizon planning with LLMs that is capable of generating hybrid plans interleaved with System-$1$ and System-$2$ sub-plans. System-$1.x$ offers
a promising middle ground between a fast but inaccurate System-$1$ Planner, used for easy problems, and an accurate but slow System-$2$ Planner, used for hard problems (see Fig. 1 for an overview).

At its core, System-$1.x$ is composed of three trained components: (1) a controller that decomposes a planning problem into easier and harder sub-goals, (2) a System-$1$ Planner that solves the easier sub-goals without any explicit search or exploration, and (3) a System-$2$ Planner that solves the harder sub-goals by deliberately searching over possible actions. One of the primary strengths of System-$1.x$ is its *train-time controllability* – based on a user-specified hyperparameter $x\in[0,1]$, we train a controller that ultimately governs the degree of hybridization between the System-$1$ and $2$ planners.
Moreover, it also offers *test-time controllability*, by which an already trained controller can be adjusted towards solving more or fewer problems using System-$2$, providing another level of inference-time compute.(^3^33E.g., we can train a System-$1.5$ model and then add a bias term to the controller at test time to increase the probability of System-$2$, inducing it to *act* like a System-$2$ model (or System-$1.25$, System-$1.75$, etc.).)
Importantly, all three components are implemented by the same fine-tuned LLM, using only search traces supervision. System-$1.x$ is thus a *fully (LLM-based) neural planner* that does not rely on external solvers or verifiers and requires only one base LLM.
By not relying on external tools, our method has an advantage over inference-time methods that rely on symbolic planners, as external tools may not exist for certain domains, making data-driven approaches like System-$1.x$ self-contained and easier to apply to new domains and to scale up.
At the same time, System-$1.x$ can also be seamlessly converted into a *neuro-symbolic planner* by replacing the System-$2$ Planner with a symbolic solver (e.g., A^∗), allowing us to integrate powerful symbolic tools when they are available.

We experiment with two diverse planning problems: Maze Navigation and Blocksworld. We demonstrate that our System-$1.x$ Planner matches and generally outperforms a System-$1$ Planner, a System-$2$ Planner, and a System-$1.x$ variant (without sub-goal decomposition) at all budgets
by up to $33\%$ absolute accuracy.
We also report similar findings with our neuro-symbolic System-$1.x$, that in fact typically outperforms symbolic search, beating A^∗ by up to 39% at a fixed budget and matching it at maximum budget.
Next, we show the controllability of our framework by training a System-$1.75$ Planner that, compared to a System-$1.5$ Planner, trades off efficiency for greater accuracy.
This trend can be continued to recover the full System-$2$ performance.
System-$1.x$ also generalizes to different search algorithms (BFS, DFS, and A^∗) and exhibits exploration behavior that closely resembles the corresponding algorithm it is trained on.
Overall, the System-$1.x$ Planner introduces a novel way of applying LLMs to controllable and hybrid planning, optimizing for both accuracy and efficiency.
This, in turn, allows System-$1.x$ to outperform both System-$1$ and System-$2$ at a fixed budget.
By intelligently allocating more resources to harder sub-goals, System-$1.x$ is able to save its System-$2$ budget for cases where it is necessary.

Figure: Figure 2: Overview of our System-$1.x$ Planner. Left: The process for training data construction. We generate three kinds of data to fine-tune our three components: (1) System-$1$ data (linear chains), (2) System-$2$ data (search trees), and (3) controller data (consisting of sub-goals and easy/hard annotations) conditioned on a user-specified hybridization factor $x$. Right: During inference, the controller generates the sub-goals and predicts whether each is easy or hard. Then, it invokes System-$1$ and System-$2$ for easy and hard sub-goals respectively to construct the final plan.
Refer to caption: x2.png

## 2 System- 1 . x formulae-sequence 1 𝑥 1.x 1 . italic_x : Controllable and Hybrid Planning with LLMs

We start with the requisite background on planning problems and our setup (Section 2.1), followed by an overview and a detailed description of our method System-$1.x$ Planner in Section 2.2 and Section 2.3, respectively.

### 2.1 Background and Problem Setup

A planning problem can be modeled as a Markov Decision Process $\mathcal{M}=(\mathcal{S},\mathcal{A},\mathcal{T},\mathcal{R})$ defined with a set of states $\mathcal{S}$, a set of actions $\mathcal{A}$ on any given state, a transition function $\mathcal{T}:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{S}$ defining transitions between pairs of states based on an action, and a reward function $\mathcal{R}:\mathcal{S}\rightarrow\mathbb{R}$ assigning a reward for reaching the goal state.
Given such a planning problem, a start state $s_{0}\in\mathcal{S}$ and a goal state $s_{g}\in\mathcal{S}$, the objective of classical planning is to generate a plan $\mathcal{P}=(a_{1},...,a_{n})$, as a sequence of $n$ actions $a_{i}\in\mathcal{A}$ that helps transition from the start state to the goal state.
Using this notation, we define some salient concepts in a planning problem below:

- •
System-$1$ Planner. We use the term “System-$1$ Planner” to denote any planner that directly generates a plan as a sequence of actions *without* conducting any exploration or search. System-$1$ Planners are typically only model-based, trained to only output the final plan.
Within the scope of this study, a System-$1$ Planner will specifically refer to a neural LLM-based planner.
- •
System-$2$ Planner. We use the term “System-$2$ Planner” to denote planners that *do* conduct search before generating a plan. Unlike model-based System-$1$ Planners, System-$2$ Planners can either be symbolic or model-based. Symbolic System-$2$ Planners are search algorithms. Ones that *do not* rely on heuristics to minimize the search space are called uninformed algorithms (e.g., Depth First Search or Breadth First Search), and the ones that *do* are called informed (e.g., Greedy Best First or A^∗). A model-based System-$2$ Planner, within the scope of this study, will specifically refer to an LLM trained to verbalize search trajectories (defined below) before generating a plan. Thus, the terms System-$1$ and System-$2$ will refer to LLM-based planners while symbolic algorithms will be addressed separately.
- •
Search Trajectory. Given a search algorithm, we define a search trajectory or a search trace as the step-by-step execution of the algorithm for an input problem; in the context of LLMs, this will mean a verbalized representation of a search trajectory.
Trajectories consist of the final plan, all intermediate actions explored during search, their corresponding states, their validity, etc.
- •
Valid Plan: A plan $\mathcal{P}=(a_{1},...,a_{n})$ is considered valid if starting from the start state $s_{0}$, sequentially executing all taken actions in the plan leads to the goal state $s_{g}$, or more formally, $\mathcal{T}(\mathcal{T}(...\mathcal{T}(s_{0},a_{1})...,a_{n-1}),a_{n})=s_{g}$.
*Plan Validity* is a metric measuring the percentage of valid plans, i.e., the accuracy of the generated plans in reaching the goal state.
- •
#States-Explored: Given a planning problem and a planner (System-$1$, $2$, or $1.x$), we define #States-Explored ($\mathit{SE}$, in short) as the set of all states (both valid as well as invalid) that are visited by the planner on its way to generating the plan. In the case of an LLM planner, this corresponds to the number of states that the planner needs to verbalize for exploration (see right of Fig. 2 for an example output), and thus adds to the token cost of generation.
Since a System-$1$ Planner generates a plan directly without any additional explorations, it only explores the states that are part of its plan, i.e., $\mathit{SE}_{\textrm{Sys1}}\!=\!n$, where $n$ is the length of the generated plan. A System-$2$ Planner, on the other hand, will perform additional state explorations before generating a plan, resulting in $\mathit{SE}_{\textrm{Sys2}}\gg\mathit{SE}_{\textrm{Sys1}}$. Note that #States-Explored for a System-$2$ Planner will vary based on the underlying search algorithm or the LLM planner learning from that algorithm’s traces. For example, A^∗, being an informed search algorithm, will typically explore fewer states than Breadth First Search. Similarly, an LLM trained on such A^∗ traces is expected to be more efficient than the one trained on BFS’s traces. *Plan Validity* (i.e., plan accuracy) and *#States-Explored* will be our two metrics of interest, using which we will compare the performance at varying budgets of all planners (discussed in Section 4).
- •
Sub-goal. Finally, planning problems are typically compositional, meaning that they can be decomposed into sub-problems, which we will refer to as sub-goals.
Formally, given a plan $P$ between states $s_{0}$ and $s_{g}$, a sub-goal can be characterized by a pair of states $(s_{i},s_{j})$ s.t. $i,j\in[0,g],i\leq j$, where $s_{i}$ and $s_{j}$ are intermediate states on the plan to get from $s_{0}$ to $s_{g}$.

#### Problem Setup.

Having defined the key terms and metrics above, we now describe the setup underlying System-$1.x$ Planner.
To build a System-$1.x$ Planner, we assume access to two things: (1) a training dataset $\mathcal{D}$ of search trajectories for $N$ planning problems, and (2) a user-specified hybridization factor $x\in[0,1]$. Given a planning problem of initial state $s_{0}$, goal state $s_{g}$, and a gold plan $\mathcal{P}$, let us denote the corresponding gold search trajectory as $\mathcal{T}$, making the training dataset $\mathcal{D}=\{(s_{0}^{(i)},s_{g}^{(i)}),\mathcal{P}^{(i)},\mathcal{T}^{(i)}\}_
{i=1}^{N}$.
In our experiments, the gold plans and the corresponding trajectories will be obtained using a symbolic System-$2$ Planner (e.g., A^∗ search) but more generally, the source of these trajectories could be any neural or symbolic engine capable of exploration or search. The hybridization factor $x$ is a user-defined hyperparameter that will determine the balance between System-$1$ and System-$2$.

### 2.2 System- 1 . x formulae-sequence 1 𝑥 1.x 1 . italic_x Overview

Using the setup described in Section 2.1, we develop our System-$1.x$ Planner that consists of three trained components: (i) a *Controller* for
decomposing planning problems into sub-goals and classifying them into easy or hard sub-goals,
(ii) a *System-$1$ Planner* for *fast* planning of easy sub-goals, and (iii) a *System-$2$ Planner* for *slow* planning of hard sub-goals.
See Fig. 2 for an overview.
We train all three components by automatically generating data from the gold search traces in a way that also respects the user’s constraints (specified in the form of the hybridization factor). In the following two subsections, we describe how we train each component and how all three join to make System-$1.x$.

### 2.3 Training Data Generation for System- 1 . x formulae-sequence 1 𝑥 1.x 1 . italic_x

#### System- 1 1 1 1 Planner Training Data.

The training data for the System-$1$ Planner is $\mathcal{D}_{\textrm{Sys1}}\!=\!\{(s_{0}^{(i)},s_{g}^{(i)}),\mathcal{P}^{(i)}
\}_{i=1}^{N}$ where the input is a natural language description of the planning problem consisting of a start state $s_{0}^{(i)}$ and a goal state $s_{g}^{(i)}$ and the output is the corresponding plan in natural language $\mathcal{P}^{(i)}$ (see Appendices C and C for examples). For the Maze domain, these gold plans are also optimal plans while for Blocksworld, they may include additional explorations, making them sub-optimal at times (though they are always valid).

#### System- 2 2 2 2 Training Data.

Similar to System-$1$, the input to a System-$2$ Planner is also a natural language description of the planning problem. However, the target output of the System-$2$ Planner is a verbalized search trajectory $\mathcal{T}^{(i)}$ as described in Section 2.1 (refer to Appendices C and C for examples). This yields a training dataset of $\mathcal{D}_{\textrm{Sys2}}\!=\!\{(s_{0}^{(i)},s_{g}^{(i)}),\mathcal{T}^{(i)}
\}_{i=1}^{N}$.

#### Controller Training Data.

Recall that the System-$1.x$ Planner is designed to minimize state explorations by only performing System-$2$ planning *as needed*, i.e., saving states by employing System-1 for easier sub-goals and reserving search with System-2 for harder sub-goals. Hence, the role of the controller is two-fold: (i) decomposing a problem into sub-goals characterized by a start and end state $(s_{i},s_{j})$, and (ii) classifying those sub-goals as easy or hard so that System-2 can be invoked only for the hard sub-goals.
However, most planning domains lack gold annotations of sub-goal decompositions and their easy and hard classifications.
Therefore, we propose an automatic data generation process for training our controller, as described below and more formally in Algorithm 1.
The inputs to preparing the controller data are (1) the gold plans $\{\mathcal{P}^{(i)}\}_{i=1}^{N}$ that will be decomposed into sub-goals, (2) the user-defined hybridization factor $x$, and (3) a hardness function $h(\cdot,\cdot)$ for (sub-)goals.

Figure: Algorithm 1 Training Data Generation for System-$1.x$ Controller

- •
Step 1: Defining and Ranking using a Hardness Function. A hardness function $h(s_{i},s_{j})$ takes a start state $s_{i}$ and a goal state $s_{j}$ as input, and returns a scalar value estimating the hardness of the goal or the sub-goal. An example of a hardness function for a Maze Navigation task is the number of obstacles in a sub-maze, where a higher value indicates greater difficulty. Sections Section 3.4, and Section 4.3 more concretely describe and compare these hardness functions for different tasks, respectively. Generally, hardness functions can be constructed for most planning domains where heuristic searches like A^∗ are frequently applied.
Using this hardness function between the start and the goal state $h(s_{0},s_{g})$, we generate a rank ordering of the training examples.
- •
Step 2: Annotating Easy Instances as System-$1$-only. Intuitively, some planning problems in the train set can be solved successfully via only a System-$1$ Planner. For such instances, no further decomposition is needed. These correspond to the first $(1-x)\times N$ easiest samples with the least $h(\cdot,\cdot)$. Note that this is a definition of hardness, and what is considered as easy is determined by the hybridization factor $x$. For example, when $x=0.0$, all samples will be annotated as easy, making System-$1.x$ the same as System-$1$.
- •
Step 3: Annotating Hard Instances as Hybrid System-$1$ + System-$2$.
For the remaining $x\times N$ (hard) samples,
we assume that they can be decomposed into sub-goals, each of which can be assigned to either System-$1$ or System-$2$. However, to ensure overall task success, the decompositions should neither be too coarse, i.e., requiring further decompositions, nor too fine-grained, making them susceptible to decomposition errors (Prasad et al., ). Hence, we adopt a sliding window approach that optimizes for the following: find a contiguous chunk of length $x\times n$ of an $n$-length plan to be assigned System-$2$, such that it corresponds to the hardest sub-goal and the sub-goals on either side of it correspond to the easiest (and hence assigned System-$1$). More formally, this requires us to solve the following constrained optimization problem:
$(j,k)=\mathrm{argmin}_{u,v\in[0,g],u\leq v}h(s_{0},s_{u})-h(s_{u},s_{v})+h(s_{
v},s_{g})\text{, s.t. }|v-u|=x\times n$
Given a start state $s_{0}$ and goal state $s_{g}$, we want to find two intermediate states $s_{j}$ and $s_{k}$ between $s_{0}$ and $s_{g}$ along the length of the plan, such that the hardness of that sub-goal $h(s_{j},s_{k})$ is maximized (and hence assigned System-$2$) while the hardness of the other two sub-goals $h(s_{0},s_{j})$ and $h(s_{k},s_{g})$ is minimized (and hence assigned System-$1$).
This process results in a three-way decomposition.(^4^44Note that when $u=0$ or $v=g$, there will be two decompositions rather than three.)
The final result is a controller training dataset $\mathcal{D}_{c}=\{(s_{0}^{(i)},s_{g}^{(i)}),\{\mathcal{G}^{(i)}\}_{j=1}^{t}\}_
{i=1}^{N}$ where for each planning problem, we have an annotated list of $t\in\{1,2,3\}$ sub-goals $\{\mathit{\mathcal{G}_{j}}^{(i)}\}_{j=1}^{t}$ and their corresponding System-$1$/System-$2$ assignments. See Appendices C and C for examples of the controller data.
In practice, the components we use for controller data generation (e.g., sub-goal decomposition strategy, hardness heuristic) can easily be swapped with other variants, based on the problem at hand (further explored in Appendix B).

### 2.4 Training and Inference of System- 1 . x formulae-sequence 1 𝑥 1.x 1 . italic_x Planner

Using the data generation process described above, we finetune a single base LLM to behave as a System-$1$ Planner, a System-$2$ Planner, or a controller.
During inference, we first use the controller to generate a meta-plan – a list of sub-goals and their easy versus hard assignments.
After solving each with the appropriate planning model, we concatenate the sub-plans from the two planners, in order, to construct the final plan (see Fig. 2 for an example of a concatenated plan, denoted by ‘+’).(^5^55In our experiments, we observe that the controller almost always generates continuous sub-goals (i.e., the end of the previous sub-goal matches the start of the next sub-goal).)

#### Train- and Test-time Controllability.

We design System-$1.x$ such that there is a single point of control for training the system, i.e., the hybridization factor $x$, and this control lies with the end-user.
Setting it adjusts the training data for the controller, i.e., what is annotated as easy versus hard, both across samples (Step 2 of the algorithm) and within samples (with sub-goals; Step 3 of the algorithm). This ultimately yields the user-specified level of hybridization.
Hence, System-$1.x$ offers *training-time control* of compute (e.g., one could train a System-$1.25$, $1.5$, or a $1.75$ Planner).
Furthermore, the controller’s design also offers an additional degree of *test-time control*:
since the controller classifies sub-goals as System-$1$ or System-$2$, the end-user could also re-balance the model towards System-$1$ or $2$ based on the controller confidence threshold.
By default, the controller generates System ‘$1$’ or ‘$2$’ based on which token has a higher probability mass.
However, the user can add a bias term to these token probabilities to solve a greater or smaller number of sub-goals using System-$1$ or System-$2$, adjusting the behavior of an already-trained System-$1.x$ Planner.
This means that a System-$1.5$ Planner, for example, can be biased to behave as a System-$1.25$ Planner or a System-$1.75$ Planner at test time.
In our results in Figs. 3, 5, 7 and 6, we explore how both train-time and test-time control impacts performance.

## 3 Experimental Setup

### 3.1 Tasks

We evaluate System-$1.x$ Planner on two classical planning tasks that are challenging for LLMs (Valmeekam et al., ; Lehnert et al., ): (1) Maze Navigation and (2) Blocksworld.

#### Maze Navigation.

We first experiment with a robotic maze navigation task – given a 2D maze with some cells containing obstacles and four permissible actions {‘left’, ‘right’, ‘up’, ‘down’}, the objective is to find a path from a start state to a goal state by avoiding the obstacles. We randomly generate a balanced dataset of 4K planning problems for maze navigation using the following configuration – 5x5 maze, 40% of the cells containing obstacles, and an equal number of problems (500) with optimal plan lengths between 1 to 8. Controlling for the plan length allows us to study a planner’s ability to solve harder planning problems. We remove duplicates (problems where the placement of the obstacles, the start state, and the goal state match exactly), and construct a 3200/400/400 (train/validation/test) balanced split for training our models.

#### Blocksworld.

Additionally, to test out-of-distribution (OOD) generalization to longer plans, we experiment with Blocksworld, a classical planning problem from the International Planning Conference (IPC)-2000. The task consists of a table and a few blocks stacked on the table or on top of each other in one configuration. A robot is tasked to move blocks to another goal configuration by only moving one unstacked block at a time. Following the data creation algorithm in Bohnet et al. (), we generate problems consisting of 4-7 blocks (without repetition). From there, we create a train/validation/test split of 3000/250/200 samples where the train and the validation split consist of samples with plan lengths 1-6 and the test split consists of samples with plan lengths 7-10. Different from maze which has a fixed action space of 4, Blocksworld has a much larger action space that also increases with the number of blocks.

### 3.2 Baselines

We compare our System-$1.x$ Planner with (1) a System-$1$ Planner, (2) a System-$2$ Planner, (3) a symbolic planner, specifically A^∗, and (4) a System-$1.x$ Planner without sub-goal decomposition. The latter is also a hybrid planner but the controller is trained to predict an instance as either *fully* System-$1$ or *fully* System-$2$, thus allowing us to evaluate the effectiveness of sub-goal decomposition of our full System-$1.x$ model.
Under the umbrella of System-$2$ Planners, we train multiple variants that are fine-tuned with data obtained from different search algorithms. In particular, we consider two uninformed search algorithms (Breadth-First Search and Depth-First Search) and an informed search algorithm (A^∗). Given the superiority of A^∗, our primary experiments will be based on A^∗ traces while we reserve the other search algorithms for further analysis in Section 4.3. Refer to Appendix A for a short background on A^∗.

### 3.3 Evaluation Metrics

We compare all methods along two axes: accuracy and cost. As defined in Section 2.1, accuracy is given by the fraction of valid plans generated by a planner while for cost, we compute the average #States-Explored by a planner before reaching the goal.

#### Reporting Results.

Note that in order to fairly compare the performance of Systems $1$, $2$, and $1.x$, their #States-Explored should be matched, such that we compare performance at a fixed budget for each system.
First, since System-$1$ does not do any exploration, it is constant w.r.t. budget and hence has the same accuracy irrespective of #States-Explored.
Next, to adapt System-$2$ and System-$1.x$ to lower budgets, we truncate the search when the maximum number of states allowed by the budget has been reached. This value of maximum allowed states is given by the highest possible value such that the average #States-Explored matches the desired budget. We refer to this as truncation below.
Finally, to adapt System-$1.x$ to higher budgets, we use System-$1.x$’s test-time controllability, increasing the bias term on System-$2$ reasoning (cf. Section 2.4).
As this term increases, the model uses more and more System-$2$ planning, i.e., $x\rightarrow 1$ in System-$1.x$.
We refer to this as test-time control.

We perform this matching and report plan validity (i.e., accuracy) for the following values of #States-Explored.
First, we vary the maximum budget of states explored in intervals of 5 for Maze and 10 for Blocksworld, up to the number of states used by System-$2$ (the most compute-intensive system we consider).
We also consider two specific points in the range of #States-Explored:
we match System-$2$’s #States-Explored to the number of states that System-$1.x$ uses by default.
In the other direction, we match
System-$1.x$’s #States-Explored to the number of states used by System-$2$.
These points let us directly compare the two systems without any truncation or test-time control. In the main paper, we present our results with plots while we refer to the Appendix D for detailed tables.

### 3.4 Implementation Details

We choose Mistral-7B-Instruct-v0.2 (Jiang et al., ) as the base LLM and fine-tune all our components with LoRA (Hu et al., ) with a rank of 8 for a maximum of 3 epochs and a batch size of 4, resulting in three adapters for System-$1$, System-$2$, and the controller.
For the purposes of Section 4.1, System-$1.x$ will specifically refer to a System-$1.5$ Planner (i.e., $x\!=\!0.5$, which is a balanced hybrid between a System-$1$ Planner and System-$2$ Planner) and fine-tuned from A^∗ traces.

#### Hardness Function for Maze Navigation.

Given two maze states $s_{i}=(a,b)$ and $s_{j}=(c,d)$ we define hardness of a sub-goal $h(s_{i},s_{j})$ as the number of obstacles in the rectangular sub-maze given the end-points. More obstacles will mean that the model might have to search more and would likely benefit from System-$2$ planning.

#### Hardness Function for Blocksworld.

A state in Blocksworld is characterized by the configuration of the blocks. Our hardness function computes a distance metric for a sub-goal: For every block that is not in its correct position in the goal state (i.e., the blocks above and below it are different between the start and goal states), we add a cost of 1. Additionally, for a block that is *not* on the table and also not in its correct position, we add 1 more to the cost, indicating greater hardness for moving blocks that are in the middle of a stack.

Refer to Appendix A for additional implementation details e.g., our System-$2$ implementations.

## 4 Results and Analysis

### 4.1 System- 1 . x formulae-sequence 1 𝑥 1.x 1 . italic_x outperforms System- 1 1 1 1 and 2 2 2 2

Figure: (a) Maze Navigation
Refer to caption: x3.png

#### Study Setup.

In this first set of experiments, we compare our System-$1.x$ Planner with the following baselines (cf. Section 3.2) (1) a System-$1$ Planner, (2) a System-$2$ Planner, and (3) a System-$1.x$ Planner without sub-goal decomposition.

Results for Maze Navigation. Fig. 3(a) (cf. Table 3) shows the plan accuracy obtained by each planner at different #States-Explored. The values of #States-Explored are as described previously in Section 3.3. Based on this, we summarize our key findings.

- •
System-$1.x$ outperforms all baselines at all budgets. Without truncation or test-time control, System-$1.x$ ($x\!=\!0.5$) uses $13.6$ states on average.
At this number of states, it obtains an accuracy of $70.4\%$, outperforming the System-$1$ Planner by 21% (48.7% $\rightarrow$ 70.4%), the System-$2$ Planner by 33% (37.2% $\rightarrow$ 70.4%), and the System-$1.x$ variant without sub-goal decomposition by 20% (50.0% $\rightarrow$ 70.4%).
Next, to compare all methods at *lower* budgets (i.e., with #States-Explored of 5 and 10), we do state truncation (as described in Section 3.3) by limiting the search (generation) to a maximum number of states. We find that even at these lower budgets, System-$1.x$ continues to be significantly more accurate compared to baselines, pointing to an effective allocation of resources.
Finally, System-$1.x$’s *test-time control* capability lets us increase compute to match that of System-$2$ by biasing the controller and solving more sub-goals with System-$2$.
Doing so eventually transforms a System-$1.x$ Planner into a *System-$2$ Planner with sub-goal decomposition*, outperforming vanilla System-$2$ by 3% and achieving the highest accuracy of $96.7\%$ at 27.3 states.
This highlights the effectiveness of our sub-goal decomposition (more details below).
- •
System-$1.x$ benefits from sub-goal decomposition. We validate the utility of sub-goal decomposition from two observations. First, the full System-$1.x$ outperforms the System-$1.x$ variant that does not perform sub-goal decomposition. Second, System-$2$ also benefits from sub-goal decomposition as shown by the maximum accuracy of 96.7% which is achieved via test-time control and biasing the controller to solve every sub-goal using System-$2$. However, note that System-$2$ with decomposition still applies System-$2$ planning to every step, making System-$1.x$ more performant at any given budget.
- •
System-$1$ is cheaper but not accurate. On one extreme of the plot, System-$1$ Planner is cheaper since it only explores the states that are part of its plan, amounting to an average of 3 states. However, this comes at a cost to performance: it also only achieves an accuracy of 49%. Another limitation of a System-$1$ Planner is that unlike System-$1.x$, it is not controllable and hence, there is no easy affordance for improving performance by exploring more states.
- •
System-$2$ is more accurate but expensive. On the other extreme, System-$2$ Planner achieves a maximum accuracy of 94% but explores a much higher 24.4 states in the process. While System-$2$ can be adapted to minimize #States-Explored, such adaptivity is only possible during inference via state-truncation.
Test-time truncation of #States-Explored is typically ad-hoc and not preferable because the loss in performance will only increase as the plan length grows. This is in contrast to the System-$1.x$ Planner, which allows for systematic control of compute both at training-time (via a user-defined hybridization factor $x$), and at test-time (by biasing the controller).

#### Results for Blocksworld.

Fig. 3(b) (cf. Table 4) reports our results on Blocksworld (BW) that studies out-of-distribution generalization to longer plan lengths. Our first observation is that System-$1$ only obtains an accuracy of 9% and although System-$2$’s accuracy is higher at 28%, given the longer plan lengths, it also explores a significantly higher number of states (55).

Figure: Figure 4: An example decomposition generated by System $1.5$ for Blocksworld. The adjacent blocks ‘C’ and ‘F’ (in the goal state) are separated by 4 blocks in the intital state. The controller generates an intermediate state $\mathcal{G}_{1}$ where blocks ‘C’ and ‘F’ are a block apart, with the sub-goal $s_{0}\rightarrow\mathcal{G}_{1}$ being harder (solved using System-$2$) and the sub-goal $\mathcal{G}_{1}\rightarrow s_{g}$ being easier and solved via System-$1$.
Refer to caption: x5.png

Thus, when we perform truncation to get lower values of #States-Explored, System-$2$’s accuracy drops to almost 0%. System-$1.x$ without sub-goal decomposition also does not work for OOD test points because the controller predicts almost all samples as hard and solves them using System-$2$. Hence, System-$1.x$ without sub-goal decomposition practically becomes a System-$2$ in such scenarios, suffering major losses to performance with truncation. However, in contrast to all baselines, System-$1.x$ *with* sub-goal decomposition can solve a larger fraction of problems at lower budgets (e.g., 25% at 30 states compared to System-$2$ Planner’s 13%) because of
its ability to leverage a System-$1$ Planner for simpler sub-goals that have shorter plan lengths and are more likely to be in-distribution (refer to example in Fig. 4). At maximum #States-Explored, System-$1.x$ obtains comparable performance to a System-$2$ Planner. Overall, when testing on OOD data, the results in Fig. 3(b) highlight the key role that the System-$1.x$ controller plays in decomposing longer-horizon planning problems.
Crucially, what is generally a weak System-$1$ Planner for harder, OOD goals can be used effectively to solve easier, ID sub-goals, thereby saving a lot of compute.

Figure: Figure 5: Performance of System-$1.x$ in conjunction with a symbolic (A^∗) System-$2$ Planner on Maze. The neuro-symbolic System-$1.x$ Planner matches if not outperforms A^∗ search with the same budget of #States-Explored, e.g., by 39% at 11.6 states.
Refer to caption: x6.png

### 4.2 Neuro-symbolic System- 1 . x formulae-sequence 1 𝑥 1.x 1 . italic_x outperforms or matches A ∗ at all budgets

#### Study Setup.

While we primarily designed System-$1.x$ as a fully neural planner with all three components (System-$1$, $2$, and the controller) developed on top of the same LLM, we note that System-$1.x$ can also act as a neuro-symbolic planner. This can be achieved by using a symbolic solver like A^∗ as the System-$2$ component. We follow this setup to report results on the Maze Navigation task, again setting $x\!=\!0.5$.

#### Results.

Table 5 (cf. Table 5) compares the accuracy of all planners at different #States-Explored. Our main result is that the conclusions drawn with a fully neural System-$1.x$ also transfer to a neuro-symbolic System-$1.x$. Notably, at an average of 11.6 states, neuro-symbolic System-$1.x$ outperforms A^∗ by a large margin of 39% (31.0% $\rightarrow$ 70.5%). This can again be explained by the ineffectiveness of #States-Explored truncation for System-$2$ Planners, symbolic or neural.
The trend is also consistent at all lower budgets.
System-$1.x$ can be test-time controlled to obtain a near-perfect accuracy (99.2%), matching that of A^∗.

### 4.3 Analyses and Ablations of System- 1 . x formulae-sequence 1 𝑥 1.x 1 . italic_x Planner

We conduct all analyses and ablations on the maze navigation task.

#### Train-time Control: System- 1.75 1.75 \mathbf{1.75} bold_1.75 trades off efficiency for accuracy compared to System- 1.5 1.5 \bm{1.5} bold_1.5 .

One of the core strengths of our planner is its *training-time controllability*.
The hybridization factor $x$ allows the user to specify the System-$1$ to System-$2$ balance they want in the final planner.
To demonstrate this capability, we train a System-$1.75$ Planner by setting $x=0.75$. Table 6 (cf. Table 6) shows our results on the maze task.
By default, System-$1.75$ uses $16.6$ states on average and obtains an accuracy of $75.7\%$, compared to System-$1.5$’s $70.4\%$ with a default average of 13.6 states (Table 3) i.e., a 5% gain at the cost of 3 more states.

Figure: Figure 6: Train-time controllability of System-$1.x$ Planner by setting $x\!=\!0.75$. System-$1.75$ largely outperforms System-$2$. Compared to Fig. 3(a), System-$1.75$ yields an accuracy of 75.7% vs. 70.4% (with System-$1.5$) by utilizing 3 more states.
Refer to caption: x7.png

Thus, as we increase the value of $x$, the System-$1.x$ Planner will use more states and improve performance, converging to a System-$2$ Planner that additionally performs sub-goal decomposition.
Compared to System-$2$, System-$1.75$ is again significantly more performant at all budgets (e.g., by $28\%$ at $16.6$ states) and eventually obtains the highest accuracy of $96.7\%$ when acting as a System-$2$ with sub-goals.
This echoes our System-$1.5$ Planner findings, which also demonstrated similar gains at high budgets.

Broadly, these results showcase our controller’s effectiveness, which in turn validates our hardness measures and sub-goal decompositions.
We further ablate features of the controller in Appendix B, comparing against a random controller, testing the effectiveness of the sliding window, and contrasting different hardness functions.
These experiments confirm our choices in Section 3.4.

Figure: (a) System-$1.x$ with BFS
Refer to caption: x8.png

#### Generalizability: System- 1 . x formulae-sequence 1 𝑥 1.x 1 . italic_x beats System- 2 2 2 2 with all search algorithms (A ∗ , DFS, BFS).

We conducted our main experiments by leveraging supervision from A^∗ traces. In this experiment, we show that System-$1.x$ is robust to different search algorithms, working with other options like Breadth First Search (BFS) and Depth First Search (DFS).
First, note that for mazes, BFS explores all four actions (up, down, left, right) at each state and hence, on average, is the most expensive search strategy in terms of states explored.
However, for an unweighted maze, BFS always generates optimal plans.
DFS, on the other hand, explores fewer states because it returns the first valid plan, though that plan may not necessarily be optimal.
Appendices C and C contains examples of BFS and DFS trajectories.
Based on Fig. 7 (cf. Tables 7 and 8), we summarize our key findings:

- •
System-$1.x$ continues to outperform System-$2$ and ‘System-$1.x$ without sub-goal decomposition’ by large margins (e.g., up to 39% at 17.4 states for BFS and at 10 states for DFS), showcasing our planner’s flexibility to learn from different algorithms.
- •
System-$1.x$ closely resembles the behavior of the search algorithm it is trained on.
For example, System-$1.x$ (BFS) is more accurate and generates a significantly higher number of optimal plans than System-$1.x$ (DFS) because the former is trained on optimal plans (refer to Table 2 for a study on validity versus optimality).
In the process, however, System-$1.5$ (BFS) explores more states than System-$1.x$ (DFS), similar to their symbolic counterparts.
Among the three algorithms studied in this paper, System-$1.x$ (A^∗) is the most accurate and efficient.

#### Qualitative Analysis of System 𝟏 1 \bm{1} bold_1 , 𝟐 2 \bm{2} bold_2 , and 𝟏 . 𝒙 formulae-sequence 1 𝒙 \bm{1.x} bold_1 bold_. bold_italic_x .

Fig. 8 shows an example from our test set where both System-$1$ and System-$2$ fail but System-$1.x$ succeeds. We consider a maze configuration where the plan length is quite long (8) and there is a solitary path to the goal, making the problem challenging for LLMs. We find that the System-$1$ Planner generates an incorrect plan that ignores the placement of the obstacles. On the other hand, the System-$2$ Planner avoids obstacles successfully initially but then takes a path that leads it to a dead end. It is unable to recover from that and the search does not terminate. Our System-$1.x$ Planner is, however, able to solve the problem successfully by first breaking it up into 3 sub-goals and solving the easy sub-goals close to the start state and the goal state using System-$1$ and the hard sub-goal in the middle (that includes a number of obstacles) with deliberate System-$2$ planning.

Figure: Figure 8: A qualitative example showing (1) a failure case for a System-$1$ Planner because it generates a plan through the obstacles, (2) a failure case for a System-$2$ Planner because the generated plan leads to a dead end and the model does not recover from it, and (3) a successful case for our System-$1.x$ Planner that solves the easy sub-goals near the start state and the goal state using System-$1$ and the hard sub-goal in the middle using System-$2$.
Refer to caption: x10.png

## 5 Discussion and Limitations

#### Comparison to Dual-Process Theories.

While System-$1.x$ draws on dual process theories of human cognition, it deviates in important ways.
Crucially, most dual-process accounts hold that System-1 thinking occurs all the time, with System-2 occurring some of the time (Evans, ), whereas in our planning framework, the two are mutually exclusive.
It is worth noting that, whether mutually exclusive or not, dual-process accounts require some control mechanism that triggers System-$2$; errors in this controller can lead to compounding errors downstream, which has also been posited as a theory for breakdowns in human cognition (Tversky and Kahneman, ; Gilovich et al., ).
We also do not take a position on whether performing search by next-token prediction is optimal; indeed, our neuro-symbolic results in Fig. 5 indicate that System-$1.x$ is compatible with both neural implementations of search and symbolic search.
Dual-process accounts also typically rely on some form of metacognition, where agents reason not only about the task, but also form a *model of reasoning* itself (Ganapini et al., ).
This entails having not only a world model – in our case, how actions affect the agent’s state – but also a model of reasoning, i.e., *how difficult a particular goal is or what kind of planning it might require*.
This is implemented by the controller, which routes between System-$1$ and System-$2$ based on the predicted hardness of a sub-goal.

#### Inferring x 𝑥 x italic_x from a State Budget.

In our work, we set $x$ in System-$1.x$, as well as the test-time control values, inducing a maximum budget.
By fitting a function to the points in Figs. 3, 5, 6 and 7, one can easily go the other direction, mapping a particular state budget (or token budget) to a corresponding value of $x$ or a corresponding control value.
This would allow users with specific compute constraints to ensure that the planner does not use more resources than allotted.

#### Limitations.

Firstly, like past work (Gandhi et al., ; Lehnert et al., ), our work focuses on fully-observable and deterministic domains; however, many real-world problems are partially-observable and non-deterministic.
Secondly, our method is based on model-generated sub-goals; we find in Section 4.1 that System-$2$ also benefits from sub-goals, indicating that they are generally beneficial to all methods.
Similarly, System-$1.x$ relies on a *relative* ranking of sub-goals by hardness; this can entail variable performance if the sub-goals are all easy or all hard (in absolute terms), in which case System-$1.x$ may lose efficiency, solving the most difficult of the easy goals with System-$2$ when System-$1$ would suffice, or lose performance, solving the easiest of a set of hard sub-goals with System-$1$ despite them requiring System-$2$.
This could be remedied by introducing an absolute threshold on hardness; however, this would entail finding that threshold using validation data, which our current method avoids.
Finally, System-$1.x$ training involves creating data with a sliding window of System-$2$ timesteps by assigning each sub-goal to System-$1$ or System-$2$.
While this empirically works well for the problems we study, long plans with hundreds or thousands of steps might require more windows.

## 6 Related Work

#### Combining LLMs and Symbolic Planners.

Despite the widespread success of LLMs in complex problem-solving, a large body of recent work has highlighted their shortcomings on long-horizon planning problems (Valmeekam et al., , ; Pallagani et al., ; Momennejad et al., ; Hirsch et al., ; Zheng et al., ; Aghzal et al., ), persisting across popular prompting techniques like Chain-of-Thought (Wei et al., ), ReAct (Yao et al., ), and Reflexion (Shinn et al., ).
These methods can largely be grouped into System-$1$ inference-time methods in which the LLM does not search, backtrack, or learn from incorrect actions.
Systematic search is either not performed at all or delegated to symbolic solvers (e.g., Liu et al., ; Pan et al., ; Xie et al., , discussed further below), thus deviating from the focus of this work on equipping LLMs to solve harder planning problems via search.

More related to our work are inference-time methods that *do* involve planning, tree search, and backtracking.
These System-$2$-inspired methods have a search algorithm that operates *on top of* and guides an LLM with reward models, value functions, or verifiers (Hao et al., ; Yao et al., ; Besta et al., ; Zhou et al., ; Sel et al., ; Koh et al., ).
In a similar spirit, neuro-symbolic planning systems like *LLM-Modulo Frameworks* (Kambhampati et al., ) have emerged that combine LLMs with symbolic planners (Nye et al., ; Liu et al., ; Pan et al., ; Xie et al., ; Kambhampati et al., ; Zuo et al., )
System-$1.x$ differs from this class of inference-time methods in two major ways. Firstly, it is a training-time method that teaches the LLM to search, with the goal of enhancing the LLM’s intrinsic planning capabilities and discovering more effective search strategies, making it self-contained (as opposed to complex inference-time methods relying on external modules).
Secondly, it is also a hybrid system that can alternate between System-$1$ and System-$2$-style planning, whereas past work is capable of one or the other, but not both. Notably, this kind of hybridization distinguishes System-$1.x$ from other work that either creates hybrids between weaker and stronger models in the form of model cascades (Lin et al., ; Yue et al., ) or between neural and symbolic methods (e.g., LLM-Modulo frameworks).

#### LLMs Generating Plans.

Methods combining LLMs and symbolic planners need some channel of communication between the LLM and the symbolic planning component.
This is usually a value function or reward model producing a single score for a state, making the success of the method contingent on the quality of the reward model, or the LLM’s ability to act as a value function (as in Yao et al. (); Lightman et al. ()).
Furthermore, off-loading planning or search adds additional modules at test-time that may not always be available for certain domains.
It also assumes that the model’s representation is already sufficient for the task and complicates finetuning the representation,
since externalized search is typically non-differentiable.
In an attempt to mitigate such concerns, a second line of work removes the dependency on separate reward models and external tools and teaches LLMs to conduct search by themselves (Yang et al., ; Gandhi et al., ; Lehnert et al., ). For example, Gandhi et al. () introduce Stream-of-Search (SoS), which teaches LLMs to search by verbalizing trajectories and Lehnert et al. () propose Searchformer, that learns from A^∗ search dynamics.
This line of work predates LLMs: Anthony et al. () generate data from tree search which they use to iteratively train a neural model to perform System-$1$ planning.
However, Gandhi et al. () and Lehnert et al. () differ from our work in that their final models are System-$2$-only, incurring a high computational cost for all examples and states by performing full planning at all times, whereas our method is a hybrid between Systems $1$ and $2$, dynamically allocating computation to more difficult parts of the plan. Moreover, to meet user budget constraints, System-$2$-only methods also have to rely on approaches like post-hoc truncation while System-$1.x$ offers more systematic controllability via its controller.

## 7 Conclusion

We introduced the System-$1.x$ Planner, a novel neural planner that adaptively interleaves quick and cost-efficient System-$1$ planning with more costly but performant System-$2$ planning.
On two tasks, we showed that our method results in strong performance across a range of budgets: on Mazes, System-$1.x$ beats obtains the best performance at every budget, and on Blocksworld it outperforms System-$2$ at all budgets except the highest, where it is comparable.
System-$1.x$ Planner achieves this by decomposing problems into sub-goals and intelligently allocating System-$2$’s additional resources to harder sub-goals while allowing System-$1$ to quickly solve the easier ones. Furthermore, our method is adaptable, allowing users to control the cost and performance by specifying the degree to which the planner relies on System-$2$.
In our analysis, we find that System-$1.x$ is controllable, generalizes to various search algorithms, and performs better out-of-distribution.
We also ablate choices to our training data creation, including the choice of the hardness function and the search algorithm, finding System-$1.x$ is robust to such changes.

## Acknowledgements

This work was supported by NSF-CAREER Award 1846185, NSF-AI Engage Institute DRL-2112635, DARPA MCS Grant N66001-19-2-4031, and Google PhD Fellowships. The views contained in this article are those of the authors and not of the funding agency.

## Appendix A Additional Details of System- 1 . x formulae-sequence 1 𝑥 1.x 1 . italic_x Planner

#### Background on A ∗ .

A^∗ is an informed search algorithm that decides the next best state to expand with a function $f(n)=g(n)+t(n)$ that considers (1) the cost $g(n)$ from the start state to the current state $n$, and (2) a heuristic function $t(n)$ that gives an estimate of the cost from state $n$ to the goal. Note that A^∗ is optimal if the heuristic $t(n)$ is admissible (i.e., $t(n)\leq t^{*}(n)$ which means that the heuristic never overestimates the true cost to the goal $h^{*}(n)$) and consistent (i.e., $t(n)\leq c(n,n^{\prime})+t(n^{\prime})$ for all states $n$ and its successor $n^{\prime}$ and $c$ is the cost to transition from $n$ to $n^{\prime}$). For the Maze Navigation task, Manhattan Distance is an example of such an admissible heuristic, and hence $A^{*}$ with it will always generate optimal plans.

#### System- 𝟐 2 \mathbf{2} bold_2 Planner for Maze Navigation.

We implement a System-$2$ Planner for the Maze domain by verbalizing all possible explorations at each state, including the ones that lead to invalid states (i.e., outside the maze, have obstacles, or have already been visited). See example in Appendix C.

#### System- 𝟐 2 \mathbf{2} bold_2 Planner for Blocksworld.

In contrast to the Maze domain, the number of actions at each state in Blocksworld problem is directly proportional to the total number of blocks. Consequently, the number of possible states that can be explored (both valid and invalid) is significantly larger in this domain, often exceeding the maximum input token budgets of standard LLMs (in our case, 8096 tokens). Therefore, when verbalizing the search trajectories $\mathcal{T}$ in $\mathcal{D}_{\textrm{Sys2}}$ using A^∗ search to train System-$2$ Planner, we cap the number of valid and invalid states explored to 3 and 2 respectively. The verbalized valid states are chosen by picking the top-3 scored states as per the A^∗ heuristic (that computes the number of mismatches between the start state and the goal state), while (up to) 2 invalid states are chosen randomly to make the model learn from mistakes.
Refer to Appendix C for an example.

## Appendix B Additional Results

System-$1.x$ Controller outperforms a random controller. In Table 1, we compare our System $1.5$ controller with a random controller that arbitrarily chooses 50% problems to be solved by System-$2$. Our trained controller outperforms the random controller by a significant 10%.

**Table 1: Comparison of our trained controller in System-$1.x$ Planner with a controller that randomly chooses $x\%$ of problems to solve with System-$2$.**
|  | Accuracy |
| --- | --- |
| System $1.5$ (w/ random controller) | 70.5 |
| System $1.5$ (w/ our controller) | 79.5 |

#### Analyses of System- 1 . x formulae-sequence 1 𝑥 1.x 1 . italic_x Controller.

In this section, we analyze the different components of our System-$1.x$ controller.

Figure: Figure 9: Comparison of System-$1.x$ Planner with and without sliding window-based sub-goal decomposition on the Maze Navigation task. Sliding window-based decomposition outperforms the variant without it at all budgets.
Refer to caption: x11.png

- •
Effectiveness of Sliding Window Decomposition. Recall that we generated training data for the controller by using a sliding window approach that assigned a contiguous $x$% of the plan to System-$2$ according to a hardness function.
Here, we evaluate the effectiveness of this approach by comparing it to a System-$1.x$ variant *without* the sliding window decomposition.
In this variant, the $x$% System-$2$ allocation can either be at the beginning or at the end of the plan but not in the middle, resulting in a maximum of two decompositions instead of three.
As shown in Fig. 9, our sliding window variant not only obtains higher accuracy but is also far more efficient. This is because with three decompositions, a weaker System-$1$ Planner can be used to solve two granular sub-goals (instead of one) and hence is more likely to succeed.
- •
Comparison of Hardness Functions. Our experiments on maze used the number of obstacles in a sub-maze as the hardness function.
In Table 10, we compare it to Manhattan Distance,
which rates goals that are further away (according to the distance function) as more difficult.
We observe that both functions lead to comparable performance, with obstacles being slightly more efficient.
Taken together with the previous experiment, these results quantify the influence of two essential inputs to the controller’s training: hardness function and the decomposition strategy.

**Table 2: Comparison of Valid Plan Accuracy and Optimal Plan Accuracy for System-$1.x$ Planner in Maze Navigation using A^∗ search. While not using sub-goal decomposition nearly guarantees optimality, using sub-goal decomposition may generate plans that are sub-optimal.**
|  | Valid Plan | Optimal Plan | #States-Explored |
| --- | --- | --- | --- |
| System-$1.x$ (w/o sub-goals) | 33.5 | 33.2 | 4.8 |
| System-$1.x$ (w/o sub-goals) | 38.2 | 38.0 | 9.7 |
| System-$1.x$ (w/o sub-goals) | 62.2 | 61.7 | 15.0 |
| System-$1.x$ (w/o sub-goals) | 79.5 | 78.7 | 17.4 |
| System-$1.x$ (w/ sub-goals) | 30.5 | 30.2 | 4.5 |
| System-$1.x$ (w/ sub-goals) | 56.2 | 53.7 | 10.0 |
| System-$1.x$ (w/ sub-goals) | 70.4 | 61.5 | 13.6 |

#### Optimality of System- 1 . x formulae-sequence 1 𝑥 1.x 1 . italic_x .

In Table 2, we compare the optimality and validity of the plans generated by our System-$1.x$ Planner. While System-$1.x$ without sub-goal decomposition generates plans that are almost always optimal, we observe that sub-goal decomposition may sometimes hurt optimality. This happens because the sub-goals generated by the controller may not always lie on the optimal path.

## Appendix C Prompts and Examples

See the subsequent pages for prompts and examples from both domains.

[Uncaptioned image]: x13.png

[Uncaptioned image]: x14.png

[Uncaptioned image]: x15.png

[Uncaptioned image]: x16.png

[Uncaptioned image]: x17.png

[Uncaptioned image]: x18.png

## Appendix D Tables corresponding to Result Figures

In the tables below, we report the accuracies corresponding to all the plots in the paper.

**Table 3: Comparison of System-$1.x$ Planner ($x=0.5$) with all baselines on Maze Navigation (corresponding to Fig. 3(a)). The blue rows indicate accuracy obtained by all methods when #States-Explored is matched to that of System $1.5$ with sub-goals. The green rows indicate accuracy obtained when #States-Explored is maximized. All tables, henceforth, will use the same color coding.**
|  | Accuracy | #States-Explored |
| --- | --- | --- |
| System-$1$ | 48.7 | 3.1 |
| System-$2$ (truncated) | 12.2 | 4.8 |
| System-$2$ (truncated) | 19.7 | 9.9 |
| System-$2$ (truncated) | 37.2 | 13.6 |
| System-$2$ (truncated) | 37.2 | 14.8 |
| System-$2$ (truncated) | 63.7 | 19.8 |
| System-$2$ (default) | 93.7 | 24.4 |
| System-$1.5$ w/o sub-goal (truncated) | 33.5 | 4.8 |
| System-$1.5$ w/o sub-goal (truncated) | 38.2 | 9.7 |
| System-$1.5$ w/o sub-goal (truncated) | 50.0 | 13.4 |
| System-$1.5$ w/o sub-goal (truncated) | 62.2 | 15.0 |
| System-$1.5$ w/o sub-goal (default) | 79.5 | 17.4 |
| System-$1.5$ w/o sub-goal (test-time controlled) | 83.7 | 20.0 |
| System-$1.5$ (w/o sub-goal) (test-time controlled) | 93.7 | 24.4 |
| System-$1.5$ w/ sub-goal (truncated) | 30.5 | 4.5 |
| System-$1.5$ w/ sub-goal (truncated) | 56.2 | 10.0 |
| System-$1.5$ w/ sub-goal (default) | 70.4 | 13.6 |
| System-$1.5$ w/ sub-goal (test-time controlled) | 82.2 | 19.9 |
| System-$1.5$ w/ sub-goal (test-time controlled) | 92.2 | 24.4 |
| System-$1.5$ w/ sub-goal (test-time controlled) | 96.7 | 27.3 |

**Table 4: Comparison of System-$1.x$ Planner ($x=0.5$) with all baselines on Blocksworld (corresponding to Fig. 3(b)).**
|  | Accuracy | #States-Explored |
| --- | --- | --- |
| System $1$ | 9.0 | 4.5 |
| System $2$ (truncated) | 0.0 | 9.8 |
| System $2$ (truncated) | 0.0 | 19.9 |
| System $2$ (truncated) | 13.0 | 29.3 |
| System $2$ (truncated) | 27.0 | 38.2 |
| System $2$ (default) | 28.0 | 55.5 |
| System-$1.5$ w/o sub-goal (truncated) | 0.0 | 9.8 |
| System-$1.5$ w/o sub-goal (truncated) | 0.0 | 19.9 |
| System-$1.5$ w/o sub-goal (truncated) | 13.0 | 29.3 |
| System-$1.5$ w/o sub-goal (truncated) | 27.0 | 38.0 |
| System-$1.5$ w/o sub-goal (default) | 28.0 | 55.1 |
| System-$1.5$ w/ sub-goal (truncated) | 1.5 | 9.6 |
| System-$1.5$ w/ sub-goal (truncated) | 17.5 | 20.0 |
| System-$1.5$ w/ sub-goal (truncated) | 25.0 | 30.0 |
| System-$1.5$ w/ sub-goal (default) | 25.0 | 38.3 |
| System-$1.5$ w/ sub-goal (test-time controlled) | 26.0 | 53.5 |

**Table 5: Comparison of Neuro-symbolic System-$1.x$ Planner ($x=0.5$) with all baselines on Maze Navigation (corresponding to Fig. 5).**
|  | Accuracy | #States-Explored |
| --- | --- | --- |
| A^∗ (truncated) | 12.5 | 4.8 |
| A^∗ (truncated) | 22.5 | 9.8 |
| A^∗ (truncated) | 31.0 | 11.3 |
| A^∗ (truncated) | 42.0 | 14.5 |
| A^∗ (truncated) | 67.7 | 19.8 |
| A^∗ (default) | 100.0 | 22.4 |
| System-$1.5$ w/o sub-goal (truncated) | 33.0 | 4.8 |
| System-$1.5$ w/o sub-goal (truncated) | 40.2 | 9.8 |
| System-$1.5$ w/o sub-goal (truncated) | 45.7 | 11.5 |
| System-$1.5$ w/o sub-goal (truncated) | 65.7 | 14.9 |
| System-$1.5$ w/o sub-goal (default) | 84.2 | 16.5 |
| System-$1.5$ w/o sub-goal (test-time controlled) | 94.0 | 20.0 |
| System-$1.5$ w/o sub-goal (test-time controlled) | 100.0 | 22.4 |
| System-$1.5$ w/ sub-goal (truncated) | 30.5 | 4.5 |
| System-$1.5$ w/ sub-goal (truncated) | 58.7 | 10.0 |
| System-$1.5$ (default) | 70.5 | 11.6 |
| System-$1.5$ w/ sub-goal (test-time controlled) | 76.0 | 14.8 |
| System-$1.5$ w/ sub-goal (test-time controlled) | 89.7 | 19.9 |
| System-$1.5$ w/ sub-goal (test-time controlled) | 99.2 | 23.9 |

**Table 6: Comparison of System-$1.x$ Planner ($x\!=\!0.75$) with all baselines on Maze Navigation (corresponding to Fig. 6).**
|  | Accuracy | #States-Explored |
| --- | --- | --- |
| System-$2$ (truncated) | 12.2 | 4.8 |
| System-$2$ (truncated) | 19.7 | 9.9 |
| System-$2$ (truncated) | 37.2 | 14.8 |
| System-$2$ (truncated) | 47.0 | 16.6 |
| System-$2$ (truncated) | 63.7 | 19.8 |
| System-$2$ (default) | 93.7 | 24.4 |
| System-$1.75$ w/o sub-goal (truncated) | 24.2 | 4.6 |
| System-$1.75$ w/o sub-goal (truncated) | 29.2 | 9.8 |
| System-$1.75$ w/o sub-goal (truncated) | 44.5 | 14.6 |
| System-$1.75$ w/o sub-goal (default) | 59.7 | 16.6 |
| System-$1.75$ w/o sub-goal (default) | 86.5 | 20.3 |
| System-$1.75$ w/o sub-goal (test-time controlled) | 93.7 | 24.4 |
| System-$1.75$ w/ sub-goal (truncated) | 23.0 | 4.9 |
| System-$1.75$ w/ sub-goal (truncated) | 38.7 | 9.6 |
| System-$1.75$ w/ sub-goal (truncated) | 66.7 | 15.0 |
| System-$1.75$ w/ sub-goal (default) | 75.7 | 16.6 |
| System-$1.75$ w/ sub-goal (test-time controlled) | 82.0 | 19.9 |
| System-$1.75$ w/ sub-goal (test-time controlled) | 91.2 | 24.4 |
| System-$1.75$ w/ sub-goal (test-time controlled) | 96.7 | 26.8 |

**Table 7: Comparison of System-$1.x$ Planner ($x\!=\!0.5$ and BFS) with all baselines on Maze Navigation (corresponding to Fig. 7(a)).**
|  | Accuracy | #States-Explored |
| --- | --- | --- |
| System-$2$ (truncated) | 11.7 | 9.4 |
| System-$2$ (truncated) | 28.0 | 17.4 |
| System-$2$ (truncated) | 28.0 | 19.9 |
| System-$2$ (truncated) | 56.2 | 29.7 |
| System-$2$ (default) | 91.2 | 39.8 |
| System-$1.5$ w/o sub-goal (truncated) | 35.2 | 9.6 |
| System-$1.5$ w/o sub-goal (truncated) | 45.0 | 17.2 |
| System-$1.5$ w/o sub-goal (truncated) | 52.5 | 19.9 |
| System-$1.5$ w/o sub-goal (default) | 77.2 | 26.9 |
| System-$1.5$ w/o sub-goal (test-time controlled) | 81.2 | 30.0 |
| System-$1.5$ w/o sub-goal (test-time controlled) | 91.2 | 39.8 |
| System-$1.5$ w/ sub-goal (truncated) | 43.0 | 9.8 |
| System-$1.5$ w/ sub-goal (default) | 67.0 | 17.4 |
| System-$1.5$ w/ sub-goal (test-time controlled) | 78.5 | 29.7 |
| System-$1.5$ w/ sub-goal (test-time controlled) | 86.5 | 39.9 |
| System-$1.5$ w/ sub-goal (test-time controlled) | 91.7 | 45.4 |

**Table 8: Comparison of System-$1.x$ Planner ($x\!=\!0.5$ and DFS) with all baselines on Maze Navigation (corresponding to Fig. 7(b)).**
|  | Valid Acc | Avg States |
| --- | --- | --- |
| System-$2$ (truncated) | 11.7 | 4.7 |
| System-$2$ (truncated) | 23.2 | 9.7 |
| System-$2$ (truncated) | 42.0 | 14.5 |
| System-$2$ (truncated) | 69.7 | 19.8 |
| System-$2$ (truncated) | 81.2 | 25.0 |
| System-$2$ (default) | 83.5 | 30.4 |
| System-$1.5$ w/o sub-goal (truncated) | 36.0 | 4.7 |
| System-$1.5$ w/o sub-goal (truncated) | 50.7 | 9.8 |
| System-$1.5$ w/o sub-goal (truncated) | 73.2 | 15.0 |
| System-$1.5$ w/o sub-goal (default) | 74.0 | 18.7 |
| System-$1.5$ w/o sub-goal (test-time controlled) | 76.3 | 19.8 |
| System-$1.5$ w/o sub-goal (test-time controlled) | 81.2 | 25.0 |
| System-$1.5$ w/o sub-goal (test-time controlled) | 83.5 | 30.4 |
| System-$1.5$ (truncated) | 40.2 | 4.5 |
| System-$1.5$ (default) | 62.3 | 10.0 |
| System-$1.5$ (test-time controlled) | 76.3 | 14.9 |
| System-$1.5$ (test-time controlled) | 79.7 | 20.0 |
| System-$1.5$ (test-time controlled) | 82.7 | 33.6 |

**Table 9: Comparison of System-$1.x$ Planner with and without sliding window decomposition (corresponding to Fig. 10).**
|  | Accuracy | #States-Explored |
| --- | --- | --- |
| System-$1.5$ w/o Sliding Window (truncated) | 27.5 | 4.6 |
| System-$1.5$ w/o Sliding Window (truncated) | 45.2 | 10.0 |
| System-$1.5$ w/o Sliding Window (default) | 67.2 | 17.0 |
| System-$1.5$ w/o Sliding Window (test-time controlled) | 72.1 | 20.0 |
| System-$1.5$ w/o Sliding Window (test-time controlled) | 77.2 | 25.0 |
| System-$1.5$ w/o Sliding Window (test-time controlled) | 83.2 | 30.0 |
| System-$1.5$ w/o Sliding Window (test-time controlled) | 90.0 | 35.3 |
| System-$1.5$ w/ Sliding Window (truncated) | 30.5 | 4.5 |
| System-$1.5$ w/ Sliding Window (truncated) | 56.2 | 10.0 |
| System-$1.5$ w/ Sliding Window (default) | 70.4 | 13.6 |
| System-$1.5$ w/ Sliding Window (test-time controlled) | 82.2 | 19.9 |
| System-$1.5$ w/ Sliding Window (test-time controlled) | 92.2 | 24.4 |
| System-$1.5$ w/ Sliding Window (test-time controlled) | 96.7 | 27.3 |

**Table 10: Comparison of two hardness functions (Manhattan Distance and #Obstacles) for Maze Navigation (corresponding to Fig. 10).**
|  | Accuracy | #States-Explored |
| --- | --- | --- |
| System-$1.5$ w/o sub-goal (#Obstacles) | 33.5 | 4.8 |
| System-$1.5$ w/o sub-goal (#Obstacles) | 38.2 | 9.7 |
| System-$1.5$ w/o sub-goal (#Obstacles) | 50.0 | 13.4 |
| System-$1.5$ w/o sub-goal (#Obstacles) | 62.2 | 15.0 |
| System-$1.5$ w/o sub-goal (#Obstacles) | 79.5 | 17.4 |
| System-$1.5$ w/o sub-goal (#Obstacles) | 83.7 | 20.0 |
| System-$1.5$ w/o sub-goal (#Obstacles) | 93.7 | 24.4 |
| System-$1.5$ w/o sub-goal (Manhattan) | 31.7 | 4.8 |
| System-$1.5$ w/o sub-goal (Manhattan) | 54.5 | 15.0 |
| System-$1.5$ w/o sub-goal (Manhattan) | 35.2 | 10.0 |
| System-$1.5$ w/o sub-goal (Manhattan) | 80.0 | 18.8 |
| System-$1.5$ w/o sub-goal (Manhattan) | 81.5 | 19.9 |
| System-$1.5$ w/o sub-goal (Manhattan) | 93.7 | 24.4 |

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: 1. The term plan validity should not be used interchangeably with plan accuracy. Validity is a binary concept that indicates whether a plan meets all required conditions or constraints (i.e., valid or invalid), whereas accuracy implies a measure of correctness or closeness to an ideal solution, which can vary in degree.
2. The definition of a sub-goal as a "pair of states" adds unnecessary complexity and deviates from the usual understanding. Sub-goals are typically single intermediate states that help guide progress toward the final goal.
3. The hardness function defined for Blocksworld, in Section A.3, seems wrong. It states that if a block is not on the table and not in its goal position, an additional 1 is added to the hardness cost. However, this approach doesn't account for scenarios where a block is in the air after a pick-up action—this intermediate position may not be the goal but could be one step away from it. Adding to the hardness cost in such cases could mistakenly label states as more challenging, even when they are actually closer to the goal. Similarly for the Maze Navigation task, counting all obstacles in the sub-maze as part of the hardness cost is problematic, as obstacles outside the plan trajectory can inflate the difficulty inaccurately.
4. In Section 2.3, under Controller Training Data, Step 3, it’s unclear why only a contiguous chunk should be assigned to System-2. What is the rationale for restricting it to contiguous data?
5. According to the authors' definition of sub-goals, are they explicitly training the Controller to decompose the task into exactly three sub-goals?

**Minor Comments:**
1. Examples in the figures, particularly Figure 2, would benefit from clearer annotations in the maze to improve the interpretation of the numbering. The current numbering follows a top-to-bottom, left-to-right order, but this is not immediately clear.
2. In Figure 2, System-2 output, I do not understand why this is invalid “Exploring action left State [3, 1] is invalid”?
3. The authors should maintain consistency in their notation. In Section 2.3, when discussing Controller training data, the notation for initial and goal states switches from $s_i$​ and $s_j$​ in Step 1 to $s_0$​ and $s_g$​ later in the paragraph.


**References:**

[1] Fabiano, F., Pallagani, V., Ganapini, M.B., Horesh, L., Loreggia, A., Murugesan, K., Rossi, F. and Srivastava, B., 2023, December. Plan-SOFAI: A Neuro-Symbolic Planning Architecture. In Neuro-Symbolic Learning and Reasoning in the era of Large Language Models.
soundness: 2
strengths: An innovative feature of this hybrid approach, which combines quick solutions from System-1 with thorough search-based solutions from System-2, is a user-controlled parameter x (between 0 and 1) that adjusts how much System-2 is used compared to System-1. This allows users to balance speed and accuracy based on the task’s needs.
summary: This work proposes a hybrid planning system that combines a large language model (LLM) fine-tuned to act as either a System-1 or System-2 planner, with a Controller that decomposes tasks into sub-goals based on difficulty. The Controller generates a meta-plan by assigning "easy" sub-goals to System-1 for faster solutions and "hard" sub-goals to System-2 for more deliberate, search-based solutions. The final plan is constructed by concatenating sub-plans from both systems. However, it faces limitations due to compounding errors across systems, particularly as task complexity grows.
weaknesses: 1. A significant limitation of this approach is its dependency on multiple components performing flawlessly: System-1 must solve the easy sub-goals without hallucinating, System-2 must solve the harder sub-goals using search trajectories accurately, and the Controller must correctly decompose and assign tasks between the two systems. This compounded reliance on error-free performance from each component raises concerns about the approach’s reliability, especially as problem complexity increases. For even moderately difficult tasks, or as the number of objects scales, this method may struggle to maintain effectiveness, as errors are likely to accumulate across the system.
2. A limitation of this hybrid approach is that selecting the x value too greedily can hurt performance and increase training computation costs. Meanwhile, setting x too high leads to more thorough searches by System-2, which increases compute requirements and makes the approach similar to existing methods like fine-tuning LLMs for planning or SOFAI architectures [1].
3. For System-2, the hardness function should be explicitly defined for each specific domain in which the planner operates. Without domain-specific definitions, the hardness function risks being too generalized, leading to inaccurate difficulty assessments that don’t align with the unique challenges of each task.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: - You make the case that System-1.x is advantageous over inference-time methods relying on symbolic planners since they may not exist for certain domains, yet System-1.x relies on defining a hardness function, which is essentially a heuristic function. How could System-1.x be leveraged in new domains where a user is not a domain expert?
- In addition, it is non-trivial to construct hardness functions for multi-task domains like Alfworld [1], Robotouille [2] or Mini-BEHAVIOR [3]. How would System-1.x be applied to such domains?
- There appears to be a tradeoff in Figure 3 with accuracy and states explored with Sys-1.5 with and without subgoals. Sys-1.5 with subgoals achieves higher performance with less states explored but as the state exploration budget increases, no subgoals is better. Why is that?

[1] Alfworld: Aligning text and embodied environments for interactive learning (Shridhar et. al 2020)

[2] Demo2Code: From Summarizing Demonstrations to Synthesizing Code via Extended Chain-of-Thought (Wang et. al 2023)

[3] Mini-BEHAVIOR: A Procedurally Generated Benchmark for Long-horizon Decision-Making in Embodied AI (Jin et. al 2023)
soundness: 3
strengths: $Originality:$ This paper introduces a new method to collect data to finetune a hybrid System 1/2 system whose hybridization factor x can be customized during train and test time.

$Quality:$ The figures and methodology are well-done and the experiments cover relevant baselines and ablations.

$Clarity:$ The paper is well-written and clear.

$Significance:$ Constructing LLM planners that can outperform classical planning approaches with minimal exploration is very important in domains where querying the world model can be expensive (e.g. real world systems like robotics).
summary: This paper introduces System-1.x which acts as a hybrid System 1 / System 2 planner that outperforms fully System 1 and 2 systems, an A* planner, and a System-1.x variant without subgoal decomposition. This paper contributes a method for collecting data to train a System-1.x system through the introduction of domain-specific hardness functions to determine which of the collected samples should be annotated for System-1 (easy samples) or System-2 (hard samples).
weaknesses: The introduction makes the following claim

"System-1.x is a fully LLM-based neural planner ... not relying on any external solvers or verifiers... it has an advantage over inference-time methods that rely on symbolic planners which may not exist for certain domains."

However, System-1.x strongly rely on the presence of a hardness function, which is essentially a heuristic function. This assumption is too strong and cannot simply be listed as a limitation of this approach; the domains that are tested on could be purely solved using classical planners like A* with access to the hardness (heuristic) function and a valid plan would be retrieved (regardless of consistency or admissibility of the hardness function) much faster than any LLM approach in terms of inference time.

To improve this paper, evaluating on environments where classical planners cannot be trivially applied would give more credibility to this LLM approach. A user-specified hardness function cannot be provided for the environment since a classical planner would be able to utilize this along with the other environment information provided to the System-1.x planner and quickly find a valid plan. 

One potential idea is utilizing an LLM to provide a hardness value for a pair of states as other works have done, using an LLM to approximate a heuristic function [1,2,3]. This would require some new experiments to show the effectiveness of the hardness function and would necessitate a new approach other than the sliding window mechanism to be token-efficient.

This is a very important problem to solve in this space and I wish the authors the best of luck.

[1] Large Language Models as Commonsense Knowledge for Large-Scale Task Planning (Zhao et. al 2023)

[2] Reasoning with Language Model is Planning with World Model (Hao et. al 2023)

[3] Toolchain*: Efficient Action Space Navigation in Large Language Models with A* Search (Zhuang et. al 2023)

---

confidence: 5
contribution: 1
initial_rating: 3
presentation: 2
questions: 1. In the experimental setup, the authors mention that the hybridization factor x allows System-1.x to control the degree of System-1 versus System-2 planning. How sensitive is this hybridization factor to changes in task complexity? Were there significant trade-offs observed with larger values of x in different domains?
2. In discussing Blocksworld’s out-of-distribution generalization, the paper mentions that System-1.x effectively utilizes System-1 for ID sub-goals while reserving System-2 for OOD sub-goals. Could the authors explain how the controller identifies which sub-goals are in-distribution vs. out-of-distribution during inference?
3. The authors claim that System-1.x can match or exceed a purely System-2 Planner’s accuracy with fewer states explored. What specific methods were used to prevent overfitting to the training traces, especially for tasks requiring extensive state exploration?
4. Why is there no baseline comparison against other fast and slow architectures used for solving planning problems? It is not clear to me what is the advantage of using this approach against architectures like Plan-SOFAI that are both optimal and resource-efficient compared to System 2 solvers for planning tasks.
soundness: 2
strengths: System-1.x shows robust adaptability and performance across different planning tasks (e.g., Maze Navigation, Blocksworld), outperforming both purely System-1 and System-2 planners due to its effective sub-goal decomposition.
summary: The paper proposes System-1.x, a hybrid planning framework using language models to balance fast, intuitive System-1 planning with deliberate, accurate System-2 planning.
weaknesses: The related work section of the paper does not cover papers similar to this work. To cite a few papers that should have been used as baselines to compare System 1.x against - 
[1] Katz, M., Kokel, H., Srinivas, K., & Sohrabi, S. (2024). Thought of Search: Planning with Language Models Through The Lens of Efficiency. In The First Workshop on System-2 Reasoning at Scale, NeurIPS'24.
[2] Fabiano, F., Pallagani, V., Ganapini, M. B., Horesh, L., Loreggia, A., Murugesan, K., ... & Srivastava, B. (2023, December). Plan-SOFAI: A Neuro-Symbolic Planning Architecture. In Neuro-Symbolic Learning and Reasoning in the era of Large Language Models.
[3] Webb, T., Mondal, S. S., Wang, C., Krabach, B., & Momennejad, I. (2023). A Prefrontal Cortex-inspired Architecture for Planning in Large Language Models. arXiv preprint arXiv:2310.00194.
Refer to the questions for more weaknesses.

---

confidence: 5
contribution: 1
initial_rating: 1
presentation: 2
questions: In the results section for blocksworld, which numbers are from in-distribution testing and which are from out-of-distribution testing?

What guarantees does System 1.75 have?

Did you consider wall-clock time budgets? This would be a more fair comparison. Surely the authors know that querying LLMs repeatedly takes far longer than querying A*, so I'm curious why these times weren't reported in the paper?
soundness: 1
strengths: In general, the goal of creating a neurosymbolic planning system is a very good one. However, the one presented in this paper is preliminary. 

I really like the idea of having a hybridization factor. It could be interesting to have a way to control this at inference time rather than at training time, i.e. like iterative-deeping based searches use more search budget when given more time.
summary: This paper attempts to create a mixed-mode planning system that both immediately generates plans without deliberate state-space search, and does deliberate state space search.

However, this paper seems deliberately misleading in terms of what it claims, namely the improvements over A*.
weaknesses: While this work attempts to build a neurosymbolic planning system, which is a good goal, it seems like the work may not be ready for publication at ICLR. 

The main results of the paper rest on a claim about the "States explored" metric, however, there are several issues with this evaluation. Primarily, computational costs of querying LLMs are not accounted for. A single pass of an LLM clearly can do a significant amount of computation. Furthermore, intermediate LLM-generated states are never checked, e.g. they could contain hallucinations, so it doesn't seem like they'd make a reasonable metric. More importantly there is simply no guaranteed correspondence between intermediate states inside of A* and reported intermediates produced by an LLM to the degree that the two can be compared meaningfully. Because of this, it is unreasonable to restrict A* to run in correspondence with the LLM output, when a full A* computation may several orders of magnitude less than a computational single pass of an LLM. Since the paper rests on the states explored metric, I highly encourage the authors to propose a better method for comparing computational costs between LLMs and A*. 

Another ommission is the fact the the overall system is trained by calling A* thousands of times, which makes an efficiency argument extremely questionable. Regardless of the current state of such an argument, I do buy into the general idea that mixed-system planning algorithm could be more efficient than a system-2 one and more accurate than a system-1 one, but I think the authors would need to fairly evaluate this to make progress on building such an algorithm.

The other main metric used in the paper is "valid plan accuracy". Such a metric is not meaningful when using systems with guarantees, namely A*, which is guaranteed to find optimal plans, while the proposed system has no such guarantees. Because of the false equation between A* intermediate states and LLM-output, the budget restriction is not meaningful and skews the accuracy metric significantly. For instance, if wall time budget were used instead, A* would simply have an accuracy of 100%. Reporting otherwise is potentially misleading. 

The paper claims to test out-of-distribution blocksworld, but it is unclear from figure 1 which results are out of distribution testing and which are in-distribution testing. Also, the left hand side of figure 1 has a correct maximum accuracy of 100%, but the right hand side has a maximum accuracy of only 30%, which seems extremely misleading. Can you clearly label which results in Figure 1 are from in-distribution versus out-of-distribution testing and present the results in Figure 1 with a uniform scale 0-100?

"model-based" on line 144 seems misused, namely confusing parameterized models like neural networks with transition models used in planning and RL. In general, some terminology is unconventional or misused. 

line 253: "we assume that they can be decomposed into sub-goals". This is a very dangerous assumption that rules out true planning problems, as often sub-goals interact. This is the case for blocksworld (but not the maze task), so since the blocksworld dataset has been filtered in this way, it no longer represents the original task and is in fact far simpler to solve [1]. The method for decomposing plans is not obvious, and the sliding window approach, while interesting, is certainly not guaranteed to decompose an arbitrary problem successfully. In the worst case, the system must always be able to fall back on System 2. 

The system is given tiny datasets and (for mazes) tested within distribution. 5x5 mazes are far too small and A* can scale to much bigger problems, while it's unclear if the proposed LLM-based approach does. The relatively high system 1 performance is a good indicator that parts of the problem are being memorized -- and in the case of mazes it is clear how this is possible since the task has decomposable subgoals that can be independently memorized. It's good that out-of-distribution was considered for blocksworld, but the results section doesn't always distinguish between numbers reported from in-distribution testing and out-of-distribution testing. 

In general, planning is misunderstood. By default A* is sound, complete, and produces optimal plans. In contrast, an LLM generator is not sound, not complete, and not optimal. When A* is limited by search budget, it is not the same algorithm, but still will never produce an incorrect plan, and if given enough time will produce the optimal plan. In contrast, an LLM (or system that uses one) is capable of producing incorrect plans, and has no optimality guarantee even if given infinite computation. The proposed method does not have any guarantees, wheras systems like LLM-Modulo do have soundness guarantees (but not completeness!). Please consider adding a discussion section that explicitly compares the theoretical guarantees and limitations of A* versus the proposed LLM-based approach. This could help readers better understand the tradeoffs involved and the contexts in which each approach might be most appropriate.

[1] Sussman, G. J. (1973). A computational model of skill acquisition.

See also: https://en.wikipedia.org/wiki/Sussman_anomaly

Meta-review: This paper presents a framework for LLM-based planning that adaptively interleaves quick and cost-efficient planning with more costly but performant planning. This is achieved by having a controller decompose the problem into sub-goals and then classifying them as requiring the efficient or performant planner. The paper demonstrates that this framework creates a planner with improved controllability, flexibility, and generalizability.

Decision: Accept (Poster)