Out-of-Distribution Detection with Deep Nearest Neighbors

Yiyou Sun, Yifei Ming, Xiaojin Zhu, Yixuan Li

Deep learning models are notoriously overconfident. When presented with an input that looks nothing like their training data—an Out-of-Distribution (OOD) sample—they often assign it a high-confidence label from a known class rather than admitting, "I don't know." This presents a major safety hurdle for deploying AI in open-world scenarios like autonomous driving or medical diagnosis.

Existing "distance-based" OOD detection methods attempt to solve this by measuring how far a test sample is from the training data in the model's feature space. However, popular methods like the Mahalanobis distance assume that the training data follows a specific distribution, usually a mixture of Gaussians. Researchers from UW-Madison point out that deep features rarely satisfy these rigid statistical assumptions.

In this paper, the authors ask: Can we ditch the assumptions and use a simple, non-parametric nearest-neighbor approach instead? Their resulting method, KNN-OOD, significantly outperforms complex parametric methods, reducing the false positive rate on ImageNet benchmarks by nearly 25% compared to previous state-of-the-art distance-based methods.

The KNN-OOD Framework

The authors propose a straightforward framework that uses the $k$-th nearest neighbor distance as an OOD score. The process involves four key steps:

  1. Feature Extraction: Pass an image through a pre-trained neural network and extract the vector from the penultimate layer (just before the final classification head).
  2. Normalization: Crucially, normalize these feature vectors to have a unit length ($L_2$ norm).
  3. Distance Calculation: For a test sample, calculate the Euclidean distance to all samples in the training set.
  4. Scoring: The OOD score is the distance to the $k$-th nearest neighbor. If this distance exceeds a threshold determined by in-distribution data, the sample is flagged as OOD.

Key Insights: Why KNN Works

While the core idea is simple, its success hinges on moving away from flawed assumptions and leveraging modern representation learning techniques.

The "Gaussian Assumption" is a Myth: Using the Henze-Zirkler test, the authors proved that deep embeddings often fail multivariate normality tests. Parametric methods are essentially trying to fit a square peg in a round hole.

Normalization is Non-Negotiable: Without normalization, in-distribution (ID) samples often have much larger feature magnitudes than OOD samples. In a raw Euclidean space, this makes ID samples appear "farther" from their neighbors than OOD samples, breaking the detection logic. Normalization projects everything onto a unit sphere, making distance a pure measure of semantic similarity.

Contrastive Learning is the Perfect Partner: While KNN works with standard models, training with Supervised Contrastive Learning (SupCon) significantly boosts performance. SupCon explicitly pushes same-class samples together and different-class samples apart, creating a highly compact feature space where KNN thrives.

Feature space and distance distributions with and without contrastive learning.

State-of-the-Art Results

The authors evaluated KNN-OOD across rigorous benchmarks, proving its efficacy at scale:

  • ImageNet Superiority: On the large-scale ImageNet-1k benchmark, KNN+ (using SupCon) achieved a False Positive Rate (FPR95) of 38.47%. This is a massive 24.77% absolute reduction in errors compared to the parametric SSD+ baseline (63.24%).
  • Model Agnostic: The method works seamlessly across different architectures, including ResNets and Vision Transformers (ViT). On ViT, KNN outperformed Mahalanobis distance across all tested OOD datasets.
  • CIFAR Benchmarks: On CIFAR-10, KNN+ achieved an average FPR95 of 11.07%, outperforming other non-parametric methods like Isolation Forests (65.49%) and Local Outlier Factor (40.06%) by a wide margin.

Practicality and Limitations

Using the Faiss library for similarity search, KNN-OOD can run in milliseconds even on ImageNet-scale data, making it practical for real-time applications.

However, a primary limitation is Memory Overhead. KNN requires storing the embeddings of the training set. For datasets with billions of images, this could become a storage bottleneck. Fortunately, the authors demonstrate that sub-sampling the training set (even down to 1%) retains most of the detection performance, offering a practical workaround for massive datasets.

Effect of sub-sampling the training set on FPR95 across different values of k.

Ultimately, the quality of KNN-OOD detection remains tied to the underlying model's training. If the feature extractor fails to separate classes well, KNN will struggle. Nonetheless, by stripping away rigid parametric assumptions, KNN-OOD establishes a powerful, simple, and highly effective new baseline for out-of-distribution detection.

Summary updated

Abstract

Out-of-distribution (OOD) detection is a critical task for deploying machine learning models in the open world. Distance-based methods have demonstrated promise, where testing samples are detected ...
BibTeX
@inproceedings{sun2022out,
  author = {Yiyou Sun and Yifei Ming and Xiaojin Zhu and Yixuan Li},
  title = {{Out-of-Distribution Detection with Deep Nearest Neighbors}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=mH1c2naIFx},
}
Figure