Conceptio › Archive › arXiv CS

arXiv CSopen access

GRACE: A Dynamic Coreset Selection Framework for Large Language Model Optimization

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

databases datamanagement sql storage

databases, sql, data management, storage

GRACE: A Dynamic Coreset Selection Framework for Large Language Model Optimization Tianhao Tang

Haoyang Li

Lei Chen

CSE, HKUST Hong Kong SAR [email protected]

Computing, PolyU Hong Kong SAR [email protected]

DSA, HKUST (GZ)&HKUST Guangzhou, China [email protected]

arXiv:2604.11810v1 [cs.DB] 9 Apr 2026

Abstract Large Language Models (LLMs) have demonstrated remarkable capabilities in natural language understanding and generation. However, their immense number of parameters and complex transformerbased architectures result in significant resource demands and computational complexity during training, making it challenging to optimize them efficiently on large datasets. To reduce training costs while preserving performance, researchers have investigated coreset selection techniques, which aim to identify small, representative subsets of the entire training dataset to accelerate LLM training. However, existing coreset selection methods fail to adapt to the dynamic nature of LLM training and often struggle with scalability for models of this size. To address these limitations, we propose a graph-guided adaptive and dynamic coreset selection framework for LLMs, namely GRACE. GRACE dynamically constructs and updates coresets by combining representation diversity with gradientbased importance metrics, ensuring both informativeness and efficiency. To mitigate the computational cost of frequent updates, GRACE leverages a 𝑘-NN graph-based propagation mechanism and selectively updates scores and embeddings, adapting to evolving training dynamics. Extensive experiments on three benchmarks demonstrate that GRACE significantly improves training efficiency and downstream performance across diverse LLMs and tasks.

Keywords Large Language Model, coreset, data selection, adaptive training ACM Reference Format: Tianhao Tang, Haoyang Li, and Lei Chen. 2018. GRACE: A Dynamic Coreset Selection Framework for Large Language Model Optimization. In Proceedings of Make sure to enter the correct conference title from your rights confirmation email (Conference acronym ’XX). ACM, New York, NY, USA, 19 pages. https://doi.org/XXXXXXX.XXXXXXX

Introduction

Large language models (LLMs) [2, 3, 42, 59], such as GPT [59], LLaMA [2, 3], and DeepSeek [18], have demonstrated remarkable abilities in understanding and generating human-readable Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. Conference acronym ’XX, Woodstock, NY © 2018 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-1-4503-XXXX-X/2018/06 https://doi.org/XXXXXXX.XXXXXXX

language, emerging as novel approaches for interacting with database systems. Their strengths in tasks such as natural language query processing [39, 84], knowledge extraction [6, 36], and data summarization [36] make them particularly valuable for assisting in managing database systems [24, 72, 85], such as constructing and simplifying complex queries [47, 61] or facilitating efficient data exploration [36, 52]. In general, LLMs are primarily built on the Transformer architecture [67], featuring billions of parameters (e.g., Llama-3 with 7∼65 billion parameters) and trained on massive datasets. This design enables them to capture intricate data patterns, following an autoregressive training scheme that predicts the next token based on previous context. The training objective is to maximize the likelihood of correct token sequence. Despite their impressive performance, LLMs present significant challenges regarding the computational demands of training. Specifically, given 𝑁 training samples with an average sequence length 𝑇 , and an LLM with 𝐿 layers and hidden dimension 𝑑, the time complexity of training this LLM on the entire dataset once (i.e., one epoch) is 𝑂 (𝑁 𝐿(𝑑𝑇 2 + 𝑑 2𝑇 )). This complexity is determined by both the size of the data and the architecture of the model, specifically the sequence length, hidden size, and total number of parameters [29, 42]. Therefore, considering the large number of parameters in models such as LLMs, it is challenging and resourceintensive to optimize LLMs on new corpora or downstream task datasets. Recently, parameter-efficient fine-tuning (PEFT) methods [21, 26, 30, 31, 44] such as LoRA [31] have been proposed. These methods introduce a small fraction of trainable parameters while freezing the rest, achieving performance comparable to full finetuning. However, effective task and domain adaptation with PEFT methods still requires processing millions of tokens and substantial GPU resources. To accelerate model training and fine-tuning, recent research has proposed selecting a small and representative coreset from the entire training dataset and optimizing the model on this coreset instead of the full dataset [11, 12, 25, 68]. The coreset is designed to preserve the statistical and structural properties of the original data, ensuring that training on it achieves comparable model performance. By prioritizing the most informative and diverse samples, coreset selection reduces redundancy, improves training speed, and lowers resource consumption. The coreset selection technique has been highly successful in accelerating the training of neural networks, including graph neural networks [40, 41, 46] and convolutional neural networks [12, 37, 56, 82]. Depending on the technique, existing approaches can be categorized into three types: dataproperty-based, uncertainty-based, and gradient-based approaches. Specifically, data-property-based approaches [11, 13, 46, 65] select coresets based on intrinsic properties of the data, such as feature

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

similarity or diversity. While these methods are simple and efficient for selection, they overlook information about model-specific learning difficulties for the target models. Also, uncertainty-based methods [5, 7, 54, 74] first obtain the prediction probabilities or loss values from the target model on each training sample and construct the coreset by prioritizing uncertain samples, such as those with incorrectly predicted labels. However, these selection methods require a full evaluation of samples using the target model, which is computationally intensive, especially for LLMs. Also, the uncertainty metrics do not directly correlate with the gradient optimization procedure, and thus the selected samples are not sufficiently beneficial for training. Further, gradient-based methods [34, 58, 71, 77] utilize gradient information, which explicitly encodes how each sample affects model updates during optimization. These methods construct coresets by prioritizing samples with larger gradient magnitudes or by solving a gradient-matching problem to approximate the gradients of the full dataset using a smaller subset. However, due to the high dimensionality and significant computational cost of calculating gradients for LLMs with billions of parameters, these approaches often encounter efficiency and scalability challenges when applied to LLMs [29, 75]. More importantly, the above methods select a static coreset before model training, failing to adapt to the evolving training dynamics of LLMs. Although some approaches dynamically update coresets at fixed intervals using intermediate metrics like sample losses or gradients [76, 77], they cannot accurately align with real-time model dynamics, often resulting in unnecessary updates and excessive computational overhead. In this paper, we propose an adaptive and dynamic coreset selection framework for LLMs. We construct dynamic coresets based on gradient matching during training and adaptively update them to efficiently capture important training information. However, directly constructing dynamic coresets presents several technical challenges, as outlined below: C1: While the gradient matching problem has been studied in conventional deep learning models (e.g., CNNs), its application to LLMs introduces unique challenges. The vast scale and complex transformer architecture of LLMs result in prohibitive computational costs and a lack of theoretical guarantees for coreset selection in transformer-based LLMs. C2: Dynamic coreset selection for LLMs inherently requires multiple evaluations of data samples, which results in high computational costs, even for forward passes through the model. Therefore, designing an effective metric and algorithm to select coresets for LLMs with billions of parameters is critical for accelerating LLM training. C3: Beyond simply updating the coreset based on a manually defined epoch interval, determining the optimal moment to update the coreset is nontrivial. A naive approach that repeatedly solves the matching problem leads to excessive computational overhead, which impedes efficiency. To address these challenges, we propose GRACE, a GRaphguided Adaptive and Dynamic Coreset sElection framework that selects coresets for transformer-based LLMs and adaptively updates them using graph-based approximations. First, we conduct a theoretical analysis of gradient calculations in LLMs based on transformer architectures. Building on this analysis, we formalize

Tang et al.

the coreset selection problem, incorporating both feature-coverage representation scores and gradient-related importance scores to ensure diversity and informativeness in the selected coreset. Since the problem is NP-hard, we design an efficient greedy algorithm with a provable approximation ratio. Secondly, to adaptively update the coreset during training, we propose an adaptive checking strategy to periodically check for value changes in gradient-related scores during training. Additionally, since recalculating all dynamic indicators is expensive, we propose to exploit data similarity properties by constructing a 𝑘-NN graph based on the data representations. When an update is required, instead of recalculating scores or representations for all samples, we leverage the historical indicators saved during training and selectively recompute indicators for a subset of the full data, propagating the update to similar samples through the graph structure. This enables an efficient way to update dynamic indicators with evolving LLMs and ensures the coreset remains effective. To summarize, our contributions are as follows: • We propose a dynamic and adaptive coreset selection framework, GRACE, for LLM training and fine-tuning. GRACE dynamically constructs and updates coresets based on the training dynamics, with an adaptive mechanism to determine update moments. • We provide a theoretical analysis of the gradient matching problem for transformer-based LLMs. This analysis enables the formulation of a tractable coreset selection objective that balances feature coverage and gradient-based importance, offering a foundation for efficient coreset construction in LLM training. • To address the inefficiency of frequent full recomputation, GRACE employs a graph-guided update mechanism. The framework constructs a 𝑘-NN graph and uses training history to model data similarity, allowing selective recomputation of scores and embeddings, as well as efficient approximation of graph updates. An adaptive checking strategy identifies when updates are necessary, thereby further reducing computational overhead. • Extensive experiments on the MathInstruct, BioInstruct, and DialogSum benchmarks demonstrate that GRACE significantly improves training efficiency and downstream performance across diverse tasks.

Preliminary and Related Works

In this section, we first introduce the preliminaries of LLMs and then discuss existing coreset selection approaches. Important notations used in this paper are summarized in Table 1.

2.1

Large Language Model and Training

2.1.1 Large Language Models. Large language models (LLMs) [42], such as GPT [59], LLaMA [2, 3], and DeepSeek [18], are trained on extensive datasets (e.g., corpora). These models have demonstrated exceptional abilities in text understanding and analysis, which have been applied to a wide range of tasks, such as database tuning [24], query optimization [22], and data integration [36, 57]. Besides the extensive training data, the success of LLMs also relies on the transformer architecture. LLMs are composed of multiple transformer blocks [67] with billions of parameters, which enable LLMs to capture long-range dependencies within input sequences and autoregressively generate output sequences.

GRACE: A Dynamic Coreset Selection Framework for Large Language Model Optimization

Given any natural language input, it is first processed by a tokenizer to break the sentence into a sequence 𝑋 = (𝑥 1, 𝑥 2, . . . , 𝑥𝑇 ) of length 𝑇 , where each token represents a word or sub-word. Each token 𝑥𝑖 is then mapped to an embedding x𝑖 , forming the initial hidden representation X = [x1, x2, . . . , x𝑇 ] ∈ R𝑇 ×𝑑 , where 𝑑 is the hidden dimension of the LLM. The transformer processes the embeddings through 𝐿 layers of transformer blocks. Each transformer block consists of a multi-head self-attention (MHSA) mechanism module followed by a feed-forward network. Specifically, given the input H (𝑙 −1) to the transformer block at layer 𝑙 and H (0) = X, the MHSA mechanism applies self-attention across 𝑛ℎ attention heads. The self-attention operation for each head 𝑖 ∈ {1, · · · , 𝑛ℎ } is computed as: Q𝑖(𝑙 ) = H (𝑙 −1) W𝑄(𝑙𝑖) ,

(1)

K𝑖(𝑙 ) = H (𝑙 −1) W𝐾(𝑙𝑖) ,

(2)

V𝑖(𝑙 ) = H (𝑙 −1) W𝑉(𝑙𝑖 ) , ! Q𝑖(𝑙 ) (K𝑖(𝑙 ) ) ⊤ (𝑙 ) Z𝑖 = softmax V𝑖(𝑙 ) √ 𝑑𝑘

(3) (4)

where Q𝑖(𝑙 ) ∈ R𝑇 ×𝑑𝑘 , K𝑖(𝑙 ) ∈ R𝑇 ×𝑑𝑘 , and V𝑖(𝑙 ) ∈ R𝑇 ×𝑑 𝑣 are the learned Query matrix, Key matrix, and Value matrix. Also, W𝑄(𝑙𝑖) ,

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Table 1: Important notations. Notation 𝑋 , 𝑥𝑖 ,𝑇 X, x1 (𝑙 ) H𝑖 (𝑙 ) H̄𝑖 (𝑙 Z ) , Ô 𝑃ˆ𝜽 (𝑋 ) 𝑃ˆ𝜽 (𝑥𝑖 |𝑥 <𝑖 ) D𝑡𝑟𝑎𝑖𝑛 D𝑡𝑒𝑠𝑡 D𝑐𝑜𝑟𝑒 M𝜽 , 𝐿 L (𝑋𝑖 , 𝜽 ) ∇𝜽 L (𝑋𝑖 , 𝜽 ) ∇Ô L (𝑋𝑖 , 𝜽 ) 𝐺 𝑅 (·), 𝐼 (·) 𝜆, 𝛿 𝑏 T Δ𝐼 , ΔH 𝐼 𝑛𝑒𝑤 (𝑋𝑖 ) H̄𝑛𝑒𝑤 (𝑋𝑖 )

Description Input sequence, 𝑖-th token, sequence length Initial hidden states, 𝑖-th token’s embedding Hidden states of 𝑋𝑖 after 𝑙-th layer Mean hidden states of 𝑋𝑖 along sequence MHSA output at 𝑙-th layer, predicted logits Predicted probabilities of sample 𝑋 Predicted probabilities of 𝑖-th output token Training dataset Test dataset Selected coreset LLM with parameters 𝜽 , LLM layer size Prediction loss of sequence 𝑋𝑖 Gradient w.r.t model parameters Gradient w.r.t logits outputs Graph built from training data Representation score, importance score Balance coefficient, update check threshold Selection budget in size Total number of training steps Change of importance score and embedding Importance score after updates Mean hidden states after updates

W𝐾(𝑙𝑖) , and W𝑉(𝑙𝑖 ) are learnable weight matrices that project the input H𝑖(𝑙 −1) into query, key, and value spaces, respectively. The outputs of all attention heads are then concatenated and projected with an output weight W𝑂(𝑙 ) to produce the final MHSA output: h i Z (𝑙 ) = CONCAT Z1(𝑙 ) , ..., Z𝑛(𝑙ℎ) W𝑂(𝑙 ) (5)

2.1.2 Large Language Model Training. The training loss leverages an autoregressive paradigm to maximize the correct next-token prediction. The loss function of learning a sequence is defined as: 𝑇

L (𝑋, 𝜽 ) = − And this is followed by a feed-forward network: F (Z (𝑙 ) ) = W2(𝑙 ) 𝜎 Z (𝑙 ) W1(𝑙 ) + b1(𝑙 ) + b2(𝑙 )

(6)

where W1(𝑙 ) and W2(𝑙 ) are weight matrices, b1(𝑙 ) and b2(𝑙 ) are bias vectors, and 𝜎 (·) denotes the activation function (e.g., ReLU). Combining these components, the hidden representation of the sequence is updated at each layer 𝑙 = 1, 2, . . . , 𝐿 as follows: H (𝑙+1) = H (𝑙 ) + F (H (𝑙 ) + A (H (𝑙 ) )) For simplicity, we omit the normalization operation and positional encoding in the transformer block. After passing through 𝐿 layers, the final hidden state H (𝐿) is then projected to the token vocabulary space by a final projection matrix Wℎ , resulting in the predicted outputs Ô = H (𝐿) Wℎ ∈ R𝑇 ×𝑛 𝑣𝑜𝑐𝑎𝑏 . The token-wise probabilities are then obtained by applying a softmax function row-wise. Specifically, unlike autoregressive inference that generates tokens sequentially, the training procedure is fully parallel: the entire input sequence is available and processed at once. This allows the model to compute all token-level predictions simultaneously and enables efficient loss and gradient computation with respect to the full output logits, as follows: 𝑃ˆ𝜽 (𝑋 ) = softmax( Ô) ∈ [0, 1]𝑇 ×𝑛 𝑣𝑜𝑐𝑎𝑏 where 𝑛 𝑣𝑜𝑐𝑎𝑙 is the vocabulary size and 𝜽 is the parameter of the large language model.

1 ∑︁ log 𝑃ˆ𝜽 (𝑥𝑖 |𝑥 <𝑖 ) 𝑇 𝑖=1

(7)

where 𝑥𝑖 = 𝑋 [𝑖] is the 𝑖-th token of 𝑋 , and 𝑥 <𝑖 = 𝑋 [1 : 𝑖 − 1] denotes the tokens from the first to the (𝑖 − 1)-th tokens for 𝑋 . Specifically, 𝑃ˆ𝜽 (𝑥𝑖 |𝑥 <𝑖 ) can be seen as the 𝑖-th row of 𝑃ˆ𝜽 (𝑋 ). This loss function is equivalent to the average of cross-entropy losses that maximize the likelihood of correct next-token predictions. The training process employs the mini-batch stochastic gradient descent (SGD) algorithm [9] that uniformly samples mini-batches from the entire dataset. Given the training data D𝑡𝑟𝑎𝑖𝑛 , the LLM M𝜃 can be optimized as follows: ∑︁ 1 𝜽 𝑡 +1 = 𝜽 𝑡 − 𝜂 ∇𝜽 L (𝑋𝑖 , 𝜽 𝑡 ) |D𝑡𝑟𝑎𝑖𝑛 | 𝑋 ∈ D 𝑖

