TL;DR
ClusterUCB is a new framework that slashes the computational cost of selecting high-quality data for fine-tuning Large Language Models (LLMs) by up to 80%. By clustering training data and using a modified "Multi-Armed Bandit" algorithm, it identifies the most influential data samples for a target task without needing to calculate gradients for the entire dataset at every step.
What Problem Does This Paper Address?
Supervised Fine-Tuning (SFT) is essential for tailoring LLMs to specific tasks, but not all data is created equal. Researchers often use gradient-based data influence to find the "best" samples—those that most effectively reduce the model's loss on a target task.
The catch? Calculating these influences is incredibly expensive. You have to compute the gradients for every single sample in a massive training pool across multiple training checkpoints. For most researchers and engineers, the "full-budget" version of this selection process is simply too slow and resource-intensive to be practical. Previous attempts to save time by calculating gradients less frequently often led to poor data selection because the model's "influence landscape" changes as it learns.
Methods
The authors introduce ClusterUCB, which treats data selection as a strategic resource allocation problem. It works in three main steps:
- Clustering with Gradients: Based on the intuition that samples with similar gradients have similar impacts, the framework first clusters the entire training pool using K-means based on initial gradient similarities.
- Inter-cluster Selection (The Bandit Approach): The authors frame the selection process as a Multi-Armed Bandit problem. Each cluster is an "arm," and the "reward" is the influence score of a sample drawn from that cluster.
- Modified Upper Confidence Bound (UCB): To decide which clusters to sample from, they use a modified UCB algorithm.
- Distribution Estimation: Unlike standard UCB which focuses on the mean, ClusterUCB records historical rewards to estimate the distribution of each cluster. It looks for clusters likely to contain "top-tier" samples (high variance/high potential), not just a high average.
- Cold Start: A small portion of the computing budget is initially spread across all clusters to ensure the algorithm doesn't prematurely ignore a "hidden gem" cluster.
By the end of the process, the algorithm has spent most of its "gradient-calculation budget" on the clusters that actually matter, ignoring the vast sea of low-influence data.
Datasets
The authors used a massive training pool of 407,740 instances aggregated from eight popular datasets:
- General/Instruction: Flan-v2, Dolly, Open Assistant v1, GPT4-Alpaca, ShareGPT.
- Reasoning/Math: CoT (Chain-of-Thought), GSM8k train.
- Coding: Code-Alpaca.
They evaluated the resulting models on four major benchmarks: MMLU (general knowledge), TydiQA (multilingual QA), GSM8k (math), and HumanEval (coding).
Key Insights and Ideas
- Gradients are "Sticky": A crucial discovery was that clusters formed at the beginning of training remain relatively effective throughout the process. This allows the team to cluster once and reuse those groups, saving massive amounts of overhead.
- Targeting the "Tail," not the "Mean": In data selection, we don't care about the average sample; we care about the outliers with the highest influence. By modifying UCB to account for standard deviation ($\hat{\mu}_c + \beta * \hat{\sigma}_c$), the algorithm specifically hunts for clusters that contain these high-impact outliers.
- Exploration is Mandatory: The "Cold Start" period is vital. Without it, the algorithm might get stuck "exploiting" a mediocre cluster simply because it hasn't seen enough samples from a better one yet.
Key Results
- Efficiency: ClusterUCB achieved results comparable to "full-budget" methods (like LESS and Dynamic) while using only 20% of the computing budget.
- Performance: On the MMLU benchmark,
LESS-ClusterUCB(20% budget) actually slightly outperformed the originalLESS(100% budget), scoring 47.8 vs 47.0. - Superiority over Reranking: Simply picking 20% of data at random to "rerank" (the
Rerankbaseline) performed significantly worse than the ClusterUCB approach, proving that the bandit-based cluster selection is doing something much smarter than random sampling. - Model Agnostic: The method proved effective across different architectures, including LLaMA-2-7B and Qwen2.5-3B.
Limitations and Future Work
- Individual vs. Collective Influence: The current method looks at how much one sample helps the model. It doesn't yet account for diversity or redundancy. For example, it might select 1,000 very influential samples that are all nearly identical, which is less useful than a diverse set.
- Simple Clustering: The study used K-means, the simplest clustering algorithm. The authors suggest that more sophisticated clustering techniques could further improve performance.
- Fixed Clusters: While initial clusters are "sticky," they do lose some effectiveness over time. Future work could explore "lightweight" ways to update clusters during the training process without blowing the computational budget.
Summary updated