Large Language Models as Commonsense Knowledge for Large-Scale Task Planning

Summary

The paper proposes to use large language models (LLMs) as a world model instead of a policy for task planning. Specifically, the LLM is used to approximate the state of the world and acts as a heuristic policy in Monte-Carlo Tree Search (MCTS). Experimental results demonstrate the effectiveness of the method, outperforming a finetuned small model and a LLM policy.

Strengths

1. The paper innovatively proposes to use language model as world model instead of policy model for task planning. The idea is quite interesting and the motivation is convincing, i.e., this can lower the complexity of the problem and better utilize the encoded commonsense knowledge in language models. 2. The experimental results demonstrates the effectiveness of the proposed method.

Weaknesses

1. It is better to include more baselines that employ special design for task planning, e.g., SayCan [1], Zero-Shot Planner [2], etc. 2. Only simple settings are considered in this work, i.e., object re-arranging task in a household environment. I would be interested in seeing if the method will still work when applied to more complex environments, which contain more diverse objects making it harder to predict world state. [1] Ahn et al. Do As I Can, Not As I Say: Grounding Language in Robotic Affordances [2] Huang et al. Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents

Questions

LLM-MCTS retrieves in-context examplars from a dataset. Does the baseline model also do this?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

Seems that I don't see a limitation section in the paper? Also, broader societal impacts are not included, which should typically be consider for a generation model like large language models. Please refer to weakness section for improvement.

Summary