𝑡𝑟𝑎𝑖𝑛

where the gradient ∇𝜃 L (𝑋𝑖 , 𝜽 𝑡 ) denotes the gradient of the sequence 𝑋𝑖 at training iteration 𝑡.

2.2

Coreset selection for LLM Training

Due to the large parameter size of LLMs, it is highly time-consuming and resource-intensive to optimize the LLMs [33], especially on large datasets. Recently, coreset selection approaches [11, 12, 25, 38, 40, 41, 46, 53, 68] have been proposed to select a weighted subset of the dataset that approximates the statistical properties of the full dataset. In this way, the model optimized on the coreset achieves performance comparable to the model optimized on the full dataset. By training models on carefully selected coreset, the training time

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

can be significantly reduced while achieving performance comparable to models trained on the entire dataset. We provide the formal definition of coreset selection as follows: Definition 2.1 (Coreset Selection). Given a model M𝜃 , a training dataset D𝑡𝑟𝑎𝑖𝑛 , and a test dataset D𝑡𝑒𝑠𝑡 , coreset selection aims to construct a weighted subset D𝑐𝑜𝑟𝑒 ⊆ D𝑡𝑟𝑎𝑖𝑛 of size 𝑏 such that the performance of the model M𝜃 trained on D𝑐𝑜𝑟𝑒 is as close as possible to the performance of a model trained on the full dataset D𝑡𝑟𝑎𝑖𝑛 when evaluated on the test dataset D𝑡𝑒𝑠𝑡 . The objective can be expressed as follows: arg min Eval(D𝑡𝑒𝑠𝑡 , M𝜽 D𝑡𝑟𝑎𝑖𝑛 ) − Eval(D𝑡𝑒𝑠𝑡 , M𝜽 D𝑐𝑜𝑟𝑒 ) D𝑐𝑜𝑟𝑒

𝑠.𝑡 .

Tang et al.

easiest samples to learn. Second, other approaches [27, 43, 55, 79, 83] define uncertainty indicators based on changes in the training loss before and after training. However, uncertainty-based approaches present three key limitations when applied to LLMs. First, they require a trained or partially trained model to calculate prediction or uncertainty scores, which is impractical for LLMs due to their immense number of parameters. Second, estimating uncertainty over large datasets is computationally expensive, as it necessitates running the LLM on every instance to obtain scores. Finally, empirically defined uncertainty scores are not theoretically or directly linked to model optimization, meaning that samples selected based on uncertainty may not provide the most beneficial gradients for improving the model.

|D𝑐𝑜𝑟𝑒 | ≤ 𝑏, D𝑐𝑜𝑟𝑒 ⊆ D𝑡𝑟𝑎𝑖𝑛

where Eval(D𝑡𝑒𝑠𝑡 , ·) is an evaluation function on the test data D𝑡𝑒𝑠𝑡 , such as accuracy. Also, M𝜽 D𝑡𝑟𝑎𝑖𝑛 and M𝜽 D𝑐𝑜𝑟𝑒 are LLMs trained on the full training dataset D𝑡𝑟𝑎𝑖𝑛 and the coreset D𝑐𝑜𝑟𝑒 , respectively. The optimization problem is challenging to solve explicitly for two main reasons. First, the objective function is often non-convex or high-dimensional [17], making direct optimization difficult. Second, solving the problem requires evaluating all possible subsets [23], which is computationally prohibitive due to the combinatorial nature of the selection process. Therefore, researchers have explored alternative formulations to construct the coreset efficiently while approximating the desired performance [4, 23]. Specifically, depending on the techniques used to select the coreset from the entire dataset, existing approaches can be classified into three types, i.e., data-property-based [8, 11–13, 25, 65, 68], uncertainty-based [5, 19, 27, 38, 43, 50, 53, 55, 64, 74, 79, 83], and gradient-based [20, 37, 56, 58, 73, 80]. 2.2.1 Data-property-based Approaches. Data-property-based approaches rely on the intrinsic properties of the dataset, such as feature diversity or statistical similarity, to select the coreset. For instance, methods such as FastCore [12] and D4 [65] employ clustering techniques (e.g., K-means [51]) to group similar data points based on their features extracted from a pre-trained encoder [8, 13, 65]. Subsequently, they select representative samples that maximize the coverage of dataset’s distribution. While these approaches are simple and effective at maintaining data diversity, they do not consider the task-specific information and the influence of individual data points on the specific model (e.g., LLMs) [4]. Consequently, the task-agnostic nature can lead to suboptimal performance [4]. 2.2.2 Uncertainty-based Approaches. Uncertainty-based methods select coreset instances by leveraging uncertainty metrics derived from the training target model or proxy models, such as training loss and prediction scores. The basic idea behind these methods is that uncertain samples, which are those the model cannot confidently classify or predict, contain valuable information and are likely to have a significant impact on improving the model’s performance during training. Firstly, several studies, including [5, 19, 54, 64, 74], compute prediction scores and training loss for inputs to the model. These works then empirically select samples based on uncertainty indicators such as prediction scores, training loss, or a combination of both. Depending on the strategy, they may empirically select the most uncertain samples, moderately uncertain samples, or the

2.2.3 Gradient-based Approaches. Since data-property-based and uncertainty-based methods cannot theoretically guarantee optimal model performance, gradient-based methods are proposed. They directly use gradient information from the training process to select data samples that are most influential for model optimization. The most common way is to build a gradient matching problem [20, 58, 80], which is generally defined in other deep learning models [37, 56, 73]. The gradient matching coreset aims to closely approximate the gradient of all data samples at a specific training step with parameter 𝜽 , seeking to ensure that training on the coreset results in similar parameter updates as training on the full dataset. Formally, following [40], the problem is defined as: Definition 2.2 (Gradient Matching Coreset). Given a model M𝜃 and a full training dataset D𝑡𝑟𝑎𝑖𝑛 of size 𝑛, the goal is to construct a weighted subset D𝑐𝑜𝑟𝑒 ⊆ D𝑡𝑟𝑎𝑖𝑛 of size less than 𝑏, such that the total gradient computed on the coreset D𝑐𝑜𝑟𝑒 closely approximates the total gradient of the full dataset D𝑡𝑟𝑎𝑖𝑛 as follows: arg min ∥

| D∑︁ 𝑡𝑟𝑎𝑖𝑛 |

D𝑐𝑜𝑟𝑒

∇𝜽 L (𝑋𝑖 , 𝜽 ) −

𝑖=1

𝑠.𝑡 . |D𝑐𝑜𝑟𝑒 | ≤ 𝑏, 𝑤 𝑗 ≥ 0,

| D∑︁ 𝑐𝑜𝑟𝑒 |

𝑤 𝑗 ∇𝜽 L (𝑋 𝑗 , 𝜽 ) ∥

(8)

𝑗=1 | D∑︁ 𝑐𝑜𝑟𝑒 |

𝑤 𝑗 = 𝑛,

𝑗=1

where ∇𝜽 L (𝑋 𝑗 , 𝜽 ) is the gradient of sample 𝑋 𝑗 with respect to model parameters 𝜽 , and 𝑤 𝑗 is the non-negative weight of each selected sample 𝑋 𝑗 ∈ D𝑐𝑜𝑟𝑒 . Due to the non-convexity of the objective function and the exponential combinatorial nature of subset selection in Equation (8), it is infeasible to obtain the optimal coreset through exhaustive search [56]. The computational complexity grows exponentially with the dataset size, making direct optimization impractical for large-scale problems [56]. To address this, several approaches [41] compute the gradient norms of the loss function for individual instances and select samples by maximizing both gradient magnitudes and diversity. While they are effective for smaller models, these approaches are unsuitable for LLMs due to the prohibitive cost of gradient computations, which are significantly higher for billions of parameters compared to smaller models like GNNs [41] or MLPs [56]. To improve efficiency, several researchers replace gradient-based metrics with feature-based distances between samples [40, 46, 56]. This relaxation avoids gradient computations but

GRACE: A Dynamic Coreset Selection Framework for Large Language Model Optimization

fails to capture the complex dependencies and rich contextual information in transformer-based LLMs, leading to a loss of critical information and suboptimal performance. More importantly, the above approaches select the coreset statically before training, which ignores the evolving dynamics of LLMs during training. This static selection often results in suboptimal coresets that fail to adapt to changes in the model’s learning process. Thus, to address these challenges, we propose a dynamic coreset selection framework for LLMs.

Framework Overview

We introduce the procedure for GRACE, which is composed of three stages, summarized in Algorithm 1. Stage 1: Indicator Extraction and Graph Construction. Before coreset selection and model training, we extract the required features of training samples. Based on this feature extraction, we construct a mutual 𝑘-NN graph to capture the similarity structure among samples, which serves as the backbone for coreset construction, enhancing diversity and supporting efficient local updates later in the process. As shown in Algorithm 1 lines 1-3, given the warmup-trained target LLM M𝜽 𝑤𝑎𝑟𝑚 , we extract importance scores 𝐼 (𝑋𝑖 ) and the last-layer hidden states H𝑖𝐿 for any 𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛 . We then construct a mutual 𝑘-NN graph 𝐺 by treating data samples as nodes and computing Euclidean distances from extracted hidden states. During construction, we retrieve the top-𝑘 nearest neighbors in embedding space for each sample 𝑋𝑖 and keep an undirected edge (𝑖, 𝑗) only if the relation is mutual: 𝑋𝑖 is in the top-𝑘 list of 𝑋 𝑗 , and 𝑋 𝑗 is in the top-𝑘 list of 𝑋𝑖 . Stage 2: Coreset Selection and Model Training. After indicator extraction and graph construction, we train the LLM with coreset selection, as shown in Algorithm 1 lines 4-9. We divide the training steps within one epoch into several intervals, each comprising 𝑡𝑐 training steps, and define 𝑏 as the coreset budget for each interval. As in lines 5-6 of Algorithm 1, at the start of each interval, we sample a subset D𝑠 of size 𝑛𝑆 without replacement from the entire training dataset and construct a coreset D𝑐𝑜𝑟𝑒 of size 𝑏 with the coreset selection objective following Equation (16) in Section 4.2. Then, the model is trained on the coreset D𝑐𝑜𝑟𝑒 for 𝑡𝑐 steps, as shown in lines 7-9. This process is also shown as Stage 2 in Figure 1. Stage 3: Graph Update Checking and Updating. After 𝑡𝑐 training steps, following Algorithm 1 lines 10-11, we perform the checking and update procedure as described in Algorithm 3, which may update importance scores and embeddings. We first randomly sample a small validation subset from the most recently selected coreset, recompute their current importance scores with the latest model parameters, and measure the score change via Equation (18). If the change exceeds the threshold, we select samples via Equation (19), recompute their scores as well as embeddings, and update them through substitution and propagation over the graph structure via Equation (21). Finally, we incrementally repair only the affected portions of the 𝑘-NN structure. If no update is needed, we will keep the graph unchanged. After the checking and update step, we redo the sampling and coreset selection and repeat Stages 2 and 3 until the training finishes, as shown in Figure 1.

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Algorithm 1: Overall Framework Input: Warmed-up LLM M𝜽 𝑤𝑎𝑟𝑚 , initial LLM M𝜽 0 , training dataset D𝑡𝑟𝑎𝑖𝑛 , training steps T , check interval 𝑡𝑐 , sample size 𝑛𝑆 , coreset budget 𝑏 Output: Trained LLM with parameters 𝜽 𝑡 𝑛 1 { H̄𝑖 , 𝐼 (𝑋𝑖 )}𝑖=1 ← ExtractFeature(M𝜽 𝑤𝑎𝑟𝑚 ) 𝑛 2 𝐺 ← BuildGraph({ H̄𝑖 , 𝐼 (𝑋𝑖 )}𝑖=1 ) 3 𝑡 =0 4 while 𝑡 < T do 5 D𝑆 ←RandomSample(D𝑡𝑟𝑎𝑖𝑛 , 𝑛𝑆 ) 6 D𝑐𝑜𝑟𝑒 ← SelectCoreset(D𝑆 , 𝐺, 𝑏) // Algorithm 2 7 for 𝑖 = 1 . . . 𝑡𝑐 do Í 1 8 𝜽 𝑡 ← 𝜽 𝑡 −1 − 𝜂 | D𝑐𝑜𝑟𝑒 𝑋𝑖 ∈ D𝑐𝑜𝑟𝑒 ∇𝜽 L (𝑋𝑖 , 𝜽 𝑡 −1 ) | 9 𝑡 ←𝑡 +1 if 𝑡 mod 𝑡𝑐 = 0 then 𝐺 ← CheckandUpdate(M𝜽 𝑡 , 𝐺, D𝑐𝑜𝑟𝑒 ) // Algorithm 3

10 11

return Trained LLM M𝜽

Methods

In this section, we first provide a theoretical analysis of how to select a coreset for LLMs to preserve their performance, taking into account the specific characteristics of transformer-based architectures and autoregressive training loss in Section 4.1. Building on this analysis, in Section 4.2, we define the objectives for coreset selection that incorporate representation scores of hidden states and the gradient-based importance scores extracted from the LLM. Then we introduce the 𝑘-NN graph and propose a greedy algorithm for coreset selection. In Section 4.3, we propose an adaptive graph update checking and updating approach over the 𝑘-NN graph to fit the changes in training steps and reduce computational overheads.

4.1

Theoretical Analysis

As introduced in Section 2.2.3, directly utilizing Equation (8) as the objective for coreset selection on LLMs is nontrivial. First, the relaxation analysis of transformers becomes more complex due to the non-linearity introduced by self-attention mechanisms, requiring further theoretical investigation. Second, utilizing gradients from other layers adds significant computational overhead during the backward pass. Moreover, the process remains highly timeconsuming due to the size and complexity of LLMs, and the sparsity of gradients persists, given the billions of parameters in these models. Therefore, a theoretical analysis of coreset selection for LLMs remains lacking, particularly in the context of transformer-based architectures and billion scale LLM parameters. In the following, we present a theoretical framework to adapt the coreset selection definition in Equation (8) to LLMs. Since it is infeasible to solve the coreset selection problem in Equation (8) directly, following [40, 56, 73], we first relax the weight 𝑤 𝑗 to a binary selection indicator 𝑤 𝑗 ∈ {0, 1} and define a mapping function 𝛾 : D𝑡𝑟𝑎𝑖𝑛 → D𝑐𝑜𝑟𝑒 to associate each training sample 𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛 with a representative sample 𝑋 𝑗 ∈ D𝑐𝑜𝑟𝑒 in the coreset, i.e., 𝛾 (𝑋𝑖 ) = 𝑋 𝑗 . Therefore, we have the following upper bound

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Tang et al. Use old graph

Stage 1: Indicators Extraction and Graph Construction Hidden States

Warm-up Trained LLM

Stage 2: Coreset Selection and Model Training Representation Score +

Build

Importance Scores

Sampled Subset

Importance Score

LLM Training

Stage 3: Graph Update Checking and Updating

Yes Graph Update Checking

LLM Coreset

Selective Re-computation

Graph Updating

Coreset Selection

Update graph

Figure 1: Overview of GRACE. Stage 1: Hidden states and importance scores of all training samples are extracted from a warm-up trained model. A 𝑘-NN graph is constructed from these indicators. Stage 2: Sample a subset of samples from the graph and select the coreset, then train the model with the coreset. Stage 3: At checking steps, if significant changes in importance scores are detected, the graph will be updated. A subset is selected for recomputation and updated scores and embeddings are propagated through the graph structure. The 𝑘-NN graph is also updated and then reused in the next selection. through the triangle inequality: ∑︁ ∥ ∇𝜽 L (𝑋𝑖 , 𝜽 ) − 𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛

Proof Sketch. We analyze over W1 , W2 , W𝑄 , W𝐾 , W𝑉 and W𝑂 defined in (1), (5) and (6). Defining 𝑐 1 and 𝑐 2 as constants correlated with W1 , W2 , W𝑄 , W𝐾 , W𝑉 and W𝑂 , we have:

𝑤 𝑗 ∇𝜽 L (𝑋 𝑗 , 𝜽 )∥

𝑋 𝑗 ∈ D𝑐𝑜𝑟𝑒

∑︁

≤∥

∑︁

∥∇𝜽 L (𝑋𝑖 , 𝜽 ) − ∇𝜽 L (𝑋 𝑗 , 𝜽 )∥

(∇𝜽 L (𝑋𝑖 , 𝜽 ) − ∇𝜽 L (𝛾 (𝑋𝑖 ), 𝜽 ))∥

≤𝑐 1 ∥X𝑖 − X 𝑗 ∥ + 𝑐 2 ∥∇Ô𝑖 L (𝑋𝑖 , 𝜽 ) − ∇Oˆ𝑗 L (𝑋 𝑗 , 𝜽 )∥

𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛

∑︁

