acceptodds
Under review as a conference paper at ICLR 2027

ShapleyOG: Fast Adaptive Shapley Value Estimation with Odd Gaussian Processes

39 views

Abstract

Shapley values are a central tool for attribution in machine learning. Since their exact computation requires evaluating the cooperative game to be explained on exponentially many player coalitions, they are typically estimated from a limited number of evaluations. Recently, ShaplEIG has shown that adaptively selecting the coalitions to evaluate substantially improves sample efficiency over classical estimators. This, however, comes at the cost of a sequential procedure that, in every iteration, refits a Gaussian process surrogate of the game and selects the coalition with the largest expected information gain about the Shapley values. The resulting computational overhead limits its applicability to costly games with low evaluation budgets. We present fast adaptive Shapley value estimation with Odd Gaussian Processes (ShapleyOG) to overcome this limitation. ShapleyOG leverages the fact that Shapley values depend only on the odd functional component of the game, and we show that under paired sampling a Gaussian process surrogate on this component alone yields the same Shapley value posterior and coalition selection criterion from half as many observations. Moreover, ShapleyOG refits the surrogate only on a sparse schedule and efficiently updates the selection criterion in between, and it extends quadrature-based computation schemes to the prior covariance of the Shapley values, which allows for exact or cheaper approximate computation. In extensive experiments on diverse games, ShapleyOG matches the estimation accuracy of ShaplEIG while reducing its overhead by up to three orders of magnitude. As a result, it outperforms state-of-the-art non-adaptive estimators at equal total computation time already when a single evaluation takes a tenth of a second and a budget of a few thousand evaluations suffices, thereby widening the regime in which adaptive coalition selection is applicable and pays off.

Primary area:
interpretability and explainable AI
Keywords:
Interpretability, Shapley values, Adaptive coalition selection, Surrogate modeling, Gaussian Processes, Odd/even decomposition, Computational efficiency

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_FnQiOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes ShapleyOG, a faster method for adaptive Shapley value estimation. It combines an odd Gaussian process with less frequent hyperparameter fitting, incremental updates, and quadrature computations. The experiments show substantial reductions in computational overhead while generally maintaining estimation accuracy.

Critical strengths

1.The method has clear theoretical support. Under fixed hyperparameters and paired observations, the paper proves equivalence of the Shapley posterior and the information gain criterion between the full and odd GPs. These results provide a sound basis for reducing computation. 2.I found the paper clearly written. The problem is well defined, and the presentation makes it easy to understand the motivation behind each component and how it contributes to the overall method.

Critical weaknesses

1.The practical runtime advantage still needs direct validation. Total runtime is constructed from measured algorithm overhead and an assumed cost per value function evaluation. Experiments with an actual expensive model would help establish whether the gains hold when batching, parallel evaluation, and varying evaluation costs are taken into account. 2.I would like to see a comparison using the same odd GP, initialization, fitting strategy, and evaluation budget, but replacing information gain selection with random paired sampling. This would help separate the accuracy gains from GP modeling and active selection, and clarify when the additional cost of active selection is worthwhile. 3.The evaluation also omits the complementary contribution sampling methods of Zhang et al. (2023)[1]. These methods estimate Shapley values using differences between complementary coalitions, which are directly related to the odd targets used here. Although OddSHAP and other paired methods are included, a comparison with these direct sampling estimators under equal evaluation budgets and total runtime would better establish the additional benefits of GP modeling and information gain selection.

[1] Efficient sampling approaches to shapley value approximation

Questions for authors

please see weaknesses

2 comments

We thank the reviewer for the concrete suggestions; all additions are in the revised PDF.

W1 (runtime validation with batched evaluation and varying costs). We agree that this relationship was not made explicit in the paper; the revised PDF now does so and adds a live experiment.

