acceptodds
Under review as a conference paper at ICLR 2027

Sublinear Estimation of Additive Interpretability under SHAP

Abstract

Additive feature attribution methods explain model predictions as sums of per-feature contributions, but their fidelity is fundamentally limited by how well the model behavior can be represented additively. We formalize this limitation through , defined as the best achievable coefficient of determination over the class of additive functions. We reduce the problem to explained-variance estimation and prove that a sublinear learnability estimator can estimate additive interpretability under the Shapley coalition distribution without recovering the optimal attribution vector. For any fixed error tolerance and success probability, the estimator requires model evaluations in the high-dimensional regime. Across synthetic and real-world experiments, it accurately estimates additive interpretability with fewer model evaluations than attribution-based baselines. These results enable practitioners to assess whether an additive explanation can faithfully represent a prediction before paying the cost of computing its feature attributions.

Primary area:
interpretability and explainable AI
Keywords:
Explainable AI, SHAP, Additive Explanations, Explained Variance Estimation

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_UN7iOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper argues for interpreting a model with an additive model and compare their method to SHAP. Therein, the method is to just fit a linear model (the unconstrained way, in comparison to SHAP) on the coalitions. The main claim of this paper is that this can be done easier and quicker in comparison to standard SHAP estimation via KernelSHAP.

Critical strengths
  1. Lemma 1 (Fourth-moment bound under Shapley sampling) seems to be a novel result, which can help with Kong & Valiant (2018)'s approach.
  2. Important issue: Making model interpretability more efficient is an important research area. This is particularly true for Shapley-based explanations, as they require an exponential number of subset evaluations for computing ground-truth attribution scores.
  3. The paper submitted the code for its experiments, which is a good thing.
Critical weaknesses

In my opinion this paper contains many weaknesses, which makes me argue clearly for rejection.

  1. The theoretical and methodological contribution of this work is very limited: This paper is basically just an application of Kong & Valiant (2018), a 2018 NeurIPS paper, to interpretability. While this may be an interesting avenue for interpretability, this work does not make a clear case for it. The main contribution here is an additional Lemma to the original results. But it is not clear how any of this work is relevant for the existing literature on more-efficient Shapley computations. First, the topic of better approximations is studied a lot (e.g. [4] and [5] for recent examples) but not at all positioned here in this paper. Particularly LeverageSHAP [4], which is a refinement of KernelSHAP that proposes a selection order of the coalitions, is important for any such work studying the linear estimation of SHAP-like attribution scores. Second, the "issue" of non-linearity is the main reason why interaction-based explanation methods are proposed ([3] and [1]), which is also absent from the paper here. Importantly, FaithSHAP investigates this linear fit (or lack there off) as its main driver for defining its interactions. This is further discussed in works such as Shapley residuals [2].
  2. Hence, the here presented paper does not really position itself within the main literature on Shapley-based interpretability. It is unclear what the benefits and the costs are. For one, we loose efficiency in the attributions, as the here proposed method just applies the unconstrained least-squares.
  3. Weak baselines: Only KernelSHAP as baseline. The paper only looks at the residuals of the scores. There is no connection weather this is good or bad in terms of interpretability. While I do not think this is too important here in light of the major issues already part of the paper, but the empirical evaluation only contains 6 tabular datasets. None of which suggests much interactivity in the literature.

References:

Questions for authors

None

1 comment

The review’s summary describes our method as fitting an unconstrained linear model to obtain attribution scores more efficiently than KernelSHAP. This description does not match the proposed method.

Our paper studies a different question from efficient Shapley estimation or interaction attribution. We investigate how faithfully can an additive explanation represent a prediction, and can this representational limit be assessed efficiently? We characterize this capability by Rmax⁡2R^2_{\max}, the optimal coefficient of determination achievable by the additive function class under the explanation setting. Unconstrained least squares defines this quantity. Our method does not fit that model or return its coefficients.

