acceptodds
Under review as a conference paper at ICLR 2027

BestSHAP: Best-of-Many Adaptive Approximations for the Shapley Value

Abstract

The Shapley value has become a popular concept in attribution problems because it is uniquely characterized by a specified set of axioms. However, computing the Shapley value for a general characteristic function requires exponentially many queries, motivating extensive research into randomized approximation algorithms. Although several randomized algorithms achieve the best-known query complexity for a specified approximation guarantee, none consistently outperforms the others in practice. In other words, without access to the ground-truth Shapley values, it remains unclear which estimate is the most accurate. In this work, we show that identifying the potentially best estimate can come for free, without requiring access to the ground-truth Shapley values. As a first step, we introduce a class of provably adaptive randomized algorithms that retain the best-known query complexity while requiring only linear memory. These algorithms differ in their choice of control variates, and the effectiveness of the adaptivity associated with each variate depends on the characteristic function used. In particular, this class naturally generalizes the linear-memory KernelSHAP framework. The estimates produced by these algorithms can be obtained simultaneously using the same sequence of sampled subsets. Moreover, the mean squared errors of these estimates, which measure their expected approximation quality, can be approximated in parallel without increasing the time or memory complexity. These estimates of the approximation error thus enable us to select the potentially best candidate. Theoretically, the accuracy of this selection improves as the number of sampled subsets increases. Our theoretical results are supported by empirical evaluations. Furthermore, our proposed algorithm, BestSHAP, consistently outperforms existing linear-memory baselines.

Primary area:
interpretability and explainable AI
Keywords:
Shapley value, adaptive approximation, KernelSHAP

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_emWyOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper considers the problem of approximating the Shapley value efficiently given a black box utility function UU. The authors propose an extension of the "linear-memory framework" (Li et al., 2026a), which writes the Shapley value as a sum over weighted utility evaluations and uses Monte Carlo approximation via importance sampling. Variants of this approach have appeared under different names in the literature (MSR, Unbiased KernelSHAP, order-1 SHAP-IQ, AdaLina, GELS, ARM, OFA, etc.).

The benefit of these methods are the linear time complexity of computing the estimate, compared with polynomial time complexity for most other methods. The substantial drawback of these methods are that they perform worse in practice than other methods, see e.g. Witter et al. (2025).

The SOTA baselines are currently TreeMSR (Witter et al., 2025), the originally proposed KernelSHAP (Lundberg et al, 2017) with paired sampling (Covert et al., 2021), recently improved by LeverageSHAP (Musco & Witter, 2025), and extended by OddSHAP (Fumagalli et al., 2026). Most methods can be viewed as a special case of the RegressionMSR framework: It proposes to learn a powerful surrogate U^≈U\hat U \approx U from which the Shapley values can be efficiently extracted and ϕ(U^)≈ϕ(U)\phi(\hat U) \approx \phi(U). To correct the estimate it additionally exploits linearity of Shapley values and uses MSR on the residual (see Related Work in the paper)

The linear-memory framework (AdaLina; Li et al. 2026a) considered here (Eq 7) is a special case of this, where the surrogate is a constant function, which is the weighted mean that depends on the chosen sampling distribution. The constant prediction of the surrogate is called control variate, and the proposed method BestSHAP aims at choosing this constant in an adaptive rather than a static way from a pre-defined set of options (i.e. selecting the best-performing control variate from different sampling distributions). This can also be viewed as an approach for learning the control variate/constant surrogate within the regressionMSR framework. BestSHAP is supported and constructed using three theoretical results (Theorem 1-3). The experimental evaluation then shows on several tabular datasets with ground-truth TreeSHAP values that BestSHAP consistently outperforms other AdaLina variants.

