Improving Large Language Model Planning with Action Sequence Similarity
Authors: Xinran Zhao
Hanie Sedghi
Bernd Bohnet
Dale Schuurmans
Azade Nova
Venue: ICLR 2025 Poster (2025)
Keywords: planning with LLM
in-context learning (ICL)
action sequence
Primary area: foundation or frontier models, including LLMs
TL;DR: We propose GRASE-DC, an iterative exemplar re-sampling method to boost LLM planning performance using in-context learning (ICL). It achieves ~10-30 absolute points of accuracy improvement on various tasks and different LLMs.

Abstract: Planning is essential for artificial intelligence systems to look ahead and proactively determine a course of actions to reach objectives in the virtual and real world. Recent work on large language models (LLMs) sheds light on their planning capability in various tasks. However, it remains unclear what signals in the context influence the model performance. In this work, we explore how to improve the model planning capability through in-context learning (ICL), specifically, what signals can help select the exemplars. Through extensive experiments, we observe that commonly used problem similarity may result in false positives with drastically different plans, which can mislead the model. In response, we propose to sample and filter exemplars leveraging plan side action sequence similarity (AS). We propose GRASE-DC: a two-stage pipeline that first re-samples high AS exemplars and then curates the selected exemplars with dynamic clustering on AS to achieve a balance of relevance and diversity.  Our experimental result confirms that GRASE-DC achieves significant performance improvement on various planning tasks (up to ~11-40 point absolute accuracy improvement with 27.3% fewer exemplars needed on average). With GRASE-DC* + VAL, where we iteratively apply GRASE-DC with a validator, we are able to even boost the performance by 18.9% more.
Extensive analysis validates the consistent performance improvement of GRASE-DC with various backbone LLMs and on both classical planning and natural language planning benchmarks. GRASE-DC can further boost the planning accuracy by ~24 absolute points on harder problems using simpler problems as exemplars over a random baseline. This demonstrates its ability to generalize to out-of-distribution problems.

Published as a conference paper at ICLR 2025
IMPROVING LARGE LANGUAGE MODEL PLANNING WITH ACTION SEQUENCE SIMILARITY
Xinran Zhao?.2, Hanie Sedghi', Bernd Bohnet', Dale Schuurmans', Azade Nova'
Google DeepMind, *Carnegie Mellon University
ABSTRACT
Planning is essential for artificial intelligence systems to look ahead and proac- tively determine a course of actions to reach objectives in the virtual and real world. Recent work large language models (LLMs) sheds light their plan- ning capability in various tasks. However, it remains unclear what signals in the context influence the model performance. In this work, explore how to im- prove the model planning capability through in-context learning (ICI.) specifi- cally, what signals can help select the exemplars. Through extensive experiments, we observe that commonly used problem similarity may result in false positives with drastically different plans, which can mislead the model. In response, we propose to sample and filter exemplars leveraging plan side action sequence sim- ilarity (AS). We propose GRASE-DC: two-stage pipeline that first re-sapsles high AS exemplars and then curates the selected exemplars with dynamic cluster- ing on AS to achieve a balance of relevance and diversity. Our experimental re- sult confirms that GRASE-DE DC achieves significant performance improvement various planning tasks (up to - 11-0 point absolute accuracy improvement with 27.3% fewer exemplars needed average). With GRASE-DC**VAL. where we iteratively apply GRASE-DC with validator, we are able to even boost the performance by 18.9% more. Extensive analysis validates the consistent perfor- mance improvement of GRASE-DC with various backbone LLMs and on both classical planning and natural language planning benchmarks. GRASE-DC further boost the planning accuracy by -24 absolute points on harder problems using simpler problems as exemplars over a random baseline. This demonstrates its ability to generalize to out-of-distributie problems.
INTRODUCTION
Planning is important for intelligent agents when exploring the environment and conducting complex multi-hop actions to achieve their goals strategically. Classical studies planning mainly leverage search-based algorithms and reinforcement learning to tackle these problems. Recent advances in utilizing Large Language Models (LLMMs) as the backbone of agents, e.g., for games (ToT., Yao al.] 2023) and travel scheduling (Xie et al. [022), call for the need to improve model planning ability to facilitate various downstream applications.
Recent work achieves good performance LLM planning with combination of search-based al- gorithms and LLM decoding (Besta et al., 2024 Silver et al. 2024: Lehnert et al., 2024]; however, multiple rounds of prompting in a tree structure. e.g., Monte-Carke Tree Search (MCTS), can lead to high inference cost (Yao et al., 2023). To further improve the effectiveness and efficiency, this paper focuses improving the planning capability of LLMs with direct prompting in the in-context learning (ICL) (Brown et al.] (2220) manner. We aim to seek signals that help select the good demon- strative task-plan examples in the context, i.e. exemplars (Rubin et al. (022). Previous work (Ye) et al. 2023) in the natural language processing (NLP) community considers an exemplar selector as a dense retriever (Karpukhin et al. 2020) that matches the semantics of two task descriptions. However, for planning tasks, semantically similar task descriptions with one different initial state can lead to different core strategies and eventually drastically different correct plans. For example,
Work done student rescarcher Google DeepMind. Correspondance xinranz3 @ andrew.cmu.edu.

---

Published as a conference paper at ICLR 2025
Generative Re- Sampling of Action sequence Similar Exemplars (GRASE)
Dynamic Clustering
Gonorated Plans lo?)
(aC)
Stepd" Borate Step 248 (GRACE-DC))
Test Examplo
Steps: Final KGL with selected
Selecsed
Unstace b4, b5 Pickeup b5 Stzck 0.5
Exeempier Car disatte
Taak: Hnttals o4 bi.... b5 b4
Model Intial Plare lo?
Not solccted
Pickup
LLM
Exerr piee Cluster
Urstack 64, b5
2. Pirlocp hs
Tae
Taskl
Random
3. Stack
Test Examplc
THIRSH
THIRSHO
Instuali bof on bi,, bit...
Step2: Compute Action suquarice Smrlllally (A5)
Ref
Reference Plans
Gooll bi on bdl
dandidato Poot
Sempling wilh relevance
Candidate Pool
Unstactbo bd.
Step3: high Exemplars
Pideup
An illustration of our two-stage GRASE-DC pipeline. Given a test example, [GRASE stage:] we first use the random exemplars from the candidate pool to acquire the initial model plan. We then utilize actions in this plan to rank the pool with the action sequence similarity. [DC stage:] we further sample the specific exemplar pool for the test example with the relevance and diversity in the lens of clusters based on action sequence similarity. Finally, we conduct ICL, and prompt LLMs with the sampled pool and original test example. We can iteratively apply GRASE-DC, i.e., GRASE-DC*, by re-sampling exemplars with the action sequences of the generated plans.
Figure I:
requiring an end state of a block on the top or bottom of a 100-block pile will only have a one- word difference in task description: put b/ on the table vs. put b/00 on the table, but the problem complexity, as well as the desired operations in plans, is different. To avoid potential false positive exemplars, we explore the signals from the actual plans with the view of their essence: sequence of ordered and dependent actions. We validate such intuition by comparing the ICL performance on various tasks with exemplars sampled from signals in the tasks plans. We propose to consider plans as a series of ordered actions and measure the Action sequence Similarity (AS). Specifically, measure the similarity between two action sequences with their longest common action sequence (LCCA) normalized by sequence lengths. Our analytical experiments with Oracle plans of test ex- amples confirm that the proposed AS is better and more robust signal in selecting exemplars to assist the model planning, compared to random sampling or signals from task descriptions.
We propose GRASE-DC two-stage pipeline that empirically leverages AS to improve LLM plan- ning with ICL. As shown in Figure [ we first acquire the model's 's initial output plans for the test examples with randomly selected exemplars. Then, we perform the first stage. Generative Re- sampling of Action Sequence Similar Exemplars (GRASE): we utilize the model-generated plans to compute the action sequence similarity with all exemplar candidates. Last, given the set of similar exemplars sampled in GRASE, we further remove potential noise and redundancy with a Dynamic Clustering (DC) step: we capture the geometric relations among exemplar candidates plus each test example with clustering over their distance as the reciprocal of AS. We utilize these relations to keep a new dynamic set of exemplars for each individual test example with a balance between relevance and diversiry. We use this final set of exemplars, with a dynamic size for each test example, to con- struct the prompt for standard ICL to guide models to generate plans. Since GRASE-DC maintains the original ICL pipeline, with the final model-generrted plans, we can iteratively apply the GRASE and DC steps, we denote this iterative approach as GRASE-DC'.
We evaluate the performance of GRASE-DC on both classic planning benchmarks (Acronautiques let al. 1998 Höller et al.) 2020 Bohnet et al., (024) as well as natural language planning bench- marks (Zheng et al.) 2024). Through extensive experiments, we show that GRASE-DC achieves significant and robust performance improvement in planning through ICL with LLMs across tasks with a concise set of exemplars. GRASE-DO achieves up to -11-40 point absolute accuracy im- provement and 27.3% fewer exemplars needed on average, compared to random exemplar selection. GRASE-DC* with validator further achieves similar or better performance with fewer exemplars, compared to GRASE-DC, with up to 18.9% performance improvement and 39% fewer exemplars.
We further analyze the cost of selecting exemplars with our approach against random selection. We show that with parallel computation of plan similarity, the extra compute cost for selecting exemplars with AS is negligible compared to random, and GRASE only requires only one additional prompt to the LLMs, which is much less than the overhead of the search- based algorithms such as MCTS and ToT. We further investigate how to use MLP and BPE-Proxy to approximate AS at different performance-efffciene. trade-offs. We estimate the floating-poin operations per second
2

---

