CaSh: Shapley Value Computation with Cache Optimization

In recent years, the Shapley value has become the de facto standard for equitable attribution in data analytics, such as data valuation and model interpretability. Since exact computation entails an exponential complexity of O (2

n

), sampling-based approximation algorithms are widely adopted. However, these methods treat utility functions as stateless black boxes, leading to a critical system-level inefficiency: the redundant and costly evaluation of identical coalitions that recur during sampling. To address this bottleneck, we propose CaSh, an algorithm-agnostic Ca ching framework that accelerates existing Sh apley value approximation algorithms by strategically storing and reusing intermediate coalition utility computations. CaSh leverages a high-performance Direct Mapping architecture tailored for Shapley value approximation to cache coalition utility results, enabling significant speedups without introducing any additional approximation error. We integrate CaSh with major approximation algorithms and evaluate the performance across diverse data analytics tasks. Experimental results demonstrate that CaSh consistently accelerates widely used approximation algorithms, reducing total computation time by 8% to 29% depending on the underlying sampling strategy. This efficiency gain is achieved without introducing additional approximation error beyond the underlying estimator, improving the efficiency of Shapley value-based data analytics pipelines.