KNN Distance for OOD

Unlike parametric methods that assume a specific distribution (e.g., Gaussian), KNN makes no assumptions about the underlying data structure. It operates directly on the feature manifold, using the distance to the k-th nearest neighbor in the training set as a normality score. This allows it to detect OOD inputs even when in-distribution data is multi-modal or has complex, non-convex boundaries. The method is purely instance-based, deferring all computation to inference time.

The choice of distance metric critically impacts detection performance. Common options include:

• Euclidean Distance (L2): Standard straight-line distance, sensitive to feature scale.
• Cosine Distance: Measures angular separation, robust to magnitude differences and preferred for high-dimensional sparse features like text embeddings.
• Mahalanobis Distance: Accounts for feature covariance, scaling distances by the inverse of the class-conditional covariance matrix. Feature normalization (e.g., L2-normalization) is often applied before distance computation to prevent high-magnitude features from dominating.

The value of k controls the bias-variance trade-off in density estimation:

• Small k (e.g., k=1): Highly sensitive to local noise and outliers. A single mislabeled training point near the boundary can create false positives. Captures fine-grained manifold structure but has high variance.
• Large k (e.g., k=50): Provides a smoother, more stable density estimate but may over-smooth the manifold boundary, missing small gaps or thin regions where OOD inputs could hide. Optimal k is typically found via validation on a held-out OOD dataset.

KNN distance is only as good as the representation space it operates in. Raw pixel or token spaces often fail to capture semantic similarity. Best practice is to extract features from a penultimate layer of a deep neural network trained on the in-distribution task. Modern approaches use contrastively learned embeddings or hyperspherical projections to ensure that semantically similar inputs cluster tightly while dissimilar ones are pushed apart, maximizing the separation between in-distribution and OOD distance scores.

The primary drawback of raw KNN is its linear inference complexity O(N * D), where N is the training set size and D is feature dimensionality. For large-scale deployments, exact search is infeasible. Mitigation strategies include:

• Approximate Nearest Neighbor (ANN) libraries like FAISS or ScaNN, which use quantization and graph-based indexing to achieve sub-linear retrieval.
• Subsampling the training set to a representative core set.
• Feature compression via PCA or random projection to reduce dimensionality before indexing.

The raw k-th neighbor distance is an uncalibrated score. To make a binary accept/reject decision, a threshold must be set. This is typically calibrated on a validation set containing both in-distribution and auxiliary OOD samples. The threshold is chosen to achieve a target True Negative Rate (TNR) at a fixed True Positive Rate (TPR) (e.g., 95% TPR). Without proper calibration, the system may either reject too many valid inputs or accept too many anomalies, undermining operational reliability.

A density-based anomaly detection method that measures the local density deviation of a data point relative to its neighbors. While KNN Distance uses absolute distance to the k-th neighbor, LOF compares local densities, making it more robust to regions of varying data density.

• Identifies points in substantially lower-density regions
• Adapts to clusters with different densities automatically
• Computationally more expensive than raw KNN distance

Deep One-Class Classification that trains a neural network to map normal data into a minimal hypersphere, flagging points far from the center as anomalies. This approach learns a compact representation explicitly optimized for distance-based detection, unlike KNN which operates on pre-trained features.

• Jointly optimizes feature extraction and anomaly scoring
• Avoids the computational burden of storing training samples
• Requires careful tuning to prevent hypersphere collapse