The Best of Both Worlds: Bridging Quality and Diversity in Data Selection with Bipartite Graph
Authors: Minghao Wu
Thuy-Trang Vu
Lizhen Qu
Gholamreza Haffari
Venue: ICML 2025 poster (2025)
Keywords: Large Language Models
Data Selection
Primary area: deep_learning->large_language_models

Abstract: The performance of large language models (LLMs) is strongly influenced by the quality and diversity of data used during supervised fine-tuning (SFT). However, current data selection methods often prioritize one aspect over the other, resulting in suboptimal training outcomes. To address this, we formulate data selection as a set cover problem and present GraphFilter, a novel approach that balances both quality and diversity in data selection. GraphFilter models the dataset as a bipartite graph connecting sentences to their constituent n-grams, then employs a priority function that combines quality and diversity metrics multiplicatively. GraphFilter iteratively selects sentences with the highest priority, removes covered n-grams from the bipartite graph, and recomputes priorities to reflect the changing data landscape. We validate GraphFilter using three model backbones across six widely-used benchmarks, demonstrating that it outperforms nine existing baselines in both model performance and computational efficiency. Further analysis shows that our design choices lead to more effective subset selection, underscores the value of instruction diversity, and provides insights into how quality and diversity interact with different subset sizes.

The Best of Both Worlds: Bridging Quality and Diversity in Data Selection with Bipartite Graph
Minghao Wu Thuy-Trang Vu
Lizhen Qu'
Gholamreza Haffari
Abstract
2023; Mesnard et al., 2024; Yang et al., 2024). Central to the success of these models is the quality and diversity of the data used during supervised fine-tuning (SFT). Fine- tuning on high-quality data ensures that the model learns accurate language patterns and responds appropriately to imputs (Wang al., 2023; Zhou al., 2023), while diversity in the data allows the model to generalize across different contexts and topies (Abbas et al., 2023; Maharana al., 2024). However, the vastness of available SFT data presents challenge: selecting subset of data that balances both quality and diversity to optimize model performance.
The performance of large language models (LLMs) is strongly influenced by the quality and diversity of data used during supervised fine- tuning (SFT). However, current data selection methods often prioritize aspect over the other, resulting in suboptimal training outcomes. To address this, we formulate data selection set cover problem and present GRAPHFILTER, a novel approach that balances both quality and di- versity in data selection. GRAPUFILTER models the dataset as a bipartite graph connecting sen- tences to their constituent n-grams, then employs priority function that combines quality and di- versity metrics multiplicatively. GRAPHIILTER iteratively selects sentences with the highest pri- ority, removes covered n-grams from the bipar- tite graph, and recomputes priorities to reflect the changing data landscape. We validate GRAPH- FILTER using three model backbones across six widely-used benchmarks, demonstrating that it outperforms nine existing baselines in both model performance and computational efficiency. Fur- ther analysis shows that our design choices lead to more effective subset selection, underscores the value instruction diversity, and provides in- sights into how quality and diversity interact with different subset sizes.
Recent methods for data selection often prioritize either quality diversity, rarely achieving an optimal balance of both. Approaches that focus exclusively quality may overlook the variety of language patterns necessary for effec- tive generalization (Marion et al., 2023; Ankner et al., 2024), Conversely, methods emphasizing diversity might include lower-quality data, which could negatively impact model performance (Abbas al., 2023; Lu et al., 2024). This focus can result in models that either overfit specific data patterns underperform due to the inclusion of irrelevant poor-quality data. Hence, it is crucial develop data selection strategy that simultaneously maximizes both data quality and diversity for effective supervised fine-tuning.
In response to this challenge, we formulate data selection as set cover problem and propose a novel method, GRAPH- FILTER, which models both diversity and quality in data selection. The cover problem aims select the smallest collection of subsets to cover every element in given uni- versal set (Garey & Johnson, 1979). To achieve this in data selection, GRAPHFILTER models the dataset as a bipartite graph, where sentences and n-grams are represented as two distinct sets of nodes, with edges indicating the presence of n n-grams in sentences. This bipartite structure allows us to prioritize sentences that introduce unique n-grams, thereby maximizing the diversity of the selected subset. In addi- tion to diversity, GRAPHFILTER incorporates quality into the selection process by re-ranking sentences based on quality metric. To balance these two aspects, we employ a priority function that combines quality and diversity met- ries multiplicatively. Coneretely, we use SUPERFILTER (Li et al., 2024a) the quality metrie. measures the infor-
1. Introduction
Large language models (LLMs) have significantly advanced the field of natural language processing (NLP), enabling models to generate coherent and contextually relevant text across variety of tasks (Ouyang al., 2022; Sanh et al., 2022; OpenAI, 2023; Touvron et al., 2023a;b; Anil et al.,
'Department of Data Science AI, Monash University, Mel- bourne, Australia. Correspondence Minghao Wu <ming- h mdu..
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

The Best of Both Worlds: Bridging Quality and Diversity in Data Selection with Bipartite Graph
mativeness of response by comparing its perplexity when conditioned on the instruction with its standalone perplexity. Moreover, we leverage Term Frequency-Invers, Document Frequency (TF-IDF) scores for n-grams within sentences as the diversity metric. The priority function multiplies these two measures, assigning higher priority to sentences that are both informative (high-quality) and contribute substantially to n-gram diversity. During selection, GRAPHFILTER itera- tively chooses the sentence with the highest priority, updates the bipartite graph by removing covered n-grams, and recal- culates priorities based on the updated graph. By balancing diversity and quality in this manner, GRAPHFILTER effec- tively build a subset of examples that is both high-quality and broadly representative of the entire dataset.
2. Related Work
Data Engineering for Large Language Models The suc- cess of recent large language models (LLMs) largely relies on the data used during their training process (Zha et al.. 2023). State-of-the-art LLMs are generally trained on vast corpora (OpenAI, 2023; Team et al., 2024; Dubey et al., 2024). A significant area of research focuses on curating high-quality corpora for pre-training these models (Raffel et al., 2020; Computer, 2023; Soldaini et al., 2024; Penedo et al., 2024). Furthermore, Wang et al. (2023) demonstrate that LLMs are capable of synthesizing high-quality datasets for supervised fine-tum tinettuning which leads to a surge of research dataset synthesis (Xu et al., 2023; Li et al., 2023; Gu- nasekar et al., 2023; Ding et al., 2023; Cui et al., 2023; Wu et al., 2024; Chen et al., 2024a; Xu et al., 2024). These re- search efforts facilitate the synthesis of large-scale datasets containing billions of tokens for various purposes, resulting in a significant demand for selecting valuable subsets.
To demonstrate the effectiveness of GRAPHFILTER, we con- ducted extensive experiments, comparing GRAPHFILTER against nine baseline approaches using three model back- bones across six widely-used benchmarks. Our empirical re- sults indicate that GRAPHFILTER significantly outperforms offte-of-the-ar the-art baselines and achieves notably better computational efficiency. Specifically, in terms of overall performance, GRAPUFILTER substantially outperforms all the baseline approaches across three model backbones, and is significantly more efficient than most baselines without re- quiring GPUs for computation. GRAPHFILTEE outperforms the baselines by up to +2.37 for GEMMA-2-2B, +3.02 for BUSTRAL-7B-VO. and +3.38 for LLAMA-3-8B, and is significantly more efficient than these baselines without re- quiring GPUs for computation. Furthermore, we perform an in-depth analysis validate the effectiveness of our design choices in GRAPHFILTER, examine the characteristics of the selected subsets and the importance of instruction di- versity, and investigate the impacts of quality and diversity under various data scales.
recent state-of
Data Selection Data selection strategies aim iden- tify the most informative data subsets for training or fine- tuning models by considering quality and diversity. Quality- focused approaches prioritize metrics like complexity, diffi- culty, or informativeness (Marion et al., 2023; Chen et al., 2024b; Liu et al., 2024; Li et al., 2024b;a), but may ne- glect the range of language patterns needed for generaliza- tion. Conversely, -iversity-focused methods capture a broad spectrum of linguistic patterns and contexts, potentially incorporating lower-quality data that could impair model performance (Abbas et al., 2023; Lu et al., 2024).
Ours To overcome limitations in current data selection methods, we propose GRAPHFILTER, a novel approach that represents the dataset as a bipartite graph of sentences and their n-grams, By balancing quality and diversity with a priority function, our method improves model performance across various downstream tasks.
In summary, the contributions of this work are threefold:
We frame data selection as a set cover problem and introduce novel approach, GRAPHFILTER, which leverages a bipartite graph structure to balance both diversity and quality. This bipartite graph connects sentences to their constituent n-grams, enabling the construction of subset of examples that is not only high-quality but also broadly representative of the en- tire dataset (see Section 3).
3. Methodology
In this section, we first introduce the data selection problem for supervised fine-tuning in Section 3.1. Subsequently, we describe the modeling of the dataset as bipartite graph in Section 3.2. Finally, we explain the re-ranking of the graph nodes using a priority function that integrates quality and diversity metrics in data selection in Section 3.3.
Through experiments using three model backbones across six widely-used benchmarks, we demonstrate that our method, GRAPHFILTER, surpasses existing data selection strategies, achieving significantly better computational efficiency (see Section 4).
3.1. Data Selection Problem
Our detailed analyses provide valuable insights into the design choices of GRAPHFILTER, the characteristics of the selected subset, and the importance of quality and diversity in relation to the subset sizes (see Section 5).
The data selection problem involves the challenge of iden- tifying and selecting the most relevant and informative subset of supervised instances from a larger dataset to fine-tune large language models (LLMs). Formally, let D = U be the supervised fine-tuning (SFT)
2

---

The Best of Both Worlds: Bridging Quality and Diversity in Data Selection with Bipartite Graph
Algorithm 1 GRAPHFILTER
disjoint and independent sets such that every edge connects vertex from the other set. For- mally, bipartite graph G = (u, V,E) consists of sentence nodes (U = ) n n-gram nodes (V = { M. 1). and edges (E C u x V). This structure allows us to capture the occurrence of n-grams within sentences, providing a foundation for selecting sentences that maximize n- n-gram coverage while adhering to specific priorities. We introduce the details of the priority for re-ranking the sentences based both quality and diversity in Section 3.3.
1: Input: 21 = {u, I the set of sentence nodes; V {u,}}== the set of n-gram nodes; & - 4 x V. the set of edges between sentence nodes and n-gram nodes; k the data selection budget; (()), the priority function for each U;
vertex from one
2: Output: The selected subset S;
3: S ==0
4: while |S] < kA do
5: u² + arg ueu d(u) {Select
the sentence with the highest
priority)
Our objective is select a subset of sen- tences, denoted S, from the entire dataset, constrained by a data selection budget k. The aim is to maximize the coverage of unique n-grams while aligning with a priority function <(u) for each sentence u E U. As illustrated in Algorithm I, our method, referred to as GRAPHFILTER, operates iteratively by updating the graph structure to reflect the n-gram coverage as sentences are selected. The pro- begins with an empty set of selected sentences, S 0, and a bipartite graph G that includes sentence nodes, n-gram nodes, and connecting edges. In each iteration, we select the sentence u² E lI that has the highest priority score ((u"), add u² to S, and then remove u* from the set of remaining sentences U. Next, we identify the n-grams covered by u", denoted as Vus. We then remove all edges that connect u² to the n-gram nodes in Vu-. Subsequently, all edges con- necting to nodes in V.. are eliminated from the graph. Note that the priority of each sentence u E U is computed based on the most recent graph G during each iteration.
GRAPHFILTER
6: Vu- + f (u E) (Find n-gram nodes connected to u*}
7: S + SUU(") {Add u' to the selected set}
8: u + u \ [u*} (Remove x' from the remaining sentences]
9: & E ((uu,e) 1 V {Remove edges connected to u²}
10:
for all v Vu- do
11:
+ & v(, E u} {Remove edges connecting to h}
12: end for
13: end while
dataset, where æ; represents the instruction and yi its corre- sponding response for the i-th training instance. Our aim is to select a subset Sn of size from D. utilizing the data se- lection strategy æ. where is the data selection budget. The objective is to determine the optimal data selection strategy x² that is capable of selecting subset S, maximizing the performance of the fine-tuned LLM fo on the downstream tasks DMs. Therefore, the data selection problem can be formally formulated as:
Set Cover Problem Our problem formulation is related to the classical set cover NP-hard problem (Garey & Johnson, 1979). In the set cover problem, given universe of elements and a collection of sets whose union comprises the universe, the objective to identify the smallest number of sets whose union still contains all elements in the universe. Similarly, in special case of our problem where the priority function assigns the same score to all sentences (i.e., d(u) for all u E Lf), and the goal is to find the minimal set of sentences that cover all n-grams, our task becomes analogous to the set cover problem. In this scenario, the greedy approach used in Algorithm can be shown to have an approximation factor of H (r)) (Vazirani, 2001), where is the maximum degree of the sentence nodes in the graph (the largest number of grams contained in any sentence), and (r) Eh & is the r-th harmonic number. This relationship highlights the theoretical foundations of our method and provides insight into its performance guarantees in this special case.
n² = arg max R (fo: Dw,,, subject to |S²| = k, where 0 FF,
(1)
where S₂ is the subset of the training data selected by the strategy ı, FineTune(FF, Sxx) denotes the parameters of the model backbone FF after fine-tuning on the selected data subset. Sx, fo is the fine-tuned model with parameters 0, and R (fe; Dea) is the performance metric (c.g., accuracy) of the fine-tuned model fo evaluated on the test set Dia-
3.2. Modeling Datasets as Bipartite Graphs
In our approach, we model the dataset as bipartite graph to effectively represent the relationships between sentences and their constituent n-grams. A bipartite graph is a spe- cial type of graph whose vertices can be divided into two
A Minimalist Example Moreover, we present a minimal- ist example in Figure 1. Initially, the bipartite graph is displayed in Figure la. In Figure 1b, the sentence node 41 is selected as u" in Algorithm 1, along with its associated
3

---

The Best of Both Worlds: Bridging Quality and Diversity in Data Selection with Bipartite Graph
u
V
u
V
u
V
u
V
U1
01
U1
01
U1
01
U1
U1
1/2
1/2
1/2
12
22
02
U2
02
03
03
03
03
13
03
V3
04
14
114
04
14
14
u4
U/
U5
075
15
45
VG
(a) Initial Graph
(b) Selection
(c) Remove Edges
(d) Remove Nodes
Figure I: An example of a single iteration of GRAPHFILTER without the priority function. In this case, the degree of a sentence node serves as the priority score. Sentence nodes are in blue and n n-gram nodes in green. The selected sentence node is yellow, while connected n-gram nodes are red. Removed n-gram nodes are white, with removed edges as dashed lines. Node un is selected in the current iteration, and 44 will be the next.
n-gram nodes, Va,, which are highlighted in red. Figure Ic demonstrates the removal of edges connected #1 and Var, as indicated by dashed lines. Finally, Figure 1d illustrates the removal of isolated nodes, shown in white. The next se- lected sentence node is u4. In this example, GRAPHFILTER can cover all the n-grams by selecting only i1 and u4.
Quality Metric For quality, we employ the SUPERFILTER as the quality measure (Li et al., 2024a;b). The SUPERFIL- TER metric evaluates the informativeness of response by comparing the perplexity of the response conditioned on the instruction with the perplexity of the response alone. Formally, for a given sentence node u associated with the enstruction-respons pair (z, y), the quality priority metric is defined as:
By modeling the dataset as a bipartite graph and employing an iterative selection algorithm, GRAPHFILTER effectively selects subset of sentences that maximizes n-gram cover- age while adhering to specified priorities. Note that each SFT training instance comprises instructions and responses. In this work, we apply GRAPHFILTER solely to the instruc- tions of the SFT data.
(UALITY(w) = SUPERFILTER(Z,0) = PPL x)
PPL
1 T
where PPL((W) = exp
log P(we wee)
(2)
where PPL(W) ) is the perplexity of the sentence w with a length of T, PP) is the perplexity of the response y, and PPL(y x)) is the perplexity of the response y conditioned on the instruction x. higher SUPERFILTER value indicates that the response is more relevant and informative given the instruction, thus reflecting higher quality. It is important to note that the choice of quality metric can be determined based on specific user needs and the quality scores can be precomputed prior to the selection process.
Implementation In a brute-force implementation, the computational complexity of our algorithm is O(N) per iteration. This complexity results from the need to perform operations such as selecting the tighest-priorit, sentence and removing edges, which involve scanning the sets of sen- tences (l)), n-grams (V), and edges (E). These sets are not optimized for efficient access modification. To enhance computational efficiency, we employ max-heap (or prior- ity queue) to select the highest-priority sentence, allowing this selection to be performed in Olog N) time per itera- tion. This reduces the selection complexity from O(N) to O Olog N). Additionally, the max-heap data structure facili- tates the localization of priority updates affected nodes, eliminating the need to enumerate all nodes and edges.
Diversity Metric For diversity, we use the Term Frequency-Inverse Document Frequency (TF-IDF) measure of the significance of each n-gram within the dataset. The TF-IDF score of an n-gram v is calculated as TF-IDF(u) = TF(u) x IDF(v), where TF()) (Term Frequency) is the number of times n-gram u appears in the sentence, and IDF(v) (Inverse Document Frequency)
3.3. Balancing Quality and Diversity with Priority Function
is defined as IDF(u) log ) with N being the total number of sentences in the corpus, and de being the number of sentences containing n- n-gram v. Furthermore, we com- pute the sum of TF-IDF scores of all n-grams (of varying lengths) present in the sentence:
As illustrated in Algorithm 1, GRAPHFILTER naturally se- lects subset with maximal n-gram coverage, emphasizing data diversity. However, the quality of the data is equally important for effective language model training. To balance both quality and diversity in our selection process, we de- fine a priority function d(u) for each sentence node u e U which is used re-rank the sentence nodes during selection.
DIVERSITY = Σ TF-IDF(v),
(3)
VEV.

