Query-based Submodular Data Selection for Efficient Instruction Tuning

Introduction

As large language models (Touvron et al., [51]; Grattafiori et al., [13]; Jiang et al., [20]) are deployed in increasingly specialized roles, from multilingual question answering (Clark et al., [8]; Lewis et al., [29]) to complex multi-step reasoning (Wei et al., [55]; Wang et al., [52]; Yao et al., [60]), their effectiveness hinges less on the scale of pretraining than on the quality and composition of the data used to fine-tune them (Longpre et al., [36]; Zhou et al., [62]). LIMA (Zhou et al., [62]) demonstrates that a few carefully chosen examples can rival models trained on orders of magnitude more data, underscoring a core insight: which examples a model trains on matters far more than how many. This motivates a principled data selection problem: given a large, heterogeneous training pool and a small set of target demonstrations that specify a desired capability, how should we select a compact subset to maximize downstream performance?

A growing body of work has tackled data selection for instruction tuning from diverse angles. Quality-based methods use heuristic scores such as instruction-following difficulty (Li et al., [30]) or LLM-judged complexity and quality (Chen et al., [4]; Liu et al., [33]; Du et al., [11]) to filter or rank examples, while distributional approaches match the selected subset to a reference distribution (Xie et al., [59]). Data pruning techniques identify and remove uninformative samples via gradient-based importance estimates (Tan et al., [49]), and coreset methods enforce diversity through clustering or submodular optimization (Wei et al., [56]; Zhang et al., [61]). Among these, LESS (Xia et al., [58]) achieves strong targeted performance by estimating per-example influence via gradient similarity and selecting the top-$K$ highest-scoring candidates. However, all these methods score each candidate independently against the target set and select the top-ranked examples. This point-wise strategy ignores how selected examples interact with one another: as the budget shrinks, top-ranked candidates increasingly share similar gradient directions, so the selected subset wastes its limited capacity on redundant signals instead of covering complementary aspects of the target task. The tighter the budget, the larger the marginal cost of each redundant selection, yet the scoring criterion remains oblivious to intra-subset overlap. This analysis motivates a selection objective that jointly accounts for target relevance and inter-example redundancy, with diversity pressure that adapts to the budget size.

We propose Query-based Submodular functions with Gradient-guided Synthesis (QSGS), a unified coreset construction framework that operates in three tightly coupled stages built on a shared gradient representation. First, low-rank gradient features are computed from early-stage checkpoints of a warm-up model, yielding both per-example influence scores against the target set and compact gradient embeddings for pairwise similarity computation. Second, a target-aware submodular graph cut selects examples by jointly maximizing relevance to the target task and minimizing intra-subset redundancy in gradient space. This subset-level objective is useful under tight budgets, where each redundant selection consumes a larger fraction of the limited capacity and displaces a potentially complementary example.

Third, a gradient-guided synthesis step identifies target gradient directions that are uncovered by the selected subset and generates synthetic examples to fill the residual gaps.

We evaluate QSGS at an extreme 0.5% data budget, which contains only 1,350 out of 270,000 examples across diverse benchmarks and model families. QSGS consistently outperforms LESS across the evaluated settings, notably matching full-data MMLU performance, as shown in Figure 1. Importantly, its advantage becomes more pronounced as the available data decreases, demonstrating strong robustness in highly data-scarce regimes. Our ablation studies show that the graph-cut objective accounts for the majority of the performance improvement, with gradient-guided synthesis providing additional gains, while maintaining a selection overhead below 0.1% of the total pipeline cost.

Our contributions are as follows:

• We propose QSGS, a unified coreset selection framework for LLM instruction tuning that first computes gradient-based influence scores, then selects samples based on influence scores, and fills residual coverage gaps through gradient-guided data synthesis.

• We design a target-aware submodular graph cut objective that jointly maximizes candidate–target relevance and minimizes intra-subset redundancy in gradient space. We also introduce a gradient-guided synthesis method that identifies uncovered target gradient directions via residual subspace analysis and generates targeted synthetic examples to fill the gaps.

