# On the Robustness of Deep K-Nearest Neighbors

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Mar 2019.

## Built on by (most cited first, 10 of 10)

- [Towards flexible perception with visual memory](https://mlsanity.com/paper/2408.08172/) (2024)
- [Consistent Non-Parametric Methods for Maximizing Robustness](https://mlsanity.com/paper/2102.09086/) (2021)
- [A Simple Framework to Enhance the Adversarial Robustness of Deep Learning-based Intrusion Detection System](https://mlsanity.com/paper/2312.03245/) (2023)
- [ASK: Adversarial Soft k-Nearest Neighbor Attack and Defense](https://mlsanity.com/paper/2106.14300/) (2021)
- [Adversarial Attack and Defense for Non-Parametric Two-Sample Tests](https://mlsanity.com/paper/2202.03077/) (2022)
- [p-DkNN: Out-of-Distribution Detection Through Statistical Testing of Deep Representations](https://mlsanity.com/paper/2207.12545/) (2022)
- [Pulling Back the Curtain: Unsupervised Adversarial Detection via Contrastive Auxiliary Networks](https://mlsanity.com/paper/2502.09110/) (2025)
- [Improved Search of Relevant Points for Nearest-Neighbor Classification](https://mlsanity.com/paper/2203.03567/) (2022)
- [On the Efficiency of Training Robust Decision Trees](https://mlsanity.com/paper/2507.10048/) (2025)
- [Separating Knowledge and Perception with Procedural Data](https://mlsanity.com/paper/2508.11697/) (2025)

## Abstract (arXiv)

Despite a large amount of attention on adversarial examples, very few works have demonstrated an effective defense against this threat. We examine Deep k-Nearest Neighbor (DkNN), a proposed defense that combines k-Nearest Neighbor (kNN) and deep learning to improve the model's robustness to adversarial examples. It is challenging to evaluate the robustness of this scheme due to a lack of efficient algorithm for attacking kNN classifiers with large k and high-dimensional data. We propose a heuristic attack that allows us to use gradient descent to find adversarial examples for kNN classifiers, and then apply it to attack the DkNN defense as well. Results suggest that our attack is moderately stronger than any naive attack on kNN and significantly outperforms other attacks on DkNN.