Non-myopic Generation of Language Models for Reasoning and Planning

Authors: Chang Ma, Haiteng Zhao, Junlei Zhang, Junxian He, Lingpeng Kong
Primary area: foundation or frontier models, including LLMs
Keywords: LLM reasoning; agents; optimal control

Abstract:
Large Language Models (LLMs) have demonstrated remarkable abilities in reasoning and planning. Despite their success in various domains, such as mathematical problem-solving and coding, LLMs face challenges in ensuring reliable and optimal planning due to the inherent myopic nature of autoregressive decoding. This paper revisits LLM reasoning from an optimal control perspective, proposing a novel method, Predictive-Decoding, that leverages Model Predictive Control to enhance planning accuracy. By reweighting LLM distributions based on foresight trajectories, Predictive-Decoding aims to mitigate early errors and promote non-myopic planning. Our experiments show significant improvements across a wide range of tasks in math, coding, and agent-based scenarios. Furthermore, Predictive-Decoding demonstrates computational efficiency, outperforming search baselines while utilizing inference compute more effectively. This study provides insights into optimizing LLM planning capabilities.

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

Reviews and discussion:
<thread>
creation date:
1730386483783

thread_type:
official_review

<thread_object>
creator: reviewer_4xru

<content>
summary:
This paper presents "Predictive-Decoding," a novel optimal-control approach that enhances Large Language Models' planning and reasoning capabilities by leveraging Model Predictive Control to overcome the myopic limitations of autoregressive decoding. The method reweights LLM distributions based on foresight trajectories, demonstrating improved performance in math, coding, and agent-based tasks while being computationally more efficient than existing search-based methods.

strengths:
- The framework can work on different kinds of tasks.
- The method makes sense.
- Attempt to fair comparison on the effort to the number of tokens.

weaknesses:
- The proposed method is not particularly fancy; the Lookahead Search in [1] presented an almost identical approach.
- The paper lacks comparison with the latest search algorithms, such as BFS-based TOT and A*-based Q*[2]. The authors should have included comparisons with these SOTA algorithms in the experimental section.
- The paper needs more discussion on results based on different rewards (Self reflection/Reward model). There seems to be a lack of details regarding the evaluation steps in the search process.
- Many existing papers have suggested that LLMs do not inherently possess self-reflection capabilities. This paper lacks detailed experimental discussion regarding self-feedback abilities.

[1]Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters

[2] Q*: Improving Multi-step Reasoning for LLMs with Deliberative Planning

questions:
- Differentiate between the mentioned Lookahead Search and explain what makes Predictive-Decoding unique. 
- Additional experimental results are needed: provide more detailed comparison with TOT and Q*.
- More specifics about the evaluation process during decoding.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730471305619

thread_type:
official_review

<thread_object>
creator: reviewer_2bkh

<content>
summary:
The paper addresses the problem of myopia (short-sightedness) in Large Language Models (LLMs) during reasoning and planning tasks. It proposes a novel method called Predictive-Decoding, which leverages Model Predictive Control (MPC) to mitigate early errors and enhance non-myopic planning. By re-weighting the LLM distributions based on foresight trajectories, the method aims to improve planning accuracy. Extensive experiments demonstrate significant improvements in performance across various tasks, including math problem-solving, coding, and agent-based interactions. The proposed method shows computational efficiency, outperforming search-based baselines with reduced computational resources.

strengths:
- The application of Model Predictive Control to mitigate myopia in LLMs is a novel approach that enhances planning accuracy.
- The paper provides a solid foundation and supports the claims with experimental results.
- The paper is well-organized, with clear explanations of the problem, methodology, and results.

weaknesses:
See questions

questions:
Failure Cases: Can the authors provide more insights into the specific scenarios where Predictive-Decoding may fail or perform sub-optimally? What are the common characteristics of these failure cases?

Broader Applicability: Have the authors considered testing the method on more open-ended tasks, such as advanced data analysis or complex decision-making scenarios? 

Parameter Sensitivity: Can the authors provide more details on the sensitivity of the method to different hyperparameters (e.g., foresight length, sampling number)?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730652239767

thread_type:
official_review

<thread_object>
creator: reviewer_ihg8

<content>
summary:
In this work, authors propose Predictive-Decoding, a training-free approach to improve LLM planning with non-myopic generation, based on their claim that focusing solely on historical information can lead to irreversible mistakes and potential planning failures. Targeting at the myopia issue in language models pretrained with next-token prediction, Predictive-Decoding leverages Model Predictive Control to enhance planning accuracy.

