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

• URL: http://arxiv.org/abs/2607.12229v1
• Date: Tue, 14 Jul 2026 00:20:13 GMT
• Title: SHEAF: Self-profiled Hardness Estimation from Answer-set Flux for Predicting Query Hardness in Graph-based ANN Search
• Abstract summary: 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.<n>We develop a fixed-probe evaluation protocol that scores each measure over all queries with an observed minimum sufficient beam.
• Score: 0.9179857807576733
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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.

Related papers

• GridProbe: Posterior-Probing for Adaptive Test-Time Compute in Long-Video VLMs [3.9266376632068485]
  GridProbe is an efficient training-free posterior-probing inference paradigm.<n>It scores evidence in answer space using a frozen VLM's own reasoning.<n>It selects question-relevant frames adaptively, resulting in sub-quadratic attention cost with little to no accuracy loss.
  arXiv  Detail & Related papers  (2026-05-11T15:57:46Z)
• δ-EMG: A Monotonic Graph Index for Approximate Nearest Neighbor Search [33.62724124122037]
  We propose an error-bounded ANN search algorithm that controls approximation accuracy during query time.<n>Under a recall requirement of 0.99, our algorithm achieves 19,000 QPS on the SIFT1M dataset, outperforming other methods by more than 40%.
  arXiv  Detail & Related papers  (2025-11-21T03:20:54Z)
• $\texttt{SPECS}$: Faster Test-Time Scaling through Speculative Drafts [55.231201692232894]
  $textttSPECS$ is a latency-aware test-time scaling method inspired by speculative decoding.<n>Our results show that $textttSPECS$matches or surpasses beam search accuracy while reducing latency by up to $sim$19.1%.
  arXiv  Detail & Related papers  (2025-06-15T05:50:05Z)
• Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search [23.208935102841103]
  We propose a new distance-based termination condition for beam search to replace the commonly used condition based on beam width.<n>We prove that, as long as the search graph is navigable, our resulting Adaptive Beam Search method is guaranteed to approximately solve the nearest-neighbor problem.<n>We find that Adaptive Beam Search outperforms standard beam search over a range of recall values, data sets, graph constructions, and target number of nearest neighbors.
  arXiv  Detail & Related papers  (2025-05-21T15:18:53Z)
• A Bi-metric Framework for Fast Similarity Search [23.254885582600775]
  We propose a new "bi-metric" framework for designing nearest neighbor data structures. Our framework assumes two dissimilarity functions: a ground-truth metric that is accurate but expensive to compute, and a proxy metric that is cheaper but less accurate. We show how to construct data structures using only the proxy metric, while only using a limited number of calls to both metrics.
  arXiv  Detail & Related papers  (2024-06-05T03:17:48Z)
• Less is More: One-shot Subgraph Reasoning on Large-scale Knowledge Graphs [49.547988001231424]
  We propose the one-shot-subgraph link prediction to achieve efficient and adaptive prediction.<n>Design principle is that, instead of directly acting on the whole KG, the prediction procedure is decoupled into two steps.<n>We achieve promoted efficiency and leading performances on five large-scale benchmarks.
  arXiv  Detail & Related papers  (2024-03-15T12:00:12Z)
• Camera Based mmWave Beam Prediction: Towards Multi-Candidate Real-World Scenarios [15.287380309115399]
  This paper extensively investigates the sensing-aided beam prediction problem in a real-world vehicle-to-infrastructure (V2I) scenario. In particular, this paper proposes to utilize visual and positional data to predict the optimal beam indices. The proposed solutions are evaluated on the large-scale real-world DeepSense $6$G dataset.
  arXiv  Detail & Related papers  (2023-08-14T00:15:01Z)
• Fast Beam Alignment via Pure Exploration in Multi-armed Bandits [91.11360914335384]
  We develop a bandit-based fast BA algorithm to reduce BA latency for millimeter-wave (mmWave) communications. Our algorithm is named Two-Phase Heteroscedastic Track-and-Stop (2PHT&S)
  arXiv  Detail & Related papers  (2022-10-23T05:57:39Z)
• IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
  Methods have to trade between obtaining high accuracy while maintaining load balance and scalability in distributed settings. We propose a novel approach called IRLI, which iteratively partitions the items by learning the relevant buckets directly from the query-item relevance data. We mathematically show that IRLI retrieves the correct item with high probability under very natural assumptions and provides superior load balancing.
  arXiv  Detail & Related papers  (2021-03-17T23:13:25Z)
• Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
  Local features provide region-to-region rather than point-to-point correspondences. We propose guidelines for effective use of region-to-region matches in the course of a full model estimation pipeline. Experiments show that affine solvers can achieve accuracy comparable to point-based solvers at faster run-times.
  arXiv  Detail & Related papers  (2020-07-20T12:07:48Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator) We first consider $gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $mathcalS$ and action space $mathcalA$. We prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level.
  arXiv  Detail & Related papers  (2020-05-26T17:53:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.