SHEAF: Self-profiled Hardness Estimation from Answer-set Flux for Predicting Query Hardness in Graph-based ANN Search

Graph-based Approximate Nearest Neighbor (ANN) search relies on a beam-width parameter to balance recall and throughput. Typically, this parameter is fixed for an entire workload, which is inefficient because queries vary significantly in difficulty. The author investigates whether a query's required beam width can be predicted cheaply and accurately before the full search begins, without relying on ground truth or complex geometric proxies.

The paper introduces Self-profiled Hardness Estimation from Answer-set Flux (SHEAF). Instead of using static geometric measures like Local Intrinsic Dimensionality (LID), SHEAF observes the search's own behavior. It performs two shallow, low-cost probe searches at fixed beam widths and calculates the 'flux'—the degree to which the top-k answer set changes between these two widths. This flux, along with distance-based features, is fed into a lightweight regressor to predict the minimum beam width required to hit a specific recall target.

SHEAF demonstrates that a query's hardness is fundamentally algorithmic and tied to the search's convergence state. By measuring answer-set churn, the model captures how much work a query still requires. Experiments on popular indexes (CAGRA and HNSW) across four diverse datasets show that SHEAF outperforms five baseline measures, including LID, by up to 1.55x in held-out correlation. Because the probe searches are fixed and shallow, the overhead becomes asymptotically negligible for harder queries, making it a practical tool for adaptive search policies.

This work provides a robust, index-agnostic way to implement adaptive ANN search. By accurately predicting per-query difficulty, systems can dynamically allocate computational resources—using smaller beams for easy queries and larger beams for hard ones—thereby improving overall system throughput and efficiency without sacrificing recall.