Non-myopic Generation of Language Models for Reasoning and Planning

W3&Q3: More specifics about the evaluation process during decoding.

We tested on two different evaluation settings in this work:

• Using LLM self-estimation of foresight steps to guide action resampling. This setting uses LLM probability for evaluation, which calculates the length normalized probability of all tokens within current step and T0 future steps. (Table 3-5)

• Using an external reward to guide generation. We tested two different kinds of reward, designed-heuristics for agent tasks(Table 7), as well as a reward model, math-shepherd for math tasks (Table 8 & Figure 6).

We revised the manuscript in Section 4 to clarify the evaluation process.

W4: Many existing papers have suggested that LLMs do not inherently possess self-reflection capabilities. This paper lacks detailed experimental discussion regarding self-feedback abilities.

As aforementioned, our work is not focused on improving self-reflection capabilities of LLMs. However, for agent tasks, the model indeed involves taking observation and error messages from the environment and fixing the plans. We add an analysis of step-level self-reflection for AlfWorld and PDDL in the revised manuscript Appendix C, following [1][2].

As shown in Figure 11, Predictive-Decoding exhibits continuous improvement across 20 steps. For the AlfWorld task, Predictive-Decoding shows a larger slope across 20 steps, showcasing improved self-reflection ability compared with Act and ReAct. For the PDDL task, however, Predictive-Decoding shows only comparable self-reflection ability with Act. Notably, on both tasks, Predictive-Decoding shows larger improvement at later steps, which indicates improved long-range self-reflection ability.

[1] Xu, Yiheng, et al. "Lemur: Harmonizing natural language and code for language agents." ICLR (2023).

[2] Ma, Chang, et al. "AgentBoard: An Analytical Evaluation Board of Multi-turn LLM Agents." NeurIPS (2024).

Thank you for your careful review and constructive comments.

At the high level, we would like to first clarify several terms. Predictive-Decoding is a search-free algorithm, in that for each step we directly generate the next action and do not keep other options for backtracking as in the search-based algorithms. Furthermore, self-reflection represents a separate direction from our experiment settings, as we aim to directly improve planning accuracy by avoiding mistakes, rather than incorporating reflections to fix mistakes. These two methods in improving planning are distinct from each other

These guide our methodology and experimental design. We focus on evaluating direct action generation quality rather than advancing search methods or reflection-based improvements.

We have revised our manuscript to incorporate your valuable suggestions, including:

• add baselines TOT and A* search in Table 8.
• add more details of the evaluation process in Section 4.
• add a self-reflection ability analysis in Appendix C.

We address the concerns below:

W1&Q1: The proposed method is not particularly fancy; the Lookahead Search in [1] presented an almost identical approach. Differentiate between the mentioned Lookahead Search and explain what makes Predictive-Decoding unique.

Lookahead Search, introduced in [1], primarily performs rollouts 𝑁 steps ahead and uses a process reward model to score the lookahead generation. This score is then used to guide beam search. Predictive-Decoding incorporates several design elements different from Lookahead Search:

• We use a sampling-resampling algorithm to select an action, which allows for temperature configurations to implement trade-offs between more local or global generations.
• Predictive-Decoding is search-free, selecting only one action at each step. This aligns with the principles of model predictive control in its design, whereas Lookahead Search, as mentioned in the paper, is representative of MCTS-style methods.
• Additionally, Predictive-Decoding introduces trajectory recycling to improve sampling efficiency.

Moreover, we observed an interesting difference in the experimental findings between the two papers. As shown in Figure 3 of [1], Lookahead Search exhibits worse inference scaling relative to beam search and weighted best-of-N. In contrast, our experiments in Figure 6, which also analyze inference scaling laws using the same reward model, Math-Shepherd, reveal different trends. Our method demonstrates strong performance-efficiency trade-offs under similar experimental conditions. While a direct implementation comparison is not feasible at this time (we are awaiting an open-source implementation of Lookahead Search), these differing results suggest potential advantages in our design approach.

Although incorporating foresight is also explored in contemporary work, our method is unique in proposing a well-performing recipe for non-myopic generation.

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

Thank you for the author's response, which addressed most of my concerns. I will increase my score.

Thank you for your constructive review as well as appreciation of our work! Thanks to your proposal, we added a failure case analysis section in Appendix E.2.

We address the questions below:

Q1: 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?

This is a great suggestion! We add a study of failure cases in the revised manuscript. Please refer to section Appendix E.2