The estimator itself builds on Kong & Valiant (2018). Our main technical contribution is proving the Shapley-specific fourth-moment bound that yields an O(dlog⁡d)O(\sqrt d\log d) model-evaluation guarantee in the high-dimensional regime. This result establishes that additive fidelity can be estimated in a regime where regression coefficients cannot be uniquely identified from the sampled equations. For regression-based attribution methods such as LeverageSHAP, incorporating the efficiency constraint leaves d−1d-1 free parameters, requiring at least d−1d-1 sampled equations for full column rank. Below this budget, a pseudoinverse or regularization can select a solution, but the sampled equations alone do not uniquely determine the coefficients. Our estimator avoids this identification requirement.

The experiments include OLS, CHIVE, and EigenPrism in addition to KernelSHAP. We used KernelSHAP as a simple attribution-first baseline and primarily emphasized learnability and explained-variance methods because they address our scalar estimation target. The distinction between estimating optimal fidelity and recovering coefficients motivated this selection. Nevertheless, modern SHAP estimators are relevant empirical comparisons, and we will add them to evaluate the advantage against stronger attribution-first baselines.

Interaction-based explanations are also important related work. We do not claim to be the first to recognize the representational limitations of additive explanations. Our contribution is to make this limitation actionable through a scalar fidelity diagnostic with a sublinear estimation guarantee. This addresses a preliminary question: is an additive representation sufficiently faithful, or is a richer explanation needed? Interaction methods then characterize how features jointly contribute. Our method can assess additive representability without recovering either attribution coefficients or interaction quantities, and is complementary to these methods rather than a replacement for them. We will expand the discussion of Faith-Shap, Shapley Residuals, and other interaction-based approaches to clarify their relationship to our target.

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

The paper introduces "additive interpretability", the best achievable R^2 of an additive surrogate of the model's local behaviour under the Shapley coalition distribution, i.e., the R^2 of the unconstrained weighted least-squares problem underlying KernelSHAP. The authors show that the explained-variance estimator of Kong & Valiant (2018) applies to this setting, proving a fourth-moment bound with C = O(log d) that yields an O(sqrt(d) log d) sample complexity in the high-dimensional regime. Experiments on six UCI datasets and synthetic polynomials report lower sample requirements than KernelSHAP, OLS, CHIVE and EigenPrism at higher dimensions.

Critical strengths
  • Assessing whether Shapley values can faithfully explain a given prediction remains a relevant problem, given their wide adoption in machine learning practice.
Critical weaknesses
  • Important related work is not discussed. Beyond the works cited (e.g., Hooker, 2004; Lundberg & Lee, 2017b), the fact that Shapley values do not capture feature interactions, and the quantification of this limitation, have been studied extensively. In particular:
    • Grabisch & Roubens, "An axiomatic approach to the concept of interaction among players in cooperative games", International Journal of Game Theory, 1999.
    • Kumar, Scheidegger, Venkatasubramanian & Friedler, "Shapley Residuals: Quantifying the Limits of the Shapley Value for Explanations", NeurIPS 2021.
    • Tsai, Yeh & Ravikumar, "Faith-Shap: The Faithful Shapley Interaction Index", JMLR 2023.
    • Bordt & von Luxburg, "From Shapley Values to Generalized Additive Models and Back", AISTATS 2023.
  • Relevant baselines appear to be missing. KernelSHAP is no longer the state of the art, and several recent estimators substantially reduce its error, e.g.:
    • Musco & Witter, "Provably Accurate Shapley Value Estimation via Leverage Score Sampling", ICLR 2025.
    • Chen, Seshadri, Villani, Niroula, Chakrabarti, Ray, Deshpande, Yalovetzky, Pistoia & Kumar, "A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values", NeurIPS 2025.
    • Witter, Liu & Musco, "Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values", NeurIPS 2025.
  • The novelty of the contribution is unclear. The proposed metric is the R^2 of a weighted linear regression, namely the unconstrained version of the KernelSHAP regression problem, and the estimator is that of Kong & Valiant (2018). The main technical result (Lemma 1) bounds the log d cost arising from the concentration of the Shapley kernel on small and large coalitions. A closely related characterization appears in Chen et al. (2025), who show that the Shapley kernel's coherence parameter is Theta(d log d), versus Theta(d) under leverage-score sampling.