• Experiments across three benchmarks (MMLU, TydiQA, BBH) and three model families (Llama-2, Llama-3, Mistral) show that QSGS at 0.5% budget matches or exceeds full-data performance on Mistral-7B, while the gap widens as the budget shrinks.

Related Work

Instruction tuning and data curation. Instruction tuning [41] aligns pretrained language models with downstream tasks by fine-tuning instruction–response pairs [36, 54, 7]. As training pools grow increasingly heterogeneous, the composition of the fine-tuning mixture has been shown to matter more than its sheer size [62, 4]. LIMA [62] demonstrates that as few as 1,000 carefully curated examples can match the performance of much larger mixtures. These findings motivate a growing body of work on principled data selection for instruction tuning. Our method tackles this problem and enables data-efficient instruction tuning with a small fraction of the training pool.

Data selection for instruction tuning. Existing methods [57, 18, 34, 6, 39, 31] for selecting instruction-tuning data can be broadly grouped into quality-based filtering and influence-based scoring [21]. On the quality side, AlpaGasus [4] uses an LLM judge to filter low-quality examples, MoDS [11] introduces a three-stage pipeline based on quality, coverage, and necessity, IFD [30] measures the gap between a model’s expected and intrinsic responses to identify high-value examples, and DEITA [33] scores data along complexity, quality, and diversity dimensions. These methods rely on heuristic proxies and do not condition on a specific target capability. On the influence side, influence functions [26] estimate the effect of removing a training point on model predictions via an inverse-Hessian–vector product. TracIn [44] traces gradient inner products across training checkpoints, while TRAK [42] uses random projections for efficient attribution. LESS [58] adapts this line of work to instruction tuning by combining LoRA-compressed gradients with Adam-adjusted influence scoring, enabling targeted selection where 5% of the data suffices to match full-dataset performance. In the multimodal setting, TIVE [35] extends gradient-based influence to visual instruction tuning. However, all these methods produce point-wise scores that rank examples independently, ignoring inter-example interactions. Our method builds on a submodular objective that explicitly models pairwise redundancy, while further closing coverage gaps via gradient-guided synthesis.

Coreset selection and submodular optimization. Coreset selection aims to identify a representative subset that preserves the learning performance of the full dataset. Classical approaches include geometry-based coverage [5, 1, 46, 47], uncertainty and error based sampling [9, 43, 50], gradient-based methods [38, 23] and decision-boundary-based methods [12, 37]. Submodular functions provide a natural framework for subset selection with diminishing returns [40, 28]. Wei et al. [56] show that Facility Location and related coverage functions can select informative training subsets for supervised learning, and subsequent work applies submodular objectives to active learning [2], curriculum learning [24], and continual learning [25]. Graph-cut objectives have been used for document summarization [32] and general data subset selection [19]. We bring graph cuts into the query-based selection setting, replacing input features with gradient projections and coupling the dispersion penalty with an influence-derived relevance term so that the selected subset is both diverse and aligned with the target task.

Method

Problem Formulation

Let $\mathcal{D} = \{\mathbf{x}_1, \ldots, \mathbf{x}_n\}$ be a large pool of candidate instruction-tuning examples, and let $\mathcal{V}$ be a small target validation set containing a handful of examples that embody a specific desired capability. The goal is to select a subset $\mathcal{S} \subseteq\mathcal{D}$ with $|\mathcal{S}| = K$ such that a model fine-tuned on $\mathcal{S}$ achieves low loss on $\mathcal{V}$, and consequently strong performance on the test set. Directly finding the optimal subset is NP-hard. Most existing methods [58, 59] operate under a point-wise assumption: they score each candidate independently against the target and select the top-$k$ examples. However, by ignoring inter-sample relationships, this paradigm inevitably suffers from diversity collapse. When a target requires specific reasoning skills, the algorithm redundantly selects highly homogeneous variations of the same problem, wasting the limited budget.

Targeting this problem, we propose QSGS framework as illustrated in Figure 2. The process for coreset construction can be summarized as follows: (1) Gradient feature computation. We compute low-dimensional gradient features for each data sample in $\mathcal{D}$ and derive influence scores that measure each candidate’s contribution to the target tasks. (2) Query-based graph cut selection. We formulate a submodular graph cut objective that jointly maximizes relevance to $\mathcal{V}$ and minimizes intra-subset redundancy in gradient space. (3) Gradient-guided synthesis. We identify residual subspace gaps and generate targeted synthetic examples to fill them.

