The Best of Both Worlds: Bridging Quality and Diversity in Data Selection with Bipartite Graph

## Abstract

Abstract The performance of large language models (LLMs) in natural language processing (NLP) tasks is significantly influenced by the quality and diversity of data used for supervised fine-tuning (SFT). Current data selection methods often focus solely on quality or diversity, leading to underperforming models due to suboptimal training data. In this paper, we introduce GraphFilter , a novel method that represents the dataset as a bipartite graph, linking sentences to their constituent n-grams. This representation effectively captures the relationships between sentences and linguistic patterns, facilitating the selection of sentences that enhance n-gram diversity. To balance quality and diversity during selection, we propose a priority function that combines the quality metric with the diversity metric in a multiplicative manner. GraphFilter iteratively selects high-priority sentences, updates the bipartite graph by removing covered n-grams, and re-calculates priorities to reflect the evolving data landscape. We conduct extensive experiments using three model backbones across six widely used benchmarks. The results demonstrate that GraphFilter outperforms all nine baseline approaches, achieving superior model performance and computational efficiency. Our analyses validate the effectiveness of our design choices, examine the subsets selected by GraphFilter and other methods, highlight the importance of instruction diversity, and explore the role of quality and diversity in relation to subset sizes. GraphFilter establishes a new foundation for effective data selection strategies, encouraging further research in data selection for LLMs.

## 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 a variety of tasks (Ouyang et al., ; Sanh et al., ; OpenAI, ; Anil et al., ; Touvron et al., ; ; Anil et al., ; Mesnard et al., ; Yang et al., ). 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 inputs (Wang et al., ; Zhou et al., ), while diversity in the data allows the model to generalize across different contexts and topics (Abbas et al., ; Maharana et al., ). However, the vastness of available SFT data presents a challenge: selecting a subset of data that balances both quality and diversity to optimize model performance.

Recent methods for data selection often prioritize either quality or diversity, rarely achieving an optimal balance of both. Approaches that focus exclusively on quality may overlook the variety of language patterns necessary for effective generalization (Marion et al., ; Ankner et al., ). Conversely, methods emphasizing diversity might include lower-quality data, which could negatively impact model performance (Abbas et al., ; Lu et al., ). This focus can result in models that either overfit to specific data patterns or underperform due to the inclusion of irrelevant or poor-quality data. Hence, it is crucial to develop a data selection strategy that simultaneously maximizes both data quality and diversity for effective supervised fine-tuning.

Figure: Figure 1: GraphFilter.
Refer to caption: /html/2410.12458/assets/x1.png

