Research map / Large language models / Agents, code and math
Non-myopic Generation of Language Models for Reasoning and Planning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Predictive-Decoding, a training-free method that reweights LLM action distributions using sampled foresight rollouts (Model Predictive Control view) to reduce myopic planning in math, coding, and agent tasks.
Problem
Autoregressive LLM decoding is myopic, so planning errors made early in multi-step reasoning or agent trajectories are hard to avoid; LLMs also struggle to evaluate intermediate steps without foresight.
Approach
Frames LLM planning as Model Predictive Control and resamples each action using a softmax-weighted distribution over K foresight rollouts of length T0 (sampling-importance-resampling), with a trajectory pool that recycles overlapping rollouts; requires no training.
Key results
- On GSM8K, Predictive-Decoding with Llama-3-8B improves accuracy to 78.5% vs 71.3% autoregressive PAL, and 81.3% with Self-Consistency.
- On AlfWorld with Llama-3.1-70B, success rate rises to 44.0% vs 19.4% for Act.
- With Math-Shepherd reward model on GSM8K, Predictive-Decoding+RM reaches 89.9% vs 86.5% for Guided-Decoding+RM at higher compute, and 87.9% at lower compute.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Predictive-Decoding instead of autoregressive PAL | Llama-3 8B · GSM8K | accuracy: 71.3 -> 78.5 | Helped |
| use Predictive-Decoding instead of autoregressive PAL | Llama-3 8B · MATH | accuracy: 29.7 -> 34.0 | Helped |
| add Self-Consistency to Predictive-Decoding | Llama-3 8B · GSM8K | accuracy: 78.5 -> 81.3 | Helped |
| add Self-Consistency to Predictive-Decoding | Llama-3 8B · MATH | accuracy: 34.0 -> 40.3 | Helped |
| use Predictive-Decoding instead of Beam Search | Llama-3 8B · MATH | accuracy: 34.4 -> 34.0 | Hurt |
| use Predictive-Decoding instead of Beam Search | Deepseek-Coder 6.7B · MBPP | pass@1: 39.7 -> 34.0 | Hurt |
| use Predictive-Decoding instead of ReAct | GPT-3.5 Turbo · AlfWorld | success: 7.5 -> 14.9 | Helped |
| use Predictive-Decoding instead of ReAct | GPT-3.5 Turbo · PDDL | success: 3.3 -> 11.7 | Helped |
| increase foresight from T_0=1 to T_0=6 (ablation) | Predictive-Decoding · HumanEval | pass@1: 45.1 -> 57.3 | Helped |
| increase foresight from T_0=1 to T_0=6 (ablation) | Predictive-Decoding · GSM8K | accuracy: 77.0 -> 78.5 | Helped |
| increase sampling number from K = 2 to K = 8 (ablation) | Predictive-Decoding · HumanEval | pass@1: 51.2 -> 57.3 | Helped |
| increase sampling number from K = 2 to K = 8 without trajectory recycle (ablation) | Predictive-Decoding · HumanEval | pass@1: 47.6 -> 49.4 | No clear effect |
Surprising findings
- Around 60% of GSM8K/MATH examples show myopic planning under the paper's gap measure, with most errors occurring in myopic cases.
- GPT-3.5-Turbo self-evaluation of intermediate AlfWorld steps has very low correlation (0.133) with human labels without foresight.
Limitations
- Limited to tasks with clear reasoning steps such as math or coding; not tested on free-form or long-context generation.
- Agent world-model hallucinations degrade foresight evaluation, requiring higher sampling temperature.
- Does not explore using the method to generate training data.
Experimental setup
Datasets: GSM8K MATH HumanEval MBPP AlfWorld PDDL
Benchmarks: GSM8K MATH HumanEval MBPP AlfWorld PDDL
Metrics: accuracy pass@1 pass@10 success rate progress rate FLOPS
Baselines: Chain-of-Thought PAL Beam Search Self-Consistency Guided-Decoding MCTS Self-Infilling ReAct Act
Builds on: Model Predictive Control energy-based model sampling ReAct Chain-of-Thought Beam Search
Closest papers by meaning
- LLMs Can Plan Only If We Tell Them (ICLR 2025 · similarity 0.91)
- PlanU: Large Language Model Reasoning through Planning under Uncertainty (NeurIPS 2025 · similarity 0.90)
- Can LLMs Fix Issues with Reasoning Models? Towards More Likely Models for AI Planning (AAAI 2024 · similarity 0.89)
- Planning in the Dark: LLM-Symbolic Planning Pipeline Without Experts (AAAI 2025 · similarity 0.89)
- SPIRAL: Symbolic LLM Planning via Grounded and Reflective Search (AAAI 2026 · similarity 0.89)
- Thought of Search: Planning with Language Models Through The Lens of Efficiency (NeurIPS 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.