LLMs Can Plan Only If We Tell Them
Authors: Bilgehan Sel
Ruoxi Jia
Ming Jin
Venue: ICLR 2025 Poster (2025)
Keywords: large language models
decision-making
planning
Primary area: foundation or frontier models, including LLMs
TL;DR: Investigating what enables autonomous planning in large language models

Abstract: Large language models (LLMs) have demonstrated significant capabilities in natural language processing and reasoning, yet their effectiveness in autonomous planning has been under debate. While existing studies have utilized LLMs with external feedback mechanisms or in controlled environments for planning, these approaches often involve substantial computational and development resources due to the requirement for careful design and iterative backprompting. Moreover, even the most advanced LLMs like GPT-4 struggle to match human performance on standard planning benchmarks, such as the Blocksworld, without additional support. This paper investigates whether LLMs can independently generate long-horizon plans that rival human baselines. Our novel enhancements to Algorithm-of-Thoughts (AoT), which we dub AoT+, help achieve state-of-the-art results in planning benchmarks out-competing prior methods and human baselines all autonomously.

Published as a conference paper at ICLR 2025
LLMs CAN PLAN ONLY IF WE TELL THEM
Bilgehan Sel *
Department of ECE Virginia Tech Blacksburg, VA 24061, USA bsel@vt.edh
Ruoxi Jia
Ming Jin
Department of ECE
Department of ECE Virginia Tech
Virginia Tech
Blacksburg, VA 24061, USA ruoxijia@vt.edi
Blacksburg, VA 24061, USA iinmingevt. edu
ABSTRACT
Large language models (LLMs) have demonstrated significant capabilities in nat- ural language processing and reasoning, yet their effectiveness in autonomous planning has been under debate. While existing studies have utilized LLMs with external feedback mechanisms or in controlled environments for planning, these approaches often involve substantial computational and development resources due to the requirement for careful design and iterative backprompting. Moreover, even the most advanced LLMs like GPT-4 struggle to match human performance standard planning benchmarks, such as the Blocksworld, without additional support. This paper investigates whether L. can independently generate long- horizon plans that rival human baselines. Our novel enhancements to Algorithm- of- ohouhhtss (AoT), which we dub AoT+, help achieve state-of-the-ae results planning benchmarks out-competing prior methods and human baselines all au- tonomously.
INTRODUCTION
Large language models (LLMs) based on the transformer architecture (Vaswani) 2017) have emerged as a transformative force in artificial intelligence, revolutionizing natural language processing and demonstrating remarkable capabilities across diverse domains. These models, trained on vast cor- pora of text data, have shown prowess not only in language-related tasks but also in problem-solving (Huang & Chang (2022), reasoning (Brown 2020 Chowdhery et al. 20222) ) and even coding (Chen ct al. 2021; Thoppilan et al. 2022). The rapid advancements Al technology have sparked in- tense interest exploring their potential for more complex cognitive tasks, reinforcement learning
(Khattar Jin 2023] Khattar et al.
2024; Gu et al. [024] 2025 Meimand et al.] 2023), control
(Sel et al. [22]202]]]] Gunes al. 2023
Coskun al. 2022 [Sel
202 uu Abdeen
2024
2022). optimization (Jin et al.
2023
2024 Al- et al. [2233
Khattar & Jin 2024 A Tawah
& Jin 2024 Yang al. 2023). ) federated-leammet
(Khan al. 2023). cyber-security (Manzoor
et al. 2024 Roy et al. 2024a Cody et al. 2022; Huang et al. 2022; Wang et al.) 2024). including
sequential decision-mane making and planning. These efforts have yielded promising results, showcasing
the models' ability to generate solutions for wide array of challenges (Huang & Chang, [022]
Suzgun et al. 2022). However, as the complexity of tasks increases, particularly in domains requir- approaches become apparent (Yao et al. 2022 Long 2023 Valmeekam et al. 2023 Sel al. 2024a).
ing long-horizon planning and precise execution, the limitations of current
One of the primary challenges in utilizing LLMs for planning tasks is their inherent difficulty in self- verifying outputs (Stechly al. 2024 Liu et al. 2024b) Roy et al. 2024b). This limitation manifests
in various ways, from suggesting potentially illegal actions to failing to recognize whether a goal
Corresponding author

---

Published as a conference paper at ICLR 2025
LLM-Modulo
Not Valid
Verifier
Problem
Plan
Valid
Problem Instance
Candidate Plan
Plan
AoT+
Problam
Plan
Plan
Problem Instance
Figure 1: Illustration outlining differences between AoT+ and LLM-Modulo-like frameworks.
has been achieved in planning problems. Moreover, LLMs often struggle with inductive reasoning. finding it challenging to verify whether their hypotheses hold true for given cases crucial step in generalizing from simple observations to broader phenomena (Qiu al.) 2023). To address these shortcomings, researchers have increasingly turned to hybrid approaches that combine LLMs with external verification tools (Zhou al. 2022, Drozdov et al., 2022) Yao et al. 2024 inter alia).
These methods typically use LLMMs as idea generators or heuristics, with external systems providing feedback to guide the models towards more accurate and feasible solutions. While this approach has shown promise, introduces significant complexity and potential failure modes, often requiring substantial development time and resources to implement and maintain (Chu et al. 2023).
An alternative strand of research has focused improving LLMs' planning capabilities through advanced prompting techniques. Mirroring biological cognitive abilities to activate analytical System 2 instead of immediate System / (Kahneman 2011), methods such Chain-of-Thought (CoT) aimed at teaching LLMMs step-by-step reasoning, have demonstrated some success enhancing LLMs' reasoning abilities (Wei al.) [202]] Kojima et al. 2022). However, recent studies have highlighted the limitations of these approaches, particularly in more challenging planning domains. For instance, in benchmarks like Blocksworld, where human performance reaches approximately 78% accuracy, even state-of-the-as models like GPT-4 achieve only around 30% accuracy, with CoT prompting offering little to improvement. The situation even more concerning in complex planning domains such logistics, where GPT-4's success rate for generating valid plans drops to a mere 14% (Valmeekam et al., 2023). Notably, the performance of open-source L.LMs these planning tasks is even more limited, further underscoring the significant gap between current LLM capabilities and human-level planning proficiency across various domains.
These sobering results have led some researchers to conclude that current LLMs are fundamen- tally ill-suited for autonomous planning tasks, particularly those requiring long-horizon reasoning in-depth
Valmeekam et al., 2023 Stechly et al. 2024 Kambhampati et al., 2024). However, investigations suggest that this pessimism may be premature. We posit that with simple in-context examples showing the search process that also acknowledges the limitations of LLMs, is pos-
2

---

Published as a conference paper at ICLR 2025
sible to dramatically improve their autonomous planning capabilities without resorting to external verification tools which significantly increases development and computational costs.
In this paper, introduce AoT+, enhanced prompting technique that builds upon the founda- tion of the Algorithm of Thoughts (AoT) approach (Sel et al., 2024b) to activate System 3 thinking, more deliberate decision-making process one uses when facing doubt, dilemma, [Webb] (02T). Our method not only challenges the perceived limitations of LLMs in planning tasks but also demonstrates the potential surpass previous state-of-the-art results, including those achieved using external verifiers. Through extensive experimentation and analysis, we seek to an- swer two critical questions:
disruption
1. Can LLMs generate long-horizon plans that rival human performance without external tools?
2. If so, what key factors differentiate our prompting technique from other step-by-sten meth- ods like Chain-of-Thoughee
To address these questions, we first examine the limitations of existing approaches. We argue that while COT prompting has shown success in many reasoning tasks, it falls short in non-ergodic plan- ning problems where single misstep can lead to an unrecoverable state. Methods like Tree of Thoughts (ToT) (Yao et al. 2024) attempt mitigate this issue by using external systems to track the search process and guide exploration. However, the computational cost of these approaches ren- ders them impractical for problems with non-trivial depth and breadth. AoT framework (Sel al.] 2024b), which demonstrated that incorporating "human intuitions" in the search process, along with self-verification and backtracking mechanisms, could lead to significant improvements over CoT while remaining computationally efficient. However, our preliminary tests with vanilla AoT re- vealed a tendency for state hallucinations, which we hypothesize is caused by excessive "cognitive load" phenomenon where the model struggles to manage all the relevant information, leading to errors in decision-making
Motivated by recent findings on LLMs' attention mechanisms, which show tendency to focus the beginning and end of their context (Liu et al. 2024a), we introduced several key innovations in AoT+:
1. Periodic Structured State Generation: We implement mechanism for periodically regener- ating and restating the current problem state during the search process. This helps alleviate the cognitive load on the model by reducing the need to attend to the entire context history.
2. Random Trajectory Augmentation: To further simplify the prompting process and improve generalizability, we introduced random search trajectories augmented with correct steps leading to goal states. This approach allows for more efficient example generation without thought processes.
requiring
Figure[iilusternn the key components and workflow of our AoT+ method compared to traditional approaches. These innovations have led to remarkable improvements in performance across multiple challenging planning domains. In the Blocksworld benchmark, AoT+ not only surpasses previous LLM-based methods but also exceeds human performance benchmarks. Similarly, in the logistics domain, our method achieves state-of-the- of-the-art results, dramatically improving upon the performance of vanilla GPT-4. The success of AoT+ raises intriguing questions about the nature of reasoning in LLMs and the potential for unlocking more sophisticated cognitive abilities through better un- derstanding. Our work suggests that L.MMs may possess latent planning capabilities that can be activated through the right combination context, structure, and guidance.
RELATED WORK
Sequential Decision-Making with LLMs. Having been trained on a large corpus of world-wide text, LLMs excel at understanding wide range of topics that helps them coming up with possible continuations. The earliest works have observed improvements over standard prompting (Brown) 2020) for general problem solving, where directly expect the model to generate the steps after the other, by step-by-step reasoning by transforming the original problem to a sequential decision-
making one, e.g., CoT (Nye et al. 2021 Wei et al. 2022
Kojima et al. 2022 Zhang et al. 2022
3

---

Published as a conference paper at ICLR 2025
However, ToT showed the underwhelming performance in problems that are inherently sequential, such as plamning problems (Long. 2023; Yao et al. 2024). These works and their follow-ups, Lei et al. 2023); Besta et al. (2024); Chen et (2024) have relied on using LLMs mere heuristics with an external mechanism to keep track of search traces to further boost L.Mss capabilities. How- ever, due significantly increased API requests for individual search nodes, they are notoriously expensive and slow. (Sel et al. (2024b) proposed the use of pure LLM framework that requires only a single query to match or even surpass methods like ToT, using carefully curated examples woven with human-inm iommaannttutionns in their search trajectories directly in-context, that leads to drastic reductions in compute and API costs.
Verfiierificttinn. It is an intuitive and natural direction to try to utilize L.MSs to evaluate the reasonability and the correctness of their decisions. There is large literature showing that self- verification can help detect mistakes in the token generation of LLMs to correct them to improve performance on domains such as instruction-tuningg (Bai et al. (022), coding (Zelikman al. 2023
Kim et al. 2024). ethical decision- decision-making (Ma et al. 2023 Sel et al. (024a)), cuestton-ansserinng
(Madaan et al. 2024 (Shinn al. 2024 Paul al. 2024 Xie al. 2024| at 2024). However, there are also cases where LLMs perform poorly at correcting themselves, especially in symbolic
tasks /Valmeekam et al. 2023 Kamoi al. 2024 Kambhampati al. 2024).
Classical Search Algorithms. The field of classical search algorithms has a rich history in AI and planning. Dynamic Programming (Bellman 1966), laid the groundwork for solving complex problems by breaking them down into simpler subproblems. The A algorithm (Hart et al.) 1968), revolutionized pathfinding and graph traversal by combining the benefits of breadth-firg first search and best-first search. More recently, Monte Carlo Tree Search (MCTS) methods (Kocsis Szepesvári, 2006 Coulom| 2006 Gelly & Silver, 20077) Ramadan et al. 2023), exemplified by AlphaGo (Silver ct al. 2017) and AlphaZero (Schrittwieser et al., 2020), have shown remarkable success in game- playing domains, demonstrating the power of combining search with learned policies. The concept of heuristics, central to many of these algorithms, guides the search process towards promising solutions, principle we leverage in our use of LLMs heuristic generators.
3 PROMPTING METHODOLOGIES FOR PLANNING PROBLEMS
3.1 PLANNING VS. MYOPIC PROBLEMS
To understand the challenges faced by Large Language Models (LLMs) in planning tasks, it is crucial to distinguish between myopic and planning problems (Keeney 1993 Bertsekas 1995):
Myopic Problems. A myopic problem is a task that can be solved through simple reasoning and memorization, typically requiring straightforward, step-by-step approach without the need for long-term strategy or consideration of future consequences.
Planning Problems. A planning problem is task that requires the ability to formulate a sequence of actions to achieve a specific goal, often involving multiple steps, consideration of future states, and the ability to backtrack or revise the plan based on intermediate outcomes.
The key distinction lies in the cognitive processes required for each type of problem. Myopic prob- lems can often be solved using predetermined set of steps, making them amenable simple prompting techniques. Planning problems, however, demand a more sophisticated approach that incorporates: Self-doubt and verification (the ability to question and verify each step's 's validity and its contribution to the overall goal); Heuristic reasoning (the use of intuition or learned strategies to guide the exploration of more promising solution paths); Backtracking (the capability to recognize dead-ends and return to previous states to explore alternative paths); and State-tracking (maintaining an accurate representation of the current problem state throughout the solution process). These re- quirements pose significant challenges for LLMs, which are primarily trained on static text corpora and may lack explicit training in dynamic problem-solving scenarios. This discrepancy manifests in curious phenomena: LLMs can often generate code/plans to solve planning problems but struggle to execute the same logic in natural language reasoning tasks. We posit that this disconnect stems from the nature of the training data and the inherent limitations of current prompting methodologies.
4

---