Questions for authors
  • How does this work relate to the references listed above, and what does it contribute beyond them?
  • Does the KernelSHAP baseline use paired sampling (Covert & Lee, 2021)?
  • How were the datasets chosen? Was the goal to span different orders of magnitude of d? They differ from those commonly used in the Shapley estimation literature; this is not a problem in itself, but it makes comparison with prior work difficult. Could the results be reproduced on standard datasets such as Adult/Census, California Housing, COMPAS or Diabetes?
3 comments

We thank the reviewer for the constructive feedback. The main concerns involve the novelty of our contribution, the relationship to prior work on interactions and representational limitations, and the strength and comparability of the empirical evaluation.

Our contribution is to formulate optimal additive fidelity as a pre-explanation diagnostic and establish its sublinear estimation guarantee under Shapley sampling. The estimator is adapted from Kong & Valiant (2018). Our main technical contribution is the Shapley-specific directional fourth-moment bound that enables its application. Chen et al.’s analysis controls the largest sampling-rescaled squared row norm η\eta and a response-dependent total second moment of a vector estimator γ\gamma. Ours establishes directional fourth-moment control that enables the scalar-estimation analysis. The moments are connected, but the stated bounds are not interchangeable.

We do not claim to be the first to recognize the representational limitations of additive explanations. We make this limitation actionable through a scalar fidelity diagnostic and an adapted estimator with a sublinear model-evaluation guarantee under Shapley sampling. This addresses a preliminary question: is an additive representation sufficiently faithful, or is a richer explanation needed? Interaction methods then characterize how features jointly contribute. By estimating only the diagnostic, our approach avoids recovering attribution or interaction coefficients and can assess the need to go beyond additivity with a sublinear model-evaluation guarantee. We will expand the related-work discussion to make this complementary role explicit.

We agree that recent efficient SHAP estimators deserve discussion and comparison. Our baseline selection primarily focused on learnability and explained-variance estimators because they directly address our scalar estimation problem. The central distinction is that our method estimates the best achievable additive fidelity with a sublinear number of model evaluations, without recovering the attribution vector. Modern SHAP estimators improve attribution recovery but still solve this additional task. For example, LeverageSHAP provides an O(dlog⁡d)O(d\log d) evaluation guarantee under its approximation criterion. Given the substantial gap observed for KernelSHAP at higher dimensions, we expect direct scalar estimation to remain advantageous. We will add modern SHAP estimators in the experiments to strengthen the comparison.

Below, we address the remaining experimental questions individually.

Does the KernelSHAP baseline use paired sampling?

No. Our baseline uses Captum’s default KernelSHAP implementation, which samples nontrivial coalitions individually rather than pairing each with its complement. We will clarify this in the paper.

How were the datasets chosen?

We selected datasets with diverse feature dimensions, while balancing the number of low- and high-dimensional datasets. This allows us to examine both the regime where conventional regression is competitive and the higher-dimensional regime targeted by our guarantee. We will clarify this selection rationale in the experimental section.

Could the results be reproduced on Adult/Census, California Housing, COMPAS, or Diabetes?

We are currently extending the evaluation to additional datasets suggested by the reviewer and expect to include the results in the appendix. Their relatively low feature dimensions make these experiments feasible within the rebuttal period.

Thanks to the authors for engaging in the discussion. After reading the rebuttal I will maintain my score.

Thank you for considering our response. We have uploaded the revised manuscript, with changes highlighted in blue. Section 2 now discusses the relevant interaction and functional-decomposition literature.

