Unifying and Optimizing Data Values for Selection via Sequential Decision-Making

Data selection has emerged as a crucial downstream application of data valuation, yet the theoretical foundations for using data values in selection remain underexplored. We reformulate data selection as a sequential decision-making problem where the optimal selection sequence arises from dynamic programming, and data values can be understood as encodings of this optimal sequence. This framework unifies and reinterprets existing methods like Data Shapley through the lens of approximate dynamic programming, revealing them as myopic linear approximations to the sequential problem. We further analyze how selection optimality degrades with utility curvature under submodularity, explaining when and why these approximations fail. To bridge theory and practice, we propose an efficient bipartite graph-based surrogate that preserves submodular structure while enabling scalable greedy selection with provable guarantees. Experiments on classical ML benchmarks and large-scale LLM fine-tuning data selection demonstrate substantial improvements over existing methods. Code is publicly available at https://github.com/frankhlchi/SeqDataVal

Modern machine learning models are trained on very large datasets, but not all of that data is equally useful. Some examples help a model a great deal, others add little, and a few can even hurt its performance. To handle this, researchers created methods that give each training example a usefulness score, and these scores are then used to select a smaller, higher-quality subset for training. It has remained unclear, however, whether these popular scores really select the best possible subset. This paper studies that question. We show that selecting data one example at a time, in order of value, is naturally a step-by-step decision process, and we describe the best way to make those choices. Viewed this way, several widely used methods (such as Data Shapley) are simplified strategies that consider only the next step, which helps explain when they work well and when they fail. Building on this, we develop a faster and more accurate selection method. Across standard benchmarks and large-scale language model fine-tuning, it selects better training data than existing methods while staying efficient enough for practical use.