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

1 Introduction

• Pass@k can be high even when correct samples repeat a single strategy, so the paper evaluates diversity at the level of distinct correct solution strategies.It measures U@k and effective diversity alongside accuracy.Source: §1 · pp. 1–2
• The paper motivates strategy diversity because correct solutions can differ in reasoning path, computational efficiency, or interpretation of an ambiguous request.Meaningful variety also benefits systems that rely on repeated sampling and selection (Li et al., 2022; Pourreza et al., 2025).Source: §1 · pp. 1–2
• ELITEREPLAY builds a quality-diversity archive of verified solutions spanning distinct approaches, then combines GRPO with replay loss on that archive.The archive is constructed before training using the frozen base model.Source: §1 · p. 2
• On Spider, ELITEREPLAY reaches 93.2% pass@128, outperforming the strongest baseline by 6.3 percentage points while producing up to 77% more distinct correct strategies.It retains 62% of the base model’s correct strategies on BIRD and 60% on Spider, at least 23 percentage points more than any baseline; on AmbiQT it covers both interpretations on 27.0% of questions versus 14.2% for the strongest baseline.Source: Figure 1 · p. 1, §1 · p. 2

2 ELITEREPLAY

• The method first builds a fixed archive of verified solutions spanning distinct approaches, then trains with GRPO plus replay loss on that archive.The archive is built with the frozen base model before training.Source: §2 · p. 2, Figure 2 · p. 3

2.1 Constructing the elite archive

• The behavior descriptor combines a labeler-assigned approach with deterministic structural features, and each archive cell stores at most one verified solution.The descriptor guides archive search; the paper evaluates diversity using a separate deterministic strategy measure.Source: §2.1 · p. 3
• Search more than doubles the cells occupied by seed sampling and yields more distinct elites than direct sampling.Selection prioritizes applicable approaches not yet represented, while verified candidates fill empty cells or replace an existing elite if shorter.Source: §2.1 · p. 3

2.2 Training with elite replay

• Replay samples verified archive solutions across questions and occupied cells, using length-normalized negative log-likelihood to avoid giving longer solutions more weight.The replay loss is combined with the on-policy GRPO objective using a fixed mixing weight; the archive remains fixed during training.Source: §2.2 · p. 4

• The evaluation uses three complementary metrics to capture distinct correct strategies, structural diversity among correct samples, and retention of base-model strategies.Source: §3 · p. 4
• Each SQL solution’s strategy is derived deterministically from its AST, distinguishing structural approaches such as joins from nested-subquery filtering.Source: §3 · p. 4
• U@k measures the expected number of distinct strategies among correct samples in a random k-sample subset, unlike pass@k, which counts whether any sample is correct.Source: §3 · p. 4
• Effective diversity measures expected structural dissimilarity between random samples while counting only pairs in which both are correct.Source: §3 · p. 4
• Strategy retention measures the fraction of base-model strategies still accessible after post-training, among questions where the base model produces at least two distinct correct strategies.Source: §3 · p. 4

• The study uses Qwen3.5-4B-Base, trains on 5,000 BIRD questions, and builds its archive from 1,000 questions that remain in the RL training pool.Source: §4 · pp. 4–5
• On BIRD and Spider, Figure 3 tracks pass@k and U@k as sampling budget grows; EliteReplay improves accuracy over the base model and produces more distinct correct strategies than any baseline.Source: Figure 3 · p. 5
• Evaluation uses BIRD dev for in-distribution performance and Spider 1.0 dev for out-of-distribution generalization on databases disjoint from training; SQL correctness is execution accuracy.Source: §4 · p. 5
• Additional evaluations use MATH-500 for an unrelated domain and AmbiQT for questions with two valid interpretations, drawing 128 samples per question.Source: §4 · p. 5
• Baselines are GRPO, MaxRL, DPH-F, and SetPO; all methods train on the same data for 100 steps, with EliteReplay replay weight µ = 0.05.Source: §4 · p. 5
• On MATH-500, Figure 4 compares pass@k for BIRD-trained models; baselines barely improve or degrade against the base model, while EliteReplay substantially improves it despite no math training.Source: Figure 4 · p. 5
• Figure 5 reports effective diversity—the probability that two samples are both correct and structurally different—and EliteReplay scores highest on both benchmarks.Source: Figure 5 · p. 5

