acceptodds
Under review as a conference paper at ICLR 2027

FastDV: Scalable Model-Agnostic Data Valuation via Density Ratio Leave-One-Out

Abstract

Leave-One-Out (LOO) data valuation (DV) quantifies the contribution of an individual sample through the finite utility change induced by its removal, providing useful guidance for data pruning, procurement, and selection. While model-agnostic DV avoids repeated model retraining by evaluating distributional utilities, existing methods typically rely on sensitivity, influence, or hierarchical approximations rather than explicit finite deletion. Moreover, most DV methods are developed for centralized settings, leaving independently computed values across multiple data holders generally incomparable. In this work, we propose FastDV, a scalable model-agnostic valuation framework. Specifically, we first derive an additive-statistic formulation that decomposes target set dependence into sample-wise additive statistics, making individual deletions analytically decomposable and distributed data partitions naturally composable. Guided by this principle, FastDV defines sample value through a Pearson-divergence-based density-ratio utility and achieves efficient LOO valuation through exact rank-one updates. Leveraging the partition composability of the above formulation, FastDV further extends to multi-party global valuation and produces globally comparable values without pooling raw client data. Extensive experiments on typical valuation tasks and data marketplaces demonstrate the effectiveness and scalability of FastDV. Notably, FastDV achieves up to 15.7 speedup over the fastest baseline on million-scale datasets.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Data valuation, federated learning, data selection

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_4sboOpenReview ↗
Rating
4(+2)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Fastdv values a sample by the change in a regularized density ratio utility after deletion. This gives leave one out scores without repeatedly training a downstream model. With the support set, kernel anchors and hyper-parameters fixed, all deletions reuse a shared matrix inverse through exact rank one updates. The real-world value is that clients can combine their local statistics to obtain a global ranking without pooling raw data.

Critical strengths

(1) It is a very good point that the deletion formula accounts for the change from N to N -1 without changing the coefficient lambda. With the kernel map and support statistic fixed, the same matrix inverse can be then reused across different deletions.

(2) Also it is a plus that raw client data can stay local. Count weighted statistics give the centralized scores with the same kernel map, support statistic and regularization.

(3) Some experiment designs are solid. For example, both removal directions are tested, and the runtime comparison includes anchor construction. In the Products removal test in Fig. 5, 200 anchors gives accuracy similar to 5k anchors. It also takes less valuation time.

Critical weaknesses

(1) In the Fig.4, authors compare methods with different utilities and pools clean/noisy samples. However, the correlation of ~0.8 with model based loo may partly come from separating those groups. The result actually right now does not well show the separate benefit of exact deletion.

(2) In the Table 4, the improvement may include better client allocation. There is a confounding factor there.

(3) The label free score avoids target labels, but sigma/lambda use support set validation. I would suggest that for the comparison to be clear, it would be good to give the validation objective and label access for Fastdv and the baselines.

Questions for authors

please see weakness part.

4 comments

We sincerely thank the reviewer for the careful assessment of our work, particularly the recognition of our exact deletion formulation, efficient shared-inverse computation, and distributed valuation without sharing raw client data. Below, we address your concerns point by point.

W1: Thanks for your suggestion. Following your suggestion and that of Reviewer eFU3, we extend the correlation analysis in Fig. 4. Specifically, we increase the sample size from 200 to 1,000 and separately evaluate clean and noisy samples to examine whether the overall correlation is primarily driven by group separation.

As shown in Table R1, FastDV consistently achieves the highest Spearman correlations, reaching 0.80 and 0.69 for clean and noisy samples, respectively. These results indicate that FastDV's higher overall correlation is not solely driven by clean/noisy group separation, but also reflects meaningful within-group ranking agreement.

Moreover, we provide additional visualizations in Appendix A.5.3 and highlighted them in blue to offer a more intuitive illustration.

Table R1LAVASAVAKairosFastDV
Clean0.610.560.650.80
Noisy0.620.460.200.69
Overall0.720.640.730.85

W2: We emphasize that adaptive cross-client data allocation is a unique advantage of FastDV. By leveraging the partition composability of additive statistics, FastDV recovers centralized-equivalent sample values across clients without pooling raw data (Corollary 3.2). This enables global ranking and selection across distributed clients, which is one of our core contributions and was intentionally highlighted in the original experiments.

To provide a more controlled comparison, following your suggestion and that of Reviewer eFU3, we additionally introduce FastDV_local, which uses the same globally computed FastDV scores but removes the lowest-valued 40% of samples within each client, following the identical selection protocol as the baselines. The results are reported in Tables R4 and R5. Notably, FastDV_local outperforms Kairos in seven of the eight settings, demonstrating competitive valuation effectiveness even under identical per-client selection budgets. These results indicate that FastDV's effectiveness is not solely attributable to better client allocation, while global selection provides additional benefits. We will incorporate these additional results into the revised manuscript.

