Is Data Shapley Not Better than Random in Data Selection? Ask NASH
Xiao Tian, Jue Fan, Rachael Hwee Ling Sim, Zixuan Wang, Nancy F. Chen, Bryan Kian Hsiang Low · 2026
Read Is Data Shapley Not Better than Random in Data Selection? Ask NASH by Xiao Tian, Jue Fan, Rachael Hwee Ling Sim, Zixuan Wang, Nancy F. Chen, Bryan Kian Hsiang Low (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-10684.txt.
Introduction
Xiao Tian and colleagues set out NASH, a data choice plan that settles whether Data Shapley values beat random choice, and when. Data choice seeks top training sets, and some work picks top-scoring data by Data Shapley or other semivalues, which weigh ties among all sets. Other work finds Shapley choice at times no better than random. NASH splits the goal rule, such as check truth, into plain part rules Shapley scores can read. It then picks data by tuning a goal that joins those parts in a curved way.
The plan thus cashes in on spots where Shapley values guide choice, rather than forcing them onto a tangled goal whole. Tests show NASH lifts Shapley-based data choice results a lot with small added run cost. By splitting a goal into parts where Shapley thought works, the method gives a steady and fast route to top sets.
Catalog record
| CREATOR | Xiao Tian, Jue Fan, Rachael Hwee Ling Sim, Zixuan Wang, Nancy F. Chen, Bryan Kian Hsiang Low |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 112692 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.10684
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Is Data Shapley Not Better than Random in Data Selection? Ask NASH Xiao Tian, Jue Fan, Rachael Hwee Ling Sim, Zixuan Wang, Nancy F. Chen, Bryan Kian Hsiang Low Abstract Data selection studies the problem of identifying high-quality subsets of training data. While some existing works have considered selecting the subset of data with top- m m Data Shapley or other semivalues as they account for the interaction among every subset of data, other works argue that Data Shapley can sometimes perform ineffectively in practice and select subsets that are no better than random . This raises the questions: (I) Are there certain “Shapley-informative” settings where Data Shapley consistently works well? (II) Can we strategically utilize these settings to select high-quality subsets consistently and efficiently? In this paper, we propose a novel data selection framework, NASH ( N on-linear A ggregation of SH apley-informative components), which (I) decomposes the target utility function (e.g., validation accuracy) into simpler, Shapley-informative component functions, and selects data by optimizing an objective that (II) aggregates these components non-linearly. We demonstrate that NASH substantially boosts the effectiveness of Shapley/semivalue-based data selection with minimal additional runtime cost. Our implementation is provided in https://github.com/snoidetx/nash . † † affiliationnotice: Equal contribution 1 Introduction As the scale of machine learning (ML) grows larger, data selection ( 19 ; 1 ) , which aims to select the best subset of training data of a limited size m , has become increasingly important. For example, the ML model owner may have a limited budget to purchase data or a limited storage to store data for training; the raw feasible set may contain harmful data that degrade model utility. Specifically, the utility of a selected subset can be quantified through some utility function u , such as the commonly used validation accuracy u_{V} on a held-out validation set V . However, optimizing u_{V} is computationally challenging . Bruteforce search over all candidate subsets requires exponential number of evaluations of u_{V} (note that the evaluation of u_{V} on each candidate subset requires one round of model training and evaluation). Even if u_{V} is considered (approximately) monotone submodular, the greedy algorithm (i.e., selecting the datum that maximally improves u_{V} at each round) requires polynomial number of evaluations of u_{V} . To address this challenge, a common data selection heuristic is the top- m heuristic : to assign each training datum a numerical score computed using data valuation methods ( 35 ) , and select the subset of training data with top- m scores . Figure 1 : Overview of NASH data selection framework. When the utility function (e.g., validation accuracy u_{V} ) is complex and involves different roles of data (e.g., 3 roles in the figure), Shapley values fail to inform on data with different strengths (e.g., different columns of data in the figure), and thus may perform badly. To address this, our NASH first decomposes u_{V} to simpler, fewer-role components where Shapley values are informative (i.e., each compartment in the figure). It then aggregates these Shapley-informative components non-linearly to account for the interaction among selected data. Data Shapley ( 14 ; 20 ) and its generalization, semivalues ( 10 ; 24 ; 46 ) , are well-known data valuation methods and thus also commonly applied to data selection tasks. Section 2 gives a detailed review of these methods. An important principle of Data Shapley and semivalues is that (†) each datum’s worth depends on other data present in the training set . Thus, each datum i ’s valuation score should incorporate its (marginal) contribution to every subset S of other training data (i.e., u(S\cup\{i\})-u(S) ). This principle is particularly relevant to data selection, because it is sensible that one should not myopically view each datum as working independently when trying to select a subset that jointly works well. Hence, prior works ( 14 ; 24 ; 50 ) have empirically demonstrated the effectiveness of Data Shapley and semivalues (using u_{V} as utility function) in data selection, compared with other methods that do not consider interactions such as leave-one-out (LOO) values and influence functions ( 23 ) . Nonetheless, recent works ( 47 ; 5 ) show that selecting via top- m heuristic with Data Shapley based on u_{V} may sometimes result in an under-performing subset , which can be even worse than random selection (Sec. 2 ). The above paradox implies that Data Shapley is only effective for certain utility functions u . Can we make Data Shapley consistently effective in ML data selection (e.g., using u_{V} as utility function)? Intuitively, selecting with Data Shapley works well when each subset’s sum of Shapley values is indicative of its actual utility. We formalize this Shapley-informativeness property and analyze why arbitrary utility functions u , as well as specific utility functions u_{V} (induced by ML), are not Shapley-informative. Thus, we ask the question: Is there any Shapley-informative ML utility functions such that each subset’s sum of Shapley values is well indicative of its actual utility? We show that simpler utility functions, such as prediction correctness for a single validation datum, are provably Shapley-informative under reasonable assumptions. We name such simpler functions Shapley-informative components , which will serve as building blocks for our proposed data selection framework. This leads to the next question: Given Data Shapley’s advantages (†), can we strategically utilize the Shapley-informative components to consistently achieve effective data selection and optimize u_{V} ? At first glance, readers may think of maximizing the average of these components. However, this linear aggregation recovers the flawed vanilla Data Shapley. Therefore, we present a novel data selection framework, NASH ( N on-linear A ggregation of SH apley-informative components ), which uses a sum of concave functions to aggregate Shapley-informative components. Fig. 1 gives an overview of NASH . We also explain how the NASH objective can be optimized effectively and efficiently using the greedy algorithm, thus introducing minimal additional runtime cost to current Shapley/semivalue-based data selection methods. Notably, existing works on efficient approximation of Shapley values/semivalues (e.g., 14 ; 26 ; 50 ) can be freely plugged into NASH and become effective in data selection , which further validates the practicality of NASH . Our contributions are summarized as follows: • We formalize the Shapley-informativeness property that ensures the effectiveness of Data Shapley for data selection, and analyze why commonly used utility functions fail to satisfy it thus making Data Shapley ineffective ( Section 3.1 ); • We show that simpler utility functions, such as prediction correctness for a single validation datum, are provably Shapley-informative ( Section 3.2 ); • We propose a novel data selection framework NASH based on the above Shapley-informative components, which consistently selects data effectively and efficiently ( Section 3.3 ); • We empirically demonstrate that NASH substantially boosts the effectiveness of Data Shapley and semivalues using various datasets and models ( Section 4 ). Significance to the research community. Due to the inconsistent performance of Data Shapley/semivalues in data selection, existing works have only demonstrated that Data Shapley is beneficial on limited datasets and settings (e.g., injecting noise to the datasets). NASH largely eliminates this restriction and shows that Data Shapley/semivalues can be consistently reliable in data selection and have robust performances across datasets/settings,