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

Chenglin Li, Qianglong Chen, Zhi Li, Feng Tao, Yicheng Li, Hao Chen, Fei Yu, Yin Zhang

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

Instruction tuning—the process of fine-tuning a model on pairs of instructions and responses—is the primary method for aligning Large Language Models (LLMs) with human intent. While effective, the scarcity of high-quality human-annotated data has led researchers to develop "self-evolution" methods like Evol-Instruct. These methods prompt an LLM to iteratively increase the complexity of existing instructions.

However, these prior approaches often rely on random sampling of evolution actions (e.g., "add constraints" or "deepen reasoning"). This lack of control frequently results in "perplexing" instructions—nonsensical or overly convoluted prompts that can actually degrade model performance. The core challenge lies in navigating the massive space of possible instruction variations to find those that truly enhance learning.

Comparison of random evolution vs. MCTS-guided evolution.

As illustrated in Figure 1, random sampling can lead to instructions that are logically impossible or irrelevant (scoring 0), whereas the guided search of IDEA-MCTS ensures that evolution leads to high-quality, meaningful tasks (scoring 3).

Methodology: IDEA-MCTS

The authors propose framing instruction synthesis as a state-space search problem. In this framework, each node represents a specific version of an instruction, and edges represent "evolution actions." IDEA-MCTS navigates this space using the standard Monte Carlo Tree Search cycle:

  1. Selection: High-value instruction nodes are selected using the Upper Confidence Bound (UCT) to balance exploration and exploitation.
  2. Expansion: The system applies evolution actions to generate new, more complex versions of the instruction.
  3. Evaluation: A specialized LLaMA-based scoring model calculates a reward based on three key metrics: Quality, Complexity, and Diversity.
  4. Simulation & Backpropagation: These rewards are propagated back up the tree to inform and optimize future searches.

To further refine the process, the researchers used "meta-prompts" to extract task-specific evolution actions from the data itself. This ensures that the evolution is relevant to the specific domain, such as requiring "Pythonic style" for coding tasks rather than applying generic complexity prompts.

Experimental Results

The framework was tested in a low-resource setting starting with only 1,000 seed instructions from the Alpaca and Dolly datasets. The results demonstrate that MCTS-guided evolution significantly outperforms random iterative methods across all evaluated dimensions.

Performance metrics comparing IDEA-MCTS against baseline methods.

As shown in Figure 5, IDEA-MCTS (MCTS+) raised the average evaluation scores of the synthetic data from 2.19 to 3.81. Notably, the complexity score saw a dramatic increase from 1.40 to 3.62, indicating that the search process effectively identifies challenging yet coherent instruction paths.

In open-domain benchmarks, models fine-tuned on MCTS-evolved data consistently outperformed those tuned on randomly evolved data. For instance, a Mistral-7B model achieved a 62.80% win rate on Alpaca-Eval, a 5.28% improvement over the standard Evol-Instruct method. On MT-Bench, which assesses multi-turn conversation, the MCTS+ method improved the average score from 5.90 to 6.94, demonstrating superior handling of complex dialogues.

Conclusion

IDEA-MCTS demonstrates that instruction evolution is a non-linear optimization problem that benefits significantly from systematic search. By treating instruction refinement as a search problem rather than a random process, the framework acts as a filter that prevents models from spiraling into gibberish. This approach provides a scalable and efficient way to generate high-quality synthetic data, resulting in a 5% average improvement in instruction-following benchmarks and enhanced general reasoning capabilities in low-resource settings.

Summary updated

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.
BibTeX
@inproceedings{li2024optimizing,
  author = {Chenglin Li and Qianglong Chen and Zhi Li and Feng Tao and Yicheng Li and Hao Chen and Fei Yu and Yin Zhang},
  title = {{Optimizing Instruction Synthesis: Effective Exploration of Evolutionary Space with Tree Search}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2024},
  url = {https://openreview.net/forum?id=jiLTIC6qvM},
}
Figure