# Pick the Mixture, Not the Samples: Combinatorial Data Selection for LLMs

> Combinatorial data selection that optimizes domain mixture before ranking samples outperforms per-sample scoring by 20-54%, making domain allocation the key lever in LLM fine-tuning.

- **Source:** [arXiv](https://arxiv.org/abs/2610.14028)
- **Published:** 2026-10-24
- **Permalink:** https://picx.dev/p/fJH0z7
- **Whiteboard:** https://picx.dev/p/fJH0z7/image

## Summary

## 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)**

| Selection | Attribution | Qwen3-8B N=50K m=1K | Qwen3-8B N=200K m=3.5K | Llama-3.2-3B N=50K m=1K |
|---|---|---|---|---|
| **MtS** | **Oracle** | **0.694** | **0.718** | **0.281** |
| Stratified | Oracle | 0.666 | 0.694 | 0.190 |
| Greedy (top-m) | Oracle | 0.603 | 0.632 | -0.203 |
| Greedy | LESS | 0.548 | 0.580 | -0.238 |
| Greedy | EL2N | 0.567 | 0.598 | -0.244 |
| Greedy | Superfiltering | 0.534 | 0.640 | -0.179 |
| Greedy | DEITA | 0.531 | 0.579 | -0.109 |
| k-DPP | DPP kernel | 0.581 | 0.612 | -0.101 |
| Facility Location | Submodular | 0.554 | 0.586 | -0.016 |
| Random | Uniform | 0.549 | 0.567 | 0.076 |
| CRAIG | Gradient matching | 0.452 | 0.579 | -0.204 |
| Full data | — | 0.548 | 0.581 | 0.030 |

**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)**

| Method | IFEval | MMLU | GSM8K | ARC-C | HumanEval |
|---|---|---|---|---|---|
| **MtS*** | **0.5048** | **0.7254** | **0.8062** | **0.5857** | **0.8049** |
| RegMix | 0.4822 | 0.7136 | 0.7959 | 0.5558 | 0.7703 |
| DoReMi | 0.4802 | 0.7149 | 0.8016 | 0.5316 | 0.7622 |
| LESS† | 0.4484 | 0.7213 | 0.7930 | 0.5486 | 0.7512 |

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

| Method | m | u | GPU-hr |
|---|---|---|---|
| Stratified | 1k | 0.666 | 0.58 |
| Stratified | 5k | 0.678 | 2.92 |
| EL2N | 1k | 0.567 | 1.43 |
| **MtS** | **1k** | **0.694** | **16.58** |
| **MtS** | **5k** | **0.691** | **18.92** |
| Full data | 50k | 0.548 | 29.17 |
| LESS | 1k | 0.548 | 70.58 |

### Data Pricing Application

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

| Method | B=15% | B=20% | B=25% |
|---|---|---|---|
| Additive LP | 0.197 | 0.146 | 0.137 |
| **MtS** | **0.229** | **0.242** | **0.249** |
| Oracle | 0.236 | 0.246 | 0.250 |
| **Optimality recovery** | **89.5%** | **95.6%** | **98.3%** |

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.

---

_Markdown view of https://picx.dev/p/fJH0z7, served by PicX — AI-generated visual whiteboard summaries of research papers._