Gradient Feature Computation

We leverage gradient-based influence to measure each training sample’s contribution to the target tasks. To make this tractable for large-scale datasets, we employ LoRA [16] and random projections [22] to reduce gradient dimensionality, and assign bigger weights to early-stage checkpoints before convergence to obtain more informative gradient features. Crucially, we retain the pairwise influence score matrix rather than collapsing it into a scalar per sample, and construct compact gradient for efficient similarity computation in the subsequent graph cut stage.

Following [44], we use a first-order approximation of training dynamics to estimate the influence of a training data point on held-out data. For a warm-up model, the influence of a training example $x$ on a validation example $v$ is defined as:

where $T$ is the number of warmup training epochs, $\bar{\eta}_i$ is the mean learning rate in epoch $i$, $\theta_i$ is the model checkpoint after epoch $i$, and $\Gamma(\cdot;\theta_i)$ denotes the projected Adam gradient update at checkpoint $\theta_i$. Computing these scores requires model checkpoints along the training trajectory; we circumvent the circular dependency between data selection and training by performing a short warmup run on a randomly selected $\mathcal{D}_{\mathrm{warmup}}\subset\mathcal{D}$. Unlike prior work [58, 61] that aggregates the per-validation-example scores into a single scalar per training sample, we retain the full influence score matrix $\mathbf{S}\in\mathbb{R}^{n\times| \mathcal{V} |}$ with entries $S_{ij}=\mathcal{I}(x_i,v_j)$. This 2D representation preserves the fine-grained structure of each candidate’s contribution to every validation example, which is essential for the relevance term in our graph cut objective (Section 3.3).

We perform LoRA fine-tuning [16] on $\mathcal{D}_{\mathrm{warmup}}$ for $T$ epochs, checkpointing the model after each epoch to store $\{\theta_i\}_{i=1}^{T}$ along with their Adam optimizer states. LoRA freezes the pre-trained weights and adds a low-rank adaptor, reducing the number of trainable parameters to less than 2% of the full model. Each gradient is projected into a $d$-dimensional space via a fixed random matrix [22, 42], forming a compact gradient datastore from which the influence score matrix $\mathbf{S}$ is computed. Beyond the influence score matrix, the graph cut objective requires pairwise similarity between training examples. We construct a gradient embedding for each training example by concatenating the checkpoint-weighted gradient projections:

where $\Vert$ denotes concatenation. The $\sqrt{\bar{\eta}_i}$ weighting ensures that the inner product between two embeddings recovers the weighted cosine similarity used in the graph cut kernel (Eq. (4)). Since the concatenated dimension $Td$ can be large, we apply a Johnson–Lindenstrauss random projection (Johnson et al., [22]) to reduce each embedding to $d'$ dimensions while preserving pairwise distances with high probability. The resulting embeddings $\tilde{\mathbf{e}}(x) \in\mathbb{R}^{d'}$ are L2-normalized so that their inner product equals cosine similarity, enabling efficient similarity computation in the graph cut stage.

We propose assigning bigger weights to checkpoints sampled before convergence to compute gradient features. This is motivated by the observation that gradient norms during the warmup phase are significantly larger than those at convergence, and therefore encapsulate more discriminative information about how each sample affects the model’s updates.

Query-based Graph Cut Selection

To simultaneously combat diversity collapse and early saturation of coverage-based alternatives, we build on the classical submodular graph cut framework (Iyer et al., [19]) and adapt it to the query-driven data selection setting. The standard graph cut objective selects a subset that minimizes intra-subset similarity, promoting diversity but without any notion of task relevance. We introduce a query-aware relevance term derived from the influence score matrix that steers the selection toward the target validation set, turning the diversity-seeking cut into a joint relevance-diversity objective.

The relevance of a candidate $x$ to the target set is the aggregate influence over all validation examples:

