# SPaR: Self-Play with Tree-Search Refinement to Improve Instruction-Following in Large Language Models

arXiv: https://arxiv.org/abs/2412.11605 · HTML: https://mlsanity.com/paper/2412.11605/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 44 of its 48 references that are in the map.
- First posted on arXiv 16 Dec 2024.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)
- Synthetic data and self-improvement for LLMs / [Code and instruction data synthesis](https://mlsanity.com/synth/code-and-instruction-data-synthesis/)

## Builds on (most cited first, 30 of 44)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension](https://mlsanity.com/paper/1705.03551/) (2017)
- [Self-Instruct: Aligning Language Models with Self-Generated Instructions](https://mlsanity.com/paper/2212.10560/) (2022)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [AgentBench: Evaluating LLMs as Agents](https://mlsanity.com/paper/2308.03688/) (2023)
- [Instruction-Following Evaluation for Large Language Models](https://mlsanity.com/paper/2311.07911/) (2023)
- [WizardLM: Empowering large pre-trained language models to follow complex instructions](https://mlsanity.com/paper/2304.12244/) (2023)
- [ChatGLM: A Family of Large Language Models from GLM-130B to GLM-4 All Tools](https://mlsanity.com/paper/2406.12793/) (2024)
- [GLM-130B: An Open Bilingual Pre-trained Model](https://mlsanity.com/paper/2210.02414/) (2022)
- [Instruction Tuning with GPT-4](https://mlsanity.com/paper/2304.03277/) (2023)
- [Self-Rewarding Language Models](https://mlsanity.com/paper/2401.10020/) (2024)
- [Identifying the Risks of LM Agents with an LM-Emulated Sandbox](https://mlsanity.com/paper/2309.15817/) (2023)
- [Reinforced Self-Training (ReST) for Language Modeling](https://mlsanity.com/paper/2308.08998/) (2023)
- [Scaling Relationship on Learning Mathematical Reasoning with Large Language Models](https://mlsanity.com/paper/2308.01825/) (2023)
- [ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Search](https://mlsanity.com/paper/2406.03816/) (2024)
- [Evaluating Large Language Models at Evaluating Instruction Following](https://mlsanity.com/paper/2310.07641/) (2023)
- [Meta-Rewarding Language Models: Self-Improving Alignment with LLM-as-a-Meta-Judge](https://mlsanity.com/paper/2407.19594/) (2024)
- [Benchmarking Complex Instruction-Following with Multiple Constraints Composition](https://mlsanity.com/paper/2407.03978/) (2024)
- [Self-Alignment with Instruction Backtranslation](https://mlsanity.com/paper/2308.06259/) (2023)

## Built on by (most cited first, 23 of 23)

- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [From System 1 to System 2: A Survey of Reasoning Large Language Models](https://mlsanity.com/paper/2502.17419/) (2025)
- [MCP Security Bench (MSB): Benchmarking Attacks Against Model Context Protocol in LLM Agents](https://mlsanity.com/paper/2510.15994/) (2025)
- [Incentivizing Reasoning for Advanced Instruction-Following of Large Language Models](https://mlsanity.com/paper/2506.01413/) (2025)
- [Generative AI Act II: Test Time Scaling Drives Cognition Engineering](https://mlsanity.com/paper/2504.13828/) (2025)
- [MetaScale: Test-Time Scaling with Evolving Meta-Thoughts](https://mlsanity.com/paper/2503.13447/) (2025)
- [From Drafts to Answers: Unlocking LLM Potential via Aggregation Fine-Tuning](https://mlsanity.com/paper/2501.11877/) (2025)
- [RECAST: Expanding the Boundaries of LLMs' Complex Instruction Following with Multi-Constraint Data](https://mlsanity.com/paper/2505.19030/) (2025)
- [Skill Self-Play: Pushing the Frontier of LLM Capability with Co-Evolving Skills](https://mlsanity.com/paper/2607.22529/) (2026)
- [TDRM: Smooth Reward Models with Temporal Difference for LLM RL and Inference](https://mlsanity.com/paper/2509.15110/) (2025)
- [Replay Failures as Successes: Sample-Efficient Reinforcement Learning for Instruction Following](https://mlsanity.com/paper/2512.23457/) (2025)
- [Improving Rationality in the Reasoning Process of Language Models through Self-playing Game](https://mlsanity.com/paper/2506.22920/) (2025)
- [Self-Improving Model Steering](https://mlsanity.com/paper/2507.08967/) (2025)
- [Beyond the Trade-off: Self-Supervised Reinforcement Learning for Reasoning Models' Instruction Following](https://mlsanity.com/paper/2508.02150/) (2025)
- [LLM-Driven Preference Data Synthesis for Proactive Prediction of the Next User Utterance in Human-Machine Dialogue](https://mlsanity.com/paper/2601.09713/) (2025)
- [Self-Evolving Deep Research via Joint Generation and Evaluation](https://mlsanity.com/paper/2606.04507/) (2026)
- [Evolutionary System 2 Reasoning: An Empirical Proof](https://mlsanity.com/paper/2512.05760/) (2025)
- [SEIF: Self-Evolving Reinforcement Learning for Instruction Following](https://mlsanity.com/paper/2605.07465/) (2026)
- [Anchored Self-Play for Code Repair](https://mlsanity.com/paper/2607.03523/) (2026)
- [Enhancing LLM Reasoning via Non-Human-Like Reasoning Path Preference Optimization](https://mlsanity.com/paper/2510.11104/) (2025)
- [Financial Instruction Following Evaluation (FIFE)](https://mlsanity.com/paper/2512.08965/) (2025)
- [Cross-Relational Preference Learning for Better LLM Instruction Following](https://mlsanity.com/paper/2608.29352/) (2026)
- [ScopeIF: Improving Scope-Aware Precise Instruction-Following in Large Language Models via Graded Reward Modeling](https://mlsanity.com/paper/2609.32189/) (2026)

## Abstract (arXiv)

Instruction-following is a fundamental capability of language models, requiring the model to recognize even the most subtle requirements in the instructions and accurately reflect them in its output. Such an ability is well-suited for and often optimized by preference learning. However, existing methods often directly sample multiple independent responses from the model when creating preference pairs. Such practice can introduce content variations irrelevant to whether the instruction is precisely followed (e.g., different expressions about the same semantic), interfering with the goal of teaching models to recognize the key differences that lead to improved instruction following. In light of this, we introduce SPaR, a self-play framework integrating tree-search self-refinement to yield valid and comparable preference pairs free from distractions. By playing against itself, an LLM employs a tree-search strategy to refine its previous responses with respect to the instruction while minimizing unnecessary variations. Our experiments show that a LLaMA3-8B model, trained over three iterations guided by SPaR, surpasses GPT-4-Turbo on the IFEval benchmark without losing general capabilities. Furthermore, SPaR demonstrates promising scalability, greatly enhancing models like GLM-4-9B and LLaMA3-70B. We also identify how inference scaling in tree search would impact model performance. Our code and data are publicly available at https://github.com/thu-coai/SPaR.