Refresh Only the Gradients That Could Change the Selection

Choosing training data by looking at each example's gradient, meaning the direction that example would push the model's weights, works better than choosing by surface meaning. It is also expensive. Each candidate needs its own backward pass, and the method has to be rerun whenever the model changes enough that old gradients go stale. On multi-million-example instruction pools this cost is what kills gradient methods. LESS could not be run at the 5.8M scale in Large-Scale Data Selection for Instruction Tuning. Yet A Critical Look at Targeted Instruction Selection finds that gradient distances are the only representation that tracks target loss consistently, with Spearman correlation often above 0.9.

This note proposes treating the set of candidate gradients as a slowly changing graph and refreshing only part of it. A nearest-neighbor graph connects examples whose gradients point in similar directions. When the model moves, we recompute true gradients for a small, chosen fraction of examples. We estimate how everyone else drifted from the measured drift of their graph neighbors. We then spend further backward passes only on examples whose estimated drift could plausibly move them across the line that separates selected from rejected examples. The claim is that this uses a small fraction of the backward passes of full recomputation and keeps selection quality close to it.

Core Claim

Existing graph-based gradient selectors build their graph once, over gradients computed once. G2IS (Beyond Similarity) walks a cosine-similarity graph of LoRA gradients to pick conflict-free, task-aligned data. KNNG-CS (Efficient Coreset Selection via K-Nearest Neighbor Graphs) replaces dense pairwise distances with a sparse K-nearest-neighbor graph and scores examples by in-degree. Neither handles the fact that gradients change as the weights change.

The obvious fix borrows dynamic graph maintenance, such as SPatch-style repair when nodes are deleted or incremental coarsening. That fix aims at the wrong cost. Building a KNN graph over low-dimensional projected gradients takes near-linear time, $O(n^{1.14})$ per KNNG-CS. The dominant cost is the $n$ backward passes needed to obtain fresh gradients.

Our contribution therefore moves the "dynamic" part from the edges to the node contents. The graph serves two purposes. It carries measured drift from refreshed examples to unrefreshed ones. It also schedules which examples deserve a real backward pass. This is the same lazy, query-driven evaluation that JIT Sampling Trees use in Fully Dynamic Coreset Spectral Clustering, where expensive quantities are computed only when a query needs them. Here the expensive quantity is a gradient.

Mechanism

We store a random projection of each candidate's LoRA gradient, as LESS-style pipelines do. Let $g_i^{(s)}$ be example $i$'s stored gradient, last computed at checkpoint $s$. At a new checkpoint $t$, a refreshed set $R_t$ receives true gradients $g_j^{(t)}$. Every other example gets an estimate:

$$\hat g_i^{(t)} = g_i^{(s)} + \sum_{j \in N(i)\cap R_t} w_{ij}\,\big(g_j^{(t)} - g_j^{(s_j)}\big).$$

Here $N(i)$ is $i$'s graph neighborhood and $w_{ij}$ are normalized similarity weights. The second term is a neighbor-averaged drift. The bet is that nearby gradients move together because they share the parameters that the update touches.

The selection score $u_i$ can be a LESS-style alignment with target gradients or a G2IS consistency score. The refresh decision then compares estimated drift against the selection margin. Example $i$ is queued for a real backward pass when

$$\|\hat g_i^{(t)} - g_i^{(s)}\| \cdot L_u \;>\; |u_i - u_{\text{cut}}|.$$

In this rule, $u_{\text{cut}}$ is the score of the $k$-th ranked example and $L_u$ bounds how much the score changes per unit of gradient change. For cosine scores against a fixed target, $L_u$ is roughly the inverse gradient norm.

The rule spends computation where a ranking flip is possible. Examples deep inside the selected set or far below the cut are never recomputed. The initial refresh set is seeded by sampling one representative per coarse graph cluster, in the spirit of KNNG-CS in-degree representatives, so that drift is measured everywhere.

When an example is refreshed, only its own edges are re-searched in the graph. When pruning removes examples, as in multi-epoch dynamic pruning, we repair the hole with the weighted-clique-then-sparsify patch of SPatch (Graph-based Nearest Neighbors with Dynamic Updates via Random Walks). Edge maintenance is deliberately secondary.

Research Program

The first step is diagnostic: measure whether gradient drift is spatially coherent at all. On a LESS-style pipeline, we compute full projected gradients at four warmup checkpoints over a 198k subsample of the TÜLU unfiltered pool, mirroring the setup in A Critical Look. We then measure how well the drift of an example's K neighbors predicts its own drift, compared with the drift of random examples. If neighbor drift is no better than the global mean drift, the propagation idea is dead and we stop there. That outcome is itself a useful negative result.

The second step builds the refresh scheduler and traces the full cost–quality curve. Cost is measured in backward passes as a fraction of full recomputation. Quality is measured as overlap with the oracle top-$k$ set and as downstream accuracy after fine-tuning.

The third step tests generality beyond instruction tuning. We plug the scheduler into dynamic coreset training on CIFAR-100 and ImageNet. There, re-selection is triggered repeatedly during training, so stale gradients matter more than in one-shot instruction selection.