strengths:
1. investigate an important problem, i.e. short-sightedness.
2. Good performance-budget balance in experiments.

weaknesses:
1. case study? (focusing solely on historical information can lead to irreversible mistakes and potential planning failures.)
2. The formulation in lines 126-127 is not a POMDP, and lacks of mapping from global states to local observations. 
3. I'm concerned that the author's hypotheses in lines 188-191 are untenable. It seems like saying that "the more confident the answer is for a given model, the more likely it is to be correct." and in this case the greedy answer should usually be selected?

questions:
See the Weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1730853827737

thread_type:
official_review

<thread_object>
creator: reviewer_fxex

<content>
summary:
This paper looks at LLM planning and reasoning from an optimal control perspective and proposes a novel method to enhance planning accuracy. The authors argue that LLMs face challenges in reliable and optimal planning due to their inherent myopic nature of autoregressive decoding. Predictive-Decoding leverages Model Predictive Control to re-weight LLM distributions based on foresight trajectories, aiming to mitigate early errors and promote non-myopic planning.

strengths:
1. The idea of making the LLM to think long term (non-myopic) makes sense for LLM planing and reasoning
2. The author seems to perform different experimentation on different test-beds.

weaknesses:
1. the presentation of this paper could be improved (for instance fig 1 is too many figures/text, could you make it simpler)?
2. the introduction of "Myopic Gap" seems to be interesting, but the section could be rewritten for better readability. 
3. lacking larger llm model size for math and gsm experimentation.

questions:
1. how does the number of FLOPS related to # of tokens? And also to the actual decoding/inference time?
2. how sensitive in the sampling temperature in determining the optimal solution parameter? Do you have to tune this for each test-beds?
3. it seems the diversity is still an issue even in the MPC problem right? how would you solve it?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732166845966

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Updated Manuscript and Response to All Reviewers

comment:
We sincerely thank all the reviewers for their feedback and constructive comments. We are pleased that the reviewers recognize the novelty and importance of non-myopic generation for LLM planning (R#1, R#2, R#3) as well as the solid/nice results across comprehensive tasks (R#1, R#2, R#3, R#4). In response to the reviewers’ comments, we have conducted three additional experiments (including one additional LLM, two search baselines, and an analysis) and revised the manuscript accordingly. **All changes are highlighted in blue in the updated PDF**. The updates are summarized as follows:

1. **Figure 1:** Revised the main figure and selected an example with less text. (R#1)
2. **Section 2:** Replaced the POMDP process with a decision process to avoid confusion. (R#2)
3. **Sections 3.1 & 3.2:** Added an explanation for the myopic gap formulation (R#1) and provided a more detailed analysis of the results.
4. **Section 4:** Included additional details about the evaluation process. (R#4)
5. **Section 5.2, Table 4:** Added results for Llama-3-70b on GSM8K and Math. (R#1)
6. **Section 5.3, Table 8:** Included results for A* search and Tree of Thought. (R#4)
7. **Appendix C:** Added an analysis of self-reflection abilities. (R#4)
8. **Appendix E.1:** Conducted a case study to illustrate how myopic generation leads to planning failure. (R#2)
9. **Appendix E.2:** Added an analysis of failure cases. (R#3)

We have addressed the queries and suggestions raised by each reviewer in detail and provided clarifications where necessary. We greatly appreciate the reviewers’ valuable contributions, which have helped us improve the quality of our manuscript. Should further clarification be required to assist in advancing our score, please do not hesitate to let us know.

Thank you once again for your thoughtful review and feedback!
</content>
</thread_object>

</thread>
<thread>
creation date:
1732488638993

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
A Kind Reminder for Reading the Response

comment:
Thank you again for your comments! We have added many revisions to address your concerns. Since the rebuttal period is closing very soon, can you please check the response to see whether it mitigates your conerns? We would greatly appreciate that!

Thank you,

The Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
LLMs face challenges in ensuring optimal planning due to their inherent myopic nature of autoregressive decoding. Motivated by these challenges, the authors propose a novel method Predictive-Decoding inspired by model predictive control (MPC) to mitigate early errors and enhance planning accuracy.

Although the presentation of the original version is unclear to some extent and lacks comparisons with current search methods, this paper presents an intuitive integration of MPC with LLM. The authors offer an interesting method supported by experimental results, including failure cases, and the authors' response addresses most of the reviewers’ questions.