Breaking the Speed-Accuracy Tradeoff in Shapley Interaction Estimation

Introduction

Cooperative game theory has quietly become the standard mathematical language for explaining machine learning models. When we want to know how much a single feature contributes to a prediction, or how much a training point contributes to model performance, we reach for Shapley values or Banzhaf values. These cardinal-probabilistic values rest on solid axiomatic foundations and have spread across feature attribution, data valuation, and beyond. But singleton attributions tell an incomplete story. They cannot capture the synergies and redundancies between features, and in models like the vision-language system SigLIP-2, the interaction between an image patch and a text token may carry more meaning than either in isolation.

This is where interaction indices come in, generalizing probabilistic values from single elements to subsets. The catch is computational. Computing these quantities exactly requires evaluating the value function across all 2^n subsets, which is intractable for any realistic feature count. The paper I want to discuss, "Proxy-Based Approximation of Shapley and Banzhaf Interactions" by Thies, Baniecki, Witter, Hüllermeier, Muschalik, and Fumagalli, introduces ProxySHAP, an estimator designed to resolve a tension that has constrained the entire field: existing methods are either fast or accurate, rarely both.

The Tradeoff That Defined Prior Work

To appreciate the contribution, it helps to understand the two camps of existing estimators and why each falls short.

The first camp is sampling-based methods. SHAP-IQ generalizes Maximum Sample Reuse (MSR) to interactions. It is efficiently computable and unbiased, but the variance is the problem. The authors note that its variance scales quadratically with the magnitude of the value function, and crucially, this variance compounds for higher-order interactions. So while you can run it cheaply, the estimates you get for third- and fourth-order interactions are noisy enough to be unreliable without enormous budgets.

The second camp is regression-based methods like KernelSHAP-IQ. These are accurate in principle, but they need to fit a coefficient for every higher-order term being estimated. The number of such terms grows combinatorially, so the sample budgets required to fit them well become impractical. KernelSHAP-IQ also carries a quadratic time complexity in n, which makes scaling to thousands of features painful.

A third, more recent line of work uses surrogate or proxy models to approximate the value function ν with a cheaper-to-evaluate ˆν. ProxySPEX, for instance, fits a tree surrogate and extracts Fourier coefficients. But this approach has two weaknesses. First, extracting these coefficients scales exponentially with tree depth, forcing aggressive truncation that throws away accuracy. Second, and more subtly, even with perfect Fourier coefficients, you would recover the interactions of the surrogate ˆν, not the true function ν. The proxy introduces a bias that is never corrected.

This is the precise gap ProxySHAP targets.

How ProxySHAP Works

ProxySHAP operates in two phases, and understanding both is the key to seeing why it succeeds.

Phase 1: Fit a tree-based proxy. The method samples binary coalitions and their corresponding game values, then fits a gradient-boosted tree ensemble (XGBoost, LightGBM, and similar) as a regression proxy. Trees are extremely sample-efficient at capturing structured dependencies, which is exactly what you want when each evaluation of ν is expensive.

The central theoretical contribution lies in how interactions are extracted from this proxy. The authors derive a polynomial-time generalization of interventional TreeSHAP that computes exact interaction indices for tree ensembles. This matters because prior tree-based extraction methods suffered from exponential dependence on tree depth. By bypassing that bottleneck, ProxySHAP can read off exact interactions from the proxy at scale. I find this the most quietly important part of the work. A polynomial-time exact algorithm for arbitrary-order interactions over tree ensembles is a structural result that stands on its own, independent of the surrogate framing.

Phase 2: Residual correction via MSR. Here is where the proxy bias problem gets solved. Because the proxy interactions are only approximations of the true interactions, ProxySHAP applies a residual adjustment. It uses Maximum Sample Reuse on the residuals between the proxy and the true game values. This is the path to consistency: as budget grows, the residual correction drives the estimate toward the true interaction values rather than getting stuck at the proxy's interactions.

The subtlety the paper formalizes is when this correction is safe. Naively, you might worry that applying MSR to residuals inherits the same variance explosion that plagued SHAP-IQ at high interaction orders. The authors characterize the specific conditions under which residual MSR corrects proxy bias without variance scaling exponentially in interaction size. In other words, the proxy does the heavy lifting on the structured part of the signal, and the residual is small and well-behaved enough that correcting it does not reintroduce the variance catastrophe. This conditional guarantee is what lets the method win in both budget regimes at once.

Results and What They Imply

The empirical claims are strong. ProxySHAP reportedly achieves the lowest approximation error in both small-budget and large-budget regimes, outperforming ProxySPEX and KernelSHAP-IQ, and it scales to applications with thousands of features. The headline demonstration is a SigLIP-2 explanation using only 2048 model calls, recovering token interactions between image patches and text tokens that singleton attributions cannot represent.

What I think is underappreciated here is the architecture of the win. Most estimators in this space pick a single mechanism and live with its tradeoff curve. ProxySHAP composes two mechanisms with complementary failure modes. The tree proxy is biased but low-variance and sample-efficient; residual MSR is unbiased but potentially high-variance. By having the proxy absorb most of the structure, the residual that MSR must handle is small, which is precisely the regime where MSR variance is manageable. This is a divide-and-conquer strategy applied to the bias-variance decomposition itself, and I expect the pattern to generalize beyond Shapley interactions to any setting where you have a cheap structured approximator and an expensive unbiased corrector.

My Take and Some Open Questions

Several things stand out to me beyond the paper's stated results.

First, the reliance on a tree ensemble proxy is both a strength and a hidden assumption. Trees excel when the value function has low-order, axis-aligned interaction structure. For functions with dense, high-order interactions that trees cannot represent efficiently, the proxy bias will be large, the residual will be large, and the MSR correction will face exactly the variance problem the method is trying to avoid. The conditional nature of the variance guarantee is honest about this, but it means ProxySHAP's dominance is partly a statement about the structure of real-world value functions, namely that they tend to be approximately sparse in interaction order. I would want to see adversarial cases where this assumption breaks.

Second, the interventional TreeSHAP extension deserves attention on its own terms. The interventional versus observational distinction in TreeSHAP has real consequences for what the attributions mean, particularly under feature correlation. The choice of the interventional variant suggests the authors are prioritizing a clean causal-style marginalization, which I think is the right call for interpretability but worth flagging for practitioners who assume all Shapley estimates are interchangeable.

Third, there is a practical question about proxy fitting cost. The method counts model calls, but fitting and querying the tree ensemble at high interaction orders has its own compute footprint. For very large n, the number of interaction terms one might want to extract grows quickly even if each extraction is polynomial-time. The reported scaling to thousands of features is encouraging, but the constants and the practical limits on interaction order would shape adoption.

Conclusion

ProxySHAP makes a clean argument: stop choosing between fast and accurate, and instead compose a fast biased estimator with a slow unbiased corrector so that each operates in its favorable regime. The polynomial-time interventional TreeSHAP extension removes a longstanding exponential bottleneck, and the formal characterization of when residual MSR stays well-behaved turns an intuition into a guarantee. The result is an estimator that performs across budget scales and reaches into genuinely high-dimensional settings like vision-language models.

The open frontier, in my view, is understanding the limits of the structural assumption baked into the proxy. If real value functions are usually low-order-sparse, ProxySHAP will dominate. The interesting research question is how to detect, online, when you are in a regime where that assumption fails, and whether the proxy itself can signal its own unreliability before the residual correction is overwhelmed. That diagnostic capability would turn a strong estimator into a trustworthy one.