Research map / Large language models / Agents, code and math
Planning in Natural Language Improves LLM Search for Code Generation
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 PlanSearch, which searches over diverse natural-language plans (observations combined into ideas) before generating code, improving pass@k on LiveCodeBench, HumanEval+, and MBPP+ over repeated sampling.
Problem
LLM inference-time search for code generation is inefficient because models repeatedly sample highly similar, incorrect solutions, lacking output diversity.
Approach
Search over diverse natural-language plans (generated observations combined over subsets, then turned into ideas and code) rather than directly over code, which increases idea-level diversity and thus pass@k; diversity score predicts search gains.
Key results
- PlanSearch on Claude 3.5 Sonnet reaches pass@200 of 77.0% on LiveCodeBench vs. 41.4% pass@1 without search and 60.6% pass@200 for GPT-4o repeated sampling.
- PlanSearch improves pass@200 over repeated sampling across all four non-search models on LiveCodeBench, HumanEval+, and MBPP+ (e.g., GPT-4o-mini LCB 53.3 to 64.9).
- Public test filtering lets PlanSearch reach 77.1% on LiveCodeBench at pass@20.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Search over observation-derived natural-language plans instead of repeatedly sampling code | Claude-Sonnet-3.5 · LiveCodeBench | pass@200: 55.6 -> 77.0 | Helped |
| Search over observation-derived natural-language plans instead of repeatedly sampling code | Claude-Sonnet-3.5 · HumanEval+ | pass@200: 88.9 -> 98.5 | Helped |
| Search over observation-derived natural-language plans instead of repeatedly sampling code | Claude-Sonnet-3.5 · MBPP+ | pass@200: 83.0 -> 93.7 | Helped |
| Use PlanSearch rather than IdeaSearch | GPT-4o-mini · LiveCodeBench | pass@200: 59.4 -> 64.9 | Helped |
| Use PlanSearch rather than IdeaSearch | GPT-4o · HumanEval+ | pass@200: 97.6 -> 99.5 | Helped |
| Use PlanSearch rather than IdeaSearch | DeepSeek-Coder-V2 · MBPP+ | pass@200: 89.1 -> 92.6 | Helped |
| Use PlanSearch rather than repeated sampling | o1-mini · LiveCodeBench | pass@200: 90.8 -> 91.3 | Helped |
| Apply public test filtering to PlanSearch | Claude-Sonnet-3.5 · LiveCodeBench | pass@20: 77.1% | Helped |
| Increase maximum observation subset size from 2 to 3 (ablation) | PlanSearch · LiveCodeBench | pass@k | No clear effect |
| Increase the number of observation-tree layers (ablation) | PlanSearch · LiveCodeBench | pass@k | Helped |
| Remove the translation step that converts observation combinations to code (ablation) | PlanSearch · LiveCodeBench | pass@k | Hurt |
| Skip pseudocode translation (ablation) | PlanSearch · LiveCodeBench | pass@k | Mixed |
Surprising findings
- PlanSearch often lowers pass@1 (e.g., Sonnet 3.5 on LiveCodeBench) while raising pass@k.
- Base models with public test filtering often exceed their instruct counterparts at pass@1, and instruct models can underperform base models at high k.
Limitations
- PlanSearch hurts pass@1 and only beats repeated sampling at larger k (k of 4 or more).
- Search is uniform over leaf nodes and limited to depth 2 due to compute cost; o1-mini results are saturated and costly to evaluate.
- pass@k estimator is theoretically biased for PlanSearch because samples are not independent.
Experimental setup
Datasets: LiveCodeBench HumanEval+ MBPP+
Benchmarks: LiveCodeBench HumanEval+ MBPP+
Metrics: pass@k pass@1 diversity score
Baselines: Repeated Sampling IdeaSearch Chain-of-Thought o1-mini repeated sampling
Builds on: repeated sampling chain-of-thought Tree of Thoughts best-of-n sampling
Closest papers by meaning
- Thought of Search: Planning with Language Models Through The Lens of Efficiency (NeurIPS 2024 · similarity 0.91)
- Let's Revise Step-by-Step: A Unified Local Search Framework for Code Generation with LLMs (NeurIPS 2025 · similarity 0.89)
- CodePlan: Unlocking Reasoning Potential in Large Language Models by Scaling Code-form Planning (ICLR 2025 · similarity 0.89)
- Simple Baselines are Competitive with Code Evolution (NeurIPS 2026 · similarity 0.88)
- Automating Thought of Search: A Journey Towards Soundness and Completeness (Student Abstract) (AAAI 2025 · similarity 0.88)
- AlphaZero-Like Tree-Search can Guide Large Language Model Decoding and Training (ICML 2024 · similarity 0.88)
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.