We added LeverageSHAP using the authors’ implementation together with three datasets mentioned in the review: Adult/Census, COMPAS, and Diabetes. LeverageSHAP performed the best among Australian (d=14)(d=14) and the newly added low-dimensional datasets. The Kong & Valiant's estimator retains the lowest reported mean budget in Table 1’s higher-dimensional settings. These results support the high-dimensional scope of our original empirical claim.

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

The authors define the additive interpretability as the best achievable coefficienf of determination Rmax⁡2(H)R^2_{\max} (\mathcal{H}) from a class of additive functions H\mathcal{H} and construct an estimator of Rmax⁡2R^2_{\max} that requires O(dlog⁡d)O(\sqrt{d} \log d) model evaluations for fixed accuracy and confidence. Their estimator is an adaption of the estimator introduced by Kong & Valiant (2018). Moreover, they prove that the Shapley coalition distribution satisfies the structural and moment conditions required for sublinear learnability estimation. Finally, they evaluate their estimator across multilinear polynomials and six real-world datasets and which supports the sublinear scaling and in some cases demonstrate lower sample requirements than the baselines.

Critical strengths

Characterizing the limits and efficiency additive feature attribution is interesting.

Critical weaknesses

-The paper reads not very clearly. -All the citations are before 2024 and outdated. There is no paper citated say from many related papers on Shapley Interaction in NeurIPS, ICML, ICLR, AAAI 2025-2026. -Empirical evidence is thin and they overstate their findings. Their approach requires fewer model evaluations than the baselines only on 21/36 evaluations and when including the standard deviations (which are huge), their approach is often in the same interval as some of the baselines. -In B.2, they mention a "German" dataset once but this is mentioned nowhere else in the manuscript and they are missing the number of samples they used to deterimine the ground truth for the Australian and Spectfheart datasets.

Questions for authors

-contributions are unclear: in introduction they claim to construct an estimator of Rmax⁡2R^2_{\max} but in conclusion they state that the estimator is from Kong & Valiant (2018). -estimator requires O(dlog⁡d)O(\sqrt{d} \log d) model evaluations, however dd is neither defined in the abstract nor in the introduction. -in 5. Experiments they state that they use 10 independent seeds and report the eighth order statistic, i.e. the number of samples with which 80% of the observed runs reach the target error or better. Why this metric rather than reporting the mean and std deviation over all runs? -in 5.1 they state that their estimator approaches some reference value before n=dn=d but do not state the value of the reference value or how it is determined. -Are the values in table 1 averaged over the 10 target predictions? -Why are standard deviations of their approach and the baselines in all experiments so large? -Discussion section contains mostly future directions and only very little about implications/impact of their work. Future direction are fairly vague. Which research question is their work trying to answer?

2 comments

We thank the reviewer for the constructive feedback. The main concerns involve the clarity of our contributions, the relationship to recent Shapley interaction work, the interpretation of the empirical results, and the presentation of technical details and experimental design.

Our contribution is to formulate additive interpretability as a diagnostic that separates representational limitations from attribution-estimation errors, and to establish that it can be estimated with sublinear model evaluations under Shapley sampling. The estimator is adapted from Kong & Valiant (2018). Our main technical contribution is proving the Shapley-specific moment bound needed to obtain the O(dlog⁡d)O(\sqrt d\log d) guarantee in the high-dimensional regime, where dd is the number of features.

Recent Shapley interaction methods are relevant. But they address a different problem: how to attribute effects to feature interactions, whereas our work asks whether an additive representation is sufficiently faithful. We show that this scalar diagnostic can be estimated with sublinear model evaluations. We therefore view our method as a pre-explanation diagnostic that can indicate when a richer interaction-based representation may be warranted, rather than as a replacement for these methods.

Our empirical claim concerns the high-dimensional regime, rather than uniform superiority across all settings. Section 5.2 explicitly reports that conventional regression requires fewer evaluations at low dimensions, while our estimator becomes favorable at higher dimensions. For example, in Table 1, our estimator requires a mean of 1,539 evaluations on Parkinsons (d=753)(d=753), compared with 5,255 for the strongest baseline, EigenPrism. On QSAR Toxic (d=1024)(d=1024), the corresponding means are 992 versus 3,215 for CHIVE. These represent approximately threefold reductions in reported mean budget. The aggregate count of 21/36 settings does not capture this dependence on dimension. We will qualify the Abstract’s empirical claim to higher-dimensional settings.