Published as a conference paper at ICLR 2025
GPT-4
Claude 3.5 Sonnet
LLaMA 3.1 405B
Model Input
Model Inpul
Model Input
L..ia context examplet....
L--nn-conextt examples...
[. -.in-roneeet exumpees...
Use: 8664
Use:: 8644
Use:: 8644
Astitant: 8-6-2
6-6-2
8- 2
4-266
4-2-6
4 2-26
6
Anrwer (4 (8-
Answer (8-18-66
Answer: (1 (8- 44
User: 11 1051
User: 1255
Use
3 36611
Model Output
Ourppt
Quiput
Astistant: 11 10
Assitant:
Asustant: 11
5
3 34 (no, wait, that's not
5-1
20 4
6 6-16-12
Answer: (11) 13
Answer: (15 5) 14
Answer:
Figure 2: Observed tendency of state-of-the-ar LLMs make simple arithmetic errors when fol- lowing Chain of Thought (CoT) prompting.
3.2 THE INCOMPATIBILITY OF CHAIN-OF-THOUGHT PLANNING PROBLEMS
Thought (CoT) prompting has emerged as a popular technique for enhancing LLMs' rea- soning capabilities. However, current literature reveals fundamental incompatibilities between CoT and the requirements of planning problems:
Chain-of-Thhough
1. Linear thinking: CoT encourages linear progression of thoughts, which is often insuffi- cient for problems requiring exploration of multiple paths or backtracking (Stechly et al. 2023
Sel 2024a).
2. Lack of self-correction: The step-by-step nature of CoT does not inherently support the recognition and correction of mistakes made early in the reasoning process Yao et al., 2022
3. Overreliance on example structure: LLMs tend mimic the structure of provided ex- amples, leading to rigid thinking patterns that may not generalize well to novel problem instances Sel al. (2024b).
To illustrate these limitations, conducted experiments using the Game of 24, simple yet illus- trative planning problem with a depth of and maximum breadth of 48. Figure demonstrates how major LLMs, when presented with CoT examples, tend to produce responses that stylistically match the examples but often fail to arrive at correct solutions.
This observation underscores critical insight: the effectiveness of prompting techniques can be heavily influenced by the distribution of problem-solvine approaches in the training data. The preva- lence of step-by-step solutions in educational contexts may inadvertently bias frontier LLMMs towards CoT--like reasoning, limiting their ability to adapt to problems requiring more flexible thinking.
While traditional planning algorithms like or MCTS can cleanly separate planning from exe- cution, this separation becomes less clear when considering LLM-based planning. In real-world applications where we rely on LLMs, the action space often vast or infinite, and the execution itself may require complex natural language generation (e.g., creative writing) reasoning (e.g., crossword puzzles) that cannot easily reduced to simple programmatic execution. Even in seem- ingly straightforward domains like Blocksworld, maintaining accurate state representations during plan execution, as evidenced by the increasing rates in both CoT and vanilla AoT approaches (see Appendix A.T).
experiments reveal that LLMs struggle with
3.3 ALGORITII-
PROMPTING FOR PLANNING
The Algorithm-of Thoughts (AoT) prompting technique represents a significant advancement in addressing the limitations of CoT for planning problems. Key features of AoT include:
5

---

Published as a conference paper at ICLR 2025
verbose description of the problem- solving steps, including exploration of multiple paths.
Explicit search process: AoT incorporates
Backtracking examples: In-context examples demonstrate the process of backtracking when reaching dead-ends, teaching LLMS that direct paths solutions are not always available.
Heuristic guidance: AoT prompts include human-like intuitions to guide the search pro- cess, mimicking expert problem-solving strategies.
AoT shows marked improvements over CoT in various planning domains, including the Game of 24, crossword puzzles, and creative writing tasks. However, AoT is not without its drawbacks:
The requirement for human-lide like intuitions in the search process makes crafting effective AoT prompts time-consuming and challenging.
Complexity of prompt creation:
2. Potential for bias: The inclusion of human heuristics may inadvertently introduce biases or limit the LLM's ability to discover novel solution strategies.
3. State hallucination: While AoT reduces false positives (invalid solutions), it still struggles with accurately maintaining the problem state throughout the reasoning process.
The issue of state hallucination is particularly intriguing. Our analysis reveals that these hallucina- tions occur not just the conclusion of the reasoning process but throughout the solution attempt. This suggests that while AoT improves the overall planning capabilities of LLMs, it does not fully address the fundamental challenge of maintaining accurate internal representation of the problem state.
These findings motivate our research into more advanced prompting techniques that can better lever- age the latent capabilities of LLMs while addressing the specific challenges of planning problems. In the following sections, we introduce our novel AoT+ methodology. which builds upon the strengths of AoT while incorporating mechanisms to mitigate its weaknesses, particularly in the areas of state tracking and heuristic discovery.
4 AOT+ PROMPTING
Motivated by our new understanding of the failure modes in AoT prompting and the challenges in developing prompts that include human-lite intuition in the search process, we propose enhance- ments that drastically improve the performance of LLMs in benchmarks where they were previously shown to inadequate.
4.1
USE OF RANDOM SOLUTION TRACES DOES NOT DEGRADE PERFORMANCE
While including in-context examples showing the search process improves performance, the re- quirement for these examples to incorporate human intuition makes development more involved and potentially arbitrary. To support the notion that LLMs can plan autonomously, we tested completely random trajectories, only interwoven with the correct solution path that reaches the goal the end.
We utilize a novel approach to generate search trajectories by combining successful and unsuccess- ful solution attempts. Starting with successful trajectory that reaches the goal state and four unsuccessful ones, we first select a random number of steps from the initial solving process. We then intersperse these with random jumps between states drawn from the unsuccessful trajectories, again selecting a random number of steps at each transition. Crucially, we ensure that our in-context examples always terminate with the final successful steps that reach the goal state from the suc- cessful trajectory. This approach introduces controlled randomness while maintaining goal-directed behavior the random portions allow exploration of the search space, while consistently ending with successful goal achievement creates an implicit bias that helps guide the model toward finding valid solutions. Despite the predominantly random nature of these trajectories, our empirical results show that this method effectively engages the model in active search behavior. The randomness appears to help prevent the model from fixating on specific solution patterns while still maintaining enough structure through the guaranteed successful conclusion to guide it toward valid solutions.

---

Published as a conference paper at ICLR 2025
Contrary to expectations that this approach would significantly increase solution length and the chance hallucination, we found that random trajectories have a negligible impact on performance. Our comprchensive results across all three benchmarks originally tested in the AoT paper (which are also used in Tree of Thoughts paper) demonstrate this surprising finding.
Method CoT-SC
Game of 24
Crossword Puzzle
Creative Writing
9.0%
15.6%
6.93
ToT
69.0%
46.5%
7.56
AoT 71.0%
52.0%
7.58
AoT+R 70.0%
54.0%
7.59
Table 1: The effect of utilizing random trajectories instead of human intuition for AoT+ in various benchmarks.
Table 1 presents comparison of performance across different methods such as CoT-SC (self- consistency) (Wang et al., (022) with 10 samples, including Tree of Thoughts (ToT), original AoT, and our random trajectory version of AoT (referred to AoT+R(andom)), Notably, AoT+R achieves performance very close to that original AoT, and both surpass ToT across all bench- marks. This is particularly significant given that ToT relies external tools for state tracking and management. These results suggest that the power of the AoT approach lies not in the specific heuristics provided, but in the overall structure of the problem-solving process it encourages. By demonstrating that random trajectories can be nearly as effective as carefully crafted ones, we open the door to more flexible and generalizable prompting strategies for planning problems.
4.2 MEMOIZATION AVOIDS HALLUCINATIONS
Our analysis revealed frequent hallucinations in state representation during the AoT process. We hypothesize that these hallucinations stem from the LLM's need to continuously recompute and track the current state after each action, potentially overwhelming its computational capacity as the solution trace grows longer.
To address this issue, we draw an analogy to the concept of memoization in dynamic programming. In computer science, memoization is optimization technique that stores the results of expensive function calls and returns the cached result when the same inputs occur again. We adapt this prin- ciple to prompting strategy, periodically restating and caching the current problem state with identifiers such as "x.y.2." where z is the LLM's z-th candidate for the first decision step, and represents the y-th candidate for the second operation after æ-th candidate for the first one. through- out the solution process as shown in Figure
This approach offers several advantages over external state tracking methods used in techniques like ToT:
1. It eliminates the need for external models to interpret actions and compute states, which can be complex and error-prone.
2. It avoids the computational overhead of reprocessing the entire context when new informa- tion is added, leveraging the caching mechanisms inherent in transformer architectures.
3. It significantly reduces API costs and latency in real-world applications, as it doesn't 't re- quire stopping and restarting the generation process to inject external state information.
To validate our hypothesis and demonstrate the effectiveness of this memoization-inspe approach, we conducted experiments using -LaMAA--113--hh- offered by Meta to observe changes in attention patterns. Table [ demon- strates the more structured attention mecha- nism as a shift towards the visited states, re- sulting from our AoT+ approach with memo- ization. This structured attention suggests that the model can more easily access and utilize
Method
Blocksworld
List Functions
AoT
86.3%
78.5%
AoT+
27.0%
26.3%
Table 2: Average of the percentage of the attention over the solution steps (in opposed to the problem definition and/or initial and goal state definitions.

---

Published as a conference paper at ICLR 2025
AoT
AoT+
Model Input
Model Input
[.. I..in-contess AeI examples & system
...itecottrtt AcT' exampls & system
prompt...]
prompt...
Starting State:
Starting State:
A on on C Table, D on on Table
A on on on Table, D on E on Table
Goal State:
Goal State:
E on B, on C o
E onn B, on C
Model Output
Model Output
Unstack A from B and Stack on Unstack B from C and Pus-down B
Unstack from Stack A on B C A on on T.
1.1. Unstack B from and Put-down B: B on Con
E
Puck-up C and Stack C on B
11.1 Pick-up C and Stack C on B: C on T, on on en
Backtracking after "Stack D Unstack A from D and Put-down A Unitack from C and Put-down Unstack D from E and Stack on Pick-up Stack on
Backtracking to 1:;
1.2 Unstack A from D and Pus-down A: ez C on T, on
1.2.1 Unstack from Cand Put-down B T, Con T, A
on
1.2.1 Unstack D from E and Stack D on C: D on C on T, on T, on on 12111. Pick-up E and
C T,
on T,
Backtracking to initial state:
Backtrakkng to the initial state:
Unstack A from 8 and Pot-down Unstack E from B STATE ERROR
Unstack from Put-down
2.1 Unstack from C: on T, on T, on T, on R.on
PDDL Solution: Unstack...
Exact PDDL solution:
Unstack...
Figure 3: Comparison between AoT and AoT+ for Blocksworid benchmark. Due AoT's compu- tational overhead of reprocessing the entire context, it hallucinates state and produces an action for another state. AoT+ on the other hand, periodically restates and caches the current problem hop to any previously visited node.
relevant state information throughout the reasoning process without resulting too much state iden- tification.
The incorporation of memoization in AoT+ addresses a fundamental limitation how LLMs pro- cess long sequences of information in planning tasks. By providing periodic, easily accessible state summaries, we reduce the cognitive load on the model, allowing it to focus more on the planning process itself rather than struggling to maintain accurate representation of the problem state.
worth noting that this approach to state management in prompting shares similarities with the challenges faced in inductive reasoning tasks. Both planning and induction problems require the model to maintain and verify hypotheses over extended reasoning chains. The success of our mem- oization technique in planning tasks suggests potential applications in improving LLM performance on inductive reasoning problems as well.
5 EXPERIMENTAL RESULTS
In this section, show that simplified and enhanced prompting version is able to get state- of-the-art results in planning benchmarks, Blocksworld and Logistics, and in inductive reasoning benchmarks, List Functions and ACRE, which all known be quite challenging for LLMS Valmeekam et al, 2023,, Stechly et al., 2024 Qiu et al. 2023). We further investigate whether our setups work in wide range LLMs.
5.1 PROBLEM SETUPS
In this section, we present descriptions of the benchmarks we use, along with prompt generation methodologies for the methods tested. Our problem setups closely follow those in Valmeekam et al. (2023) for Blocksworld and Logistics, and Qiu et al. (003)) for ACRE and List Functions. For pure planning problems such Blocksworld and Logisties, utilize PDDL formalize the instances and to check the validity of the outputs. For detailed descriptions of these problem setups, we refer readers the aforementioned papers.
8

---

Published as a conference paper at ICLR 2025
Accuracy (%)
Problem
Method
Gemini 1.5
LLaMA 3.1
GPT-
GPT-4o
Claude
8B-Flash-Pro
8B-70B-405B
CoT
35
43
8-16-4
4-6-25
LLM-Modulo
82
48
19
3-4-0
0-13-34
Blocksworld
AoT
45
43
66
8-23-25
3-17-35
AoT+
82
73
82
27-39-46
5-52-77
CoT
27
6-7-16
2-7-5
LLM-Modulo
70
56
26
3-5-8
4-16-30
Logistics
AoT
41
8-11-24
5-13-32
AoT+
80
70
53
19-24-57
14-71-75
CoTT
38
34
38
18-22-32
4-18-28
LLM-Modulo
70
62
38-54-66
18-34-54
List Functions
AoT
58
62
44
28-32-54
14-36-42
AoT+
84
64
38-56-68
28-62-68
CoT
28
26
22
12-18-24
8-14-26
LLM-Modulo
50
20-34-52
10-34-46
ACRE
AoT
46
48
34
18-26-38
8-20-42
AoT+
72
70
56
30-36-58
20-42-68
Table 3: Performance of various methods on Blocksworld and Logistics environments with various L.Mss.
Blocksworid. Blocksworld a classic planning domain where the goal is to arrange a set of blocks into specified configuration. Each block be the table top of another block, and the agent can perform actions such as picking block, putting it down, or stacking it on another block. This domain tests LLM's ability reason about spatial relationships and sequential actions.
Logistics. The Logistics domain involves planning the transportation of packages between locations in different cities. It includes trucks for intra-city transport and airplanes for inter-city transport. This domain tests an LLM's ability to reason about complex multi-step plans involving multiple types of actions and objects.
The List Functions dataset Rule 2020) evaluates an LLM's ability to induce rules that transform input lists into output lists. These transformations can range from simple operations like selecting specific elements to more complex operations involving multiple steps or conditional logic.
List Functions.
ACRE. The Abstract Causal REasoning (ACRE) dataset (Zhang et al. 2021) tests an LLM's ability identify causal relationships. involves determining which objects (referred as "Blickets") can activate machine based on observed outcomes.
Prompt Generation. For all problems, we generate prompts following the principles outlined in SSel et al. (024b), with our additional modifications described in the previous section. Our prompt generation pipeline creates task-specific prompts for various methods:
CoT: We provide examples of solved problems with step-by-step reasoning.
AoT: We include examples that demonstrate backtracking and exploration of multiple lution paths.
AoT+: We incorporate periodic state regeneration along with the random trajectories.
For Blocksworld and Logistics, we convert PDDL. representations into simple natural language de- scriptions of the start and goal states. These descriptions serve as the problem instances in our prompts. For List Functions and ACRE, we use natural language to describe the input-output pairs. In all cases, our prompt generation pipeline allows for flexible creation of task-specific prompts that align with the different methodologies being evaluated, while maintaining consistency with the AoT framework and incorporating are given in Appendix B For LLM-Modulo frameworks, we use their code-base to evaluate their performance various L.IMs.
novel enhancements. All the prompts use for methods

---

Published as a conference paper at ICLR 2025
5.2 MAIN RESULTS
Our experiments demonstrate the effectiveness of the AoT+ methodology across a range of challeng- ing planning and reasoning tasks. Table 3 presents comprehensive comparison of our approach against other methods, including Chain-of-Thouught architectures. Across all benchmarts-Bloccswotte Logisties, List Functions, and ACRE-AoT+ consistently outperforms or matches the best existing methods, including those using external veri- fication tools like L.M-MMoulo. This performance is particularly noteworthy in complex planning domains such as Logistics, where AoTT+ shows substantial improvements over both CoT and LLM- Modulo approaches. It also surpasses human performance of 78% (Valmeekam et al. 2023) in the Blocksworld domain when GPT-4 or Claude is used.
Thought (CoT), LLM-Modulo, and with various LLM
The benefits of AoT+ are evident across different LLM architectures, from GPT-4 to smaller models like LLaMA and Gemini variants. This consistency suggests that method successfully leverages the inherent capabilities of LLMs, enabling more effective planning and reasoning within a single prompt framework. It is particularly noteworthy that AoT+ consistently outperforms matches LLM-Modulo across all tasks, despite not relying on external verification tools. This suggests that method successfully leverages the inherent capabilities of LLMs, enabling them plan and reason more effectively within a single prompt framework.
The gains of AoT+ are more substantial with larger models, revealing an emergent ability for plan- ning as the scale of the models increases. Notably, the open-source LLaMM 3.1 405B model demon- strates remarkably competitive results with GPT-4 when used with AoT+, level of performance fails to achieve within LLM-Modulo frameworks. This observation underscores the effectiveness of AoT+ in unlocking the latent planning capabilities of large language models. The strong perfor- mance on both planning (Blocksworld, Logistics) and inductive reasoning (List Functions, ACRE) tasks highlights the versatility of AoT+. By addressing the core challenges of state tracking and exploration in LLM reasoning, our method appears to unlock latent capabilities that are applicable across a wide range of cognitive tasks.
Blocksworld Output
Logistics
Methods
Input
Total
Input
Output
Total
CoT
583.4
67.3
650.7
891.4
313.7
1205.1
AoT 1562.9
366.6
1929.5
2655.3
1817.3
4472.6
LLM-Modulo
5956.0
496.9
6452.9
21201.1
1814.2
23015.3
AoT+ 1755.2
312.6
2067.8
2879.4
1726.7
5606.1
Table 4: Token count comparisons between LLM-Modulo and AoT+ with GPT-4.
While it might be assumed that AoT+, with its detailed reasoning traces and state-tracking, would require higher total input and output tokens compared to LLM-Modulo, Table reveals a surpris- ing contrast. In fact, AoT+ demonstrates significantly lower token usage, with alternative methods requiring more than 3 times the total tokens. This efficiency primarily due to us not employing the iterative prompting employed by other frameworks, which rapidly increases both input and out- put tokens. Moreover, these iterative API requests lead to substantially longer exccution times, with LLM-Modulo methods taking average more than 6 times longer to complete the benchmarks. Al- though this duration can be influenced by external factors such as internet latency, the magnitude of the difference suggests potential significant impacts in real-time applications, highlighting AoT+'s advantages in scenarios where responsiveness and resource optimization are crucial.
6 CONCLUSION
This paper introduces AoT+, an enhanced prompting technique that significantly improves the plan- ning and reasoning capabilities of large language models (LLMs). The key innovations of AoT+ address fundamental limitations in how LLMs process long sequences of information in planning tasks. Through comprehensive experiments across challenging benchmarks, our results consistently show that AoT+ matches or outperforms existing SOTA methods, including those using external ver- ification, across various LLM architectures. By demonstrating that L.MS can autonomously plan and reason at high levels of performance, AoT+ opens new avenues for research and applications.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported in part by the National Science Foundation under grants ECCS-233177 and IIS-2312794, the Amazon-Virgima Tech Initiative for Efficient and Robust Machine Learning, and the Commonwealth Cyber Initiative. Bilgehan Sel acknowledges support through a grant from the Amazon- Virginia Tech Initiative for Efficient and Robust Machine Learning.
REFERENCES
Ahmad Al-Tawaha and Ming Jin. Does online gradient descent (and variants) still work with biased gradient and variance? In 2024 American Control Conference (ACC), pp. 3570-3575, IEEE, 2024.
Ahmad Al-Tawaha, Harshal Kaushik, Bilgehan Sel, Ruoxi Jia, and Ming Jin. Recision-focused learning for inverse noncooperative games: Generalization bounds and convergence analysis. IFACCPPpprsOOnLiee 56(2);3366)66333 2023.
Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, et al. Constitutional ai: Harm- lessness from ai feedback. arXiv preprint arXiv:2212.08073., 2022.
Richard Bellman. Dynamic programming. science, 153(37311:34-37, 1966.
Dimitri P. Bertsekas. Dynamic Programming and Optimal Control, Two Volume Set. Athena Scien- tific, 2nd edition, 1995. ISBN 1886529116.
Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gian- inazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, et al. Graph of thoughts: Solving elaborate problems with large language models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 17682-17690, 2024.
Tom B Brown. Language models are few-shot learners. arXiv preprint arXiv:2005. 2020.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, al. Evaluating large language models trained on code. arXiv preprint trXiv:2107.03374 2021.
Sijia Chen, Baochun Li, and Di Niu. Boosting of thoughts: Trial-and-error problem solving with large language models. In The Twelfth International Conference on Learning Representations, 2024.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311 2022.
Zheng Chu, Jingchang Chen, Qiangiong Chen, Weijiang Yu, Tao He, Haotian Wang, Weihua Peng. Ming Liu, Bing Qin, and Ting Liu. A survey of chain of thought reasoning: Advances, frontiers and future. arXiv preprint arXiv:2309. 15402, 2023.
Tyler Cody, Abdul Rahman, Christopher Redino, Lanxiao Huang, Ryan Clark, Akshay Kakkar, Deepak Kushwaha, Paul Park, Peter Beling, and Edward Bowen. Discovering exfiltration paths using reinforcement learning with attack graphs. 2022 IEEE Conference on Dependable and Secure Computing (DSC), pp. 1-8. IEEE, 2022.
Umit H Coskun, Bilgehan Sel, and Brad Plaster. Magnetic field mapping of inaccessible regions using physics-informed neural networks. Scientific Reports, 12(1): 12858. 2022.
Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In International conference on computers and games, pp. 72-83. Springer, 2006.
Andrew Drozdov, Nathanael Schärli, Ekin Akyürek, Nathan Scales, Xinying Song, Xinyun Chen, Olivier Bousquet, and Denny Zhou. Compositional Semantic Parsing with Large Language Mod- els. September 2022. URL htl.hhttss.:/ppneiviieee de

---

Published as a conference paper at ICLR 2025
Sylvain Gelly and David Silver. Combining online and offline knowledge in uct. In Proceedings of the 24th international conference on Machine learning, pp. 273 273-280, 2007.
Shangding Gu, Bilgehan Sel, Yuhao Ding, Lu Wang, Qingwei Lin, Ming Jin, and Alois Knoll. Balance reward and safety optimization for safe reinforcement learning: A perspective of gradient manipulation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp- 21099-21 106, 2024.
Shangding Gu, Bilgehan Sel. Yuhao Ding, Lu Wang, Qingwei Lin, Alois Knoll, and Ming Jin. Safe and balanced: A framework for constrained multi objeti-beecttvve reinforcement learning. IEEE Transactions Pattern Analysis and Machine Intelligence, 2025.
Uygar Gunes, Artun Sel, Bilgehan Sel, and Cosku Kasnakoglu. Dynamic modeling and trajectory tracking of quadcopter via linear and backstepping controller. In AIAA SCITECH 2023 Forum, pp. 0492, 2023.
Peter E Hart, Nils J Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2):100-107, 1968.
Jianfeng He, Runing Yang, Linlin Yu, Changbin Li, Ruoxi Jia, Feng Chen, Ming Jin, and Chang- Tien Lu. Can we trust the performance evaluation of uncertainty estimation methods in text summarization? arXiv preprint arXiv:2406. 17274, 2024.
Mengkang Hu, Yao Mu, Xinmiao Yu, Mingyu Ding, Shiguang Wu, Wenqi Shao, Qiguang Chen, Bin Wang, Yu Qiao, and Ping Luo. Tree-planner: Efficient close-loop task planning with large language models. arXiv preprint arXiv:2310.08582, 2023.
Jie Huang and Kevin Chen- Chang. Towards reasoning in large language models: A survey. arXiv preprint 12. 2022.
Lanxiao Huang, Tyler Cody, Christopher Redino, Abdul Rahman, Akshay Kakkar, Deepak Kush- waha, Cheng Wang. Ryan Clark, Daniel Radke, Peter Beling, et al. Exposing surveillance detec- tion routes via reinforcement learning, attack graphs, and cyber terrain. In 2022 21 IEEE In- ternational Conference on Machine Learning and Applications (ICMLA), pp. 1350-1357. IEEE, 2022.
Ming Jin, Vanshaj Khattar, Harshal Kaushik, Bilgehan Sel, and Ruoxi Jia. On solution functions of optimization: Universal approximation and covering number bounds. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 8123-8131, 2023.
Ming Jin, Bilgehan Sel, Fnu Hardeep, and Wotao Yin. Democratizing energy management with Ilm-assisted optimization autoformalism. In 2024 IEEE International Conference on Communi- cations, Control, and Computing Technologies for Smart Grids (Smar(GridCommm) pp. 258-263. IEEE, 2024.
Daniel Kahneman. Thinking, fast and slow. macmillan, 2011.
Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Kaya Stechly, Mudit Verma, Siddhant Bhambri, Lucas Saldyt, and Anil Murthy, Llms can't plan, but can help planning in Ilm-modulo frameworks. arXiv preprint arXiv:2402.01817 2024.
Ryo Kamoi, Yusen Zhang, Nan Zhang, Jiawei Han, and Rui Zhang. When can 1lms actually correct their own mistakes? critical survey of self-correction of llms. arXiv preprint arXiv:2406.01297. 2024.
Ralph L Keeney. Decisions with multiple objectives: Preferences and value tradeoffs. Cambridge university press, 1993.
Ahmad Faraz Khan, Xinran Wang, Qi Le, Azal Ahmad Khan, Haider Ali, Jie Ding, Ali Butt, and Ali Anwar. Pi-fl: Personalized and incentivized federated learning. arXiv preprint arX1::2304.07514 2023.
12

---

Published as a conference paper at ICLR 2025
Vanshaj Khattar and Ming Jin. Winning the cityleam challenge: adaptive optimization with lutionary search under trajectory-basse guidance. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 12284,1 2023.
Vanshaj Khattar and Ming Jin. Optimization solution functions as deterministic policies for offline reinforcement learning. In 2024 American Control Conference (ACC), pp. 1263-1268. IEEE, 2024.
Vanshaj Khattar, Yuhao Ding, Bilgehan Sel, Javad Lavaei, and Ming Jin. A cmdp- within-online framework for meta-safe reinforcement learning. arXiv preprint arXiv:2405. 16601, 2024.
Geunwoo Kim, Pierre Baldi, and Stephen McAleer. Language models can solve computer tasks.
Advances in Neural Information Processing Systems, 36, 2024.
Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference on machine learning. pp. 282-293. Springer, 2006.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances neural information processing systems, 09221199-222133 2022.
Bin Lei, Chunhua Liao, Caiwen Ding, et Boosting logical reasoning in large language models through new framework: The graph of thought. arXiv preprint arXiv:2308. 08614, 2023.
Nelson Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. Lost in the middle: How language models use long contexts. Transactions of the Association for Computational Linguistics, 11:157-173, 2024a.
Zhendong Liu, Changhong Xia, Wei He, and Chongjun Wang. Trustworthiness and self-awareness in large language models: An exploration through the think-solve-verifyy framework. In Pro- ceedings of the 2024 Joint International Conference Computational Linguistics, Language Resources and Evaluation (LREC-COLING 2024), pp. 16855-16866, 2024b.
Jieyi Long. Large language model guided tree-of-thought. arXiv preprint arXiv:2305.08297 2023.
Xiao Ma, Swaroop Mishra, Ahmad Beirami, Alex Beutel, and Jilin Chen. Let's do a thought ex- periment: Using counterfactuals to improve moral reasoning. arXiv preprint arXiv:2306. 14308, 2023.
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et Self-refine: Iterative refinement with feedback Advances in Neural Information Processing Systems, 36, 2024.
Faizan Manzoor, Vanshaj Khattar, Chen-Ching Liu, and Ming Jin. Zero-day attack detection in dig- ital substations using in-context learning. In 2024 IEEE International Conference on Communi- cations, Control, and Computing Technologies for Smart Grids (SmarGridComm)) pp. 220-225. IEEE, 2024.
Mostafa Meimand, Vanshaj Khattar, Zahra Yazdani, Farrokh Jazizadeh, and Ming Jin. Tuneopt: evolutionary reinforcement learning hvac controller for energy-comtee optimization tuning. In Proceedings of the 10th ACM International Conference on Systems for Efficient Buildings, Cities, and Transportation, pp. 265-268, 2023.
Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, et al. Show your work: Scratchpads for intermediate computation with language models. arXiv preprint arXiv:21 2021.
Debjit Paul, Mete Ismayilzada, Maxime Peyrard, Beatriz Borges, Antoine Bosselut, Robert West, and Boi Faltings. Refiner: Reasoning feedback intermediate representations. In Proceedings of the 18th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1100-1126. 2024.
13

---

Published as a conference paper at ICLR 2025
Linlu Qiu, Liwei Jiang, Ximing Lu, Melanie Sclar, Valentina Pyatkin, Chandra Bhagavatula, Bailin Wang, Yoon Kim, Yeji Choi, Nouha Dziri, et al. Phenomenal yet puzzling: Testing in- ductive reasoning capabilities of language models with hypothesis refinement. arXiv preprint arXiv:2310.08559, 2023.
Mohammad S Ramadan, Ahmad Al-Tawaha, Mohamed Shouman, Ahmed Atallah, and Ming Jin. Monte carlo grid dynamic programning: Almost sure convergence and probability constraints. arXiv preprini arXiv:2303.06200 2023.
Padmaksha Roy, Ahmad Al-Tawaha, Rouxi Jia, Laura Freeman, Peter Beling, Chen-Ching Liu, Alberto Senggiovanni-vincentee Ming Jin, et al. Defense against joint poison and evasion attacks: A case study of derms. arXiv preprint arXiv:2405.02989, 2024a.
Soumyadeep Roy, Aparup Khatua, Fatemeh Ghoochani, Uwe Hadler, Wolfgang Nejdl, and Niloy Ganguly. Beyond accuracy: Investigating eroor types in gpt-4 responses to usmle questions. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 1073-1082, 2024b.
Joshua Stewart Rule. The child as hacker: building more human-like models learning. PhD thesis, Massachusetts Institute of Technology, 2020.
Julian Schritwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(7839):004-699 2020.
Artun Sel, Bilgehan Sel, Umit Coskun, and Cosku Kasnakoglu. Comparative study of ekf-based parameter estimation and a nonlinear optimization-based estimation on pmsm system identifica- tion. Energies, 14(19):6108 1008 2021a.
Artun Sel, Bilgehan Sel, and Cosku Kasnakoglu. Glsde based parameter estimation algorithm for pmsm model. Energies, 14(3):611, 2021b.
Bilgehan Sel, Priya Shanmugasundaram, Mohammad Kachuee, Kun Zhou, Ruoxi Jia, and Ming Jin. Skin-in-the-game: Decision making via multi-stakcholder alignment in llms. arXiv preprint arXiv:2405. 12933, 2024a.
Bilgehan Sel, Ahmad Tawaha, Vanshaj Khattar, Ruoxi Jía, and Ming Jin. Algorithm of thoughts: Enhancing exploration of ideas in large language models. In Forty-first International Conference on Machine Learning, 2024b.
Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. Advances Neural Information Processing Systems, 36, 2024.
David Silver. Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676)3354 359-359, 2017.
Kaya Stechly, Matthew Marquez, and Subbarao Kambhampati. Gpt-4 doesn't know it's wrong: An analysis of iterative prompting for reasoming problems. arXiv preprint arXiv:2310.12399 2023.
Kaya Stechly, Karthik Valmeekam, and Subbarao Kambhampati. On the self-verification limitations of large language models on reasoning and planning tasks. arXiv preprint arXiv:2402.08115, 2024.
Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoc V. Le, Ed H. Chi, Denny Zhou, and Jason Wei. Challenging BIG- Bench Tasks and Whether Chain-of-Thhouee Can Solve Them. October 2022. URL http: [cs].
//arxiv. weriiiorrg/aa abs/ / 210 09261 ar arXiv:2210.0922
Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam Shazeer, Apoorv Kulshreshtha, Heng- Tze Cheng, Alicia Jin, Taylor Bos, Leslie Baker, Yu Du, et al. Lamda: Language models for dialog applications. arXiv preprint arXiv:2201.0888
2022.
14

---

Published as a conference paper at ICLR 2025
Zain ul Abdeen, He Yin, Vassilis Kekatos, and Ming Jin. Learning neural networks under input- output specifications. In 2022 American Control Conference (ACC), pp. 1515-1520. IEEE, 2022.
pp.
Zain ul Abdeen, Xiangyu Zhang, Waris Gill, and Ming Jin. Enhancing distribution system re- silience: A first-order meta-rl algorithm for critical load restoration. In 2024 IEEE International Conference on Communications, Control, and Computing Technologies for Smart Grids (Smart- GridComm), pp. 129-134. IEEE, 2024.
Karthik Valmeekam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati. On the planning abilities of large language models-a critical investigation. Advances in Neural Informa- tion Processing Systems, 36:75993-76005, 2023.
Vaswani. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
Cheng Wang. Christopher Redino, Ryan Clark, Abdul Rahman, Sal Aguinaga, Sathvik Murli, Dhruv Nandakumar, Roland Rao, Lanxiao Huang, Daniel Radke, al. Leveraging reinforcement learn- ing in red teaming for advanced ransomware attack simulations. In 2024 IEEE International Conference on Cyber Security and Resilience (CSR), pp. 262 269. IEEE, 2024.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-Consistency Improves Chain of Thought Reasoning in Language Models. September 2022. URL
net forum?id
1PLINIMMrW
P.J. Webb. System 3 Thinking: How to Choose Wisely when Facing Doubt, Dilemma, Or Disruption. Intentional Training Concepts Pty Limited, 2021. ISBN 978 9781922553560, URL https://
books. google cow./bookss....lGGe....
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837, 2022.
Yuxi Xie, Kenji Kawaguchi, Yiran Zhao, James Xu Zhao, Min- Yen Kan, Junxian He, and Michael Xie. Self-evaluation guided beam search for reasoning. Advances Neural Information Process- ing Systems, 36, 2024.
Runing Yang, Ruoxi Jia, Xiangyu Zhang, and Ming Jin. Certifiably robust neural ode with learning- based barrier function. IEEE Control Systems Letters, 111634-1399, 2023.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03629, 2022.
Shunyu Yao, Dian Yu, Jeffrey Zhao Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Ad- vances in Neural Information Processing Systems, 36, 2024.
Eric Zelikman, Eliana Lorch, Lester Mackey, and Adam Tauman Kalai. Self-taught optimizer (stop): Recursively self-improving code generation. arXiv preprint arXiv:2310.02304, 2023.
Chi Zhang, Baoxiong Jia, Mark Edmonds, Song-Chus Zhu, and Yixin Zhu. Acre: Abstract causal reasoning beyond covariation. In Proceedings of the ieee/cvf conference computer vision and pattern recognition, pp. 10643-10653, 2021.
Zhuosheng Zhang, Aston Zhang, Mu Li, and Alex Smola. Automatic chain of thought prompting in large language models. In The Eleventh International Conference on Learning Representations, 2022.
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schu- urmans, Claire Cui, Olivier Bousquet, Quoe V. Le, and Ed H. Chi. Least-to-Most Prompting Enables Complex Reasoning in Large Language Models. September 2022. URL https:
// //openreview.o N127005
15

---

Published as a conference paper at ICLR 2025
A ADDITIONAL EXPERIMENTS
A.1 IMPACT OF SOLUTION DEPTH FOR AOT AND AOT+
In order provide further evidence the use memoization for reducing state errors and hal- lucinations, we conducted an experiment to analyze the error rates for states for AoT and AoT+ in the Logisties benchmark using LLaMA 3.1 70B model. This model is chosen since is rel- atively cheap to do inference on computationally while already having good performance in the benchmark with AoT+.
We chose 200 games from the Logistics benchmark where both AoT+ and AoT was providing solutions after reaching a solution depth 20 actions, whether it be correct or not. Then we sampled 20 states in each depth and checked whether the state assumed by the LLM would be reached if were to follow the actions it proposed starting from the initial state. there was a discrepancy, we that AoT+ dramatically reduces state hallucinations and emross compared to AoT, which in return helps it achieve a superior performance as shown in Table 3 across various benchmarks and LLMs.
marked it as error. In Figure
1.0
AoT
AoT+
State Error Rate
0.8
0.6
0.2
0.0
2
10 13 14
16 17
Solution Depth
Figure 4: Comparison of error rates in state estimation with respect to solution depth for AoT and AoT+ in the Logistics benchmark using LLaMA 3.1 70B model.
16

---

Published as a conference paper at ICLR 2025
A.2 IMPACT OF EACH INNOVATION A
We also provide a more complete main results together with ablation studies on the impact of each innovation of AoT+. We denoted AoT with random solution traces instead of human intuitions as AoT+R and AoT with memoization as AoT+M. As we can see in Table 5 AoT+R do have very close performance AoT, whereas AoT+M, or we can think of it AoT+ with human intuitions, getting similar performance to AoT+.
Accuracy (%)
Problem
Method
Gemini 1.5
LLaMA 3.1
GPT4
GPT-4o
Claude
8B-Flash-Pro
8B-70B-444 -40BB
CoT
35
43
8-16-4
4-6-25
Self-Refin (SF = 10)
39
43
48
12-13-4
3-8-25
Blocksworld
Tree-Planner (N 25)
44
46
11-20-31
7-16-33
I.MMMMduulo
82
48
19
3-4-0
0-13-34
AoT
66
8-23-25
3-17-35
AoT+R
44
44
67
7-22-26
4-16-35
AoT+M
84
28-39-48
6-52-80
AoT+
82
73
82
27-39-46
5-52-77
CoT
14
16
27
6-7-16
2-7-5
LLM-Modulo
70
56
26
3-5-8
4-16-30
Logisties
AoT
24
34
41
8-11-24
5-13-32
AoT+R
24
41
9-10-24
7-16-36
AoT++M
80
72
51
18-25-58
15-73-77
AoT+
53
19-24-57
14-71-75
CoT
38
34
38
18-22-32
4-18-28
LLM-Modulo
62
38-54-66
18-34-54
List Functions
AoT
58
62
44
28-32-54
14-36-42
AoT+R
56
62
46
28-30-54
12-36-42
AoT+M
84
62
42-56-66
28-62-66
AoT+
84
70
64
38-56-68
28-62-68
CoT
28
22
12-18-24
8-14-26
LLM-Modulo
52
46
50
20-34-52
10-34-46
ACRE
AoT
34
18-26-38
8-20-42
AoT+R
46
50
34
18-28-34
6-22-42
AoT+M
70
60
36-36-60
24-44-58
AoT+
72
70
56
30-36-58
20-42-68
Table 5: Performance of various methods Blocksworld, Logistics, List Functions and ACRE environments with various LLMs. SF refers to the number of iterations for self-feedback, and N refers to the number of initial samples for Tree-Planner.
A.3 MORE INFORMATION ON TOKEN EFFICIENCY
Blocksworld
Logistics Output
Methods
Input
Output
Total
Input
Total
CoT
583.4 +22.6
67.3 +25.2
650.7 +33.8
891.4 #46.6
313.7 +19.8
1205.1 +50.6
AoT
1562.9 +15.3
366.6 +88.7
1929.5-90.
2655.3 #174.3
1817.3 4263.4
4472.6 1315.8
LLM-Modulo
5956.0 +37.8
496.9 +44.4
6452.9 -5.3
21201.1
1814.2 +306.7
23015.3 4:09.6
AoT+
1755.2 +15.3
312.6 +105.8
2067.8 1106.9
2879.4 #174.3
1726.7 #208.2
5606.1 #271.5
Table Token count comparisons between LLM-MMdulo and AoT+ with GPT-4 with std also given.
A.4 ADDITIONAL BASELINE SELF- REFINEMENT
To demonstrate simple iterative methods for improving planning performance through LLM self- feedback, we evaluated Self-Refine (Madaan et al., 2024). We adhered to their original hyper- parameters (Temperature 0.7) but extended the maximum iterations from 4 to 10 to ensure fair
17

---

Published as a conference paper at ICLR 2025
comparison with other baseline, Tree-Plannee (Hu et al. 2023 which employs maximum of 10 corrections (SF = 10). All prompts for initial generation and feedback are provided in Appendix For prompt generations,
implemented 5-shot setting, and specifically for feedback, lever- aged the feedback provided to the L.M in the LLMM-oduuo framework, which offers reliable vali- dation through external validator. As shown in Table Self-Refine demonstrates only marginal improvements over the CoT baseline, a finding that aligns with the "Mathematical Reasoning" task results reported in Madaan et al. 2024)
A.5 ADDITIONAL. BASELINE TREE- PLANNER
We evaluated Tree-Plannee (Hu et al. 2023) the Blocksworld benchmark, incorporating sampling, merging, and backtracking steps for comparative analysis. is crucial to note that Tree- PeeePllaneer re- quires knowledge of action reversibility, which may be challenging infeasible in non-ergodic envi- ronments. Fortunately, Blocksworid allows straightforward action reversal (e.g.. "Pick-up" reverses "Put-down", "Unstack" reverses "Stack").. We maintained the structural hyperparameters from the original implementation, with = 25 initial samples and a maximum of 10 error corrections. For detailed information about these hyperparameters and the method, readers should consult the original paper. As demonstrated in Table Tree-Planner consistently outperforms Self-Refine and occasionally matches AoT's performance. While appears surpass LLM-Modulo, we attribute this partially to LLM-Modulo'ss o optimization for GPT-4, their primary LLM. For generation prompts, we utilized the Self-Refine Initial Generation prompt detailed in Appendix BB. The supplementary material includes implementation code for Tree-Planner in the Blocksworld environment.
18

---

Published as a conference paper at ICLR 2025
B ALL USED PROMPTS
B. SELF-REFINE BLOCKSWORLD INITIAL GENERATION
System
I am playing with a set of blocks where need to arrange the blocks into stacks. Here are the actions can do
Pick up a block
Unstack block from on top another block Put down block
Stack a block on top of another block
I have the following restrictions on my actions:
I can only pick up or unstack one block at a time.
I can only pick up unstack block if my hand is empty.
I can only pick up a block if the block is on the table and the block is clear. A block is clear if the block has other blocks top of it and if the block is not picked up. I can only unstack block from on top of another block if the block am unstacking was really top of the other block.
I can only unstack a block from on top of another block if the block I am unstacking clear. Once pick up unstack block, I am holding the block.
I can only put down block that am holding.
I can only stack block on top of another block if I am holding the block being stacked.
I can only stack block on top of another block if the block onto which am stacking the
block clear.
Once put down or stack block, my hand becomes empty.
Once you stack a block on top of second block, second block is no longer clear.
User
As initial conditions have that, Block is clear, the Block is clear, the hand empty, the Block C is top of the Block A, the Block D is top of the Block C, the Block A is on the table and the Block on the table. My goal is to have that the Block B is top of the Block C and the Block D is top of the Block A.
Assistant
[PLAN]
unstack the Block from on top of the Block D put down the Block B on the table unstack the Block from on top of the Block
stack the Block A top of the Block C pick up the Block B from the table
stack the Block B top of the Block A [PLAN END]
User
initial conditions have that, the Block A is clear, hand empty, the Block A is on top of the Block D. the Block B is top of the Block C, the Block D is top of the Block and the Block C is on the table. My goal is have that the Block A is top of the Block C.
19

---

Published as a conference paper at ICLR 2025
Assistant
[PLAN]
unstack the Block from on top of the Block put down the Block A
unstack the Block from on top of the Block B put down the Block D
unstack the Block from on top of the Block C
put down the Block B pick up the Block A
stack the Block A top of the Block C
[PLAN END]
User
As initial conditions I have that, the Block B is clear, the Block D is clear, the hand is empty, the Block C is on top the Block A, the Block D is on top of the Block C, the Block A is the table and the Block B is on the table. My goal is have that the Block B is on top of the Block and the Block on top of the Block A
Assistant
[PLAN]
unstack Block D from top of the Block put down the block D on the table unstack Block C from on top of the Block
stack the Block C on top of the Block B pick up the Block D from the table stack the Block D on top of the Block A unstack the Block from on top the Block stack the Block C on top the Block D pick up the Block B from the table stack the Block B top of the Block C
[PLAN END]
User
As imitial conditions I have that, the Block A is clear, the Block B is clear, the hand is empty, the Block A is on top of the Block C, the Block B is on top of the Block D, the Block C is the table and the Block D is on the table. My goal is have that the Block A is on top the Block C and the Block on top of the Block A.
Assistant
[PLAN]
unstack the Block from top of the Block D put down the Block B on the table unstack the Block from on top of the Block C
stack the Block A on top of the Block C pick up the Block B from the table
stack the Block B on top of the Block A [PLAN END]
20

---

Published as a conference paper at ICLR 2025
B.2 SELF-REFING BLOCKSWORLD FEEDBACK
System
I am playing with a set of blocks where need to arrange the blocks into stacks, Here are the actions can do
Pick up a block
Unstack block from on top another block Put down block
Stack a block on top of another block
I have the following restrictions on my actions:
I can only pick up or unstack one block at a time.
I can only pick up unstack block if my hand is empty.
I can only pick up a block if the block is on the table and the block is clear. A block is clear if the block has other blocks top of it and if the block is not picked up.
I can only unstack block from on top of another block if the block am unstacking was really top of the other block.
I can only unstack block from on top of another block if the block I am unstacking is clear. Once pick up or unstack a block, I am holding the block.
I can only put down a block that am holding.
I can only stack block on top of another block I am holding the block being stacked.
I can only stack block on top of another block if the block onto which I am stacking the
block clear.
Once put down or stack block, my hand becomes empty.
Once you stack a block on top of second block, the second block is no longer clear.
User
As initial conditions I have that, the Block B is clear, the hand is empty, the Block B is top of the Block C, the Block C is on top of the Block D, the Block on top of the Block A and the Block A is the table. My goal is to have that the Block A is on top the Block C and the Block on top of the Block A.
My plan is as follows:
[PLAN]
unstack the Block B from on top of the Block C put down the Block
unstack the Block C from on top of the Block D
put down the Block unstack the Block D from on top of the Block A stack the Block on top of the Block B pick up the Block A
stack the Block A on top the Block C unstack the Block D from top of the Block B
stack the Block D on top the Block A [PLAN END]
Check whether this plan valid or not:
Assistant
[CHECK]
The above plan is invalid. The following action at step 1 has an unmet precondition: unstack the Block from top of the Block C
The unmet precondition is: the Block A is clear [CHECK]
21

---

Published as a conference paper at ICLR 2025
User
As initial conditions I have that, the Block D is clear, the hand is empty, the Block A is on top of the Block the Block C is on top of the Block B, the Block on top of the Block
A and the Block B is on the table.
My goal is to have that the Block A is on top the Block D and the Block on top of the Block B.
My plan is as follows:
[PLAN]
unstack the Block from on top of the Block put down the Block D
unstack the Block from on top of the Block C put down the Block A
unstack the Block from on top of the Block B
put down the Block pick the Block D
stack the Block D on top of the Block B pick the Block A
stack the Block on top of the Block D
[PLAN END]
Check whether this plan valid or not:
Assistant
[CHECK]
The above plan is valid. [CHECK]
User
As initial conditions have that, the Block D is clear, the hand empty, the Block A is on top of the Block the Block C is top of the Block B, the Block on top of the Block A and the Block B is on the table.
My goal is have that the Block A is top of the Block B and the Block on top of the Block C.
My plan is as follows:
[PLAN]
unstack the Block from the Block A put down the Block D
unstack the Block from the Block C put down the Block A
pick up the Block D
stack the Block D on top of the Block C pick up the Block A
stack the Block A top of the Block B [PLAN END]
Check whether this plan valid or
Assistant
[CHECK]
The above plan is invalid. The following action at step 8 has unmet precondition: stack the Block A on top the Block B The unmet precondition is:
the Block B is clear [CHECK]
22

---

Published as a conference paper at ICLR 2025
User
As initial conditions have that, the Block A is clear, the hand is empty, the Block A is on top of the Block the Block B is on top of the Block C, the Block D on top of the Block
B and the Block C is on the table.
My goal is have that the Block A is on top the Block C.
My plan is as follows:
[PLAN]
unstack the Block A from on top of the Block D put down the Block unstack the Block D from top of the Block B
put down the Block unstack the Block B from top of the Block C
put down the Block pick up the Block A
stack the Block A on top of the Block C
[PLAN END]
Check whether this plan is valid or not:
Assistant
[CHECK]
The above plan is valid. [CHECK]
B.3
AoT+ BLOCKSWORLD
System
I am playing with set of blocks where need to arrange the blocks into stacks. Here the actions can do Pick up block Unstack a block from on top of another block Put down a block Stack block top of another block I have the following restrictions my actions: I can only pick up or unstack one block at a time. can only pick up unstack a block my hand is empty. can only pick up block if the block on the table and the block is clear. A block is clear if the block has other blocks on top of it and if the block not picked up. can only unstack block from on top of another block if the block am unstacking was really top of the other block. I can only unstack block from top of another block if the block am unstacking is clear. Once pick up or unstack a block I am holding the block. can only put down a block that am holding. I can only stack block on top of another block am holding the block being stacked. I can only stack a block on top of another block if the block onto which am stacking the block is clear. Once I put down or stack a block, my hand becomes empty. cannot stack a block under another block. I can only stack block top of block. Also, in the last part, do not use numbered list or something to return the actions, just return them like in the examples. Use 'The PDDL version: bla bla' return the PDDL code, and do add anything after the actions.
User
Start: D on A C on B on table. Goal: A on D on B.
Assistant
Firstly, we should satisfy D being on B without B being on A. Since B is on the table, we should remove every block top of later stack first D then A top of B.
23

---

Published as a conference paper at ICLR 2025
1. Unstack D from A.
2. Put-down D
on table, on C on on table.
3. Unstack A from C
Put-down
A on table, D on table, on B on table.
Unstack from
6. Put-down C
on table, on table, on table, D on table.
Now everything is the table and we need to simply by stack the blocks in sequence. So, first D on B, then A on D.
7. Pick-up D
8. Stack D on B
on table, on table, on table.
9. Pick-up A
10. Stack on D
The PDDL version:
(unstack A)
(put-down D)
(unstack A C)
(put-down A)
(unstack B)
(put-down C)
(pick-up D)
(stack D B)
(pick-up A)
(stack A D)
User
Start: on table, on on table, on table.
Goal: A on B on D on C.
Assistant
For the goal state, all blocks need to be stacked on top of each other with C being on the table (because there only four blocks and all four blocks are top of each other). Then in sequence, first D, then B, then needs to stacked.
1. Pick-up D
2. Stack D on C is not clear. Backtracking...
1. Unstack B from C
2. Put-down B
on table, on table, on table. D on table.
Now that all blocks are on the table, we just have to follow the initial plan of ours.
Pick-up D
4. Stack D on C
on table, on table, on on table.
5. Pick-up B
Stack B on D
A on table, B on D on C on table.
Pick-up A
8. Stack A B.
-A on B on D on C on table.
The PDDL version:
(unstack B C) (put-down B)
24

---

Published as a conference paper at ICLR 2025
(pick-up D)
(stack D (
(pick-up B)
(stack B D)
(pick-up A)
(stack A B)
User
Start: on on on table, on table.
Goal: B on D, C on A.
Assistant
clear (clear means no block in on top of it) and only needs to be put on D, and clear also. Then, C should be and it's satisfied currently. Let's start with placing B D and let's examine again then.
1. Unstack B from
2. Stack B on D
-B on on table, Cn on table.
Goal is satisfied.
The PDDL version:
(unstack B C) (stack B D)
User
Start: on table, C on A on table. Goal: B on A on D on C.
Assistant
For the goal state, all blocks need to be stacked on top of each other with C being on the table (because there are only four blocks and all four blocks are on top each other). Then in sequence, first D, then A, then B needs to be stacked. not clear, there on top of it. Backtracking...
1. Unstack from D. However,
1. Unstack C from A Put-down
B on table, C on table, A on D on table. Now that C is on the table, we can unstack A from D.
3. Unstack A from D
Put-down A
on table, on table, table, D on table.
Now that all blocks are on the table, we just have to follow the initial plan of ours.
Pick-up D
6. Stack D on C
on table, on table, on on table.
7. Pick-up A
Stack A
A on D on C on table, on table.
9. Pick-up B
10. Stack on A.
-B on on D on C on table.
The PDDL version:
(unstack C A)
(put-down C)
25

---

Published as a conference paper at ICLR 2025
(unstack A D)
(put-down A)
(pick-up D)
(stack D C)
(pick-up A)
(stack A D)
(pick-up B)
(stack B A)
User
Start: D A B on C on table.
Goal: D on B, A on C.
Assistant
D is already on B, but not clear. A is on C, but C is not clear. Let's start with making B clear.
1. Unstack from
Put-down D
- D on table, A on B on C on table.
Unstack from
4. Put-down A
on table, on C table, on table. Now, we can place D on B to make it D on B on C, which would satisfy one of the goals (D on B). on not satisfied since B is on C. Then B needs to also be unstacked.
5. Unstack B from C
6. Put-down B
on table, on table, C on table, D on table. Now that all blocks are on the table, we just have to follow the initial plan of ours.
Pick-up D
8. Stack D on B
on table, on on table, on table.
9. Pick-up A
10. Stack on C.
A on C on table, D on B on table.
The PDDL version:
(unstack D A)
(put-down D)
(unstack A B)
(put-down A)
(unstack B C)
(put-down B)
(pick-up D)
(stack D B)
(pick-up A)
(stack A C)
User
Start: D on B on C on A on table.
Goal: D on C on A on B.
26

---

Published as a conference paper at ICLR 2025
Assistant
For the goal state, all blocks need to be stacked on top of each other with B being on the table (because there are only four blocks and all four blocks are on top each other). Then in sequence, first A, then C, then D needs to be stacked.
Unstack from
2. Put-down I)
on table, on Con on table.
3. Unstack B from C
Put-down
B on table, C on A on table, D on table. Unstack from
6. Put-down C
on table, on table, C on table, D on table.
Now that all blocks are the table, we just have follow the initial plan of ours.
7. Pick-up A
Stack A o B
A on B on table, C on table, D on table.
Pick-up C
10. Stack C on A
on on on table, on table.
11. Pick-up D
12. Stack on C.
DD on C on A on B on table.
The PDDL version:
(unstack D B)
(put-down D)
(unstack B C)
(put-down B)
(unstack A)
(put-down C)
(pick-up A)
(stack A B)
(pick-up C)
(stack C A)
(pick-up D)
(stack D C)
B.4 AoT+ LOGISTICS
System
We are playing game called logistics where there are multiple cities each city having possibly multiple locations and one of them being an airport. For transit, have trucks and airplanes. Trucks can go any location inside the city, and the airplanes can go to any location as long as it's another airport. whereas the airplanes are between the cities. Our goal is given package at a specific
basically, trucks are used for inter-city transport
location, we wish to transport it to the goal location. The naming scheme for the locations Lx-y, where and y are both digits, and x designates the city the location is at, is like its index. Lx-0 are always an airport. Always give the final answer as in the examples -> 'The PDDL version: bla bla' and do not add anything after the steps.
User
Start:
Airplanes: A0 at L1-0, Al L1-0
27

---

Published as a conference paper at ICLR 2025
Trucks: TO L0-1, T1 at L1-0, T2 1.2-1 Packages: PO at L2-0, PI at L2-1, P2 at L1-1, P3 at L0-0. P4 at L2-0, P5 at L2-0
Goal: PO at L2-0, PI at L0-1, P2 LI-0, P3 L2-0, P4 at L1-0, P5 at L1-1
Assistant
There are three cities since only locations talked about are LO, L1 and L2. We have two airplanes A0 and AI, and are both LI-0. Let's first examine which packages need moved to other cities.
PO: L.2 L.2 (no)
Pl: L2 -> L0 (yes)
P2: L1 LI (no)
P3: LO -> L2 (yes)
P4: L2 > L1 (yes)
P5: L2 >> L1 (yes)
The packages PO and P2 only need to moved within the city, and P1, P3, P4 and P5 will need be transferred via planes other cities. Let's sort the within city first. PO needs to be moved from L2-0 to L2-0, so no moves are necessary there. P2 should be moved from L1-1 L1-0. The truck at C1 TI at L1-0, so it needs go LI-1 first and go to LI-0 after loading the package. Drive-truck T1 at L1-0 L1-1 C1
2. Load-truck P2 to T1 at L1-1
Drive-truck T1 at L1-1 to L1-0
4. Unload-truck P2 from T1 at L1-0
Airplanes: AO at L1-0, Al L1-0
Trucks: TO at L0-1, 1, T1 at (driven but not change) L1-0, T2 at L2-1
Packages: P1 at L.21,, P3 at LO-0, P4 at 1.2-0, P5 at 1.2-0
Now, we finished with inter-city transports. and are left with the packages P1, P3, P4 and P5. Let's transfer PI first. P1 needs to go from L2-1 to L0-1. Both locations are not need first
airports
truck carry it from L2-1 L2-0 and then airplane to take to LO-0, then finally another truck to take it from L0-0 to L0-1. The truck in L2 is T2 and it in L2-1. So we can directly load it take it L2-0. The airplanes are in L1-0, so one of them (let's ' say A0) needs to fly to L2-0. The truck in CO is TO and it is in L0-1 so it also needs to go to I.10 be loaded with
5. Load-truck P1 to T2 at 1.2-1.
Drive-truck T2 from L2-1 to L2-0 in C2
7. Unload-truck P1 from T2 at L2-0
Fly-airplane AO LI- L2-0
Load-airplane P1 to AO at L2-0
10. Fly-airplane A0 from L2-0 to L0-0
11. Unload-airplane P1 from A0 L0-0
12. Drive-truck TO from L.0-1 to L0-0 in CO
13. Load-truck P1 to TO L0-0
14. Drive-truck TO from L0-0 to L0-1 in CO
15. Unload-truck P1 from TO L0-1
Airplanes: AO at LO-0, A1 at L1-0
Trucks: TO (driven but no change) L0-1, T1 at L1-0, T2 L2-1
Packages: P3 at LO-0, P4 at L2-0, P5 at L2-0
Now, let's continue with P3. needs to go from L0-0 to L2-0.. The airplane AO is already at LO-0, so can directly load it to take it to L2-0 which is the final destination. 16. Load-airplane P3 to AO at L0-0
17. Fly-airplane AO from L0-0 to L2-00
18. Unload-airplane P3 from AO at L2-0
Airplanes: AO at L2-0, A1 L1-0
Trucks: TO at L0-1, 1, T1 at L1-0, T2 at L2-1
Packages: P4 L2-0, P5 L2-0
28

---

Published as a conference paper at ICLR 2025
Now, let's continue with P4. P4 needs go from 1.2-0 to L1-0. The airplane AO is already at L2-0, so we can directly load it to take it to LI-0 which is the final destination.
19. Load-airplane P4 to A0 L2-0
20. Fly-airplane AO from L.-00 to L1-0
21. Unload-airplane P4 from AO L1-0
Airplanes: A0 at L1-0, A1 at L1-0
Trucks: TO at L0-1, TI at L1-0, T2 L2-1
Packages: P5 at L2-0
Finally, let's move P5. P5 needs to go from L2-0 to L1-1. The airplane AO is at L1-0, so we need to fly it to L2-0 to load P5. Then, need to fly it back to L1-0 and use the truck TI to take it to L.-11. The truck in C1 is at L1-0, so can directly br used to take P5 to the final destination L.1-1.
22. Fly-airplane AO from LI-0 to L2-0
23. Load-airplane P5 to A0 L2-0
24. Fly-airplane AO from L2-0 to LI-0
25. aalpade P5 from AO L1-0
26. Load-truck P5 to T1 at L1-0
Drive-truck T1 from 1.1-0 to 1.1-1 in C1
28. Unload-truck P5 from T1 at L1-1
Airplanes: AO at LI-0, AI L1-0
Trucks: TO at L0-1, Tl at L1-1, T2 at L2-1
Packages: All packages are at their goal locations. The PDDL version: (drive-truck T1 L1-0 L1-1
(load-truck P2 T1 L1-1)
(drive-truck T1 1.1-1 L1-0 C1)
(unload-truck TI L1-0)
(load-truck P1 T2 L2-1)
(drive-truck T2 I.2-1 1.2-0 C2) (unload-truck P1 T2 L2-0)
(fly-airllane AO L1-0 L2-0)
(load-airplane PI AO L2-0)
(fly-airplane AO L2-0 LO-0)
(unload-airplame P1 AO LO-0)
(drive-truck TO LO-1 LO-0 CO)
(load-truck P1 TO L0-0)
(drive-truck TO L0-0 LO-1 CO)
(unload-truck P1 TO L0-1)
(load-airplane P3 AO LO-0)
(fyyaiiplaane AO LO-0 L2-0)
(unload-airplane P3 AO L2-0)
(load-airplane P4 AO L2-0)
(fly-airplane AO 1.2-0 L1-0)
(unload-airplane AO I.1-0)
(fly-airplane AO LI-0 L2-0)
(load-airplane P5 AO L2-0)
(fly-airplane AO L.-0 L1-0)
(unload-airplane P5 AO L1-0)
(load-truck P5 TI L1-0)
(drive-truck T1 L1-0 L1-1 CI)
(unload-truck P5 T1 LI-1)
User
Start:
Airplanes: AO at L2-0, Al L2-0
Trucks: TO at LO-0, TI at L1-0, T2 L2-0
29

---

Published as a conference paper at ICLR 2025
Packages:
PO LO-0, P1 at 1.2-0, P2 at 1.2-0, P3 at L1-2, P4 L.-00 Goal: PO at L0-0, PI at L0-0, P2 at L2-0, P3 at L2-1, P4 L2-2
Assistant
5. Load-truck P3 to T1 at L1-2
Drive-truck T1 from L1-2 to L1-0 C1
7. Unload-truck P3 from TI at L1-0
Fly-airplane AI from L2-0 to L1-0
9. Load-airplane P3 to A1 at L1-0
10. Fly-airplane A1 from L1-0 to L2-0
11. Unload-airplane P3 from A1 1.2-0
12. Load-truck P3 to T2 at 1.2-0)
13. Drive-truck T2 from 1.2-0 to 1.-1 in C2
14. Unload-truck P3 from T2 at L2-1
Airplanes: AO at L0-0, Al L2-0
Trucks: TO at LO-0, T1 at L1-0, T2 at L2-1
Packages: P4 LO-0
Finally, let's move P4. P4 needs to go from L0-0 to L2-2. The airplane AO is already LO-0, so we can directly load to take to L2-0.. Then, we need to use the truck T2 to take it from L2-0 L2-2. The truck in C2 is at L2-1, so it needs to go L2-0 to be loaded with P4 to take it to the final destination L2-2.
15. Load-airplane P4 to AO at L0-0
16. Fly-airplane AO from L0-0 to L.200
17. Unload-airplane P4 from AO L2-0
18. Drive-truck T2 from L2-1 to L2-0 in C2
19. Load-truck P4 to T2 L2-0
20. Drive-truck T2 from L2-0 to L2-2 in C2
21. Unload-truck P4 from T2 at L2-2
Airplanes: AO at L2-0, A1 at L2-0
Trucks: TO L0-0, T1 at L.100, T2 1.2-2
Packages: All packages are at their goal locations.
The PDDL version:
(load-airplane P1 AO L2-0)
(fly-airplane AO L.-0 LO-0)
(unload-airplame P1 AO LO-0)
(drive-truck T1 L.-0 L1-2 C1)
(load-truck P3 T1 L1-2)
(drive-truck T1 1.1-2 I.1-0 C1)
(unload-truck P3 TI L1-0)
(fly-airllane AI L2-0 L1-0)
(load-airplane P3 A1 L1-0)
(fly-airllane A1 L1-0 L2-0)
(unload-airplane P3 L2-0)
(load-truck P3 T2 L2-0)
(drive-truck T2 L2-0 L2-1 C2)
(unload-truck P3 T2 L2-1)
(load-airplane P4 AO LO-0)
(fly-airplane AO L0-0 L2-0)
(unload-airplane P4 AO L2-0)
(drive-truck T2 L2-1 L2-0 C2)
(load-truck P4 T2 L2-0)
(drive-truck T2 L2-0 L2-2 C2)
(unload-truck P4 T2 L2-2)
30

---

Published as a conference paper at ICLR 2025
User
Start:
Airplanes: AO L1-0
Trucks: TO at LO-0, TI at L1-1
Packages: PO L.-0,, P1 at L1-1, at 10-0, at L0-1
Goal: PO at L0-1, P1 at L0-1, P2 at L1-0, P3 L1-1
Assistant
There are two cities since only locations are talked about are L0 and L.1 We have one airplane AO, and it is in L1-0. Let's first examine which packages need to moved to other cities.
PO: LI -> LO (yes)
Pl: L1 >> LO (yes)
P2: LO >> L1 (yes)
P3: L. - L.1 (yes)
All packages need to be transferred via planes other cities. Let's transfer PO first. PO needs to from L1-0 to L0-1. The airplane AO is already at LI-0, so we can directly load take L0-0. Then, need use the truck TO take from L0-0 L0-1. The truck in CO is TO and it's at LO-0. So, the package PO can be directly loaded to TO to be taken the final destination L0-1.
1. Load-airplane PO to AO at L1-0
Fly-airplane from L1-0 L0-0
3. Unload-airplane PO from A0 at LO-0
Load-truck PO to TO at L0-0
5. Drive-truck TO from L0-0 to L0-1 in CO
Unload-truck PO from TO at L0-1
Airplanes: AO at LO-0
Trucks: TO at L0-1, T1 at L1-1
Packages: P1 L1-1, P2 L0-0, P3 L0-1
Now, let's continue with P1. Pl needs to go from L1-1 to L0-1. The truck in C1 is TI and it's L1-1 as the package, so we can directly load the package to T1. The airplane AO is at LO-0, so we need to fly it to L1-0 to load Pl. Then, we need to fly it back to L0-0 and use the truck TO take it to L.-1. The truck in CO TO and it's 1.0-1. So, needs be moved from 10-1 to L.-0 to load P1 and to be driven back to LO-1 which is the target destination for Pl.
7. Load-truck P1 Tl at L1-1
Drive-truck Tl from LI-1 to LI-0 in
9. Unload-truck P1 from T1 at L1-0
10. Fly-airplane AO from LO-0 to L1-0
11. Load-airplane P1 to A0 at L1-0
12. Fly-airplane AO from L.1-0 to L.-0
13. Unload-airplane P1 from AO L0-0
14. Drive-truck TO from L0-1 to L0-0 in CO
15. Load-truck P1 to TO L0-0
16. Drive-truck TO from L0-0 to L0-1 in CO
17. Unload-tron -trckk P1 from TO L0-1
Airplanes: AO at LO-0
Trucks: TO at L0-1, T1 at L1-0
Packages: P2 at LO-0, P3 at L0-1
Now, let's continue with P2. P2 needs to go from L0-0 to L1-0. The airplane A0 is already LO-0, so we directly load it to take it to L1-0 which is the final destination.
18. Load-airplane P2 to AO at L0-0
19. Fly-airplane AO from L0-0 to L1-0
20. Unload-airplane P2 from AO at L1-0 Airplanes: A0 at L1-0
31

---

Published as a conference paper at ICLR 2025
Trucks: TO at L0-1, T1 L.-0
Packages: P3 at L0-1
Finally, let's move P3. P3 needs to go from L0-1 L1-1. The truck in CO TO and it's in LO-1 already. So, we can directly load P3 to TO to transfer it to L0-0. The airplane AO is in L1-0, so it needs to transferred to L0-0 load P3 to transfer
L1-0. The truck in C1 is T1 and it's already in L1-0, so we can directly load P3 to it to carry it to the target destination LI-1.
21. Load-truck P3 to TO at L0-1
22. Drive-truck TO from L0-1 to L0-0 in CO
23. Unload-truck P3 from TO L0-0
24. Fly-airplane AO from L1-0 to L0-0
25. Load-airplane P3 to AO at L0-0
26. Fly-airplane AO from L0-0 to L1-0
27. Unload-airplane P3 from AO L1-0
28. Load-truck P3 to TI at L1-0
29. Drive-truck Tl from L1-0 to L1-1 in CI
30. Unload-truce P3 from T1 at L1-1
Airplanes: AO at 1.1-0
Trucks: TO at LO-0, T1 at L1-1
Packages: All packages are at their goal locations. The PDDL version: (load-airplane PO AO L1-0)
(fly-airplane AO L1-0 L0-0)
(unload-airplane PO AO LO-0)
(load-truck PO TO L0-0)
(drive-truck TO L0-0 LO-1 CO) (unload-truck PO TO L0-1)
(load-truck P1 Tl L1-1)
(drive-truck T1 L.1-1 L1-0 C1) (unload-truck P1 T1 L1-0)
(fl--airllane AO L0-0 L1-0)
(load-airplane PI AO L1-0)
(fly-airplane AO L1-0 LO-0)
(unload-airplane P1 AO LO-0)
(drive-truck TO LO-1 LO-0 CO)
(load-truck P1 TO L0-0)
(drive-truck TO L0-0 LO-1 CO)
(unload-truck P1 TO L0-1)
(load-airplane P2 AO LO-0)
(fy-airplaane AO LO-0 L1-0)
(unload-airplane P2 AO L1-0)
(load-truck P3 TO L0-1)
(drive-truck TO L.-1 L0-0 CO) (unload-truck TO L.--0)
(fly-airplane AO LI-0 LO-0)
(load-airplane P3 AO LO-0)
(fly-airplane AO LO-0 L1-0)
(unload-airplane P3 AO L1-0)
(load-truck P3 TI L1-0)
(drive-truck T1 L1-0 L1-1 CI)
(unload-truck P3 T1 L1-1)
32

---

Published as a conference paper at ICLR 2025
B.5
AoT+ ACRE
System
Here, you will be given combinations of objects and whether the system will be the "on" or "off" state. There are some set of objects that will lead to the system being in the "on" state. And if any of those objects
in the mix with the other objects, the result will
always be "on". If none of them are there, then it's in the "off" state. While solving, there will also be undetermined cases for some blocks. Here is the general idea:
any one of the blocks is "on", the output is "on" If all blocks are off, the output "off"
there is an (undetermined) block with all other "off" blocks, the output is "undetermined" be careful, sometimes there cases where undetermined blocks will on. Follow the output exactly as it is given the examples after writing "Test cases:
understand some union of the
dont want you to write it in any other way.
User
Train:
blue rubber sphere, brown rubber cylinder -> on brown rubber cylinder off blue rubber sphere -> on yellow metal sphere, green metal sphere, green rubber cylinder, cyan rubber cylinder, green rubber sphere -> on green rubber sphere, brown metal cylinder, green rubber cylinder, cyan rubber cylinder off
cyan rubber cylinder, green rubber cylinder off Test:
green rubber sphere ->?
green metal sphere ->?
brown rubber cylinder, green rubber cylinder
brown rubber cylinder, green rubber sphere
Assistant
Let's start with writing all the elements we know lead to off or on state: Off: brown rubber cylinder, green rubber sphere, brown metal cylinder, green rubber cylinder, cyan rubber cylinder On: blue rubber sphere
undetermined: yellow metal sphere, green metal sphere
Now, we focus the line:
blue rubber sphere (on), brown rubber cylinder (off) -> on: does not yield any new info Now, let's focus on the line:
yellow metal sphere (undetermined). green metal sphere (undetermined), green rubber cylinder (off), cyan rubber cylinder (off), green rubber sphere (off) on: at least one of the "yellow metal sphere" and 'green metal sphere" are on. Can be one of them or both of them. This means that if those two appear together, that case will be on. If only one of them appear with the off objects it will be undetermined. Test cases:
green rubber sphere -> off green metal sphere (undetermined) -> undetermined brown rubber cylinder (off), green rubber cylinder (off) off
brown rubber cylinder (off), green rubber sphere (off) -> off
33

---

Published as a conference paper at ICLR 2025
User
Train:
purple metal cube -> off green rubber cube -> on green rubber cube, purple metal cube -> on green metal cube, gray metal cylinder, green rubber cylinder -> off gray metal cube, gray metal cylinder, green rubber cylinder -> on cyan metal cylinder, green metal cube, gray metal cylinder -> off Test:
purple metal cube ? green rubber cube -> ?
green metal cube, gray metal cylinder, green rubber cylinder, cyan metal cylinder ->
green metal cube, gray metal cylinder, green rubber cylinder, gray metal cube ->
Assistant
Let's start with writing all the elements we know lead to the off or on state: Off: purple metal cube, green metal cube, gray metal cylinder, green rubber cylinder, cyan metal cylinder
On: green rubber cube, gray metal cube
undetermined: none
Then we already know every case.
Test cases:
purple metal cube (off) off
green rubber cube (on) -> on
green metal cube (off), gray metal cylinder (off), green rubber cylinder (off), cyan metal cylinder (off) -> off
green metal cube (off), gray metal cylinder (off), green rubber cylinder (off), gray metal
cube (on) ->
User
Train:
yellow metal cube on
yellow metal cube, green rubber sphere -> on green rubber sphere -> green metal cube -> yellow rubber sphere, green metal cube, yellow rubber cube, yellow rubber cylinder -> on blue metal cylinder, yellow rubber cube, yellow rubber cylinder off Test:
yellow rubber sphere ->
green metal cube ->
blue metal cylinder, yellow rubber cube, yellow rubber cylinder, yellow rubber sphere -> ? blue metal cylinder, yellow rubber cube, yellow rubber cylinder, yellow metal cube ->
Assistant
Let's start with writing all the elements we know lead to the off or on state: Off: green rubber sphere, blue metal cylinder, yellow rubber cube, yellow rubber cylinder On: yellow metal cube, green metal cube
undetermined: yellow rubber sphere Now, let's focus on the line: yellow rubber sphere (undetermined)) green metal cube (on), yellow rubber eube (off), yellow rubber cylinder (off) >> on: since one of them is already on, yellow rubber sphere stays undetermined Test cases:
34

---

Published as a conference paper at ICLR 2025
yellow rubber sphere (undetermined) undetermined
green metal cube (on) -> on blue metal cylinder (off), yellow rubber cube (off), yellow rubber cylinder (off), yellow rubber sphere (undetermined) -> undetermined
blue metal eylinder (off), yellow rubber cube (off), yellow rubber cylinder (off), yellow metal cube (on) -> on
B.6 AOT+ LIST FUNCTIONS
System
In the following, will have lists inputs and outputs. The task is understand the rule to from the input list to the output list. Tell the hypothesis that works for all of the input-output relations. In the end, always print out the python code in the examples, do not change the style you give the python code.
User
[3, 4,
1,
2,
0, 8,
[1]
15, 6,
8, 2, 9, 7,7,
3.
9. 1,
-.
1.
7,
8.
[9]
18. 0, 7,
88 6, 1, 9,
Assistant
First obvious thing is that although the input length varies, the output always has one element, Let's first see whether the output element included the input and whether the place it appears has some relation:
[3, 4, 1, 5, 2, 0, 8, 6, 9] -> [1] appears in the third place
05, 6, 8, 2, 9, 4, 7,
[6] appears in the third place
3, 1,
[1] appears in the third place
(, appears in the third place
29.5,7.2)=>(1]]ppaar in the third place
[6,4, 0,,,9,,, 1]-> [9] appears in the third place 0,, 4. [6] appears in the third place
68, 1, 0,
appears in the third place
Since it always appear in the third place, that's ss our hypothesis. However, there are examples as to what happens when there are less than three elements in the input. By default, let's say we will return empty list.
input list has least three elements, than the output is the third element. If it has less than three elements, than the output is an empty list. Python program:
Final hypothesis:
def transform list (input_ _itt if len (input_1ss >- 3: return [input_lst [2]]
else:
return []
35

---

Published as a conference paper at ICLR 2025
User
9. [0]
[2.5]
[4]
Assistant
The input and the output has variable length. Let's first analyze the input and output
lengths:
8 5>> 9
1->2
8
2->3
10 11
10->
3->4
0->1
In all cases, the output list is element longer than the input list. Let's where the new element added and what it is:
[7, 8, 9, 2, 6, -> [7, 3, 8, 4, 6, 4 is added the 7th place [0,->]0,4]00 is added at the 2nd place
4, 4, 6, 0, 7] 4 is added at the 7th place (8.2.5.,.333466...))))- 2. (2.5 at the 3rd place
U.8.3.5..2.9111...644111..33 3. 9, 4, 7, 6, 4] is added the 7th place 0, 3, 4, 9, 1, 8, 4] 4 added at the 7th place
(5, 4] added the 4th place
[]>> [4] 4 added at the 1st place
The added element is always
added at the 7th place the list has at least elements, otherwise it is added at the end of the list.
Final hypothesis: The output list is the input list with 4 added at the 7th place if the list has at least 7 elements, otherwise 4 is added at the end of the list. Python program:
def sransform_ice (input_ist)
if len (input_lst: return input_ [:6] [4] input_ [6:]
else:
return input_lst. + [4]
User
[42, 1,42, 18, 42, 1] [4.0]=>[4.0]
[1, 42, 42, 18, 42, 1,4
8,5, (0,,,,,, 65]
[0.0,2]=
[7, 13,,,3,11
[34, 6,,.0]
68, 1,4,
[75, 0, (45. 75. 0]
[8, 18,9, 1.9118)
36

---

Published as a conference paper at ICLR 2025
Assistant
The input and the output has variable length. Let's first analyze the input and output
lengths:
7 7
2>>2
6->6
3->3
4->4
5->5
6->6
3->3
an cases, the output list is the same length the input list. Let's whether the elements in the output list are included the input list and whether the order has changed:
[42. 42, 42, 18. 42, 1] [1, 42, 42, 18, 42, 1, 42] There is definitely many similarities between the input and the output. The input is shifted to the left by
[] [4, They are the same
7, 1. 65] The input is shifted to the left by [2,0,2] 9, 0] The input shifted the left by 2
[65, 0, 5, 7, [0, 8, 5,
13. 63, The input is shifted to the left by
[34, 68, 134. 68, 1,4, 0] They are same
0, (5,3
75, 0] The input is shifted to the left by input shifted to the left by I
[8, 81
The input is either shifted the left by some amount stays the same (or think of as shifted to the left by 0. Let's see whether there is some pattern for how much is shifted. Perhaps that shifting amount appears in the input sequence.
[42, 42, 42, 18, 42, 1|-> shifted by -> the second and the last element (7th element)
[4, shifted by 0 the second the last element
[65, 0, 8, 09, 5, 1-->> shifted by -> 6th or the last element
[9, shifted by -> third or the last element
[7,9, 13->
by 1 -> fourth or the last element [34, 68, 1,4, 1, shifted by fifth or the last element
[75, 0, 5,
shifted by 6th or the last element [8, 9, >>>>>99 8] -> shifted by -> third or the last element
The shifting amount always the last element in the input list.
Final hypothesis: The output list is the input list shifted to the left by the amount that the
last element in the input list.
Python program:
def transform list if 1en (input 1st) return []
1st):
shift_amount input_lst
return input_lst [shift_amount:] input_lst : ft_amcunt]
User
[6, 5, 11, 91, 7) [11, 42, 91]
25, 90, 93.9 90]
5.)
[55, 80,
[22,
24, 78, 39, 39,
(0,
23, 85,
[36, 63, 40, 25, 25, 43]
35, 10, 17,
17, 12, 0, 46, 6]
37

---

Published as a conference paper at ICLR 2025
Assistant
The input and the output has variable length. Let's first analyze the input and output
lengths:
7 3
6->2
7->3
5->
5
9->5
10->6
10->6
The output list is always shorter than the input list. Let's see whether the elements in the output list are included in the input list and whether the order has changed:
[6, 5, 11, 42, 91, 70, 4] -> [11, 42, 91] The output list is the input list without the first and the last two elements
[3, 91, 25, 90, 92, 0] -> [25, 90] The output list is the input list without the first and the
last two elements
[6, 74, 55, 80, 5, 60] -> [55, 80, The output list is the input list without the first two and the last two elements
[22, 21, 62, 6, 0] -> [62] The output list is the input list without the first two and the last two elements
[5, 24, 24, 78, 39, 8] - [78] The output list is the input list without the first two and the last two elements
[24, 46, 0, 31, 74, 5, 44, 80, 94] >> [0, 31, 74, 44] The output list is the input list without the first and the last two elements
[93, 23, 36, 63, 40, 25, 9, 43, 8, 53] -> [36, 63, 40, 25, 9, 43] The output list is the input list without the first two and the last two elements
[3, 35, 10, 17, 12. 0, 46, 6. 8. 7] -> [10. 17, 12, 0, 46, 6] The output list is the input list without the first two and the last two elements
The output list is always the input list without the first two and the last two elements. We should also consider what happens when the input has length less than 4. By default, let's return empty list.
Final hypothesis: The output list is the input list without the first two and the last two elements. If the input list has less than 4 elements, the output is empty list. Python program:
def trans form__ list (input_lst) if len (input_lst) 4: return
else:
return input_ 1st [2:-2]
User
[15, 2, 2, 15, 6,
15,4,2) (1,6,44 1|
[1, 1.
1.447
[18,
58,
88, 5, 8, 9, 8.
[1, 95,55,4
95]
[1, 0,3]
38

---

Published as a conference paper at ICLR 2025
Assistant
The input and the output has variable length. Let's first analyze the input and output
lengths:
10->
7->0
9->7
9->3
7->3
10->0
6->2
10->3
The output list is always shorter than the input list. Let's see whether the elements in the output list are included in the input list and whether the order has changed:
[15, 2, 2, 15. 6, 15, 4, 2] [I. 6, 4] The output list is the input list without the elements that appear more than once
[1, 1, 1. 1. I, 1] -> []
The output list the input list without the elements that appear
more than once
2, 12, 0, 1, 4, -} [12, 3, 0, 5, 1, The output list is the imput list without the elements that appear more than once
[9, 19,47, 7, 47, 25, 5, 45, 25] -> 19, 7, 45] The output list the input list without the elements that appear more than once
[0, 8, 4, 2, 8, 4, 6] -> [0, 2. 6] The output list is the imput list without the elements that appear more than
[18, 5, 5, 5, 5, 5, 18, 18, 5, 5] -> The output list is the input list without the elements that appear more than once
[8, 5, 8, 9, 8, 8] -> [5, 9] The output list is the input list without the elements that appear more than once
[1, 95, 4, 0, 54, 4, 54, 95, 95] -> [1, 0, 3] The output list is the input list without the elements that appear more than once
The output list is always the input list without the elements that appear more than once. Final hypothesis: The output list is the input list without the elements that appear more than once.
Python program:
def frrm list (input_lst) return [x for in input_lst 1st if input_ lesut_sst.oo count (x) == 1]
User
5,
6, 1,91
[0]
(6.8.9.3....7.411))))))
(3,8,2
[2, 1,0, 1,0,4,,
5, 6, 6...3.2
[4, 9, 2.
6, 6]
Assistant
First obvious thing that although the input length varies, the output always has one element. Let's first whether the output element included in the input and whether the place it appears has some relation:
5, 3, > [3] appears in the third place
[2, 0, 6, 1, 9] -> [6] appears in the third place
[8. 9, 1, 4, 2, 5, 7, 6] [0] appears in the seventh place
39

---

Published as a conference paper at ICLR 2025
16, 8, 9, 3, 8.
2] [4] appears in the seventh place
[3, 8, 2.
7
5,
[1] appears in the fourth place
1, 1.
4. 7.
[3] appears in the third place
[1,7,3,2,
6, 6.
[7] appears in the second place
2, 0]
appears in the fifth place
Since it doesn't it always appear in the same place, let's see whether the place it appears has some relation with the first element in the input list:
[2 3, 9] [3] appears in the third place -> 2
[2, 6, 1, 9] - [6] appears in the third place - 2++1
[8.9, 1, 4, 5, 0, 6] [0] appears in the seventh place 8
8,8.9.3,87,,4111
[4] appears in the seventh place -> +
1,
appears in the fourth place
2, 1, 0,,,0,4,7,811 [3] appears in the third place -> 2
[1, 2,
[7] appears in the second place 1 +
0] 3, [6] appears in the fifth place -> 4+
The output element always the element in the input list that the position of the first element plus one. However, there are no examples as to what happens when there are less elements in the input than the first element plus one. By default, let's say we will return an empty list.
Final hypothesis: the input list has more elements than the first element plus one, than the output the element at the position of the first element plus one (in python, it will directly be the element at the position the first element). it has less elements than the first element plus one, than the output is empty list.
Important reminder: since we are talking about the order, let's not forget that python indexing starts from O. Therefore, let's say 5th element should be accessed by not 5. Python program:
def transform_1 sst (input_]st]]
if 1en (input 1st) input 1st 10 return [input_ 1st input 1st [0] 11
else:
return []
User
[1, 4, 6, 7, (9,4,,7]
9. 2,
4. 6.6.
0,
[7.544]-1154]
7,9.3,8,4)
[7,
3,
[6] - 0
13,9, 1.7.5.
Assistant
The input and the output has variable length. Let's first analyze the input and output
lengths:
6 6->3
8 8->3 3
5->3
3->2
5.>3
9->3
1-x0
7
40

---

Published as a conference paper at ICLR 2025
The output list is always shorter than the input list. Let's see whether the elements in the output list are included in the input list and whether the order has changed:
[1, 9, 4, 3] [9, 4. 7] The output list the input list without the first and the last elements
2. 9, 4, 8, 5, 1> [2, 9, 6] The output list is the input list without the first and the last four elements. Or They are at the positions 2, 3, 4
[7.3, 5, 0, 2] [3, 5, OJ The output numbers the positions 2, 3,
[7.5.4] [5, 4] The output numbers at the positions 2,
[7,9,388, 8, - 8] The output numbers the positions 2, 3, 4
[7,6,3, 5, 0. 1]-> -> [6, 3, 8] The output numbers at the positions 2, 3, 4 [6]-> The output is empty, because the input only has element.
7] The output numbers at the positions 2, 4 Let's check whether the first one is also the same:
[3,9, 4,,2,,,
[1,9, 4, 6. -1 4, The output numbers the positions 2, 3, 4 So, the elements are at the positions 2, 3, 4 mostly, and once at 2, 3 (when the input only has elements) and once the output empty when the list only has single element. It appears that the output consists of starting from the second position, but including at most three elements.
Final hypothesis: The output consists of elements that start from the second position of the input list, up to three elements at most. Python program:
def transform. list (input_lst)) max vax_index min (4, len (input_lat)) if len (input_lst) >= 2: return input_lst [1 [1:max__imm index]
else: return ||
41


Reviews:
[{"review_id": "IvNdoItWAD", "reviewer": "Reviewer_NGCL", "summary": "This paper investigates whether Large Language Models (LLMs) can effectively generate long-horizon plans autonomously, without requiring external verification tools or complex frameworks. The authors introduce AoT+ (Algorithm-of-Thoughts Plus), an enhanced prompting technique that builds upon the original Algorithm of Thoughts (AoT) approach. The paper suggests that LLMs may possess latent planning capabilities that can be activated through appropriate structuring of the problem-solving process, without requiring external verification tools or complex frameworks.", "questions": "Is there any scalable way to promote AoT+?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper presents a novel perspective challenging both overly pessimistic and optimistic views of LLMs' planning capabilities.\nThe AoT+ innovations are creative combinations of existing ideas since it uses periodic state regeneration to manage attention/cognitive load.\nThere is comprehensive empirical evaluation across multiple challenging benchmarks, such as clear ablation of components through comparison of AoT vs AoT+\nThe paper has well-structured progression of ideas from problem motivation to solution.", "weaknesses": "The paper focuses heavily on successful cases but lacks systematic analysis of where AoT+ fails.\nWhile the paper compares AoT vs AoT+, it doesn't fully isolate the impact of each innovation.\nThe AoT+ assumes we have a pddl instance of the problem, so I'm not sure if this method is scalable to general domain.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cPBGT3dses", "reviewer": "Reviewer_9ec5", "summary": "This paper investigates the planning capabilities of Large Language Models (LLMs) and presents an improved prompting technique which authors refer to as AoT+ because the method has been built on a previous method referred to as AoT. While current LLMs exhibit limited efficacy in complex planning tasks that demand multi-step, long-term reasoning, traditional methods such as Chain-of-Thought (CoT) and Tree-of-Thought (ToT) prompting encounter notable challenges due to lack of integrated error correction which limits their performance in planning scenarios. Both CoT and ToT lack the flexibility to backtrack, resulting in inadequate performance on benchmarks like Blocksworld. AoT that this paper has been built on enhances planning accuracy by incorporating human-like intuition and backtracking strategies. The proposed AoT+ technique introduces periodic structured state generation, which reiterates the problem state to help LLMs concentrate on pertinent information and reduce cognitive overload, along with random trajectory augmentation that uses random solution paths interspersed with correct steps, facilitating easier prompt creation while ensuring high accuracy. The effectiveness of AoT+ is validated through various experiments demonstrating its superior performance over existing methods across various tasks, including Blocksworld and Logistics, without the need for external verification tools. By utilizing structured prompts that help LLMs in state management and heuristic search, AoT+ also decreases token usage and computational time compared to other frameworks, enhancing its practicality for real-time applications.", "questions": "- Can you provide specific examples of common failure modes for AoT+, particularly regarding state hallucinations? Are there particular problem types or scenarios where these issues are more prevalent?\n- How interpretable are the decision paths generated by AoT+? Can users trace the model’s reasoning steps and identify where an error may have occurred in the planning sequence?\n- Would incorporating intermediate reward structures within AoT+ improve long-horizon planning accuracy by incentivizing the model to reach sub-goals?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Although the work has been built on existing AoT work, it still shows several strengths including: \n- Achieving state-of-the-art performance across complex planning benchmarks without the need for external verification tools, \n- Unlike approaches like Tree-of-Thought (ToT) that require extensive API requests and computational resources, AoT+ operates efficiently within a single-prompt framework, cutting down on token usage and latency. This improvement is also observed in AoT but token counts in AoT+ is more efficient.\n- The use of random solution trajectories in AoT+ (instead of rigid, human-crafted sequences) makes it easier to generate prompts and apply the method across various planning problems.\n- By leveraging memoization-inspired techniques for periodic state regeneration, AoT+ helps to improve issues around state hallucination (errors in tracking problem states), enhancing the model’s ability to stay on track over multi-step tasks.\n- AoT+ demonstrates consistent performance improvements across various LLMs indicating its model agnostic nature.", "weaknesses": "Authors have done great work, and can potentially improve the paper more by addressing the following:\n- In terms of presentation I expect a more clear diagram explaining different stages of the proposed method. It took me some time to get a better sense of the proposed method by going through the details in methodology section. \n- While AoT+ performs well on the benchmarks reported in the paper, evaluation on real-world planning tasks like pathfinding for robotics would strengthen the work.\n- While AoT+ addresses state hallucination issues, the paper doesn’t provide a detailed error analysis of where these hallucinations occur. Identifying specific failure points would offer valuable insights for refining state-tracking strategies.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uRTpURQN4A", "reviewer": "Reviewer_XU54", "summary": "This paper explores the capabilities of LLM in autonomous planning, addressing their previous limitations when compared to human performance. Further, this paper proposes a new prompting method that enable LLMs to generate long-horizon plans autonomously.", "questions": "See Weakness for more details.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- It presents a significant advancement in the autonomous planning capabilities of LLMs, demonstrating their potential to match or exceed human performance.\n- This paper proposes a prompting strategy to generate long-horizon plans.", "weaknesses": "- First, the identification of your performance gap has already been established[1].\n- However, several key baselines are missing. Although significant research addresses planning optimization strategies, much of it does not conduct experiments in the blocksworld domain [2-4]. Furthermore, baseline [5], which even operates in blocksworld, has not been directly compared.\n- Given that your method relies on search-based techniques, it would be beneficial to include comparisons with MCTS-Decoding or A*, as these are also search-based approaches. Please explain why these specific search-based approaches were not included. \n\nIf you can reasonably resolve my issue, I will reconsider my score.\n\n[1] Stechly et al. Chain of Thoughtlessness? An Analysis of CoT in Planning\n\n[2] Madaan et al. SELF-REFINE: ITERATIVE REFINEMENT WITH SELF-FEEDBACK\n\n[3] Shinn et al. Reflexion: Language Agents with Verbal Reinforcement Learning\n\n[4] Hu et al. Tree-Planner: Efficient Close-loop Task Planning with Large Language Models\n\n[5] Hao et al. Reasoning with Language Model is Planning with World Model", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zJChnpzHqj", "reviewer": "Reviewer_MUTU", "summary": "This paper proposes AoT+, a new prompting technique based on the previous work AoT, in research of LLM's ability for planning. The authors analysed the limitations of previous work, such as CoT, ToT, AoT. And then as a pre-study, it is showed that using random solution traces will not degrade the performance in comparison to AoT.\nThe authors further hypothesised that state hallucinations are due to continuous recomputation and tracking of the current state after each action. Based on this hypothesis, the authors introduced memoization in AoT+, inspired by dynamics programming. It is further shown that the attention weighs more on non-solution steps in AoT+.\nThe results demonstrate AoT has satisfactory performance improvement against other baselines and reduces the token usage.\n\nThe proposed method is based on previous AoT together with memoization and random traces. The method is simple yet effective. The paper shows promising results and improvement in comparison with baselines.  However, The paper itself lacks explanation in implementation of the proposed method. For example, it is unknown that how the authors interweave the correct solution path with random trajectories in 4.1 or how is memoization done in 4.2. Furthermore, the experiments can be done in a more consistent setting and more human performance data should be compared to support \"out-competing human baselines\". Until these concerns are resolved, this paper should be considered for a weak reject.", "questions": "* I think there might be a grammar error with the sentence: (L339) \"Table 3 demonstrates the more structured attention mechanism as a shift towards the visited states, resulting from our AoT+ approach with memoization.\" How is \"memoization\" implemented? What is the exact prompt modification? Why is this not presented in the main paper? Why does memoization prevent state identification?\n* What does CoT-SC mean in Table 1? It is not explained in the paper.\n* In Section 4.2: What specific version of LLaMA-13B did you use?\n* For random solution trajectories, what is the percentage of solution path? \n* How do you incorporate memoization into the proposed method?\n* Readability of figure 1 and figure 4 should be improved.\n* Figure 3 should be referred as a Table.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "* The paper conducted proper experiments on attention to support the hypothesis about state hallucination. \n* The proposed method shows promising results in higher performance and lower token usages.", "weaknesses": "* This paper would benefit from examples of AoT and AoT+, similar to how it benefits from examples of CoT.\n* The observation that random in-context examples does not hurt performance is not new. For instance Min 2022 (https://arxiv.org/abs/2202.12837) presents a study of what makes ICL work. I quote from their abstract: \"randomly replacing labels in the demonstrations barely hurts performance on a range of classification and multi-choice tasks, consistently over 12 different models including GPT-3\".\n* The authors can improve the illustration of the results by showing variance, confidences interval and other related statistical metrics, for example, in Table 3.\n* The author claims that the proposed method out-competes prior methods and human baselines. However, only human performance in Logistics is compared and only AoT+ with GPT4 can slightly outperform human performance.\n* Figure 1 and Figure 4 is not informative. Furthermore, the paper itself lacks descriptions of actual details of pipeline.\n* Though experiments to verify random solution traces and memoization are conducted, it is noticed they are done in different models and/or domains. It would be more convincing for extra ablation study under same settings in Section 5.2 main results.\n* The hypothesis in Section 4.2, \"that these hallucinations stem from the LLM’s need to continuously recompute and track the current state after each action, potentially overwhelming its computational capacity as the solution trace grows longer\", though partially supported by a experiment in attention, is not fully explained or validated over the length of solution trace.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nnzYt0X2dN", "reviewer": "Reviewer_4iqA", "summary": "The paper explores various aspects of planning and problem-solving using language models, focusing on whether LLMs can independently generate long-horizon plans that rival human baselines. The authors introduce novel enhancements to the Algorithm-of-Thoughts (AoT), termed AoT+, which achieve state-of-the-art results in planning benchmarks, surpassing prior methods and human performance—all autonomously. These enhancements, including Periodic Structured State Generation and Random Trajectory Augmentation, significantly improve LLM performance, suggesting that LLMs may have latent planning capabilities that can be unlocked through the right combination of context, structure, and guidance.", "questions": "Why might using random trajectories, rather than carefully crafted ones, provide greater flexibility and generalizability as prompting strategies for planning problems? In the context of this paper, crafting examples for Blocksworld as well as other tasks appears relatively straightforward and requires minimal effort.\n\nWhat considerations should be made when representing complex states, such as those in environments like ALFWorld?\n\nHow is memoization actually incorporated in AoT+? Does it involve cache the tokens for problem definitions?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper presents a highly original approach to addressing the limitations of large language models (LLMs) in autonomous planning. It introduces the Algorithm-of-Thoughts (AoT+), an enhanced prompting technique that builds upon the Algorithm of Thoughts (AoT) approach. By activating what the authors term \"System 3 thinking,\" a more deliberate decision-making process, the paper challenges the perceived boundaries of LLMs in complex planning tasks. The use of random solution traces and memoization to improve the performance of LLMs in planning further highlights the novelty of this work.\n\nThe paper maintains a high standard of quality in terms of its depth of analysis. It conducts experiments with a diverse set of language models and various prompting strategies, resulting in a comprehensive evaluation of the proposed methods. The authors effectively communicate complex concepts through clear figures and tables, and the structure is logical and easy to follow. The paper begins by identifying the limitations of prior work, proceeds to verify the efficacy of the proposed techniques through experiments, and concludes with an extensive evaluation of its findings.\n\nBy addressing LLMs’ limitations in planning tasks and proposing novel enhancements, this paper significantly contributes to advancing the problem-solving and decision-making capabilities of language models.", "weaknesses": "AoT+ requires explicitly restating and caching the current problem state throughout the solution process, which introduces additional complexity. This can demand extra effort in crafting effective state representations, and may be particularly challenging in tasks where the state is difficult to define or capture, such as in ALFWorld.\n\nRegarding the token count comparison table, it would be more comprehensive to include other baselines, such as CoT and AoT, to provide a fuller comparison.\n\nThe paper does not specify which version of the Claude model is used in the main experiments (Claude 3.5, Sonnet?). Providing this information would enhance clarity and reproducibility.\n\nThe paper lacks details on the implementation of memoization, which makes it somewhat unclear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)