Planning In Natural Language Improves LLM Search For Code Generation

• 77.0% pass@200 on LiveCodeBench with Claude 3.5 Sonnet / PlanSearch exceeds pass@1 = 41.4% without search and pass@200 = 60.6% with standard repeated sampling.The paper reports similar improvements on HumanEval+ and MBPP+.Source: Figure 1 · p. 2, §1 · p. 3
• Instruction-tuned models often lead base models at pass@1, but that advantage can disappear or reverse when generating many samples.The paper presents this as evidence that instruction-tuned models may have less diversity in some settings.Source: §1 · p. 2
• The authors hypothesize that low high-level output diversity limits inference-time search, especially when repeated sampling produces highly similar incorrect programs.They note that single-sample performance alone does not capture model quality when more inference-time compute is available.Source: §1 · pp. 1–2
• Correct solution sketches support correct programs, and a sketch’s correctness captures much of the variation in whether a generated solution passes.The authors report that accuracy conditioned on a particular self-generated sketch tends toward either 0% or 100%.Source: §1 · p. 2
• PlanSearch generates problem observations, combines subsets into candidate plans, and translates those plans into code, outperforming repeated sampling and IdeaSearch.The model can regenerate its natural-language strategy for an additional sample before code generation.Source: §1 · p. 3, Figure 2 · p. 3
• Across the analyzed models, search algorithms, and benchmarks, idea diversity is highly correlated with performance gains from search.The authors present this correlation as support for the role of exploring plans in idea space.Source: §1 · p. 3

2.1 Search in Classical AI

• Classical search methods, including breadth-first search, depth-first search, A*, and Monte Carlo Tree Search, have been used for pathfinding, planning, optimization, and game playing.Work on board games has also found logarithmic ELO improvement with increased inference-time compute.Source: §2.1 · p. 4

2.2 Search with Language Models

• Repeated sampling generates many code candidates directly, while PlanSearch searches over latent ideas before producing code to increase output diversity.Prior natural-language planning approaches often focus on contrived tasks with obvious search steps, unlike code generation as presented here.Source: §2.2 · p. 4
• For many models and benchmarks, an instruct model’s pass@1 advantage over its base counterpart disappears or reverses as k increases, suggesting lower diversity in some instruct models.The reported pattern does not hold for every model and benchmark.Source: Figure 3 · p. 5
• Prior work explores language-model search through repeated sampling, natural-language planning, and tool-using agents; PlanSearch instead induces diversity at inference time without training a model to search.The paper positions this as a way to adapt an LLM API not designed for search.Source: §2.2 · pp. 4–5

3. Motivation

• Code search can test generated programs against provided cases, often avoiding the harder task of selecting a correct answer from many open-ended outputs.The paper contrasts code search with domains such as poetry, where choosing the correct generation is difficult.Source: §3 · p. 5

3.1 Defining the Search Space

• The authors test natural-language idea space as a search space, motivated by the hypothesis that the right solution sketch describes the correct program.They identify the sketch as a natural-language description of the correct program and test the idea using GPT-4o-mini on LiveCodeBench.Source: §3.1 · pp. 5–6

3.2 Backtranslation

• A correct backtranslated sketch improves accuracy, with the paper reporting relatively high accuracy even when the sketch is only 10 tokens long.Accuracy increases with sketch length.Source: §3.2 · p. 6, Figure 4 · p. 6

3.3 Conditioning on Idea Quality

• Conditioning on a sketch polarizes solve rates toward 0 or 1, suggesting that whether the idea is correct explains substantial performance variation.The authors propose searching for correct sketches and observations before generating code.Source: §3.3 · p. 7

4.1 REPEATED SAMPLING

• Repeated sampling generates code solutions directly until one passes tests or the sample limit is reached.The baseline uses few-shot problem-solution examples.Source: §4.1 · p. 7

4.2 IDEASEARCH

• IDEASEARCH first asks one LLM instance for a natural-language solution, then has another implement it; articulating an idea increases diversity.The method isolates the effect of providing a solution sketch and gives non-negligible gains over chain-of-thought prompting.Source: §4.2 · p. 8

