acceptodds
Under review as a conference paper at ICLR 2027

GhostMatch: Validation-Free Online Batch Selection for LLM Training via Submodular Gradient Matching

Abstract

Online batch selection reduces LLM training cost by replacing a candidate batch with a smaller informative subset. Existing selection methods often rely on held-out validation data, while their objectives may lack approximation guarantees. We introduce GhostMatch, a validation-free method that selects a weighted subset to preserve the gradient geometry of the current candidate batch. Casting this problem as facility location in gradient space yields a monotone submodular objective, so greedy selection achieves the classical approximation guarantee. We also provide a nonconvex convergence analysis that directly relates the optimization error from subset selection to its gradient representation error. We use ghost inner products to compute the exact pairwise gradient geometry needed for facility-location selection without materializing per-example gradients. Across four LLM fine-tuning configurations from 1.1B to 8B parameters, GhostMatch remains competitive with validation-guided methods while using no held-out data and training on only half of each candidate batch, including outperforming the validation-guided OPUS baseline on Mistral-7B ( vs F1). A controlled ablation further shows that exact gradient geometry consistently outperforms an approximate alternative.

Primary area:
foundation or frontier models, including LLMs
Keywords:
large language models, online batch selection, gradient matching, coresets, submodular optimization, efficient training

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_Uw2WOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper proposes GhostMatch, a validation-free online batch selection method for LLM fine-tuning. At each step, a candidate batch ( b=8) is reduced to a weighted subset (k=4) by approximately reconstructing the candidate batch's mean gradient. Selection is formulated as a facility location problem over pairwise gradient distances, which yields a monotone submodular objective with the classical (1−1/e) greedy guarantee, while the underlying gradient geometry is computed exactly via ghost inner products. A nonconvex stationarity bound relates optimization error to the realized representation cost, with a linear-convergence variant under the PL condition. Experiments on four LoRA fine-tuning configurations (1.1B to 8B) claim parity with validation-guided baselines (GREATS/OPUS) while using no held-out data, plus an ablation showing that exact gradient geometry beats a zeroth-order approximation.

Critical strengths
  1. A clean formulation with a well-controlled ablation. Casting per-step selection as facility location over exact, ghost-computed gradient geometry is an elegant combination, and the ZeroOrder ablation (16/16 matched runs) cleanly isolates the value of exact geometry, a design variable that prior validation-free work only approximates. This is the paper's most convincing evidence.

  2. Unusually honest reporting. The authors disclose the limits of their own guarantee (Prop. 2) and report a failure case (Llama-3-8B cold start) with extended-horizon follow-up. This raises confidence in what is reported, though it does not resolve the decisive issues below.

Critical weaknesses
  1. The proposed method fails to reduce training cost, contradicting its main motivation. To compute the ghost Gram matrix, the algorithm still needs a forward pass and per-sample backward signals on the full 2k candidate batch, plus another full forward and backward pass on the selected k subset. As shown in the paper's own runtime tables, a single GhostMatch step is 1.5 to 3 times slower than a standard full-batch step. However, the paper only compares methods at a fixed number of steps instead of fixed compute, and provides no wall-clock or FLOP curves. If evaluated at equal wall-clock time, the full-batch baseline would run for 2 to 3 times as many steps. In fact, Appendix F already shows that the full-batch baseline catches up when trained longer. Thus, there is no evidence that GhostMatch actually speeds up training.

  2. Missing random baseline and weak statistical significance. The paper never compares against the simplest baseline of picking k examples uniformly at random. Without this control, we cannot know if the gains come from the selection metric or just from the reweighting mechanism. For instance, on Llama-2-7B, all five tested methods cluster tightly between 9.38 and 9.95 ppl, a range where random selection would easily fall. Moreover, the headline result in the abstract (0.609 vs. 0.572 F1 against OPUS) is averaged over only 2 runs with a standard deviation of 0.026, which is not statistically meaningful. Finally, the theoretical (1−1/e) guarantee only holds for the shifted facility-location objective, not for the actual representation error used in the convergence proof (which suffers from an extra b⋅mt/eb⋅m_t/e error term in Prop. 2). As a result, the submodular approximation does not actually guarantee good convergence.

