Large-scale black-box models have become ubiquitous across numerous applications. Understanding the influence of individual training samples on predictions made by these models is crucial for improving their trustworthiness. The backbone of current influence estimation techniques involves computing gradients for every training point or repeated training on different subsets. These approaches face obvious computational challenges when scaled up to large datasets and models.In this work, we introduce a principled approach to address the computational challenge in data influence estimation. Our approach is empowered by a novel insight into the duality of data influence. Specifically, we discover that the problem of training data influence estimation has an equivalent counterfactual dual problem — how would the prediction on training samples change if the model was trained on a specific test sample? Surprisingly, solving the dual yields results equivalent to the original problem. Further, we demonstrate that highly efficient methods exist for this dual problem, which entails only a forward pass of the neural network for each training point.We demonstrate the utility of our approach across various applications, including data leakage detection, memorization, and language model behavior tracing.