1 Introduction↩︎

Data plays a fundamental role in modern machine learning, with recent advances heavily dependent on massive datasets [1]–[3]. However, not all data contributes equally to model performance, leading to the development of data valuation methods that quantify the contributions of individual training samples. The dominant approaches to data valuation are grounded in cooperative game theory [4]–[6]. In this formulation, training samples are treated as players in a cooperative game, where the utility function measures the validation performance of models trained on different data subsets. Data values are then derived by aggregating each sample’s marginal contributions across various subset combinations, leading to principled methods such as Data Shapley and more [7]–[9].

These valuation methods provide essential guidance for crucial data-centric tasks like data selection, where the goal is to identify optimal subsets of training data that maximize model performance [7], [10], [11]. The standard protocol evaluates data values through selection curves: data points are ranked by their assigned values, and model performance is measured as more points are incrementally added in descending order of their values. As shown in Figure 1, superior data values (e.g., Data Values I) should show both immediate efficiency through steeper initial curves and sustained effectiveness via consistently higher performance across all selection budgets over its peer Data Values II.

Despite the clear importance of this selection objective, existing methods have not been explicitly optimized for this criterion. We address this gap by first establishing a fundamental optimization objective that captures the selection performance of data values across all possible subset sizes. This optimization problem can be naturally reformulated as a sequential decision-making process, where each selection decision builds upon previous choices, and the cumulative rewards directly and exactly correspond to selection performance across different subset sizes.

We show that this sequential perspective not only provides theoretical clarity but also naturally leads to an exact dynamic programming (DP) solution [12] for the optimal selection sequence, from which data values can be derived as sequence encodings. Furthermore, we reveal that existing methods like Data Shapley [7] and other semi-values [8], [9] can be understood as specific instances of myopic linear cost (reward) function approximation in approximate dynamic programming (ADP) [13], [14]. Through both theoretical and empirical analysis, we show that the effectiveness of such approximations is determined by the utility function’s curvature. This insight aligns with recent observations [11] that Data Shapley performs particularly well on heterogeneous datasets. While our framework provides the optimal selection sequence through DP, its exact computation becomes intractable for large datasets. To bridge this gap between theoretical optimality and practical efficiency, we develop a novel approximation scheme based on bipartite graphs that preserves essential theoretical properties while enabling practical computation.

Specifically, our contributions are listed as follows:

• We formulate selection curves induced by data values as an explicit finite-horizon sequential decision problem, derive an exact DP characterization of the optimal selection sequence (from which data values arise as sequence encodings), and use this lens to reinterpret popular semi-value methods (Shapley, Banzhaf, Beta Shapley) as myopic approximate dynamic programming solutions.

• We provide new theoretical insights by analyzing existing game-theoretic data valuation methods as myopic linear approximations under our framework.

• We develop an efficient approximation scheme using bipartite surrogate utility models that preserve submodular structure, yielding provable guarantees under sufficient sandwich conditions while enabling practical computation.

• Through comprehensive experiments, we identify significant performance gaps in existing data valuation methods compared to optimal selection strategies, and demonstrate that our approximation scheme substantially closes this gap while maintaining computational efficiency.

2 Background and Preliminaries↩︎

2.1 Assumptions and Notation↩︎

We summarize here the standing assumptions and notation used throughout the paper.

2.1.0.1 Datasets and utility functions.

We consider a finite dataset \(\mathcal{D} = \{1,\dots,n\}\) with \(n = |\mathcal{D}|\). A (set) utility function is a map \(U : 2^{\mathcal{D}} \to \mathbb{R}\), and we adopt the normalization \(U(\emptyset) = 0\). Whenever we discuss curvature or submodularity, we additionally assume \(U(\{i\}) > 0\) for all \(i \in \mathcal{D}\). For a subset \(S \subseteq \mathcal{D}\) and element \(i \notin S\), we use the shorthand \(\Delta_i U(S) \triangleq U(S \cup \{i\}) - U(S)\) for the marginal contribution of \(i\) to \(S\). We say \(U\) is monotone if \(U(A) \leq U(B)\) for all \(A \subseteq B \subseteq \mathcal{D}\), and submodular if \(\Delta_i U(A) \geq \Delta_i U(B)\) for all \(A \subseteq B \subseteq \mathcal{D}\) and \(i \in \mathcal{D}\setminus B\).

2.1.0.2 Sequential selection and permutations.

A selection order over \(\mathcal{D}\) is represented by a permutation \(\pi\) of \(\{1,\dots,n\}\). We denote by \(S_k^\pi \triangleq \{\pi(1),\dots,\pi(k)\}\) the size-\(k\) prefix induced by \(\pi\). Given a value function \(v:\mathcal{D}\to\mathbb{R}\), we write \(\pi_v\) for the permutation that sorts points in non-increasing order of \(v\), and write \(S_k^v \triangleq S_k^{\pi_v}\) for the size-\(k\) subset selected by ranking according to \(v\). When the underlying \(v\) is clear from context, we simply write \(S_k\).

2.1.0.3 Data values and marginal-contribution weights.

Game-theoretic data values assign to each point \(i\in\mathcal{D}\) a score \(v(i) = \sum_{S \subseteq \mathcal{D}\setminus\{i\}} \alpha_i(S)\,\Delta_i U(S)\), where \(\alpha_i(S) \geq 0\) are marginal-contribution weights (which may depend on the element \(i\) being valued), with normalization \(\sum_{S} \alpha_i(S) = 1\). In semi-value based methods, these weights do not depend on \(i\) and depend only on the subset size, i.e., \(\alpha_i(S) = \alpha_{|S|}\), and satisfy the normalization \(\sum_{k=0}^{n-1} \binom{n-1}{k} \alpha_k = 1\).

2.1.0.4 Curvature.

For a normalized, monotone submodular function \(U\) with \(U(\{i\}) > 0\) for all \(i\), the curvature \(c \in [0,1]\) is defined as \(c \triangleq 1 - \min_{i \in \mathcal{D}} \frac{\Delta_i U(\mathcal{D}\setminus\{i\})}{\Delta_i U(\emptyset)}\). Intuitively, \(c = 0\) corresponds to linear (modular) utilities, while \(c = 1\) corresponds to maximal diminishing returns.

2.2 Data Values and Data Selection↩︎

The predominant data values leverage solutions from the game theory, known as Game-theoretic Data Values. Please refer to Sections 9.1 and 9.3 for a broader review of other methods.

Data values provide principled approaches for quantifying the importance of training samples, with data selection emerging as a crucial downstream application. The goal of data selection is to identify an optimal subset of training data that maximizes model performance. Recent work [11] has formulated data selection with a fixed size constraint \(S^*_k = \text{argmax}_{S \subseteq \mathcal{D}, |S|=k} U(S)\), where a subset \(S\) of size \(k\) is selected to maximize the utility function \(U\).

The standard protocol for data selection using data values is:

2.3 Sequential Decision-Making and Markov Decision Processes↩︎

Sequential decision-making problems can be systematically modeled through Markov Decision Processes (MDPs) [15]. An MDP is defined by a tuple \(\mathcal{M}=(\mathcal{S}, \mathcal{A}, P, r)\), where \(\mathcal{S}\) represents the finite state space, \(\mathcal{A}\) denotes the set of possible actions, \(P(s'|s,a)\) specifies the probability of transitioning to state \(s'\) when taking action \(a\) in state \(s\), and \(r: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}\) is the reward function.

2.4 Approximate Dynamic Programming↩︎

DP faces computational challenges due to the curse of dimensionality when state and action spaces grow large. Approximate Dynamic Programming (ADP) [13], [14], [16] introduces approximation techniques to address these limitations. The first key strategy in ADP involves parametric function approximation to estimate both value functions and reward functions. Instead of maintaining exact values for each state-action pair \((s,a)\), ADP employs parametric approximations like \(\hat{V}(s;\theta)\) for value functions and \(\hat{r}(s,a;\theta)\) for finite-horizon undiscounted reward functions, where \(\theta\) represents learnable parameters in linear models [17] or neural networks [18]. The second strategy involves simplified decision rules at each state that consider only immediate or limited-horizon future rewards, rather than the full backward induction required by exact dynamic programming. These approximations enable ADP to handle high-dimensional MDPs by trading off exact optimality for computational tractability while maintaining solution quality through careful approximation design. For a comprehensive discussion of ADP methods, we refer readers to Appendix 9.2. Among various ADP approaches to solving sequential decision-making problems, myopic reward function approximation [19], [20] represents the most computationally efficient strategy by combining both approximation strategies: it uses parameterized reward approximation \(\hat{r}(s,a;\theta)\) and adopts the simplest decision rule \(\sigma_{\text{myopic}} = \arg\max_{a \in \mathcal{A}} \hat{r}(s,a;\theta)\). This solution focuses solely on maximizing an approximated immediate reward for the nearest time period, ignoring how current decisions might impact future states.

