Model-agnostic feature attribution methods such as KernelSHAP explain a prediction by "removing" features and watching the output change. Removal is simulated by filling the missing features with values from a background dataset, which is a few hundred reference rows drawn from training data. The cost is multiplicative: $M$ feature subsets times $B$ background rows means $M \times B$ model calls per explained instance. Almost all speed-up work attacks $M$, through better subset samplers, variance reduction or amortized networks, and leaves the background as a randomly drawn block of rows. This proposal attacks $B$. We compress the background to a handful of real rows with farthest point sampling (FPS), the greedy rule from topological data analysis that repeatedly picks the point farthest from everything chosen so far. We weight each kept row by how many original rows it stands in for.
The key choice is the distance used. We do not measure distance between rows in input space. We measure it in a model-induced metric: two background rows are close if substituting one for the other barely changes the model's output across a set of probe queries. In this metric, the worst-case quantity that FPS controls translates directly into a worst-case bound on Shapley error for every feature and every subset. A 10–20× reduction in $B$ then becomes a 10–20× reduction in explanation latency, comes with a certificate, and composes with every existing sampler.
Core Claim
Let $f$ be the model and $D$ the full background of $N$ rows. For an instance $x$ and feature subset $S$, the interventional value is $v_D(S)=\frac{1}{N}\sum_{b\in D} f(x_S, b_{\bar S})$, where $x_S$ keeps $x$'s features in $S$ and $b_{\bar S}$ fills the rest from $b$. Suppose we replace $D$ by landmarks $L\subset D$. Each landmark $l$ is weighted by the fraction of $D$ in its nearest-landmark cell. Define the model-induced distance $d_f(b,b')=\sup_{x,S}|f(x_S,b_{\bar S})-f(x_S,b'_{\bar S})|$. If every $b\in D$ lies within $\epsilon$ of its landmark under $d_f$, then $|v_D(S)-v_L(S)|\le\epsilon$ for all $x,S$. Each Shapley value is a weighted difference of value functions whose weights sum to one, so
$$|\phi_i^{D}(x)-\phi_i^{L}(x)|\le 2\epsilon \quad \text{for every feature } i \text{ and instance } x.$$
The quantity that matters is therefore the worst-case covering radius in $d_f$. That is the k-center objective, and greedy FPS is the classical 2-approximation for it. This is why FPS, rather than k-means, is the principled tool here. The covering property is the same one Topological Data Analysis with ε-net Induced Lazy Witness Complex exploits to bound topological error of landmark complexes. We transplant it from point-cloud geometry to the space of background rows. FPS also returns actual data rows, so it avoids the off-manifold synthetic references that Explaining a machine learning decision to physicians via counterfactuals warns produce physiologically impossible states.
Research Program
The method has an offline stage and an online stage. Offline, we draw $P$ probe queries $(x,S)$ from training instances and from subset sizes weighted as in the KernelSHAP kernel. We evaluate $f$ on every background row under every probe. This represents each row as a $P$-dimensional output vector, and $d_f$ is approximated by the $\ell_\infty$ distance between these vectors. This costs $N\times P$ model calls, paid once per model. We then run FPS on these vectors. The run stops either at a budget $k$ or when the covering radius falls below a target $\epsilon$, which mirrors the precision stopping rule tol in kernelshap: Kernel SHAP. Finally we assign Voronoi weights. Online, any estimator runs unchanged with $k$ weighted rows instead of $B$.
Three analyses accompany the method. First, the probe approximation replaces a supremum by a finite maximum. We will measure how often the certified $2\epsilon$ bound is violated on held-out instances and subsets as $P$ grows. This tells us whether the "certificate" holds empirically or only nominally. Second, FPS is known to pick isolated outliers early. Under $d_f$, an outlier is selected only if it genuinely changes model output, and its weight is then small, so the bias it introduces is bounded. We will still test a trimmed variant that drops the top fraction of rows by nearest-neighbor distance. Third, we will show that the gain is orthogonal to estimators that reduce $M$. These include the sketched-regression samplers of A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values, the Taylor-proxy control variates of Goldwasser et al., and the hybrid exact-plus-paired sampling in kernelshap. All of them sample subsets over an unstructured hypercube and keep the background fixed. Our method changes only the background, so the speed-ups should multiply.
Baselines
The naive reference point is the default practice of a random background of $B=200$ rows, the kernelshap default. Its attributions are compared to a ground truth computed with a much larger background (several thousand rows). On low-dimensional tabular tasks the ground truth uses exact subset enumeration; on high-dimensional ones it uses a large fixed KernelSHAP sample. The same subset draws are shared across all background variants, so differences isolate background error.
Equal-size random subsampling at each $k$ is the cheapest competitor. It shows whether any structured selection is needed at all.
The strongest existing practice is weighted k-means compression, which uses centroids weighted by cluster size. We also run weighted k-medoids, which keeps real rows. K-medoids minimizes average rather than worst-case distance, so it is the competitor most likely to beat us on mean error. All selectors receive the same $k$, the same pool $D$, and the same wall-clock budget for selection. K-means and k-medoids get several restarts, and the best one is reported.
Two ablations isolate the key ingredients. FPS in standardized input space tests whether the model-induced metric matters. Unweighted FPS in $d_f$ tests whether the Voronoi weights matter.
Beating the baselines means two things. First, at matched $k\in\{5,10,20,40\}$, our method must achieve lower maximum and 95th-percentile per-feature Shapley error than all baselines. Second, its mean error must be no worse than k-medoids, and it must match the $B=200$ random baseline's error with at least 10× fewer rows.
No reported result was found on Lacuna for background-set compression on any of these datasets, so there is no published number to beat directly. For context on the latency frontier, FastSHAP: Real-Time Shapley Value Estimation reports 200x to 1000x speed-ups over KernelSHAP and an Exclusion AUC of 0.51 on Imagenette. CoRTX: Contrastive Framework for Real-time Explanation reports 0.00015 seconds per instance on tabular data.
Why not just…?
Why not just subsample the background at random? Random rows give an unbiased estimate of the value function, but they carry no worst-case guarantee. They also under-represent rare regions where the model's output changes sharply. This is the analogue of random sampling erasing thin structures in point clouds, as shown by Shan et al.. The matched-$k$ comparison on tail error settles this directly. If random sampling matches us on the 95th percentile at $k=20$, the proposal's claim fails.
Why not just use weighted k-means or k-medoids, as libraries already do? This is the real threat. K-medoids optimizes average quantization error, and average Shapley error may be what users experience most often. Our argument is that the bound above depends on the covering radius, not the average distance. K-means centroids can also be off-manifold, which matters for categorical or clinical features. We will report mean and worst-case error separately. We will openly state the regime, if one exists, where k-medoids in $d_f$ wins on mean error. A hybrid that seeds k-medoids with FPS landmarks is a fallback if neither dominates.
Why not just amortize the explainer (FastSHAP, CoRTX) and skip per-instance estimation? Amortized explainers win on online latency. However, they require training a surrogate and an explainer network. Their accuracy depends on that surrogate, and they can drift on inputs unlike their training data, as FastSHAP's own reliance on a conditional surrogate makes clear. Background compression needs no training, carries a per-instance error certificate, and also reduces the cost of generating the Shapley labels that supervise those explainers. We will measure that label-generation saving as a secondary result rather than claim to beat amortized latency.
Why not just apply FPS to the subsets instead, picking dispersed points of the Boolean cube? This is the more obvious intersection. However, KernelSHAP's weighting deliberately concentrates samples on very small and very large subsets, and Hamming dispersion would fight that weighting. Paired sampling in kernelshap and the importance distributions in the sketching framework already address redundancy among subsets. Reducing $B$ attacks a factor no existing sampler touches, so we chose it.
Proposed Experiments
The tabular benchmarks are Census Income, Bank Marketing, Bankruptcy (high-dimensional) and NHANES, all used by FastSHAP, CoRTX or the sketching framework. For each we train a gradient-boosted tree model and a multilayer perceptron, and explain 1,000 held-out instances. We report mean, 95th-percentile and maximum absolute Shapley error relative to the large-background ground truth. We also report rank correlation of top features, model calls per explanation, and wall-clock latency, along with the offline cost $N\times P$. As a stress test of the outlier issue, we inject 1% corrupted rows into $D$.
The decisive checks are three. The certified $2\epsilon$ bound must hold on at least 99% of held-out (instance, subset) pairs once $P$ reaches a modest size such as a few hundred. Model-induced FPS must beat input-space FPS on worst-case error, which shows the metric, not FPS alone, does the work. Finally, combining our 20-row background with the Modified $\ell_2$ sketched sampler must yield a multiplicative latency reduction at unchanged error. If input-space FPS performs as well as the model-induced version, the method collapses to a simpler heuristic, and we will report it that way.
References
- Topological Data Analysis with \epsilon ϵ -net Induced Lazy Witness Complex.
- Explaining a machine learning decision to physicians via counterfactuals
- kernelshap: Kernel SHAP
- A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values
- Stabilizing Estimates of Shapley Values with Control Variates
- FastSHAP: Real-Time Shapley Value Estimation
- CoRTX: Contrastive Framework for Real-time Explanation
- Real-time 3D Single Object Tracking with Transformer