Task-Aware Early Termination for HNSW via Label-Histogram Stabilization

Abstract

Vector similarity search (VSS) underlies classification and retrieval systems where downstream tasks care about label correctness rather than exact neighbor identities. However, existing early termination methods for approximate nearest neighbor search optimize for traditional Recall@$K$ and are agnostic to task-specific metrics. We observe that label distributions over retrieved candidates stabilize earlier than exact neighbor identities during HNSW graph traversal, as labels are a coarser signal. Based on this insight, we propose a training-free early termination criterion that monitors the L1 distance between consecutive label histograms and terminates when stability is detected. On the Iceberg ImageNet-EVA02 benchmark, our method achieves 58.6% p50 latency reduction and 55.9% p99 latency reduction compared to fixed-efSearch baselines, while preserving Label Recall@100 within 0.01 percentage points. Compared to ID-stability early exit at the same checkpoint interval, our method achieves 19.5% lower p99 latency without sacrificing task-relevant recall.