This paper proposed to leverage LLMs both as a (commonsense) world model and heuristic policy within the MCTS search algorithm to tackle household planning tasks namely object rearrangements. The main idea is that for each simulation phase in MCTS, the algorithm sample from LLM to obtain the initial belief of states (of objects) and then use the LLM as a heuristic policy to guide action selection and finding promising trajectories. [Some details of when and how often the LLM is used as a world model is missing from the main paper (see questions)] The paper evaluated their approach using a subset of VirtualHome tasks– object rearrangement. They tested models on simple and compositional (rearranging multiple objects) tasks, as well as in-distribution and out-of-distribution settings. They use the `success rate’ of completing the tasks within 30 steps as evaluation metrics for comparison. They demonstrate significant improvements over baselines including a variant of the MCTS wo/ commonsense world model, a supervised GPT-2 model, and using GPT-3.5 only as the action policy. The improvements are larger for compositional and OOD setups where their method benefits from the MCTSC’s lookahead and LLM’s commonsense knowledge of the world.

Strengths

- Interesting/timely approach to leveraging LLM both as a world model and policy within the MCTS framework for the important task of planning - Significant improvements over baselines - Thorough and insightful ablation study to analyze the functioning of different components

Weaknesses

- The paper only tested on object rearrangement task with limited object relationships (on, inside). More complex and realistic tasks are left unexplored. - The paper benefits from the rewriting of Sec 4.2 to add technical details. At its current state, it’s unclear how often the LLM is used as a world model (see questions).

Questions

1– From my understanding the LLM is only used once (per simulation) to get the initial state of the objects. How do you use that to estimate the value of selected actions (line 175)? Do you get different world states for different simulation iterations? is the commonsense model used at any other stage in the MCTS search algo? I think a more organized description of the process with a running example would be helpful. 2- During MCTS, to sample state from the belief, do you sample the position of all available objects or task-related objects? 3- Some notations are undefined in Algorithm 1: d, tau, d’, … 4- Why did the author limit themselves to only object rearrangement tasks with only a few object relationships (on, inside)? Did the author explore their method on other household or planning tasks? 5- For compositional tasks, are models provided with 1 few-shot compositional example or a simple example? 6- Line 291: how is the ground-truth reward function obtained? It's unclear how the ground-truth reward function is different from the one used in the proposed final model 7- An interesting observation is that sometimes GPT3.5 and MCTS outperform in the unseen apartment setup compared to the seen one (on some tasks). Do authors have any insight/speculation on this?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Yes, briefly in conclusion.

Summary

The paper introduces a new methodology _Monte Carlo planning with common sense knowledge_. The idea is to rely on LLMs to integrate common background knowledge into Monte Carlo Tree Search algorithm with application to language-instructed object rearrangement tasks. Assuming access to a dataset of expert actions and observations, a list of all objects, containers and surfaces appearing in the dataset are retrieved. Similar to [S.Li 2022](https://arxiv.org/pdf/2202.01771.pdf) an LLM is used to approximate the belief of the state, containing the list of objects and their relationship. For instance, the fridge is likely to be in the kitchen. To derive a policy, an LLM is also used, building on the work of [S.Li 2022](https://arxiv.org/pdf/2202.01771.pdf). Relying on PUCT, the model takes as input the examples in the dataset, the goal description, the current observations and the history of actions and outputs the list of next actions to take. The method developed is evaluated on the Virtual Home, where the task is to rearrange objects in different apartments. The complexity of the task depends on the novelty of the apartment and the object considered (could be observed or not in the training data). The benchmark includes four methodologies, UCT, two baselines based on [S.Li 2022](https://arxiv.org/pdf/2202.01771.pdf) and the proposed methodology. The results demonstrate the improvement induced by _Monte Carlo planning with commonsense knowledge_ independently of the complexity of the task. An ablation study demonstrates the improvement induced by the initial approximation of the belief of the state. Finally an analysis of failures is conducted and demonstrates that most of them are linked to inadmissible actions outputted by the LLMs and back-and-forth behavior.

Strengths

The work builds on [S.Li 2022](https://arxiv.org/pdf/2202.01771.pdf), relying on an LLM to approximate the belief of the state and to derive a policy. The novelty is to rely on MCTS and PUCT to derive the policy instead of DT. The approach is evaluated on a broader task than [S.Li 2022](https://arxiv.org/pdf/2202.01771.pdf), including compositional task that are supposed to be more complex than simple task to solve. Finally, the ablation study provides insights on the added value of each block of the proposed methodology.

Weaknesses

The paper mostly relies on experiments and ideas from [S.Li 2022](https://arxiv.org/pdf/2202.01771.pdf) and would gain clarity if clearly stated. For instance, the use of LLMs to initialize the belief state was already used in [S.Li 2022](https://arxiv.org/pdf/2202.01771.pdf). Additionally, the code is not public and the implementation of LLM_MCTS is not super clear form pseudo code available in _Algorithm 1_. The paper would gain clarity by making the code public or available in supplementary materials.

Questions

The parameters $c_{puct}$ and $c_{uct}$ can have a huge impact on the performance of the algorithm. How did you select the parameters? PUCT can struggle with large state spaces, did it motivate the choice to keep only 2 types of relationship instead of 59 proposed in the task. Getting insights on the potential drop in performance induced by an increase in the size of the state space would be interesting. 200 expert trajectories are used in the training set. Having an idea of the impact of the number of trajectories on the performance of the methodology could be of great interest.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

The two main limitations of the methodology are the non admissible outputs produced by the model and the back and forth behavior. The two were acknowledged by the authors.

Summary

This work demonstrates that LLMs can be used as the commonsense models of the world and serve as the heuristic policy in search algorithms. Specifically this paper uses Monte Carlo Tree search to explore word states sampled from the output of LLMs and commonsense policy from LLMs can effectively guide the search, which reduces the search complexity. Experimental results on daily planning tasks again verify the advantages over using LLMs solely as policies.

Strengths

a). Novel idea by incorporating commonsense knowledge from LLMs into search algorithms instead of LLMs solely as policies. This work also points out that doing the search with the help of LLMs as a model may be better and more efficient than using LLMs directly as a policy. b). Comprehensive evaluation of the proposed methods including simple tasks, compositional tasks or in-distribution, out-of-distribution tasks. c). Good insights that improvements might come from the MCTS’s look-ahead search and more explorations of other possible search directions. Overall this work might motivate more research utilizing LLM’s world knowledge for decision-making problems.

Weaknesses

a). This work argues that planning policy may suffer from hallucination issues of LLMs in the related work. However this work did not justify how their proposed methods can help relieve the issues. It can add some context to discuss this. b). As discussed in the paper, the proposed method might face the efficiency problem.

Questions

(a) Just curious about why the baseline of UCT achieves zero success rate in Table 1 and can you explain more about this? Due to huge search space, UCT might fail to solve in a given time limit. But are there any improved search methods that can achieve better success rates, i.e., stronger baselines?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

n.a.

Summary

This paper introduces a technique to incorporate large language models' commonsense knowledge into Monte Carlo Tree Search to guide planning. It uses LLMs to obtain probabilities over the initial belief of the state, and as a heuristic policy to guide simulation. Evaluation on household object rearrangement tasks in VirtualHomes demonstrates that the method is empirically more effective than search algorithms that don’t incorporate LLMs (UCT), or just having LLMs generate a policy through direct prompting (GPT3.5 Policy). The paper also makes a theoretical argument in favor of using model-based methods rather than model-free methods with LLMs.

Strengths

1. Novel approach to planning with LLMs that doesn’t just entail having the LLM directly generate a policy, but as part of a search algorithm 2. Technique significantly outperforms both vanilla search algorithms and using LLMs directly to generate policies on household object rearrangement tasks 3. Ablation study and analysis give good insight into what helps, and where there is still room for improvement

Weaknesses

1. The paper evaluated this technique in only occurred in one domain -- VirtualHome -- and it is unclear whether it can generalize to other embodied domains. 2. The main barrier to using this approach in practice is that it entails making multiple calls to GPT3.5 when computing each action, alongside having to do additional search on top -- making it less efficient than both vanilla search and vanilla LLM generation methods. Though computational expense was noted as a limitation in the conclusion, it may also be valuable to additionally report runtimes in the paper 3. The theoretical arguments for “knowledge of LLMs regarding states of world is more complete than their knowledge of policies for accomplishing daily tasks” (L58-59, Section 5.3), whereby description length of policies vs. world models is used to justify this claim, is not entirely convincing to me. First, it is unclear whether the argument the authors put forth that “learning about the world would likely require less training data than learning policies to do all tasks in the domain” (L62) applies to LLMs, which have been trained on an abundance of data and are not at all limited by data scarcity. This argument also makes assumptions about the way LLMs represent policies vs. models which seem not at all obvious to me — why is description length the best way to characterize LLM knowledge? LLMs are not trained to be efficient compressors, they are trained to imitate the training set. * Is there a way to empirically validate this claim in particular? --- Missing citations: - https://aclanthology.org/2022.acl-long.120/

Questions

1. Instead of performing similarity search, can you just constrain generation and/or prompt the model explicitly to choose amongst a limited set of available actions/object? This may help avoid translation errors. 2. Can you clarify the connection between LLM knowledge and description lengths?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Some limitations were mentioned in conclusion, though there is no explicit limitations section.

Thank you for your response

Thank you for your detailed responses to clarify details. I believe including these in the paper will greatly improve the readability of the paper. Despite some missing details which their inclusion will greatly improve readability, this is a solid paper and I am leaning towards positive recommendation.

Reply to all reviewers

As the discussion period ends soon, we briefly summarize the main review comments along with our responses. The reviewers have highlighted several key strengths in our research: * **Novel Approach**: All reviewers acknowledge and appreciate the novelty in our planning approach with LLM, particularly in its utilization as part of a search algorithm rather than using LLM solely as a policy. * **Better Performance**: Reviewers 3x3m, jShB, Mf2f, and euNw highlighted our method's superior performance over existing techniques in object rearrangement tasks. * **Comprehensive Evaluation**: Reviewers jShB and RKS5 appreciate our thorough evaluation, encompassing a broad range of tasks, including simple tasks, compositional tasks, and both in-distribution and out-of-distribution tasks. * **Insightful Ablation Study**: Reviewers 3x3m, jShB, RKS5, and Mf2f appreciate our ablation study and analysis for providing good insights into the effective components of our methodology and areas where there is room for improvement. We have made detailed responses to clarify the reviewers’ concerns: * One review (RKS5) misunderstood our paper’s main contribution and stated that our paper relies mainly on ideas from Li et al. [1]. Our research utilizes GPT-3.5 as a commonsense world model for model-based search with MCTS, while Li et al. [1] use behavior cloning to finetune GPT-2 as a model-free policy. There are fundamental differences between the model-based and the model-free approaches, conceptually and algorithmically. Details are presented in our global response. * **Domain and tasks in experiments**. We mainly solve object rearrangement tasks as it has many useful and practical purposes in daily life, and our experiments investigate a fairly large set of planning capabilities required in embodied AI. Virtualhome is also a well-established platform used in many prior works. See the full answer in our global response. * **Runtime performance**. Our study shows the trade-off between accuracy and efficiency and explores the feasibility of our approach. We also introduced various potential methods that could enhance the runtime performance, which is interesting for future research. See the full answer in our global responses. * **LLM’s world model v.s. LLM policy**. Reviewer 3x3m suggests we ground "LLM has more comprehensive knowledge about world modeling than policy" more firmly in experimental results. We conducted additional experiments about planning for air travel from a starting city to a destination city, which we analyzed in our introduction. Our preliminary result suggests that GPT-3.5’s world model + shortest path algorithm achieved 63.5% accuracy, higher than the 50.4% accuracy achieved by the GPT-3.5 policy. It is a side finding of our paper that supplements the central argument. See the full answer in our reply to the reviewer 3x3m. * **large belief state**. In the latest reply message, reviewer RKS5 misunderstood our point and stated that our method cannot scale up to a large state belief. Classical methods, such as PUCT (in Table 2, LLM-MCTS Uniform State Prior), struggle with large belief states. However, RKS5 seemed to miss out on the fact that we use LLM to provide a prior that effectively narrows down the belief space for search in a large domain, which is reflected in our ablation study (Table 2). This is a key contribution of our work that is clearly claimed in the paper. Details are in our reply message to RKS5. * **Code**. Reviewer RKS5 wishes to see our code. We have shared our implementation with the AC via a private message. [1] S. Li et al., “Pre-trained language models for interactive decision-making,” Neurips 2022.