≤

≤𝑐 1 (∥X𝑖 − X 𝑗 ∥) + 𝑐 2 ∥∇Ô𝑖 L (𝑋𝑖 , 𝜽 )∥ + 𝑐 2 ∥∇Oˆ𝑗 L (𝑋 𝑗 , 𝜽 ) ∥

∥∇𝜽 L (𝑋𝑖 , 𝜽 ) − ∇𝜽 L (𝛾 (𝑋𝑖 ), 𝜽 )∥

𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛

Since minimizing this upper bound corresponds to assigning each training point to its nearest neighbor in the gradient space of the coreset instance, we have: ∑︁ ∥∇𝜽 L (𝑋𝑖 , 𝜽 ) − ∇𝜽 L (𝛾 (𝑋𝑖 ), 𝜽 )∥

Then we have: ∑︁ 𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛

≤

𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛

∑︁

min 𝑋 𝑗 ∈ D𝑐𝑜𝑟𝑒

∥∇𝜽 L (𝑋𝑖 , 𝜽 ) − ∇𝜽 L (𝑋 𝑗 , 𝜽 )∥ 𝑐 1 X𝑖 − X 𝑗 + 𝑐 2 ∥∇Ô 𝑗 L (𝑋 𝑗 , 𝜽 ) ∥ + 𝑐 3

(9)

Thus, the theorem is proved. Due to the space limit, we put the whole proof in the Appendix. □

Equation (9) is still computationally intensive, as it requires extracting and comparing gradients for every training sample. Therefore, we further upper-bound the gradient representations through intermediate features that are easier to obtain during forward passes. As introduced in Section 2.1, LLMs are composed of layers of transformer blocks, which are non-linear and consist of a complex selfattention mechanism. Therefore, we first analyze the coreset selection based on a single-layer transformer block and discuss how to extend it to multi-layer transformer-based LLMs.

The objective in Equation (10) is to select a coreset D𝑐𝑜𝑟𝑒 with size 𝑏 from the training data D𝑡𝑟𝑎𝑖𝑛 , such that the LLM optimized on Dcore achieves similar performance to that optimized on D𝑡𝑟𝑎𝑖𝑛 , balancing data diversity and data quality. Specifically,

≤

𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛

min 𝑋 𝑗 ∈ D𝑐𝑜𝑟𝑒

∥∇𝜽 L (𝑋𝑖 , 𝜽 ) − ∇𝜽 L (𝑋 𝑗 , 𝜽 )∥

Theorem 4.1. Given a one-layer transformer-based LLM M𝜃 and a training dataset D𝑡𝑟𝑎𝑖𝑛 = {𝑋𝑖 }𝑛𝑖=1 , the LLM M𝜃 processes each training instance 𝑋𝑖 as input and progressively predicts the logits Ô𝑖 for 𝑋𝑖 . Consequently, given the D𝑡𝑟𝑎𝑖𝑛 and the coreset D𝑐𝑜𝑟𝑒 , the gradient difference in Equation (9) can be upper-bounded by the following objective: ∑︁ min ∥∇𝜽 L (𝑋𝑖 , 𝜽 ) − ∇𝜽 L (𝑋 𝑗 , 𝜽 )∥ 𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛

≤

∑︁ 𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛

𝑋 𝑗 ∈ D𝑐𝑜𝑟𝑒

min 𝑋 𝑗 ∈ D𝑐𝑜𝑟𝑒

𝑐 1 X𝑖 − X 𝑗 + 𝑐 2 ∥∇Ô 𝑗 L (𝑋 𝑗 , 𝜽 )∥ + 𝑐 3

(10)

where X𝑖 denotes the input embedding representations of sample 𝑋𝑖 and ∇Ô𝑖 L (𝑋𝑖 , 𝜽 ) is the gradient of loss with respect to the output logits Ô𝑖 for 𝑋𝑖 . Also, 𝑐 1 and 𝑐 2 are Lipschitz constants associated Í with the model parameters 𝜽 and 𝑐 3 = ∥ 𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛 ∇Ô𝑖 L (𝑋𝑖 , 𝜽 )∥.

• The first term ∥X𝑖 − X 𝑗 ∥ is a representation score that measures the distance between a training data point 𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛 and a coreset point 𝑋 𝑗 ∈ D𝑐𝑜𝑟𝑒 . The goal is to minimize this distance, ensuring that the coreset D𝑐𝑜𝑟𝑒 adequately represents the entire training dataset D𝑡𝑟𝑎𝑖𝑛 . • The second term ∥∇Ô 𝑗 L (𝑋 𝑗 , 𝜽 )∥ is an importance score that focuses on the gradient magnitude of the coreset point 𝑋 𝑗 ∈ D𝑐𝑜𝑟𝑒 . By minimizing this term, the selected coreset points are encouraged to have gradients that are significant enough to effectively guide the model’s parameter updates, thereby preserving the model’s training quality. The inclusion of both terms ensures that the coreset points are not only representative of the input diversity in the training data but also make substantial contributions to gradient updates during optimization. This dual focus enables the trained LLMs to achieve high performance when using the selected coreset.

4.2

Coreset Selection

In this subsection, we propose the coreset selection objective and present a greedy algorithm for coreset selection.

GRACE: A Dynamic Coreset Selection Framework for Large Language Model Optimization

4.2.1 Representation Score. Intuitively, the point 𝑋 𝑗 in D𝑐𝑜𝑟𝑒 should have a minimal distance to as many data points in D𝑡𝑟𝑎𝑖𝑛 as possible for sufficient data diversity. To minimize the embedding distance ∥X𝑖 − X 𝑗 ∥, we utilize the cosine similarity to convert it into a maximization objective. We use hidden state representations from the final layer of the model for each instance, as the transformer blocks there provide more semantic and contextual information. Specifically, given a training dataset D𝑡𝑟𝑎𝑖𝑛 = {𝑋𝑖 }𝑛𝑖=1 where each 𝑋𝑖 is composed of 𝑇 tokens, suppose the LLM M𝜃 processes each training instance 𝑋𝑖 as input and produces hidden state representations H𝑖(𝐿) ∈ R𝑇 ×𝑑 for 𝑋𝑖 at the last layer 𝐿 of transformer blocks, where 𝑑 is the hidden state dimension. Formally, the representation score of the coreset D𝑐𝑜𝑟𝑒 is: ∑︁ 𝑅(D𝑐𝑜𝑟𝑒 ) = max cos( H̄𝑖(𝐿) , H̄ (𝐿) (11) 𝑗 ) 𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛

Algorithm 2: SelectCoreset Input: Candidate samples D𝑆 , selection budget 𝑏, Graph 𝐺 built on training data Output: Coreset D𝑐𝑜𝑟𝑒 1 D𝑐𝑜𝑟𝑒 ← ∅ 2 while |D𝑐𝑜𝑟𝑒 | < 𝑏 do 3 for 𝑋𝑖 ∈ D𝑆 \D𝑐𝑜𝑟𝑒 do 4 𝑅𝑆 (D𝑐𝑜𝑟𝑒 ∪ {𝑋𝑖 }) ← Equation (16) 5 Δ𝑅𝑆 (𝑋𝑖 |D𝑐𝑜𝑟𝑒 ) = 𝑅𝑆 (D𝑐𝑜𝑟𝑒 ∪ {𝑋𝑖 }) − 𝑅𝑆 (D𝑐𝑜𝑟𝑒 ) 6 7 8

𝑋 ∗ = arg max𝑋𝑖 ∈ D𝑆 \D𝑐𝑜𝑟𝑒 Δ𝑅𝑆 (𝑋𝑖 |D𝑐𝑜𝑟𝑒 ) D𝑐𝑜𝑟𝑒 = D𝑐𝑜𝑟𝑒 ∪ {𝑋 ∗ } return D𝑐𝑜𝑟𝑒

𝑋 𝑗 ∈ D𝑐𝑜𝑟𝑒

To obtain a fixed-size representation, we compute the mean in the token length dimension of H𝑖(𝐿) , denoted as H̄𝑖(𝐿) ∈ R𝑑 . 4.2.2 Importance score. In Theorem 4.1, the selected coreset is encouraged to have gradients with respect to the output logits that can effectively guide the model’s parameter updates, i.e., ∥∇Ô 𝑗 L (𝑋 𝑗 , 𝜽 )∥. It can be computed by: 𝐼 (𝑋 ) = ∥∇Ô L (𝑋, 𝜽 )∥ = 𝑃ˆ ( Ô) − O

(12)

where O is the one-hot ground truth matrix of sample 𝑋 . We define 𝐼 (𝑋 ) as the importance score. The importance score measures per-sample gradient sensitivity, analogous to per-sample gradient-norm difficulty. However, directly selecting samples with large importance score values can be suboptimal. High importance scores may reflect noisy and mislabeled inputs. In addition, under constrained training budgets, prioritizing hard samples does not always contribute to model training due to limited steps for gradients explode. In practice, with constrained training budgets, prioritizing low- or mid-difficulty mass yields steadier improvement. Such a strategy is consistent with the observations in [62, 82] and with our evaluation setup. Thus, to adaptively favor moderately difficult samples [1, 16], instead of selecting based on the largest or smallest importance scores, we first rescale the raw importance scores to [0, 1] via min-max 𝐼 (𝑋 ) −min𝑋 ′ ∈D𝑡𝑟𝑎𝑖𝑛 𝐼 (𝑋 ) normalization 𝐼˜(𝑋 ) = to normalmax𝑋 ′ ∈D𝑡𝑟𝑎𝑖𝑛 𝐼 (𝑋 ) −min𝑋 ′ ∈D𝑡𝑟𝑎𝑖𝑛 𝐼 (𝑋 )

ize scale differences across datasets, sources, or checkpoints. Then, we define a warped importance score for selection as:

Γ(𝛼 + 𝛽) ˜ 𝛼 −1 𝐼 (𝑋 ) (1 − 𝐼˜(𝑋 )) 𝛽 −1 )𝛾 Γ(𝛼)Γ(𝛽)

(13)

𝛼 and 𝛽 are the parameters associated with the Beta distribution that control the mean and variance. 𝛾 ≥ 0 is a temperature parameter that controls the sharpness of the warped importance scores without changing the induced ranking. We define: 𝛼 = 1 + 𝐶 · (Mean(𝐼˜(𝑋 )))𝑞 · 𝜂𝑟 , 𝛽 = 𝐶 − 𝛼

with extremely high or low 𝐼 (𝑋𝑖 ). In addition, we can shift the mode of the Beta curve toward harder samples when the budget is large or toward easier samples when the budget is tight, thus adapting to different regions according to the score distribution and training budget. The temperature 𝛾 allows us to smoothly align the score scale with the representation score computed by embedding similarity. Formally, given a selected subset from the training dataset D𝑐𝑜𝑟𝑒 ⊆ D𝑡𝑟𝑎𝑖𝑛 , the warped importance score of the coreset D𝑐𝑜𝑟𝑒 is: ∑︁ 𝐼ˆ(D𝑐𝑜𝑟𝑒 ) = (Beta(𝐼˜(𝑋𝑖 ), 𝛼, 𝛽))𝛾 𝑋𝑖 ∈ D𝑐𝑜𝑟𝑒

∑︁ 𝑋𝑖 ∈ D𝑐𝑜𝑟𝑒

(

Γ(𝛼 + 𝛽) ˜ 𝐼 (𝑋𝑖 ) 𝛼 −1 (1 − 𝐼˜(𝑋𝑖 )) 𝛽 −1 )𝛾 Γ(𝛼)Γ(𝛽)

(15)

With these scores, we then formally define our coreset selection problem as follows: Definition 4.2 (Coreset Selection Problem). Given the training dataset D𝑡𝑟𝑎𝑖𝑛 and the selection budget 𝑏, our target is to select a coreset D𝑐𝑜𝑟𝑒 ⊆ D𝑡𝑟𝑎𝑖𝑛 that maximizes the following objective 𝑅𝑆 (D𝑐𝑜𝑟𝑒 ): 𝑅𝑆 (D𝑐𝑜𝑟𝑒 ) = 𝜆𝑅(D𝑐𝑜𝑟𝑒 ) + (1 − 𝜆) 𝐼ˆ(D𝑐𝑜𝑟𝑒 ) (16) 𝑠.𝑡 .|D𝑐𝑜𝑟𝑒 | ≤ 𝑏 where 𝑅(D𝑐𝑜𝑟𝑒 ) is the representation score of D𝑐𝑜𝑟𝑒 defined in Equation (11), 𝐼ˆ(D𝑐𝑜𝑟𝑒 ) is the importance score of D𝑐𝑜𝑟𝑒 defined in Equation (13), and 𝜆 is a hyper-parameter balancing contributions of each term. Theorem 4.3. The Coreset Selection Problem is NP-hard.

