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:
- 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").
- Combinatorial Expansion: These observations are grouped into subsets to inspire "second-order" observations, creating a tree of ideas.
- 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.
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.
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.
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