Questions for authors
  1. Is there any configuration where GhostMatch reaches a given evaluation loss with less total compute (wall-clock or FLOPs, scoring pass included) than Regular full-batch training? If yes, please show compute-normalized curves; if no, what is the method's practical value?

  2. Where does random-k selection (same k, uniform or cluster-reweighted) land in Table 1 for each configuration?

  3. Can you provide any worst-case guarantee on the realized representation cost ct(SG)c_t(S_G), which is the quantity that actually enters Theorem 1, beyond the additive bound in Proposition 2? If not, what does the (1−1/e)(1−1/e) guarantee actually imply for optimization?

Reviewer_PiYKOpenReview ↗
Rating
1
Confidence
2
Informativeness
3
Presentation
2
Soundness
1
Read review
Paper summary

The paper targets the problem of online batch selection in finetuning task such that the selected finetuning batch size is smaller in size than the training batch size and closely matches the gradients of the upstream batch. This work formulates this problem as a facility location problem where the addition of samples is monotone submodular and retains the classic approximation guarantee of (1-1/e). In theorem 1, they provide the analysis of relation between optimization error of training on standard vs online selected subset and the gradient representation error between standard and selected subset of data in downstream setting. They provide empirical evaluations on MMLU, TyDiQA, SAMSum with models like Llama-3-8B, Llama-2-7B and Alpaca. They claim that GhostMatch remains competitive with validation-directed baselines despite using no validation data. The downstream performance consistently improves with ghostmatch approach over zeroth-order counterpart and that the training advantage with full-batch is trasient in nature over ghostmatch on long horizon task. Background knowledge required (beyond basics)

  • What does monotone submodular (diminishing returns) mean, F(A∪{x})−F(A)≥F(B∪{x})−F(B)F(A \cup \{x\})- F(A) \geq F(B \cup \{x\}) - F(B) for A⊆BA \subseteq B?
  • what is classic (1-1/e) approximation guarantee?
  • Basic optimization inequalities: L-smoothness, Cauchy-Schwarz and Young inequalities, variance decomposition E∣∣X∣∣2=∣∣EX∣∣2+E∣∣X−EX∣∣2E||X||^2 = ||EX||^2 + E||X - EX||^2, telescoping sums and geometric series.
  • Why SGD converges to a noise floor with a constant step size, and to zero with a decaying one.
  • The idea of approximating a full-data gradient with a weighted subset and how field has evolved
Critical strengths
  • The motivation for this work is strong and the authors have done a good job in communicating it.
  • They have provided good theoretical analysis of their work.
  • In the literature review section they are honest about what other works have proposed and how this work overlaps with them.
Critical weaknesses

The empirical results do not support the claims made in the abstract and introduction (please refer to my critical analysis)

  • There should have been a background section at least in the appendix to explain readers about basics required to understand this work.
  • The motivation of the paper is to save the finetuning cost but there is no analysis provided on wall-clock time or even computational cost on all the experimental settings reported in Table 1. Figure 1 is insufficient to accept the claim of reduction in training cost.