4.3 PLANSEARCH

• PLANSEARCH first generates observations, combines them into candidate plans, and searches those plans rather than tokens, code lines, or whole programs.The method is motivated by narrow changes in sampled code that fail to address idea-level pitfalls.Source: §4.3 · p. 8, §4.3.1 · p. 8

4.3.1 Prompting for Observations

• PLANSEARCH prompts for typically 3 to 6 first-order observations and forms all subsets of size at most two.The exact number of observations depends on the LLM output.Source: §4.3.1 · p. 8

4.3.2 Deriving New Observations

• It expands observation combinations into second-order observations, but truncates the resulting tree at depth two for computational constraints.Generated observations need not be correct; they serve to elicit a more diverse set of ideas.Source: §4.3.2 · p. 8

4.3.3 Observations to Code

• For each leaf, the model uses the problem and observations to produce a natural-language solution, then generates a second idea by soliciting criticism of the first.The criticism step doubles the number of proposed ideas.Source: §4.3.3 · pp. 8–9
• Each natural-language solution is translated into pseudocode and then Python to reduce translation error that could cause the model to disregard the observations.Source: §4.3.3 · p. 9

5.3 Results

• 77.0 pass@200 on LiveCodeBench is reported for PlanSearch with Claude 3.5 Sonnet, versus 41.4 for the top model without search.The results report improvements over existing methods across all evaluated models and benchmarks.Source: §5 · p. 9, §5.3 · p. 11

5.1 Datasets

• We evaluate search methods on MBPP+, HumanEval+, and LiveCodeBench; a May 2024 cutoff was used for all models to reduce contamination risk given Claude 3.5 Sonnet’s April 2024 knowledge cutoff.Source: §5.1 · pp. 9–10

5.2 Experiment Details

• Repeated Sampling and IdeaSearch generate exactly n codes, while PlanSearch usually generates about 300 to 400; pass@k uses an unbiased estimator.When k exceeds n, remaining generations are assumed not to pass.Source: §5.2 · p. 11

5.4 Public Test Filtering

• 77.1% accuracy on LiveCodeBench after 20 submissions is reported with public-test filtering, compared with pass@200 of 77.0% without filtering.Filtering selects samples that pass public tests before final submission.Source: §5.4 · p. 11

6. Analysis

• PLANSEARCH and IDEASEARCH outperform basic sampling by a wide margin, and PLANSEARCH achieves the best scores across methods and models.The analysis presents results normalized by attempts per completion; compute-normalized results are described as similar when sufficient inference-time compute is spent.Source: §6 · pp. 11–12
• IDEASEARCH performs somewhat better than the Chain-of-Thought baseline; the authors speculate this may reflect splitting sketch and code generation into separate responses.The authors contrast that setup with producing chain-of-thought and code in one response.Source: §6 · p. 12
• Diversity scores account for much of the variation in relative pass@k gains across methods and models on the same dataset, suggesting they can proxy for those gains.The analysis notes that pass@k trends differ across models and relates some of those differences to idea diversity.Source: §6 · p. 12
• PLANSEARCH can slightly reduce pass@1 while increasing the chance that a pool contains a correct idea, allowing pass@k to surpass less diverse pools.The analysis notes this tradeoff for several models, including Claude 3.5 Sonnet on LiveCodeBench.Source: §6 · p. 12

6.1 Measuring Diversity

• Idea-space diversity is highly predictive of relative improvement from pass@1 to pass@200, while ordinary entropy can miss differences in the underlying ideas of generated programs.The authors contrast minor variations of one program with programs based on different ideas, even when the models have equal entropy.Source: §6.1 · p. 12, Figure 6 · p. 13
• The diversity score compares generated programs pairwise using LLM judgments of whether their ideas are similar, with the reported score averaged across problems.For large pools, the procedure samples 40 codes; it backtranslates code into natural language before comparing each pair using code and its corresponding idea, with GPT-4o-mini as the supporting LLM.Source: §6.1 · pp. 12–13

