acceptodds
Under review as a conference paper at ICLR 2027

Predictable Size-Conditional Linear Control Variates for Unbiased Semi-Value Estimation

Abstract

Shapley values and more generally, semi-value attribute a model's prediction to individual players, such as features or training points. Utility assigns a score to every possible subset of players; however, exact computation is exponential, so practice relies on unbiased sampling with variance reduction. Adalina recently removes factor from the query complexity, at linear time and space per utility query. However, its single global scalar control variate cannot capture variation among same-size coalitions, and fitting it on the samples it corrects induces an bias. Observing that this within-size variation is often close to linear, we propose SLICE, which adds a size-wise mean and a size-wise linear control variate with closed-form centering, both fit only on past batches and held fixed for the current one. SLICE is unbiased at finite sample size, keeps Adalina's linear cost and -free query complexity, and, with population-optimal coefficients, does not increase MSE over its global-only counterpart. Across 12 datasets and 18 semi-value settings, SLICE matches or outperforms every baseline, with a median error reduction of .

Primary area:
interpretability and explainable AI
Keywords:
Shapley value, semi-values, approximation

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_LDwaOpenReview ↗
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
AuthorsOpenReview ↗

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.


W1 & Q(i). Utility functions beyond tree ensembles (Appendix G.4, Tables 9–11, Figure 5, pg. 25–27)

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.

    GamePlayersEvaluation budgetSettings where SLICE has lowest errorMedian MSE(Adalina)/MSE(SLICE)
    Breast Cancer (MLP)301000n1000n16/186.65
    MNIST (CNN)251000n1000n16/185.08
    Wine (MLP)13512n512n18/185.66
    Diabetes (MLP)1064n64n18/181.60

    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<2nT<2^n). The larger games use T=1000nT=1000n, which corresponds to only 2.8×10−52.8\times10^{-5} and 7.5×10−47.5\times10^{-4} of exhaustive enumeration on Breast Cancer and MNIST, respectively.

  • Result 2: Representative accuracy and exceptions (Table 10).

    At T=1000nT=1000n, mean relative ℓ2\ell_2 error:

    Semi-valueBreast Cancer: SLICE / best baselineMNIST: SLICE / best baseline
    Shapley0.024 / 0.1080.024 / 0.047
    Beta(4,1)0.039 / 0.0700.041 / 0.066
    Banzhaf(0.5)0.014 / 0.0330.017 / 0.035
    Beta(16,1)0.046 / 0.0410.069 / 0.057

    We report the exceptions. SLICE loses 2 of 18 settings on each large game, primarily when q⋆q^\star is concentrated near one extreme of the coalition sizes. In those settings, its first-batch centering γ1=(u∅+uN)/2\gamma_1=(u_\emptyset+u_N)/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≥2nT\ge2^n is included only to illustrate the trend):

    GameQ=32Q=32Q=64Q=64Q=128Q=128Q=512Q=512Q=1000Q=1000
    Breast Cancer0.891.432.274.866.65
    MNIST1.091.582.434.425.08
    Wine0.911.492.435.667.55†7.55^†
    Diabetes0.961.602.56†2.56^†5.77†5.77^†7.36†7.36^†

    At Q=32Q=32, Adalina is slightly better on three games (ratios 0.89–0.96), showing the short-horizon cost of predictable fitting.

AuthorsOpenReview ↗

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 O(n)O(n) streaming state. With coalition storage matched to SLICE's streaming state, SLICE achieves lower error.