Table R4 (Arxiv)KairosFastDV_localFastDV
FedAVG64.21±0.6666.59±0.8566.71±0.52
FedProx63.85±0.7464.97±0.6665.84±0.48
Scaffold60.95±1.6661.44±1.6761.20±1.71
FedDC62.59±1.0263.51±0.8463.93±1.05
Table R5 (Wiki)KairosFastDV_localFastDV
FedAVG71.05±0.1271.69±0.6671.84±0.37
FedProx71.09±0.1171.75±0.5271.88±0.33
Scaffold62.00±0.3860.39±0.4860.73±0.34
FedDC48.40±1.4648.57±1.1448.76±1.10

W3: We thank the reviewer for this helpful suggestion. Regarding hyperparameter selection, FastDV builds upon uLSIF, which provides an established selection strategy based on the least-squares density-ratio estimation loss. Accordingly, the kernel bandwidth σ\sigma and regularization coefficient λ\lambda can be selected using only target and support features, without accessing labels from either set. The selected hyperparameters remain fixed throughout valuation. Thus, FastDV follows the same label-access restrictions as the baselines, with neither labels used before the completion of valuation.

To ensure a transparent comparison, we summarize the label-access protocols in Table R6. All methods perform valuation without accessing target or support labels. Only after valuation and sample selection are the selected target samples labeled for downstream training, while support labels are used for downstream validation. These clarifications will be incorporated into the revised manuscript.

Table R6ValuationValidation
Target LabelsSupport LabelsSupport FeaturesTarget LabelsSupport Labels
LAVANoNoYesYesYes
SAVANoNoYesYesYes
KairosNoNoYesYesYes
FastDVNoNoYesYesYes

Dear Reviewer 4sbo,

Thank you for your valuable insights and the time spent reviewing our work, especially during this busy period. We greatly appreciate it.

As we near the final day of the discussion period, we wanted to check in and see if our responses have addressed your concerns. We welcome your further queries and suggestions and are ready to provide any additional information or clarification you might need.

We understand that reviewing is a time-consuming task and greatly appreciate your commitment to advancing academic discourse. Our team is dedicated to improving our work based on your feedback, believing it will enhance our contribution to the field.

Thank you once again for your guidance and support.

Best regards,
The Authors

I thank authors for their response which address most of my concerns. Therefore, I have raised my score to accept accordingly.

We are very pleased to hear that our rebuttal clarified your concerns. Thank you for your generous time and invaluable support throughout this process.

Reviewer_eFU3OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents FastDV, a model-agnostic method for data valuation that measures each individual observation's contribution to how well the dataset as a whole fits a reference distribution. The contribution of an observation is defined as the change in an empirical utility (derived from a regularised density ratio estimator) when that observation is removed. By expressing the utility in terms of additive kernel-based statistics, the authors show that leave-one-out contributions to the utility can be computed exactly for their proposed empirical utility via rank-one matrix updates, without re-solving the estimation problem each time. The same framework applies in a distributed setting where various data holders compute statistics and then aggregate them to recover the centralized scores without sharing raw data.

Critical strengths
  1. FastDV computes exact leave-one-out scores for its empirical utility at a low computational cost. The experiments confirm speedups over existing methods.
  2. The distributed formulation guarantees equivalence with centralized valuation without sharing raw data. The data procurement experiments show the benefit of globally comparable scores.
Critical weaknesses
  1. The link between FastDV scores and model-based leave-one-out values remains mostly empirical. Proposition 3.1 bounds prediction risk using Pearson divergence, but does not establish that the two methods rank observations similarly. Figure 4 reports a promising Spearman correlation of 0.80, although this comparison is limited to 200 CIFAR-10 observations. A broader evaluation would help establish when FastDV scores reflect the effect of removing observations on model performance.
  2. In the federated learning experiments, FastDV selects the top 60% of observations globally, whereas the baselines select the top 60% within each client. FastDV can therefore allocate more of the selection budget to clients with higher-valued data. The observed performance gains may thus result from better valuation scores, a better distribution of selected observations across clients, or both. Since these two effects are not evaluated separately, it is unclear how much each contributes to the improvement. Comparing global and per-client selection using the same FastDV scores would help clarify this distinction