measuring the total contribution of $x$ to the entire target set. The pairwise similarity between two candidates is defined by the weighted cosine similarity of their gradient projections across checkpoints:

The formula above ensure that $w(x,x') \ge0$ for all pairs, which quantifies redundancy in gradient space: a high $w(x,x')$ indicates that the two examples induce similar parameter updates.

We seek a coreset $\mathcal{S} \subset\mathcal{D}$ of size $K$ that maintains high relevance to $\mathcal{V}$ while exhibiting low internal similarity. We formalize this via a target-aware submodular graph cut:

where the first term maximizes the cumulative influence of $\mathcal{S}$ on the target task, while the second term acts as a dispersion penalty that minimizes intra-subset redundancy in gradient space. The hyperparameter $\lambda> 0$ balances relevance and diversity. Two terms capture complementary properties of a selected subset. The relevance term favors examples aligned with the target capability, while the pairwise term discourages repeatedly selecting examples that induce similar gradient updates. Under a tight cardinality constraint, each redundant example consumes a larger fraction of the available selection capacity and leaves fewer slots for complementary training signals. Furthermore, unlike coverage functions that saturate when the sparse set $\mathcal{V}$ is fully covered, our dispersion penalty operates on the internal structure of $\mathcal{S}$ itself and continues to discriminate among candidates regardless of $\lvert\mathcal{V}\rvert$.

Because $w(x,x') \ge0$, the pairwise sum $\sum_{x,x' \in\mathcal{S},x \ne x'} w(x,x')$ is supermodular. Its negation is therefore submodular. Since the relevance term is modular, their sum $f(\mathcal{S})$ is submodular. The objective is generally nonmonotone because adding a highly redundant example can decrease its value. The resulting objective is a nonmonotone submodular maximization problem under a cardinality constraint. Randomized algorithms (Buchbinder et al., [3]) provide constant factor approximation guarantees for this class of problems. In practice, we adopt the deterministic greedy procedure in Algorithm 1 because it is simple, efficient, and empirically stable for our selection setting. We therefore do not claim that the theoretical $1/e$ approximation guarantee applies to Algorithm 1.

Algorithm 1: Query-based graph cut

Input: Candidate pool $\mathcal{D}$; validation set $\mathcal{V} = \{v_1,\ldots,v_m\}$; influence score matrix $S \in\mathbb{R}^{n \times|\mathcal{V}|}$ with $S_{ij} = \mathcal{I}(x_i,v_j)$ (Eq. (1)); gradient embeddings $\tilde{e}(x)$ for all $x \in\mathcal{D}$ (Eq. (2)); budget $K$

Output: Coreset $\mathcal{S}$

1. for each $x \in\mathcal{D}$ do

2. $\operatorname{Rel}(x) \leftarrow\sum_{v \in\mathcal{V}} \mathcal{I}(x,v)$ (Eq. (3));

3. end

4. $\mathcal{S} \leftarrow\varnothing$;

5. while $|\mathcal{S}| < K$ do

6. $x^* \leftarrow\operatorname*{argmax}_{x \in\mathcal{D}\setminus\mathcal{S}} \Delta(x \mid\mathcal{S})$ (Eq. (6));

7. $\mathcal{S} \leftarrow\mathcal{S} \cup\{x^*\}$;

8. end

9. return $\mathcal{S}$

In practice, we use the deterministic greedy algorithm, as shown in Algorithm 1. At each iteration, we add the element with the largest marginal gain:

Intuitively, $x^*$ is selected when its relevance to the target task outweighs its total similarity to examples already chosen, automatically balancing exploitation against exploration. This criterion also makes the selection order interpretable, since each chosen example must provide additional target aligned information beyond what is already covered by $\mathcal{S}$. To scale to large candidate pools, we approximate $w(x,x')$ via the compact gradient embeddings from § 3.2:

$w(x,x') \approx\sum_{i=1}^{T} \bar{\eta}_i(1+\langle\hat{e}(x),\hat{e}(x')\rangle)$, where $\hat{e}$ is the L2-normalized randomly projected embedding from Eq. equation 2. The additive constant contributes the same value to the marginal gain of every remaining candidate at a fixed greedy iteration and therefore does not affect the selection ordering. This avoids recomputing over the raw gradients across all checkpoint gradients.