ShapleyOG is exactly equivalent to a batched acquisition approach (Section 3.3): between the refits at 2i2^i and 2i+12^{i+1}, the coalitions selected via EIG form a deterministic sequence that depends only on the previously selected coalitions, not on their observed values. They can thus be evaluated in parallel as one batch, with identical estimates and overhead for the coalition selection. Consequently, for a fixed evaluation time, the total computation time perspective of Figure 2 (left) also covers parallel evaluation with kk evaluations at a time, by reading the assumed cost per evaluation as the time of one evaluation round divided by kk (Section 4.2, App. E.4), e.g., one minute per round with k=64k = 64 corresponds to about 1 s. Since the figure spans three orders of magnitude of this cost, i.e., many combinations of round times and parallelization factors, it already characterizes that, on the considered games and budgets, ShapleyOG is beneficial in batched settings wherever the round time divided by kk exceeds a tenth of a second, a regime that is common in ML applications and in particular for the expensive models the reviewer mentions. Deviating settings (random evaluation times, coalition-dependent costs) are discussed in App. E.4.

To further validate this perspective, we ran ShapleyOG in batched mode on a live TabPFN v2 model (details in App. F.8): 10 players, 8 parallel evaluations, measured evaluation costs of 6 to 61 seconds that grow with the coalition size, 10 seeds, against OddSHAP as the strongest competitor. After 32, 64 and 128 evaluations, with measured end-to-end wall-clock times (overhead and evaluations) of 1.9, 3.6 and 7.0 min that differ by at most 0.1 min between the two methods, the geometric mean NMSE of ShapleyOG is 37, 3.9 and 1.8 times lower, and the batched run selects exactly the coalitions of a sequential one. At larger budgets, which on a 10-player game quickly cover a substantial fraction of all coalitions, non-adaptive estimators narrow the gap, as observed for the small games in Section 4.2.

W2 (same odd GP without active selection). We have added an ablation of the adaptive coalition selection to the revised PDF (Section 4.2, App. E.5 and F.6). On the same games, budgets, and seeds as in the main experiment, we benchmark a non-adaptive counterpart of ShapleyOG: the same odd GP and hyperparameter fitting procedure, but based on random, paired coalition sampling (uniform over coalition sizes, the standard and stronger choice, with the border trick of Fumagalli et al. (2023) for sufficiently large budgets).

At equal evaluation budget, the counterpart is outperformed by ShapleyOG (NMSE pooled across games, relative to the counterpart; Table 12):

budget TT2565121024204840968192
NMSE ShapleyOG / counterpart0.650.610.570.560.570.57
NMSE best baseline per game / counterpart1.701.701.631.371.271.31

ShapleyOG thus reduces the NMSE to 56–65%, while the counterpart in turn is more accurate than the best baseline estimator of the main experiment per game by a factor of 1.27 to 1.70 in the geometric mean over games, i.e., the GP surrogate and the adaptive selection contribute comparably to the advantage of ShapleyOG. While the overhead of ShapleyOG is mostly higher than that of its counterpart, ShapleyOG is still more accurate at equal total computation time from 0.1 seconds per evaluation on. For cheaper value functions, the counterpart is itself dominated by OddSHAP except at the smallest total times (Figure 7, right, App. F.6), so that it only pays off in a narrow regime of evaluation costs.

W3 (complementary contribution sampling of Zhang et al., 2023). We have added these estimators to the main experiment (Section 4.2, App. F): we ran all three variants (CC, CCN, CCB) on all games, seeds, and budgets and report the one with the lowest pooled NMSE, CCN (App. F.7). Its NMSE is up to almost three orders of magnitude higher than that of ShapleyOG (NMSE pooled across games by the geometric mean; see also Figure 1, left, and Table 14):

budget TT2565121024204840968192
NMSE ShapleyOG4.0e-31.1e-32.9e-48.7e-52.5e-56.8e-6
NMSE CCN3.1e-11.5e-16.5e-22.5e-21.1e-24.9e-3

The same holds at equal total runtime (Figure 2, left).

We hope that these additions resolve the three concerns. Given the strengths the reviewer lists, we would be grateful if the reviewer adjusted the overall rating and the soundness score accordingly.

Thank you for your detailed response. It addressed my concerns, and I have increased the score.

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

