Non-myopic Generation of Language Models for Reasoning and Planning
Authors: Chang Ma
Haiteng Zhao
Junlei Zhang
Junxian He
Lingpeng Kong
Venue: ICLR 2025 Poster (2025)
Keywords: LLM reasoning; agents; optimal control
Primary area: foundation or frontier models, including LLMs
TL;DR: We aim at improving the optimality of LLM reasoning and planning by introducing a non-myopic generation method.

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.

Published as a conference paper at ICLR 2025
NON-MYOPIC GENERATION OF LANGUAGE MODELS FOR REASONING AND PLANNING
Chang Ma
Haiteng Zhao
Junlei Zhang Junxian H Lingpeng Kong**
"The University of Hong Kong Peking University Zhejiang University
Westlake University {cma, 1pk) hku. ak, junxianh@cse ust.ts .kk
*The Hong Kong University Science and Technology
ABSTRACT
Large Language Models (LLMs) have demonstrated remarkable abilities in reason- ing and planning. Despite their success various domains, such as mathematical problem-solving and coding, LLMs face challenges in ensuring reliable and opti- mal 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 fore- sight trajectories, Predictive-Decodin 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, Predietive-Decoding demonstrates computational efficiency, outperforming search baselines while utilizing inference compute more effectively. This study provides insights into optimizing LLM planning capabilities. Code is available at this repo
INTRODUCTION
Large Language Models (LLMs) extensively pretrained on large corpus predict the next tokens. Models like GPT-4 (Achiam et al. 2023) have demonstrated a capacity for step-by-ster reasoning and planning, breaking down complex problems into sequential steps that progressively lead to solutions (Wei et al., 2022). This sequential planning capability has led to significant advancements in mathematical problem-solving (Cobbe al. 202T) and programming tasks (Chen al., (02T).
It has also enabled essential applications such as tool use (Qin et al. (202)) and the development of LLM agents (ao al. 2022). Consider scenario where an agent is tasked with cooking a meal:
given instruction like "Put salt on steak" and an initial observation such as "There is a shelf in front you," the LLM assigns the highest probability to the most appropriate action. After executing this action, the LLM generates subsequent actions, each building upon the previous steps. This process creates a sequential chain actions that advances toward task completion, guided by continuous interaction with environmental observations:
pl "Go to the shelf." | "There is a shelf in front of you.") pl "Pick up the saltbotile." "Go to the shelf. A saltbotile is the shelf"")
where "A saltbottle is on the shelf" is the new observation after going to the shelf. This iterative process continues until the specified goal state is achieved. However, this autoregressive decoding process could easily lead to irreversible errors, as LLMs tend to follow the most natural local follow- ups. For instance, given a different observation "A spice bottle is on the shelf", the LLM is likely to generate actions "Pick up the spice bottle" followed by "Shake the bottle over the steak". Such a sequence of actions totally conflicts with the intended instruction "Put salt on the steak". This contrasts with reinforcement learning paradigms, which use reward-based training teach models to anticipate long-term action consequences and learn optimal decision policies (Silver et al.] 2014). The sight-iight LLMs raises critical questions about their planning capabilities: (i) Can an LLM proactively avoid erroneous steps without necessitating their occurrence? (ii) What is the degree of optimality achievable in LLM-basee planning strategies?
Equal advising.

---

