Research map / Large language models / Instruction and fine-tuning
The Best of Both Worlds: Bridging Quality and Diversity in Data Selection with Bipartite Graph
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GraphFilter, a set-cover-style data selection method that builds a sentence–n-gram bipartite graph and greedily selects instructions by the product of SuperFilter quality and TF-IDF n-gram diversity, outperforming nine baselines for SFT on Magpie.
Problem
Selecting a subset of SFT data that balances quality and diversity, since existing methods tend to optimize one at the expense of the other.
Approach
Model the dataset as a bipartite graph between instructions and their n-grams, and iteratively pick the instruction maximizing quality×diversity (TF-IDF over covered n-grams), removing covered n-gram nodes and recomputing priorities after each pick.
Key results
- GraphFilter achieves the best overall average (avgall) for all three backbones, e.g., 47.97 vs 46.70 for SuperFilter on Llama-3-8B, and up to +3.38 over Longest.
- Runtime of 2.48 hours on A100 for 10K selection, versus 32.34 hours for AlpaGasus; the CPU-only variant without priority runs in 0.53 hours.
- Ablation shows removing quality (TF-IDF only) or diversity (SuperFilter only) lowers avgall on Llama-3-8B (46.58 and 46.78 vs 47.97).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| select training data with GraphFilter instead of the strongest overall baseline | Gemma-2-2b · Overall benchmarks | avgall: 34.36 -> 35.06 | Helped |
| select training data with GraphFilter instead of the strongest overall baseline | Mistral-7B-v0.3 · Overall benchmarks | avgall: 38.40 -> 39.38 | Helped |
| select training data with GraphFilter instead of the strongest overall baseline | Llama-3-8B · Overall benchmarks | avgall: 47.19 -> 47.97 | Helped |
| add the combined unigram, bigram, and trigram features (ablation) | GraphFilter · Llama-3-8B overall benchmarks | avgall: 46.48 -> 47.97 | Helped |
| add SuperFilter as the quality metric (ablation) | GraphFilter with TF-IDF diversity · Llama-3-8B overall benchmarks | avgall: 46.58 -> 47.97 | Helped |
| add TF-IDF as the diversity metric (ablation) | GraphFilter with SuperFilter quality · Llama-3-8B overall benchmarks | avgall: 46.78 -> 47.97 | Helped |
| replace SuperFilter with Perplexity as the quality metric (ablation) | GraphFilter with TF-IDF diversity · Llama-3-8B overall benchmarks | avgall: 47.97 -> 46.43 | Hurt |
| use 3-grams instead of 1-grams (ablation) | GraphFilter · Llama-3-8B overall benchmarks | avgall: 46.48 -> 47.97 | Helped |
| use 4-grams instead of 3-grams (ablation) | GraphFilter · Llama-3-8B overall benchmarks | avgall: 47.97 -> 47.43 | Hurt |
| apply GraphFilter to instructions rather than responses (ablation) | Llama-3-8B · Overall benchmarks | avgall: 44.68 -> 47.97 | Helped |
| remove the priority function (ablation) | GraphFilter · 10K subset selection | runtime (hrs): 2.48 -> 0.53 | Helped |
| use a quality-only SuperFilter selection instead of GraphFilter | data selection · Smaller budgets (1K and 5K instances) | model performance | Helped |
Surprising findings
- Quality-based ArmoRM subsets perform well on AlpacaEval-2.0 but poorly on other benchmarks, and Perplexity-selected data gives the worst GSM8K results.
- Applying GraphFilter to responses as well as instructions reduces performance versus instruction-only application.
Limitations
- Quality metric (SuperFilter with GPT-2) and n-gram order chosen by heuristics; only evaluated on Magpie-based 10K subsets.
- Gains over best baselines on some benchmarks are small (e.g., HellaSwag), and GraphFilter is second on some metrics.
Experimental setup
Datasets: Magpie-Pro-300K-Filtered MMLU ARC HellaSwag GSM8K AlpacaEval-2.0 MT-Bench
Benchmarks: MMLU ARC HellaSwag GSM8K AlpacaEval-2.0 MT-Bench
Metrics: accuracy length-controlled win rate win rate MT-Bench score MTLD runtime
Baselines: Random Longest Perplexity ArmoRM AlpaGasus Deita SuperFilter Kmeans InsTag
Builds on: SuperFilter set cover greedy algorithm Magpie
Closest papers by meaning
- Towards Scalable Data Diversification for Language Model Pretraining via Leverage Score Sampling (NeurIPS 2026 · similarity 0.90)
- Harnessing Diversity for Important Data Selection in Pretraining Large Language Models (ICLR 2025 · similarity 0.90)
- CoLoR-Filter: Conditional Loss Reduction Filtering for Targeted Language Model Pre-training (NeurIPS 2024 · similarity 0.88)
- SmallToLarge (S2L): Scalable Data Selection for Fine-tuning Large Language Models by Summarizing Training Trajectories of Small Models (NeurIPS 2024 · similarity 0.88)
- DELIFT: Data Efficient Language model Instruction Fine-Tuning (ICLR 2025 · similarity 0.88)
- DsDm: Model-Aware Dataset Selection with Datamodels (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.