Planning In Natural Language Improves LLM Search For Code Generation

Evan Wang, Federico Cassano, Catherine Wu, Yunfeng Bai, Will Song, Vaskar Nath, Ziwen Han, Sean Hendryx, Summer Yue, Hugh Zhang

TL;DR

Scaling inference-time compute (search) for LLMs often hits a wall because models repeatedly sample similar, incorrect solutions. This paper introduces PLANSEARCH, a novel algorithm that searches over natural language "idea space" to force diversity, nearly doubling the performance of state-of-the-art models like Claude 3.5 Sonnet on competitive coding benchmarks.

What Problem Does This Paper Address?

The "Bitter Lesson" of AI suggests that scaling two things leads to progress: learning and search. While scaling training compute (learning) has led to the current LLM revolution, scaling inference compute (search) has been less successful.

The authors identify a core bottleneck: a lack of diversity. Most LLMs, especially those post-trained to be helpful chatbots, are optimized to produce a single "correct" answer. When you ask them for 200 solutions to a hard coding problem (a method called Repeated Sampling), they often give you 200 slight variations of the same wrong idea. If the underlying conceptual approach is flawed, generating more code won't fix it.

Methods

Instead of searching over individual tokens or entire programs, PLANSEARCH searches over natural language plans. The process follows a structured trajectory:

  1. Generate Diverse Observations: The model is prompted to generate several "first-order" observations or hints about the problem (e.g., "Use a hashmap," "This looks like a greedy search").
  2. Combinatorial Expansion: These observations are grouped into subsets to inspire "second-order" observations, creating a tree of ideas.
  3. Strategy to Code: For each leaf node in this idea tree, the model generates a natural language strategy, translates that into pseudocode, and finally implements the actual Python code.
Figure 2: An example trajectory of PLANSEARCH, which searches over plans in natural language as a method of increasing diversity in the search process. PLANSEARCH first generates observations, then combinatorially samples subsets of these observations to generate the next step in the search process. To generate the next layer of observations, the combinations derived from the first observations are used as a stepping stone to generate the next observations, and the process repeats. After generating both the first and second order observations, PLANSEARCH then generates a natural language description of a strategy to solve the problem. For additional diversity, the model is prompted to regenerate its strategy as an additional sample before generating code. See Section 4.3 for additional discussion.

By forcing the model to commit to different conceptual observations before writing a single line of code, PLANSEARCH ensures the resulting pool of solutions is conceptually diverse.

Datasets

The authors evaluated their method on three major coding benchmarks:

  • HumanEval+ and MBPP+: Enhanced versions of classic benchmarks with more rigorous test cases to prevent "reward hacking."
  • LiveCodeBench: A "contamination-free" benchmark consisting of recent competitive programming problems. The authors specifically used problems from May to September 2024 to ensure models like Claude 3.5 Sonnet (with an April 2024 cutoff) hadn't seen them during training.

Key Insights and Ideas

  • The "Instruct Model Paradox": Instruction-tuned models are much better at providing a single correct answer (pass@1) than base models. However, because they are so "peaky," they lack diversity. As the number of samples ($k$) increases, base models often catch up or even outperform instruct models because they explore a wider range of ideas.
  • Idea Space is the Right Abstraction: Through "backtranslation" experiments (turning correct code into natural language sketches), the authors showed that if a model gets the high-level idea right, it can almost always implement the code correctly.
  • Predicting Search Gains: The authors introduced a diversity score ($D$) based on LLM-as-a-judge pairwise comparisons of ideas. They found that this diversity score is a highly accurate predictor of how much a model's performance will improve when you scale search.
Figure 3: Despite DeepSeek-Coder-V2-Lite-Base having significantly lower pass@1 than its instruct counterpart, we observe that this trend reverses as k increases, suggesting that the instruct model has less diversity than its base model counterpart. We observe this trend for many, but not all, models and benchmarks, and provide the full data in Appendix I.

Key Results

PLANSEARCH consistently outperformed standard repeated sampling across all models and benchmarks:

  • Claude 3.5 Sonnet: Achieved a pass@200 of 77.0% on LiveCodeBench using PLANSEARCH, compared to 60.6% with standard repeated sampling and 41.4% for a single sample.
  • Efficiency: Running PLANSEARCH on a small model (GPT-4o-mini) outperformed much larger models that weren't using search after only 4 attempts.
  • Public Test Filtering: By using the few public test cases provided in coding problems to filter out bad candidates, the authors could achieve the same 77% accuracy with only 20 submissions instead of 200.
Figure 1: Comparison of REPEATED SAMPLING, both pass@1 and pass@k, and our novel method PLANSEARCH. On every model, our method outperforms baselines by a wide margin, with the best model-method combination of Claude 3.5 Sonnet / PLANSEARCH achieving performance nearly double that of the best model without search.

Limitations and Future Work

  • Compute Cost: PLANSEARCH requires generating many intermediate natural language steps, which increases the token count per solution. However, the authors show that when normalized for compute, PLANSEARCH still wins once you are willing to spend more than ~10,000 tokens per problem.
  • Uniform Search: Currently, the algorithm explores all branches of the observation tree uniformly. The authors suggest that future work could use Monte-Carlo Tree Search (MCTS) to dynamically prune unpromising ideas and focus compute on the most likely solutions.
  • Post-Training for Search: The authors argue that the current LLM training paradigm (optimizing for one right answer) is fundamentally at odds with search. They suggest re-imagining post-training to specifically optimize for a balance of quality and diversity.

Summary updated

Abstract

While scaling training compute has led to remarkable improvements in large language models (LLMs), scaling inference compute has not yet yielded analogous gains. We hypothesize that a core missing component is a lack of diverse LLM outputs, leading to inefficient search due to models repeatedly sampling highly similar, yet incorrect generations. We empirically demonstrate that this lack of diversity can be mitigated by searching over candidate plans for solving a problem in natural language. Based on this insight, we propose PlanSearch, a novel search algorithm which shows strong results across HumanEval+, MBPP+, and LiveCodeBench (a contamination-free benchmark for competitive coding). PlanSearch generates a diverse set of observations about the problem and then uses these observations to construct plans for solving the problem. By searching over plans in natural language rather than directly over code solutions, PlanSearch explores a significantly more diverse range of potential solutions compared to baseline search methods. Using PlanSearch on top of Claude 3.5 Sonnet achieves a state-of-the-art pass@200 of 77.0% on LiveCodeBench, outperforming both the best score achieved without search (pass@1 = 41.4%) and using standard repeated sampling (pass@200 = 60.6%). Finally, we show that, across all models, search algorithms, and benchmarks analyzed, we can accurately predict performance gains due to search as a direct function of the diversity over generated ideas. Code can be found at https://github.com/scaleapi/plansearch.
BibTeX
@inproceedings{wang2025planning,
  author = {Evan Wang and Federico Cassano and Catherine Wu and Yunfeng Bai and Will Song and Vaskar Nath and Ziwen Han and Sean Hendryx and Summer Yue and Hugh Zhang},
  title = {{Planning In Natural Language Improves LLM Search For Code Generation}},
  booktitle = {International Conference on Learning Representations},
  year = {2025},
  url = {https://openreview.net/forum?id=48WAZhwHHw},
}
Figure