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

We thank the reviewer for their constructive feedback and thoughtful comments. Below, we address the specific points raised:

1. Quality Metric

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

References:

1. From quantity to quality: Boosting llm performance with self-guided data selection for instruction tuning. 2023.
2. Superfiltering: Weak-to-strong data filtering for fast instruction-tuning. 2024.
3. Wizardlm: Empowering large language models to follow complex instructions. 2023.

2. Broader Scientific Literature

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

3. Budget Selection

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.

Furthermore, 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.

References:

1. Superfiltering: Weak-to-strong data filtering for fast instruction-tuning. 2024.
2. Alpagasus: Training a better alpaca with fewer data. 2023.
3. What makes good data for alignment? a comprehensive study of automatic data selection in instruction tuning. 2023.

4. Data Diversity Concern

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

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

5. Influence Functions for Data Selection

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

We thank the reviewer for their thoughtful feedback of GraphFilter. We address your comments and questions below.

1. Additional Diversity-Based Methods

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

2. Using MTLD and SkyworkRM as Direct Optimization Objectives

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

We thank the reviewer for their thorough assessment.

1. Quality Metrics

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

2. N-gram

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.

5. N-gram Importance

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

3. Scalability Analysis

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

4. Semantic Diversity

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

Furthermore, 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.

5. Priority Function

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

6. Bias

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.

7. Miscellaneous

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

We sincerely appreciate your thoughtful review of our paper.

1. Diversity Approach

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

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

2. Reliance on SuperFilter

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

3. Priority Function

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

4. Instruction-only Application

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.

5. Small Dataset

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.

References:

1. Superfiltering: Weak-to-strong data filtering for fast instruction-tuning." 2024.
2. Alpagasus: Training a better alpaca with fewer data. 2023.
3. What makes good data for alignment? a comprehensive study of automatic data selection in instruction tuning. 2023.

6. Missing Literature

We will incorporate these references in our revised manuscript.

We sincerely appreciate your thoughtful review of our paper on GraphFilter.

1. Generalizability

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

2. Diversity Metrics

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.

3. Adaptability

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

4. Error Bars

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

5. Different Subset Sizes and Hyperparameters

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

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

6. Method Name

We will change the name to "GraphFilter" in the future version to improve readability.

7. Choice of Trigrams

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.

8. Hyperparameter Sensitivity

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