---

The Best of Both Worlds: Bridging Quality and Diversity in Data Selection with Bipartite Graph
where Vu is the set of n-grams connected sentence u in the graph G. In our work, Vu includes unigrams (n = 1), bigrams (n = 2), and trigrams (n = 3) present in sentence e, capturing both word-level and phrase-level features.
(IFD) metric computed by smaller language models. Li et al. (2024b) introduce this method, while Li et al. (2024a) demonstrate that smaller models can be used for computing IFD scores.
Diversity-based (8) KMEANS clusters the training instances with the state-of-the-ar sentence embedding model and selects the training instances that are closest their respective cluster centroids (Arthur & Vassilvit- skii, 2007); (9) INSTAG is designed for analyzing the SFT dataset by tagging the topics of training instances, and can be used for selecting the subset with the most diverse topics from the entire dataset (Lu et al., 2024),
Priority Function To effectively prioritize sentences based on both quality and diversity, we combine the QUAL- ITY score and the DIVERSITY score for the sentence node into a single priority function:
d(u) = QUALITY(U) x DIVERSITY(U).
(4)
This function assigns higher priority to sentences that are both high-quality and contribute significantly to n-gram diversity. By integrating both quality and diversity into the priority function, our selection algorithm can effectively choose a subset of examples that are both high-quality and broadly representative of the entire dataset.
We present more details of baselines in Section A.1. We conduct experiments using three diverse model backbones, including GEMMA-2-2B (Team et al., 2024), MISTRAL-7B- v0.3 (Jiang et al., 2023), and LLAMA-3-A0 (Dubey et al., 2024). The optimization details are in Section A.2.
4. Experiments
Evaluation We conduct evaluations on six popular bench- marks, categorized into two groups:
In this section, we initially outline our experimental setup in Section 4.1, followed by our main results in Section 4.2.
Standardized: We assess the LLMS using LM- CILLUATION-HARNESS (Gao al., 2024) on four standardized benchmarks: MMLU (Hendrycks et al., 2021), ARC (Clark et al., 2018), He HellaSwap (Zellers et al., 2019), and GSM8K (Cobbe et al., 2021). The model performance on these benchmarks is measured by accuracy. We use the macro-average accuracy across four benchmarks as the overall performance of this group, denoted as (
4.1. Experimental Setup
Training Dataset Xu et al. (2024) utilize state-of-the- art open-source large language models (LLMs) to create high-quality dataset collection known as Magpie. In our research, we employ the Magpie dataset, which is and comprises 300K training instances.' For this study, we choose a subset of 10K training instances using various selection methods from the entire dataset, unless otherwise stated.
generated by LLAMA-3-70B-INSTEN
LLM--s-a-Judge: We evaluate LLMs using AlpacaEval-2.0 (Dubois et al., 2024) and MT-Bench (Zheng et al., 2023), with GPT-40- 2024-05-13 as the judge. For AlpacaEval-2 222 O, 197-4-1106-PREVEE
Baselines We compare our approach, GRAPHIFITER,, with diverse array of baseline methods:
generates reference answers, and we report both the length-controlled win rate (LC) and the original win rate (WR). For MT-Bench, performance is denoted as jMM, the macro-average across all categories. Overall performance of this group, /LLM. is the macro-average of LC and Par-
Heuristic: (1) RANDOM randomly selects a subset from the entire dataset; (2) LONGEST sorts the training instances in descending order based on the length of the instructions:
Quality-based: (3) PERPLEXITY utilizes perplexity values, where larger values typically indicate higher difficulty and quality of training instances; (4) AR- MORM is the state-of-the-art open-sourced reward model presented by Wang et al. (2024); (5) ALPAGA- SUS demonstrates that state-of-the-art L.MSs can be di- rectly prompted for estimating data quality (Chen et al., 2024b): (6) DEITA leverages CHATGPT to synthesize quality estimation dataset and fine-tune LLMs for data quality estimation (Liu et al., 2024); (7) SUPER- FILTER indicates the InstructionnFollloiing Difficulty
We define overall model performance, MALL. as the macro- average of results from four standardized benchmarks, LC, and par- In calculating PALL and P Mur is scaled by 10x to align with range of I to 100, matching other benchmarks. Further evaluation details are in Section A.3.
4.2. Main Results
GRAPHFILTER surpasses all baseline approaches. As shown in Table 1, GRAPHFILTTER consistently outperforms all baseline approaches across the three model backbones on both standardized benchmarks and LLM-as L.MM-as-aJJudee bench- marks. It achieves either the best or second-bes best results on most individual benchmarks. Specifically, in terms of PALL.
httpss/////uggggaac...oo Magpie- Bagpie-Alln wateee-Anggggggi-----eea Pwt.eeee--ooooooPPo1- Polo--000---PPeeeee
5

---

The Best of Both Worlds: Bridging Quality and Diversity in Data Selection with Bipartite Graph
Table I: Main results given by GEMMA-2-2B, MISTRAL-7B-VO.3. and LLAMA-3-8B on the standardized benchmarks and LLM-as- as-a-J benchmarks. HS, GSK, and AE-2 correspond Wellaswag, GSM8K, and AlpacEEvall al-2 respectively. The best results are highlighted in bold, and the second-hest results are highlighted underline.
Standardized
LLM-as-a-Judge
MMLU
ARC
HS
G8K
AE-2
MT MT-Bench
PALL
AABENC
PLaM
Acc
Acc
Acc
Acc
LC
WR
Mae
1st
2nd
GEMMA-2-21
RANDOM
25.25
47.52
58.27
9.10
35.03
10.77
13.73
4.73
5.44
4.01
29.01
33.03
LONGEST
25.50
47.06
56.43
8.79
34.45
10.40
13.10
4.79
5.54
4.05
29.17
32.69
PERPLEXITY
23.34
47.58
59.04
6.48
34.11
12.19
14.76
4.98
5.75
4.21
31.00
33.07
ARMORM
25.42
48.06
56.19
10.62
35.07
13.40
16.39
4.84
5.55
4.14
30.92
33.69
ALPAGASUS
26.56
47.18
58.69
10.57
35.75
13.12
15.76
4.89
5.68
4.11
31.03
34.18
DEITA
28.72
47.51
58.35
10.16
36.18
12.99
15.86
4.82
5.62
4.01
30.57
34.31
SUPERFILTER
28.82
47.20
59.18
9.33
36.13
12.87
15.55
4.88
5.49
4.26
30.81
34.36
KMEANS
28.39
46.96
56.59
10.31
35.56
12.19
14.76
4.98
5.74
4.23
31.00
34.04
INSTAG
27.60
47.75
59.98
9.86
36.29
12.75
15.47
4.79
5.45
4.13
30.31
34.30
GRAPHFILTER
29.06
47.92
59.38
10.71
36.77
13.14
15.99
5.01
5.77
4.25
31.64
35.06
MISTRAL- 7B
v0.3
RANDOM
25.50
52.17
67.44
9.17
38.57
14.76
17.41
5.03
5.93
4.13
32.51
36.55
LONGEST
25.17
52.11
67.32
10.30
38.73
13.67
16.14
4.96
6.00
3.91
31.62
36.36
PERPLEXITY
30.64
52.42
69.31
4.62
39.25
13.60
16.18
4.98
6.01
3.95
31.70
36.73
ARMORM
28.84
50.85
68.85
9.63
39.54
15.56
18.89
5.13
5.93
4.34
33.43
37.51
ALPAGASUS
28.67
51.92
68.61
9.48
39.67
14.67
18.14
5.21
6.13
4.30
33.40
37.58
DEITA
29.86
50.82
67.99
10.60
39.82
14.08
16.49
5.03
5.93
4.13
32.18
37.27
SUPERFILTER
33.59
52.45
68.56
9.93
41.13
13.59
16.75
5.23
6.01
4.44
32.92
38.40
KMEANS
28.77
50.58
67.81
11.55
39.68
13.98
16.83
5.11
5.93
4.29
32.52
37.29
INSTAG
28.29
50.99
67.44
12.59
39.82
14.55
17.36
5.11
5.86
4.36
32.84
37.50
GRAPHFILTER
33.24
52.48
69.69
11.92
41.83
15.16
18.85
5.38
6.23
4.54
34.49
39.38
LLAMA-33
8B
RANDOM
49.55
52.00
67.30
22.14
47.75
22.17
25.05
S.99
6.95
5.03
41.04
45.51
LONGEST
44.52
50.56
67.99
24.56
46.91
20.17
22.67
5.97
6.82
5.13
39.96
44.59
PERPLEXITY
51.08
52.31
68.74
20.96
48.27
20.38
22.87
6.02
7.02
5.01
40.28
45.61
ARMORM
47.84
52.24
68.11
24.64
48.21
23.45
26.60
6.19
7.14
5.24
42.66
46.36
ALPAGASUS
49.90
51.63
68.40
25.89
48.96
22.90
25.94
6.09
7.05
5.13
41.90
46.60
DEITA
48.49
52.40
68.46
25.78
48.78
22.23
24.42
6.12
7.12
5.11
41.70
46.42
SUPERFILTER
50.16
51.10
67.70
27.45
49.10
22.54
24.68
6.13
7.23
5.03
41.91
46.70
KMEANS
51.98
51.35
67.15
25.12
48.90
22.06
24.80
6.14
7.03
5.25
41.72
46,51
INSTAG
53.16
52.85
67.86
25.85
49.93
22.10
24.64
6.13
7.05
5.21
41.72
47.19
GRAPHFILTER
53.73
52.92
67.76
27.81
50.55
22.95
26.71
6.26
7.21
5.31
42.79
47.97
GRAPHFILTER outperforms the baselines by up to +2.37 for GEMMA-2-2BB +3.02 for MISTRAL-7B-VV +3.38 for LLAMA-3-8BB compared to LONGEST. These re- sults demonstrates the superiority of GRAPUFILTER which effectively combines the quality and diversity in selection.
sults in the worst performance GSM8K, highlighting the risks of depending solely neural models for selecting high-quality data.
and
GRAPHFILTER is highly efficient, with its variant run- ning quickly on a CPU. Recent baselines typically rely on neural models for quality estimation, which generally re- quire a GPU. We compare the runtimes of various baselines on system equipped with an A100 80G GPU and 20 CPU cores, as shown in Table 2. As elaborated in Section 3.3, GRAPHFILTER defaults to using quality estimation model for QUALITY (u). When utilizing SUPERFILTER, GRAPH- FILTER completes its tasks 2.48 hours, highlighting its efficiency. Notably, without using the priority function d(u) for re-ranking, GRAPHFIn FILTEE
Quality- data selection approaches appear to exhibit biases towards specific benchmarks. Quality- based approaches often use neural models to estimate the quality of each training instance. However, these mod- els display biases that can significantly affect downstream performance. As demonstrated in Table 1, models fine- tuned on subsets chosen by ARMORM perform well on AlpacaEva1-22 22.0 but poorly on other benchmarks. Fur- thermore, the PERPLEXITY-Seles subset consistently re-
ILTTER becomes even faster, taking
6

---

The Best of Both Worlds: Bridging Quality and Diversity in Data Selection with Bipartite Graph
Table 2: Runtime (in hours) for selecting 10K training in- stances. indicate the CPU-only method.
Table 4:
Ablation study for QUALITY(u) and DIVERSITY(U) in the priority with LLAMA-3-8B. indicates the component is not used.
Runtime (hrs)
PERPLEXITY
0.92
QUALITY(U) DIVERSITY
PBENCH
PLLMM
PALL
ARMORM
5.93
RANDOM
TF-IDF
47.75
41.04
45.51
ALPAGASUS
32.34
SUPERFILTER
TF-IDF
50.55
42.79
47.97
DEITA
22.65
PERPLEXITY
TF-IDF
49.21
40.85
46.43
SUPERFILTER
1.95
ARMORM
TF-IDF
49.01
41.85
46.61
KMEANS
2.26
DEITA
TF-IDF
49.11
41.97
46.73
INSTAG
25.48
X
TE-IDF
48.94
41.87
46.58
GRAPHFILTER
2.48
SUPERFILTER
X
49.52
41.28
46.78
w/o priority ((u)
0.53
X SUPERFILTER SKYWORKRM
X 48.27
40.28
45.61
MTLD
50.15
42.42
47.47
MTLD 49.51
42.01
46.93
Table 3: Ablation study for n-gram combination with LLAMA-3-8B. / indicates that various n-grams used.
Table 5: Ablation study for the choice of n-gram order with LLAMA-3-8B. #nodes indicates the total number of nodes in the bipartite graph. RT indicates the runtime in hours.
N-gram
JBENCH
FLLM
PALL
Unigram
Bigram
Trigram
50.55
42.79
47.97
D-gram
#nodes
RT (hrs)
Дuuseи
MALL
49.02
41.41
46.48
0.1M
2.12
49.02
41.41
46.48
/
49.09
41.70
46.63
2
1.0M
2.30
49.58
42.14
47.31
49.84
41.78
47.15
2.6M
2.48
50.55
42.79
47.97
4.8M
3.38
50.11
42.63
47.43
7.4M
4.58
50.44
42.81
47.95
only 0.53 hours on CPU. This is up to 61x faster than other baselines, compared to 32.34 hours by ALPAGASUS.
measure leads to reduced performance, highlighting the im- portance of using optimal metrics. These findings support our decision integrate quality and diversity in the priority.
5. Analysis
Combining n-grams captures features at different lev- els. We examine the effectiveness of n-gram combinations, which are designed to capture both word-level and phrase- level features. The results are presented in Table 3. Our ob- servations suggest that the variant of GRAPHFILTER, which integrates unigrams (n = 1), bigrams (n = 2), and trigrams (n 3), significantly outperforms other variations that do not incorporate n-gram combinations. Different n-grams capture features at varying levels, and merging them can effectively consolidate this information.
GRAPHFILTER is compatible with various quality met- rics. In this work, we leverage SUPERFILTER as the de- fault quality metric due to its effectiveness and efficiency. However, GRAPHFILTER is designed to be flexible and is not limited to using SUPERFILTER alone. This flexibility allows the method to adapt to different evaluation needs by incorporating alternative quality metrics. As demonstrated in Table 4, the QUALITY component the priority func- tion duu) can be replaced with various quality metrics, such PERPLEXITY, ARMORM, and DEITA. This adaptability highlights the robustness and versatility of GRAPHFIL.TER.
Both QUALITY(w) and DIVERSITY(U) in priority fune- tion enhance the data selection. We provide empirical evidence in Table 4 showcasing the effectiveness of our pro- posed priority function. By incorporating the QUALITY(U) metric (using SUPERFILTER) and the DIVERSITY metric (using TF-IDF) into GRAPHFILTER, we achieve superior performance across all evaluation metries. This demon- strates that combined priority function significantly hances the model's 's ability to select high-quality and diverse training data. Omitting either the quality metric (X TF- IDF) or the diversity metric (SUPERFILTER + X) results in noticeable performance declines. Furthermore, replacing the SUPER FILTER metric with PERPLEXITY as the quality
The choice of trigrams (n 3) balances the model per- formance and efficiency. We conduct experiments with n-gram sizes from to 5 using LLAMA-3-8E, As shown in Table 5, our results indicate a significant performance im- provement when moving from unigrams (n 1) to trigrams (n 3). However, beyond n 3, we observe diminish- ing
negative returns. Furthermore, the number of n-gram nodes increases substantially with (from M. for unigrams to 7.4M for 5-grams), as well as the runtime (from 2.12 12 hours to 4.58 hours). These findings demonstrate that the trigrams (n = 3) is the optimal choice for balancing performance and efficiency in our experiments.

---

The Best of Both Worlds: Bridging Quality and Diversity in Data Selection with Bipartite Graph
45
Graphe ArMORM!
Gracht Iue mrab
ARMMRR
-40
Quality f
35
GRATIFITTTR
LoNGestt
AG
30
PERZLES EXIT4 AMEANS
26
80
100
110
Diversity f
(a) Quality-Diversity relationship
(b) GRAPHFILTER vs. ARMORM
(c) GRAPHFILTER vs. INSTAG
Figure 2: Figure 2a displays the diversyy relationships of subsets selected by different methods, with 1 indicating preference for higher values. Figure 2b shows the semantic diversity in a t-SNE plot of subsets from GRAPHFILTER and ARMORM, where green rectangles indicate data points chosen by GRAPHFILTER but not by ARMORM. Figure 2c depicts the semantic diversity in t-SNE plot comparing subsets from GRAPHFILTER and INSTAG.
Table 6: Applying GRAPUFILTER to instructions and re- sponses with LLAMA-3-8B, The / indicates that GRAPH- FILTER is applied. Lexical diversity is measured by MTLD (McCarthy & Jarvis, 2010), and quality is assessed using ARMORM, scaled by 100x.
I SurinFrutik
1 DxSTAG II GRAMIPLNTA
25
1.5
Content Type
Benchmarks
Lexical Diversity
Quality
Inst.
Resp.
PeaM
MALL
Inst.
Resp.
-05
1X
5K
10K
SOK
100K
200K
50.55 42,79 47.97
102.43
71.74
81.54
Data selection budget
47.16 39.71 44.68
90.22
73.57
81.52
/
48.03
41.20
45.76
90.13
72.60
81.52
Figure 3: Performance gap (Axil) with respect to PALL comparing SUPERFILTER, INSTAG, and GRAPHFILTER against RANDOM, across various data selection budgets.
GRAPHFILTER effectively balances quality and diversity in its selected datasets. In this section, we analyze the subsets selected by GRAPHFILTER and other methods, with results shown in Figure 2. To confirm that GRAPHFILTER maintains quality and diversity, we measure lexical diver- sity using the MTLDD metric (McCarthy & Jarvis, 2010) and assess data quality with the advanced reward model, SKYWORKRM (Liu& & Zeng, 2024). As depicted in Fig- ure 2a, GRAPHFILTER achieves the highest lexical diver- sity and ranks second in data quality. We also visualize GRAPHFILTER instructions compared with ARMORM and INSTAG using the RGE-LARRG--N-VV.. model. It is evi- dent that GRAPHFILTER selects instructions not chosen by ARMORM, shown by green rectangles in Figure 2b. Further- more Figure 2c illustrates that GRAPHFILTER and INSTAG exhibit similar semantic diversity. These results suggest that GRAPUFILTER not only selects high-quality data but also maximizes dataset diversity.
ates the impact of applying GRAPHFILTER to instructions, responses, or both on model performance. As shown in Table 6, applying GRAPHFILTER only to instructions pro- duces the best benchmark results, greatly improving lexical diversity in instructions with minimal effect on response diversity compared to other methods. Notably, all three vari- ations maintain similar quality with different performances, underscoring the importance of instruction diversity.
The priority of quality and diversity varies with data se- lection budgets, and GRAPHFILTER excels at balancing these two factors effectively. After showcasing GRAPHI- FILTER's superiority. an open question remains: When should diversity be prioritized over quality, and vice versa? We hypothesize that the data selection budget plays crucial role in determining the priority between quality and diver- sity and present the results in Figure 3. Our results indicate that the effectiveness of quality-based and diversity-basee strategies is medge--dependent. Specifically, the quality- based SUPER FILTERR excels with smaller budgets (1 K and
Prioritizing instruction diversity most effectively im- proves model performance. Each SFT training instance comprises an instruction and its response. This study evalu-
8

---

The Best of Both Worlds: Bridging Quality and Diversity in Data Selection with Bipartite Graph
5K instances), but its advantage diminishes as the budget increases. This suggests that quality-based methods with neural models may exhibit biases toward certain linguistic patterns, which limits model generalization when the budget is sufficiently large. Conversely, the diversity-based INSTAG performs poorly with small budgets but surpasses SUPER- FILTER with larger ones. This observation demonstrates that diversity- based methods are more prone to introducing low- quality data with smaller budgets. Notably, GRAPHFILTER consistently achieves significant performance gains com- pared to R RANDOM across all budget levels. These findings show that the data selection budget influences the effective- ness of different approaches, and GRAPHFILTER success- fully integrates both quality and diversity.
Acknowledgements
We would like to thank the anonymous reviewers and pro- gram chairs for their constructive feedback and valuable suggestions, which have greatly improved the quality of this paper. This work is partly supported by the ARC Future Fellowship FT190100039.
References
Abbas, A., Tirumala, K., Simig, D., Ganguli, S., and Mor-
cos, A. S. Semdedup: Data-efficient learning at web-scale through semantic deduplication. CoRR, abs/2303, 3000000 2023, doi: 10.48550/ARXXV.223330002222 000.0 URL https: //doi www.i..rg//ioo 1 4804448550//aa 2303 09540.
6. Conclusion
Anil, R., Borgeaud, S., Wu, Y., Alayrac, J., Yu, J.. Sori- cut, R., Schalkwyk, J., Dai, A. M., Hauth, A., Millican, K. Silver, D., Petrov, S., Johnson, M., Antonoglou, I., Schrittieser, J., Glaese, A., Chen, J., Pitler, E., Lilli- crap, T. P., Lazaridou, A., Firat, O., Molloy, J., Isard, M., Barham, P. R., Hennigan, T.,, Lee, B., Viola, F., Reynolds, M., Xu, Y., Doherty, R., Collins, E., Meyer, C.,, Ruther- ford, E., Moreira, E., Ayoub, K., Goel, M., Tucker, G., Piqueras, E., Krikun, M., Barr, I., Savinov, N., Danihelka, I., Roclofs, B., White, A., Andreassen, A., von Glehn, T., Yagati, L.,, Kazemi, M., Gonzalez, L.., Khalman, M., Sygnowski, J., and et al. Gemini: A family of highly capable multimodal models. CoRR, abs/2312. 11055, 2023, doi: 10.4555/AARXIV22312.1888 //doi. org/ 10. 480404550/0/
In this work, we formulate data selection as a set cover problem and introduce GRAPHFILTER, novel method for data selection that models the dataset as a bipartite graph linking sentences to their constituent n-grams. To balance quality and diversity, we use a priority function that com- bines quality metric with diversity metric, allowing us to select subsets that enhance n-gram diversity and maintain high response quality. Our extensive experiments demon- strate GRAPHFILTER'S 's effectiveness across three model backbones and six benchmark datasets. Compared to nine baseline methods, GRAPHFILTER consistently delivers supe- rior model performance and computational efficiency. Our analyses validate our design choices, assess the subsets cho- sen by GRAPHFILTER and other methods, highlight the importance of instruction diversity, and examine the role of quality and diversity relative to subset sizes. We believe GRAPHFILTER lays the groundwork for more effective data selection strategies, encouraging further research in data selection for LLMs.
URL https: 2312 11805.
Ankner, Z., Blakeney, C., Sreenivasan, K., Marion, M., Leavitt, M. L., and Paul, M. Perplexed by perplexity: Perplexity-based data pruning with small reference mod- els. CoRR, 200/2221552051,, 2024. doi: 10.48550/ARXIV. 2405 20541. URL https: /tw./iooooooo/ooo oowpioooroo......o /00gg///...0 /80.4455/00. arXiv 2405 20541.
48550/
Impact Statement
Arthur, D. and Vassilvitskii, k-means++: the advan- tages of careful seeding. In Bansal, N., Pruhs, K., and Stein, C. (eds.), Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pp. 1027-1035. SIAM, 2007. URL http: /ddl.acm. acc. org/citat
Our proposed method, GRAPHFILTER, aims to improve the efficiency and effectiveness of LLM training by enabling the selection of high-quality, diverse data subsets. This could lead to more resource-efficien model training processes and potentially better-perfon perter-peforming models. While the primary impact of our work methodological, we acknowledge that improvements in LLM training techniques could indirectly contribute to the broader adoption and application of these models across society. We believe the computational effi- ciency benefits of our approach align with efforts to reduce the environmental impact of training large models. As with any advancement in AI capabilities, we encourage thought- ful consideration of how improved language models might be deployed and used in practice.
cfm? -ereiidd2ii33330 1283382833338 111.83...888881 1283494.
Chen, J., Qadri, R., Wen, Y., Jain, N., Kirchenbauer, J., Zhou, T., and Goldstein, T. Genqa: Generating millions of instructions from handful of prompts. CORR, abs/2406. 10323, 2024a. doi: 10.48550/ARXIV. 2406. 10323. URL http:://t///tt...... http://d...ogg.g././/o 48550/ arXiv. 2406 10323.
Chen, L., Li, S., Yan, J., Wang. H., Gunaratna. K., Yadav, V., Tang, Z., Srinivasan, V., Zhou, T., Huang, H., and Jin,