In response to this challenge, we propose a novel method, GraphFilter, as shown in [Figure 1](#S1.F1), which models the dataset as a bipartite graph to capture the relationships between sentences and their constituent n-grams. In this model, sentences and n-grams are distinct sets of nodes, with edges indicating n-grams’ presence in sentences, providing a comprehensive overview of n-gram coverage. This structure allows us to prioritize sentences that contribute unique n-grams, enhancing the diversity of the selected subset. To ensure high-quality and diverse sentence selection, we use a priority function that evaluates sentences on these dimensions. For quality, we use the SuperFilter, a metric that measures the informativeness of a response by comparing its perplexity when conditioned on the instruction with its standalone perplexity, favoring more relevant responses. For diversity, we calculate Term Frequency-Inverse Document Frequency (TF-IDF) scores for n-grams within sentences. By summing the TF-IDF scores of all n-grams present in a sentence, we estimate the sentence’s contribution to covering significant and less frequent linguistic patterns in the dataset. The priority function combines these two measures multiplicatively, assigning higher priority to sentences that are both informative (high-quality) and contribute substantially to n-gram diversity. During the selection process, GraphFilter iteratively selects sentences with the highest priority scores, updates the bipartite graph by removing the covered n-grams, and re-calculates the priorities based on the modified graph.

To demonstrate the effectiveness of GraphFilter, we conducted extensive experiments, comparing GraphFilter against nine baseline approaches using three model backbones: Gemma-2-2b (Team et al., ), Mistral-7B-v0.3 (Jiang et al., ), and Llama-3-8B (Dubey et al., ). The evaluation was performed across six widely-used benchmarks: MMLU (Hendrycks et al., ), ARC (Clark et al., ), HellaSwag (Zellers et al., ), GSM8K (Cobbe et al., ), AlpacaEval-2.0 (Dubois et al., ), and MT-Bench (Zheng et al., ). Our empirical results indicate that GraphFilter significantly outperforms recent state-of-the-art baselines and achieves notably better computational efficiency. Specifically, in terms of overall performance, GraphFilter outperforms the baselines by up to $+2.37$ for Gemma-2-2b, $+3.02$ for Mistral-7B-v0.3, and $+3.38$ for Llama-3-8B, and is up to $61\times$ faster than these baselines without requiring GPUs for computation. Furthermore, we performed an in-depth analysis to validate the effectiveness of our design choices in GraphFilter, examine the characteristics of the selected subsets and the importance of instruction diversity, and investigate the significance of quality and diversity under various data scales.

In summary, the contributions of this work are threefold:

- •
We introduce a novel bipartite graph model for datasets, named GraphFilter, which effectively captures the complex relationships between sentences and n-grams. This model enables efficient data selection for supervised fine-tuning (see [Section 3.2](#S3.SS2)).
- •
We propose a priority function that seamlessly integrates quality and diversity metrics for re-ranking the data. This ensures that the selected data maximizes n-gram coverage while maintaining high quality (see [Section 3.3](#S3.SS3)).
- •
Through experiments, we demonstrate that our method, GraphFilter, surpasses existing data selection strategies, achieving significantly better computational efficiency (see [Section 4](#S4)). Additionally, 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](#S5)).

## 2 Related Work

#### Data Engineering for Large Language Models

The success of recent large language models (LLMs) largely relies on the data used during their training process (Zha et al., ). State-of-the-art LLMs are generally trained on vast corpora (OpenAI, ; Team et al., ; Dubey et al., ). A significant area of research focuses on curating high-quality corpora for pre-training these models (Raffel et al., ; Computer, ; Soldaini et al., ; Penedo et al., ). Furthermore, Wang et al. () demonstrate that LLMs are capable of synthesizing high-quality datasets for supervised fine-tuning, which leads to a surge of research on dataset synthesis (Xu et al., ; Li et al., ; Gunasekar et al., ; Ding et al., ; Cui et al., ; Wu et al., ; Chen et al., ; Xu et al., ). These research efforts facilitate the synthesis of large-scale datasets containing billions of tokens for various purposes, resulting in a significant demand for selecting valuable subsets.

#### Data Selection

Data selection strategies aim to identify the most informative data subsets for training or fine-tuning models by considering quality and diversity. Quality-focused approaches prioritize metrics like complexity, difficulty, or informativeness (Marion et al., ; Chen et al., ; Liu et al., ; Li et al., ; ), but may neglect the range of language patterns needed for generalization. Conversely, diversity-focused methods capture a broad spectrum of linguistic patterns and contexts, potentially incorporating lower-quality data that could impair model performance (Abbas et al., ; Lu et al., ).

#### 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.

## 3 Methodology

In this section, we first introduce the data selection problem for supervised fine-tuning in [Section 3.1](#S3.SS1). Subsequently, we describe the modeling of the dataset as a bipartite graph in [Section 3.2](#S3.SS2). Finally, we explain the re-ranking of the graph nodes using a priority function that integrates quality and diversity metrics during the data selection process in [Section 3.3](#S3.SS3).

### 3.1 Data Selection Problem

The data selection problem involves the challenge of identifying and selecting the most relevant and informative subset of supervised instances from a larger dataset to fine-tune large language models (LLMs). Formally, let $\mathcal{D}=\{(x_{i},y_{i})\}_{i=1}^{N}$ be the supervised fine-tuning (SFT) dataset, where $x_{i}$ represents the instruction and $y_{i}$ its corresponding response for the $i$-th training instance. Our aim is to select a subset $\mathcal{S}_{\pi}$ of size $k$ from $\mathcal{D}$, utilizing the data selection strategy $\pi$, where $k$ is the data selection budget. The objective is to determine the optimal data selection strategy $\pi^{*}$ that is capable of selecting a subset $\mathcal{S}_{\pi}$ maximizing the performance of the fine-tuned LLM $f_{\theta}$ on the downstream tasks $\mathcal{D}_{\text{tst}}$. Therefore, the data selection problem can be formally formulated as:

$$ $\displaystyle\pi^{*}=\operatorname*{arg\,max}_{\pi}\,\mathcal{R}\left(f_{\theta};\mathcal{D}_{\text{tst}}\right)\text{, subject to }|\mathcal{S}_{\pi}|=k\text{, where }\theta=\text{FineTune}(\mathcal{F},\mathcal{S}_{\pi}),$ (1) $$

where $\mathcal{S}_{\pi}$ is the subset of the training data selected by the strategy $\pi$, $\theta=\text{FineTune}(\mathcal{F},\mathcal{S}_{\pi})$ denotes the parameters of the model backbone $\mathcal{F}$ after fine-tuning on the selected data subset $\mathcal{S}_{\pi}$, $f_{\theta}$ is the fine-tuned model with parameters $\theta$, and $\mathcal{R}\left(f_{\theta};\mathcal{D}_{\text{tst}}\right)$ is the performance metric (e.g., accuracy) of the fine-tuned model $f_{\theta}$ evaluated on the downstream tasks $\mathcal{D}_{\text{tst}}$.

Figure: Algorithm 1 GraphFilter

### 3.2 GraphFilter : Modeling Datasets as Bipartite Graphs

In our approach, we model the dataset as a bipartite graph to effectively represent the relationships between sentences and their constituent n-grams. A bipartite graph is a special type of graph whose vertices can be divided into two disjoint and independent sets such that every edge connects a vertex from one set to a vertex from the other set. Formally, a bipartite graph $\mathcal{G}=(\mathcal{U},\mathcal{V},\mathcal{E})$ consists of sentence nodes ($\mathcal{U}=\{u_{i}\}^{N}_{i=1}$), n-gram nodes ($\mathcal{V}=\{v_{j}\}^{M}_{j=1}$), and edges ($\mathcal{E}\subseteq\mathcal{U}\times\mathcal{V}$). This structure allows us to capture the occurrence of n-grams within sentences, providing a foundation for selecting sentences that maximize n-gram coverage while adhering to specific priorities. We introduce the details of the priority for re-ranking the sentences in [Section 3.3](#S3.SS3).

Our objective is to select a subset of sentences, denoted as $\mathcal{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 $\phi(u)$ for each sentence $u\in\mathcal{U}$. As illustrated in [Algorithm 1](#algorithm1), our method, referred to as GraphFilter, operates iteratively by updating the graph structure to reflect the n-gram coverage as sentences are selected. The process begins with an empty set of selected sentences, $\mathcal{S}=\emptyset$, and a bipartite graph $\mathcal{G}$ that includes sentence nodes, n-gram nodes, and connecting edges. In each iteration, we select the sentence $u^{*}\in\mathcal{U}$ that has the highest priority score $\phi(u^{*})$, add $u^{*}$ to $\mathcal{S}$, and then remove $u^{*}$ from the set of remaining sentences $\mathcal{U}$. Next, we identify the n-grams covered by $u^{*}$, denoted as $\mathcal{V}_{u^{*}}$. We then remove all edges that connect $u^{*}$ to the n-gram nodes in $\mathcal{V}_{u^{*}}$. Subsequently, $\mathcal{V}_{u^{*}}$ and all edges between its n-grams and other sentences are eliminated from the graph. Note that the priority of each sentence $u\in\mathcal{U}$ is computed based on the most recent graph $\mathcal{G}$ during each iteration.

Moreover, we present a minimalist example in [Figure 2](#S3.F2). Initially, the bipartite graph is displayed in [2(a)](#S3.F2.sf1). In [2(b)](#S3.F2.sf2), the sentence node $u_{1}$ is selected as $u^{*}$ and is highlighted in yellow, along with its associated n-gram nodes, $\mathcal{V}_{u^{1}}$, which are highlighted in red. [2(c)](#S3.F2.sf3) demonstrates the removal of edges connected to $u_{1}$ and $\mathcal{V}_{u^{1}}$, as indicated by dashed lines. Finally, [2(d)](#S3.F2.sf4) illustrates the removal of isolated nodes, shown in white. The next selected sentence node is $u_{4}$. In this example, GraphFilter can cover all the n-grams by selecting only $u_{1}$ and $u_{4}$.

Our problem formulation is related to the classical set cover NP-hard problem (Garey & Johnson, ). In the set cover problem, given a universe of elements and a collection of sets whose union comprises the universe, the objective is to identify the smallest number of sets whose union still contains all elements in the universe. Similarly, in a special case of our problem where the priority function assigns the same score to all sentences (i.e., $\phi(u)=1$ for all $u\in\mathcal{U}$), 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 1](#algorithm1) can be shown to have an approximation factor of $H(r)$ (Vazirani, ), where $r$ is the maximum degree of the sentence nodes in the graph (the largest number of n-grams contained in any sentence), and $H(r)=\sum_{k=1}^{r}\frac{1}{k}$ 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.

By modeling the dataset as a bipartite graph and employing an iterative selection algorithm, GraphFilter effectively selects a subset of sentences that maximizes n-gram coverage while adhering to specified priorities. Each SFT training instance comprises instructions and responses. In this work, we apply GraphFilter solely to the instructions of the SFT data.

Figure: (a) Initial Graph

#### Implementation

In a brute-force implementation, the computational complexity of our algorithm is $\mathcal{O}(N)$ per iteration. This complexity results from the need to perform operations such as selecting the highest-priority sentence and removing edges, which involve scanning the sets of sentences ($\mathcal{U}$), n-grams ($\mathcal{V}$), and edges ($\mathcal{E}$). These sets are not optimized for efficient access or modification. To enhance computational efficiency, we employ a max-heap (or priority queue) to select the highest-priority sentence, allowing this selection to be performed in $\mathcal{O}(\log N)$ time per iteration. This reduces the selection complexity from $\mathcal{O}(N)$ to $\mathcal{O}(\log N)$. Additionally, the max-heap data structure facilitates the localization of priority updates to affected nodes, eliminating the need to enumerate all nodes and edges.

### 3.3 Balancing Quality and Diversity with Priority Function

As illustrated in [Algorithm 1](#algorithm1), GraphFilter naturally selects a 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 define a priority function $\phi(u)$ for each sentence node $u\in\mathcal{U}$, which is used to re-rank the sentence nodes during selection.

#### SuperFilter for Quality

For quality, we employ the SuperFilter as the quality measure (Li et al., ; ). The SuperFilter metric evaluates the informativeness of a 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 instruction-response pair $(x,y)$, the quality priority metric is defined as:

$$ $\displaystyle\textsc{Quality}(u)$ $\displaystyle=\textsc{SuperFilter}(x,y)=\frac{\textsc{ppl}(y\mid x)}{\textsc{ppl}(y)},$ (2) $\displaystyle\text{where }\textsc{ppl}({\bm{w}})$ $\displaystyle=\exp\left(-\frac{1}{T}\sum_{t=1}^{T}\log P(w_{t}\mid{\bm{w}}_{<t})\right),$ $$

where $\textsc{ppl}({\bm{w}})$ is the perplexity of the sentence ${\bm{w}}$ with a length of $T$, $\textsc{ppl}(y)$ is the perplexity of the response $y$, and $\textsc{ppl}(y\mid x)$ is the perplexity of the response $y$ conditioned on the instruction $x$. A 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 quality metrics, such as SuperFilter, can be pre-computed prior to the selection process.

#### TF-IDF for Diversity

For diversity, we use the Term Frequency-Inverse Document Frequency (TF-IDF) as a measure of the significance of each n-gram within the dataset. The TF-IDF score of an n-gram $v$ is calculated as $\textsc{TF-IDF}(v)=\textsc{TF}(v)\times\textsc{IDF}(v)$, where $\textsc{TF}(v)$ (Term Frequency) is the number of times n-gram $v$ appears in the corpus, and $\textsc{IDF}(v)$ (Inverse Document Frequency) is defined as $\textsc{IDF}(v)=\log\left(\frac{N}{d_{v}}\right)$, with $N$ being the total number of sentences in the corpus, and $d_{v}$ being the number of sentences containing n-gram $v$. Furthermore, we compute the sum of TF-IDF scores of all n-grams (of varying lengths) present in the sentence:

$$ $\textsc{Diversity}(u)=\sum_{v\in\mathcal{V}_{u}}\textsc{TF-IDF}(v),$ (3) $$

where $\mathcal{V}_{u}$ is the set of n-grams connected to sentence $u$ in the graph $\mathcal{G}$. In our work, $\mathcal{V}_{u}$ includes unigrams ($n=1$), bigrams ($n=2$), and trigrams ($n=3$) present in sentence $u$, capturing both word-level and phrase-level features.

#### Combined Priority Function

To effectively prioritize sentences based on both quality and diversity, we combine the Quality score and the Diversity score for the sentence node $u$ into a single priority function:

$$ $\phi(u)=\textsc{Quality}(u)\times\textsc{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 that not only covers a wide range of linguistic patterns but also maintains a high standard of data quality.

## 4 Experiments

In this section, we initially outline our experimental setup in [Section 4.1](#S4.SS1), followed by a presentation of our main results in [Section 4.2](#S4.SS2).

### 4.1 Experimental Setup

#### Training Dataset

Xu et al. () utilize state-of-the-art open-source large language models (LLMs) to create a high-quality dataset collection known as Magpie. In our research, we employ the Magpie dataset, which is generated by Llama-3-70B-Instruct and comprises 300K training instances.(^1^11[https://huggingface.co/datasets/Magpie-Align/Magpie-Pro-300K-Filtered](https://huggingface.co/datasets/Magpie-Align/Magpie-Pro-300K-Filtered)) For this study, we choose a subset of 10K training instances using various selection methods from the entire dataset, unless otherwise stated.

#### Baselines

We compare our approach, GraphFilter, with a diverse array of baseline methods:

- •
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) ArmoRM is the state-of-the-art open-sourced reward model presented by Wang et al. ();(^2^22[https://huggingface.co/RLHFlow/ArmoRM-Llama3-8B-v0.1](https://huggingface.co/RLHFlow/ArmoRM-Llama3-8B-v0.1)) (5) AlpaGasus demonstrates that state-of-the-art LLMs can be directly prompted for estimating data quality (Chen et al., ); (6) Deita leverages ChatGPT to synthesize a quality estimation dataset and fine-tune LLMs for data quality estimation (Liu et al., ); (7) SuperFilter indicates the Instruction-Following Difficulty (IFD) metric computed by smaller language models. Li et al. () introduce this method, while Li et al. () demonstrate that IFD scores from smaller models are as accurate as those from larger models;
- •
Diversity-based: (8) Kmeans clusters the training instances with the state-of-the-art sentence embedding model and selects the training instances that are closest to their respective cluster centroids (Arthur & Vassilvitskii, ); (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., ).

We present more details of these baseline approaches in [Section A.1](#A1.SS1). To demonstrate the effectiveness and generality of GraphFilter, we conduct experiments on three diverse model backbones, including Gemma-2-2b (Team et al., ),(^3^33[https://huggingface.co/google/gemma-2-2b](https://huggingface.co/google/gemma-2-2b)) Mistral-7B-v0.3 (Jiang et al., ),(^4^44[https://huggingface.co/mistralai/Mistral-7B-v0.3](https://huggingface.co/mistralai/Mistral-7B-v0.3)) and Llama-3-8B (Dubey et al., ).(^5^55[https://huggingface.co/meta-llama/Meta-Llama-3-8B](https://huggingface.co/meta-llama/Meta-Llama-3-8B)) The optimization details are in [Section A.2](#A1.SS2).

**Table 1: Main results given by Gemma-2-2b, Mistral-7B-v0.3, and Llama-3-8B on the standardized benchmarks and LLM-as-a-Judge benchmarks. The datasets HS, G8K, and AE-2 correspond to HellaSwag, GSM8K, and AlpacaEval-2.0, respectively. The best results are highlighted in bold, and the second-best results are highlighted in underline.**
|  | Standardized | LLM-as-a-Judge | $\mu_{\textsc{all}}$ |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | MMLU | ARC | HS | G8K | $\mu_{\textsc{bench}}$ | AE-2 | MT-Bench | $\mu_{\textsc{llm}}$ |  |  |  |  |
|  | Acc | Acc | Acc | Acc | LC | WR | $\mu_{\textsc{mt}}$ | 1st | 2nd |  |  |  |
| Gemma-2-2b |  |  |  |  |  |  |  |  |  |  |  |  |
| Random | 25.25 | 47.52 | 58.27 | 09.10 | 35.03 | 10.77 | 13.73 | 4.73 | 5.44 | 4.01 | 29.01 | 33.03 |
| Longest | 25.50 | 47.06 | 56.43 | 08.79 | 34.45 | 10.40 | 13.10 | 4.79 | 5.54 | 4.05 | 29.17 | 32.69 |
| Perplexity | 23.34 | 47.58 | 59.04 | 06.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 | 09.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 | 09.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 | 09.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 | 04.62 | 39.25 | 13.60 | 16.18 | 4.98 | 6.01 | 3.95 | 31.70 | 36.73 |
| ArmoRM | 28.84 | 50.85 | 68.85 | 09.63 | 39.54 | 15.56 | 18.89 | 5.13 | 5.93 | 4.34 | 33.43 | 37.51 |
| AlpaGasus | 28.67 | 51.92 | 68.61 | 09.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 | 09.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-3-8B |  |  |  |  |  |  |  |  |  |  |  |  |
| Random | 49.55 | 52.00 | 67.30 | 22.14 | 47.75 | 22.17 | 25.05 | 5.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 |

#### Evaluation

We conduct evaluations on six popular benchmarks, categorized into two groups:

- •
Standardized: We assess the LLMs using Lm-Evaluation-Harness (Gao et al., ) on four standardized benchmarks: MMLU (Hendrycks et al., ), ARC (Clark et al., ), HellaSwag (Zellers et al., ), and GSM8K (Cobbe et al., ). 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 $\mu_{\textsc{bench}}$.
- •
LLM-as-a-Judge: We evaluate LLMs using two benchmarks: AlpacaEval-2.0 (Dubois et al., ) and MT-Bench (Zheng et al., ), with gpt-4o-2024-05-13 as the judge. For AlpacaEval-2.0, gpt-4-1106-preview 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 $\mu_{\textsc{mt}}$, the macro-average across all categories. Overall performance of this group, $\mu_{\textsc{llm}}$, is the macro-average of LC and $\mu_{\textsc{mt}}$.

We define overall model performance, $\mu_{\textsc{all}}$, as the macro-average of results from four standardized benchmarks, LC, and $\mu_{\textsc{mt}}$. In calculating $\mu_{\textsc{all}}$ and $\mu_{\textsc{llm}}$, $\mu_{\textsc{mt}}$ is scaled by $10\times$ to align with a range of 1 to 100, matching other benchmarks. Further evaluation details are in [Section A.3](#A1.SS3).

### 4.2 Main Results

#### GraphFilter surpasses all baseline approaches.

As shown in [Table 1](#S4.T1), GraphFilter consistently outperforms all baseline approaches across the three model backbones on both standardized benchmarks and LLM-as-a-Judge benchmarks. It achieves either the best or second-best results on most individual benchmarks. Specifically, in terms of $\mu_{\textsc{all}}$, GraphFilter outperforms the baselines by up to $+2.37$ for Gemma-2-2b, $+3.02$ for Mistral-7B-v0.3, and $+3.38$ for Llama-3-8B, compared to Longest. These results demonstrates the superiority of GraphFilter which effectively combines the quality and diversity in data selection.

**Table 2: Runtime (in hours) for data selection approaches when selecting 10K training instances. $\dagger$ indicate the CPU-only method.**
|  | Runtime (hrs) |
| --- | --- |
| Perplexity | 00.92 |
| ArmoRM | 05.93 |
| AlpaGasus | 32.34 |
| Deita | 22.65 |
| SuperFilter | 01.95 |
| Kmeans | 02.26 |
| InsTag | 25.48 |
| GraphFilter | 02.48 |
| w/o priority $\phi(u)$ | 00.53^$\dagger$ |

#### Quality-based 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 models display biases that can significantly affect downstream performance. As demonstrated in [Table 1](#S4.T1), models fine-tuned on subsets chosen by ArmoRM perform well on AlpacaEval-2.0 but poorly on other benchmarks. Furthermore, the Perplexity-selected subset consistently results in the worst performance on GSM8K, highlighting the risks of depending solely on neural models for selecting high-quality data.

#### GraphFilter is highly efficient, with its variant running quickly on a CPU.

Recent baselines typically rely on neural models for quality estimation, which generally require a GPU. We compare the runtimes of various baselines on a system equipped with an A100 80G GPU and 20 CPU cores, as shown in [Table 2](#S4.T2). As elaborated in [Section 3.3](#S3.SS3), GraphFilter defaults to using a quality estimation model for $\textsc{Quality}(u)$. When utilizing SuperFilter, GraphFilter completes its tasks in 2.48 hours, highlighting its efficiency. Notably, without using the priority function $\phi(u)$ for re-ranking, GraphFilter becomes even faster, taking only 0.53 hours on a CPU. This is up to $61\times$ faster than other baselines, compared to the 32.34 hours by AlpaGasus.

## 5 Analysis

In this section, we perform an ablation study for GraphFilter ([Section 5.1](#S5.SS1)), analyze the selected subsets ([Section 5.2](#S5.SS2)), highlight instruction diversity ([Section 5.3](#S5.SS3)), and examine the interplay between quality and diversity concerning subset sizes ([Section 5.4](#S5.SS4)).

### 5.1 Ablation Study

#### Combining n-grams captures features at different levels.

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 4](#S5.T4). Our observations 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.

**Table 3: Ablation study for n-gram combination of GraphFilter with Llama-3-8B. ✓ indicates that various n-grams are used.**
| N-gram | $\mu_{\textsc{bench}}$ | $\mu_{\textsc{llm}}$ | $\mu_{\textsc{all}}$ |  |  |
| --- | --- | --- | --- | --- | --- |
| Unigram | Bigram | Trigram |  |  |  |
| ✓ | ✓ | ✓ | 50.55 | 42.79 | 47.97 |
| ✓ |  |  | 49.02 | 41.41 | 46.48 |
|  | ✓ |  | 49.09 | 41.70 | 46.63 |
|  |  | ✓ | 49.84 | 41.78 | 47.15 |

#### Both Quality ​ ( u ) Quality 𝑢 \textsc{Quality}(u) and Diversity ​ ( u ) Diversity 𝑢 \textsc{Diversity}(u) in priority function enhance the data selection.

We provide empirical evidence in [Table 4](#S5.T4) showcasing the effectiveness of our proposed priority function. By incorporating the $\textsc{Quality}(u)$ metric (using SuperFilter) and the $\textsc{Diversity}(u)$ metric (using TF-IDF) into GraphFilter, we achieve superior performance across all evaluation metrics. This demonstrates that our combined priority function significantly enhances the model’s ability to select high-quality and diverse training data. Omitting either the quality metric (✗ + TF-IDF) or the diversity metric (SuperFilter + ✗) results in noticeable performance declines. Furthermore, replacing the SuperFilter metric with Perplexity as the quality measure leads to reduced performance, highlighting the importance of using optimal metrics. These findings support our decision to integrate quality and diversity in the priority function.

Figure: (a) Quality-Diversity relationship
Refer to caption: /html/2410.12458/assets/figures/tsne_vs_armorm.png

### 5.2 What Data Are Selected by GraphFilter ?

#### 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 3](#S5.F3). To confirm that GraphFilter maintains quality and diversity, we measure lexical diversity using the MTLD metric (McCarthy & Jarvis, ) and assess data quality with the advanced reward model, SkyworkRM (Liu & Zeng, ).(^6^66[https://huggingface.co/Skywork/Skywork-Reward-Llama-3.1-8B](https://huggingface.co/Skywork/Skywork-Reward-Llama-3.1-8B)) As depicted in [3(a)](#S5.F3.sf1), GraphFilter achieves the highest lexical diversity and ranks second in data quality. We also visualize GraphFilter instructions compared with ArmoRM and InsTag using the bge-large-en-v1.5 model.(^7^77[https://huggingface.co/BAAI/bge-large-en-v1.5](https://huggingface.co/BAAI/bge-large-en-v1.5)) It is evident that GraphFilter selects instructions not chosen by ArmoRM, shown by green rectangles in [3(b)](#S5.F3.sf2). Furthermore, [3(c)](#S5.F3.sf3) illustrates that GraphFilter and InsTag exhibit similar semantic diversity. These results suggest that GraphFilter not only selects high-quality data but also maximizes dataset diversity.

**Table 5: Applying GraphFilter to instructions and responses with Llama-3-8B. The ✓ indicates that GraphFilter is applied. Lexical diversity is measured by MTLD (McCarthy & Jarvis, ), and quality is assessed using ArmoRM, scaled by $100\times$.**
|  | Content Type | Benchmarks | Lexical Diversity | Quality |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | Inst. | Resp. | $\mu_{\textsc{bench}}$ | $\mu_{\textsc{llm}}$ | $\mu_{\textsc{all}}$ | Inst. | Resp. |  |
| GraphFilter | ✓ |  | 50.55 | 42.79 | 47.97 | 102.43 | 71.74 | 81.54 |
|  |  | ✓ | 47.16 | 39.71 | 44.68 | 090.22 | 73.57 | 81.52 |
|  | ✓ | ✓ | 48.03 | 41.20 | 45.76 | 090.13 | 72.60 | 81.52 |

### 5.3 The Diversity of Instruction and Response: Which Matters More?

#### Prioritizing instruction diversity most effectively improves model performance.

Each SFT training instance comprises an instruction and its response. This study evaluates the impact of applying GraphFilter to instructions, responses, or both on model performance. As shown in [Table 5](#S5.T5), applying GraphFilter only to instructions produces the best benchmark results, greatly improving lexical diversity in instructions with minimal effect on response diversity compared to other methods. Notably, all three variations maintain similar quality with different downstream outcomes, underscoring the importance of instruction diversity.

Figure: Figure 4: Performance gap ($\Delta_{\textrm{{all}}}$) with respect to $\mu_{\textsc{all}}$, comparing SuperFilter, InsTag, and GraphFilter against Random, across various data selection budgets.

### 5.4 Quality and Diversity: Which Should Be Prioritized?

After showcasing GraphFilter’s superiority in previous sections, an open question remains: When should diversity be prioritized over quality, and vice versa?

#### The priority of quality and diversity varies with data selection budgets, and GraphFilter excels at balancing these two factors effectively.

We hypothesize that the data selection budget plays a crucial role in determining the priority between quality and diversity and present the results in [Figure 4](#S5.F4). Our results indicate that the effectiveness of quality-based and diversity-based strategies is budget-dependent. Specifically, the quality-based SuperFilter excels with smaller budgets (1K and 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 SuperFilter 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 compared to Random across all budget levels. These findings show that the data selection budget influences the effectiveness of different approaches, and GraphFilter successfully integrates both quality and diversity.

## 6 Conclusion

In this work, we introduce GraphFilter, a 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 combines a quality metric with a diversity metric, allowing us to select subsets that enhance n-gram diversity and maintain high response quality. Our extensive experiments demonstrate GraphFilter’s effectiveness across three model backbones and six benchmark datasets. Compared to nine baseline methods, GraphFilter consistently delivers superior model performance and computational efficiency. Our analyses validate our design choices, assess the subsets chosen by GraphFilter and other methods, highlight the importance of instruction diversity, and examine the role of quality and diversity relative to subset sizes.

## 7 Ethics Statement

In this work, we present GraphFilter, a data selection method for supervised fine-tuning of large language models (LLMs). We acknowledge the ethical considerations related to data usage, potential biases, and the societal impact of LLMs. All datasets utilized in our experiments are publicly available and have been used extensively in prior research. We have adhered to all applicable licenses and terms of use for these datasets. However, we recognize that biases present in the training data can be propagated or even amplified by LLMs. To mitigate this risk, we recommend that practitioners applying GraphFilter conduct thorough analyses of the selected data subsets to identify and address potential biases. Furthermore, while our goal is to enhance model performance and computational efficiency, we are aware that improved models could be misused in ways that are harmful or unethical. We advocate for the responsible deployment of LLMs and encourage users to follow ethical guidelines and best practices to prevent misuse.

## 8 Reproducibility Statement

We are committed to ensuring the reproducibility of our results presented in this paper. To facilitate replication and verification by the research community, we provide comprehensive details of our proposed method, GraphFilter, in the main paper.

All hyperparameters, training configurations, and implementation specifics are thoroughly documented. For our experimental evaluations, we use publicly available datasets and benchmarks, namely MMLU (Hendrycks et al., ), ARC (Clark et al., ), HellaSwag (Zellers et al., ), GSM8K (Cobbe et al., ), AlpacaEval-2.0 (Dubois et al., ), and MT-Bench (Zheng et al., ). All experiments were conducted using standard computational resources without the need for specialized hardware. Details about the computational setup and resource requirements are outlined in this work. By ensuring that all components of our work are transparently documented and accessible, we aim to facilitate reproducibility and encourage further exploration of our method by the research community.

We will release the source code of GraphFilter and all scripts used for data selection, model training, and evaluation upon acceptance of this paper.

## Appendix A Experimental Setup

### A.1 Baselines

In this work, we compare GraphFilter against following baselines:

- •
Random selects a random subset of size $k$ from the entire dataset, where $k$ is the designated data selection budget.
- •
Longest chooses the top-$k$ instances from the entire dataset, ranking them in descending order based on the number of words in each instruction.
- •
Perplexity selects the top-$k$ instances from the entire 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., ).(^8^88[https://huggingface.co/openai-community/gpt2](https://huggingface.co/openai-community/gpt2))
- •
ArmoRM represents one of the state-of-the-art reward models (Wang et al., ). It evaluates multiple rewards from diverse perspectives and integrates these rewards using a gating network.
- •
AlpaGasus employs gpt-3.5-turbo to assess data quality (Chen et al., ). Given the improved model performance and limited budget, we substitute gemma-2-27b-it in this work, using the prompt illustrated in [Figure 5](#A1.F5). gemma-2-27b-it is the state-of-the-art open large language model (LLM) and significantly surpasses gpt-3.5-turbo according to the Chatbot Arena Leaderboard.(^9^99[https://huggingface.co/spaces/lmsys/chatbot-arena-leaderboard](https://huggingface.co/spaces/lmsys/chatbot-arena-leaderboard))
- •
Deita utilizes ChatGPT to create a quality estimation dataset and fine-tune large language models (LLMs) for evaluating data quality (Liu et al., ). We employ the official codes and models provided by Liu et al. () for data selection.(^10^1010[https://github.com/hkust-nlp/deita](https://github.com/hkust-nlp/deita))
- •
SuperFilter refers to the Instruction-Following Difficulty (IFD) metric, which is calculated using smaller language models. Introduced by Li et al. (), this method is shown by Li et al. () to provide IFD scores from smaller models that are as reliable as those from larger models. In this study, gpt2 is used for computing these scores (Radford et al., ).
- •
Kmeans involves clustering training instances using a state-of-the-art sentence embedding model and selecting instances that are nearest to their respective cluster centroids (Arthur & Vassilvitskii, ). In this work, we begin by sampling 50K instances from the entire dataset and encoding their instructions into sentence embeddings using the bge-large-en-v1.5 model.(^11^1111[https://huggingface.co/BAAI/bge-large-en-v1.5](https://huggingface.co/BAAI/bge-large-en-v1.5)) These embeddings are used for training the Kmeans model with 10K clusters. Once the Kmeans model is established, we cluster the sentence embeddings of instructions for the entire dataset and select the instances closest to each cluster centroid.
- •
InsTag is designed to analyze the SFT dataset by tagging the topics of training instances. It can be used to select a subset with the most diverse topics from the entire dataset (Lu et al., ). We utilize the official codes and models released by Lu et al. () for data selection.(^12^1212[https://github.com/OFA-Sys/InsTag](https://github.com/OFA-Sys/InsTag))

Figure: Figure 5: The prompt used for AlpaGasus annotation.

### 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\times 10^{-5}$, a warmup ratio of 0.05, and a linear learning rate schedule. All the experiments run for 3 epochs.

#### Computation Infrastructure

For this study, all methods are trained using two A100 80GB GPUs, which are interconnected via PCIe.

### A.3 Evaluation

In this work, we evaluate the approaches on six widely used benchmarks:

- •
MMLU (Hendrycks et al., ) is a benchmark designed to assess knowledge acquired during pretraining, by evaluating models exclusively in zero-shot and few-shot settings. It covers 57 subjects across STEM, the humanities, social sciences, and more, totaling approximately 14,000 test examples.
- •
ARC (Clark et al., ) is a 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., ) is a challenging dataset for evaluating commonsense natural language inference, which is particularly difficult for state-of-the-art models, though its questions are trivial for humans. It contains approximately 10,000 test examples.
- •
GSM8K (Cobbe et al., ) comprises a collection of diverse grade school math word problems created by human problem writers, containing approximately 1,000 test examples.
- •
AlpacaEval-2.0 (Dubois et al., ) is an automated tool for evaluating instruction-following language models. Its test set consists of 805 instructions generated by large language models (LLMs). Models are evaluated based on the winning rate against a reference answer, judged by a state-of-the-art LLM, such as gpt-4. AlpacaEval-2.0 is an upgraded version of the original AlpacaEval, featuring reduced length bias for a fairer evaluation of responses of varying lengths.
- •
MT-Bench (Zheng et al., ) is a multi-turn test set containing 80 questions that cover 8 aspects: writing, roleplay, reasoning, math, coding, extraction, STEM, and humanities. A state-of-the-art LLM, such as gpt-4, is used to score model outputs on a scale from 1 to 10.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 4
questions: * Related Work like DEITA considered three dimensions: complexity, quality and diversity. DEITA tries to maintain complexity and diversity while selecting high quality data first. It would be interesting to compare the in Section 5.2 to see the improvement of GraphFilter from DEITA’s data selection.


* It is interesting to see how the performance will change if the n-gram nodes can be visited multiple times, since different task or knowledge may need different amount of training data.


* It would be interesting if the paper can try to apply SOTA methods only on instructions and do some evaluation.
soundness: 3
strengths: * **Significance**: The paper targets an important problem in LLM SFT, which is how to select the training data.

* **Originality**: The paper proposes an efficient and effective method to select high quality and diversity data by designing a priority score and a bipartite graph representation for the dataset.

* **Clarity**: The paper adopts various datasets and baselines. The effectiveness of the proposed method is supported by comprehensive experiments and sound ablation study. 

* **Quality**: The paper is well-written. The presentation is clear and the graphs and tables are well-organised.
summary: The paper proposes a simple yet effective method named 'GraphFilter' to efficiently select SFT data with possible CPU-only computation. GraphFilter represents a dataset as a bipartite graph connecting sentences to their n-grams, allowing it to balance the quality and diversity sentences that maximise n-gram diversity. 

The paper also designs a priority function to combine quality and diversity in a multiplicative manner. The method iteratively selects high-priority sentences, updates the graph by removing covered n-grams, and recalculates priorities to adapt to the evolving dataset structure. 

Experiments across three model backbones and six benchmarks demonstrate that the proposed method outperforms nine baselines in both model performance and computational efficiency. Further analysis validates the method's effectiveness and highlights the importance of balancing instruction diversity with data quality for effective model fine-tuning.
weaknesses: * The Related Work for data selection could be enriched. The paper may explain more the limitations of the current methods and why it is important to address these limitations. In addition, methods like S2L [1] and DiverseEvol [2], although focusing on SFT a specific task, should also be added and discussed. Otherwise, the claim for solving SFT data selection problem should be narrowed down.


* The paper divides the existing methods into two categories:  quality-focused and diversity-focused. However, they always consider other different criteria or have different explanation of quality, for example, verbosity, complexity, and helpfulness to a specific task [3,4]. The paper should also discuss why the perplexity-based score is enough to capture the quality of the data.


* In the bipartite graph, the n-gram nodes are only visited once, and the edges and nodes are removed after being visited. It indeed accelerates the data selection process and enables the method to visit as many n-grams as possible given limited budget. However, the data needed to learn a certain knowledge or gain a certain capability may not be the same. The concern is that the model may not learn well on specific tasks, as supported that in the main results the method proposed does not perform the best in all tasks.


* In Section 5.3, the paper performs a comprehensive ablation study on applying GRAPHFILTER to instructions or responses. It is notable that SOTA methods like DEITA and ARMORM are applied both on instructions and responses, while the performance for the proposed method fails to outperform SOTA methods when applied to both instructions and responses. 


References:

[1] SMALLTOLARGE (S2L)- Scalable Data Selection for Fine-tuning Large Language Models by Summarizing Training Trajectories of Small Models, Yu et al., CoRR 2024.

[2] Self-Evolved Diverse Data Sampling for Efficient Instruction Tuning, Wu et al., CoRR 2023.

[3] What makes good data for alignment? A comprehensive study of automatic data selection in instruction tuning. Liu et al., ICLR 2024.

[4] Interpretable preferences via multi-objective reward modeling and mixture-of-experts. Wang et al., CoRR 2024.

---

confidence: 5
contribution: 3
initial_rating: 6
presentation: 3
questions: N/A
soundness: 3
strengths: Originality

The originality of GRAPHFILTER lies in its approach to data selection for supervised fine-tuning (SFT) of large language models (LLMs). Unlike prior methods that treat quality and diversity as separate concerns, GRAPHFILTER integrates both dimensions by representing the dataset as a bipartite graph connecting sentences and n-grams. This graph structure is a novel way to capture linguistic diversity at the n-gram level while the priority function effectively balances quality and diversity within the selection process. Using a bipartite graph to represent sentence-n-gram relationships is a creative approach, setting the paper apart from conventional selection techniques that use heuristics or embeddings alone. Additionally, including a priority function that combines quality metrics like SUPERFILTER with TF-IDF for diversity provides a unique, data-driven selection mechanism that ensures relevance and informativeness of the chosen data.

Quality

The quality of the research is high, demonstrated by a thorough methodology and comprehensive experimentation. The bipartite graph model and priority function are clearly defined and logically justified, and the selection process is detailed in both algorithmic form and example illustrations. The extensive experiments cover three different model architectures and six popular benchmarks, ensuring a broad and robust evaluation. Including nine baseline approaches provides a clear and rigorous comparison highlighting GRAPHFILTER’s advantages across multiple configurations. The authors further validate the effectiveness of their design choices through ablation studies, examining how different n-gram combinations and priority functions impact performance, which adds to the paper’s methodological robustness.

Clarity

The paper is well-organized and communicates complex ideas effectively. Each approach component—dataset representation, quality and diversity metrics, and the iterative selection process—is clearly explained with diagrams and examples illustrating the graph model and selection procedure. Definitions for quality and diversity metrics and the rationale for combining them are presented straightforwardly. Using an algorithmic breakdown and a visual example to show each iteration of GRAPHFILTER enhances clarity. The experimental results are also well-presented, with tables summarizing key findings and ablation studies that provide deeper insights into specific aspects of the approach.

Significance

GRAPHFILTER is significant because it offers a scalable, efficient solution to the data selection problem in LLM fine-tuning, a critical need given the vast datasets and resources involved in training. By balancing quality and diversity, GRAPHFILTER creates more representative and effective subsets, which can improve model generalization without requiring extensive computational resources. This can potentially enhance SFT for LLMs in domains where data quality and diversity are essential, such as multilingual NLP and domain-specific applications. Moreover, the method’s efficiency is demonstrated by its ability to run on CPUs while achieving faster runtimes than GPU-dependent baselines, making it accessible for more resource-constrained environments. The open-sourcing of GRAPHFILTER and its accompanying data selection scripts provides a valuable tool for future research in data-efficient model training.
summary: The paper presents GRAPHFILTER, a novel method for selecting high-quality and diverse subsets of data for supervised fine-tuning (SFT) of large language models (LLMs). The method represents the dataset as a bipartite graph, linking sentences to n-grams, allowing for an efficient selection process that enhances both quality and diversity. Key contributions include:

* Bipartite Graph Model: GRAPHFILTER models sentences and n-grams as nodes in a bipartite graph, capturing n-gram diversity and allowing for efficient sentence selection.
* Priority Function for Quality and Diversity: A priority function that combines quality (measured by SUPERFILTER) and diversity (via TF-IDF for n-grams) guides the sentence selection process, ensuring a balanced and high-value subset.
* Extensive Benchmarking: Experiments on three model backbones and six benchmarks show that GRAPHFILTER outperforms nine other data selection methods, achieving better model performance and computational efficiency.

The paper demonstrates the effectiveness of GRAPHFILTER, providing insights into the selected subsets' characteristics and highlighting the importance of instruction diversity for model training
weaknesses: 1. Limited Adaptability Beyond Current Quality Metrics
Weakness: The method relies heavily on the SUPERFILTER metric for quality assessment, which may limit its generalizability, particularly in domains or languages not well-represented by this metric. This reliance could be restrictive, especially when different quality indicators are needed based on the type of LLM or domain being fine-tuned.

Recommendation: To increase adaptability, the authors could explore alternative or domain-specific quality metrics that could be seamlessly integrated into the priority function. An experiment comparing SUPERFILTER with other quality metrics (e.g., perplexity or reward-based metrics tailored to specific tasks) would provide insights into GRAPHFILTER's flexibility. Alternatively, a modular design allowing users to plug in their quality metrics could make the method more versatile and applicable across diverse datasets.

2. Lack of Comprehensive Error Analysis in Data Selection
Weakness: The paper does not provide an in-depth error analysis to examine cases where GRAPHFILTER might underperform or select less useful data, especially when quality and diversity conflict. Such analysis would be valuable for understanding the method’s limitations and refining the priority function.

Recommendation: A targeted error analysis could categorize cases where selected data may not align well with model performance. For example, the authors could examine if lower-quality but diverse data instances significantly impact model outputs or if certain n-grams introduce noise. This analysis could also help fine-tune the priority function to better manage trade-offs between quality and diversity, potentially through a weighted approach that adjusts depending on the dataset characteristics.

3. Evaluation Limited to Standard Benchmarks and Missing Real-World Scenarios
Weakness: The evaluation is limited to standard benchmarks, which, while effective for baseline comparisons, may not fully capture the method’s utility in diverse or more practical real-world scenarios. Standardized datasets often lack the complexities of domain-specific data, such as legal, biomedical, or social media text, where quality and diversity requirements vary.

Recommendation: Extending the evaluation to real-world or specialized datasets would enhance the evidence for GRAPHFILTER’s broad applicability. A domain-specific test (e.g., using a biomedical or multilingual dataset) would provide insights into how GRAPHFILTER handles more nuanced data selection needs. Additionally, incorporating a diverse data type, such as conversational or low-resource languages, could demonstrate the method’s robustness across data complexities.

4. Minimal Analysis of Computational Efficiency Gains
Weakness: While the paper notes GRAPHFILTER’s computational efficiency, it lacks a detailed analysis of where and how these gains are achieved, particularly regarding graph updates and priority re-ranking. This could limit readers’ understanding of the method’s scalability and how well it would perform on substantially larger datasets.

Recommendation: Breaking down computational costs (e.g., time spent on graph updates vs. priority re-ranking) would clarify the efficiency gains and allow for targeted optimizations. Additionally, experimenting with larger dataset subsets or more frequent updates could provide a clearer picture of how GRAPHFILTER scales with data size. If feasible, comparing runtime and memory usage across different datasets would also offer valuable insights for practical applications.

5. Overemphasis on N-gram Diversity Without Fine-Grained Control
Weakness: The method’s focus on n-gram diversity may be limited if particular n-grams or patterns are less relevant to specific tasks. In some cases, emphasizing phrase-level or domain-specific terms could be more beneficial than broad n-gram diversity, but the current setup lacks control over such granular adjustments.

Recommendation: Incorporating a mechanism to adjust the weight or importance of specific n-gram levels or types would add flexibility. For instance, allowing users to prioritize specific n-gram frequencies or filtering by linguistic features such as named entities or domain-specific terms could enhance GRAPHFILTER’s relevance for task-specific fine-tuning. This could be tested with a small-scale experiment where the diversity weight is adjusted based on target domain characteristics, such as including only highly informative bigrams in biomedical data.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: Is there much variance in these results?  What about re-running multiple times in order to get error bars?

Why TFIDF and not just TF (as noted above)?  Or just giving every n-gram a score of 1.

Why Quality x Diversity?  What about Quality + Diversity?  Quality^2 * Diversity?  Quality * Log(Diversity)?  Quality^(10/log(N)) * Diversity, where N is the size of the subset.  You know what I mean?  There is some assumption underlying Quality x Diversity, and since it’s the central topic of the paper, it would be good to spell it out and test it.
soundness: 3
strengths: For the most part, the paper is clearly-written and well organized.  It’s relatively easy to understand what has been done, and, many of the things that were done are well-motivated and sound.  Figure 2 and Algorithm 1 add to the clarity.  The ablations are presented well in the Tables.  The main claim: that we need quality and diversity together to select a good dataset for supervised fine-tuning (SFT), is well-supported by the experiments.  It’s a fairly reasonable idea, and seems potentially beneficial to others doing supervised fine-tuning.
summary: This paper introduces a method to filter data for supervised fine-tuning of LLMs.  Given a budget of a certain number of instruction+response pairs on which to fine-tune, this paper proposes that we should prioritize selecting both high-quality instructions (assessed with some kind of quality metric) and diverse instructions (by selecting new unique n-grams).  Prior work has focused on either quality or diversity in isolation.  The approach is implemented using a data structure called GraphFilter, which links n-grams to the sentences that they occur in.  The algorithm proceeds in a greedy manner, selecting instructions that have the highest product of quality times diversity, and then removing all selected n-grams from future assessments of diversity (meaning instructions with those n-grams will now be weighted lower in the next iteration).  The proposed method is shown to improve over various baselines, and ablations show that using both the quality score and the diversity score together are better than using either in isolation.  Another interesting experiment shows that the value of quality is highest with smaller budgets, whereas with larger budgets, the importance of diversity grows.
weaknesses: The overall motivation for a SFT data budget is not perfectly motivated.  What controls the size of this budget?  Do we see diminishing/negligible returns as we FT over more and more data?  Could downstream accuracy actually suffer as we move to lower-quality data?  Or are we just limited by our own compute budgets for doing the supervised fine tuning?  It would have been useful to motivate this further in the paper, as the exact motivation can affect the reviewer evaluation of what experiments should have been run, etc.  Right now, it’s not clear whether filtering data generated by an LLM for SFT is as important as filtering data scraped from the web for pretraining.

I am confused about the use of TFIDF in this context.  Normally, TF is the term frequency *within a document*, and IDF is the inverse of the frequency of the term *across documents*.  It’s a good metric for finding keywords in a specific document because “important” terms are frequent in the given document, but less frequent across documents.  But here, TF seems to mean the *global* term frequency, while IDF represents the inverse frequency *across sentences*.  I struggled to think of examples where this is useful.  For many terms, I would expect them to occur at most once in each sentence, so it seems to me that TF and DF would be very similar for most terms, and thus the overall “diversity score” scales with x log(1/x), where x is the frequency of the term.  I do not expect this score to encourage diversity; indeed, I think diversity arises from removing the n-grams from consideration that have already been used in instructions – so on subsequent iterations, sentences containing previously-unseen n-grams will get higher scores.  It is not clear – and ablations do not test – if using what-is-called TFIDF provides a benefit over, say, counting each N-gram based purely on its frequency, or even giving each N-gram a score of 1.  Since both using “TFIDF”, and calling it that, seem incorrect to me, and this score is more complicated than other approaches, it’s hard for me to recommend using this algorithm to my colleagues working on supervised fine-tuning.  It’s hard to picture the paper being published with this issue.

I didn’t find Figure 1 that useful; it would be better if it illustrated how the algorithm works in a bit more detail.

Some of the claims were misleading or at least oversold.  For example, GraphFilter “captures the complex relationships between sentence and n-grams.”  From my perspective, it captures a single relationship, whether the sentence CONTAINS the n-gram… and that’s a fairly straightforward relationship.  Also, GraphFilter is “up to 61x faster than these baselines without requiring GPUs.”  But isn’t it just 61x faster than a SINGLE baseline (AlpaGasus)?  If we’re cherry-picking single baselines, how much faster is it than Random?  And isn’t it only 61x faster when not using the priority function for re-ranking?  And yet I don’t see where we report the accuracy when not using the priority function.  It’s not valid to claim it outperforms the baseline accuracy by x% and is 61x faster, when it seems these things are not JOINTLY true.  It would be like having an untested mode of GraphFilter that picks the shortest instructions and using this to justify a claim that GraphFilter is 500x faster than the baselines.  Besides, I don’t really understand what it means not to use ϕ(u), because as far as the paper says, ϕ(u) is how GraphFilter ranks sentences (Equation (4)).  Finally, the intro claims GraphFilter outperforms the baselines by “up to +2.37 for GEMMA-2-2B, +3.02 for MISTRAL-7B-V0.3, and +3.38 for LLAMA-3-8B” – but this is only over LONGEST, and that’s not even as good as RANDOM.  I am not sure the paper *intentionally* tried to mislead the reader, but after reading the introduction, the reader was *expecting* GraphFilter to beat a COMPETITIVE baseline by being BOTH 2-3% better AND 61x faster.

In terms of other ablations, since we see that unigrams to trigrams are important, it leads us to wonder, what about four-grams?  And five-grams?  Where does it level off?

I am also not sure how sound it is to report results applying GraphFilter to instructions only (and not responses).  Perhaps it would have been more fair to test each baseline being applied to either instructions only, responses only, or both, and then to report the best result across all three (assuming that was how the results were compiled for GraphFilter).

Small points (not affecting the scoring/evaluation of the paper):
- While Section 5.4 is great, you should remind everyone there are only 300K sentences in total so things will approach random (Δ_all will got to zero) as we increase the budget.
- Without using TFIDF nor SuperFilter, is it random?  So why is the result 45.61 in Table 4 and yet random gets 45.51 in the main Table 1?  Is that a typo?  Did you re-run it again?  Is it not random?

Meta-review: This paper proposes GraphFilter - a method for selecting high-quality and diverse data for supervised fine-tuning of LLMs. The key idea is to represent the dataset as a bipartite graph linking sentences to n-grams with a priority function that balances between quality and diversity metrics.

Strengths: The approach itself is well-motivated by considering quality and diversity through a graph-based representation. The evaluations are also comprehensive, with multiple models and benchmarks.

Weaknesses: The reviewers raised several issues including the limited exploration of alternative metrics, lack of analysis on the computational complexity and scalability etc.

This paper lies in the borderline from the reviews and also from the internal discussions. While it addresses an important problem and also shows competent performance, the technical contribution falls short of the bar of ICLR. The core approach largely combines existing techniques without substantial innovations, and may not bring too many new insights. Therefore, I'm inclined to reject this paper.

Decision: Reject