𝐼ˆ(𝑋 ) = (Beta(𝐼˜(𝑋 ), 𝛼, 𝛽))𝛾 =(

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

(14)

where 𝜂 is the coreset selection budget in percentage, 𝑞 and 𝑟 are hyper-parameters controlling the contribution of the mean score and budget, and 𝐶 is a constant. In this way, we suppress outliers

Proof Sketch. This problem can be reduced from the Maximum Coverage Problem (MCP) [28], which is NP-hard. Due to space limit, we put the full proof in our technique report. □ 4.2.3 Coreset Selection Algorithm. Since the coreset selection problem is NP-hard, we cannot obtain an optimal solution in polynomial time. To address this, we propose a greedy algorithm. The basic idea is to iteratively select the data point that provides the maximum gain of 𝑅𝑆 score until reaching the budget 𝑏 in a greedy manner. First of all, we define the marginal gain of the 𝑅𝑆 score as follows: Δ𝑅𝑆 (𝑋𝑖 |D𝑐𝑜𝑟𝑒 ) = 𝑅𝑆 (D𝑐𝑜𝑟𝑒 ∪ {𝑋𝑖 }) − 𝑅𝑆 (D𝑐𝑜𝑟𝑒 )

(17)

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Load Recent History EL2N Score

Select Samples for Recompute

Tang et al.

Score and Embedding Update Propagation

Recompute Embedding and Scores

𝑘-NN graph update

Figure 2: Overview of the graph update process. From left to right: we begin with a 𝑘-NN graph constructed from initial representations and EL2N scores (blue nodes). When adaptive update checking is triggered, a subset of recently trained samples (green) is loaded and we use their history scores as new scores. Another small number of samples (purple) are then selected for recomputation. Combining the history scores and recomputed scores as updated scores, they are then propagated to their neighbors through the graph structure (blue to green), allowing approximate updates without full recomputation. To simplify the process of the coreset selection algorithm, we build a mutual 𝑘-NN graph 𝐺 to save the hidden state representations and importance scores. The detailed definition of 𝐺 is as follows: Definition 4.4 (𝑘-NN graph). We construct a mutual 𝑘-NN graph 𝐺 = (D𝑡𝑟𝑎𝑖𝑛 , 𝐸) where each node 𝑋𝑖 is a data point in D𝑡𝑟𝑎𝑖𝑛 filled with its importance score and hidden state representation. There is an edge 𝑒𝑖 𝑗 ∈ 𝐸 connecting 𝑋𝑖 and 𝑋 𝑗 if and only if 𝑋 𝑗 is one of the top-𝑘 nearest neighbors of 𝑋𝑖 , and 𝑋𝑖 is one of the top-𝑘 nearest neighbors of 𝑋 𝑗 too. The edge weight of 𝑒𝑖 𝑗 is defined as 2 𝑤𝑖 𝑗 = exp(−∥ H̄𝑖(𝐿) − H̄ (𝐿) 𝑗 ∥ /100). Since hidden states and importance scores evolve during training, 𝐺 must be updated accordingly, where the details are discussed in Section 4.3. Then, as shown in Algorithm 2, we initialize D𝑐𝑜𝑟𝑒 as an empty set. Then we compute the marginal gain of 𝑅𝑆 score as Equation (17) for each 𝑥𝑖 in D𝑆 , where 𝑅𝑆 (·) is the score calculated from Equation (16). This process is repeated until the number of selected samples reaches the budget 𝑏. Theorem 4.5. Algorithm 2 achieves a (1 − 𝑒1 ) approximation ratio to the optimal solution. 𝑘 Proof Sketch. Suppose D𝑐𝑜𝑟𝑒 is the selected coreset using Al𝑜𝑝𝑡 gorithm 2 of size 𝑘, and D𝑐𝑜𝑟𝑒 is the unknown subset that maximizes the score 𝑅𝑆 (·) in Equation (17). We can first prove that 𝑘 ) is monotone increasing and submodular. Then, we Δ𝑅𝑆 (𝑋𝑖 |D𝑐𝑜𝑟𝑒 𝑘 ) ≥ (1 − 1 )𝑅𝑆 (D 𝑜𝑝𝑡 ). Due to space prove that it satisfies 𝑅𝑆 (D𝑐𝑜𝑟𝑒 𝑐𝑜𝑟𝑒 𝑒 limit, we put the full proof in our Appendix. □

Time Complexity Analysis. Given the selection budget 𝑏, the candidate sample size |D𝑆 |, and the embedding dimension 𝑑, the time complexity is 𝑂 (𝑑) for each computation of Equation (11), and 𝑂 (1) for Equation (15). This requires a loop of 𝑂 (|𝐷𝑆 |𝑏) for each selection, with 𝑘 selections in total. Thus, the total time complexity for Algorithm 2 is 𝑂 (|D𝑆 |(𝑏 2𝑑 + 𝑏)).

4.3

Graph Update Checking and Updating

According to Equation (8) and Equation (16), the selection quality is constrained by representations and scores under parameter 𝜽 . While 𝜽 changes during training, the extracted representations and scores evolve. Therefore, if we use the static graph constructed at the beginning to select the coreset for subsequent training steps, the new coreset may not accurately reflect the current training dynamics or capture the most representative samples under the updated model parameters.

One simple way is to fully update the 𝑘-NN graph 𝐺 by recomputing all sample embeddings and scores. However, its time complexity is O (𝑁 2𝑑 + 𝑁 𝐿(𝑑𝑇 2 + 𝑑 2𝑇 )), which is high and impractical for LLM training. In addition, we observe that model drift is not uniform: most samples maintain roughly the same difficulty ranking across short training intervals, and only a small subset changes substantially. To efficiently capture training dynamics, we propose approximating score and representation updates via the graph 𝐺. The dynamic update procedure in Algorithm 3 consists of three main steps: • Step 1: Adaptive Update Checking: In lines 1–3, we randomly sample a set S𝑡 from the current 𝐷𝑐𝑜𝑟𝑒 and compute their importance score variation using Equation (18). If the variation exceeds the threshold 𝛿, an approximate graph update is triggered. • Step 2: Selective Recalculation: In lines 4–10, for each 𝑋𝑖 in 𝐷𝑡𝑟𝑎𝑖𝑛 , we calculate 𝑠𝑢𝑝𝑑𝑎𝑡𝑒 according to Equation (19). We then iteratively expand a set 𝐷𝑟𝑒𝑐𝑎𝑙 to include the top-𝑘𝑟𝑒𝑐𝑎𝑙 disjoint data points with the highest 𝑠𝑢𝑝𝑑𝑎𝑡𝑒 scores. The importance score of data in 𝐷𝑟𝑒𝑐𝑎𝑙 will be accurately updated. • Step 3: Score and Embedding Propagation: In lines 11–16, we recompute the importance scores for samples in 𝐷𝑟𝑒𝑐𝑎𝑙 using the current model, while approximately updating the remaining importance scores in 𝐷𝑡𝑟𝑎𝑖𝑛 \ 𝐷𝑟𝑒𝑐𝑎𝑙 via Equation (21). Similarly, we further check and update embeddings for selected samples and update the 𝑘-NN graph accordingly. 4.3.1 Adaptive Update Checking. To avoid unnecessary recomputation, we adopt an adaptive strategy that triggers graph updates only if significant changes in importance scores are detected. We periodically evaluate the need for recomputation based on the discrepancy between historical and current importance scores. When the training steps reach the check interval 𝑡𝑐 , we first uniformly sample a subset S𝑡 from the trained data in the previous steps and evaluate their current importance scores for comparison. For samples 𝑋𝑖 ∈ S𝑡 with historical scores at previous 𝑐 steps, we define the average discrepancy score of S𝑡 that reflects the variation in importance scores as: 1 ∑︁ Δ = |S𝑡 | 𝐼

𝑋𝑖 ∈ S𝑡

𝑡𝑘 −𝑡𝑐 |𝐼 (𝑋𝑖 )𝑡𝑘 − 𝐼 (𝑋𝑖 )𝑡𝑐 | 𝑡𝑘 =0 𝜆𝑐 Í𝑡𝑐 𝑡𝑘 −𝑡𝑐 𝐼 (𝑋𝑖 )𝑡𝑐 𝑡𝑘 =0 𝜆𝑐

Í𝑡𝑐

(18)

where 𝜆𝑐 = 0.99 is an exponential decay factor that emphasizes recent changes. 𝐼 (𝑋𝑖 ) is the importance score in Equation (12). We then compare it to a predefined threshold 𝛿. Once the discrepancy

GRACE: A Dynamic Coreset Selection Framework for Large Language Model Optimization

Algorithm 3: CheckandUpdate Input: Graph 𝐺, model M𝜽 𝑡 , graph score update check threshold 𝛿, embedding update check threshold 𝛿ℎ , coreset trained for last steps D𝑐𝑜𝑟𝑒 , update momentum 𝛼, recompute budget 𝑘𝑟𝑒𝑐𝑎𝑙 Output: Updated Graph 𝐺 1 S𝑡 ← RandomSample(D𝑐𝑜𝑟𝑒 , 𝑛𝑠 ) 𝐼 2 Δ ← Equation (18) // Update Checking 𝐼 3 if Δ > 𝛿 then 4 {𝑠𝑢𝑝𝑑𝑎𝑡𝑒 (𝑋𝑖 )}𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛 ← Equation (19) 5 D𝑟𝑒𝑐𝑎𝑙 ← ∅ 6 while |D𝑟𝑒𝑐𝑎𝑙 | < 𝑘𝑟𝑒𝑐𝑎𝑙 do 7 𝑋 ∗ = arg max𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛 𝑠𝑢𝑝𝑑𝑎𝑡𝑒 (𝑋𝑖 ) 8 if 𝑋 ∗ ∉ D𝑟𝑒𝑐𝑎𝑙 , 𝑋 ∗ ∉ N (𝑋 𝑗 ) ∀𝑋 𝑗 ∈ D𝑟𝑒𝑐𝑎𝑙 then 9 D𝑟𝑒𝑐𝑎𝑙 ← D𝑟𝑒𝑐𝑎𝑙 ∪ {𝑋 ∗ }, 𝑠𝑢𝑝𝑑𝑎𝑡𝑒 (𝑋 ∗ ) ← 0 10 11 12 13 14 15 16 17

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

while simultaneously avoiding the selection of neighbors of already selected samples. This selection process is repeated until a predefined budget 𝑘𝑟𝑒𝑐𝑎𝑙 is reached, forming a subset of samples D𝑟𝑒𝑐𝑎𝑙 for score and embedding recomputation. 4.3.3 Approximate Graph Updating. After selective recomputation, we have new scores and representations of the selected samples. We first update the scores via approximate updating and further update the embeddings and the 𝑘-NN graph. We propagate updated importance scores to the remaining outdated samples using their local neighborhood information. Given the updated scores 𝐼 new (𝑋𝑖 ) for each node 𝑋𝑖 in 𝐺, we identify the nodes whose neighbors have updated scores and are sufficiently similar to their updated neighbors. Concretely, For every non-anchor node 𝑋𝑖 ∉ Drecal , we consider only those graph neighbors 𝑋 𝑗 that are in 𝐷 recal and discard neighbors that are far in representation space or that have historically disagreed in difficulty. We define the affinity between 𝑋𝑖 and its neighbor 𝑋 𝑗 as:

{𝐼 𝑛𝑒𝑤 (𝑋𝑖 ), H𝑛𝑒𝑤 } ← ExtractFeature(M𝜽 𝑡 , D𝑟𝑒𝑐𝑎𝑙 ) 𝑖 {𝐼 𝑛𝑒𝑤 (𝑋𝑖 )}𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛 \D𝑟𝑒𝑐𝑎𝑙 ← Equation (21) 𝐺 ← {𝐼 𝑛𝑒𝑤 (𝑋𝑖 )}𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛 ΔH ← Equation (22) // Embedding Update Checking if ΔH > 𝛿ℎ then {H𝑛𝑒𝑤 }𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛 \D𝑟𝑒𝑐𝑎𝑙 ← Equation (23) 𝑖 𝐺 ← Update 𝑘-NN structure

aff(𝑖, 𝑗) = 𝑤𝑖 𝑗 · exp(−0.1|𝐼 (𝑋𝑖 ) − 𝐼 (𝑋 𝑗 )|)

where 𝑤𝑖 𝑗 is the edge weight in Definition 4.4. If any of the neighbors has aff(𝑖, 𝑗) > 𝛽 for a threshold 𝛽, we include it for propagation. Let N𝑖★ = { 𝑗 ∈ N (𝑋𝑖 ), aff(𝑖, 𝑗) > 𝛽} be the set of neighbors of 𝑋𝑖 that passed the threshold. We update 𝑋𝑖 ’s score by solving a simple quadratic objective. This objective balances its old score with those of its most similar neighbors as follows:

return Updated Graph 𝐺

𝐸 (𝑋𝑖 ) = exceeds the threshold, it means a significant shift in training dynamics, and we start the graph updates. During training, we compute and cache importance scores at each training step. 4.3.2 Selective Recomputation. We first adopt a selective recomputation strategy guided by two key principles: (1) reusing historical importance scores for samples whose scores are likely to remain valid during training, and (2) prioritizing representative samples that are located at the boundaries of homogeneous regions in the graph. First, we initially filter out candidates that have recent historical scores, as they are less likely to require updating. To quantify this, we define the staleness score as sta(𝑋𝑖 ) = 𝑡 − 𝑡ℎ𝑖𝑠𝑡𝑜𝑟 𝑦 , which indicates the number of steps since the last update for 𝑋𝑖 . 𝑡ℎ𝑖𝑠𝑡𝑜𝑟 𝑦 is the training step of the latest update. Secondly, we also want to de-prioritize samples that are highly similar to their neighbors and prioritize samples that lie at the edge of homogeneous Í regions. We define the uniqueness score as uni(𝑋𝑖 ) = |𝐼 (𝑋𝑖 ) −

𝑗 ∈N (𝑋𝑖 ) 𝑤𝑖 𝑗 𝐼 (𝑋 𝑗 )

𝑗 ∈N (𝑋𝑖 ) 𝑤𝑖 𝑗

|, where 𝑤𝑖 𝑗 is the edge weight

in Definition 4.4. uni(𝑋𝑖 ) captures the deviation of 𝑋𝑖 ’s current importance score from the weighted average of its neighborhood. Larger 𝑢𝑛𝑖 (𝑋𝑖 ) means the node sits in a decision boundary region where a correction would affect many other points. Combining two scores, we have the selective update determination score as: 𝑠𝑢𝑝𝑑𝑎𝑡𝑒 (𝑋𝑖 ) = uni(𝑋𝑖 ) · sta(𝑋𝑖 )

(20)

(19)

The larger the 𝑠𝑢𝑝𝑑𝑎𝑡𝑒 , the more strongly the sample is prioritized to recompute the importance score. To ensure diversity and avoid over-concentration in dense regions, we apply a simple greedy algorithm to iteratively select samples with the largest 𝑠𝑢𝑝𝑑𝑎𝑡𝑒 (𝑋𝑖 ),

2 2 1 ∑︁ 1 𝑛𝑒𝑤 𝑤𝑖 𝑗 𝐼 𝑛𝑒𝑤 (𝑋𝑖 ) − 𝐼 𝑛𝑒𝑤 (𝑋 𝑗 ) 𝐼 (𝑋𝑖 ) − 𝐼 (𝑋𝑖 ) + 2 2 ★ 𝑗 ∈ N𝑖

where 𝐼 new (𝑋 𝑗 ) is the recomputed score of neighbor 𝑋 𝑗 , and Í 𝑤 𝑤𝑖 𝑗 is the edge weight. Define 𝛼𝑖 𝑗 = Í 𝑖★𝑗 𝑤𝑖 𝑗 , 𝑗 ∈ N★ 𝛼𝑖 𝑗 = 1, the 𝑗 ∈N𝑖

𝑖

closed-form solution of this strictly convex objective is exactly the following weighted average: 1 1 𝐼 𝑛𝑒𝑤 (𝑋𝑖 ) = 𝐼 (𝑋𝑖 ) + 𝛼𝑖 𝑗 𝐼 new (𝑋 𝑗 ) (21) 2 2 Then, we apply this update to the neighbors of each 𝑋𝑖 that satisfy the affinity condition. After the update is complete, we reconstruct the coreset based on the updated scores and resume training. Instead of using the same procedure for updating the representation, we have an additional check for the embedding update. Given the old embeddings as well as the recomputed embeddings in Section 4.3.2, we check the average embedding shift for these embeddings by: ∑︁ 1 ΔH = ∥ H̄𝑖 − H̄𝑛𝑒𝑤 ∥ (22) 𝑖 |D𝑟𝑒𝑐𝑎𝑙 | 𝑋 ∈ D 𝑖

𝑟𝑒𝑐𝑎𝑙

∈ R𝑑 denotes the mean hidden state representation ob-

where H̄𝑖 Í tained by H̄𝑖 = 𝑇1 𝑇𝑡=1 H𝑖 [𝑡], where H𝑖 ∈ R𝑇 ×𝑑 represents the hidden states from the model. The score is then compared with a given threshold 𝛿ℎ . If the shift is insignificant, we skip the embedding update and retain the graph unchanged. Otherwise, we perform the representation update using the same strategy as the scores. For each embedding recomputed, we directly replace the embeddings with the new embeddings. We adopt the same similarity

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

check as Equation (18) and propagate the embedding via: Í 1 1 𝑗 ∈ N (𝑋𝑖 ),aff(𝑖,𝑗 ) >𝛽 𝑤𝑖 𝑗 H̄ 𝑗 𝑛𝑒𝑤 Í H̄𝑖 = H̄𝑖 + 2 2 𝑗 ∈ N (𝑋𝑖 ),aff(𝑖,𝑗 ) >𝛽 𝑤 𝑖 𝑗

Tang et al.

(23)

Updating the representations affects the previously constructed 𝑘-NN graph. However, rebuilding the entire graph after each update would incur 𝑂 (𝑛 2𝑑) cost and becomes unnecessary when only a subset of nodes changes. Therefore, GRACE performs a local graph repair strategy that updates only the changed nodes and their affected neighborhoods. Specifically, we use an LSH-based approximate neighbor index to retrieve a small candidate set for updated embeddings, and then refine the final neighbors by exact distance computation. In this way, the graph can be maintained efficiently without recomputing the full 𝑘-NN structure. Theorem 4.6 (Bounded Error of the Selective Update, Short version). Consider the update round as defined in Equation (21). Then for every 𝑋𝑖 , we have Change Stability: The per-round change of any node is bounded, and Local Approximation Error bound: The local approximation methods error is bounded. Proof Sketch. Due to space limit, we put the full proof in our Appendix. □ Theorem 4.6 supports our approximation strategy by showing that selective updates through similar neighbors keep the update error controlled. Therefore, our graph-based selective update can maintain locally accurate importance scores and embeddings while recomputing only a subset of samples. Time Complexity Analysis. Suppose the LLM has 𝐿 layers with a hidden dimension of 𝑑, the average data length is 𝑇 , the data size is 𝑁 , the update checking size is |S𝑡 |, and the recomputation size is |D𝑟𝑒𝑐𝑎𝑙 |. The time complexity is 𝑂 (|S𝑡 |𝐿(𝑑 2𝑇 + 𝑑𝑇 2 )) for adaptive checking, 𝑂 (𝑁 + |D𝑟𝑒𝑐𝑎𝑙 |𝐿(𝑑 2𝑇 + 𝑑𝑇 2 )) for selective recomputation, 𝑂 (|D𝑟𝑒𝑐𝑎𝑙 |𝑛𝑑) for score and embedding propagation, and 𝑂 (|D𝑟𝑒𝑐𝑎𝑙 |(log 𝑁 + 𝑛𝑑)) for 𝑘-NN updating. In summary, the time complexity for Algorithm 3 is 𝑂 (|S𝑡 ||D𝑟𝑒𝑐𝑎𝑙 |𝐿(𝑑 2𝑇 + 𝑑𝑇 2 ) + 𝑁 + |D𝑟𝑒𝑐𝑎𝑙 |(log 𝑁 + 2𝑛𝑑)).

Experiments

In this section, we present a comprehensive empirical evaluation of GRACE. We first introduce the experimental settings in Section 5.1, including datasets, tasks, model backbones, baseline methods, evaluation metrics, and implementation details. We then report the main results on MathInstruct in Section 5.2, analyzing both effectiveness and end-to-end efficiency. Next, we conduct ablation studies to isolate the contributions of key components in GRACE in Section 5.3 and perform a systematic sensitivity analysis under multiple selection budgets, balance coefficients, and update schedules in Section 5.4. Finally, in Section 5.5, we evaluate GRACE on two additional instruction-tuning benchmarks to assess its generalization across domains and tasks.

5.1

Experimental Settings

5.1.1 Datasets and Evaluation Procedure. We use three benchmarks from different tasks and fields: MathInstruct [78], BioInstruct [66], and DialogSum [15] for evaluation.

MathInstruct. MathInstruct [78] contains 262K high-quality instances for fine-tuning on math problems, which are constructed from 14 different math-related data sources to provide wide coverage of various math fields and difficulty levels. It contains several tasks related to mathematics, including code generation, reasoning, and question answering. Following the settings of [78], we evaluate the performance on both in-domain and out-of-domain open-ended generation tasks from the MathInstruct [78] benchmark. Here, the in-domain tasks consist of test sets from three math datasets whose training portions are included in the MathInstruct training mixture, while the out-of-domain tasks consist of three standalone math reasoning benchmarks that are never used for training and are only used for evaluation. In-domain tasks primarily evaluate the training quality on training the distribution, while out-of-domain tasks assess the model’s ability to generalize beyond the training distribution. Together, these benchmarks offer a comprehensive assessment across a range of mathematical problems, such as arithmetic, algebra, and commonsense reasoning. For evaluation, following [74, 78], each evaluation task is assessed using exact match accuracy, which measures whether the final output exactly matches the ground-truth solution. We use the same procedure as the original paper [78], where all evaluations are conducted under the zero-shot setting and adopt the Program-of-Thought prompting approach [14] as the primary strategy. If the generated code is not executable, we fall back to Chain-of-Thought prompting [70]. This encourages the model to give numerical answers directly after reasoning steps, imitating a human’s step-by-step reasoning process. BioInstruct and DialogSum. In Section 5.5, we also conduct experiments on two additional datasets. BioInstruct [66] contains biomedical question answering problems. With an instructioninput-output triplet format, the dataset evaluates a wide range of scenarios in medical and biomedical question answering tasks, such as diagnostic analysis and clinical decision making. DialogSum [15] contains comprehensive dialog samples of daily-life scenarios extracted from open dialog repositories, each paired with a corresponding summarization reference. We use the split settings from [69] that perform a 9 : 1 train–test split on datasets. For BioInstruct and DialogSum datasets, we use the same generation prompt at evaluation as in training with a zero-shot setting. We evaluate the generated output using the ROUGE-L metric [49], which measures the comprehensiveness of answers compared to human references. Typically, we measure the F1 score of the ROUGE-L metric. The higher the F1 score, The better the QA answers or summarized text match the reference. 5.1.2 Models and Baselines. We evaluate GRACE on supervised fine-tuning tasks with LoRA [31] using Phi-2 [45], Llama-2-7b [2] and Qwen2.5-7b [63] models. We compare GRACE with several baselines that employ diverse selection methods and strategies. We set up the following selection types: static and dynamic. Static selection: Static selection methods select one fixed coreset for the entire training procedure. We compare with the following static selection baselines: • Random. It randomly samples a subset from the training dataset.

GRACE: A Dynamic Coreset Selection Framework for Large Language Model Optimization

• Middle Perplexity (MP) [5, 54]. It selects samples with loss values that are closest to the median of all loss values. • Facility Location (FL) [8]. It selects samples to maximize similarity to all samples in the embedding space by solving a facility location problem. • DivIR [83]. It selects samples that have the largest reduction in loss value after warm-up training. • Long4Align [81]. It selects samples with the longest sequential completion lengths. • GradN [60]. It selects samples with the largest gradient values from the last layer. • Least Confidence (LC) [8]. It selects samples that have the smallest output probabilities of tokens multiplied over the entire generated sequences. • TAGCOS [80]. It uses Orthogonal Matching Pursuit to solve the gradient matching problem (8) directly to select a coreset. Dynamic selection: Dynamic selection methods reconstruct a new coreset before the start of every epoch. We establish the following baselines for comparison with dynamic selection methods: • Fix Interval Random. It randomly samples a subset from the training dataset before starting each epoch. • Fix Interval Middle Perplexity (DynamicMP). Before starting each epoch, it recalculates the loss values of all samples and selects samples with loss values that are closest to the median of all values. • Fix Interval Facility Location (DynamicFL). Before starting each epoch, it re-extracts the representations for all data samples and selects samples to maximize representation coverage over the embeddings by solving a facility location problem. • kMQ [76]. It first extracts embeddings for the data and clusters the embeddings into several clusters. Before each epoch, it randomly samples from clusters with weights and uses the scores to adjust the weights of each cluster before the next selection. 5.1.3 Implementation Details. For a fair comparison, all methods are compared under the same constrained budget of training steps, such as 10% of the full training steps. Static selection methods first warm up the model for 10% of the full training steps, then use it to extract scores, embeddings, or gradient vectors, and select a single coreset of size 𝑏. Dynamic selection methods first extract scores or embeddings using the current model before each epoch, and then build a coreset for the upcoming epoch. The selection size at each update is bounded by 𝑏. For model training, we apply LoRA [31] with rank 128, scale factor 512, and dropout rate 0.05. Models are trained for 3 epochs with a batch size of 128. We use learning rates of 2e-5 for Phi-2 and 4e-5 for Llama-2-7b and Qwen2.5-7b, with a linear learning rate scheduler with a 3% warm-up stage. In GRACE, we use FAISS [35] to construct a 𝑘-NN graph and build the LSH index with 𝑘 = 10. The sensitivity of the selection budget 𝜂, the balance control hyperparameter 𝜆, the check threshold 𝛿, and the check interval 𝑡𝑐 will be discussed in Section 5.4.

5.2

Main Results

5.2.1 Effectiveness Evaluation. Table 2 summarizes the in-domain and out-of-domain average accuracy on MathInstruct under a 10%

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

training budget for all selection strategies. GRACE is the only method that consistently achieves the best in-domain and out-ofdomain averages across all three backbones, showing that our coreset construction transfers well across different model architectures and task distributions. Compared to static coreset baselines, uncertainty-based methods such as Middle Perplexity, GradN, and Least Confidence, as well as gradient-based TAGCOS, exhibit substantial performance variation across models and between in-domain and out-of-domain tasks. This suggests that their signals do not generalize robustly. This also shows that relying on a single indicator is insufficient to provide stable gains in the multitask setting. Dynamic methods that naively recalculate static criteria at fixed intervals do not uniformly improve upon their corresponding static versions and, in some cases, may even degrade performance, indicating that simple updates can introduce noise into the training dynamics. Overall, GRACE outperforms both static and dynamic alternatives on average across all evaluation regimes. 5.2.2 Efficiency Evaluation. We measure and report the end-toend running time for all methods under a consistent 10% training budget on the MathInstruct dataset, using the same hardware and optimizer settings. The reported time combines three stages: (1) the warm-up phase used by baseline methods that require an initial model to extract indicators, (2) the indicator extraction step for all scores and embeddings needed by the baselines and GRACE, and (3) the subsequent model-training phase, which includes on-the-fly indicator recalculation and coreset updates for dynamic methods. As Figure 3 shows, the uncertainty-based and the geometricbased static methods are the fastest overall because they perform feature or score extraction only once at the beginning and then train on a fixed coreset without further updates. However, the gradient-based method TAGCOS uses noticeably more time than all other methods because it needs to compute and store full gradient vectors over the training set, which is substantially more expensive than extracting forward-pass indicators. For dynamic baselines, the methods that require full feature or score extraction incur higher runtime, as they need to refresh their coresets at fixed intervals. Despite adding extra overhead through warm-up and adaptive updates over static settings, GRACE is still more efficient than entirely dynamic strategies, which are costly due to repeated recomputation and coreset re-selection. This highlights that GRACE achieves a well-balanced trade-off between dynamic settings and computational efficiency.

5.3

Ablation Study

In this section, we apply several ablation variants of GRACE to test the components and designs: • GRACE\R: GRACE excludes the representation score 𝑅(·) and only uses the importance score 𝐼ˆ(·). • GRACE\I: GRACE excludes the importance score 𝐼ˆ(·) and only uses the representation score 𝑅(·). • GRACE\Update: GRACE without any coreset update strategy. • GRACE\AdaUpdate: GRACE without the adaptive coreset update strategy. Coreset is updated at every interval.

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Tang et al.

Table 2: MathInstruct results with 10% training budget. We report in-domain (GSM8K, MATH, NumGlue) and out-of-domain (SVAMP, DeepMind, SimuLeq) average accuracies (%).

Type

Methods

Base (Pretrained Model) Random Middle Perplexity Facility Location DivIR Long4Align GradN Least Confidence TAGCOS Fix Interval Random Fix Interval Middle Perplexity Fix Interval Facility Location kMQ GRACE

Static

Dynamic

Phi-2 In-domain Out-domain 19.66 22.96 48.35 50.79 47.46 47.55 46.16 48.89 47.58 52.16 42.54 36.11 43.00 39.89 46.93 45.49 43.59 42.94 47.00 50.07 46.92 47.31 47.38 48.88 45.90 48.26 50.54 55.27

Total Time (h)

Qwen2.5-7B In-domain Out-domain 47.73 58.39 60.66 63.39 61.02 62.07 60.66 65.26 61.34 64.23 59.91 64.96 60.54 60.64 61.47 59.57 56.24 54.64 60.06 61.14 60.17 61.41 61.23 61.57 60.85 59.73 62.19 67.12

Table 3: Ablation Experiments to test the Effect of Scores. In means in-domain tasks, and Out means out-of-domain tasks.

51 49 47 45 12

Model

10 8 6 4 2

GR AC E

Dy na

TA GC

ad N Gr

g4 Ali gn

Lo n

Di vIR

Figure 3: Time Comparison As shown in Table 3, GRACE\R suffers from a performance drop in generalization according to the performance decrease on out-ofdomain tasks. GRACE\I results in an even sharper performance drop, showing that informativeness is a critical signal for coreset selection. Using both components jointly achieves the highest overall accuracy, confirming their complementarity. In addition, incorporating the update strategy is essential for coreset effectiveness, as GRACE\Update shows significant performance degradation, particularly on out-of-domain tasks. On the other hand, GRACE\AdaUpdate yields only marginal improvements or even worse results compared to the adaptive strategy. GRACE adopts an adaptive strategy triggered only when training dynamics shift significantly and can achieve the best performance, confirming that well-timed, signal-driven updates are more effective than frequent but unconditioned ones.

5.4

Llama2-7B In-domain Out-domain 3.39 2.56 22.66 17.57 22.90 18.33 21.01 15.54 23.33 21.90 15.16 10.61 19.30 15.18 22.34 18.13 19.44 16.12 20.65 18.80 22.24 17.05 22.13 17.44 22.47 16.21 23.89 24.05

Parameter Sensitivity

In this section, we systematically probe key hyper-parameters of GRACE, including the training budget 𝜂, representation-importance balance 𝜆, adaptive checking threshold 𝛿, and checking interval

G·\I G·\R G·\Update G·\AdaUpdate GRACE

Phi-2 In Out 48.49 52.98 50.23 54.82 48.79 51.54 50.08 53.03 50.54 55.27

Llama-2 In Out 22.78 18.40 21.67 21.22 23.42 23.62 23.19 22.57 23.89 24.05

𝑡𝑐 , to reveal how each one influences performance. We conduct sensitivity experiments on the Phi-2 and Llama2-7b models. 5.4.1 Selection budget 𝜂. Figure 4 reports the accuracy of GRACE and all baseline methods on Phi-2 and Llama2-7b under selection budgets 𝜂 ∈ {2%, 5%, 10%, 20%, 30%}, for both in-domain and outof-domain tasks. Across models, domains, and budgets, GRACE is consistently the best performing methods, demonstrating its robustness to budget constraints. In the extremely low-budget regime, where many static and dynamic baselines suffer sharp drops in performance, GRACE degrades much more gracefully and still secures substantial gains, showing its effectiveness under severe training constraints. Compared to static methods, GRACE achieves a more stable improvement as the budget increases, suggesting that dynamic settings help to better align the selected coreset with the evolving model needs. While dynamic baselines do benefit from periodic updates, they still lag behind GRACE in most settings, and sometimes they show fluctuations in performance when the budget increases. This indicates that while periodic updates do help selection strategies improve performance, they may suffer from problems due to simple update schedules or less effective selection criteria. Overall, the figure illustrates that GRACE combines strong performance across different budgets with stable, monotonic gains as more data is allowed, achieving robust coreset quality.

GRACE: A Dynamic Coreset Selection Framework for Large Language Model Optimization Phi-2 In-domain

Phi-2 Out-domain

Accuracy

40 2 5

10 20 Select budget (%)

Random Middle Perplexity Facility Location

15 2 5

10 20 Select budget (%)

DivIR Long4Align GradN

Llama2 Out-domain

Llama2 In-domain

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

10 2 5

Least Confidence TAGCOS Fix Interval Random

10 20 Select budget (%)

2 5

Fix Interval Middle Perplexity Fix Interval Facility Location

10 20 Select budget (%)

kMQ GRACE

Figure 4: Experiment results under different budgets on MathInstruct

Accuracy (%)

26 54 51 48 In-domain Out-of-domain

45 42

0.0

0.2 0.4 0.6 0.8 Balance Control λ

Accuracy (%)

51 In-domain Out-of-domain

48 0.0

0.2 0.4 0.6 0.8 Balance Control λ

1.0

24 22 20

0.1 0.2 0.3 Check Threshold δ

Figure 7: 𝛿 for Phi-2

In-domain Out-of-domain 0.0

0.1 0.2 0.3 Check Threshold δ

Figure 8: 𝛿 for Llama2-7b 26 Accuracy (%)

57 Accuracy (%)

0.0

can see that extremely low thresholds (𝛿 ≈ 0) result in frequent updates, similar to a strategy that is not adaptive. In contrast, high thresholds (i.e., 𝛿 ≥ 0.3) suppress updates and reduce the method to a static strategy. We can see that the best performance is observed under moderate thresholds, indicating that infrequent but strategically timed updates are adequate for a dynamic coreset strategy. This confirms that excessive updates may cause instability in the coreset, whereas insufficient updates result in outdated importance scores and degrade performance. Thus, a balanced choice matters.

54 51 In-domain Out-of-domain

48 45

In-domain Out-of-domain

Figure 6: 𝜆 for Llama2-7b

1.0

Figure 5: 𝜆 for Phi-2

1/8

1/4 1/2 Sample Fraction tc/e

Figure 9: 𝑡𝑐 /T𝑒 for Phi-2

24 22 In-domain Out-of-domain

20 18

1/8

1/4 1/2 Sample Fraction tc/e

Figure 10: 𝑡𝑐 /T𝑒 for Llama2

5.4.2 Balance Control 𝜆. We vary the balancing coefficient 𝜆 from Equation (16) as 𝜆 ∈ {0, 0.2, 0.4, 0.6, 0.8, 1} and plot the relationship between 𝜆 and performance on both Phi-2 and Llama2-7b models, referring to Figure 5 and Figure 6. Both models exhibit a non-monotonic trend, where the performance initially improves when 𝜆 increases from 0 and peaks around intermediate values before degrading as 𝜆 approaches 1. This pattern confirms that neither component alone is sufficient. Typically, Llama2-7b shows sharper performance variance according to the change in 𝜆, which might be because larger models may be more sensitive to the balance between diversity and informativeness due to their higher capacity to exploit subtle distributional coverage. 5.4.3 Checking Threshold 𝛿. In Figure 7 and 8, we present how GRACE performs under different settings of the checking threshold 𝛿 in Equation (18). With varying 𝛿 ∈ [0, 0.35] at a step of 0.05, we

5.4.4 Checking interval 𝑡𝑐 and Sample Fraction 𝑡𝑐 /T𝑒 . To enable more adaptive coreset updates, we partition the training process into multiple subsets, allowing update checks and reselection to occur more flexibly. Suppose training steps in one epoch T𝑒 , we define the Sample Fraction as the ratio of the checking interval 𝑡𝑐 to T𝑒 , computed by 𝑡𝑐 /T𝑒 . Here, we vary 𝑡𝑐 /T𝑒 ∈ {0.125, 0.25, 0.5, 1}. We then analyze how different 𝑡𝑐 /T𝑒 affects overall performance, as shown in Figure 9 and 10. We observe that in-domain performance is relatively stable across different interval settings. However, using a moderate check interval tends to outperform both frequent and coarse settings. In addition, out-of-domain accuracy appears to be more sensitive to the chunk size. These results show that a balanced update interval is preferable for maximizing overall performance.

5.5

Evaluation on Additional Datasets

We further evaluate GRACE on two additional benchmarks to assess its generalization beyond mathematical problems. Specifically, we consider a domain-specific QA dataset, BioInstruct, and a dialog summarization dataset, DialogSum, following the same training protocol as in the main experiments, and evaluate on three budgets. 5.5.1 Effectiveness Evaluation. Table 4 and Table 5 show the performance comparison on two additional datasets for QA and summarization tasks. GRACE outperforms all the static and dynamic baselines at comparable budgets. On BioInstruct, the behavior across budgets is quite heterogeneous. The performance may drop significantly even if the selection and training budget is increased. This suggests that on this relatively small, domain-specific QA dataset, simply adding more data does not always help if the selection criterion only focuses on very easy or very hard samples. GRACE runs remain aligned with best baselines and often improve upon them, demonstrating the powerful adaptive ability under different conditions. On DialogSum, the overall task appears easier for all methods, and the gap between strong baselines is narrower. In this

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Tang et al.

Table 4: ROUGE-L results on BioInstruct

Type -

Static

Dynamic

Models Selection Budget Base (Pretrained Model) Random Middle Perplexity Facility Location DivIR Long4Align GradN Least Confidence TAGCOS Fix Interval Random Fix Interval Middle Perplexity Fix Interval Facility Location kMQ GRACE

Llama2-7b 10% 20% 30% 19.70 32.57 33.38 33.47 32.62 32.81 33.10 32.97 33.02 32.85 31.83 33.36 33.34 28.29 29.07 29.80 30.77 33.44 33.60 31.52 31.54 32.01 31.33 33.78 34.12 33.06 33.18 33.05 33.25 32.79 33.02 32.81 32.75 33.04 33.08 32.89 33.58 33.58 33.97 34.14

10% 33.63 31.24 35.57 36.91 33.54 32.21 34.52 33.67 32.72 31.48 37.77 32.72 39.61

Phi-2 20% 34.77 23.13 23.36 37.85 33.93 33.66 29.29 30.01 36.59 24.46 34.96 38.49 30.09 40.00

30% 20.72 16.77 35.16 27.43 34.61 22.11 34.64 34.58 17.95 37.51 31.62 33.01 39.80

Qwen2.5-7b 10% 20% 30% 23.62 38.10 37.03 36.85 38.98 38.43 38.07 39.41 37.19 37.62 38.47 38.47 38.75 33.29 33.23 33.67 38.91 38.18 37.37 34.82 34.40 34.58 38.78 38.69 38.50 38.09 37.13 37.30 38.94 38.05 38.30 37.22 35.99 36.03 39.02 37.74 37.17 39.71 39.15 38.96

Table 5: ROUGE-L results on DialogSum

Type -

Static

Dynamic

Llama2-7b 20% 30% 15.92 37.38 37.98 38.86 37.12 38.35 38.55 37.46 38.52 39.21 37.52 38.54 39.11 32.80 34.48 35.66 36.90 37.91 39.28 36.80 38.02 38.19 37.48 37.38 38.62 36.23 38.02 39.14 37.55 38.48 39.00 35.91 37.47 37.59 36.46 38.38 38.91 37.63 38.70 39.38 10%

regime, GRACE yields consistent but moderate improvements. For all three models, GRACE outperforms the best method at all budgets. Overall, these two datasets show that GRACE generalizes beyond mathematical problems to other tasks, such as natural language question answering and summarization.

Conclusion

In this paper, we propose GRACE, a dynamic coreset selection framework for efficient large language model training. Combining the representation diversity and gradient-based importance metrics with a 𝑘-NN graph-based update mechanism, GRACE adapts coresets to evolving training dynamics while reducing computational costs. Experiments on Llama2-7b, Phi-2 and Qwen2.5-7b models

10% 36.06 36.35 36.22 37.22 31.16 35.02 36.41 35.51 36.01 35.85 35.56 35.33 37.61

Phi-2 20% 22.24 37.47 37.23 36.76 38.78 33.92 35.80 36.99 36.84 36.77 36.93 36.96 37.27 38.91

30% 37.67 37.68 38.44 39.13 34.90 37.10 37.72 38.01 37.97 37.49 38.09 37.93 39.39

Qwen2.5-7b 10% 20% 30% 16.97 37.93 38.99 39.28 37.63 39.07 39.19 38.12 39.28 38.99 39.61 40.14 40.05 32.55 34.75 35.87 37.38 38.45 38.66 37.83 38.64 39.12 38.23 38.97 39.50 38.84 38.81 39.35 38.06 39.20 39.41 37.81 38.92 39.18 37.59 39.24 39.34 39.86 40.31 40.29

across three benchmarks demonstrate that GRACE outperforms baselines in both efficiency and performance, making it a scalable and effective solution for resource-constrained LLM training.

References [1] Abhinab Acharya, Dayou Yu, Qi Yu, and Xumin Liu. 2024. Balancing Feature Similarity and Label Variability for Optimal Size-Aware One-shot Subset Selection. In Forty-First International Conference on Machine Learning. [2] Meta AI. 2023. Llama 2: Open Foundation and Fine-Tuned Chat Models. arXiv:2307.09288 [cs.CL] https://arxiv.org/abs/2307.09288 [3] Meta AI. 2024. The Llama 3 Herd of Models. arXiv:2407.21783 [cs.AI] https: //arxiv.org/abs/2407.21783 [4] 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. 2024. A Survey on Data Selection for Language Models. Transactions on Machine

GRACE: A Dynamic Coreset Selection Framework for Large Language Model Optimization

Learning Research (2024). https://openreview.net/forum?id=XfHWcNTSHp Survey Certification. [5] Zachary Ankner, Cody Blakeney, Kartik Sreenivasan, Max Marion, Matthew L. Leavitt, and Mansheej Paul. 2024. Perplexed by Perplexity: Perplexity-Based Data Pruning With Small Reference Models. doi:10.48550/ARXIV.2405.20541 [6] Simran Arora, Brandon Yang, Sabri Eyuboglu, Avanika Narayan, Andrew Hojel, Immanuel Trummer, and Christopher Ré. 2023. Language Models Enable Simple Systems for Generating Structured Views of Heterogeneous Data Lakes. Proc. VLDB Endow. 17, 2 (Oct. 2023), 92–105. doi:10.14778/3626292.3626294 [7] Tianyi Bai, Ling Yang, Zhen Hao Wong, Jiahui Peng, Xinlin Zhuang, Chi Zhang, Lijun Wu, Jiantao Qiu, Wentao Zhang, Binhang Yuan, and Conghui He. 2024. Multi-Agent Collaborative Data Selection for Efficient LLM Pretraining. arXiv:2410.08102 [cs] doi:10.48550/arXiv.2410.08102 [8] Gantavya Bhatt, Yifang Chen, Arnav M. Das, Jifan Zhang, Sang T. Truong, Stephen Mussmann, Yinglun Zhu, Jeffrey Bilmes, Simon S. Du, Kevin Jamieson, Jordan T. Ash, and Robert D. Nowak. 2024. An Experimental Design Framework for Label-Efficient Supervised Finetuning of Large Language Models. arXiv:2401.06692 [cs] doi:10.48550/arXiv.2401.06692 [9] Léon Bottou. 2012. Stochastic gradient descent tricks. In Neural networks: tricks of the trade: second edition. Springer, 421–436. [10] Valérie Castin, Pierre Ablin, and Gabriel Peyré. 2024. How Smooth Is Attention?. In Forty-first International Conference on Machine Learning. https: //openreview.net/forum?id=aP0H8A1ywk [11] Chengliang Chai, Jiabin Liu, Nan Tang, Ju Fan, Dongjing Miao, Jiayi Wang, Yuyu Luo, and Guoliang Li. 2023. GoodCore: Data-effective and Data-efficient Machine Learning through Coreset Selection over Incomplete Data. Proc. ACM Manag. Data 1, 2 (June 2023), 157:1–157:27. doi:10.1145/3589302 [12] Chengliang Chai, Jiayi Wang, Nan Tang, Ye Yuan, Jiabin Liu, Yuhao Deng, and Guoren Wang. 2023. Efficient Coreset Selection with Cluster-based Methods. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD ’23). Association for Computing Machinery, New York, NY, USA, 167–178. doi:10.1145/3580305.3599326 [13] Hao Chen, Yiming Zhang, Qi Zhang, Hantao Yang, Xiaomeng Hu, Xuetao Ma, Yifan Yanggong, and Junbo Zhao. 2023. Maybe Only 0.5% Data Is Needed: A Preliminary Exploration of Low Training Data Instruction Tuning. arXiv:2305.09246 [cs] doi:10.48550/arXiv.2305.09246 [14] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde De Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. 2021. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374 (2021). [15] Yulong Chen, Yang Liu, Liang Chen, and Yue Zhang. 2021. DialogSum: A Real-Life Scenario Dialogue Summarization Dataset. In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli (Eds.). Association for Computational Linguistics, Online, 5062–5074. doi:10.18653/v1/2021.findings-acl.449 [16] Yeseul Cho, Baekrok Shin, Changmin Kang, and Chulhee Yun. 2025. Lightweight Dataset Pruning without Full Training via Example Difficulty and Prediction Uncertainty. arXiv:2502.06905 [cs] doi:10.48550/arXiv.2502.06905 [17] Marina Danilova, Pavel Dvurechensky, Alexander Gasnikov, Eduard Gorbunov, Sergey Guminov, Dmitry Kamzolov, and Innokentiy Shibaev. 2020. Recent Theoretical Advances in Non-Convex Optimization. arXiv:2012.06188 [math.OC] [18] DeepSeek-AI, Aixin Liu, Bei Feng, et al. 2024. DeepSeek-V3 Technical Report. arXiv:2412.19437 [cs.CL] [19] Alexander Vladimirovich Demidovskij, Aleksei Trutnev, Artem Tugarev, Igor Salnikov, and Stanislav Pavlov. 2023. DAREL: Data Reduction with Losses for Training Acceleration of Real and Hypercomplex Neural Networks. In Workshop on Advancing Neural Network Training: Computational Efficiency, Scalability, and Resource Optimization (WANT@NeurIPS 2023). [20] Zhiwei Deng, Tao Li, and Yang Li. 2024. Influential Language Data Selection via Gradient Trajectory Pursuit. arXiv:2410.16710 doi:10.48550/arXiv.2410.16710 [21] Tim Dettmers, Artidoro Pagnoni, Ari Holtzman, and Luke Zettlemoyer. 2023. Qlora: Efficient finetuning of quantized llms. Advances in neural information processing systems 36 (2023), 10088–10115. [22] Ju Fan, Zihui Gu, Songyue Zhang, Yuxin Zhang, Zui Chen, Lei Cao, Guoliang Li, Samuel Madden, Xiaoyong Du, and Nan Tang. 2024. Combining Small Language Models and Large Language Models for Zero-Shot NL2SQL. Proc. VLDB Endow. 17, 11 (July 2024), 2750–2763. doi:10.14778/3681954.3681960 [23] Dan Feldman. 2020. Introduction to Core-sets: an Updated Survey. arXiv:2011.09384 [cs.LG] [24] Victor Giannakouris and Immanuel Trummer. 2025. 𝜆 -Tune: Harnessing Large Language Models for Automated Database System Tuning. Proc. ACM Manag. Data 3, 1, Article 2 (Feb. 2025), 26 pages. doi:10.1145/3709652 [25] Aviv Hadar, Tova Milo, and Kathy Razmadze. 2024. Datamap-Driven Tabular Coreset Selection for Classifier Training. Proc. VLDB Endow. 18, 3 (Nov. 2024), 876–888. doi:10.14778/3712221.3712249 [26] Junxian He, Chunting Zhou, Xuezhe Ma, Taylor Berg-Kirkpatrick, and Graham Neubig. 2022. Towards a Unified View of Parameter-Efficient Transfer Learning.

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

In International Conference on Learning Representations. https://openreview. net/forum?id=0RDcd5Axok [27] Yexiao He, Ziyao Wang, Zheyu Shen, Guoheng Sun, Yucong Dai, Yongkai Wu, Hongyi Wang, and Ang Li. 2024. SHED: Shapley-Based Automated Dataset Refinement for Instruction Fine-Tuning. arXiv:2405.00705 [cs] doi:10.48550/ arXiv.2405.00705 [28] Dorit S Hochbaum. 1997. Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems. Approximation algorithms for NP-hard problems (1997), 94–143. [29] Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. 2022. Training compute-optimal large language models. In Proceedings of the 36th International Conference on Neural Information Processing Systems. 30016–30030. [30] Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin De Laroussilhe, Andrea Gesmundo, Mona Attariyan, and Sylvain Gelly. 2019. Parameter-efficient transfer learning for NLP. In International conference on machine learning. PMLR, 2790–2799. [31] Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, Weizhu Chen, et al. 2022. Lora: Low-rank adaptation of large language models. ICLR 1, 2 (2022), 3. [32] Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing (Dallas, Texas, USA) (STOC ’98). Association for Computing Machinery, New York, NY, USA, 604–613. doi:10.1145/ 276698.276876 [33] Berivan Isik, Natalia Ponomareva, Hussein Hazimeh, Dimitris Paparas, Sergei Vassilvitskii, and Sanmi Koyejo. 2024. Scaling Laws for Downstream Task Performance of Large Language Models. doi:10.48550/ARXIV.2402.04177 [34] Ayrton San Joaquin, Bin Wang, Zhengyuan Liu, Nicholas Asher, Brian Lim, Philippe Muller, and Nancy Chen. 2024. In2Core: Leveraging Influence Functions for Coreset Selection in Instruction Finetuning of Large Language Models. arXiv:2408.03560 [cs, stat] doi:10.48550/arXiv.2408.03560 [35] Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data 7, 3 (2019), 535–547. [36] Moe Kayali, Anton Lykov, Ilias Fountalis, Nikolaos Vasiloglou, Dan Olteanu, and Dan Suciu. 2024. Chorus: Foundation Models for Unified Data Discovery and Exploration. Proc. VLDB Endow. 17, 8 (April 2024), 2104–2114. doi:10.14778/ 3659437.3659461 [37] Krishnateja Killamsetty, Durga S, Ganesh Ramakrishnan, Abir De, and Rishabh Iyer. 2021. GRAD-MATCH: Gradient Matching Based Data Subset Selection for Efficient Deep Model Training. In Proceedings of the 38th International Conference on Machine Learning. PMLR, 5464–5474. [38] Teddy Lazebnik, Amit Somech, and Abraham Itzhak Weinberg. 2022. SubStrat: A Subset-Based Optimization Strategy for Faster AutoML. Proc. VLDB Endow. 16, 4 (Dec. 2022), 772–780. doi:10.14778/3574245.3574261 [39] Boyan Li, Yuyu Luo, Chengliang Chai, Guoliang Li, and Nan Tang. 2024. The Dawn of Natural Language to SQL: Are We Fully Ready? Proc. VLDB Endow. 17, 11 (July 2024), 3318–3331. doi:10.14778/3681954.3682003 [40] Haoyang Li, Shimin Di, Lei Chen, and Xiaofang Zhou. 2024. E2GCL: Efficient and Expressive Contrastive Learning on Graph Neural Networks. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 859–873. [41] Haoyang Li, Shimin Di, Calvin Hong Yi Li, Lei Chen, and Xiaofang Zhou. 2024. Fight Fire with Fire: Towards Robust Graph Neural Networks on Dynamic Graphs via Actively Defense. Proceedings of the VLDB Endowment 17, 8 (2024), 2050– 2063. [42] Haoyang Li, Yiming Li, Anxin Tian, Tianhao Tang, Zhanchao Xu, Xuejia Chen, Nicole Hu, Wei Dong, Qing Li, and Lei Chen. 2024. A survey on large language model acceleration based on kv cache management. arXiv preprint arXiv:2412.19442 (2024). [43] Ming Li, Yong Zhang, Zhitao Li, Jiuhai Chen, Lichang Chen, Ning Cheng, Jianzong Wang, Tianyi Zhou, and Jing Xiao. 2024. From Quantity to Quality: Boosting LLM Performance with Self-Guided Data Selection for Instruction Tuning. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), NAACL 2024, Mexico City, Mexico, June 16-21, 2024, Kevin Duh, Helena Gómez-Adorno, and Steven Bethard (Eds.). Association for Computational Linguistics, 7602–7635. arXiv:2308.12032 [cs] doi:10.18653/V1/ 2024.NAACL-LONG.421 [44] Xiang Lisa Li and Percy Liang. 2021. Prefix-tuning: Optimizing continuous prompts for generation. arXiv preprint arXiv:2101.00190 (2021). [45] Yuanzhi Li, Sébastien Bubeck, Ronen Eldan, Allie Del Giorno, Suriya Gunasekar, and Yin Tat Lee. 2023. Textbooks Are All You Need II: phi-1.5 technical report. arXiv:2309.05463 [cs.CL] [46] Yiming Li, Yanyan Shen, and Lei Chen. 2022. Camel: Managing Data for Efficient Stream Learning. In Proceedings of the 2022 International Conference on Management of Data (SIGMOD ’22). Association for Computing Machinery, New York, NY, USA, 1271–1285. doi:10.1145/3514221.3517836

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

[47] Zhaodonghui Li, Haitao Yuan, Huiming Wang, Gao Cong, and Lidong Bing. 2024. LLM-R2: A Large Language Model Enhanced Rule-Based Rewrite System for Boosting Query Efficiency. Proc. VLDB Endow. 18, 1 (Sept. 2024), 53–65. doi:10.14778/3696435.3696440 [48] Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song, and Yufa Zhou. 2024. Multi-Layer Transformers Gradient Can Be Approximated in Almost Linear Time. arXiv:2408.13233 [cs] doi:10.48550/arXiv.2408.13233 [49] Chin-Yew Lin. 2004. ROUGE: A Package for Automatic Evaluation of Summaries. In Text Summarization Branches Out. Association for Computational Linguistics, Barcelona, Spain, 74–81. https://aclanthology.org/W04-1013/ [50] Hanmo Liu, Shimin Di, Haoyang Li, Shuangyin Li, Lei Chen, and Xiaofang Zhou. 2024. Effective Data Selection and Replay for Unsupervised Continual Learning. In 40th IEEE International Conference on Data Engineering, ICDE 2024, Utrecht, The Netherlands, May 13-16, 2024. IEEE, 1449–1463. doi:10.1109/ICDE60146.2024. 00119 [51] Stuart Lloyd. 1982. Least squares quantization in PCM. IEEE transactions on information theory 28, 2 (1982), 129–137. [52] Yuze Lou, Chuan Lei, Xiao Qin, Zichen Wang, Christos Faloutsos, Rishita Anubhai, and Huzefa Rangwala. 2024. DATALORE: Can a Large Language Model Find All Lost Scrolls in a Data Repository?. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). 5170–5176. doi:10.1109/ICDE60146.2024.00388 [53] Lei Ma, Lei Cao, Peter M. VanNostrand, Dennis M. Hofmann, Yao Su, and Elke A. Rundensteiner. 2024. Pluto: Sample Selection for Robust Anomaly Detection on Polluted Log Data. Proc. ACM Manag. Data 2, 4, Article 203 (Sept. 2024), 25 pages. doi:10.1145/3677139 [54] Max Marion, Ahmet Üstün, Luiza Pozzobon, Alex Wang, Marzieh Fadaee, and Sara Hooker. 2023. When Less Is More: Investigating Data Pruning for Pretraining LLMs at Scale. arXiv:2309.04564 [cs] doi:10.48550/arXiv.2309.04564 [55] Dheeraj Mekala, Alex Nguyen, and Jingbo Shang. 2024. Smaller Language Models Are Capable of Selecting Instruction-Tuning Training Data for Larger Language Models. doi:10.48550/ARXIV.2402.10430 [56] Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. 2020. Coresets for Data-efficient Training of Machine Learning Models. In Proceedings of the 37th International Conference on Machine Learning. PMLR, 6950–6960. arXiv:1906.01827 [cs, stat] [57] Avanika Narayan, Ines Chami, Laurel Orr, and Christopher Ré. 2022. Can Foundation Models Wrangle Your Data? Proc. VLDB Endow. 16, 4 (Dec. 2022), 738–746. doi:10.14778/3574245.3574258 [58] Dang Nguyen, Wenhan Yang, Rathul Anand, Yu Yang, and Baharan Mirzasoleiman. 2024. Memory-Efficient Training of LLMs with Larger Mini-batches. arXiv:2407.19580 [cs] doi:10.48550/arXiv.2407.19580 [59] OpenAI. 2023. GPT-4 Technical Report. arXiv:2303.08774 [cs.CL] [60] Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. 2021. Deep Learning on a Data Diet: Finding Important Examples Early in Training. In Advances in Neural Information Processing Systems, Vol. 34. Curran Associates, Inc., 20596–20607. [61] Tonghui Ren, Yuankai Fan, Zhenying He, Ren Huang, Jiaqi Dai, Can Huang, Yinan Jing, Kai Zhang, Yifan Yang, and X Sean Wang. 2024. Purple: Making a large language model a better sql writer. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 15–28. [62] Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari Morcos. 2022. Beyond Neural Scaling Laws: Beating Power Law Scaling via Data Pruning. Advances in Neural Information Processing Systems 35 (Dec. 2022), 19523–19536. [63] Qwen Team. 2024. Qwen2.5: A Party of Foundation Models. https://qwenlm. github.io/blog/qwen2.5/ [64] Tristan Thrush, Christopher Potts, and Tatsunori Hashimoto. 2024. Improving Pretraining Data Using Perplexity Correlations. arXiv:2409.05816 [cs, stat] doi:10. 48550/arXiv.2409.05816 [65] Kushal Tirumala, Daniel Simig, Armen Aghajanyan, and Ari Morcos. 2023. D4: Improving LLM Pretraining via Document De-Duplication and Diversification. Advances in Neural Information Processing Systems 36 (Dec. 2023), 53983–53995. [66] Hieu Tran, Zhichao Yang, Zonghai Yao, and Hong Yu. 2024. BioInstruct: Instruction Tuning of Large Language Models for Biomedical Natural Language Processing. Journal of the American Medical Informatics Association 31, 9 (June 2024), 1821–1832. arXiv:https://academic.oup.com/jamia/articlepdf/31/9/1821/58868340/ocae122.pdf doi:10.1093/jamia/ocae122 [67] A Vaswani. 2017. Attention is all you need. Advances in Neural Information Processing Systems (2017). [68] Jiayi Wang, Chengliang Chai, Nan Tang, Jiabin Liu, and Guoliang Li. 2022. Coresets over multiple tables for feature-rich and data-efficient machine learning. Proc. VLDB Endow. 16, 1 (Sept. 2022), 64–76. doi:10.14778/3561261.3561267 [69] Shaobo Wang, Xiangqi Jin, Ziming Wang, Jize Wang, Jiajun Zhang, Kaixin Li, Zichen Wen, Zhong Li, Conghui He, Xuming Hu, and Linfeng Zhang. 2025. Data

Tang et al.

Whisperer: Efficient Data Selection for Task-Specific LLM Fine-Tuning via FewShot In-Context Learning. arXiv:2505.12212 [cs.CL] https://arxiv.org/abs/2505. 12212 [70] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. 2022. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems 35 (2022), 24824–24837. [71] Mengzhou Xia, Sadhika Malladi, Suchin Gururangan, Sanjeev Arora, and Danqi Chen. 2024. LESS: Selecting Influential Data for Targeted Instruction Tuning. In Forty-First International Conference on Machine Learning. [72] Guoliang Li Xinyang Zhao, Xuanhe Zhou. 2024. Chat2Data: An Interactive Data Analysis System with RAG, Vector Databases and LLMs. [73] Yu Yang, Hao Kang, and Baharan Mirzasoleiman. 2023. Towards Sustainable Learning: Coresets for Data-efficient Deep Learning. In Proceedings of the 40th International Conference on Machine Learning. PMLR, 39314–39330. https:// proceedings.mlr.press/v202/yang23g.html [74] Yu Yang, Siddhartha Mishra, Jeffrey N Chiang, and Baharan Mirzasoleiman. 2024. SmallToLarge (S2L): Scalable Data Selection for Fine-tuning Large Language Models by Summarizing Training Trajectories of Small Models. doi:10.48550/ ARXIV.2403.07384 [75] Junjie Oscar Yin and Alexander M Rush. 2024. Compute-constrained data selection. arXiv preprint arXiv:2410.16208 (2024). [76] Simon Yu, Liangyu Chen, Sara Ahmadian, and Marzieh Fadaee. 2024. Diversify and Conquer: Diversity-Centric Data Selection with Iterative Refinement. arXiv:2409.11378 [cs] doi:10.48550/arXiv.2409.11378 [77] Zichun Yu, Spandan Das, and Chenyan Xiong. 2024. MATES: Model-Aware Data Selection for Efficient Pretraining with Data Influence Models. doi:10.48550/ ARXIV.2406.06046 [78] Xiang Yue, Xingwei Qu, Ge Zhang, Yao Fu, Wenhao Huang, Huan Sun, Yu Su, and Wenhu Chen. 2024. MAmmoTH: Building Math Generalist Models through Hybrid Instruction Tuning. In The Twelfth International Conference on Learning Representations. https://openreview.net/forum?id=yLClGs770I [79] Chi Zhang, Huaping Zhong, Kuan Zhang, Chengliang Chai, Rui Wang, Xinlin Zhuang, Tianyi Bai, Jiantao Qiu, Lei Cao, Ju Fan, Ye Yuan, Guoren Wang, and Conghui He. 2024. Harnessing Diversity for Important Data Selection in Pretraining Large Language Models. arXiv:2409.16986 [cs] doi:10.48550/arXiv.2409.16986 [80] Jipeng Zhang, Yaxuan Qin, Renjie Pi, Weizhong Zhang, Rui Pan, and Tong Zhang. 2024. TAGCOS: Task-agnostic Gradient Clustered Coreset Selection for Instruction Tuning Data. arXiv:2407.15235 [cs] doi:10.48550/arXiv.2407.15235 [81] Hao Zhao, Maksym Andriushchenko, Francesco Croce, and Nicolas Flammarion. 2024. Long Is More for Alignment: A Simple but Tough-to-Beat Baseline for Instruction Fine-Tuning. arXiv:2402.04833 [cs] doi:10.48550/arXiv.2402.04833 [82] Haizhong Zheng, Rui Liu, Fan Lai, and Atul Prakash. 2023. Coverage-Centric Coreset Selection for High Pruning Rates. arXiv:2210.15809 [cs] doi:10.48550/ arXiv.2210.15809 [83] Haotian Zhou, Tingkai Liu, Qianli Ma, Jianbo Yuan, Pengfei Liu, Yang You, and Hongxia Yang. 2023. LoBaSS: Gauging Learnability in Supervised Fine-tuning Data. arXiv:2310.13008 [cs] doi:10.48550/arXiv.2310.13008 [84] Wei Zhou, Yuyang Gao, Xuanhe Zhou, and Guoliang Li. 2025. Cracking SQL Barriers: An LLM-based Dialect Transaltion System. Proc. ACM Manag. Data 3, 3 (SIGMOD) (2025). [85] Xuanhe Zhou, Guoliang Li, Zhaoyan Sun, Zhiyuan Liu, Weize Chen, Jianming Wu, Jiesi Liu, Ruohang Feng, and Guoyang Zeng. 2024. D-Bot: Database Diagnosis System using Large Language Models. Proc. VLDB Endow. 17, 10 (June 2024), 2514–2527. doi:10.14778/3675034.3675043

7 Appendix 7.1 Proof of Theorem 4.1 Proof. The gradient with respect to all parameters is a concatenation of gradients with respect to each parameter’s weights. Therefore, by the triangle inequality: ∥∇𝜽 L (𝑋𝑖 , 𝜽 ) − ∇𝜽 L (𝑋 𝑗 , 𝜽 )∥ ∑︁ ≤ ∥∇W L (𝑋𝑖 , 𝜽 ) − ∇W L (𝑋 𝑗 , 𝜽 )∥ W

where W ∈ {W1, W2, W𝑄 , W𝐾 , W𝑉 W𝑂 } We analyze all parameters W1 , W2 , W𝑄 , W𝐾 , W𝑉 , and W𝑂 , and combine them into the final form. Since the layer norm and activation function are generally Lipschitz continuous, we omit them from the equation.

GRACE: A Dynamic Coreset Selection Framework for Large Language Model Optimization

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

For the gradient match associated with W𝑉 , we have:

Following [48], we define: 𝑇 ×𝑑

∇W𝑉 L (𝑋𝑖 , 𝜽 )) − ∇W𝑉 L (𝑋 𝑗 , 𝜽 ))

