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

1 INTRODUCTION

• Multiple-constraint instruction following matters because failures can raise safety issues, while independent-response preference pairs add content variation that obscures decisive requirements.The paper illustrates how different story content can distract from whether the required ending sentence was followed.Source: §1 · p. 2
• SPaR uses an actor and refiner initialized from the same model; tree search refines failed responses into comparable preference pairs for training.The refiner judges the actor’s responses, and refinement starts from those judged to have failed to follow instructions accurately.Source: §1 · p. 2
• After three iterations, LLaMA3-8B-Instruct surpasses GPT-4-Turbo on IFEval; SPaR also scales across models without degrading general benchmarks.The paper reports effective scaling to LLaMA3-70B-Instruct and maintained or improved performance on general benchmarks.Source: §1 · p. 2
• The paper reports a 43K-prompt complex instruction-following dataset and an SFT dataset intended to improve instruction-following capabilities.It also reports improvements to LLaMA3-70B-Instruct through SPaR.Source: §1 · p. 2

2.1 OVERALL FRAMEWORK

• The actor generates responses, the refiner identifies inaccurate ones, and tree search refines them into pairs used to train the actor while RFT improves the refiner.Both models are prepared for the next self-improvement iteration.Source: §2.1 · p. 3, §2.3 · p. 4

2.2.1 PROMPT CREATION

• A taxonomy-based process adds balanced combinations of constraints to seed prompts and checks generated prompts for validity and conflicting requirements.The prompt set is designed to address the scarcity of high-quality, multi-constraint instruction-following data.Source: §2.2.1 · pp. 3–4

2.2.2 ACTOR AND REFINER INITIALIZATION

• About 43K prompts are constructed; 8K initialize the actor, 5K the refiner, and 30K are reserved for self-play training.The actor is bootstrapped with strong-LLM responses, while the refiner receives judgment examples and minimally revised corrections.Source: §2.2.2 · p. 4

2.3 TREE-SEARCH INTEGRATED SELF-PLAY TRAINING

• Each iteration collects negative data, refines it through tree search, and uses the resulting data to train the actor and refiner for the next round.This pipeline is intended to continuously improve both models.Source: §2.3 · p. 4

2.3.1 NEGATIVE DATA COLLECTION

• For each prompt, the actor samples K responses; the refiner judges them, and majority voting selects the final label and a matching judgment.Incorrect responses and their corresponding judgments become negative instances for subsequent refinement.Source: §2.3.1 · p. 4

2.3.2 TREE-SEARCH REFINEMENT

• Breadth-first search expands refinements level by level, evaluates each with the refiner, and continues until it finds a correct response.SPaR also implements depth-first search; the search explores multiple paths while minimizing irrelevant variation.Source: §2.3.2 · p. 5

2.3.3 ACTOR TRAINING

• The actor is trained with DPO on refinement pairs, treating the negative response as rejected and the refined response as chosen.The reference model is initialized from the current actor and remains fixed during training.Source: §2.3.3 · p. 5

2.3.4 REFINER TRAINING

• Refiner RFT uses refinement tuples linking a tree parent and its judgment to a correct response, alongside judgment tuples based on majority voting.The two data types train the refiner’s refinement and judgment capabilities, respectively.Source: §2.3.4 · p. 5

3.1 EXPERIMENT SETUP

• Experiments use three self-play iterations with 10k prompts per iteration; actor updates use DPO and refiner updates use RFT.Models under 10B parameters are bootstrapped as actor and refiner, while LLaMA3-70B-Instruct is used directly in both roles.Source: §3.1 · p. 6

3.3 ACTOR EVALUATION RESULTS

• After three iterations, SPAR-8B-DPO-iter3 surpasses GPT-4-Turbo (81.3% average accuracy) on IFEval.SPAR also outperforms other methods in every training iteration.Source: §3.3 · p. 6, Table 1 · p. 7
• SPAR maintains or improves general-benchmark performance, particularly on GSM8k and HumanEval.The reported benchmarks also include TriviaQA and MMLU.Source: §3.3 · p. 6

3.4 REFINER EVALUATION RESULTS

• By iteration three, SPAR-8B-RFT-iter3 surpasses GPT-4o-Mini on judgment, including on adversarial test sets.The authors suggest similar positive and negative tree-search examples may improve robustness to adversarial samples.Source: §3.4 · p. 7, Table 2 · p. 8
• SPAR progressively improves LLaMA3-8B-Instruct refinement accuracy (success rate) with each training iteration, eventually matching GPT-4o-Mini; self-evaluation yields significantly higher accuracy than evaluation by GPT-4o.Source: §3.4 · p. 8

3.5 ABLATIONS AND ANALYSIS

