One Data Shapley Vector Is Not Enough
12 min read
We have a pool of \(d\) training points and room to train on only \(m\) of them. Which \(m\)? The obvious plan is to score each training point by how much it contributes to accuracy on a held-out validation set, sort, and keep the top \(m\).
Data Shapley, introduced by Ghorbani & Zou [GZ, ICML ’19], supplies exactly that score: each training point’s Shapley value in the game “retrain on a coalition of data, measure validation accuracy.” The scores are good at flagging mislabeled and corrupted points. And yet the obvious plan does not always work: selecting the top scorers can be no better than picking at random (Wang, Yang, Zou, Kwon & Jia [WYZKJ, ICML ’24]). I had filed that under estimation noise, since the scores come from Monte Carlo over retrainings. Tian, Fan, Sim, Wang, Chen & Low [TFSWCL, ICML ’26] look instead at how the linearity of the Shapley value interacts with accuracy as the metric, and find a failure that survives exact Shapley values, because it is built into the aggregation.
The failure traces to the choice of game: define it carelessly and we get clean Shapley values for a question we did not mean to ask (a PSA on Shapley values). The fix, NASH, keeps the per-point vectors that linearity provides for free and aggregates them non-linearly. Selection becomes a coverage problem.
The Game and the Puzzle
A failure that survives exact Shapley values must already be in the game itself. 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.
Linearity Explains the Failure
Nothing in that definition looks broken, so the flaw is in what \(f_V\) averages over. Validation accuracy is an average over the validation points of a per-point correctness game:
\[ f_V(S) = \frac{1}{|V|} \sum_{v \in V} f_v(S). \]
Each component asks one yes-or-no question about a validation point \(v \in V\):
\[ 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). \]
Read left to right, the identity is useful: the same retrainings that determine datum \(i\)’s aggregate value already determine its value for every individual validation point. Read right to left, it is the diagnosis: the aggregate score is an average, and the average discards which points a datum helps.
Here is a three-datum example where that goes wrong. Three training points \(A\), \(B\), \(C\); 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.
In the diagram, the top-two pick leaves the hard pair hollow, while NASH’s pick fills every validation dot. The failure is structural. 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 (do you see why the sort solves it?). But the accuracy of a set is not the sum of its members’ scores. \(A\) and \(B\) are substitutes: each is worth \(\tfrac{5}{14}\) on its own, and the second one adds nothing. No single vector of \(d\) numbers can express substitutability. Expressing it requires knowing that \(A\)’s value and \(B\)’s value sit on the same validation points.
Coverage from Shapley Mass
Keeping all \(|V|\) per-point vectors is easy; knowing what to do with them is the open part. A short computation on the toy turns them into a 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 the mass reads cleanly, because the toy is a coverage game. 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 \,]. \]
Its Shapley values 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\), the mass is the fraction of \(v\)’s helpers that \(M\) contains:
\[ s_v(M) = \frac{|M \cap R_v|}{|R_v|}. \]
That fraction is positive exactly when \(M\) holds a helper, which is what securing \(v\) requires:
\[ f_v(M) = \mathbf{1}[\, s_v(M) > 0 \,]. \]
So on a coverage game the mass determines correctness outright. 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. That is the coverage the aggregate score cannot express.
Real data are messier than pure coverage: a datum can help one point and hurt another, and near-duplicates only partly substitute. But the monotone relationship survives. 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\). Enough mass on a point, and the point is covered.
Aggregating Outside the Shapley Layer
So the objective should spread mass so 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. Where does \(F\) come from? 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.)
Concavity is the engine, and the toy shows it working. 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. The second round is the one that matters. 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. \(C\) wins, and NASH returns the covering pair \(\{A, C\}\). Nothing in the objective mentions coverage; diminishing returns produced it.
In the plot, the two arrows are equal steps in mass and unequal steps in \(F\). The greedy construction also comes with a 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. So when the per-point Shapley values are nonnegative, the objective is monotone submodular (can you prove it?). Greedy then inherits the classical \((1 - 1/e)\) approximation for monotone submodular maximization, proved by Nemhauser, Wolsey & Fisher [NWF, ’78] (see the greedy guarantee). All of it runs on the per-point Shapley vectors, and there are \(|V|\) of them where Data Shapley needed one.
The Cost Is Arithmetic
The components are \(|V|\) separate games, so \(|V|\) Shapley vectors sounds like \(|V|\) times the work. It is not. 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. Every saving traces back to one property of the Shapley value, the one that broke the aggregate score.
Linearity, Both Ways
Linearity works in both directions. It is the property that lets us read exact Shapley values off a fitted surrogate (a PSA on Shapley values), and it makes the per-point decomposition free. The same linearity forces the aggregate to be a plain average. An average cannot encode that two data are substitutes. NASH keeps the linearity and moves the non-linearity outside the Shapley layer, into a concave \(F\) applied to sums of already-computed scores, where it costs arithmetic instead of retrainings. And because the only property of \(\phi\) it uses is linearity, any semivalue (Beta Shapley, Data Banzhaf) drops into the same pipeline unchanged.
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 hand back one number per training point, so top-\(m\) on them meets the same wall. 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 then resolves without blaming the valuation: Data Shapley was never a bad score, and top-\(m\) was reading one vector where there were always \(|V|\). When a score is an average over the things we are trying to cover, keep the terms of the average and select against those.