- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
SLICE is a Monte Carlo-based semi-value (SV) estimation method that builds on ADALINA (Li et al., 2026), which in turn uses Maximum Sample Reuse (MSR; Wang & Jia, 2023) with importance sampling and control variates for variance reduction.
While ADALINA only uses a single control variate, SLICE proposes a more expressive approach with size-specific control variates and coefficients that are updated online from previous batches.
Also, by fitting the control variates on previous data only, it overcomes the estimation bias of ADALINA, resulting in SLICE as an unbiased estimator (for fixed sample size) while maintaining linear scaling in the amount of players and low utility query complexity (log n free).
Furthermore, it is shown that for population-optimal coefficients the MSE is bounded by the MSE of a baseline with global control variates only.
The paper presents experiments across 12 datasets and various semi-value types where SLICE consistently matches or outperforms the considered competitor methods.
Refs:
- Weida Li, Yaoliang Yu, and Bryan Kian Hsiang Low. Adalina: Adaptive linear approximation for the shapley value and beyond. In Forty-third International Conference on Machine Learning, 2026a.
- Jiachen T Wang and Ruoxi Jia. Data banzhaf: A robust data valuation framework for machine learning. In International conference on artificial intelligence and statistics, pp. 6388–6421. PMLR, 2023
Critical strengths
- The proposed algorithm applies concepts from control-variate based variance reduction to SV estimation, thereby leveraging more expressive control variates than ADALINA and presenting efficient online update rules. The authors also present an approach to make the estimator unbiased for fixed sample size while maintaining linear scaling and low query complexity. Thus, it enhances the capability of ADALINA and overcomes existing drawbacks, while maintaining beneficial properties.
- In the presented experiments across 12 datasets and various semi-value types, SLICE consistently matches or outperforms the considered competitor methods by a large margin.
Critical weaknesses
- Experimental scope: The experiments only considers tree-ensemble based utility functions where the interaction order is bounded by tree depth; several state-of-the-art baselines are missing [in particular OddSHAP (Fumagalli et al., 2026) for Shapley values, Linear MSR and Tree MSR with XGBoost (Witter et al., 2025; not just MSR-Prob, but with surrogate adjustment)], the same test instance is explained across different seeds of a dataset and only the estimation performance of SLICE and the competitors for a single utility query budget (per dataset; T=nQ) is indicated. Also, the algorithm introduces several hyperparameters (e.g. ridge parameter) which are set to specific values without explanation or analysis of sensitivity. Consequently, it is unclear whether SLICE actually outperforms competitors by such a large margin in general, or only in this specific setting.
- Practical relevance: Although the correction of ADALINA’s O(1/T) bias is theoretically appealing, this bias is typically negligible in practice for larger values of T (e.g. T=nQ as in the experiments). The derived MSE bound (Theorem 5.6) only holds for the population-optimal coefficients, which are not known in practice, and Corollary 5.9 depends on the coefficient-estimation penalty which is also unknown in practice. It is thus unclear what the practical relevance of central theorems derived in this work is.
Refs:
- Fumagalli, F., Butler, L., Kang, J.S., Ramchandran, K.; Witter, R.T.. (2026). An Odd Estimator for Shapley Values. Proceedings of the 43rd International Conference on Machine Learning.
- R. Teal Witter, Yurong Liu, and Christopher Musco. Regression-adjusted monte carlo estimators for shapley values and probabilistic values. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025.
Questions for authors
- Could you please extend the presented experiment with i) additional utility function families beyond tree-based ones (e.g. feature attribution or data valuation for neural networks; feasible for small player counts by exhaustive enumeration), ii) add further estimation baselines (OddSHAP, Linear MSR and Tree MSR with XGBoost; all available in the widely used shapiq package (Muschalik et al., 2024); if they are not tractable for the current utility budget please compare them on lower budgets), iii) indicate the performance of SLICE and competitor methods for different utility budgets T (e.g. nQ/32, nQ/16, nQ/8, …, nQ) and iv) also vary the explained test instances with seeds and v) show how the estimation performance of SLICE varies with different configurations of the hyperparameters (e.g. for the ridge parameter or UCB gate parameterization). Lastly, could you please explain how you came up with the specific configuration used in the experiments and whether alternative configurations were tested.
- Could you clarify the practical relevance of the contributions in Section 5, especially for Theorems 5.6 and Corollary 5.9. In particular, could you please explain if and how they can be exploited in practical settings where the quantities they depend on are unknown.
- Could you please (more clearly) clarify the conceptual relation to Linear MSR (Witter et al., 2025) and state explicitly what SLICE adds beyond it? Also please explain why it is not included as a baseline.
Refs:
- Muschalik, M., Baniecki, H., Fumagalli, F., Kolpaczki, P., Hammer, B., & Hüllermeier, E. (2024). shapiq: Shapley interactions for machine learning. Advances in Neural Information Processing Systems, 37, 130324-130357.
- R. Teal Witter, Yurong Liu, and Christopher Musco. Regression-adjusted monte carlo estimators for shapley values and probabilistic values. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025.
9 comments
Response to Reviewer LDwa (2/4)
W1 & Q(ii). OddSHAP, Linear MSR, and Tree MSR (Appendix G.5, Tables 12–15, pg. 27–29)
Our new results clarify a complementary trade-off: regression-adjusted estimators achieve higher accuracy with sufficient memory, whereas SLICE can continuously use all queried utilities with an streaming state. With coalition storage matched to SLICE's streaming state, SLICE achieves lower error.
We evaluated Linear/Tree MSR (), shapiq 1.8.0 RegressionMSR (linear/XGBoost), and OddSHAP, using matched utility-query budgets, datasets, and seeds.
-
Result 1: Equal utility-query budgets (Table 12).
At the largest budgets, the median ratios of error(method)/error(SLICE) are:
Method Supported semi-values Error ratio Linear MSR () All 18 0.86 Tree MSR () All 18 0.17 shapiq RegressionMSR (linear) Shapley, Banzhaf 0.53 shapiq RegressionMSR (XGBoost) Shapley, Banzhaf 0.21 OddSHAP Shapley 0.10 Ratios below 1 favor the competing method. We acknowledge that regression adjustment, particularly with tree surrogates, is substantially more accurate when all queried coalitions can be retained.
-
Result 2: Accuracy–memory trade-off (Table 13).
For CIFAR-small (, Shapley, ):
Method Relative error Peak additional memory SLICE 0.441 6.7 MB Linear MSR () 0.369 1,979.5 MB Tree MSR () 0.084 1,758.7 MB OddSHAP 0.048 13,905.0 MB The evaluated regression-adjusted methods store queried coalitions for surrogate fitting, whereas SLICE maintains an -size streaming state independently of the number of queries.
-
Result 3: Fixed-memory comparisons (Table 14).
We restrict the baselines' coalition-storage allowance to times the memory of SLICE's streaming state, excluding surrogate and solver memory (favoring the baselines). The baselines can retain at most queries, whereas SLICE processes all queries.
Number of datasets (out of 12) where SLICE has lower error:
Storage allowance Linear MSR Tree MSR OddSHAP 1× SLICE state 12/12 12/12 11/12 2× 12/12 12/12 9/12 4× 12/12 9/12 7/12 Thus, at 1× coalition-storage allowance, SLICE achieves lower error in 35/36 comparisons.
To clarify, this Result 3 is a fixed-memory comparison, not an equal-query comparison. The advantage arises when the memory allowance cannot retain all queried coalitions. When the memory constraint is relaxed sufficiently, Tree MSR and OddSHAP recover their accuracy advantage.
-
Result 4: Comparison with an -memory online linear surrogate (Table 15).
To address whether a linear-space surrogate could replace SLICE, we implemented a new linear model updated by SGD on previous batches, frozen during the current batch, and used with closed-form centering.
Online linear surrogate Error / SLICE at final budget Bounded coefficients (Theorem 5.4 conditions satisfied) 1.06 Unbounded coefficients (Theorem 5.4 bound unavailable) 0.99 The bounded surrogate has slightly higher error than SLICE, whereas the unbounded version has comparable accuracy. The online surrogate also requires step-size tuning, whereas SLICE uses closed-form, moment-based updates.
Therefore, we would carefully clarify our contribution from these experiments: not universal accuracy dominance over regression adjustment, but effective streaming semi-value estimation with memory independent of the query budget, finite-sample unbiasedness, and dimension-free concentration.
Response to Reviewer LDwa (3/4)
W1 & Q(iii). Performance across different query budgets (Appendix G.7, Table 17, Figs. 6–7)
We added a six-budget evaluation across all 216 dataset–semi-value settings, using ten seeds and the same hyperparameters.
Mean relative error (lower is better):
| Budget fraction | 1/32 | 1/16 | 1/8 | 1/4 | 1/2 | 1 |
|---|---|---|---|---|---|---|
| SLICE | 0.454 | 0.302 | 0.200 | 0.133 | 0.089 | 0.059 |
| Adalina | 0.468 | 0.331 | 0.234 | 0.166 | 0.117 | 0.083 |
| Predictable global-only | 0.489 | 0.339 | 0.237 | 0.167 | 0.117 | 0.083 |
Among these three methods, SLICE has the lowest mean error at every evaluated fraction. At the full budget, SLICE outperforms both baselines in all 216 settings based on seed-mean errors. Figures 6–7 additionally show the budget dependence of other applicable sampling baselines for Shapley values.
Very-small-budget limitation. At , Adalina is more accurate (0.922 vs. 1.268). Since and are not yet activated, the gap reflects SLICE's predictable global centering rather than the added controls. For Shapley, SLICE overtakes Adalina from approximately 10n–20n queries onward.
W1 & Q(iv). Variability across explained test instances (Appendix G.2, Table 5)
We added a separate instance-variation experiment and find that SLICE outperforms Adalina on all 360 evaluated dataset–semi-value–instance combinations.
For each dataset, we randomly select ten distinct explained test instances. For classification, we also sample a target class, and exact ground truth is recomputed for each instance. This gives 12 datasets × 3 semi-values × 10 instances = 360 comparisons, with an overall median error(Adalina)/error(SLICE) ratio of 2.25.
Representative error ratios (minimum / median / maximum across ten instances):
| Dataset | Shapley | Beta(16,1) | Banzhaf |
|---|---|---|---|
| superconduct | 2.41 / 3.79 / 4.81 | 2.72 / 3.70 / 4.31 | 1.93 / 3.29 / 4.40 |
| har | 1.18 / 1.59 / 1.96 | 1.25 / 1.43 / 1.65 | 1.25 / 1.43 / 2.23 |
| CIFAR-small | 1.04 / 1.11 / 1.23 | 1.05 / 1.07 / 1.12 | 1.05 / 1.08 / 1.21 |
Thus, the improvements are not limited to a single fixed explained instance.
W1 & Q(v). Hyperparameter selection and sensitivity (Appendix G.2, Table 4)
We used one configuration across all 216 settings, with no per-dataset or per-semi-value tuning, and added a systematic sensitivity analysis. Our default setting follows the experimental framework of Adalina; keeps in Thm 5.4 small; is unit-free and acts mainly through the clip; the warm-up gives about 8 samples per free coordinate of and per stratum, and its samples are not discarded. The only data-driven choice was over 0.05 from a single-seed pilot at (≤2% effect).
We varied one parameter at a time on four datasets × three semi-values × ten seeds. The following are median errors relative to the defaults (Values above 1 indicate degradation):
| Alternative | ||
|---|---|---|
| 0.98 | 1.00 | |
| 1.32 | 1.09 | |
| 1.01 | 1.00 | |
| 1.39 | 1.61 | |
| multiplier – | 1.00 | 1.00 |
| 0.97 | 0.98 | |
| 1.21 | 1.59 | |
| Warm-up | 1.17 | 1.08 |
For the tested moderate ranges (, , warm-up , and the evaluated gate and ridge settings), median final error changes by at most 2.3%. The main degradations arise from excessively infrequent refitting, strong shrinkage or clipping, and long warm-up. The defaults are not retrospectively optimal, but selecting the best configuration separately per setting using ground truth would improve median error by 5.5%.
Response to Reviewer LDwa (1/4)
We sincerely appreciate Reviewer LDwa for the detailed and thorough review. We have added new experiments and analysis. All additions are highlighted in blue in the revised PDF.
We extended the evaluation to four nonlinear neural-network attribution games, with exact semi-value ground truths from exhaustive coalition enumeration. Experiments show that SLICE's improvements are not restricted to tree-ensemble utilities.
We use three MLP-based feature-attribution games and one CNN-based superpixel-attribution game. Each is evaluated under 18 semi-values, with 20 explained instances × 20 estimator seeds per instance. All applicable methods use the same query-budget accounting, including initialization queries.
Result 1: Accuracy on neural-network games.
The comparison is against the applicable baselines evaluated in Appendix G.4. The MSE ratios are medians across the 18 semi-value settings; values above 1 favor SLICE.
For Wine and Diabetes, we use the largest evaluated budgets below the exhaustive enumeration cost (T<2n). The larger games use T=1000n, which corresponds to only 2.8×10−5 and 7.5×10−4 of exhaustive enumeration on Breast Cancer and MNIST, respectively.
Result 2: Representative accuracy and exceptions (Table 10).
At T=1000n, mean relative ℓ2 error:
We report the exceptions. SLICE loses 2 of 18 settings on each large game, primarily when q⋆ is concentrated near one extreme of the coalition sizes. In those settings, its first-batch centering γ1=(u∅+uN)/2 can be far from the sampled utilities.
Result 3: Dependence on budget (Table 11).
The median MSE(Adalina)/MSE(SLICE) increases with the query budget (†: T≥2n is included only to illustrate the trend):
At Q=32, Adalina is slightly better on three games (ratios 0.89–0.96), showing the short-horizon cost of predictable fitting.