---

The Best of Both Worlds: Bridging Quality and Diversity in Data Selection with Bipartite Graph
H. Alpagasus: Training better alpaca with fewer data. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7- 11, 2024. OpenReview.net, 2024b. URL https:// www/ffounm wteerrummiidFFdooeeoeee d=FdVxgSShvx
Billock, J., Hong, J., Lee, J., Fu, J., Chi, J., Huang, J., Liu, J., Wang, J., Yu, J., Bitton, J., Spisak, J., Park, J., Rocca, J., Johnstun, J., Saxe, J., Jia, J., Alwala, K. V., Upasani. K., Plawiak, K., Li, K., Heafield, K., and Stone, K. The Ilama 3 herd of models. CoRR, abs/2407. 21000721788 21733, 2024, doi: 10.48550AARXX1224771177555 URL https: / //doi.org////// 10. 48w50/ 240.:.ii............ 217833
Clark, P., Cowhey, I., Etzioni, O., Khot, T., Sabharwal, A., Schoenick, C., and Tafjord, O. Think you have solved question answering? try arc, the A12 reasoning challenge. CoRR, abs/1 055477 2018. URL http://arxis arg/abs/1803 05457.
Dubois, Y., Galambosi, B., Liang, P., and Hashimoto, T. B. Length-controlled alpacaeval: A simple way to debias automatic evaluators. CoRR, abs/2404.04475, 2024. doi: 10.48550AARXX1.24400.44777 URL https: https:///di...// org 1C. 0ww.4445550///. 2404 04475. 04475.
Cobbe, K. Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert. M., Tworek, J., Hilton, J., Nakano, R., Hesse, C., and Schulman, J. Training verifiers solve math word problems. CoRR, abs/2 2021. URL https:/ / /aaaxixivvorr/ abs /tab/////100 221001101111 14168.
Gao, L., Tow, J., Abbasi, B., Biderman, S., Black, s., DiPofi,
A., Foster, C.. Golding, L., Hsu, J., Le Noac'h, h, A., Li,
H., McDonell, K., Muennighoff, N., Ociepa, C., Phang,
J., Reynolds, L., Schoelkopf, H., Skowron, A., Sutawika,
Computer, T. Redpajama: an open dataset for training
L., Tang, E., Thite, A., Wang, B., Wang. K., and Zou, A. A framework for few-shot language model evaluation,
large language models, 2023, URL ht htsps: //gittu.. com/ httm//togetherccmpuuerree RedPa Data.
07 2024. URL https: / zenodo. org/ records/ 12608602.
Cui, G., Yuan, L., Ding. N., Yao, G., Zhu, W., Ni, Y., Xie, G., Liu, Z., and Sun, M. Ultrafeedbcck: Boosting language models with high-quality feedback. CoRR, abs/2310.01377, 2023. doi: 10.48550/ARXIV. 2310.01377, URL https:://oolt http///i..ogg././////oo// 48550/ arXiv. 2310 01377.
Garey, M. R. and Johnson, D. S. Computers and Intractabil- ity: A Guide to the Theory of NP- J.P-Completeness. W. H. Freeman, 1979.
Gunasekar, S., Zhang, Y., Aneja, J., Mendes, C. T., Giorno, A. D., Gopi, S., Javaheripi, M., Kauffmaan,, P., de Rosa, G., Saarikivi, O., Salim, A., Shah, S., Behl, H. S., Wang, X., Bubeck, S., Eldan, R., Kalai, T., Lee, Y. 'T,, and Li, Y. Textbooks CoRR, abs/2306. 11644, 2023, doi: 10.48550/ARXIV. 2306.11644 URL https: tttp:/iooogo......o////. arXiv.2305 11644.
Ding, N., Chen, Y., Xu, B., Qin, Y. Hu, S., Liu, Z., Sun, M., and Zhou, B. Enhancing chat language models by scaling high-quality instructional conversations. In Bouamor, H., Pino, J., and Bali, K. (eds.), Proceedings of the 2023 Conference on Empirical Methods Natural Lan- guage Processing, pp. 3029-3051, Singapore, December 2023. Association for Computational Linguistics. doi: 10. 10.18663/w1120233emmbpp http://22022emmmmmmmmm........ main. URL https:// ac sclanthologg wrgg 2023 emnlp-ma i 183.
all you need.
Hendrycks, D., Burns, C., Basart, S., Zou, A., Mazeika, M., Song, D., and Steinhardt, J. Measuring massive multitask language understanding. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, forum?
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A.,
Goyal, A., Hartshorn, A., Yang, A., Mitra, A., Sravanku- mar, A., Korenev, A., Hinsvark, A., Rao, A., Zhang, A., Rodriguez, A., Gregerson, A., Spataru, A., Rozière, B., Biron, B., Tang, B., Chern, B., Caucheteux, C., Nayak, C., Bi, C., Marra, C., McConnell, C., Keller, C., Touret, C., Wu, C., Wong, C., Ferrer, C. C., Nikolaidis, C., Allonsius, D., Song, D., Pintz, D., Livshits, D., Esiobu, D., Choud- hary, D., Mahajan, D., Farcia-Olano D., Perino. D., Hup- kes, D., Lakomkin, E., AlBadawy, E., Lobanova, E., Di- nan, E., Smith, E. M., Radenovic, F., Zhang, F., Synnaeve, G., Lee, G., Anderson, G. I., Nail, G., Mialon, G., Pang, G. Cucurell, G., Nguyen, H., Korevaar, H., Xu, H. Tou- vron, H., Zaroy, I., Ibarra, A., Kloumann, I. M., Misra, I., Evtimov, I., Copet, J., Lee, J., Geffert, J., Vranes, J., Park, J., Mahadeokar, J., Shah, J., van der Linde, J.,
2021. URL httph: /openreviewweeeeeeeeeeeeeee / Jm=-d
Jiang, A. Q., Sablayrolles, A., Mensch, A., Bamford, C., Chaplot, S., de Las Casas, D., Bressand, F., Lengyel, G., Lample, G., Saulnier, L.,, Lavaud, L. R., Lachaux, M., Stock, P., Scao, T. L., Lavril, T., Wang, T., Lacroix, T., and Sayed, W. E. Mistral 7b. CoRR, abs/23 10.06825, 2023. doi: 10.4850/ARRXI.23100666 / //doi.orrg... /10.0//000000
URL https: 2310 .6825..
Li, H., Koto, F., Wu, M., Aji, A. and Baldwin, T. Bactrian- x A multilingual replicable instruction-followiii model with low-rank adaptation. CORR, abs/2305. 15011, 2023. doi: 10.48550/ARXIV22305.. 15011. URL https: 40t5:///..455///////////
10