We evaluated Linear/Tree MSR (k=1,10k=1,10), 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:

    MethodSupported semi-valuesError ratio
    Linear MSR (k=10k=10)All 180.86
    Tree MSR (k=10k=10)All 180.17
    shapiq RegressionMSR (linear)Shapley, Banzhaf0.53
    shapiq RegressionMSR (XGBoost)Shapley, Banzhaf0.21
    OddSHAPShapley0.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 (n=3072n=3072, Shapley, T=20nT=20n):

    MethodRelative errorPeak additional memory
    SLICE0.4416.7 MB
    Linear MSR (k=10k=10)0.3691,979.5 MB
    Tree MSR (k=10k=10)0.0841,758.7 MB
    OddSHAP0.04813,905.0 MB

    The evaluated regression-adjusted methods store queried coalitions for surrogate fitting, whereas SLICE maintains an O(n)O(n)-size streaming state independently of the number of queries.

  • Result 3: Fixed-memory comparisons (Table 14).

    We restrict the baselines' coalition-storage allowance to cc times the memory of SLICE's streaming state, excluding surrogate and solver memory (favoring the baselines). The baselines can retain at most mcm_c queries, whereas SLICE processes all TT queries.

    Number of datasets (out of 12) where SLICE has lower error:

    Storage allowanceLinear MSRTree MSROddSHAP
    1× SLICE state12/1212/1211/12
    2×12/1212/129/12
    4×12/129/127/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 O(n)O(n)-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 surrogateError / 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 O(n)O(n) memory independent of the query budget, finite-sample unbiasedness, and dimension-free concentration.

AuthorsOpenReview ↗

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 ℓ2\ell_2 error (lower is better):

Budget fraction1/321/161/81/41/21
SLICE0.4540.3020.2000.1330.0890.059
Adalina0.4680.3310.2340.1660.1170.083
Predictable global-only0.4890.3390.2370.1670.1170.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 T=2nT=2n, Adalina is more accurate (0.922 vs. 1.268). Since W0W_0 and W1W_1 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):

DatasetShapleyBeta(16,1)Banzhaf
superconduct2.41 / 3.79 / 4.812.72 / 3.70 / 4.311.93 / 3.29 / 4.40
har1.18 / 1.59 / 1.961.25 / 1.43 / 1.651.25 / 1.43 / 2.23
CIFAR-small1.04 / 1.11 / 1.231.05 / 1.07 / 1.121.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 B=100B=100 follows the experimental framework of Adalina; βˉ=1\bar\beta=1 keeps (3+8βˉ)(3+8\bar\beta) in Thm 5.4 small; λ=1\lambda=1 is unit-free and acts mainly through the clip; the warm-up gives about 8 samples per free coordinate of bkb_k and per stratum, and its samples are not discarded. The only data-driven choice was δgate=0.1\delta_{gate}=0.1 over 0.05 from a single-seed pilot at Q=15Q=15 (≤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):

AlternativeT=nQ/8T=nQ/8T=nQT=nQ
B=10B=100.981.00
B=1000B=10001.321.09
λ=100\lambda=1001.011.00
λ=104\lambda=10^41.391.61
ϵ\epsilon multiplier 10−1210^{-12}–10−310^{-3}1.001.00
δgate=0.5\delta_{\mathrm{gate}}=0.50.970.98
βˉ=0.5\bar\beta=0.51.211.59
Warm-up 32(n−1)32(n-1)1.171.08