Gradient-Guided Synthesis

Even with diversity-aware selection, the training pool $\mathcal{D}$ may not contain examples that cover every gradient direction required by the target task. At extreme budgets, this subspace gap is especially acute: the selected subset $\mathcal{S}$ spans a low-dimensional subspace of gradient space, and some target capabilities may lie entirely outside it. We address this with a post-selection synthesis step that uses the gradient geometry of $\mathcal{S}$ to identify what is missing and generate targeted synthetic examples.

Residual subspace identification. After selecting $\mathcal{S}$ via Algorithm 1, we measure how well the selected subset covers the target validation set in gradient space. For target validation set $\mathcal{V}$, we compute the gradient residual:

where $\bar{g}(\mathcal{V}) = \frac{1}{|\mathcal{V}|}\sum_{v \in\mathcal{V}}\Gamma(v)$ is the mean gradient of the validation set, which is averaged over checkpoints for brevity, and the projection is onto the subspace spanned by $\{\Gamma(x) : x \in\mathcal{S}\}$. The residual norm $\|r\|$ quantifies the uncovered component of validation set: a large residual indicates that no selected example provides a gradient update aligned with this target direction.

Targeted synthesis. We leverage the warm-up model $\theta$ to generate candidate synthetic samples with the validation examples from $\mathcal{V}$. The prompt instructs the model to produce diverse instruction–response pairs that exercise the same capability from different surface contexts. We then compute the gradient features of each synthetic candidate $\tilde{x}$ using the same LoRA checkpoints and random projection as the original datastore, and select the candidates whose gradient direction best aligns with the residual:

Selected synthetic examples are added to $\mathcal{S}$, the residuals are recomputed, and the process repeats until a synthesis budget $K_{\mathrm{syn}}$ is exhausted or all residual norms fall below a threshold $\epsilon$.

Naïve synthetic data generation produces examples that are semantically related to the target task but may be redundant with data already in $\mathcal{S}$. By selecting synthetic candidates based on their alignment with the residual gradient direction, we ensure that each synthetic example provides a training signal that is both target-relevant and complementary to the existing subset. This couples the generation process tightly with the graph cut framework: the residual in Eq. equation 7 is precisely the component of the target gradient that the dispersion-optimized subset failed to capture.

Table 1: Coreset selection performance at the 0.5% data budget across three models and three benchmarks. Full denotes training on all ∼270K examples; Rand. denotes uniform 0.5% random sampling; LESS [58] denotes top-$K$ gradient influence selection. Bold indicates the best result among selected subsets. Standard deviations over three seeds are reported in subscript. QSGS consistently outperforms all baselines across every model–benchmark combination.

Model Data %	MMLU Full (100%)	MMLU Rand. (0.5%)	MMLU LESS (0.5%)	MMLU QSGS (0.5%)	TydiQA Full (100%)	TydiQA Rand. (0.5%)	TydiQA LESS (0.5%)	TydiQA QSGS (0.5%)	BBH Full (100%)	BBH Rand. (0.5%)	BBH LESS (0.5%)	BBH QSGS (0.5%)
Llama-2-7B	51.6	45.0(1.3)	45.2(0.5)	47.9(0.4)	54.0	48.4(0.9)	50.2(0.2)	52.3(0.2)	43.2	35.7(0.6)	38.3(0.5)	40.1(0.6)
Mistral-7B	60.4	57.0(0.5)	58.8(0.7)	60.4(0.7)	57.7	53.9(0.7)	55.3(0.5)	57.5(0.3)	53.0	51.5(0.6)	52.4(0.2)	53.2(0.8)
Llama-3-8B	70.4	67.0(0.4)	67.5(0.8)	68.3(0.6)	70.7	67.1(0.6)	67.7(0.2)	68.7(0.3)	65.6	62.3(1.3)	62.9(1.1)	63.9(0.8)

Experiments

We first describe the experimental setup in § 4.1, then present main results in § 4.2. Section 4.3 provides ablation studies isolating the contribution of each component, and offers further analysis including comparisons of submodular objectives.

