We present a unified framework of provably efficient randomized estimators for Shapley values. We also provide, for the first time to our knowledge, provable guarantees for KernelSHAP, the most popular Shapley value method.

We present an optimistic query routing protocol in clustering-based approximate maximum inner product search that reaches the same accuracy as SoTA routers by probing 50% fewer data points.