Greedy Information Projection for LLM Data Selection

1. Problem Statement

The paper addresses the critical challenge of data selection for fine-tuning Large Language Models (LLMs). While scaling laws suggest that increasing data volume improves performance, practitioners increasingly find that data quality becomes the limiting factor once a sufficient quantity is reached.

• The Core Challenge: Selecting a small subset of training examples that maximizes downstream performance while respecting computational and storage constraints.
• The Gap: Existing methods often rely on ad-hoc heuristics (e.g., perplexity thresholds, deduplication) or separate processes for handling quality (e.g., LLM ratings) and diversity (e.g., clustering). There is a lack of a unified theoretical framework that simultaneously optimizes for both high-quality and diverse data under a single objective.

2. Methodology: Greedy Information Projection (GIP)

The authors propose GIP, a principled framework that casts data selection as a Mutual Information (MI) maximization problem.

A. Theoretical Formulation

The framework models the relationship between data embeddings and task-specific "query" signals (scores).

• Inputs:
  • $F \in \mathbb{R}^{d \times m}$: Data embedding matrix (features of $m$ candidates).
  • $G \in \mathbb{R}^{m \times n}$: Score matrix (evaluations of $m$ candidates across $n$ quality dimensions, e.g., helpfulness, accuracy).
  • $Q \in \mathbb{R}^{d \times n}$: A "query embedding" matrix constructed such that $F^\top Q \approx G$. This links the feature space (diversity) to the score space (quality).
• Objective: The goal is to select a subset $S$ of size $k$ that maximizes the mutual information between the query signals ($Z_Q$) and the selected data projections ($Z_{F_S}$), assuming Gaussian distributions.
  $$\max_S I(Z_Q; Z_{F_S})$$
• Geometric Interpretation: Maximizing this MI is mathematically equivalent to minimizing the volume (determinant) of the query embeddings projected onto the null space of the selected data.
  • Quality: Ensures selected data aligns with high-score directions.
  • Diversity: Ensures selected data spans new directions in the embedding space (reducing the null space volume).

B. Efficient Approximation Algorithm (Greedy Matching Pursuit)

Directly optimizing the MI objective is computationally intractable for large datasets. The authors derive a Greedy Matching Pursuit (MP) algorithm:

1. Relaxation: They use the Arithmetic Mean-Geometric Mean (AM-GM) inequality to relax the determinant minimization into a trace minimization problem, which is linear and easier to optimize.
2. Dual Formulation: The problem is transformed into minimizing the residual gain of query embeddings projected onto the null space of the selected set.
3. Algorithm (Algorithm 1):
   • Precompute the Gram matrix ($\Phi = F^\top F$) to store inner products.
   • Maintain a residual score matrix $W$.
   • Iterative Selection: At each step, select the data point that maximizes the sum of squared projections of the residuals onto the candidate.
   • Update: Efficiently update the residual matrix $W$ using precomputed inner products without re-computing projections from scratch.
4. Complexity: The algorithm runs in $O(m^2d + mnk)$ time. After the initial $O(m^2d)$ precomputation, the selection phase scales nearly linearly with the dataset size $m$, making it feasible for large-scale data.

C. Two Variants of Scoring

The framework supports two ways to generate the score matrix $G$:

1. MP+MA (Multi-Attribute): Uses external LLM evaluations (e.g., GPT-4o) to score data on multiple dimensions (coherence, accuracy, helpfulness, difficulty).
2. MP+SC (Self-Compression): Uses an internal geometric signal. It calculates how "central" a sample is to the dataset distribution by summing its dot products with all other samples ($g_i = \sum_j f_i^\top f_j$). This requires no external supervision.

3. Key Contributions

1. Unified Theoretical Framework: Introduces a single mutual information objective that naturally balances quality (alignment with scores) and diversity (spanning the feature space), avoiding the need for separate heuristics.
2. Efficient Algorithm: Develops a Greedy Matching Pursuit algorithm with efficient projection-based updates. It avoids the need for gradient computation or external validation sets, unlike methods like LESS or DSIR.
3. Strong Empirical Performance: Demonstrates that GIP can match or exceed full-dataset fine-tuning performance using only 1% to 20% of the training data across various benchmarks and model sizes.

4. Experimental Results

The authors evaluated GIP on Instruction Following (MT-Bench, BBH, Alpaca-Eval-V2) and Mathematical Reasoning (GSM8K) using models like Mistral-7B, Qwen3-4B/8B/32B.

• Data Efficiency:
  • On GSM8K, GIP (MP+MA) achieved 83.24% accuracy with only 20% of the data, matching the full dataset performance (83.24%).
  • On MT-Bench, GIP (MP+MA) with just 1% (512 samples) of the Alpaca-52k dataset achieved scores comparable to or better than full-data training on Qwen3-8B (8.26 vs 7.74).
• Comparison with Baselines:
  • GIP consistently outperformed Random selection, LIMA (length-based), Alpagasus (quality-based), CaR (clustering), DSIR (importance resampling), and LESS (gradient-based).
  • Notably, GIP achieved these results without requiring a trained model for gradients (unlike LESS) or a held-out validation set (unlike DSIR/LESS), significantly reducing computational overhead.
• Robustness:
  • The method remained stable under embedding noise (IoU > 85% for mild noise).
  • It performed well across different model scales (7B to 32B) and task types (reasoning vs. creative writing).

5. Significance and Future Work

• Practical Impact: GIP offers a computationally efficient, theoretically grounded method for data curation. It eliminates the need for expensive gradient calculations or external validation sets, making high-quality data selection accessible for resource-constrained environments.
• Theoretical Insight: The geometric interpretation of MI maximization provides a clear explanation for why "quality" and "diversity" co-emerge: selecting data that minimizes the volume of the query projection naturally forces the selection to cover high-value directions while avoiding redundancy.
• Future Directions: The authors suggest extending the framework to pre-training scale datasets (via streaming variants), handling non-Gaussian noise, and adapting to multimodal and continual learning settings.

In summary, GIP represents a significant step forward in LLM data selection by unifying quality and diversity into a single, efficiently solvable optimization problem, enabling high-performance fine-tuning with drastically reduced data requirements.