Experimental Setup

Dataset and metrics. Following [58], we use a heterogeneous pool of ∼270K instruction-tuning examples drawn from four sources: Flan v2 [36], Chain-of-Thought [55], Dolly [10], and Open Assistant [27]. This pool spans a wide range of formats and reasoning types and contains no obvious in-domain data for the target evaluation tasks, making it a realistic and challenging selection environment. We evaluate on three benchmarks that together cover diverse capability dimensions: MMLU [15] comprises 57 multiple-choice tasks spanning science, humanities, and professional knowledge; BBH [48] contains 27 hard reasoning tasks selected from BIG-Bench; TydiQA [8] is a multilingual extractive QA dataset covering 9 typologically diverse languages. For each benchmark, the few-shot examples provided per subtask serve as the validation set $\mathcal{V}$ for data selection and as in-context demonstrations during evaluation.

Implementation details. Warmup training uses a randomly selected 5% of $\mathcal{D}$ for $T = 4$ epochs, producing 4 LoRA checkpoints. Gradients are projected to $d = 8192$ dimensions. Unless otherwise noted, we report results at a 0.5% data budget ($K \approx1{,}350$ examples), the extreme-budget regime that is our primary focus. We additionally evaluate at 1%, 2%, and 5% budgets for the scaling study. For gradient-guided synthesis, we generate $K_{\mathrm{syn}} = 100$ candidate examples per under-covered subtask and select up to 10 synthetic examples total. For Llama 3 training, following [53, 17, 61], we extend the training set to a combination of 17 datasets. All experiments are conducted on NVIDIA RTX A6000 GPUs. We evaluate QSGS across three base models: Llama-2-7B [51], Llama-3-8B [13], Mistral-7B [20]. All warmup and final fine-tuning are performed with LoRA [16]. All ablations are conducted on Llama-2-7B / MMLU at the 0.5% budget.

Main Results

Table 1 presents results at the 0.5% data budget ($K \approx1{,}350$ examples). QSGS improves over LESS by 1.6% on average across all nine model–benchmark combinations, with gains in every individual setting. The improvement is most pronounced on Llama-2-7B, where QSGS leads by 2.2% on average and the gap between full-data and 0.5% performance is also the widest. This is consistent with our expectation: when the budget is tight relative to model capacity, top-$K$ selection is more prone to spending its limited budget on redundant high-scoring examples, and diversity-aware selection yields the greatest marginal benefit. On the stronger Llama-3-8B, the absolute gain narrows to 0.9%, suggesting that a more capable base model is more tolerant of suboptimal data composition. Notably, on Mistral-7B, QSGS at 0.5% matches or approaches full-data performance on all three benchmarks,

We further compare QSGS against a broader set of non-gradient baselines on Llama-2-7B in Table 2. Lexical retrieval methods such as BM25 [45] and representation-based approaches including DSIR [59] and RDS [14] all perform close to random selection, trailing QSGS by 1.3% to 2.6%. These methods score each candidate independently against the target distribution and lack any mechanism to enforce diversity within the selected subset. As a result, they tend to retrieve clusters of near-duplicate examples that are individually relevant but jointly redundant, exhausting the limited budget without adequate coverage of the target gradient space. In contrast, the graph cut objective in QSGS explicitly penalizes pairwise similarity among selected samples, ensuring that each additional example contributes complementary gradient information rather than duplicating directions already represented in the coreset.

Table 2: Full baseline comparison at 0.5% data budget on Llama-2-7B. Our method outperforms existing methods.

	Rand.	BM25	DSIR	RDS	LESS	TAGCOS	QSGS
MMLU	45.0(1.3)	46.6(0.5)	45.1(0.1)	45.0(0.3)	45.2(0.5)	44.8(0.3)	47.9(0.4)
TydiQA	48.4(0.9)	49.7(0.7)	47.5(0.5)	48.6(0.1)	50.2(0.2)	48.1(0.3)	52.3(0.2)
BBH	35.7(0.6)	39.8(0.5)	36.8(0.5)	36.7(0.2)	38.3(0.5)	39.1(0.7)	40.1(0.6)