Published as a conference paper at ICLR 2025
(FLOPs) needed for exemplar selection and plan generation for each test example. The proposed MLP achieves 95% performance of GRASE with around 66% FLOPs; BPE-Proxy achieves 83% performance of GRASE with around 27% FLOPs, showing the effectiveness of these methods.
To assess the broader applicability of our method, we further evaluate it on different backbone LLMs well data beyond its original training distribution. We observe that GRASE consistently enhances the planning capabilities of different backbone LLMs. This means it reliably leads to better performance across range of LLMs, regardless of their design. Furthermore, GRASE-DC significantly outperform random baseline (~24 absolute points) on harder and out-of-distribution test examples using simple exemplar candidates.
2
METHODOLOGY
2.1 TASK FORMATION
In this paper, we investigate how to improve the planning capability of large language models (LLMs) through in-context learning (ICL). Given the task description of the planning problem (e.g., the initial component states and the final goal), we prompt the model with a set of exemplar candi- dates and let the model directly output the executable and verifiable plans in the response.
Formally, each planning instance, either an exemplar candidate (c) or test example (l), contains a task description and referential Oracle plan, i.e., (Ca, Gp) refers to an exemplar candidate and (la, 4p) refers to test example. Each plan Cp or Lp can be rewritten into sequence of actions A {ai, (2...... For each task, there exists validator, c.g., rule-based system VAL (Howey) ct al. 2004), to verify if each action in A is valid considering its impact on the states and if the objectives (described the object states) in task descriptions satisfied after executing plar It is common to exist multiple plans that satisfy one specific task description, which can be different in the action orders or number of steps.
In ICL setting, for each test example that contains task description la and plan 4p- we sample a set of exemplars D, = f(1,,c2- c2..) from all exemplar candidates 'D to form the prompt for model M (typically LLM) and collect the model generated plans: p' P(t,, M), where VAL can verify if p' exccutable and can satisfy t., where p' is not necessarily the same as the referential ty. For planning task, the actions in sequence are temporally dependent, where the pair-wise order matters. To compute the similarity of two action sequences A,, Ay. we propose to find the longest common action sequence Are. (ordered and consecutive) that exists in both, denoted as LCAS (A,, Aj). Action sequence similarity of a pair of plans, as a measure of plan similarity, is then defined as Sim = |LCAS(A, A2)12/((45))))))
([A) [Aş)). Next, we discuss the details of our method.
2.2 GRASE-DC: ICL WITH ACTION SEQUENCE SIMILARITY
We propose GRASE-DC two-stage pipeline that leverages Sim to help sample exemplars for conducting ICL, as shown in Figure I
(1) GRASE: Generative Re-sampling of Action Sequence Similar Exemplars: Given test example, we first randomly select a set of exemplars from the candidates to obtain an initial model goner-generated plan (p'). Next, in the first GRASE stage, rewrite p' into the corresponding action sequence A'' and rank the exemplar candidates with Sim between A' and each Ac. After this stage, we can already conduct conventional ICL with the ranking by selecting the Top-N (e.g., N=40) exemplars to include in the context for prompting the LLMs. However, Sim can further provide us with relational information among candidates, which be leveraged to further refine the exemplar candidates for each test example.
(2) DC: Dynamic Clustering: To reduce potential redundancy and noise in the candidates we con- duct dynamic clustering, with the reciprocal of Simas defining the pair-wise distance, We keep the
Planning problems are commonly written in Planning Domain Definition Language (ArDaa/Arronautiquuss
et al. 1998). which provides a standard representation that guarantees problem and solution verification with task domain description. For tasks not written in PDDL, there is commonly used rule-based verification system, e.g., check all the constraints of travel planning problem. The verification of a plan is generally considered less costly than searching for a plan.
3

---

Published as a conference paper at ICLR 2025
exemplars with the highest interval of similarity (e.g., mean plus three standard deviations) with the test example. For other examples, we cap the maximum number of exemplars per cluster to ensure diverse set of candidates and include it in the context. With DC, automatically collect different set of exemplars for each test example, which relieves the need to search for the number of exemplars, i.e., N in Top-N.
GRASE-DC maintains the original pipeline of ICL, where operations are all done on the exemplar selection, not the instruction the output, which makes the pipeline flexible and easy to iterate over. We can either iterate the GRASE step before conducting DC, or iterate GRASE and DC steps together. We denote these iterative versions GRASE* and GRASE-DC* respectively.
Next, we discuss the GRASE and DC steps in more detail. For clarity, common abbreviated terms along with explanations are gathered in Table 3 in Appendix A2.
2.2.1 GRASE: GENERATIVE RE-SAMPLING OF ACTION SEQUENCE SIMILAR EXEMPLARS
Exemplar selection (Rubin et al. 2022 Zhang et al. 2022 Ye al. 2023) has been shown boost ICL performance by leveraging woblemmlevee similarity (e.g., similarity in task description). In this section, we aim build an exemplar scoring method for LLM planning. Specifically, given a set of candidate exemplars DD and a test example description td. the method scores and ranks each entry in DD to decide the corresponding Dr that then forms the prompt.
Beyond problem-level similarity, we identify that the underlying plan similarity reveals the actual similarity or the potential mutual referencing ability of two planning tasks since (1) objects in plan- ning tasks can be renamed; (2) complex tasks can be composed of multiple threads of simple tasks, e.g., reverse the order of a three-block pile. Two similar-sized problems can share similar task de- scriptions but require completely different threads. We present qualitative example comparing what exemplars will be selected via high task or plan similarity in Appendix AA
As result, we treat Sim as the way to score the exemplars. In an analytical case, we propose to use the Oracle plans for the test example (tp) to compute the score to validate if it acts as a good signal for exemplars. We denote this analytical method as Baseline Besides acting concept. modeling planning performance with Baseline AS can also be used to detect the quality of certain exemplar pool, which helps to decide if extra candidates are needed.
proof of
To empirically leverage Sim instead of Oracle plan fp. we let the model generate p' (i.e., A') by itself to compute the Sim The method to generate p' can be arbitrary. In our experiments, we first use randomly sampled exemplars to let the model generate plans in an ICL manner. Besides start- ing with random sampling, GRASE can cooperate with any strategies that output model-generated plans, e.g.. ICL with problem-lewe similarity or Chain-of Chain-of-Thought prompting (Wei et al. 2022). In this direction, we extend our experiment with the model model-generated plans from both GRASE (Ap- pendix A.5) alone and GRACE-De (Section 3.2). i.e., an iterative approach of our strategy.
As described in (Kambhampati et al.) 2024). ) we can obtain hard critiques (if the current plan is executable or correct) from VAL outputs for PDDL planning problems to assist LLMs. Before re- sampling, we can also apply VAL and only conduct GRASE on the test examples where models generate the wrong plans initially, as classical rejection sampling (RS) pipeline. We denote this variant as GRASE+VAL and GRASE-DC+VAL for our pipeline at different steps. We show the performance gain from RS with either GRASE and random sampling in A.8 Note that the action sequence is not an equivalent representation of the original plans since the objects are ignored. We explore other design choices for plan representation in Section A.7
2.2.2 DC: DYNAMIC CLUSTERING WITH ACTION SEQUENCE SIMILARITY
One critical component that contributes to the success of ICL is the choice of exemplar candidates. In the previous section, we discuss the ranking of the candidates. this section, we further discuss the curation of the candidate pool for noise removal.
In a realistic scenario, the exemplar candidates are either from previous interaction records of the environment, e.g., in Web Arena (Zhou et al.] 2023), automatic environment exploration, e.g., in BAGEL (Murty et al. 2024). However, since the test examples are unknown when collecting the ex- emplar candidates, there could be noise introduced to the context when simply selecting the Top-N
4

---

Published as a conference paper at ICLR 2025
in the exemplar ranks. Specifically, we identify two kinds of noise: (1) duplicating unnecessary examples; and (2) unnecessary or redundant actions in a good example, with potential complemen- tary actions from other examples. The existence of these kinds of noise suggests the importance of keeping a set of exemplars considering both the relevance and diversity, with similar findings in Auto-Co'T (Zhang al. 2023). We denote the whole strategy Dynamic Clustering (DC):
The goal of this step is to remove less relevant exemplars for each test example, since for different test examples, there is no guarantee of fixed number of good exemplars in the pool. We leverage Simas between generated plans and each exemplar candidate plan to sample dynamic number of candidates for each test example. That is, we compute the mean plus one standard deviation for all Simas scores among the candidates and discard any candidate that scores below this threshold. We then use the remaining candidates to build the clusters.
Relevance:
Upon acquiring the first rough candidate set with good relevance, the second step aims at sampling a diverse set of exemplars with removed duplication. We leverage the Simas between each pair of these candidates to conduct Agglomerative Hierarchical Clustering (Müllner 2011] to capture the internal relations among candidates. Before clustering, to ensure that highly relevant exemplars are not discarded, similar to the relevance step, we keep all candidates with scores above mean plus standard deviation. In practice, we select X to be 3.
Diversity:
We control the number of clusters with hyperparameter No With the clusters, we can sample a diverse set of exemplars to perform ICL by ensuring that there are fewer than three examples selected per cluster. Nº is considered control balance between relevance (large No) and diversity (small No). In Section 3.2] we show robust performance with different values of No. which helps alleviate the cost of deciding the hyperparameter.
3 EXPERIMENTS AND ANALYSIS
3.1 EXPERIMENTAL SETUP
Dataset and LLM Backbone. Similar to existing work (Valmeekam et al.] 2023a Bohnet et al., 2024], we conduct our main experiments on data collected by or created from the pipeline of (Aero-) nautiques et al.) 1998 Höller et al. 2020). Specifically, we conduct experiments on four PDDL tasks: Blocks World, Minigrid, Logistics, and Tetris, with details Appendix A.T For natural lan- guage planning.
Trip Planning (Zheng et al. 2024). We use 300 test examples for each task and the originally provided training set as our exemplar candidates. For each test example, there is Oracle test plan given, which is valid plan and satisfies the goal in the task description, but it is not necessarily the only viable plan. If the use of backbone L.MM is not specified, we use Gemini 1.5 Pro (Gemini Team et al. 2024) as the default generate plans at test time. We also experiment with other commercial and open-source LLMs, including GPT-4-Turbo (Achiam Øt al. 2023), Claude-3.0-O8 3.0--uus (Anthropic 2024), and LLama 3.1 (Dubey et 2024 with different parameter sizes (results are in Section 3.3
conduct experiments
Baseline and Metric. For baselines, we use Random to denote the commonly used random sam- pling (Valmeekam et al. 2023a Bohnet et al. 2024). To validate our intuition on the effectiveness of AS in Section 2.2.1] also task description similarity as a baseline. Given the task descrip- tion of a test example (1,)) and an exemplar candidate (Cz). we compute the similarity as the token overlap with QA-F1, following (Khashabi al. [0200] Zhhao al.] 2023). We denote this method as Task. For the metric, similar to (Valmeekam et al. [2023a] Bohnet et al. 2024). we use planning accuracy, which denotes the portion of test examples with generated plans that are both executable at each step (no undefined behavior or failed pre-condition) and satisfy the final goals.
3.2 PERFORMANCE ON PDDL TASKS
What signal helps ICL for planning? We first validate our intuition in Section 2.2.1 by com- paring the ICL performance between sampling exemplars with signals from the task description
Empiriaally, with n exemplar candidates to be clustered, we set the number of clusters to be 0.25 NN, when there are more clusters considered, typically more exemplars included in the context for ICI.
5

---

