Out-of-Distribution Detection through Soft Clustering with Non-Negative Kernel Regression

Aryan Gulati, Xingjian Dong, Carlos Hurtado, Sarath Shekkizhar, Swabha Swayamdipta, Antonio Ortega

Introduction

As Large Language Models (LLMs) are increasingly deployed in sensitive domains such as medicine and finance, the ability to identify "Out-of-Distribution" (OOD) inputs is critical for system safety. OOD detection aims to flag data that differs significantly from the training distribution, preventing the model from making unreliable predictions on unfamiliar inputs.

Existing OOD detection strategies typically fall into two categories, each with distinct trade-offs:

  1. Distance-based methods (e.g., kNN): These provide high accuracy by comparing queries to the entire training set. However, the requirement to store and search millions of training points makes them computationally prohibitive for large-scale LLM applications.
  2. Clustering-based methods (e.g., kMeans): These are storage-efficient, as they only store a small number of cluster centers. However, "hard" clustering—assigning a point to a single center—is often too rigid, leading to misclassification of valid data at cluster boundaries.

This paper introduces NNK-Means (Non-Negative Kernel Means), a "Goldilocks" solution that combines the efficiency of clustering with the nuanced accuracy of distance-based methods.

Methodology

The core innovation is the application of soft clustering via sparse coding. Unlike kMeans, which forces a binary assignment, NNK-Means represents each data point as a weighted, non-negative linear combination of multiple cluster centers (atoms). This approach allows the model to capture the underlying geometry of the data manifold more effectively than rigid partitions.

Comparison of OOD detection strategies: kNN (distance-based), kMeans (hard clustering), and NNK-Means (soft clustering).

OOD Scoring and Reconstruction Error

The system learns a dictionary of atoms from in-distribution (ID) training data. During inference, a query's OOD score is determined by its reconstruction error: if a query cannot be accurately represented by a sparse combination of the learned atoms, it is flagged as OOD. By focusing on local geometric structure rather than global density, the method is more robust to "tail-end" phenomena in the data distribution.

Entropy-Constrained NNK-Means (EC-NNK-Means)

To further optimize efficiency, the authors propose EC-NNK-Means. This variant introduces an entropy-based regularization term that penalizes the use of redundant or low-importance cluster centers. During training, the algorithm iteratively prunes these atoms, resulting in a highly compressed dictionary that retains only the most essential representative points.

Experimental Results

The authors evaluated the method across four standard NLP benchmarks: 20 Newsgroups, Banking77, CLINC150, and AG News. The results demonstrate that NNK-Means variants outperform state-of-the-art baselines (including MSP and Energy-based scores) in 71% of experimental settings.

Efficiency and Performance Trade-offs

One of the most significant findings is the impact of the entropy constraint on model size and performance. As shown in the figures below, increasing the entropy weight allows for a massive reduction in the final number of atoms (storage) while maintaining or even improving AUROC scores.

AUROC performance and atom reduction across different entropy weights and initial dictionary sizes.

Key efficiency metrics include:

  • Storage Reduction: On the CLINC150 dataset, EC-NNK-Means achieved a 97% reduction in storage compared to kNN by representing 15,000 instances with just a few hundred atoms.
  • Inference Speed: The method delivered an 11× speedup in inference time compared to kNN-based approaches.
  • Robustness: These gains remained consistent across various text embedding types, including both frozen pre-trained models and those fine-tuned with contrastive loss.

Conclusion and Future Work

NNK-Means provides a scalable and accurate framework for OOD detection in language models. By moving from hard cluster boundaries to soft, geometric reconstructions, the method avoids the "dead zones" of traditional clustering while bypassing the computational overhead of kNN.

Future research may explore the application of these geometric properties to multilingual settings and the use of efficient dictionary learning to audit massive pre-training datasets for data quality issues.

Summary updated

Abstract

As language models become more general purpose, increased attention needs to be paid to detecting out-of-distribution (OOD) instances, i.e., those not belonging to any of the distributions seen during training. Existing methods for detecting OOD data are computationally complex and storage-intensive. We propose a novel soft clustering approach for OOD detection based on non-negative kernel regression. Our approach greatly reduces computational and space complexities (up to 11x improvement in inference time and 87% reduction in storage requirements) and outperforms existing approaches by up to 4 AUROC points on four different benchmarks. We also introduce an entropy-constrained version of our algorithm, which leads to further reductions in storage requirements (up to 97% lower than comparable approaches) while retaining competitive performance. Our soft clustering approach for OOD detection highlights its potential for detecting tail-end phenomena in extreme-scale data settings.
BibTeX
@inproceedings{gulati2024out,
  author = {Aryan Gulati and Xingjian Dong and Carlos Hurtado and Sarath Shekkizhar and Swabha Swayamdipta and Antonio Ortega},
  title = {{Out-of-Distribution Detection through Soft Clustering with Non-Negative Kernel Regression}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2024},
  doi = {10.18653/v1/2024.findings-emnlp.758},
}
Figure