2.5 Submodular Optimization and Optimization from Samples↩︎

Submodular optimization [21]–[23] aims to maximize set functions that exhibit diminishing returns. The most closely related domain to our work, sequential submodular optimization [24], [25], focuses on optimizing over a sequence of different submodular functions, particularly targeting applications like purchase probability functions in recommendation systems. We employ submodular functions as a theoretical lens to analyze data values behavior, similar to approaches in optimization from samples literature [26]–[28]. For comprehensive reviews, we refer readers to Appendix 9.4 and Appendix 9.5.

3 Sequential Data Selection Framework↩︎

Having introduced the preliminaries, we now present our main sequential data selection framework and introduce the sequential selection problem that forms the foundation of our approach.

3.1 Sequential Data Selection as a Deterministic Markov Decision Process↩︎

The nested constraint \(S_{k-1}^\pi \subset S_k^\pi\) reveals the inherent recursive structure of Problem 3: each selection decision is conditioned on all previous choices, and the marginal contribution of the \(k\)-th selected sample depends on the composition of the existing subset. This sequential dependency naturally suggests reformulating the problem as a Deterministic Markov Decision Process (DMDP). Specifically, this is a finite-horizon, undiscounted, deterministic MDP with no stochastic transitions:

• State \(s_t \subseteq \mathcal{D}\): the set selected so far, with \(s_0=\emptyset\).

• Action \(a_t \in \mathcal{D}\setminus s_t\): the next element to add.

• Transition: \(s_{t+1}=s_t\cup\{a_t\}\) (deterministic).

• Reward: \(r(s_t,a_t)=U(s_t\cup\{a_t\})\).

Remark (Reward design). We define the per-step reward as the prefix utility \(U(s_{t+1})\) rather than the marginal gain \(\Delta_{a_t}U(s_t)\). This choice ensures that the cumulative reward \(\sum_{t=0}^{n-1} r(s_t,a_t) = \sum_{k=1}^{n} U(S_k^\pi)\) exactly equals the area-under-the-selection-curve (AUSC) objective in Problem 3; using marginal gains would instead yield \(U(S_n^\pi) = U(\mathcal{D})\), a constant independent of \(\pi\).

For any trajectory corresponding to a permutation \(\pi\), the cumulative reward is \(\sum_{t=0}^{n-1} r(s_t,a_t)=\sum_{t=0}^{n-1}U(s_{t+1})=\sum_{k=1}^{n}U(S_k^\pi)\), which matches Problem 3 exactly. The one-step greedy (myopic) policy selects \(a_t\in\arg\max_{a\in\mathcal{D}\setminus s_t} U(s_t\cup\{a\})= \arg\max_{a\in\mathcal{D}\setminus s_t}\Delta_a U(s_t)\), where \(\Delta_a U(s_t)=U(s_t\cup\{a\})-U(s_t)\) is the marginal gain. For a linear surrogate \(\hat{U}(S)=\hat{b}+\sum_{i\in S}\theta_i\), we have \(\Delta_a \hat{U}(s)=\theta_a\), so the myopic policy reduces to ranking by \(\theta_a\) (i.e., data values).

To solve the sequential data selection problem, which starts from an empty set and sequentially selects data points until all data is selected, we need to analyze what factors determine the selection quality. The solution quality is fundamentally determined by two key factors (see Figure 2 for a visual overview):

Through this lens of utility modeling and decision-making, we will analyze how different solutions arise from specific choices of these two components.

3.2 An Exact Solution via Dynamic Programming↩︎

Under the DMDP formulation, our goal is to find an optimal policy that maximizes the cumulative reward starting from any state. Let \(V(s)\) denote the optimal value function starting from state \(s\), representing the maximum achievable cumulative reward from state \(s\) onwards. According to the Bellman optimality equation [12]:

\[\label{eq:bellman} V(s) = \begin{cases} 0, & \text{if } |s| = n \\ \begin{align}[t] &\max_{a \in \mathcal{D}\setminus s} \big\{U(s \cup \{a\}) \\ &\quad \quad + V(s \cup \{a\})\big\} \end{align}, & \text{otherwise} \end{cases}\tag{1}\]

where the terminal value is \(0\) since no further selections can be made, and the cumulative return is accumulated through the per-step rewards \(U(s\cup\{a\})\).

The optimal policy \(\sigma^*(s) = {\text{argmax}}_{a \in \mathcal{D}\setminus s} \{U(s\cup\{a\})+V(s \cup \{a\})\}\) outputs the action that maximizes the sum of immediate reward and future value, naturally inducing an optimal selection sequence. This solution represents the ideal case where both components achieve optimality: (1) Reward Modeling: the ground-truth utility function \(U\), and (2) Decision Policy: full-lookahead decision policy through immediate reward plus value function maximization as shown in Equation 1 .

However, this exact solution faces significant computational challenges as it requires evaluating utilities for exponentially many subsets, motivating the need for efficient approximation methods. Specifically, the state space has \(2^n\) subsets and each state has up to \(n\) actions, yielding \(O(n \cdot 2^n)\) state-action pairs. If each utility evaluation \(U(\cdot)\) is treated as an \(O(1)\) oracle call, evaluating the Bellman equation requires \(O(n \cdot 2^n)\) time. In practice, however, each utility evaluation may itself be expensive (e.g., requiring model retraining), making the exact DP solution computationally prohibitive.

3.3 Approximated Solutions via Approximated Dynamic Programming↩︎

The exact solution through dynamic programming, while theoretically optimal, faces significant computational challenges in both key components: obtaining the ground-truth utility \(U(s)\) requires model retraining for exponentially many subsets, and computing the optimal value function requires evaluating all possible future states recursively.

To address these computational challenges, we can leverage Approximate Dynamic Programming (ADP) to simplify both components. For reward modeling, instead of computing the ground-truth utility through actual model training, we can approximate it with parametric surrogate functions. For decision making, rather than considering all future states through value function optimization, we can adopt myopic policies that only consider immediate rewards. As we will show, existing data valuation methods naturally fit into this framework through specific approximation choices.

4 Analyzing Existing Data Values via ADP↩︎

Having established the optimal sequential selection framework, we now demonstrate how existing data valuation methods can be unified and analyzed through ADP. This perspective reveals that the ranking sequences induced by data values arise from specific approximation schemes in our sequential decision-making framework.

This regression perspective reveals that these methods implicitly fit a linear surrogate \(\hat{U}(S) = \hat{b} + \sum_{i \in S} \theta_i\) to approximate the true utility function, where the coefficients \(\theta_i\) correspond to data values. This insight directly connects to the ADP framework:

4.1 Optimality Analysis↩︎

We now analyze when existing game-theoretic data values achieve optimal sequential selection.

While linear utility represents an idealized case, real-world selection typically exhibits diminishing returns captured by submodular functions [30]. We characterize performance degradation through the curvature parameter \(c \in [0,1]\), which measures the degree of diminishing returns (\(c=0\) for linear, \(c=1\) for maximum diminishing returns).

The \((1-c)^2\) bound degrades quadratically with curvature: when \(c=0\) we recover exact optimality, while as \(c \to 1\) the guarantee weakens. This explains why data valuation methods struggle on highly redundant datasets where points are nearly substitutable. The bound is worst-case and most useful for explaining failures rather than predicting success.

5 Efficient Approximation via Bipartite Graphs↩︎

Our analysis reveals that exact optimal selection requires exponential computation, while existing methods sacrifice optimality through linear approximations. We now develop a practical middle ground: a bipartite graph-based surrogate that preserves submodular structure while enabling efficient greedy selection with provable guarantees.

5.1 Bipartite Graph Construction↩︎

We construct a bipartite graph \(G = (X_{\text{train}}, X_{\text{valid}}, E)\) between training and validation sets.

5.2 Theoretical Guarantees↩︎

Coverage-based surrogates inherit the classical \((1-1/e)\) greedy guarantee for submodular maximization. Under idealized “sandwich” conditions where the surrogate uniformly approximates the true utility, this transfers to an end-to-end guarantee of \((1-\epsilon)(1-1/e)\) for budget-\(k\) selection (Theorem 20 in Appendix 16).

In practice, these sufficient conditions may not hold exactly. Our empirical results instead support the practical claim that the bipartite coverage surrogate is a significantly better predictor of the true utility than linear baselines, which in turn leads to substantially improved greedy selection (see utility approximation quality in Table 1).

