Technical Summary: HARP – Efficient Data Selection for Finetuning Large Language Models

1. Problem Statement

Finetuning Large Language Models (LLMs) requires selecting high-quality subsets of data to improve downstream performance while managing computational costs. Existing approaches face a trade-off between two competing goals:

• Train-free selectors: These methods (e.g., based on embedding similarity, clustering, or diversity objectives) are scalable and cheap but rely on proxies that may not align with the actual downstream objective (e.g., task accuracy). High embedding similarity to a test set, for instance, does not guarantee high marginal utility for improving the model.
• Train-based selectors: These methods (e.g., Shapley value estimation, influence functions, or gradient-based approximations) explicitly estimate the contribution of data to downstream performance, offering better alignment with the target objective. However, they are computationally prohibitive, requiring numerous costly "train–evaluate" iterations to assess candidate subsets.

The paper posits a need for a "middle ground": a selector that retains the downstream alignment of train-based evaluation but avoids the exhaustive cost of evaluating every candidate.

2. Methodology: Hierarchical Active Region Pruning (HARP)

HARP is an efficient, train-based data selection framework designed to reduce selection costs while preserving alignment with downstream objectives. It operates through three core mechanisms:

A. Hierarchical Node–Leaf Construction

Instead of evaluating individual training examples, HARP organizes the training pool into a two-level hierarchy:

1. Nodes: Coarse local regions formed by clustering training examples based on normalized embeddings.
2. Leaves: Atomic selection units (groups of examples) within each node.
   This structure reduces the number of candidate units from $N$ (individual examples) to $G$ (leaves), where $G \le N/C_{min}$.

B. Efficient Utility Estimation via Empirical Bayes

Evaluating every leaf is still expensive. HARP employs a sampling and inference strategy:

1. Representative Sampling: For each node, a small set of representative leaves is selected (via size stratification and farthest-first sampling) and actually finetuned/evaluated.
2. Inference: The utility of unmeasured leaves is inferred using Empirical Bayes posteriors. The method interpolates local estimates based on similarity to measured representatives and applies shrinkage toward a global mean to reduce estimation noise.
3. Proxy Evaluation Set: To further reduce evaluation costs, HARP constructs a compact proxy evaluation set ($\tilde{E}$) that preserves domain coverage and diversity, rather than evaluating on the full validation set during every iteration.

C. Complementary Selection Envelopes

Based on the estimated main effects (utility contributions) of leaves, HARP introduces two selection strategies (envelopes) to handle redundancy and complementarity differently:

• HARP-C (Conservative Coverage): Uses a conservative envelope that credits only the strongest positive leaf per domain while accumulating all estimated harms. This prevents over-counting utility when multiple leaves capture the same redundant information. It is particularly effective for noisy or heterogeneous data.
• HARP-E (Expansive Additive): Uses an expansive envelope that sums positive contributions across leaves. This allows multiple complementary leaves within the same domain to receive credit. It performs best on clean, on-task data where redundancy is less of a concern.

D. Theoretical Guarantees

The paper provides theoretical analysis showing that under assumptions of local smoothness and bounded estimation error, HARP controls selection error. Specifically, the error bound for HARP-C is proportional to $(K+1)\eta$ and for HARP-E to $K\eta$ (where $K$ is the max leaves in a set and $\eta$ is the estimation error), demonstrating stability even with approximate utility estimates.

3. Key Contributions

1. HARP Framework: A novel hierarchical data selection method that reduces train-based selection costs by orders of magnitude through leaf-level grouping and Empirical Bayes inference.
2. Dual Envelope Strategy: The introduction of HARP-C and HARP-E, which offer complementary strengths: HARP-C for robust pruning in noisy environments and HARP-E for maximizing coverage in clean datasets.
3. Theoretical Analysis: Formal proofs establishing the stability of the selection process and bounds on selection error relative to estimation accuracy.
4. Empirical Validation: Comprehensive evaluation across 3 base models, 3 training datasets, and 4 reasoning benchmarks.

4. Experimental Results

The authors evaluated HARP against 6 baselines (including Random, DSIR, DQ, Full Finetuning, and SHED variants) across 36 experimental settings (3 models $\times$ 3 datasets $\times$ 4 benchmarks).

• Performance: HARP variants achieved the best result in 28 out of 36 settings (78%).
• Comparison to Baselines: On average, HARP-C and HARP-E outperformed the strongest non-HARP baseline (SHED-O) by +8.9 and +7.9 points, respectively. They also significantly outperformed Full Finetuning.
• Data Efficiency: HARP variants achieved these results using roughly 7$\times$ fewer training examples than 10k-budget baselines and 56$\times$ fewer than Full Finetuning.
• Dataset Sensitivity:
  • HARP-C excelled on noisy (Self-Instruct) and heterogeneous (Tulu-3) datasets.
  • HARP-E performed best on clean, on-task datasets (WizardLM), often surpassing Full Finetuning.
• Ablation Studies: The method showed robustness to variations in leaf size ($L$) and the number of representatives per node ($R$), with default settings providing a practical balance between granularity and cost.

5. Significance and Claims

The paper claims that HARP successfully bridges the gap between the scalability of train-free methods and the objective alignment of train-based methods. By organizing data hierarchically and inferring utilities via Empirical Bayes, HARP avoids the exhaustive train–evaluate iterations that make traditional train-based selection infeasible at scale.

The authors emphasize that the two envelopes are complementary: HARP-C is superior for "conservative pruning" in noisy data regimes, while HARP-E is better for "broader on-task coverage" in clean regimes. The work demonstrates that high-quality finetuning can be achieved with significantly reduced data and computational resources without sacrificing downstream performance, addressing the inefficiency and redundancy often found in current large-scale finetuning datasets.

Limitations: The authors note that HARP requires an evaluation set reflecting the downstream task distribution and that their current experiments are limited to reasoning benchmarks, leaving coding and open-ended generation tasks for future work.