{"id":"fceb1a4a-67ad-4564-9048-60b4d61179a4","arxiv_id":"2502.04554","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"Data selection is reframed as dynamic programming over an MDP, existing data values are shown to be myopic linear approximations, and a bipartite coverage surrogate is proposed, but its exact optimality guarantee is unsound.","lead":"This paper recasts data selection as a sequential decision problem, interprets existing data value methods like Data Shapley as myopic approximations of that problem, and proposes a bipartite graph surrogate for scalable selection. A generalist reader might care because data selection is central to efficient model training, yet the paper's headline guarantee relies on a false optimality claim.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem G.3 is false: greedy coverage selection is not optimal for the sum-of-prefix-utilities objective; the bipartite surrogate's key guarantee is unsupported.","rationale":"The reader's weakest_assumption identifies exactly the most load-bearing concern. The paper's central contribution is a bipartite graph surrogate that supposedly preserves theoretical guarantees for optimal sequential selection. That guarantee is Theorem G.3, which asserts that greedy selection is exactly optimal for the sum-of-prefix-utilities objective under coverage functions. This assertion is false because the objective is the minimum sum set cover problem, which is NP-hard and for which greedy is only a 4-approximation. The proof's exchange argument fails because it treats adjacent swaps as if they only exchange two marginal gains, but in a coverage setting moving an element earlier changes the first-cover time of every covered validation point, not just the swapped pair. Submodularity alone cannot make greedy optimal for MSSC. This is a clear correctness error in the paper's main algorithmic claim, not a stylistic or presentation issue. The MDP reformulation and curvature analysis are interesting, but they do not rescue the surrogate's theoretical foundation. The abstract also advertises large-scale LLM experiments that do not appear in the text, and Table 1's 'Average' row is inconsistent with the method always winning, but the false theorem is sufficient to warrant rejection. Therefore the reader's REJECT verdict remains appropriate, and I agree with the identified weakest assumption.","tokens_in":179,"tokens_out":4155,"duration_ms":58415,"concrete_test":"Run a brute-force search over all permutations for a small random coverage instance (e.g., n=4 training points, m=5 validation points, arbitrary coverage sets). Compute the prefix-sum objective sum_{k=1}^n |\\cup_{j=1}^k S_{\\pi(j)}| for the greedy ordering and for the optimal permutation. If greedy is not strictly optimal for any instance (or use a known MSSC counterexample from Feige et al. 2004), then Theorem G.3 is falsified. Also verify the swap step of the exchange argument on that counterexample to locate the error.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The sequential objective (Eq. 1) for the coverage surrogate \\hat{U} in Definition G.1 is sum_{k=1}^n |\\cup_{j=1}^k S_{\\pi(j)}|. This is equivalent, up to a constant, to minimizing the sum of first-cover times over validation points, i.e., the Minimum Sum Set Cover (MSSC) problem, which is NP-hard and for which greedy achieves only a 4-approximation. Therefore Theorem G.3's claim that greedy is exactly optimal for any coverage function is false. The exchange argument in §G.4 is invalid: swapping two adjacent elements changes the coverage times of many later elements, and submodularity alone does not imply that such a swap preserves the prefix-sum objective. Because the advertised 'provable guarantees' for the bipartite surrogate rest entirely on Theorem G.3, the main algorithmic contribution loses its theoretical foundation. The empirical results may stand alone, but the abstract's claim that the surrogate 'ensures greedy selection is still optimal when the surrogate utility is correctly specified and learned' is unsupported and in general false.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper reformulates data selection—ranking data by scores and then selecting prefixes of that ranking—as a finite-horizon deterministic MDP whose objective is the sum (equivalently average) of utilities of all prefixes. It interprets game-theoretic data values (Data Shapley, Beta Shapley, Data Banzhaf) as myopic linear reward approximations in an ADP scheme, proves that all semivalues are optimal under linear utility and enjoy a (1-c)^2 approximation under monotone submodular utilities with curvature c, and proposes a learned bipartite coverage surrogate for which greedy selection is claimed to be exactly optimal. The experiments compare the proposed surrogate against a large set of baselines on eight OpenML datasets.","tokens_in":23717,"tokens_out":11383,"duration_ms":112286,"significance":"The unifying MDP/ADP perspective is conceptually attractive and may be of interest to the data-valuation community. Theorem 4.3 and Theorem 4.6 appear correct and give a clean, testable explanation of when linear/myopic value rankings should degrade. The paper also provides reproducible code and a careful evaluation protocol. However, the headline guarantee of the proposed bipartite surrogate—that greedy selection is optimal under a correctly specified coverage surrogate—is false, because the corresponding optimization problem is minimum sum set cover, which is NP-hard; this invalidates the main algorithmic contribution as advertised.","major_comments":[{"comment":"Theorem G.3 asserts that the greedy sequence is exactly optimal for the sum-of-prefix-utilities objective of the coverage surrogate. This objective is equivalent, up to an additive constant, to minimizing the sum of first-cover times over validation points, i.e., the minimum sum set cover problem, which is NP-hard and for which greedy is known to achieve only a 4-approximation. The exchange argument in §G.4 is therefore invalid: swapping two adjacent elements can change the first-cover times of many later-covered validation points, and submodularity of the coverage function does not imply that an inversion-free sequence maximizes the prefix-sum objective. Since Section 5.3 and the abstract rely on Theorem G.3 for the claim that greedy selection is optimal when the surrogate is correctly specified and learned, the advertised provable guarantees of the bipartite method are unsupported.","section":"Appendix G, Theorem G.3"},{"comment":"The claimed equivalence between game-theoretic data values and the proposed ADP solution rests on Lemma C.1, which states that constrained weighted least-squares coefficients converge to the semivalue. This lemma is not proved: the displayed constraint 'Û(S)θ_i = U(D) − U(∅)' is not a well-formed constraint on θ, and the proof simply asserts that the expectation converges to the exact marginal contributions. A valid derivation (or a precise citation to the projection/least-squares characterization of semivalues) is needed; without it, Theorem 4.1's statement that Data Shapley, Beta Shapley, and Data Banzhaf are exactly recovered as myopic linear approximations remains unestablished.","section":"Appendix C, Lemma C.1 and Theorem 4.1"}],"minor_comments":[{"comment":"The abstract states that experiments include large-scale LLM fine-tuning data selection, but Section 7 and Appendix H describe only eight OpenML datasets with logistic regression; no LLM fine-tuning experiments are reported.","section":"Abstract and Section 7"},{"comment":"The 'Average' and 'Std Dev' rows of Table 1 appear to be miscomputed or misaligned: for example, DataShap is listed with average 0.043, while its nine per-dataset means are all near 0.6–0.8.","section":"Table 1"},{"comment":"Remark 4.7 misspells 'performs' as 'preforms'.","section":"Remark 4.7"},{"comment":"Appendix E refers to 'Section 4.4 of the main paper', but the relevant discussion is in Section 4.1.1.","section":"Appendix E"},{"comment":"Section H.5 states that DynamicProgramming is run on training sets of 20 points, but the paper does not describe how the 2^20 subset utilities are obtained under the 1000-retraining budget; this should be clarified.","section":"Appendix H.5"}],"recommendation":"reject","confidential_remarks":"To the editor: The false optimality claim in Theorem G.3 is the decisive issue; it invalidates the paper's central advertised guarantee for the bipartite surrogate. A revised manuscript could potentially be viable if it replaced the optimality claim with the standard 4-approximation of greedy for minimum sum set cover and repositioned the contribution, but that would be a substantial rewrite rather than a local correction."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe genuinely new thing is the framing: data selection as a finite-horizon deterministic MDP, with Data Shapley, Banzhaf, and beta values reinterpreted as myopic linear reward approximations in approximate dynamic programming. That is a useful way to organize the data valuation literature, and the paper deserves credit for it. The curvature analysis for semivalues (Theorem 4.6) is mostly a standard (1-c)^2 greedy-type bound restated for semivalues; it is correct, but less novel than the authors suggest.\n\nThe soft spots are load-bearing. Theorem G.3 claims greedy selection is exactly optimal for the prefix-sum coverage objective. That is false. The objective for the coverage surrogate is, up to constants, the minimum sum set cover problem, which is NP-hard and for which greedy only gives a 4-approximation. The exchange argument in G.4 does not handle how an adjacent swap changes first-cover times for many later validation points; submodularity alone does not imply the claimed optimality. So the \"provable guarantees\" for the proposed bipartite surrogate sit on an invalid proof. The abstract also advertises large-scale LLM fine-tuning experiments that do not appear in the text; the experiments use 20-50 training points. Table 1's average and std rows are garbled (the average row is not an average of the means above it), and the claim that Bipartite wins on every dataset is contradicted by 2dplanes, where BetaShapley's mean is 0.747 versus 0.745. Lemma C.1, the weighted least squares recovery of semivalues, is asserted rather than derived.\n\nOn the positive side, Theorem 4.3 on linear utility optimality is sound, and the ADP reinterpretation is a real conceptual contribution. The errors are concentrated in the surrogate theory and in presentation, not in the core reframing. But the paper as submitted cannot be accepted: the main algorithmic guarantee is unsupported, and the empirical claims outrun what was actually run.\n\nWould I send it to referees? Yes. The MDP/ADP framework is worth refereeing, and the false theorem is fixable by replacing exact optimality with an honest approximation guarantee. I would not cite the surrogate guarantee as it stands, but I would consider citing the framing. It would also make a good reading group case study in how an exchange argument can fail.","headline":"Smart MDP/ADP framing of data valuation, but the surrogate's exact-optimality theorem is false and the advertised LLM experiments are missing.","tokens_in":24277,"tokens_out":4013,"would_cite":true,"duration_ms":40674,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Data values for selection are approximate solutions to a sequential decision problem, and the gap between a value-based ranking and the optimal sequence is governed by utility curvature.","keywords":["data valuation","data selection","sequential decision-making","dynamic programming","approximate dynamic programming","submodularity","curvature","bipartite coverage model"],"falsifier":"Take a small coverage instance with three training points and two validation points arranged so that the largest first-step coverage blocks later coverage, enumerate all six selection orders, and compare $\\sum_{k=1}^n \\hat U(S_k)$ for greedy versus the best order; a better non-greedy order would refute the appendix's exact-optimality claim for the surrogate.","tokens_in":23282,"feed_emoji":"🎯","tokens_out":12201,"duration_ms":115299,"temperature":0.7,"pith_summary":"Data selection is usually treated as a scoring problem: assign each point a value and add points in descending order. This paper argues that the process is really a sequential decision problem, where the objective is the average utility over all prefixes of the chosen order, and the optimal order comes from dynamic programming. From that vantage point, existing game-theoretic values such as Data Shapley, Beta Shapley, and Data Banzhaf become special cases of a myopic linear approximation to the dynamic program. The paper then characterizes when those approximations break down: for monotone submodular utilities with curvature $c$, the value-ranked selection has only a $(1-c)^2$ guarantee, which collapses as data becomes substitutable. To make the ideal tractable, it proposes a bipartite coverage surrogate that supports greedy selection and, in the reported experiments, reaches a given accuracy with far fewer selected samples than the baselines.","feed_headline":"Data values are myopic shortcuts to an optimal selection sequence","feed_subtitle":"Reformulating selection as dynamic programming explains when ranking by Shapley-style scores fails.","key_machinery":"The machinery that carries the argument is the reformulation of data selection as a finite-horizon deterministic MDP, together with the Bellman equation $V(s)=U(s)+\\max_{a\\in D\\setminus s}V(s\\cup\\{a\\})$. States are selected subsets, actions are the next training point, transitions are $s_{t+1}=s_t\\cup\\{a_t\\}$, and rewards are the utility $U(s_t)$, so that the sum of rewards equals the selection-curve objective. Existing data values enter as a specific ADP instance: a linear reward surrogate $\\hat U(S)=\\sum_{i\\in S}\\theta_i$ estimated by weighted least squares, paired with the myopic decision rule $\\pi(s)=\\arg\\max_{a\\notin s}\\theta_a$; the weights in the least-squares fit select which game-theoretic value is recovered. The analysis object that explains performance is the curvature $c$ of a monotone submodular utility, which upper-bounds how much marginal contributions shrink, and the paper's guarantee is the $(1-c)^2$ factor. For the practical surrogate, the mechanism is a weighted bipartite graph from training points to validation points, with the coverage utility $\\hat U(S)=|\\cup_{i\\in S}S_i|$, whose monotonicity and submodularity justify greedy maximum-coverage selection.","core_discovery":"The paper's central claim is that data values for selection are not autonomous scores but encodings of an optimal sequential policy. Formally, it models selection as a deterministic MDP whose state is the current selected set, whose action is the next point to add, and whose reward at step $t$ is the utility $U(s_t)$; the objective is $\\max_\\pi \\frac{1}{|D|}\\sum_{k=1}^{|D|}U(S_k)$ with nested sets. The exact solution is the Bellman recursion $V(s)=U(s)+\\max_{a\\in D\\setminus s}V(s\\cup\\{a\\})$. The paper claims that every game-theoretic valuation can be reproduced as an ADP solution that uses a linear surrogate $\\hat U(S)=\\sum_{i\\in S}\\theta_i$ plus a myopic policy that always picks the largest $\\theta_i$, with method-specific weights chosen by least squares. It then proves a $(1-c)^2$ approximation for monotone submodular utilities with curvature $c$, showing why high substitutability destroys the ranking's value. Finally, it proposes a bipartite coverage model $\\hat U(S)=|\\cup_{i\\in S}S_i|$ over validation points, claims greedy maximum coverage is optimal for that surrogate, and reports experiments on eight datasets where the bipartite method reaches target accuracy with far fewer samples than the baselines.","pith_inferences":["If the MDP view is accepted, the gap between a value method's ranking and the DP-optimal sequence can serve as a model-free diagnostic for when data values mislead selection; the paper does not build this diagnostic, but its experiments suggest it would flag high-curvature datasets.","The $(1-c)^2$ bound points to a practical pre-check: estimate utility curvature before choosing a valuation method, and prefer coverage-based or non-myopic selection when curvature is high; the paper validates the trend but does not propose such a rule.","The surrogate's exact-optimality claim may need to be relaxed to a constant-factor approximation, since the sum-of-prefix coverage objective is computationally hard in general; the reported selection-curve gains would still support using the method.","A natural extension is to replace the uniform distribution over budgets with any user-supplied distribution, which the DP formulation can accommodate and which would yield data values tuned to the budgets that actually matter."],"forward_implications":["Under linear utility, every semi-value method produces the same selection sequence, and that sequence is optimal for the sequential objective.","For monotone submodular utilities of curvature $c$, every semi-value ranking satisfies $U(G_k)\\ge (1-c)^2 U(\\mathrm{OPT}_k)$ for each prefix, and the same bound holds for the summed selection objective.","As $c$ approaches 1, the guarantee degrades quadratically, so high data substitutability—not dataset size or noise—is what causes game-theoretic values to lose their advantage.","Optimal data values are naturally defined by the selection step $v^*(i)=n-t^*(i)$ in the optimal trajectory, rather than by aggregating marginal rewards.","A learned bipartite coverage model turns selection into greedy maximum coverage, avoiding model retraining, and the reported curves show it reaching target accuracy with substantially fewer samples."],"supporting_citations":[{"why":"Supplies the dynamic-programming optimality equation that defines the optimal selection sequence.","marker":"Bellman, 1966"},{"why":"Introduces Data Shapley, the main existing value method the paper reinterprets as a myopic linear ADP solution.","marker":"Ghorbani & Zou, 2019"},{"why":"Defines Beta Shapley and the semi-value family whose ranking behavior is unified under Theorem 4.1.","marker":"Kwon & Zou, 2021"},{"why":"Defines Data Banzhaf, another semi-value instance covered by the same unification.","marker":"Wang & Jia, 2023"},{"why":"It supplies the myopic reward-function-approximation decision rule used to characterize data values as ADP solutions.","marker":"Powell, 2016"},{"why":"Reports the empirical observation that Data Shapley works well on heterogeneous data, which the paper ties to low curvature.","marker":"Wang et al., 2024b"}],"fun_headline_variants":["Shapley values are myopic shortcuts to optimal selection","Data selection as a dynamic program: Shapley is a myopic shortcut","Why data Shapley fails: it ignores the sequential nature of selection","Unifying data valuation and selection via sequential decision-making"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The bipartite surrogate's theoretical guarantee depends on greedy selection being exactly optimal for the sum-of-prefix coverage objective, a premise asserted by an exchange argument that does not account for how early choices constrain later coverage.","fun_headline_variants_meta":{"raw":{"variants":["Shapley values are myopic shortcuts to optimal selection","Data selection as a dynamic program: Shapley is a myopic shortcut","Why data Shapley fails: it ignores the sequential nature of selection","Unifying data valuation and selection via sequential decision-making"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001465,"raw_usage":{"total_tokens":5919,"prompt_tokens":994,"completion_tokens":4925,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":610,"completion_tokens_details":{"reasoning_tokens":4852}},"tokens_in":610,"tokens_out":4925,"duration_ms":35263,"temperature":1.0,"reasoning_tokens":4852,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T22:22:04.450806+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small coverage instance with three training points and two validation points arranged so that the largest first-step coverage blocks later coverage, enumerate all six selection orders, and compare $\\sum_{k=1}^n \\hat U(S_k)$ for greedy versus the best order; a better non-greedy order would refute the appendix's exact-optimality claim for the surrogate.","supporting_citations":[],"review_version":1}