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

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 $(1-1/e)$ 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 ($0.609$ vs $0.572$ F1). A controlled ablation further shows that exact gradient geometry consistently outperforms an approximate alternative.