---

The Best of Both Worlds: Bridging Quality and Diversity in Data Selection with Bipartite Graph
Li, M., Zhang, Y., He, S., Li, Z., Zhao, H., Wang. J., Cheng, N., and Zhou, T. Superfiltering: Weak-to-strong data filtering for fast instruction-tuning. In Ku, L.-W,, Mar- tins, A., and Srikumar, V. (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pupers), pp. 14255-14273, Bangkok, Thailand, August 2024a. Association for Com- putational Linguistics. doi: 10.18653w11/02244c11oorr 769. URL https: https////aaaaaaooooooooooo.. acl-long long. 766.
2309.04564. URL https: /ow..oog/1...../ 48550/ a arXiv 2309. 04564.
McCarthy, P. M. and Jarvis, S. Mtld, vocd-d, and hd-d: A validation study of sophisticated approaches to lexical diversity assessment. Behavior research methods, 42(2): 381-392, 2010.
Mesnard, T., Hardin, C., Dadashi, R., Bhupatiraju, S., Pathak, S., Sifre, I.., Rívière, M., Kale, M. S., Love, J., Tafti, P., Hussenot, L., Chowdhery, A., Roberts, A., Barua, A., Botev, A., Castro-Ros, A., Slone, A., Héliou, A., Tacchetti, A., Bulanova, A., Paterson, A., Tsai, B., Shahriari, B., Lan, C. L.,, Choquette-Chon C. A., Crepy, C., Cer, D., Ippolito, D., Reid, D., Buchatskaya, E., Ni, E., Noland, E., Yan, G., Tucker, G., Muraru, G., Rozhdestvenskly, G., Michalewski, H., Tenney, I., Gr- ishchenko, I,, Austin, J., Keeling, J., Labanowski, J., Lespiau, J., Stanway, J., Brennan, J., Chen, J., Ferret, J., Chiu, J., and et al. Gemma: Open models based on gemini research and technology. CoRR, abs/2403.082 08295, 2024. doi: 00-4550/ARRXXI224000002292 http..orrr/0.44555//axivv....0 08229.
Li, M.. Zhang, Y., Li, Z., Chen, J., Chen, L., Cheng, N., Wang. J., Zhou, T., and Xiao, J. From quantity to qual- ity: Boosting LLM performance with self-guided data selection for instruction tuning. In Duh, K., Gomez, H., and Bethard, S. (eds.), Proceedings of the 2024 Confer- ence of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies (Volume I: Long Papers), pp. 7602-7635, Mex- ico City, Mexico, June 2024b. Association for Compu- tational Linguisties. doi: 10. 10..8653/w120024mmac--oooo
URL https:
421. URL https: : http///aaantoool.org/////22 naacl -orec-llogg.. 421.
OpenAL. GPT- technical report. CoRR, abs///a3.0/2777777 2023. doi: 1044550/rxxiw.22330087444 URL https: 10. (tw..4445500r.. www.::2ii..3030.777..4. 08774.
Liu, C. Y. and Zeng, L. Skywork reward model series. https:/ https://hugghte /huggingface...//kyyaa Skywork, September 2024. URL https: htapss////ggggggaae..e. Skywok...
co/
Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C. L.,, Mishinn, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., Schulman, J., Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P. F., Leike, J., and Lowe, R. Training language models to follow instructions with human feedback. In NeurlPS, 2022.
Liu, W., Zeng, W., He, K., Jiang, Y., and He, J. What makes good data for alignment? A comprchensive study of auto- matic data selection in instruction tuning. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenRe- view.net, 2024. URL https:/ wpw.reveee.eeeeeeeeeeeeee. net/ Borum?iddBTKALLLyy
Penedo, G., Kydlícek, H., Allal, L. B., Lozhkov, A., Mitchell, M., Raffel, C., von Werra, L., and Wolf, T. The fineweb datasets: Decanting the web for the finest 2024. doi: text data at scale. CoRR, URL https: //doi. 10.488550AAXXI.2206...77 17557. org/10. , 000.448555/xii 2406 17557.
Lu, K., Yuan, H., Yuan, Z. Lin, R., Lin, J., Tan, C., Zhou, C., and Zhou, J. #instag: Instruction tagging for analyzing supervised fine-tuning of large language models. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. URL https: //openreviee formm det.:ruwwb.....ssseeeeebbbb.b..
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I., et al. Language models are unsupervised multitask learners. OpenAl blog, 18):9, 2019.
Maharana, A., Yadav, P., and Bansal, M. D2 pruning: Mes- sage passing for balancing diversity & difficulty in data pruning. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. URL https: //operrevi ew net/ forum? d=thbtt.kkee...
Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, P. J. Exploring the limits of transfer learning with a unified text-to-text trans- former. Mach. Learn. Res., 21:140: 2020. URL http: httpp//.rr//appre/////2//2// html.
Marion, M., Üstün, A., Pozzobon, L., Wang. A., Fadacc, M., and Hooker, S. When less is more: Inves- tigating data pruning for pretraining Ilms at scale. CoRR, abs/2309.00 04564, 2023. doi: 10. 10.48550/ARXIV
Sanh, V., Webson, A., Raffel, C., Bach, S. H., Sutawika,
L., Alyafeai, Z., Chaffin, A., Stiegler, A., Raja, A., Dey, M., Bari, M. S., Xu, C., Thakker, U., Sharma, S. S.,