Below, we address the technical details and experimental design questions individually.

Why report the eighth order statistic rather than the mean and SD across runs?

The eighth order statistic summarizes a reliability-oriented budget: approximately the budget by which 80% of the ten observed runs have reached the error threshold. A mean across seeds does not express this reliability objective.

What is the reference value in Section 5.1, and how is it determined?

The reference value calculation is introduced at the beginning of Section 5: "We construct a high-budget reference estimate of Rmax⁡2R^2_{\max} using KernelSHAP with an independent set of sampled coalitions." The stop conditions are described in Appendix B.2. We will improve the presentation here.

Are Table 1 values averaged over ten target predictions?

Yes. For each prediction, we obtain a budget summary using the eighth order statistic across ten independent seeds. Table 1 reports the mean and SD of these summaries across ten target predictions. Synthetic results are aggregated analogously across ten functions. Section 5 states this procedure.

Why are the standard deviations so large?

In Table 1, the SDs measure variation in budget summaries across different predictions or functions, rather than sampling variability for one fixed target. They therefore combine differences in estimation difficulty across targets with variability in the seed-based budget summaries. The aggregate results do not isolate these contributions, and we will clarify this interpretation.

What research question does the paper answer, and what are its implications?

Our research question concerns defining and efficiently estimating the best achievable additive fidelity, as stated in the Introduction: “whether Rmax⁡2R^2_{\max} can be estimated more efficiently without finding the optimal attribution.”

The practical implication is to distinguish representational limitations from estimation errors. A low Rmax⁡2R^2_{\max} indicates that more accurate attribution recovery cannot overcome the additive class’s fidelity limit under the chosen settings, whereas a high value indicates that a faithful additive approximation exists. A potential application is therefore to provide an early signal of whether continued sampling to recover attribution values is worthwhile or whether to stop. We will foreground this potential use in the Discussion.

Appendix B.2 mentions “German” and omits the reference budgets for Australian and Spectfheart.

These are reporting errors. We will correct the inconsistent dataset name and provide the fitting and independent evaluation budgets for both Australian and Spectfheart.

d is undefined.

d denotes the number of input features. It is introduced with the coalition representation in Section 3, but should be defined when the complexity bound first appears. We will add this definition.

We have uploaded the revised manuscript, with changes highlighted in blue. We clarified the contributions and related-work positioning, revised the description of Figure 1’s absolute error, and clarified the budget aggregation and standard deviations.

We also added LeverageSHAP comparisons in Table 1 and results on COMPAS, Diabetes, and Adult in the appendix. The Kong & Valiant's estimator retains the lowest reported mean budget on the three higher-dimensional datasets and synthetic settings with (d≥250)(d\ge250), while LeverageSHAP performs best on the three added low-dimensional datasets. These results support the high-dimensional scope of our empirical claim.

Comments on the paper

1 comment

Thank you for clarifying your concerns. We have uploaded a revised manuscript that distinguishes the estimator adapted from Kong & Valiant from our Shapley-specific fourth-moment contribution, and explains why estimating optimal additive fidelity without recovering attribution coefficients is useful. Section 2 expands the comparison with interaction-based explanations, functional decompositions, and efficient SHAP estimators.

We have added LeverageSHAP comparisons and results on COMPAS, Diabetes, and Adult. At absolute error 0.025, LeverageSHAP achieves the lowest reported mean evaluation budget on Australian (d=14)(d=14) and the three added low-dimensional datasets. Kong & Valiant's estimator retains the lowest reported mean budget on the three higher-dimensional datasets and synthetic settings with (d≥250)(d\ge250). These results clarify both the high-dimensional advantage and the settings where attribution-first methods are more efficient.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.