𝐺 (X) = ∇Z L (𝑋, 𝜽 ) ∈ R

𝑇 ×𝑇

𝑇

𝑞(X) = 𝐺 (X) · (XW𝑉 W𝑂 ) ∈ R

≤ X𝑇𝑖 Z𝑖 ∇Ô𝑖 L (𝑋𝑖 , 𝜽 ))W𝑇2 W𝑇1 W𝑇𝑂

𝑝 1 (X) = ℎ(X) ⊙ 𝑞(X) ∈ R𝑇 ×𝑇

− X𝑇𝑗 Z 𝑗 ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 ))W𝑇2 W𝑇1 W𝑇𝑂

where 𝑇 is the sequential length, 𝑑 is the hidden dimension, and ⊙ is the Hadamard product. In the following analysis, we mainly use the triangle inequality and the Cauchy-Schwarz inequality, and we state them here to avoid repeated descriptions. For the gradient match associated with W1 , we have:

≤ 𝑐𝑉1 ∇Ô𝑖 L (𝑋𝑖 , 𝜽 )) − ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 )) + 𝑐𝑉3 X𝑖 − X 𝑗 + 𝑐𝑉2 Z𝑖 − Z 𝑗 where 𝑐𝑉1 = Z𝑖 X𝑇𝑖 ∥W𝑂 W1 W2 ∥

