Optimizing Instruction Synthesis: Effective Exploration of Evolutionary Space with Tree Search (2024)

Abstract: Instruction tuning is a crucial technique for aligning language models with humans’ actual goals in the real world. Extensive research has highlighted the quality of instruction data is essential for the success of this alignment. However, creating high-quality data manually is labor-intensive and time-consuming, which leads researchers to explore using LLMs to synthesize data. Recent studies have focused on using a stronger LLM to iteratively enhance existing instruction data, showing promising results. Nevertheless, previous work often lacks control over the evolution direction, resulting in high uncertainty in the data synthesis process and low-quality instructions. In this paper, we introduce a general and scalable framework, IDEA-MCTS (Instruction Data Enhancement using Monte Carlo Tree Search), a scalable framework for efficiently synthesizing instructions. With tree search and evaluation models, it can efficiently guide each instruction to evolve into a high-quality form, aiding in instruction fine-tuning. Experimental results show that IDEA-MCTS significantly enhances the seed instruction data, raising the average evaluation scores of quality, diversity, and complexity from 2.19 to 3.81. Furthermore, in open-domain benchmarks, experimental results show that IDEA-MCTS improves the accuracy of real-world instruction-following skills in LLMs by an average of 5% in low-resource settings.

## introduction large language models (llms) have exhibited remarkable capabilities across a wide range of tasks in the field of natural language processing (nlp) @xcite @xcite @xcite @xcite . notably, llms can be trained to enhance their figure 1 : iteratively enhance seed instructions using llms: the prior method's random sampling instruction evolution led to a perplexing instruction by selecting "add constraints" multiple times. our method uses mcts to find suitable prompts, resulting in high-value instructions that align the language model to effectively learn multiple skills. recent work explores synthesizing instruction data with llms by prompting them with example data or prompts and iteratively enhancing the instruction data, offering an efficient and costeffective alternative to human annotation @xcite @xcite . they introduced evolution prompts for llms, such as "add constraints", "increase reasoning" and "complete input.", enabling llms to iteratively improve seed instructions. however, the process suffers high uncertainty due to the limited evolution reward ..... 1) selection 2) expansion 3) evaluation 4) simulation 5) backpropagration 1+1=? 2+2=? 2+2*3=? provide the code to solve 2+2*3=? 1+1=? provide the code to solve 2+2*3=? provide the code to solve 2*4+2* 3=? provide the code to solve following question.john has 12 pencils, and he buys 7 more pencils. how many pencils does john have now? provide the code to solve following question.john has 12 pencils, and he buys 7 more pencils. how many pencils does john have now? please provide the python code to solve the following problem using a function. the function should take two arguments: the initial number of pencils and the number of pencils purchased. the function should return the total number of pencils john has now. john initially has 12 pencils and then purchases 7 additional pencils. use meaningful variable names and include comments explaining each step. reward ..... please provide the python code to solve the following problem using a function. the function should take two arguments: the initial number of pencils and the number of pencils purchased. the function should return the total number of pencils john has now. john initially has 12 pencils and then purchases 7 additional pencils. use meaningful variable names and include comments explaining each step. 1+1=? 1+1=? 2+2=? 2+2*3=? figure 2: framework of mcts for instruction synthesis: 1. selection: choose high-value leaf nodes. 2. expansion: evolve the selected leaf nodes to generate new nodes. 3. evaluation: assess the current node to determine a reward. 4. simulation: randomly evolve the current instruction to a terminal state. 5. backpropagation: propagate the terminal state's reward back through the path's nodes. intuitively, simple seed instructions can evolve into a wide variety of forms during the evolutionary process. to efficiently optimize and control this evolution, we introduce a novel framework, idea-mcts, which expands the evolution prompts as the action space and incorporates a tree search algorithm to iteratively enhance seed instruction data. in mcts, each seed instruction acts as the root node. high-value nodes are identified through selection and use evolution prompts for further expansion, followed by simulation and backtracking, to find an optimal evolution action space to enhance the instructions. in this process, we employ customizable evaluation models to assess the quality, diversity, and complexity of the nodes, effectively controlling the direction of instruction evolution. this framework enhances instruction data and provides a clearer understanding of the evolution process, as shown in the case analysis in appendix d. our experimental results show that idea-mcts significantly enhances the seed instruction data and models fine-tuned on this enhanced data exhibit substantial improvements compared to previous methods. we believe this work provides clear guidance for instruction synthesis, aiding models in achieving data-efficient alignment and enhancing overall performance. the contributions of our work are as follows: recent efforts have extended into open-domain it, characterized by a wide range of formats and task types, driven by crowdsourced human-generated instruction-response pairs @xcite @xcite @xcite . however, the high cost of human annotation poses significant challenges @xcite . one promising solution for this limitation is the synthesis of instruction data with the help of stronger llms @xcite @xcite . yet, using llm-generated data increases the risk of lowquality examples, highlighting the need for more focus on dataset refinement and enhancement. some works @xcite @xcite address this by prompting stronger llms to filter instruction data based on its quality, diversity, and complexity, serving as a form of refinement. however, this approach lacks the synthesis of new instruction, limiting the model's instructionfollowing capabilities, especially in low-resource scenarios where only a small amount of data is available. other works @xcite enhance existing seed instructions by using llms with carefully designed prompt templates. @xcite enhanced the original instructions using tree-structured prompts but focused only on the complexity and heavily relies on llms' intrinsic knowledge. additionally, some work @xcite @xcite design a series of evolution prompts to iteratively guide llms in enhancing the seed instructions. however, random selection during instruction evolution introduces high uncertainty and affects the quality of generated instructions. to effectively enhance the seed instruction data, we propose idea-mcts, which expands the evolu-tion action space, introduces evaluation models and iteratively improves instruction data with mcts. tree search for llm enhancement tree search methods such as bfs, a* search @xcite , and mcts @xcite @xcite , are widely used to find an optimal state in a tree structure. integrating tree-search methods with llms presents a novel approach to find an effective sequence of actions that leads to a favorable outcome. effective search strategy is crucial for reasoning and planning @xcite @xcite . depth/breadth-first search in @xcite , a* search in @xcite and mcts in @xcite @xcite @xcite . ## approach in this section, we introduce the novel framework idea-mcts, which enhances the quality, diversity, and complexity of seed instructions with a stronger llm, using mcts. we first define the problem, including the state, action space, and reward function. then, we discuss the expansion of evolution prompts from two key aspects and the use of mcts with llm to efficiently explore the action spaces. finally, we fine-tune models based on the instruction data generated by the llm, proving the effectiveness of the framework in low-resource settings. ## conclusion in this paper, we introduce a novel framework that leverages the power of mcts combined with heuristic evaluation to synthesis high-value instruction data. our statistical analysis validates the framework's effectiveness in synthesizing highvalue data. by fine-tuning open-source models with these evolved instructions, models achieve competitive competitive performance compared to previous methods.