Self-Play Search Distillation for Large Language Model Reasoning
Lorenzo Molfetta, Wai-Chung Kwan, Giacomo Frisoni, Luca Ragazzi, Gianluca Moro, Pavlos Vougiouklis, Jeff Z. Pan, Pasquale Minervini
cs.AI
2026-09-25
SPSD turns MuZero board self-play search into replay-checked CoT; OPSD on Qwen3-4B-Base lifts six-benchmark math mean 24.1→36.6 and held-out win rate 15%→45%.
High-quality process labels are scarce. A final answer says whether a solution worked. It does not show how a solver kept state, dropped a plausible fork, or planned through a later penalty. Human process annotation is expensive, hard to verify, and capped by the annotator. If the student writes its own traces, the data inherit its current mistakes.
Executable board games compress that gap. Rules define legal actions and deterministic transitions. Terminal outcomes expose delayed returns. Local rule edits change the reasoning task without changing the eval interface. MuZero-style self-play already stores more than the chosen move: alternatives, opponent replies, branch values, and replayable continuations. The search expert is a player with an engine sitting beside the board. SPSD puts those external experts in the data loop and keeps the LLM out of expert self-play, so supervision quality is no longer tied to the student's policy.
Three offline stages. The student never joins expert self-play, and search values stay hidden at inference. The post-training corpus is board records only. There are no math problems in the training mix.
An EfficientZero expert (Expert Iteration family, via LightZero) is trained on each of Connect4, Domineering, Simplified Othello, and Tic-Tac-Chess, with 50 MCTS simulations per decision. MCTS is Monte Carlo tree search: simulated rollouts compare legal moves on a tree. Each trajectory starts with a uniform random legal prefix so a deterministic expert does not collapse onto one line; the expert then plays both seats. At each kept state the export is a selected root action (the move at the search tree's current root), a visit-count policy, a root value, and branch evidence with replayable prefixes. Every branch is replayed in the environment. Records that fail replay are dropped.
Surviving records become two language tasks. Move-choice traces rank legal root actions by visits, replay the expert move, at most one alternative, and one opponent reply, narrate only board effects and terminals, and box the expert's legal handle. Six state questions cover occupancy, legality, threat count, legal-action count and enumeration, and successor state, so a model cannot score a good move while misreading the board. Each game contributes 5,000 examples except Tic-Tac-Chess (600 verified states); 80% move-choice, 20% state questions.
Three post-training paths share the student-facing prompt and the boxed legal action. SFT fits the linearized traces. OPSD (on-policy self-distillation) lets the student sample its own completion while a frozen teacher, conditioned on the expert trace, applies a forward KL on the student's prefixes, so privileged evidence follows the student's state distribution. RuleBot-Distill keeps the OPSD recipe and swaps the search corpus for heuristic rule-bot completions. That split tests search structure against a verified good action. SFT fits states the expert visited. A weaker student does not reach those boards, which is why the teacher is conditioned on the student's own prefixes.
Training runs for 1,000 steps on one H200 (141 GB) for Qwen3-4B-Base, Qwen3-8B with thinking off or on, and Llama-3.1-8B. Games are 15 held-out Ludii titles. Math is the mean of MATH500, AIME24, AIME25, AMC23, Olympiad Bench, and Minerva Math.
On Qwen3-4B-Base:
| method | math mean | held-out win | FIDE | legality |
| Base | 24.1 | 15% | 15.0% | 65.0% |
| SFT | 30.3 | 20% | 19.9% | 34.9% |
| RuleBot-Distill | 33.9 | 35% | 35.1% | 70.1% |
| OPSD | 36.6 | 45% | 39.9% | 75.1% |
OPSD leads all four. MATH500 moves from 56.4 to 74.0, AIME24 from 6.2 to 12.7, AIME25 from 5.9 to 12.4, AMC23 from 29.7 to 47.0, and Minerva Math from 20.2 to 38.6. On Olympiad Bench, RuleBot scores 35.7 against OPSD's 35.1. SFT legality falls to 34.9%: memorizing traces washes out legal actions.
Other backbones tell a narrower story. With thinking off, Qwen3-8B OPSD lifts the math mean from 48.3 to 51.4 and win rate from 45% to 55%, while legality drops from 95% to 85%. With thinking on, math is already near 74.9 and OPSD only reaches 75.0; games still move, FIDE 51.0 to 59.5 and win rate 53.7% to 62.7%, with legality staying at 100%. SFT in that thinking-on setting collapses legality to 30.6% and win rate to 16.4%. Llama-3.1-8B math barely moves (19.5 base, 19.2 OPSD), and RuleBot and OPSD produce identical game scores: FIDE 47.5, win rate 50%.
SFT peaks early then falls. OPSD keeps rising in the second half of training. Enriching five base games with nine local rule variants each (50 environments) under the same 1,000-step budget yields FIDE 42.4%, legality 77.3%, and math mean 39.2, against 39.9%, 75.1%, and 36.6 for the base curriculum. The variant mix leads on all three metrics at every logged step.
Figure 4 scores the model's committed moves with a fresh 50-simulation MuZero search. Wins pile up where Q50 and oracle agreement are both high. SPSD-Qwen3-4B couples winning more tightly to matching MCTS than Gemini 3.1 Pro does. Search is hidden at inference, so that agreement is a behavioral signature: rank actions by downstream consequences.
This is a synthetic-data path that needs neither human process labels nor a student teaching itself. Executable rules let every narrated transition be replay-checked. Search experts can, in principle, exceed human play. For teams already doing verifiable RL, it adds a different process signal: compare alternatives, anticipate replies, read delayed value.
It is not a substitute for math RL. The large lift is on a 4B base. Qwen3-8B with thinking and Llama-3.1-8B show weak or null math transfer. RuleBot already takes 4B win rate from 15% to 35% and math mean from 24.1 to 33.9; search structure adds 10 win points and 2.7 math points on top. The practical recipe is narrower: if you have executable rules and a search expert, write comparisons and consequences into an offline corpus and attach them with OPSD to the student's own prefixes. Varying the rules beats stacking homogeneous games.
There is no standalone Limitations section. The conclusion only flags expanding the executable curriculum. The tables already draw harder edges.
Transfer is backbone-bound. Llama-3.1-8B math goes from 19.5 to 19.2, and both expert sources produce the same game numbers, so search distillation adds almost nothing on that instruction model. Qwen3-8B with thinking already saturates the six math benchmarks. SPSD's main stage is a weak base.
The control set is incomplete. There is no same-budget comparison with math-domain GRPO, process-reward models, human process labels, or natural-language MCTS traces such as ASTRO. RuleBot is already strong, so verified good actions plus OPSD carry a lot of the gain; the extra credit assigned to search structure is a 2.7-point math mean and 10 win points on 4B.
The training games are Connect4-scale, not Go. Superhuman here means EfficientZero versus people on these small games, not AlphaZero-level play poured into an LLM. On 15 held-out Ludii games, 4B OPSD still has only 75.1% legality, so about one turn in four dies on format or illegal moves. All runs are 1,000 steps on one H200; longer training and larger experts are untested. Figure 1 shows frontier models still far from saturating board play, and SPSD was not applied to them.