Algorithm 3 selects the threshold \(\tau^\ast\) that minimizes the mean squared error between the coverage surrogate \(\hat{U}(S)\) and the measured utility \(U(S)\) over randomly sampled subsets \(S\). While our bipartite approximation does not achieve the optimal performance of exact DP, our experiments demonstrate that it outperforms existing methods while maintaining computational efficiency.

6 Data Values for Selection: From Reward Functions to Value Functions↩︎

Our framework reveals a fundamental insight: data values for selection should arise from value functions rather than reward functions. Through the optimal policy derived in Section 3.2, we can define optimal data values as \(v^*(i) = n - t^*(i)\), where \(t^*(i)\) represents the optimal selection step for sample \(i\). Unlike traditional game-theoretic data values (e.g., Shapley) that aggregate marginal contributions via fixed weighting schemes, \(v^*(i)\) is an encoding of the optimal selection sequence: the DP solution yields an optimal permutation \(\pi^*\), and we simply record each sample’s position in this ordering. This value-function perspective naturally captures sequential dependencies that myopic methods miss. The encoding is not unique since any monotonic transform induces the same ranking, and when multiple optimal permutations exist, \(t^*(i)\) depends on tie-breaking. While exact computation remains challenging due to exponential state space, this perspective suggests that approximate methods like lookahead policies [14] offer promising directions beyond myopic selection.

7 Experiment↩︎

For evaluation, we compare our approach Bipartite with nine baseline data valuation methods including Influence Function [31], Data Shapley [7], Beta Shapley [9], Data Banzhaf [8], AME [32], DVRL [33], DataOob [34], Leave-One-Out (LOO) and Random, all implemented in OpenDataVal [35] and other public dataset sources. We conduct experiments on eight diverse datasets from OpenML [36], following the standard data valuation evaluation protocol that generates selection curves by iteratively adding points based on their assigned values. Unless otherwise stated, all classical OpenML experiments are averaged over 20 independent runs with 1000 model retraining steps except for the DynamicProgramming method (Algorithm 6), which is used for optimality verification in sequential selection. Detailed experimental settings and dataset descriptions are provided in Appendix 18.

7.1 RQ1: How Close are Existing Data Values to Optimal Sequential Selection?↩︎

Following the experimental settings detailed in Appendix 18.5, our quantitative analysis reveals substantial performance gaps between existing methods and the optimal sequential selection method DynamicProgramming, as summarized in Table [tab:dp95gap]. Across all datasets, existing methods consistently underperform optimal selection by 8.39% to 23.76%. The largest gap appears in structured datasets, particularly bbc-embeddings where the best baseline falls short by 23.76%. For detailed analysis of selection curves and method-specific behaviors across different data budgets, we refer readers to Appendix 21.

width=0.9

7.2 RQ2: How Does Curvature Impact the Performance of Game-theoretic Data Values?↩︎

To empirically examine our theoretical analysis of utility curvature’s impact on data valuation methods, we construct a controlled experimental framework using iterative message-passing. Given a dataset with class labels, we implement an iterative feature aggregation process parameterized by a propagation proportion \(p \in [0,1]\). At each iteration, each data point \(x_i\) updates its features according to: \[x_i^{new} = (1-p)x_i + p\cdot\text{mean}({x_j | j \in \mathcal{N}_i})\] where \(\mathcal{N}_i\) represents the set of within-class neighbors of point \(i\). This mechanism provides control over data point substitutability, which serves as a proxy for the utility function’s curvature: at \(p=0\) (no message-passing), points maintain their original distinctive features (low substitutability, corresponding to low curvature), while at \(p=1\) (full message-passing), points within each class converge through complete feature averaging (high substitutability, corresponding to high curvature). Through systematic variation of \(p\), we examine the impact of increasing feature similarity on both the mean performance and selection curves of different valuation methods.

Our results in Figure 4 demonstrate three key findings that are consistent with the theoretical predictions (more detailed six propagation steps with step size 0.2 analysis in Appendix 19): (1) under low substitutability (\(p=0.0\)), all methods DataShap, BetaShap, and Banzhaf achieve strong performance with mean accuracy above 0.70; (2) as substitutability increases through higher propagation proportions (serving as a curvature proxy), we observe systematic performance degradation across all methods; and (3) the convergence in performance between these game-theoretic methods at high substitutability is consistent with our analysis that all these approaches face similar fundamental limitations under strong substitution effects. Note that we do not directly compute the true curvature \(c\); rather, we use substitutability as a qualitative proxy that aligns with the theoretical framework.

width=0.9

7.3 RQ3: How Effective is Bipartite-based Approximation for Data Selection?↩︎

Following the experimental settings detailed in Appendix 18.6, the selection curves in Figure 5 demonstrate the clear advantages of our bipartite-based approach Bipartite. On structured datasets like bbc-embeddings, our method exhibits remarkably steep initial performance improvements, achieving over 60% accuracy with just 20 samples, ahead of the baselines in this early-selection regime. This pattern of superior early-stage selection is consistently observed across different datasets.

The performance advantage is particularly pronounced on complex datasets with heterogeneous feature distributions. In the digits dataset, our method demonstrates exceptional sample efficiency, reaching 80% accuracy with just 25 samples, while baseline methods require nearly twice as many samples to achieve comparable performance. Similar patterns emerge in the nomao dataset, where our method shows a clear advantage in the crucial early stages where efficient selection is most valuable, and attains the highest average accuracy over the selection curve. Even on relatively simpler datasets like 2dplanes and fried, our method shows noticeable improvements in selection efficiency. The curves reveal not only faster initial accuracy gains but also more stable progression, with fewer fluctuations compared to baseline methods. The electricity dataset results further emphasize this stability, where our method shows a strong early-stage advantage and attains the highest average accuracy. To quantify these observations, we present detailed average performance metrics for the selection curves of Figure 5 in Table 7.

Large-scale Data Selection Effectiveness. To further validate the effectiveness on large-scale data selection, we extended our evaluation to larger selection budgets of 500 data points. As shown in Table [tab:selection95results95500], our Bipartite method achieves the highest average accuracy (0.828) across all datasets. Notably, it ranks first on three datasets (bbc-embeddings, MiniBooNE, digits) and ties for first on two others (election, electricity). The performance gaps between methods narrow at larger budgets, as expected when selecting a significant portion of the dataset. Yet our method consistently maintains competitive or superior performance. Traditional methods like DataShap and BetaShap perform competitively (averaging 0.820 and 0.821, respectively) compared to learning-based approaches like DVRL (0.758), aligning with our theoretical analysis that game-theoretic methods maintain reliable performance when data substitutability effects diminish at larger selection sizes.

Utility Approximation Performance. To validate our bipartite model’s effectiveness as a utility approximation, we compare its approximation quality against standard baselines including linear regression, MLP, and game-theoretic methods. We evaluate the surrogate actually used by each method on the same sampled subsets: for linear and game-theoretic baselines, this is the linear surrogate \(\hat{U}(S)=\hat{b}+\sum_{i\in S}\theta_i\); for Bipartite, it is the learned coverage surrogate; and for MLP, it is the fitted nonlinear predictor. When a method is characterized by centered-feature regression (e.g., Banzhaf or Beta Shapley in Theorem 5), we use the equivalent uncentered parameterization from Remark 12, and for fairness fit only the intercept \(\hat{b}\) by least squares on the same sampled subsets (this does not change the induced ranking but is necessary for comparing approximation error). As shown in Table 1, our method achieves significantly lower approximation error (MSE: 0.019) compared to all baselines, with the next best method (linear regression) having more than four times higher error (MSE: 0.089). This validates our theoretical insight that the bipartite coverage structure effectively captures the underlying utility relationships while maintaining computational efficiency.

LLM Fine-tuning Data Selection. Beyond classical ML benchmarks, we evaluate on large-scale LLM fine-tuning using the DATE-LM benchmark [37]. We adapt our bipartite approach to this setting as BipCov, which constructs the bipartite graph using RAG-style embeddings between pool instructions and task reference examples (details in Appendix 18.7). Under the official DATE-LM pipeline (200k instruction pool, select 10k examples, LoRA fine-tune Llama-3.1-8B, evaluate on MMLU/GSM8K/BBH), BipCov achieves 63.89\(\pm\)​0.34% average accuracy (mean\(\pm\)std over three seeds), improving over the strong baseline RDS+ (62.88\(\pm\)​0.25%) and Random (62.82\(\pm\)​0.31%). Unlike similarity-based methods that score each example independently, BipCov first prioritizes reference coverage and then falls back to reference similarity after binary coverage saturates, yielding a coverage-prioritized ordering for instruction selection.

8 Conclusion↩︎

We establish a theoretical framework unifying data valuation and sequential decision-making, showing that existing game-theoretic methods are myopic linear approximations with fundamental limitations under high utility curvature. To bridge the gap, we develop an effective bipartite graph-based utility approximation and data selection method.