Questions for authors
  1. Does the correlation reported in Figure 4 hold for larger datasets or different downstream models? This would help assess whether FastDV consistently identifies observations that matter for predictive performance.
  2. Could you evaluate FastDV using its globally computed scores but selecting the top 60% of observations within each client, as done for the baselines? Comparing this with the current global selection strategy would help determine how much of the performance gain comes from allocating the selection budget differently across clients.
3 comments

We appreciate the reviewer's positive evaluation of our work, particularly the recognition of FastDV's efficient exact LOO computation, centralized-equivalent distributed valuation, and effectiveness in data procurement. In what follows, we provide point-by-point responses to your concerns and questions.

W1/Q1: We clarify that FastDV does not claim exact ranking equivalence with model-based LOO, which is also a common challenge for existing model-agnostic valuation methods (e.g., LAVA, SAVA, and Kairos), as discussed in Appendix A.6. However, FastDV differs from these methods by providing a risk-based theoretical justification for its Pearson-divergence-based valuation principle. Specifically, Proposition 3.1 establishes a connection between Pearson divergence and downstream prediction risk, while the higher Spearman correlation observed in Fig. 4 provides complementary empirical evidence of FastDV's agreement with model-based LOO. Since evaluating model-based LOO requires N+1N+1 model training runs for NN samples, our original experiment was conducted on 200 samples.

Following your suggestion and that of Reviewer 4sbo, we extend the Correlation with Model-based LOO experiments in two aspects: (i) To assess FastDV's generalizability across downstream models, we additionally compute model-based LOO scores using MobileNetV3-Small [1]. (ii) We increase the sample size from 200 to 1,000 and separately report Spearman correlations for clean, noisy, and overall samples. The results are presented in Tables R1–R2.

Notably, FastDV consistently achieves the highest Spearman correlation with model-based LOO across all downstream models. Although the absolute correlations vary across downstream models, FastDV consistently maintains its relative advantage, demonstrating its generalizability across different learning architectures. Furthermore, the clean/noisy subgroup results confirm that this agreement is not solely driven by group separation. These findings provide stronger empirical evidence that FastDV can consistently identify samples relevant to downstream predictive performance.

Furthermore, we provide additional visualizations in Appendix A.5.3 and highlighted them in blue.

Table R1 (ResNet50)LAVASAVAKairosFastDV
Clean0.610.560.650.80
Noisy0.620.460.200.69
Overall0.720.640.730.85
Table R2 (MobileNetV3-Small)LAVASAVAKairosFastDV
Clean0.430.440.400.51
Noisy0.360.420.200.49
Overall0.550.550.580.64

W2/Q2: We thank the reviewer for this insightful observation. Indeed, leveraging the partition composability of additive statistics, FastDV achieves centralized-equivalent global valuation through aggregated client statistics. This enables samples across different clients to be ranked under a common reference, allowing the selection of the global top 60% samples. Such globally comparable sample-level valuation and the resulting cross-client selection capability constitute one of FastDV's core contributions.

Inspired by your suggestion, we additionally introduce FastDV_local, which uses exactly the same globally computed FastDV scores but removes the lowest-valued 40% of samples within each client, following the same selection protocol as the baselines. This controlled comparison allows us to distinguish valuation effectiveness under fixed client budgets from the additional benefit of global budget allocation.

As shown in Tables R3 and R4, FastDV_local remains highly competitive even under identical per-client selection budgets, outperforming Kairos in seven of the eight settings. These results demonstrate that FastDV's effectiveness is not solely attributable to cross-client budget allocation, while its globally comparable scores enable additional gains through flexible global selection.

Table R3 (Arxiv)KairosFastDV_localFastDV
FedAVG64.21±0.6666.59±0.8566.71±0.52
FedProx63.85±0.7464.97±0.6665.84±0.48
Scaffold60.95±1.6661.44±1.6761.20±1.71
FedDC62.59±1.0263.51±0.8463.93±1.05
Table R4 (Wiki)KairosFastDV_localFastDV
FedAVG71.05±0.1271.69±0.6671.84±0.37
FedProx71.09±0.1171.75±0.5271.88±0.33
Scaffold62.00±0.3860.39±0.4860.73±0.34
FedDC48.40±1.4648.57±1.1448.76±1.10

[1] Searching for MobileNetV3. ICCV, 2019.

Thank you for the detailed response and the additional experiments. I encourage the authors to include these new analyses in the revised manuscript. My concerns have been adequately addressed, and I maintain my score.

We are truly pleased to have been able to address the concerns you raised. We greatly value your time and attention to our rebuttal. We will incorporate the relevant content into our revised manuscript. Your support is invaluable in this process.

