An Odd Estimator for Shapley Values Fabian Fumagalli 1 2 Landon Butler 3 Justin Singh Kang 3 Kannan Ramchandran 3 R. Teal Witter4 Abstract The Shapley value is a ubiquitous framework for attribution in machine learning, encompassing fea- ture importance, data valuation, and causal infer- ence. However, its exact computation is generally intractable, necessitating efficient approximation methods. While the most effective and popular estimators leverage thepaired samplingheuristic to reduce estimation error, the theoretical mech- anism driving this improvement has remained opaque. In this work, we provide an elegant and fundamental justification for paired sampling: we prove that the Shapley value dependsexclusively on the odd component of the set function, and that paired sampling orthogonalizes the regres- sion objective to filter out the irrelevant even com- ponent. Leveraging this insight, we propose Odd- SHAP, a novel consistent estimator that performs polynomial regression solely on the odd subspace. By utilizing the Fourier basis to isolate this sub- space and employing a proxy model to identify high-impact interactions, OddSHAP overcomes the combinatorial explosion of higher-order ap- proximations. Through an extensive benchmark, we find that OddSHAP achieves state-of-the-art estimation accuracy at larger sampling budgets. 1. Introduction As machine learning models are increasingly deployed in high-stakes domains, from healthcare and finance to crimi- nal justice, the need to understand their decision-making pro- cesses has become paramount (Doshi-Velez & Kim, 2017). To address the opacity of these complex systems, the Shap- ley value has emerged as thede factostandard framework 1Department of Statistics, LMU Munich 2MCML 3Department of Electrical Engineering and Computer Science, UC Berkeley 4Mathematical Sciences Department, Claremont McKenna College. Correspondence to: Fabian Fumagalli , R. Teal Witter . Proceedings of the 43 rd International Conference on Machine Learning, Seoul, South Korea. PMLR 306, 2026. Copyright 2026 by the author(s). for explanation. Its rigorous game-theoretic foundation has made it ubiquitous across distinct tasks, including at- tributing model predictions to input features (Strumbelj & Kononenko, 2010; Lundberg & Lee, 2017), quantifying the contribution of training points to model performance (Ghorbani & Zou, 2019), and estimating the causal effect of variables in structural causal models (Janzing et al., 2020; Heskes et al., 2020). Let d denote the number of players, indexed by [d] = {1, . . . , d}. We define a value function f: 2 [d] →R that assigns a scalar payofff(S) to every coalitionS⊆[d] . This abstraction unifies various attribution tasks; depending on the context, f(S) may represent: The prediction of a model masked to only include features in S. The loss of a model trained exclusively on the data points in S. The expected outcome of a structural causal model under an intervention on the variables inS. In all these settings and more, the value function f implic- itly encodes complex higher-order interactions across the 2d possible subsets. To disentangle these dynamics and at- tribute the total value to individual players, we turn to the Shapley value. It offers a principled attribution framework, uniquely characterized as the only method satisfying the axioms ofefficiency,symmetry,dummy, andlinearity(Shap- ley, 1953). For any player i∈[d] , the Shapley value of f is defined as the weighted average of marginal contributions: ϕi(f) = X S⊆[d]\{i} p|S|[f(S∪ {i})−f(S)],(1) where pℓ = 1 d d−1 ℓ −1 . Computing Equation (1) directly in- volves summing exponentially many terms, rendering exact evaluation intractable for general functionsf. This work specifically targets the general, model-agnostic paradigm, operating under the assumption that the target function f possesses no known or accessible architecture. In this model-agnostic paradigm, the Shapley value must be estimated for medium to large values ofd. In contrast, struc- tural information about f can be leveraged to make precise calculations mathematically tractable for all d (Rozember- czki et al., 2022). When such structural blueprints are avail- able, researchers have successfully bypassed approxima- tion entirely by designing highly tailored, exact algorithms. Examples of these bespoke solutions span multiple archi- 1 arXiv:2602.01399v2 [cs.LG] 29 May 2026 An Odd Estimator for Shapley Values መ𝑓 ≈ ≈ 𝑓 Kernel SHAP/Leverage SHAP Odd SHAP Function Estimate መ𝑓odd 𝜙𝑖( መ𝑓) Paired Sampling Poly SHAP ≈ መ𝑓 𝜙𝑖( መ𝑓) 𝜙𝑖( መ𝑓odd) መ𝑓 Linear fit Select odd fit Polynomial fit Figure 1.OddSHAP balances expressive power with efficiency by only fitting theoddcomponent of the value function. tectures, including K-nearest neighbor approaches for data valuation (Jia et al., 2019; Wang et al., 2023; 2024), graph neural networks (Muschalik et al., 2025), Gaussian pro- cesses (Mohammadi et al., 2025), and linear models (Strum- belj & Kononenko, 2014). The decision tree domain has similarly benefited from specialized exact methods, most no- tably TreeSHAP (Lundberg et al., 2020; Yu et al., 2022) and its subsequent adaptations for mapping feature interactions (Zern et al., 2023; Muschalik et al., 2024b). 1.1. Surrogate Estimators The most effective estimators typically rely on function class approximations: they fit astructuredsurrogate model ˆf≈f and return its exact Shapley values, ϕi( ˆf), as the estimate. Crucially, the function class must be structured enough that exactly computing the Shapley values of ˆfis efficient. KernelSHAP (Lundberg & Lee, 2017) and LeverageSHAP (Musco & Witter, 2025) can be viewed through this lens; they exploit a specific weighted linear regression prob- lem whose coefficients recover the exact Shapley values (Charnes et al., 1988). Consequently, these estimators sat- isfy aconsistencyproperty: as the sample budget approaches the full coalition space (m→2 d), they converge to the true Shapley values. Although practical budgetsmare often or- ders of magnitude smaller than2d, this theoretical guarantee appears to be a crucial driver of estimation performance. Recent advancements have sought to extend this regression framework to more expressive function classes. Methods such as FourierSHAP (Gorji et al., 2025), ProxySPEX (But- ler et al., 2025), and RegressionMSR (Witter et al., 2025) replace the linear basis with sparse Fourier representations or gradient boosted trees (GBTs). If the model class is cor- rectly specified—i.e., if f is truly an exact sparse Fourier function or a tree ensemble—the best approximation ˆf co- incides withf, ensuring thatϕ i( ˆf)is consistent. However, in the general setting,f rarely falls within these restricted classes. Consequently, simple proxy-based esti- mates are subject to model misspecification bias; even with an infinite query budget, ϕi( ˆf) may not converge to ϕi(f). RegressionMSR addresses this limitation by introducing a residual adjustment term that makes its final estimate consis- tent, achieving significantly higher accuracy in the large-m regime compared to unadjusted proxy methods. Recent work has extended the linear regression strategy of KernelSHAP and LeverageSHAP to polynomial regression (Fumagalli et al., 2026). Like both linear methods, the re- sulting PolySHAP estimator is consistent: Fumagalli et al. (2026) show that the Shapley values of the bestpolynomial approximation to f, under a specific weighting and con- straint, are the Shapley values of f itself. While PolySHAP demonstrates superior performance by capturing higher- order interactions, it faces a scalability bottleneck; the com- putational cost of the regression scales quadratically with the size of the polynomial basis. 1.2. Our Work Our work aims to circumvent this complexity barrier while retaining the expressive power and consistency of higher- order approximations. To achieve this, we exploit a funda- mental structural property: the decomposition of the value function into odd and even components. A set function f isoddif f(S) =−f(S c) andevenif f(S) =f(S c) for all S⊆[d] , where Sc := [d]\S is the complement. Every f admits a unique decomposition into odd and even components,f=f odd +f even, with fodd(S) = f(S)−f(S c) 2 ;f even(S) = f(S) +f(S c) 2 . 2 An Odd Estimator for Shapley Values Table 1.Average MSE for Shapley value estimators withm≈100d. OddSHAP achieves the lowest average rank. DistilBERT (d= 14) Estate (d= 15) ViT16 (d= 16) Cancer (d= 30) IL60 (d= 60) CG60 (d= 60) NHANES (d= 79) Crime (d= 101) Avg. Rankm1440 1722 1705 2281 5521 5521 5864 11126–MSR7.5×10 −4 2.8×10−2 1.2×10−4 2.2×10−2 3.5×10−3 2.1×10−3 4.7×10−2 3.6×101 7.75SV ARM3.7×10 −4 3.3×10−2 5.7×10−5 3.5×10−3 2.2×10−3 9.7×10−4 4.0×10−2 1.5×101 6.75PermutationSampling6.2×10−4 5.3×10−3 1.2×10−4 1.1×10−4 1.3×10−4 1.4×10−4 3.5×10−3 2.7×100 5.62LeverageSHAP 7.7×10−5 3.4×10−4 3.5×10−5 3.2×10−5 2.6×10−5 2.5×10−5 6.2×10−4 7.5×10−1 3.25PolySHAP-38.0×10 −5 3.2×10−7 3.8×10−5 4.0×10−5 3.25RegressionMSR 3.1×10−5 1.3×10−5 1.0×10−5 3.0×10−4 9.7×10−6 7.6×10−5 2.4×10−4 5.6×10−1 2.62Proxy3.6×10 −4 3.3×10−5 4.6×10−5 4.2×10−4 4.9×10−5 2.9×10−4 7.0×10−4 5.3×100 5.00FFD-RD1.6×10 −3 1.8×10−6 5.3×10−4 6.4×10−7 5.75FFD-RD-Corrected1.8×10−3 6.8×10−5 8.50FourierSHAP1.9×10 −2 3.0×10−2 4.9×10−3 7.7×10−2 4.1×10−3 8.5×10−3 1.7×10−1 1.9×102 9.12OddSHAP 4.6×10−5 5.1×10−7 1.3×10−5 4.2×10−6 1.6×10−6 6.2×10−6 5.8×10−5 1.3×10−1 1.50 Crucially, the Shapley value dependsexclusivelyon the odd component of the value function: ϕi(f) =ϕi(fodd)∀i∈[d]. This insight suggests a targeted estimation strategy: rather than approximating the full function f, which entails learning potentially complex but irrelevant even structures, we can restrict our approximation to the odd component, ˆfodd ≈f odd, and directly computeϕ i( ˆfodd). Remarkably, this insight clarifies the theoretical mecha- nism behindpaired sampling, a popular heuristic in which every sampled coalition S is paired with its complement Sc. While empirical studies show paired sampling greatly improves estimation performance (Covert & Lee, 2021; Mitchell et al., 2022; Olsen & Jullum, 2026), the underly- ing structural mechanism driving this has remained opaque. We show that paired sampling implicitly performs an even- odd decomposition, isolating the relevant signal. Mayer & W¨uthrich (2025) proved that KernelSHAP with paired sam- pling exactly recovers Shapley values for value functions with interactions of at most degree 2, but left the analysis of higher-order interactions open. Subsequently, Fumagalli et al. (2026) demonstrated that a first-order polynomial ap- proximation with paired sampling is equivalent to a second- order approximation, conjecturing a general pattern: that for odd k, an order-k fit with paired sampling is equivalent to order-(k+ 1). We answer this conjecture in the affirmative and provide a fundamental explanation: paired sampling orthogonalizes the regression problem, separately fitting the odd and even components off. Since the Shapley value of the even component vanishes, paired sampling effectively isolates the signal relevant to the Shapley value. Beyond elucidating the mechanics of paired sampling, we leverage this decomposition to design a more precise Shap- ley value estimator. Our objective is to reduce the computa- tional complexity of polynomial regression by restricting the model solely to odd terms. However, the standardunanim- ity basis—employed by KernelSHAP, LeverageSHAP, and PolySHAP—is ill-suited for this task, as its individual basis functions do not cleanly decouple into odd and even com- ponents. To overcome this, we reformulate the regression problem in theFourier basis. This basis offers a decisive structural advantage: a basis function is odd if and only if its interaction order is odd. Specifically, Fourier terms of odd cardinality are odd functions, while those of even car- dinality are even. Consequently, we can efficiently isolate the relevant signal by restricting the polynomial regression exclusively to odd-order Fourier terms. Even within the restricted odd subspace, the number of can- didate terms remains prohibitive; for example, there are d 3  distinct third-order interactions. Efficiently identifying the significant few is a challenge addressed by recent interaction detection methods such as SPEX (Kang et al., 2025), Fouri- erSHAP (Gorji et al., 2025), and ProxySPEX (Butler et al., 2025), which learn sparse approximations in the Fourier domain. Leveraging the efficiency of fitting decision trees, we incorporate ProxySPEX as a selection subroutine. Our proposed algorithm,OddSHAP, proceeds in two stages: first, it fits a GBT to the sampled coalitions to identify the dominant odd-order Fourier coefficients; second, it solves the polynomial regression problem restricted to this selected basis. Unlike pure proxy methods, OddSHAP produces a consistent estimator that retains the expressive power of higher-order polynomials. As demonstrated in Figure 2 and Table 1, this approach achieves state-of-the-art estimation accuracy on standard benchmarks given sufficient budgets. Our contributions can be summarized as follows: 1. Theoretical Unification of Paired Sampling:Lever- aging the insight that Shapley values depends strictly on the odd component of the value function, we provide the first general theoretical justification for the widely used paired sampling heuristic, proving that it implic- itly decouples the regression problem into independent odd and even objectives. This result generalizes prior findings limited to low-order interactions, revealing the structural mechanism that makes this heuristic so successful in practice. 2. The OddSHAP Estimator:We propose OddSHAP, a consistent estimator that performs polynomial regres- sion exclusively on a sparse selection of odd-order Fourier basis functions. By filtering out irrelevant even components and identifying high-impact interactions 3 An Odd Estimator for Shapley Values via a proxy model, OddSHAP retains the expressive power of higher-order polynomials without incurring their prohibitive combinatorial cost. 3. State-of-the-Art Performance:Through extensive experiments on standard benchmarks, we demonstrate that OddSHAP achieves state-of-the-art estimation ac- curacy under larger budgets. It significantly outper- forms higher-order PolySHAP in terms of computa- tional efficiency and surpasses the prior state-of-the-art method, RegressionMSR, in estimation accuracy. 2. Prior Work on Regression Formulations In this section, we review the notation and results needed to present our work. The foundational mechanism underpin- ning KernelSHAP, and its improved variant LeverageSHAP, is aweighted least squaresregression. Both strategies are grounded by a rigorous theoretical guarantee: Charnes et al. (1988) proved that the coefficients of the optimal constrained weighted linear approximation ˆf exactly recover the Shap- ley values of the original functionf, i.e.,ϕ i(f) =ϕi( ˆf). These frameworks operate using theunanimity basis, of- ten referred to as the M¨obius basis (Rota, 1964; Grabisch, 2016) in combinatorial contexts, where each basis function corresponds to a specific coalition T⊆[d] . Formally, the unanimity basis functionsu T : 2[d] →Rare defined as uT (S) =1[T⊆S]. Because a full basis expansion involves 2d terms, fitting the complete set is computationally intractable. Therefore, we restrict our focus to a sparse subset of interactions, denoted by the collectionT ⊆2[d]. We define FM (f,T) as the class of functions spanned by the unanimity basis restricted to T , subject to boundary con- straints. Specifically, every approximation g∈ FM (f,T) is constrained to match the ground truth f on the empty and full coalitions, ensuring the efficiency property. Formally, FM (f,T)= ( g= X T∈T uT αT :g(S)=f(S), S∈{∅,[d]} ) . Consider the collection of empty and singleton-coalitions T≤1 ={T⊆[d] :|T| ≤1} . Restricting the function to this class allows exact recovery of the Shapley values via a specific weighted and constrained linear regression problem. Theorem 2.1(Linear Regression (Charnes et al., 1988)). Let ˆfbe the best approximation inF M (f,T ≤1)tofi.e., ˆf= argmin g∈FM(f,T≤1) X S⊆[d]:0<|S| η·d) to detect and model interactions. In low sample budget scenarios, OddSHAP coincides with Proxy (LGBM), and yields comparable results with Regres- sionMSR or LeverageSHAP. When compared against the fixed-budget FFD framework,FFD-RDoutperforms Odd- SHAP and the flexible-budget methods within equivalent budget regimes across most tree-based value functions (Es- tate, Cancer, IL60, and CG60). However, its performance degrades substantially on deep learning-based value func- tions (DistilBERT and ViT). This performance split indi- cates that while feature interactions of order5 and higher are largely negligible for tree-based architectures, they remain highly active in deep neural networks, which we explicitly confirm by approximating the spectral energy in Section D.6. Interestingly, the adaptiveFFD-RD (corrected)variant per- forms significantly worse across almost all value functions, with ViT being the sole exception. Furthermore, because the budget of FFD scales quadratically (O(d2)), their strict sam- ple requirements expand drastically in high-dimensional settings, rendering them less practical as the feature di- mension d grows. In conclusion, OddSHAP provides a flexible-budget framework that adapts robustly across di- verse interaction structures, delivering highly competitive performance across all evaluated value functions. 5.2. Ablation of Evaluation Costs and Runtime To simulate diverse real-world applications, we vary the evaluation cost of f as T1 ∈ {0.001,0.01,0.1,1}seconds per evaluation. Although we evaluate f sequentially, we note that evaluation costs can be amortized through paral- lelization. Figure 3 reports the MSE (median with IQR) for the runtime of all algorithms and the smallest cost (T1 = 0.001s). We observe a similar pattern as in Figure 2, and provide other cost settings and datasets in Section D. 10 1 100 101 Runtime (seconds) 10 2 10 1 100 101 102 103 104 MSE (Median ± IQR Band) Crime (d = 101) MSR SVARM Permutation Sampling LeverageSHAP RegressionMSR (LGBM) Proxy (LGBM) FFD-RD FFD-RD (corrected) FourierSHAP OddSHAP ( = 10) Figure 3.Approximation quality measured by MSE (median with interquartile range) and total runtime in seconds for a simulated setting with 0.001s per subset evaluation. Similar plots for other datasets appear in Section D. 5.3. Ablation of Interaction Sparsity Including higher-order interactions yields a more expressive approximation of f, but this capacity comes at the expense of increased runtime and a larger sample budget. To evaluate this trade-off, we vary the regression variable factor across η∈ {2,5,10,50}, which controls the number of included odd interactions via |Todd|=⌈m/η⌉−d . Figure 4 illustrates the empirical impact on Shapley value accuracy. We report the MSE Ratio, defined as the Shapley MSE of OddSHAP- η normalized by the error of the interaction-free baseline, LeverageSHAP. Estimates across all value functions were computed under a fixed budget of 10,000 samples, and we defer additional experiments under 5,000 and 20,000 samples to Section D, along with results for the Estate value function (omitted here due to outlier improvements). 8 An Odd Estimator for Shapley Values 0 200 ( = 50) 1,000 ( = 10) 2,000 ( = 5) 5,000 ( = 2) Number of Regression Variables (m/ ) 10 2 10 1 100 101 102 MSE Ratio (Median ± IQR Band) DistilBERT ViT16 Cancer CG60 IL60 NHANES Crime Figure 4.MSE ratio between OddSHAP and LeverageSHAP as a function of the number of regression variables in OddSHAP, computed under a fixed budget of 10,000 samples. Across all datasets, we initially observe a strong decrease in the MSE Ratio as the number of interactions increases, validating that incorporating influential interactions signifi- cantly improves estimation over the interaction-free baseline. Specifically, with η= 10 (corresponding to roughly 1,000 interactions), we observe at least a 6× reduction in error for all value functions and up to a 62× reduction for one value function (Cancer). However, incorporating too many interactions eventually induces overfitting, reversing gains. 5.4. Ablation of Paired and Non-Paired Sampling Paired sampling isolates the odd component of f within the Fourier regression, eliminating the need to model even-order terms. However, it is not guaranteed to outperform non- paired sampling. Figure 5 illustrates the estimation accuracy achieved by paired and non-paired sampling across distinct interaction support. We report the MSE Ratio, defined as the Shapley MSE normalized by the error of OddSHAP (paired sampling with odd interactions). Estimates were computed under a fixed budget of 10,000 samples, and we defer additional experiments to Section D. All Odd All Odd 100 101 102 103 MSE Ratio (Median ± IQR Band) Non-Paired Sampling Paired Sampling DistilBERT ViT16 Cancer CG60 IL60 NHANES Crime Figure 5.MSE ratio of paired and non-paired sampling withAllor Oddinteractions relative to OddSHAP under 10,000 samples. Across all datasets, non-paired sampling underperforms paired sampling, with the non-pairedOddvariant perform- ing worst. Under paired sampling, including both even and odd interactions (All) splits the interaction budget |T |=⌈m/η⌉with superfluous even terms. Because these even terms mathematically cancel out, this configuration effectively restricts odd interactions to a smaller, less ex- pressive subset, explaining its slight performance drop. Ul- timately, incorporating even interactions under paired sam- pling only increases runtime without improving estimation. 6. Discussion We introduced OddSHAP, a budget-flexible algorithm for computing Shapley values that achieves state-of-the-art per- formance under larger budget constraints across a broad range of feature dimensions. OddSHAP is based on a the- oretical insight: Shapley values depend only on the odd component of the value function. In addition to serving as a basis for the OddSHAP algorithm, this insight provides the first rigorous theoretical basis for the popular heuristic ofpaired samplingused in prior state-of-the-art algorithms, and resolves an open conjecture in Fumagalli et al. (2026). Limitations and Future DirectionsWhile OddSHAP of- fers clear advantages, it introduces certain computational and statistical limitations. Computationally, the algorithm scales quadratically with the number of selected interac- tions; since our formulation ties the interaction count to the budget m, the overall runtime is cubic in m. While the regression factor η= 10 ensures stable performance across diverse applications, we recommend capping and decou- pling the number of selected interactions for larger budgets. Statistically, paired sampling does not strictly guarantee outperforming non-paired sampling. While it isolates odd interactions, reducing the regression to m/2 paired observa- tions, rather than m independent samples, halves the number of rows in the design matrix. This fundamentally inflates es- timator variance and increases mutual coherence due to the loss of independent subset coverage. Moreover, exploring the empirical correlations between even and odd interactions observed by Butler et al. (2025) presents a promising av- enue to leverage even components and improve estimation. Finally, unlike baselines such as FFD-RD that rely on rigid fixed-budget assumptions of non-existing higher-order inter- actions, OddSHAP accommodates more flexible interaction structures. In practice, pre-existing structural knowledge of the value function could be explicitly combined with Odd- SHAP’s interaction detection to further optimize sample efficiency, a compelling direction for future exploration. 9 An Odd Estimator for Shapley Values Acknowledgments Fabian Fumagalli gratefully acknowledges funding by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation): TRR 318/3 2026 – 438445824. This mate- rial is based upon work supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-2146752. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. Impact Statement This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here. References Butler, L., Agarwal, A., Kang, J. S., Erginbas, Y . E., Yu, B., and Ramchandran, K. Proxy-SPEX: Sample-Efficient Interpretability via Sparse Feature Interactions in LLMs. InProceedings of Advances in Neural Information Pro- cessing Systems (NeurIPS), 2025. Castro, J., G´omez, D., and Tejada, J. Polynomial calculation of the Shapley value based on sampling.Computers & Operations Research, 36(5):1726–1730, 2009. doi: 10.1016/j.cor.2008.04.004. Charnes, A., Golany, B., Keane, M., and Rousseau, J. Ex- tremal principle solutions of games in characteristic func- tion form: core, chebychev and shapley value general- izations. InEconometrics of planning and efficiency, pp. 123–133. Springer, 1988. Chen, T. and Guestrin, C. XGBoost: A scalable tree boost- ing system. InProceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 785–794. ACM, 2016. doi: 10.1145/2939672.2939785. Covert, I. and Lee, S. Improving KernelSHAP: Practical Shapley Value Estimation Using Linear Regression. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 3457–3465, 2021. Deng, J., Dong, W., Socher, R., Li, L., Li, K., and Fei-Fei, L. Imagenet: A large-scale hierarchical image database. InProceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), pp. 248–255, 2009. Dinh, A., Miertschin, S., Young, A., and Mohanty, S. D. A data-driven approach to predicting diabetes and cardio- vascular disease with machine learning.BMC Medical In- formatics Decisision Making, 19(1):211:1–211:15, 2019. doi: 10.1186/S12911-019-0918-5. Doshi-Velez, F. and Kim, B. Towards a rigorous sci- ence of interpretable machine learning.arXiv preprint arXiv:1702.08608, 2017. Frye, C., de Mijolla, D., Begley, T., Cowton, L., Stanley, M., and Feige, I. Shapley explainability on the data manifold. InProceedings of the International Conference on Learning Representations (ICLR), 2021. Fumagalli, F., Muschalik, M., Kolpaczki, P., H¨ullermeier, E., and Hammer, B. SHAP-IQ: Unified Approxima- tion of any-order Shapley Interactions. InProceedings of Advances in Neural Information Processing Systems (NeurIPS), 2023. Fumagalli, F., Witter, R. T., and Musco, C. PolySHAP: Extending KernelSHAP with Interaction-Informed Poly- nomial Regression. InProceedings of the International Conference on Learning Representations (ICLR), 2026. Ghorbani, A. and Zou, J. Y . Data shapley: Equitable valua- tion of data for machine learning. InProceedings of the International Conference on Machine Learning (ICML), pp. 2242–2251, 2019. Gorji, A., Amrollahi, A., and Krause, A. SHAP values via sparse fourier representation. InProceedings of Advances in Neural Information Processing Systems (NeurIPS), 2025. Grabisch, M.Set Functions, Games and Capacities in Deci- sion Making, volume 46. Springer International Publish- ing Switzerland, 2016. ISBN 978-3-319-30690-2. doi: 10.1007/978-3-319-30690-2. Harsanyi, J. C. A simplified bargaining model for the n- person cooperative game.International Economic Re- view, 4(2):194–220, 1963. Heskes, T., Sijben, E., Bucur, I. G., and Claassen, T. Causal shapley values: Exploiting causal knowledge to explain individual predictions of complex models. InProceedings of Advances in Neural Information Processing Systems (NeurIPS), volume 33, pp. 4778–4789, 2020. Janzing, D., Minorics, L., and Bl ¨obaum, P. Feature rele- vance quantification in explainable AI: A causal problem. InProceedings of the International Conference on Artifi- cial Intelligence and Statistics (AISTATS), pp. 2907–2916, 2020. 10 An Odd Estimator for Shapley Values Jia, R., Dao, D., Wang, B., Hubis, F. A., Hynes, N., G¨urel, N. M., Li, B., Zhang, C., Song, D., and Spanos, C. J. Towards efficient data valuation based on the shapley value. InProceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1167–1176, 2019. Kang, J. S., Butler, L., Agarwal, A., Erginbas, Y . E., Pedarsani, R., Yu, B., and Ramchandran, K. SPEX: Scal- ing feature interaction explanations for LLMs. InForty- second International Conference on Machine Learning, 2025. Ke, G., Meng, Q., Finley, T., Wang, T., Chen, W., Ma, W., Ye, Q., and Liu, T. LightGBM: A Highly Efficient Gradi- ent Boosting Decision Tree. InProceedings of Advances in Neural Information Processing Systems (NeurIPS), pp. 3146–3154, 2017. Kolpaczki, P., Bengs, V ., Muschalik, M., and H¨ullermeier, E. Approximating the shapley value without marginal contributions. InProceeedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 13246–13255, 2024. Lundberg, S. M. and Lee, S. A Unified Approach to Inter- preting Model Predictions. InProceedings of Advances in Neural Information Processing Systems (NeurIPS), pp. 4765–4774, 2017. Lundberg, S. M., Erion, G. G., Chen, H., DeGrave, A. J., Prutkin, J. M., Nair, B., Katz, R., Himmelfarb, J., Bansal, N., and Lee, S. From local explanations to global un- derstanding with explainable AI for trees.Nature Ma- chine Intelligence, 2(1):56–67, 2020. doi: 10.1038/ s42256-019-0138-9. Maas, A. L., Daly, R. E., Pham, P. T., Huang, D., Ng, A. Y ., and Potts, C. Learning word vectors for sentiment anal- ysis. InProceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Lan- guage Technologies (HLT), pp. 142–150, 2011. Mayer, M. and W ¨uthrich, M. V . Shapley values: Paired- sampling approximations.CoRR, abs/2508.12947, 2025. Mitchell, R., Cooper, J., Frank, E., and Holmes, G. Sam- pling permutations for shapley value estimation.Journal of Machine Learning Research, 23(43):1–46, 2022. Mohammadi, M., Muandet, K., Tiddi, I., Teije, A. T., and Chau, S. L. Exact shapley attributions in quadratic- time for fanova gaussian processes.arXiv preprint arXiv:2508.14499, 2025. Muschalik, M., Baniecki, H., Fumagalli, F., Kolpaczki, P., Hammer, B., and H¨ullermeier, E. shapiq: Shapley Interac- tions for Machine Learning. InProceedings of Advances in Neural Information Processing Systems (NeurIPS), pp. 130324–130357, 2024a. Muschalik, M., Fumagalli, F., Hammer, B., and H¨ullermeier, E. Beyond TreeSHAP: Efficient Computation of Any- Order Shapley Interactions for Tree Ensembles. InPro- ceeedings of the AAAI Conference on Artificial Intelli- gence (AAAI), pp. 14388–14396, 2024b. doi: 10.1609/ aaai.v38i13.29352. Muschalik, M., Fumagalli, F., Frazzetto, P., Strotherm, J., Hermes, L., Sperduti, A., H¨ullermeier, E., and Hammer, B. Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks. InThe Thirteenth Interna- tional Conference on Learning Representations, 2025. Musco, C. and Witter, R. T. Provably Accurate Shapley Value Estimation via Leverage Score Sampling. InProc- cedings of the International Conference on Learning Rep- resentations (ICLR), 2025. Olsen, L. H. B. and Jullum, M. Improving the Weight- ing Strategy in KernelSHAP. InExplainable Artificial Intelligence, pp. 194–218, 2026. Redmond, M. Communities and Crime Unnormalized, 2011. Rota, G.-C. On the foundations of combinatorial theory: I. Theory of M ¨obius functions. InClassic Papers in Combinatorics, pp. 332–360. Springer, 1964. Rozemberczki, B., Watson, L., Bayer, P., Yang, H., Kiss, O., Nilsson, S., and Sarkar, R. The shapley value in machine learning. InProceedings of International Joint Conference on Artificial Intelligence (IJCAI), pp. 5572– 5579, 2022. Sanh, V ., Debut, L., Chaumond, J., and Wolf, T. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter.CoRR, abs/1910.01108, 2019. Shapley, L. S. A Value for n-Person Games. InContri- butions to the Theory of Games (AM-28), Volume II, pp. 307–318. Princeton University Press, 1953. Street, W. N., Wolberg, W. H., and Mangasarian, O. L. Nu- clear feature extraction for breast tumor diagnosis. In Biomedical image processing and biomedical visualiza- tion, volume 1905, pp. 861–870, 1993. Strumbelj, E. and Kononenko, I. An Efficient Explanation of Individual Classifications using Game Theory.Journal of Machine Learning Research, 11:1–18, 2010. doi: 10. 5555/1756006.1756007. Strumbelj, E. and Kononenko, I. Explaining prediction models and individual predictions with feature contri- butions.Knowledge and Information Systems, 41(3): 647–665, 2014. doi: 10.1007/s10115-013-0679-x. 11 An Odd Estimator for Shapley Values Wang, J. T. and Jia, R. Data banzhaf: A robust data valuation framework for machine learning. In Ruiz, F. J. R., Dy, J. G., and van de Meent, J. (eds.),Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 6388–6421, 2023. Wang, J. T., Zhu, Y ., Wang, Y .-X., Jia, R., and Mittal, P. A privacy-friendly approach to data valuation. InPro- ceedings of Advances in Neural Information Processing Systems (NeurIPS), volume 37, 2023. Wang, J. T., Mittal, P., and Jia, R. Efficient data shapley for weighted nearest neighbor algorithms. InProceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 2557–2565, 2024. Wendler, C.Machine learning on non-Euclidean domains: Powersets, lattices, posets. PhD thesis, ETH Zurich, 2023. Witter, R. T., Liu, Y ., and Musco, C. Regression-adjusted monte carlo estimators for shapley values and probabilis- tic values. InProceedings of Advances in Neural Infor- mation Processing Systems (NeurIPS), 2025. Yeh, I. and Hsu, T. Building real estate valuation models with comparative approach through case-based reasoning. Appied Soft Computing, 65:260–271, 2018. doi: 10.1016/ J.ASOC.2018.01.029. Yu, P., Bifet, A., Read, J., and Xu, C. Linear tree shap. In Proceedings of Advances in Neural Information Process- ing Systems (NeurIPS), volume 35, 2022. Zern, A., Broelemann, K., and Kasneci, G. Interventional SHAP values and interaction values for piecewise linear regression trees. InProceedings of the 37th AAAI Con- ference on Artificial Intelligence, volume 37, pp. 11164– 11173, 2023. Zhou, Z., Mee, R., Hamers, H., and Zheng, W. Fast ap- proximation of shapley values through fractional factorial designs.Journal of the American Statistical Association, pp. 1–20, 2025. 12 An Odd Estimator for Shapley Values A. Expanded Table Table 3.Summary statistics of MSE for Shapley value estimators withm≈100d. OddSHAP achieves the lowest average rank. DistilBERT (d= 14) Estate (d= 15) ViT16 (d= 16) Cancer (d= 30) IL60 (d= 60) CG60 (d= 60) NHANES (d= 79) Crime (d= 101) Avg. Rankm1440 1722 1705 2281 5521 5521 5864 11126–MSRMean7.5×10 −4 2.8×10−2 1.2×10−4 2.2×10−2 3.5×10−3 2.1×10−3 4.7×10−2 3.6×101 7.751st Quartile1.6×10 −4 1.7×10−2 4.4×10−5 1.2×10−2 1.9×10−3 1.1×10−3 2.1×10−2 9.7×100 7.62Median5.6×10 −4 2.8×10−2 1.2×10−4 2.3×10−2 2.7×10−3 1.6×10−3 3.6×10−2 2.4×101 7.883rd Quartile8.8×10 −4 4.0×10−2 1.8×10−4 2.9×10−2 4.5×10−3 2.1×10−3 6.3×10−2 3.7×101 7.75SV ARMMean3.7×10 −4 3.3×10−2 5.7×10−5 3.5×10−3 2.2×10−3 9.7×10−4 4.0×10−2 1.5×101 6.751st Quartile6.5×10 −5 1.6×10−2 2.6×10−5 2.3×10−3 1.6×10−3 7.8×10−4 1.8×10−2 5.3×100 6.50Median2.4×10 −4 3.2×10−2 5.2×10−5 3.0×10−3 1.8×10−3 8.7×10−4 3.1×10−2 7.2×100 6.623rd Quartile4.7×10 −4 4.8×10−2 7.5×10−5 4.7×10−3 2.4×10−3 1.1×10−3 5.3×10−2 1.1×101 6.75PermutationSamplingMean6.2×10 −4 5.3×10−3 1.2×10−4 1.1×10−4 1.3×10−4 1.4×10−4 3.5×10−3 2.7×100 5.621st Quartile2.3×10 −4 1.9×10−3 6.2×10−5 5.3×10−5 9.1×10−5 8.0×10−5 1.3×10−3 8.6×10−1 5.75Median4.9×10 −4 2.9×10−3 9.1×10−5 7.2×10−5 1.2×10−4 1.2×10−4 2.1×10−3 1.2×100 5.623rd Quartile8.6×10 −4 4.4×10−3 1.6×10−4 1.7×10−4 1.9×10−4 1.6×10−4 4.2×10−3 2.6×100 5.62LeverageSHAPMean 7.7×10−5 3.4×10−4 3.5×10−5 3.2×10−5 2.6×10−5 2.5×10−5 6.2×10−4 7.5×10−1 3.251st Quartile 3.2×10−5 9.2×10−5 1.9×10−5 1.1×10−5 1.3×10−5 1.8×10−5 2.4×10−4 1.9×10−1 3.38Median6.9×10 −5 1.6×10−4 2.7×10−5 2.3×10−5 2.2×10−5 2.2×10−5 4.8×10−4 2.7×10−1 3.383rd Quartile1.1×10 −4 2.6×10−4 4.3×10−5 4.2×10−5 3.2×10−5 3.2×10−5 9.0×10−4 5.8×10−1 3.38PolySHAP-3Mean8.0×10 −5 3.2×10−7 3.8×10−5 4.0×10−5 3.251st Quartile4.5×10 −5 3.1×10−8 1.7×10−5 1.3×10−5 3.25Median 6.6×10−5 1.1×10−7 2.8×10−5 2.7×10−5 3.253rd Quartile 1.1×10−4 3.7×10−7 4.8×10−5 6.2×10−5 3.25RegressionMSRMean 3.1×10−5 1.3×10−5 1.0×10−5 3.0×10−4 9.7×10−6 7.6×10−5 2.4×10−4 5.6×10−1 2.621st Quartile 1.4×10−5 6.5×10−6 4.4×10−6 1.8×10−4 6.1×10−6 5.0×10−5 1.3×10−4 3.0×10−1 2.75Median 2.2×10−5 1.0×10−5 8.9×10−6 2.7×10−4 1.0×10−5 7.4×10−5 1.7×10−4 3.6×10−1 2.883rd Quartile 4.1×10−5 1.8×10−5 1.2×10−5 4.1×10−4 1.2×10−5 1.0×10−4 2.7×10−4 5.4×10−1 2.62ProxyMean3.6×10 −4 3.3×10−5 4.6×10−5 4.2×10−4 4.9×10−5 2.9×10−4 7.0×10−4 5.3×100 5.001st Quartile1.1×10 −4 2.1×10−5 1.4×10−5 2.5×10−4 3.3×10−5 1.9×10−4 4.1×10−4 2.6×100 4.88Median2.9×10 −4 2.5×10−5 2.4×10−5 3.8×10−4 4.6×10−5 3.0×10−4 5.3×10−4 3.5×100 4.883rd Quartile4.8×10 −4 3.9×10−5 4.6×10−5 5.5×10−4 6.1×10−5 3.7×10−4 9.9×10−4 5.6×100 5.00FFD-RDMean1.6×10 −3 1.8×10−6 5.3×10−4 6.4×10−7 5.751st Quartile5.4×10 −4 2.2×10−7 1.8×10−4 6.3×10−8 5.50Median1.3×10 −3 5.3×10−7 2.9×10−4 2.0×10−7 5.753rd Quartile2.8×10 −3 1.8×10−6 7.6×10−4 3.5×10−7 6.00FFD-RD-CorrectedMean1.8×10 −3 6.8×10−5 8.501st Quartile1.8×10 −3 6.8×10−5 9.50Median1.8×10 −3 6.8×10−5 8.503rd Quartile1.8×10 −3 6.8×10−5 7.50FourierSHAPMean1.9×10 −2 3.0×10−2 4.9×10−3 7.7×10−2 4.1×10−3 8.5×10−3 1.7×10−1 1.9×102 9.121st Quartile2.9×10 −3 1.4×10−2 2.6×10−3 3.1×10−2 2.0×10−3 6.2×10−3 8.2×10−2 6.2×101 9.00Median7.4×10 −3 2.4×10−2 3.4×10−3 7.2×10−2 3.2×10−3 8.2×10−3 1.2×10−1 1.1×102 9.003rd Quartile2.5×10 −2 4.2×10−2 6.4×10−3 9.3×10−2 5.2×10−3 9.7×10−3 2.3×10−1 1.7×102 9.12OddSHAPMean 4.6×10−5 5.1×10−7 1.3×10−5 4.2×10−6 1.6×10−6 6.2×10−6 5.8×10−5 1.3×10−1 1.501st Quartile 1.6×10−5 2.4×10−7 5.4×10−6 2.5×10−6 1.2×10−6 4.5×10−6 3.2×10−5 6.6×10−2 1.62Median 3.8×10−5 3.9×10−7 8.6×10−6 3.5×10−6 1.6×10−6 5.8×10−6 4.9×10−5 8.4×10−2 1.383rd Quartile 5.7×10−5 7.1×10−7 1.8×10−5 5.4×10−6 2.0×10−6 7.8×10−6 6.7×10−5 1.3×10−1 1.50 13 An Odd Estimator for Shapley Values B. Delayed Proofs Observation 3.1(Shapley values of Odd and Even Functions) Proof.Rearranging Equation 1, we have ϕi(f) = X S⊆[d] f(S)(1[i∈S]p |S|−1 −1[i /∈S]p |S|).(6) Since f=f odd +f even and the Shapley value ϕi(·) is a linear operator, it suffices to show that ϕi(feven) = 0. We will next rewrite the summation over complementary pairs S and Sc. We pair each subset containing i with its complement, which does not containi. LetSdenote the subset in each pair wherei∈S. Then, ϕi(feven) = X S,Sc feven(S)p|S|−1 −f even(Sc)p|Sc| = X S,Sc feven(S)[p|S|−1 −p |Sc|],(7) where the last equality follows because feven is even (i.e., feven(S) =f even(Sc)). Notice that |Sc|=d− |S| . Using the symmetry of the binomial coefficient, it is easy to show that p|S|−1 =p d−|S|. Then every term in Equation (7) is 0, and the lemma statement follows. Theorem 3.2(Even-Odd Separation via Paired Sampling). Suppose the vector space V is even-odd decomposable, and let w|S| be a symmetric weight with w|S| =w d−|S|. Under paired sampling, the weighted least squares projection onto the affine spaceF(f)completely decouples, argmin g∈F(f) X S∈S w|S| (f(S)−g(S)) 2 = argmin godd∈Fodd(fodd) X S∈S w|S| (fodd(S)−g odd(S))2 + argmin geven∈Feven(feven) X S∈S w|S| (feven(S)−g even(S))2 . Proof of Theorem 3.2. Consider the inner summation for a specific pair S and Sc. Since w|S| =w |Sc|, we can expand the sum over the pair and apply an even-odd decomposition: (f(S)−g(S)) 2 + (f(Sc)−g(S c))2 = (feven(S) +fodd(S)−g even(S)−g odd(S))2 + (feven(Sc) +fodd(Sc)−g even(Sc)−g odd(Sc))2 .(8) Using the definition of even and odd functions on the complement: (8) = (feven(S) +fodd(S)−g even(S)−g odd(S))2 + (feven(S)−f odd(S)−g even(S) +godd(S))2 .(9) After expanding and refactoring: (9) = 2 (fodd(S)−g odd(S))2 + 2 (feven(S)−g even(S))2 = (fodd(S)−g odd(S))2 + (feven(S)−g even(S))2 + (fodd(Sc)−g odd(Sc))2 + (feven(Sc)−g even(Sc))2 , where the last equation follows by again applying the definition of even and odd functions to half of the terms. Substituting this expression back into the objective and separating the minimization completes the proof. Corollary 3.3(Frontier Invariance under Unanimity). Under paired sampling, ifk is odd and ˆfk is the solution to Equation (4) under classF M (f,T ≤k), then ϕi( ˆfk) =ϕi( ˆfk+1)∀i∈[d]. 14 An Odd Estimator for Shapley Values Proof. By Lemma 3.4, the restricted unanimity class FM (f,T ≤k) is equivalent to the Fourier restricted class FF (f,T ≤k). We can therefore parameterize the solution space using Fourier coefficients, where the conversion to unanimity coefficients is given by Eq. 2.76 in (Grabisch, 2016): αS = (−2)|S| X T⊇S βT . Consider the expansion from degree limit k to k+ 1. By the conversion above, it can be seen that this only introduces Fourier basis terms corresponding to subsets T where |T|=k+ 1 . Since k is odd, k+ 1 is even. Thus, the expansion only adds dimensions to the even subspace of the Fourier domain. The subspace of odd-degree Fourier terms remains identical. By Theorem 3.2, under paired sampling, the optimization of the odd component is independent of the even subspace. Consequently, the odd component of the minimizer remains invariant, and by Observation 3.1,ϕ( ˆfk) =ϕ( ˆfk+1). Lemma 3.4(Unanimity and Fourier Equivalence).For anyf, the span of the unanimity and Fourier restricted classes on T≤k are the same i.e., FM (f,T ≤k) =FF (f,T ≤k). Proof of Lemma 3.4. We can use a change of variable to show this quickly. First, observe that the constraints g(S) = f(S), S∈ {∅,[d]}are conditions on the function values, which are independent of the basis representation. Therefore, it suffices to show that the unconstrained spans of the two bases restricted to orderkare identical. Fourier to Unanimity:Assume g is in the unconstrained Fourier class of up to order k (i.e., βT = 0for all |T|> k). To see the conversion from Fourier to unanimity coefficients, we can represent coalitions using an indicator vector x∈ {0,1}d where xi = 1if the i-th feature is present. The bases can then be written asuT (x) =Q i∈T xi and χT (x) =Q i∈T (1−2x i). Expanding the Fourier basis yields χT (x) = P S⊆T (−2)|S|uS(x), which immediately gives the coefficient conversion formula (Grabisch, 2016): αS = (−2)|S| X T⊇S βT . For any set S such that |S|> k, the condition T⊇S implies |T| ≥ |S|> k. Thus, βT = 0for all such T, which implies αS = 0. Thus,gadmits a representation in the unanimity class of up to orderk. Unanimity to Fourier:Conversely, assume g is in the unanimity class of up to order k (i.e., αS = 0 for all |S|> k ). Alternatively, we can represent coalitions using x∈ {1,−1}d where −1 indicates the presence of a feature. In this case, the bases are χT (x) = Q i∈T xi and uT (x) = Q i∈T 1−xi 2 . Expanding the unanimity basis yields uT (x) = 1 2|T| P S⊆T (−1)|S|χS(x), which gives the reverse conversion (Grabisch, 2016): βT = (−1)|T| X S⊇T αS 2|S| .(10) Since the unconstrained subspaces are identical, and the boundary constraints are basis-independent, we conclude that FM (f,T ≤k) =FF (f,T ≤k). Theorem 3.5(Fourier Regression).Consider any collection of coalitions T ⊃ T≤1. Consider the best polynomial approximation tofin the Fourier basis onT: ˆf= argmin g∈FF (f,T) X S⊆[d]:0<|S|