Improving Large Language Model Planning with Action Sequence Similarity

Authors: Xinran Zhao, Hanie Sedghi, Bernd Bohnet, Dale Schuurmans, Azade Nova
Primary area: foundation or frontier models, including LLMs
Keywords: planning with LLM, in-context learning (ICL), action sequence

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.

Decision: accept (poster)
Reviewer scores: 5, 8, 5, 5

Reviews and discussion:
<thread>
creation date:
1729652674774

thread_type:
official_review

<thread_object>
creator: reviewer_brrl

<content>
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.

strengths:
[+] The overall structure is compact and clear.

[+] The use of four benchmark domains provides convincing results.

[+] 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.

[-] 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.

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?

2. Could you provide a detailed pseudocode for GRASE-DC? I am a bit confused with the steps in Diversity Clustering.
</content>
</thread_object>

</thread>
<thread>
creation date:
1729689354384

thread_type:
official_review

<thread_object>
creator: reviewer_bjer

<content>
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.

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.
- The GRASE-DC shows great generalization performance on more complex tasks.
- 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.
2. The selected evaluation datasets lack some real world simulated tasks such as ALFWorld, Mind2Web, ScienceWorld, etc.
3. 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.

[1] Automatic Chain of Thought Prompting in Large Language Models, ICLR 2023

questions:
- Why are MLP and BPE-Proxy more efficient than LCAS, as encoding the action sequence to embeddings itself requires inference time?
- Why is Sim$_{AS}$ designed as shown in line 141, whereas based on experience LCAS($A_i$, $A_j$) should be squared?
- 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730712984100

thread_type:
official_review

<thread_object>
creator: reviewer_gvwe

<content>
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.

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.
- **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.
- **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.
- **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.
2. 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.

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730714952437

thread_type:
official_review

<thread_object>
creator: reviewer_p57g

<content>
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.

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.
2. 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.
2. 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.

questions:
Refer to weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733300975914

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Thanks for the discussion period

comment:
We express our sincere gratitude to the area chair and reviewers for hosting an insightful and constructive discussion.

We appreciate that the reviewers acknowledge that:

1. The paper is well-written with a clear presentation of the ideas (Reviewer gvwE, BrrL)

2. The proposed method from simple and effective intuition shows significant empirical performance on planning tasks (Reviewer p57G, gvwE, BjER, BrrL)

3. The empirical evaluation is extensive, showcasing the robustness of the approach across backbone LLMs and settings (Reviewer p57G, BjER, BrrL)

Through the discussion, we have carefully addressed and responded to the concerns and questions raised by the reviewers, as acknowledged in the discussion, which are summarized as follows:

1. In response to Reviewer p57G, as acknowledged by the reviewer, we first describe how results in the original draft (good performance on Tetris planning) can address the concerns about LLMs’ initial performance. We then conduct additional experiments to address the reviewer’s concern about the rejection sampling baseline and show robust gain from GRASE. In the second round of discussion, we explained how the rejection sampling with random and GRASE is comparable. We believe the discussion and new results can provide a good response to the reviewer’s concern.

2. In response to Reviewer gvwE. We sincerely appreciate the reviewer for liking our paper and we updated the formula and notion of action sequence similarity in the paper.

3. In response to Reviewer BjER, in the first round of discussion, we addressed the reviewer’s confusion with PDDL validators, efficiency comparison, and the iteration decision of the proposed methods. We also further discussed the details of the significance of our work compared to the literature. In the second round of the discussion, we further introduce how GRASE-DC is a point-wise (i.e., per test question) clustering method on exemplar selection with signals from planning, which differs from previous work on QA tasks with a single fixed cluster. We also further show the significance of our test suite (4 pure planning tasks and 2 natural planning tasks) with abundant previous work in the communities and detailed comparison with simulated tasks with examples.

4. In response to Reviewer BrrL, in the first round of discussion, as acknowledged by the reviewer (“The clarifications and new empirical results have addressed some of my earlier concern”), we successfully convinced the reviewer of the significance of our ICL-based approach, new baselines from plan-side similarity, and pseudo code to show the details of the implementation.
In the second round of discussion, we further answer the reviewer’s additional questions on the exact latency and how our method shows great performance with a multiple iteration variant (i.e., GRASE-DC*) in the original paper. At this point, we have not heard the reviewer’s further insights or details. We believe the current answers provide a good response to these questions.

Accordingly, in light of the reviewers' great suggestions, we improved our draft to incorporate the discussion, as mentioned in our response to Reviewer BjER, which is summarized as follows:

1. We add discussion on PDDL VAL and edit the typo in Sim_AS in Section 2.1; 
2. We update the notion of action sequence similarity (AS) as we refer to the baseline AS as Basline_AS, instead of italic AS across the papers; 
3. We extend our explanation on +VAL in Section 2.2.1 and link it to rejection sampling (RS). 
4. In Appendix A.8, we further compared RS with random sampling and GRASE; 
5. We add a reference and discussion on Auto-CoT in Section 2.2.2 and Section 4.

As acknowledged by the reviewers, our method shows a solid contribution to improving the planning performance of large language models from the novel perspective of plan similarity. The simple yet effective intuition we showcase can also inspire further ideas in the community. We believe that our responses and corresponding changes can address most of the reviewers’ concerns and questions. The new points in the second round discussion are straightforward to be integrated into the final draft.

We sincerely appreciate the area chair's effort in hosting the discussion period and the reviewers' collaborative effort and engagement. We hope that our contributions and responses can be taken into full consideration.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper proposes a method to enhance LLM’s planning by improving the example selection in in-context learning. Instead of leveraging semantic similarity, the proposed method uses AS similarity. The writing is mostly easy to follow. The AS similarity is intuitive, and the performance improvement is grounded. As the paper suggests AS similarity is more suited for planning tasks, a running or illustrative example would help better concretize the idea. The method is sensitive to its initial plan (which is affected by randomly selected examples). The added analysis and ablation study in the rebuttal period makes the comparison more insightful and more grounded.