Reproduce “Non-myopic Generation of Language Models for Reasoning and Planning” on OpenResearch

About this paper

Chang Ma, Haiteng Zhao, Junlei Zhang, Junxian He, Lingpeng Kong

Researchers from The University of Hong Kong, Peking University, Zhejiang University, and The Hong Kong University of Science and Technology introduce Predictive-Decoding, a training-free approach inspired by Model Predictive Control to address the myopic nature of Large Language Model (LLM) autoregressive planning. The method re-weights LLM output distributions for current actions based on evaluations of sampled future trajectories, enhancing reasoning and planning accuracy across math, coding, and agent tasks while demonstrating superior computational efficiency compared to existing search-based methods.

Key insights

• LLM autoregressive planning exhibits a measurable "myopic gap" in approximately 60% of cases, with this myopia being more pronounced in incorrect solutions (76.5% of GSM8K errors).
• LLMs can better identify planning mistakes when foresight (considering future steps) is incorporated, suggesting a need for explicit lookahead mechanisms.
• Framing LLM reasoning as an optimal control problem, specifically drawing from Model Predictive Control, provides a theoretically grounded method to mitigate myopic behavior.

Summary by alphaXiv.