∇W1 L (𝑋𝑖 , 𝜽 )) − ∇W1 L (𝑋 𝑗 , 𝜽 )) ≤

𝑐𝑉3 = ∥W𝑂 W1 W2 ∥ ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 )) ∥Z𝑖 ∥

W𝑇𝑂 W𝑇𝑉 X𝑇𝑖 Z𝑇𝑖 ∇Ô𝑖 L (𝑋𝑖 , 𝜽 ))W𝑇2

𝑐𝑉2 = ∥W𝑂 W1 W2 ∥ ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 ))

− W𝑇𝑂 W𝑇𝑉 X𝑇𝑗 Z𝑇𝑗 ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 ))W𝑇2 ≤ 𝑐 11

X𝑗

For gradient match associated with W𝑄 and W𝐾 , we first define:

∇Ô𝑖 L (𝑋𝑖 , 𝜽 )) − ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 ))

𝑐 3 = Z𝑖 ⊙ ∇Ô𝑖 L (𝑋𝑖 , 𝜽 ))X𝑇𝑖

+ 𝑐 31 X𝑖 − X 𝑗 + 𝑐 21 Z𝑖 − Z 𝑗

where 𝑐 11 = ∥Z𝑖 X𝑖 ∥ ∥W𝑉 W𝑂 ∥ ∥W2 ∥ ,