Acknowledgements↩︎

This research was supported by the National Science Foundation (NSF) under grant numbers NSF2406647 and NSF2406648. It was also supported by the National Artificial Intelligence Research Resource (NAIRR) Pilot and the Delta advanced computing and data resource, which is supported by the National Science Foundation under award NSF-OAC-2005572. This work was also supported by IBM through the IBM-Rensselaer Future of Computing Research Collaboration.

Impact Statement↩︎

This paper presents work whose goal is to advance the field of machine learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.

9 Related Work↩︎

9.1 Data Valuation↩︎

Data valuation seeks to quantify the contribution of individual training samples to model performance. Game-theoretic approaches have dominated this field, beginning with Data Shapley [7], which adapts the Shapley value from cooperative game theory to quantify data contributions. This seminal work inspired various extensions, including Beta Shapley [9], which introduces a family of semi-values through Beta function weighting, and Data Banzhaf [8], which provide robust valuation frameworks through binary-weighted marginal contributions. While these general methods are computationally intensive, specialized approaches like [38] achieve near-linear time complexity by exploiting algorithmic structures such as K-Nearest Neighbors, compared to the exponential complexity of model-agnostic approaches. Recent developments address specific challenges in data valuation: [39] proposed CS-Shapley for better handling class-wise contributions in classification tasks, while [40] introduced PC-Winter value to tackle the unique challenges of graph-structured data valuation. Alternative theoretical frameworks, such as the Core [41], have also emerged to address coalition stability in data valuation.

Recent work has focused on improving computational efficiency and valuation accuracy. [42] proposed learning data utility functions to avoid repeated model retraining, while [43] developed DU-Shapley as an efficient proxy through discrete uniform distributions. [44] introduced EcoVal, which accelerates valuation by clustering similar data points and propagating values within clusters. P-Shapley [45] leverages predicted probabilities instead of accuracy for finer-grained utility differentiation. For applications requiring only top-ranked data points, [46] proposed GPGapE, which uses Gaussian processes to model non-linear mappings from data features to values, significantly reducing the computational burden for top-\(m\) data identification. In the graph domain, [47] introduced Shapley-Guided Utility Learning for effective graph inference data valuation, combining transferable data-specific and model-specific features to approximate test accuracy without relying on ground truth labels.

Several approaches have tackled computational challenges through gradient-based methods. [48] introduced In-Run Data Shapley, which calculates Shapley values during model training without requiring retraining, enabling data attribution even for large foundation models. Building on this, [49] proposed data value embedding to capture temporal dependence in data influence, revealing that training data impact varies significantly across different training phases. [50] presented stochastic amortization as a unified approach to accelerate feature and data attribution, using noisy labels to train amortized models that significantly accelerate several data valuation methods.

Parallel efforts have explored training-free and task-agnostic directions. [51] developed SAVA, a scalable variant of the LAVA framework [52] that applies optimal transport between training and validation sets in batches rather than requiring the entire dataset. For generative models, [53] introduced GMValuator, a similarity-based approach that evaluates training data contributions to generated samples without model retraining. [54] proposed a fine-grained analysis called Dataset Usage Cardinality Inference to estimate the exact proportion of data used in training, addressing security concerns for data owners assessing unauthorized usage risks. In the context of large language models, [55] formulated data selection as a generalized Optimal Control problem and introduced PMP-based Data Selection for accelerating the learning of language models through optimally selected pre-training data.

Additional notable approaches include DAVINZ [56], which enables data valuation at network initialization by theoretically deriving domain-aware generalization bounds, while [57] proposed a task-agnostic framework based on statistical properties without validation requirements. Alternative paradigms include reinforcement learning-based approaches like DVRL [33] and complexity-gap scoring [58], which offer diverse perspectives beyond traditional game-theoretic methods.

9.2 Approximate Dynamic Programming↩︎

Sequential decision-making under uncertainty has been extensively studied through the lens of Markov Decision Processes [12]. However, exact solutions become computationally intractable for large state spaces, motivating the development of Approximate Dynamic Programming (ADP) methods [13], [14]. Key ADP techniques include value function approximation, which represents the optimal value function through parameterized function classes, and policy gradient methods, which directly optimize parameterized policies [59]. Recent advances combine these approaches with deep learning, leading to successful applications in game playing [60] and robotics [61].

The connection between combinatorial optimization and sequential decision-making has been explored through submodular function maximization, where greedy algorithms provide constant-factor approximations [62]. Our work bridges these areas by showing that data valuation methods implicitly solve a sequential selection problem, with their approximation quality governed by utility function curvature.

9.3 Semi-values↩︎

Semi-values generalize the Shapley value by relaxing the efficiency axiom while maintaining other desirable properties [63]. The Banzhaf value [5] was originally developed for analyzing voting power, while Beta Shapley [9] provides a flexible family of semi-values parameterized by Beta function weights. Recent theoretical work has characterized semi-values through weighted least squares regression [64], a perspective we leverage to establish the ADP interpretation of data valuation methods.

9.4 Submodular Optimization↩︎

Submodular functions provide a powerful mathematical framework for modeling diminishing returns across diverse domains [65]. The seminal work by Nemhauser et al.[62], [66] established that a greedy algorithm achieves a \((1-1/e)\)-approximation for monotone submodular maximization under cardinality constraints—a bound that is provably tight. Recent advances have addressed more challenging settings: [67] improved approximation algorithms for non-monotone submodular maximization with cardinality constraints, while their subsequent work [68] provided a tight \(1/2\)-approximation for unconstrained submodular maximization. Researchers have also explored various extensions, including weak submodularity [69], submodular cover and knapsack constraints [70], and probabilistic models defined through submodular functions [71]. Our work draws on these theoretical foundations, particularly the analysis of approximation bounds, to develop efficient algorithms for data selection that maintain theoretical guarantees while improving computational tractability.

Another closely related domain of sequential submodular optimization [24], [25], [72] focuses on optimizing over a sequence of different submodular functions, particularly targeting applications like product ranking in recommendation systems. Unlike these works which optimize across multiple different submodular functions (where each function evaluates prefixes of different lengths), our Sequential Data Selection Problem maximizes the expected utility across different selection sizes using a single consistent utility function.

9.5 Optimization from Samples↩︎

Optimization from Samples (OPS) addresses how to optimize functions when only sample evaluations are available, not direct oracle access [28]. This paradigm reveals a fundamental gap between learnability and optimizability: [26] showed that for submodular functions with bounded curvature, approximation algorithms exist using polynomial samples, yet [28] established that for coverage functions, no constant-factor approximation is possible with polynomial samples from any distribution. To overcome these limitations, [73] introduced Optimization from Structured Samples (OPSS), where samples encode structural information about the function. With assumptions on subset coverage patterns and marginal contributions, they achieved constant approximations for coverage maximization. For submodular functions, curvature critically affects approximation guarantees. [26] established a \((1-c)/(1+c-c^2)\)-approximation for submodular functions with curvature \(c\), which aligns with our analysis in Section 4.1 where we prove data valuation methods achieve a \((1-c)^2\) approximation for sequential selection. Our bipartite graph approximation method draws inspiration from these structural approaches. Also, [74] extends these sample-based approaches to cooperative games where cost functions must be learned from samples rather than accessed directly.

9.6 Other Linear Surrogate Models for Data Selection↩︎

Beyond traditional data valuation methods based on cooperative game theory [7]–[9], recent approaches have explored linear surrogate functions for model-aware data selection. [75] introduced datamodels, a framework that maps training subsets to model predictions through linear functions, while [76] extended this approach with DsDm to directly optimize training data selection for target tasks. While these methods also model relationships between training data and model performance, our work uniquely frames data selection as a sequential decision process with theoretical guarantees under varying utility structures.

9.7 Efficient Data Valuation Methods↩︎

Recent work has explored various approaches to address the computational challenges in data valuation. These methods can be broadly categorized into two complementary directions. Gradient-based acceleration methods such as G-Shapley [7], All-S Influence [77], and FreeShap [78] focus on reducing the computational cost of each individual model training through gradient approximations or parameter sharing techniques. These approaches maintain the full valuation framework while making each utility evaluation more efficient. In contrast, our Bipartite method belongs to a different category that aims to reduce the total number of model evaluations needed by learning more effective approximations of the utility landscape. While gradient-based methods accelerate each utility computation instance, our approach requires fewer total evaluations to achieve superior selection performance. These two categories of methods are conceptually complementary and could potentially be combined; using gradient-based acceleration for the subset evaluations required by our bipartite graph construction process would further enhance computational efficiency while maintaining the theoretical guarantees of our framework.

9.8 Parallel Work on Unifying Data Selection Methods↩︎

