Summary

• Framework: The paper introduces Combinatorial Data Selection (CDS), a framework that separates attribution (how samples are scored) from selection (which subset to pick), explicitly modeling nonadditive sample interactions and multi-task evaluation.
• Method: Proposes Mixture-then-Select (MtS), a two-stage algorithm that first determines the domain mixture (allocation across skill domains) and then ranks samples within each domain by attribution score.
• Results: MtS outperforms 8 baselines across 4 selection principles by 20–54% relative improvement, beats full-data training, and reaches ≥89% of optimal performance in data-purchasing scenarios across all budget levels tested.
• Key insight: The data pool exhibits substantial cross-domain complementarity (joint utility > sum of parts) and within-domain redundancy, validating the need for combinatorial rather than per-sample selection.
• Theory: Provable approximation guarantee — the gap to the optimal subset is linear in selection size m and independent of data pool size N.

Introduction and Theoretical Foundation

Background and Motivation

LLM fine-tuning data selection faces two fundamental challenges:

1. Tasks are heterogeneous: Samples help different evaluation tasks unevenly — a sample useful for math may be useless or harmful for dialog.
2. Samples interact: Training on two samples together can yield more (complementary) or less (substitutive) than the sum of individual contributions.

These facts make per-sample scoring fundamentally insufficient. Current methods (LESS, DEITA, influence functions) score samples independently and take top-m, ignoring combinatorial structure.

Problem Formulation

The selection problem maximizes aggregate utility $u(S)$ subject to budget constraints:

$$u(S) = f\bigl(u_{1}(S), \dots, u_{T}(S)\bigr)$$

where $T$ tasks are evaluated, and $f$ is an aggregator (e.g., weighted average). The utility function is non-additive.

Theoretical Foundation: Möbius Decomposition

The set utility is decomposed via Möbius inversion, keeping singleton and pairwise terms:

$$u(S) = \sum_{j \in S} v_{j} + \sum_{\{i,j\} \subseteq S} \varphi_{ij} + \varepsilon(S)$$

where $v_j = u(\{j\})$ is the singleton value, $\varphi_{ij} = u(\{i,j\}) - v_i - v_j$ is the pairwise interaction, and $\varepsilon(S)$ captures higher-order terms. This pairwise approximation captures ≥90% of variance on real data.

The pairwise interaction matrix $\Phi$ is further decomposed along the domain partition:

$$\Phi = \Phi_{w} + \Phi_{\text{block}} + \Phi_{\text{res}}$$

• $\Phi_w$: within-domain (block-diagonal) interactions
• $\Phi_{\text{block}}$: cross-domain block-mean interactions (captured by the mixture decision)
• $\Phi_{\text{res}}$: residual deviations (uncontrolled, contributes to the bound's gap)

Methodology

Mixture-then-Select (MtS) Algorithm

Stage 1 — Choose domain mixture: maximize a learned utility predictor $\hat{g}$ over feasible mixtures:

$$\hat{\mathbf{n}} \leftarrow \arg \max_{\mathbf{n} \in \mathbb{Z}_{\geq 0}^{T}, \sum_{c} n_{c} = m, n_{c} \leq |C_{c}|} \hat{g}(\mathbf{n})$$

Stage 2 — Within-domain selection: pick top $\hat{n}_c$ samples in each domain $C_c$ ranked by per-sample values $v_j$.

Theoretical Guarantees

Theorem 1 (Spectral Guarantee): Under structural assumptions, with probability ≥ 1−η:

$$u(S_{MtS}) \geq u(S^{*}) - \underbrace{\sum_{c=1}^{T} \beta_{w,op}^{(c),cent} n_{c}^{*} v_{\max}}_{\text{within-domain gap}} - \underbrace{\delta_{op} m v_{\max}}_{\text{cross-domain gap}} - \mathcal{R}(m) - 2E(m)$$

where the gap is linear in $m$ (not $m^2$), independent of pool size $N$, and decomposed by stage.

Theorem 2 (Operator-Norm Robustness): If $\|\hat{\Phi} - \Phi\|_{op} \leq \epsilon_{op} v_{\max}$, the bound picks up an additive $2\epsilon_{op} m v_{\max}$ gap, preserving the structural form.

Key Design Choices

• Attribution-agnostic: MtS works with any per-sample scoring method (oracle, LESS, EL2N, influence-based)
• Domain-uniform-cost extension: Budget constraint becomes $\sum_c p_c n_c \leq B$ for data pricing
• Complexity: Runtime dominated by sorting ($O(N \log N)$), negligible vs. fine-tuning cost

Empirical Validation / Results

Setup

• Data pool: 50K–200K instruction-tuning samples from 13 public sources, partitioned into T=8 skill domains
• Models: Qwen3-8B (main), Llama-3.1-8B-Instruct, Llama-3.2-3B-Instruct (cross-model), LoRA rank 16
• Baselines: LESS, EL2N, Superfiltering, DEITA, k-DPP, Facility Location, CRAIG, Stratified, Random, DoReMi, RegMix, DIDS

Main Results

Table 2: Performance Comparison (utility, higher is better)

Key findings:

• MtS beats all baselines by 20–54% relative
• MtS's 1K subset beats full 50K training by Δ = +0.146
• All sample-level methods bunch near random when off-domain samples are reused
• MtS with cheap EL2N attribution recovers 97% of oracle utility at ~4 orders of magnitude less compute

Table 3: Downstream Benchmarks (Qwen3-8B, 50K pool)

Table 4: Compute-Utility Tradeoff (N=50K, Qwen3-8B)

Data Pricing Application

Table 5: Data Purchasing under Budget (Llama-3.2-3B-Instruct)

Notably, the additive baseline's utility decreases with budget (ignoring interactions wastes capacity on redundant samples), while MtS tracks the oracle closely and matches it on 58% of instances.

Theoretical and Practical Implications

Theoretical Contributions

1. CDS framework: Separates attribution from selection, generalizing submodular selection to admit both complementary and substitutive interactions
2. Spectral guarantee: The operator-norm-based bound is ~51× tighter than entrywise Bounded-Complementarity forms on real data
3. Stage-decomposed gap: Within-domain and cross-domain residual interactions contribute separable terms, each controlled by operator norms

Practical Implications

1. Domain mixture > attribution: The load-bearing decision is which domains to sample from, not which per-sample score to use
2. Capacity dependence: Gains require sufficient model capacity (gap grows with LoRA rank); at high ranks MtS achieves Δ = +0.046 vs. Stratified
3. Cost efficiency: MtS uses 43% less total compute than full-data training and 77% less than LESS, with ~27% higher utility
4. Screening rule: Fit a pilot predictor; proceed if predicted gain over uniform allocation exceeds uncertainty, else use Stratified

Conclusion

The paper's central finding is that for modern LLMs, selecting the domain mixture matters more than per-sample scoring. MtS provides a practical, theoretically-grounded algorithm that:

• Outperforms strong baselines by 20–54% across models, data pool sizes, and attribution methods
• Generalizes to budget-constrained data purchasing with varied prices
• Remains robust to domain definition changes (coarsening, relabeling, noise)

Future directions: vendor-level pricing, alternative task aggregations under non-uniform priorities, alignment with specific downstream evaluation goals, and scalable calibration at very large data scales. The broader takeaway: as LLMs improve at cross-task learning, data composition becomes as critical a design lever as model architecture.