∥W1 W2 ∥ ∥W𝑉 W𝑂 ∥ ∥X𝑖 ∥ + X 𝑗 2 𝑐 4 = ∥W1 W2 ∥ ∥W𝑉 W𝑂 ∥ X 𝑗

𝑐 31 = ∥W𝑉 W𝑂 ∥ ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 )) ∥Z𝑖 ∥ ∥W2 ∥ ,

𝑐 5 = ∥diag(𝑝 1 (X𝑖 )𝟙𝑛 )Z𝑖 ∥ ∥X𝑖 ∥ + X 𝑗

𝑐 21 = ∥W𝑉 W𝑂 ∥ ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 ))

𝑐 6 = (∥diag(𝑝 1 (X𝑖 )𝟙𝑛 )Z𝑖 ∥) 2 𝑐7 = X𝑗 ℎ(X) 𝑗

X 𝑗 ∥W2 ∥

For the gradient match associated with W2 , we have:

and we further define: ∇W2 L (𝑋𝑖 , 𝜽 )) − ∇W2 L (𝑋 𝑗 , 𝜽 ))

𝑐 3 = (𝑐 3 + 𝑐 5 ) ∥W𝐾 ∥ , 𝑐 4 = 𝑐 4 ∥W𝐾 ∥

≤ W𝑇1 W𝑇𝑂 W𝑇𝑉 X𝑇𝑖 Z𝑇𝑖 ∇Ô𝑖 L (𝑋𝑖 , 𝜽 ))

𝑐 2 = 𝑐 6 ∥W𝐾 ∥ , 𝑐 5 = 𝑐 7 ∥W𝐾 ∥

− W𝑇1 W𝑇𝑂 W𝑇𝑉 X𝑇𝑗 Z𝑇𝑗 ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 ))W𝑇2

𝑐 3𝐾 = (𝑐 3 + 𝑐 5 ) W𝑄 , 𝑐 4𝐾 = 𝑐 4 W𝑄

𝑄

𝑐 2𝐾 = 𝑐 6 W𝑄 , 𝑐 5𝐾 = 𝑐 7 W𝑄

≤ 𝑐 12 ∇Ô𝑖 L (𝑋𝑖 , 𝜽 )) − ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 ))

So for W𝑄 we have:

+ 𝑐 32 X𝑖 − X 𝑗 + 𝑐 22 Z𝑖 − Z 𝑗

∇W𝑄 L (𝑋𝑖 , 𝜽 )) − ∇W𝑄 L (𝑋 𝑗 , 𝜽 ))

where 𝑐 12 = ∥Z𝑖 X𝑖 ∥ ∥W𝑉 W𝑂 W1 ∥

𝑄

𝑐 32 = ∥W𝑉 W𝑂 W1 ∥ ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 )) ∥Z𝑖 ∥

≤ 𝑐 3 X𝑖 − X 𝑗 𝑄

𝑐 22 = ∥W𝑉 W𝑂 W1 ∥ ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 ))

X𝑗

+ 𝑐 4 Z𝑖 ⊙ ∇Ô𝑖 L (𝑋𝑖 , 𝜽 ))X𝑇𝑖 − Z 𝑗 ⊙ ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 ))X𝑇𝑗 𝑄

For the gradient match associated with W𝑂 , we have:

+ 𝑐 2 Z𝑖 − Z 𝑗 𝑄

+ 𝑐 5 diag(𝑝 1 (X𝑖 )𝟙𝑛 ) − diag(𝑝 1 (X 𝑗 )𝟙𝑛 )

∇W𝑂 L (𝑋𝑖 , 𝜽 )) − ∇W𝑂 L (𝑋 𝑗 , 𝜽 ))

