- 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 . 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 from which the Shapley values can be efficiently extracted and . 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
- 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.
- 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.
- 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
- Can your theoretical insights be used to improve stronger approximators, such as KernelSHAP, TreeMSR, OddSHAP etc.?
- How does BestSHAP compare to other adaptive estimators, such as ShaplEIG?
- How does BestSHAP compare to stronger baselines, such as KernelSHAP, TreeMSR, OddSHAP etc. regarding estimation quality against both, time and query budget?
- Is it correct that in this work KernelSHAP variants mostly refer to Unbiased KernelSHAP (Covert et al., 2021)?
- Could BestSHAP be used to improve the more general RegressionMSR framework? How and by how much?
5 comments
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 where is the query budget, we set . We also note that OddSHAP faces scalability bottlenecks due to the computation of (see lines 142–144 in the OddSHAP repository https://github.com/FFmgll/oddshap/blob/main/src/oddshap/oddshap.py). Specifically, for large values of , this term underflows to 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 , tends to be less structured, so that the nine control variates we employed produce the same estimate of . To partially address this, we construct the target characteristic functions 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 to , 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 , averaged over different random seeds. Let denote the depth of . Due to time constraints, we present results on the three datasets below:
Method GPSP CIFAR10_small Fashion-MNIST TreeMSR with 0.0055 2.83 0.179 TreeBest with (Ours) 0.0026 2.80 0.179 TreeMSR with 0.0081 1.26 0.112 TreeBest with (Ours) 0.0070 1.25 0.112 BestSHAP (Ours) 0.0069 7.28 0.259 KernelSHAP 0.0118 49.98 0.599 OddSHAP 0.0100 4.04 0.858 We also report the validation of ,
Depth GPSP Fashion-MNIST CIFAR10_small D=5 0.70 0.43 0.53 D=10 0.76 0.10 0.56 Our observations are:
- TreeBest may improve upon TreeMSR in approximating the residual when there are structrues inside to leverage;
- Larger validation does not necessarily lead to lower . On GPSP, with a larger even makes TreeMSR worse than our BestSHAP. A Larger 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 without requiring the groundtruth , rather than competing to propose a consistently better randomized algorithm. Across existing studies, it can be observed that different randomized algorithms favor different ; 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 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:
- 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.
- Did you use paired sampling for the methods where this is known to be preferable? (KernelSHAP,LeverageSHAP,OddSHAP)?
- 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
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.?
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.
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.
Mistry, N. (2026). Revisiting RegressionMSR: A reproducibility study. Transactions on Machine Learning Research.