Planning with Large Language Models for Code Generation

By Shun Zhang, Zhenfang Chen, Yikang Shen, Mingyu Ding, Josh Tenenbaum, Chuang Gan. 2023

256 citations recorded by the source corpus.

Existing large language model-based code generation pipelines typically use beam search or sampling algorithms during the decoding process. Although the programs they generate achieve high token-matching-based scores, they often fail to compile or generate incorrect outputs. The main reason is that conventional Transformer decoding algorithms may not be the best choice for code generation. In this work, we propose a novel Transformer decoding algorithm, Planning-Guided Transformer Decoding (PG-TD), that uses a planning algorithm to do lookahead search and guide the Transformer to generate better programs. Specifically, instead of simply optimizing the likelihood of the generated sequences, the Transformer makes use of a planner to generate candidate programs and test them on public test cases. The Transformer can therefore make more informed decisions and generate tokens that will eventually lead to higher-quality programs. We also design a mechanism that shares information between the Transformer and the planner to make our algorithm computationally efficient. We empirically evaluate our framework with several large language models as backbones on public coding challenge benchmarks, showing that 1) it can generate programs that consistently achieve higher performance compared with competing baseline methods; 2) it enables controllable code generation, such as concise codes and highly-commented codes by optimizing modified objective.

Subfields: Artificial Intelligence, Information Systems, Software, Large Language Models, Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

In Software

In Large Language Models

In Natural Language Processing

Citations in the corpus

Code Llama: Open Foundation Models for Code (2023, background): “A recent stream of work takes into account program execution or unit tests to filter, cluster, or improve the correctness of programs when few candidates must be submitted (Li et al., 2022; Chen et al., 2023a; Le et al., 2022; Zhang et al., 2023), or unit tests them within a reinforcement learning o”
Large Language Models as Commonsense Knowledge for Large-Scale Task Planning (2023, methodology): “On the other hand, similar to our work, some studies try to use LLMs as heuristics [42] or transition function [13] in MCTS, boosting the performance in coding or small-scale reasoning.”
Tree of Thoughts: Deliberate Problem Solving with Large Language Models (2023, background): “As they are trained on vast amount of world knowledge and human examples, LMs are known to have already absorbed rich commonsense that makes it possible to propose reasonable plans conditioned on problem setting and environmental states [10, 39, 34, 11, 32, 38, 37].”
LLM-Assisted Code Cleaning For Training Accurate Code Generators (2023, methodology): “Zhang et al. (2023c) proposed a lookahead-search-based decoding algorithm for improving reasoning in LLM S and is orthogonal to our work.”
ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution (2024, unknown): “…(Chen et al., 2023c; Liventsev et al., 2023), enhancing code performance (Madaan et al., 2023a), solving algorithmic competition challenges (Li et al., 2022; Shinn et al., 2023), robotics (Liang et al., 2023; Wang et al., 2023b), and general task solving (Yang et al., 2023b; Zhang et al., 2022).”
Graph of Thoughts: Solving Elaborate Problems with Large Language Models (2023, background): “In this work, we harness the graph abstraction as a key mechanism that enhances prompting capabilities in LLMs.”
Large Language Models for Software Engineering: Survey and Open Problems (2023, methodology): “For example, Zhang et al. [66], [67] reported improvements over baselines of between approximately 11% and 27%, while Zhang et al. [68] hybridized code generation with API search techniques.”
A Survey of Large Language Models (2023, unknown): “planning-guided decoding [345], which can be considered as the imitation of bug-fixing and code-planning processes by programmers.”
Consistent estimation of generative model representations in the data kernel perspective space (2024, background): “Generative models have gained popularity in natural language processing [4, 20], text-to-image generation [7], and code generation [24], as well as in other domains [1, 21].”
Concentration bounds on response-based vector embeddings of black-box generative models (2025, unknown): “Generative models in artificial intelligence have found ubiquitous use in natural language processing (Devlin et al., 2019; Brown et al., 2020; Sanh et al., 2022), code generation (Zhang et al., 2023) and text-to-image generation (Crowson et al., 2022).”