5.2 Preserving base-model strategies

• ELITEREPLAY retains 62% of the base model’s correct strategies on BIRD and 60% on Spider, versus baseline ranges of 34–39% and 30–37%.Figure 6 measures retention over questions where the base model uses at least two strategies.Source: Figure 6 · p. 6, §5.2 · p. 6

5.1 Accuracy and strategy diversity

• On BIRD, ELITEREPLAY reaches 74.8% pass@128 versus MaxRL’s 73.7%, and on Spider it leads post-trained methods at 93.2%.On Spider, ELITEREPLAY’s 93.2% pass@128 exceeds the baselines’ maximum of 86.9%.Source: §5.1 · p. 6
• ELITEREPLAY’s U@128 is 9.1 versus MaxRL’s 6.2 on BIRD and 9.4 versus the strongest baseline’s 5.3 on Spider; effective diversity is also highest on both benchmarks.Effective diversity is 25.9% on BIRD versus 23.4% for the strongest baseline; on Spider, ELITEREPLAY reaches 31.4% versus the base model’s 27.9%.Source: §5.1 · p. 6

5.2 Preserving base-model strategies

• Across common base strategies, ELITEREPLAY’s coverage reductions never exceed 9 percentage points, while baselines lose up to 28 points on BIRD; Spider shows the same pattern.In three representative BIRD questions, baselines often concentrate correct samples on one strategy, while ELITEREPLAY maintains multiple approaches closer to the base model’s distribution.Source: §5.2 · p. 6, Figure 7 · p. 7

5.3 Diversity under ambiguity

• At k=128, Both@k reaches 27.0% for ELITEREPLAY versus 14.2% for the strongest diversity-preserving baseline, closing over half the gap to the base model’s 37.0%.Both@k is the share of questions with correct queries for both valid readings.Source: §5.3 · p. 7, Table 1 · p. 7

5.4 Ablating archive construction and replay

• Elite-archive SFT reaches 74.6% pass@128 on BIRD and 92.8% on Spider, 8–9 points above IID SFT, but tops out at 37% BIRD pass@1 versus ELITEREPLAY’s 52.5%.Figure 8 shows that elite-archive SFT beats IID archive SFT at large sampling budgets, but neither matches ELITEREPLAY’s pass@1.Source: Figure 8 · p. 7, §5.4 · p. 7
• Elite SFT→GRPO without replay falls to 68.5% pass@128 and U@128 of 3.0, comparable to GRPO’s 67.9% and 3.0; ELITEREPLAY continues replay during RL.The comparison indicates that an SFT warm-up alone does not preserve the archive’s coverage and diversity through RL.Source: §5.4 · pp. 7–8
• At U@128, ELITEREPLAY produces 9.1 distinct correct strategies versus 7.4 with IID replay, despite comparable pass@k; the archive’s composition matters.The authors attribute IID replay’s lower diversity to overrepresentation of the base model’s frequent approaches.Source: Table 2 · p. 8, §5.4 · p. 8

Diversity in RL post-training

• Prior RL post-training work reports reduced output diversity, policy entropy, and large-budget coverage (Kirk et al., 2024; Cui et al., 2025; Zhao et al., 2025; Oh et al., 2026).Mitigations include pass@k objectives, novelty rewards, base-model regularization, and entropy or temperature controls.Source: §6 · p. 8
• Unlike methods that use pass@k as a diversity proxy, ELITEREPLAY replays an archive built for coverage and measures diversity at the level of solution strategies.The related work describes prior approaches based on pass@k (Yu, 2025).Source: §6 · p. 8

Mixing demonstrations and replay into RL

• Prior LLM methods replay demonstrations, verified trajectories, or base-model samples for learning or reference-model alignment; ELITEREPLAY uses quality-diversity search to retain distinct correct solutions throughout RL.In evolutionary RL, archives typically come from a separate search process; ELITEREPLAY builds its archive once from the base model’s own solutions.Source: §6 · p. 8