• Across character-sequence and start/end story tasks, refinement pairs outperform interfering pairs.The uppercase-ratio distractor is learned rapidly, while story-generation interference can perform worse than the original model at step 0.Source: §3.5 · p. 8, Figure 4 · p. 9
• Removing refinement data or tree search reduces actor performance; the authors also report tree search improves refinement and refiner judgment, especially on adversarial inputs.They attribute tree-search benefits in part to difficult samples and more preference pairs, and identify iterative training as important for mutual actor-refiner improvement.Source: §3.5 · p. 9, Table 4 · p. 9, Table 5 · p. 9
• Increasing inference-time sampling improves performance over greedy decoding, and tree-search refinement ultimately outperforms best-of-N generation.The reported growth for tree-search refinement is slower; the authors conclude refinement may be better suited than generation for scaling test-time compute.Source: §3.5 · pp. 9–10, Figure 5 · p. 9

4.1 INSTRUCTION FOLLOWING

• Complex instructions increasingly involve numerous constraints, and subtle response differences can determine whether they are correct.The section situates instruction-following benchmarks and enhancement methods in this setting.Source: §4.1 · p. 10

4.2 AUTONOMOUS LLM ALIGNMENT

• Autonomous alignment methods use strategies including self-training, feedback, and self-judgment, but independent response sampling can introduce interfering factors.SPAR instead constructs preference pairs by self-refining responses to minimize extraneous elements and highlight key differences.Source: §4.2 · p. 10

5 CONCLUSION

• SPAR trains LLMs on refinement pairs to improve instruction-following capabilities through self-play.The conclusion contrasts refinement pairs with independently sampled responses, which can contain extraneous factors.Source: §5 · p. 10
• LLaMA3-8B-Instruct trained with SPAR outperforms GPT-4-Turbo on IFEval.The conclusion also reports that inference-time compute scaling can further improve its performance.Source: §5 · p. 10
• SPAR’s iterative enhancement of instruction-following, judgment, and refinement abilities is presented as a promising path to continuous self-improvement.Source: §5 · p. 10

A DATASET INFORMATION

• The prompt-constraint taxonomy refines Cheng et al. (2024) to make it more comprehensive and support prompt diversity.Figure 6 presents the refined taxonomy.Source: A DATASET INFORMATION · p. 14, Figure 6 · p. 14
• Prompt evolution uses a dedicated template, while the refiner has a judgment template and a multi-turn refinement template.Figures 7 and 8 show the templates; the judgment and refinement templates are both identified as Figure 8.Source: A DATASET INFORMATION · p. 14

B TREE-SEARCH ALGORITHM

• The appendix provides separate algorithms for breadth-first and depth-first refinement.The detailed processes are identified as Algorithm 1 and Algorithm 2, respectively.Source: B TREE-SEARCH ALGORITHM · p. 14

C IMPLEMENTATION DETAILS

• Actor SFT uses 8k examples; refiner datasets include approximately 9k judgment and 3k refinement examples, constructed with GPT-4o-Mini.The data-construction search budget is 15, with about 3.7 expanded nodes on average.Source: C IMPLEMENTATION DETAILS · pp. 14, 16
• The detailed refinement procedures use breadth-first and depth-first tree search, with DFS recursing when the judgment falls below threshold vth.Source: C IMPLEMENTATION DETAILS · p. 16

D BASELINES

• The baseline set includes methods using code feedback, language feedback, self-judgment, meta-judgment, and web-resource-based data generation.Baseline comparisons use nearly identical training-sample counts for fairness.Source: D BASELINES · p. 16, C IMPLEMENTATION DETAILS · p. 16

E.1 INSTRUCTION-FOLLOWING EVALUATION RESULTS.

• SPAR outperforms all baselines on instruction-following benchmarks, with substantial improvements in each iteration.The results are reported in Table 6 and Figure 9.Source: §E.1 · p. 16

• SPAR training does not harm general performance and can bring enhancements.Source: §E.2 · p. 17

• Judgment capability improves in each iteration, and accuracy outperforms all baselines.Source: §E.3 · p. 17

• Majority voting@5 is selected to balance performance and computation time when improving judgment capability across iterations.The reported sampling-times and performance results for SPAR-8B-SFT are on LLMBar.Source: §E.4 · p. 17

E.5 ABLATION STUDY ON REFINEMENT CAPABILITY.

• Tree-search decoding strategies largely outperform other refinement strategies; methods other than greedy decoding use the same inference budget.Table 10 reports Acc-GPT and Acc-SPAR, judged by GPT-4o and SPAR-8B-RFT-iter3, respectively.Source: §E.5 · p. 17, Table 10 · p. 20

E.6 INFERENCE-TIME SCALING COMPARISON

• With added inference compute, SPAR outperforms self-rewarding on LLaMA3-8B-Instruct and Mistral-7B-Instruct.Figure 10 compares performance as inference response generations increase.Source: §E.6 · p. 17, Figure 10 · p. 18
• SPAR-7B consistently surpasses all baseline methods across iterations.Source: Figure 9 · p. 17