Similar for W𝐾 we have:

≤ W𝑇𝑉 X𝑇𝑖 Z𝑖 ∇Ô𝑖 L (𝑋𝑖 , 𝜽 ))W𝑇2 W𝑇1

∇W𝐾 L (𝑋𝑖 , 𝜽 )) − ∇W𝐾 L (𝑋 𝑗 , 𝜽 ))

− W𝑇𝑉 X𝑇𝑗 Z 𝑗 ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 ))W𝑇2 W𝑇1

≤ 𝑐 3𝐾 X𝑖 − X 𝑗

≤ 𝑐𝑂 1 ∇Ô𝑖 L (𝑋𝑖 , 𝜽 )) − ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 ))

+ 𝑐 4𝐾 Z𝑖 ⊙ ∇Ô𝑖 L (𝑋𝑖 , 𝜽 ))X𝑇𝑖 − Z 𝑗 ⊙ ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 ))X𝑇𝑗

+ 𝑐𝑂 3 X𝑖 − X 𝑗

+ 𝑐 2𝐾 Z𝑖 − Z 𝑗

+ 𝑐𝑂 2 Z𝑖 − Z 𝑗

+ 𝑐 5𝐾 diag(𝑝 1 (X𝑖 )𝟙𝑛 ) − diag(𝑝 1 (X 𝑗 )𝟙𝑛 )

𝑇 where 𝑐 𝑂 1 = ∥W1 W2 ∥ X𝑖 Z𝑖 ∥W𝑉 ∥

𝑐𝑂 3 = ∥W1 W2 ∥ ∥W𝑉 ∥ ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 )) ∥Z𝑖 ∥ 𝑐𝑂 2 = ∥W1 W2 ∥ ∥W𝑉 ∥ ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 ))

X𝑗

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

Tang et al.

7.2

Summarize the above, we have: ∇𝜽 L (𝑋𝑖 , 𝜽 )) − ∇𝜽 L (𝑋 𝑗 , 𝜽 )) ∑︁ ≤ ∇W𝑘 L (𝑋𝑖 , 𝜽 )) − ∇W𝑘 L (𝑋 𝑗 , 𝜽 )) 𝑘 ∈ {𝑄,𝐾,𝑉 ,𝑂,1,2} 𝑉 ≤ (𝑐 11 + 𝑐 12 + 𝑐 𝑂 1 + 𝑐 1 )·

∇Ô𝑖 L (𝑋𝑖 , 𝜽 )) − ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 ))

(24)

𝑉 + (𝑐 21 + 𝑐 22 + 𝑐 𝑂 2 + 𝑐 2 ) Z𝑖 − Z 𝑗

(25)

𝑄 𝑉 𝐾 + (𝑐 31 + 𝑐 32 + 𝑐 𝑂 3 + 𝑐3 + 𝑐3 + 𝑐3 ) 𝑄 + (𝑐 4 + 𝑐 4𝐾 )·

X𝑖 − X 𝑗

Z𝑖 ⊙ ∇Ô𝑖 L (𝑋𝑖 , 𝜽 ))X𝑇𝑖 − Z 𝑗 ⊙ ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 ))X𝑇𝑗

(26)

(27)

𝑄

+ (𝑐 5 + 𝑐 5𝐾 ) diag(𝑝 1 (X𝑖 )𝟙𝑛 ) − diag(𝑝 1 (X 𝑗 )𝟙𝑛 )

(28)

With local Lipschitz continuity of the attention mechanism [10], we have for Equation (26) Z𝑖 − Z 𝑗 ≤ 𝛼 X𝑖 − X 𝑗

∇Ô𝑖 L (𝑋𝑖 , 𝜽 ))X𝑇𝑖 − ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 ))X𝑇𝑗 ≤ 𝛽 ∇Ô𝑖 L (𝑋𝑖 , 𝜽 ))X𝑇𝑖 − ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 ))X𝑇𝑗 ≤ 𝛽 ∥X𝑖 ∥ ∇Ô𝑖 L (𝑋𝑖 , 𝜽 ) − ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 ) + 𝛽 ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 )

Proof of Theorem 4.5

𝑘 ) is monotone increasing and subLemma 7.1. The Δ𝑅𝑆 (𝑋𝑖 |D𝑐𝑜𝑟𝑒 modular.

Z𝑖 ⊙ ∇Ô𝑖 L (𝑋𝑖 , 𝜽 ))X𝑇𝑖 − Z 𝑗 ⊙ ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 ))X𝑇𝑗 𝑝,𝑞

7.3

Proof. We first prove the following lemma.

Also, we have that for Equation (27)

≤ 𝑚𝑎𝑥𝑙 ∈ {𝑖,𝑗 },𝑝,𝑞<𝑛 Z𝑙

Proof of Theorem 4.3

Proof. We show that the computation of the representation score can be reduced from the Maximum Coverage Problem [28], which is known to be NP-hard. Given a universe 𝑈 of elements, a collection of subsets {𝑆 }𝑛𝑗 , and a budget k, MCP is going to pick a fixed number of sets such that the cardinality of the union of chosen sets | ∪ 𝑆 𝑗 | is maximized. Consider each sample 𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛 as an item that needs to be covered, and each candidate 𝑋 𝑗 ∈ D𝑐𝑜𝑟𝑒 as a set that covers the samples in D𝑡𝑟𝑎𝑖𝑛 . We define the cosine similarity as an indicator function: cos(𝑋𝑖 , 𝑋 𝑗 ) = 1 if 𝑋𝑖 is covered by 𝑋 𝑗 and 0 otherwise. For simplicity, we set the importance score 𝐼ˆ(𝑋𝑖 ) to 0 for all 𝑋𝑖 . Then 𝑅𝑆 (D𝑐𝑜𝑟𝑒 ) = 𝜆𝑅(D𝑐𝑜𝑟𝑒 ) is equivalent to the total number of covered items. If 𝑅𝑆 (D𝑐𝑜𝑟𝑒 ) can be solved exactly in polynomial time, then MCP can also be solved in polynomial time. Since MCP is known to be NP-hard, our selection objective 𝑅𝑆 (D𝑐𝑜𝑟𝑒 ) is also NP-hard. □

X𝑖 − X 𝑗

And for the Equation (28), similarly, we can relax it to a combination of ∇Ô𝑖 L (𝑋𝑖 , 𝜽 )) − ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 )) and X𝑖 − X 𝑗 . For simpler notation and analysis, we directly denote the remaining constant terms in Equation (27) and Equation (28) associated with ∇Ô𝑖 L (𝑋𝑖 , 𝜽 ) − ∇Ô𝑖 L (𝑋 𝑗 , 𝜽 ) as 𝐶 1 , and X𝑖 − X 𝑗 as 𝐶 2 .

𝑘 ) is monotone and subProof. We prove that the Δ𝑅𝑆 (𝑋𝑖 |D𝑐𝑜𝑟𝑒 modular as follows. 𝑘 • Monotone increasing: Given any D𝑐𝑜𝑟𝑒 and data point 𝑋𝑖 , we 𝑘 𝑘 can have 𝑅𝑆 (D𝑐𝑜𝑟𝑒 ∪ {𝑋𝑖 }) − 𝑅𝑆 (D𝑐𝑜𝑟𝑒 ) ≥ 0, since the representation score and the importance score are both non-negative for 𝑘 . Thus, Δ𝑅𝑆 (𝑋 |D 𝑘 ) is a new 𝑋𝑖 for the selected coreset D𝑐𝑜𝑟𝑒 𝑖 𝑐𝑜𝑟𝑒 monotone increasing. ′𝑘 ′𝑘 , 𝑋 ∈ D • Submodularity: Given D̃𝑐𝑜𝑟𝑒 ⊂ D𝑐𝑜𝑟𝑒 𝑖 𝑡𝑟𝑎𝑖𝑛 , and 𝑋𝑖 ∉ ˜ ′𝑘 ′𝑘 D𝑐𝑜𝑟𝑒 , D𝑐𝑜𝑟𝑒 , we can obtain: ′𝑘 ′𝑘 Δ𝑅𝑆 (𝑋𝑖 |D𝑐𝑜𝑟𝑒 ) = 𝜆(𝑅(D𝑐𝑜𝑟𝑒 ∪ {𝑋𝑖 }) ′𝑘 − 𝑅(D𝑐𝑜𝑟𝑒 )) + (1 − 𝜆) 𝐼ˆ({𝑋𝑖 }) ′𝑘 ′𝑘 ′𝑘 Δ𝑅𝑆 (𝑋𝑖 | D̃𝑐𝑜𝑟𝑒 ) = 𝜆(𝑅( D̃𝑐𝑜𝑟𝑒 ∪ {𝑋𝑖 }) − 𝑅( D̃𝑐𝑜𝑟𝑒 ))

+ (1 − 𝜆) 𝐼ˆ({𝑋𝑖 })

𝑄

𝑉 𝐾 Then, define 𝑐 1 = 𝑐 31 + 𝑐 32 + 𝑐 𝑂 3 + 𝑐 3 + 𝑐 3 + 𝑐 3 + 𝐶 1 and 𝑐 2 = 1 2 𝑂 𝑉 1 2 𝑂 𝑉 𝑐 1 + 𝑐 1 + 𝑐 1 + 𝑐 1 + 𝛼 (𝑐 2 + 𝑐 2 + 𝑐 2 + 𝑐 2 ) + 𝐶 2 , we have

∥∇𝜽 L (𝑋𝑖 , 𝜽 ) − ∇𝜽 L (𝑋 𝑗 , 𝜽 )∥

Since the marginal score satisfies the following inequality: 𝑘 ′𝑘 Δ𝑅𝑆 (𝑋𝑖 |D𝑐𝑜𝑟𝑒 ) − Δ𝑅𝑆 (𝑋𝑖 | D̃𝑐𝑜𝑟𝑒 )≤0

(29)

≤𝑐 1 ∥X𝑖 − X 𝑗 ∥ + 𝑐 2 ∥∇Ô𝑖 L (𝑋𝑖 , 𝜽 ) − ∇Oˆ𝑗 L (𝑋 𝑗 , 𝜽 )∥

we can obtain the inequality as:

≤𝑐 1 ∥X𝑖 − X 𝑗 ∥ + 𝑐 2 ∥∇Ô𝑖 L (𝑋𝑖 , 𝜽 )∥ + 𝑐 2 ∥∇Oˆ𝑗 L (𝑋 𝑗 , 𝜽 )∥

′𝑘 ′𝑘 ′𝑘 ′𝑘 𝑅𝑆 ( D̃𝑐𝑜𝑟𝑒 ∪ 𝑋𝑖 ) − 𝑅𝑆 ( D̃𝑐𝑜𝑟𝑒 ) ≥ 𝑅𝑆 ( D𝑐𝑜𝑟𝑒 ∪ 𝑋𝑖 ) − 𝑅𝑆 ( D𝑐𝑜𝑟𝑒 )

𝑘 ) is submodular. It demonstrates that Δ𝑅𝑆 (𝑋𝑖 |D𝑐𝑜𝑟𝑒

Í Define 𝑐 3 = ∥ 𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛 ∇Ô𝑖 L (𝑋𝑖 , 𝜽 )∥ then we have ∑︁ min ∥∇𝜽 L (𝑋𝑖 , 𝜽 ) − ∇𝜽 L (𝑋 𝑗 , 𝜽 )∥ 𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛

≤

∑︁ 𝑋𝑖 ∈ D𝑡𝑟𝑎𝑖𝑛

□ 𝑘 ) is monotone increasing Lemma 7.1 indicates that Δ𝑅𝑆 (𝑋𝑖 |D𝑐𝑜𝑟𝑒

𝑋 𝑗 ∈ D𝑐𝑜𝑟𝑒

min 𝑋 𝑗 ∈ D𝑐𝑜𝑟𝑒

𝑐 1 X𝑖 − X 𝑗

+ 𝑐 2 ∥∇Ô 𝑗 L (𝑋 𝑗 , 𝜽 )∥ + 𝑐 3 Thus, Theorem 4.1 is proved.

□

and submodular. 𝑜𝑝𝑡 Suppose 𝑅𝑆 (D𝑐𝑜𝑟𝑒 ) denotes the optimal value of the objective for the coreset selection problem within budget 𝑘𝑆 , we can derive: ∑︁ 1 𝑘 𝑘 Δ𝑅𝑆 (𝑋𝑖 |D𝑐𝑜𝑟𝑒 )≥ Δ𝑅𝑆 (𝑋𝑖 |D𝑐𝑜𝑟𝑒 ) (30) 𝑘𝑆 𝑜𝑝𝑡 𝑘 𝑋𝑖 ∈ D𝑐𝑜𝑟𝑒 \D𝑐𝑜𝑟𝑒

𝑜𝑝𝑡

The Equation (30) provides the upper bound for 𝑅𝑆 (D𝑐𝑜𝑟𝑒 ). By the inductive hypothesis, 1 𝑜𝑝𝑡 𝑘 𝑅𝑆 (D𝑐𝑜𝑟𝑒 ) ≥ (1 − ( )𝑘𝑆 )𝑅𝑆 (D𝑐𝑜𝑟𝑒 ) (31) 𝑘𝑆

GRACE: A Dynamic Coreset Selection Framework for Large Language Model Optimization

The fraction ( 𝑘1𝑆 )𝑘𝑆 ) approaches 𝑒1 as 𝑘𝑆 grows. Thus, the approximation ratio for the coreset selection algorithm is 1 − 𝑒1 . □

7.4

Full Version and Proof of Theorem 4.6

Theorem 7.2 (Bounded Error of the Selective Update). Consider the update round as defined in Equation (21). Let 𝐼 ★ (𝑋𝑖 ) be the true importance score of 𝑋𝑖 at the current model parameter 𝜃 𝑡 . Define N𝑖★ = { 𝑗 ∈ N (𝑋𝑖 ), aff(𝑖, 𝑗) > 𝛽} to be the set of neighbors of 𝑋𝑖 that pass the threshold in Equation (20), 𝑟𝑖 = max 𝑗 ∈ N★ |∥ H̄𝑖 − H̄j ∥ as the 𝑖 maximum distance between neighbors and 𝑋𝑖 in 𝑘-NN. We also define 𝜀 as the LSH approximation error according to [32]. The score error of 𝑋𝑖 is then defined as 𝑒𝑖 = 𝐼 (𝑋𝑖 ) − 𝐼 ★ (𝑋𝑖 ). Then for every 𝑋𝑖 , the following two properties hold: (1) Change Stability: The per-round change of any node is bounded by: 1 𝐼 𝑛𝑒𝑤 (𝑋𝑖 ) − 𝐼 (𝑋𝑖 ) ≤ max{0, max∗ 𝐼 ∗ (𝑋 𝑗 ) − 𝐼 (𝑋𝑖 ) } 2 𝑋 𝑗 ∈ N𝑖

Conference acronym ’XX, June 03–05, 2018, Woodstock, NY

(2) Local Approximation Error bound: Let the current estimation error of node 𝑋𝑖 before the update be 𝑒𝑖𝑜𝑙𝑑 = 𝐼 (𝑋𝑖 ) − 𝐼 ★ (𝑋𝑖 ) and after the update be 𝑒𝑖𝑛𝑒𝑤 = 𝐼 𝑛𝑒𝑤 (𝑋𝑖 ) − 𝐼 ★ (𝑋𝑖 ). Then we have: 1 1 𝑒𝑖𝑛𝑒𝑤 ≤ 𝑒𝑖𝑜𝑙𝑑 + (𝐿ℎ 𝑟𝑖 + 𝜀), 2 2 Proof. (1) is directly obtained from the update rule in Equation (21). For (2), starting from Equation (21), if we subtract 𝐼 ★ (𝑋𝑖 ) Í from both sides, we obtain 𝑒𝑖new = 12 𝑒𝑖old + 12 𝑋 𝑗 ∈ N★ 𝑤𝑖 𝑗 𝐼 ★ (𝑋 𝑗 ) − 𝑖 𝐼 ★ (𝑋𝑖 ) . By local Lipschitz continuity we have |𝐼 ★ (𝑋 𝑗 ) − 𝐼 ★ (𝑋𝑖 )| ≤ 𝐿ℎ ∥ H̄ 𝑗 − H̄𝑖 ∥ ≤ 𝐿ℎ 𝑟𝑖 for every similar neighbor 𝑋 𝑗 ∈ N𝑖★ when exact neighbors are used. When neighborhoods are retrieved via LSH, the use of approximate candidates perturbs the convex combinaÍ ★ tion by at most 𝜀 lsh in magnitude. Thus, we have 𝑗 𝑤 𝑖 𝑗 (𝐼 (𝑋 𝑗 ) − ★ 𝐼 (𝑋𝑖 )) ≤ 𝐿ℎ 𝑟𝑖 +𝜀 lsh . Combining these inequalities with the triangle inequality, we obtain the stated bound. □

GRACE: A Dynamic Coreset Selection Framework for Large Language Model Optimization

Related documents