SHEAF predicts ANN query hardness 1.55x better with two shallow probes
A new measure predicts per-query beam width using only answer-set flux from two shallow probes.
Dongfang Zhao introduces SHEAF, a self-profiling measure that predicts query hardness in graph-based approximate nearest neighbor (ANN) search. Traditional beam-width tuning uses a fixed parameter for all queries, but workloads show huge variance: on SIFT1M, the beam needed for 95% recall varies by 32×. Existing proxies like local intrinsic dimensionality (LID) are static and geometric, offering weak correlation. SHEAF defines hardness as the flux in a query's top-k answer set when probed at two shallow depths, then uses that flux to predict the per-query beam needed.
Experiments on CAGRA and HNSW indexes across four datasets (including SIFT1M) show SHEAF beats five baseline measures by up to 1.55× in held-out correlation. The method requires only two shallow probes and no ground truth at query time, making it deployable for adaptive query serving on both GPU and CPU. This allows systems to allocate beam width dynamically, improving throughput without sacrificing recall—a practical advance for large-scale vector search in production.
- SHEAF measures query hardness via answer-set flux between two shallow probe widths, not static geometry.
- On CAGRA and HNSW indexes, SHEAF achieves up to 1.55× better correlation with minimum beam than baselines like LID.
- Requires only two shallow probe searches and no ground truth, enabling deployable per-query beam prediction on GPU/CPU.
Why It Matters
Enables dynamic beam-width tuning for ANN search, boosting throughput while keeping recall high across diverse queries.