The paper presents ShapleyOG: a Shapley value estimation that builds on previous work to build a faster adaptive estimation algorithm. Adaptivity means that the procedure selects new coalitions based on an expected information gain (EIG) computation. ShapleyOG substantially builds upon a previous adaptive procedure ShaplEIG but it integrates the fact that Shapley values depend only on the odd component of the value function of the game. Experiments show the effectiveness of ShapleyOG in reducing the computation time while maintaining comparable accuracy results.

Critical strengths

The paper is well-written and easy to follow. The authors introduce all the necessary background and ideas before presenting ShapleyOG. Section 3 first reports a series of backbone theoretical results that justify the construction of the algorithm and provide computational costs for the operations/subroutines involved then the procedure itself. Section 4 reports the experimental results. While the ideas used in constructing ShapleyOG are not completely novel I find the analysis quite interesting. The authors first shows that using Gaussian Processes (GP) with Hamming kernels as surrogates basically allow to restricting to the odd component (as known for the actual Shapley values), and then devise a way to fit the odd GP to the odd components. The analysis is completed with numerical considerations on how to compute covariances.

Critical weaknesses

The ideas behind the work are not exactly novel, even if the analysis has its own value. The experimental evaluations are interesting but I had to get to the appendix to understand the meaning of the games that the authors use: I understand that a reader more expert than me in this literature could not see it as a problem but a small description of the dataset in the main body could be of help.

Questions for authors

The authors leave as future question one that would be interesting to answer and would strenghten this work: ShapleyOG is dominated by non-adaptive estimators on some small games, especially at large budgets. They state that it is unclear which structural properties of a game are responsible: Why do you think intrinsic properties of the games are the culprits here? Do you have any intuition/insights?

1 comment

We thank the reviewer for the very positive assessment and the careful reading.

W (description of the games in the main text). We have added a short description to Section 4.1: all games are local explanations of machine learning models, where the players are the input features (image patches, words, or tabular features) and the value function is the model's prediction for a single instance given only the features of a coalition. We have also rewritten the detailed description of the games in Appendix E.1 to enhance clarity.

Q (game properties behind the cases in which ShapleyOG is outperformed). First, a more precise statement of the observation: on average, ShapleyOG is outperformed only on games with at most 20 players and there predominantly at the larger budgets (Table 5, Figure 4). On these games, the considered budgets are tens to several hundred times the number of players and, on the smallest of them, a substantial share of all coalitions. Even for games of the same size and at the same budget, however, the average ranking of ShapleyOG relative to the competing estimators is not always the same, so characteristics of the individual games must play a role. Which characteristics are decisive is still open. Our current hypothesis is that the estimation passes through two phases, of which the second is reached within the considered budgets only on small games. In an early phase, the main effects of the individual players have to be inferred from few evaluations, and the Hamming kernel GP with its player-specific lengthscales is very sample-efficient at this. In a later phase, the main effects are well determined and the remaining error stems from higher-order interactions. The Hamming kernel has one lengthscale per player and no parameters of its own for interactions (Equation 2), which may limit it in this second phase, whereas some of the competing estimators can catch up. Testing this hypothesis requires controlled experiments. One possible direction for improvement is a surrogate with additional parameters that control higher-order interactions more explicitly [1, 2], while avoiding computations with exponential cost in the number of players. Both are beyond the scope of this paper. We believe, however, that this indicates further potential of the approach, which we plan to investigate in future work.

References:

  • [1] Duvenaud, D. K., Nickisch, H., & Rasmussen, C. E. (2011). Additive Gaussian processes. Advances in Neural Information Processing Systems, 24.
  • [2] Lu, X., Boukouvalas, A., & Hensman, J. (2022). Additive Gaussian processes revisited. In International Conference on Machine Learning (pp. 14358–14383). PMLR.
Reviewer_pNq2OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes ShapleyOG based on an already developed ShaplEIG to accelerate adaptive Shapley value estimation. ShapleyOG restricts the Gaussian processes to its odd component and refitts the GP only at powers of two and using bordered Cholesky / Sherman–Morrison updates in between.

Critical strengths
  1. The paper is well-organized with good literature and experiments.