---

The Best of Both Worlds: Bridging Quality and Diversity in Data Selection with Bipartite Graph
Szczechla, E., Kim, T., Chhablani, G., Nayak, N. V., Datta, D., Chang, J., Jiang, M. TT, Wang, H., Manica, M., Shen, S., Yong. Z. X., Pandey, H., Bawden, R., Wang, T., Neeraj. T., Rozen, J., Sharma, A., Santilli, A., Févry, T., Fries, J. A., Teehan, R., Scao, T. L.., Bi- derman, S., Gao, L., Wolf, T., and Rush, A. M. Mul- titask prompted training enables zero-shot task gener- alization. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. Open 2022. URL https: //openreviee ew. net/forum wiw.iiiddvvvvvbwe
Miller, M., Rahtz, M., Watson, M., Risdal, M., Kazemi, M. Moynihan, M., Zhang, M., Kahng, M., Park, M., Rahman, M., Khatwani, M., Dao, N., Bardoliwalla, N., Devanathan, N., Dumai, N., Chauhan, N., Wahltinez, O., Botarda, P., Barnes, P., Barham, P., Michel, P., Jin, P., Georgiev, P., Culliton, P., Kuppala, P., Comanescu, R., Merhej, R., Jana, R., Rokni, R. A., Agarwal, R., Mullins, R., Saadat, S., Carthy, S. M. Perrin, S., Amold, S. M. R., Krause, S., Dai, S., Garg, S., Sheth, S., Ronstrom, S., Chan, S., Jordan, T., Yu, T., Eccles, T., Hennigan, T., Kocisky, T. Doshi, T., Jain, V., Yadav, V., Meshram, V., Dharmadhikari, V., Barkley, W., Wei, W., Ye, W., Han, W. Kwon, W. Xu, X., Shen, Z., Gong, Z., Wei, Z., Cotruta, V. Kirk, P. Rao, A., Giang, M., Peran, L.,, Warkentin, T., Collins, E., Barral, J., Ghahramani, Z., Hadsell, R., Sculley, D., Banks, J., Dragan, A., Petrov, S., Vinyals, O., Dean, J., Hassabis, D., Kavukcuoglu, K., Farabet, C., Buchatskaya, E.,, Borgeaud, S., Fiedel, N., Joulin, A., Kenealy, K., Dadashi, R., and Andreev, A. Gemma 2: Improving open language models at practical size, 2024. URL https: / arxiv. org/ abs//aa///// 2408. 00118.
Soldaini, L.. Kinney, R., Bhagia, A., Schwenk, D., Atkin- son, D., Authur, R., Bogin, B., Chandu, K., Dumas, J., Elazar, Y., Hofmann, V., Jha, A., Kumar, S., Lucy, L., Lyu, X., Lambert, N., Magnusson, I., Morrison, J. Muennighoff, N., Naik, A., Nam, C., Peters, M., Ravichander, A., Richardson, K., Shen, Z., Strubell, E., Subramani, N., Tafjord, O., Walsh, E., Zettlemoyer, L., Smith, N., Hajishirzi, H., Beltagy, I., Groeneveld, D., Dodge, J., and Lo, K. Dolma: an open corpus of three trillion tokens for language model pretraining re- search. In Ku, L.-W., Martins, A., and Srikumar, V. (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 15725-15788, Bangkok, Thailand, August 2024. Association for Computational Linguis- tics. doi: 10. 10.18665///122024.acll 840. URL https: ///ac//antholooy..orr///////////
Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., Rodriguez, A., Joulin, A., Grave, E., and Lample, G. Llama: Open and efficient foundation lan- guage models. CoRR, abs/2302.13991 1044855/ARXIV.23022.155
2023a. doi: URL https:/ /doi. org/10. 48550 htt.5/0/axxv..22. 230.. 13971.
acl -l-cclllll long. 840.
Team, G., Riviere, M., Pathak, S., Sessa, P. G., Hardin, C., Bhupatiraju, S., Hussenot, L., Mesmard, T., Shahriari, B., Ramé, A., Ferret, J., Liu, P., Tafti, P., Friesen, A., Casbon, M., Ramos, S., Kumar, R., Lan, C. L.,, Jerome, S., Tsit- sulin, A., Vieillard, N., Stanczyk, P., Girgin, S., Momchev, N., Hoffman, M., Thakoor, S., Grill, J.-B., Neyshabur, B., Bachem, O., Walton, A., Severyn, A., Parrish, A., Ahmad, A., Hutchison, A., Abdagic A., Carl, A., Shen, A., Brock, A., Coenen, A., Laforge, A., Paterson, A., Bastian, B., Piot, B., Wu, B., Royal, B., Chen, C., Kumar, C., Perry, C., Welty, C., Choquette- Chho, C. A., Sinopalnikov, D., Weinherger, D., Vijaykumar, D.,, Rogoziáska, D., Her- bison, D., Bandy, E., Wang, E., Noland, E., Moreira, E., Senter, E., Eltyshev, E., Visin, F., Rasskin, G., Wei, G. Cameron, G., Martins, G., Hashemi, H. Klimezak- Pluciáska, H., Batra, H., Dhand, H., Nardini, I., Mein, J. Zhou, J., Svensson, J., Stanway, J., Chan, J., Zhou, P.. Carrasqueira, J., Iljzii J., Beeker, J., Fernandez. J., van Amersfoort, J., Gordon, J., Lipschultz. J., Newlan, J., yeong Ji, J., Mohamed, K., Badola, K., Black, K., Milli- can, K., McDonell, K., Nguyen, K., Sodhia, K., Greene, K., Sjoesund, L. L., Usui, L., Sifre, L., Heuermann, L., Lago, L., McNealus, L., Soares, L. B., Kilpatrick, L., Dixon, L., Martins, L., Reid, M., Singh, M., Iverson, M., Görner, M., Velloso, M., Wirth, M., Davidow, M.,
Touvron, H., Martin, L.,, Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., Bikel, D., Blecher, L.,, Canton-Ferres C., Chen, M., Cucurull, G., Esiobu, D., Fernandes, J., Fu, J., Fu, W., Fuller, B., Gao, C., Goswami, V., Goyal, N., Hartshorn, A., Hosseini, S., Hou, R., Inan, H., Kardas, M., Kerkez, V., Khabsa, M., Kloumann, I., Korenev, A., Koura, P. S., Lachaux, M., Lavril, T., Lee, J., Liskovich, D., Lu, Y., Mao, Y., Martinet. X., Mihaylov, T., Mishra, P., Molybog, I., Nie, Y., Poulton, A., Reizenstein, J., Rungta, R. Saladi, K., Schelten, A., Silva, R., Smith, E. M., Sub- ramanian, R. Tan, X. E.,, Tang. B., Taylor, R., Williams, A., Kuan, J. X., Xu, P., Yan, Z., Zarov, I., Zhang, Y. Fan, A., Kambadur, M., Narang, S., Rodriguez, A., Stojnic, R., Edunov, S., and Scialom, T. Llama 2: Open founda- tion and finc-tuned chat models. CoRR, 22//2307.09288 2023b. doi: 0004885WAARXXV222070002222 //doi. org 100 485544855//// 2307 09288.
URL https:
Vazirani, V. V. Approximation Algorithms. Poringer-Verlag
Berlin, Germany, 2001.
Wang, H., Xiong, W., Xie, T., Zhao H., and Zhang, T. Interpretable preferences via multi -ujti-objecctiv reward mod- eling and mixture-of-experrs CoRR, abs/2406. 12845,
12

---

The Best of Both Worlds: Bridging Quality and Diversity in Data Selection with Bipartite Graph
2024. doi: 10448550/ARXXI222061153888 URL https: /ttp//100..0555//1111111/ / 12845
the Association for Computational Linguistics, pp. 4791- 4800, Florence, Italy, July 2019. Association for Compu- tational Linguistics. doi: 10. 10.18653/w1//19--1477 URL https///allatthol..o httpss//dcaaccboooooooooo///2222
Wang. Y., Kordi, Y., Mishra, S., Liu, A., Smith, N. A., Khashabi, D., and Hajishirzi, H. Self-instruct: Align- ing language models with self-generated instructions. In Rogers, A., Boyd-Graber, J., and Okazaki, N. (eds.), Pro- ceedings of the 61st Annual Meeting of the Association for Computational Linguistics ( (Volume 1: Long Papers), pp. 13484-13508, Toronto, Canada, July 2023. Associ- ation for Computational Linguistics. doi: 10.18653/v1/ 2023.acl-long.77 754. URL hwtptttpp//// org/2023 long. 754.
org/p19-1472
Zha, D., Bhat, Z. P., Lai, K., Yang, F., Jiang, Z., Zhong, S.,
and Hu, X. Data-centric artificial intelligence: A survey. CoRR, 0ts/2303.10158 2023, doi: 10.48550/ARXIV, 2303.10158. URL https: ptttts:://do. http://di..rrr....93335 arXiv. 2303. 2303.10158. 10158.
Zheng, L.,, Chiang, W. Sheng, Y., Zhuang, S., Wu, Z., Zhuang, Y., Lin, Z., Li. Z., Li, D., Xing, E. P., Zhang, H., Gonzalez, J. E., and Stoica, I. Judging lim-as-a-judge with mt-bench and chatbot arena. CoRR, 0bss2200600668 2023. doi: 00445500/axii.222600566683 URL https: //doi. org/ 10. 48550 2306 05685.
Wu, M., Waheed, A., Zhang, C., Abdul-Mageed, M., and Aji, A. F. LaMini-LM: A diverse herd of distilled models from large-scale instructions. In Graham, Y. and Purver, M. (eds.). Proceedings of the 18th Confer- ence of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 944-664, St. Julian's, Malta, March 2024. Asso- ciation for Computational Linguistics. URL https: // //aclanthology org.or///////.
Zhou, C., Liu, P., Xu, P., lyer, S., Sun, J., Mao, Y., Ma, X., Efrat, A., Yu, P., Yu, L., Zhang, S., Ghosh, G., Lewis, M., Zettlemoyer, L., and Levy, O. LIMA: less is more for alignment. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, (eds.), Advances in Neural Information Processing Systems 36: Annual Conference Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
Xu, C., Sun, Q. Zheng, K., Geng, X., Zhao, P., Feng, J. Tao, C., and Jiang, D. Wizardlm: Empowering large language models to follow complex instructions. CoRR, abs/2304. 12244, 2023. doi: 10.48550/ARXIV. 2304.12244. URL httph:ttp////ett //tp:::///diiiee org/10..01100000 48550/ arXiv.2300 12244.
Xu, Z.. Jiang, F., Niu, L., Deng, Y.. Poovendran, R., Choi, Y., and Lin, B. Y. Magpie: Alignment data synthesis from scratch by prompting aligned IIms with nothing. CoRR, abs/2406.08464, 2024. doi: 10.48550/ARXIV. 2406.08464. URL https: peetts:://o.... http//oo..o///// org/ 48550/ arXiv. 2406 08464.
Yang, A., Yang, B., Hui, B., Zheng, B., Yu, B., Zhou, C., Li, C., Li, C., Liu, D., Huang, F., Dong, G., Wei, H., Lin, H., Tang, J., Wang, J., Yang, J., Tu, J., Zhang. J., Ma, J., Yang, J., Xu, J., Zhou, J., Bai, J., He, J., Lin, J., Dang, K., Lu, K., Chen, K., Yang, K., Li, M., Xue, M., Ni, N., Zhang, P., Wang, P., Peng, R., Men, R., Gao, R., Lin, R., Wang, S., Bai, S., Tan, S., Zhu, T., Li, T., Liu, T., Ge, W. Deng, X., Zhou, X., Ren, X., Zhang. X., Wei,
X., Ren, x., Liu, X., Fan, Y., Yao, Y., Zhang, Y., Wan,
Y., Chu, Y., Liu, Y., Cui, Z., Zhang. Z., Guo, Z., and Fan, Z. Qwen2 technical report. CORR, 0obs/2407.106777 2024. doi: 10.48550/ARXI22447..000 //doi. www.ioorg1100 httpr///....88..//.
URL https: 48550 www.v http:///vivvvv..... 240. 10671.
Zellers, R., Holtzman, A., Bisk, Y., Farhadi, A., and Choi, Y. HellaSwag: Can a machine really finish your sen- tence? In Korhonen, A., Traum, D., and Marquez, L. (eds.), Proceedings of the 57th Annual Meeting of
13

---

The Best of Both Worlds: Bridging Quality and Diversity in Data Selection with Bipartite Graph
A. Experimental Setup
Ht System:
request your feedback gerfornence + assistant In resporie to the inst lon and the given input steplayed. tollowing.
A.1. Baselines
+
In this work, we compare GRAPHFILTER against following baselines:
#tinnsrrction::
(instruction!
Ht Input: (inptt)
RANDOM selects random subset of size k from the entire dataset, where & is the designated data selection budget.
tt Response: (output
Ht: USER:
LONGEST chooses the top-k instances from the entire dataset, ranking them in descending order based on the number of words in each instruction.
Please rate according to the accuracy ot the responce to the instruction and the input. Each assistant receives 5, waere higher scare indicates higher Level of the accuracy, Plesse tisst output a single line containing value ladiesting the seares. In the line,
on scola
PERPLEXITY selects the top-k instances from the en- tire dataset, sorted in descending order according to the perplexity values of the instructions. For the perplexity computation in this work, we utilize GPT2 (Radford et al., 2019).²
provide corprahensive explanation of your avaluation, avoiding any potential biss.
Figure 4: The prompt used for ALPAGASUS annotation.
ARMORM represents one of the state-of-the-art re- ward models (Wang et al., 2024). It evaluates multiple rewards from diverse perspectives and integrates these rewards using gating network.
These embeddings used for training the KMEANS model with 10K clusters. Once the KMEANS model is established, we cluster the sentence embeddings of in- structions for the entire dataset and select the instances closest to each cluster centroid.
ALPAGASUS employs GPT-3.5-TURBB to assess data quality (Chen et al., 2024b). Given the improved model performance and limited budget, we substitute GEMMA-2-27B-IT in this work, using the prompt il- lustrated in Figure 4. GEMMA-2-27B: of-the-art open large language model (L.LM) and sig- nificantly surpasses GPT-3.5-TURBO according to the Chatbot Arena Leaderboard.
INSTAG is designed to analyze the SFT dataset by tagging the topics of training instances. It can be used select subset with the most diverse topies from the entire dataset (Lu et al., 2024). We utilize the official codes and models released by Lu et al. (2024) for data selection.
is the state-
DEITA utilizes CHATGPT to create quality esti- mation dataset and fine-tune large language models (LLMs) for evaluating data quality (Liu et al., 2024). We employ the official codes and models provided by Liu et al. (2024) for data selection.
A.2. Optimization
Hyperparameters In this study, all experiments utilize the same set of hyperparameters. Specifically, we employ a batch size of 64, a learning rate of 2 x 10-3 3 a warmup ratio of 0.05, and a linear learning rate schedule. All the experiments run for 3 epochs.
SUPERFILTEA refers the nnstloction-Followingg Dif- ficulty (IFD) metric, which is calculated using smaller language models. Introduced by Li et al. (2024b), this method is shown by Li et al. (2024a) to provide IFD scores from smaller models that are as reliable as those from larger models. this study, GPT2 is used for computing these scores (Radford et al., 2019).
Computation Infrastructure For this study, all methods are trained using two A100 80GB GPUs, which are inter- connected via PCIe.
KMEANS involves clustering training instances using state-of-the-art sentence embedding model and select- ing instances that are nearest their respective cluster centroids (Arthur & Vassilvitskii, 2007). In this work, we begin by sampling 50K instances from the entire dataset and encoding their instructions into sentence model.5
A.3. Evaluation
In this work, we evaluate the approaches six widely used benchmarks:
embeddings using the
MMLU (Hendrycks et al., 2021) is a benchmark de- signed to assess knowledge acquired during pretrain- ing, by evaluating models exclusively in zero-shot and few-shot settings. It covers 57 subjects across STEM, the humanities, social sciences, and more, totaling ap-
"nttpsss/hoggingffaeeccoo//p http:///.........oooooo.oaaaaaaa 2
hhttpsss//ugginngfcccccco// 1msys/
hhttse///gsthub..cmmm/uuttttpppp
"ittoss//hngginnfaccc.o////
bge- -ge-1arge-en--1.. Shttps://githin CFm/OFA- Sys/ InsTag
14

---

The Best of Both Worlds: Bridging Quality and Diversity in Data Selection with Bipartite Graph
proximately 14,000 test examples.
ARC (Clark al., 2018) is multiple-choice question- answering dataset containing questions from science exams for grades 3 to 9, amounting to approximately 4,000 test examples.
HellaSwag (Zellers et al., 2019) is a challenging dataset for evaluating commonsense natural language inference, which particularly difficult for state-of-the- art models, though its questions trivial for humans.
It contains approximately 10,000 test examples.
GSM8K (Cobbe et al., 2021) comprises a collection of diverse grade school math word problems created by human problem writers, containing approximately 1,000 test examples.
AlpacaEva1-2.0 0 (Dubois et al., 2024) is an au- tomated tool for evaluating instruction-followwe guage models. Its test set consists of 805 instructions generated by large language models (L.Ms).. Models are evaluated based on the winning rate against a refer- ence answer. judged by a ofate-of-thheart LLM, such as GPT-4. AlpacaEval-2. is an upgraded version of the original A AlpacaEval, featuring reduced length bias for fairer evaluation of responses of varying lengths.
lan-
MT-Bench (Zheng et al., 2023) is multi-turn test set containing 80 questions that cover 8 aspects: writing, roleplay, reasoning, math, coding, extraction, STEM, and humanitics. state-of-the-art LLM, such as GPT- 4, is used to score model outputs on a scale from to 10.
15


Reviews:
[{"review_id": "792qaducz8", "reviewer": "Reviewer_6GvX", "summary": "This paper presents GRAPHFILTER, a novel data selection method designed to address the challenge of balancing data quality and diversity in SFT. The core idea is to model the dataset as a bipartite graph where sentences are connected to their constituent n-grams. By using a priority function that multiplicatively combines quality and diversity metrics, GRAPHFILTER iteratively selects sentences. This approach aims to maximize n-gram coverage while taking into account the quality of the data. Extensive experiments on three mainstream models across six benchmarks show that GRAPHFILTER outperforms nine baselines in terms of both model performance and computational efficiency.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your thoughtful review of our paper on GraphFilter.\n## 1. Generalizability\nGraphFilter demonstrates strong generalizability through consistent performance across three model backbones and six diverse benchmarks. The Magpie dataset used in our experiments is a general dataset covering a wide range of tasks. We will clarify these points in our future revision.\n## 2. Diversity Metrics\n**GraphFilter is designed to be agnostic to the specific quality and diversity metrics used.** We have demonstrated that GraphFilter is compatible with a wide range of quality metrics, as shown in Table 4. Please note that we carelessly presented incorrect results in Table 4, which we will correct in our future revision. Furthermore, we conducted additional experiments using MTLD as the diversity metric. During the iterative selection process, we maintained the bipartite graph structure but updated the MTLD scores iteratively as n-gram nodes were removed. As shown in the table below, GraphFilter is flexible enough to accommodate different quality and diversity metrics while maintaining strong performance.\n| Quality(u)| Diversity(v) | $\\mu_{BENCH}$ | $\\mu_{LLM}$ | $\\mu_{ALL}$ |\n|--|--|--|--|--|\n|SuperFilter | TF-IDF | 50.55 |42.79|47.97|\n|Perplexity| TF-IDF | 49.21 |40.85|46.43|\n|ArmoRM| TF-IDF | 49.01 |41.85|46.61|\n| DEITA| TF-IDF | 49.11 |41.97|46.73|\n| X| TF-IDF | 48.94 |41.87|46.58|\n|SuperFilter |X | 49.52 |41.28|46.78|\n| X|X | 48.27 |40.28|45.61|\n| SuperFilter | MTLD | 50.15 | 42.42 | 47.47 |\n| SkyworkRM| MTLD | 49.51 | 42.01 | 46.93 |\n## 3. Adaptability\nGraphFilter can be easily adapted for domain-specific scenarios. This adaptation can be achieved in two ways: (1) **replacing the default general quality metrics with domain-specific ones**, as discussed in Section 3.3, or (2) **introducing a whitelist for domain-specific terms, allowing n-gram nodes containing these terms to be visited multiple times.** These modifications ensure that domain-specific examples receive higher priority during selection. We will discuss these strategies in our future revision.\n## 4. Error Bars\nWe acknowledge the importance of error bars in our results. Due to limited resources and time, we were unable to run more experiments with different random seeds and include error bars in this rebuttal. We will address this issue in the future revision.\n## 5. Different Subset Sizes and Hyperparameters\nTo evaluate how GraphFilter performs across different subset sizes, we conducted experiments with Llama-3-8B, as shown in Figure 3. Our results demonstrate that the quality-focused data selection method has an advantage when the budget is small, while the diversity-focused method performs better with larger budgets. Our approach consistently outperforms the baseline methods across all budget sizes, demonstrating its robustness and effectiveness.\n\nWe assume that both quality and diversity are equally important for data selection, so we did not introduce any hyperparameters into the priority function (Equation 4). We acknowledge that introducing such hyperparameters could further improve the method's adaptability. Due to limited computational resources and time, we were unable to provide the results in this rebuttal. We will include these results in the future version.\n## 6. Method Name\nWe will change the name to \"GraphFilter\" in the future version to improve readability.\n## 7. Choice of Trigrams\n**Our choice of trigrams was based on our preliminary study to balance between diversity representation, model performance, and computational efficiency.** As shown in the table below, we conducted experiments with n-gram sizes from 1 to 5 using Llama-3-8B. Our results indicate a significant performance improvement when moving from unigrams (n=1) to trigrams (n=3). However, beyond n=3, we observe diminishing or even negative returns. Furthermore, the number of n-gram nodes increases substantially with n (from 0.1M for unigrams to 7.4M for 5-grams), as well as the runtime (from 2.12 hours to 4.58 hours). We will include this analysis in our future revision.\n| n-gram | # of n-gram nodes | Runtime (hrs) | $\\mu_{BENCH}$ | $\\mu_{LLM}$ | $\\mu_{ALL}$ |\n|--|--|--|--|--|--|\n| 1| 0.1M| 2.12| 49.02 | 41.41 | 46.48 |\n| 2| 1.0M| 2.30| 49.58 | 42.14 | 47.31 |\n| 3| 2.6M| 2.48| 50.55 | 42.79 | 47.97 |\n| 4| 4.8M| 3.38| 50.11 | 42.63 | 47.43 |\n| 5| 7.4M| 4.58| 50.44 | 42.81 | 47.95 |\n## 8. Hyperparameter Sensitivity\nIn GraphFilter, the primary hyperparameter is the n-gram size, which we set to 3. This choice is detailed in Section `7. Choice of Trigrams`. Other hyperparameters, such as learning rate and batch size, are kept consistent across all methods to ensure a fair comparison. Furthermore, we acknowledge the potential benefits of introducing an additional hyperparameter to control the balance between quality and diversity in the priority function (Equation 4). Due to limited resources and time, we will include such an analysis in our future revision.", "claims_and_evidence": "This paper made the following main claims, which I think is well supported.\n- GRAPHFILTER can achieve a better balance between data quality and diversity compared to existing methods.\n\n- It achieves sota performance on multiple benchmarks\n\n- GRAPHFILTER is computational efficient. \n\n- The combination of n - gramsand the multiplicative priority function are crucial for the success of the method.\n\n- Applying GRAPHFILTER to instructions alone yields the best performance, emphasizing the importance of diverse instructions in SFT.", "methods_and_evaluation_criteria": "Yes. The methods are novel to me and the evaluation criteria is common used.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "Yes. GRAPHFILTER offers a promising approach to balancing quality and diversity in data selection. The experimental validation is strong, but more details are needed regarding the generalizability of the method, the choice of diversity metrics, and the adaptability to different scenarios.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths\n1. I think the presented method is simple yet effective. Besides, the computational efficiency is impressive. \n \nWeaknesses\n1. There is no mention of error bars (or std) in the tables.\n\n2. The impact of different subset sizes (e.g., 1K vs. 100K) as well as settings of hyperparameters on the balance between quality and diversity needs further exploration.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Would you consider change the name GRAPHFILTER, to GraphFilter? Writing everything in uppercase looks strange to me.\n\n2. How was the choice of using up to trigrams justified? Would variable or larger n - grams improve the results?\n\n3. What is the sensitivity of the hyperparameters?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "mdnYIo9bWh", "reviewer": "Reviewer_ZQbQ", "summary": "This paper introduces GRAPHFILTER, a method to optimize data selection for training large language models by balancing quality and diversity. Using a bipartite graph and a priority function, it enhances model performance and efficiency. Extensive tests show that GRAPHFILTER surpasses traditional methods, demonstrating the role of well-balanced data selection in improving LLM generalization.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your thoughtful review of our paper.\n## 1. Diversity Approach\nWe would like to highlight that **our research demonstrates that lexical diversity through n-grams serves as an effective proxy for semantic diversity.** As shown in Figure 2a and 2c, we demonstrated that the subset selected by GraphFilter exhibits significantly higher lexical diversity compared to all the baselines and is as semantically diverse as those diversity-focused methods (e.g. InsTag). **This suggests that our approach effectively captures semantic diversity through lexical diversity.**\n\nThe semantic diversity could be incorporated by extending our priority function to $\\phi(u) = quality(u) \\times LexicalDiversity(u) \\times SemanticDiversity(u)$. For semantic diversity, we could measure the average pairwise cosine distance between embeddings of the candidate example $u$ and all previously selected examples. A larger distance would indicate higher semantic novelty. However, adding semantic distance calculations would introduce significant computational overhead, particularly for large datasets. Due to limited resources and time, we were unable to conduct this experiment in this rebuttal. We will explore this direction in our future revision.\n## 2. Reliance on SuperFilter\nWe would like to respectfully clarify that **GraphFilter is designed to be agnostic to the specific quality metric used, requiring only that the metric can be computed on a per-example basis.** We discovered an inaccuracy in the original Table 4 results. The updated results presented below actually strengthen our claims: GraphFilter maintains strong performance across various quality metrics. These results demonstrate that, while SuperFilter works best in our setting, our approach is not fundamentally dependent on it and can effectively leverage different quality assessment methods. **When new quality metrics are introduced, GraphFilter can be easily adapted to incorporate them, as long as they can be computed on a per-example basis.** Additionally, as suggested by `Reviewer ipfn`, we evaluated GraphFilter with the MTLD score as the diversity metric and the SkyworkRM as the quality metric. The results are presented in the updated Table 4 as well. **We observe that GraphFilter is also compatible with different diversity metrics, further validating the robustness and flexibility of our approach.** We will update Table 4 accordingly in our revision.\n| Quality(u)| Diversity(v) | $\\mu_{BENCH}$ | $\\mu_{LLM}$ | $\\mu_{ALL}$ |\n|--|--|--|--|--|\n|SuperFilter | TF-IDF | 50.55 |42.79|47.97|\n|Perplexity| TF-IDF | 49.21 |40.85|46.43|\n|ArmoRM| TF-IDF | 49.01 |41.85|46.61|\n| DEITA| TF-IDF | 49.11 |41.97|46.73|\n| X| TF-IDF | 48.94 |41.87|46.58|\n|SuperFilter |X | 49.52 |41.28|46.78|\n| X|X | 48.27 |40.28|45.61|\n| SuperFilter | MTLD | 50.15 | 42.42 | 47.47 |\n| SkyworkRM| MTLD | 49.51 | 42.01 | 46.93 |\n## 3. Priority Function\nOur approach treats quality and diversity as equally important. We acknowledge that introducing an explicit weighting parameter could provide additional flexibility. We will include this discussion and corresponding experiments in our revised manuscript.\n## 4. Instruction-only Application\n**It is important to note that our approach does not ignore responses entirely.** When computing quality scores, we consider both the instruction and its corresponding response, ensuring that instruction-response pairs are of high quality. Furthermore, **every method has its own optimal way of being applied.** As demonstrated in Table 5 of our submission, **applying GraphFilter to instructions yields superior performance compared to applying it to responses or both.** We will include this discussion in our revised manuscript to clarify our design choices.\n## 5. Small Dataset\n**We followed well-established practices from previous works, many of which select comparable or even smaller proportions of data.** SuperFiltering [1] selects up to 7800 examples from 52K training examples. AlpaGasus [2] selects 9K examples from 52K training examples. DEITA [3] selects 10K example from 300K training examples. In our work, we select 10K examples from 300K examples. This proportion is consistent with the scale of data selection in related works and allows us to conduct a fair comparison. Furthermore, we conducted extensive experiments across multiple budget sizes, as shown in Figure 3. Our approach consistently outperforms the baseline methods across all budget sizes, demonstrating its robustness and effectiveness. We will include these additional details in the revised manuscript.\n\nReferences:\n\n1. Superfiltering: Weak-to-strong data filtering for fast instruction-tuning.\" 2024.\n2. Alpagasus: Training a better alpaca with fewer data. 2023.\n3. What makes good data for alignment? a comprehensive study of automatic data selection in instruction tuning. 2023.\n\n## 6. Missing Literature\nWe will incorporate these references in our revised manuscript.", "claims_and_evidence": "The claim that GRAPHFILTER induces the diversity of the selected data is convincing, due to the nature of the set cover problem.", "methods_and_evaluation_criteria": "I have the following concerns about the methodology:\n1.\tMaximizing the n-gram indeed ensures some granular lexical diversity of texts, but the general and more importantly semantic or domain diversity of the texts are not considered. Hence the motivation to apply set cover problems on the n-grams is not that robust.\n2.\tThe quality part relies on the previous work SUPERFILTER, leaving the contribution of the paper mostly to the diversity part.\n3.\tThe priority function in equation (4) is a direct integration of quality and diversity score. A balance between these two might be considered.", "theoretical_claims": "No theoretical claims are found.", "experimental_designs_or_analyses": "The experiments are comprehensive. However, there are some critical issues:\n1.\tThe paper only applies the method to the instructions of the SFT data, which I think is a critical issue. In many cases, the responses of the SFT data are even more important.\n2.\tThe training data might be too small to show the significance of the performance scores in the experiments.\n3.\tThere are more related baselines that are not considered, see “Essential References Not Discussed” below.", "relation_to_broader_scientific_literature": "This paper mostly applies the set cover optimization on the n-grams of texts to select LLM SFT data. The method of using set cover is novel but I think for general improvement of LLM’s performance, this data selection method would have limited contribution.", "essential_references_not_discussed": "The set cover problem is often considered as one of the coreset methods. There are other submodular functions that are easy to implement and maybe should be considered as baselines. For one example of the references, see [1] below. There are other papers that consider the diversity of the data on a higher level, such as the diversity of their quality aspects or topics as in [2] below. The authors might consider citing this paper and even consider it as a baseline. Another related work is [3] below, which also uses the same diversity-based method as in [2] on the data directly. It might also be cited or considered as a baseline.\n\n[1] Kaushal, V., Ramakrishnan, G., & Iyer, R. (2022). Submodlib: A submodular optimization library. arXiv preprint arXiv:2202.10680.\n[2] Li, X., Gao, M., Zhang, Z., Yue, C., & Hu, H. (2024). Rule-based data selection for large language models. arXiv preprint arXiv:2410.04715.\n[3]Yang, Y., Wang, H., Wen, M., Mo, X., Peng, Q., Wang, J., & Zhang, W. (2024). P3: A Policy-Driven, Pace-Adaptive, and Diversity-Promoted Framework for data pruning in LLM Training. arXiv preprint arXiv:2408.05541.", "other_strengths_and_weaknesses": "The application of the set cover is novel and the experiments of the paper are comprehensive. However, there are some critical weaknesses of the paper, as discussed above.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "g66PADDKha", "reviewer": "Reviewer_NgtT", "summary": "The paper introduces GRAPHFILTER, a data selection method for LLM fine-tuning that balances quality and diversity by modeling the dataset as a bipartite graph of sentences and n-grams. The approach iteratively selects sentences using a priority function combining SUPERFILTER (quality) and TF-IDF (diversity). Experiments across three model backbones and six benchmarks show GRAPHFILTER outperforms nine baselines in performance and efficiency. Key contributions include a novel graph-based formulation, a priority function merging quality/diversity, and empirical validation demonstrating superior results.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough assessment.\n## 1. Quality Metrics\nWe would like to clarify that **GraphFilter is designed to be agnostic to the specific quality metric used.** We discovered an inaccuracy in the original Table 4 results. The updated results presented below actually strengthen our claims: GraphFilter maintains strong performance across various quality metrics. These results demonstrate that, while SuperFilter works best in our setting, our approach is not fundamentally dependent on it. **When new quality metrics are introduced, GraphFilter can be easily adapted to incorporate them.** We will update Table 4 accordingly in our revision.\n| Quality(u)| Diversity(v) | $\\mu_{BENCH}$ | $\\mu_{LLM}$ | $\\mu_{ALL}$ |\n|--|--|--|--|--|\n|SuperFilter | TF-IDF | 50.55 |42.79|47.97|\n|Perplexity| TF-IDF | 49.21 |40.85|46.43|\n|ArmoRM| TF-IDF | 49.01 |41.85|46.61|\n|DEITA| TF-IDF | 49.11 |41.97|46.73|\n| X| TF-IDF | 48.94 |41.87|46.58|\n|SuperFilter |X | 49.52 |41.28|46.78|\n| X|X | 48.27 |40.28|45.61|\n| SuperFilter | MTLD | 50.15 | 42.42 | 47.47 |\n| SkyworkRM| MTLD | 49.51 | 42.01 | 46.93 |\n## 2. N-gram\n**Our choice of trigrams was based on model performance and efficiency.** As shown in the table below, we conducted experiments with n-gram sizes from 1 to 5 using Llama-3-8B. Our results indicate a significant performance improvement when moving from unigrams (n=1) to trigrams (n=3). Furthermore, the number of n-gram nodes increases substantially with n, as well as the runtime. We will include this analysis in our future revision.\n| n-gram | # of n-grams | Runtime (hrs) | $\\mu_{BENCH}$ | $\\mu_{LLM}$ | $\\mu_{ALL}$ |\n|--|--|--|--|--|--|\n| 1| 0.1M| 2.12| 49.02 | 41.41 | 46.48 |\n| 2| 1.0M| 2.30| 49.58 | 42.14 | 47.31 |\n| 3| 2.6M| 2.48| 50.55 | 42.79 | 47.97 |\n| 4| 4.8M| 3.38| 50.11 | 42.63 | 47.43 |\n| 5| 7.4M| 4.58| 50.44 | 42.81 | 47.95 |\n## 5. N-gram Importance\nWe would like to point out that **the importance of n-grams is not uniform but is determined by the TF-IDF re-weighting.**  As shown in Table 4, the TF-IDF re-weighting (SuperFilter + TF-IDF vs. SuperFilter + X, and X + X vs. X + TF-IDF) significantly improves the performance of GraphFilter. We will clarify this point in our revision.\n## 3. Scalability Analysis\nWe discussed the implementation details of GraphFilter in Line 192-205. The brute-force GraphFilter has a time complexity of $O(N)$ per example. To improve the scalability, we employed a max-heap (or priority queue) data structure to select the highest-priority examples and reduce the time complexity to $O(log N)$ per example. Due to limited resources and time, we were unable to evaluate GraphFilter on extremely large datasets in this rebuttal. We will clarify this in our future revision.\n## 4. Semantic Diversity\nWe would like to highlight that **our research demonstrates that lexical diversity through n-grams serves as an effective proxy for semantic diversity.** As shown in Figure 2a and 2c, we demonstrated that GraphFilter exhibits significantly higher lexical diversity compared to all the baselines and is as semantically diverse as those diversity-focused methods (e.g. InsTag), **suggesting that our approach effectively captures semantic diversity through lexical diversity.**\n\nFurthermore, the semantic diversity could be incorporated by extending our priority function to $\\phi(u) = Quality(u) \\times LexicalDiversity(u) \\times SemanticDiversity(u)$. For semantic diversity, we could measure the average pairwise cosine distance between embeddings of the candidate example $u$ and all selected examples. A larger distance indicates higher semantic novelty. However, adding semantic distance introduces significant computational overhead, particularly for large datasets. Due to limited resources and time, we were unable to conduct this experiment in this rebuttal. We will explore this direction in our future revision.\n## 5. Priority Function\nWe conduct additional experiments, as suggested. As shown in the table below, the multiplicative priority function outperforms the additive function. We will include this analysis in our revision.\n| Priority Function | $\\mu_{BENCH}$ | $\\mu_{LLM}$ | $\\mu_{ALL}$ |\n|--|--|--|--|\n|Multiplicative| 50.55 | 42.79 | 47.97 |\n|Additive| 49.92 | 42.41 | 47.17 |\n## 6. Bias\n**We do observe bias in the selected examples. This bias stems from the quality-based metrics, rather than our approach.** As discussed in lines 318-329, we observe that metrics like ArmoRM and Perplexity inherently favor certain types of examples. In contrast, GraphFilter addresses this issue by balancing quality and diversity. Although GraphFilter may inherit some bias from the quality metric, it mitigates this bias by incorporating diversity metrics into the selection process.\n## 7. Miscellaneous\nDue to the length limit, we will include discussions and experiments on synthetic dataset, broader literature, out-of-distribution and low-resource settings, and theoretical analysis in our future revision.", "claims_and_evidence": "The claims are supported by comprehensive experiments, including ablation studies, runtime comparisons, and benchmark results. However, the reliance on SUPERFILTER as the sole quality metric raises questions about generalizability. While the paper shows GRAPHFILTER works with other metrics (e.g., PERPLEXITY), it does not thoroughly explore how alternative quality measures (e.g., reward models beyond SUPERFILTER) might affect outcomes. Additionally, the theoretical justification for the set cover approximation could be strengthened by discussing how the priority function impacts the greedy algorithm’s guarantees.", "methods_and_evaluation_criteria": "The bipartite graph framework is well-suited for balancing diversity (via n-gram coverage) and quality. The evaluation criteria (standardized benchmarks, LLM-as-a-judge, and efficiency metrics) are appropriate. However, the paper could better justify the choice of n-gram combinations (unigrams, bigrams, trigrams) and explore sensitivity to n-gram size. The use of the Magpie dataset, while large, may limit generalizability to other domains or data distributions.", "theoretical_claims": "The paper correctly relates GRAPHFILTER to the set cover problem and cites the greedy algorithm’s approximation ratio. However, the analysis assumes uniform n-gram importance, which may not hold in practice (e.g., rare n-grams might be more critical). The theoretical discussion would benefit from addressing how TF-IDF weighting interacts with the coverage objective.", "experimental_designs_or_analyses": "The experimental design is robust, with multiple baselines, model backbones, and benchmarks. The runtime comparison (CPU vs. GPU baselines) highlights practical advantages. However, the paper does not test GRAPHFILTER on out-of-distribution data or explore how diversity impacts generalization in low-resource settings. Additionally, the reliance on synthetic Magpie data (generated by LLAMA-3-70B) may not reflect real-world data selection challenges.", "relation_to_broader_scientific_literature": "The work builds on data selection/curation for LLMs (e.g., SemDedup, DEITA) and diversity-aware methods (e.g., KMEANS, DPPs). However, it does not engage with recent advances in active learning or coresets for LLMs, which also aim to balance quality/diversity. The bipartite graph approach is novel but could be compared to graph-based data pruning methods in other domains (e.g., recommender systems).", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "Strengths :\n\nNovel integration of quality/diversity via bipartite graphs.\n\nStrong empirical results across diverse benchmarks.\n\nEfficient CPU implementation, reducing hardware barriers.\n\nWeaknesses :\n\nLimited exploration of quality metric alternatives (e.g., reward models).\n\nN-gram approach may miss semantic diversity captured by embeddings.\n\nNo analysis of how GRAPHFILTER affects downstream bias/fairness.", "other_comments_or_suggestions": "Other Comments Or Suggestions\n\nClarify how n-gram selection (unigrams, bigrams, trigrams) was optimized.\n\nDiscuss scalability to billion-scale datasets.\n\nInclude a sensitivity analysis for the priority function’s multiplicative form (e.g., additive alternatives).", "questions_for_authors": "How does GRAPHFILTER perform with alternative quality metrics (e.g., human annotations)? If results degrade, does this indicate over-reliance on SUPERFILTER?\n\nCould semantic diversity (e.g., BERT embeddings) complement or replace n-gram-based diversity?\n\nDoes the method exacerbate biases in the original dataset (e.g., underrepresented topics)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sMhupPk6Om", "reviewer": "Reviewer_ipfn", "summary": "The paper presents GraphFilter, a data selection approach designed to balance quality and diversity in SFT for LLMs. The key contribution is formulating data selection as a set cover problem and leveraging a bipartite graph structure where sentences are connected to their constituent n-grams. The priority function, which multiplicatively combines quality and diversity scores, guides the iterative selection of high-quality and diverse sentences. The method is evaluated across three model backbones and six benchmarks, outperforming nine baselines in both model performance and computational efficiency. Extensive experiments and ablation studies justify the design choices, highlighting the effectiveness of instruction diversity and the interplay between quality and diversity across different subset sizes.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful feedback of GraphFilter. We address your comments and questions below.\n\n## 1. Additional Diversity-Based Methods\n\nWe appreciate the reviewer's suggestion to explore additional clustering-based approaches for diversity. Following this recommendation, we conducted supplementary experiments comparing GraphFilter against hierarchical and spectral clustering baselines. For a fair comparison, we implemented these methods using the same procedure as our KMEANS baseline: we embedded instructions using BAAI/bge-large-en-v1.5 (https://huggingface.co/BAAI/bge-large-en-v1.5), clustered them into 10K clusters, and randomly selected one example from each cluster. The results in the table below demonstrate that GraphFilter consistently outperforms all clustering-based methods, including hierarchical and spectral clustering, across all evaluation metrics ($\\mu_{BENCH}$, $\\mu_{LLM}$, and $\\mu_{ALL}$). This further validates the effectiveness of our bipartite graph approach in capturing both quality and diversity compared to traditional clustering techniques.\n\n|                         | $\\mu_{BENCH}$ | $\\mu_{LLM}$ | $\\mu_{ALL}$ |\n|-------------------------|---------------|-------------|-------------|\n| KMEANS                  | 48.90         | 41.72       | 46.51       |\n| InsTag                  | 49.93         | 41.72       | 47.19       |\n| Hierarchical Clustering | 49.44         | 41.55       | 47.01       |\n| Spectral Clustering     | 49.68         | 42.03       | 47.12       |\n| GraphFilter             | 50.55         | 42.79       | 47.97       |\n\n## 2. Using MTLD and SkyworkRM as Direct Optimization Objectives\n\nThank you for this insightful question. We conducted additional experiments using MTLD and SkyworkRM as direct optimization objectives within our GraphFilter framework. To implement this approach, we replaced our original quality and diversity metrics with these measures: SkyworkRM scores were used to initialize the quality score (u) for each example, while MTLD scores served as the diversity measure (v). During the iterative selection process, we maintained the bipartite graph structure but updated the MTLD scores after each selection as n-gram nodes were removed. The results below show that our current formulation with SuperFilter for quality and TF-IDF for diversity provides a more effective optimization strategy than directly using the SkyworkRM and MTLD metrics. Furthermore, we would like to highlight that our approach is flexible and can easily incorporate other quality and diversity metrics as direct optimization objectives, when new state-of-the-art metrics become available.\n\n| Quality(u)  | Diversity(v) | $\\mu_{BENCH}$ | $\\mu_{LLM}$ | $\\mu_{ALL}$ |\n|-------------|--------------|---------------|-------------|-------------|\n| SuperFilter | TF-IDF       | 50.55         | 42.79       | 47.97       |\n| SuperFilter | MTLD         | 50.15         | 42.42       | 47.47       |\n| SkyworkRM   | MTLD         | 49.51         | 42.01       | 46.93       |", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes:\nThe bipartite graph representation of data is intuitive and allows for effective tracking of n-gram coverage.", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Baseline selection is reasonable, but additional diversity-based methods could be explored.\n\nWhile INSTAG and KMEANS are reasonable diversity baselines, clustering-based approaches (e.g., hierarchical clustering or spectral clustering) could provide more granularity.", "relation_to_broader_scientific_literature": "Closely related, with enough novelty.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "The writing is well and easy to follow.", "other_comments_or_suggestions": "NA", "questions_for_authors": "I would like to know whether using the coordinates of this figure (MTLD, SKYWORKRM) as direct optimization objectives would lead to better results.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "NA"}}, {"review_id": "GfWcHnk93Y", "reviewer": "Reviewer_mKJ5", "summary": "This paper proposes a novel method for selection SFT data for LLM fine-tuning. The proposed GraphFilter method pairs each instruction in the SFT dataset with a corresponding set of n-grams. It then assigns a priority rank to each example using a priority function that takes into account both quality and diversity of the sample (this assignment is re-done after each sampling step). Examples with highest priority are sampled first in the proposed algorithm. After selecting an example proposed algorithm removes the all the edges that go into the n-grams connected to the selected examples insuring that each n-gram is only encountered in a single samples example.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive feedback and thoughtful comments. Below, we address the specific points raised:\n## 1. Quality Metric\nWe are sorry about the confusion caused by this description. Equation 2 essentially measures the difficulty of the example, as suggested by [1, 2]. The correct interpretation should be: \"A higher value indicates greater difficulty, thus reflecting higher quality.\" As demonstrated by recent study, LLMs can achieve better performance by focusing on more challenging examples [3]. We will revise the manuscript to clarify this point.\n\nReferences:\n\n1. From quantity to quality: Boosting llm performance with self-guided data selection for instruction tuning. 2023.\n2. Superfiltering: Weak-to-strong data filtering for fast instruction-tuning. 2024.\n3. Wizardlm: Empowering large language models to follow complex instructions. 2023.\n## 2. Broader Scientific Literature\nWe appreciate your suggestions regarding related work. In the revised version, we will expand our discussion to better contextualize our work within the broader literature, as you suggested.\n## 3. Budget Selection\n**Our decision to use k=10K as the primary budget size was informed by established works in the field.** Specifically, this choice aligns with recent data selection methods that have demonstrated strong performance using similar budget sizes. For instance, SuperFiltering [1] utilized 7.8K examples from a pool of 52K, AlpaGasus [2] employed 9K examples from 52K, and DEITA [3] selected 10K examples from a total of 300K. By adopting a budget size of 10K, we ensure a fair and meaningful comparison with these baselines.\n\nFurthermore, we conducted extensive experiments across multiple budget sizes (1K, 5K, 10K, 50K, 100K, and 200K) as shown in Figure 3. These results demonstrate that the quality-focused data selection method has an advantage when the budget is small, while the diversity-focused method performs better with larger budgets. Our approach consistently outperforms the baseline methods across all budget sizes, demonstrating its robustness and effectiveness. We will include these additional details in the revised manuscript.\n\nReferences:\n\n1. Superfiltering: Weak-to-strong data filtering for fast instruction-tuning. 2024.\n2. Alpagasus: Training a better alpaca with fewer data. 2023.\n3. What makes good data for alignment? a comprehensive study of automatic data selection in instruction tuning. 2023.\n## 4. Data Diversity Concern\nWe acknowledge that this could lead to a loss of diversity in the training data, as the same n-grams may represent different concepts in different contexts. However, we believe this is not a significant issue for our method. **As shown in Figures 2a and 2c, the GraphFilter demonstrates significantly higher lexical diversity compared to all the baselines and is as semantically diverse as diversity-focused methods (e.g., InsTag).** Furthermore, we would like to clarify that when an n-gram node is removed from the bipartite graph, we lower the rankings of the corresponding examples rather than completely removing them from the training set. This approach allows the model to continue learning from these examples, albeit with lower weights. Additionally, there are two possible ways to mitigate this potential issue. First, we can use a larger n-gram size so that shorter n-grams are less likely to be completely removed. Second, we can allow for multiple visits to the same n-gram during the data selection process. \n\nRegarding the pre-training stage, we agree with your concern about the potential loss of diversity if the n-gram size is too small. In our preliminary experiments, we found that using n-grams of size 3 is sufficient in the context of SFT. However, larger n-grams may be necessary for pre-training. We will include these discussions in the revised manuscript.\n\n## 5. Influence Functions for Data Selection\n\nThank you for your suggestion to explore the use of influence functions for data selection. We agree that this is an interesting direction for future research and that this approach could be included as one of the baseline methods. Unfortunately, we are unable to include this method in our rebuttal due to constraints on computational resources and time, as influence-function-based methods typically require fine-tuning the model on the entire dataset first and then computing the Hessian of the loss function for each example. Compared to influence-function-based methods and other baseline approaches, our method is significantly more efficient and scalable, as shown in Table 2, making it suitable for real-world applications with large amounts of data. Furthermore, the subset selected by influence functions is model-dependent and may not generalize well to other models. We will discuss this potential extension in the revised manuscript.", "claims_and_evidence": "Most of the claims are supported by experimental results.", "methods_and_evaluation_criteria": "Yes, the selected methods and benchmark make sense for the data selection/ranking problem tackled in this paper.", "theoretical_claims": "Quality Metric:\n- Eq. 2 seem to contradict the sentence \"A higher SUPERFILTER value indicates that the response is more relevant and informative given the instruction, thus reflecting higher quality\", i.e. lower PPL(y|x) indicates that the response (y) is more relevant and informative given the instruction (x), but since PPL(y|x) is in the nominator of the equation it would also mean that lower PPL(y|x) would result in lower QUALITY(u) (SUPERFILTER) metric and not higher as stated but he authors.\n\nThe rest of the theoretical statements seem to be correct.", "experimental_designs_or_analyses": "I could not find major issues.", "relation_to_broader_scientific_literature": "While the number of recent works proposing and investigating data curation methods is vast, the related literature could do a better job discussing how the this work relates to the broader set of works in this are. For example, the n-gram overlap has been used in prior data selection methods by Xie et al., the interplay between diversity and quality has been looked at in several recent works including Goyal et. al, Chi et al., and Chang et al..\n\nXie, Sang Michael, et al. \"Data selection for language models via importance resampling.\" Advances in Neural Information Processing Systems 36 (2023): 34201-34227.\n\nGoyal, Sachin, et al. \"Scaling Laws for Data Filtering--Data Curation cannot be Compute Agnostic.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2024.\n\nChang, Ernie, et al. \"Scaling Parameter-Constrained Language Models with Quality Data.\" arXiv preprint arXiv:2410.03083 (2024).\n\nZhang, Chi, et al. \"Harnessing Diversity for Important Data Selection in Pretraining Large Language Models.\" arXiv preprint arXiv:2409.16986 (2024).", "essential_references_not_discussed": "While I don't thinks there are missing works that are essential to understand the context, I think the relation to other existing works in this domain could be discussed in greater length and detail (see \"Relation To Broader Scientific Literature\").", "other_strengths_and_weaknesses": "Strengths:\n- novelty: to the best of my knowledge the presented formulation of the data selection problem is novel;\n- seemingly strong empirical performance\n- the fact that the proposed method  falls within the lower range of runtime among the evaluated approaches is a strength;\n\nWeaknesses:\n- missing justification for the decision of using the budget of k=10k examples for the main results presented;\n- see section \"Theoretical claims\" for a potential methodological issue;", "other_comments_or_suggestions": "If I understand it correctly, after selecting an example proposed algorithm removes the all the edges that go into the n-grams connected to the selected examples insuring that each n-gram is only encountered in a single sampled example. \n\nWouldn't this approach reduce data diversity rather than enhance it? More specifically, if different n-grams are only encountered in a single context, the model's ability to recall knowledge after training can be diminished as demonstrated by Allen-Zhu et al. (2023). While it may not be an issue for SFT (especially if the method in only applied to the instructions and not the responses) I wonder if this could be an issue if the method was applied to selection of data for pre-training.\n\nAllen-Zhu, Zeyuan, and Yuanzhi Li. \"Physics of language models: Part 3.1, knowledge storage and extraction.\" arXiv preprint arXiv:2309.14316 (2023).", "questions_for_authors": "- Did authors consider adding baselines that use influence functions for data selection? While this has not been used for SFT afaik, the advantage of these methods is that they make data selection directly dependent on the intrinsics (i.e. parameters & architecture) of the model for which the data is selected.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: GRAPHFILTER is a novel data selection method for supervised fine-tuning (SFT) of large language models, designed to balance data quality and diversity. It represents the dataset as a bipartite graph linking sentences to their constituent n-grams. It iteratively selects data points using a priority function that combines quality and diversity metrics, aiming for maximum n-gram coverage with high-quality examples. 

Reviewers generally agree on the merits of the proposed method, which introduces a novel and compelling approach to data selection, praised for its simplicity and unique formulation, possibly involving bipartite graphs. This method demonstrates strong empirical performance, achieving effective results across various benchmark datasets. A key advantage is its impressive computational efficiency, fast runtimes compared to alternatives, and lower hardware barriers. The majority of concerns have been addressed through the rebuttal, such that the experimental evaluation lacks rigor, or justifies key decisions like the data budget size, the method's scope and approach, relying on potentially superficial n-gram diversity metrics, and inadequately explores alternative quality assessments. However, we highly recommend that the authors incorporate this feedback and revisions into the next version of the paper.
Decision: Accept (poster)