BH-Exit: Label-Free Early Termination for HNSW Search via Bucket-Histogram Stability

Abstract

Dense retrieval systems rely on approximate nearest neighbor (ANN) search, where early termination is crucial for latency-sensitive applications. Existing methods like ID-Overlap monitoring require exact matching between consecutive candidate sets, which is conservative---the candidate set may have converged distributionally even when exact IDs differ. We propose BH-Exit, which monitors bucket-histogram stability instead of exact ID-Overlap. Corpus vectors are assigned to buckets via offline $k$-means clustering, and search terminates when the L1 distance between consecutive bucket histograms falls below a threshold. On BEIR TREC-COVID, BH-Exit achieves 28% p50 latency improvement over ID-Overlap while maintaining equivalent retrieval quality (nDCG@10 = 0.6725). The method is robust across bucket granularities ($C \in [64, 4096]$), with improvements ranging from 13% to 40%.