Recent work by [79] presents a comprehensive tutorial on data selection methods for foundation models, focusing on both heuristic and principled approaches to data curation. While their work provides valuable insights into the practical aspects of data selection in foundation model training pipelines, our work differs in several key aspects: First, we focus specifically on the optimization perspective of data selection with data values, providing theoretical guarantees of optimality under our proposed sequential decision making and approximate dynamic programming framework. Their work takes a broader view, covering various selection strategies without explicit optimization guarantees. Second, our work presents a novel unifying framework via approximate dynamic programming (ADP) [14]. This framework reveals that many existing data valuation methods can be interpreted as specific instances of myopic cost function approximation heuristic [19], [20], which is a classical strategy in the ADP literature. This theoretical connection not only provides new insights into why existing methods work but also suggests principled ways to improve them. Third, while both works aim to bridge the gap between heuristic and principled approaches, we focus more on the theoretical foundations of data valuation methods for selection tasks. We provide rigorous analysis of the limitations of data attribution methods and characterize the conditions under which they can achieve optimal performance. Our work thus complements theirs by providing deeper theoretical understanding of data valuation based selection methods, while their tutorial offers broader practical guidance across different selection paradigms. Together, these parallel efforts contribute to advancing both the theoretical foundations and practical applications of data selection methods. In parallel, GraphFilter [80] also formulates data selection over a bipartite graph, but with a sentence–n-gram construction and a set-cover greedy procedure aimed at LLM SFT diversity, in contrast to our training–validation utility-coverage surrogate analyzed within the sequential decision-making framework.

10 Complete Formulation of Theorem 5↩︎

This section provides the complete mathematical formulations for the regression characterizations of game-theoretic data values stated in Theorem 5.

Part (A) [Shapley: Constrained WLS (KernelSHAP form)]: Assume \(n = |\mathcal{D}| \geq 2\). The Shapley value \(v_{\mathrm{Shap}}(i)\) is the unique solution to the constrained weighted least squares problem: \[\label{eq:shapley95wls} \min_{\theta\in\mathbb{R}^n}\sum_{\substack{S\subseteq\mathcal{D}\\ 1\le |S|\le n-1}}\omega_{\mathrm{Shap}}(|S|)\Big(U(S)-\sum_{i\in S}\theta_i\Big)^2 \quad\text{s.t.}\quad \sum_{i\in\mathcal{D}}\theta_i=U(\mathcal{D}),\tag{2}\] where the size weight is \(\omega_{\mathrm{Shap}}(k)=\binom{n-2}{k-1}^{-1}\) for \(1\le k\le n-1\). The sum excludes \(|S|=0\) and \(|S|=n\) since these boundary cases are handled by the normalization \(U(\emptyset)=0\) and the efficiency constraint.

Part (B1) [Banzhaf: Unconstrained OLS with Centered Features]: Sample \(S\sim\mathrm{Unif}(2^{\mathcal{D}})\) (each element included i.i.d.with \(p=\tfrac12\)). Define centered features \(z_i(S)=\mathbb{I}_{i\in S}-\tfrac12\). Then the Banzhaf value satisfies: \[\label{eq:banzhaf95ols} v_{\mathrm{Banz}}(i)=\theta_i^*,\quad (\theta^*,b^*)=\arg\min_{b,\theta}\;\mathbb{E}_{S}\Big[\Big(U(S)-b-\sum_{i\in\mathcal{D}}\theta_i z_i(S)\Big)^2\Big].\tag{3}\]

Part (B2) [Beta Shapley: Weighted OLS with Centered Features]: Assume \(a>1\) and \(b>1\), and assume \(U\) is bounded (see Remark 11 for well-definedness conditions). Draw \(p\sim\mathrm{Beta}(a,b)\); then \(S\mid p\sim\mathrm{Bern}(p)^{\mathcal{D}}\). Define \(z_i(S,p)=\mathbb{I}_{i\in S}-p\) and weight \(w(p)=1/[p(1-p)]\). The Beta Shapley value satisfies: \[\label{eq:betashap95wls} v_{\mathrm{Beta}}(i)=\theta_i^*,\quad (\theta^*,b^*)=\arg\min_{b,\theta}\;\mathbb{E}_{p,S}\Big[w(p)\Big(U(S)-b-\sum_{i\in\mathcal{D}}\theta_i z_i(S,p)\Big)^2\Big].\tag{4}\]

11 Proof of Theorem 5↩︎

We provide proofs for all three parts of Theorem 5.

11.1 Part (A): Shapley as Constrained WLS↩︎

11.2 Part (B1): Banzhaf as Unconstrained OLS↩︎

11.3 Part (B2): Beta Shapley as Weighted OLS↩︎

12 Technical Remarks on Regression Characterizations↩︎

This section collects technical remarks that support the main results in Section 4.

13 Proof of Game-theoretic Data Values as ADP Solutions↩︎

We provide the complete proof that data value-induced rankings correspond to myopic ADP trajectories.

14 Proof of Linear Utility Optimality↩︎

This proof shows that all semi-value methods achieve identical selection performance under linear utilities because they preserve the ordering of the underlying weights \(w_i\). This explains why different methods like Data Shapley, Beta Shapley, and Data Banzhaf all achieve optimal sequential selection despite their different weighting schemes.

15 Analysis of Data Valuation Methods Under Submodular Functions↩︎

In this appendix, we provide a complete proof that ranking-based element selection using any standard data valuation method achieves a \((1-c)^2\) approximation ratio for monotone submodular functions with curvature \(c\). This result unifies previous analyses and provides general curvature-dependent bounds for Shapley value, Banzhaf value, and Leave-one-out methods, providing theoretical foundations for the results presented in Section 4.1 of the main paper.

15.0.0.1 Standing assumptions for this appendix.

Throughout this section, we assume:

• \(U: 2^{\mathcal{D}} \to \mathbb{R}_{\geq 0}\) is non-negative;

• \(U\) is normalized: \(U(\emptyset) = 0\);

• \(U\) is monotone: \(U(A) \leq U(B)\) for all \(A \subseteq B\);

• \(U\) is submodular: \(\Delta_i U(A) \geq \Delta_i U(B)\) for all \(A \subseteq B\) and \(i \notin B\);

• \(U(\{i\}) > 0\) for all \(i \in \mathcal{D}\) (so that curvature is well-defined).

The data value \(v(i)\) is assumed to be a non-negative normalized average of marginal contributions: \[v(i) = \sum_{S \subseteq \mathcal{D}\setminus\{i\}} \alpha_i(S) \Delta_i U(S), \quad \text{with } \alpha_i(S) \geq 0 \text{ and } \sum_S \alpha_i(S) = 1.\] This includes Shapley, Banzhaf, Beta Shapley, and LOO as special cases, but excludes methods that can produce negative scores or are not representable as such normalized averages.

15.1 Preliminaries and Submodular Functions↩︎

Consider a dataset \(\mathcal{D}\) and a monotone submodular utility function \(U: 2^\mathcal{D} \rightarrow \mathbb{R}_{\geq 0}\) with \(U(\emptyset) = 0\). For any sets \(A \subseteq B \subseteq \mathcal{D}\) and element \(i \in \mathcal{D} \setminus B\), monotone submodularity implies: \[\begin{align} U(A) &\leq U(B)\\ U(A \cup \{i\}) - U(A) &\geq U(B \cup \{i\}) - U(B) \end{align}\]

A fundamental property of submodular functions is their curvature, which measures how much marginal contributions decrease as sets grow. For a normalized (\(U(\emptyset)=0\)) monotone submodular function \(U\), its curvature \(c \in [0,1]\) is defined as: \[c = 1 - \min_{i \in \mathcal{D}} \frac{U(\mathcal{D}) - U(\mathcal{D}\setminus\{i\})}{U(\{i\})}\] This definition implies that for any element \(i\) and set \(S \subseteq \mathcal{D}\setminus\{i\}\): \[U(S \cup \{i\}) - U(S) \geq (1-c)U(\{i\})\]

15.2 Data Valuation Methods and Curvature↩︎

We consider data valuation methods that assign a value \(v(i)\) to each element \(i \in \mathcal{D}\) as a weighted average of marginal contributions: \[v(i) = \sum_{S \subseteq \mathcal{D}\setminus \{i\}} \alpha(S)[U(S \cup \{i\}) - U(S)]\] where marginal-contribution weights \(\alpha(S) \geq 0\) satisfy \(\sum_S \alpha(S) = 1\). A particularly important class of such valuations are semi-values, which satisfy additional symmetry properties through size-based weights: \[\alpha(S) = \alpha_{|S|} \text{ for some } \alpha_k \geq 0 \text{ with } \sum_{k=0}^{|\mathcal{D}|-1} \binom{|\mathcal{D}|-1}{k}\alpha_k = 1\] where \(\alpha_k\) represents the weight assigned to all subsets of size \(k\).