For the tested moderate ranges (B≤100B\le100, λ≤100\lambda\le100, warm-up ≤16(n−1)\le16(n-1), 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%.

Reviewer_kvBWOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes SLICE, a method for unbiased semi-value estimation that extends ADALINA by introducing two additional control variates, W_0 and W_1, to capture between-size and within-size utility variation. The method estimates coefficients using previous batches to ensure finite-sample unbiasedness. Experiments on 12 datasets show improvements over the selected baselines.

Critical strengths

1.The paper addresses the limitations of ADALINA by introducing size-conditional control variates to capture both between-size and within-size utility variation. 2.The theoretical analysis is solid, establishing finite-sample unbiasedness while maintaining O(n) computational complexity per query. 3.The experimental results are promising, showing consistent improvements across different datasets and semi-value settings.

Critical weaknesses

1.The paper discusses Regression MSR, which shares a similar idea of using regression adjustment to reduce variance while maintaining unbiasedness. However, neither Linear MSR nor Tree MSR is included in the experiments, making it difficult to fully assess the advantages of SLICE over these closely related methods. 2.As shown in Theorem 5.8, coefficient estimation errors may offset the theoretical variance reduction. Although warm-up and gating strategies are used in the experiments, their individual contributions are not evaluated. It would be helpful to further investigate their effectiveness under different sampling budgets, especially when the budget is limited. 3.The paper provides some evidence supporting the effectiveness of W_1 in capturing within-size linear variation. However, it does not directly investigate whether the improvement from W_0 is related to between-size mean variation, which is the main motivation for introducing this component.

Questions for authors

1.Could the authors include Linear MSR and Tree MSR as additional baselines in the experiments, using the same utility-query budgets? 2.How does the sampling budget affect the effectiveness of online coefficient estimation and the resulting variance reduction? It would be helpful to further compare SLICE with ADALINA and the predictable global-only baseline under smaller sampling budgets. 3.Could the authors further investigate the effects of the warm-up and gating strategies through ablation or sensitivity analyses? 4.Is the improvement from W_0 related to the degree of between-size mean utility variation? Could the authors provide further experimental evidence to support this relationship?

6 comments
AuthorsOpenReview ↗

Response to Reviewer kvBW (1/3)

We sincerely appreciate Reviewer kvBW's careful and constructive review. We have further revised the manuscript to adopt a unified experimental protocol across game families, applicable baselines, budgets, and varying explained instances. The latest revisions are highlighted in red, while earlier changes remain in blue.


W1 & Q1. Regression-adjusted baselines: accuracy versus memory (Section 6; Figure 3; Tables 1, 5, 8; Appendix G.5–G.6)

The unified experiments establish a trade-off: regression-adjusted estimators are more accurate at equal utility-query budgets, whereas SLICE can continue incorporating queries with an O(n)O(n) streaming state when storing sampled coalitions becomes infeasible.

Result 1: Unified equal-query comparison (Tables 5 and 8).

We now evaluate 12 tree games (10 varying explained instances, 6 semi-values) and two neural-network games (20 instances × 20 estimator seeds, 18 semi-values), across six budgets and all applicable baselines, including Linear/Tree RegressionMSR and OddSHAP.

At the largest budget, the median ratios error(method)/error(SLICE)\mathrm{error}(\mathrm{method})/\mathrm{error}(\mathrm{SLICE}) for the Shapley value on tree games are:

MethodError ratio
Linear MSR0.57
Tree MSR0.18
OddSHAP0.10

Ratios below 1 favor the competing method. On the neural-network games, Tree RegressionMSR also outperforms SLICE in all 36 semi-value settings. We explicitly acknowledge this accuracy advantage whenever memory permits storing the queried coalitions.

Result 2: Measured accuracy–memory trade-off (Table 10).

For Shapley attribution at the largest budget, the supplementary resource comparison reports relative error / peak additional memory:

Methodhar (n=561n=561)CIFAR-small (n=3072n=3072)
SLICE0.138 / 1.3 MB0.441 / 6.7 MB
Tree MSR0.010 / 261.7 MB0.084 / 1,758.7 MB
OddSHAP0.002 / 4,453 MB0.048 / 13,905 MB

These evaluated regression-adjusted implementations retain sampled coalitions and require memory that increases with the query budget, unlike SLICE's O(n)O(n) state.

Result 3: Data valuation under an actual 16 GB constraint (Section G.6, Table 14; Figure 3d).

We added KNN-Shapley data valuation with n=10,000n=10{,}000 training-point players and exact ground truth.

At Q=10Q=10 queries per player, Tree RegressionMSR is more accurate than SLICE (3.646 versus 4.166 relative error), but runs out of memory at Q=20Q=20. OddSHAP already exceeds the memory limit at Q=2Q=2.

In contrast, SLICE continues to Q=500Q=500, reaching 0.124 relative error using only 20 MB, versus 0.638 for Adalina at the same budget. This shows the practical benefit of using additional queries when coalition-storing estimators can no longer run within the available memory.

Overall, we have revised our contribution statement to emphasize finite-sample unbiasedness, dimension-free concentration, and competitive streaming semi-value estimation with O(n)O(n) memory independent of the query budget, rather than universal accuracy superiority over regression-adjusted estimators.

AuthorsOpenReview ↗

Response to Reviewer kvBW (2/3)

W2 & Q2. Sampling budgets and online coefficient estimation (Section 6; Tables 5–6; Appendix G.3–G.4 and E.2)

SLICE's advantage depends on the sampling budget: it typically becomes the most accurate tested O(n)O(n)-memory estimator after a dataset- and semi-value-dependent crossover, while other estimators can be preferable at very small budgets.

Result 1: Unified budget sweep and crossover (Tables 5–6).

Our revised main evaluation varies explained instances across seeds and compares all applicable baselines at six query budgets.

On the 12 tree games, SLICE is the most accurate O(n)O(n)-memory estimator at the largest budget in all 72 dataset–semi-value settings. However, at the smallest budget, another estimator is often preferable.

We define the crossover QcQ_c as the first queries-per-player budget after which SLICE remains the most accurate tested O(n)O(n)-memory estimator. The median crossovers are:

Semi-valueMedian QcQ_c
Shapley16
Banzhaf (0.2, 0.5, 0.8)16
Beta-Shapley (16, 1)45
Beta-Shapley (1, 16)60

Across the 72 tree settings, QcQ_c ranges from 10 to 250 queries per player. On the two neural-network games, SLICE is the most accurate O(n)O(n)-memory estimator in 32/36 settings at Q=1000Q=1000, with four highly skewed settings showing no crossover.

For a direct comparison with predictable global-only, the supplementary fixed-instance sweep (Appendix G.10, Table 20) reports mean errors of 0.454 → 0.059 for SLICE, 0.468 → 0.083 for Adalina, and 0.489 → 0.083 for predictable global-only, from the smallest to largest budget fraction.

At the earlier T=2nT=2n Shapley checkpoint, Adalina is better (0.922 versus 1.268). This reflects the short-horizon cost of predictable global centering and delayed activation of the additional controls.

Result 2: Does online coefficient estimation offset the theoretical gain? (Theorem 5.6; Appendix E.2, Table 2, Figure 4)

Theorem 5.6 decomposes the MSE difference relative to predictable global-only into a nonnegative attainable population gain and a nonnegative online coefficient-estimation penalty.

We evaluate these terms using 30 saved runs for each of 12 tree games and two semi-values (24 settings). Independent reference pools are used exclusively for offline evaluation, not by SLICE during estimation.

At the largest budget:

  • Median estimated penalty-to-gain ratio: 0.04.
  • Estimated MSE difference (SLICE minus predictable global-only): negative in all 24 settings, with pointwise 95% confidence intervals entirely below zero.
  • Larger penalty-to-gain ratios occur in high-dimensional settings, including har (0.50/0.38) and CIFAR-small (0.83/0.79), for Shapley/Beta(16,1), respectively.

These measurements support online variance reduction in the evaluated settings. We explicitly acknowledge that online MSE dominance remains conditional rather than guaranteed for every finite horizon.


W2 & Q3. Warm-up and gating (Appendix G.7–G.8; Tables 16–18)

Warm-up and gating are safeguards against unreliable corrections, not mechanisms that universally improve accuracy.

In 72 supplementary fixed-instance real settings, disabling both reduces median final error by approximately 4%, because activation delays beneficial corrections.

Conversely, on synthetic games with weak size structure, removing both increases MSE relative to global-only by 9% at Q=8Q=8 with βˉ=1\bar\beta=1, and by 73% with βˉ=5\bar\beta=5. Default SLICE remains within 0.5% of global-only on these tested games.

Table 18 further shows limited sensitivity to moderate changes in gate threshold, ridge regularization, and batch size. All variants retain finite-sample unbiasedness because the coefficients remain predictable.

We retain the conservative defaults to guard against unreliable corrections when the utility structure is unknown, while acknowledging the resulting short-budget accuracy trade-off.

AuthorsOpenReview ↗

Response to Reviewer kvBW (3/3)

W3 & Q4. Is the improvement from W0W_0 related to between-size mean variation? (Appendix G.7, Tables 15–16)

Our new analysis finds a strong relationship between the share of utility variation explained by coalition size and the gain obtained from W0W_0.

We measure the between-size variation share as ρ0=Varq⋆(μ∣S∣)/Varq⋆(uS)\rho_0 = Var_{q^\star}(\mu_{\lvert S\rvert}) / Var_{q^\star}(u_S) and define the W0W_0 gain as error(global-only)/error(global+W0W_0). Across 72 settings, the gain of W0W_0 has Spearman correlation 0.90 with ρ0\rho_0. The correlation remains at least 0.71 within each semi-value setting. Likewise, the within-size linear-structure measure predicts the gain of W1W_1 with Spearman correlation 0.79).