Published as a conference paper at ICLR 2025
Panning ewwer
PD0L Panniing Whignd
PSD. Planning
POOL Hennin log stice
Sandin
Anndin
bxdk
Enne Daca reprovent 22%
Number Exemplas logg scale)
Number of Exemplars (log-stale)
Number of Exemplars (logscaaee)
Number of Exemplars (log-ccate)
Figure 2: PDDL Planning on various tasks with Gemini 1.5 Pro. Baseline denotes ranking exem- plars with the plan similarity given Oracle test plans. Task denotes the baseline that calculates the similarity between each test example and exemplar candidate with token overlap in descriptions.
PDOL Plnning: Biockewertd
PDOL Planning Mirigdd
PDOL Planeing: Terris
POOL Planning Logieties
Bars ripesser
EnerBara
Number Exemplars llgg scale)
Number of Exemplars (leg scale)
Number oxempplass (og scale)
Number Exemptors (oog scale)
Figure 3: PDDL planning accuracy on various tasks with Gemini 1.5 Pro. Baseline AS (AS lines) denotes the use of Oracle test plans. Baseline and Random lines are the anchors across rows (the second row focuses on exemplars from 4 to 40). GRASE denotes the use of model output plans from random exemplars. VAL denotes the use of the plan validator. GRASE-DC" denotes another iteration with the model outputs from GRASE-DC. Numbers of exemplars for GRASE-DC and its iteration denote the average number of exemplars used over the whole test set with N, 1.2.3.
(Task) and plans (Baseline where both methods are based on token matching, with contextu- alized embedding involved. The comparison is shown in Figure we can observe that the proposed Baseline As presents strong and robust signal on selecting the exemplars, which achieves signifi- cant improvement in ICL performance with Gemini in all domains, compared to Random and Task. It observed that the performance of Task over different datasets not consistent. Specifically, while in Blocksworld and Minigrid, signals from the task descriptions (Task) are misleading and lead to an accuracy even worse than Random, it performs almost similarly to Random in Tetris On the other hand, in Logistics, Task achieves similar performance as Baseline The reason can be that the action types are much attached the objects, e.g., between an airplane and airports, there is only one kind of action defined: flying airplane. Examples with similar object sets, which can be captured by task descriptions, will lead to similar action sequences.
Main results on PDDL planning tasks. After validating the performance of Baseline we then evaluate the performance of our proposed GRASE-DC on PDDL tasks. Figure the trend of performance change with line charts over varied numbers of exemplars. For the detailed scores, we also present the performance in tables in Appendix A.II We also explore other empirical methods
built upon Baseline AS in Section 3.6.
As shown in Figure 3 (upper row), with GRASE, observe significant and consistent performance improvement against Random. GRASE achieves 15 absolute planning accuracy points improvement (43 to 58) on Blocksworld, as well as other tasks: 6.3 Minigrid (58 to 64.3); 10.3 Tetris (5.7 to 16); 5.3 on Logistics (20.7 to 26). If the plan validator is provided GGRASE+VAL. and the re-sampling is only done on failed examples, we can observe extra -3-5 accuracy points gain.
Since the generated plans themselves can be wrong, GRASE can suffer from diminishing perfor- mance gain with additional exemplars. However, our surprise, when the number of exemplars

---

Published as a conference paper at ICLR 2025
LLM: GPT:6-Turto
ULM: Opus
LLM: Lams3.1-708
ULM: Lhma3.3-4258
lender
Number of esemplars (logorale)
Number of esemplars Oog-scale)
Numbeer of eooeplers (logsstak)
Number of esemplats (kogerale)
Figure 4: PDDL Planning on Blocksworld with various LLMs with different numbers of exemplars. All models are using the same set of exemplars for Random. Opus denotes Claude-3.0- Ouupp...
small (e.g., 1 and 4 for Blocksworld), GRASE perform better than Baseline AS- One poten- tial reason is that Gemini can generate plans toward a correct preferred direction even with random exemplars. However, minor mistakes make the whole plan invalid GRASE helps Gemini trieve and learn from the exemplars from preferred directions, thus the minor mistakes are addressed. Baseline AS. the other hand, helps sample exemplars with the Oracle test plans, which can devi- ate from the preferred directions, e.g., in action priority. We also observe consistent performance improvement over AS through iterating only over GRASE Appendix [A.5
Next, in Figure 3 (lower row), we observe that GRASE-DC, with N. = 1, 2, 3, achieves improved performance compared to the baselines. In the first iteration (solid line). GRASE-DC achieves -1 1-0 point absolute planning accuracy improvement over Random. Similarly, VAL brings extra performance gain, with consistently improved performance over the analytical Baseline After one iteration (dashed line), GRASE-DC" either with without VAL, helps achieve higher perfor- mance with few exemplars (pushing the curve to the upper left), which further improves the overall effectiveness and efficiency of the pipeline at inference. We also show the original performance without zoom-in (i.c., not focusing on exemplars from 4 to 40) in Figure 8 in the appendix.
3.3 PERFORMANCE WITH OTHER LLMS
We further examine whether the observed performance improvements of our proposed methods translate to L.MMs other than Gemini 1.5 Pro. We test the performance of GRASE on both commer- cial and open-source LLMs, including GPT-4-Turbo (Achiam et al. 2023 Claude-3.0-Opus (An-) thropic 2024). and LLama 3.1 (Dubey et al. 2024) with different parameter sizes. For GPT-4 and Claude, we use their official API service For Llama 3.1, we use the instruct-turbo version provided by Together AI (Together AI Team 2024 More details are in Section A.2
As shown Figure 4 we observe that GRASE generally helps the models achieve improved per- formance on PDDL planning over the random exemplar selection (Random). With GRASE, models also show improved performance with the increasing number of exemplars, while the improvement can be unstable with random selection. On the other hand, we observe that, with the help of GRASE, open-source Llama-3. 1-7BB can achieve similar performance to GPT-4-Turbo with ran- dom exemplar selection, which further signifies the usability of GRASE in general application.
3.4 PERFORMANCE ON NATURAL LANGUAGE TRIP PLANNING
In the previous sections, we show the significant performance of GRASE-DC on PDDL tasks. We further experiment Natural Plan (Zheng al. 2024), where problems, plans, and actions are written in natural language. We use the Trip Planning dataset, where the actions are flights between two cities, which are eventually linked given travel and visit time frame. We use the rule-based validator from the original work to parse and evaluate the correctness of the output plans
full plan to help the travelers cover each city within the
Thhe that minor emrrr can lead total failure adds the complexity of planning tasks. For example, Blooksworld, the model forget to put down block in hand and continue operate. Exemplars help remind models to keep hands empty before conducting the next action. "Trip Planning has natural definition of actions. We apply AS on Calendar Planning with extended definition of actions Appendix A.6
7

---

Published as a conference paper at ICLR 2025
Natural Planning: Trip
Natural Planning: Trip (Best Performing)
220
Planning Acc (%)
50
GRASE
Plan Accuracy (95)
TAT
Taak
66.
10
31.7
25.0
24.2
Erer BaS represent 10%
62
16
en
Number of Exemplars (log scale)
Number of Cities
Figure 5: Natural language planning performance on Trip Planning with Gemini 1.5 Pro. (left) ICL performance with different numbers of exemplars and signals for exemplars sampling. Baseline AS (denoted as AS in the figure) denotes the use of Oracle test plans. (right) ICL performance with different problem complexity (denoted by number of cities). Best Performing denotes the use of 40 and 100 exemplars for Random and GRASE, respectively.
PDOL Blockswordd OOD
PDDL: Blockswortd (Best Performing)
GRA81-DC
Konden
DRADE
OOD
Nirder
Planning Acc (%6
20
Plan Accur Accuracy (%)
8L2
77.
GIAEE OC
40-
50
26.1
K5.
114
62.9
47%4
[40.5
26.2
43.5
26-
25 25
21,0
Bart Ipprssent
3.7
102
Number of Exemplars (log-scale)
Number of Blocks
Figure 6: (left) PDDL planning performance on Blocksworld -ODD setting Unlike Figure 3 (with 3-7 blocks in each example), we test on problems containing 8-20 blocks. Baseline denotes the use of Oracle test plans. Numbers of exemplars for GRASE-DC denote the average number of exemplars used over the whole test set with No = 2, 3; (right) ICL performance with different numbers of blocks. Best Performing denotes 4 and 13.9 (on average) exemplars for Random and GRASE-DC, respectively. Since all the exemplar candidates are with 3-7 blocks, we denote test examples with 3-7 blocks as in-distribution (ID) and 8-20 blocks as out-of-distributton (OOD).
As shown in Figure 5 (left), we observe that both Baseline and GRASE achieve better perfor- mance compared to the random baseline, while sampling exemplars with problem/task similarity do not show significant improvement. Similar to PDDL. tasks, using model-generated initial plans to conduct GRASE achieves better results than Baseline One reason Oracle plans may not always align with the model preference, e.g., on which cities to start, which brings extra noise. Figure 5 (right) further validates the source of the gain. It depicts a detailed view of the best- pest-performing entries on Figure 5 (left) across different problem complexity (# of cities), noting that the gain from GRASE is across the problems with different # of cities. The improvement is prominent in harder planning problems including more cities.
be that the reference
3.5 ANALYSIS: OUT-OF-DISTRIBUTTI GENERALIZATION
Motivated by (Bohnet et al.] 2024). we note one crucial factor that decides the hardness of the planning problems: the size the object set. The bigger the size, the harder the planning problem. For Blocksworid, the size denotes the number of the blocks in the problem, i.e. how many blocks are on the table, where some of them are required to rearranged to reach the goal state. Here, we investigate how our proposed method performs in settings where the size of each test example is different from all the exemplar candidates. This essentially captures the -iit--i--tttittiiionn (OOD) scenario. For the OOD setting, we use exemplar candidates with size 3-7 to solve test examples with size 8-20. From Figure 6 (left), we observe that similar to our findings in Section 3.2 AS achieves significant performance compared to random sampling across various numbers of exemplars, with no decrease in performance when there is a large number of exemplars. We also observe that utilizing the model-gena -ndee--gneertted plans achieves even improved performance than Oracle test plans (Baseline AS), which further validates our assumptions in Section 3.2 that GRASE helps models refine its preferred direction of plans with targeted exemplars.
8

---

Published as a conference paper at ICLR 2025
POOL Planning: Blocksword
PODL Planning: Blockswardd
NL* Prey
fancom
GRASE
Planning Acc 196
Planning
Ero Burs raprovar,
Number of exemplars (log scale)
Per example cost FLOPs ilog
Figure 7: PDDL planning performance Blocksworld with different ways to empirically approx- imate AS from the view of (left) numbers of exemplars (right) computation efficiency, GRASE* denotes the iterative application of GRASE only.
As expected, GRASE-DC further improves the model performance by reducing potential noise, so that models can achieve better performance with fewer exemplars, compared to GRASE alone. From the per block size performance in (rigre(((right)),, we note that Random can completely fail to help models solve hard problems (e.g.. problems with 16 and 19 blocks), while GRASE-DC helps achieve consistent gain, which is more significant when the problem is harder: 23.3 points absolute accuracy improvement for dittr--distribution (8-20 blocks) test cases versus 16.3 for in-distribution
(3-7 blocks) cases on average.
3.6 ANALYSIS: HOW TO APPROXIMATE AS, CONSIDERING THE EFFICIENCY TRADE-OFFS?
In our main experiments, we demonstrate how the plan similarity (AS) is a good source of signal for exemplar selection, well as how GRASE approximates AS and boosts model performance. It is worth noting that there is extra computing needed for the selection of exemplars compared to Random. For Baseline AS. computing LCAS is dynamic programming problem, which can be done in parallel by CPUs in neglectable time. GRASE requires one additional prompt to the LLMs, which is much less than search-based algorithms such MCTS and ToT, which typically require multiple simulations and one prompt on each node in tree structure. To achieve further efficiency, we propose additional methods to approximate AS.
Multi-Layer Perceptron (MLP): We utilize the Gecko model (Lee et al. 2024) to acquire em- beddings, denoted m, to represent the task descriptions and plans. Following our definition in Section 2.1 for an exemplar candidate and a test example, we treat the approximation as a regres- sion task with mean square error (MSE) between MIP((m(ca) (n(()))m(()) m(aa) and Sim of Ac Ar- During training, we sample pairs from candidates. During inference, use to to score and rank all candidates to conduct ICL. The implementation details are in Appendix A.2
Byte Pair Encoding as the Proxy: the above MLP-based method relieves the need for one extra prompt step to acquire p' with an embedding step from a comparative lightweight language model. However, the cost still grows linearly with the number of exemplar candidates. To further improve the efficiency, we propose to add a proxy between the exemplar candidates and the test examples.
Similar to the common practice tokenization in NLP (Zouhar al. 2023), we treat actions as characters in natural languages and their sequences (i.e., plans) as sentences. We conduct Byte Pair Encoding (BPE, Gage 1994) over the action sequences of the exemplar set to acquire the most commonly appearing sequences, which can be considered as the common subroutines of plans. We denote these proxy action sequences as 6,, ...,... bn (n is typically 200), which are also action sequences but not necessarily full plans. Before inference, we first pre-compute the Sim between each by and exemplar candidate action sequence A.. Then during inference, for each la of a test example, Sim is computed as the weighted average of each proxy similarity: Sim = Even cos (mm(ta), m(bb)) Sim'as, where m is the embedding model (e.g., Gecko).
To compare the efficiency of the methods described above, we estimate the floating- operations per second (FLOPs) needed for exemplar selection and plan generation for each test example. We compute the FLOPs of LLMs following PaLM (Chowdhery et al.) 2022), where the number of FLOPs per token is approximately equal to the number of parameters. We assume the use of 1000 candidates (200 natural language tokens per candidate) in the pool, LLama 3.1 405B for inference, and Gecko (IB, 768 dimensions) for embedding. We also assume that Gecko embeddings for the exemplar candidates and BPE tokens are pre-computed (extended details are in Appendix A.3.

---

Published as a conference paper at ICLR 2025
can observe that, at the best-perforning entries, MLP achieves 95% performance of GRASE with around 66% FLOPs and BPE-Proxy achieves 83% performance of GRASE with around 27% FLOPs. Although MLP and BPE-Proxy can not get performance improvement through iteration, they present to be good alternatives of GRASE when there is a limited budget.
From Figure 7
4 RELATED WORK
2023 Valmeekam et al., LLM Planning. Recent investigation on LLM capability (Hao et al.
2023b Kambhampati et al. 2024) shows that models struggle with solving planning tasks di- rectly given the problem descriptions, To comprehensively study this problem, researchers have designed various benchmarks and environments (Valmeekam et al., 2024 Xie et al., 2024 Bohnet et al. 2024 Zheng et al.) 2024 Hu & Shu 2023). In response, there is a line of work discovering the methods to improve planning with LLMs: e.g., applying advanced prompting methods (Silver al.] 2024), utilizing external tools (Hirsch et al. 2024 Hao et al. 2024), or leveraging search-based al- gorithms (Hao et al. 2023 Lehnert et al. |024] /uhi- et al. 2024). In our work, we instruct the model with common and direct in-context learning, without format conversion or customized tool use. We show that simple exemplar selection helps achieve good performance on various planning tasks at low cost.
LLM In-Context Learning. Prompting and in-context learning (ICL.) have been considered as the prominent way interact with LLMs, which achieves significant performance on various tasks (Brown et al.) 2020; Wei et al.] 2022; Agarwal et al. 2024). Strategical exemplar selection key ICL success, where the model performance can be sensitive to perturbations over the ex- emplars (Zhang et al. 2022). Previous work on exemplar (i.e., demonstration) selection mainly focuses on improving the modeling of task-side similarity (Rubin et al.) 2022] Ye al. 2023). Re- cently, Auto-CoT (Zhang et al. 2023) discusses how to select exemplars with a fixed cluster test examples and their rationales. our work, we demonstrate the effectiveness of the similarity from another perspective, the expected outputs. We show how the action sequence works analytically and empirically on both performance and efficiency (c.g., -DC reduces the exemplar needed). We anticipate the design to be extended to tasks requiring long and dependent sequences answers, such as web agent trajectory, coding, and math.
Iterative Refinement with LLMs. Leveraging model-generated signals improve model perfor- mance has demonstrated its effectiveness in various domains, with supervised fine-tuning (Schick) & Schüizze 202T Welleck al., 2022] Peng et al., 2023 Chen al., 2024). prompting (Zelikman et al. 2022). and reinforcement learning (Brooks et al. 2024: Madaan et al. 2024). iPET (Schick & Schütze| 2021) iteratively applies model classification output to improve few-shot learning- STaR (Zelikman al., (022) uses the model-generated rationales to improve model reasoning capa- bility. Recently, Self-Refine (Madaan et al., (024) shows how to utilize feedback on the generation sampled from the same model to refine the model output. Unlike commonsense reasoning tasks such as WSC (Levesque et al. 2012). where the answer is a single choice with a rough overall ex- planation. In planning tasks, besides the overall goal achievement, the validity of every single action in the sequence is also vital. In our work, we utilize the model-generated plans to re-sample the exemplars in ICL with action sequence similarity. Maintaining the ICI. pipeline also allows direct evaluation and easy bootstrapping.
5 CONCLUSION
In this paper, we propose GRASE-DC to improve the model planning capability through in-context learning. To do so, we found action sequence similarity (AS) acts significant and consistent signal in sampling and filtering exemplars. Following this finding, our GRASE-DC first re-samples high AS exemplars and then curates the selected exemplars with dynamic clustering on AS to achieve balance of relevance and diversity. Experiments on various planning tasks and settings validate consistent and robust performance improvement with the proposed methods. Extensive analysis demonstrates that our proposed methods deliver these strong results across different LLMs, and even in -fitt--diitriuution scenarios. Given the efficiency and applicability of GRASE-DC, we plan to investigate its application in more complex scenarios and generalization to different environments.
10

---

Published as a conference paper at ICLR 2025
6 ACKNOWLEDGMENT
The authors thank Sherry Tongshuang Wu, Hanjun Dai, Bo Dai, Bethany Yixin Wang, Katayoon Goshvadi, Ken Liu, Jiannan Xiang. Xiang Ji, Kaixuan Huang, Xiangyu Qi, Xiang Li, Shikhar Murty, and Vijay Viswanathan for their valuable feedback, and anonymous reviewers for helpful discussions and comments. The authors also thank Google DeepMind teams at large for the insightful discussions and for providing supportive research environment. At CMU, Xinran Zhao supported by the ONR Award NO001423 1000142312840.
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Ale- man, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, al. Gpt-4 technical report. arXiv preprint X3xx:3333008744 2023.
Constructions Aeronautiques, Adele Howe, Craig Knoblock, ISI Drew McDermott, Ashwin Ram, Manuela Veloso, Daniel Weld, David Wilkins Sri, Anthony Barrett, Dave Christianson, et al. Pddll the planning domain definition language. Technical Report, Tech. Rep., 1998.
Rishabh Agarwal, Avi Singh, Lei M Zhang, Bernd Bohnet, Luis Rosias, Stephanie C.Y. Chan, Biao Zhang, Aleksandra Faust, and Hugo Larochelle. Many-shot in-context learning. In ICMI, 2024 nwt. fort/forum?dd
Workshop on In- In-Context Learning, 2024. URL hhttps:///ppnttt
goi7DFH1qS
Anthropic. Introducing the next generation of claude, 2024. URL bttttp:://www.atthrr..
Com/
Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Michal Podstawski, Hubert Niewiadomski, Piotr Nyczyk, and Torsten Hoefler. Graph of Thoughts: Solving Elaborate Problems with Large Language Models. Proceedings of the AAAI Conference on Artificial Intelligence, 38(16)17668211669, Mar 2024. doi: 10. 1609/aaai, www.16.2899990 view/29720
wttp:///ojaaaaaaoooooaoa..a atg.//aaaaaaaaaaa.aaaaa.aaaaa.aa wwwp://gg/.////iieeeeee Cwwpp//AAA/aaaa artiice/
Bernd Bohnet, Azade Nova, Aaron T Parisi, Kevin Swersky, Katayoon Goshvadi, Hanjun Dai, Dale Schuurmans, Noah Fiedel, and Hanie Sedghi. Exploring and benchmarking the planning capabil- ities of large language models. arXiv preprint arXiv:2406. 13094, 2024.
Ethan Brooks, Logan Walls, Richard L. Lewis, and Satinder Singh. Large language models can implement policy iteration. Advances in Neural Information Processing Systems, 36, 2024.
Tom B Brown, Ben Mann, N Ryder, M Subbiah, Kaplan, P Dhariwal, A Neelakantan, P Shyam, G Sastry, A Askell, Agarwal, et al. Language models are few-shot leareer. arXiv preprini arXiv:2005. 14165, 1, 2020.
Yunmo Chen, Tongfei Chen, Harsh Jhamtani, Patrick Xia, Richard Shin, Jason Eisner, and Ben- jamin Van Durme. Learning to retrieve iteratively for in-context learning. arXiv preprint arXiv:2406. 14739, 2024.
Aakanksha Chowdhery al. Palm: Scaling Language Modeling with Pathways, 2022. URL
https://arxixs /ttp:s////xxxvo/r///////// abs//////// htt//////.22/.//////////////a//a /2///2224222222222
Xiang Deng, Yu Gu, Boyuan Zheng, Shijie Chen, Samuel Stevens, Boshi Wang, Huan Sun, and Yu Su. Mind2web: Towards generalist agent for the web, 2023.
Abhimanyu Dubey et al. The Llama Herd of Models. arXiv, 2024. URL htttt://pp/xiii
orq/abs/2407..22 227883
Philip Gage. A new algorithm for data compression. The C Users Journal, 12(2):23-38, 1994.
Gemini Team et al. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context. arXiv, 2024. URL //arxii wwwp://wwwwworr/p//////////// 05530

---

Published as a conference paper at ICLR 2025
Yu Gu, Boyuan Zheng, Boyu Gou, Kai Zhang. Cheng Chang, Sanjari Srivastava, Yanan Xie, Peng Qi, Huan Sun, and Yu Su. Is your Ilm secretly a world model of the internet? model-based planning for web agents. CoRR, abs/2411.06559, 2024. URL htttps://aaxttti org. abs/
2411 06559
Shibo Hao, Yi Gu, Haodi Ma, Joshua Jíahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. Reasoning with language model is planning with world model. arXiv preprint arXiv:2305. 2023.
Yilun Hao, Yongchao Chen, Yang Zhang, and Chuchu Fan. Large language models can plan your travels rigorously with formal verification tools. arXiv preprint arXiv:2404. / /891, 2024.
Eran Hirsch, Guy Uziel, and Ateret Anaby-Tavor, What's the plan? evaluating and developing planning-aware techniques for Ilms. arXiv preprint arXiv:2402. 1489, 2024.
Daniel Höller, Gregor Behnke, Pascal Bercher, Susanne Biundo, Humbert Fiorino, Damien Pellier, and Ron Alford. Hddl: An extension to pddl for expressing hierarchical planning problems. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020), pp. 9883-9899 AAAI Press, 2020. doi: 10. w..1609/aai..34iin 334206.6542.
Richard Howey, Derek Long, and Maria Fox. Val: Automatic plan validation, continuous effects and mixed initiative planning using pddl. In 16th IEEE International Conference on Tools with Artificial Intelligence, pp. 294 201-301. IEEE, 2004.
Zhiting Hu and Tianmin Shu. Language models, agent models, and world models: The law for machine reasoning and planning. arXiv preprint urXiv:2312.05230 2023.
Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Mudit Verma, Kaya Stechly, Siddhant Bhambri, Lucas Paul Saldyt, and Anil Murthy. Position: LLMs can't plan, but can help planning in LLM-modulo frameworks. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 228252 PMLR, 21-27 Jul 2024. URL https: /ttp:s/://occceeeeeee ngs mlrr .tmll
1tsas//223//ambhamppaa
Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.). Proceedings of the 2020 Conference on Empirical Methods Natural Language Processing (EMNLP), pp. 6769 6781, Online, Novem- ber 2020. Association for Computational Linguistics. doi: 10. emn pp ma 550
URL https::///// wwwaaaaaannllooooooooooooo org.go.rog/00
D. Khashabi, S. Min, T. Khot, A. Sabhwaral, O. Tafjord, P. Clark, and H. Hajishirzi. Unifiedqa: Crossing format boundaries with a single qa system. In UnifiedQA: Crossing Format Boundaries With Single QA System, 2020.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles, 2023.
Jinhyuk Lee, Zhuyun Dai, Xiaoqi Ren, Blair Chen, Daniel Cer. Jeremy R. Cole, Kai Hui, Michael Boratko, Rajvi Kapadia, Wen Ding, Yi Luan, Sai Meher Karthik Duddu, Gustavo Hemaandez Abrego, Weiqiang Shi, Nithi Gupta, Aditya Kusupati, Prateek Jain, Siddhartha Reddy Jonnala- gadda, Ming- Wei Chang, and Iftekhar Naim. Gecko: Versatile text embeddings distilled from large language models, 2024. URL
www.xi..rrg/ab//24/0 /2r.g//ab//233... 20327
Lucas Lehnert, Sainbayar Sukhbaatar, DiJia Su, Qinqing Zheng, Paul Mc Michael Rabbat, and Yuandong Tian. Beyond a#: Better planning with transformers via search dynamics bootstrap- ping. In First Conference on Language Modeling, 2024. URL https: http:///pppeeeeeee////e fforum? deme:id==GGooduuu
12