We notice several characteristics of these suboptimal cases where the non-myopic generation is worse than myopic generation:

• Repetition of in-context examples: Several failed cases in the MATH dataset exhibit repetition of in-context examples within the answers to unrelated questions. This is possibly because improving the overall confidence of generation can sometimes lead to repetition, as the model tends to yield high confidence when copying from in-context examples. This issue accounts for 1% of the incorrect examples in the MATH dataset. However, this phenomenon does not occur in other datasets, likely due to the inherent difficulty of the MATH task.

• Token Level Typos: A few failed cases in GSM8K dataset shows minor spelling mistakes in variables, resulting in failed execution. For example, raymond_jewels -> raymond_jews. This is due to the averaged probability calculation at the step level may ignore token level mistakes. However, as LLM rarely makes these mistakes, these cases are rare.

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

This is great advice. The current decision-making tasks we tested are mostly fully-observable tasks, where the outcomes of actions are easier to anticipate. AlfWorld, however, is a partially-observable task, making the results more difficult to predict, and the world model is more prone to hallucinate. Nevertheless, we find that even with imperfect future estimation (see hallucination analysis in Appendix C), the model still benefits from foresight.

We plan to test more partially-observable agent tasks to analyze the stability of foresight in more complex decision-making scenarios, including tool use and web browsing. We will include these in later revisions, although this may take longer than the rebuttal period.

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

Our method involves altogether four hyperparameters: foresight length, sampling number, as well as two sampling temperature ($\alpha$ and $\tau$).

We provide a detailed analysis of foresight length and sampling number in Table 6 Section 5.2. Generally, this algorithm is sensitive to foresight lengths. Performances on both GSM8K and HumanEval significantly improve with longer foresight, which determines the level of non-myopia in generation.

Increasing sampling number K leads to better performances as it could give a more accurate account of the original generation distribution. However, trajectory recycling significantly improves the sampling efficiency. Thus this hyperparameter affects performance less than foresight length.

For sampling temperature, please refer to our response to Reviewer fXex Q2. Generally, action sampling temperature $\tau$ significantly impacts performance, as it also controls the tradeoff between more local/global generation.

Thank you for your thoughtful review!

We have revised our manuscript to incorporate your valuable suggestions, including:

• adding a case study to illustrate the specific kind of planning failures in Appendix E.1
• revising the confusing term POMDP

W1: case study? (focusing solely on historical information can lead to irreversible mistakes and potential planning failures.)

We add a dedicated example in Appendix E.1 to illustrate the phenomenon. In the case, the agent needs to finish the goal “look at bowl under the desklamp”. At the beginning, the agent is exploring the surroundings to look for a bowl. It arrives at shelf 1, where there is only a cellphone and a creditcard. The agent picks up the cellphone despite given instructions that it needs to find a bowl. As the agent can only carry one thing at a time, it became stuck when it actually finds a bowl and found it has no arm to carry. Therefore, this case results in a planning failure due to the tendency of models to perform history-consistent completion of the next action.

We also show that after using Predictive-Decoding, this task could be successfully completed.

W2: The formulation in lines 126-127 is not a POMDP, and lacks of mapping from global states to local observations.

Thanks for pointing it out. We use the notation "POMDP" following [1][2], which differs from common MDP processes in that the agent takes observations of the world to make decisions, rather than directly relying on the state. This aligns with our setting involving LLM agents; however, we agree that it may seem confusing, especially as we also introduced reasoning tasks.

To address this, we have revised the manuscript to use a more general description, replacing "POMDP" with "decision process."

[1] Xie, Tianbao, et al. "OpenAgents: An Open Platform for Language Agents in the Wild." COLM 2024.

[2] Xiong, Weimin, et al. "Watch Every Step! LLM Agent Learning via Iterative Step-Level Process Refinement." ACL 2024.

W3: 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?

We want to clarify that greedy autoregressive generation does not produce the most confident answer (i.e., a sequence) as scored by the LLM (maximum log P). Instead, it only generates the most confident token at the current generation step. As shown in Figure 2, around 60% of the samples yield more confident answers through non-myopic generation, illustrating that greedy answers are not always selected when aiming to find the most confident answer.

Moreover, the hypothesis proposed in lines 188–191 suggests that: 1) LM next-token prediction is entirely myopic, and 2) LLMs, however, could internally perform non-myopic generation due to their extensive pre-training. We aim to discuss whether LLMs can perform non-myopic generation effectively; however, our analysis suggests otherwise.