Representative Shapley results (gain above 1 means W0W_0 helps):

Datasetρ0\rho_0Gain from W0W_0
wave energy0.051.01×
jannis0.491.55×
GPSP0.531.77×
FOTP0.691.96×
superconduct0.732.05×

The pattern is consistent with our motivation: when coalition size explains little utility variance, W0W_0 contributes little; when between-size variation is substantial, the gain is typically larger. The roles of the controls also depend on the semi-value distribution. For example, on superconduct under Shapley, adding W0W_0 reduces relative error from 0.0845 to 0.0413, while for Beta-Shapley(16,1), W1W_1 provides the larger individual gain (Table 6).

We appreciate the reviewer's suggestions, which led us to clarify the memory–accuracy trade-off and directly validate both the online fitting procedure and the structural motivation for W0W_0 and W1W_1.

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

The recent work Adalina of Li et al. (ICML'26) introduced a global control variate to improve the complexity of estimating the Shapley value (and more generally, semi-values). In this work, the authors refine the idea of Adalina by regressing over two additional control variates (one to account for size-dependent effects and another to account for a general linear effect). By separating the regression and estimation using batches, the authors also managed to remove the O(1/T) bias of the original Adalina. Similar query complexity as Adalina was achieved, with essentially the same time and space complexity. Preliminary experiments confirm the effectiveness of the proposed method.

Critical strengths
  • simple and effective improvement over Adalina
  • encouraging empirical results
Critical weaknesses
  • writing could be improved at various places (details below)

  • the effect of hyperparameters is not discussed and no time or space comparison

Questions for authors

There are a few places where the presentation could be improved:

  • lines 188-191: additional details may be needed to help the authors understand what is R_{glob} and the purpose of Figure 2
  • line 202: it is not clear what does "gate each coefficient online" mean
  • line 315: it might be helpful to point out that b_k is the solution to Eq (7)? do we drop the orthogonal condition b⊥1b \perp 1 here? how does scaling bb affect the results? how sensitive the results are wrt λ\lambda?
  • regression over β\beta seems to depend on the batch size. how does the batch size affect the performance?
  • In Eqs (17) and (18), there are a few parameters: epsilon, delta_{gate} and βˉ\bar\beta; their sensitivity were not discussed in the main paper.
  • Section 5.4 seems less useful as one cannot verify its condition in a single run.

For the experiments, I think it is good to also report the runtime and memory consumption, just as a validation of Proposition 5.10.

3 comments
AuthorsOpenReview ↗

Response to Reviewer ctPD (1/2)

We sincerely thank Reviewer ctPD for the positive assessment and constructive suggestions. We have further revised the manuscript following additional reviewer feedback. The latest changes are highlighted in red, while earlier revisions remain in blue. We have updated the references below to match the latest manuscript (L = manuscript line number).


Q1. What is RglobR_{\mathrm{glob}} and the purpose of Figure 2? (L192–217)

RglobR_{\mathrm{glob}} measures the potential benefit of reallocating samples across coalition sizes. Figure 2 motivates why SLICE retains q⋆q^\star and introduces size-conditional controls instead of changing the sampling distribution.

  • Definition. With γ⋆\gamma^\star fixed, let vs=E[(uS−γ⋆)2∣∣S∣=s]v_s=\mathbb E[(u_S-\gamma^\star)^2\mid |S|=s]. The globally centered estimator's second moment M(q)M(q) is minimized by qsopt∝qs⋆vsq_s^{\mathrm{opt}}\propto q_s^\star\sqrt{v_s}. Thus, Rglob=M(q⋆)/M(qopt)≥1R_{\mathrm{glob}}=M(q^\star)/M(q^{\mathrm{opt}})\ge1 quantifies the potential second-moment reduction from reallocating queries across sizes. For example, Rglob=1.15R_{\mathrm{glob}}=1.15 corresponds to a 13% reduction in the second moment.
  • Figure 2(a): Why retain q⋆q^\star? Rglob≤1.15R_{\mathrm{glob}}\le1.15 for Shapley and moderately asymmetric semi-values, with medians of only 1.16–1.20 even under extreme Beta-Shapley asymmetry. Moreover, q⋆q^\star keeps ∣zS∣2|z_S|_2 constant, supporting Theorem 5.2 without requiring pilot estimates of vsv_s. The between-size drift that motivates W0W_0 remains within individual sampled contributions.
  • Figure 2(b): Why introduce linear W1W_1? The median out-of-fold within-size Rs2R_s^2 is approximately 0.66 (up to 0.97), indicating substantial linear structure. Although this diagnostic fits each size separately while SLICE shares one linear-effect vector, our direct ablation (Appendix G.7, Table 16) validates its usefulness: removing W1W_1 increases median final error by 1.83× across 72 fixed-instance settings.

Q2. What does "gate each coefficient online" mean? (L216–217; Eq. 18)

Each coefficient βj,s,k\beta_{j,s,k} is independently activated or deactivated using only statistics from previous batches.

Initially, both coefficients are zero. After observing at least 8(n−1)8(n-1) interior samples and eight samples in the corresponding stratum, we compute the standardized correlation statistic in Eq. (18). At each batch, a coefficient is set to its clipped least-squares estimate only if this statistic exceeds the threshold. Otherwise, it is set to zero.


Q3. Relation of bkb_k to Eq. (7), orthogonality, scaling, and λ\lambda (L324–336; Appendix G.8)

Equation (16) provides an O(n)O(n) diagonal moment-based estimate of the linear-effect direction in Eq. (7), while preserving bk⊥1nb_k\perp\mathbf 1_n.

  • Orthogonality. Since 1n⊤xS=0\mathbf1_n^\top x_S=0 for every coalition, the numerator of Eq. (16) is orthogonal to 1n\mathbf1_n. Thus, 1n⊤bk=0\mathbf1_n^\top b_k=0, including after the ℓ1\ell_1 rescaling, and the constant Ks,tK_{s,t} in Lemma 4.2 vanishes.
  • Relation to b⋆b^\star. The conditional population covariance E[xSxS⊤∣∣S∣=s]\mathbb E[x_Sx_S^\top\mid |S|=s] is isotropic on 1n⊥\mathbf1_n^\perp. Consequently, the population moment equation recovers the direction of b⋆b^\star up to a scalar factor absorbed by β1,s,k\beta_{1,s,k}.
  • Scaling and λ\lambda. The ridge parameter rescales bkb_k by Dk/(Dk+λ)D_k/(D_k+\lambda). Since W1W_1 is linear in bkb_k, its coefficient can compensate for this scaling unless clipping becomes active. The sensitivity experiment (Appendix G.8, Table 18) confirms that λ≤100\lambda\le100 changes median final error by at most approximately 1%, whereas λ=104\lambda=10^4 causes a 1.61× increase because the shrinkage becomes too large to compensate.
AuthorsOpenReview ↗

Response to Reviewer ctPD (2/2)

Q4–Q5. Batch size and hyperparameter sensitivity (Appendix G.8, Table 18, pp. 31–32)

SLICE shows limited sensitivity to moderate hyperparameter changes. The main degradations arise from excessive clipping, shrinkage, infrequent refitting, or delayed activation.

We conducted a one-at-a-time sensitivity study on GPSP, spambase, superconduct, and har (n=32n=32–561), across Shapley, Beta-Shapley(16,1), and Banzhaf values (10 seeds per setting).

Table 18 reports the median error ratio relative to the default configuration (values above 1 indicate degradation):

ParameterAlternativeT=nQ/8T=nQ/8T=nQT=nQ
B=100B=100100.981.00
10001.321.09
λ=1\lambda=11001.011.00
10410^41.391.61
ϵ=10−9\epsilon=10^{-9}10−1210^{-12}–10−310^{-3}1.001.00
δgate=0.1\delta_{\mathrm{gate}}=0.10.50.970.98
βˉ=1\bar\beta=10.51.211.59
Warm-up =8(n−1)=8(n-1)32(n−1)32(n-1)1.171.08

Table 18 also reports additional values and per-setting ranges.

Our default configuration was fixed before the evaluations, without dataset-specific or semi-value-specific tuning. The only pilot-informed choice was δgate=0.1\delta_{\mathrm{gate}}=0.1 rather than 0.05, based on a single-seed pilot at Q=15Q=15. Choosing the best configuration retrospectively for each setting using ground truth would reduce median error by only 5.5%.


Q6. Practical usefulness of Section 5.4 (Appendices D.4 and E.2; Table 2; Figure 4)

We agree that the condition in Corollary E.1 cannot be verified from a single estimation run. We clarify its analytical role and provide an empirical assessment of whether online coefficient-estimation costs offset the attainable variance reduction.

Theorem 5.6 decomposes the MSE difference relative to predictable global-only into an attainable population variance reduction and a nonnegative penalty from online coefficient estimation. When a stratum's coefficient is zero, its attainable gain and estimation penalty cancel, so its net contribution relative to predictable global-only is zero. This motivates conservative gating when the estimated signal is unreliable.

To assess the actual online coefficients, we analyzed 30 saved runs per setting, covering 12 datasets and two semi-values (24 settings). Independent reference pools were used exclusively for offline evaluation of the moment quantities, not during SLICE estimation.

At the final budget, the estimated MSE difference (SLICE minus predictable global-only) is negative in all 24 settings, with pointwise 95% confidence intervals entirely below zero. The median estimated penalty-to-gain ratio is 0.04.

Representative results, including challenging high-dimensional cases:

DatasetP^/G^\hat P/\hat G ShapleyP^/G^\hat P/\hat G Beta(16,1)Δ^T×103\hat\Delta_T\times10^3 Shapley / Beta
spambase0.020.02−2.6485 / −1.0474
har0.500.38−8.3685 / −8.6914
Fashion-MNIST0.230.32−38.7457 / −8.2139
CIFAR-small0.830.79−15.3367 / −15.5190

All 24 results and confidence intervals appear in Table 2. After coefficient activation, estimated net MSE differences are negative at all recorded checkpoints, with pointwise intervals excluding zero except at two early checkpoints (Figure 4). These intervals condition on the shared reference pools and exclude reference-sampling uncertainty.

We acknowledge in Appendix H that online MSE dominance remains conditional, rather than guaranteed for every utility and finite horizon.


Q7. Runtime and memory (Appendix G.9, Table 19, p. 32)

Measured resource usage supports the O(Tn)O(Tn)-time, O(n)O(n)-memory complexity of Proposition 5.7, with modest overhead relative to Adalina.

Single CPU thread; wall-clock time / peak additional RSS:

DatasetSLICEAdalina
GPSP (n=32n=32, T=32,000T=32{,}000)7 s / 0.19 MB6 s / 0.13 MB
BT (n=77n=77, T=77,000T=77{,}000)1,131 s / 7.14 MB1,070 s / 7.13 MB
har (n=561n=561, T=56,100T=56{,}100)19 s / 1.27 MB16 s / 1.15 MB
Synthetic (n=16,000n=16{,}000, T=20nT=20n)429 s / 30.8 MB378 s / 27.4 MB
Synthetic (n=64,000n=64{,}000, T=20nT=20n)6,645 s / 121 MB5,644 s / 109 MB

When nn increases fourfold from 16,000 to 64,000 at T=20nT=20n, memory grows 3.9× and runtime 15.5×, consistent with the expected 4× and 16× scaling. Across these measurements, SLICE takes at most 1.3× Adalina's runtime and adds at most 12 MB of peak memory.

We hope these clarifications and measurements address the reviewer's questions about the estimator's construction, hyperparameters, theoretical interpretation, and computational overhead.

AuthorsOpenReview ↗

Manuscript Revision Update and Updated Responses to Reviewer ctPD

Dear Reviewer ctPD,

Thank you again for your positive assessment and constructive suggestions.

Following further reviewer feedback, we have substantially revised the manuscript and updated our responses above to reflect the latest version. The new revisions are highlighted in red.

In particular, we have strengthened the experimental evaluation under a unified protocol (Section 6; Appendix G.2–G.4), incorporating additional baselines, multiple utility-query budgets, varying explained instances, and neural-network attribution games.

The analyses addressing your specific questions remain available in the revised manuscript, including the explanations of RglobR_{\mathrm{glob}} and online gating (Sections 3–4), hyperparameter sensitivity (Appendix G.8, Table 18), empirical validation of the online MSE decomposition (Appendix E.2, Table 2), and runtime/memory measurements (Appendix G.9, Table 19).

We would greatly appreciate your consideration of these updates and welcome any further feedback.

Thank you again for your time and thoughtful review.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

Dear Area Chair and Reviewers,

We sincerely appreciate all reviewers for constructive feedback. As the discussion period approaches its end, we would like to clarify our original research objective, why we expanded our evaluation, and what the revised results establish.


1. Original Motivation & Core Contributions

Our work was motivated by Adalina (Li et al., ICML 2026), which achieves log(n)-free query complexity with O(n) time per utility query and O(n) memory. Our original objective was to further reduce estimation error while preserving these computational and memory guarantees.

To this end, SLICE introduces size-conditional control variates while maintaining O(n) time per query and O(n) memory. By fitting coefficients only on past batches, we establish finite-sample unbiasedness and recover log(n)-free query complexity through a Hilbert-space martingale concentration inequality without relying on i.i.d. concentration.

These methodological and theoretical contributions remain central to both the original and revised manuscripts.


2. Why we expanded the experimental evaluation

Consistent with our original objective, our initial experiments followed Adalina's evaluation protocol, primarily comparing estimators operating under O(n) memory constraints.

However, we recognize the reviewers' important point that such comparisons alone cannot establish broader practical competitiveness, particularly against regression-adjusted estimators. We therefore expanded our evaluation to include further baselines under a unified protocol, across tree and neural-network games, multiple query budgets, and varying explained instances.


3. What the revised experiments establish

New experiments clarify three distinct regimes:

  • Within the O(n)-memory estimators, SLICE achieves the lowest error in all 72 tree dataset–semi-value settings at the largest evaluated budget, with median crossover budgets of 16–60 queries per player.
  • At equal query budgets, coalition-storing regression-adjusted estimators generally achieve higher accuracy when sufficient memory is available.
  • Under memory constraints, SLICE can incorporate additional queries with O(n) memory independent of the query budget. In our new 10,000-player data-valuation experiment under 16 GB, coalition-storing estimators cannot reach 20 queries per player, whereas SLICE reaches 500 queries per player using only 20 MB.

4. Clarification of our positioning

Thanks to the reviewers' constructive feedback, these additional comparisons have helped us identify more precisely when SLICE is preferable. While the expanded evaluation has refined our empirical positioning, our original objective and core methodological and theoretical contributions remain unchanged. The revised manuscript now characterizes practical scope and limitations more rigorously.


We have revised the abstract, introduction, experiments, and conclusion accordingly, and provided detailed responses to each reviewer's concerns.

We sincerely appreciate the reviewers' feedback, which has substantially strengthened our work, and hope these revisions can be considered in the final assessment.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.