---

Published as a conference paper at ICLR 2025
Hector J. Levesque, Ernest Davis, and Leora Morgenstern. The winograd schema challenge. In Pro- ceedings of the Thirteenth International Conference on Principles of Knowledge Representation and Reasoning, KR 12, pp. 552-561, AAAI Press, 2012. ISBN 9781577355601.
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uni
Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self-feedback. Advances in Neural Information Processing Systems, 36, 2024.
Shikhar Murty, Christopher Manning, Peter Shaw, Mandar Joshi, and Kenton Lee. Bagel: Boot- strapping agents by guiding exploration with language. arXiv, 2024. URL https: //axxiv. org hog/abs/20 2403. 08140
Daniel Müllner. Modern hicrarchical, agglomerative clustering algorithms, 2011. URL https: 2378
Jianmo Ni, Gustavo Hernandez Abrego, Noah Constant, Ji Ma, Keith Hall, Daniel Cer, and Yin- fei Yang. Sentence-t5: Scalable sentence encoders from pre-trained text-to-text models. In
Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), Findings of the Associa- tion for Computational Linguistics: ACL 2022, pp. 1864-1874, Dublin, Ireland, May 2022. findiings-acl.1466 URL
Association for Computational Linguistics. doi: 10. 10.18663/112022. 10.11666311202...nnnnnn-----o attpps:/aclaatthcloo..ooo
wwndingg-nninnnn....... 146
Baolin Peng, Michel Galley, Pengeheng He, Hao Cheng, Yujia Xie, Yu Hu, Qiuyuan Huang, Lars Liden, Zhou Yu, Weizhu Chen, et al. Check your facts and try again: Improving large language models with external knowledge and automated feedback. arXiv preprint arXiv:2302. 12813, 2023.
Ohad Rubin, Jonathan Herzig, and Jonathan Berant. Learning retrieve prompts for in-context learning. In Marine Carpuat, Marie-Catherine de Marneff,, and Ivan Vladimir Meza Ruiz (eds.), Proceedings of the 2022 Conference of the North American Chapter of the Association for Com- putational Linguistics: Human Language Technologies, pp. 2655-2671, Seattle, United States, July 2022. Association for Computational Linguistics. doi: 10. 1/0/533/1112222aacecll main. 191. URL ltttps::/aclantholoog.o ort. 2022 naac wwm.aiii... 191
Timo Schick and Hinrich Schütze. It's not just size that matters: Small language models are also few-shot learners. In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilek Hakkani-Tur, Iz Beltagy, Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou (eds.), Proceedingy of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 2339-2352, Online, June 2021. Association for Computational Linguistics. doi: 18.18653/v 10t.21/22112mmm 10021.naccl-mal naccl
URL
185)
Mohit Shridhar, Xingdi Yuan, Marc-Alexandre Côté, Yonatan Bisk, Adam Trischler, and Matthew Hausknecht. ALFWorld: Aligning Text and Embodied Environments for Interactive Learning. In Proceedings of the International Conference on Learning Representations (ICLR), 2021. URL
https://arxin org/ abs/2010 03768
Tom Silver, Soham Dan, Kavitha Srinivas, Josh Tenenbaum, Leslie Kaelbling, and Michael Katz. Generalized planning in PDDL domains with pretrained large language models. In AAAI Confer- ence on Artificial Intelligence (AAAI), 2024.
Together AI Team. Together ai, 2024. URL https:://wwtttttteeer wwwetheree....... ai/
Karthik Valmeekam, Matthw Marquez, Alherto Olmo, Sarath Sreedharan, and Subbarao Kambhampati. Planbench: An extensible benchmark for evaluating large language models on planning and reasoning about change. In A. Oh, T. Naumann, A. Glober- son, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Pro- cessing Systems, volume 36, pp. 38975-38987. Curran Associates, Inc., 2023a. URL httpss//pproeeeingg...eerrr cttpssc.cpppppppaeeeeeeeeeee fireer_fffii files L wwwws/papeeeeeeeeeepepeaaaeeeeee wwwppr//paa.... filee/ 7232ocedee8e7aaaa0ee722233555533 oat.:aaececcettttteeeee-ereeee-e pap.:aaaaa--peeeeeaaaatttteee -atastes and Benchmarks.
pdf
13

