EliteReplay: Preserving Diverse Solutions in RL Post-Training via Quality-Diversity Search

What it claims

Adding a small, fixed replay loss on a pre-built archive of diverse verified solutions to GRPO keeps much of the base model's range of correct strategies without giving up accuracy. The authors also argue that pass@k is a poor proxy for diversity, because a model can reach high pass@k with a single strategy per question. They introduce U@k (expected number of distinct correct strategies among k samples) and a strategy-retention metric to measure this. On BIRD, EliteReplay matches the best baseline's pass@128 while producing about 47% more distinct correct strategies. It also retains at least 23 points more of the base model's strategies than any baseline.

How it works

Offline: build the archive with MAP-Elites, using the frozen base model as the generator.

1. Sample verified seed solutions from the base model.
2. A separate labeler LLM reads the seeds and proposes a vocabulary of approaches, including ones the seeds never used.
3. Each solution's cell is defined by two things combined: the labeler's approach label and deterministic structural features, such as joins or subqueries in SQL.
4. The search loop then runs: - Pick a target approach, preferring ones not yet in the archive. - Pick a parent elite, preferably one using a different approach. - Prompt the base model to rewrite the parent toward the target approach. - Verify the result. - File it under the approach it actually used. It fills an empty cell or replaces the current elite only if it is shorter.

This search more than doubles the cells occupied by seed sampling alone.

flowchart LR
  A[Select target approach + parent elite] --> B[Base model rewrites toward target]
  B --> C{Verified correct?}
  C -- no --> A
  C -- yes --> D{Cell empty or candidate shorter?}
  D -- yes --> E[Insert as elite]
  D -- no --> A
  E --> A

Online: train with GRPO plus elite replay.

• Each step samples archive entries, balanced across questions and occupied cells.
• The replay loss is the negative log-likelihood of those entries, normalized by length.
• The total loss is (1−μ)·GRPO + μ·replay, with μ = 0.05, adapted from CHORD.
• The archive is never updated during training.
• Inference is plain sampling, with no archive lookup.

Diversity is evaluated with a separate AST-derived notion of "strategy", not the search descriptor.

Evidence

Setup

• Base model: Qwen3.5-4B-Base.
• RL training: 5,000 BIRD questions. The archive is built on a 1,000-question subset that stays in the RL pool.
• All methods run for 100 steps.
• Correctness is execution accuracy, with n = 128 samples per question.
• Baselines: GRPO, MaxRL, DPH-F (forward-KL), SetPO (diversity bonus).

Results

• BIRD pass@1: every post-trained method rises from 25.3% (base) to 52–56%. EliteReplay's own pass@1 is not broken out.
• BIRD pass@128:
• EliteReplay: 74.8%
• MaxRL: 73.7%
• Base model: 73.6%
• GRPO, SetPO and DPH-F: 68–69%, which is below the base model.
• BIRD U@128: EliteReplay 9.1 vs MaxRL 6.2.
• Spider (out-of-distribution): pass@128 of 93.2%, 6.3 points above the strongest baseline, with up to 77% more distinct correct strategies.
• Effective diversity (probability that two samples are both correct and structurally different):

On Spider, GRPO halves the base model's effective diversity.

• Strategy retention: 62% on BIRD and 60% on Spider, at least 23 points above any baseline. This is measured over questions where the base model has two or more correct strategies.
• AmbiQT: covers both interpretations on 27.0% of questions vs 14.2% for the strongest baseline.
• MATH-500: the BIRD-trained EliteReplay model improves pass@k "substantially" over the base model, while baselines barely move or degrade. The text gives this only as a plot, with no numbers.

How to use it

Artifacts are at https://github.com/skai-research/EliteReplay.

To reproduce the method you need:

• an automatic verifier for your task;
• a labeler LLM;
• domain structural features to define cells (the paper suggests loops and recursion for code);
• a search budget spent before training.

The replay loss itself is a one-line addition to a GRPO loop. The labeler model, search budget and compute are in appendices not included in the fetched text.

Limits

• Tested only on text-to-SQL with one 4B base model and 100 training steps. Math appears only as transfer evaluation.
• The method depends on a verifier and on a hand-chosen structural feature set for each domain.
• The archive is static, so it can only preserve strategies the base model can already produce, not discover new ones.
• The fetched text cuts off partway through the results. Ablations (μ, archive vs direct sampling), compute cost and any authors' limitations section were not visible.