In modern machine learning, understanding "why" a model made a prediction or "how much" a specific data point contributed to training is often as important as the prediction itself. However, calculating these values—whether through Shapley values, Banzhaf values, or Leave-One-Out cross-validation—is notoriously expensive. Traditionally, these methods require thousands of model evaluations, where each evaluation provides only a tiny sliver of information about a single feature or data point.
A new paradigm, often termed Maximum Sample Reuse (MSR), is transforming this landscape. Instead of treating a model evaluation as a single-use data point, MSR algorithms ensure that every single model call updates the estimates for all features or data points simultaneously.
The Information Waste Problem
To understand the breakthrough, consider the traditional way we estimate the Shapley value, the gold standard for feature importance. Standard Monte Carlo methods rely on "marginal contributions": you pick a feature, create a random subset of other features, and see how much the model's output changes when you add your feature to that subset.
As noted by Patrick Kolpaczki, Viktor Bengs, and Eyke Hüllermeier in Approximating the Shapley Value without Marginal Contributions, this approach is incredibly wasteful. If you have 100 features, a single model evaluation of a feature subset tells you something about the "coalition" as a whole, but traditional sampling only uses it to update one feature's marginal contribution. The other 99 features gain nothing from that computation.
From Marginal Contributions to Global Updates
The core intuition behind MSR is to move away from the "difference" (marginal) and toward "averages." Mathematically, the Shapley value of a feature can be reframed as the difference between two weighted averages:
- The average model output when the feature is present.
- The average model output when the feature is absent.
This reframing is the engine behind the SVARM algorithm. When you evaluate a random subset of features $S$, you immediately know which features are in $S$ and which are not. SVARM uses that single evaluation to update the "present" average for every feature in $S$ and the "absent" average for every feature not in $S$.
As Patrick Kolpaczki and colleagues demonstrate, this "global update" mechanism allows the information gain per model call to scale with the number of features. In Antithetic Sampling for Top-K Shapley Identification, they show that this shift moves budget efficiency from a fixed ratio to one that scales linearly with the system's complexity.
Scaling to Interactions and Data Valuation
This principle isn't limited to individual features; it extends to complex interactions and data quality assessment:
- Higher-Order Interactions: Fabian Fumagalli and Maximilian Muschalik introduced SHAP-IQ and SVARM-IQ (SHAP-IQ: Unified Approximation of any-order Shapley Interactions). These methods use a single model evaluation to update estimates for all possible interaction groups (pairs, triplets, etc.) that are contained within or touching the sampled subset.
- Data Valuation: In the context of valuing training data, Ruoxi Jia and Tianhao Wang developed Data Banzhaf (Data Banzhaf: A Data Valuation Framework with Maximal Robustness to Learning Stochasticity). By training a model on a random subset of data, they can simultaneously update the influence estimates for every single data point in the entire dataset, drastically reducing the number of training runs needed to identify high-quality or "poisoned" data.
Beyond Game Theory: Sampling and Cross-Validation
The philosophy of "recycling" computation appears in other high-stakes estimation tasks as well.
In mutual information estimation, Anshumali Shrivastava and Ryan Spring proposed Locality-Sensitive Sampling (LSS) (Mutual Information Estimation using LSH Sampling). Instead of using Locality-Sensitive Hashing just to find a single nearest neighbor, they use every item retrieved in a hash bucket to compute statistical estimates, maximizing the information gain from the hashing process.
Similarly, for cross-validation, Yuetian Luo and Rina Barber developed Iterative Approximate Cross-Validation (IACV) (Iterative Approximate Cross-Validation). By sharing updates across all data-point-specific models during the training process, they can estimate leave-one-out errors without the massive overhead of retraining the model $N$ times.
Why It Works: Amortized Computation
The success of Maximum Sample Reuse stems from amortization. In traditional Monte Carlo sampling, the variance of your estimate decreases only as you add more independent samples. In MSR, you are essentially "coupling" the estimates.
By using the same model evaluation to update multiple targets, you induce correlations that, if handled correctly (as in the regression-adjusted estimators by R. Teal Witter and Christopher P Musco), lead to much lower variance for a fixed computational budget. The reader should view MSR not just as a faster algorithm, but as a fundamental shift in how we extract information from expensive black-box functions: every query is a precious resource that should be squeezed for every bit of information it contains.