7 Conclusion

• ELITEREPLAY raises accuracy in- and out-of-distribution while retaining most base-model correct strategies, and strategy-level evaluation reveals differences pass@k conceals.The authors conclude that post-training need not trade diversity for reliability.Source: §7 · p. 8

Limitations

• Experiments use Qwen3.5-4B-Base; evaluation on larger models and other model families remains future work.The authors selected this moderate-size model to fit multiple training runs within their compute budget.Source: Limitations · p. 9
• Evaluation is limited to text-to-SQL; distinguishing strategies in domains without clear structural representations, such as many math tasks, may be challenging.The authors identify program optimization and algorithmic coding as possible future domains with verifiable solutions and meaningful behavioral distinctions.Source: Limitations · p. 9

A.1 Algorithm

• EliteReplay first constructs an archive with the frozen base model, then uses archived solutions to guide GRPO post-training.The algorithm has two stages: archive construction and training with replay.Source: §A.1 · p. 13

A.2 Behavior space

• The archive descriptor combines a labeler-assigned approach with deterministic structural features, placing each verified solution in a question-specific cell that holds at most one elite.The labeler induces a broader approach vocabulary from verified seeds, while SQL parse features distinguish structures within an approach.Source: §A.2 · p. 13

A.3 Archive search

• Search uses verified candidates from the frozen base model on training questions, prioritizing applicable approaches not yet represented and then those with fewer prior targeting attempts.Candidates are generated from a target approach and preferably a verified parent using a different approach; a candidate enters the cell for the approach it actually uses and fills an empty cell or replaces its elite if shorter.Source: §A.3 · p. 13
• Repeated approaches cannot add archive coverage, and targeting unrepresented approaches first steers search toward approaches the base model rarely produces.Counting targeting attempts also reduces repeated attempts at approaches the base model fails to realize; the procedure finds more distinct approaches than direct sampling.Source: §A.3 · p. 14

A.4 Training with elite replay

• Each training step pairs on-policy GRPO rollouts with verified archive elites for replay, sampled across questions and occupied cells so questions with larger archives do not dominate.The replay loss averages token negative log-likelihood within solutions and then across solutions; its fixed weight is inspired by CHORD, and the archive remains fixed during training.Source: §A.4 · p. 14

B.1 Archive construction for text-to-SQL

• For text-to-SQL, archive construction uses 5,000 BIRD training questions, builds the archive from 1,000, and retains only queries that execute successfully and match the gold result.The 1,000 archive questions are sampled proportionally across databases and difficulty levels and remain in the RL training pool; a separate LLM labels approaches and SQL parse features refine the archive cells.Source: §B.1 · p. 14
• The text-to-SQL search generates 72 candidates per question and selects verified elites across questions for a 1,500-example replay set.Each question receives eight initial samples and eight rounds of eight mutations; the labeler proposes up to eight applicable approaches per question.Source: §B.1 · p. 14

B.2 Prompts for behavior-space construction and search

• The prompt templates have the labeler describe and classify verified queries, propose applicable approaches beyond those already observed, and guide the frozen model to generate a query using a target approach.Mutation prompts can include a verified parent; the search procedure chooses the target approach, and the parent block is omitted when no verified parent is available.Source: §B.2 · p. 15

B.3 Implementation and training configuration

• All methods use the same BIRD training data and train for 100 steps; training runs use four NVIDIA A100 80 GB GPUs.The distributed RL framework is veRL, integrated with Trinity-RFT, with vLLM for rollout generation; two GPUs are allocated to policy optimization and two to rollout generation.Source: §B.3 · p. 16, Table 5 · p. 16
• MaxRL replaces GRPO’s standard-deviation normalization with mean-reward normalization and uses the resulting advantages without subsequent GRPO standardization.MaxRL uses no replay or additional reference-model KL penalty.Source: §B.3 · p. 16
• SetPO combines GRPO advantages with set-level diversity marginals, using λset = 0.05 and τ = 1.0.Marginals are computed within each eight-response group using embeddings from the frozen Qwen3-Embedding-0.6B model.Source: §B.3 · p. 16
• DPH-F preserves questions with eight initially correct responses using forward-KL on cached references, while applying GRPO to the exploration partition.The procedure yields 301 preservation questions and 4,699 exploration questions; it uses 128 cached reference responses per iteration with β = 0.01.Source: §B.3 · p. 16
• EliteReplay and IID replay each use 128 verified archive responses per iteration alongside 128 GRPO questions with eight on-policy responses each.Both optimize the same replay objective and sampling procedure, but IID constructs its archive from independent base-model samples rather than directed quality-diversity search; both archives contain 1,500 verified responses.Source: §B.3 · p. 16