Reviewer_YXhSOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes FastDV, a method for valuing individual samples through changes in a regularized density-ratio utility relative to a reference distribution. With the kernel dictionary and hyperparameters fixed, it represents the target dataset through a second-moment matrix and computes finite-deletion scores using a shared inverse and rank-one corrections. The resulting formulation supports exact empirical deletion and a distributed protocol that recovers centralized scores under a common representation without pooling client samples. Experiments cover sample removal, selection without target labels, procurement, federated learning, and million-scale valuation, showing useful removal rankings and lower valuation time relative to the evaluated baselines.

Critical strengths
  1. FastDV makes exact empirical deletion and distributed comparability available in one implementable valuation method.

  2. The experiments support useful valuation at substantially lower reported cost.

Critical weaknesses

The large-scale comparison with the closest kernel-based baseline remains incomplete. Section 4.2 excludes Kairos beyond 100K samples because of out-of-memory failures. KAIROS: Scalable Model-Agnostic Data Valuation, Section 3.4, describes cached per-point kernel averages and batch updates; the sums in its Eq. (13) can in principle be accumulated without retaining a full quadratic kernel matrix. The manuscript does not explain the tested storage configuration. Thus its observed failure does not establish an inherent memory barrier for Kairos, and the relative large-scale runtime remains unsettled. Kairos's quadratic offline work still distinguishes it from fixed-anchor FastDV, and the completed SAVA comparison provides independent efficiency evidence. This limits the breadth of the scalability claim rather than invalidating the demonstrated capability.

Questions for authors

Can you report the Kairos storage configuration and its large-scale runtime when kernel sums are accumulated in memory-bounded blocks on the same CPU? This would determine whether the reported advantage extends to a memory-efficient implementation of the closest kernel-based baseline.

2 comments

We sincerely thank the reviewer for recognizing FastDV's contributions in unifying exact empirical LOO valuation and globally comparable distributed scoring, as well as its practical advantages in valuation effectiveness and scalability. Below, we address your main concern.

W1/Q1:

Thanks for your valuable suggestion. We recognize that memory-bounded block-wise computation provides a feasible optimization for Kairos. By computing kernel similarities in blocks and retaining only temporary kernel submatrices and accumulated per-sample statistics, it avoids materializing the full quadratic kernel matrix, substantially reducing memory requirements. However, block-wise computation reduces memory requirements but does not eliminate the quadratic computational cost. According to Eq. (13) of Kairos, computing the kernel averages requires O(N2+NM)O(N^2+NM) operations, regardless of the block size CC.

To investigate this, we additionally implemented memory-bounded Kairos with three block sizes (C=500,1000,2000C=500,1000,2000) and evaluated them on the same CPU. Table R1 reports the runtime and peak memory usage of different valuation methods across dataset sizes, with each entry presented as runtime (seconds) / peak memory (GiB). For Kairos, all three variants successfully processed 1M samples, but remained substantially slower than FastDV. Smaller blocks introduce more block-processing overhead, whereas larger blocks increase temporary memory requirements and may reduce cache efficiency. Consequently, C=1000C=1000 achieves the best runtime among the tested configurations. Even the fastest configuration (C=1000C=1000) required 469.9s, compared with only 14.8s for FastDV, yielding a 31.8× speedup. This advantage arises from FastDV's fixed-anchor representation and shared additive statistics, which achieve O(B3+NB2)\mathcal{O}(B^3+NB^2) complexity and linear scaling in NN for fixed BB. These results demonstrate that FastDV's computational advantage persists even after removing the memory bottleneck of the original tested Kairos implementation.

Table R110K50K100K500K1M
Kairos_raw0.4 / 5.027.9 / 67.7428.1 / 246.7OOMOOM
Kairos_block_0.5k0.8 / 0.513.3 / 0.599.6 / 0.69201.1 / 1.45780.8 / 2.39
Kairos_block_1k0.7 / 0.552.4 / 0.607.5 / 0.69122.7 / 1.44469.9 / 2.39
Kairos_block_2k0.8 / 0.683.5 / 0.6811.1 / 0.76231.5 / 1.45894.8 / 2.39
FastDV0.2 / 0.730.8 / 0.831.4 / 0.896.5 / 1.4114.8 / 2.34

Dear Reviewer YXhS,

Thank you for your valuable insights and the time spent reviewing our work, especially during this busy period. We greatly appreciate it.

As we near the final day of the discussion period, we wanted to check in and see if our responses have addressed your concerns. We welcome your further queries and suggestions and are ready to provide any additional information or clarification you might need.

We understand that reviewing is a time-consuming task and greatly appreciate your commitment to advancing academic discourse. Our team is dedicated to improving our work based on your feedback, believing it will enhance our contribution to the field.

Thank you once again for your guidance and support.

Best regards,
The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.