One Data Shapley Vector Is Not Enough
10 min read
Suppose we have more training data than we can afford to use. A natural approach is to score each point by how much it helps and keep the highest scorers. Data Shapley supplies such a score by averaging the improvement from adding a point to different training sets [GZ, ICML ’19].
Surprisingly, even exact scores can lead us to choose a poor training set. Two high-scoring points may help the model on the same test examples. A lower-scoring point could help on examples neither of them serves. Selecting points together calls for keeping track of where each one helps.
The Game and the Puzzle
We have room for \(m\) of \(d\) training points, indexed by \([d] = \{1, \dots, d\}\). For a training subset \(S\), let \(f_V(S)\) be the accuracy of a model retrained on \(S\), measured on held-out examples \(V\) called the validation set. Treating the training points as players makes \(f_V\) a game: it assigns a value to each group of points. The Shapley value of datum \(i\) is the weighted average of its marginal contributions:
\[ \phi_i(f_V) = \sum_{S \subseteq [d] \setminus \{i\}} \frac{|S|!\,(d - |S| - 1)!}{d!}\, \big( f_V(S \cup \{i\}) - f_V(S) \big), \]
where the weight is the probability that a uniformly random ordering of the data seats exactly the coalition \(S\) before \(i\). Selecting a training set of size \(m\) then looks one sort away: compute the \(d\) scores, keep the \(m\) largest. It is that top-\(m\) heuristic which sometimes loses to random selection [WYZKJ, ICML ’24].
For each validation point \(v \in V\), define the correctness game:
\[ f_v(S) = \mathbf{1}\big[\text{the model retrained on } S \text{ gets } v \text{ right}\big], \]
where \(\mathbf{1}[\cdot]\) is one when its argument holds and zero otherwise, so each \(f_v\) is a game with values in \(\{0, 1\}\) (with the convention \(f_v(\emptyset) = 0\)).
A three-datum example makes the loss concrete. There are three training points \(A\), \(B\), \(C\) and seven validation points, five easy and two hard. A model gets an easy point right exactly when its training set contains \(A\) or \(B\), and a hard point right exactly when it contains \(C\). For an easy point \(v\), datum \(A\) raises the accuracy from \(0\) to \(1\) exactly when \(A\) arrives before \(B\) in the random ordering (otherwise \(B\) has already secured the point), which happens half the time, while \(C\) never changes the outcome:
\[ \phi_A(f_v) = \phi_B(f_v) = \tfrac{1}{2}, \qquad \phi_C(f_v) = 0. \]
For a hard point \(v\) the roles swap, with \(C\) taking the full value and the other two acting as dummies:
\[ \phi_C(f_v) = 1, \qquad \phi_A(f_v) = \phi_B(f_v) = 0. \]
Averaging each datum’s score over the five easy and two hard points collapses the two cases into one vector:
\[ \phi_A(f_V) = \phi_B(f_V) = \frac{5 \cdot \tfrac{1}{2} + 2 \cdot 0}{7} = \frac{5}{14}, \qquad \phi_C(f_V) = \frac{5 \cdot 0 + 2 \cdot 1}{7} = \frac{4}{14}. \]
The two largest scores are \(\phi_A(f_V)\) and \(\phi_B(f_V)\), so top-\(m\) with \(m = 2\) selects \(\{A, B\}\). That pair covers every easy point and misses both hard ones, for validation accuracy \(\tfrac{5}{7}\). Now compare against a uniformly random pair. Of the three pairs, only \(\{A, B\}\) misses anything: \(\{A, C\}\) and \(\{B, C\}\) each get all seven validation points right. So the average accuracy of a random pair beats what the scores chose:
\[ \frac{1}{3}\left( \frac{5}{7} + 1 + 1 \right) = \frac{19}{21} > \frac{5}{7}. \]
Exact Shapley values, computed to the last decimal, select strictly worse than random.
To understand the loss, we need to look at what happens when validation accuracy averages over examples.
Linearity Explains the Failure
Validation accuracy averages a separate correctness game over the validation points:
\[ f_V(S) = \frac{1}{|V|} \sum_{v \in V} f_v(S). \]
The Shapley value is a fixed linear combination of its argument’s \(2^d\) values. Substituting \(f_V = \tfrac{1}{|V|}\sum_{v \in V} f_v\) and pulling the average through those fixed weights leaves a per-point average of Shapley values:
\[ \phi_i(f_V) = \frac{1}{|V|} \sum_{v \in V} \phi_i(f_v). \]
The same retrainings that determine datum \(i\)’s aggregate value also determine its value for every validation point. But the aggregate score discards which points a datum helps.
The diagram preserves the per-validation-point pattern that the aggregate score loses. Sorting by score and keeping the \(m\) largest exactly solves one particular set objective:
\[ \max_{M \subseteq [d],\; |M| = m} \; \sum_{i \in M} \phi_i(f_V), \]
a plain sum of per-member scores. The accuracy of a set is not such a sum: \(A\) and \(B\) are substitutes, each worth \(\tfrac{5}{14}\) on its own, while the second one adds nothing. No single vector of \(d\) numbers can express this substitutability. Expressing it requires knowing that \(A\)’s value and \(B\)’s value sit on the same validation points.
Coverage from Shapley Mass
The \(|V|\) per-point vectors support a set-level selection rule. Define the Shapley mass that a candidate set \(M \subseteq [d]\) places on validation point \(v\):
\[ s_v(M) = \sum_{i \in M} \phi_i(f_v). \]
In words, the mass is how much of the credit for getting \(v\) right sits inside \(M\). In the toy coverage game, the mass has a closed form. Write \(R_v \subseteq [d]\) for the set of data that can secure point \(v\) (the easy points have \(R_v = \{A, B\}\), the hard points \(R_v = \{C\}\)), so the model gets \(v\) right exactly when the training set meets \(R_v\):
\[ f_v(S) = \mathbf{1}[\, S \cap R_v \neq \emptyset \,]. \]
Claim: in a coverage game, the mass is the fraction of \(v\)’s helpers that \(M\) contains, and positive mass is equivalent to getting \(v\) right:
\[ s_v(M) = \frac{|M \cap R_v|}{|R_v|}, \qquad f_v(M) = \mathbf{1}[\, s_v(M) > 0 \,]. \]
Proof
The Shapley values of \(f_v\) are an equal split among the helpers. A datum outside \(R_v\) never changes the outcome, so it contributes nothing:
\[ \phi_i(f_v) = 0 \quad \text{for } i \notin R_v. \]
A datum inside \(R_v\) is pivotal exactly when it is the first of \(R_v\) to arrive in the random ordering, and by symmetry each of the \(|R_v|\) helpers is first equally often:
\[ \phi_i(f_v) = \frac{1}{|R_v|} \quad \text{for } i \in R_v. \]
Summing these over the members of \(M\) counts the helpers inside \(M\), each at weight \(1/|R_v|\), which is the fraction in the claim. That fraction is positive exactly when \(M\) holds a helper, which is what securing \(v\) requires.
In the toy, \(\{A, B\}\) loads mass \(1\) onto every easy point and \(0\) onto every hard one, while \(\{A, C\}\) puts positive mass on all seven points. Real data are messier than pure coverage: a datum can help one point and hurt another, and near-duplicates only partly substitute. Tian, Fan, Sim, Wang, Chen & Low [TFSWCL, ICML ’26] make a consistent-player assumption: each datum helps or hurts a given point consistently and never both. Under it, some threshold on \(s_v(M)\) recovers \(f_v(M)\) exactly, with high probability over a uniformly random \(M\) of size \(m\).
Aggregating Outside the Shapley Layer
The objective should spread mass so that every validation point clears its threshold, rather than maximize total mass. NASH (Non-linear Aggregation of SHapley-informative components) does that by putting a concave function between the mass and the score:
\[ M^\star = \operatorname*{argmax}_{M \subseteq [d],\; |M| = m} \; \sum_{v \in V} F\big( s_v(M) \big), \]
where \(F\) is increasing and concave, so each extra unit of mass on a point counts for less than the one before. We approximate this maximization greedily: add the datum with the largest gain in the objective, \(m\) times. When the masses are nonnegative and \(F\) is a cumulative distribution function on that domain, the objective also has a threshold interpretation. Model the mass that point \(v\) needs as a random threshold \(\tau_v\) with cumulative distribution function \(F\). A point is covered when its mass clears its threshold, \(s_v(M) \ge \tau_v\), so the expected number of covered points sums those probabilities over the validation set:
\[ \sum_{v \in V} \Pr(\tau_v \le s_v(M)) = \sum_{v \in V} F\big( s_v(M) \big). \]
That sum is the objective above. An increasing concave \(F\) gives diminishing returns; when it is also a threshold distribution, the objective is expected coverage. The concrete choice is a saturating exponential, \(F(x) = 1 - e^{-\lambda x}\), picked for the shape of a learning curve: large gains from the first relevant data, saturation after that. The rate \(\lambda > 0\) is the method’s one hyperparameter. (Take \(F\) logarithmic instead and the objective is the Nash welfare, a second reading of the name.)
In the toy, concavity changes the second greedy step. Take \(\lambda = 2\), so \(F(s) = 1 - e^{-2s}\); any \(\lambda\) that bends \(F\) visibly across \([0, 1]\) behaves the same. The first greedy step adds \(A\) (or \(B\)). It places mass \(\tfrac{1}{2}\) on each of the five easy points, whereas \(C\) would place mass \(1\) on each of the two hard points, so the first-round gains are:
\[ A: \; 5\,F(\tfrac{1}{2}) \approx 3.16, \qquad C: \; 2\,F(1) \approx 1.73, \]
and five half-covered points beat two fully covered ones. Adding \(B\) raises the five easy points from mass \(\tfrac{1}{2}\) to mass \(1\), a second half-unit each, while adding \(C\) raises the two hard points from \(0\) to \(1\):
\[ B: \; 5\,\big(F(1) - F(\tfrac{1}{2})\big) \approx 1.16, \qquad C: \; 2\,\big(F(1) - F(0)\big) \approx 1.73. \]
The easy points are already half covered, so their second half-unit of mass moves \(F\) less than their first did. The second-round gain is larger for \(C\), so NASH returns the covering pair \(\{A, C\}\) even though the objective contains no explicit coverage indicator.
In the plot, equal increases in mass produce smaller gains once a validation point already has some coverage. For nonnegative per-point Shapley values, the greedy construction also has an approximation guarantee. Each \(s_v(\cdot)\) is modular, a plain sum of fixed per-member scores. An increasing concave function of a nonnegative modular function is submodular, and a sum of submodular functions is submodular. The objective is therefore monotone submodular. Greedy then inherits the classical \((1 - 1/e)\) approximation for monotone submodular maximization, proved by Nemhauser, Wolsey & Fisher [NWF, ’78] (see the greedy guarantee). The calculation uses all \(|V|\) per-point Shapley vectors rather than their average.
Computational Cost
Estimators of \(\phi_i(f_V)\) already retrain on sampled coalitions and measure validation accuracy. That accuracy averages the per-point correctness values that define each \(f_v\). The same retrainings furnish all \(|V|\) vectors at once; the extra cost is storing \(|V|\) numbers per coalition instead of their average. The greedy aggregation is cheap on its own: each of the \(m\) rounds scores each of the \(d\) candidates by a sum over \(|V|\) points, so selection is \(O(m\,d\,|V|)\) arithmetic on numbers already in hand, seconds against the retrainings.
Beyond Data Shapley
Linearity lets us read exact Shapley values from a fitted surrogate (a PSA on Shapley values) and makes the per-point decomposition free. It also forces the aggregate score to be an average that cannot encode substitutes. NASH applies the non-linearity outside the Shapley layer, using a concave \(F\) on sums of already-computed scores. Because the construction uses only linearity, any semivalue with that property, including Beta Shapley and Data Banzhaf, fits the same pipeline.
The same pipeline runs across regimes: choosing which OpenML rows to fit a logistic regression on, and choosing which examples to finetune BERT and Llama-2 with. On the BERT paraphrase task, selecting a fifth of the pool, NASH reaches about \(77\%\) validation accuracy, against about \(70\%\) for both top-\(m\) Data Shapley and random selection, and below \(60\%\) for influence functions and TracIn. Those last two also return one number per training point, so top-\(m\) selection loses the same coverage information. Flip \(30\%\) of that task’s training labels and Data Shapley does pull ahead of random, about \(66\%\) against \(58\%\), while NASH lands at about \(75\%\). The empirical puzzle does not require Data Shapley to be a bad score: top-\(m\) selection was using one averaged vector where \(|V|\) component vectors were available.