GREATS: Online Selection of High-Quality Data for LLM Training in Every Iteration
Authors: Jiachen T. Wang
Tong Wu
Dawn Song
Prateek Mittal
Ruoxi Jia
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Online Batch Selection
Large Language Model
Primary area: interpretability_and_explainability
TL;DR: We develop a principled and efficient online batch selection algorithm that is scalable to large language models.

Abstract: Online batch selection methods offer an adaptive alternative to static training data selection by dynamically selecting data batches during training. However, existing methods either rely on impractical reference models or simple heuristics that may not capture true data informativeness. To address these limitations, we propose \emph{GREedy Approximation Taylor Selection} (GREATS), a principled and efficient online batch selection method that applies greedy algorithm to optimize the data batch quality approximated by Taylor expansion. We develop a series of techniques to scale GREATS to large-scale model training. Extensive experiments with large language models (LLMs) demonstrate that GREATS significantly improves training convergence speed and generalization performance.

GREATS: Online Selection of High-Quality Data for LLM Training in Every Iteration
Jiachen T. Wang*
Tong Wu Princeton University
Princeton University
ti cianhaovvagggpiccctoo...om edu
tongsu@princeton. edu
Dawn Song UC Berkeley dawnsong@cs. berkeley.ede
Prateek Mittal
Ruoxi Jia" Virginia Tech
Princeton University pmi mmiitall@rinnetonn. edu
muoxijia@vt
Abstract
Online batch selection methods offer an adaptive alternative to static training data selection by dynamically selecting data batches during training. However, existing methods either rely impractical reference models simple heuristics that may not capture true data informativeness. To address these limitations, we propose GREedy Approximation Taylor Selection (GREATS), principled and efficient online batch selection method that applies greedy algorithm to optimize the data batch quality approximated by Taylor expansion. We develop series of techniques to scale GREATS to large-scale model training. Extensive experiments with large language models (LLMs) demonstrate that GREATS significantly improves training convergence speed and generalization performance. Our codebase is publically available htttt:::///// thub. cww www.oe/maaaen--eaaee T-Wang
1 Introduction
I Large language models (LLMs) are of paramount importance in today's technological landscape. However, the extensive training times, often spanning weeks or even months, pose challenges such as prolonged development cycles and increased resource consumption. Moreover, these models are trained on massive data collected from the open world, which can include low-quality, redundant, and biased information. This underscores the need for effective selection of high-value training data.
Online batch selection: adaptive variant of data selection at the batch level. Online batch selection methods aim to improve data selection by dynamically choosing data during the training process. At each training iteration, these methods leverage the partially trained model determine which data to select for the current training iteration from sampled batch, thereby adapting to the model's 's learning progress and focusing on the most informative examples for the model's 's current state. In contrast to static data selection methods (e.g., only once prior the training process, online batch selection allows for more adaptive and dynamic approach to data selection. By continuously updating the selection criteria based on the model's s progress, online batch selection can identify the most relevant and informative examples each stage of training, potentially leading to faster convergence and better generalization performance. Moreover, online batch selection operates on smaller batches of data, reducing the need for cumbersome data preprocessing and enabling more efficient of computational resources compared to static data selection methods that process the entire dataset upfront.
45 which select training data
"Conresoondence to Jiachen T. Wang and Ruoxi Jia.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

However, existing online batch selection algorithms exhibit significant limitations and have found minimal success with LLMs. Reference-model-eeee additional reference models. In [30], the reference models are trained on substantial amount of hold-out data. This leads to considerable computational costs and reduces the amount of data available for training the main model. (9] utilize publicly available large-scale pre-trained models that already achieve very high performance on the targeted downstream tasks as reference models. Even if this assumption holds true in practice, the algorithm requires a Bayesian treatment and querying the reference models for every sample in the candidate batch at each iteration. These operations are computationally expensive, making the approach impractical for large-scal LLM training. Reference- model-free methods prioritize challenging samples based on metrics like high loss [28] 20 or large gradient norm 23 While some of these methods are computationally efficient and practical to implement, they often rely on simple heuristics that may not capture the true informativeness or relevance of the examples. As result, these methods often fall short in terms of performance and may even underperform compared to simple uniform selection in some cases. This highlights the need for more efficient and principled online batch selection techniques that can identify the most informative examples based on a deeper understanding of the model's 's learning dynamics and the relationships between the examples.
batch selection methods [30 9 rely on
In this work, we propose GREedy Approximation Taylor Selection (GREATS). which addresses the limitations of existing methods and significantly improves the convergence speed and generalization performance of language model training. We summarize our contributions as follows.
I. Principled Formulation for Optimal Batch Selection. We introduce principled formulation of the online batch selection problem as a set utility function optimization task. Given a small set of validation data from the target domain, the utility function measures the reduction in loss achieved by updating the model with a selected subset of the training batch. Unlike previous methods that rely on heuristics, this framework aims to directly optimize the model's performance on the validation set, ensuring the selection of informative and diverse examples.
II. Efficient Approximations for Scalable Batch Selection. The set function optimization formula- tion naturally leads greedy algorithm that iteratively selects the most informative examples based on their marginal contribution to the model's 'ss performance. However, directly applying the greedy algorithm to optimize the validation performance involves updating model with each potential candi- date training point and checking the validation performance, which is computationally inefficient. To tackle this challenge, we propose to leverage Taylor expansions to approximate the variation of validation loss in one-step gradient descent. The key insight is that the impact of training example on the model's validation loss can be efficiently approximated using gradient inner-products between the training examples and the validation data. This approximation eliminates the need for expensive model updates and validation loss evaluations for each candidate subset.
III. Online Batch Selection at the Speed of Regular Training, A direct implementation of GREATS would require computing per-sample gradients, which is computationally expensive. To address this challenge, we develop novel technique called "ghost inner-product" that allows for the efficient computation of pairwise gradient inner-products without the need to instantiate any model-sized vectors. As gradient inner- menrr-prdduct arise in various machine learning algorithms and applications beyond data selection, this technique may be of independent interest.
IV. Comprehensive Evaluations. We conduct extensive experiments on various language modeling tasks to thoroughly assess the performance of GREATS. We show that GREATS consistently speeds up training convergence and improves generalization performance across different models, training datasets, and evaluation datasets, even with a limited number of validation points. Furthermore, we show that GREATS can provide benefits even in the pretraining setting, where the validation data comes from the same domain as the training dataset. This highlights the robustness and versatility of our approach in various learning scenarios. In addition to its performance benefits, we empirically confirm that GREATS, equipped with the "ghost mnner-product" technique, achieves a runtime comparable to regular training. This underscores the practical feasibility of our approach.
2 Related Works
Online Batch Selection. Few studies have investigated the use of online batch selection to enhance the training of models before the era of large language models. [28] 23 20 examined selecting the
2

---

"hard examples" based on their gradient norn or maximum sample loss. While some of these methods are computationally efficient, they often depend on simple heuristics that cannot represent the true informativeness. (30 p suggested using additional reference models to more accurately estimate the importance of samples. However, recently [2 demonstrated these methods are computationally expensive and cannot directly apply to large language models.
Static Data Selection for Large-scale Models. Recently, there has been a growing interest in design methods to select data before training foundation models. We point the readers to 2 for a comprehensive literature review. These works select training data only once, prior to the training process. This is primarily motivated by efficiency concern, as the time spent on data selection can be amortized over large number of training steps. However, the non-adaptive nature of this single-step selection often results in suboptimal performance, as the selected data may not be the most informative or diverse throughout the entire training process [4). Moreover, these algorithms often require extensive and complex data preprocessing steps. Some of the data selection algorithms even require training an additional model solely for the purpose of data selection 4 44, which introduces additional computational costs and implementation complexity to the training pipeline. These drawbacks emphasize the need for more efficient and adaptive data selection techniques that can dynamically identify the most informative and relevant examples throughout the training process.
Online Domain Reweighting. Recent work has explored online methods for dynamically re- weighting domains during language model pre-training. Compared with online batch selection, this approach operates coarser granularity by focusing on data source-level selection rather than individual examples, and typically updates domain weights less frequently. Similar to this work, 12 uses gradient-based influence estimation to update domain weights. 3 uses training loss as a reward signal to adapt domain sampling probabilities. This has been recently refined by [2]] through a scaling law-based method.
3 Backkround
In this section, we introduce the setup of online batch selection and the concept of utility function. We then discuss the limitations of existing scoring and top-k paradigm in the literature.
Set-up of online batch selection. Given a training dataset DDr = { a deep learning model is usually being trained to minimize the training loss Σi= f(w, 2;) via an iterative optimization procedure such stochastic gradient descent (SGD). Starting with an initial model wo. during an iteration I, a batch S of the training points is being used, and update the model parameters from we to w++1 via W(+1 == we ?) E.es Vε(w,, 2) where 77 is the learning rate at iteration t A complete run of neural network training thus consists of model checkpoints {wo, W1,-.. wT) ). In the setting of online batch selection, a large batch B, = {21,... ,,,) } is being sampled from the training set Drr at training iteration An online batch selection algorithm aims to select the most valuable subset B, from B. can be naturally formulated as an optimization problem, where the objective is to maximize the utility of the selected B, for model update. Here, we describe the existing online batch selection algorithms through the concept of a utility function.
Utility Function. At training iteration I, utility function U maps an input training data batch S to score indicating the utility of this batch for the model update at iteration (. Specifically, for given utility function U, the task of online batch selection over a candidate batch B, is to identify the subset B, S B, that optimizes:
B
argmaxx ((((S) SSB,,
(1)
where i is fixed budget of sample number ts |Br] used update the model. Since (1t) is set function, solving Equation (I) presents significant challenges, as it may require evaluating the utility (S) for a large number of subsets S S B, Existing online batch selection methods circumvent this issue through "Scoring and Top-k Paradigm" which compute an importance score Φ2 for each data point E B, and then selecting the subset of data points with the highest importance scores. For example, 28 20 use the individual loss on the training data point Φ= f(wr,,) 2) as the importance
'Here we incorporate the normalization term [S] into the learning rate ne for notational simplicity.
3

---

use the individual gradient norm o= = VV =)Il as the importance score. leverage reference model and use the "reducible loss" as the importance score. The use of importance scores for online batch selection essentially defines the utility function (S) Eies Φi (U) and conjectures that the sum of individual data points" importance scores is a reliable indicator of a dataset S"s utility, hoping for a positive correlation with the model w/ 's performance at the (t + 1) step after updating on S. Consequently, existing online batch selection strategies aim to maximize Lies (U) by selecting the top-k data points with the highest importance scores.
score. 23
30
Limitations of Scoring and Top-k Paradigm. Most scoring mechanisms for estimating the value of an individual data point = E B, result in similar data receiving similar scores. However, in the context of online batch selection, diversity is crucial. Consequently, a subset B, consisting of the iop-K valued data points may lack diversity. In particular, duplicate points might be scored equally high and be incorrectly assumed to doubly improve the model, though this is likely not the case. The primary issue with this top-K methodology is that it ignores the interactions among the selected data points. When a data point is selected, the importance scores of the remaining data points will usually change. For instance, the values of data points similar to the selected ones will typically decrease, while the values of data points that are very different from the selected ones will increase.
4 Optimizing Utility in Online Batch Selection via Greedy Algorithms
4.1 A Principled Utility Function for Online Batch Selection.
The performance of a model is typically measured through a set of validation points (z(val).. For a given validation data point 2(val), an ideal utility function at a single iteration is the reduction in validation loss:
T (1;::<(v)) (val)) = Elw,, ((val)) (i:00-(((--p (S),
(2)
where ( == W, ne--,, 7/ Eges Ve(w,, 2) and S B, is the subset of the batch selected for model update. While this is a principled choice for an optimization objective in online batch selection, optimizing U9) is computationally expensive, as it involves evaluating model updates with respect to combinatorially many subsets S C B, (a total of (1B..) subsets).
Vanilla Greedy Algorithm. To address the challenge of evaluating the objective function for numerous subsets, the greedy optimization algorithm is widely used due to its effectiveness in set function optimization. The greedy algorithm iteratively selects the element that provides the largest marginal gain to the utility function, given the previously selected elements. Mathematically, when a utility function (1()) is given, the greedy algorithm selects data points E B, one at time, At each selection round, the algorithm selects the data point 2" = argmax_ess ZEB, (8,
- (2)))
This process continues until & data points have been added to B,. The greedy algorithm is known to provide near-optimal solutions for monotone submodular set functions, with famous (1 (1-12 1/e)-- approximation guarantee [31]. The greedy algorithm only requires O()(B.l) evaluations of (1(1), significant improvement over the (14-l) evaluations required by the brute-force method.
However, optimizing (1t) using the greedy algorithm is still not practical for online batch selection. Each evaluation of the utility function (S) in (2) involves computing aggregated gradients, updating the model, and calculating the validation loss, which can significantly increase the per- iteration cost of training. Since online batch selection algorithms run alongside the model training, these costs cannot be amortized across training runs they would be with static dataset selection. This makes the greedy algorithm infeasible for real-time online batch selection.
4.2 An Efficient Greedy Algorithm for Utility Optimization without Utility Evaluation
Here, we develop an efficient approximation for the marginal gain of a data point 2 E B, \, B, to the utility of the already selected subset B, For notational simplicity, we denote g(,,) Vl(w,, 2,) for all 2; E B, Given that the learning rate t/ in model training typically small, a lower-order Taylor expansion often provides accurate approximation for the change in loss during single gradient

---

Algorithm GRBedy Approximation Taylor Selection (GREATS)
1: Input:
HessianApprox: approximation method for Hessian matrix.
2: Initialize model w/p
3: for = -....,, do
4: Sampled random batch B, from Di.-
5: Initialize the importance score Φ2 1)/)(s) 8(strab) for every E B..
6: Initialize the selected batch B, + (..
7: for 1,...,kk do
8:
2" - .E8, Oz.
9:
Add =" into B,
PlessianApper = "exact" then
11:
Update the importance score Φ₂ t Φ: - 17, B(a) (2 for = E B, B..
12:
else if HessianApprox "identity" then
Update the importance score Φ, t Φ₂ n/ g(2) 8(z)) for E B, B.. Take one step of gradient update on the selected batch B, and obtain Wr+1-
14:
update, with approximation errors Onτ)) for first-order approximations.
(=,B.) = 100 (8, U (2+}) (B.) E(Te+1 (B.), (val)) f(Tr+1 (B, {zi}); = =(val))
(( x(val)) -((Te+1 (B.) (1(B(z,)) 2 2(val))
m)g())) Ve( (vaa))
Interpretation. The first-order approximation of the marginal gain (z; computes the inner- product between (1) the gradient of the individual training loss with respect to the original model We, and (2) the gradient of the validation loss with respect to the "virtual model" W2+1 (B.), i.e., wa updated with the existing selected batch. The inner- inner-product represents the direct influence of 2 the validation loss at the "virtual model" W (B.). The gradient B(x.) is computed with respect to w,
instead of w1+1 (B:) because the model update process is performed using the gradients with respect wy. The approximation in (3) essentially estimates the improvement validation loss by including 2 in the model update, assuming that B, already guaranteed to included.
However, the computation of VE(ūū++1 (B.). 2(val) still requires obtaining the updated model param- eter We+1 (Be) and performing additional backpropagations to compute the validation gradient, which again incurs significant computational overhead. To efficiently approximate it, use another Taylor expansion as follows:
ve W (B:), 2(va)) Vilw, 1T.
Σ g(z), (vall) 2 B(2(va)) - .hH (wal))
Σ g())
B
where the Hessian matrix (2(va))) = (2 (val)), and B(2(val) = Ve(we, 2 (val)) Plugging this approximation back into we have
U (z)
n ((.) (2((a))
Σ ((s)
(())))
B(stva))
=EB,
Importance
Conrection of importance from already selected points
Interpretation. The first gradient inner- produ-product T)(B(..) "gg(val) coincides with the TracIN score proposed (33) as a measure for data point's importance. It captures the alignment between the gradient of the training loss for 2; and the gradient of the validation loss, indicating how much the update based on 2 would contribute to the reduction of the validation loss with respect to the original model Wy. The second term g()))) H Exee, B(a) is correction term for 2;'s original
importance after picking B. It penalizes the similarity between 2; and the data points in B,, as
5

---

measured by the Hessian- Hessian-weighted inner- umerr-product of their gradients. Intuitively, if the gradient of 2; is similar to the gradients of the data points in B,, the correction term will be large, reducing the overall marginal gain of adding 2, to the selected subset. This encourages the selection of diverse data points that provide complementary information to the model update.
Algorithm. Using the approximation from 4 we develop new algorithm that approximates the vanilla greedy algorithm. Initially, each data point 2 E B₁ is assigned an importance score o, initialized as Φz = (xx)(=) B(z(vayy. which approximates the marginal gain of adding z to an empty set, i.e., (2: {t) = ((2+)) The algorithm begins by selecting the data point with the highest importance score, 2 = BBB Φ2. After selecting a data point =" for model update, the importance scores for the remaining data points are adjusted by -1//8(z,, (2(a)))) This adjustment approximates the marginal gain of adding each remaining data point to the set containing e", i.e., (2a {²*}). The algorithm iteratively selects the data point with the highest adjusted importance score and updates the scores for the remaining points until k data points have been selected. As we can see, this iterative process closely mimics the behavior of the vanilla greedy algorithm while not requiring any actual evaluation of U(+), allowing for computationally tractable approximation of the greedy algorithm in the context of online batch selection. The pseudocode for the proposed algorithm is detailed in Algorithm
Validity of Taylor Approximation. We evalu- ate the fidelity of using Taylor expansion to ap-
Sure Gradiig Tet pridace
of ferdieet produces Hestar Internatie
8.0033
0.0773
proximate U Following the experimental set- tings from our GPT2 experiments detailed in Ap- pendix B we sample different batch subsets S and evaluate (S)) at the 3500th training itera- tion. Figure Sesureeiillstrraa iillstraaes the correlation between actual and predicted validation loss changes in single gradient update step. Panel (a) shows the correlation when using only the first-order term (the sum of training gradients' dot prod- ucts with the validation point) for loss change approximation. Panel (b) demonstrates the im- proved correlation when incorporating both the first-order term and the Hessian interaction term. The enhanced correlation coefficient with the in- clusion of the Hessian term indicates that our ap- proximations effectively capture the actual loss dynamics, with the second-order term providing substantial improvement in predictive accuracy.
52897
00000
2-10002
-00055
-20075
-0.0755
(
E50 0923 0339 033
0010
100
1500
E.EE 3.09 RES0
Figure 1:
(a) We show the correla- tion between the ground-truth model valida- tion loss change in one gradient update it- eration (5; ((va)) ( 2 ((va)) and the first-order Taylor ap- proximation Exes (r(((=) 8(zival). (b) We show the correlation between (S; and the first-order approximation corrected by the Hessian interaction EEes (1((s) g(z(val)
l(ur, 2(val))
Ex,'es (() H (y(van)B(2"))
4.3 The Ghost Inner-Product Technique
Implementation Challenges of [. Although Algorithm Saanhhmmelinn Teliminates the need for explicit utility evaluations and relies solely on gradient and Hessian information, its efficient implementation remains challenge. The initial importance scores 7)g((=) B(a(o))) require computing the inner- products between the gradients of each E B, and the validation point (vva)), Directly implementing this would involve calculating the individual gradients for every data point in B3, This cannot leverage the parallel processing capabilitics of GPUs and would require running backpropagation [B,] times with mini-batch size of 1, resulting in significantly higher per-iteration runtime cost compared to regular training. Furthermore, the correction term (1) (=(va)))(=> requires computing the product for each pair of 2, -, E B,. Even if we approximate the Hessian as the identity matrix (=()))) I), calculating the pairwise g(s) "(=²) still necessitates either storing all individual gradient vectors {g{=) or recomputing g(=) during each round of greedy selection. Both the memory and computational demands of these approaches are impractical for
training large-scale models.
Efficient Computation of ALL Initial Importance Scores. To address the challenge of computing the gradient inner-products between all = E B, and 2(val), we propose a novel technique called "ghost inner-product", which is inspired by the "ghost clipping" technique from the differential

---

privacy literature [ 6 The key idea behind "ghost inner- prreurtp is to avoid explicitly computing individual gradient vectors, thereby improving the efficiency of the algorithm. To illustrate this technique, consider simple linear layer T E Bg3xd is the mini-batch input, and s = (s(1), " E Bxd2 is the output (i.e., the pre-activation tensor). Let g(0) denote the individual loss on 2G. By applying the chain rule, we can express the gradient of an individual loss g(1) == f(w, 2,) with respect to W as
aW, where W E R is the weight matrix,
a = (a ..... )
ae
agti 8g(()
de
aw
ag(T) OW
Ōs(1)
: (ti) is the aggregated loss. Note that the output gradient हhीर is readily available during the backpropagation pass. To efficiently compute the gradient inner-product between validation point and each training point, include the validation data 2 together in the batch
dt
for backpropagation. That is, we take the backpropagation on Σ}= (6) + {(=(Ta)) Hence, for cach
training-validuen validation pair (2i, 2(val)), we have the gradient inner-product
DEGi Og(=
dE
de
((a))) ((=((a)))
OW
OW
as(())
Og(ztvany
By using the "ghost inner- mmnerrproduct technique, we can compute the result without explicitly forming any full gradient vectors. Consequently, computing the gradient inner-product between every pair of training and validation points requires only one backpropagation, which is significantly more efficient than the direct method that would require > |B,] backpropagations. We note that the "ghost inner- meeer-product" technique can be applied to various types of layers beyond linear layers. Similar decompositions as in Equation (5) have been studied in the differential privacy literature [36, 5 26). enabling the extension of this technique other layer types. Extension on LoRA in Appendix
Efficient Approximation of Importance Correction. The importance correction term B (g(wl) ((2=) poses computational challenges due to the involvement of the Hessian matrix. A straightforward approximation is to assume (z R3 I, simplifying the problem to computing the gradient inner-produs product g(=) B(=-). This upproximation has been widely used in the literature, particularly in the context of second-order optimization methods and letannen [29 13 32). The key motivation behind this approximation is that the Hessian matrix is often diagonally dominant, especially when the model is close to a local minimum
4 By assuming H (2(-0)) & I, the importance correction term simplifies to 02 '/2 B(s) B(=²)) We can then apply the ghost inner-produc' technique previously developed for computing pairwise gradient mnner-produce This allows us to efficiently compute the importance correction term without explicitly forming the individual gradient vectors the Hessian-vedd vector products.
Merging Batch Selection and Gradient Update in One Backpropagation. Utiiizing the techniques developed in this section, we can calculate or approximate terms in a single backpropagation pass, without the need to materialize any model-sized vectors. Although computing the gradient of the aggregated training loss Σ E g(3) for the training batch is necessary for parameter updates, an additional backpropagation pass is not required. By retaining the activations and output gradients from the previous backpropagation. we can efficiently compute this gradient without incurring the cost of another pass (see Appendix A..3 for details). Consequently, the process of training with batch selection introduces minimal additional runtime overhead. This approach provides substantial benefits over the direct method of materializing per-sample model-sized gradients, making it more feasible for real-world applications.
importance scores and correction
5 Experiments
In this section, we first evaluate the performance of GREATS against several baselines diverse set of models, training datasets, and validation set configurations. We then empirically examine its computational efficiency when implemented with "ghost inner-product" technique from Section 4.3
5.1 Experimental Setup
Model- Traederrriiinnn-alllle Evaluation Pairs. We examine multiple combinations of models, training datasets, and evaluation datasets to evaluate our proposed GREATS algorithm, shown in Table Specifically,
7

---

Table 1: Combination of models, training datasets, and evaluation datasets
Task
Model
Training Dataset
Evaluation Dataset
Number of validation data
Fine-tuning
LLAMA-2-7B
38
LESS
45
MMLU 1i
5
Fine-tuning
MISTRAL-7B
19
LESS
45
TYDIQA
10
Finc-tuning
LLAMA-3-8B
ALPACA
B7
SAMSUM 14
16
Pretraining
GPT-SMALL
OPENWEBTENT
15
OPENWEBTEXT
15
16
Deppladryy SONLLI sede
Tex: Parpecty SOHLI ucceigg
End Paggedyy trrgge pagg)
Text Derpli city HOLLL Serggo peto)
Bepear
Deguir
10
Maslow
Molls
NIVET
UABATS
GREATS
CRACES
(2)
500
1800
1500 2i00
2500 3600 Stags
(b)
930 2000
3500
Steps
2000
2503 3002
500
1000
3500
Stogs
2000
2500
3000
(c)
500 1906
1926 2300
Stape
2500 3000
Figure 2: Comparison of the validation and test perplexity dynamics during training for different online batch selection methods MMLU. We select sociology and US foreign policy subjects.
fine-tune three large language models (LLMs): LLAMA-2- 2-M 7B BS), MISTRAL-7B 7B [1)] and
LLAMA-3-8B [T] using LESS training data 43 and the ALPACA dataset 37 For evaluation,
employ the MMLU [17, TYDIQA 77. and SAMSUM [14] datasets (deferred to Appendix C). Additionally, we conduct pretraining experiment using the GPT-SMALL model 34. For both training and evaluation, validation data to be small (i.e., < 16) to mimic practical scenarios where training directly on them is impossible.
use the OPENWEBTED dataset [15]. In all experiments, we limited the
Baselines. We compare our algorithm with regular training and a variety of online batch selection
algorithms: (1) MaxLoss [28), which selects training data points with the highest loss values. (2)
GradNorm (23), which prioritizes training data points with the highest gradient norms. (3) Reference model-based method (RHOLoss), for which implement the RHO-Loss algorithm from [30] as a representative baseline. Given computational constraints, we use 1amna-..-8B-IInttuue [10] the reference model, paired with Llama2-7B the target model (4) settance-based method (SBERT), which selects training batches based on their semantic similarity to validation data using Sentence-BERT embeddings 35
Training Details. For all batch selection methods, we select 50% of the batch data for gradient updates during each step. In contrast, the regular training baseline performs updates the entire batch, utilizing twice as much data as the batch selection methods. In the main paper, we show the results of setting the batch size to 4 for MMLU and TYDIQA, 16 for SAMSUM and OPENWEBTEXT. Additional training details and ablation studies are provided in Appendix B
5.2 Performance Evaluation
In this section, we present and discuss the comparison between GREATS and the baseline algorithms in model training performance across different models, training, and evaluation datasets. We evaluate the performance on both the validation set (being used for batch selection in GREATS) and a test set that is drawn from the same domain of the evaluation datasets.
GREATS significantly speeds up training convergence. In Figure 2 and we show the dy- namies of perplexity on the validation and test datasets. As we can see from Figure 2 and Figure 4 across all settings, the GREATS algorithm achieves a significantly faster reduction in test perplexity compared all of the baselines and often achieves better overall performance.
"We note that while larger pretrained models could serve reference models, their computational costs increase substantially, particularly due to the need for repeated queries each training iteration. Furthermore, in specialized domains, general-purpose purpose pretrained models may exhibit suboptimal performance, necessitating fine- linettnnng on substantial holdout datasets. This additional requirement becomes impractical when computational efficiency and data availability are crucial considerations. We thank the anonymous NeurIPS reviewer for their helpful suggestion regarding the reference model selection in our comparisons.
8

---

Nepiinity
Derpiertty
Recudar GREATS of ViL-1)
16
GREATS VAL=2)
GREATS (MME))
GREATS (ound)
Peppects
Heppotty
ORRAAS
5.5
0
3.0
3.2
(4)
1095
2000
3000
(b)
1000
2000
3000
4.5
2033
0000)
140M)
5000
30600
(4)
2030
6140)
5600
5930
30000
Figure 3: (a)-(b): Impact of the number of validation data points on the performance of GREATS.
(c)-(d); Comparison of the validation and test perplexity dynamics during GPT2 pretraining for different online batch selection methods.
Method
MMLU (AVG.)
Soc.
Pol.
Alg.
Anat.
Astr.
Eth.
Clin.
Bio.
Chem.
TYDIQA
Regular
50.4%
62%
60%
40%
52%
48%
52%
54%
48%
38%
54.3%
GradNorm
50.4%
62%
62%
38%
50%
48%
54%
52%
50%
38%
53.4%
MaxLoss 50.8%
64%
58%
40%
52%
46%
54%
54%
50%
40%
54.7%
Ours 54.2%
68%
64%
44%
56%
52%
56%
54%
50%
44%
55.0%
Table 2: Accuracy on MMLU (9 subjects) and TYDIQA test set for online batch selection methods.
These results demonstrate the robust effec- tiveness of our approach in improving model convergence speed and generalization perfor- mance across various settings. We note that the validation-free approaches such as GradNorm and MaxLoss may lead to the selection of low- quality data. While is generally considered that data points with high training loss or large gradients are important to learning, there is an- other possibility that the data points that achieve these properties are corrupted data which is not learnable.
Dvall Deeptentty LE15-THRRA
3,475
Teet D'rpplecty LE55-TydROA
1.40
3.490
MacLaai
1.20
CREATS
[a) 560 1000 1392 2000 2500 3003
(b)
1000 3500 2000
2000 3000
Figure 4: Comparison of the validation and test perplexity dynamics during training for different online batch selection methods on TYDIQA
GREATS improves performance on downstream tasks. While perplexity is a direct measure of the performance of NLP models, it is not very interpretable, and the performance is often evaluated in terms of downstream tasks. In T we show the test accuracy on 9 (randomly selected) subjects from MMLU and TYDIQA. As we can see, GREATS consistently outperforms or at least achieves the same accuracy as the baselines. Notably, we observe at least a 3.4% improvement in the average performance of the 9 MMLU subjects compared to all baselines.
GREATS is robust to the number of validation points. In Figure (a)-(b) we conduct an ablation study to evaluate the impact of the number of validation points used for GREATS algorithm. As we can see, even with just 2 validation examples, the test perplexity on the MMLU dataset consistently lower than that of regular training. This robustness may be attributed to the relatively rare format of the validation corpus, which allows GREATS effectively select examples from the batch that can help learn the particular format. Even if such a selection may overfit the specific validation examples, the selected batch can still improve the performance on the test examples, demonstrating the effectiveness of the GREATS algorithm in adapting to the characteristics of the validation set.
GREATS also improves LLM pretraining. In Figure 3 (c)-(d), we evaluate the performance of GREATS on pretraining GPT-SMALLL on OPENWERTEXT. Due to computational resource constraints, we omit the baselines of GradNorm and MaxLoss, as they have been shown to be ineffective in all other experiments. As we can see, even for model pretraining, GREATS provides an improvement in test performance, although the improvement marginal compared the gains observed in the fine-tuning experiments. This marginal improvement can be attributed to the fact that the validation data used in this experiment is also drawn from the same distribution as the training set, i.c., OPEN WEB EE TEXT. As a result, the selected batches may not provide as much additional information or diversity as in the case of fine-tuning, where the validation data often comes from a different distribution or focuses on specific tasks. Nevertheless, the consistent improvement in test performance suggests that GREATS can still identify informative examples that contribute to better model generalization, even in the pretraining setting.
9

---

5.3 Runtime Comparison
We compare the runtime efficiency of GREATS algorithm with "ghost inner- paeeer-prductt technique against GREATS implemented directly by calculating per-sample gradients. The runtime is measured by training GPT-SMALL on WEENWETTEXT. Additionally, we compare against GradNorm's 's direct implementation using per-sample gradients, as it is the most similar algorithm to GREATS and allows for a fair comparison.
GREATS with "ghost inner-product" achieves runtime close to regular training. As shown in T the runtime of GREATS using our efficient approximation techniques is comparable to that of regular training, with only a slight increase in runtime due pair- wise inner- inner-product operations (but almost negligible compared with model backpropagation). This demonstrates the effectiveness of our approximation methods in reducing the computational overhead associated with online batch selection. On the other hand, the direct implementation of GREATS, which requires computing per-sample gradients, exhibits significant runtime increase compared to both regular training and our efficient GREATS implementation. The direct approach is significantly slower than regular training (almost 20 times slower), making impractical for real-world applications.
Throughput
Regular Training
76.2
GREATS (ghost)
71.3
GREATS (direct)
4.2
GradNorm (direct) 6.8
Table 3:
Efficiency com- parison of different imple- mentations of GREATS. We use throughput-f+ training data points being processed per second-as the efficiency metric.
The runtime of GradNorm with direct per-sample gradient computation falls between our efficient GREATS implementation and the direct GREATS implementation. This is because GradNorm does not need to compute the per-sample gradients from the validation set, which reduces its computa- tional overhead compared to the direct GREATS implementation. However, GradNorm still incurs significant runtime increase compared to regular training due to the per-sample gradient calculation for the training batch. We remark that the "ghost norm" technique from differential privacy literature 16 225 5 6) which is similar to "ghost inner-pre mmer-product", can be used to improve the runtime of GradNorm, potentially bringing it closer to regular training.
6 Conclusion and Limitations
In this work, we introduced GREATS, a novel online batch selection algorithm designed to enhance the efficiency and effectiveness of training large language models. Here, we briefly summarize the limitations of this work.
I. Availability of validation data. One potential limitation of GREATS is that it requires the validation data to be available before training. We stress that there are many scenarios where the validation data is naturally available before training such fine-tuning domain adaptation. Developing a validation-free variant of GREATS is an interesting future work.
II. Extension to Adam. The ghost inner- menrrttroduct technique developed in this work is specifically tailored for Stochastic Gradient Descent (SGD). It is not directly extendable to other popular optimiz- like Adam due their normalization terms. Nonetheless, using SGD proxy for Adam has proved to be effective in our experiment. Extending our ghost inner-produce technique to Adam and similar optimizers remains an exciting direction for future research.
I... Memory constraint for large batch sizes. In scenarios where GPU memory constraints prevent adding validation data to the training batch for backpropagation, we can easily extend our "ghost" techniques by using gradient accumulation. However, this may increase runtime due to additional backpropagation steps for validation data, it maintains the fcasibility of our techniques under memory constraints. Improving computational efficiency for large batch sizes remains an important direction for future research.
IV. Perplexity may not be an ideal objective. this work, the utility function being defined as the validation loss. While GREATS achieves promising results overall in terms of test perplexity, we note that perplexity may not reflect the performance in downstream tasks. While GREATS usually achieves higher performance on the downstream task, the improvement is often minor. Directly optimizing terms of the downstream performances another important future work.
10

---

Acknowledgment
This work is supported in part by the National Science Foundation under grants I1S-2312794, IIS- 2313130, OAC-2239622, CNS-2131938, Amazon- Virginia Tech Initiative in Efficient and Robust Machine Learning, the Commonwealth Cyber Initiative, OpenAl and Google.
We thank Ashwinee Panda, Xinyu Tang, and Yiding Jiang for their helpful feedback on the preliminary version of this work. We thank anonymous NeurlPS reviewers for the helpful feedback and discussion of this work.
References
[1] Al@Meta. Llama 3 model card. 2024.
[2] Alon Albalak, Yanai Elazar, Sang Michael Xie, Shayne Longpre, Nathan Lambert, Xinyi Wang, Niklas Muennighoff, Bairu Hou, Liangming Pan, Haewon Jeong, Colin Raffel, Shiyu Chang, Tatsunori Hashimoto, and William Yang Wang. A survey on data selection for language models, 2024.
[3] Alon Albalak, Liangming Pan, Colin Raffel, and William Yang Wang. Efficient online data mixing for language model pre-training, arXiv preprint arXiv:2312.02400 2023.
[4] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223-11 2018.
[5] Zhiqi Bu, Jialin Mao, and Shiyun Xu. Scalable and efficient training of large convolutional neural networks with differential privacy. Advances in Neural Information Processing Systems, 14338355-88118 2022.
[6] Zhiqi Bu, Yu-Xin Yu-Xiang Wang, Sheng Zha, and George Karypis. Differentially private optimization on large model at small cost. In International Conference on Machine Learning, pages 3192- 3218. PMLR, 2023.
[7] Jonathan H. Clark, Eunsol Choi, Michael Collins, Dan Garrette, Tom Kwiatkowski, Vitaly Nikolaev, and Jennimaria Palomaki. Tydi qa: A benchmark for information-sseking question answering in typologically diverse languages. Transactions the Association for Computational Linguistics, 2020.
[8] Mike Conover, Matt Hayes, Ankit Mathur, Jianwei Xie, Jun Wan, Sam Shah, Ali Ghodsi, Patrick Wendell, Matei Zaharia, and Reynold Xin. Free dolly: Introducing the world's first truly open instruction-tuned 11m, 2023.
[9] Zhijie Deng, Peng Cui, and Jun Zhu. Towards accelerated model training via bayesian data selection. Advances in Neural Information Processing Systems, 36, 2024.
[10] Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, al. The llama 3 herd of models. arXiv preprint arXiv:2407.21728 2024.
[11] Logan Engstrom, Axel Feldmann, and Aleksander Madry. Dsdm: Model-aware dataset selection with datamodels. arXiv preprint arXiv:2401.12926, 2024.
[12] Simin Fan, Mattco Pagliardini, and Martin Jaggi. Doge: Domain reweighting with generalization estimation. In Forty-first International Conference Machine Learning, 2024.
[13] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adap- tation of deep networks. In International conference on machine learning, pages 1126-1135. PMLR, 2017.
[14] Bogdan Gliwa, Iwona Mochol, Maciej Biesek, and Aleksander Wawer. SAMSum corpus: A human-annotater dialogue dataset for abstractive summarization. In Proceedings of the 2nd Workshop on New Frontiers in Summarization, pages 70-79, Hong Kong, China, November 2019. Association for Computational Linguistics.

---

[15] Aaron Gokaslan and Vanya Cohen. Openwebtext corpus. http://Skyyiion007, http://iiiooo...ttuubb.. / OpenwebTextCorpus 2019.
[16] lan Goodfellow. Efficient per-example gradient computations. arXiv preprint arXiv:1510.01799
2015.
[17] Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding, In International Conference on Learning Representations, 2020.
[18] Edward J Hu, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, Weizhu Chen, et al. Lora: Low-rank adaptation of large language models, In International Conference on Learning Representations, 2021.
[19] Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. Mistral 7b, 2023.
[20] Angela H Jiang. Daniel I.-K Wong, Giulio Zhou, David G Andersen, Jeffrey Dean, Gregory R Ganger, Gauri Joshi, Michael Kaminksy, Michael Kozuch, Zachary Lipton, al. Accelerating deep learning by focusing on the biggest losers. arXiv preprint arXiv: 191000062, 2019.
[21] Yiding Jiang, Allan Zhou, Zhili Feng, Sadhika Malladi, and J Zico Kolter. Adaptive data optimization: Dynamic sample selection with scaling laws. arXiv preprint arXiv:2410.11820, 2024.
[22] Jean Kaddour, Oscar Key, Piotr Nawrot, Pasquale Minervini, and Matt Kusner. No train no gain: Revisiting efficient training algorithms for transformer-based language models. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[23] Angelos Katharopoulos and François Fleuret. Not all samples are created equal: Deep learning with importance sampling. In International conference on machine learning, pages 2525-2533
PMLR, 2018
[24] Andreas Köpf, Yannic Kilcher, Dimitri von Rütte, Sotiris Anagnostidis, Zhi-Rui Tam, Keith Stevens, Abdullah Barhoum, Nguyen Minh Duc, Oliver Stanley, Richárd Nagyfi, et al. Ope- nassistant pngessaaioonsdemmcrataiiii large language model alignment. arXiv preprint arXiv:2304.07327, 2023.
[25] Jaewoo Lee and Daniel Kifer. Scaling up differentially private deep learning with fast per- example gradient clipping. Pruceedings on Privacy Enhancing Technologies, 2021.
[26] Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto. Large language mod- els can strong differentially private learners. In International Conference on Learning Representations, 2021.
[27] Shayne Longpre, Le Hou, Tu Vu, Albert Webson, Hyung Won Chung, Yi Tay, Denny Zhou, Quoc V Le, Barret Zoph, Jason Wei, et al. The flan collection: Designing data and methods for effective instruction tuning. arXiv preprint arXiv:2301. 13688, 2023.
[28] Ilya Loshchilov and Frank Hutter. Online batch selection for faster training of neural networks. arXiv preprint arXiv: 1511111111000 1.06443, 2015.
[29] James Martens and Roger Grosse. Optimizing neural networks with fronecker-factored approx- imate curvature. In International conference on machine learning, pages 2408-2417. PMLR, 2015.
[30] Sören Mindermann, Jan Brauner, Muhammed T Razzak, Mrinank Sharma, Andreas Kirsch, Winnie Xu, Benedikt Höltgen, Aidan N Gomez, Adrien Morisot, Sebastian Farquhar, et al. Pri- oritized training on points that are learnable, worth learning, and not yet learnt. International Conference Machine Learning, pages 15630-15649, PMLR, 2022.
12

---

[31] George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions- Mathematical programming. 14:265-294 1978.
[32] Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-learning algorithms. arXiv preprini (et::::800302999 2018.
[33] Garima Pruthi, Frederick Liu, Satyen Kale, and Mukund Sundararajan. Estimating training data influence by tracing gradient descent. Advances in Neural Information Processing Systems, 33:19920- 19930, 2020.
[34] Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodci, and Ilya Sutskever. Language models are unsupervised multitask learners. 2019.
[35] N Reimers. Sentence-bert: Sentence embeddings using siamese bert-networks. arXiv preprint MeXiv:/908 10084, 2019.
[36] Gaspar Rochette, Andre Manoel, and Eric W Tramel. Efficient per-example gradient computa- tions in convolutional neural networks. In Workshop Theory and Practice of Differential Privacy (TPDP), 2020.
[37] Rohan Taori, Ishaan Gulrajani. Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. Stanford alpaca: An inslroction-follooinng llama model. https://gi thw..
ord alpaca 2023.
[38] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.0922 07.88888, 2023.
[39] Jiachen T Wang, Prateek Mittal, Dawn Song, and Ruoxi Jia. Data shapley in one training run. arXiv preprint arXiv:2406. 1011 2024.
[40] Jiachen T Wang, Tianji Yang. James Zou, Yongchan Kwon, and Ruoxi Jia. Rethinking data shapley for data selection tasks: Mislcads and merits. arXiv preprint arXiv:2405.055: 03385, 2024.
[41] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35:24824-24833 2022.
[42] Alexander Wettig, Aatmik Gupta, Saumya Malik, and Danqi Chen. Qurating: Selecting high-quality data for training language models. arXiv preprint arXiv:2402.09739, 2024.
[43] Mengzhou Xia, Sadhika Malladi, Suchin Gururangan, Sanjeev Arora, and Danqi Chen. Less: Selecting influential data for targeted instruction tuning. arXiv preprint arXiv:2402.04333, 2024.
[44] Sang Michael Xie, Hieu Pham, Xuanyi Dong, Nan Du, Hanxiao Liu, Yifeng Lu, Percy $ Liang, Quoc Le, Tengyu Ma, and Adams Wei Yu. Doremi: Optimizing data mixtures speeds up language model pretraining. Advances in Neural Information Processing Systems, 36, 2024.
[45] Yifan Zhang, Yifan Luo, Yang Yuan, and Andrew C Yao. Autonomous data selection with language models for mathematical texts. In ICLR 2024 Workshop on Navigating and A Addressing Data Problems for Foundation Models, 2024.
13

---

A Ghost Inner-Product
Notation Review. Consider a linear layer s = aW, where W Rdixda is the weight matrix, (a(") (a("..... a (B))T the mini-batch input, and (s(!), ..... B T the layer output (i.e., the pre-activation tensor). For non-sequential data, E RRBxi Bxd2, For sequential data with sequence length T, E Bxxd xT , E _ Bxd2 XT Let g() l(w, 2,) denote the current model's individual loss on 2,, and we denote := Σラ= gه)) the aggregated loss over the full data batch
For notation convenience, we denote individual output derivative b( {2t) (=))==-
A.1 Ghost Inner-Product for Linear Layers
Non-sequential data, For non-sequential data, we can decompose the gradient of an individual loss g() with respect W
Qg() aw
Ogti) O0()) de Os(()
OE Ōs(1)
Os(1) oW 0sti) OW a (1)
a (())
(6)
where the second equality is because ((3) does not depend (+) for j * i, and the third equality is
due to the linear transformation aW. An important observation is that the individual's 's output gradient b (i) is readily available during the backpropagation with respect to the aggregated loss l.
Say we interested computing the gradient inner-product 21: 22 in the same batch in the backpropagation. For non-sequential data, we have each (+) Rd
(g(3)
ex(2)
between data points
ow
and b (9) E R Rlxd2 By ( we have
OE(1)
0((2)
(1) & b())
(2(2) 2
(2(2)
b())
= (ba) o (b2) (=
(7)
ow
ow
where the second equality is due the mixed product property. is particularly interesting because 8
ag03>
2W without actually instantiating it shows that we can compute the inner-product between ow
and
the huge gradient vector 8W or ac(2)
ag(1)
vectors) for a @ a (2) and b 8w We can first take the dot products (i.e., inner-product for
(2), then multiply the results together. Moreover, all of the materials a (1) (2) (1) (2) that are required for computation are all already available during the backpropagation with respect to f. Hence, with just single backpropagation, we can efficiently compute the gradient inner-product between every pair of the data points within the batch.
Sequential data. For sequential data, have each (6) [RdixT and b () T'xd, We can
similarly decompose the gradient of an individual loss g()) with respect to W follows:
0e
0E6) ()
Of 0g(1)
dl
T
(0)
b
(8)
aw
(5(1) DW
3s(T) aw
t=l
14

---

By
8 we have
age
0(
Σ
(1)
b
(
Σ
2
a
ow
ow
11
(
a
3
a
Σ
(2)
(2)
a
tzz
b
12.
Σ
Σ
(1)1
a/2
b
(b,
(2)T
1= 1=
((alt)) T a(23)
((()) (b(2))
Hence, comparing with directly computing per- cer-sample gradients, if 27 did2, it is more memory- and (a(") a (2), then take the inner product
efficient first multiply the matrices of (D()) ( (b(2)
between the two T x T matrices. 27 2 di d2, then we can first take the outer products ( & (1) and a (2) @ (2), then take their inner product. In either case, only need a single backpropagation to compute the gradient inner-product between every pair of the data points within the batch, similar to the case of non-sequential data.
Concurrent with this work, also apply the ghost inner-product technique for efficient data attribu- tion 39
A.2
Ghost Inner-Product for LoRA
LoRA. For a linear layer W, LoRA (Low-Rank Adaptation) [18 introduces additional trainable parameters to adapt the model effectively while maintaining computational efffiiicccccicccccccc...... Specifically, the original weight matrix is modified as W W + AB, where new low-rank matrices with & min(d,, d2). This adaptation allows for significant modifications of the layer's ' behavior through a low low-rank update, which adds a minimal number of parameters to the model compared to the original number in W. Here, we show how to compute ghost inner-produc for LoRA.
RRdixr and RRrxda are
The gradient of LoRA layer A can be computed as
at de OW
@e Os Ös Ow
B
BJ
aA
ow
0A
and the gradient of LoRA layer B can be computed
ae at aw'
ow AB AT (a
ØB
Non-sequential data, For non-sequential data, the inner-product between two gradients on A can be written
15

---

0e(2)
d1
(()
((1)))
00 b())
BT)
0A
0A
jk
jk
1=1
d1
(2)
B
aj
(2)
B
de
(2)
BT
(2)
B
i=1
a 2
((DUBBT)
Similarly, we have
de(1)
0e(2)
d
A (a (b))))))) jk
(AT (a(2) (02b))))
²B
²B
j=1 k=1
Σ AJaa (1) DD (1)
[[ AJaa
AJ.a.")
(
b ((ATa!)) * (ATa(2))
Sequential data. We now consider the setting of sequential data with sequence length T. In this case. we have
() ( Bxd,, xT and b (b ....,..(())))) (B))TT R Rxdds
20(1)
0E(2)
d2
(1)
(1) D
BT
a
(2) jt
(2) Pi
B
0A
0A
T
da
(1)
(1)
B 1k
Σ
a
jt
(2)
85
B
1=1
[=1
1=1
T
T
Σ
B
B
T
T
ΣΣ
B
a
jt
ΣΣ
Σ
f
1
D
Lk
Σ
jr
(2)
D
(2) ek
(a")²
a
(D(")
(D(2))
where in the second-to-the-lass step we denote D (
(2) BT
A.3 Merging Batch Selection and Gradient Update in One Rackpropagation
By utilizing the ghost inner-product technique developed in this paper, we can calculate or ap- proximate all importance scores and correction terms in a single backpropagation pass, without materializing any model-sized vectors. To compute the gradient inner-product between each training
16

---

point 2; E B₁ and the validation data 2(va)), we propose including 2 in the backpropagation along with the training batch. Specifically, we can backpropagate with respect to 2 ( + g(=(ma))
After performing GREATS and selecting B,, it may seem necessary to backpropagate with respect to Ex,88, ((,) to compute the gradient for the parameter update. However, this is not required. We can ag(+) simply reuse the output gradient 8g(i] from the original backpropagation and aggregate the gradients for all selected data points. This technique, referred the "book- peep-ig trick, is adapted from [6]
17

---

B Details of Experimental Setup
Training Dataset. In our experiments, use three training datasets: LESS +3 ALPACA [C]
BY-NC 4.0), and OPENWEB TEXT [3][C Specifically, LESS is a combination of four instruction tuning datasets: FLAN V2 27 CoT 41, DOLLY (8) and OPENASSISTANT (24. The LESS dataset comprises 270k data points, from which we randomly select 5% for training. Alpaca is an instruction-following dataset containing 52k data points. OPENWEBTEX: is recreation of the WEBTEXT 34 corpus, containing approximately 8 million documents.
Evaluation Dataset. To our GREATS, we consider four datasets: MMLUU 17], TYDIQA 77]. SAMSUM [4], and OPEN OPENWEBTENT" [[]. Specifically, MMLU consists of multiple-choice ques- tions covering 57 subjects, including math, computer science, US history, and more. In Table 2 report accuracy for nine selected subjects: Sociology. US Foreign Policy, Abstract Algebra, Anatomy, Astronomy, Business Ethics, Clinical Knowledge, College Biology, and College Chemistry. TYDIQA a multilingual question-answer answering dataset including 1 diverse languages. In our evaluation, we randomly select 500 test data to compute the perplexity and F1 score. The task is to extract the answer to query from a given passage. SAMSUM a dialog dataset with the task of summarizing a given dialogue between humans.
More Training Details. For the experiment results shown the main paper, the training hyperpa- rameters are shown below:
1. Finetuning LLAMA-2-78 to MMLU: We finetune LLAMA-2-7B on 5% of the LESS dataset, setting the LoRA rank to 128, LoRA a to 1.0, and dropout to 0.1. The learning rate is set to 2e-5
2. Finetuning MISTRAL-7B to TYDIQA: We finetune MISTRAL-7B on 40% of the LESS dataset, setting the LoRA rank to 128, LoRA a to 1.0, and dropout to 0.1. The learning rate is set le-5.
3. Finetuning LLAMA-3-8B to SAMSUM: We finetune LLAMA-3-8B on the ALPACA dataset using Torchtune setting the LoRA rank 8, LoRA a 0.1, and the learning rate to 2c-5.
4. Pretraining GPT-SMALL OPENWEBTEXT: We pretrain the GPT-SMALL model with learning rate of 6e-4 and a batch size of 16
More Evaluation Details. To evaluate the accuracy of MMLU and TYDIQA, we follow the LESS paper's approach, using few-shot in-context learning demonstrations. Specifically, we measure the 5-shot accuracy for the MMLU dataset and the 1-shot macro-averaged Fl score for TYDIQA. We
also provide examples of evaluation data in Figure 5 and g
Example of MMLU
Question:
The shift from "civil religion" to "common religion" means that:
(A) the increasing burcaucracy of the state has made religion only a marginal part of our lives,
(B) despite the weakening of traditional authority, our everyday lives and ccommn sense" remain shaped by religious beliefs and values
(C) religious participation in collective worship may have declined, people still practise their faiths in private
(D) people are much more likely to discuss their religious beliefs in public, informal settings
Answer: B
Figure 5: Example of MMLU
"Codehase for task I and task 2: htapa/////lrpr////ttttttoootttta
1 'Codehase for task 3:
hhb httpp:///gthhbb.ooayyyrrrrr/rrrr
"Codebase for task 4: https::/ggichu..cmm/aapppppp
18

---

Example of TYDIQA
Passage: Home Box Office (HBO) is an American premium cable and satellite television network that owned by the namesake unit Home Box Office, Inc., a division of AT&T's WarnerMedia, The program which featured on the network consists primarily of theatrically released motion pictures and original television shows, along with made-for-cable movies, documentaries and occasional comedy and concert specials. Question: Who owns HBO? Answer: Home Box Office
Figure 6: Example of TYDIQA
Example of SAMSUM
Dialog:
O'Neill: Is everything ok?
O'Neill: didn't 't hear back from you O' O'Neill: <file_gif>
Ted: Hey
Ted: I have been really busy today
Ted: Sorry.
Ted: Yes everything fine :)
Ted: I'll send you photo later on :)
O'Neill: Great!!
Answer: O' O'Neill is worried about not having heard from Ted. Ted is fine and is going to send photo later.
Figure 7: Example of SAMSUM
Example of OPENWEBTENT
Text:
A magazine supplement with an image of Adolf Hitler and the title 'The Unreadable Book' is pictured in Berlin, No bans "Mei...
Figure 8: Example of OPENWEBTEX.
C Additional Experiment Results
Phepdasslyy
Pepteciy Aipeca
Regida
Repuiar
Quodioott
GrodNorzs
MasLaso
Muiloss
CREATS (Ouna)
GREATS (Ouns)
Stegis
Stepo
Figure 9: Experimental results SAMSUM, where we leveraged ALPACA as the training data. Our
GREATS method significantly outperforms other approaches.
UratNoer Nateu
Crathoers MadLes
RUKCOO
DREATA
FREATE
Nodaun
GRENTS
623
1
Skge
Supe
Sape
Sage
Figure 10: Similar to Figure instead, we use batch size of and learning rate of 4e-5.
19

---

Regelr
Hard
6.75
Mustan
GREATS
CREAAT
600
820
SRERT
810
7:30
0330
500
1062
1802
2000
2000
2008
(b)
300
1000
1539 2090
2000 3093
(6)
1000
3030
3006
(4)
0
1000
2000
3000
Figure 11: Similar to Figure 2 instead, we use batch size of 32 and a learning rate of 2e-5.
10.3
0.3
4.0
Cooflien
Cratkkes MarLos
Gredhtem
Motass
Maslowe
BHOLOO CREATS
GREATS
GREATS
GRESATS
(C)
(d)6
Mayo
Figure 12: Similar to Figure 2 instead, use batch size of 32 and learning of 4e-5.
20

---

D Broader Impacts
We expect our work to have positive societal impact. We developed novel method facilitate the training process of large language models.
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our main contribution claimed in the introduction is developing efficient online batch selection algorithm which is detailed in Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
In Section 6 discussed the limitation of this work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
22

---

Justification:
The paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibiliyy
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: In Appendix we include all information required for reproducing our experiment results.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
23

---

Answer: [No]
Justification: We will release the code repo for this work at the time of publishing. We provided the link to the Github repo that built upon in Appendix B
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
public/guides httple/eeeooeeueeeesssssoooooona
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurlPS code and data submission guidelines (https wetgguddddeeouuubbuneeee ssiniooiccy for more details.
//nips.co
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: In Appendix B experiment results.
we include all information required for reproducing our
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Due to the computationally expensive nature, for data selection experiments we only take I training run, and for most of the other experiments we take the results from the average of runs.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: In Appendix B we include all information required for reproducing our experiment results.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics sectpa://neurips: http:///wwwarr...cooo/////ccccca
Answer: [Yes]
Justification: have reviewed the ethics requirement.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discussed the broader impacts in Appendix D
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
25

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: all information is mentioned in Appendix B
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
26

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: the paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [No]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "NAVcpMKXOz", "reviewer": "Reviewer_2jYA", "summary": "This paper proposes GREATS (GREedy Approximation Taylor Selection), a novel online batch selection algorithm for large language model (LLM) training. GREATS aims to improve training efficiency by dynamically selecting the most informative data points from each training batch, based on their potential to reduce validation loss. The authors formulate the batch selection problem as set function optimization and leverage Taylor expansions to efficiently approximate the impact of each data point on validation loss. To address the computational overhead of calculating per-sample gradients, they introduce a technique called \"ghost inner-product.\" Experimental results demonstrate that GREATS consistently accelerates training convergence and improves generalization performance across various language modeling tasks.", "questions": "Please look at weaknesses.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "*  GREATS is grounded in a principled set function optimization framework, aiming to directly optimize model performance on a held-out validation set. This contrasts with heuristic-based methods, providing a stronger theoretical foundation.\n*  Leveraging Taylor expansions to approximate the marginal gain of data points is a clever approach that significantly reduces computational complexity. This makes GREATS more practical for large-scale LLM training compared to methods requiring repeated model updates and validation evaluations.\n* The proposed \"ghost inner-product\" technique for efficient gradient inner-product calculation is innovative and addresses a major computational bottleneck in online batch selection. This technique has the potential for broader applicability in machine learning beyond data selection.", "weaknesses": "* As also pointed out by the authors, GREATS relies on a small set of clean validation data, which may not always be readily available in practical scenarios, especially for pretraining. Classifying a point as noisy and not of interest just because a similar point doesnt exist in validation might not be ideal, and I am not sure how GREATS could be handling this.\n\n* Approximation Accuracy: While the use of Taylor expansions for approximation is efficient, the accuracy of these approximations can be affected by factors like learning rate and non-linearity of the model. Further analysis and discussion on the potential limitations of these approximations would strengthen the paper.\n\n* Limited Comparison: The paper only compares GREATS against simple baseline methods (Regular, MaxLoss, GradNorm) and excludes comparison with reference-model-based methods. While these are computationally expensive, including such comparisons might be beneficial to the larger research community.\n\n*  The performance of GREATS is likely sensitive to various hyperparameters like the learning rate, batch size, and the number of validation data points. The paper lacks a systematic study of these hyperparameter sensitivities.\n\n* As pointed out by the authors, the \"ghost-inner product\" technique works best in tandem with SGD, but not with Adam or other optimizers. Thus, it is unclear if these models used Adam while training, but just SGD for the utility function computation, or if the entire model was trained through SGD itself. I believe, Adam with weight decay has become a common optimizer for these LLMs and the findings if presented by training through SGD might not translate to the practical setting where Adam or AdamW is used. I believe further clarification might be required here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the nice words!\n\n**Q [Requirement of validation set]**\n\n**A.** We acknowledge that the availability of a high-quality validation set is a limitation of GREATS. However, most state-of-the-art data selection (e.g., [1, 2]) and online batch selection techniques (e.g., [3]) rely on a high-quality validation set. This is a common approach in the field to guide the selection process toward data that aligns with the target domain or task. In finetuning tasks, practitioners typically have a small set of high-quality, task-specific data that can serve as a validation set. **Validation data for pretraining:** We agree that for pretraining scenarios, obtaining a representative validation set can be more challenging. However, even in these cases, it's often possible to curate a small set of diverse, high-quality samples that help for data selection [4, 5, 6]. Our experiments demonstrate that **GREATS can perform well even with a very small validation set** (as few as 2-5 samples), which makes the requirement more practical to fulfill in many scenarios. Furthermore, GREATS selects points based on their potential to improve performance on the validation set instead of simply filtering data points that are similar to the validation data. It's worth noting that while GREATS does require a validation set, it avoids other limitations of existing methods, such as the need for reference models, making it more practical for large-scale training scenarios.\n\n[1] Xia, Mengzhou, et al. \"LESS: Selecting Influential Data for Targeted Instruction Tuning.\" ICML 2024\n\n[2] Xie, Sang Michael, et al. \"Data selection for language models via importance resampling.\" NeurIPS 2023\n\n[3] Mindermann, Sören, et al. \"Prioritized training on points that are learnable, worth learning, and not yet learnt.\" ICML 2022\n\n[4] Tirumala, Kushal, et al. \"D4: Improving llm pretraining via document de-duplication and diversification.\" NeurIPS 2024\n\n[5] Maini, Pratyush, et al. \"Rephrasing the Web: A Recipe for Compute and Data-Efficient Language Modeling.\"\n\n[6] FineWeb: decanting the web for the finest text data at scale.\n\n**Q [Approximation accuracy of Taylor expansion]** *“While the use of Taylor expansions for approximation is efficient, the accuracy of these approximations can be affected by factors like learning rate and non-linearity of the model. Further analysis and discussion on the potential limitations of these approximations would strengthen the paper.”*\n\n**A.** We thank the reviewer for the valuable suggestions. We conducted additional experiments and examined two key correlations in **Figure 5 in Global response**: **(a)** The correlation between the actual validation loss change in a single gradient update step and the loss change predicted by the sum of training gradients taking dot product with the validation point (i.e., the first term in Equation (4)). **(b)** The correlation between the actual validation loss change in a single gradient update step and the loss change predicted by both the gradient dot product sum and the Hessian interaction term, as shown in Equation (4). As we can see, if we do not incorporate the interaction term, the Pearson correlation coefficient is approximately 0.75. Figure (b) shows that the correlation coefficient improved by including the Hessian interaction term to approximately 0.84. These results demonstrate that our approximations capture a significant portion of the actual loss change, with the inclusion of the Hessian interaction term providing a notable improvement in accuracy.\n\n**Q [Comparison with reference-model-based methods]** \n\n**A.** We have conducted additional experiments using the RHO-Loss method from [1] as a representative baseline for reference-model-based approaches. Due to time and computational constraints, we used Llama-3.1-8B-Instruct as the reference model (with Llama2-7B as the target model), prioritizing training on data points with high RHO loss ($L(x; f_{tgt}) - L(x; f_{ref})$ where $f_{tgt}$ is the target model and $f_{ref}$ is the reference model). Surprisingly, the RHO-Loss method performed poorly, showing the worst performance across almost all settings. We hypothesize two main reasons here: **(1) Noise and scale discrepancy:** The loss value from the current target model $L(x; f_{tgt})$ is highly noisy and may be of a different scale compared to the reference model. This discrepancy could result in $L(x; f_{ref})$ having minimal impact on the batch selection results. **(2) Reference model limitations:** Due to computational and time constraints, we used a relatively small pretrained model as the reference. This may not adequately reflect the \"learnability\" or \"difficulty\" of the training examples, which is crucial for effective data selection. These findings highlight a key advantage of GREATS: it offers a more efficient and flexible alternative that can perform well without relying on reference models, which can be computationally expensive or may not be available in practice. \n\n[1] Mindermann, Sören, et al. \"Prioritized training on points that are learnable, worth learning, and not yet learnt.\" ICML 2022.\n\n**Q [Experiment with additional baselines & different hyperparameters]** \n\n**A.** As suggested, we have performed experiments with additional baselines and different choices of learning rates / batch sizes. The results are in **Global response Q1**. The results show that GREATS **consistently performs well** across all the hyperparameter configurations we considered. This robustness suggests that GREATS can maintain its effectiveness without requiring extensive hyperparameter tuning. An ablation study on the number of validation points in Figure 3 (a)-(b) of the paper. This study demonstrates that GREATS can perform effectively even with a small number of validation points (2 to 5), which is a crucial aspect of its practical applicability.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "jomx1MEXa5", "reviewer": "Reviewer_vNzN", "summary": "The paper proposes a new online batch selection algorithm, GREATS, which frames batch selection as an optimization problem: specifically, selecting a subset of the training data that maximally reduce the validation loss when used as part of training. It uses a Taylor approximation of the effects of training on a given data point to estimate the value of each data point for the purposes of training, including a second order Hessian term that partially accounts for potential interactions between the data points of the batch affecting their collective value as training data, then greedily selects a batch of training data to minimize validation loss. Further, the paper propose the 'ghost inner product' method of efficiently computing pairwise gradient inner products with only a single step of backpropegation.\n\nThe paper tests their method in a variety of finetuning settings on Llama-2-7B, Mistral-7B, and Llama-3-8B (trained on either LESS or Alpaca datasets and tested on MMLU, TydiQA, or SamSUM), as well as for pretraining a GPT2 base model from scratch on OpenWebText data. It uses some fairly simple baselines (the \"regular\" unbiased sampling of batches, sampling high loss data points, and sampling high gradient norm data points), and finds that GREATS consistently outperforms them. Finally, the authors address the questions of sensitivity to validation data set size and of runtime, finding that GREATS is pretty robust to using smaller validation sets and that their implementation of GREATS has little computational overhead.", "questions": "Do the authors use SGD or Adam in their experiments? The limitations section mentions the ghost inner product technique doesn't work for Adam, but says \"using SGD as a proxy for Adam has proved to be effective in our experiment.\" Does this mean the authors compute the ghost inner product for SGD, but then just use the results for Adam? (The learning rates seem to suggest so).\n\nI have concerns about the optimality of the training setups. The paper does not appear to describe any sort of hyper parameter tuning for the finetuning or pretraining. How were these values selected? Additionally, given that SGD (or Adam?) with small batch sizes is a nonstandard choice for such experiments, how would the authors argue that their results can be expected to be relevant to a setting that better matches current SOTA (e.g., with Adam and large batch sizes)? Can we expect the method's benefits to hold for larger batch training, given that batch selection should become less impactful as batch size increases (e.g., going to zero once we reach full-batch training).\n\nFrom what I understand, the authors always select batches using validation data drawn from the same distribution as the testing data. In realistic training settings, one usually does not know the exact distribution form which the downstream test data will be drawn. Thus, I wonder if the authors could address the question of what happens when the validation data used during online batch selection is partially \"off distribution\" for the actual test data?", "limitations": "Lacking an implementation of the ghost inner product method for Adam and similar state of the art optimizers may be a significant limitation of this method? It depends on whether the authors were forced to use SGD in their experiments.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "**Originality**:\nThe clear formulation of the objective for online batch selection, the Taylor approximation-based approach to efficiently optimize that objective, and the ghost inner product method all seem like potentially original and valuable contributions.\n\n**Quality**:\nThe paper largely seems well put together and executed, though with some potential issues related to a lack of strong baselines.\n\n**Clarity**: \nThe paper was generally clear, with some grammatical issues or weird phrasing. E.g.,\nLine 13: \"the extensive training times\" --> \"their extensive training times\"\nLine 59: \"updating model\" --> \"updating the model\"\nLine 62: \"one-step gradient\" --> \"one step of gradient\" or \"single-step gradient\"\nLine 87: \", and update\" --> \"and updates\"\nLine 88: \"where\" --> \", where\"\nand various other places.\n\nHowever, the introduction of \"utility functions\" seems superfluous. It seems like the authors can just talk about the optimization objectives of various batch selection methods directly. E.g., \"We search for training datapoints that minimize the validation loss\" vs \"We propose to set the utility function to be the validation loss, and then search for training data points that optimize this utility function\".\n\n**Significance**:\nThe significance of this contribution is hard to judge due to 1) potentially weak baselines, and 2) lack of engagement with more contemporary prior work.\nHowever, it seems potentially high, due to the importance of the domain, and because the approach seems simple and intuitively well-motivated.", "weaknesses": "I think the biggest weakness of this paper is the lack of stronger baselines to compare against. E.g., both of the following seem like stronger contenders than the max loss / max grad norm approaches:\n- https://proceedings.neurips.cc/paper_files/paper/2023/hash/dcba6be91359358c2355cd920da3fcbd-Abstract-Conference.html\n- https://proceedings.neurips.cc/paper_files/paper/2023/hash/6b9aa8f418bde2840d5f4ab7a02f663b-Abstract-Conference.html\n\nIf I'm considering using some online batch selection method from the literature, max loss / max grad norm don't really seem like they'd even be in the running. So comparing against them doesn't really help establish to be that GREATS would be the most appropriate choice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments! \n\n**Q. [Relationship between online batch selection and offline data selection / data mixture optimization techniques [1, 2]? & Additional baseline comparison]** \n\n**A.** \nWe appreciate the reviewer highlighting the relevant literature on offline data selection [1] and data mixture optimization [2]. We'd like to clarify that **offline data selection techniques are not direct competitors to online batch selection methods** like GREATS. Instead, these approaches are complementary and can be used in conjunction in the training pipeline. Offline methods can provide an initial high-quality dataset, while online methods can further optimize the training process by selecting the most informative batches during runtime. This potential synergy between offline and online data selection is an interesting direction for future research. \n\n**Additional baselines:** As suggested by other reviewers, we have expanded our comparisons to include reference model-based online batch selection techniques [3] and embedding similarity-based batch selection. Our results show that GREATS **consistently outperforms** these baselines across various hyperparameter settings, further validating its effectiveness. See **Q1 in global response** for a detailed discussion. \n\n[1] Xie, Sang Michael, et al. \"Data selection for language models via importance resampling.\" NeurIPS 2023.\n\n[2] Xie, Sang Michael, et al. \"Doremi: Optimizing data mixtures speeds up language model pretraining.\" NeurIPS 2024.\n\n[3] Mindermann, Sören, et al. \"Prioritized training on points that are learnable, worth learning, and not yet learnt.\" ICML 2022.\n\n**Q. [Experiment with different hyperparameters]** \n\n**A.** As suggested, we have performed experiments with different choices of learning rates and batch sizes. Our results show that GREATS **consistently performs** well across all the hyperparameter configurations we considered. This robustness suggests that GREATS can maintain its effectiveness without requiring extensive hyperparameter tuning. An ablation study on the number of validation points in Figure 3 (a)-(b) of the paper. This study demonstrates that GREATS can perform effectively even with a small number of validation points (2 to 5), which is a crucial aspect of its practical applicability.\n\n**Q. [Potential distribution shift between validation and test distribution?]**\n\n**A.** \nWe appreciate the reviewer's insightful question. **Subsampling validation data** is one solution here. This subsampling approach effectively reduces overfitting to the validation set and introduces some variability in the selection process, which can help mitigate the impact of potential distribution mismatches.\n\nWe acknowledge that the availability of a high-quality validation set is a limitation of GREATS. However, most state-of-the-art data selection (e.g., [1, 2]) and online batch selection techniques (e.g., [3]) rely on a high-quality validation set. This is a common approach in the field to guide the selection process toward data that aligns with the target domain or task. In finetuning tasks, practitioners typically have a small set of high-quality, task-specific data that can serve as a validation set. Our experiments demonstrate that **GREATS can perform well even with a very small validation set** (as few as 2-5 samples), which makes the requirement more practical to fulfill in many scenarios. We stress that while GREATS does require a validation set, it avoids other limitations of existing methods, such as the need for reference models, making it more practical for large-scale training scenarios.\n\n[1] Xia, Mengzhou, et al. \"LESS: Selecting Influential Data for Targeted Instruction Tuning.\" ICML 2024. \n\n[2] Xie, Sang Michael, et al. \"Data selection for language models via importance resampling.\" NeurIPS 2023. \n\n[3] Mindermann, Sören, et al. \"Prioritized training on points that are learnable, worth learning, and not yet learnt.\" ICML 2022.\n\n**Q [Do the experiments use Adam optimizer?]** \n\n**A.** **In all of our experiments, we use AdamW as the optimizer for model training.** This aligns with common practices in training large language models. We acknowledge that our theory for GREATS is derived in terms of SGD. While the theory can be extended to Adam, the efficient \"ghost\" inner-product technique we developed is specifically tailored for SGD and is challenging to directly adapt to Adam due to its more complex update rule and maintained moments. Hence, we adopt a hybrid approach where we select the valuable batch based on the theory derived from SGD, but perform the actual training updates using AdamW. This approach allows us to benefit from the computational efficiency of our SGD-based selection method while still leveraging the optimization benefits of AdamW for training. Despite this theoretical mismatch, our experiments demonstrate that this hybrid approach performs well in practice. The consistent improvements over baselines across various models and tasks suggest that the SGD-based utility function provides a good proxy for data importance, even when Adam is used for training. We recognize the potential for further improvement by aligning the batch selection more closely with Adam-style updates.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "VakNFALFmo", "reviewer": "Reviewer_oEUR", "summary": "The paper presents an online adaptive subset selection framework GREATS which acts as a principled and efficient online batch selection. The authors further showcase their proposal's utility towards training for Large language models training thereby better performance during training", "questions": "NA", "limitations": "The authors have clearly mentioned about their proposed limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper for is well written, easy to follow.\n- Contributions are well formulated and clearly stated.\n- The paper's proposal is well-suited towards better efficient training in Large language model training as authors show extensive experiments in practical utility of their proposal towards efficient LLM training.", "weaknesses": "Notation could be a bit better:\n- For instance under definition of $\\textbf{Utility Function}$, $U^{(t)}: \\mathrm{R}^d \\rightarrow \\mathrm{R}^d$ denotes the utility function mapping the training set to an optimal batch. \n- vector notations should be bold\n\nMany adaptive subset selection techniques have been shown to be either submodular or weakly submodular. As in either case, submodular functions provide better functionality. It would have been interesting to see if the proposed utility function which is essentially the loss w.r.t validation data satisfies some form of submodularity. Some form of theoretical justification would be highly appreciated.\n\n\nExperiment comparison wise:\n- Regarding baselines, I am wondering why authors have not tried any baseline comparison against submodular subset selection techniques. Some examples: https://proceedings.mlr.press/v139/killamsetty21a. Subset selection techniques is often to show better in many cases.\n\nI am willing to increase my rating if this questions can be addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q. [Notation]**\n\n**A.** We thank the reviewer for the suggestions on the notations, which we will incorporate into our revision. We note that the utility function $U^{(t)}: R^d \\rightarrow R$ maps to the model performance change in $t$th step instead of the optimal batch. \n\n**Q. [Is the proposed utility function close to submodular?]**\n\n**A.** \nWe sincerely appreciate the reviewer's insightful question. We conducted additional experiments and in **Global response’s Figure 5 (c)**, we plot how the loss change in a single gradient update step, i.e., our utility function $U^{(t)}(S)$, against  varying input batch sizes $|S|$. We observed that as batch sizes increase, the average loss change (computed across randomly sampled subsets of fixed sizes) indeed exhibits a \"diminishing returns\" trend. This behavior is consistent with the general properties of submodular functions. However, we also noted significant variance in the utilities, especially for smaller batch sizes. This high variance suggests that strict submodularity may not hold. The observed \"diminishing returns\" trend aligns with the intuition behind submodular functions and provides some justification for the effectiveness of our greedy selection approach. While our utility function may not be strictly submodular, we conjecture that it could potentially fall into the category of weakly submodular functions. \n\nWe will incorporate this analysis into our paper, which might open up interesting theoretical directions for future work. \n\n**Q. [Discussion on submodular subset selection techniques]**\n\n**A.** We sincerely appreciate the reviewer for bringing our attention to the relevant literature on submodular subset selection techniques. \nTo the best of our knowledge, gradient coreset-based online data selection algorithms, including those utilizing submodular optimization (like [1]), generally face scalability challenges when applied to the setting of foundation models. The primary limitation stems from their requirement to compute (or even store) per-sample gradient vectors, which becomes prohibitively expensive in terms of both computation (or memory) for large-scale models with millions or billions of parameters. For instance, if we understand correctly, to optimize the resulting error in [1], the computation of $Err$ requires computing per-sample gradient vectors. An interesting future avenue is to explore whether our \"ghost inner product\" technique can be further extended to address the computational problems in this line of work. \nWe will incorporate these references and discussion into our related work section in the revision. \n\n**Additional baselines:** As suggested by other reviewers, we have expanded our comparisons to include reference model-based online batch selection techniques [2] and embedding similarity-based batch selection. Our results show that GREATS consistently outperforms these baselines across various hyperparameter settings, further validating its effectiveness. See **Q1 in global response** for a detailed discussion. \n\n[1] Killamsetty, Krishnateja, et al. \"Grad-match: Gradient matching based data subset selection for efficient deep model training.\" ICML 2021\n\n[2] Mindermann, Sören, et al. \"Prioritized training on points that are learnable, worth learning, and not yet learnt.\" ICML 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "M4cArrxQcz", "reviewer": "Reviewer_SyBn", "summary": "The paper introduces a well-motivated online data selection method based on Taylor series expansions (with additional approximations) and apply it to training/fine-tuning LLMs. The paper's results show good performance improvements on fine-tuning tasks, but little gains on pre-training tasks.", "questions": "- It is unclear when the Hessian is set to the identity in all GREATS experiments. I assume H=I always, as otherwise the runtime would blow up. Is this assumption correct?\n\n- How did you choose the (up to 16) validation dataset points? Randomly?", "limitations": "The authors have moderately addressed the limitations of their work. I've pointed out what else I was expecting to see in the weaknesses section.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is very well motivated, and tackles a problem which has clear significance to large scale model training.\n\nThe problem setup is very intuitive and straightforward: select the data points now which would maximize utility after one model update step.\n\nThe paper is also relatively well written. The method is clearly derived and explained -- most/each introduced approximation is accompanied by a clear interpretation.  I most enjoyed reading section 3.2 -- splitting out the importance score of a sample and correcting it based on the scores of previously seen samples is very neat.\n\nThe paper includes several relevant experiments (most on fine-tuning) -- using a few relevant baselines. The results appear strong, in general, when compared to the selected baselines.", "weaknesses": "I gave the paper a rating of 5 mostly because of the limited evaluation. Simple baselines are just missing from the paper, e.g.: (1) a classifier to detect similarity to validation data and (2) rho loss. I would be happy to increase my rating if these baselines are added to the paper.\n\nTo clarify, regarding rho loss, I do not find the argument in line 262-263 at all convincing. In a separate pass, you can just label the training data with per token losses from a pre-trained reference model. No extra training flops needed over the \"Max Loss\" baseline.\n\nNote that influence functions [Koh & Liang] (in the context of LLMs too [Grosse et al.]) are not discussed anywhere, even though they are closely related with the method proposed here. The difference is that influence functions look at final performance and the paper here looks at 1-step performance. It would be great to see what happens when consider n-step unrolls, i.e., and use the influence functions formulation -- of course, this could be left specifically for future work.\n\nThe runtime complexity (i.e. number of flops) of the GREATS algorithm is missing (under every condition) and is not compared to that of regular training. Indeed runtime comparisons (i.e. in seconds) are useful, they are a bit incomplete.\n\nA minor point is that the argument in lines 28-29 is tenuous at best (\"Moreover, online batch selection operates on smaller batches of data, reducing the need for cumbersome data preprocessing and enabling more efficient use of computational resources compared to static data selection methods that process the entire dataset upfront\".) It is much more convenient to pre-cache the data when training these models. At training time, one really just wants to use accelerators as efficiently as possible. \n\n[Koh & Liang] Understanding Black-box Predictions via Influence Functions\n[Grosse] Studying Large Language Model Generalization with Influence Functions", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments!\n\n**Q. [Additional Baseline Comparison.]**\n\n**A.** We sincerely appreciate the reviewer's feedback and suggestions for additional baselines. We have taken these recommendations seriously and have expanded our comparisons accordingly. **(1) Reference model-based online batch selection (RHO Loss) [1]**: We have implemented and evaluated the RHO Loss method as suggested. **(2) Similarity to validation data:** Regarding the suggestion of *\"a classifier to detect similarity to validation data,\"* we note that our validation sets are very small, which may not be sufficient to train a robust classifier. Instead, we implemented a method that selects the training batch based on embedding similarity to the validation data, using Sentence-BERT embeddings. This approach serves as a proxy for the suggested classifier-based method while being applicable to our small validation set scenario.\n\nOur expanded experiments show that GREATS consistently outperforms these additional baselines across various hyperparameter settings, further validating its effectiveness. We have included a detailed discussion of these results in **Q1 in global response**. \n\n[1] Mindermann, Sören, et al. \"Prioritized training on points that are learnable, worth learning, and not yet learnt.\" ICML 2022.\n\n**Q. [Relationship to the influence function.]**\n\n**A.** We appreciate the reviewer's insightful comment regarding the relationship between our proposed method and influence functions. Influence functions typically assume strong convexity of the loss landscape and convergence to a local optimum. In contrast, our method makes no such assumptions, making it more suitable for the highly non-convex landscapes encountered in large language model training. While influence functions focus on the impact of training examples on the final model performance, our method explicitly considers the immediate impact on the next training step. This allows us to capture the dynamic nature of the training process and adapt to the model's current state. We will incorporate this discussion into the related work section. \n\n**Q. [Runtime complexity of GREATS?]**\n\n**A.** We appreciate the valuable suggestion! Here’s the complexity analysis for GREATS: Assuming that the batch size is $B$ and the number of model parameters is $p$, the complexity of backpropagation is $O(Bp)$. \nThe additional cost of the \"ghost\" dot-product involves computing the pairwise dot-product between each data point’s activation (or output derivative), which are of dimension $O(\\sqrt{p})$, and then taking the scalar product between the inner product results on activations and output derivatives. The step of computing the pairwise activation (or output derivative) dot-products has a runtime complexity of $O(B^2 \\sqrt{p})$, resulting in a $B \\times B$ matrix. Taking the element-wise product between the two $B \\times B$ matrices has a runtime complexity of $O(B^2)$. Hence, the overall runtime complexity is $O(Bp) + O(B^2 \\sqrt{p})$. In practice, since the batch size $B$ is significantly smaller than the number of parameters $p$, the additional runtime $O(B^2 \\sqrt{p})$ is negligible compared to the backpropagation complexity $O(Bp)$. This analysis explains why our empirical runtime measurements (in seconds) show that GREATS performs comparably to regular training. We will incorporate this detailed complexity analysis into our paper to provide a more comprehensive understanding of the algorithm's efficiency. Thank you for highlighting this important aspect!\n\n\n\n**Q.** “*A minor point is that the argument in lines 28-29 is tenuous at best (\"Moreover, online batch selection operates on smaller batches of data, reducing the need for cumbersome data preprocessing and enabling more efficient use of computational resources compared to static data selection methods that process the entire dataset upfront\".) It is much more convenient to pre-cache the data when training these models. At training time, one really just wants to use accelerators as efficiently as possible.*”\n\n**A.** We appreciate the reviewer’s valuable comments. We agree with the reviewer and acknowledge that offline data selection provides the convenience for not modifying training pipeline. We will include this point and modify the Introduction accordingly. On the other hand, online batch selection offers unique advantages in terms of adaptability to the model's learning progress. This can be particularly valuable in scenarios where the relevance of data may change as training progresses. Furthermore, offline and online selection methods are not mutually exclusive and can be complementary. A hybrid approach, leveraging both pre-cached, pre-selected data and dynamic online selection, could potentially offer the best of both worlds. \n\n**Q. [Hessian approximation used in the experiments?]**\n\n**A.** In all of our experiments, we use identity matrix as the approximation to the Hessian matrix, and we found the performance is already good. Future work can further explore the use of more advanced techniques for Hessian approximation, such as K-FAC [1]. \n\n[1] Martens, James, and Roger Grosse. \"Optimizing neural networks with kronecker-factored approximate curvature.\" ICML 2015. \n\n**Q. [How to choose the validation data?]**\n\n**A.** In the standard benchmarks such as MMLU, the validation data is being provided for each subject of size 5. For the benchmarks where the validation set size is large, we sample the validation set used in the experiments uniformly at random. We will incorporate this additional detail into our experiment setting section.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "ypNRxXsbHd", "reviewer": "Reviewer_tC7z", "summary": "This paper proposes a novel online batch selection algorithm called GREedy Approximation Taylor Selection (GREATS) for training large language models (LLMs). The algorithm aims to improve training convergence speed and generalization performance by selecting informative and diverse examples for model updates. GREATS uses a principled formulation of the online batch selection problem and leverages greedy algorithms and Taylor expansions to approximate the utility of data points. This paper presents extensive experiments on various LLM tasks to demonstrate the effectiveness of GREATS in improving training performance.", "questions": "Why are uniform selection and selection-via-Proxy [*1] not included as baselines?\n\n[*1] Selection via proxy: Efficient data selection for deep learning, ICLR 2020.", "limitations": "The authors have addressed the limitations in the main text.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) This paper presents a novel online batch selection algorithm that addresses the limitations of existing methods and significantly improves training convergence speed and generalization performance.\n2) The algorithm is based on a principled formulation and uses innovative techniques such as greedy algorithms and Taylor expansions to approximate the utility of data points.\n3) This paper provides comprehensive evaluations on various LLM tasks, demonstrating the robustness and versatility of GREATS.", "weaknesses": "1) The authors only consider MaxLoss and GradNorm as baselines, they do not compare GREATS with other state-of-the-art online batch selection methods.\n2) No confidence intervals in any of the tables, which makes it hard to gauge the significance of the accuracy gains.\n3) The authors only report accuracy on MMLU and TYDIQA test sets, I cannot find the results of other datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback!\n\n**Q. [Additional Baseline Comparison.]** *\"Why are uniform selection and selection-via-Proxy not included as baselines?\"*\n\n**A.** We thank the reviewer for bringing up potentially additional baselines. If we understand correctly, the “uniform selection” baseline corresponds to the “Regular” curve in our current experiments, where the training batches are sampled uniformly at random. For “Selection-via-proxy”, our understanding is that it is a general paradigm for accelerating offline data selection. We'd like to clarify that **offline data selection techniques are not competitors to online batch selection methods** like GREATS. Instead, these approaches are complementary and can be used in conjunction in the training pipeline. Offline methods can provide an initial high-quality dataset, while online methods can further optimize the training process by selecting the most informative batches during runtime. This potential synergy between offline and online data selection is an interesting direction for future research. \n\nAs suggested by the reviewers, we have expanded our comparisons to include reference model-based online batch selection techniques [1] and embedding similarity-based batch selection. Our results show that GREATS consistently outperforms these baselines across various hyperparameter settings, further validating its effectiveness. See **Q1 in global response** for a detailed discussion. \n\n[1] Mindermann, Sören, et al. \"Prioritized training on points that are learnable, worth learning, and not yet learnt.\" ICML 2022.\n\n**Q. [Error bar for the experiment results?]**\n\n**A.** We sincerely appreciate the reviewer's insightful suggestion. We have updated the experiment results for key benchmarks with error bars across 3 independent runs. \n\n   |                     | Regular        | GradNorm       | MaxLoss        | GREATS (Ours)  |\n   |---------------------|----------------|----------------|----------------|----------------|\n   | MMLU - sociology    | 62.7% (±0.9)   | 61.0% (±0.5)   | 63.9% (±0.8)   | **66.1% (±0.8)**  |\n   | MMLU - us_foreign_policy | 60.1% (±0.8) | 62.2% (±1.4) | 60.2% (±1.2) | **65.8% (±2.2)**   |\n   | TYDIQA              | 54.3% (±0.3)   | 53.4% (±0.18)  | 54.7% (±0.13)  | **55.0% (±0.3)**   |\n\n\nThese updated results with error bars further solidify our findings. GREATS consistently outperforms all baselines across these key benchmarks, even when accounting for run-to-run variability. We've also added error bars to the loss curves for these experiments (see **Q1 in global response**) which show similar results. Due to the computational intensity nature of some experiments, we are in the process of extending this multiple-run analysis to the Alpaca-Samsum and OpenWebText (pretraining) settings. We're committed to providing a complete picture of GREATS' performance across all benchmarks in the revision.\n\n**Q. [Accuracy results for other datasets?]**\n\n**A.** We thank the reviewer for the valuable comment! \n\n**OpenWebText Pretraining:** For our GPT2 pretraining on OpenWebText, we primarily focused on test loss as the most appropriate metric. This choice was made due to the nature of pretraining (where the model is not instruction-tuned) and our computational constraints. Test loss provides a direct measure of the model's ability to predict the next token, which is the core objective of language model pretraining.\n\n**Alpaca-Samsum:** Since Samsum is a summarization task, we evaluated the model's performance using the ROUGE-1 score, which is a standard metric for summarization quality. Here are the additional experiment results on Samsum's test set: \n\n| | Regular  | GradNorm | MaxLoss | GREATS (Ours) |\n|----------|----------|----------|----------|----------|\n| ROUGE-1    | 35.78% (±0.1)  | 35.91% (±0.03) | 35.65%(±0.24)  | **36.74%(±0.46)**    |\n\nAs we can see, GREATS outperforms all baselines on this metric, further demonstrating its effectiveness across diverse task types.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:
We thank all the reviewers for the positive assessments!

**Q1 [Additional baseline comparisons & hyperparameter choices]** 

**A.** We appreciate the reviewers' suggestions for additional baseline comparisons and hyperparameter sensitivity analysis. In response, we have conducted extensive additional experiments in **Figure 1-4 in the attached pdf**. 

**Additional Baseline Comparisons.** 
- **Reference model-based online batch selection [1] (Reviewers 2jYA, SyBn)**: We implemented the RHO-Loss method from [1] as a representative baseline for reference model-based approaches. As suggested by Reviewer SyBn, we use a pretrained LLM as the reference model. Due to time and computational constraints, we used Llama-3.1-8B-Instruct as the reference model (with Llama2-7B as the target model), prioritizing training on data points with high RHO loss ($L(x; f_{tgt}) - L(x; f_{ref})$ where $f_{tgt}$ is the target model and $f_{ref}$ is the reference model). Surprisingly, the RHO-Loss method performed poorly, showing the worst performance across almost all settings. We hypothesize two potential reasons here: **(1) Noise and scale discrepancy:** The loss value from the current target model $L(x; f_{tgt})$ is highly noisy and may be of a different scale compared to the reference model. This discrepancy could result in $L(x; f_{ref})$ having minimal impact on the batch selection results. **(2) Reference model limitations:** Due to computational and time constraints, we used a relatively small pretrained model as the reference. This may not adequately reflect the "learnability" or "difficulty" of the training examples, which is crucial for effective data selection. These findings highlight a key advantage of GREATS: it offers a more efficient and flexible alternative that can perform well **without relying on reference models**, which may not be available in practice. 
- **Similarity-based batch selection (Reviewer SyBn)**: We implemented a baseline that selects training batches based on their similarity to validation data using Sentence-BERT embeddings. This approach also did not outperform GREATS.

**Hyperparameter Sensitivity Analysis.** We repeated MMLU experiments with various hyperparameter settings, including different batch sizes and learning rates. Each experiment was run with 3 different random seeds, and we have included error bars in our plots to reflect the variability. Across these expanded comparisons and varied hyperparameter settings, GREATS **consistently outperformed** all baselines. This robust performance across different scenarios further validates the effectiveness and stability of our proposed method.

[1] Mindermann, Sören, et al. "Prioritized training on points that are learnable, worth learning, and not yet learnt." ICML 2022.

**Q2 [Do the experiments use Adam optimizer?] (for Reviewer 2jYA and vNzN)** 

**A.** **In all of our experiments, we use AdamW as the optimizer for model training.** This aligns with common practices in training large language models. We acknowledge that our theory for GREATS is derived in terms of SGD. While the theory can be extended to Adam, the efficient "ghost" inner-product technique we developed is specifically tailored for SGD and is challenging to directly adapt to Adam due to its more complex update rule and maintained moments. Hence, we adopt a hybrid approach where we select the valuable batch based on the theory derived from SGD, but perform the actual training updates using AdamW. This approach allows us to benefit from the computational efficiency of our SGD-based selection method while still leveraging the optimization benefits of AdamW for training. Despite this theoretical mismatch, our experiments demonstrate that this hybrid approach performs well in practice. The consistent improvements over baselines across various models and tasks suggest that the SGD-based utility function provides a good proxy for data importance, even when Adam is used for training. We recognize the potential for further improvement by aligning the batch selection more closely with Adam-style updates.

Meta-review: This paper tackles a significant problem: dynamically selecting data batches during training to improve efficiency for large-scale LLM training. The proposed algorithm, GREATS, formulates batch selection as an optimization problem and employs greedy algorithms and Taylor expansions to approximately t solve the optimization problem. Additionally, it proposes a "ghost inner product" method for efficiently computing pairwise gradient inner products within a single backprop step. The empirical results are comprehensive and demonstrate strong performance in improves training convergence speed and generalization performance when compared to relevant baselines.
Decision: Accept (spotlight)