This framework encompasses several important cases from the main paper:

1. Data Shapley: \(\alpha(S) \propto \frac{|S|!(|\mathcal{D}|-|S|-1)!}{|\mathcal{D}|!}\)

2. Data Banzhaf: \(\alpha(S) = \frac{1}{2^{|\mathcal{D}|-1}}\)

3. Leave-one-out: \(\alpha(S) = 1\) if \(S = \mathcal{D}\setminus\{i\}\), 0 otherwise

We now establish a fundamental relationship between data values and singleton utility values under curvature constraints.

15.3 Approximation Analysis↩︎

Inspired by the curvature-based analysis framework introduced by [26], we begin by establishing a fundamental relationship between the value of a set constructed through sequential selection and the individual values of its elements. This relationship forms the cornerstone of our approximation guarantee.

This theorem formalizes the approximation guarantee mentioned in Section 4.1 of the main paper:

15.4 Sequential Selection Guarantees↩︎

We now extend our analysis to the sequential selection setting, providing theoretical foundations for the results discussed in Section 4.1:

16 End-to-end Approximation Guarantee for Bipartite Surrogate↩︎

16.1 Submodularity of Coverage Utility↩︎

16.2 End-to-end Approximation Theorem↩︎

This section provides the complete formulation and proof for the theoretical guarantee of our bipartite graph-based approach.

17 Computational Complexity Analysis↩︎

We present a detailed analysis of the computational complexity for our bipartite graph-based approach described in Algorithm 3. Let \(n=|X_{\text{train}}|\) denote the number of training points, \(m=|X_{\text{valid}}|\) the number of validation points, and \(d\) the feature dimensionality. The computational cost comprises three main components.

The first component involves computing pairwise distances between training and validation points, requiring \(\mathcal{O}(nmd)\) operations when using Euclidean distance. While this step dominates the computation for high-dimensional data, it can be optimized through vectorized BLAS operations or approximate nearest-neighbor search techniques.

The second component performs threshold search across \(N_{\tau}\) candidate values. For each threshold, the algorithm evaluates prediction error on \(K\) random subsets through two operations: constructing edges by scanning the distance matrix (\(\mathcal{O}(N_{\tau}nm)\) comparisons) and computing coverage for \(K\) subsets of average size \(k\) (\(\mathcal{O}(N_{\tau}K(k + m))\) operations using efficient bit-set implementations). Since \(k \ll m\) and both \(K\) and \(N_{\tau}\) are small constants in practice (typically \(K=100\), \(N_{\tau}=30\)), the edge construction dominates this phase.

The final component executes greedy selection after determining the optimal threshold \(\tau^*\). Using a priority queue with lazy updates to track residual node degrees, this phase requires \(\mathcal{O}(n\log n + |E_{\tau^*}|)\) operations, where \(|E_{\tau^*}| \leq nm\) represents the number of edges in the sparsified graph.

The total computational complexity thus becomes:

\(\mathcal{O}(nmd) + \mathcal{O}(N_{\tau}nm) + \mathcal{O}(n\log n + |E_{\tau^*}|)\)

Since \(d\) and \(N_{\tau}\) are dataset-specific constants, the algorithm scales linearly with \(nm\). The space complexity is \(\mathcal{O}(nm)\), primarily storing the distance matrix and edge set.

In practical data valuation scenarios where \(m \ll n\), our method offers significant computational advantages over traditional Shapley-based approaches that require extensive model retraining [7], [8]. Furthermore, both distance computation and edge construction phases are naturally parallelizable and GPU-compatible, enabling efficient scaling to larger datasets as demonstrated in our experimental results.

18 Experimental Details↩︎

We provide detailed descriptions of our experimental setup, including baseline methods, datasets, and evaluation protocols.

18.1 Target Model↩︎

In our experiments, the target model used for data valuation is the Logistic Regression model from the Scikit-learn machine learning library. The data valuation process involves repeatedly training this Logistic Regression model on different data subsets to evaluate the marginal contributions of each training sample to the model’s test performance, thereby deriving the corresponding data value scores.

18.2 Baseline Methods↩︎

We evaluate our approach against the following state-of-the-art data valuation methods:

• Random: A naive baseline that randomly selects data points

• LOO (Leave-one-out): Measures each point’s marginal contribution by removing it from the full dataset

• Influence Function [31]: Approximates data influence using model gradients

• Data Shapley [7]: Assigns values based on average marginal contributions across different subset sizes

• Beta Shapley [9]: Generalizes Shapley value by relaxing the efficiency axiom

• Data Banzhaf [8]: Captures influence through binary marginal contributions

• AME (Average Marginal Effect) [32]: Estimates influence using sparse regression

• DVRL (Data Valuation using Reinforcement Learning) [33]: Learns data values through policy optimization

• DataOob (Data Out-of-Bag) [34]: Uses out-of-bag estimates from bagging models to evaluate data utility

All baseline methods are implemented using OpenDataVal [35], ensuring standardized implementation and fair comparison. All experiments were conducted on CPU using Scikit-learn’s built-in multi-threading capabilities for parallel acceleration.

18.3 Dataset Details↩︎

Our experiments use eight diverse datasets from OpenML [36], spanning tabular, text, and image domains:

• 2dplanes (ID 727): A synthetic dataset for binary classification

• nomao (ID 1486) [81]: A real-world dataset for duplicate detection

• bbc-embeddings [82]: Text classification dataset with news articles

• MiniBooNE (ID 43974) [83]: Particle physics dataset for binary classification

• digits [84]: Handwritten digit recognition dataset

• election [85]: Election outcome prediction dataset

• electricity (ID 44080) [86]: Time series dataset for price movement prediction

• fried (ID 901): Synthetic tabular/categorical dataset

These datasets are commonly used in data valuation research [7], [33], [34] and represent a diverse range of learning tasks and data characteristics.

18.4 Evaluation Protocol Details↩︎

For each dataset, we follow a rigorous evaluation protocol:

1. Data Splitting: Each dataset \(\mathcal{D}\) is randomly split into:

   • Training set \(\mathcal{D}_{train}\)

   • Validation set \(\mathcal{D}_{valid}\) (for computing utility functions)

   • Test set \(\mathcal{D}_{test}\) (for evaluation)

2. Value Assignment: Data valuation methods compute values for each training point using validation set performance

3. Sequential Selection:

   • Rank training points by assigned values in descending order

   • Iteratively add points following this ranking

   • Train model on selected subset at each step

   • Record test accuracy

4. Performance Curves: Plot test accuracy versus selection size \(k \in [1,|\mathcal{D}_{train}|]\)

5. Experimental Control:

   • All methods limited to 1000 model retraining steps

   • Results averaged over 20 independent runs

   • Consistent random seeds used across methods

This protocol follows standard practices in data valuation literature [7], [9], [44] and ensures fair and comprehensive evaluation of different methods.

18.5 RQ1 Experimental Settings↩︎

To establish performance bounds and quantify the limitations of existing data valuation methods, we conduct experiments with the following specific settings:

• Data Sampling: For each dataset:

  • Training set: 20 points

  • Validation set: 100 points

  • Test set: 500 points

• Random Seeds: 20 independent trials using seeds from 10 to 200 with step 10

• Methods Compared:

  • Optimal strategy: DynamicProgramming (Algorithm 6)

  • Existing methods: Random, LOO, Influence, DataShap, BetaShap, Banzhaf, AME, DVRL, DataOob

• Evaluation: Test accuracy evaluated by sequentially adding points based on their assigned values

The selection curves are generated by plotting test accuracy against selection size \(k\), with results averaged over all trials.

18.6 RQ3 Experimental Settings↩︎

We evaluate our bipartite graph-based approximation approach Bipartite with the following settings:

• Dataset Splitting:

  • Standard datasets:

    • Training set: 50 points

    • Validation set: 50 points

    • Test set: 500 points

  • Large datasets (digits and bbc-embeddings):

    • Training set: 100 points

    • Validation set: 100 points

    • Test set: 1000 points

• Evaluation Protocol:

  • Model retraining steps: 1000

  • Independent runs: 20

  • Metric: Test accuracy vs. selection size

18.6.0.1 Budget-500 protocol.

The split above is used for the standard RQ3 selection curves and the detailed small-budget selection table. The large-scale Budget-500 table in the main text uses a separate protocol with 500 training candidates for every dataset. Standard datasets use 50 validation and 500 test points, while digits and bbc-embeddings use 100 validation and 1000 test points. The reported Budget-500 value is the mean test accuracy over the top-\(k\) selection curve for \(k=1,\ldots,500\), rather than only the endpoint at \(k=500\).