B.4 Evaluation datasets and correctness checks

• BIRD dev and Spider 1.0 dev are evaluated with 128 samples per question; SQL correctness is execution-result agreement with the gold query, and invalid or non-executable queries count as incorrect.Execution accuracy establishes correctness on the given database, not equivalence across all possible databases.Source: §B.4 · p. 16
• AmbiQT measures whether sampled queries cover both valid readings of an ambiguous question, using Both@k as the fraction of questions with a correct query for each reading among k samples.The evaluation uses a reproducible, proportionally stratified sample of 500 questions.Source: §B.4 · p. 17

B.5 Strategy descriptors and evaluation diversity metrics

• Diversity evaluation uses a deterministic AST-based representation distinct from the LLM-assigned search descriptor, distinguishing SQL structures while ignoring superficial differences such as table aliases.The representation includes features such as joins, subqueries, aggregation, window functions, set operations, and ordering with a limit.Source: §B.5 · p. 17

B.6 Retention and coverage change

• Retention measures the fraction of each question’s base-model correct strategies also found among the post-trained model’s correct samples, counting each strategy once and averaging equally across questions.It is reported on BIRD and Spider questions where the base model produces at least two correct strategies.Source: §B.6 · p. 17
• Coverage change compares, for each common strategy, the share of eligible questions with at least one correct query of that type against the base model’s share.BIRD coverage uses the 1,131 questions on which the base model produces a correct query; less common strategies are grouped as “other.”Source: §B.6 · p. 17

B.7 AmbiQT example

• Both@k checks coverage of both readings rather than just one; the example question permits a query over individual earnings or retrieval of a precomputed average.The case studies illustrate per-question behavior behind aggregate retention and coverage results, which are computed over all eligible questions.Source: §B.7 · p. 17, §B.8 · p. 17

C.1 Archive growth during quality-diversity search

• MAP-Elites increases occupied behavior cells from 1,132 after seed sampling to 2,708 after eight mutation rounds.The authors interpret this growth as targeted search finding verified approaches beyond initial sampling.Source: §C.1 · p. 17

C.2 Comparing elite and IID archives

• Among 547 questions represented in both archives, elite-archive solution pairs differ in strategy more often than IID pairs (66.2% versus 45.5%).Both archives use 72,000 generation attempts and supply 1,500 verified replay examples.Source: §C.2 · p. 17

C.3 Replay weight

• Larger replay weights modestly reduce pass@1, while pass@128 remains in a similar range across settings.Table 7 reports the BIRD replay-weight comparison; the default weight is used in other experiments.Source: §C.3 · p. 18, Table 7 · p. 18

C.5 Case studies on Spider

• On Spider question Q929, ELITEREPLAY preserves both NOT IN and LEFT JOIN ... IS NULL approaches, while several baselines concentrate on one.The case study presents the two approaches as alternative solutions to the same question.Source: §C.5 · p. 18

C.6 Representative queries

• Representative BIRD and Spider queries illustrate alternative SQL strategies for maximum selection, attribute lookup, anti-joins, joins, and ranking.The examples include subquery and join approaches, as well as structural variants around NOT IN.Source: §C.6 · pp. 18–20

C.4 Coverage change on BIRD and Spider

• On BIRD and Spider, ELITEREPLAY loses less coverage than baselines across the base model’s common strategies.The reported comparison covers every strategy on BIRD and Spider.Source: §C.4 · p. 18, Figure 9 · p. 19, Figure 10 · p. 19