# Efficient Banzhaf-Based Data Valuation for k-Nearest Neighbors Classification

arXiv: https://arxiv.org/abs/2605.21033 · HTML: https://mlsanity.com/paper/2605.21033/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 41 references that are in the map.
- First posted on arXiv 20 May 2026.

## Builds on (most cited first, 18 of 18)

- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Deduplicating Training Data Makes Language Models Better](https://mlsanity.com/paper/2107.06499/) (2021)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [Estimating Training Data Influence by Tracing Gradient Descent](https://mlsanity.com/paper/2002.08484/) (2020)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation](https://mlsanity.com/paper/2008.03703/) (2020)
- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms](https://mlsanity.com/paper/1908.08619/) (2019)
- [Training Data Influence Analysis and Estimation: A Survey](https://mlsanity.com/paper/2212.04612/) (2022)
- [Data Banzhaf: A Robust Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2205.15466/) (2022)
- [Sampling Permutations for Shapley Value Estimation](https://mlsanity.com/paper/2104.12199/) (2021)
- [Data Shapley in One Training Run](https://mlsanity.com/paper/2406.11011/) (2024)
- [LAVA: Data Valuation without Pre-Specified Learning Algorithms](https://mlsanity.com/paper/2305.00054/) (2023)
- [Bounding the Estimation Error of Sampling-based Shapley Value Approximation](https://mlsanity.com/paper/1306.4265/) (2013)
- [OpenDataVal: a Unified Benchmark for Data Valuation](https://mlsanity.com/paper/2306.10577/) (2023)
- [Efficient Data Shapley for Weighted Nearest Neighbor Algorithms](https://mlsanity.com/paper/2401.11103/) (2024)
- [A Note on "Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms"](https://mlsanity.com/paper/2304.04258/) (2023)

## Abstract (arXiv)

Data valuation, the task of quantifying the contribution of individual data points to model performance, has emerged as a fundamental challenge in machine learning. Game-theoretic approaches, such as the Banzhaf value, offer principled frameworks for fair data valuation; however, they suffer from exponential computational complexity. We address this challenge by developing efficient algorithms specifically tailored for computing Banzhaf values in k-nearest neighbor (kNN) classifiers. We first establish the theoretical hardness of the problem by proving that it is #P-hard. Despite this intractability, we exploit the locality properties of kNN classifiers to develop practical exact algorithms. Our main contribution is a dynamic programming framework that achieves significant computational improvements: we present a pseudo-polynomial algorithm with O(Wkn2) time complexity for weighted kNN classifiers, where W is the maximum sum of top-k weights, and a specialized algorithm for unweighted kNN that achieves O(nk2) time complexity, that is, linear in the number of data points. We also offer efficient Monte Carlo estimation methods. Extensive experiments on real-world datasets demonstrate the practical efficiency of our approach and its effectiveness in data valuation applications.