The fourth step scales to the full 5.8M pool. That is the regime where gradient methods have so far been excluded and only representation-based selection has been run.

Baselines

The naive reference points are random selection and stale gradients. Random selection is the uniform subset at the same budget. Stale gradients means computing gradients once at the first checkpoint and never refreshing them, at the cost of a single pass.

Stale gradients are the most important ablation, because they isolate whether refreshing matters at all. For random selection we cite balanced random at 41.1 average versus RDS+ at 50.5 when choosing 10k from 5.8M (Large-Scale Data Selection for Instruction Tuning).

The quality ceiling is full recomputation: LESS-style gradients recomputed for every candidate at every checkpoint. This is the method we must approach at a fraction of its cost. No reported result was found on Lacuna for LESS on the 198k TÜLU subsample, so we run it ourselves with the same model, the same projection dimension, and the same checkpoints. Beating our method's cost here means matching LESS's downstream average within one point while using no more than a quarter of its backward passes.

The strongest scalable competitor on instruction tuning is RDS+, which uses position-weighted mean-pooled hidden states. It is the method that actually wins at multi-million scale today, with 50.5 average when selecting 10k from 5.8M in 87 GPU-hours. We run it on the identical pool, with the identical selected-set size and fine-tuning recipe, and give it equal tuning effort. Beating it means a higher average on the same GSM8K, BBH, TyDiQA, Codex, SQuAD, and AlpacaEval suite at comparable GPU-hours.

Two ablations isolate our key ingredients. Random refresh spends the same backward-pass budget on randomly chosen examples and keeps stale gradients elsewhere, with no propagation. It tests whether propagation helps. Propagation without margin scheduling refreshes cluster representatives only. It tests whether margin-aware targeting helps.

A cheap competitor for targeting is loss-triggered refresh. It uses forward-pass loss change, which needs no backward pass, to choose which examples to refresh. This is a genuine threat because forward passes cost roughly a third as much.

For vision, the strongest dynamic coreset baseline is ERACS (Efficient Representativeness-Aware Coreset Selection), which re-selects only when the gradient signal-to-noise ratio falls. It reports 69.67% on CIFAR-100 at a 10% budget and 63.91% on ImageNet at 10%. We plug our scheduler into its re-selection step. Beating it means equal or better accuracy at lower re-selection cost, or higher accuracy at equal wall-clock time.

Why not just…?

Why not just rebuild the graph from scratch at each checkpoint? Rebuilding the graph is cheap; KNNG-CS reports near-linear construction. Rebuilding the gradients is not. A periodic rebuild only helps if it comes with fresh gradients for everyone, and that is exactly full recomputation. We include full recomputation as the ceiling. Rebuilding the graph without fresh gradients is identical to the stale baseline.

Why not just reuse gradients from one checkpoint? This is the real threat. If gradient rankings barely move during fine-tuning, refreshing is wasted effort. Two pieces of evidence suggest rankings do move. LESS-style methods aggregate over multiple checkpoints, which implies that rankings shift between them. G2IS found it necessary to model Adam momentum, which also changes effective gradients over time. But neither is a direct measurement. The diagnostic in step one and the stale baseline settle the question. If stale gradients match full recomputation on instruction tuning, we will report that and shift the main claim to the vision dynamic-coreset setting. There, re-selection happens over many epochs and drift is necessarily larger.

Why not just use static embeddings like RDS+? RDS+ scales and wins at 5.8M. However, A Critical Look finds hidden-state embeddings "surprisingly inconsistent" at predicting target loss, while gradients are monotone with it. Our aim is to make gradients affordable at RDS+'s scale. The head-to-head comparison on the 5.8M pool at matched GPU-hours decides whether that is worth it.

Why not just prune by loss, as InfoBatch does? InfoBatch (InfoBatch) needs multiple epochs of loss history and ignores redundancy. GREATS (GREATS) shows that loss heuristics over-select similar hard examples. Loss change is nonetheless a plausible cheap drift signal, which is why loss-triggered refresh is a baseline. If it matches our graph-propagated estimate, the graph earns its place only for imputation and not for scheduling, and we will say so.

Proposed Experiments

The decisive experiment is the cost–quality curve on the 198k TÜLU subsample with a 7B-class model. Refresh budgets run from 5% to 100% of full recomputation, with selected sets of 1% and 5% of the pool. The proposal succeeds if three conditions hold at about 20% of the backward passes. Our method must recover at least 90% of the oracle top-$k$ overlap. It must stay within one point of full recomputation on the downstream average. It must also clearly beat both random-refresh and stale gradients.

The neighbor-drift diagnostic reports the correlation between predicted and true drift as a function of K and of checkpoint gap. It should be reported before any downstream number.

The scaling experiment runs the best configuration on the 5.8M pool against RDS+'s reported 50.5 at a matched GPU-hour budget.

The vision experiment repeats ERACS's CIFAR-100 and ImageNet 10% budgets with our scheduler inside its re-selection loop. It reports both accuracy and re-selection overhead.

To probe the "curse of randomness," we also run larger budgets. At those budgets we expect all methods, ours included, to converge toward random. We would treat a gain there as suspicious rather than as a win.