Maximum Sample Reuse for Efficient Model Attribution

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 122 papers34 conceptsfrozen 2026-10-04

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:

  1. The average model output when the feature is present.
  2. 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:

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.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_maximum_sample_reuse_for_efficient_model_19d7efe5,
  title = {Maximum Sample Reuse for Efficient Model Attribution},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/maximum-sample-reuse-for-efficient-model-attribution/rdr_19d7efe5fb8940ea8b097e26012df46b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_maximum_sample_reuse_for_efficient_model_19d7efe5_v1,
  title = {Maximum Sample Reuse for Efficient Model Attribution},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/maximum-sample-reuse-for-efficient-model-attribution/rdr_19d7efe5fb8940ea8b097e26012df46b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}