Questions for authors
  • GhostMatch’s selection objective, representative weights, and gradient-error bound closely follow CRAIG [1], which already formulates gradient coreset selection through facility location with a classical greedy guarantee. CREST [2] extends this construction to random candidate minibatches and evaluates selection at every training step, while CoLM’s preliminary formulation [3] already states essentially the same weighted minibatch objective used by GhostMatch. Exact ghost gradient computations, including LoRA-specific formulations, are also established in GREATS [4], with related computational machinery available through GhostSuite [5]. GhostMatch’s main distinction therefore appears to be integrating these existing components for validation-free LLM fine-tuning. Its nonconvex and PL bounds largely specialize standard biased-SGD analysis [6], so the paper needs stronger evidence that this integration provides a substantive computational or empirical advance over its predecessors.
  • It is not clear how the gradient geometry is preserved over the finetuning process. A visualization of gradient trajectory of a complete finetuning set and the subset selected by GhostMatch would help show the comparison instead of relying only on the final evaluation metric. This would also help in understanding if the method is getting stuck in some kind of minimum or if there are some spikes. I would highly encourage authors to include this visualization.
  • In equation 3, the final inequality term seems like an equality that will hold true all the time based on the explanation provided earlier. can you explain the ≤\leq condition?
  • It is not clear to me how the values of ∣S∣|S| is selected. Is there any relation between ∣S∣|S| and performance? For the experiments reported, b=8b=8 and ∣S∣=k=4|S| = k = 4 seems to be selected values. If there is no closed-form solution for choice of ∣S∣|S|, I would like to see an ablation showing the sensitivity of performance to the of choice of ∣S∣|S|. However, this is subject to comptuational time of experiments. I understand if it is beyond the scope of rebuttal period.
  • The std values reported in Table 1 for TyDIQA and SamSum are close to 0 which is a point of concern. Is there any explanation for this?
  • The paper claims that GhostMatch saves on computational time however, the timing calculation here is not clear to me. It is still slower than Regular method in the experimental analysis so how is it saving trianing cost relative to Regular?
  • In Figure 1, the timings for Regular are low for Llama-2-7B as compared to TinyLlama-1.1B. Are there any explanations for this? There are no timings for OPUS or ZeroOrder in end-to-end training. Figure 1's left panel uses a different model i.e. phi2. Any reason behind this different choice?
  • please report peak GPU memory for Regular, GREATS, OPUS, ZeroOrder and GhostMatch at a few values of b.
  • Please report wall-clock time along with accuracy. If the proposition of this paper is reduction in LLM training cost, that claim is only supported if you report accuracy and training times and memory cost. If other methods or Regular matches or beats GhostMatch the proposed method is not saving cost. Same applies vice versa, a small drop in performance is acceptable if the method is saving on cost provided such a saving is reported with fair comparison.

References

[1] Mirzasoleiman, B., Bilmes, J., & Leskovec, J. (2020, November). Coresets for data-efficient training of machine learning models. In International Conference on Machine Learning (pp. 6950-6960). PMLR.
[2] Yang, Y., Kang, H., & Mirzasoleiman, B. (2023, July). Towards sustainable learning: Coresets for data-efficient deep learning. In International Conference on Machine Learning (pp. 39314-39330). PMLR.
[3] Nguyen, D., Yang, W., Anand, R., Yang, Y., & Mirzasoleiman, B. (2025, May). Mini-batch coresets for memory-efficient language model training on data mixtures. In International Conference on Learning Representations (Vol. 2025, pp. 82476-82496).
[4] Wang, J. T., Wu, T., Song, D., Mittal, P., & Jia, R. (2024). Greats: Online selection of high-quality data for llm training in every iteration. Advances in Neural Information Processing Systems, 37, 131197-131223.
[5] Wang, J. T., Mittal, P., Song, D., & Jia, R. (2025, May). Data shapley in one training run. In International conference on learning representations (Vol. 2025, pp. 12358-12395). https://github.com/Jiachen-T-Wang/GhostSuite
[6] Ajalloeian, A., & Stich, S. U. (2020). On the convergence of SGD with biased gradients. arXiv preprint arXiv:2008.00051.

Reviewer_MNeEOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes GhostMatch, a validation-free online batch selection method, where in each optimization step, a weighted subset was selected based on pair-wise gradient similarity by solving facility location problem, which is monotone submodular. The required pairwise gradient dot product is computed based on the "ghost dot-product" technique, which does not materialize per-sample gradients. Experiments on four LoRA fine-tuning configurations (TinyLlama-1.1B, Llama-2-7B, Mistral-7B, Llama-3-8B; k=4 from b=8) show GhostMatch is competitive with the validation-guided GREATS and OPUS without using held-out data, consistently outperforms a zeroth-order variant that keeps the same selection rule, and is faster per step than GREATS though slower than training on the full candidate batch.

Critical strengths

The paper is very clear to understand; the topic is very important since currently most of the data selection algorithms require access to holdout data, which itself is often hard to select.

Critical weaknesses

If I understand it correctly, the main contribution of the paper is to extend the existing coreset-based data selection to online, per-iteration setting?

My main concern with this approach is that, by reducing the batch size by half, it will be very difficult to be competitive with the random full batch but with extra compute cost. The experiment results in Table 1 show that Regular is a very competitive baseline. The theoretical results do not suggest that the approach will outperform the full-batch Regular approach.

Another question is how the pair-wise gradient dot product can be computed when using gradient accumulation?

Questions for authors

See above.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.