---

Published as a conference paper at ICLR 2025
Karthik Valmeekam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati. On the planning abilities of large language models-a critical investigation. Advances in Neural Informa- fion Processing Systems, 36:75993-76005, 2023b.
Karthik Valmeekam, Matthew Marquez, Alberto Olmo, Sarath Sreedharan, and Subbarao Kamb- hampati. Planbench: An extensible benchmark for evaluating large language models on planning and reasoning about change. Advances in Neural Information Processing Systems, 36, 2024.
Zora Zhiruo Wang, Jiayuan Mao, Daniel Fried, and Graham Neubig. Agent workflow memory, 2024.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 25.24824-24837, 2022.
Sean Welleck, Ximing Lu, Peter West, Faeze Brahman, Tianxiao Shen, Daniel Khashabi, and Yejin Choi. Generating sequences by learning self-correct. arXiv preprint arXiv:22/1.00055 2022.
Jian Xie, Kai Zhang, Jiangjie Chen, Tinghui Zhu, Renze Lou, Yuandong Tian, Yanghua Xiao, and Yu Su. Travelplanner. benchmark for real-world planning with language agents. In Forty-first International Conference on Machine Learning, 2024.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. the Seveth-Seventh Annual Conference on Neural Information Processing Systems, 2023. URL
btg/abs/2300 10601
Jiacheng Ye, Zhiyong Wu, Jiangtao Feng, Tao Yu, and Lingpeng Kong. Compositional exemplars for in-context learning. The Fortieth International Conference on Machine Learning, 2023.
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. Star: Bootstrapping reasoning with reasoning, Advances in Neural Information Processing Systems, 15:15576-11488, 2022.
Yiming Zhang, Shi Feng, and Chenhao Tan. Active Example Selection for In-Context Learning. In Yoav Goldberg. Zornitsa Kozareva, and Yue Zhang (eds.), Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. Emirates, December 2022. Association for Computational Linguistics. doi: 10.18653/v 1/2022. emnlp-main.622 6222. URI. https: ac antho org. 2022. emn 1 p ma n, 622
Abu Dhabi, United Arab
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 Representationss 2023.
net ttte://forrmmm...S.Stt..... JUHKr
Xinran Zhao, Hongming Zhang, Xiaoman Pan, Wenlin Yao, Dong Yu, and Jianshu Chen. Thrust: Adaptively propels large language models with external knowledge. In Thirty-seventh Confer- ence on Neural Information Processing Systems, 2023. URL
Huaixiu Steven Zheng, Swaroop Mishra, Hugh Zhang, Xinyun Chen, Minmin Chen, Azade Nova, Le Hou, Heng-Tze Cheng, Quoc V. Le, Ed H. Chi, and Denny Zhou. Natural plan: Benchmarking Ilms on natural language planning. arXiv preprint arXiv:2406. 13094, 2024. URL https://
www.v//.rg/bbb////ee 04520
Longtao Zheng, Rundong Wang, Xinrun Wang, and Bo An. Synapse: ennjectory-as-xeempp prompting with memory for computer control. In The Twelfth International Conference on Learn ing Representations, 2023.
Tan Zhi- Zui,Xuan, Lance Ying. Vikash Mansinghka, and Joshua B Tenenbaum. Pragmatic instruction following and goal assistance via cooperative languagc-guided inverse planning. arXiv preprint arXiv:2402. /7930, 2024.
Shuyan Zhou, Frank F Xu, Hao Zhu, Xuhui Zhou, Robert Lo. Abishek Sridhar, Xianyi Cheng, Yonatan Bisk, Daniel Fried, Uri Alon, et al. Webarena: A realistic web environment for building autonomous agents. arXiv preprini a00 13854, 2023.
14

---

Published as a conference paper at ICLR 2025
Vilém Zouhar, Clara Meister, Juan Gastaldi, Li Du, Tim Vieira, Mrinmaya Sachan, and Ryan Cotterell. A formal perspective on byte-pair encoding.
Anna Rogers, Jordan Boyd- Graber, and Naoaki Okazaki (eds.), Findings of the Association for Computational Linguistics: ACL. 2023, pp. 598-614, Toronto, Canada, July 2023. Association for Computational Linguis- tics. doi: 10. 10.18653/v1/222. Findings-and aacdings-acl.38 a81.38
awn....iinnnngsaa......... URL https::: / /acl anthe onthollog...rg/0002..
15

---

