# Planning In Natural Language Improves LLM Search For Code Generation

arXiv: https://arxiv.org/abs/2409.03733 · HTML: https://mlsanity.com/paper/2409.03733/

## Key facts

- Cited by 83 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Sep 2024.

## Built on by (most cited first, 30 of 83)

- [SimpleRL-Zoo: Investigating and Taming Zero Reinforcement Learning for Open Base Models in the Wild](https://mlsanity.com/paper/2503.18892/) (2025)
- [A Survey on Test-Time Scaling in Large Language Models: What, How, Where, and How Well?](https://mlsanity.com/paper/2503.24235/) (2025)
- [Is Your LLM Secretly a World Model of the Internet? Model-Based Planning for Web Agents](https://mlsanity.com/paper/2411.06559/) (2024)
- [AutoGLM: Autonomous Foundation Agents for GUIs](https://mlsanity.com/paper/2411.00820/) (2024)
- [SafeBench: A Safety Evaluation Framework for Multimodal Large Language Models](https://mlsanity.com/paper/2410.18927/) (2024)
- [The Limits of Inference Scaling Through Resampling](https://mlsanity.com/paper/2411.17501/) (2024)
- [A Survey on Large Language Models for Mathematical Reasoning](https://mlsanity.com/paper/2506.08446/) (2025)
- [Code to Think, Think to Code: A Survey on Code-Enhanced Reasoning and Reasoning-Driven Code Intelligence in LLMs](https://mlsanity.com/paper/2502.19411/) (2025)
- [Code as Agent Harness](https://mlsanity.com/paper/2605.18747/) (2026)
- [DrugAgent: Automating AI-aided Drug Discovery Programming through LLM Multi-Agent Collaboration](https://mlsanity.com/paper/2411.15692/) (2024)
- [Agent-RLVR: Training Software Engineering Agents via Guidance and Environment Rewards](https://mlsanity.com/paper/2506.11425/) (2025)
- [LLMs as Planning Formalizers: A Survey for Leveraging Large Language Models to Construct Automated Planning Models](https://mlsanity.com/paper/2503.18971/) (2025)
- [Surveying the Effects of Quality, Diversity, and Complexity in Synthetic Data From Large Language Models](https://mlsanity.com/paper/2412.02980/) (2024)
- [Optimizing Temperature for Language Models with Multi-Sample Inference](https://mlsanity.com/paper/2502.05234/) (2025)
- [RefactorBench: Evaluating Stateful Reasoning in Language Agents Through Code](https://mlsanity.com/paper/2503.07832/) (2025)
- [RethinkMCTS: Refining Erroneous Thoughts in Monte Carlo Tree Search for Code Generation](https://mlsanity.com/paper/2409.09584/) (2024)
- [B-STaR: Monitoring and Balancing Exploration and Exploitation in Self-Taught Reasoners](https://mlsanity.com/paper/2412.17256/) (2024)
- [GSO: Challenging Software Optimization Tasks for Evaluating SWE-Agents](https://mlsanity.com/paper/2505.23671/) (2025)
- [A Survey on LLM Test-Time Compute via Search: Tasks, LLM Profiling, Search Algorithms, and Relevant Frameworks](https://mlsanity.com/paper/2501.10069/) (2025)
- [Structured Scaling of AI Discovery Across Diverse Scientific Domains](https://mlsanity.com/paper/2604.19341/) (2026)
- [Self-Generated In-Context Examples Improve LLM Agents for Sequential Decision-Making Tasks](https://mlsanity.com/paper/2505.00234/) (2025)
- [RPG: A Repository Planning Graph for Unified and Scalable Codebase Generation](https://mlsanity.com/paper/2509.16198/) (2025)
- [On the Effect of Sampling Diversity in Scaling LLM Inference](https://mlsanity.com/paper/2502.11027/) (2025)
- [Rethinking Inference-Time Scaling: Efficiency Limits and Linguistic Signals](https://mlsanity.com/paper/2504.14047/) (2025)
- [CER: Confidence Enhanced Reasoning in LLMs](https://mlsanity.com/paper/2502.14634/) (2025)
- [Large Language Models (LLMs) for Source Code Analysis: applications, models and datasets](https://mlsanity.com/paper/2503.17502/) (2025)
- [PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving](https://mlsanity.com/paper/2502.16111/) (2025)
- [Generative AI Act II: Test Time Scaling Drives Cognition Engineering](https://mlsanity.com/paper/2504.13828/) (2025)
- [Teaching LLMs to Plan: Logical Chain-of-Thought Instruction Tuning for Symbolic Planning](https://mlsanity.com/paper/2509.13351/) (2025)
- [Optimizing Sequential Multi-Step Tasks with Parallel LLM Agents](https://mlsanity.com/paper/2507.08944/) (2025)

## Abstract (arXiv)

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.