Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces SHEAF, a novel method for estimating query hardness in graph-based approximate nearest neighbor (ANN) search by analyzing the flux of answer sets between shallow probe widths. Unlike the static local intrinsic dimensionality (LID), SHEAF dynamically assesses how much the top-k answer set changes, enabling more accurate per-query beam-width predictions. The results show that SHEAF outperforms five baseline measures, achieving up to 1.55 times better correlation in predicting the necessary beam width across various ANN indexes and datasets.
Query hardness can vary dramatically, and SHEAF predicts the optimal beam width for each query with unprecedented accuracy, outperforming traditional methods.
Graph-based approximate nearest neighbor (ANN) search is usually governed by a beam-width parameter that trades recall for throughput and is fixed for the whole workload. Yet, queries may not be equally hard: for example, on the widely used data set SIFT1M, the beam that a query needs to reach 95\% recall varies by more than $32\times$. Therefore, serving each query at its own width would help if the system could tell, cheaply and in advance, how hard it is. The prevailing proxy for this difficulty is called local intrinsic dimensionality (LID); however, LID is static and geometric, which makes it only weakly predict the minimum beam. This paper presents a new measure, namely Self-profiled Hardness Estimation from Answer-set Flux (SHEAF), which represents a query's hardness as how much its own top-$k$ answer set changes between two shallow probe widths. We design a self-profiling estimator that turns this flux into a deployable per-query beam predictor; furthermore, we develop a fixed-probe evaluation protocol that scores each measure over all queries with an observed minimum sufficient beam. On popular ANN indexes such as CAGRA and HNSW across four diverse data sets, SHEAF predicts the per-query beam better than five baseline measures on both GPU and CPU by up to $1.55\times$ in held-out correlation, using only two shallow probe searches and no query-time ground truth.