18.6.0.2 DVRL training budget calibration.

Following OpenDataVal’s default, we use DVRL(rl_epochs=1000, rl_batch_size=32), which makes pred_model.fit() approximately \(1000\) times in the RL loop – matching the \(1000\)-retraining budget of the other sampling-based methods (InfluenceSubsample, DataBanzhaf, DataOob, BipartiteMatchingEvaluator, and AME via four bagging proportions of \(250\)). Each DVRL pred_model.fit() call uses a minibatch of \(32\) examples, intrinsic to its REINFORCE-style training.

18.7 LLM Fine-Tuning Data Selection (DATE-LM)↩︎

To assess whether our selection framework transfers to large-scale LLM fine-tuning, we evaluate on DATE-LM [37]. We refer to our adapted method as BipCov (Bipartite Coverage), which applies the core bipartite graph coverage framework from Section 5 with RAG-style embeddings suitable for instruction selection.

18.7.1 Experimental Setup↩︎

18.7.1.1 Task and Protocol.

DATE-LM (Table 3) studies single-task instruction fine-tuning: given a target evaluation task, methods select a training subset from a large instruction pool to maximize downstream task performance. We follow the official DATE-LM Table 3 protocol for direct comparison with published baselines.

18.7.1.2 Training Pool.

Following DATE-LM, we sample 200,000 instructions from Tulu 3 unfiltered [87] using seed 42. For multi-turn conversations we keep only the first user–assistant turn, consistent with the DATE-LM data pipeline. The pool contains diverse instruction-response pairs spanning general knowledge, reasoning, coding, and creative tasks.¹

18.7.1.3 Reference Set.

For each target task, we sample 100 prompt+label examples from the evaluation dataset using seed 42.² These reference examples guide task-aware data selection.

18.7.1.4 Selection Budget.

Each method produces a score vector over the 200k pool and selects the top 10,000 examples (5%) for fine-tuning.

18.7.1.5 Base Model and Fine-Tuning.

We fine-tune meta-llama/Llama-3.1-8B (base, not instruction-tuned) using LoRA [88] with the following hyperparameters:

• LoRA rank: 128, LoRA alpha: 512, LoRA dropout: 0.1

• Target modules: q_proj, k_proj, v_proj, o_proj³

• Learning rate: \(2 \times 10^{-5}\) with linear warmup for the first 3% of training steps, followed by cosine annealing to 0

• Effective batch size: 128 (micro batch 1 \(\times\) gradient accumulation 128, single device)

• Training epochs: 2 (approximately 156 optimization steps)

• Max sequence length: 2048 tokens (truncated)

• Precision: bf16 (full bf16, no mixed precision)

• Gradient clipping: none

• Loss masking: assistant-only (instruction tokens are masked via labels \(=-100\))

18.7.1.6 Evaluation Tasks.

We evaluate on three diverse benchmarks using official DATE-LM evaluation scripts:

• MMLU [89]: 14,042 questions across 57 subjects, evaluated with 0-shot accuracy.

• GSM8K [90]: 1,319 grade-school math problems, evaluated with 8-shot chain-of-thought exact match.

• BBH [91]: 6,511 questions across 27 challenging BIG-Bench subtasks, evaluated with 3-shot exact match.

18.7.2 BipCov Implementation Details↩︎

18.7.2.1 Adapting BipCov to DATE-LM.

DATE-LM exposes data selection methods through a per-example metric vector (metrics.npy) over the pool; the pipeline selects top-\(k\) by this score. To instantiate BipCov, we build a bipartite graph between pool instructions and the task reference set using cosine similarity in an embedding space.

18.7.2.2 Graph Construction.

We sparsify the bipartite graph by connecting each reference example to its top-\(L\) nearest pool examples. We fix \(L=200\) throughout all experiments, which provides sufficient coverage while keeping the graph sparse. This hyperparameter was chosen based on preliminary experiments showing stable performance for \(L \in [100, 500]\).

18.7.2.3 Greedy Selection.

We apply lazy greedy maximization of the maximum-coverage objective to generate a selection order up to \(k=10{,}000\). The algorithm maintains a set of covered reference examples and iteratively selects the pool example that covers the most uncovered references. When binary coverage saturates (i.e., all reference examples are covered before reaching budget \(k\)), we fill the remaining budget by ranking uncovered pool examples by their mean cosine similarity to the reference set. This fallback ensures a complete top-\(k\) ordering compatible with the DATE-LM pipeline while maintaining the coverage-first priority. In the ref-aligned Llama-3.1-8B last-token hidden-state score files used for Table 4, binary coverage saturated after selecting 2, 1, and 5 examples for MMLU, GSM8K, and BBH, respectively; the remaining positions up to 10,000 were filled by the mean-similarity fallback. Thus the DATE-LM results should be interpreted as coverage-prioritized, reference-aligned similarity selection rather than pure coverage across the entire 10k budget.

18.7.2.4 RAG-style Embeddings.

For computing bipartite edge weights, we explore both LLM internal representations and external retrieval encoders:

• LLM hidden states: Last-token or position-weighted mean pooled hidden states from Llama-3.1-8B, as used by Rep-Sim and RDS+ (4096 dimensions).

• Retrieval encoders: Dense retrieval models including BGE-large-v1.5 (1024 dim), E5-large-v2 (1024 dim), Qwen3-Emb-8B, GTE-Qwen2-7B, NV-Embed-v2, and GritLM-7B.

We treat each pool instruction as a “document” and each reference prompt as a “query”, applying model-specific formatting (e.g., query:/passage: prefixes for E5) when applicable, analogous to retrieval in RAG pipelines.

18.7.3 Baseline Methods↩︎

We compare against the following DATE-LM baselines:

• Random: Uniform random selection from the pool (DATE-LM reports average over 3 random seeds).

• BM25 [92]: Lexical matching between pool instructions and reference prompts.

• Rep-Sim: Cosine similarity using last-token hidden states from Llama-3.1-8B; each pool example is scored by its average similarity to reference examples.

• RDS+ [93]: Similar to Rep-Sim but uses position-weighted mean pooling over all token hidden states: \(\mathbf{e} = \sum_{i=1}^{L} w_i \mathbf{h}_i\) where \(w_i = i / \sum_{j=1}^{L} j\).

• Grad-Sim: Gradient similarity between pool examples and reference examples using a warmup LoRA checkpoint.

• LESS [94]: Learned embedding-based scoring using gradient features from a warmup checkpoint.

18.7.4 Computational Cost↩︎

Table 3 summarizes the computational requirements recorded from the synced DATE-LM GPU run logs. The dominant cost is embedding computation and downstream fine-tuning/evaluation; BipCov’s coverage-based scoring itself takes only seconds on CPU once embeddings are available.

18.7.5 Why Coverage Helps↩︎

Compared with average-similarity scoring (Rep-Sim, RDS+), BipCov encourages early diversity with respect to the reference distribution: each selected example is rewarded for covering previously uncovered reference prompts, reducing redundancy while maintaining task alignment via the similarity graph. Once all reference prompts are covered, the remaining budget is filled by the mean-similarity fallback described above.

Consider a scenario where the reference set contains questions about geography, mathematics, and history. Average-similarity methods may over-select examples similar to the most frequent reference type, while BipCov prioritizes balanced coverage across reference topics before adding additional high-similarity examples.

The embedding-backend ablations (Table 6) further suggest that stronger retrieval encoders provide more faithful semantic neighborhoods, which can translate into better downstream fine-tuning performance. Notably, Qwen3-Emb-8B achieves the highest average score (63.71%), suggesting that larger, task-aware embedding models may provide better guidance for instruction selection.

18.7.6 Results and Analysis↩︎

Table 4 reports mean \(\pm\) std over three fine-tuning seeds (42, 1337, 2025) for Random, RDS+, and our BipCov selection. The BipCov row uses the ref-aligned prompt+label reference construction with Llama-3.1-8B last-token hidden-state embeddings; the weighted-mean LLM embedding variant appears separately as an embedding ablation in Table 6. BipCov achieves the best average performance (63.89%) with a +1.01% improvement over RDS+ (62.88%), demonstrating consistent gains across different training seeds.

For completeness, we also reproduce the broader DATE-LM Table 3 baseline set under the same official pipeline (single fine-tuning seed 1337; Table 5). BipCov with BGE embeddings achieves the best average (63.56%), outperforming all reproduced baselines including gradient-based methods (Grad-Sim, LESS) that require additional warmup training.

Table 6 reports representation (embedding) ablations for BipCov. Key observations:

• Retrieval encoders outperform LLM hidden states: BGE (63.56%) and Qwen3-Emb-8B (63.71%) outperform weighted-mean LLM embeddings (62.89%), suggesting that models trained for semantic retrieval provide better similarity signals for coverage-based selection.