Published as a conference paper at ICLR 2025
Planning Challenge: Your gool is to "Examine an alarmclock with the desklamp".
Stop
Step Pickup coliphone
Step to
Stop Pickup olarnclock
free has aiready bost mude Too latel
Errar: Action Cannot
X
Myapic Reasoner
6.02: Hamax Canso
0.89, Wrong
LLM: 0.91, Humas: Wrong
ULM: 0:43, Humar Wrong
Rescale actinn prababiity with global correctness
Stop
Step 2: Pickup caliphone
Foroiihht
LUM 0:43
Step Pickup koychotn
Step Foresigtt
ILWI 0:45
Probesbiity
Prodictive Dacoding
Step 2: to udetoble 2 Step Foresight
Picksp callphass
Fickap leychals
On Sidanable
Correctooss
Figure The illustrative overview of Predictive-Decodee Decoding on one ALFWorld example. LLM autoregressive planning often suffers from near sight. Predictive-Decou rescales LLM generation distribution based on evaluation of foresight, enabling non-myonn con-myopic planning.
To investigate the causes and extent of myopia (short-sightedness) in LLM planning, we refer to optimal control theory (Qin & Badgwell 1997). Optimal planning is framed as a combinatorial opti- mization problem aimed at maximizing goal achievement through 7 steps of actions (a1, 02.--.. .. ar)) Model Predictive Control (MPC; Camacho et al.) (007) outlines the optimality condition for LLM- like planners sequential planning must be non-myopic, which requires the anticipation of future outcomes in addition to considering past actions, represented as p(a, (t. History, Future). Conversely, focusing solely on p(a,] History) can lead irreversible mistakes and potential planning failures. Recent studies (Shih et al. 2023 Bachmann & Nagarajan 2024) have observed myopia in language models pretrained with next-token prediction. Our research further reveals that even in advanced LLMs like am3-3 (Dubey et al. 2024), more than half of the reasoning processes on popular math tasks demonstrate a lack of global awareness, with myopia being particularly pronounced in incorrect instances (33.1). Additionally, LLMs initially do not seem sensitive to mistakes; however, errors accumulate during multi-step planning and become increasingly noticeable over several steps ($3.2). These findings emphasize the importance of thinking with foresight.
To address this, we propose Predictive- Predictive-Decoding. Decoding, a training-free free approach to improve LLM planning with non-myopic generation. Predictive-Decodee
re- re-weigghs LLM distribution based the closed- form solution in Model Predictive Control (Bq. ( such that sampling from the re-weighted solution is approximately solving planning with global-optimality. For each step d₁ Predictive-Decoding samples multiple foresight trajectories (0z, 0t-11-....... (t+To) and rescales the original generation distribution based on the evaluations of foresight trajectories. Best action de sampled from this Extensive experiments on math, coding, and agent tasks show notable improvements. For example, without using any additional supervision, we achieve a 7.2% improvement on GSM8K (Cobbe et al. [02I] and 25.3% improvement on AlfWorld (Shridhar et al. (02T) accuracy over ReAct (Yoo al. 2022). It requires no special prompt design and preserves generation diversity.
distribution. An overview is illustrated in Figure [
Furthermore, Predictive- Decoddng utilizes inference compute more effectively than other planning approaches. Previous methods have implemented various techniques to enhance planning, such as repeated sampling (Wang et al. 2022) and searching algorithms (Yao et al. 2024) Xie et al. 2024]] Hao
et al. 2023 Zhou al. 2023). While these methods improve performance, they often require significantly higher computational resources, resulting in sub-optimal
cnapuutttion-erfomman trade-offs (Snell et al. 2024 Wu al. 2024b). In contrast, Predictive Predictive-Decodingg adopts a "no-regrets" approach that optimizes sequentially and simplifies the solution space, avoiding the exponential growth associated with iterative planning methods. This efficiency is reflected in our inference scaling law results with a fixed LLM and reward model, where Predictive-Decodii superiority over all state-of-the-- Predictive- Predictiv-Decoding outperforms MCTS (Hao et al. [023 by 2.4% and Guided Decoding (Xie et al. 2024) by 1.4%, while utilizing 50% of the FLOPS, demonstrating its effectiveness and efficiency.
achieves Pareto (SOTA) baselines (55.4). Specifically, on the GSM8K benchmark.
2 PROBLEM FORMULATION. AN OPTIMAL CONTROL VIEW
One of the fundamental problems in decision decision-making is whether we can solve a long-term goal step by step QQn & Badgwell] 1997). Traditionally, reinforcement learning approaches have relied on
2

---

Published as a conference paper at ICLR 2025
Table 1: Non-iterative planning is efficient and suitable for closed-loop settings. Iterative planning, though better for global optimal decisions, is slow and impractical for realistic agent tasks. Predictive- Decoding combines the best of both. Advantages include: lobal- Optimally of solution, Salinng to long-range planning. p fficiency, and losed-Loop Interaction.
Decision Making
Paradigm Hlustration
Representative Methods
Type
Advanlage
Solution
Self- Self-Consistency (Wang et al.
2022
Sample
Tree-of-Thought T30 crai
2025
Search
Herativv Planning
Solution
Guided-Decoding (Xre al
Search
Monte Carlo Tree (Hab
(Hab
2023
Search
Bed Solution
Reflexion (Shinn air 2074
Prompt
Chain-of- (Wei ct al
2022
Sample
Sequential Planning
Best Solation
ReAct (Ya enall 2022
Sample
Predictive-Doodinng (Ours)
Sample
G
e
multiple iterations training (Silver et al., 2014)) and searching (Silver et al. (0177) to achieve optimal results. However, recent advancements demonstrate that LLMs possess the capability for sequential planning (Wei al. [022). Sequential planning can achieve optimal outcomes non-myopic, while also offering other benefits, shown in Table [ In this section, we first outline the context of the problem and reconsider LLM planning from the perspective of trajectory optimization.
Planning as Trajectory Optimization We consider Decision Process defined by tuple (g, A,A, A,7, T, R), with goal g. state space S, valid actions space A, transition function T S A S, and r(s, alg) R* is the reward function that measures how well each step aligns with the goal (with the goal dependency omitted for simplicity). Global-Optimal Planning aims to find an action sequence that maximizes cumulative reward over a set number of steps. We model this as Trajectory Optimization process: find sequence of actions ao:T that maximizes an objective J (Return) factorized over per-timestep rewards (St, ae) over a planning horizon with I steps:
T
max_ (so, ) Bu:T
Σ ast,
subject to Sc. as), V [0,
Conversely, Myopic Planner maximizes the return shorter horizon. For instance, a planner that maximizes the immediate reward at current step, i.e ag = moaxa,r(S,,. at), is myopic, while non-myopic planning works towards global-optimality
Previous approaches to trajectory optimization follow a straightforward intuition: using large language models (LLMs) to generate diverse trajectories through sampling or search, and then selecting the
best one (Wang et al. 2022. Yao et al. [2024] Hao et al. 2023 Xie et al.) 2024 Shinn et al. 2024). However, significant drawback is the exponential growth of the solution space. Each action step offers |A] possibilities, leading to [A|" potential solutions after T steps. Despite attempts to prune trajectories and accelerate search (Zhuang et al., 2023; Wang et al., 2024a), most iterative planning methods are either mone-connniing or perform poorly with limited iterations (Chen et al. (024b). Additionally, iterative methods are often unsuitable for closed-loop scenarios, where agents interact with their environment in real-time, each decision alters the environment and is irreversible.
Sequential Planning with Model Predictive Control Model Predictive Control (Qin & Badgwell 1997) introduces different paradigm for planning: instead of optimizing an entire action sequence aor at once, this method selects the best action at each timestep d ... ai, fixing each as it progresses and then optimizing the subsequent steps. This transforms Eq. [ a series of optimization problems, each with linear size solution space [.A]. The colors denote: the current action to decide 0r, history,
and future.
a6 arg max 4g
max J (s": ( ag. 01 oT)
Tail Subproblem
af arg max
max
I (s o/: 01
ar)
(2)
ag...,ay
af = arg max [J (s", 10,,ahT-1:00 aT)
Cr
3

---

Published as a conference paper at ICLR 2025
This method requires two steps: first, for each action de, compute the maximum future outcomes (tail subproblem), and then select the action that yields the best future outcomes. Model Predictive Control can also use sampling for inference, but it improves sampling efficiency in two folds: the solution space for each equation is linear and the size of the tail subproblem is reduced after each step. We further provide sample efficiency theoretical analysis and simulations in Appendix [B.
LLM Autoregressive Planning Solving Eq. i challenging We need to identify an action that achieves the best outcome after T steps. LLM provides straightforward solution this problem: leverages its extensive knowledge to anticipate the next best action, dy for achieving the goal. This method can be formalized as:
d/ = arg max PLLM (aol (S))
do
df = arg max PLLM (a1 So, 4()
(3)
dr arg maaamaaaiiii PLLM (aT So, 1
This approach is widely adopted in LLM reasoning and planning, encompassing (CoT: Wei et al. 2022). ReAct (Yao et al. 2022). and Voyager (Wang el al., 2023a). Research has demonstrated that with carefully designed prompts and in-context examples, LLM autoregressive
planning can achieve competitive performance in various tasks (Cobbe et al. 2021 Chen et al. 2021
Shridhar al. 2021). We further investigate whether LLM autoregressive planning global-optimal.
DIAGNOSING THE DEFICIENCY OF LLM PLANNERS
Comparing Eq 3 with 2 we observe that LLM- --Mdddaeddda action selection time step differs from the optimal control approach. Instead of maximizing future outcomes in the tail subproblem, LLMs select actions based on the immediate conditional probability arg max,, pL.M (at S d/ Consequently, the optimality of LLM planning hinges on two hypotheses: (1) Non-myopic: LLMS inherently plan ahead, with current step probabilities accounting for the success of future steps. (2) Evaluation capability; The probability distribution in LLMs can effectively substitute for J. distinguishing successful trajectories from failed ones. In the following sections, we will examine and investigate the validity of these two hypotheses.
3.1 FINDING 1: LLM AUTOREGRESSIV PLANNING IS MYOPIC
We begin by investigating whether LLMs inherently plan ahead. While next-token prediction is typically greedy, evidence suggests extensive pretraining might enable LLMs to implicitly plan future tokens (Wu et al. 2024a). We therefore intends to measure whether current LLMs have such ability. We define a metric "myopic gap" to probe whether LLMM could plan ahead: a myopic LLM planner would fail to find the optimal trajectory within its distribution.
Definition 3.1. (Myopic Gap for LLM Planning) Given language model with distribution
P(ag, 01,.................. ...ar) .,,,), let P be the support set of the distribution. a/e are generated autoregressively following Eq. Then the myopic gap for planning is:
p' max P(as, 01, (1,...,rr) ar) P(d.. .f.) RoTEP
(4)
p" represents the accumulated difference between PLLM (a.) history future) and PLLM history) at all steps. A positive gap (p" 0) indicates that the LLM's action selection is myopic for at least one intermediate step, while p" = 0 proves consistent global-awareness during planning. Here we include small margin (p" 0.01 myopic) discriminate myopic and non-myopic cases.
We empirically calculate the myopic gap of 1,1 ama 3- 8B on two challenging reasoning tasks, GSM8K (Cobbe et al., 2021) and MATH (Hendrycks et al. (021). We ensemble the generation of token-level Beam Search (Freitag & Al-Onaizan 2017) and Predictive Decoding (detailed in $4) as
Fach token within of is generated based the highest current probability; express this at the action level for brevity.
4

---

Published as a conference paper at ICLR 2025
223
Wrong
Wrong Contect
Wrong
Correct
Overall
223
GSM8K
11:3
Myopic
Non-myophe
89
401
490
Densi
Myopic Rate
76.5%
57.35
62.8%
MATH
Myopic
2172
785
2947
Non-myoopc
1341
702
2043
Myopic Rate
61.8%
52.7%
59.1%
Myopic (GSSMBK)
8.00
145
Myopic Gap pr (MATH)
636
835
330 815 3.0
Figure 2:
Myopic Gap distribution for correct and wrong samples (drawn with kde-plot). Myopic examples are defined as p" > 0.01. Wrong samples show a higher myopic rate on both tasks.
the non-myopic target. Results in Figure 2 show that around 60% of all examples show are myopic. Additionally, correct samples are often less myopic, while 76.5% of GSM8K errors and 61.8% of MATH errors occur when LLM planning is myopic. Correct samples tend to have smaller gaps, this motivates us that optimizing generation towards non-myopic may lead to improved results.
3.2 FINDING 2: LLM STRUGGLES TO IDENTIFY MISTAKES IN PLANNING EARLY
In this section, we explore another bottleneck in LLM sequential planning: Can LLMs evaluate intermediate steps and identify mistakes early on?
We perform an LLM score calibration analysis by com- paring LLM evaluations of intermediate steps with ground truth human annotations. We collect samples of trajec- tories agxr, / (0,T) and use the LLM to evaluate these trajectories PLLM (oo, Q1..... at). GPT-3. 5urbbo is used to evaluate trajectories on the agent task AlfWorld, while -1ama3-33
0.975
MLM Scote
Conrect Stose Score Doncity
0.925
0.900
0.875
evaluates steps of the GSM8K trajec- tory. The L.M score for Ilama3 is calculated using L.IM probability, and the score for proprietary GPT-3.5 is ob- tained through prompt-based self-evaluation (Xie et al.) 2024). Human annotators label each step in the AlfWorld trajectory with scores from 0, 0.25, 0.5, 0.75, 1, where O indicates that the task is unlikely to be completed and indicates high likelihood of successful completion. Each step in the GSM8K trajectory is labeled as either Correct or Incorrect following Lightman et al. (2023).
Step
Figure 3: In GSM8K, the first incorrect step's 's average score is among correct steps, but not after few steps.
As shown in Table 2 5--rrb could barely estimate intermediate progress simply with the current trajectory age, with only م = 0.133 correlation to human ground truth and Calibration Error 065. However, after given future trajectory (foresight of 3 steps), LLM evaluation improves. This is in line with previous observations (Uesato et al. 2022] Lightman et al., 2023) that LLMs are more natural at evaluating complete trajectories, rather than intermediate actions.
The evaluation of intermediate steps for Llama3- BB on GSM8K shows a calibration error of 0.332 when compared to human ground truth. We observe that incorporating foresight into the evaluation could help avoid early mistakes. As shown in Figure 3 the score for the first incorrect step falls within the high-density region of correct step scores but becomes easily distinguishable from correct steps after few iterations. Consequently, the GSM8K calibration score decreases to 0.323 when foresight of three steps is applied (detailed in Table 2 However, the correlation does not improve, as the scores of positive steps slightly drops, leading to some overlap with ambiguous incorrect steps.
Table 2: LLM Score Calibration vs. Human Ground &ruth for AlfWorld uses a 0.5 threshold for binary classification.
Calibration Error ECF (wo. Foresight)
Calibration Frvor ECE (w. Foresight)
Comelation (wo. Foresight)
Correlation (w. Foresight)
Task
Model
AlWooldd GSMSK
GPT-3.5-TURBO
0. 0.165* 0.332
0.108* 0.323
0.291 0.376
LLAMA-3
0.417
5

---

Published as a conference paper at ICLR 2025
4 BEYOND MYOPIC GENERATION FOR BETTER PLANNING
Our findings presented above highlight critical issues with current LLM decoding methods, partic- ularly their tendency toward myopic planning. In this section, we introduce Deccoding which follows MPC principles to reduce myopic planning in LLMs. The pipeline is introduced in following sections and the pseudocode is presented in Algorithm
4.1 PREDICTIVE-DEECOIIG
Our decision-makee strategy draws inspiration from model predictive control (MPC) (Qin & Badgwell 1997). It solves the I' sub-optimization problems (Eq. 2 and addresses myopia with foresight. Here in order to ensure non-myopic planning, our main objective is to generate of according to:
d = arg max E E PLLM (az, Spe s')), Va, P,
(5)
where P is the support set of distribution PLLM (az a/2,, s and a PLLM a S/2, dy). Note that based on results from $3.2 LLMs could evaluate future steps after incorporating few steps of foresight. Therefore we evaluate the future constrained to To steps of foresight, i.c. ay, == 1
We use constrained decoding and sampling to apply soft constraints on outputs, promoting di- verse generation and preventing overfitting to our partial (To steps) foresight. Our method follows the campling-importaann importance-resamllingg resampling (SIR) technique from energy-based models (EBM) (Smith &
Gelfand 1992, Ji et al. 2023) to achieve the optimization goal.
Proposition 4.1. The distribution that solves the optimization problem in Eq is in the form of: P. (a,) PIlM (at) a'z, s'2) exp [Ea..,s. PIIM (at, 1 Syt a s'22) /T].
(6) The detailed proof is in Appendix B.22 Specifically we first use the LLM sample a set with size K of foresight rollouts agt-T, given prefix aL, in parallel, as well as obtaining the exponential value of generation probability Wg of each rollout. Then we obtain the categorical distribution
Categorical
10 Ex= my Ex_ we The next action step is determined as the first step in the sampled
rollout from this distribution. In the limit K + oo and temperature T + 0, the method recovers the exact maximum value of the distribution. In practice, we can choose K according to computational budget and set T according to whether we want the model to more towards the distribution or generate more diversely.
Predictive- Predictive-Decoding mainly uses LLM self-evaluation of foresight to improve planning, but this method could also be integrated with an external heuristics J. Eq. can be rewritten as p(a:) oc pl..M [at] Act,Set) Set) exp J (So; agrr)] which uses the heuristic function J rather than LLM probability to evaluate the foresight. This setting enables L.M to utilize discrete heuristies more effectively and makes it easier to compare with other search baselines which often use external reward models. More details are elaborated in $.3
4.2 RECYCLING TRAJECTORY ROLLOUTS
In previous work, foresight in generation has been applied for controllable tasks (Deng al. 2020 Lu et al. 2021 Qin et al. 2022), typically using token-level constraints with short lookahead of only few tokens. In contrast, generating future actions involves longer foresights, which could lead to increased computation with complexity O ((TT)). Insufficient sampling number K can inaccurately model the distribution p- (at). while larger K is inefficient. Inspired by work on accelerating LLM inference (Fu et al. 2024). we design a memory pool to recycle sampled trajectories.
We observe that different sampled trajectories at different time-steps often overlap. For example, when an agent needs to heat tomato, the trajectory starting from "go to the microwave put the tomato in microwave + heat the tomato with microwave" overlaps with "open the fridge + take the tomato from fridge go to the microwave put the tomato in microwave heat the tomato with microwave" since the tomato needs heating after being taken from the fridge. Thus, previously sampled trajectories and their probabilities (aut+T, Pi) be reused for evaluating timestep i' (t,t+ To). provided their trajectory matches a = a/.g- Similarly, this could be applied for mathematical reasoning as well coding, separate reasoning paths often share steps.

---

Published as a conference paper at ICLR 2025
Table The accuracy( %6) on GSMSK(cight-shot) and MATH (four-shot)." CODEX results are taken from Xie al. (2224). Inference FLOPS for PAL is denoted and Guided- FLOPS
scales according to the number generated tokens reported in the paper.
Model
Size
Method
Inference FLOPS
#Sample
GSMBK
MATH
CODEX
175B
Autoregressive (PAL., Gan et (0233)
72.0
Guided-Decodiing Xic et 2024)
138.5k
N=1
80.2
Autoregressive (PAL)
7.5 x 10
71.3
29.7
Beam Search
478.6 10
N=1
34.4
Autoregressive Self-Consistency
59.8 10
LLAMA-3
Beam Search Self- Consssstennyy
478.6 10
=
79.5
39.4
119.3 10tH
=
63.9
Predictive-Decoddi
161.3 10
==1
78.5
34.0
Predictive Predictive-Decoding Self-Consisteney
129.0 10tH
N =
81.3
40.3
Autoregressive (PAL)
6.6 10
N
53.4
12.7
MISTRAL-0.3
7B
Beam Seurch
418.8 10
N
65.5
18.2
Predictive-eccodin
141.1 10
N
66.7
19.5
Autoregressive (PAL)
53.7 10
==1
43.8
ILAMA-3
70B
Beam Seurch
343.7 10th
N
91.4
48.1
Predictive Predictive-Decoding
115.5 10
==1
49.2
Table The pass@ @ 1(%) and pass 10(%) rates on HumanEval (zero-shot) and MBPP (zero-shot). MBPP uses the 500 samples test set from huggingface. 'Results are taken from Roziere et al. 20233)
FLOPS pass @
HUMANEYAL
MBPP
Model
pass@
pass@ 10
pass@
pass @ 10
GPT-3.5 TURRO"
Autoregressive
48.1
$2.2
GPT-4!
Autoregressive
67.0
Autoregressive
2.9 10
44.3
72.1
33.5
48.4
Beam Search
290.0 10!2
53.5
70.1
33.6
50.2
LLAMA-3
8B
Self-infilling Zheng et al. 2023
5.8 10
51.8
75.6
33.4
48.6
Predictve--ecoddngg
76.6 10
S7.3
76.8
38,4
52.6
Autoregressive
2.4 10
45.2
66.5
38.6
53.8
Beam Search
240.0 10
46.7
50.0
39.7
42.6
DEEPSEEK CODER
Self-infilling
10
76.2
Predictive Decoodng
62.4 10
47.6
79.9
34.0
55.2
EXPERIMENTS
5.1 EXPERIMENT SETTINGS
Benchmarks Our evaluation covers three domains: math GSM8K (Cobbe et al.) 2021) and
MATH (Hendrycks al. 202T), coding HumanEval (Chen 2021 and MBPP (Austin al. 2021 and agents two agent tasks AlfWorld (Shridhar et al. 2021 and PDDL (from Agentboard, Ma al. 2024) to understand planning ability closed-loop interactions.
Evaluation Settings We list the LLMs used for evaluation in Appendix F.I We use vLLM inference infrastructure for efficiency (Kwon al., (023). To ensure fair comparisons, we use standardized prompts from Guo et al. (2024), Gao et al. (2023), Cobbe et al. (2021), and Ma et al. (0024). Hyperparameter and prompt details are stated in Appendix
FLOPS calculation Many of our experiments report computational efficiency to better illustrate tradeoff. We using FLOPS as the metric, Kaplan al.) (2020), i.e. FLOPSS
performance-effictae
6nP, where P is the number of parameters in the LLM, and the number of generated tokens.
Baselines We incoporate iterative planning baselines Self-Consistency (Wang et al. 2022), Guided- Decoding (Xie et al. 2024), MCTS (Hao et al. 2023) and Self-Infilling (Zheng et al. (023) and
sequential planning baselines ReAct (Yao et al. (022). Beam Search, PAL (Gao et al. 2023). COT (ei et al. )) Tree of Thought (Yao et al. 2024), A Search (Zhuang et al. 2023 Wang
ct al. 2024b) in our evaluation. We excluded search agents such as LATS (Zhou et al. 2023 from comparison, they primarily address non-environment altering agents (e.g., QA and Retrieval).
7

---

Published as a conference paper at ICLR 2025
Table 5: The success rates(%) and the progress rales(%) on AlfWorld (one-shot) and PDDL (one-shot) within 20 steps. DeccciiveeDeeoding uses the same prompt as Act.
ALFWORLD
PDDL
Model
Size
Method
FLOPS
Sumple
Success
Progress
Success
Progress
Act (Ya al 2022
N
6.7
25.6
5.0
20.0
GPT-3.5 TURBO
ReAct Yao et il 2022.
8.4k
7.5
34.8
3.3
15.6
CeddictiveDecoddig
40.7%
149
33.2
11.7
28.9
Act ReAct
x x0
19.4
43.0
35.0
LLAMA-3.1
70B
488.0 10
N=
18.7
43.4
18.3
36.9
Predictive Delildiive--
224.1 1
==1
44.0
53.9
38.3
Table 6: Impact of Foresight To, sampling number K and trajectory recycle eb. FLOPS of autore- gressive generation is denoted as and is scaled based on number generated tokens.
# Foresight T
FL.PP
GSM8K
HumanEval
Sampling K
FLOPSS
HUMANEVAL w. &3,
wo.
To
3.6k
77.0
45.1
==
6.6k
51.2
47.6
To
7.2k
76.4
48.8
K
13.24
54.3
46.3
To
14.4k
77.9
52.4
K
19.9k
50.6
49.4
To 6
21.5k
78.5
57.3
K =
26.4k
57.3
49.4
5.2 PREDICTIVE DECODING MAIN RESULTS
Results on Math Tasks Following (Xie et al. 2024), we use the Program Aided Language Model (PAL) format, executing generated code in Python obtain answers. As shown in Table Predictive- Decoding improves accuracy by 7.2% on GSM8K and 4.3% on MATH with Llama3, and 13.3% and 6.8% with Mistral-0.3. While Beam Search achieves similar gains, it requires over 3x the compu- tation. Our method matches or exceeds Beam Search and, when combined with Self- Saff-Consistency, outperforms both autoregressive and beam search approaches. Guided-Decoding works well with Codex but underperforms with Ilama3 due to overconfident scores. For the stronger 70B model, the myopic gap narrowed but redictive-Decodiin still improves performances by a distinct margin.
Results on Coding Tasks Table presents results for two code generation tasks. The Pass@ 10 setting selects the best from 10 generations, highlighting both accuracy and diversity. outperforms all baselines with Llama3, achieving strong quality-diversin diversity balance, detailed in the subsequent temperature analysis. Interestingly, beam search shows less stability in the Pass 10 setting, suggesting that search-based methods may result in lower diversity in generation.
-eccodinn
Results on Agent Tasks Table 5 presents the performance of two agent tasks: Srddictive-eecoding Act and
shows improvements of up 24.6% two agent tasks and outperforms consistently achieved more significant enhancements success rates than
ReAct. Notably, Predictive-Decaan in progress rates. Predictive-Decoding excels in strategic planning and error reduction, leading to higher success rates. Case studies compared to baselines are available in Appendix
Impact of Foresight Length To We analyze the impact of foresight length in Table Performances on both GSMSK and HumanEval both improve with longer foresight. Notably, Llama myopia on GSM8K is mitigated with just foresight steps, indicating that LLMs already possess partial capability to plan ahead. On HumanEval, Predictive-Decodie foresight length. This aligns with findings from studies on inference time scaling (Snell et al. 20244. which we discuss further in $5.4 Our method is more efficient in mitigating myopia compared to Beam Search, as shown in Figure
scale significantly with increased
Impact of Sampling number K and Trajectory Recyele We must sample from the original distribu- tion as described in $4.1 but more sampling may reduce efficiency. shown in Table 6 increasing K leads to better performances it could give more accurate account of the original generation distribution. Also, trajectory recycle significantly improve the sampling efficiency.
Impact of Sampling temperature and LLM generation temperature As shown in Figure when a remains constant, all values of r enhance the diversity compared to vanilla generation, as opposed to search-base based methods that often sacrifice diversity. Higher 7 values increase diversity but can degrade performance by causing myopia. a significantly influences performance outcomes, with the best balance between diversity and performance achieved at moderate values (0.3-0.6).
8

---

Published as a conference paper at ICLR 2025
Performance v.S. Efficiency
Performance v.5. Diversity
T-001
Predictive Decoding 8-0.6
56
Decoding
Tea)
F5-01
Beam Search
Tw=2
Po1903
2
3-0.0
55000
48
Predictive Decoding
46
Search Autorsgreasive
Autoregressive Decboing, avo.6
0.06
(10-121
Diversity
Performance v.S. Efficiency GSM8K. Predictive Decoding is Pareto su- perior to Beam Search with longer foresight.
Figure 4:
Figure Illustrating Performance and Diversity tradeoff on HumanEval by controlling parame- ters and a. Diversity uses 1- ROUGE score.
Table 7: The success (a) and the progress rates(%) on AlfWorld (one-shot) and PDDL (one-shot) with different large language models and matching function heuristics.
ALFWORLD
PDDL
Model
Method
# Foresight To
Success
Progress
Success
Progress
Yao 2022
To
6.7
25.6
5.0
20.0
GPT-3.5 TURBO
ReAct Yao 2022
To
7.5
34.8
3.3
15.6
Predictive Decooingg Reward
To
7.5
29.5
6.7
23.9
Predietive-Desoding Reward
To
13.4
37.6
8.3
27.9
Table The accuracy(%) on GSMSK (8-shot) with reward model(RM) Math-Shepherd.
Model
Size
Method
Inference FLOPS
Reward FLOPS
GSM8K
Autoregressive
10
0.0 x 10
70.4
R.M-weighted Self-Comsistency
41.x 10
0.4 x 10
82.8
RM-based Ranking
14.5 x 10
0.4 10
85.9
Guided-Decodding RM
276.2 10
11.4 1012
86.5
LLAMA-3
8B
Tree-of-Thought RM
81.5 10
3.7 10
82.0
A Search RM
71.6 x 10
1.6 10
83.6
Monte Carlo Tree Search RM
360.0 10!2
16.2 10
85.5
Predictive- Deciiiiv--Deddignn + RM
182.3 x 10
2.9 10
87.9
Predietive-Decoofie + RM
360.5 16
5.6 x 10
89.9
More analysis including world model, reflection and prompt sensitivity are in Appendix
5.3 PLANNING REWARD OPTIMIZATION
Recall that Predictive-Decodiee samples from distribution solve the trajectory optimization problem using LLM self- self-evaluation. Similarly we can define such distribution for any target. The same sampling technique could maximize the objective left right. We examine how Predictive- Decoding performs with two different types of objective:
Guiding Agent Planning with Heuristies We employ human-designed reward heuristics J guide LLM planning, following the approach recommended by Ma et al, (2024). The heuristic rewards are sparse, requiring multiple steps to increase rewards. As shown Table 7 even without foresight, the reward enhances LIM agent performance. Predictive-Decoding further overcomes the sparsity with foresight and improves the utility reward functions.
Guiding LLM Reasoning with Reward Model We use Math-Shepherd (Wang et al. 2023b) as Seteetvve-Decoding against other reward model based planning methods. Results in Table 8 demonstrate that all algorithms improve by over 10% with Sath-Shepherd. Although strong baselines like quided-Decoding and MCTS are effective, they require extensive computation. Predictive- Deccoiing achieves 1.5% improvement over Guided- Decoding with only 65% of the computation and 2.4% improvement over MCTS with just 50% of the computation. We further compare sample efficiency in $5.4
the reward model for GSMSK. We compare

---

Published as a conference paper at ICLR 2025
5.4 DISCUSSION: INFERENCE SCALING LAW
Snell et al. 2224)) recently stressed the importance of inference scaling law, which states that LLM inference could benefit from using more computation to support more expressive algorithms. Wu et al.) (2024b) further discuss the
trade-off of different search algorithms. However, is yet to be discussed if searching the most efficient and effective choice for LLM reasoning.
Inforence Scaling Law on GSMBK
90
We follow setting in $5.3 using reward model Math- Shepherd. In Figure 6 we plot the inference scal- ing law of various methods and observe that: (i) Sampling-based methods have better computation efficiency compared to search- based methods. How- ever autoregressive generation using simple reward ranking tends to saturate when more computation is available. (ii) Predictive-Decodin samples from optimal solution space achieves better scaling law than all sampling and search baselines. Predictive- DeddictiveDeecodig performance also consistently improves with more computation.
188
86
Auting wedue Rork
Auttig nedie Weigteed Witeo
78
which directly
HCTS
76
Predithee Decudingth gir (3344
Predithe Decudinghh IK- 2,440
155
32
54
128
256
512
Inference FLOPS (10
Figure 6: Inference time scaling law on 189 examples sampled from GSM8K. All algo- rithms use Llama3-8B and Math-Shepherd.
6 RELATED WORK
LLM-based Planning and Reasoning One major development is the emergence of LLM step-by-step reasoning abilities (Wei et al. (2022). This capability is further enhanced by more expressive inference
algorithms like searching (Yao et al. 2022
2024 Hao et al.) 2023 Wang al. 2023a Zheng et al., 2023,Xie et al.] 2024 Zhao et al. 2024 Sun et al. 2024). However, most of these algorithms are
computation-intensiee Recent work discusses the inference time scaling law for LLM reasoning (Wul cet al. 2024b Snell et al. 2024). This highlights the need for an efficient yet global-optimal method. Dredictive-eccoding
Another line of work studies the expressiveness of LLM reasoning. Feng et al. (2024) confirms LLM reasoning's s expressiveness equals dynamic programming.
Our work attempts to close this research gap by introducing
Li et al. (2024) discusses Turing completeness in -fiin-of-thougt reasoning. Our theory does not contradict their claims but examines whether any pretrained LLM could find such an optimal solution.
Model Predictive Control Model Predictive Control (MPC) a widely used control strategy that invol ves solving an optimization problem at each time step by forecasting future results (Witkin & 1988 Qin & Badgwell 1997). Similarly, in model-based reinforcement learning (RL), an agent aims maximize future success by using dynamics model to simulate state transitions (Silver et al., 2017 Ha& & Schmidhuber 2018 Anthony et al.) [017]] Racanière et al.) 2017) Nagabandi et al.) 2018). These algorithms enable agents think ahead, envisioning the outcomes of various potential actions, and making deliberate selections among alternatives. Our method follows this line of work.
Kass
7 CONCLUSIONS AND LIMITATION
In this paper, we analyzed the limitations and potential of Large Language Models (LLMs) in planning and reasoning tasks, particularly focusing on their myopic tendencies. We introduced Predictive-eecodine which employs Model Predictive Control to enhance non- non-myopic planning. significantly improving performance across various domains. Our experiments confirmed Predictive- Decoding's effectiveness boosting planning accuracy and computational efficiency. These results open promising avenues for future research into optimizing LLM reasoning and incorporating foresight into decision-makine paving the way for more robust and efficient LLM applications.
The main limitation of our work is that we are targeted towards improving reasoning and planning at inference times, without exploring how our method could aid in generating training data an advantage of search-based methods. Additionally, Predictive- Decoodigg limited to tasks with clear reasoning steps, like math or coding. While potentially could aid global awareness in free-form generation, such long-context tasks, we leave this for future research.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, lige Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et Gpt-4 technical report. arXiv preprint (rXXiv23033.87744 2023.
Thomas Anthony, Zheng Tian, and David Barber. Thinking fast and slow with deep learning and tree search. Advances in neural information processing systems, 30, 2017.
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al. Program synthesis with large language models. arXiv preprint arXiv:2108.07732 077332, 2021.
Gregor Bachmann and Vaishnavh Nagarajan. The pitfalls of next-token prediction. arXiv preprint arXiv:2403.065 066.23333, 2024.
Eduardo F Camacho, Carlos Bordons, Eduardo F Camacho, and Carlos Bordons. Constrained model predictive control. Springer, 2007.
Boyuan Chen, Diego Marti Monso, Yilun Du, Max Simchowitz, Russ Tedrake, and Vincent Sitz- mann. Diffusion forcing: Next-token prediction meets full-sequence diffusion. arXiv preprint arXiv:2407.01392, 2024a.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger. Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojeiech Zaremba. Evaluating large language models trained on code, 2021.
Ziru Chen, Michael White, Raymond Mooney, Ali Payani, Yu Su, and Huan Sun. When is tree search useful for Ilm planning? it depends the discriminator. arXiv preprint arXiv:2402. 10890, 2024b.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichir Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv preprint 10X1122110.14168, 2021.
Yuntian Deng, Anton Bakhtin, Myle Ott, Arthur Szlam, and Mare' Aurelio Ranzato. Residual energy-based models for text generation. arXiv preprint arXiv:2004.11714, 2020.
Yilun Du, Jiayuan Mao, and Joshua B Tenenbaum. Learning iterative reasoning through energy diffusion. arXiv preprint arXiv:2406.11177 2024.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang. Angela Fan, et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024.
Guhao Feng. Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: theoretical perspective. Advances in Neural Information Processing Systems, 36, 2024.
Markus Freitag and Yaser Al-Onaizan. Beam search strategies for neural machine translation. arXiv preprint arXiv: 702.0/ 2017.
Yichao Fu, Peter Bailis, Ion Stoica, and Hao Zhang. Break the sequential dependency of Ilm inference using lookahead decoding. arXiv preprint arXiv:240..02057 2024.
11

---

Published as a conference paper at ICLR 2025
Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig. Pal: Program-aise aided language models. In International Conference on Machine Learning, pp. 10764-10799, PMLR, 2023.
Daya Guo, Qihao Zhu, Dejian Yang, Zhenda Xie, Kai Dong, Wentao Zhang, Guanting Chen, Xiao Bi, Yu Wu, YK Li, et al. Deepseek-coder: When the large language model meets programming-the rise of code intelligence. arXiv preprint arXiv:2401. 2024.
David Ha and Jürgen Schmidhuber. World models. arXiv preprint arXiv: 2018.
Shibo Hao, Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. Reasoning with language model is planning with world model. arXiv preprint 2rXiv:2305.1499.. 2023.
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. arXiv preprint arXiv: (03.:22003.08774 2021.
Michael Janner, Yilun Du, Joshua B Tenenbaum, and Sergey Levine. Planning with diffusion for flexible behavior synthesis. arXiv preprint arXiv:2205.0992 2022.
Haozhe Ji, Pei Ke, Hongning Wang, and Minlie Huang. Language model decoding as direct metrics optimization. arXiv preprint arXiv:2310.0104// 2023.
Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. arXiv preprint arXiv:2310.06825, 2023.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.088 200000000.06,,,..... 2020.
Thanard Kurutach, Ignasi Clavera, Yan Duan, Aviv Tamar, and Pieter Abbeel. Model-ensemble trust-region policy optimization. arXiv preprint arXiv: 1802. 2018.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Yu, Joey Gonzalez, Hao Zhang, and Ion Stoica. vllm: Easy, fast, and cheap Ilm serving with pagedattention. See https::/vvllm. ai/(accessed August 2023), 2023.
Yann LeCun, Sumit Chopra, Raia Hadsell, M Ranzato, Fujie Huang, al. A tutorial on energy-based learning. Predicting structured data, 100), 2006.
Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. arXiv preprint xxXi:2442..12873 2024.
Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. arXiv preprint 2.Xiv:2305.20053 2023.
Ximing Lu, Sean Welleck. Peter West, Liwei Jiang, Jungo Kasai, Daniel Khashabi, Ronan Le Bras, Lianhui Qin, Youngjae Yu, Rowan Zellers, al. Neurologic a esque decoding: Constrained text generation with lookahead heuristics. arXiv preprint 12.00726, 2021.
Chang Ma, Junlei Zhang, Zhihao Zhu Cheng Yang, Yujiu Yang, Yaohui Jin, Zhenzhong Lan, Lingpeng Kong, and Junxian He. Agentboard: An analytical evaluation board of multi-turn I1m agents. arXiv preprint arXiv:2401.13178 2024.
Anusha Nagabandi, Gregory Kahn, Ronald S Fearing, and Sergey Levine. Neural network dynam- ics for model-based deep reinforcement learning with model-free fine-tuning. In 2018 IEEE international conference robotics and automation (ICRA), pp. 7559-7566. IEEE, 2018.
Lianhui Qin, Sean Welleck, Daniel Khashabi, and Yejin Choi. Cold decoding: Energy-based constrained text generation with langevin dynamics. Advances in Neural Information Processing Systems, 15:9538-95511 2022.
12

---

Published as a conference paper at ICLR 2025
S Joe Qin and Thomas A Badgwell. An overview of industrial model predictive control technology. In Alche symposium series, volume 93, pp. 232-256. New York, NY: American Institute of Chemical Engineers, 1971-c20022 1997.
Yujia Qin, Shihao Liang, Yining Ye, Kunlun Zhu, Lan Yan, Yaxi Lu, Yankai Lin, Xin Cong, Xiangru Tang, Bill Qian, et al. Toolllm: Facilitating large language models to master 16000+ real-world apis. arXiv preprint arXiv:2307. 16789, 2023.
Sébastien Racanière, Théophane Weber, David Reichert, Lars Buesing, Arthur Guez, Danilo Jimenez Rezende, Adrià Puigdomènech Badia, Oriol Vinyals, Nicolas Heess, Yujia Li, et al. iragination-augmeen agents for deep reinforcement learning. Advances in neural information processing systems, 30, 2017.
Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, al. Code llama: Open foundation models for code. arXiv preprint arXiv:2308./223 /2950, 2023.
Andy Shih, Dorsa Sadigh, and Stefano Ermon. Long horizon temperature scaling. In International Conference on Machine Learning, pp. 31422-31434. PMLR, 2023.
Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024.
Mohit Shridhar, Xingdi Yuan, Marc-Alexander 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://arxia org/ abs 2010. 03768
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International conference on machine learning, pp. 387-395. Pmir, 2014.
David Silver, Julian Schritwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676::554-359) 2017.
Adrian FM Smith and Alan E Gelfand. Bayesian statistics without tears: sampling-resampling perspective. The American Statistician, 46(2):84 88, 1992.
Charlic Snell, Jachoon Lee, Kelvin Xu, and Aviral Kumar. Scaling Ilm test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.033 2024.
Haotian Sun, Yuchen Zhuang, Lingkai Kong, Bo Dai, and Chao Zhang. Adaplanner: Adaptive planning from feedback with language models. Advances in Neural Information Processing Systems, 36, 2024.
Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. Advances in Neural Information Processing Systems, 01:3706-373111 2023.
Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song. Noah Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. Solving math word problems with process-and outcome-based feedback. arXiv preprint arXiv:2211.14277. 2022.
Ante Wang, Linfeng Song, Ye Tian, Baolin Peng, Dian Yu, Haitao Mi, Jinsong Su, and Dong Yu. Litesearch: Efficacious tree search for 11m. arXiv preprint arXiv:2407.00332, 2024a.
Chaojie Wang. Yanchen Deng, Zhiyi Lyu, Liang Zeng, Jujie He, Shuicheng Yan, and Bo An. Q Im- proving multi-step reasoning for Ilms with deliberative planning. arXiv preprint arXiv:2406. 14283, 2024b.
Guanzhi Wang, Yugi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Voyager: An open-ended embodied agent with large language models. arXiv preprint (tt.:2335..1299 2023a.
13

---

Published as a conference paper at ICLR 2025
Peiyi Wang. Lei Li. Zhihong Shao, RX Xu, Damai Dai, Yifei Li, Deli Chen, Y Wu, and Zhifang Sui. Math-shepherd: A subel-free step-by st- verifier for Ilms in mathematical reasoning. arXiv preprint 1XXi::3312.089.3. 2023b.
Xuezhi Wang and Denny Zhou. Chain-of-thought reasoning without prompting. arXiv preprint 1xXiv:2402.10200, 2024.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe Le, Ed Chi, Sharan Narang, Aakanksha Chowdh- ery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint www.::2223..117220 2022.
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, 35:24824 248377, 2022.
Andrew Witkin and Michael Kass. Spacetime constraints, ACM Siggraph Computer Graphics, 22(4): 159-168, 1988.
Tong Wu, Zhihao Fan, Xiao Liu, Hai-Tao Zheng. Yeyun Gong, Jian Jiao, Juntao Li, Jian Guo, Nan Duan, Weizhu Chen, et al. Ar-diffusion: Auto-regressive diffusion model for text generation. Advances in Neural Information Processing Systems, 36:39957-39974, 2023.
Wilson Wu, John X Morris, and Lionel Levine. Do language models plan ahead for future tokens? arXiv preprint arXiv:2404.00835 2024a.
Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. An empirical analy- sis of compute-optinn optimal inference for problem-solving with language models. arXiv preprint arXiv:2408.007244 2024b.
Yuxi Xie, Kenji Kawaguchi, Yiran Zhao, James Xu Zhao, Min-Yen Kan, Junxian He, and Michael Xie. Self-evaluation guided beam search for reasoning. Advances Neural Information Processing Systems, 36, 2024.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models, arXiv preprint arXiv:2210.03629, 2022.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36, 2024.
Haiteng Zhao, Chang Ma, Guoyin Wang, Jing Su, Lingpeng Kong, Jingjing Xu, Zhi-Hong Deng, and Hongxia Yang. Empowering large language model agents through action learning. arXiv preprint arXiv:2402. 15809, 2024.
Lin Zheng, Jianbo Yuan. Zhi Zhang, Hongxia Yang, and Lingpeng Kong. Self-infilling code generation. arXiv preprint xrXiv:2311.17972. 2023.
Andy Zhou, Kai Yan, Michal Shlapentokh-Rottinn Rothmmn,, Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifies reasoning acting and planning in language models. arXiv preprint arXiv:2310.04406 2023.
Yuchen Zhuang, Xiang Chen, Tong Yu, Saayan Mitra, Victor Bursztyn, Ryan A Rossi, Somdeb Sarkhel, and Chao Zhang. Toolchain Efficient action space navigation in large language models with a search. arXiv preprint arXiv:2310. 13227, 2023.
14

---

Published as a conference paper at ICLR 2025
A
PSEUDO CODE
Algorithm 1 Predictive-Decoddie for Planning
Input: prompt, the language model, maximum number of iterations sampling number K sampling temperature environment env, rollout length To. Output: Action sequence dp....47.
Set 5p +- Initialize env, finish +- False
for t .,, do > Sample Foresight.
Input prompt and 6/. oo oo...,,. sy to language model context;
for k= k 1,2...,, do /f parallel
Sample at st. 1 1..11. Oi-T, Sc-To+1 pLLM context);
Ps - P (a (.... She context);
Wy exp (Px)T); end for
> Re-sample based on foresight.
Sample j Categorical
W1
WK
kk-1 we
ER
Set at a/:
> Takes the action df
Update St,1, finish + Execute de in environment env;
break if finish is True;
end for
Return the action sequence do:... a'y
B THEORETICAL RESULTS
B. SAMPLE EFFICIENCY OF MODEL PREDICTIVE CONTROL
In this section, we explain in detail why model predictive control has the potential to improve sample efficiency in solving trajectory optimization problems.
We begin by introducing a stochastic setting, where trajectory (0o,4) .1..... ar) is chain of actions that could take values in set A. policy model models the distribution of trajectories as (T),,, denoting the probability that the policy model samples the trajectory.
For the best scenario, the policy model perfect and the sample 7' ~ (T(T) maximizes the objective J(T) and r' is the best solution. However, in most cases our LLM is not the perfect policy model and prone to make errors during sampling. Instead, we sample multiple solutions T1, .2......, Tk ~ Ty (T( and selects the best solution 7' max;=1..... J (T,). A different method is using model predictive control during sampling. We thereby discuss the number necessary to obtain the correct r'.
Proposition B.1. Given the optimal trajectory T' (do....,dy, that maximizes J.
71, MHAl (T)... The best og is the first step of the trajectory 7 that maximizes J.
ah satisfies:
max Jag, Fram) . :ias ~ :T(:1a0)
ag
arg max dg
J- I-....k
Then P(a d6) 2 P( ag) d6)
Informal proof: If æ has no knowledge of J. then the best case in sampling would be 71, ? ? A first sample ag from ((a)), then samples T-aa, ~ (T (-1 og), order to gain thorough information about which do would be the best for the trajectory. In this case, the sampling process is same as model predictive control and thus the best case results in P(a a()) P(aj o)). However, when Ty places more importance on an & an i.c. Eag, T ((az) > न (an), there exists larger possibility that aj selected by J instead of de than model predictive control, let be the times og is sampled,
15

---

Published as a conference paper at ICLR 2025
k n. then E maxx-1..... I Jap.
r E max I Jap: T ( T o selected would be larger and P( d)) P(ag = d6).
Thus the probability that
This proposition show that if directly sample solution from an exponential solution space, it would be unlikely to obtain the optimal solution. We also showcase this phenomenon that model predictive control improves sample efficiency than direct sampling through simulated experiments.
2.2
Navve teusire Samp Mocel Prockcive Contral
Saccss Rate with 3020
9.4
Nax Pubiie Oidi
Nard Pudiiie Ordine
SaORREesiis daypirg
500
750
1250 1500
Sampling Numbar (N)
Figure 7: Pass@ 1000 accuracy v.s. problem scale on the simulation task. He follows a uniform dis- tribution. The performance of iterative sampling decreases significantly when the problem scales up.
Figure Pass@k accuracy on simulation task with different sampling numbers. Larger de- notes that the sampling distribution Te is close to ground truth model.
We focus very simple combinatorial optimization problem, where list (ao,a),... ai....;,.. ar) satisfies ag E A takes the value from [A] integers. Our objective is to find the list of numbers with maximum sum. We control the sample complexity of "random sampling ranking" and "model predictive control". Results are shown in Figure 7 and Figure 8 On all settings, MPC is more sample efficient than naive iterative sampling. Notably, we alter number based on value numberr/r Larger 7 is closer to uniform distribution yet smaller to the optimal distribution. We can see that good prior always results in improved performances, and the gap between iterative sampling and MPC smaller. However, when the my is not good (e.g. using a I.I.M that is not -ell-pretrained), the sample efficiency of MPC is much better than iterative sampling.
prior distribution To such that it samples the closer
B.2 PROOF FOR PROPOSITION
The distribution that solves the optimization problem in Eq is in the form of:
Pr (ax) PLLM (oe a s'2)) exp [E,,,.., PLLM (ar, a,t, 8st a /T]
Proof. The goal is to solve this optimization problem:
df arg max Ea,,,,, PLLM (ar, a,t, ales S24)
dr
Energy-based Model can transfer the optimization problem into probability distribution, such as,
Lemma B.2. LLCunn et al.
2006 Let f (fr).e.... a set of evaluation metrics, the distribution p(x) solves the optimization problem x argmin Σ, (4f(x), only if p(x) satisfies:
xcP
p(z) (t)
where P is the support of probability distribution of po-
Here a is generated by LLM through autoregressive generation, i.. a, ~ PLLM ( and the constraint can be rewritten f(a;) Ea...s., PLLM (at, a,1 a,,, s'a). Plugging into Eq. 9 and we would yield pa,- 7 can be added as a temperature coefficient and does not lead to difference in optimization.
16

---

Published as a conference paper at ICLR 2025
p:0.1331
p:0
p:0.5212
Human Eve luation Score
Human Eva Ielatiiion Score
Human Eva luationnnnn Score
500
4% Self-Evakuation with Foresight (World Model)
Self Sclf-Evaluation Score
Self-Evaluation with Foresight
Figure 9: Comparison of GPT-3.5-Turbo Self-Evaluation f(s, a) w/o. modeling on 152 trajectory data from AlfWorld. We compare from left-to-right (1) LLM direct self-evaluation based on past trajectory(p (21 LLM first perform model rollout and then perform self-evaluation based on both past and future trajectory( 0.291), (3)substituting LLM-as- --oo---wordd for accurate world model for rollout(p 0.521) against human evaluation. All scores are chosen from (0.0.25,0.5,0.75,, and KDE plots to visualize overlapping discrete points.
0.0
Vanill PAL
-3,4
Predictive Decoding
Performance
123
0.0
.8.2
-8.5
1-shot
Prompt Type
Figure Prompt sensitivity to instruction brevity, as well as the number of in context samples on GSM8K. Both methods use Llama3-8B.
C MORE ANALYSIS
Dedietive-Decoding requires the LLM to act as world model infer states after each step. However, we often observe hallucinations. For instance, in AlfWorld, when the agent tries to find an apple and place it on desk 1, the imagined state after "open fridge 1" might incorrectly include an apple in the fridge, even it's not there. This reflects an inherent model bias issue KKrrtaach et al. (0118). where the world model fails to accurately represent the environment. environment transitions. Most evaluation emror are false positives, indicating LIMM overconfidence in predicting step outcomes. Increasing 0.05-0.1 helps mitigate this by preventing overfitting.
Impact of Agent World Model Hallucination
shows that this results in lower LLM score accuracy compared to using real
Prompt Sensitivity Analysis Wang Zhou 2024) proposes an intereting problem: improving LLM reasoning without prompting. We find Predictive- DecioiingDeodinggg can also improves performances and maintain high performance even without in-context samples and detailed instructions. As shown in Figure 10 vanilla generation with LLM show significant drop in performance when the detailed instructionsa are not given, or when there are no in-context examples. Predictive-Decoding shows smaller decline in performance, demonstrating better prompt sensitivity. Moreover, Predictive- Decoding without in-context examples could outperforms vanilla generation with in-context examples. This demonstrate method also has the potential to improve reasoning without prompting.
Reflection Analysis Shinn al. 2024): Ma et al. (2024) emphasize the importance of reflection for decision making. However, Predictive Decoding mainly takes a different approach it's targeted at avoiding errors, rather than correcting errors. However, for agent tasks that exploration is necessary, the model still needs to adapt plans to new observations. In this section, we anlayze the ability of Seadictive-Decodiin to perform reflection.
17

---

Published as a conference paper at ICLR 2025
Allworld Reflection
PDDL Reflection
Prodic Decoding
Decod ng
Act
0.30
0.3
0.25
Progess Rate
0.20
0.2
0.05
0.00
0.0
2.5
5.0
10.0
12.5
15.0
Figure 11: Long-range interaction analysis. Specifically, we report the progress rate w.r.t. step of AlfWorld, PDDL. for 1-70B.
We compare the progress rate of LLM w.r.t number of interaction steps taken. A model with self-reflection ability would continuously benefit from more interaction steps.
As shown in Figure 11 Dredictive-Decoding exhibits continuous improvement across 20 steps. For the AlfWorld task, Predictivv--eccodee shows a larger slope across 20 steps compared to Act and ReAct, showcasing improved reflection ability compared with Act and ReAct. For the PDDL task, however, Predictive- Predictive-Decoding shows comparable self-reflection ability with Act. Notably, on both tasks, sradictive-eecodiig shows larger improvement later steps, which indicates improved long-range reflection ability.
D FURTHER DISCUSSION ON RELATED WORK
Combinatorial Optimization via Sequential Sampling Sampling-basee based methods have been extensively used to solve combinatorial optimization efficiently (Sun & Yang, 2023 Janner et al.) 2022, Qin et al. 2022 Du et al. 2024), by constructing energy-based model where the generative probability reflects the objective. However, these methods often use non-autoregressive sampling, which undermines the Markov property of sequences critical to tasks like planning and language modeling. Autoregressive diffusion models (Wu et al. 2023; Chen et al., (024a) have been proposed to sample based optimization constraints while enabling causal generation. However, these methods rely on diffusion training loss and cannot be directly applied to LLMs. In this work, follow Deng al. (2020): et (2023) and the aapplingimmprttanc--rssspppllppi technique, which enables us to maintain autoregressive next-token prediction while achieving global optimality. This method can be easily combined with model predictive control and used on any LLM.
(SIR)
E
CASE STUDY
E.
CASE STUDY ILLUSTRATING PREDICTIVE-DECODIAS
Case Study for Reasoning Here we provide the generations to show how Predictive-Decoding solves a math problem.
Question: Toulouse has twice as many sheep as Charleston. Charleston has times many sheep as Seattle. How many sheep do Toulouse, Charleston, and Seattle have together if Seattle has 20 sheep?
def solution():
[' #Touluse has twice many sheep as Charleston. Charleston has times as many sheep Seattle. How many sheep do Toulouse, Charleston, and Seattle have together if Seattle has 20 sheep?': 1.0)
18

---

Published as a conference paper at ICLR 2025
Line 1: #Toulouse has twice many sheep Charleston. Charleston has 4 times many sheep as Seattle. How many sheep do Toulouse, Charleston, and Seattle have together Seattle has 20 sheep?
{" seattle sheep 20": 1.0]
Line 2: seattle seattle.sheep 20
{' Sharleston_shegy = seattle.sheep 4": 0.9767, charleston seattle.sheep': 0.0233}
Line 3: charleston_sheep scattle_sheep
{' coulouse_shecp charleston_sheep * 2": 0.9377, "toulouse.sheep seattle.sheep * 2": 0.0623}
Line 4: toulouse charlestonssheep *
{ sotel_sheep- t
toulouse_sheep': 1.0}
Line 5: total seattle.sheep + sharleston.sheep toulouse_sheep'
{' resultt= total shepp' 0.9999}
Line 6: result = total sheep
(* return result':1.0)
Line 7: return result
Examples in trajectory pool:
Foresight for the first line (composed of 6 steps):
{ ('Action': None, 'Reward': J. 0.9984305701520592]
{'Action':
charlessto...........
+ Toulouse, haa.l:scw..ssss....inaaaaaaaaoeo
Charloston_has_A__
a sheep?"M"\n! 'Reward': 0. 0.99843057015205999
{ ('Action': seattle_sheep 20
'Reward': 0. 0.9984305701520552)
l'Action': charleston charleston_sheepp sheep = seattle_sheep 4\n', 'Reward': 0
> 09943037011200522
('Action': taulouse_sheep charleston_sheep 2 'Reward':
+ 09944957005205999
('Action': total_sheas _seepp_ = seattle seattle_sheep seeeppseepppppppeeeee + charleston_sheee
toulcuse_sheep'n' 'Reward'; 0. 0.9984305701520592)
Foresight for the third line (composed of 4 steps):
('Action': charleston_sheep seattle_sheep 4\n', 'Reward': + .984275095836792),
('Action':
toulouse_shee sheep .98427509558367921
charleston_sheeplan 'Reward': 0
{ ('Action': cotal_sheet = seattle + charleston_sheep
+ ttoulossesheepplane 'Beward'; (.9842750955896777
('Action': result total total_sheep'n', 'Reward': 0.9842750955833799)
{ ('Action':" return result)n', 'Reward': 0. 0.98427509338337992
19

---

Published as a conference paper at ICLR 2025
From the case study could observe that for easier steps, the distribution is concentrated single action. This is due to LLM generation is inherently confident on these lines. Our method mainly helps improving the lines where LLM generation is less confident (e.g. Line 3 & 4).
Case Study for Agent In this section we also provide a case study for agent task. Agent tasks are different from reasoning tasks in two ways: (i) Agent tasks make predictions not only based on prior actions, but also on environment observations. Therefore, during foresight, the agent needs to use LLM as a world model (Hao et al., 2023) to infer the next state. (ii) Exploration is crucial for agents. Therefore maintaining stochastic during sampling is important.
Here is the original generation by GPT-3.5-Turbo. 5-Turbo. We can see that this is an example of why focusing solely on historical information can lead to irreversible mistakes and potential planning failures (as mentioned $ At the beginning, the agent is exploring the surroundings to look for bowl. It arrived shelf T, where there is only a cellphone and creditcard. The agent picks up the cellphone despite given instructions and know needs to find a bowl. As the agent can only to
carry thing time, it became stuck when it actually finds bowl and found it has carry. Therefore, this case results in a planning failure due to the tendency of models to perform history-consistent completion of the next action.
Goal: look at bowl under the desklamp.
Observation: You are in the middle of a room. Looking quickly around you, you see a bed 1, desk 2, desk 1, drawer 6, drawer 5, drawer 4, drawer 3, drawer 2, drawer garbagecan 1, a laundryhamper a safe I, shelf 6, a shelf 5, a shelf 4, shelf 3, a shelf 2, and shelf 1.
Step 1: go to desk
Observation: On the desk you desklamp I, keychain 3, mug 2, pen pen and pencil? 2.
Step 2: take desklamp 1 from desk 1
Observation:
Nothing happens.
Step 3: examine desk 1
Observation: On the desk you see desklamp 1, a keychain 3, mug 2, pen 2, a pen and pencil 2.
Step 4: go to shelf 1
Observation: On the shelf 1, you see cellphone 3, and creditcard 2.
Step take cellphone 3 from shelf
Observation: You pick up the cellphone 3 from the shelf 1.
Step go to desk
Observation: On the desk 1, you see desklamp 1, a keychain 3, mug 2, pen 2, pen and pencil 2.
Below the revised generation provided by Predictive-Decodingg After incorporating foresight and resampling actions, the task could be finished by the same LLM.
Goal: look at bowl under the desklamp.
Observation: You are in the middle of a room. Looking quickly around you, you see bed desk 2, a desk 1, a drawer 6, drawer 5, drawer 4, a drawer 3, a drawer 2, drawer 1, a garbagecan 1, laundryhamper shelf 1.
safe 1, shelf 6, shelf 5, shelf shelf 3, shelf and
('go desk 1:: 0.9975, 'go to desk 2': 0.0025)
20

---

Published as a conference paper at ICLR 2025
Step 1: go to desk
Observation: use desklamp
{'use desklamp I': 0.4530, "examine desklamp 1": 0.5469, 'examine desk 2': 8.55..55111 8.551c-06)
Step use desklamp
Observation: You turn on the desklamp 1.
('examine desk 1": 0.9822, "examine desklamp 1": 0.0177)
Step 3: examine desk 1
Observation: On the desk you see desklamp a keychain 3, mug 2, pen a pen and pencil 2.
{ ('examine desklamp 1:: 0.5711, 'go desk 2'; 0.4289)
Step 4: examine desklamp Observation: Nothing happens.
('go to shelf I': 0.9974, 'go to desk 2'; 0.00258}
Step examine shelf
Observation: On the shelf I, you see cellphone 3, and creditcard 2.
('go desk 2": 0.8146, "go to shelf 2": 0.1853)
Step go to desk
Observation: On the desk 2, you alarmelock 1, bowl and cd 3.
('take bowl from desk 2": 0.9626, 'examine bowl 1": 0.03733)
Step 7: take bowl I from desk 2
Observation: You pick up the bowl from the desk ('go to desk 1": 1.0}
Step go to desk
Observation: On the desk 1. you see desklamp 1, a keychain 3, mug 2, pen 2, pen and pencil 2. The task is finished.
Examples in trajectory pool:
Foresight for the first step (composed of 5 steps):
{ ('Action': None, 'Observation's "You are in the middle of a room.
a looking quickly around you, you see bed 1, desk 2, desk 1, drawer
drawer 3, a drawer 2, drawer 1, a garbagecan 1, a Laundryhanper 1, a safe 1, a shelf 6, shelf * 5, a shelf 4, a shelf 3, shelf 2, and shelf 1.', 'Reward': + -9281983462766966
arawer 6, drawer
d'Action': 'go to desk 1', 'observation's
the desk you see a book + 1, a computer 1, desklamp 1, a notebook 1, and a pen 1.',
G 'Reward': 0. 0.92819934627669661
('Action': 'examine desklamp 1', 'Observation': 'The desklamp 1 is currently turned off.', 'Reward'; 0. (2819983422666666)
['Action': 'use desklamp 1', 'Observation': 'You turn on the desklanp 1
4 .', 'Reward': 0. 928 08889894427666665
21

---

Published as a conference paper at ICLR 2025
('Action': 'examine desk 1', 'Observation's 'On the desk you book 1, a computer
desklamp 1, notebook 1, a pen 1, and + nothing is under the desklamp 1.', 'Reward'; 0. 0.92819834627669661
('Action': 'go to desk 2', 'Observation': 'On the desk 2, you see bowl cup 1, and desklamp 2.', 'Reward': 9.981983462766666)
Foresight for the second step (composed of 5 steps):
{ ('Action': 'go to desk 1', 'Observation': 'On the desk 1, you see
+ desklamp 1, a keychain 3, a mug 2, a pen 2, pen 1, and a pencil 2
.., 'Reward'; 0.92799432928296833
('Action:: 'use desklamp 1', 'Observation': 'You turn on the desklamp 9. .', 'Reward': 0. 0.927994329282988
('Action': 'examine desk 1', 'Observation': 'On the desk 1, you desklamp 1, a keychain 3, a mug 2, a pen 2, pen 1, a pencil 2, s and a drawer 1.', 'Reward'; 0. 0.9279943292829683)
{ d'Action'; 'epen drawer 1', 'Observation': 'You open the drawer 1. Inside, you see bowl 1.", 'Reward'; 0.92799432928296833
('Action': 'take bowl from drawer 1', 'Verified': None, 'Observation's 9 "You pick up the bowl 1 from the drawer 1.", 'Reward'; .92799432928296633
{ ('Action': 'put bowl 1 on desk 1', 'Observation's 'You put the bowl on + the desk 1, under the desklamp 1.', Rewardd': 0. 9279945292829683
Foresight 2 for the second step (composed of 5 steps, lower quality):
('Action': 'go to desk 1', iioservation:: 'On the desk you see mug 2, pen 2, pen and a penci
desklamp 1, keychain
.., 'Reward'; 0. 0.7375880280339422]
( ('Action': 'examine desklamp 1', 'Observation': 'The desklamp 1 is currently turned off.", 'Reward': 0. 0.737568220039942)
{ ('Action': 'use desklamp 1', 'Observation': 'You turn on the desklamp 1
4. .., 'Reward'; 0.
('Action': 'go desk 2', 'Observation': 'On the desk you see book 1, a bowl 1, clock 1, and a stapler 1.', 'Reward': + .73756600880399422)
('Action': 'examine bowl 1', 'Observation': + bowl under the light from the desklamp 1.', 'Reward'; + .7375680280039042|
are now looking at the
('Action': 'inventory', 'Observation': "You have nothing in your inventory.', 'Reward': 0.7375680280039042)
E.2 FAILURE CASE ANALYSIS FOR PREDICTIVE-DECODDING
Here we analyze typical failure cases using Predictive- Detiidive-Decoding We mainly analyze examples where Predietive-Decodiing could be sub-optimal (perform worse than autoregressive generation).
Repetition of in-context examples Several failed cases in the MATH dataset shows repetition of in-context examples in the answer of an unrelated question. This is possibly due to that improving
22

---

Published as a conference paper at ICLR 2025
overall confidence of generation would sometimes result in repetition, the model yields high confidence when copying from in-context examples. This constitutes 1% of the wrong examples on MATH. Below is example of this kind of eπrо.:
Problem: 3 cards are chosen at random from a standard 52-card deck. What the probability that they form a pair? (A 3-card hand is 'pair' if two of the cards match in rank but the third card is different. For example, 668 is a pair, but 999 is not.)
import itertools
import numpy as np
from sympy import symbols, s, simplify
def solution()
digits 11, 3, 4, 5, 91
list_of_integers []
x symbols
expr = 3+ (x**2 x**3 x) (x 2*x**3 - 3xxx=2 + 3*x**5 xxx3) 5
(1 4*x**3 x**2)
= simplify (expr)
x3_coefficiem aaapliffeeeeeppa__coereeee
() [x**3]
result x3_ccefffiieee
return result
Token-level Spelling mistakes few failed cases GSM8K dataset shows minor spelling mistakes in variables, resulting in failed execution. For example, raymond jewels v.s. 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. Below is an example of this kind of error:
def solution():
St_____oeeeeeeeeee___eeeeeeeee > than, half, of, Raymond s, se,jewels., If, Raymond, has, ,40, iel.iieee jewels, hox,.
+ many,, jewels, does, Sicbhan, have?"n*
raymond_jevels
aaron_jewels = (raymond_jews) 2 5
Liobhan_jewell aewen_
result siobhan_jewels
return result
F EXPERIMENT PROMPTS AND PARAMETERS
F.1 IMPLEMENTATIONS AND HYPERPARAMETERS
Large Language Models Table show the source of LLMSs we used in our experiment. We use 1-4 A100s to launch the LLMs with vLLM. The vLLM configuration uses standard configs and use fp16 for all models.
Baseline Implementations
23

---

Published as a conference paper at ICLR 2025
Model Name
Model Code/APl
GPr-o.5-Turbo (Achiam et al.
2023
Azure api: qpt-35-turbo
Mistral-7b (Jiang et al. 2023
mistrralaa/Mistral-78-00001
Llama3-8b (Dubey ct al. 2024
Llama3.1-70b (Dubey ci al. 2024
nete=-LLmm///iamm33311-00------- deegsseekaal//eepseet-ooo
Deepseek-Coder-6.77 (Guo
2024
7b-instruct
Table 9: Model code/API of our evaluated models.
PAL:
We the setting of first generating the entire code and then obtain the answers through Python environment. We use the implementation from Guo et al. (2024).
Beam Search: We use the standard implementation provided by vLLMM
Guided Decoding: We widely used implementation from
Hao et al.
2023).
We reimplement Self-Consistency following (Wang al. 2022). For PAL. generation, we only weight the answers from successful executed code.
Self-Consistency:
We use Self Infilling implementation following Zheng et al. (2023). However this method requires suffix tokens, which is not available for Ilama3. Instead, first generate an entire code and then use logp to heuristically find the start of suffix.
Self Infilling:
Act: We use the implementation from AgentBoard (Ma al. 2024).
ReAct: We reimplement ReAct following Yao al. (2022) Note that LLM could freely choose to alternate between thinking and acting. We find this performs more stably compared compulsory thinking each step.
the setting that
MCTS: We the MCTS implementation from LLM- Reasoness (Hao et al. 2023). How- ever, the original implementation for GSM8K uses subquestions, which is different from other baselines. We unify each step COT format.
Hyperparameters for Main Experiments Table 10 shows the hyperparameters used for main experiments for Trediciive-eeodding Most tasks prefer moderate LLM generation temperature and very low selection temperature. However, we find that Deepseek-Codes prefer otherwise. This is due to Deepseck-Codes Coder generation is more random, making accurate sampling foresight difficult, therefore we need smaller r to prevent overfitting. The FLOPS for Prodictive-Dccdiin is roughly O(KT)), however we use parallel accelerated implementation and the actual speed is roughtly O(To).
For math and coding tasks N Sampling baselines (PAL, COT, Self Infilling) use 0.6, N use = 1.0 if otherwise stated. For agent tasks, Act and ReAct use temperature 0.0.
Beam Search uses the same beam size and best-of-n as N, coding tasks. The FLOPSS for beamsearch is roughly O 2 under this implementation.
for math tasks and N 10 for
Guided Decoding uses the standard hyperparameters from I.MM-Reasone. implementation: beam size = 5, depth limit 16, number of generations for each step = 8, beam search temperature 0.5, and reject minimum reward 0.6.
F.2
PROMPTS
Prompt Details for Coding Tasks
System Prompt
Finish writing the python function. You will only write code blocks. Write # finish after the last line of the function.
Instruction
[Instruction of the problem}
24

---

A:... Published as a conference paper at ICLR 2025
Table 10: Hyperparameters for Predictive-Deccding main experiments.
Method
Model
Task
Hyperparameters
MATH
a= 1.0
GSM8K
1.0 =.01, =,
Llama3-8B
HumanEval
a= =
MBPP
a= 1.0, 0.1, K =8,70
MATH
= 7 =
Mistral-v0.3
Predictive-Decoding
GSMSK
a= 1.0, 0.01, =
HumanEval
a= 1.0, 8.
Deepseek- Coder
MBPP
a= =
Alfworld
a 1=1.0, 1 =
Llama3.1-70B
PDDL
a= 1.0, 0
Alfworld
a= 0.6,66- 0.01, 8,
GPT-35-Turee Turbo (azure API)
PDDL
a == 8
Prompt Details for GSM8K-COT style
System Prompt
You will solve math problems following examples.
Examples
Q: There are 15 trees in the grove. Grove workers will plant trees the grove today. After they done, there will be 21 trees. How many trees did the grove workers plant today? A: There are 15 trees originally. Then there were 21 trees after some more were planted. So there must have been 21 15 6. The answer is 6.
Q: If there are 3 cars in the parking lot and 2 more cars arrive, how many cars are in the parking lot?
A: There are originally 3 cars. 2 more cars arrive. 3 + = The answer is 5.
Q
Instruction
Solve this problem following previous examples: Q: {question}
Prompt Details for GSM8K-PAL style
System Prompt
You will write python program to solve math problems. You will only write code blocks.
Examples
Q: Olivia has $23. She bought five bagels for $3 each. How much money does she have left?
# solution in Python:
def
solution ():
Olivia has $23. She bought five bagels for $3 each.
How much money does she have left 200n money -initial 23
bagels =
bagel_cost
money money_sppent bagels bagel_cost
25

---

Published as a conference paper at ICLR 2025
money-lef -lett money-initie money -ppnt result money left return result
Q: solution in Python:
Instruction
Solve this problem following previous examples: Q: (question) # solution in Python:
def solution ():
Prompt Details for MATH-PAL style
System Prompt
You will write python program to solve math problems. You will only write code blocks.
Examples
Let's write python function to solve math problems. You must return the executed result at the end the function in float. If the final result an expression, return in LaTeX in simplest form. You can only write single function.
Here are some examples:
Question: Find the coefficient of x0 when 3(x² - x² x) 3(x 2x 3x.² +z x²) 5(1 + x 4x x²) is simplifie.
solution in Python:
from sympy import symbols, simplify
def solution ():
x symbols('x*) (xx)
expr 3*(x**2 x843 x) 3+(x + 2*x**3 3*x*#2
\+ 3*x**5 x**3) 5+(1 x 4*x**3 x**2)
simplified.expr = simplify (expr)
x3_coef simplified_expr as.coefficcentss.iee dict 0[x*+3]
result = x3_coef
return result
Q:...
solution in Python:
Instruction
Solve this problem following previous examples: Q: {question] solution in Python:
def solution ():
Prompt Details for AlfWorld
System Prompt
You are a helpful assistant. Generate your next step of action after Action. Action must not be empty. e.g. Action: put down cup.
26

---

Published as a conference paper at ICLR 2025
Instruction
Your task is to interact with a virtual household simulator to accomplish a specific task. With each interaction, you will receive observation. Your role is to decide on action based on the observation. Please ensure that any objects ('obj") and receptacles ("recep") ) you mention in your response are present the observation provided.
Here are the available actions you can take:
take obj from recep
put obj in/on recep
open recep
close recep
toggle obj/recep
clean obj using recep
cool obj using recep
heat obj using recep
inventory
examine recep/obj
go to recep
Examples
Your task to: look at statue under the desklamp. You are in the middle of room. Looking quickly around you, you coffeetable 1, diningtable 1, a drawer 4, a drawer 3, drawer 2, a drawer 1, a dresser 1, garbagecan 1, sidetable 2, sidetable 1, and sofa 1.
Action: go to dresser
Observation: On the dresser 1, you cellphone 3, newspaper statue and
television 1.
Action: take statue from dresser
Observation: You pick up the statue from the dresser 1.
Action: go sidetable
Observation: On the sidetable 1, you see nothing.
Action: go to sidetable
Observation: On the sidetable 2, you see desklamp 3, newspaper 1, and statue 2.
Action: use desklamp 3
Observation: You turn the desklamp 3.
Prompt Details for PDDL
System Prompt
You are master in planning. Generate your next step action after Action. Action must not be empty. e.g. Action: put down cup.
Instruction
The robot has four actions: pickup, putdown, stack, and unstack. The domain assumes world where there are of blocks that can be stacked on top of each other, arm that can hold one block at time, and table where blocks can be placed. The actions defined this domain include:
pickup <block>; allows the arm to pick block from the table if it is clear and the arm empty. After the pickup action, the arm will holding the block, and the block will no longer be on the table clear.
putdown <block> allows the arm to put down a block on the table if is holding a block. After the putdown action, the arm will be empty, and the block will be the table and clear. stack <block> arm is holding the top block and the bottom block is clear. After the stack action, the will be empty, the top block will be on top of the bottom block, and the bottom block will no longer be clear.
allows the arm to stack block on top of another block the
27

---

Published as a conference paper at ICLR 2025
unstack <block> <bl ock>: allows the unstack block from top of another block if the arm is empty and the top block is clear. After the unstack action, the arm will be holding the top block, the top block will no longer be top of the bottom block, and the bottom block will be clear.
Examples
Goal: The goal is to satisfy the following conditions: bl on b2., b2 is on b3. Observation: bl is on the table. b2 is on the table. B3 is on the table. Robot arm is empty. The bl is clear. The b2 is clear. The b3 is clear.
Action: pickup b2
Observation: is on the table. B2 is on the table. The b1 clear. The b3 clear. You are holding 62.
Action: stack b2 b3
Observation: bl is the table. bl is b2. B3 on the table. Robot is empty. The bl is clear. The b2 is clear.
Action: pickup 62.
Observation: The action is not valid and therefore takes no effect. Please remember to satisfy the restriction of actions. You can also check valid actions.
Action: check valid actions.
Observation: valid actions are: pickup b2, unstack b2.
Action: pickup bl
Observation: 62 on b3. B3 on the table. Robot arm is empty. The b2 is clear. You are holding bl.
Action: stack b1 b2
Observation: bl is b2. b2 is b3. B3 is the table. Robot arm is empty. The bl is clear. The goal satisfied.
28


Reviews:
[{"review_id": "bfAbJBeuNw", "reviewer": "Reviewer_fXex", "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.", "questions": "1. how does the number of FLOPS related to # of tokens? And also to the actual decoding/inference time?\n2. how sensitive in the sampling temperature in determining the optimal solution parameter? Do you have to tune this for each test-beds?\n3. it seems the diversity is still an issue even in the MPC problem right? how would you solve it?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The idea of making the LLM to think long term (non-myopic) makes sense for LLM planing and reasoning\n2. 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)?\n2. the introduction of \"Myopic Gap\" seems to be interesting, but the section could be rewritten for better readability. \n3. lacking larger llm model size for math and gsm experimentation.", "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": "kjPgPkbyo7", "reviewer": "Reviewer_iHG8", "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.", "questions": "See the Weaknesses", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. investigate an important problem, i.e. short-sightedness.\n2. Good performance-budget balance in experiments.", "weaknesses": "1. case study? (focusing solely on historical information can lead to irreversible mistakes and potential planning failures.)\n2. The formulation in lines 126-127 is not a POMDP, and lacks of mapping from global states to local observations. \n3. 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?", "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": "4sht4u96dS", "reviewer": "Reviewer_2bKh", "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.", "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?\n\nBroader Applicability: Have the authors considered testing the method on more open-ended tasks, such as advanced data analysis or complex decision-making scenarios? \n\nParameter Sensitivity: Can the authors provide more details on the sensitivity of the method to different hyperparameters (e.g., foresight length, sampling number)?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- The application of Model Predictive Control to mitigate myopia in LLMs is a novel approach that enhances planning accuracy.\n- The paper provides a solid foundation and supports the claims with experimental results.\n- The paper is well-organized, with clear explanations of the problem, methodology, and results.", "weaknesses": "See questions", "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": "sT3TWm4rmg", "reviewer": "Reviewer_4xRU", "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.", "questions": "- Differentiate between the mentioned Lookahead Search and explain what makes Predictive-Decoding unique. \n- Additional experimental results are needed: provide more detailed comparison with TOT and Q*.\n- More specifics about the evaluation process during decoding.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The framework can work on different kinds of tasks.\n- The method makes sense.\n- 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.\n- 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.\n- 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.\n- Many existing papers have suggested that LLMs do not inherently possess self-reflection capabilities. This paper lacks detailed experimental discussion regarding self-feedback abilities.\n\n[1]Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters\n\n[2] Q*: Improving Multi-step Reasoning for LLMs with Deliberative Planning", "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)