7. Limitations and Future Work

• The authors argue that diversity improvements should also come from post-training, requiring objectives oriented toward search rather than only a single correct response.They identify improved post-training objectives that maximize quality and diversity as future work.Source: §7 · p. 13
• PLANSEARCH and IDEASEARCH trade a slight deterioration in pass@1 for stronger pass@k, and PLANSEARCH does not significantly outperform repeated sampling on LiveCodeBench until k ≥4.The authors note that in many domains outside code generation, running an LLM for more than a few attempts may be infeasible.Source: §7 · p. 13
• Public-test filtering can improve PLANSEARCH pass@1 significantly above repeated sampling, and filtering methods can shift high-k performance toward pass@1.The authors present filtering as a way to extract search gains into a single answer.Source: §7 · pp. 13–14
• The authors propose training the underlying model on successful PLANSEARCH plans and code as a possible way to distill pass@k gains into pass@1 without inference-time filtering.They suggest this could reduce the likelihood of following unfavorable branches of the search tree.Source: §7 · p. 14

A. Full Pass@K curves for All Models and All Benchmarks

• Pass@k curves for all models and methods are plotted over k=1–200 for HumanEval+, MBPP+, and LiveCodeBench.The appendix identifies Figures 7, 8, and 9 for those three benchmarks, respectively.Source: A. Full Pass@K curves for All Models… · p. 20, Figure 7 · p. 20, Figure 8 · p. 21

B. Full Pass@k Curves with Public Filtering

• The appendix plots pass@k curves with public-test filtering over k=1–20 for HumanEval+ and MBPP+, and identifies a corresponding LiveCodeBench plot.The HumanEval+ and MBPP+ plots are Figures 10 and 11; the prose also references Figure 5 for LiveCodeBench.Source: B. Full Pass@k Curves with Public… · p. 23, Figure 10 · p. 23, Figure 11 · p. 24

C. Average Relative Improvements

• Average relative-improvement curves compare each method’s pass@k with repeated sampling’s pass@1 across models on HumanEval+, MBPP+, and LiveCodeBench.Separate figures are identified for the public-test-filtered versions.Source: C. Average Relative Improvements · p. 25, Figure 12 · p. 25, Figure 13 · p. 26

D. Compute Normalized Pass@K Graphs

• With compute normalized across methods, PLANSEARCH begins to outperform repeated sampling when users are willing to sample at least 10,000 tokens per problem.The figure reports roughly 244 tokens per completion per problem for repeated sampling and roughly 1,428 for PLANSEARCH.Source: Figure 18 · p. 29, D. Compute Normalized Pass@K Graphs · p. 29

E. Comparison with Chain-of-Thought

• The appendix provides Chain-of-Thought comparison plots for all three benchmarks, both with and without public-test filtering.Figures 19–21 show the unfiltered comparisons; Figures 22–24 show the filtered versions.Source: E. Comparison with Chain-of-Thought · p. 30, Figure 19 · p. 30, Figure 20 · p. 31

F. Ablation on Temperature for REPEATED SAMPLING and IDEASEARCH

• At higher temperatures, REPEATED SAMPLING and IDEASEARCH both improve pass@k, though the gains may begin to plateau.The sweep uses increments of 0.1 from 0.0 to 1.2, inclusive, with top-p 0.95.Source: Figure 25 · p. 34, F. Ablation on Temperature for… · p. 34

G. Diversity Score vs Search Improvement Plots for MBPP+ and HumanEval+

• The appendix plots measured diversity against relative improvement from pass@1 to pass@200 for MBPP+ and HumanEval+.The plots are described as relating higher diversity scores to search improvement.Source: G. Diversity Score vs Search… · p. 35, Figure 26 · p. 35, Figure 27 · p. 36

H. Ablations