Table 3 traces the performance gap between QSGS and LESS on MMLU as the data budget decreases from 5% to 0.5%. At 5%, the two methods differ by only 0.9%, as the budget is large enough for top-$K$ to incidentally achieve reasonable diversity. However, the gap widens steadily to 2.2% at 1% and 2.7% at 0.5%. The increasing empirical gap is consistent with the intuition that redundancy is more costly when only a small number of examples can be retained. With a larger budget, top-$K$ selection can include redundant examples while still covering meaningful gradient directions. Under a tight budget, each redundant selection directly displaces a potentially complementary example. The submodular objective of QSGS directly addresses this by balancing relevance and coverage, allowing it to maintain broad gradient coverage even under tight budgets. Quantitatively, LESS degrades by 5.0% from the 5% budget to the 0.5% budget, while QSGS degrades by only 3.2% over the same range. Notably, QSGS at 0.5% budget already surpasses LESS at 1% budget.

Table 3: MMLU evaluation on under different data ratios.

Data Ratio	5%	1%	0.5%
Rand.	46.5(0.4)	45.9(0.6)	45.0(1.3)
LESS	50.2(0.5)	46.3(0.7)	45.2(0.5)
QSGS	51.1(0.3)	48.5(0.2)	47.9(0.4)

Ablation Studies

Component analysis. To isolate the contribution of each proposed component, we incrementally add them to our baseline (Figure 3a). The baseline relies entirely on top-$K$ selection using computed gradient features, without any synthetic samples. We evaluate two extensions: “+GC”, which replaces top-$K$ with our query-based Graph Cut, and “+GC+Syn”, which represents the full method by adding gradient-guided sample synthesis. Replacing the baseline’s top-$K$ selection with the Graph Cut objective accounts for the majority of the performance gain, increasing MMLU accuracy from 45.9 to 47.4. This confirms that diversity-aware selection is the primary driver of improvement. Building on this, gradient-guided synthesis provides a complementary boost by filling residual gaps in gradient coverage that the existing pool cannot address. This diminishing return from synthesis is entirely by design: because it specifically targets the subspace not spanned by pool-selected examples, its impact naturally shrinks as the quality of the initial pool selection improves.

Random projection dimension. We vary the projection dimension $d'$ of the compact gradient embeddings $\tilde{\mathbf{x}} \in\mathbb{R}^{d'}$ used for pairwise similarity computation in the Graph Cut objective (Eq. (2)). Performance peaks at $d'=1024$ and plateaus at $d'=2048$ (Figure 3b). For full-dimensional gradients, we use a chunked CPU–GPU transfer to accommodate the full vectors in memory during selection. Notably, operating on full-dimensional gradients degrades performance to 45.1, below random projection at every tested dimension. We attribute this to distance concentration in highdimensional spaces. As the gradient dimensionality grows, pairwise cosine similarities concentrate near zero, causing the redundancy penalty in the Graph Cut objective to vanish. When the penalty term becomes negligible, Graph Cut effectively reduces to top-$K$ relevance ranking and loses its diversity-enforcing capability. Random projection into a lower-dimensional subspace compresses the gradient representations so that semantically similar examples exhibit meaningfully non-zero similarity, thereby restoring the discriminative power of the redundancy term. Random projection reduces computational cost and acts as an implicit regularizer that preserves dominant gradient structure while suppressing the high-dimensional noise that would neutralize the diversity objective.

Sensitivity to $\lambda$. Performance varies by only 1.1% across a 50× range of $\lambda$ (Figure 3c). The optimum lies at a small $\lambda$ where relevance remains the dominant selection criterion and the redundancy penalty acts only as a mild corrective. It is sufficient to suppress near-duplicate examples whose gradient directions are nearly identical, yet too weak to override relevance-based ranking. This regime retains the highest-quality, task-aligned examples while eliminating pure redundancy, allowing the model to converge efficiently without wasting capacity on repeated training signal. At the other extreme, $\lambda=10.0$ over-weights the diversity penalty, forcing the objective to sacrifice relevance for dissimilarity and thereby selecting uninformative examples.