• Task-specific trade-offs: Different embeddings excel on different tasks. BGE achieves the best BBH score (67.14%), while Qwen3-Emb-8B leads on MMLU (62.50%) and GSM8K (63.00%). This suggests potential for task-adaptive embedding selection.

• Embedding dimension is not the bottleneck: GritLM-7B (7B parameters) underperforms BGE-large (335M parameters), indicating that embedding quality matters more than model size for this application.

19 RQ2 Experimental Validation of Curvature Impact↩︎

To empirically examine the theoretical guarantees established in Theorem 8 and the limitations described in Remark 17, we conduct controlled experiments that systematically vary data point substitutability as a qualitative proxy for utility curvature. Our experimental design uses message passing mechanisms to control the degree of within-class feature similarity, which affects the substitutability structure of the learned utility.

Our experimental setup consists of a three-class classification problem where we employ a graph-based message passing scheme that updates each point’s features by aggregating information from its within-class neighbors. The aggregation proportion increases from \(0.0\) to \(1.0\), systematically increasing substitutability, our proxy for curvature. When the proportion is small, points maintain distinctive features, corresponding to low substitutability. As the proportion increases, points within each class become increasingly similar through feature averaging, leading to high substitutability.

The experimental results are consistent with our theoretical analysis in three aspects. First, under low substitutability (proportion \(\leq 0.3\)), all methods achieve strong performance with BetaShapley obtaining a mean accuracy of \(0.706\), Banzhaf (\(0.720\)) and Shapley (\(0.738\)). This aligns with the \((1-c)^2\) approximation guarantee from Theorem 8 when the curvature proxy is small. Second, as substitutability increases (proportion \(\geq 0.5\)), we observe significant performance degradation across all methods, with mean accuracies dropping to approximately \(0.59\) at proportion \(1.0\). This deterioration is consistent with the quadratic decay in our theoretical bound as curvature approaches \(1\). Third, the convergence in performance between different methods at high substitutability is consistent with our analysis that all game-theoretic approaches face similar fundamental limitations under strong substitution effects.

These results are consistent with Theorem 8’s prediction that higher substitutability (which we use as a curvature proxy) worsens the performance of marginal-average, myopic value rankings, though we do not claim to directly estimate the true curvature \(c\) of the learned utility.

20 Algorithm for Computing Sequential Optimal Data Values↩︎

We present the complete algorithm for computing optimal data values through dynamic programming in Algorithm 6. The algorithm proceeds in two phases: (1) backward induction to compute the optimal value function and policy, and (2) forward traversal to derive data values from the optimal selection sequence. The algorithm’s first phase implements backward dynamic programming, computing the optimal value function \(V[s]\) and policy \(\sigma^*[s]\) for each state \(s\). The second phase constructs the optimal selection sequence and assigns values inversely proportional to selection order. While this algorithm yields optimal values, its computational complexity is exponential in the dataset size due to the need to evaluate all possible subset states.

Convention. The array \(V[\cdot]\) in Algorithm 6 (square brackets) stores a shifted form of the value-to-go \(V(\cdot)\) in Equation 1 (parentheses): its backward recursion maintains \(V[s] = U(s) + V(s)\), folding the current prefix utility \(U(s)\) into the stored value, with boundary \(V[\mathcal{D}] = U(\mathcal{D})\). This is purely a bookkeeping choice for a compact recursion: because \(V[s\cup\{a\}] = U(s\cup\{a\}) + V(s\cup\{a\})\) is exactly the quantity maximized inside Equation 1 , the selected action \(\sigma^\ast[s] = \arg\max_{a\in\mathcal{D}\setminus s} V[s\cup\{a\}]\) coincides with the optimal policy \(\arg\max_{a}\{U(s\cup\{a\}) + V(s\cup\{a\})\}\), so Algorithm 6 yields exactly the same optimal permutation \(\pi^\ast\) and data values \(v^\ast\).

21 Detailed Analysis of RQ1 Results↩︎

Building upon the performance gaps identified in Section 7.1, here we provide a detailed analysis of the selection curves to understand how existing methods compare with optimal sequential selection across different data budgets. Several key findings emerge:

First, the optimal selection DynamicProgramming consistently outperforms all existing methods across datasets, with particularly pronounced gaps in early selection stages (\(k \leq 5\)). This indicates that current approaches significantly underperform in identifying the most valuable initial samples. Second, the performance gap varies notably across datasets, suggesting dataset-specific challenges. The gap is particularly prominent in structured datasets like bbc-embeddings and nomao, where optimal selection demonstrates steep initial performance improvements that existing methods fail to match. Third, existing methods exhibit varying patterns of suboptimality. Game-theoretic approaches (DataShap, BetaShap, Banzhaf) tend to perform similarly to each other but consistently fall short of DynamicProgramming. Learning-based methods (DVRL, AME) and influence-based approaches show competitive performance in some cases but lack consistency across datasets. Notably, all methods cannot match the optimal strategy’s ability to achieve both rapid initial improvement and sustained performance gains.

These detailed observations complement the quantitative performance gaps reported in Section 7.1, providing deeper insights into how different data valuation approaches behave across varying selection budgets.

22 Detailed Analysis of Data Selection Performance↩︎

To quantify the selection performance improvements achieved by our bipartite graph-based approach Bipartite, we present detailed numerical results comparing against baseline methods. For each dataset and method, we compute the mean test accuracy and standard deviation across 20 independent runs. The experimental protocol follows Section 7.3.

The results reinforce our observations from the selection curves in Section 7.3. Our method Bipartite achieves the highest average accuracy, ranking first on seven of the eight datasets, with particularly substantial improvements on complex datasets like bbc-embeddings (0.878 accuracy, compared to 0.809 for the best baseline) and digits (0.764 accuracy versus 0.680 for the next best method). Even on datasets where baseline methods perform relatively well, such as nomao and MiniBooNE, our approach Bipartite still maintains a clear performance advantage while demonstrating more stable behavior across different runs. These comprehensive results validate our theoretical analysis that the bipartite graph approximation effectively preserves the essential structure of the utility function while enabling efficient computation.

23 Future Work↩︎

We outline several promising research directions that could extend our framework.

23.1 Non-myopic Planning with Expressive Models↩︎

While our current work focuses on myopic planning with structured bipartite models, an interesting direction would be exploring non-myopic planning strategies with more expressive surrogate models like neural networks, which have already been adopted in data utility learning [42]. Such models might better approximate the ground truth utility but lack the theoretical guarantees that make myopic planning optimal for linear surrogates. This presents an interesting trade-off between model expressiveness and planning complexity that warrants further investigation. Techniques from approximate dynamic programming, such as lookahead policies and rollout algorithms [14], could potentially bridge this gap by enabling limited-horizon planning with learned value function approximations.

23.2 Theoretical Extensions↩︎

Several theoretical extensions could broaden the applicability of our framework:

23.2.0.1 Weak Submodularity.

Extending our analysis beyond monotone submodularity to weaker notions like weak submodularity [69] could better capture real-world utility functions that only approximately satisfy submodular properties. Many practical machine learning objectives exhibit diminishing returns behavior that is close to, but not exactly, submodular.

23.2.0.2 Stochastic Selection.

Considering distributions over sequences rather than deterministic selections could lead to more robust selection strategies, particularly when utility estimates are uncertain. This connects to recent work on stochastic submodular optimization and could provide confidence intervals for selection quality.

23.2.0.3 Beyond Curvature.

While curvature provides a useful characterization of approximation quality degradation, other structural properties of utility functions (such as noise stability or smoothness) might yield tighter or complementary bounds for specific application domains.

23.3 Algorithmic Improvements↩︎

The practical implementation of our framework could be enhanced through several algorithmic improvements:

23.3.0.1 Alternative Distance Metrics.

Investigating different similarity measures for bipartite graph construction beyond Euclidean distance could better capture domain-specific relationships between data points. For instance, learned embeddings, kernel-based similarities, or task-specific distance functions might improve coverage-utility alignment in specialized domains.

23.3.0.2 Efficient Threshold Search.

Implementing more sophisticated optimization techniques like Bayesian optimization or gradient-free methods could improve the efficiency of threshold selection in our bipartite graph construction, particularly for high-dimensional feature spaces where the optimal threshold varies significantly.

23.3.0.3 Preprocessing Strategies.

Developing techniques to handle redundant data points through clustering or dimensionality reduction could address cases where high curvature limits theoretical guarantees. Such preprocessing could reduce effective curvature while preserving the essential structure of the selection problem.

23.3.0.4 Scalability.

For very large datasets, approximate nearest neighbor search and graph sparsification techniques could further improve computational efficiency while maintaining selection quality, enabling application to million-scale data pools.

References↩︎