Recall-Aware Early Termination in Approximate Nearest Neighbor Search

Abstract

Approximate nearest neighbor search (ANNS) is a fundamental operation in large-scale vector retrieval systems, where achieving high recall under strict latency constraints is essential. Existing ANNS approaches typically control recall using fixed search parameters, such as a predefined candidate neighbor set (CNS) size, which require significant effort to fine-tune for each use case. Even worse, due to substantial heterogeneity in query difficulty and data distribution, static parameterization often results in over-searching for easy queries and under-searching for hard ones. In this paper, we propose an adaptive framework for ANNS that explicitly incorporates user-specified recall requirements into the search process by employing an early termination strategy. We introduce two learning-based mechanisms, one for dynamically predicting the achieved recall during the search and triggers early termination once the predicted recall satisfies the target threshold, and another for estimating the minimal CNS size required to satisfy user needs during the search, enabling dynamic scaling of the CNS. Our framework is index-agnostic and can be seamlessly integrated into widely used graph-based ANN indexes, including HNSW, with negligible overhead. Extensive experiments on benchmark datasets and various graph indexes demonstrate that our methods significantly reduce query latency compared to state-of-the-art baselines. Our code is available at https://github.com/lxxabb/Recall-Aware-Early-Termination-in-Approximate-Nearest-Neighbor-Search.