• Increasing the maximum observation subset size to 3 causes only small, barely noticeable performance degradation; S = 2 is chosen to allow more completions.The authors report little overall difference across S values in Figure 28.Source: H. Ablations · p. 37, Figure 28 · p. 37
• The translation step adds minor pass@k gains; its ablations separate pseudocode generation, sketch fixing, and creating a solution sketch.The compared variants include omitting the sketch and pseudocode, omitting pseudocode alone, or omitting both the fix step and pseudocode.Source: H. Ablations · pp. 37–38, Figure 30 · p. 39
• Increasing the observation-tree depth raises pass@k above k=50; the authors choose L = 2 to balance gains against compute cost.The result is reported in Figure 29.Source: H. Ablations · p. 37, Figure 29 · p. 38

I. Base Models vs. Instruct Models for Large Samples

• At sufficiently high k, base models often match or exceed instruct models despite lower pass@1; this holds across models on HumanEval+ and MBPP+, but only for DeepSeek-Coder-V2 on LiveCodeBench.Figure 31 compares base and instruct models across the three datasets.Source: §I · p. 40, Figure 31 · p. 41

J. Base Models vs. Instruct Models with Public Test Filtering

• With public-test filtering, base models almost always exceed their instruct counterparts at pass@1.Figures 34–36 show the filtered comparisons.Source: J. Base Models vs. Instruct Models… · p. 43, Figure 34 · p. 43, Figure 35 · p. 44

K. OpenAI O1

• On LiveCodeBench, PLANSEARCH trails REPEATED SAMPLING at low k but competes with or slightly exceeds it at high k; o1-mini was evaluated only on this benchmark.Figure 37 plots results through k = 200; larger k was not run due to cost constraints.Source: K. OpenAI O1 · p. 45, Figure 37 · p. 45

L. Bar Charts

• Figures 38–39 compare pass@1 and pass@200 for REPEATED SAMPLING and PLANSEARCH on MBPP+ and HumanEval+.The bar-chart captions identify the methods and metrics shown.Source: Figure 38 · p. 46, L. Bar Charts · p. 46, Figure 39 · p. 47

M.1.1–M.2

• The backtranslation prompts first request a natural-language solution and then code matching that solution; repeated sampling instead prompts directly for code.These are the supplied prompts for the backtranslation and repeated-sampling baselines.Source: §M.1.1 · p. 48, §M.1.2 · p. 48, §M.2 · p. 48

M.3–M.4.3

• The idea prompts request creative natural-language ideas or observations, then combine observations into a solution by quoting relevant parts before each step.The observation-generation prompts ask for useful, correct observations and further observations derived from them.Source: §M.3 · p. 48, §M.4.1 · p. 48, §M.4.2 · p. 49

N. A Model of Repeated Sampling: Pass@k

• For datasets with multiple problems, overall pass@k averages per-problem solve curves, so models can separate at larger k despite different pass@1 values.The example has pass@1 values of 53% and 13%; Figure 41 shows the lower-pass@1 set surpassing the other around k = 20.Source: N. A Model of Repeated Sampling: Pass@k · pp. 49–50, Figure 41 · p. 51

O. Biased Estimator for Pass@K Due to Non-Independence of PLANSEARCH

• PLANSEARCH’s pass@k estimator can be slightly biased because it treats subsets of one run’s samples similarly to independent samples, though the authors do not consider this a large concern at k = 200.The subset interpretation is the probability that a size-k subset of generated samples contains a success.Source: O. Biased Estimator for Pass@K Due to… · p. 50

O.1 Measuring Diversity; Q. Mathematics and Examples of the Diversity Measure

• The diversity score considers the chance that two random outputs share an idea, distinguishing balanced from skewed idea frequencies unlike a simple count of unique ideas.The authors contrast an even split of outputs across two ideas with a highly uneven split.Source: Q. Mathematics and Examples of the… · p. 52

R. Additional Directions for Future Work

• Uniformly searching all leaf nodes makes going beyond a couple of tree levels quickly intractable; the experiments reach only two levels, while higher abstraction is proposed as a future direction.The authors suggest dynamic pruning and expansion as a possible improvement.Source: R. Additional Directions for Future Work · p. 52