Number of synthesized candidates. We vary the number of synthetic samples added to the coreset after Graph Cut selection (Figure 3d). Performance peaks at 10 samples and degrades sharply when all candidates are included, even falling below the no-synthesis baseline. This is consistent with the residual-guided selection in Eq. equation 8: the first few synthetic examples align with the largest uncovered gradient directions and provide genuinely complementary signal; once these gaps are filled, additional candidates inevitably overlap with existing coreset members and dilute the diversity that Graph Cut optimization establishes.

Effect of selection strategy. We replace QSGS’s Graph Cut (GC) objective with alternative submodular functions, namely Herding, $K$-Center, and Facility Location (FL), while keeping the same candidate buffer and gradient features, to isolate the role of the objective design. GC achieves the best performance, outperforming Herding and $K$-Center by 1.1% and 1.6%, respectively. Most notably, FL performs worse than even the top-$K$ baseline. We trace this to the small size of the validation set: FL saturates coverage after selecting only $\sim$10 examples, at which point the marginal gain of every subsequent selection is effectively random. The root cause lies in FL’s max-based aggregation, which scores each candidate by its similarity to the single best-selected example. Once every validation point has a nearby representative, the marginal gain of additional candidates vanishes. GC avoids this saturation by computing cumulative similarity between all selected samples and the validation set, so each new addition continues to yield positive marginal gains.

Warmup data ratio. Performance improves steadily as the warmup ratio increases from 0.5% to 10%, reflecting higher-quality gradient features (Figure 4b). We adopt 5% as the default: the gain from 5% to 10% is only 0.6% while doubling the warmup cost, indicating diminishing returns beyond 5%. The sharp drop at 0.5% warmup, which falls below even random selection, underscores that gradient-based selection fundamentally depends on the fidelity of the influence estimates; noisy gradients make even diversity-aware optimization ineffective.

Conclusion

We presented QSGS, a coreset construction framework for targeted instruction tuning that combines query-based submodular data selection with gradient-guided data synthesis. The graph cut objective jointly maximizes target relevance and minimizes intra-subset redundancy. Empirically, its advantage over pointwise selection becomes increasingly pronounced under tighter budgets, where redundant selections consume a larger fraction of the available training capacity. A complementary synthesis step fills residual coverage gaps by generating examples aligned with uncovered target gradient directions. Experiments across three benchmarks and three model families show that QSGS at a 0.5% budget consistently outperforms all baselines, achieving full-data performance on Mistral-7B.

References

More Analysis

Computational overhead. We report the wall-clock cost of each pipeline stage on NVIDIA RTX A6000 GPUs in Figure 5a. Warmup LoRA training requires approximately 304 GPU hours, gradient feature construction approximately 48 GPU hours, data construction including graph cut selection and optional synthesis less than one GPU hour, and final fine-tuning on the selected coreset approximately 32 GPU hours. Importantly, the warmup training and gradient computation are one-time costs that can be fully amortized: once the gradient features are stored, the data construction stage can be repeated in under 1 hour to produce coresets for different target validation sets, different data budgets, or different submodular trade-off parameters, without re-running any GPU-intensive computation. QSGS is therefore particularly suitable for settings in which multiple target-specific subsets are constructed from the same candidate pool.

Generated candidate examples. Figure 5b shows representative candidates produced for MMLU subtasks identified as under-covered by the residual analysis. The generated questions span several domains and exhibit varied surface forms. These examples provide qualitative evidence of topical alignment. Gradient residual alignment measures whether a generated example provides a complementary optimization signal. Developing an explicit semantic or correctness filter for generated candidates is an important direction for improving this component.

Limitations

The quality of the gradient similarity graph depends on the fidelity of the warmup checkpoints and the projected gradient features. Our ablations show that QSGS is robust to a broad range of projection dimensions and trade-off parameters, yet very small warmup sets can produce noisy influence estimates. In addition, our empirical study focuses on 7B–8B open-weight models and three representative benchmarks. Extending the evaluation to larger models, additional domains, and multi-turn or tool-use tasks is an important direction for future work, especially because the same stored gradient features can be reused to explore new target sets with limited additional cost.