Predictable Size-Conditional Linear Control Variates for Unbiased Semi-Value Estimation

Shapley values and more generally, semi-value attribute a model's prediction to individual players, such as features or training points. Utility assigns a score to every possible subset of players; however, exact computation is exponential, so practice relies on unbiased sampling with variance reduction. Adalina recently removes $\log n$ factor from the query complexity, at linear time and space per utility query. However, its single global scalar control variate cannot capture variation among same-size coalitions, and fitting it on the samples it corrects induces an $O(1/T)$ bias. Observing that this within-size variation is often close to linear, we propose SLICE, which adds a size-wise mean and a size-wise linear control variate with closed-form centering, both fit only on past batches and held fixed for the current one. SLICE is unbiased at finite sample size, keeps Adalina's linear cost and $\log n$-free query complexity, and, with population-optimal coefficients, does not increase MSE over its global-only counterpart. Across 12 datasets and 18 semi-value settings, SLICE matches or outperforms every baseline, with a median error reduction of $2.1\times$.