Proxy-Based Approximation of Shapley and Banzhaf Interactions
Santo M. A. R. Thies, Hubert Baniecki, R. Teal Witter, Eyke Hüllermeier, Maximilian Muschalik, Fabian Fumagalli · 2026
Read Proxy-Based Approximation of Shapley and Banzhaf Interactions by Santo M. A. R. Thies, Hubert Baniecki, R. Teal Witter, Eyke Hüllermeier, Maximilian Muschalik, Fabian Fumagalli (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-22738.txt.
Introduction
Thies and others present ProxySHAP, a tool for Shapley and Banzhaf interactions that joins tree proxy speed with a sound path to consistency through residual fixes. They extend interventional TreeSHAP to polynomial time exact interaction indices for tree ensembles, dodging exponential depth effects in earlier methods. Analysis pins down when maximum sample reuse corrects proxy bias without variance exploding with size. Benchmarks show it setting a new top mark for quality at small and large budgets, beating ProxySPEX and KernelSHAP-IQ on downstream uses.
Catalog record
| CREATOR | Santo M. A. R. Thies, Hubert Baniecki, R. Teal Witter, Eyke Hüllermeier, Maximilian Muschalik, Fabian Fumagalli |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 126806 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.22738
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Proxy-Based Approximation of Shapley and Banzhaf Interactions Santo M. A. R. Thies, Hubert Baniecki, R. Teal Witter, Eyke Hüllermeier, Maximilian Muschalik, Fabian Fumagalli Abstract Shapley and Banzhaf interactions capture the complex dynamics inherent in modern machine learning applications. However, current estimators for these higher-order interactions trade off between speed and accuracy. To overcome this limitation, we introduce ProxySHAP. ProxySHAP reconciles the high sample efficiency of tree-based proxy models with a principled path to consistency via residual correction. On a theoretical level, we derive a polynomial-time generalization of interventional TreeSHAP to compute exact interaction indices for tree ensembles, successfully bypassing exponential tree-depth dependencies in prior methods. Furthermore, we formally analyze the residual adjustment strategy, characterizing the specific conditions under which Maximum Sample Reuse (MSR) corrects proxy bias without its variance scaling exponentially with interaction size. Extensive benchmarking demonstrates that ProxySHAP sets a new state-of-the-art standard for approximation quality, including in large-scale applications with thousands of features. By achieving the lowest error in both small- and large-budget regimes, ProxySHAP significantly outperforms the prior best estimators ProxySPEX and KernelSHAP-IQ, while also delivering superior performance on downstream explainability tasks. 1 Introduction With the growing integration of artificial intelligence into critical decision-making processes across healthcare and finance, the demand for transparency and trustworthiness has never been higher. To interpret the often opaque dynamics of these models, the field has coalesced around cooperative game theory as the de facto standard [ 37 , 41 , 49 , 42 ] . Specifically, Shapley values [ 53 ] and Banzhaf values [ 3 ] , fundamental instances of cardinal-probabilistic values , provide a rigorous axiomatic framework for attribution. These concepts are ubiquitous in modern machine learning, serving as the cornerstone for tasks such as feature attribution [ 55 , 37 ] and data valuation [ 49 , 25 ] . Formally, we consider a set N=\{1,\dots,n\} consisting of n entities, such as input features or training data points. The theoretical foundation of these explanations rests on a value function, \nu:2^{N}\to\mathbb{R} , which assigns a scalar score to any subset (or coalition) S\subseteq N . The interpretation of \nu depends on the application: in feature attribution, \nu(S) typically represents the model’s prediction when features in N\setminus S are masked or marginalized out; in data valuation, \nu(S) corresponds to the utility, such as test accuracy or negative loss, of a model trained exclusively on the subset of data points S . To summarize the complicated dynamics of the value function, cardinal-probabilistic values quantify the marginal effect of each entity i on the model’s output. Formally, the attribution to i is a weighted sum of its marginal contributions across all possible subsets: \displaystyle\phi^{p}_{i}(\nu):=\sum_{T\subseteq N\setminus\{i\}}p_{t}(n)\Delta_{i}\nu(T), (1) where \Delta_{i}\nu(T)\coloneqq\nu(T\cup\{i\})-\nu(T) denotes the discrete derivative of \nu at coalition T with respect to i , and t:=|T| is the cardinality of T . Setting the weights to p_{t}(n)=\frac{1}{n\binom{n-1}{t}} yields the Shapley value, while p_{t}(n)=\frac{1}{2^{n-1}} yields the Banzhaf value. More generally, with the constraint that the non-negative weights sum to one, \phi^{p}_{i}(\nu) can be interpreted as the expected marginal contribution of entity i under a specific distribution over coalition sizes. While probabilistic values are useful for understanding individual contributions, they are inherently limited to singleton effects and often fail to capture the rich, higher-order dependencies between elements. For instance, in vision-language similarity models such as SigLIP-2 [ 59 ] , interactions between image and text patches are not captured by probabilistic values [ 2 ] , as illustrated in Fig. 1 . To capture these complex dynamics, recent research has shifted toward richer explanations grounded in higher-order terms. These concepts have seen rapid adoption for quantifying feature interactions [ 58 , 16 , 44 ] , cross-modal interactions in vision-language models [ 2 , 26 ] , data valuation [ 4 ] , language modelling [ 54 , 52 ] , and even hyperparameter optimization [ 62 ] . Cardinal-probabilistic interaction indices naturally generalize probabilistic values to arbitrary subsets [ 14 ] . Rather than isolating the marginal contribution of a singleton, they quantify the contribution of a subset S\subseteq N as it is added to a coalition T : \displaystyle\phi^{p}_{S}(\nu):=\sum_{T\subseteq N\setminus S}p_{t}^{s}(n)\Delta_{S}\nu(T), (2) where \Delta_{S}\nu(T) denotes the discrete derivative of \nu at T with respect to the subset S . Analogous to the singleton case, specific weight choices allow us to recover the Shapley interaction index [ 19 ] and the Banzhaf interaction index [ 19 ] . For s=1 , the interaction weights reduce to p_{t}(n) . 1.1 Estimating Cardinal-Probabilistic Interactions Figure 1 : Left: A ProxySHAP explanation of the SigLIP-2 model using only 2048 model calls. Right: In Phase 1 , we fit a regression proxy model using sampled binary coalitions and game values. In Phase 2 , we extract proxy interactions and, when appropriate, adjust them using residual estimates. Computing probabilistic values and interactions is computationally prohibitive for large n , as it requires evaluating the value function \nu(T) across all 2^{n} subsets. Consequently, researchers rely on algorithms that produce estimates using a fixed evaluation budget. For probabilistic values, there are numerous estimators such as Monte Carlo sampling [ 56 ] , maximum sample reuse (MSR) [ 60 ] , permutation sampling [ 7 ] , and regression-based approaches like KernelSHAP [ 37 , 10 , 45 ] . While historically sparse, recent work on estimating probabilistic interactions is expanding to explain the complex, higher-order dependencies inherent in modern machine learning. Yet, current estimators are generally either fast or accurate, but not both. SHAP-IQ [ 16 ] generalizes MSR to interactions, being efficiently computable, but notoriously inaccurate: its variance scales quadratically with the value function’s magnitude, which we find compounds further for higher-order interactions. Conversely, regression approaches like KernelSHAP-IQ [ 17 ] are accurate but require impractical sample budgets to adequately fit the large number of higher-order terms. Additionally, KernelSHAP-IQ remains computationally expensive, suffering a quadratic time complexity dependence on n . To circumvent these bottlenecks, recent work leverages surrogate models \hat{\nu} to approximate \nu [ 4 , 63 ] . ProxySPEX [ 4 ] extracts Fourier coefficients from a tree surrogate, which scales exponentially with depth, necessitating aggressive, accuracy-compromising truncation. Additionally, even with the exact Fourier coefficients, ProxySPEX would return the interaction of \hat{\nu} rather than the underlying function \nu . RegressionMSR [ 63 ] elegantly resolves this by directly extracting the values from the tree and employing MSR to estimate the residual values of \nu-\hat{\nu} . Despite its state-of-the-art performance for probabilistic values , RegressionMSR is restricted to singleton effects. Extending this residual-correction framework to higher-order interactions requires efficient interaction extraction from tree proxies. While an algorithm for extracting Shapley interaction indices (a particular cardinal-probabilistic interaction) exists [ 65 ] , it is ill-suited for general cardinal-probabilistic interactions (e.g., those used for vision tasks as shown in Fig. 1 ). 1.2 Our Contributions Currently, estimators of higher-order interactions trade off between speed and accuracy. In this work, we propose the state-of-the-art interaction estimator ProxySHAP , extending three recent works to produce fast and accurate estimates: We use the maximum sample reuse (MSR) method generalized to interactions by [ 16 ] . While inaccurate on its own, we combine MSR with the surrogate model and residual estimation strategy of [ 63