Critical weaknesses
  1. Limitations with existing methods are not clear in the introduction.
  2. The paper lacks an ablation study for the number of players (p).
  3. Superiority of odd GP over even and full GP has not been shown.
  4. Algorithm 1 refers to some equations that are in Appendix. A paper should include all main components in the main body.
  5. For Quadrature at Large p on page 9, this is the main claim of the paper (efficience for large p) while the results for this part is included in Appendix.
Questions for authors
  1. In the Abstract: "Shapley values are a central tool for attribution in machine learning. Since their exact computation requires evaluating the cooperative game to be explained on exponentially many player coalitions, they are typically estimated from a limited number of evaluations." what is the problem with estimation from a limited number of evaluations? it's not benefit from efficiency point of view?

  2. Why is just odd GP rather than even or full GP used?

1 comment

We thank the reviewer for the constructive comments; all changes are in the revised PDF.

Q1 (problem with limited evaluations). We agree that estimation from a limited number of evaluations is not an issue in itself: it is what makes Shapley values accessible at all for games with many players or costly value functions, and the sentence describes this setting. The point we wanted to make is that, as in every estimation task, the limited budget introduces an estimation error, and that estimators differ in how quickly they reduce this error per evaluation and per unit of computation time, which is what the paper is about. We have rephrased the abstract to make this explicit.

Q2 and W3 (even and full GP). The reviewer asks why only the odd GP is used, rather than the even or the full GP.

Regarding the full GP, for given hyperparameters and paired observations, the odd GP yields exactly the same SV posterior (Theorem 2) and the same EIG for candidate coalition pairs (Theorem 3) as the full GP, from half as many observations. The two differ only in how the hyperparameters are learned: ShapleyOG fits them to the odd targets only, which is cheaper and more appropriate, as only the odd component matters for the SVs. The ablation study already examines how this different hyperparameter fit and the dependence on paired observations affect the accuracy and the overhead (Section 4.2, Appendix F.4): all variants except ShapleyOG itself use the full GP; "+ paired acquisition" differs from ShapleyOG only in the surrogate and its hyperparameter fit, and "+ GL quadrature" additionally selects single coalitions instead of pairs. It shows comparable accuracy on average (Table 10: geometric mean NMSE of 1.2e-4 and 1.1e-4 vs. 1.2e-4 for ShapleyOG, with per-game differences in both directions), while ShapleyOG reduces the overhead to around one third. We have now stated the role of the full GP explicitly in Section 4.2 and Appendix E.5.

Regarding the even GP, Shapley values depend only on the odd component of the game (Section 3.1; Fumagalli et al., 2026a), and an even surrogate would therefore yield zero Shapley values regardless of the observations (Proposition B.2 in B.5 and Equation 4), i.e., it provably carries no information about them and is not a meaningful surrogate. We have now stated this explicitly in Section 3.1.

W1 (limitations of existing methods). Thank you for raising this. We have clarified the limitations of existing estimators in Section 1. The vast majority of existing estimators select the coalitions to evaluate non-adaptively, i.e., independently of the observed values and of the specific players involved, such that the evaluation budget may be spent on coalitions that are uninformative about the Shapley values, which is especially wasteful when evaluations are costly. ShaplEIG, the adaptive alternative, selects informative coalitions but incurs an overhead that grows faster than the budget and the number of players, which restricts it to costly games with small budgets; this is the gap that ShapleyOG closes.

W2 (number of players). The effect of the number of players was already studied in detail: the 15 games of the main experiment range from 13 to 111 players (Table 4, Appendix E.1), and the quadrature study examines a game with 1024 players (Figure 3 left, Appendix F.5). Results per game, and thus per number of players, are given in Figure 1 (right), Figure 4 and Table 5 (Appendix F.1), and the dependence of the overhead on the number of players in Figure 2 (right, top) and Table 8 (Appendix F.3); the ablation (Section 4.2, Table 9) also shows that the speed-up over ShaplEIG grows with the number of players. In short, the overhead of ShapleyOG grows with the number of players, and, for the considered budgets, its accuracy advantage is most pronounced on the games with many players, whereas on some of the smaller games at high budgets it is even outperformed by non-adaptive estimators (as noted in the conclusion).

