TL;DR
This paper introduces SRA-MCTS, a novel method that uses Monte Carlo Tree Search (MCTS) to generate high-quality "thinking" (intermediate reasoning steps) for complex code generation tasks. By enabling LLMs to self-generate and self-evaluate these reasoning steps, SRA-MCTS significantly improves code generation performance, especially on challenging problems, without requiring external supervision.
What Problem Does This Paper Address?
Large language models (LLMs) have shown impressive capabilities in generating code for simple programming tasks. However, they struggle with more complex problems that require intricate reasoning and decomposition. Existing approaches often focus on improving the quality of training data by enhancing questions or answers. While some methods like BRAINSTORM and DolphCoder attempt to generate diverse ideas or use multiple prompts, they still rely on external guidance. This paper addresses the gap in LLMs' ability to autonomously generate and refine their own reasoning processes for complex code generation, aiming to create a self-improving system.
Methods
The core of the proposed method is SRA-MCTS (Self-driven Reasoning Augmentation with Monte Carlo Tree Search). This approach augments the LLM's reasoning capabilities by generating intermediate natural language "thinking" steps. Here's how it works:
- SRA-MCTS for Thinking Generation:
- Selection: An MCTS algorithm is employed to navigate a search tree of possible reasoning steps. It uses the Upper Confidence Bound for Trees (UCT) formula to balance exploring new reasoning paths (exploration) and exploiting promising ones (exploitation).
- Expansion: For a selected node (representing a partial reasoning path), the LLM generates multiple potential next reasoning steps. These steps are added as new child nodes.
- Evaluation & Reflection: The LLM itself acts as an evaluator, scoring each generated step based on correctness, coherence, and completeness. It also generates a "reflection" – a brief thought that guides future reasoning. If the question is deemed solved, an
<end>tag is produced. - Backpropagation: The scores (rewards) from the evaluated steps are propagated back up the tree to update the reward values of parent nodes. This dynamic reward adjustment helps refine the search strategy over iterations.
- Thinking to Code: Once SRA-MCTS generates a complete "thinking" sequence for a question, this thinking is concatenated with the original question. This combined input is then fed to the LLM to generate the final code.
- Training: The generated (question, thinking, code) triples form a new dataset used for supervised fine-tuning of the LLM, thereby improving its code generation capabilities.
Datasets
- Training Data: The paper uses medium and hard-level questions from the LeetCode dataset, excluding easy ones. They perform decontamination to avoid overlap with test sets. This results in a training set of 1,819 unique questions.
- Evaluation Datasets: Standard benchmarks like Human-Eval and MBPP are used, along with their extended versions, Human-Eval+ and MBPP+. The test sets are further categorized into "Full" (all difficulties) and "Complex" (medium and hard only) splits, with GPT-4o used for classification.
Key Insights and Ideas
- LLMs can self-improve reasoning: The most significant insight is that LLMs can be guided to generate and evaluate their own reasoning steps, leading to substantial performance gains without external human supervision.
- MCTS is effective for reasoning exploration: Applying MCTS to the "thinking" generation process, rather than directly to code generation, allows for a more focused and effective exploration of diverse reasoning paths.
- "Thinking" is crucial for complex tasks: The paper strongly demonstrates that including intermediate reasoning steps ("thinking") in the training data significantly boosts performance, especially on more complex problems where simple code-only training is insufficient.
- Model size matters: The benefits of SRA-MCTS are more pronounced for larger models, suggesting that their enhanced generation and evaluation capabilities can better leverage the self-driven augmentation process.
- Self-generated data can be competitive: The study shows that data generated by smaller models using SRA-MCTS can outperform data distilled from much larger models, highlighting the efficiency and effectiveness of their self-generation approach.
Key Results
- SRA-MCTS consistently improves performance across three model scales (gemma-2-2b, Meta-Llama-3.1-8B, Qwen2.5-14B).
- The method achieves an 11-point improvement on the MBPP Complex split when applied to the Meta-Llama-3.1-8B-Instruct model.
- On average, SRA-MCTS shows a significant performance increase, particularly on the "Complex" splits of benchmarks, indicating its strength in handling harder problems.
- Ablation studies show that training data with thinking significantly outperforms data without thinking, especially for complex tasks.
- SRA-MCTS demonstrates more stable performance compared to CoT and ToT when the thinking content is varied, suggesting its generated thinking is more robust.
Limitations and Future Work
- Evaluation subjectivity: The paper notes that the LLM evaluator might sometimes overemphasize unnecessary overthinking steps, leading to unexpected results in certain cases. This suggests that the reliability of LLM-based evaluation might vary, especially for complex reasoning.
- Dataset size: While SRA-MCTS is efficient, the paper acknowledges that a larger, more diverse fine-tuning dataset (like Magicoder's) could potentially lead to even better results.
- Future work: The authors suggest exploring more sophisticated LLM-based evaluators and expanding the dataset size and diversity to further enhance performance. The potential for end-to-end self-improvement through this pipeline is a key takeaway for future research.
Summary updated