Critical strengths
  1. Theoretical results are insightful for the AdaLina framework: Selecting the sampling distribution / control variate adaptively is an interesting direction that has not been explored much in the literature, and recently shown strong performance gains using Gaussian Processes (ShaplEIG; Rundel et al., ICML'2026). The presented theoretical insights seem sound and are interesting but restricted to the AdaLina framework.
Critical weaknesses

The main weakness of this paper is that it studies exclusively the class of approximators within the AdaLina framework, which are known to be weak in practice, which is why I believe the results presented here are not significant enough to be presented at the conference.

  1. Practical relevance is weak: Other competitors generally outperform AdaLina-variants in practical applications (see e.g. Witter et al. ,2025). Moreover, the used terminology for KernelSHAP is confusing, because the authors use Unbiased KernelSHAP within the AdaLina framework, which has shown already in the original paper to perform substantially worse than the original KernelSHAP (Covert et al., 2021). The linear-time complexity argument is rarely a restriction for efficient methods like TreeMSR and compared with the required time for evaluating the utility function. The AdaLina framework is a special case of the RegressionMSR framework using a constant surrogate and without MSR adjustment, and should be presented as such. This also directly hints at why this method does not perform well on complex utility functions, since constant surrogates are limited, compared with linear (KernelSHAP) /polynomial (PolySHAP,OddSHAP) regression and boosted tree ensembles (TreeMSR). In my view, a significant contribution of this paper would be to use or extend the theoretical results to such stronger approximators. For instance, a promising direction would be to explore the improvement of TreeMSR or more generally the Regression MSR framework using these insights for MSR.
  2. Adaptive sampling is meaningful but not novel: For instance, recently ShaplEIG (Rundel et al., ICML'2026) has already shown strong improvements via adaptive sampling using Gaussian Processes as a surrogate within the RegressionMSR framework (also without MSR adjustment).
Questions for authors
  1. Can your theoretical insights be used to improve stronger approximators, such as KernelSHAP, TreeMSR, OddSHAP etc.?
  2. How does BestSHAP compare to other adaptive estimators, such as ShaplEIG?
  3. How does BestSHAP compare to stronger baselines, such as KernelSHAP, TreeMSR, OddSHAP etc. regarding estimation quality against both, time and query budget?
  4. Is it correct that in this work KernelSHAP variants mostly refer to Unbiased KernelSHAP (Covert et al., 2021)?
  5. Could BestSHAP be used to improve the more general RegressionMSR framework? How and by how much?
5 comments
AuthorsOpenReview ↗

Response (1/2)

We thank Reviewer emWy for their thoughtful feedback. To address their concerns, we provide detailed clarifications below.

Q1: Can your theoretical insights be used to improve KernelSHAP, OddSHAP etc.?

  • We assume that KernelSHAP here refers to the one (Lundberg & Lee, 2017) that explicitly solves a least-squares problem, and we note that OddSHAP is an extension of this explicit-least-squares KernelSHAP, as stated in lines 110–132. Unfortunately, the answer is no. Although explicit-least-squares KernelSHAP and linear-memory KernelSHAP are theoretically unified by Chen et al. (2025), their underlying analytical techniques differ significantly. For linear-memory KernelSHAP, the expected squared error E[∥ϕ^−ϕ∥22]\mathbb{E}[\Vert{}\widehat{\boldsymbol{\phi}} - \boldsymbol{\phi}\Vert{}_2^2] can be analytically simplified, which serves as the crucial first step to derive the optimal sampling distribution that minimizes query complexity and enables adaptivity. By contrast, to our knowledge, there is still no known useful closed-form expression for E[∥ϕ^−ϕ∥22]\mathbb{E}[\Vert{}\widehat{\boldsymbol{\phi}} - \boldsymbol{\phi}\Vert{}_2^2] in the case of explicit-least-squares KernelSHAP.

Q2: Adaptive sampling is meaningful but not novel: For instance, recently ShaplEIG (Rundel et al., ICML'2026) has already shown strong improvements via adaptive sampling. How does BestSHAP compare to ShaplEIG?

Thank you for pointing out this potential confusion; we have clarified the distinction with a footnote on Page 4.

  • The adaptivity in our work is not about adaptive sampling; rather, it refers to adjusting λf\lambda_f in Eq. (8) on the fly to its optimal value to minimize E[∥ϕ^f−ϕ∥22]∝E[(uS−λf⋅f(s))2]\mathbb{E}[\Vert{}\widehat{\boldsymbol{\phi}}^f - \boldsymbol{\phi}\Vert{}_2^2] \propto \mathbb{E}[(u_S - \lambda_f \cdot f(s))^2], where both the minimum value and the optimal solution depends on both the characteristic function UU and the control variate ff. As shown in Algorithm 1, the sampling distribution is fixed to qs∗∝1s(n−s)q_s^* \propto \frac{1}{\sqrt{s(n-s)}}, meaning the evaluations of (S,U(S))\\{(S, U(S))\\} can be fully parallelized. This is precisely how we scaled up to 308,000308,000 evaluations in our experiments. By contrast, ShaplEIG selects the next subset to evaluate sequentially based on the history of observed pairs (S,U(S))\\{(S, U(S))\\}, which inherently limits the number of evaluations in their experiments to at most 1,0241,024.

Q3: Could BestSHAP be used to improve the more general RegressionMSR framework? How and by how much? Can your theoretical insights be used to improve TreeMSR?

Yes, our framework is complementary to the RegressionMSR framework.

  • Following Witter et al. (2025, Algorithm 1), the framework samples a sequence of pairs (S,U(S))\\{(S, U(S))\\}, fits a characteristic function VV to UU (whose Shapley values can be computed exactly and efficiently), and then uses the same samples (S,U(S))\\{(S, U(S))\\} to approximate ϕ(U−V)\boldsymbol{\phi}(U-V). Note that this corresponds to setting k=1k=1 in their framework, which has been verified as the optimal choice (Mistry, 2026). Specifically, the combination of the sampling distribution and how (S,U(S))\\{(S, U(S))\\} are used to approximate ϕ(U−V)\boldsymbol{\phi}(U-V) (Line 8 in Algorithm 1 therein) constitutes a randomized algorithm, which can instantiate any existing method such as ARM or SHAP-IQ. Consequently, when comparing randomized algorithms that share the same sampling distribution, the task reduces directly to approximating ϕ(U−V)\boldsymbol{\phi}(U-V), as the exact computable term ϕ(V)\boldsymbol{\phi}(V) is fixed across all of them. In this case, the RegressionMSR framework faces the exact same challenge: different randomized algorithms favor different residual structures U−VU-V during approximation, and we do not know which one performs the best in practice where the groundtruths are inaccessible.
  • For convenience, we refer to the randomized algorithm used in the RegressionMSR framework as MSR. As demonstrated by Li et al. (2026a, Appendix B.4), the sampling distribution used by RegressionMSR is essentially identical to q∗q^* in BestSHAP (except that we do not sample ∅\emptyset and [n][n]), and the MSR estimator also reduces to Eq. (8) with λf=0\lambda_f = 0. In particular, BestSHAP uses q∗q^* to sample a single sequence of (S,U(S))\\{(S, U(S))\\} to generate finitely many candidate estimates. Consequently, these candidate estimates use the same VV, and their comparison on ∥ϕ^(U)−ϕ(U)∥\Vert{}\widehat{\phi}(U)-\phi(U)\Vert{} reduces to ∥ϕ^(U−V)−ϕ(U−V)∥2\Vert{}\widehat{\phi}(U-V) - \phi(U-V)\Vert{}^2. For general UU, ϕ(U−V)\phi(U-V) is unavailable, and it is expected that different randomized algorithms favor different U−VU-V. The RegressionMSR framework itself does not include how to predict and select the empirically best-performing estimate when approximating ϕ(U−V)\phi(U-V), whereas BestSHAP is theoretically established for this purpose.

Mistry, N. (2026). Revisiting RegressionMSR: A reproducibility study. Transactions on Machine Learning Research.

AuthorsOpenReview ↗

Response (2/2)

Q4: Is it correct that in this work KernelSHAP variants mostly refer to Unbiased KernelSHAP (Covert et al., 2021)?

Not exactly. We have clarified the definition of these variants in lines 375–377

  • Since we focus on linear-memory KernelSHAP variants, we refer to all variants that fit into the framework of Eq. (8) (which includes Unbiased KernelSHAP (Covert et al., 2021) and SHAP-IQ) and Eq. (10) (which includes Adalia and our newly introduced class of adaptive variants). To our knowledge, a special case of Eq. (8), i.e., Eq. (7), first appeared in Chen et al. (2025) as matrix multiplication estimators, and later, Li et al. (2026a, Appendix B.2) demonstrated that the formula for matrix multiplication estimators can be simplified into Eq. (7).

Q5: How does BestSHAP compare to stronger baselines, such as KernelSHAP, TreeMSR, OddSHAP etc. regarding estimation quality against both, time and query budget?

We ran additional experiments to include KernelSHAP (Lundberg & Lee, 2017), TreeMSR, and OddSHAP.

  • Since solving OddSHAP's induced least-squares problem has a time complexity of O(m3)O(m^3) where mm is the query budget, we set m=10,000m=10,000. We also note that OddSHAP faces scalability bottlenecks due to the computation of 1n(n−s)(ns)\frac{1}{n(n-s)\binom{n}{s}} (see lines 142–144 in the OddSHAP repository https://github.com/FFmgll/oddshap/blob/main/src/oddshap/oddshap.py). Specifically, for large values of nn, this term underflows to 00 due to floating-point precision limitations.

  • As discussed above, BestSHAP can replace MSR within RegressionMSR (which includes TreeMSR); we refer to this variant as TreeBest. While running TreeMSR and TreeBest, we observed that, for tree-based UU, U−VU-V tends to be less structured, so that the nine control variates we employed produce the same estimate of ϕ(U−V)\phi(U-V). To partially address this, we construct the target characteristic functions UU as sums of multiple distinct tree-based characteristic functions.

  • With the query budget fixed, the runtime ordering is: BestSHAP < TreeMSR, TreeBest < KernelSHAP < OddSHAP. Both TreeMSR and TreeBest incur additional overhead to fit VV to UU, whereas KernelSHAP and OddSHAP spend significantly more time solving least-squares problems, with OddSHAP inducing a much larger system than KernelSHAP.

  • We report the relative squared error ∥ϕ^−ϕ∥22∥ϕ∥22\frac{\Vert{}\widehat{\boldsymbol{\phi}} - \boldsymbol{\phi}\Vert{}_2^2}{\Vert{}\boldsymbol{\phi}\Vert{}_2^2}, averaged over 55 different random seeds. Let DD denote the depth of VV. Due to time constraints, we present results on the three datasets below:

    MethodGPSPCIFAR10_smallFashion-MNIST
    TreeMSR with D=5D=50.00552.830.179
    TreeBest with D=5D=5 (Ours)0.00262.800.179
    TreeMSR with D=10D=100.00811.260.112
    TreeBest with D=10D=10 (Ours)0.00701.250.112
    BestSHAP (Ours)0.00697.280.259
    KernelSHAP0.011849.980.599
    OddSHAP0.01004.040.858

    We also report the validation R2R^2 of VV,

    DepthGPSPFashion-MNISTCIFAR10_small
    D=50.700.430.53
    D=100.760.100.56

    Our observations are:

    • TreeBest may improve upon TreeMSR in approximating the residual ϕ(U−V)\phi(U-V) when there are structrues inside U−VU-V to leverage;
    • Larger validation R2R^2 does not necessarily lead to lower ∣ϕ^−ϕ∣2\\|\widehat{\boldsymbol{\phi}}-\boldsymbol{\phi}\\|^2. On GPSP, D=10D=10 with a larger R2=0.76R^2 = 0.76 even makes TreeMSR worse than our BestSHAP. A Larger R2R^2 also makes TreeMSR worse on CIFAR10_small.
    • KernelSHAP underperforms BestSHAP across all these three datasets;
    • OddSHAP does not always perform better than BestSHAP.
  • Last but not least, we would like to emphasize that our focus is on how to theoretically predict and select the empirically best-performing estimate in terms of minimizing ∥ϕ^−ϕ∥2\Vert{}\widehat{\boldsymbol{\phi}}-\boldsymbol{\phi}\Vert{}^2 without requiring the groundtruth ϕ\boldsymbol{\phi}, rather than competing to propose a consistently better randomized algorithm. Across existing studies, it can be observed that different randomized algorithms favor different UU; there is no single randomized algorithm that consistently dominates. In this work, we aim to demonstrate that it is feasible to theoretically establish a framework, i.e., BestSHAP, for predicting and selecting the empirically best-performing estimate without access to groundtruths. To our knowledge, existing studies, including the RegressionMSR framework, do not address this issue theoretically or empirically. We have run additional experiments in Appendix B to demonstrate BestSHAP's selection ability. Although our theory is limited to the framework of Eq. (10), we hope that in the future this can extend to, e.g., explicit least-squares randomized algorithms such as OddSHAP. We believe this is a critical issue in practice, as we do not usually have the groundtruth to determine which randomized algorithm is best suited for the UU at hand.

I thank the authors for their clarifications and new experiments.

My concern W2 is resolved as I have misunderstood that the sampling is adjusted.

My concern W1 remains with limited practical relevance, which is highly relevant for my final assessment of the paper:

The importance of linear-time (and linear-memory) assumption is overstated: The "linear-time" approximation is only relevant in rare applications with extremely many model calls. The typical application of Shapley values is with very few model calls, and the model calls themselves are usually the bottleneck, rather than the approximation method. I appreciate that the authors have added "non-linear"-time variants which outperform the proposed method (BestSHAP) as proposed in the paper. The current evaluation is limited to a single budget, and I would like to see such stronger baselines in the experimental evaluation in the paper (e.g. in Figure 3).

Competitors: Following the previous point, KernelSHAP and other algorithms are implemented in the shapiq package [1] and can be easily benchmarked. Also OddSHAP and KernelSHAP need to be run with paired sampling. Is the current evaluation using this? Moreover, "linear-memory" KernelSHAP is different from least-squares KernelSHAP and generally performs worse in practice (see Chen et al., 2025 or Covert & Lee, 2021), so please change this naming and use the actual (least-squares) KernelSHAP.

Improving TreeMSR with BestSHAP (TreeBest): The newly proposed estimator yields a small improvement but is an interesting result. However, replacing TreeBest actually replaces MSR with Adalina rather than BestSHAP, so this should be clarified.

BestSHAP improves Adalina, but is essentially RegressionMSR with a size-constant surrogate: The proposed estimator can be viewed as part of the Regression MSR framework with a constant surrogate (in contrast to e.g. a tree) and a specific sampling distribution: The surrogate is the constant estimate, and then the same estimator is applied to the residual, and the samples are shared between both (which was also suggested in the Regression MSR paper). The positive point of this is that for this existing framework is now supported with guarantees in this special cases. The negative point is that a constant surrogate is not powerful. I think it would be a meaningful improvement to the paper to highlight this connection more.

I have some follow-up questions:

  1. Did you use established implementations, e.g. from the shap package or shapiq [1] package (which contains RegressionMSR, OddSHAP and least-squares implementations of Kernel/LeverageSHAP)? They violate the linear-time/memory assumption, which is negligible in many applications.
  2. Did you use paired sampling for the methods where this is known to be preferable? (KernelSHAP,LeverageSHAP,OddSHAP)?
  3. Does TreeBest use insights from BestSHAP? It seems to be using Adalina instead of MSR?

In my view, the empirical evaluation of the method against strong competitors (beyond linear-memory/time) in realistic settings needs to be strengthened before this paper can be accepted.

[1] https://shapiq.readthedocs.io/en/latest/generated/shapiq.approximator.html

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

The paper highlights that there are many variants to approximate the Shapley values with the best-known query complexity. However, without access to the ground truth values, it is very hard to tell which estimate is the most accurate. To tackle this, they propose a way to identify the potentially best estimate without needing the ground truth values.

The authors introduce a class of provably randomnized algorithm that retain the best-known query complexity while requiring linear memory, and it supports different control variants that depend on the characteristic function for which the Shapley values are estimated.

The mean square error of each of the estimates is approximated and then used to pick the best performing one and they can be executed in parallel.

Critical strengths

BestSHAP generates a sequence of subsets once to obtain estimates form many adaptive randomnized algorithms, together with estimates of their MSE surrogates. I found the approach very useful as they fit a surrogate characteristic function W to U (the characteristic function).

Critical weaknesses

It is not clear the difference between BestSHAP and the class of provably randomnized algorithm that retain the best-known query complexity while requiring linear memory. The authors claims that with f=1 this corresponds to Adalina. When reading, the reader can think that BestSHAP corresponds to all these different randomnized algorithms, including, Adalina. In Fig. 3 BestSHAP is compared to Adalina so it is confusing, actually for n=784 it seems like the two lines superpone. I think it is important to explain more clear what is BestSHAP.

The authors claim in page 7 "different choices of f are better suited to different characteristic functions". The benchmarks performed are for a characteristic function U(S) that is the output of a trained model for a particular instance when the features outside S are treated as missing. The authors consider multiple datasets and with them decisions trees. To my understanding, they did not consider other type of characteristic function such as the performance of a model attained or fine tuned on the subset S. When read that sentence I was expecting to see that some variants are better for some types of U. I see the comparison of variants for different datasets with different number of features in the figures so it is showing more a difference in performance depending on the data.

Related to my first question below, in Fig 2 and 3, in each plot, the curves seem to have the same slope while having a different initial value of 1 query per player. Then, the best performing method is just the one with lowest intercept. In complexity analysis we care about the scaling and not this intercept so I do not know up to what extent is that this intercept depends on the implementation of the methods, and on the hardware used. If it is just a constant that depends on these parameters, then I see the proposed method BestSHAP just a way of generalizing and being able to compare them. I think the main contribution is the idea of fitting a surrogate characteristic function W to U and I would place the emphasis more on this contribution and to show empirically how well W approximates U. In other word, how much we can trust the estimation of the MSE. I would also like to see the comparison of the estimated MSE to the ground truth MSE at least for some cases in which the Shapley can be calculated or are known.

Questions for authors

In Fig 2 and 3, in each plot, the curves seem to have the same slope while having a different initial value of 1 query per player. I think this should be discussed. Is this showing that all the methods have a linear query complexity? it seems that then the best performing method it is just the one with lowest intercept. In complexity analysis we care about the scaling and not this intercept so I do not know up to what extent is that this intercept depends on the implementation of the methods, and on the hardware used. Please explain this.

Up to page 5 the authors talk about the function f(s) and they say that with f=1 they recover Adalina. However, then in the figures it is used s to refer to the different variants and to me, it is hard for the reader to understand the different between them. Why did you do this?

In lines with my previous point, I do not know to what extent these values s that determine the variants is not just a hyper parameter. Please explain if indeed it is like this and if with this hyper parameter you are being able to consider all the different variants that you then compare against in Fig 3 such as Adalina, the variants of KernelSHAP and the SHAP-IQ.

The authors claims that with f=1 this corresponds to Adalina. When reading, the reader can think that BestSHAP corresponds to all these different randomnized algorithms, including, Adalina. In Fig. 3 BestSHAP is compared to Adalina so it is confusing, actually for n=784 it seems like the two lines superpone. Is it because the best method found by BestSHAP is indeed Adalina?

5 comments
AuthorsOpenReview ↗

Response (1/2)

We thank Reviewer TGYq for their useful feedback. We would like to address their concerns by making clarifications below.

Q1: In Fig 2 and 3, in each plot, the curves seem to have the same slope while having a different initial value of 11 query per player. I think this should be discussed. Is this showing that all the methods have a linear query complexity? it seems that then the best performing method it is just the one with lowest intercept. In complexity analysis we care about the scaling and not this intercept so I do not know up to what extent is that this intercept depends on the implementation of the methods, and on the hardware used. Please explain this.

  • This is unrelated to query complexity analysis. By definition, query complexity measures the number of evaluations required to achieve P(∥ϕ^−ϕ∥≥ϵ)≤δ\mathbb{P}(\Vert{}\widehat{\boldsymbol{\phi}} - \boldsymbol{\phi}\Vert{} \ge \epsilon) \le \delta as the number of players n→∞n \to \infty. Here, by contrast, nn is held fixed within each subfigure; instead, the intercept corresponds to a term inside E[∥ϕ^−ϕ∥2]\mathbb{E}[\Vert{}\widehat{\boldsymbol{\phi}} - \boldsymbol{\phi}\Vert{}^2].

  • Both axes are plotted on a logarithmic scale, and we empirically verify a slope of −1-1 by fitting linear regressions to the curves. This implies log⁡y=b−log⁡T\log y = b - \log T, where y=110∑i=110∣ϕ^(i)−ϕ∣2y = \frac{1}{10}\sum_{i=1}^{10}\\|\widehat{\boldsymbol{\phi}}^{(i)}-\boldsymbol{\phi}\\|^2 and TT is the number of function evaluations used. Exponentiating both sides yields y=ebTy = \frac{e^b}{T}, which corresponds to the theoretical expectation E[∣ϕ^−ϕ∣2]=ebT.\mathbb{E}[\\|\widehat{\boldsymbol{\phi}}-\boldsymbol{\phi}\\|^2] = \frac{e^b}{T}. As stated in line 253, theory gives E[∣ϕ^−ϕ∣2]=nDE[(uS−λff(s))2]−∣φ∣2T.\mathbb{E}[\\|\widehat{\boldsymbol{\phi}}-\boldsymbol{\phi}\\|^2] = \frac{nD\mathbb{E}[(u_S - \lambda_f f(s))^2]-\\|\boldsymbol{\varphi}\\|^2}{T}. Equating the numerators yields eb=nD⋅E[(uS−λff(s))2]−∣φ∣2,e^b = nD\cdot\mathbb{E}[(u_S - \lambda_f f(s))^2]-\\|\boldsymbol{\varphi}\\|^2, demonstrating that the intercept bb depends directly on λf\lambda_f and ff. Thus, bb reflects an intrinsic algorithmic property and is independent of implementation details or hardware.

Q2: It is not clear the difference between BestSHAP and the class of provably randomnized algorithm that retain the best-known query complexity while requiring linear memory. I think the main contribution is the idea of fitting a surrogate characteristic function WW to UU.

  • Our introduced class A\mathcal{A} of linear-time, linear-memory, adaptive randomized algorithms admits the form in Eq. (10), where the control variate ff serves as the only hyperparameter. In particular, all algorithms in A\mathcal{A} share the same sampling distribution q∗q^* defined in Eq. (5), allowing us to sample a single sequence {(S,U(S))}\{(S, U(S))\} to compute all of their estimates simultaneously.

  • Not every choice of ff leads to a linear-time algorithm; this breaks down when λf∗\lambda_f^* is significantly harder to approximate than ϕ\boldsymbol{\phi}. Therefore, we establish Proposition 1 to characterize choices of ff that guarantee linear query complexity. Proposition 1 also implies that there exist infinitely many such valid control variates, a finite subset of which is denoted by F\mathcal{F}.

  • BestSHAP is a framework designed to predict and select the estimate ϕ^g\widehat{\boldsymbol{\phi}}^g satisfying g=arg⁡min⁡f∈FE[∣ϕ^f−ϕ∣2]g = \arg\min_{f\in\mathcal{F}} \mathbb{E}[\\|\widehat{\boldsymbol{\phi}}^f - \boldsymbol{\phi}\\|^2] without knowing the true Shapley value ϕ\boldsymbol{\phi}. Thus, BestSHAP goes beyond merely fitting a surrogate characteristic function WW to UU.

Q3: When read the sentence "different choices of ff are better suited to different characteristic functions," I was expecting to see that some variants are better for some types of UU. I see the comparison of variants for different datasets with different number of features in the figures so it is showing more a difference in performance depending on the data.

  • Each dataset is used to train a tree model, from which we construct multiple characteristic functions by selecting different instances xx or different logits, with the number of players equal to the number of features in the dataset. Consequently, each subfigure corresponds to a distinct characteristic function.

  • In Figure 2, s↦s2s \mapsto s^2 is an equivalent way of writing the control variate f(s)=s2f(s) = s^2 (for every subset size ss) used in Eq. (10). We use nine different control variates (shown in the legend), each yielding a distinct randomized algorithm. The observation is that the best-performing control variate varies across subfigures (i.e., across different characteristic functions), demonstrating that even tree-based characteristic functions exhibit diverse structures and favor different control variates.

AuthorsOpenReview ↗

Response (2/2)

Q4: I would also like to see the comparison of the estimated MSE to the ground truth MSE at least for some cases in which the Shapley can be calculated or are known.

  • We assume that the groundtruth MSE refers to the expression given in line 253. Unfortunately, even with the true Shapley values ϕ\boldsymbol{\phi}, this MSE requires O(2n)O(2^{n}) time to compute. According to the formula, it requires evaluating UU over all possible subsets to compute E[(uS−λff(s))2]\mathbb{E}[(u_S - \lambda_f f(s))^2], which is exponentially expensive. Furthermore, if we understand correctly, this concern is about evaluating BestSHAP's ability to predict and select the empirically best-performing estimate. To this end, we have added additional experiments in Appendix B, the results of which demonstrate that BestSHAP can reliably predict and select the empirically best-performing estimate without knowing the groundtruths.

Q5: Up to page 5 the authors talk about the function f(s)f(s) and they say that with f=1f=1 they recover Adalina. However, then in the figures it is used ss to refer to the different variants and to me, it is hard for the reader to understand the different between them. Why did you do this?

  • Although We are not sure if we understand this concern correctly, we would like to clarify this point. In the legend of Figure 2, s↦f(s)s \mapsto f(s) is an equivalent way of expressing the function ff. For example, s↦s2s \mapsto s^2 corresponds to the control variate ff defined as f(s)=s2f(s) = s^2 for every ss.

Q6: In lines with my previous point, I do not know to what extent these values ss that determine the variants is not just a hyper parameter. Please explain if indeed it is like this and if with this hyper parameter you are being able to consider all the different variants that you then compare against in Fig 3 such as Adalina, the variants of KernelSHAP and the SHAP-IQ. In Fig. 3, BestSHAP is compared to Adalina so it is confusing, actually for n=784n=784 it seems like the two lines superpone. Is it because the best method found by BestSHAP is indeed Adalina?

  • Although We are not sure if we understand this concern correctly, we would like to clarify this point. The only hyperparameter in our adaptive framework of Eq. (10) is the control variate ff, which we express as s↦f(s)s \mapsto f(s). Each subset size s=∣S∣s=|S| at which ff is evaluated is independently sampled using the optimal sampling distribution q∗q^*; this can be seen in lines 4-9 of Algorithm 1. In other words, ss itself is not a hyperparameter.

  • We noticed that the context of Figure 3 could be confusing, and thus we have updated our manuscript accordingly, with all modifications highlighted in red. In particular, we have replaced "Adalina" with "Adaptive KernelSHAP-modified".

  • We would like to clarify what Figure 3 aims to compare. All existing linear-memory KernelSHAP variants fit into either Eq. (8) or Eq. (10). The primary purpose of Figure 3 is to empirically verify the theoretical performance hierarchy: BestSHAP ≥\ge Adaptive KernelSHAP-modified ≥\ge KernelSHAP-modified ≥\ge other variants.

    • For Eq. (8) (nonadaptive): As stated in line 377, there are three choices for the sampling distribution. As proved by Li et al. (2026a, Corollary 3.4), only qs∗∝1s(n−s)q_s^* \propto \frac{1}{\sqrt{s(n-s)}} achieves linear query complexity, whereas the other two require O(nlog⁡nϵ2log⁡1δ)O\left(\frac{n\log n}{\epsilon^2}\log\frac{1}{\delta}\right). KernelSHAP-modified uses q∗q^*.
    • For Eq. (10) (adaptive): In this work, we further demonstrate that using qs∗∝1s(n−s)q_s^* \propto \frac{1}{\sqrt{s(n-s)}} is crucial for establishing adaptivity (Theorem 1). Therefore, in Eq. (10), the sampling distribution is fixed to this form. Specifically, the adaptive counterpart of KernelSHAP-modified corresponds to using the control covariate f(s)=sf(s)=s (equivalently, s↦ss\mapsto s) in Eq. (10).
    • Finally, BestSHAP is theoretically established to select the adaptive estimate that achieves the minimum MSE among finitely many candidates in the framework of Eq. (10).
  • Regarding the original Figure 3, the overlap between the two lines for n=784n=784 occurs because the adaptive estimate selected by BestSHAP is exactly Adalina.

Reviewer_TGYqOpenReview ↗

follow up

Thank you for responding to my questions. I have some remaining doubts:

Q1: In complexity analysis we care about the scaling, and in Fig 2 and 3, the methods seem to have the scaling and thus I cannot identify one as the "winning" method. Could you please clarify if my understanding is correct or if the reading from these figures is different?

In lines with this question, in the conclusions you claim "Our experiments show that BestSHAP identifies the best-performing variant within the linear-memory KernelSHAP framework and consistently outper- forms the other linear-memory baselines. ", in what figure or result one can read that BestSHAP identifies the best-performing variant within the linear-memory KernelSHAP? and where one can read that it outperforms the other linear-memory baselines?

Q2': could you please explain this item that for me it is a weakness? The authors claims that with f=1 this corresponds to Adalina. When reading, the reader can think that BestSHAP corresponds to all these different randomnized algorithms, including, Adalina. In Fig. 3 BestSHAP is compared to Adalina so it is confusing, actually for n=784 it seems like the two lines superpone.

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

This paper appears to be a meaningful extension of the previous work Adalina by extending the constant control variate to a family of control variate functions. The problem itself is interesting and significant. However, some experimental details and aspects of the presentation could be further examined and clarified to improve the paper's quality. Once the additional evidence discussed in the critical weaknesses is provided, I would be happy to increase my score.

Critical strengths

The problem itself is well define, the contribution is nontrival and writing overall easy to follow.

Critical weaknesses

The authors claim that BestSHAP can select the best-performing estimator, but the experimental evaluation does not fully support this claim. My understanding is that a high rank correlation between the estimated selection criterion and the actual approximation errors does not necessarily imply that the best candidate is correctly selected, since rank correlation measures agreement across the entire ranking. What would be more informative is for example how frequently the proposed selection rule identifies the best candidate. Therefore, the authors should consider reporting additional metrics that directly reflect selection accuracy.

For the experiment in Section 5, the candaidte set F1 is fixed and it would be much more informative to investigate different candidate sets, such as nested candidate sets F1, F2, etc and see how expanding it can affect the performance. Adding this analysis would strength the paper a lot.

Questions for authors

I noticed that Theorem 3 provides a pairwise selection guarantee, while BestSHAP can consider multiple control variate functions. I wonder whether Theorem 3 can be extended to the multiple-candidate setting. If such an extension requires nontrivial effort, the current statement of the theorem seems to be of limited significance for the proposed algorithm. The authors may consider moving it to the appendix and using the space to provide the additional experimental evidence suggested in the critical weaknesses.

2 comments

We thank Reviewer sf7U for the constructive comments. We have run additional experiments and have updated our manuscript accordingly, with the modifications marked in red.

Q1: What would be more informative is for example how frequently the proposed selection rule identifies the best candidate. For the experiment in Section 5, the candaidte set F1\mathcal{F}_1 is fixed and it would be much more informative to investigate different candidate sets, such as nested candidate sets F1\mathcal{F}_1, F2\mathcal{F}_2, etc and see how expanding it can affect the performance.

  • We sincerely appreciate this suggestion and have added this experiment with an expanding candidate set F\mathcal{F} in Appendix B. We evaluate BestSHAP's selection using both top-1 accuracy and the ratio of the minimum squared error ∥ϕ^−ϕ∥22\Vert{}\widehat{\boldsymbol{\phi}}-\boldsymbol{\phi}\Vert{}_{2}^{2} to that of the candidate selected by BestSHAP. This error ratio is maximized at 1.01.0 when the selected candidate achieves the minimum squared error. The experimental results show that although the top-1 accuracy decreases to 0.850.85 as F\mathcal{F} expands, the error ratio remains close to 1.01.0. These results demonstrate that BestSHAP can reliably select a competitive candidate against the best-performing one.

Q2: I wonder whether Theorem 3 can be extended to the multiple-candidate setting.

  • Yes, our pairwise guarantee extends directly to the multi-candidate setting via a union bound. The resulting bound reads as P(f\*≠arg⁡max⁡f∈Fβ^f)≤6∣F∣exp⁡(−TΔ232∣u∣∞4Q2),\mathbb{P}\left( f^\* \neq \arg\max_{f\in \mathcal{F}}\widehat{\beta}_{f} \right) \leq 6|\mathcal{F}|\exp\left( -\frac{T\Delta^{2}}{32\\|\mathbf{u}\\|_{\infty}^{4}Q^{2}} \right), where f∗=arg⁡min⁡f∈FMSEf∗f^*=\arg\min_{f\in\mathcal{F}}\mathrm{MSE}_{f}^{*}, Δ=min⁡f∈F ⁣:f≠f∗(βf∗−βf)\Delta = \min_{f\in\mathcal{F}\colon f\neq f^*}\left( \beta_{f^*}-\beta_{f} \right) and Q=max⁡f∈FQfQ = \max_{f\in\mathcal{F}} Q_{f}. For a fixed F\mathcal{F}, exact selection becomes harder as Δ\Delta decreases; however, a small Δ\Delta corresponds precisely to the regime where multiple candidates perform similarly (in which case selecting any of them still yields an error ratio close to 1.01.0).

Thank you for addressing my comments. I will raise my score to 3.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Our Rebuttal

We thank all the reviewers for their time and valuable feedback, and we also thank the AC, SPC, and PC for overseeing the review process. Here, we provide a summary of our rebuttal.

Our Motivation

In the line of research on approximating the Shapley value, many different randomized algorithms have been proposed. In particular, we observed that across different studies (e.g., Li & Yu, 2024a;b; Musco & Witter, 2025; Fumagalli et al., 2026a), there is strong empirical evidence that different randomized algorithms suit different characteristic functions UU, with no single algorithm consistently dominating across all UU in terms of minimizing approximation error. This motivated us to ask whether it is possible to predict the best randomized algorithm among multiple candidates for each specific UU without access to the groundtruth Shapley value, a practical challenge encountered in practice.

Our Main Contribution

By extending a linear-memory framework, we show that such a prediction for each UU is theoretically feasible, culminating in our proposed BestSHAP framework. Although it is currently limited to linear-memory randomized algorithms, we anticipate that its insights will serve as a first step toward inspiring future work on extending this approach to more sophisticated randomized algorithms, such as OddSHAP and RegressionMSR.

Our Rebuttal

  • Reviewer sf7U is supportive of our main contribution and noted that our previous Theorem 3 (which only considered pairwise comparisons) and experimental results were limited in demonstrating BestSHAP's ability to correctly predict the best-performing randomized algorithm for each UU. During the rebuttal, we extended Theorem 3 to the multiple-candidate setting and also ran an additional experiment across 120120 different values of UU (in Appendix B) to clearly confirm that BestSHAP can reliably predict the best-performing randomized algorithm.

  • Reviewer TGYq raised concerns regarding our technical clarity and the empirical evidence supporting our claimed contributions. The added experimental results in Appendix B empirically strengthen our main contribution regarding BestSHAP's selection capability, and we have also thoroughly reviewed our manuscript and added further details where necessary. Following these revisions, Reviewer TGYq recognized our main contribution.

  • Reviewer emWy raised concerns about technical details and placed greater emphasis on empirically demonstrating that BestSHAP is stronger than other non-linear-memory randomized algorithms, such as least-squares KernelSHAP, OddSHAP, and TreeMSR (an instantiation of the RegressionMSR framework). During the rebuttal, we clarified the following points:

    • The concept of adaptivity used by ShaplEIG is entirely different from the adaptivity we use, and Reviewer TGYq acknowledged this misunderstanding.
    • BestSHAP is a framework for predicting the best linear-memory randomized algorithm from a candidate set for each UU; our focus is not on competing to design a stronger individual randomized algorithm. In other words, BestSHAP is not itself a randomized algorithm. Because the candidate set used by BestSHAP can be expanded arbitrarily, and BestSHAP simply selects the best candidate from it, BestSHAP's performance depends on the candidate set we manually specify. Thus, each choice of candidate set yields a specific instantiation of the BestSHAP framework. Therefore, we can only compare a specific instantiation of the BestSHAP framework with other randomized algorithms.
    • Meanwhile, our BestSHAP framework and the RegressionMSR framework (of which TreeMSR is a specific instantiation) are complementary, as they share the same sampling distribution. In other words, they can be directly combined.

    Still, we ran an additional experiment that includes least-squares KernelSHAP, OddSHAP, and TreeMSR. In particular, we combined TreeMSR and BestSHAP to obtain TreeBest by letting BestSHAP predict over the candidate set of 99 different randomized algorithms.

    • Although we were only able to obtain results across three datasets due to the rebuttal deadline, the experimental results still support our motivating observation that no single algorithm dominates.
    • Furthermore, TreeMSR can itself be included in TreeBest's candidate set, highlighting the complementary, rather than competitive, nature of our BestSHAP framework.

    Due to the deadline, we may not be able to hear back from Reviewer emWy regarding their additional concerns. We hope the summary provided here is helpful.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.