W4 (Algorithm 1 and the appendix). All components of Algorithm 1 are described in the main text, so its references to the appendix were not necessary. We have changed the references accordingly to avoid confusion; the appendix is now referred to only from the text, not from the pseudo-code of Algorithm 1.

W5 (quadrature at large pp). Thank you for this suggestion. We have moved the essential part of the quadrature study into the main text (Figure 3, left, in Section 4.2). However, the efficiency at large pp is only one of several contributions rather than the main claim of the paper, which is the overall overhead reduction of adaptive estimation, also due to the odd GP, the refit schedule, and the efficient EIG updates.

We hope these clarifications and additions address the concerns and would be grateful if the reviewer reconsidered the overall rating and the presentation and soundness scores in their light.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the revision

We thank all reviewers for their constructive feedback. We have uploaded a revised PDF and updated supplementary code. The main changes are listed below; our individual responses to the reviews point to the exact locations.

In response to the reviews

  • Complementary contribution sampling (Zhang et al., 2023) added as baselines to the main experiment, with the choice of the CCN variant explained (Section 4, Appendix F.7) [FnQi].
  • Ablation of ShapleyOG against its non-adaptive counterpart, i.e., the same odd GP with random paired sampling (Section 4.2, Figure 3 right, Appendices E.5 and F.6) [FnQi].
  • Equivalence of ShapleyOG to a batched acquisition approach explained, which extends the total computation time analysis to batched and parallel evaluation (Sections 3.3 and 4.2, Appendix E.4), and a new real-time experiment with batched evaluation of a live model and varying evaluation costs (Appendix F.8) [FnQi].
  • Summary table of the quadrature study added to the main text (Figure 3 left, Appendix F.5) [pNq2].
  • Clearer descriptions and explanations, e.g., of the limitations of existing estimators (Section 1), the problem statement (abstract), the references of Algorithm 1 (Section 3.3), and the role of the full GP in the ablation path (Appendix E.5) [pNq2], and a description of the games (Section 4.1, extended details in Appendix E.1) [HZ2v].

Independent of the reviews

  • Experiments: all experiments were rerun with 4 threads per run (previously 1) for a more realistic setup, and all figures and tables were updated accordingly. The ablation path now covers all 15 games (previously 5) and the quadrature study 10 seeds (previously 5) for more representative results (Section 4.2, Appendices F.4 and F.5). The headline numbers changed accordingly (e.g., the speed-up over ShaplEIG is now 233–1634x instead of 388–1250x); the conclusions are unchanged.
  • Writing: sentences and passages were restructured or rewritten for readability and clarity, mainly in the appendix and at some places in the main text (e.g., the order of the paragraphs in Section 3.3, the parameterization of the integral for the linear term in Section 3.2). The appendix was restructured and extended: the computation scheme of ShaplEIG (Appendix A.2), more detailed proofs and implementation details (Appendices B and C), the cost tables split and refined for a clearer comparison with ShaplEIG (Appendix D.2), the Sherman–Morrison updates of the former Appendix D.4 removed (see below), and further experimental details (Appendix E).
  • Corrections, none of which affect the empirical results to the disadvantage of ShapleyOG: (i) The submitted version described the final term of the EIG as updated via the Sherman–Morrison formula, while the experiments had inadvertently resorted to an alternative route that recomputes it. We re-evaluated both variants, decided against the Sherman–Morrison updates for numerical reasons, and adjusted the description and the stated costs (Section 3.3, Appendix D); despite the higher theoretical cost, the measured overhead did not suffer (Section 4.2, Table 8). (ii) The ablation path and the quadrature study use the ESP computation scheme of ShaplEIG for the SV prior covariances, whose linear term we had implemented in O(p^3), following the ShaplEIG implementation, for numerical accuracy; a numerically stable O(p^2) implementation has since been presented (Mohammadi et al., 2025), which we reimplemented and reran for a fair comparison (Appendix C.7). (iii) The reported overhead of ShapleyOG now also includes the candidate resampling and the final refit and posterior computation (Appendix E.4). (iv) In the "+ paired acquisition" variant of the ablation path, the rank-one updates of the posterior covariances were not applied as intended; this is fixed and the variant rerun (Appendix F.4).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.