Published as a conference paper at ICLR 2025
A APPENDIX
A.1 STATISTICS, EXAMPLES, AND PROMPT TEMPLATES
Statistics. With the benchmark from Valmeckam et al. (023a) Bohnet et al. (2024), we construct the exemplar candidate pool with 28,000 examples for Blocksworld, 8,400 examples for Minigrid, 82,000 examples for Logistics, and 2,400 examples for Tetris, which covers the cases with either a small or large number of exemplar candidates. Each example typically contains 400 tokens on average, which varies with the complexity of the problems. For natural language planning, we follow Zheng et al. (024) to use 1,300 candidate exemplars to conduct trip planning. Please refer to the original papers for further analysis of the statistics. You can also refer to Höller et al. (2020) for extra information about the relevant PDDL domains and corresponding problem generation.
Examples. Each example written in PDDL contains a task description that describes the initial conditions, e.g., block bl on b2, and goals, e.g., block b2 on bl. For the exemplar candidate, there is a reference plan that shows one potential way to operate from the initial condition to the goal. e.g., unstack bl from b2, put on the table, and stack b2 on b1. All the descriptions, goals, and plans are written in predicate format that can be parsed by PDDL VAL. For natural language planning, descriptions and plans are written English.
We present the action space and an example for each task follows:
Blocksworld: (actions: pick-up, put-down, stack, unstack) TASK: (define (problem BW-rand-4) (:domain blocksworld-tops) (cobjects b3 62 b1 b4) (sinit (on b4 b1) (clear b4) (clear b2) (on b2 b3) (handempty) (ontable b3) (ontable bl)
Gooo: (and (on 62 b3) (on bl 62) (on b4 bl) ))
PLAN: (unstack b4 bl) (put-down b4) (pick-up bl) (stack bl b2) (pick-up b4) (stack b4 bl)
Minigrid: (actions: unlock, move, pickup. pickup-and-looss
TASK:
(define (prohlem grid_rove rrom2) (:domain grid) (sobjects p0 p1 p2 p3 (sinit; Object types (place p0) (place pl) (place p2) (place p3): Open/locked cells (open p0) (open pl) (open p2) (open p3) Connected cells (conn pO p1) (conn p0 p2) (conn pl pO) (conn pl p3) (conn p2 p0) (conn p2 p3) (conn p3 p2) (conn p3 pl); Lock and key shapes: Key placement Robot placement (at-robot p3) (arm-empty) )
GOAL: (:goal (at-robot p2))
PLAN: (move p3 p2)
Logistics: (actions: load-truck, load-airplane, unload-truck, unload-airplane, drive-truck, fly-airplane) TASK: (define (problem logistics-e1-s22 1-s2-p1-a1 (ddomain logistics-strips) (sohjects a0 t0 10-0 10-1 pO) (finit (AIRPLANEE a0) (CITY c0) (TRUCK t0) (LOCATION 10-0) (in-city 10-0 c0) (LOCATION 10-1) (in-city 10-1 c0) (AIRPORT 10-0) (OBJ pO) (at 10 10-0) (at p0 10-0) (at a0 10-0))
GOAL: (:goal(and(at p0 10-1))))
PLAN: (load-truck pO t0 10-0) (drive-truck t0 10-0 10-1 c0) (unload-truck p0 10-1)
Tetris: (actions: move-square, move-two, heve----eff/rrhhhuuu/ddwn
10-21 [0-3 f1-or [1- 11--1111111111 INPUT (define (problem Tetris-444) (zommain letris) (:objects 10-or 10- 10-2f
f2-0f 12-1f f2-2f f2-3f f3-Of f3- If f3-2f f3-3f position nothing- one_square nada- two__sraiie strriirathhh righti0 rightll - right_1) ) (iinit (connected f0-0f 10-1f) (connected 10-1f f0-0f) (connected f0- If f0-2f) (connected [0-2r (0-10) (connected [3-1f f2-1f) (connected 12-2f (3-2f) (connected A3-2f f2-20) (connected f2-3f f3-3f) (connected ff f2-3f) (clear f0-0f) (clear 1f) (clear f0-2f) (clear f0-3f) (clear fl-1f) (clear f1-3f) (clear (3-0f) (clear (3-10) (clear (3-20) (clear (3-3l) (at right righil0 [1-21 f2-21 (2-30) (at right rightll
f1-0f f2-0f f2-1f)
GOAL:(-goal (and (clear f0-0f) (clear f0-1f) (clear f0-2f) (clear f0-3f) (clear f1-0f) (clear f1-1f) (clear (1-2f) (clear (1-3())) )
PLAN: (move_l_down f1-0f f2-0f f2- f3-0f f3-1f rightll) (move_ down fl-2f f2-2f f2-3f f3-2f f3-3f f3-3f right10)
16

---

Published as a conference paper at ICLR 2025
Representation
Token
Sentence-TS-base
Sentence- Sentence-TS-large Gecko
Correlation
0.17
0.25
0.25
0.29
Table 1: Pearson correlation between task similarity and plan similarity (i.e., AS) with different ways to represent the tasks. Token denotes capturing the similarity between task descriptions with token overlap.
Trip planning:
Task and Goal: You plan visit 3 European cities for 14 days in total. You only take direct flights to commute between cities. You would like to visit Florence for 6 days. You want to meet a friend in Florence hetween day and day 14, You would like to visit Barcelona for 5 days. You would like to visit Helsinki 5 days. Here are cities that have direct flights: Barcelona and Florence. Helsinki and Barcelona. Find a trip plan of visiting the cities for 14 days by taking direct flights to commute between them.
Plan: Here is the trip plan for visiting the 3 European cities 14 days: ** 1-5:4* Arriving in Helsinki and visit Helsinki for days.
Day 5:** Fly from Helsinki Barcelona.
**Day 5-9; Visit Barcelona for days.
**y 9:** Fly from Barcelona to Florence.
**Day 9-14:*# Visit Florence days.
Prompt Templates: We use the simplest prompt to show clearly present the effect of exemplars in ICL. In detail, our prompt is ("Please solve the problem: [task]; Your plan as plain text without formatting: [plan]; done."). ) For exemplars, we fill in the task and plan and put them into the context. For text examples, the exemplars the context, we start with exemplars with the highest similarity. In our pilot study, the order of starting with the highest the lowest will not have huge impact the performance.
fill in the task and remove the parts after ...whot formatting: During writing
A.2 IMPLEMENTATION DETAILS
Metric. The detailed computation of QA-FI is follows: denoting pair of tasks t (test exam- ple) and t2 (exemplar candidate) with uni-gram tokens of each task pairs as Te, and Teg the QA-FI score can then be written QA-FI (Tr, n (T,,) U TT,)).
ICL with LLMs. For LLMs, we use the API systems, as mentioned in Section 3.3 Due to the instability of API with long context, test planning performance with few-shot exemplars (1,4.10). In this scenario (DC typically selects 10+ exemplars), diversity not the major consideration, so start with conducting pilot study the proposed GRASE. The authors would like note that comparison across commercial API systems can be unfair since the design and inference details are not disclosed.
If applicable, we set the max output token to be 1,600. We also tested our model performance with backbone LLMs with less than 70B parameters. We conduct our experiments on machine with 8 Nvidia A6000 (40G) GPUs with CUDA 12 installed with inference structure built upon vLLM (Kwon et 2023). However, we do not observe performance over 3% planning accuracy on Blocksworld with small-sized models. In these cases, ICI. only helps improve the plan validity (i.e., the actions are allowed the current states).
MLP. As sanity check, we first experiment on how much Gecko understands planning. We com-
pare the Pearson correlation between task similarity and plan similarity (AS) across different ways
to capture the similarity between 100 test examples and 400 exemplar candidates. From Table I1
we can observe that using cosine similarity with task description embeddings from Sentence- T5 (Ni
et al. 2022) shows a 0.25 correlation coefficient, which surpasses token overlap. Gecko (Lee al. 2024 achieves 0.29 correlation, which suggests that Gecko has a good understanding of the po- tential plans that relevant the task descriptions beyond the token level. We also note one
17

---

Published as a conference paper at ICLR 2025
direction to explore in the future: LLM embeddings may achieve higher correlation better MLP performance with increased cost in the trade-off compared to Gecko.
For the MLP in the main paper, initialize the network with 2 hidden layers with 400 neurons per layer. We use Adam as the optimizer with a learning rate le-5. The whole training process is not sensitive to hyperparameter settings in our experiments. We train MLP for Blocksworld with 400 exemplar candidates, which leads to 400 x 400 pairs as data points.
BPE-Proxy. We wrote a standard Python program to conduct BPE. We conduct the action-level character merging for 500 iterations. We cut off the learned tokens (short action sequences) that appear less than 200 times. In total, we collect 220 tokens to compute the Sim with all exemplar candidates before conducting inference with examples.
A.3 DETAILS ABOUT FLOPS COMPARISON
In the main paper, we compare the efficiency of the proposed methods with estimated floating-pon -ointt operations per second (FLOPs) needed for exemplar selection and plan generation for each test example. Here we provide details about the statistics presented. general, there are three stages of computation: preparation, exemplar selection, and inference. We denote that there are on average tokens per task description/plal /plans for either exemplar candidate or test example (k is around 200). Similarly, assume the of N candidates, LLama 3.1 (405B) for inference, and Gecko (IB) for embeddings with dimension (d=768).
Then, during preparation, MLP requires processing the embeddings for all exemplar candidates (both task description and plans) once, which requires 2N * * 1B FLOPs. For APE-Proxy, the be neglected. Similarly, it
computation of the frequent tokens (each is action sequence) requires processing the embeddings of the frequent tokens, which requires 200 * k * 1B FLOPs. Since N is typically larger than 1,000, BPE-Proxy achieves fast preparation compared to MIP. Baseline and GRASE require no preparation before observing the test example. For BPE-Proxy, additionally pre-compute and store the LCAS between frequent tokens and original candidates, which costs 200 N 2
During exemplar selection, MLP and -PE-Proxy both require acquiring the embedding of the task description of the test example, which takes k= 1B FLOPs. The task description embedding will be compared with all candidates/tokens for MLP/BPE-Proxy which requires N d 200 * d FLOPs for cosine similarity, respectively. GRASE requires one additional prompt, with typically 10 randomly selected exemplars in the context, the FLOPs will then be (10 + 1) x 405B. Baseline As and GRASE require the computation of LCAS, which costs N k2. which can be done by CPU in parallel and neglected compared to the scales other methods. For GRASE*, it requires double FLOPs compared to GRASE since it requires another round of LLM prompting.
Finally, during inference, with D exemplars selected, all methods require |D] * k 405B FLOPs for inference. In the original paper, compare methods with the sum of the exemplar selection and the inference cost, since the preparation is only done once before streaming the test examples.
A.4 MAIN RESULTS ON OTHER PDDL PLANNING TASKS (FULL..
We show the full performance of both GRASE-DC and the iterated version (GRASE-DC") without zoom-in in Figure cant and consistent performance improvement with varying numbers of exemplars with GRASE-DC and its iteration.
( (lower row). Similar to our findings in the main paper, we can observe signifi-
A.5 GRASE*; ITERATING GRASE ONLY
In Section 3.2
we present how we leverage GRASE-DC to improve LLM performance on vari- ous planning tasks with ICL. We show that the iterative application of GRASE-DC (GRASE-DC*) leads to significant performance improvement with fewer exemplars required. As described in Sec- tion 2.2.1 we can also iteratively apply the GRASE step only have overview of the perfor- mance with a different number of exemplars and make an easy comparison between GRASE and other baselines.
18

---

Published as a conference paper at ICLR 2025
POOL Planning: Blockswardd
POOL Planring: Min arid saaeve
POOL Planring: ToUls
POOL Planring Logistics
Witt
Epiee Dars rejessen
Eriot Bans repreient 70%
Number of Exemplars (lagscalee
Number of Exemplars (log-caale)
Number of Exemplars (log-scale)
Number of Exe Exemplars (log-scale)
Figure 8: PDDL plamning accuracy various tasks with Gemini 1.5 Pro. Baseline denotes the use of Oracle test plans to compute the similarity between test examples and exemplars. Baseline AS and Random lines the anchors across rows. GRASE denotes the of model output plans from random exemplars. VAL denotes the use of the plan validator. GRASE-DC" denotes the performance after applying GRASE-DC for another iteration with the model outputs from GRASE- DC.
Blacksworld (haration
Blocksworld GRASE9)
(Itoration GRASE-))
kanden
farden +
GANGENAL
GANGS
GRASE
65
Planning with
Number of Exemplars (lag-scale)
Number of Exemplars scolle
Number of Exemplars (log-scalo)
Figure 9: PDDL Planning Blocksworld with different iterations of GRASE and numbers of ex- emplars. The Random and Baseline AS lines are the same as Figure 3 Error bars each figure represent a 70% confidence interval. VAL denotes the use of the plan validator and only iterating over the test examples with wrong plans. Iteration 1,2 (*, **) denote the performance after (itera- tively) applying GRASE for 1, times, respectively.
As shown Figure g we can observe that, through iteration, GRASE achieves significant perfor- mance improvement compared to Random across different numbers of exemplars. Each iteration offers an additional -5 points for absolute planning accuracy improvement. In the second iteration (prompt the model four times in total), GRASE achieves better overall performance compared to Baseline As that utilizes the Oracle test plans. When GRASE is based on model-generated plans with high accuracy, can observe less decrease in gains with increasing number of exemplars.
A.6 PERFORMANCE ON NATURAL PLAN (EXTENDED)
Calendar planning:
Task and Goal: You need to schedule meeting for Harold and Patrick for half an hour between work hours of 9:00 to 17:00 Monday.
Harold's calendar is wide open the entire day. Patrick busy Monday during 9:00 9:30, 10:30 12:00, 12:30 13:30, 14:00 14:30, 15:00 16:30; Find time that works for everyone's schedule and constraints. Solution: Here the proposed time: Monday, 9:30 10:00
19

---

Published as a conference paper at ICLR 2025
Natural Planning: Calendar
Random
Planning Acc (%)
Task
Error Bars represent 70% CI
10
Number of Exemplars (log-scale)
Figure 10: Natural language planning performance on Calendar Planning with Gemini 1.5 Pro with different numbers of exemplars and signals for exemplars sampling. Baseline, As denotes computing action sequence similarity with Oracle test plans.
PDDL Planning: Blocksworid
Random
OAS
Planning Acc (%6
Error Bars represent 70% CI
Number of exemplars (log-scale)
Figure 11: PDDL planning performance on Blocksworld (100 test examples) with different repre- sentation methods of plans, where all methods use the Oracle test plans for analysis.
In Section 3.4 we present the performance improvement with AS and GRASE on trip planning. In this section, further extend our pipeline for other planning tasks in natural language. We notice that the calendar planning task in Natural Plan (Zheng et al., 2024) has a different feature with common planning problems, where the output is not plan with various actions, but time slot that available for all the participants of a meeting. The calendar planning problem can be considered as followig problem over the given slots of week (as shown above).
We further implement an elastic AS to test if AS also helps capture constraints in the task description. Similar to the vanilla AS, we represent the constraint "actions" of each participant with all the available slots in day with the half an hour interval, e.g, if the available time is 10:30 to 12:00, the corresponding action sequence will be [10:30, 11:00. 11:30). Except for the changed definition of actions, the whole pipeline remains unchanged.
we can observe that similar to our findings on PDDL planning tasks and trip planning. Task simi similarity at the token level shows similar performance as random exemplar selection. Baseline AS performs well when there is a sufficiently large number of exemplars selected, which validates the extensibility of AS on tasks with (ordered) temporal or logical constraints.
As shown in Figure 10
A.7 HOW TO REPRESENT A PLAN, CONSIDERING THE AFFORDANCE AND GRANULARITY?
In our main experiments, we show how representing plans as action sequences (AS) can show great capability in sampling the exemplars. However, AS is not equivalent to the original plan nor uses
20

---

Published as a conference paper at ICLR 2025
Method/# Exemplars
1
4
10
20
40
100
Random
36
39
43
37
37
35
GRASE
51
58
55
53
50
49
Random-RS
52
53
54
52
49
49
GRASE-RS
64
64
57
55
54
Random-RS
59
59
59
49
49
54
GRASE-RS*
70
66
67
69
69
Table 2: The comparison of planning accuracy (%) between rejection sampling (-RS) with random
sampling (Random) and GRASE on Blocksworld. RS* denotes the iterative application of RS.
leveraging the information of the actual context (i.e., domains PDDL). For example, consider two steps in the plan: unstack block A from block B, pul-down block A. AS will represent the plans as unstack, pur down, with no context of the blocks (e.g.. which block is operated?) or the overall situation (c.g., if hands empty this step).
To investigate this problem, we first extend AS by adding object affordance information: which object does the action apply to? We first propose to track the AS for each object. When computing the similarity, we consider the average of max AS-based similarly for each object. We denote the use of this similarity to rank exemplars we consider its affordance over the specific action if the action is relevant to multiple objects, e.g.. for unstack block A from block B, for the AS of block A, we add unstack_ O, for B, add unstack_ to distinguish the affordance with the order of appearance.
Object-centric Action Sequences (OAS). For each object,
Besides the object relevance, another perspective the granularity of the actions. For PDDL tasks, VAL can help acquire the actual change of the states with the understanding of the model. For exam- ple, when executing put-down block A. this action results the following changes the state: delete block A in hand, add hand empty, add block A on the table, which is a close view on the changes in the problem. We extend our definition of action to execution, i.e., each atomic change on the states. We denote the use of this similarity to rank exemplars Similarly, we also consider Object-centric Execution-basee based action Sequences (OES) as one kind of representation of plans. A detailed example is as follows:
Execution-
action Sequences (ES).
Given a PDDL p (unstack bl b6), (put-down bl), (unstack b3 b4), (put-down b3)..., the action sequence of the plan will be [unstack, put-down, unstack, put-down...), which ignores the objects as well as their affordance. For Object-centric Action Sequence Similarity (OAS), we first initialize an action sequence for each object, e.g., (b1: unstack-O, put-down, b6: unstack-1 ...). During comparing two plans written in an object-centric action sequence, for the action sequence of each object in the test example, find the object with the highest AS in the exemplar candidate. Then we use the macro-average across blocks as the overall OAS similarity.
For Execution-based action sequence Similarity (ES), we maintain the same overall structure but decompose the actions with their actual execution operations on the current states, for example, unstack is rewritten to (delete on, delete clear, delete handempty] Object-centric Execution-based action sequence Similarity (OES) is combination of OAS and ES.
We further conduct pioneer experiments by comparing these different methods represent a plan with the first 100 examples of the test set. As shown in Figure [ we can observe that: except OAS, all methods conducting ICI. with plan similarity achieve significantly better performance than random exemplar selection (+15-20 absolute points for the planning accuracy). One reason can be that the action sequence of each object is short, which makes the planning similarity computation unstable. Representing the plans in detailed way (ES and OES) achieves overall improved per- formance compared to AS. Above results motivate future work investigating what granularity or mixed granularity can achieve improved performance over the current pipeline. In our work, to keep the potential generalizability of AS beyond PDDL tasks, we us AS as the representation of a plan in main experiments.
21

---

Published as a conference paper at ICLR 2025
Method/# Exemplars
1
10
20
40
100
Random
36
39
43
37
37
35
Gecko
35
46
41
44
44
41
GRASE
51
58
55
53
50
49
Table 3: The comparison of planning accuracy (%) between embedding-based selection (Gecko)
and GRASE on Blocksworld. We use one of the state-of-the-art embedding methods, Gecko (Lee) al. 2024.. to compute the similarity of the problem similarity of test questions and exemplars.
A.8 REJECTION SAMPLING: RANDOM VS. GRASE
In Section 2.2. we describe how +VAL is akin to rejection sampling (RS). In this section, we compare the difference between RS with GRASE or random sampling. As shown Table we can observe that rejection sampling (assuming we have the gold VAL) helps both random and GRASE. However, GRASE-RS shows 5-12 point accuracy improvement over Random-RS. On the second iteration, the gap between Rand and GRASE becomes larger, which validates our performance gain.
A.9 DISCUSSION: LINK TO AGENTIC WORKFLOW
Recently, researchers in the LLM agent community have worked on capturing the similarity of trajectories with embedding models to improve agentic the workflow with memory, e-g., Agent- WorkFlow (Wang et al.) 2024) and Synapse (Zheng et al. 2023). Following the intuition, we further compare with a baseline using embedding models capture the similarity between problems. We use one of the sate-of-thhe-at embedding methods, Gecko (Lee et al. 2024), to compute the simi- larity of the problem similarity of test questions and exemplars, We then use the similarity rank and select the exemplars and conduct ICL.
we can observe that GRASE shows consistent and significant performance improvement over using the off-the-shelf embedding models. This observation further suggests the potential application of the proposed GRASE in the agentic workflow by capturing the similarity of trajectories via LCAS.
As shown Table 3
For the current scope of this paper, we focus on presenting the gains from the novel GRASE on planning tasks to show a clear contribution to planning. Besides PDDL tasks, we believe real- world simulated tasks are another important future direction, e.g.. Web Arena (Zhou et al.) 2023), Mind2Web (Deng et al. 2023). and ALFWorld (Shridhar et al., (021). Besides the planning-sie side capability, in simulated tasks, the LLM-based agents are also additionally required to capture and understand the complex environmental feedback per action (Gu et al. (024). Applying the state- based plan representation, i.c., ES in Appendix [A.7] can potentially make GRASE applicable to exemplar selection in environmental feedback simulation and eventually the whole pipeline solve simulated tasks. The authors sincerely hope the simple yet effective intuition we showcase can also inspire further ideas in the community in different directions.
22

---

Published as a conference paper at ICLR 2025
A.10 QUALITATIVE EXAMPLES OF PAIRS WITH HIGH INPUT SIMILARITY VS. PLAN SIMILARITY
To qualitatively illustrate the differences between exemplars with high task similarity and plan sim- ilarity, we present a test example as follows with the exemplars with the highest task/plan similarity follows. From the comparison, we can observe that, although plan similarity captures an exemplar with the same number of blocks and similar conditions from the appearance. The required plan can be different and unrelated. On the other hand, despite the different block sizes, the exemplar with high plan similarity is similar to the original problem from the essence: e.g., b5, b4 in the original problem are dealt in a similar way with b3, b2, respectively in the exemplar. As a result, putting the high-task-See high-task-similarity exemplars in the context results in wrong plan, while the high-plan-similariy example leads to correct plan, which is also different from the Oracle test plan.
Original
High-Plane High--Plan-Smmllarit
(define (problem BW-rand-6) (dommin blocksworld-4ogg
(define (problem B W--rand-6) (:domain blocksworld-4op
(define (problem BW-rand-5) (:domain blocksworld-4on
(zobjects b1 b5 b2 b4 b3 b6)
(objects b5 b4 b6 b3 b2 bl) (sinit(on b3 b6)
(zobjects b3 b5 b2 b4) (cinit (clear b4)
(sinit (on 62 b5)
(clear b3)
(handempty)
(on 65 63)
(on b4 b2)
(clear b4)
(on b2 b5)
(handempty)
(clear bl)
(handempty)
(on b3 b4)
(on b1 62)
(on b3 b1)
(ontable b1)
(on b4 b5)
(on b4 b2)
(on b5 bl)
(ontable b5)
(ontable b1))
(ontable b6)
(ontable b6)
(:goal (and
(clear b6)
(on 62 b3)
(on b3 b2)
(ggoal (and
(:goal (and
(on b1 b3) )))
(on b5 b4)
(on b6 b1) )))
Plan:
(on b3 b5) )))
PIAN:
(unstack b4 b2)
PIAN:
(unstack b1 b2)
(put-down b4)
(unstack b3 b4)
(put-down bl)
(unstack b2 b5)
(put-down b3)
(unstack b2 b3)
(put-down b2)
(unstack b4 b2)
(put-down b2)
(unstack b5 b3)
(put-down b4)
(unstack b3 b6)
(put-down b5)
(unstack b2 b5)
(put-down b3)
(unstack b3 bl)
(put-down b2)
(pick-up b6)
(stack b3 b2)
(unstack b5 bl)
(stack b6 b1)
(pick-up bl)
(stack b5 b4)
Gemini Output:
(stack bl b3)
(pick-up b3)
(unstack b3 b4)
Gemini Output:
(stack b3 b5)
(put-down b3)
(unstack b4 b2)
(pick-up b3)
(put-down b4)
(stack b3 b5)
(unstack b2 b5)
(pick-up b5); wrong
(put-down 62)
(stack b5 b4)
(unstack b3 b4)
(stack b3 b2)
(pick-up b5)
(stack b5 b4)
(pick-up b3)
(stack b3 b5) correct
A.11 PERFORMANCE SCORES IN A TABLE
In the main paper, we present our results in line charts to capture the trends with varying numbers of exemplars. We further present the performance of baselines and the proposed GRASF-DC in Table From the table, we can observe that GRASE+DC performs well on various tasks. The -DC step helps achieve the best performance under most scenarios, when is not, it helps achieve comparable performance with fewer exemplars.
23

---

Published as a conference paper at ICLR 2025
Exemplars
with -DC (No)
Method
4
10
20
40
100
2
3
Best
Blocksworld
Random
36
39
43
37
37
35
43
Task
25
36
40
39
41
36
41
AS
43
64
GRASE
50.7
58
54.7
53
49.3
49
51.3 (6.6)
(9.6
59.3 (12.2)
59.3
GRASE+VAL
64
64
59
56.7
54.7
54
67.3 (6.6)
(9.6)
72.3 (12.2)
72.3
GRASE*
55.7
61.7
61.7
63.7
63.7
62.3
52.3 (6.6)
57.3
60.7 (14.7)
63.7
GRASE'+VAL
69.7
66.3
67.3
69.3
69
74 (6.6)
(9.6)
80 (14.7)
80
GRASE"
57
62.3
68
65.5
GRASE" +VAL
73.7
72.3
71.3
70.7
67.7
68.3
73.7
Minigrid
Random
24
46
52
54
52
58
58
Task
26
32
37
48
48
49
49
AS
31
57
67
69
72
75
GRASE
31.3
62.3
60.3
60.7 (9.7)
(12.9)
62.7 (15.7)
64.3
VAL
61
66
67.3
69.7
65
69.7
68 (9.7)
66 (12.9)
67.7 (15.7)
69.7
GRASE*
54 (5.9)
59.7 (9.7)
68 (12.9)
68
GRASE' +VAL
74.7 (5.9)
73.7 (9.7)
74.7 (12.9)
74.7
Tetris
Random
0.7
2.0
4.3
4.3
5.7
4.0
5.7
0.7
4.0
7.0
6.0
AS
12.3
30.0
38.0
47.0
46.7
39.3
47.0
GRASE
2
6
8.3
11.3
14.6
16
35.7 (7.8)
39
43.7 (17.4)
43.7
GRASE+VAL
6.3
8.7
10.7
12.7
16.7
16.7
37.7 (7.8)
40.7 (12.8)
46 (17.4)
46
GRASE*
(8.7)
(13.7)
(17.4)
46
GRASE +VAL
46.7 (8.7)
(13.7)
54.7 (17.4)
54.7
Logistics
Random
7.0
16.3
16.3
15.7
20.7
18.0
20.7
Task
20.3
30.0
32.7
38.7
36.0
35.0
38.7
AS
21.3
30.7
33.3
38.3
37.3
40.0
40.0
GRASE
22.3
26
23.6
21.6
20.7
(12.3)
(16.1)
(19.7)
GRASE+VAL
26
27.3
26
26.3
25
23.3
38.7 (12.3)
42.7 (16.1)
41 (19.7)
42.7
GRASE*
30 (7.8)
37.3 (10)
37 (15.1)
37.3
GRASE' +VAL
42 (7.8)
44.3
44.3 (15.1)
44.3
Trip
Random
8.3
22.3
37.3
39.7
37.7
33.3
39.7
Task
3.7
23.0
32.3
38.0
37.0
38.0
AS
4.3
27.0
42.3
44.3
43.7
50.0
GRASE
17.0
35.0
40.7
45.0
45.0
51.3
51.3
Blocksworld 00D
Random
7.7
16.0
13.7
15.3
11.0
7.7
16.0
AS
11.3
18.0
20.3
18.0
19.7
19.7
20.3
GRASE
25
35.3
35.7
39.6
40
38.3
38 (9.5)
40.7 (13.9) 39.7 (17.3)
40.7
Table 4: PDDL Planning Performance in planning accuracy (%) on various tasks with Gemini 1.5 Pro. With -DC the use of dynamic clustering in the pipeline, where changing N, typically leads to 7-20 exemplars selected. For entries under -DC, numbers in brackets denote the averaged number of exemplars across the test data. denotes the iterative application of GRASE on the model-generatte plans form GRASE* (Figure(9). Blocksworld OOD denotes the performance out-of nut-of-distributian problems Figure
Best entries per row each variant of GRASE or GRASE-DC are bold.
24

---

Published as a conference paper at ICLR 2025
Abbr.
Term
Description
Random
Random
Selec-
We use Random in the figures to denote the baseline with randomly
tion
selected exemplars.
AS
Action-sequence Similarity
AS denotes the action sequence similarity, which we capture with Simas based on LCAS. We use Baseline to denote the proposed method ranking the exemplar candidates with their action sequence similarity with the Oracle test plans.
VAL
PDDL Validator
We use VAL denote the validator of the plans. +VAL in the figures denotes the variant in our pipeline, where we only operate on examples that LLMs failed the round.
ICL
In-Context Learning
We use ICL to refer to the classic ICL pipeline where we put each ex- emplar in the templates and sequentially list them as the context for prompting.
GRASE
Generative Re- sampling of
We propose GRASE as the first stage of our pipeline that utilizes the model-generated plans to help re-sample the exemplars.
Action sequence Similar Exem- plars
DC
Dynamic tering
Clus-
We propose DC as the second stage of our pipeline that resamples the exemplars from the GRASE stage by their mutual relevance calculated by AS.
Iteration
We use to refer to the iterative application of our pipeline, where the number of denotes the number of iterations.
MLP
Multi-Layer Per- ceptron
We use MLP denote the specific MLP trained to approximate AS between the test example and candidate exemplar with the exemplar task, exemplar plan, and test example task.
BPE- Proxy
Byte Pair Encod- ing as the Proxy
We use BPE to refer to the specific method to acquire tokens for plan- ning. where each "character" an action. BPE-Proxy denotes the method to only calculate the similarity between the tokens and the test examples so that the cost at inference time does scale linearly with an increasing number of exemplar candidates.
Table 5: Referential explanations to all the terms
A.12 REFERENCE FOR COMMON TERMS
To improve the readability of the paper, we wrote an explanation for set of important abbreviated terms we used in T
25


Reviews:
[{"review_id": "BJGMOiRtDR", "reviewer": "Reviewer_p57G", "summary": "The authors propose GRASE-DC, an approach to enhance planning capability in LLMs by improving ICL exemplar selection. Unlike traditional methods relying on semantic similarity, which can lead to false positives, GRASE-DC utilizes AS similarity to identify exemplars with closely aligned plan structures. The GRASE-DC pipeline comprises two stages: re-sampling high-AS exemplars and dynamically clustering them to balance relevance and diversity, yielding more accurate planning guidance with fewer exemplars. An iterative variant, GRASE-DC*+VAL, further boosts performance.", "questions": "Refer to weaknesses.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The proposed approach is both intuitive and shows good empirical performance as it selects exemplars based on AS similarity, providing the similar types of exemplars as the test task.\n2. The empirical evaluation is extensive, spanning four PDDL tasks and a natural language planning task, and it tests the method across different base models, showcasing the robustness of the approach.", "weaknesses": "1. The effectiveness of GRASE is highly dependent on the quality of initial plans generated by the LLM with randomly selected exemplars; poor initial plans can lead to compromised AS-based exemplar selection.\n2. For setups with validator access, a baseline comparison with rejection sampling could improve the analysis. E.g., under a similar validator query budget, the validator can be used to reject the invalid plans and select the better plan generated by the approach with random exemplars.", "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": "6qlGRIsIbE", "reviewer": "Reviewer_gvwE", "summary": "This paper proposes GRASE-DC, which is a new 2-stage pipeline for selecting examples for in-context learning of planning tasks based on action sequence similarity. In the ‘Generative Re-sampling of Action Sequence Similar Exemplars’ stage, GRASE-DC ranks and selects ICL exemplars with high action sequence similarities. In the ‘Dynamic Clustering’ stage, GRASE-DC performs AS-based clustering to further curate improved dynamic sets of examples that strikes a good balance between diversity and relevance to further improve the LLM’s planning ability. This paper also reports comprehensive experiment results on four PDDL tasks to empirically show the performance gain brought by GRASE-DC to different LLMs.", "questions": "In Figure 3, why on some tasks the planning accuracies of GRASE+VAL are higher than those of AS for certain numbers of examples? Is there any intuition behind this observation?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- **Originality**: This paper has good originality in that it proposes to focus on action sequence similarity instead of the traditional criteria based on the semantic similarity between task descriptions when performing example selection for LLM in-context learning of planning tasks.\n- **Quality**: This paper has high overall quality. Most of the steps in the proposed GRASE-DC pipeline are very clearly described and discussed in the methodology section, and Section 3 as well as the appendix also provide comprehensive empirical results and analysis to support the main claim of the paper.\n- **Clarity**: This paper is generally well-written and the ideas are generally well-presented in the paper. The clarity of both the writings and the figures are good. Please see the Weaknesses section in this review for things to improve.\n- **Significance**: The main intuition behind GRASE-DC is relatively simple and straightforward, but its performance gain shown in the empirical evaluations is solid.", "weaknesses": "1. In the formula on Line 141, shouldn’t there be a ‘|      |’ symbol around ‘LCAS(A_i, A_j)’? According to the previous description, LCAS(A_i, A_j) is a sequence, not a number.\n2. The notation and definition of the core concept ‘Action Sequence Similarity’ should be defined more clearly and strictly in the paper. Currently some mentions of AS are a little vague and confusing.", "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": "LQyvIY6oNg", "reviewer": "Reviewer_BjER", "summary": "This paper explores the action sequence as a key signal to measure the similarity between exemplars in planning tasks. Based on this finding, the paper introduces a two-stage pipeline, GRASE-DC, to select similar in-context examples while maintaining diversity and relevance. Experiments on both PDDL and natural language planning tasks show the promising performance of the proposed exemplar selection strategy. Further analysis includes OOD generalization and some options to replace AS when considering efficiency.", "questions": "- Why are MLP and BPE-Proxy more efficient than LCAS, as encoding the action sequence to embeddings itself requires inference time?\n- Why is Sim$_{AS}$ designed as shown in line 141, whereas based on experience LCAS($A_i$, $A_j$) should be squared?\n- How is the decision made for the iterative version of GRASE-DC on whether to iterate? Since we do not have test data trajectories and answers, based on efficiency, iteration is only needed in case of errors.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper breaks away from traditional task similarity and instead utilizes action sequence similarity to select exemplars for ICL, enhancing the model's planning performance, which is simple yet effective.\n- The GRASE-DC shows great generalization performance on more complex tasks.\n- Endeavors have been made to pursue the efficiency of the exemplar selection process.", "weaknesses": "1. The method of using clustering algorithms to improve the relevance and diversity of the selected exemplars has been proposed by other paper [1] before.\n2. The selected evaluation datasets lack some real world simulated tasks such as ALFWorld, Mind2Web, ScienceWorld, etc.\n3. Though the VAL mechanism is referenced from other paper, the authors are suggested to introduce it briefly in the paper to enhance the readability as VAL appears frequently in the paper.\n\n[1] Automatic Chain of Thought Prompting in Large Language Models, ICLR 2023", "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": "duExDwF6Bp", "reviewer": "Reviewer_BrrL", "summary": "This paper proposes GRASE-DC, a two-stage selection algorithm designed to identify effective and diverse exemplars from candidate plans, thereby enhancing in-context learning effectiveness. In the first stage, GRASE calculates the Action Similarity (AS) between different plans based on their sequence of actions. In the second stage, DC refines the selected exemplars using dynamic clustering based on AS, ensuring a balance between relevance and diversity. The effectiveness of GRASE-DC is demonstrated through extensive experiments, which show significant performance improvements over baseline methods.", "questions": "1. How do you justify that only the sequence of actions is important for capturing the plan properties? Have you considered including intermediate states (i.e., the object states and information) in the plan?\n\n2. Could you provide a detailed pseudocode for GRASE-DC? I am a bit confused with the steps in Diversity Clustering.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "[+] The overall structure is compact and clear.\n\n[+] The use of four benchmark domains provides convincing results.\n\n[+] The analysis section effectively discusses the efficiency of different methods for calculating Action Similarity (AS).", "weaknesses": "[-] My concern is that such methods may be difficult to adopt in real-world applications. I feel that in-context learning is not the optimal solution for improving the planning capabilities of LLMs, especially considering the existing o1. In-context learning is more suitable for quickly adapting the model to output desired formats or providing it with hints to follow, rather than using very long in-context prompts to enhance the model's capabilities.\n\n[-] The paper should at least compare some baseline approaches that use the similarity between plans. In the LLM-agent area, there are papers that employ similar ideas, using a similarity metric to select trajectories from the memory module. Implementing such a simple baseline would not be difficult and could provide a better complement to the experiments, enhancing their convincingness.", "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)