Q2: how sensitive in the sampling temperature in determining the optimal solution parameter? Do you have to tune this for each test-beds?

Sampling temperature is important for performance. We have two sampling temperatures involved in our algorithm, the action selection temperature $\tau$, and the LLM generation temperature $\alpha$. Generally the algorithm is sensitive to both parameters, as we report below. However, we note that we do not tune them for each test-beds, we tune the parameters when using a new LLM or when a new type of task is present (math, coding, agent).

The action selection temperature $\tau$ reflects the balance between local and global confidence. When $\tau=\infty$, the decoding results are exactly the same as autoregressive generation, while $\tau=0$ denotes that the exact maximum value of the global confidence is chosen. Most LLMs and reasoning tasks are very reliant on global confidence. Therefore the best $\tau$ is often close to 0.

In practice, tuning of $\tau$ is dependent mainly on the model. This is due to different models are different in terms of myopia, e.g. Deepseek-coder is less myopic compared to Llama3. The optimal configuration for all models and tasks are shown in Appendix Table 10.

$\alpha$ reflects basic LLM ability and sampling diversity. Normally, we use a balanced value for $\alpha$: between 0.6-1.0.

To better illustrate sampling temperature sensitivity, we report results on 2 different tasks. A curve illustrating sensitivity is also available in Figure 5.

We can see for both tables, a too large $\tau$ results in significant performance drop and a small $\tau$ yields good results for both math and reasoning. However, the optimal configurations of $\alpha$ slightly vary across models.

Q3: it seems the diversity is still an issue even in the MPC problem right? how would you solve it?

Generation diversity for reasoning tasks is a challenging issue for most algorithms. However, diversity is not undermined but improved with our method due to sampling twice. Please refer to lines 427-430 and Figure 5 for detailed analysis.

Thank you for your careful review and constructive comments.

We have revised our manuscript to incorporate your valuable suggestions, including:

• Presentation of Figure 1 and Section 3
• Additional results on larger LLM model size for math tasks.

We address the concerns below:

W1: the presentation of this paper could be improved (simplify Figure 1)?

Thanks for your suggestion! We have updated Figure 1 in the revised manuscript.

W2: the introduction of "Myopic Gap" seems to be interesting, but the section could be rewritten for better readability.

We have rewritten Section 3 in the revised manuscript, providing more detailed explanations and a more comprehensive analysis of the results.

W3: lacking larger llm model size for math and gsm experimentation.

Thanks for your suggestion. We add additional experiments for a larger LLM, Llama3-70B on MATH and GSM8K tasks. On both tasks, Predictive-Decoding surpasses myopic generation. MATH tasks show 5.4% improvement, and GSM8K shows 3% improvement, indicating a smaller yet significant improvement from non-myopic generation on stronger models. We have also added the results of Llama3-70B to Table 4 of the paper.

Q1: how does the number of FLOPS related to # of tokens? And also to the actual decoding/inference time?

The number of FLOPS directly correlates with the average number of generated tokens during inference. The calculation of FLOPS is $6nP$, where $P$ is the number of parameters within the LLM, and $n$ refers to the number of tokens generated. This calculation process follows [1][2].

[1] Kaplan, Jared, et al. "Scaling laws for neural language models." (2020).

[2] Wu, Yangzhen, et al. "An empirical analysis of compute-optimal inference for problem-solving with language models." (2024).

The actual decoding time is dependent on the inference architecture. For an inference framework without any acceleration, FLOPS reflects the actual decoding time. However, we use vLLM for implementation which supports batch-wise parallel decoding and prefix caching. The three algorithms are supported differently with vLLM acceleration:

• Autoregressive: batch decoding (vLLM supported)
• Beam Search: batch decoding + prefix caching (vLLM supported)
• Predictive Decoding: step-level batch decoding (our implementation)

Here is the calculated actual decoding time v.s FLOPS on HumanEval with Llama3-8B.

We implement Predictive Decoding parallel inference such that all samples within the batch calculate the next step based on foresight, and then the entire batch proceeds to the next step together. While Predictive Decoding appears slower in the table, we emphasize that the runtime largely depends on the implementation. Currently, Predictive Decoding is not well-optimized because vLLM does not yet support prefix caching. We plan to adopt vLLM's implementation of beam search to further accelerate Predictive Decoding with prefix caching in the future.