One Data Shapley Vector Is Not Enough
11 min read
We have a pool of \(d\) training points and room to train on only \(m\) of them. A natural plan is to score each point by how much it helps on held-out validation examples, then keep the highest scorers. Data Shapley supplies such a score by averaging a point’s contribution across possible training groups [GZ, ICML ’19]. Yet choosing the top scores can perform no better than random selection [WYZKJ, ICML ’24].
Two highly scored training points may help the same validation examples, leaving other examples poorly served. A single average score does not tell us which examples each point helps. Even computing that score exactly cannot recover the information lost by averaging. NASH keeps a separate contribution for each validation example, then combines those contributions nonlinearly so that helping a broader range of examples matters [TFSWCL, ICML ’26].
The Game and the Puzzle
What score, exactly, is being sorted? The players are the \(d\) training data \([d] = \{1, \dots, d\}\), and the game \(f_V : 2^{[d]} \to \mathbb{R}\) maps a coalition \(S \subseteq [d]\) to the accuracy, on a held-out validation set \(V\), of a model retrained on \(S\) alone. 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. The loss is in the average: validation accuracy averages over validation points, and averaging forgets which points each datum helps, so two data that help the same points look as valuable as two data that help different points. The rest of the page makes that loss exact and rebuilds selection from the per-point pieces.
Linearity Explains the Failure
How can a score computed exactly from the right retrainings lose anything? Validation accuracy averages a separate correctness game over the validation points:
\[ f_V(S) = \frac{1}{|V|} \sum_{v \in V} f_v(S). \]
Each component records whether the retrained model classifies one validation point \(v \in V\) correctly:
\[ 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\)). 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.
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.
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
What do the per-point vectors say about a set of data, rather than about one datum at a time? 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
How do we turn mass into a rule that covers every validation point? 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. The set \(M^\star\) is built greedily: add the datum with the largest gain in the objective, \(m\) times. Validation points differ in how much help they need, so 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, so any increasing concave \(F\) gives a coverage objective. 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
Doesn’t computing \(|V|\) Shapley vectors cost \(|V|\) times as many retrainings? No: every estimator of \(\phi_i(f_V)\) already retrains on sampled coalitions and measures validation accuracy, and that accuracy is an average of 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
Which parts of the construction depend on the Shapley value in particular? 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. When a score is an average over the things we are trying to cover, keep the terms of the average and select against those.