arXiv CSopen access

HNSW with Accuracy Guarantees Using Graph Spanners

arXiv:2607.02338v2 [cs.DB] 5 Jul 2026

HNSW with Accuracy Guarantees Using Graph Spanners Minghao Li

Raghav Mittal

Sanjivni Rana

University of Toronto Toronto, Canada [email protected]

The University of Texas At Arlington Arlington, Texas, USA [email protected]

The University of Texas At Arlington Arlington, Texas, USA [email protected]

Suraj Shetiya

Gautam Das

Nick Koudas

IIT Bombay Mumbai, India [email protected]

The University of Texas at Arlington Arlington, Texas, USA [email protected]

University of Toronto Toronto, Canada [email protected]

ABSTRACT Hierarchical Navigable Small World (HNSW) graphs serve as the industry standard due to their logarithmic complexity and strong empirical performance. However, HNSW relies on greedy graph traversal, a heuristic that provides no theoretical guarantees of correctness. In this paper, we propose a novel ”Certify-then-Rectify” framework that bridges the gap between the speed of heuristic search and the rigor of exact retrieval. Rather than discarding HNSW, our approach first employs a distribution-free statistical certifier to dynamically evaluate the quality of a standard HNSW search with minimal overhead. If the certification indicates that the retrieved neighbors are of low quality, the framework safely escalates to a rigorous exact recovery algorithm. To make this exact recovery computationally feasible, we reinterpret the HNSW graph as a geometric spanner and utilize Extreme Value Theory to stochastically estimate its maximum empirical stretch factor. This allows us to mathematically bound the maximum distance of true nearest neighbors. Furthermore, we successfully extend these theoretical guarantees to filtered search scenarios. Extensive evaluations on benchmark datasets demonstrate that our tiered framework delivers the average-case speed of HNSW while ensuring the worst-case correctness of exact search. PVLDB Reference Format: Minghao Li, Raghav Mittal, Sanjivni Rana, Suraj Shetiya, Gautam Das, and Nick Koudas. HNSW with Accuracy Guarantees Using Graph Spanners. PVLDB, 20(1): XXX-XXX, 2027. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/ming-afk/recall_certify_hnsw.

1

INTRODUCTION

Nearest Neighbor Search (NNS) is the computational engine behind modern AI, driving workloads ranging from Large Language Model (LLM) retrieval to molecular simulations. As datasets scale This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected]. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 20, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX

into the billions of vectors, exact linear scanning becomes computationally prohibitive, necessitating Approximate Nearest Neighbor (ANN) algorithms. Among these, Hierarchical Navigable Small World (HNSW) graphs [37, 40] have become the industry standard due to their logarithmic complexity and generally strong empirical performance.

Figure 1: Certify-then-Rectify (CTR) search framework However, HNSW relies on a greedy traversal of a proximity graph—a heuristic that offers no theoretical guarantee of recall [2, 12, 46, 57]. While HNSW performs well empirically, it is highly sensitive to hyperparameter selection (e.g., beam width, construction depth) [20, 55]. In high-dimensional spaces, greedy search frequently gets trapped in local minima, failing to retrieve the true nearest neighbor due to topology disconnects or the ”curse of dimensionality.” While a 95% recall rate is acceptable for e-commerce, it is fundamentally inadequate for logic-driven and scientific domains where a single missing entry can invalidate a result. The demand for Exact kNN is growing rapidly in complex, highstakes applications: In training perception models, identifying ”hard negatives”—images that look safe but are actually dangerous—is critical [14, 26]. If an ANN algorithm fails to retrieve these specific edge cases during data mining, the training set remains noisy, compromising safety. Exact retrieval is required to rigorously clean training distributions. In systems combining neural retrieval with symbolic logic or LLMs, vector search acts as a predicate selector. Missing a specific ”bridge” entity (e.g., a specific legal precedent or protein structure) leads to ”hallucinations” or false logical implications because the reasoning engine operates on incomplete premises [34, 50]. Existing attempts to mitigate these failures by simply increasing or predicting [12, 20] HNSW hyperparameters yield diminishing returns, incurring latency penalties without ever providing a guarantee of correctness. Moreover, they impose retraining overheads under distribution shifts.

We propose a novel framework that bridges the gap between the speed of heuristic search and the rigor of exact retrieval. We acknowledge that while our proposed search method, MBV (Metric Bound Verification) (utilizing our proposed Stretch Bounded Expansion from Query), accurately provides a formal probabilistic guarantee, it is computationally slower than heuristic HNSW. Therefore, rather than discarding HNSW, we wrap it in a Certifythen-Rectify (CTR) framework. Our approach allows users to first certify the quality of a standard HNSW search result with negligible overhead. If—and only if—the certification indicates that the retrieved neighbors are of low quality, we trigger the computationally heavier MBV algorithm to identify the exact kNN, with high tunable probability 1 . This tiered strategy provides the best of both worlds: the average-case speed of HNSW and the worst-case correctness of exact search (see Figure 1). Our implementation is also made publicly available 2 . Our contributions are structured as follows (see Figure 1):

in disconnected subgraphs. Theoretical and experimental details are in Section 8. The CTR framework is also fully integrated with DiskANN [27] in the disk-resident graph search setting and experimental details are in Section 7.10. 5. Certification of HNSW Results: We introduce a post-hoc, distribution-free statistical certification framework for vanilla HNSW. By leveraging Conformal Risk Control (CRC) [3, 4] and Learn-thenTest (LTT) [5] procedures, we construct a rigorous certifier that evaluates a distance-margin score derived purely from HNSW’s internal search state. This approach establishes finite-sample statistical guarantees on expected recall shortfall and provides perquery probabilistic bounds. Ultimately, this certifier acts as a dynamic gatekeeper with minimal computational overhead, determining whether to confidently accept the fast heuristic results or to safely escalate to exact recovery via MBV. The entire approach is realized as a lightweight wrapper around existing HNSW implementations, facilitating ease of use.

1. Stochastic Stretch Estimation (SSE):. To enable exact search, we reinterpret the HNSW graph as a geometric spanner. We introduce SSE, a sampling algorithm that accurately approximates the graph’s stretch factor t. This factor allows us to mathematically bound the maximum distance the true nearest neighbor could reside from our approximate candidates, establishing a dynamic search radius.

6. End-to-End Guarantee: We establish a formal end-to-end probabilistic recall guarantee for the complete Certify-then-Rectify framework (Section 6.4).

2 PRELIMINARIES In this section, we formalize the problem of Nearest Neighbor Search (NNS) and the structure of Hierarchical Navigable Small World (HNSW) graphs. We establish the notation for the search procedure and its computational artifacts, and we introduce the concept of graph spanners and stretch factors, which form the theoretical basis of our proposed method. Let X be a dataset of 𝑛 points in a 𝑑-dimensional vector space equipped with a distance metric 𝑑𝑖𝑠𝑡 (·, ·) (typically Euclidean distance). Given a query 𝑞 and an integer 𝑘, the Exact 𝑘-Nearest Neighbor (𝑘-NN) problem is to find the set N𝑘∗ (𝑞) ⊆ X such that |N𝑘∗ (𝑞)| = 𝑘 and ∀𝑥 ∈ N𝑘∗ (𝑞), ∀𝑦 ∈ X \ N𝑘∗ (𝑞), 𝑑𝑖𝑠𝑡 (𝑞, 𝑥) ≤ 𝑑𝑖𝑠𝑡 (𝑞, 𝑦). The HNSW index is a hierarchical graph structure approximating the proximity of points in X. It consists of a series of layers 𝐿0, 𝐿1, . . . , 𝐿𝑙𝑚𝑎𝑥 , where layer 𝐿0 contains all data points, and each subsequent layer 𝐿𝑖 contains a subset of the points from layer 𝐿𝑖 −1 , forming a hierarchy. Formally, an HNSW structure is a tuple of graphs H = (𝐺 0, 𝐺 1, . . . , 𝐺𝑙𝑚𝑎𝑥 ). Each graph 𝐺𝑖 = (𝑉𝑖 , 𝐸𝑖 ) is defined such that 𝑉𝑖 ⊆ X. The edges 𝐸𝑖 connect points within the same layer based on proximity heuristics. The hierarchy allows for logarithmic search complexity by initiating the search at the top layer (coarse granularity) and progressively refining the search region as traversal moves down to layer 𝐿0 (fine granularity). Construction proceeds iteratively by inserting points 𝑥 ∈ X. For each 𝑥, a maximum layer 𝑙 (𝑥) ≤ 𝑙𝑚𝑎𝑥 is selected randomly based on an exponential distribution. The point is inserted into all graphs 𝐺 0, 𝐺 1, . . . , 𝐺𝑙 (𝑥 ) . Connections in each layer are established using a heuristic selection strategy that balances proximity with spatial diversity (connectivity) to ensure the ”small world” property, typically bounded by a maximum degree parameter 𝑀. The search for the 𝑘-NN of a query 𝑞 in HNSW is a greedy traversal. Starting from an entry point 𝑒𝑡𝑜𝑝 in the top layer 𝐿𝑙𝑚𝑎𝑥 , the algorithm greedily moves to the neighbor minimizing 𝑑𝑖𝑠𝑡 (𝑞, ·) until a local minimum is reached. This process repeats down to layer

2. Stretch-Bounded Expansion (SBE-Q):. We present SBE-Q a technique to recover the exact neighbors. Unlike greedy heuristic descent, SBE-Q performs a principled expansion. • SBE from the Query Point (SBE-Q): We confine the search to a radius defined by the distance to the k-th approximate neighbor (𝑑𝑘 ) multiplied by the stretch factor t (i.e., radius=𝑡 × 𝑑𝑘 ). This guarantees the discovery of the true nearest neighbors. • Reservoir Sampling: To ensure SBE-Q remains theoretically sound, we use reservoir sampling to virtually ”insert” the query point q into the stretch estimation sample without altering the graph’s global stretch properties. We also explore a baseline variant, SBE-NN (Expansion from Nearest Neighbor), but find SBE-Q significantly more efficient due to its tighter bounding radius. 3. Metric Bound Verification (MBV):. Finally, we refine the candidate set obtained by SBE-Q using triangular inequality bounds derived from the stretch factor. This step recycles distance computations from the initial search to strictly filter points, ensuring the final output is the exact k-NN set. Our approach will work for any distance metric that directly or indirectly satisfies triangle inequality. 4. Utility in Filtered Search: We further demonstrate that SBEQ naturally adapts to filtered search (e.g., ”nearest vector where property P is true”), addressing scenarios where filtering fractures the small-world topology. Our techniques can be utilized within extensions like ACORN [40] to prevent traversals from getting stranded 1 In the sequel we use the term exact search when deploying MBV, with the under-

standing that the probability to identify the true kNN can be made arbitrarily high as per Section 6.4 evaluated further empirically in Section 7. 2 https://github.com/ming-afk/recall_certify_hnsw 2

𝐿0 . In layer 𝐿0 , a beam search is conducted with a beam width parameter 𝑒 𝑓 . Let this process be denoted as Search(𝑞, 𝑘, 𝑒 𝑓 ). The output of this heuristic search is an approximate set N𝑘 (𝑞) ⊆ X, where often |N𝑘 (𝑞)| < 𝑘 and N𝑘 (𝑞) ∩ N𝑘∗ (𝑞) may be empty in worst-case scenarios. Crucially, our approach utilizes the artifacts generated during this traversal. We define the Search Trace T (𝑞) as the set of all points for which the distance to 𝑞 was computed during the search:

TheoRem 3.2 (EVT Maximum StRetch Bound). According to the Fisher-Tippett-Gnedenko theorem [24], the distribution of the maximum of a large sequence of independent, identically distributed random variables converges to a specific family of distributions. For the right tail of the stretch factor distribution, the cumulative distribution function (CDF) of the block maxima converges to the Generalized Extreme Value (GEV) distribution:  h  𝑠 − 𝜇 i −1/𝜉  𝐻 (𝑠; 𝜇, 𝜎, 𝜉) = exp − 1 + 𝜉 𝜎

T (𝑞) = {𝑥 ∈ X | 𝑑𝑖𝑠𝑡 (𝑞, 𝑥) was computed during Search(𝑞, 𝑘, 𝑒 𝑓 )}.

where 𝜇 is the location parameter, 𝜎 > 0 is the scale parameter, and 𝜉 is the shape parameter. By modeling the “right tail” (the largest observed stretch factors) of our sample, we can accurately estimate the unobserved probability density of extreme stretch distortions. For a given confidence level 𝛽 ∈ (0, 1), the estimated maximum stretch factor 𝑡 ∗ is defined as the return level derived from the inverse CDF of the fitted GEV distribution:  𝜎  𝑡∗ = 𝜇 − 1 − (− ln 𝛽) −𝜉 𝜉 Thus, with confidence 𝛽, the true empirical stretch factor of the graph is bounded by 𝑡 ∗ .

This set includes the visited nodes and their immediate neighbors evaluated during the beam search. To bound the error of the approximate search, we analyze the bottom-layer graph 𝐺 0 as a geometric spanner. Definition 2.1. A weighted graph 𝐺 = (𝑉 , 𝐸), where vertices are points in a metric space (X, 𝑑𝑖𝑠𝑡), is a 𝑡-spanner if, for every pair of vertices 𝑢, 𝑣 ∈ 𝑉 , the shortest path distance in the graph, denoted 𝑑𝐺 (𝑢, 𝑣), satisfies: 𝑑𝑖𝑠𝑡 (𝑢, 𝑣) ≤ 𝑑𝐺 (𝑢, 𝑣) ≤ 𝑡 · 𝑑𝑖𝑠𝑡 (𝑢, 𝑣). The value 𝑡 ≥ 1 is called the stretch factor (or dilation) of the spanner.

3.1

In the context of NNS, the stretch factor limits how much the graph topology distorts the true metric space. If 𝐺 0 were a perfect 1-spanner (a complete graph with edge weights equal to metric distances), greedy search would be exact. The sparsification required for efficiency introduces distortion. While HNSW construction heuristics do not theoretically guarantee a constant stretch factor 𝑡 for arbitrary worst-case inputs (i.e., it is not a 𝑡-spanner by design in the traditional computational geometry sense), any realized finite HNSW graph instance 𝐺 0 possesses an intrinsic, maximum empirical stretch 𝑡𝑒𝑚𝑝 defined as: 𝑡𝑒𝑚𝑝 = max

𝑑𝐺 0 (𝑢, 𝑣)

𝑢,𝑣 ∈ X 𝑑𝑖𝑠𝑡 (𝑢, 𝑣)

.

This property is pivotal: if we know (or estimate) 𝑡𝑒𝑚𝑝 , we can relate the graph distance—which we can explore efficiently via Breadth-First Search (BFS) or Dijkstra—to the unknown metric distance 𝑑𝑖𝑠𝑡 (𝑞, 𝑥), thereby establishing a stopping condition for search expansion that guarantees the inclusion of N𝑘∗ (𝑞).

3

Practical Application of the EVT Bound

In practice, applying Theorem 3.2 requires a systematic sampling and fitting procedure prior to initiating the search. First, we generate a large pool of independent stretch factor samples by computing the exact metric distance and the shortest-path graph distance for random pairs of vertices in 𝐺. This pool is then partitioned into 𝑚 distinct blocks of size 𝑛. We extract the maximum stretch value from each block, resulting in a specialized dataset composed entirely of block maxima. Next, we apply Maximum Likelihood Estimation (MLE) to this dataset to find the optimal parameters for the Generalized Extreme Value distribution: the location 𝜇, scale 𝜎, and shape 𝜉. Once the MLE converges and the parameters are established, we substitute them—along with our target confidence level 𝛽 (e.g., 0.99)—into the GEV return level equation. The resulting value, 𝑡, acts as the rigorously defined operating stretch factor for our subsequent search expansions, ensuring the search radius dynamically adapts to the graph’s most extreme topological distortions.

4 GRAPH BASED PRUNING TECHNIQUES 4.1 Stretch Bounded Expansion from Nearest Neighbor (SBE-NN)

STOCHASTIC STRETCH ESTIMATION

For graphs of realistic sizes, computing the stretch factor exactly is not computationally feasible, as it would involve computations quadratic to the number of nodes in the graph. We, in turn, present sampling based algorithms to estimate the stretch factor of an HNSW graph 𝐺. Let 𝑆 be a random variable representing the stretch factor of a uniformly random pair (𝑢, 𝑣) from 𝑉 × 𝑉 \ {(𝑣, 𝑣) : 𝑣 ∈ 𝑉 }. Rather than estimating arbitrary percentiles, our goal is to estimate the absolute maximum empirical stretch factor via a finite sample.

We consider (X, dist) to be a metric space, where 𝐺 0 = (X, 𝐸) corresponds to the bottom-layer HNSW graph. Notably, this can be viewed as a weighted graph where each edge (𝑢, 𝑣) ∈ 𝐸 has weight dist(𝑢, 𝑣). We denote the shortest-path distance in 𝐺 0 (sum of edge weights) as 𝑑𝐺 0 (𝑢, 𝑣). Assuming 𝐺 0 to be a 𝑡-spanner (globally or locally in the vicinity of 𝑞) in the sense that for all relevant pairs 𝑢, 𝑣:

Definition 3.1 (Sample Block Maxima). Let the total sampled pairs be divided into 𝑚 blocks of size 𝑛. Let 𝑀𝑛,𝑖 = max{𝑆𝑖,1, . . . , 𝑆𝑖,𝑛 } be the maximum stretch factor observed in the 𝑖-th block.

To analyze the search expansion, we must distinguish between the approximate candidates returned by the HNSW index and the unknown ground truth.

dist(𝑢, 𝑣) ≤ 𝑑𝐺 0 (𝑢, 𝑣) ≤ 𝑡 · dist(𝑢, 𝑣)

3

For a given query 𝑞, let the ordered set of 𝑘 candidates returned by the initial HNSW search be {𝑥 (1) , 𝑥 (2) , . . . , 𝑥 (𝑘 ) }. We define the distances to the nearest and 𝑘-th candidates as: 𝑑ˆ1 = dist(𝑞, 𝑥 (1) ) and 𝑑ˆ𝑘 = dist(𝑞, 𝑥 (𝑘 ) ) Let 𝑁𝑘∗ (𝑞) denote the set of the true top-𝑘 nearest neighbors. Let 𝑑𝑘∗ denote the distance to the true 𝑘-th nearest neighbor: 𝑑𝑘∗ = max dist(𝑞, 𝑥) ∗ 𝑥 ∈𝑁𝑘 (𝑞)

Figure 2: Stretch Bound Expansion. On the left, SBE-NN expands from the first NN of q a radius 𝑑ˆ1 + 𝑑ˆ𝑘 . On the right, SBE-Q expands a radius 𝑑ˆ𝑘 from 𝑞

Since the HNSW candidates {𝑥 (1) , . . . , 𝑥 (𝑘 ) } form a valid subset of X of size 𝑘, and the true set 𝑁𝑘∗ (𝑞) minimizes the sum of distances, it necessarily holds that the true 𝑘-th distance is bounded by the approximate 𝑘-th distance: 𝑑𝑘∗ ≤ 𝑑ˆ𝑘

4.2

(1)

While SBE-NN (Section 4.1) guarantees exactness, the search radius relies on the triangle inequality to bridge the gap between the starting node 𝑥 (1) and the query 𝑞. This introduces unnecessary “slack” in the search bound—specifically the term 𝑑ˆ1 = dist(𝑥 (1) , 𝑞). In high-dimensional spaces, even the nearest neighbor may be at a significant distance from 𝑞, inflating the search radius unnecessarily. To tighten this bound, we propose SBE-Q, which conceptually initiates the expansion directly from the query point 𝑞. To formalize this, we treat the query 𝑞 as a temporary node inserted into the graph 𝐺. Let 𝐺 ′ = (𝑉 ′, 𝐸 ′ ) denote the graph augmented with 𝑞, where 𝑉 ′ = 𝑉 ∪ {𝑞}. Edges are established between 𝑞 and the top-𝑀0 computed candidates to respect graph degree upper bound. (In the case 𝑘 < 𝑀0 , we use 𝑘.) This virtual insertion alters the graph topology. In Section 4.3, we demonstrate how to efficiently test the stretch factor of 𝐺 ′ . Let 𝑡 ′ be the stretch factor of the augmented graph 𝐺 ′ (which may differ from 𝑡). We derive a bound depending solely on 𝑑ˆ𝑘 and 𝑡 ′ , eliminating the 𝑑ˆ1 overhead (see Figure 2).

This observation allows us to construct a search radius based on the observed HNSW results that guarantees the inclusion of the unknown true neighbors as per Figure 2. TheoRem 4.1 (StRetch-bounded containment of tRue top-K). Given a query 𝑞, let 𝑥 (1) be the nearest candidate and 𝑑ˆ𝑘 be the distance to the 𝑘-th candidate returned by HNSW. Every point in the true top-𝑘 set 𝑁𝑘∗ (𝑞) lies inside the graph ball of radius 𝑡 (𝑑ˆ1 + 𝑑ˆ𝑘 ) centered at 𝑥 (1) . Formally, for every 𝑥 ∗ ∈ 𝑁𝑘∗ (𝑞): 𝑑𝐺 0 (𝑥 (1) , 𝑥 ∗ ) ≤ 𝑡 (𝑑ˆ1 + 𝑑ˆ𝑘 ) Consequently: 𝑁𝑘∗ (𝑞) ⊆ {𝑥 ∈ X : 𝑑𝐺 0 (𝑥 (1) , 𝑥) ≤ 𝑡 (𝑑ˆ1 + 𝑑ˆ𝑘 )} PRoof. Let 𝑥 ∗ be any point in the true set 𝑁𝑘∗ (𝑞). By definition of the true 𝑘-th distance and Equation 1: dist(𝑞, 𝑥 ∗ ) ≤ 𝑑𝑘∗ ≤ 𝑑ˆ𝑘

(2)

TheoRem 4.2 (StRetch-Bounded Expansion fRom QeRy). Let 𝑞 be a query point virtually inserted into the graph 𝐺 such that the augmented graph 𝐺 ′ is a 𝑡 ′ -spanner. Let 𝑑ˆ𝑘 be the distance to the 𝑘-th candidate returned by HNSW. Every true top-𝑘 point lies inside the graph ball of radius 𝑡 ′ · 𝑑ˆ𝑘 centered at 𝑞. Formally, for every 𝑥 ∗ ∈ 𝑁𝑘∗ (𝑞):

Using the triangle inequality in the metric space: dist(𝑥 (1) , 𝑥 ∗ ) ≤ dist(𝑥 (1) , 𝑞) + dist(𝑞, 𝑥 ∗ )

(3)

Substituting known variables dist(𝑥 (1) , 𝑞) = 𝑑ˆ1 and the bound from Equation 2: dist(𝑥 (1) , 𝑥 ∗ ) ≤ 𝑑ˆ1 + 𝑑ˆ𝑘

𝑑𝐺 ′ (𝑞, 𝑥 ∗ ) ≤ 𝑡 ′ · 𝑑ˆ𝑘

This represents the maximum possible metric distance between the entry point 𝑥 (1) and any true answer 𝑥 ∗ . This worst-case occurs when 𝑞 lies strictly between 𝑥 (1) and 𝑥 ∗ (collinear). Since 𝐺 0 is a 𝑡-spanner, the graph distance is bounded by 𝑡 times the metric distance: 𝑑𝐺 0 (𝑥 (1) , 𝑥 ∗ ) ≤ 𝑡 · dist(𝑥 (1) , 𝑥 ∗ )

(6)

PRoof. Let 𝑥 ∗ be any arbitrary point in the true 𝑘-nearest neighbor set 𝑁𝑘∗ (𝑞). By definition of the true set and the property that the HNSW 𝑘-th distance is an upper bound (𝑑𝑘∗ ≤ 𝑑ˆ𝑘 ):

(4)

dist(𝑞, 𝑥 ∗ ) ≤ 𝑑𝑘∗ ≤ 𝑑ˆ𝑘

Combining these inequalities yields: 𝑑𝐺 0 (𝑥 (1) , 𝑥 ∗ ) ≤ 𝑡 (𝑑ˆ1 + 𝑑ˆ𝑘 )

Stretch Bounded Expansion from Query (SBE-Q)

(7)

Since the augmented graph 𝐺 ′ satisfies the 𝑡 ′ -spanner property for the pair (𝑞, 𝑥 ∗ ), the shortest path distance in 𝐺 ′ is bounded by the metric distance scaled by 𝑡 ′ :

(5)

As 𝑥 ∗ was arbitrary, the inclusion holds for all true top-𝑘 points. □

𝑑𝐺 ′ (𝑞, 𝑥 ∗ ) ≤ 𝑡 ′ · dist(𝑞, 𝑥 ∗ )

Figure 2 (left) illustrates Dijkstra’s search region as the ball with radius 𝑡 · (𝑑ˆ1 + 𝑑ˆ𝑘 ) centered at the first nearest neighbor. Any embedded vector outside of the ball is pruned.

(8)

Combining Inequality (7) and Inequality (8), we obtain: 𝑑𝐺 ′ (𝑞, 𝑥 ∗ ) ≤ 𝑡 ′ · 𝑑ˆ𝑘 4

(9)

Since this holds for any arbitrary 𝑥 ∗ ∈ 𝑁𝑘∗ (𝑞), the entire set of true nearest neighbors is contained within the graph ball 𝐵𝐺 ′ (𝑞, 𝑡 ′ · 𝑑ˆ𝑘 ). □

Algorithm 1 Incremental Reservoir Tail Patching for Stochastic Stretch Estimation Require: Existing sample 𝑆 𝑁 partitioned into 𝑚 blocks of size 𝑛 , Graph size 𝑁 , New query node 𝑧 , Target confidence 𝛽 , Previous stretch bound 𝑡 ˆ, 𝜉ˆ) , Updated return Ensure: Updated sample 𝑆 𝑁 +1 , Updated GEV parameters ( 𝜇ˆ, 𝜎 level 𝑡 ′ 1: 𝑝 ← 𝑁2+1 {Probability a random pair involves 𝑧 } 2: 𝑀𝑢𝑝𝑑𝑎𝑡𝑒 ← False {Flag to track if any block maximum requires recalculation} 3: for 𝑖 = 1 to 𝑚 do 4: for 𝑗 = 1 to 𝑛 do 5: Draw 𝑢 ∼ Uniform (0, 1) 6: if 𝑢 < 𝑝 then 7: Select random node 𝑣 ∈ 𝑉𝑁 8: Compute 𝑑𝐺 (𝑣, 𝑧 ) and 𝑑𝑋 (𝑣, 𝑧 )

Remark 1. The SBE-Q bound 𝑑𝐺 ′ (𝑞, 𝑥) ≤ 𝑡 ′ · 𝑑ˆ𝑘 is strictly tighter than the SBE-NN bound 𝑑𝐺 0 (𝑥 (1) , 𝑥) ≤ 𝑡 (𝑑ˆ𝑘 + 𝑑ˆ1 ) whenever 𝑡 ′ ≈ 𝑡. By shifting the expansion center to 𝑞, we remove the penalty 𝑑ˆ1 (the distance from the query to the closest returned candidate). In Section 7.4, we empirically demonstrate that this approach significantly reduces the volume of the graph explored while maintaining probabilistic guarantees.

𝑑

4.3

(𝑣,𝑧)

9: 𝑆𝑖,𝑗 ← 𝑑𝐺 (𝑣,𝑧) {Replace with new connection stretch} 𝑋 10: 𝑀𝑢𝑝𝑑𝑎𝑡𝑒 ← True 11: else 12: 𝑆𝑖,𝑗 ← 𝑆𝑖,𝑗 {Retain old conservative value} 13: end if 14: end for 15: end for 16: 17: if 𝑀𝑢𝑝𝑑𝑎𝑡𝑒 is True then 18: for 𝑖 = 1 to 𝑚 do 19: 𝑀𝑁 +1,𝑖 ← max(𝑆𝑖,1 , . . . , 𝑆𝑖,𝑛 ) 20: end for 21: ( 𝜇ˆ, 𝜎ˆ, 𝜉ˆ) ← MLE (𝑀𝑁 +1 ) {Fit GEV distribution to the updated block maxima} h i ˆ 22: 𝑡 ′ ← 𝜇ˆ − 𝜎ˆˆ 1 − (− ln 𝛽 ) −𝜉 {Compute new return level bound}

Figure 2 (right) illustrates Dijkstra’s search region as the ball with radius 𝑡 ·𝑑ˆ𝑘 centered at the query point 𝑞. The Dijkstra’s expansion is smaller than the expansion obtained by starting the search at the first nearest neighbor (left panel), because we do not need to traverse the additional 𝑡 · 𝑑ˆ1 term again.

Incremental Stretch Factor Estimation

For an HNSW graph 𝐺 = (𝑉 , 𝐸) of realistic size, re-evaluating the stretch factor distribution from scratch after every “virtual” query insertion is computationally prohibitive. We seek to maintain the validity of the EVT bounds derived in Section 3 without incurring the cost of a full resample. When we simulate the insertion of a query node 𝑞, the population of vertex pairs expands. To maintain a representative sample of tail extremes without full re-computation, we employ a reservoirstyle update that probabilistically injects new pairs involving 𝑞 while retaining existing sample values.

𝜉

23: else 24: 𝑡 ′ ← 𝑡 {Retain previous bound 𝑡 if reservoir was unchanged} 25: end if ˆ, 𝜉ˆ), 𝑡 ′ 26: return 𝑆 𝑁 +1 , ( 𝜇ˆ, 𝜎

Fitting the GEV distribution to these conservative maxima yields a return level 𝑡 ′ that safely upper-bounds the true maximum stretch. □

Algorithm: Incremental Reservoir Tail Patching. Because the insertion of 𝑞 adds edges to the graph, the shortest path distance 𝑑𝐺 (𝑢, 𝑣) for any existing pair (𝑢, 𝑣) can only decrease or remain constant; it cannot increase. Therefore, the previously sampled extreme stretch values either remain accurate or act as conservative overestimates. We define the update probability 𝑝 as the likelihood that a uniformly random pair in the augmented graph involves the new node 𝑞. If a newly sampled stretch factor involving 𝑞 falls into the extreme right tail, it is injected into the pool of block maxima, and the GEV parameters (𝜇, 𝜎, 𝜉) are efficiently refitted. Algorithm 1 presents the overall approach.

4.3.2 Complexity Analysis. The computational efficiency of this incremental strategy is superior to full resampling. The number of distance computations required follows a Binomial distribution 𝐾 ∼ 𝐵(𝑛, 𝑝), where 𝑝 = 𝑁2+1 . The expected number of computations is 𝐸 [𝐾] = 𝑁2𝑛 +1 . For a typical configuration where the graph size 𝑁 is large, the expected graph distance sampling cost is negligible. The primary additional overhead is the Maximum Likelihood Estimation (MLE) required to update the three GEV parameters (𝜇, 𝜎, 𝜉). Because MLE is performed solely on the small subset of extreme tail values rather than the entire sample, it operates in O (𝑚) time (where 𝑚 is the number of block maxima), effectively allowing for continuous certification with near-zero marginal cost per simulated insertion.

4.3.1 Theoretical Guarantees. We assert that the sample of extreme values updated by the Incremental Reservoir Tail Patching algorithm allows for a valid certification of the maximum stretch factor using the methodology of Theorem 3.2. TheoRem 4.3 (ConseRvative EVT CeRtification). Let 𝑆𝑒𝑥𝑡 be the pool of extreme stretch values maintained during incremental inˆ be the GEV parameters fitted to 𝑆𝑒𝑥𝑡 . For a consertion. Let ( 𝜇ˆ, 𝜎ˆ, 𝜉) fidence level 𝛽, the probability that the true maximum stretch factor of the augmented graph 𝐺 ′ does not exceed the estimated return level 𝑡 ′ is at least 𝛽.

5 METRIC BOUND VERIFICATION While the Stretch-Bounded Expansion (SBE-Q and F-SBE-Q) described in Sections 4.2 and 8 provides a theoretical containment guarantee for the true 𝑘-nearest neighbors, naively evaluating the metric distance 𝑑𝑖𝑠𝑡 (𝑞, 𝑣) for every node 𝑣 within the search radius 𝑡 ′ · 𝑑𝑘 can be computationally expensive. To bridge the gap between theoretical exactness and practical latency, we introduce Metric Bound Verification (MBV). MBV is a pruning mechanism integrated directly into the graph traversal. It exploits the triangular inequality inherent in the metric space to discard candidates within the search radius without

PRoof. The validity of this bound relies on the monotonically non-increasing nature of graph distances under edge addition. For retained pairs not involving 𝑞, the stored stretch value 𝑆 𝑜𝑙𝑑 satisfies 𝑆 𝑜𝑙𝑑 ≥ 𝑆 𝑡𝑟𝑢𝑒 . Therefore, the right tail of our sampled distribution stochastically dominates the true right tail of the augmented graph. 5

exact distance dist(𝑞, 𝑢) is computed, we can determine if the entire branch stemming from 𝑢 is effectively dead. A node 𝑢 can be discarded—preventing the addition of its neighbors to the queue— if the path through 𝑢 cannot possibly reach a point closer than the current 𝑘-th neighbor bound 𝑑ˆ𝑘 within the remaining search budget. Formally, if 𝑑𝐺 ′ (𝑞, 𝑢) is the graph distance traveled so far and 𝑅𝑠𝑒𝑎𝑟𝑐ℎ = 𝑡 ′ · 𝑑ˆ𝑘 is the current stretch-bounded radius, any descendant 𝑣 must satisfy 𝑑𝐺 ′ (𝑞, 𝑣) ≤ 𝑅𝑠𝑒𝑎𝑟𝑐ℎ . This implies the “remaining fuel” from 𝑢 is 𝑅𝑠𝑒𝑎𝑟𝑐ℎ − 𝑑𝐺 ′ (𝑞, 𝑢). If the metric distance dist(𝑞, 𝑢) exceeds this remaining capacity plus the target distance 𝑑ˆ𝑘 , no descendant can qualify. The pruning condition is (Figure 3):

Figure 3: Metric Bounded Verification. On the left, Recursive Lower Bound Pruning is shown: the parent p was pruned, and the lower bound LB(u) was then used to eliminate u. On the right, Elliptical Search Space Pruning is shown, where node u is pruned along with its descendants (Equation 11).

𝑑𝐺 ′ (𝑞, 𝑢) + dist(𝑞, 𝑢) > 𝑡 ′ · 𝑑ˆ𝑘 + 𝑑ˆ𝑘

This check tightens the search region from a simple graph ball to the intersection of the graph ball and the underlying metric constraints.

performing explicit distance computations. By maintaining recursive lower bounds on the distance from the query to the current node, we can rigorously certify that specific sub-branches of the graph cannot contain better candidates than those already found. These pruning mechanisms are universal; they apply equally to the unconstrained SBE-Q search and the filtered F-SBE-Q search, as they rely solely on metric space properties independent of node attributes.

5.1

5.3

The core of MBV relies on propagating lower bounds down the search tree (the path taken by Dijkstra’s algorithm from the virtual query node 𝑞). For any node 𝑢 visited during the expansion, let 𝑝 be its parent in the search trace (i.e., the node that added 𝑢 to the priority queue). By the triangle inequality, the metric distance dist(𝑞, 𝑢) is lower-bounded by the distance to the parent minus the edge weight connecting them:

Stretch-Bounded Expansion (SBE):. The search treats the query 𝑞 as a virtual node and expands strictly within a dynamic radius 𝑅prune = 𝑡 ′ ·𝑑ˆ𝑘 . This radius is derived from the graph’s stretch factor 𝑡 ′ and the current best-known 𝑘-th distance 𝑑ˆ𝑘 . Since the true 𝑘-th distance 𝑑𝑘∗ satisfies 𝑑𝑘∗ ≤ 𝑑ˆ𝑘 , this radius guarantees that all true 𝑘-nearest neighbors are contained within the boundary. As better candidates are discovered, 𝑑ˆ𝑘 decreases, automatically shrinking the search radius. Specifically:

(10)

Since the edge weight 𝑤 (𝑝, 𝑢) in the graph corresponds to the metric distance between 𝑝 and 𝑢, we can derive a recursive lower bound 𝐿𝐵(𝑢). This bound depends on whether the parent 𝑝 was fully evaluated or merely pruned (where only a lower bound is known).

Discovery of Better Candidates: As the expansion traverses the graph, it computes the exact metric distance 𝑑𝑡𝑟𝑢𝑒 for a visited node 𝑢. If 𝑑𝑡𝑟𝑢𝑒 < 𝑑ˆ𝑘 , 𝑢 improves upon the current top-𝑘 set. The Update Event: The algorithm inserts 𝑢 into the priority queue of results (𝑅𝑡𝑜𝑝𝐾 ) and removes the previous furthest candidate. Consequently, 𝑑ˆ𝑘 immediately decreases. Tightening the Radius: This reduction in 𝑑ˆ𝑘 triggers an immediate recalculation of 𝑅𝑝𝑟𝑢𝑛𝑒 = 𝑡 ′ · 𝑑ˆ𝑘 . The algorithm effectively “pulls in” the search horizon, pruning pending nodes in the queue that are now outside the new, tighter boundary.

• Evaluated Parent: If dist(𝑞, 𝑝) has been computed (note if this distance was in the Search Trace T (𝑞), as per section 2, it will be re-used), then: 𝐿𝐵(𝑢) = dist(𝑞, 𝑝) − 𝑤 (𝑝, 𝑢) • Pruned Parent: If 𝑝 was pruned based on its own lower bound 𝐿𝐵(𝑝), we propagate the uncertainty: 𝐿𝐵(𝑢) = 𝐿𝐵(𝑝)− 𝑤 (𝑝, 𝑢) Let 𝑑ˆ𝑘 be the distance to the current 𝑘-th nearest neighbor found so far (initially from HNSW, then updated dynamically). If 𝐿𝐵(𝑢) > 𝑑ˆ𝑘 , we can certify that 𝑢 is strictly worse than the current candidate set and cannot improve the result. Consequently, we mark 𝑢 as PRUNED and skip the expensive dist(𝑞, 𝑢) calculation (Figure 3). Crucially, we still explore 𝑢’s neighbors, as the graph topology may lead back toward 𝑞, but we do so carrying the derived lower bound.

5.2

Algorithm

The integrated procedure, SBE-Q with Metric Bound Verification, is detailed in Algorithm 2. It replaces the naive expansion phases, ensuring that expensive metric evaluations are minimized while maintaining the probabilistic guarantees of exactness derived in Theorem 4.2. This algorithm upgrades the heuristic search of an HNSW graph into an exact retrieval engine by rigorously bounding the search space and pruning unnecessary calculations. It operates through two integrated mechanisms:

Recursive Lower Bound Pruning

dist(𝑞, 𝑢) ≥ dist(𝑞, 𝑝) − dist(𝑝, 𝑢)

(11)

Metric Bound Verification (MBV):. To avoid expensive metric distance computations for every visited node, the algorithm applies two pruning checks:

Elliptical Search Space Pruning

(1) Recursive Lower Bound Pruning: It utilizes the triangle inequality to propagate lower bounds from parent nodes to their children. If a node’s lower bound distance 𝐿𝐵(𝑢)

Beyond avoiding distance computations, we can also prune the search space itself using an “Elliptical Intersection” check. If the 6

exceeds the current 𝑑ˆ𝑘 , the node is discarded without performing the expensive distance calculation. (2) Elliptical Pruning: It evaluates if a graph branch is “dead” by checking if the path through a node can possibly reach a better candidate within the remaining search budget. If 𝑑𝐺 ′ (𝑞, 𝑢) + dist(𝑞, 𝑢) > (𝑡 ′ + 1) · 𝑑ˆ𝑘 , the entire branch is pruned.

denote the sequence of metric distances from 𝑞 of the nodes popped from the bottom-layer HNSW candidate queue. A distance reversal occurs at index 𝑗 ∈ {2, . . . ,𝑇 − 1} whenever the local direction of this sequence changes, i.e.,
pop pop
𝑑 pop − 𝑑 pop < 0. 𝑗 𝑗 −1 𝑑 𝑗+1 − 𝑑 𝑗 Equivalently, the popped distances are locally non-monotone; for example, 100, 50, 120 and 50, 120, 80 each contain a reversal. Let 𝑟 𝑗 (𝑞) indicate whether a local reversal occurs at position 𝑗. We deÍ −1 fine 𝑛 rev (𝑞) = 𝑇𝑗=2 𝑟 𝑗 (𝑞) as the number of reversals, and Δrev (𝑞) as the sum of the adjacent jump magnitudes (ie. the two factors of the product in the above equation) over all positions 𝑗 with 𝑟 𝑗 (𝑞) = 1. These features quantify instability in the HNSW traversal order: larger values indicate that the search path is less geometrically consistent. Our feature-ablation results indicate that distance geometry contributes most of the score separability, while path stability statistics provide complementary gains in harder regimes: removing distance features reduces AUROC by 0.009 ∼ 0.055 across datasets. Removing reversal features has a smaller average effect but still non-negligible (up to ΔAUROC = 0.017). This supports using the full vector for cross-dataset robustness. The feature vector is then mapped through logistic regression trained on a calibration set. Crucially, the statistical guarantee is independent of the model’s predictive quality; a poor fit simply yields a more conservative certifier.

Together, these techniques guarantee the retrieval of the exact 𝑘-nearest neighbors while maintaining efficiency by aggressively filtering out unpromising candidates. Figure 3 (right) presents the Elliptical Search Space Pruning technique where the node 𝑢 is far enough from 𝑞 by graph distance (path shown in blue), such that any descendant of 𝑢 (shown by the red cloud) in the shortest-path tree will not be within the top-k as they are far away in vector space as well (shown by the orange line) and thus, can be pruned.

6

STATISTICAL CERTIFICATION VIA CONFORMAL RISK CONTROL

We frame the “Certify” phase of our “Certify-then-Rectify” workflow as a distribution-free selective prediction problem. By leveraging Conformal Risk Control (CRC) [3, 4] and Learn-then-Test (LTT) [5] procedures, we construct a rigorous statistical certifier. This certifier acts as a gatekeeper, dynamically deciding whether to trust the fast, approximate candidates returned by HNSW, or to escalate to the exact, but computationally heavier, exact recovery procedures (SBE-Q and MBV).

6.1

6.2

Problem Setup and Certifiability Score

Guaranteeing Expected Shortfall via CRC

To guarantee the average quality of the certified results without making underlying distributional assumptions about the metric space, we utilize the Conformal Risk Control (CRC) framework. We define the recall shortfall as our per-query loss function:

Let N𝑘 (𝑞) represent the approximate top-𝑘 candidates returned by the vanilla HNSW greedy traversal. Let N𝑘∗ (𝑞) represent the true 𝑘nearest neighbors obtained via an exact oracle (in our framework, this oracle is SBE-Q coupled with MBV). We define the per-query recall as: |N𝑘 (𝑞) ∩ N𝑘∗ (𝑞)| 𝑅𝑒𝑐𝑎𝑙𝑙 (𝑞) = (12) 𝑘 Given a target recall threshold 𝜏 ∈ (0, 1], we call a top-𝑘 result set ”compliant” to 𝜏 if 𝑅𝑒𝑐𝑎𝑙𝑙 (𝑞) ≥ 𝜏. Given 𝜏 and a target risk level 𝛼 ∈ (0, 1), our goal is to build a certifier 𝐶 (𝑞) that outputs “accept” only when it can statistically guarantee that the top-𝑘 result set is compliant with 𝜏. To achieve this, we define a score 𝑠 (𝑞) from HNSW’s internal search trace. We use a compact feature vector 𝑧 (𝑞) that captures (i) distance geometry, (ii) search reach, and (iii) path stability: h i 𝑧 (𝑞) = 𝑑ˆ1, . . . 𝑑ˆ100, 𝑑˜1, . . . , 𝑑˜10, |T (𝑞)|, 𝑛 rev (𝑞), Δrev (𝑞) .

𝑙 (𝑞) = max(0, 𝜏 − 𝑅𝑒𝑐𝑎𝑙𝑙 (𝑞))

(13)

Given a calibration set D𝑐𝑎𝑙 = {(𝑞𝑖 , N𝑘∗ (𝑞𝑖 ))}𝑛𝑖=1 drawn i.i.d. from an unknown query distribution P, the procedure operates as follows: (1) Compute the score 𝑠𝑖 = 𝑠 (𝑞𝑖 ) and the loss 𝑙𝑖 for each calibration query, sorting them in descending order of their score. (2) For any candidate threshold 𝜃 , define the empirical risk as: Í𝑛 𝑙𝑖 · 1 [𝑠𝑖 ≥ 𝜃 ] ˆ 𝑅(𝜃 ) = Í𝑛𝑖=1 (14) 1 𝑖=1 [𝑠𝑖 ≥ 𝜃 ] + 1 (3) Select the optimal threshold 𝜃ˆ that bounds this empirical risk: o n ˆ ) ≤ 𝛼 (1 − 𝜏) · 𝑛 (15) 𝜃ˆ = inf 𝜃 : 𝑅(𝜃 𝑛+1

𝑑ˆ1, . . . , 𝑑ˆ100 are the top-100 returned distances, and in the case 𝑘 < 100, we pad with 0 entries. 𝑑˜1, . . . , 𝑑˜10 are the remaining top10 candidate-frontier distances at termination. These features capture distance geometry. Following previous work [10], we capture the search reach with |T (𝑞)|, where T (𝑞) is the search trace defined in Section 2. We use distance-reversal statistics for path stability: 𝑛 rev (𝑞) is the number of direction reversals in successive expansion distances, and Δrev (𝑞) is their cumulative magnitude. More precisely, let

Theorem 6.1 (CRC Guarantee for HNSW Recall). If the calibration queries 𝑞 1, ..., 𝑞𝑛 are i.i.d. from P, then for a new test query 𝑄 ∼ P, the certifier 𝐶 (𝑄) = 1 [𝑠 (𝑄) ≥ 𝜃ˆ] satisfies: E[𝑙 (𝑄) · 1 [𝑠 (𝑄) ≥ 𝜃ˆ]] ≤ 𝛼 (1 − 𝜏)

(16)

This guarantee is exact in a finite-sample sense and requires no knowledge of HNSW’s internal workings.

𝑑 1pop, 𝑑 2pop, . . . , 𝑑𝑇pop 7

6.3

Pointwise Guarantees via Learn-then-Test (LTT)

property on every pair (𝑞, 𝑥 ∗ ) with 𝑥 ∗ ∈ N𝑘∗ (𝑞). Under Assumption 1,   Pr MBV(𝑞) = N𝑘∗ (𝑞) 𝐶 (𝑞) = 0 ≥ 𝛽. 𝜔

If a strict, per-query probabilistic guarantee is required, we deploy the Learn-then-Test (LTT) framework. LTT controls the certifier’s precision, ensuring that P𝑞∼P [𝑅𝑒𝑐𝑎𝑙𝑙 (𝑞) ≥ 𝜏 | 𝑠 (𝑞) ≥ 𝜃ˆ] ≥ 1 − 𝜖 with a confidence level of 1 − 𝛼. We split the calibration set D𝑐𝑎𝑙 into a training set D𝑡𝑟 and a test set D𝑡𝑒 . From D𝑡𝑟 , we define a finite set of candidate thresholds Θ. For each candidate threshold 𝜃 ∈ Θ evaluated on D𝑡𝑒 , we test the null hypothesis 𝐻 0𝜃 : P[𝑅𝑒𝑐𝑎𝑙𝑙 (𝑞) < 𝜏 | 𝑠 (𝑞) ≥ 𝜃 ] > 𝜖. Let 𝑚𝜃 denote the number of certified queries and 𝑥𝜃 denote the subset of those queries that failed to meet the target recall. We compute the one-sided binomial p-value:  𝑥𝜃  Õ 𝑚𝜃 𝑗 p-value = 𝜖 (1 − 𝜖)𝑚𝜃 − 𝑗 (17) 𝑗 𝑗=0

PRoof. By the conservative EVT certification (Theorem 4.3, via Theorem 3.2), the return level 𝑡𝜔′ upper-bounds the true maximum stretch of 𝐺𝑞′ with confidence at least 𝛽, i.e. Pr𝜔 [E𝜔 ] ≥ 𝛽. Condition on E𝜔 . Theorem 4.2 then yields the containment
N𝑘∗ (𝑞) ⊆ 𝐵𝐺𝑞′ 𝑞, 𝑡𝜔′ 𝑑ˆ𝑘 , so SBE-Q’s Dijkstra expansion, which explores exactly this graph ball, visits every true neighbor. The MBV pruning steps are lossless on the true top-𝑘: a node 𝑢 is discarded only when its certified lower bound satisfies 𝐿𝐵(𝑢) > 𝑑ˆ𝑘 , and since 𝑑ˆ𝑘 ≥ 𝑑𝑘∗ ≥ dist(𝑞, 𝑥 ∗ ) for every 𝑥 ∗ ∈ N𝑘∗ (𝑞) throughout the traversal, no true neighbor can ever trigger the pruning condition; the elliptical check is dominated by the same inequality. As 𝑑ˆ𝑘 decreases monotonically toward 𝑑𝑘∗ , the dynamic radius never drops below 𝑑𝑘∗ . Hence, under Assumption 1, the procedure returns precisely N𝑘∗ (𝑞) on E𝜔 , and the claim follows. □

To account for multiple testing over Θ, we apply a Bonferroni cor𝛼 rection, rejecting 𝐻 0𝜃 only if p-value ≤ |Θ| . The final threshold is selected as: 𝜃ˆ = max{𝜃 ∈ Θ : 𝐻 0𝜃 is rejected} (18)

6.4

Because the reservoir patch re-fits 𝑡 ′ for each 𝐺𝑞′ individually (Algorithm 1), Lemma 6.1 is per-query and transfers to 𝑄 ∼ 𝑃 with no distributional assumption: Pr𝑄,𝜔 [Recall(𝑄) = 1 | 𝐶 (𝑄) = 0] ≥ 𝛽.

End-to-End Guarantee

We certify two different events: the stochastic stretch estimation (SSE) underwrites exactness of the rectify branch with extremevalue confidence 𝛽, while the conformal certifier (CRC/LTT) controls 𝜏-recall on the certify branch with a distribution-free guarantee. The end-to-end behaviour of CTR is therefore a mixture over the certify/escalate split, and the two guarantees live on independent probability spaces. We make this precise here.

Lemma 6.2 (CeRtify bRanch, Restated). With the score 𝑠, threshold 𝜃ˆ, and loss ℓ of Section 6:  (1) (CRC,exact, marginal over Dcal × 𝑃) E ℓ (𝑄) 1[𝐶 (𝑄) =  1] ≤ 𝛼 (1 − 𝜏).  (2) (LTT; per-query, confidence 1−𝛼 over Dcal ) Pr𝑄 Recall(𝑄) ≥  𝜏 𝐶 (𝑄) = 1 ≥ 1 − 𝜖.

Sources of randomness. We isolate three independent sources: (i) the calibration sample Dcal = {(𝑞𝑖 , N𝑘∗ (𝑞𝑖 ))}𝑛𝑖=1 ∼ 𝑃 𝑛 , which fixes the threshold 𝜃ˆ; (ii) a fresh test query 𝑄 ∼ 𝑃; and (iii) the reservoir/SSE sampling 𝜔 used to fit the augmented stretch factor 𝑡 ′ on the query-augmented graph 𝐺𝑄′ , drawn only when 𝑄 is escalated. Let 𝐶 (𝑞) = 1[ 𝑠 (𝑞) ≥ 𝜃ˆ ] denote the certifier (Section 6), and let b (𝑄) be the CTR output: N b (𝑄) = N𝑘 (𝑄) if 𝐶 (𝑄) = 1 (certify), and N b (𝑄) = MBV(𝑄) if 𝐶 (𝑄) = 0 (escalate). Write 𝜌 := Pr𝑄 [ 𝐶 (𝑄) = N ˆ 1 ] for the certify rate induced
by 𝜃 , and recall the per-query loss ℓ (𝑞) = max 0, 𝜏 − Recall(𝑞) .

TheoRem 6.3 (End-to-end 𝜏-compliance of CTR). Suppose Assumptions 1–2 hold. (1) Per-query form (LTT route). With probability at least 1−𝛼 over the draw of Dcal ,   Pr Recall(𝑄) ≥ 𝜏 ≥ 𝜌 (1 − 𝜖) + (1 − 𝜌) 𝛽 ≥ min(1 − 𝜖, 𝛽). 𝑄,𝜔

(2) Expected-shortfall form (CRC route; unconditional, finitesample exact). 
 E max 0, 𝜏 − Recall(𝑄) ≤ 𝛼 (1 − 𝜏) + (1 − 𝛽) 𝜏, equivalently E[Recall(𝑄)] ≥ 𝜏 − 𝛼 (1 − 𝜏) − (1 − 𝛽) 𝜏 .

Assumptions.

PRoof. (i) Condition on the certify/escalate split, which is a function of (𝑄, 𝜃ˆ) and is independent of the SSE randomness 𝜔:

Assumption 1 (Reachability). For every escalated query 𝑞, each true neighbor 𝑥 ∗ ∈ N𝑘∗ (𝑞) is reachable from 𝑞 in the augmented bottomlayer graph 𝐺𝑞′ .

Pr[Recall(𝑄) ≥ 𝜏] = 𝜌 Pr[Recall ≥ 𝜏 | 𝐶=1]+(1−𝜌) Pr[Recall ≥ 𝜏 | 𝐶=0]. On the event of probability 1 − 𝛼 over calibration, the first conditional is ≥ 1 − 𝜖 by Lemma 6.2(2). The second is ≥ 𝛽 by Lemma 6.1, since exact recovery gives Recall = 1 ≥ 𝜏. The mixture is a convex combination of 1 − 𝜖 and 𝛽, hence at least their minimum. (ii) Decompose the expected loss by the certifier,     E[ℓ (𝑄)] = E ℓ (𝑄)1[𝐶=1] + E ℓ (𝑄)1[𝐶=0] . | {z }

Assumption 2 (Calibration oracle). The ground-truth labels N𝑘∗ (𝑞𝑖 ) used to calibrate 𝜃ˆ are the true top-𝑘 sets. Assumption 1 is the connectivity caveat of vanilla HNSW (cf. the rare 𝑖𝑛 𝑑𝑒𝑔𝑟𝑒𝑒 = 0 nodes); without it even exhaustive expansion within the stretch ball can miss a neighbor. Assumption 2 is discussed and relaxed in Remark 4.

≤ 𝛼 (1−𝜏 ) (Lemma 6.2(1))

On the escalate branch ℓ (𝑄) = 0 whenever the stretch event E𝜔 holds (Lemma 6.1), and ℓ (𝑄) ≤ 𝜏 otherwise; as Pr𝜔 [¬E𝜔 ] ≤ 1 − 𝛽

Lemma 6.1 (Exactness of the Rectify bRanch). Fix an escalated query 𝑞 and let E𝜔 be the event that 𝐺𝑞′ satisfies the 𝑡𝜔′ -spanner 8

Algorithm 2 Stretch-Bounded Expansion with MBV

independently of the split, the second term is at most 𝜏 (1 − 𝛽). Summing yields the bound. □

Require: Query 𝑞 , Graph 𝐺 ′ , Stretch 𝑡 ′ , Initial Candidates H𝑓 𝑜𝑢𝑛𝑑 Ensure: Exact 𝑘 -nearest neighbor set N𝑘∗ (𝑞) 1: Initialize: 2: 𝑅𝑡𝑜𝑝𝐾 ← Max-Priority Queue of size 𝑘 (seeded with H𝑓 𝑜𝑢𝑛𝑑 [: 𝑚𝑖𝑛 (𝑀0 , 𝑘 ) ] ) 3: 𝑄 𝑣𝑖𝑠𝑖𝑡 ← Min-Priority Queue ordered by graph distance 𝑑𝐺 ′ 4: 𝑆𝑡𝑎𝑡𝑒 ← Map (node_id: {status, val}) 5: Set initial bound based on HNSW results: 6: 𝑑ˆ𝑘 ← 𝑅𝑡𝑜𝑝𝐾 .𝑚𝑎𝑥 _𝑑𝑖𝑠𝑡 () 7: 𝑅𝑝𝑟𝑢𝑛𝑒 ← 𝑡 ′ · 𝑑ˆ𝑘

CoRollaRy 6.4 (PRobability of identifying the tRue 𝑘-NN). Exact identification of the true 𝑘 nearest neighbors corresponds to the compliance target 𝜏 = 1. Under Assumptions 1–2, with probability at least 1 − 𝛼 over Dcal ,   b (𝑄) = N ∗ (𝑄) ≥ 𝜌 (1 − 𝜖) + (1 − 𝜌) 𝛽 ≥ min(1 − 𝜖, 𝛽). Pr N 𝑘

8: 𝑄 𝑣𝑖𝑠𝑖𝑡 .𝑝𝑢𝑠ℎ (0, 𝑞, null ) {(distance, node, parent)} 9: 𝑆𝑡𝑎𝑡𝑒 [𝑞 ] ← { status: EVALUATED, val: 0 } 10: while 𝑄 𝑣𝑖𝑠𝑖𝑡 is not empty do 11: (𝑑𝑔𝑟𝑎𝑝ℎ , 𝑢, 𝑝 ) ← 𝑄 𝑣𝑖𝑠𝑖𝑡 .𝑝𝑜𝑝 () 12: if 𝑑𝑔𝑟𝑎𝑝ℎ > 𝑅𝑝𝑟𝑢𝑛𝑒 then 13: break {Dynamic Termination} 14: end if 15: Calculate Lower Bound (MBV): 16: 𝐿𝐵𝑢 ← −∞ 17: if 𝑝 ≠ null then 18: 𝑤 ← edge_weight (𝑝, 𝑢 ) 19: 𝐿𝐵𝑢 ← 𝑆𝑡𝑎𝑡𝑒 [𝑝 ].𝑣𝑎𝑙 − 𝑤 {Propagate distance or bound} 20: end if 21: Pruning Check & Metric Computation: 22: if 𝐿𝐵𝑢 > 𝑑ˆ𝑘 then 23: 𝑆𝑡𝑎𝑡𝑒 [𝑢 ] ← { status: PRUNED, val: 𝐿𝐵𝑢 } {Skip expensive distance call} 24: else 25: 𝑑𝑡𝑟𝑢𝑒 ← 𝑑𝑖𝑠𝑡 (𝑞, 𝑢 ) {Expensive computation} 26: 𝑆𝑡𝑎𝑡𝑒 [𝑢 ] ← { status: EVALUATED, val: 𝑑𝑡𝑟𝑢𝑒 } 27: Update Result Set: 28: if 𝑑𝑡𝑟𝑢𝑒 < 𝑑ˆ𝑘 then 29: 𝑅𝑡𝑜𝑝𝐾 .𝑝𝑢𝑠ℎ (𝑑𝑡𝑟𝑢𝑒 , 𝑢 ) 𝑑ˆ𝑘 ← 𝑅𝑡𝑜𝑝𝐾 .𝑚𝑎𝑥 _𝑑𝑖𝑠𝑡 () 30: 31: 𝑅𝑝𝑟𝑢𝑛𝑒 ← 𝑡 ′ · 𝑑ˆ𝑘 {Dynamically tighten search radius} 32: end if 33: Elliptical Pruning (Look-ahead): 34: if 𝑑𝑔𝑟𝑎𝑝ℎ + 𝑑𝑡𝑟𝑢𝑒 > 𝑅𝑝𝑟𝑢𝑛𝑒 + 𝑑ˆ𝑘 then 35: continue {Entire branch pruned} 36: end if 37: end if 38: Expand Neighbors: 39: for all neighbor 𝑣 of 𝑢 in 𝐺 ′ do 40: if 𝑣 ∉ 𝑆𝑡𝑎𝑡𝑒 then 41: 𝑛𝑒𝑤 _𝑑 ← 𝑑𝑔𝑟𝑎𝑝ℎ + edge_weight (𝑢, 𝑣) 42: 𝑄 𝑣𝑖𝑠𝑖𝑡 .𝑝𝑢𝑠ℎ (𝑛𝑒𝑤 _𝑑, 𝑣, 𝑢 ) 43: end if 44: end for 45: end while 46: return 𝑅𝑡𝑜𝑝𝐾

𝑄,𝜔

In particular, as 𝜖 → 0, 𝛼 → 0, and 𝛽 → 1, the bound tends to 1: the probability of recovering the true 𝑘-NN can be made arbitrarily high. PRoof. Set 𝜏 = 1 in Theorem 6.3(i) and note that Recall(𝑄) ≥ 1 b (𝑄) = N ∗ (𝑄). is equivalent to N □ 𝑘 Remark 2 (Why 𝜏 = 1 forces the LTT route). At 𝜏 = 1 the CRC bound of Theorem 6.3(ii) degenerates to E[ℓ (𝑄)] ≤ 1 − 𝛽: the conformal term 𝛼 (1−𝜏) vanishes and all exactness flows from the EVT guarantee on the escalate branch. For the operating points used in our experiments (𝜏 = 0.9), certified queries return plain HNSW, which is only 𝜏-good and carries no exactness guarantee; the honb (𝑄) = est unconditional bound on exact identification is then Pr[ N ∗ N𝑘 (𝑄)] ≥ (1 − 𝜌)𝛽 plus HNSW’s uncontrolled exact rate on the certified fraction. Thus Corollary 6.4 is a statement about the 𝜏 = 1 regime; for 𝜏 < 1 the meaningful end-to-end claim is the compliance guarantee of Theorem 6.3, not exactness. Remark 3 (Two probability spaces). The confidence 𝛽 is an extremevalue return-level guarantee over the stretch sampling 𝜔, whereas 1 − 𝜖 and 1 − 𝛼 are distribution-free conformal guarantees over 𝑃 and Dcal . The mixture in Theorem 6.3(i) is valid precisely because these sources are independent. They are not interchangeable: 𝛽 inherits the usual GEV extrapolation optimism of a fitted return level, while the conformal quantities are finite-sample exact. Remark 4 (Oracle-in-calibration coupling). The labels N𝑘∗ (𝑞𝑖 ) in Dcal are produced by the same MBV oracle, which is itself exact only with confidence 𝛽 per query (Lemma 6.1). Consequently the conformal guarantees are, strictly, recall-relative-to-oracle. To make them recall-relative-to-truth one either assumes Assumption 2 directly, or pays a union bound over the calibration set, replacing 1 − 𝜖 by 1 − 𝜖 − 𝑛(1 − 𝛽) in Theorem 6.3(i). This is the single point at which the two phases are not cleanly independent. The theorem is validated empirically in Section 7.

6.5

Dataset SIFT1M GIST1M DEEP1M T2I10M T2I100M

Description Image feature transform vectors GIST image descriptors Subset of deep image features Subset of multimodal text-to-image search Subset of multimodal text-to-image search

𝑑 128 960 96 200 200

metric l2 l2 l2 cosine cosine

#queries 10k 1k 10k 5k 5k

Table 1: Statistics Of Datasets Used

7 EXPERIMENTS 7.1 Datasets and Implementation Setup

The Query-Time Decision Rule

We augment nmslib/hnswlib3 in C++ to implement the proposed CTR pipeline, including the rectification algorithm, namely MBV, on top of HNSW. We evaluate the system on three standard benchmark datasets: SIFT1M, GIST1M4 , and DEEP1M, and two datasets for scalability test in Section 7.7: Text-to-Image (T2I) 10M and T2I

With 𝜃ˆ calibrated, the online query processing acts as a simple, two-step decision process: Require: Query 𝑞 1: Run HNSW to obtain N𝑘 (𝑞) and compute the score 𝑠 (𝑞) . 2: if 𝑠 (𝑞) ≥ 𝜃ˆ then 3: CERTIFY: Return N𝑘 (𝑞) . 4: else 5: ESCALATE: Run the exact oracle (SBE-Q and MBV) and return N𝑘∗ (𝑞) . 6: end if

3 https://github.com/nmslib/hnswlib

4 Both SIFT1M and GIST1M from: http://corpus-texmex.irisa.fr/

9

100M5 (vectors normalized). Dataset statistics are detailed in Table 1. All tests run with a single thread on an Intel Xeon Ice Lake 3.5 GHz processor with 247 GB memory and are memory-resident. For compilation, we use −𝑂3 and -march=native. We vary 𝑀, 𝑒 𝑓𝑐 (beam width during construction), 𝑒 𝑓𝑠 , and 𝑘 and examine both the cost of exact rectification and the behavior of the certification stage under different HNSW operating points. We therefore use a fixed 90% of queries provided by each dataset (the last column of Table 1) as the calibration set for conformal predictor training.

7.2

Validating Stretch Estimation via Level-2 Ground Truth

Figure 5: Effect of varying M and 𝑒 𝑓𝑐 on stretch

We validate our stochastic stretch estimation and characterize its sensitivity to key EVT hyperparameters using the level-2 HNSW subgraph, where the true maximum stretch 𝑡𝑒𝑚𝑝 is computable by brute force over a tractable number of nodes6 . We ablate the two parameters that must be committed to before sampling—confidence level 𝛽 and block count 𝑚—across (𝛽, 𝑚) ∈ {0.95, 0.995}×{200, 400} and vary sample size to generate four stretch value curves, using the brute-force 𝑡𝑒𝑚𝑝 as ground truth. Test is conducted on SIFT, GIST, and DEEP with 𝑀=32, 𝑒 𝑓𝑐 =100. In Figure 4, we show that higher 𝛽 consistently raises 𝑡 ∗ since it selects a higher quantile of the fitted GEV and is more conservative. A larger block count (𝑚=400) yields higher, more conservative estimates than 𝑚=200: more blocks supply more fitting points to the GEV, enabling better characterization of the upper tail of stretch values, whereas fewer blocks underfit the extremes. This comes at a convergence cost—𝑚=400 saturates more slowly because smaller per-block samples produce more variable block maxima, so the fitted return level continues drifting as sample size grows rather than leveling off. Despite these differences, all (𝛽, 𝑚) configurations yield a stable fitted 𝑡 ∗ —one whose value no longer changes meaningfully with additional samples—by approximately 150k sampled pairs across all three datasets. High-confidence settings (𝛽=0.995) with large 𝑚 consistently yield estimates that bound the true empirical stretch with a safe margin, whereas lower-confidence configurations reduce estimation accuracy. Therefore, for base-layer operation in later sections we use the conservative 𝑚=400, 𝛽=0.995 setting to mitigate stretch underestimation probability. m = 200, = 0.95 m = 200, = 0.995

m = 400, = 0.95 m = 400, = 0.995

SIFT

5

GIST

t*

5.0 4.5

4

4.0 20 50

100

150

200

true max stretch

20 50

100

150

200

DEEP 3.75 3.50 3.25 3.00

sample size in thousands (k)

20 50

100

150

200

Figure 4: Stretch estimation ablating 𝛽 and block count 𝑚.

5 Both DEEP and T2I from: https://research.yandex.com

6 Vanilla HNSW has no guarantee in connectivity (see also [40]). Our stretch calcula-

tion is therefore conducted only for reachable nodes, despite unreachable nodes being rare (3 𝑖𝑛 𝑑𝑒𝑔𝑟𝑒𝑒=0 nodes in our SIFT1M 𝑀=16, 𝑒 𝑓 𝑐=200 graph). 10

7.3

Stretch and HNSW Construction Parameters

To further investigate how HNSW construction parameters influence the empirical maximum stretch of the resulting graph, we adopt the same Stochastic Stretch Estimation (SSE) procedure described in Section 7.2 and repeat it for graphs derived from various HNSW construction parameters. We report the estimated stretch across SIFT1M and DEEP1M, and use a parameter grid spanning 𝑀 ∈ {16, 32, 48, 64}, 𝑒 𝑓𝑐 ∈ {100, 200, 300}, with 𝛽 = 0.995 fixed throughout. The results are presented in Figure 5. The graph shows that for fixed 𝑒 𝑓𝑐 , increasing 𝑀 consistently reduces the stretch, reflecting improved graph connectivity. Similarly, for fixed 𝑀, larger 𝑒 𝑓𝑐 yields lower stretch, indicating higherquality nearest-neighbor connections during construction. These findings align with the role of HNSW construction in shaping the graph’s effective spanner properties and its associated stretch behavior.

7.4

System Ablation

We compare the number of distance computations (NDC) required to return the true 𝑘 nearest neighbors across system variants. For ease of display, NDC is reported as a percentage of the total number of base nodes in the 1M-size datasets we use (NDC % of 1M), eg. 1% means we did 10k distance computations. Experiments fix 𝑒 𝑓𝑠 =100 and vary 𝑘 ∈ {10, 50, 100}. We evaluate four index configurations (𝑀, 𝑒 𝑓𝑐 ) ∈ {16, 32} × {100, 200} on three datasets (SIFT1M, DEEP1M, GIST1M). This experiment is independent of the final certification stage and no target recall is enforced. Experimental setup. In these experiments, we fix the underlying HNSW parameters to 𝑀=32, 𝑒 𝑓𝑐 =200, and 𝑒 𝑓𝑠 =100. Results are averaged over 100 random queries. In Figure 6, panels (a)–(c) show CRC and panels (d)–(f) show LTT on the three datasets. We fix the target recall threshold to 𝜏=0.90, and for LTT we set 𝜖=0.5. Each blue point is an operating point obtained by varying 𝛼, and the numeric annotation next to the point is the corresponding 𝛼 value; runtime is reported on the x-axis as a multiple of plain HNSW under the same configuration. In Figure 7, we keep the same HNSW configuration and vary 𝜏, with 𝛼=0.05 and 𝜖=0.5 specifically for LTT; panels (a)–(c) show plain HNSW, panels (d)–(f) show CRC, and panels (g)–(i) show LTT.

Dataset

SIFT1M

DEEP1M

GIST1M

Metric 𝑘 𝑡 SBE-NN SBE-NN+LBP&EP SBE-Q SBE-Q+LBP MBV 𝑡 SBE-NN SBE-NN+LBP&EP SBE-Q SBE-Q+LBP MBV 𝑡 SBE-NN SBE-NN+LBP&EP SBE-Q SBE-Q+LBP MBV

𝑀 = 16, 𝑒 𝑓𝑐 = 100 10 50 100 4.059 4.059 4.059 48.95 50.54 51.41 40.07 42.31 43.20 5.60 14.07 18.66 4.01 11.19 15.54 3.85 6.37 7.91 4.251 4.251 4.251 81.03 84.75 86.52 70.88 76.72 79.33 3.82 12.60 20.89 3.48 10.04 17.23 3.29 6.46 10.11 4.470 4.470 4.470 84.91 86.08 86.63 80.27 81.64 82.27 15.67 31.42 38.75 15.49 28.52 35.71 15.01 23.62 26.04

𝑀 = 16, 𝑒 𝑓𝑐 = 200 10 50 100 3.853 3.853 3.853 48.16 49.66 50.47 39.95 43.14 44.61 4.04 11.38 15.82 2.88 8.95 12.99 2.80 4.84 6.08 4.148 4.148 4.148 71.36 76.12 78.40 55.45 61.76 64.69 1.39 5.96 15.82 1.22 4.35 13.29 1.20 2.73 9.48 4.119 4.119 4.119 83.83 85.15 85.77 77.69 79.22 79.93 10.04 23.54 30.90 9.75 20.95 27.85 9.70 16.55 18.58

𝑀 = 32, 𝑒 𝑓𝑐 = 100 10 50 100 3.657 3.657 3.657 47.42 48.59 49.21 39.30 42.24 43.54 3.40 10.13 14.22 2.45 7.85 11.60 2.38 4.33 5.51 4.067 4.067 4.067 83.43 86.86 88.51 73.95 79.45 81.86 4.71 14.32 20.03 4.12 11.49 16.09 4.07 7.77 8.52 3.930 3.930 3.930 85.10 86.40 87.01 78.98 80.55 81.26 9.42 22.89 30.39 8.96 19.88 27.08 8.94 15.58 17.52

𝑀 = 32, 𝑒 𝑓𝑐 = 200 10 50 100 3.601 3.601 3.601 48.47 50.00 50.83 40.67 43.84 45.32 3.62 10.37 14.67 2.57 8.23 12.11 2.51 4.59 5.89 3.867 3.867 3.867 83.08 86.53 88.19 72.84 78.49 80.99 3.65 12.64 19.07 3.08 9.51 14.72 3.05 6.70 8.40 3.646 3.646 3.646 83.95 85.26 85.87 76.31 78.05 78.85 6.66 17.26 24.07 5.80 14.25 20.42 5.64 11.47 13.15

Table 2: NDC as percentage of 1M base nodes across SIFT1M, DEEP1M, and GIST1M.

7.5

Compared variants. We organise the variants into two families and compare five of them. The baselines,SBE-NN and SBE-Q, are expansion strategies that identify candidate nodes within the stretchbounded radius without any pruning of final distance computations.Applying the methods lower-bound pruning (LBP) and elliptical pruning (EP) on top of SBE-NN yields SBE-NN+LBP&EP,and on SBE-Q gives the proposed MBV. To isolate the individual contribution of LBP and EP,we additionally include SBE-Q+LBP, which applies only the LBP component to SBE-Q;the gap between SBEQ+LBP and MBV in Table 2 quantifies the saving attributable to EP. Results. Table 2 reveals two consistent trends. First, SBE-Q is a substantially stronger baseline than SBE-NN across all configurations, owing to its smaller expansion radius: eliminating the additive 𝑑ˆ1 term present in SBE-NN dramatically shrinks the graph region explored during rectification. Building on SBE-Q, applying LBP (SBE-Q+LBP) further reduces NDC by 14.3–26.4% across configurations relative to SBE-Q alone. Adding EP on top (MBV) achieves an additional 25.8–58.3% reduction across configurations by adaptively tightening the truncation radius as the running maximum of discovered 𝑘-NN distances decreases during Dijkstra traversal. Overall, the effect of augmenting SBE-Q with MBV is more pronounced in 𝑘 = 50 or 𝑘 = 100, as the larger 𝑑𝑘 leads to a larger expansion radius, resulting in more nodes to explore and more pruning opportunities. MBV is consequently our best-performing method: on SIFT1M it reduces NDC to as low as 2.51% of base nodes at the finest index configuration for small 𝑘, and to around 5.6% on the higher-dimensionality and harder GIST1M dataset. Second, a cross-configuration trend mirrors the stretch estimation results: finer graphs (larger 𝑀 or 𝑒 𝑓𝑐 ) yield smaller 𝑡 ∗ , which in turn shrinks the expansion radius 𝑡 ∗ × 𝑑ˆ𝑘 and lowers NDC for all five variants. Both trends above are consistent across different 𝑘.

Recall Target Compliance of Conformal Parameters

We next evaluate how the conformal parameters affect the final recall–runtime trade-off of CTR via the CRC/LTT. Rather than reporting average recall, we utilize per-query result-set compliance from Section 6.1 and report the compliance rate over a set of queries, which is the fraction of queries for which 𝑅𝑒𝑐𝑎𝑙𝑙 (𝑞)≥𝜏. Compliance rate is based on the result set after the rectification step, if certification fails. In these experiments, we fix the underlying HNSW parameters to 𝑀=32, 𝑒 𝑓𝑐 =200, and 𝑒 𝑓𝑠 =100. In Figure 6, panels (a)–(c) show CRC and panels (d)–(f) show LTT on the three datasets. We fix the target recall threshold to 𝜏=0.90, and for LTT we set 𝜖=0.5. Each blue point is an operating point obtained by varying 𝛼, and the numeric annotation next to the point is the corresponding 𝛼 value; runtime is reported on the x-axis as a multiple of plain HNSW under the same configuration. In Figure 7, we keep the same HNSW configuration and vary 𝜏, with 𝛼=0.05 and 𝜖=0.5; panels (a)–(c) show plain HNSW, panels (d)–(f) show CRC, and panels (g)–(i) show LTT. Results. In Figure 6, for both CRC and LTT, decreasing 𝛼 makes certification stricter, so fewer HNSW outputs are certified directly and more queries are rectified. This raises the compliance rate but also increases runtime; larger 𝛼 has the opposite effect. Across the 𝜏-sweeps in Figure 7, the compliance rate of plain HNSW (𝑒 𝑓𝑠 =100) drops quickly as 𝜏 increases, whereas both CTR variants remain much flatter because rectification preserves compliance on hard queries at the cost of higher runtime ratio. Specifically, at high 𝜏 values (eg. 𝜏 = 0.9, 0.99), HNSW fails the target recall more often, and the expensive MBV is invoked by the certifier more frequently, resulting in increased CTR runtime. In Section ⁇, we explore repeating certification attempts with an expanded search radius to maintain compliance and mitigate runtime increases. Comparing the two certifiers, LTT achieves higher compliance at comparable runtime ratios. This improvement comes from LTT’s stricter per-query guarantee, which enables a more selective allocation of the heavier MBV computation to queries that are more 11

Compliance rate CRC comp. rate

100% a) 90% 80%

LTT comp. rate

SIFT

100% d) 5e-2 90% 0.7 0.3 80%

72%

72%

3e-2 0.1 5×

5×

10×

10×

1e-3 5e-3

7e-2 15×

20×

1e-12 1e-10

15×

Runtime / HNSW Runtime

20×

100% b) 90% 80%

HNSW baseline GIST

0.3

0.2

53%

1× 30× 100% e) 5e-2 90% 1e-2 80%

53%

1×

20×

DEEP1e-3

0.1 100% c) 3e-2 3e-2 90% 3e-3 7e-2 78% 35×

1e-4

70%

6×

100% f) 1e-6 90% 70%

4×

Runtime / HNSW Runtime

12×

18×

24×

1e-24

1e-48

1e-4

78% 2e-2 25×

5e-4

8×

12×

Runtime / HNSW Runtime

16×

0.94

CRC Comp. rate

1.00

1.00

0.75 0.50

0.32 0.80

0.90

0.95

5×

0.80

0.90

0.95

0.99

0.80

0.85

0.90

0.95

0.85

0.90

0.95

0.99

0.80

0.99

0.00

0.38 0.80

0.85

0.90

0.95

0.95

0.99

0.80

0.85

0.90

30 0.75 0.69 10 0.50 1.3× 0.95 0.99 0.80

0.99

0.99 50 20× 30 10 0.85

0.90

0.95

36× 50 1.00 0.96

10 0.50 0.90

0.03

45× 50 1.00 0.93 30 0.75 0.68 10 0.50 2×

50 1.00 0.98 0.94 24× 30 0.75 15× 0.85

DEEP

0.93

0.50

0.49

10 0.50 0.85

0.94

0.50 1× 0.80

0.99

0.00

1.00

0.98 50 1.00 0.93 27× 30 0.75 15×

0.94

0.80 0.75

0.85

0.50

HNSW comp. rate

GIST

1.00

0.50 0.00

CRC/LTT Comp. rate

Time ratio

Time ratio

SIFT

0.99

0.99 50 19× 30

Time ratio

1.00

LTT Comp. rate

HNSW Comp. rate

Figure 6: 𝛼-sweeps on three datasets. Blue line = compliance rate as 𝛼 is varied; x-axis is in multiples of HNSW runtime.

10 0.85

0.90

0.95

0.99

Figure 7: 𝜏-sweeps on three datasets. Primary scale = compliance rate; secondary scale = time in multiples of HNSW runtime. Notably, the small 𝛼 values that appear in LTT are largely an inherent consequence of the test itself: the null benchmark is the boundary case with 𝑥𝜃 failures among 𝑚𝜃 certified queries under a Binomial(𝑚𝜃 , 𝜖) model, and the corresponding one-sided tail probability can become extremely small as soon as the observed failure count falls below the nominal level 𝜖𝑚𝜃 . Thus, the practically useful range of 𝛼 in LTT is naturally shifted toward smaller values; this is a property of the testing mechanism rather than an unusually aggressive confidence requirement. Figure 8 further illustrates how the LTT threshold 𝜃 varies jointly with 𝛼 and 𝜖. The qualitative trend of 𝜃 varying with 𝛼 and 𝜖 is consistent. In particular, along a fixed-𝜖 slice of the surface, decreasing 𝛼 increases the selected threshold 𝜃 . Since LTT certifies a query only when its score exceeds 𝜃 , a larger threshold makes certification more selective: fewer queries are accepted directly, more queries are sent to rectification, and the final compliance rate increases at the cost of higher latency. Conversely, for the same fixed 𝜖, increasing 𝛼 lowers 𝜃 , which certifies more queries directly and therefore reduces runtime, but also lowers compliance. To visually illustrate this trade-off, the black contour lines in Figure 8 depict constant-𝜖 cross-sections of the threshold surface: 𝜖=0.4 for

Figure 8: LTT threshold surface. Higher 𝜃ˆ increases the fraction of queries sent to exact rectification. Black contours show fixed 𝜖 slices, highlighting how 𝛼 controls the latency– compliance trade-off. likely to have low recall and therefore contribute the most to compliance gains. Take the 𝛼-sweep for GIST in Figure 6 for example, under the 𝛼 = 5 × 10−2 setting, LTT has four fewer false negatives and one fewer false positive than CRC in the runtime-comparable 𝛼 = 0.3 setting. We further verified that the recall shortfall of both CRC and LTT is below the respective expected and probabilistic bounds stated in Theorem 6.3, across all values of 𝜏, 𝛼, 𝜖, and 𝛽 (for stretch estimation as experiment setup) used in these experiments, validating our theorem empirically.

12

LTT Comp. rate CRC Comp. rate

M = 16, efs = 200

M = 16, efs = 300

M = 32, efs = 200

SIFT

1.00

GIST

(a)

(b)

0.99 0.98 1.00

(d)

M = 32, efs = 300 1.00

0.90

0.98

0.80

0.96

(e)

0.96

DEEP (c)

(f) 0.99

0.99 0.88 0.98

0.97

0.80 0

15

30

0

15

Time ratio

30

Time ratio

45

15

30

45

Time ratio

Figure 9: HNSW-parameter ablation on three datasets. X-axis reports runtime as a multiple of HNSW runtime. SIFT1M and DEEP1M, and 𝜖=0.7 for GIST1M. Each such crosssection isolates the one-dimensional family of operating points obtained by varying 𝛼 while holding 𝜖 fixed, thereby making clear how the resulting change in 𝜃 governs the latency–compliance trade-off described above. The figure also suggests a practical tuning strategy: first select 𝜖 so as to avoid the broad plateau region of 𝜃 (the yellow region, where variation in 𝜖 has relatively little effect on the threshold), and then vary 𝛼 to choose the desired operating point along the corresponding constant-𝜖 trade-off curve. We next study how the HNSW operating point affects the latency– compliance trade-off. In Figure 9, blue/green use 𝑀=16 and red/brown use 𝑀=32; blue/red use 𝑒 𝑓𝑠 =200, while green/brown use 𝑒 𝑓𝑠 =300. Panels (a)–(c) show CRC and panels (d)–(f) show LTT for SIFT, GIST, and DEEP. Across the rerun, increasing 𝑒 𝑓𝑠 generally shifts curves upward and left, and increasing 𝑀 produces a similar improvement in these operating ranges. The reason is that both changes improve the quality of the initial HNSW search: larger 𝑒 𝑓𝑠 explores more candidates at query time, while larger 𝑀 gives the graph more connectivity. As a result, more queries already meet the compliance target before rectification, so the expensive recovery step is triggered less often. This lowers the runtime ratio needed to reach a given compliance rate. Overall, Figure 9 suggests that 𝑒 𝑓𝑠 is the cleaner query-time knob, while 𝑀 provides a stronger index-level operating point when its memory and build-time cost is acceptable. The CTR framework naturally extends to filtered search on top of algorithms such as ACORN [40]. We present our results in Section 8.2.

7.6

Repeated Certification

Motivation. Section 7.5 shows that at high 𝜏, HNSW fails the target recall on a growing share of queries, so the certifier escalates to the expensive exact MBV rectification more often and CTR’s runtime ratio increases accordingly. As an alternative to invoking MBV, we explore repeating the certification attempt with an expanded search radius: instead of exactly rectifying a query that fails certification, we simply re-run HNSW at a larger 𝑒 𝑓𝑠 and recertify, hoping that the extra candidates already push the result into compliance without ever paying for exact recovery. This policy trades the correctness guarantee of exact rectification for the hope of a cheaper, purely HNSW-side fix, and we study whether 13

this mitigates the runtime increase from Section 7.5 while keeping recall competitive. Experimental setup. The repeated-certification policy proceeds as follows. Starting from 𝑒 𝑓𝑠 =100, we run HNSW and score the result with a CRC certifier calibrated at that 𝑒 𝑓𝑠 and the target 𝜏; if the certifier accepts, we stop and return the current result. Otherwise we increase 𝑒 𝑓𝑠 by 100, re-run HNSW at the new, larger radius, and re-certify with a separately calibrated certifier for that 𝑒 𝑓𝑠 ; this repeats until certification succeeds or 𝑒 𝑓𝑠 reaches 𝑒 𝑓𝑚𝑎𝑥 =1000, at which point the last HNSW result is returned regardless of certifier outcome. No MBV or other exact-recovery step is ever invoked. Crucially, this requires calibrating one CRC certifier per 𝑒 𝑓𝑠 value—ten certifiers, one each for 𝑒 𝑓𝑠 ∈ {100, 200, . . . , 1000}, for every (dataset, 𝜏) pair—rather than a single certifier as in Section 7.5. All certifiers are calibrated offline, on the held-out calibration split (with size being 80% of the #queries column in Table 1) before any online evaluation begins; at query time the appropriate pre-fit certifier is simply looked up for the current 𝑒 𝑓𝑠 and applied, so this calibration cost is a one-time offline expense and is not counted in the online per-query runtime ratios reported below. We fix 𝑘=100 and 𝛼=0.01, sweep 𝜏 ∈ {0.80, 0.85, 0.90, 0.95, 0.99}, and evaluate on 200 held-out queries per dataset on SIFT1M, GIST1M, and DEEP1M. Results. Figure 10 shows that, on SIFT1M and DEEP1M, repeated certification substantially mitigates the runtime increase seen with the rectifier in Section 7.5 while keeping recall on a similar level: on SIFT1M the runtime ratio only grows from 1.5× to 11× across the 𝜏-sweep (versus 1×–24× for the LTT rectifier) while compliance stays at 0.93–0.96 (versus 0.94–0.97 for the rectifier); on DEEP1M the runtime ratio grows from 1.0× to 8× (versus 1.3×–19× for the rectifier) while compliance stays at 0.92–0.95 (versus 0.96–0.99 for the rectifier). On GIST1M, however, the policy performs markedly worse, especially at high 𝜏: compliance falls from 0.80 at 𝜏=0.80 to just 0.34 at 𝜏=0.99, even as the runtime ratio still climbs to 51×. The reason is that GIST1M’s hard queries are hard precisely because plain HNSW cannot reach them: the top row of Figure 10 shows the HNSW baseline compliance rate on GIST1M collapsing to 0.02 at 𝜏=0.99, meaning almost no query is compliant at 𝑒 𝑓𝑠 =100. Repeated certification responds to this by escalating 𝑒 𝑓𝑠 into the thousands on these queries, but pushing 𝑒 𝑓𝑠 arbitrarily high does not

0.89

0.96

0.93

0.80

0.85

0.90

0.95

0.99

0.88

0.50

60

0.23

0.02

0.00

0.00

51× 60

1.00

40 0.75 0.80 0.25

0.80

60

1.00 0.95 40 0.75

11× 20 0.50 6×

1.5×

DEEP

0.28

0.14

0.75 0.25

1.00

0.50

0.00

0.50

HNSW comp. rate

GIST

1.00

0.50

1.00

Comp. rate

20 0.50

0.34 0.85

0.90

0.95

0.92

0.99

40

Time ratio

HNSW Comp. rate Iterative Comp. rate

1.00

Time ratio

SIFT

8× 20

1.0× 0.25 0.80

0.85

0.90

0.95

0.99

Figure 10: Repeated-certification policy on three datasets. Top row: plain HNSW compliance rate as 𝜏 varies (identical to the top row of Figure 7). Bottom row: compliance rate (left axis) and runtime, in multiples of the 𝑒 𝑓𝑠 =100 HNSW baseline (right axis), of the repeated-certification policy. guarantee that HNSW’s beam search actually surfaces the true nearest neighbors it is missing; many attempts are spent re-searching without ever satisfying the certifier, so both runtime and the miss rate grow together. The rectifier, by contrast, still reaches 70% compliance on GIST1M at 𝜏=0.99 (versus 0.34 for repeated certification) because MBV guarantees exact recovery of the true 𝑘-nearest neighbors whenever it is invoked (Lemma 6.1), rather than merely hoping a larger beam finds them. Overall, these results indicate that repeated certification is an attractive lower-cost alternative when the underlying HNSW index has enough residual capacity to reach the target recall through search-radius expansion alone (SIFT1M, DEEP1M), but exact rectification remains preferable whenever queries are difficult and the compliance target is stringent, since only rectification offers a correctness guarantee independent of how well HNSW itself performs.

T2I-10M (t=4.133) 10 50 100 0.55 1.16 1.55 5.55 11.64 15.51

T2I-100M (t=4.124) 10 50 100 2.33 4.63 6.11 2.33 4.63 6.11

Table 3: MBV NDC for 𝑘 ∈ {10, 50, 100}.

more densely in the ambient space: the 𝑘-th true neighbor of a typical query lies closer, so 𝑑𝑘 decreases. Since the SBE-Q search radius equals 𝑡 · 𝑑𝑘 , a smaller 𝑑𝑘 directly shrinks the expansion ball, and that ball covers a smaller fraction of the 𝑁 base nodes. Table 3 reflects this exactly: the expansion fraction drops by roughly 2.5× across all 𝑘 values when moving from 10M to 100M (eg. 𝑘=10: 5.55% → 2.33%). Recall is consistently 1 in all settings.

A natural concern is whether dataset size adversely affects the runtime overhead of CTR: larger datasets contain more candidate nodes within any search radius, which could inflate the cost of SBEQ. We test this using the Yandex Text-to-Image dataset7 at two scales—T2I-10M and T2I-100M—with index configuration 𝑀=32, 𝑒 𝑓𝑐 =200 on normalized vectors, with an Intel Xeon Ice Lake 3.5 GHz processor with 64GB memory. For each scale, stretch estimation is carried out following the same procedure as Section 7.2 (𝛽=0.995, 𝑚=400). As we use a subset of T2I-1B, query ground truths were re-computed by brute-force. We first run MBV without the certifier on 200 text queries sampled from T2I. Table 3 reports average NDC in absolute value and as a fraction of dataset size. Stretch estimation on 10M and 100M scales yields 𝑡=4.133 and 𝑡=4.124 respectively, confirming that the graph stretch does not grow appreciably with dataset size. At the same time, a 10× larger corpus means base vectors are distributed

1.00 0.75

0.85

Time ratio 50

0.94

21×

30

10 0.50 4× 0.70 0.75 0.80 0.85 0.90 0.95

LTT comp. rate 1.00 0.75

0.82

T2I-100M

50

0.91

12×

0.50

Time ratio

T2I-10M

Scalability Experiments

LTT comp. rate

7.7

𝑘 million NDC % of 𝑁

30

19× 10

0.70 0.75 0.80 0.85 0.90 0.95

Figure 11: 𝜏 ablation on T2I-10M and T2I-100M. We next conduct a full 𝜏-sweep (𝑒 𝑓𝑠 =100, 𝑘=100) to evaluate end-to-end overhead. Absolute latency increases with dataset size, as expected: HNSW grows by 8–9.4× and CTR by 7.5–8.4×. The key question is whether CTR adds disproportionate overhead beyond this baseline HNSW growth. Figure 11 shows that the normalized runtime ratio remains comparable across scales: the peak ratio even decreases from 21.3× at 10M to 19.2× at 100M. Thus, because the expansion radius remains bounded, CTR preserves the compliance–runtime trade-off across scales and introduces no additional scaling bottleneck beyond HNSW itself.

7 https://research.yandex.com/blog/benchmarks-for-billion-scale-similarity-search

14

7.8

ConANN vs. CTR

We now perform an end-to-end system comparison against ConANN [25], a recent ANN system that calibrates a conformal earlytermination rule on an IVF index to also control approximation error and meet recall target. Both systems are evaluated on three datasets (SIFT1M, DEEP1M,and T2I-10M with normalized vectors), sweeping the recall target 𝜏 ∈ {0.80, 0.85, 0.90, 0.95, 0.99} (points connected in order of increasing 𝜏 values on graph) with 𝑘=100; we report the per-query compliance rate Pr[Recall(𝑞) ≥ 𝜏] against end-to-end throughput. Index configurations. ConANN indexes each dataset with IVFFlat using 1024 Voronoi cells and exact 𝐿2 scoring within probed cells, 𝛼 calculated as 1−𝜏. CTR runs on HNSW with 𝑀=32, 𝑒 𝑓𝑐 =200, and query-time 𝑒 𝑓𝑠 =100; we certify each result with LTT (Section 6) and rectify queries that fail certification with MBV. Results. Figure 12 reports the compliance–throughput trade-off. Across all three datasets CTR attains higher compliance than ConANN at every comparable target; the systems differ chiefly in where they sit on the throughput axis. On SIFT1M, CTR is throughputcompetitive: at modest targets (𝜏 ≤ 0.90) it is as fast or faster than ConANN—at 𝜏=0.85 LTT sustains 1.7k QPS at 91% compliance versus ConANN’s 1.5k QPS at 67%—and only at stringent targets does ConANN regain a throughput edge (e.g. 789 versus 97 QPS at 𝜏=0.95), where its compliance nonetheless plateaus at 0.72–0.82 against CTR’s 0.94–0.99. The gap in compliance rate is a direct consequence of the certify-then-rectify mechanism: LTT supplies a per-query confidence guarantee, and this guarantee, combined with CTR’s ability to recover the exact nearest neighbors for queries flagged as low-quality, is what gives CTR its edge, lifting the recall of such queries toward 1 and raising the overall compliance rate. ConANN, by contrast, can only reorder and truncate its IVF probe and cannot exactly recover the neighbors it misses, so a fixed fraction of queries necessarily remains below 𝜏 at every point. ConANN

Throughput (QPS)

SIFT1M

CTR

DEEP1M

T2I-10M 10

10

3

10 10

2

1

2

75

90

60

80

Compliance Rate (%)

100

70

80

90

Figure 12: ConANN vs. CTR (upper-right is better).

7.9

DARTH vs. CRC/LTT

Recently, DARTH [12] was proposed solely as a predictor of recall. We therefore compare it directly against CRC and LTT in a certifier-only setting, i.e., without true neighbor rectification (as DARTH does not have this capability). Table 4 reports the F1 scores with respect to the binary event 𝑅𝑒𝑐𝑎𝑙𝑙 (𝑞) ≥ 𝜏. For fairness, we use DARTH only as a recall predictor and let HNSW run to the same 15

stopping point in all methods, rather than using DARTH’s earlytermination mechanism. The experiment is conducted on SIFT1M with 𝑀=32, 𝑒 𝑓𝑐 =200, 𝑒 𝑓𝑠 =100, 𝑘=100 and 1000 random queries, utilizing the implementation from the DARTH authors. Across all three target levels, CRC/LTT attain higher F1, with the gap becoming larger at stricter targets. Similar results were obtained across all data sets and are omitted for brevity. DARTH is a best-effort predictor and does not formally control the fraction of queries whose recall falls below the target. In contrast, CRC and LTT are calibrated for fixed deployment settings (dataset, index configuration, workload, and target recall 𝜏) and explicitly control compliance-related errors under that setting. Consequently, for deciding whether an HNSW result should be accepted as meeting a prescribed recall target, CRC/LTT yield a more reliable acceptance rule. 𝜏 0.85 0.90 0.95

DARTH Default Tuned 0.968 0.971 0.913 0.913 0.709 0.709

CTR CRC LTT 0.983 0.983 0.965 0.966 0.865 0.874

Table 4: Certifier comparison on SIFT1M: F1 Scores

7.10

Extension to Disk-based Search

In real production settings, loading the full vector index into memory is often infeasible at billion-scale. Vector search methods that account for disk I/O are therefore necessary. In this section we show that CTR extends to such settings using DiskANN [27], which achieves state-of-the-art disk-based ANN performance by storing a Vamana graph index on disk and exploiting beam-search with asynchronous I/O to amortise latency across concurrent node fetches. Experimental Setup. We consider three settings. (1) In-memory: the Vamana graph variant of DiskANN, where the full graph with full-precision vectors is loaded into memory prior to ANN search. We use an Intel Ice Lake node with 64GB DDR4 unified memory. (2) Limited memory: memory is insufficient to hold the entire database. (3) Heavier disk-IO We additionally increase result size 𝑘 based on the limited memory setting to assess the impact on diskIO brought by an increased MBV expansion radius, which scales with 𝑡 · 𝑑𝑘 . DiskANN search retains only quantized vectors and graph edges in memory while exact vectors reside on disk. To preserve the exactness guarantees of our algorithm, we forgo the quantized vectors and instead keep precomputed graph edge weights in memory, which costs ∼2.6GB on the T2I-10M graph (𝑅=64). The MBV algorithm is otherwise unchanged: it performs Dijkstra expansion using solely these in-memory graph edges; the only difference is that exact distance computations (Algorithm 2, line 25) issue disk reads on cache misses. In this setting, we use an Intel Ice Lake node with 8GB DDR4 memory attached to a 75GB local NVMe drive. Experiments use the T2I-10M dataset; when fully loaded, it requires ∼8GB for base vectors and ∼2.6GB for the graph (𝑅=64), totalling ∼10.6GB—exceeding the 8GB constraint but well within the 64GB limit of Setting 1. For all settings we run a 𝜏-sweep following Section 7.5, using LTT for all conformal predictors. Settings (1) and (2) results in the left and right panels of Figure 13 respectively; setting (3) results in Figure 14.

Parameters. We evaluate setting 1, 2 with 𝑘 = 10 and setting 3 8 FILTERED STRETCH-BOUNDED with 𝑘 = 20. We use 𝛼 = 0.1, 𝜀 = 0.5, and 𝜏 ∈ {0.75, 0.80, 0.85, 0.90, 0.95}. EXPANSION FROM QUERY (F-SBE-Q) The DiskANN index is built with maximum degree 𝑅 = 64 and In this Section, we show the CTR methodology can be directly exconstruction list size 𝐿build = 100; search uses list size 𝐿 = 100 tended to handle filtered ANN search (FANNS), and provide experand disk beam width 𝐵 = 2. MBV is initialised from a single seed imental results of our implementation. In FANNS, the goal is to rewith 10,000 hot-cached nodes in Vamana mode. Disk reads are istrieve the approximate 𝑘-nearest neighbors that satisfy a specific sued via io_uring in basic single-issuer mode with direct I/O and predicate condition 𝑃. Standard heuristic traversals often fail in a submit-batch size of 8, using a single thread. The MBV graph these scenarios when filters disconnect the “small world” topology. stretch parameter 𝑡 = 3.71 is estimated following Section 7.2. However, by leveraging the global connectivity of the underlying graph structure—regardless of the predicate status of intermediate nodes—we can guarantee exact recovery of true nearest neighbors using the bounds derived from the approximate search results. Remark (CTR Modifications for FANNS). The CTR pipeline requires only minimal modification to support FANNS. Deriving F-SBE-Q from SBE-Q entails a single algorithmic change: lines 25– 30 of Algorithm 3 are augmented to check the predicate prior to computing the distance. The lower-bound and elliptical pruning Figure 13: 𝑘=10: in-memory Vamana vs. DiskANN. techniques carry over unchanged, since the distance metric is independent of predicate membership—any candidate node that cannot be closer to 𝑞 than the 𝑘-th approximate neighbor, by the trianResults. As shown in Figure 13, the in-memory Vamana setting gle inequality, may be pruned regardless of whether it satisfies 𝑃. (left panel) confirms that CTR generalises beyond HNSW: it exThe conformal predictor features defined in Section 6 are likewise tends directly to the Vamana graph and achieves compliance–runtime applied to FANNS without modification. trade-offs comparable to those observed on HNSW in Figure 7 of Section 7.5. In the limited-memory setting with 𝑘=10 (right panel 8.0.1 Problem Formulation. Let 𝑃 : X → {0, 1} be a boolean predof Figure 13), the additional disk I/O incurred by MBV expansion re∗ (𝑞) such icate function. We seek the set of 𝑘 nearest neighbors N𝑘,𝑃 mains controlled, adding 8–10× DiskANN time to the runtime ratio ∗ ∗ that for all 𝑥 ∈ N𝑘,𝑃 (𝑞), 𝑃 (𝑥) = 1. Let 𝑑𝑘,𝑃 denote the distance to at each 𝜏 level. Notably, compliance rates in the limited-memory the true 𝑘-th nearest neighbor in the satisfying set: setting are consistently lower than in the in-memory setting. This gap arises because native DiskANN beam search relies on quantized vectors as distance proxies, yielding a weaker ANN baseline than exact Vamana search; as a result, the conformal certifier operates on lower-quality candidates, reducing the fraction of queries that pass certification.

∗ 𝑑𝑘,𝑃 =

max

∗ (𝑞) 𝑥 ∈ N𝑘,𝑃

dist(𝑞, 𝑥)

(19)

Let H𝑓 𝑜𝑢𝑛𝑑 be the set of candidates returned by the initial HNSW search (or any heuristic phase). We identify the subset of these candidates that satisfy the predicate 𝑃. If at least 𝑘 such candidates exist, let 𝑑ˆ𝑘,𝑃 denote the distance to the 𝑘-th closest satisfying candidate found so far. Similar to the unfiltered case, the distance to the 𝑘-th candidate found by any approximate method is an upper bound on the true 𝑘-th distance: ∗ 𝑑𝑘,𝑃 ≤ 𝑑ˆ𝑘,𝑃

(20)

8.0.2 Theoretical Guarantees. We extend Theorem 4.2 to the filtered case using the observable bound 𝑑ˆ𝑘,𝑃 . The critical insight is that while the targets must satisfy 𝑃, the path taken in the graph 𝐺 ′ to reach them need not. Thus, we rely on the spanner property of the full augmented graph 𝐺 ′ .

Figure 14: 𝜏-sweep, 𝑘=20: disk-based DiskANN (8GB + NVMe). For setting (3), Figure 14 shows the effect of increasing 𝑘 from 10 to 20. This enlarges the MBV search radius (𝑡 ·𝑑𝑘 grows as 𝑑𝑘 increases with 𝑘), expanding the explored graph fraction by approximately 70% for queries that fail certification and thereby increasing disk I/O. This is directly reflected in the runtime ratio: at 𝜏=0.9, the ratio rises from approximately 30× to 50× the DiskANN baseline. Overall, MBV transfers the recall–runtime trade-off observed from HNSW to disk-based vector search without any algorithmic modification.

TheoRem 8.1 (FilteRed SBE-Q). Let 𝑞 be a query point virtually inserted into the graph 𝐺 such that the augmented graph 𝐺 ′ is a 𝑡 ′ spanner. Let 𝑑ˆ𝑘,𝑃 be the distance to the 𝑘-th approximate neighbor satisfying predicate 𝑃 (as returned by HNSW or updated dynamically). Then, every true filtered top-𝑘 point lies inside the graph ball of radius 𝑡 ′ · 𝑑ˆ𝑘,𝑃 centered at 𝑞. ∗ (𝑞): Formally, for every 𝑥 ∗ ∈ N𝑘,𝑃 𝑑𝐺 ′ (𝑞, 𝑥 ∗ ) ≤ 𝑡 ′ · 𝑑ˆ𝑘,𝑃 16

(21)

8.1

Algorithm 3 Filtered Stretch-Bounded Expansion from Query (FSBE-Q) Require: Query 𝑞 , Predicate 𝑃 , Graph 𝐺 ′ , Stretch 𝑡 ′ , Initial Candidates H𝑓 𝑜𝑢𝑛𝑑 ∗ (𝑞) Ensure: Exact filtered set N𝑘,𝑃 1: Initialize: 2: 𝑄 𝑣𝑖𝑠𝑖𝑡 ← Min-Priority Queue ordered by graph distance 𝑑𝐺 ′ 3: 𝑅𝑡𝑜𝑝𝐾 ← Max-Priority Queue of size 𝑘 (stores pairs (dist(𝑞, 𝑢 ), 𝑢 ) where 𝑃 (𝑢 ) = 1) 4: 𝑉 𝑖𝑠𝑖𝑡𝑒𝑑 ← {𝑞 } 5: {Seed with initial heuristic results that satisfy P to establish 𝑑ˆ𝑘,𝑃 } 6: for 𝑢 ∈ H𝑓 𝑜𝑢𝑛𝑑 do 7: if 𝑃 (𝑢 ) is True then 8: 𝑅𝑡𝑜𝑝𝐾 .push(dist(𝑞, 𝑢 ), 𝑢 ) 9: end if 10: end for 11: 𝑄 𝑣𝑖𝑠𝑖𝑡 .push(0, 𝑞 ) 12: while 𝑄 𝑣𝑖𝑠𝑖𝑡 is not empty do 13: (𝑑𝑔𝑟𝑎𝑝ℎ , 𝑢 ) ← 𝑄 𝑣𝑖𝑠𝑖𝑡 .pop() 14: {Dynamic Termination Condition using 𝑑ˆ𝑘,𝑃 } 15: 𝑑ˆ𝑘,𝑃 ← 𝑅𝑡𝑜𝑝𝐾 .max_dist() {Returns ∞ if < 𝑘 found} 16: if 𝑑𝑔𝑟𝑎𝑝ℎ > 𝑡 ′ · 𝑑ˆ𝑘,𝑃 then 17: break {Guaranteed to have found all true filtered neighbors} 18: end if 19: {Expand Neighbors} 20: for each neighbor 𝑣 of 𝑢 in 𝐺 ′ do 21: if 𝑣 ∉ 𝑉 𝑖𝑠𝑖𝑡𝑒𝑑 then 22: 𝑉 𝑖𝑠𝑖𝑡𝑒𝑑 .add(𝑣 ) 23: 𝑛𝑒𝑤 _𝑑𝑔𝑟𝑎𝑝ℎ ← 𝑑𝑔𝑟𝑎𝑝ℎ + dist(𝑢, 𝑣) 24: {Check Metric Distance & Predicate} 25: if 𝑃 (𝑣) is True then 26: 𝑑𝑚𝑒𝑡𝑟𝑖𝑐 ← dist(𝑞, 𝑣) 27: if 𝑑𝑚𝑒𝑡𝑟𝑖𝑐 < 𝑅𝑡𝑜𝑝𝐾 .max_dist() then 28: 𝑅𝑡𝑜𝑝𝐾 .push(𝑑𝑚𝑒𝑡𝑟𝑖𝑐 , 𝑣 ) {Updates 𝑑ˆ𝑘,𝑃 (tightens bound)} 29: end if 30: end if 31: 𝑄 𝑣𝑖𝑠𝑖𝑡 .push(𝑛𝑒𝑤 _𝑑𝑔𝑟𝑎𝑝ℎ , 𝑣 ) 32: end if 33: end for 34: end while 35: return 𝑅𝑡𝑜𝑝𝐾

To demonstrate SBE extends naturally to filtered ANN search (FANNS), we augment ACORN [40], a representative filtered-search method, with F-SBE-Q. Our experiments in this section are comparable to the setup in Section 7.4. Note that ACORN is a variant of HNSW that adds extra edges to the underlying graph, controlled by a parameter 𝛾. In essence, the higher the selectivity of the query predicates (fewer matching vectors), the higher the value of 𝛾 required, which produces denser graphs that keep the search traversal highly navigable. Moreover, ACORN explores 2-hop neighbors at each step to maximize the probability of retrieving nearest neighbors that satisfy the query predicates. In order to understand the impact of predicate selectivity on our framework, we introduce a selectivity parameter 𝜎, which we define as the percentage of database vectors satisfying a query predicate. For instance, the value 𝜎 = 1 would imply that only 1% of vectors pass the filter (highly restrictive), while 𝜎 = 25 admits 25% (moderately selective). In our experiments, we set the value of 𝛾 as the inverse of the selectivity parameter 𝜎 per the recommendation given in the ACORN paper [40]. We evaluate the performance of F-SBE-NN, F-SBE-Q, and MBV on ACORN across three datasets (SIFT1M, DEEP1M, and GIST1M respectively). Observe that the results in Table 5 depict trends similar to those observed for HNSW (Table 2). As shown in Table 5, decreasing 𝜎 (i.e., higher selectivity) generally increases the number of nodes explored by F-SBE-Q, subject to the estimated stretch and density of the underlying graph. When either the density or stretch of the graph is high, the number of nodes explored by SBE-Q also increases, while guaranteeing perfect recall across all cases (subject to the estimation of the stretch 𝑡, which varies with the parameter 𝛾). We typically observe this increase because more selective predicates both raise the density of the underlying graph (through parameter 𝛾) and yield a larger 𝑑𝑘 ; that is, the top-𝑘 filtered results lie farther from 𝑞, which in turn enlarges the search radius. Our results further demonstrate the benefits of F-SBE-Q and MBV over F-SBE-NN, consistent with what we observed for HNSW. It is known [40] that ACORN exhibits low recall for highly selective predicates, and our framework resolves this.

PRoof. Let 𝑥 ∗ be any arbitrary point in the true filtered set

∗ (𝑞). By definition of the true set and the upper bound propN𝑘,𝑃

erty of the approximate results:

∗ dist(𝑞, 𝑥 ∗ ) ≤ 𝑑𝑘,𝑃 ≤ 𝑑ˆ𝑘,𝑃

(22)

Since the augmented graph 𝐺 ′ is a 𝑡 ′ -spanner over the full set of vertices 𝑉 ∪ {𝑞}, there exists a path between 𝑞 and 𝑥 ∗ in 𝐺 ′ such that: 𝑑𝐺 ′ (𝑞, 𝑥 ∗ ) ≤ 𝑡 ′ · dist(𝑞, 𝑥 ∗ )

(23)

8.2

Substituting the metric bound: 𝑑𝐺 ′ (𝑞, 𝑥 ∗ ) ≤ 𝑡 ′ · 𝑑ˆ𝑘,𝑃

Experiments On Stretch-Bounded Expansion For Filtered Search

Conformal Parameter Evaluation on Filtered Search

This subsection presents extended results demonstrating that our end-to-end Certify-then-Rectify (CTR) framework generalizes to the FANNS setting. Here the experiment is comparable to Section 7.5 in its motivation. In the unfiltered case, the previous sections establish that wrapping vanilla HNSW with our statistical certifiers (CRC and LTT) and exact recovery procedures (SBE-Q with MBV) yields a principled recall–runtime trade-off: queries whose HNSW results are statistically certified as meeting the target recall 𝜏 are returned directly, while those that fail certification are escalated to exact recovery. Here, we investigate whether the same framework transfers to filtered search, where the goal is to retrieve the 𝑘 nearest neighbors that additionally satisfy a boolean predicate 𝑃. Our results span a total of six datasets. We use the SIFT1M, GIST1M

(24)

Thus, the search radius defined by the approximate results is sufficient to encompass all true answers. □ 8.0.3 Algorithm. The expansion algorithm (Algorithm 3) proceeds by traversing the graph 𝐺 ′ starting from 𝑞. Crucially, to preserve the spanner property 𝑡 ′ , the traversal visits nodes regardless of whether they satisfy 𝑃. The predicate 𝑃 (𝑣) is checked only during the candidate collection phase to update the dynamic bound 𝑑ˆ𝑘,𝑃 . While Algorithm 3 presents the logic for predicate handling, in practice, this traversal is further optimized using the Metric Bound Verification techniques we introduce in Section 5. 17

Dataset

SIFT1M

DEEP1M

GIST1M

Metric 𝜎 𝑡 (SSE 𝑐 ) F-SBE-NN (% of 1M) F-SBE-Q (% of 1M) MBV (% of 1M) 𝑡 (SSE 𝑐 ) F-SBE-NN (% of 1M) F-SBE-Q (% of 1M) MBV (% of 1M) 𝑡 (SSE 𝑐 ) F-SBE-NN (% of 1M) F-SBE-Q (% of 1M) MBV (% of 1M)

𝑀=16, 𝑀𝛽 =32, 𝑒 𝑓𝑐 =200, 𝑘=10 1 5 10 25 4.699 4.203 4.175 6.089 92.06 82.14 82.39 85.15 28.72 15.31 12.64 25.50 28.48 15.10 12.44 25.01 4.369 3.946 3.914 6.628 98.81 93.94 92.92 91.29 21.94 7.99 6.55 45.76 21.91 7.97 6.54 45.60 5.207 5.199 5.180 6.984 90.70 89.98 90.12 61.63 53.08 49.25 47.25 45.22 52.99 49.12 47.08 45.21

𝑀=16, 𝑀𝛽 =32, 𝑒 𝑓𝑐 =200, 𝑘=100 1 5 10 25 4.699 4.203 4.175 6.089 97.09 89.60 89.24 87.23 44.35 32.86 29.25 41.96 44.15 32.60 28.91 40.35 4.369 3.946 3.914 6.628 99.77 96.92 96.27 91.47 60.88 30.21 24.61 72.09 60.85 30.17 24.58 72.00 5.207 5.199 5.180 6.984 91.77 90.74 90.81 61.83 69.05 64.61 62.64 51.62 69.00 64.55 62.58 51.61

𝑀=32, 𝑀𝛽 =64, 𝑒 𝑓𝑐 =200, 𝑘=10 1 5 10 25 4.052 3.775 3.750 3.641 85.71 74.25 74.74 68.64 28.16 14.94 12.28 8.30 27.97 14.75 12.11 8.18 3.571 3.560 3.520 3.608 97.93 95.40 94.14 93.25 13.97 8.48 6.17 6.04 13.96 8.47 6.16 6.03 3.887 3.387 3.387 3.909 93.66 87.88 87.51 91.47 37.33 15.38 13.74 27.85 36.99 15.13 13.49 27.40

𝑀=32, 𝑀𝛽 =64, 𝑒 𝑓𝑐 =200, 𝑘=100 1 5 10 25 4.052 3.775 3.750 3.641 92.58 82.66 82.69 76.89 45.38 32.68 28.97 22.67 45.24 32.48 28.76 22.46 3.571 3.560 3.520 3.608 99.47 97.73 96.89 96.21 51.15 34.38 26.51 24.04 51.12 34.35 26.48 24.00 3.887 3.387 3.387 3.909 94.87 89.50 89.05 92.56 60.83 35.63 32.61 48.30 60.68 35.33 32.30 47.97

Table 5: Expanded-node coverage (% of 1M) on ACORN: F-SBE-NN vs F-SBE-Q vs MBV

Table 6: Dataset Summary (Real Filtered Datasets) Dataset Paper LAION1M arXiv

𝑁 2.03M 1.00M 2.74M

𝑑 200 512 4096

𝛾 12 30 12

𝜎 ∼8% ∼10% ∼0 to 28%

Predicate 1-of-12 label CLIP top-3/30 EMIS category

and DEEP1M datasets where we introduce synthetic predicates - in essence, given a value 𝜎, we randomly select 𝜎 percent of vectors to satisfy a boolean predicate. We further evaluate our framework on three datasets with real predicates. These include the PAPER [48] and LAION1M [43] datasets from the ACORN paper. Moreover, to demonstrate scalability, we evaluate our framework on the ARXIV dataset8 , which contains high-dimensional vectors. 8.2.1 Experimental Setup. For our experiments on synthetic data, we set (𝛾 = 1/selectivity), so that selectivity levels (𝜎 = 5%, 10%, 25%) correspond to (𝛾 = 20, 10, 4), respectively. For purpose of meaningful evaluation, we used 4-fold cross-validation with 1K queries per fold, where each fold contains 25% of the queries. Across all our datasets, we used the same index and search settings: 𝑒 𝑓𝑐 =64, 𝑒 𝑓𝑠 =128, and 𝑘=50, with 𝑀=16 and the compression factor 𝑀𝛽 =32. The LTT parameter 𝜖 was dataset-dependent (explored in further detail in Section 7.5) in the 𝛼-sweep experiments: we used 𝜖=0.8 for GIST and 𝜖=0.5 for the rest of the five datasets. The certifier 𝛼 grids and 𝜏 values were also chosen per preset; for instance, the 𝜏-sweeps used 0.65–0.75 for the LAION1M dataset and 0.7–0.8 for the ARXIV dataset. We set different target recall (𝜏) windows for different datasets in order to demonstrate the transition point where the pipeline shifts from certifying nearly all queries to rectifying nearly all of them. Throughout our experiments, the values of our configuration parameters remain fixed. Moreover, for brevity, the stochastic stretch factor used for rectification is held constant at 𝑡 = 4.5 across all runs, as our primary objective is not to fine-tune the expansion radius but rather to (a) validate that the CTR certification-rectification pipeline transfers to filtered search with minimal modification, and (b) study how the predicate selectivity 𝜎 modulates the recall-runtime trade-off. We evaluate three selectivity levels: 𝜎 ∈ {5, 10, 25}. As 𝜎 decreases (higher selectivity), ACORN must traverse more of the graph to accumulate 𝑘 qualifying candidates, increasing the chance of a suboptimal heuristic result and triggering rectification. Therefore, we set 𝜏 = 0.95 for the PapeR dataset, 0.90 for Sift1M and Deep1M, 8 https://huggingface.co/datasets/SPCL/arxiv-for-fanns-large

18

0.80 for Laion1M, and 0.75 for Gist1M and aRXiv, in accordance with the base recall provided by ACORN. For each configuration, we measure two key quantities: (i) the compliance rate, defined as the fraction of test queries for which the final output (after any rectification) satisfies 𝑅𝑒𝑐𝑎𝑙𝑙 (𝑞) ≥ 𝜏, and (ii) the runtime ratio, defined as the end-to-end wall-clock time of the CTR pipeline normalized by the standalone ACORN runtime. Normalizing runtime by the ACORN baseline allows direct comparison of the overhead introduced by certification and rectification, independent of the absolute cost of the filtered traversal itself. Effect of Varying 𝛼 (Alpha-Sweeps). The parameter 𝛼 governs the stringency of the statistical certifier. In CRC, 𝛼 controls the risk level of the conformal procedure: a smaller 𝛼 requires stronger statistical evidence that the HNSW output meets the recall target before it is accepted without rectification. In LTT, 𝛼 serves as the significance level of the hypothesis test that the certifier’s error rate does not exceed a prescribed tolerance 𝜖. Figures 15, 16 and 17 present the alpha-sweep results for selectivity levels 𝜎 = 5, 10, and 25, respectively for datasets with synthetic predicates. Figure 18 presents alpha-sweep results for datasets with real query predicates. Each panel plots the compliance rate (y1 axis) and the normalized runtime (y2 axis) as a function of 𝛼, for both CRC and LTT. The baseline ACORN operating point is highlighted for reference. For CRC, the results reveal a smooth and monotonic trade-off. At small values of 𝛼, the certifier is highly conservative: it demands strong statistical evidence before accepting ACORN results, so a large fraction of queries fail certification and are escalated to the exact F-SBE-Q + MBV recovery pipeline. This drives the compliance rate close to 1.0, where nearly every query ultimately meets the recall target, albeit at the cost of elevated runtime, since the Dijkstra-based expansion in F-SBE-Q is substantially more expensive than the heuristic traversal alone. As 𝛼 increases, the certifier becomes more permissive: it accepts a larger share of ACORN outputs at face value, bypassing rectification. This reduces runtime because fewer queries invoke the expensive recovery procedure, but the compliance rate decreases accordingly, since some of the directly accepted results do not actually meet the target recall. For LTT, our results exhibit the same qualitative monotonic tradeoff but with a notable quantitative difference: the practically useful range of 𝛼 in LTT is shifted toward substantially smaller values (often by many orders of magnitude). This is an inherent property of the Learn-then-Test mechanism rather than an indication of an

LTT comp. rate CRC comp. rate

Compliance rate

SIFT

100% 0.95 80% 0.995 60% 0.97 40% 30% 300× 100% 80% 60% 40% 30%

1e-4

5e-2 370×

0.8

100% 80% 60% 40% 18%

0.6

0.9

500× 1e-15

1e-10

1e-5

1e-2

0.5

0.3

1e-6

530×

Runtime / ACORN Runtime

0.4

0.6

0.8

0.5

0.7 610×

0.2 1100×

100% 80% 1e-10 1e-3 1e-6 60% 5e-2 1e-15 40% 1e-8 18% 1e-5 510×1e-2

1e-20

1e-12

ACORN baseline

GIST

1e-30

1100×

Runtime / ACORN Runtime

100% 80% 60% 40% 29%

DEEP 0.7

0.9

0.995

100% 80% 60% 40% 29%

0.1 0.5

0.8

0.97 780×

1e-8

1e-3

5e-2 710×

910× 1e-20

1e-5

1e-2

0.3

Runtime / ACORN Runtime

910×

Figure 15: 𝛼-sweep on SIFT1M, GIST1M, DEEP1M (𝜎=5%)

LTT comp. rate CRC comp. rate

Compliance rate 100% 80% 60%0.95

42%

2×

100% 80% 0.5 60%

42%

ACORN baseline

SIFT

5× 5e-2

0.2

200×

1e-2

0.2 GIST 100% 0.6 0.6 80% 0.8 0.4 0.8 60% 0.7 0.7 40% 21% 30×0.9 200× 500× 500× 1e-15 100% 1e-8 1e-3 1e-18 80% 1e-20 1e-8 1e-12 1e-12 1e-5 60% 1e-3 1e-5 40% 1e-10 1e-15 21% 1e-6 300× 410× 1e-4

Runtime / ACORN Runtime

100% 0.995 80% 0.5 60% 40% 39% 1000× 480×

0.9

0.5

0.7

770× 1e-20

1e-10

1e-5

1e-15

1e-7

1e-3

0.2

0.6

0.8

0.95

100% 0.3 1e-2 80% 1e-30 60% 0.1 40% 39% 990× 470×

Runtime / ACORN Runtime

DEEP

740×

Runtime / ACORN Runtime

Figure 16: 𝛼-sweep on SIFT1M, GIST1M, DEEP1M (𝜎=10%)

LTT comp. rate CRC comp. rate

Compliance rate

SIFT

100% 80% 60%0.97 46% 40%

2× 5× 100% 1e-3 5e-2 80% 0.5 60% 1e-2 0.2 46% 40%

ACORN baseline

GIST

0.5

100% 100% 0.4 0.6 0.7 80% 80% 0.995 0.6 60% 0.8 0.5 0.7 60% 40% 0.8 23% 42% 20× 100× 300× 500× 980× 300× 1e-12 1e-18 100% 1e-30 100% 1e-6 0.3 80% 1e-18 80% 1e-12 1e-8 1e-10 1e-15 60% 1e-6 60% 1e-5 1e-25 40% 1e-15 23% 42% 1e-10 200× 300× 370× 1e-7 800× 330×

Runtime / ACORN Runtime

Runtime / ACORN Runtime

DEEP

0.95

1e-7

1e-3 1e-2

0.3

0.7

0.9

0.97

0.6

0.8

500× 1e-12 1e-10

1e-5

1e-18 530×

Runtime / ACORN Runtime

Figure 17: 𝛼-sweep on SIFT1M, GIST1M, DEEP1M (𝜎=25%)

LTT comp. rate CRC comp. rate

Compliance rate

Paper

100% 0.5 80% 640×

1200×

100% 80% 0.5

56% 40%

0.1

0.3

56% 40%

0.2

0.1 0.2

200×

100% 80% 0.5 60% 51% 40%

1e-10 100% 1e-6 80% 0.5 1e-3 60% 1e-8 1e-4 51% 1e-2 40% 300× 500× 560×

Runtime / ACORN Runtime

ACORN baseline

LAION1M

1000× 1e-3

0.1 0.2

1e-2

0.2

100% 80% 0.5 0.1 0.3 60% 40% 36% 2000× 3500× 2e-2 100% 0.7 1e-8 80% 1e-3 0.1 1e-10 60% 1e-6 40% 36% 1700× 6800×

Runtime / ACORN Runtime

Figure 18: 𝛼-sweep on PAPER, LAION1M, and arXiv Datasets

19

Arxiv

0.3 0.4 9600×

1e-5

Runtime / ACORN Runtime

1e-8 9600×

0.41 0.15 0.85

1.00 0.80 0.75 0.50 303× 0.25 0.00 0.85

0.88

0.88

0.88

0.90

0.90

0.90

0.93

0.93

0.93

0.95 0.99

1.00 0.75 0.50 0.25 0.00

1.00 500× 0.75 529× 300× 0.50 200× 0.25 0.00 0.95 0.96 1.00 500× 0.75 0.50 501× 300× 0.25 200× 0.00 0.95

ACORN comp. rate

GIST 0.29 0.65

0.17 0.68

0.70

0.68

0.70

0.68

0.70

0.47

0.75

0.72

0.80 1000× 1.00 0.71 994× 0.75 100× 0.50 401× 10× 0.25 0.00 0.75 0.82

0.72

1000× 1.00 0.76 300× 0.75 593× 0.49 473× 100× 0.50 30× 0.25 10× 0.00 0.75 0.82

0.30 14× 0.65

Deep1M

0.72

0.29 5× 0.65

1.00 0.75 0.50 0.25 0.00

0.82

0.29 0.84

0.86

0.88

0.90 0.98 1000×

885×

500× 300×

0.84

0.86

0.88

0.90 0.90

769× 0.84

0.86

0.88

0.90

Time ratio

ACORN Comp. rate CRC Comp. rate

1.00 0.75 0.65 0.50 197× 0.25 0.00 0.85

LTT Comp. rate

1.00 0.75 0.50 0.25 0.00

CRC/LTT Comp. rate

1000× 500×

Time ratio

Time ratio

SIFT

300×

Figure 19: 𝜏-sweep on SIFT1M, GIST1M, DEEP1M (𝜎=5%)

CRC Comp. rate

1.00 0.75 0.50 0.25 0.00

LTT Comp. rate

1.00 0.75 0.67 0.50 114× 0.25 0.00 0.85

0.53 0.24 0.85

0.88

0.90

0.93

0.53 1× 0.85

0.88

0.88

0.90

0.90

0.93

0.93

0.95 0.98

1.00 0.75 0.50 0.25 0.00

1.00 496× 100× 0.75 0.50 10× 0.25 1× 0.00 0.95 0.92 1.00 500× 0.75 300× 448× 200× 0.50 100× 0.25 0.00 0.95

ACORN comp. rate

GIST 0.34 0.65

0.21 0.68

0.70

0.72

0.34 2× 0.65

0.68

0.70

0.72

0.34 7× 0.65

0.68

0.70

0.72

0.75

1.00 0.75 0.50 0.25 0.00

Deep1M 0.57

0.82

0.82 1000× 1.00 990× 0.75 0.57 100× 0.50 10× 0.25 2× 0.00 0.75 0.82 1.00 300× 0.75 0.67 407× 0.40 100× 0.50 165× 30× 10× 0.25 0.00 0.75 0.82

0.39

0.84

0.86

0.88

0.90 0.96

740×

1000× 100× 10×

0.84

0.86

0.88

Time ratio

ACORN Comp. rate

1.00 0.75 0.50 0.25 0.00

CRC/LTT Comp. rate

0.90

0.84 500× 549× 300× 200×

Time ratio

Time ratio

SIFT

0.84

0.86

0.88

0.90

100×

Figure 20: 𝜏-sweep on SIFT1M, GIST1M, DEEP1M (𝜎=10%)

1.00 0.75 0.50 0.25 0.00

0.27 0.85

0.88

0.90

0.93

0.57 1× 0.85

0.88

0.90

0.93

0.63 42× 0.85

0.88

0.90

0.93

0.95 0.98

ACORN comp. rate

GIST 0.27 0.71

1.00 0.80 393× 100× 0.75 781× 0.50 10× 0.25 1× 0.00 0.95 0.71 0.88 1.00 300× 0.75 331× 100× 0.50 0.30 64× 0.25 30× 0.00 0.95 0.71

0.23 0.72

0.72

0.72

0.73

0.73

0.73

0.74

0.74

0.74

0.75

1.00 0.75 0.50 0.25 0.00

1.00 0.81 1000× 0.75 0.50 893× 0.25 500× 0.00 0.75 1.00 300× 0.75 252× 200× 0.34 100× 0.50 0.25 50× 0.00 0.75

Deep1M 0.59

0.82

0.84

0.86

0.88

0.90 0.97

574×

0.59

0.82

0.84

0.86

0.88

0.90

0.79

500× 385× 300× 200×

0.66 88× 0.82

100× 10×

3×

Figure 21: 𝜏-sweep on SIFT1M, GIST1M, DEEP1M (𝜎=25%)

20

0.41

Time ratio

CRC Comp. rate

1.00 0.75 0.50 0.25 0.00

0.57

1.00 0.75 0.50 0.25 0.00

CRC/LTT Comp. rate

Time ratio

ACORN Comp. rate

1.00 0.75 0.50 0.25 0.00

LTT Comp. rate

Time ratio

SIFT

100× 0.84

0.86

0.88

0.90

1.00 0.75 0.50 0.25 0.00

0.21 0.94

0.95

0.96

0.97

0.98

0.67 1× 0.94

0.95

0.96

0.97

0.98

0.68 12× 0.94

0.95

0.96

0.97

0.98

0.99 0.95

1.00 0.75 0.50 0.25 0.00

1000× 1.00 1243× 0.75 100× 0.50 10× 0.25 1× 0.00 0.99 0.95 1.00 1000× 1253× 0.75 100× 0.50 0.25 10× 0.00 0.99

ACORN comp. rate

LAION1M 0.58

0.75

0.41

0.78

0.80

0.82

0.85

1.00 0.82 1000× 2063× 0.75 100× 0.50

0.58

10×

1× 0.75

0.78

0.80

0.80

0.25 0.00

0.49

0.70

0.30 0.72

0.75

0.78

0.80 0.95

9052×

0.49

0.82

1.00 0.72 1000× 0.69 1567× 0.75 100× 0.50 3456× 0.25 10× 0.00 0.85 0.70

0.70

10000× 1000× 100×

19×

0.85

15× 0.78

1×

Arxiv

0.82

0.58

0.75

1.00 0.75 0.50 0.25 0.00

0.72

0.75

0.78

0.80

0.87

10000×

7800× 5000× 3000× 0.72

0.75

0.78

Time ratio

0.67

CRC/LTT Comp. rate

Time ratio

ACORN Comp. rate

1.00 0.75 0.50 0.25 0.00

LTT Comp. rate

1.00 0.75 0.50 0.25 0.00

CRC Comp. rate

Time ratio

Paper

0.80

Figure 22: 𝜏-sweep on PAPER, LAION1M, and arXiv Datasets recall for most queries) and steepens at high 𝜏 values as the fraction of rectified queries grows. Effect of Varying the Selectivity Parameter (𝜎). The alpha-sweep figures report runtime as a ratio relative to ACORN’s own runtime rather than as absolute latency. This normalization removes a large shared runtime component (the filtered traversal itself) and consequently compresses between-selectivity differences. In our experiments, ACORN’s absolute runtime is already fairly similar across selectivity levels (especially on SIFT1M), so the dominant visible variation within each panel comes from the 𝛼-driven certification and rectification behavior rather than from 𝜎 directly. Nevertheless, the effect of selectivity is discernible, particularly at the high-runtime end of the alpha frontier (i.e., at small 𝛼, where rectification is triggered most frequently). At this end, the runtime ratio decreases as selectivity decreases from 𝜎 = 5 to 𝜎 = 25. The mechanism is as follows: when the predicate is less selective (𝜎 = 25), a larger fraction of the database satisfies the filter, so ACORN’s heuristic traversal is more likely to encounter qualifying candidates and return a result that already meets the recall target. Consequently, fewer queries require rectification, and the average per-query overhead shrinks. Conversely, at 𝜎 = 5, the predicate is highly restrictive; ACORN must traverse deeper into the graph to find 𝑘 qualifying neighbors, increasing the chance of a suboptimal result and triggering rectification more often. Thus, selectivity effects manifest primarily as vertical shifts in the runtime axis rather than as changes in the overall shape of the compliance curve. Concluding Remarks. Taken together, these results validate that the Certify-then-Rectify framework transfers naturally to the filtered search setting. Across all datasets and across selectivity levels ranging from highly restrictive (𝜎 = 5) to moderately selective (𝜎 = 25), the CTR pipeline consistently achieves substantially higher compliance with the target recall than standalone ACORN, at a controlled and tunable runtime overhead. The 𝛼 parameter provides a smooth knob for navigating this trade-off: conservative settings (small 𝛼) prioritize correctness, while permissive settings (large 𝛼) prioritize speed. As part of future efforts, we plan to investigate how information about different predicates-including their

unusually stringent confidence requirement. In LTT, the null hypothesis is the boundary case in which exactly 𝑥𝜃 failures occur among 𝑚𝜃 certified queries under a Binomial(𝑚𝜃 , 𝜖) model. The corresponding one-sided tail probability becomes extremely small as soon as the observed failure count drops even slightly below the nominal level 𝜖 ·𝑚𝜃 . As a result, the test rejects the null (and therefore certifies the query) only at very small 𝛼 values, compressing the effective operating range. Despite this shift, the shape of the compliance-versus-runtime frontier mirrors that of CRC: decreasing 𝛼 pushes more queries through rectification, raising both compliance and runtime, while increasing 𝛼 does the reverse. Effect of Varying 𝜏 (Tau-Sweeps). Figures 19, 20 and 21 present our results for tau-sweep experiments on datasets with synthetically generated predicates, while Figure 22 presents those for datasets with real predicates. In our experiments, we fix the certifier parameters and vary the target recall threshold 𝜏. Each panel reports three quantities as a function of 𝜏: the compliance rate of the CTR pipeline, the compliance rate of standalone ACORN without any certification or rectification, and the runtime ratio of the CTR pipeline relative to ACORN. The results reveal a striking complementary pattern. As 𝜏 increases (i.e., stricter recall requirements), ACORN’s native compliance rate declines steeply: at high recall thresholds, fewer and fewer of ACORN’s heuristic results happen to contain a sufficiently large overlap with the true 𝑘-nearest filtered neighbors. In contrast, the CTR pipeline maintains a substantially higher compliance rate across the full range of 𝜏. This is because the certifier detects the queries for which ACORN’s output is deficient and escalates them to exact recovery via SBE-Q with MBV, which is guaranteed to return the true filtered neighbors. The gap between ACORN and CTR curves quantifies the value added by the certify-then-rectify mechanism: it is precisely those queries that would have silently returned low-recall results under ACORN alone that are caught and corrected. The runtime-ratio curve increases with 𝜏, reflecting the fact that higher recall targets cause more queries to fail certification and require rectification. This increase is gradual at lowto-moderate 𝜏 values (where ACORN already achieves reasonable 21

distribution, cardinality, and proximity to the query point-can be exploited to further optimize the framework. In particular, we intend to study whether predicate-specific stretch values can reduce the overhead incurred during rectification for highly restrictive filters, and whether adaptive calibration strategies can improve the certifier’s discrimination when the predicate selectivity varies across queries within a single workload.

9

stretch factor, bounding the exact recovery search radius. Recovery uses Stretch-Bounded Expansion from Query (SBE-Q) and Metric Bound Verification (MBV) to prune distance computations while preserving correctness. The framework supports filtered search without predicate-respecting paths.

REFERENCES

RELATED WORK

A dominant family of graph indexing and ANN search algorithms stems from proximity-construction methods grounded in the geometry of relative neighborhood graphs (RNGs) and approximate Delaunay graphs [42, 47]. Key examples include navigable indexes such as Navigable Small-World graphs (NSW) and their hierarchical HNSW variant [36, 37], which constitute the state-of-the-art. Given its success, many variants of the vanilla HNSW have been proposed in recent literature [33, 40, 41, 58]. Related approaches further include navigating spread-out graphs (NSGs) [22] and the disk-based DiskANN index [27]. Efforts have also been made to accelerate kNN search by compressing the vector space using quantization [29] and inverted file (IVF) indexing [19, 28], and using locality-sensitive hashing [11, 17, 35]. A comprehensive survey on ANN search appears in [39]. For filtered search, the literature can be split into: (i) works on filter-aware index structures [9, 33, 52, 58]; (ii) standard ANN backbones with improved query-time execution [1, 40]; and (iii) multi-index approaches [32]. A survey of filtered search methods is given in [15]. Beyond improving the search algorithm itself, recent work has emphasized that query difficulty and workload composition strongly affect the observed behavior of ANN indexes. Wang et al. [49] introduced Steiner-hardness, a query hardness measure specifically designed for graph-based ANN indexes, while Ceccarello et al. [10] studied how to evaluate and generate query workloads of controlled difficulty for high-dimensional vector similarity search. Recent work further explores learned termination checks, where models map query-time features to per-query budgets [30, 53, 55]. Related declarative target-recall approaches terminate when the system predicts (heuristically) that the target recall has been met (e.g., DARTH [12]). Similar early-exit ideas also appear in non-graph pipelines [8, 13, 25, 38, 56]. We also build on statistical models grounded in extreme value theory, including standard inferential toolkits for Weibull distributions [16, 21] and conformal prediction [3–5, 7]. Lastly, note that our formulations w.r.t. distance-call pruning take inspiration from recent literature on this topic [6, 18, 23, 30, 31, 44, 45, 51, 54].

10

FINAL REMARKS

This paper introduces a framework for generating correctness certificates in ANN search by wrapping HNSW in a ”Certify-thenRectify” pipeline. Using a Conformal Prediction formulation, we efficiently certify whether HNSW’s top-k results miss closer neighbors. If certification fails, we trigger exact recovery to fetch true top-k neighbors. Our key novelty is reinterpreting HNSW’s bottom layer as an empirical graph spanner to estimate a high-confidence 22

[1] Anas Ait Aomar, Karima Echihabi, Marco Arnaboldi, Ioannis Alagiannis, Damien Hilloulin, and Manal Cherkaoui. 2025. RWalks: Random Walks as Attribute Diffusers for Filtered Vector Search. PACMMOD 3, 3 (2025). [2] Yousef Al-Jazzazi, Haya Diwan, Jinrui Gou, Cameron Musco, Christopher Musco, and Torsten Suel. 2025. Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search. arXiv preprint arXiv:2505.15636 (2025). [3] Anastasios N Angelopoulos and Stephen Bates. 2021. A gentle introduction to conformal prediction and distribution-free uncertainty quantification. arXiv preprint arXiv:2107.07511 (2021). [4] Anastasios N. Angelopoulos, Stephen Bates, Emmanuel J. Candès, and Michael I. Jordan. 2024. Conformal Risk Control. J. Amer. Statist. Assoc. 119, 548 (2024), 2386–2408. https://doi.org/10.1080/01621459.2024.2302500 [5] Anastasios N. Angelopoulos, Stephen Bates, Michael I. Jordan, and Jitendra Malik. 2022. Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control. In ICLR. OpenReview. [6] Jees Augustine, Suraj Shetiya, Mohammadreza Esfandiari, Senjuti Basu Roy, and Gautam Das. 2021. A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems. In ACM SIGMOD. 142–154. [7] Stephen Bates, Anastasios Angelopoulos, Lihua Lei, Jitendra Malik, and Michael Jordan. 2021. Distribution-free, Risk-controlling Prediction Sets. J. ACM 68, 6, Article 43 (Sept. 2021), 34 pages. https://doi.org/10.1145/3478535 [8] Francesco Busolin, Claudio Lucchese, Franco Maria Nardini, Salvatore Orlando, Raffaele Perego, and Salvatore Trani. 2024. Early exit strategies for approximate k-NN search in dense retrieval. In CIKM. 3647–3652. [9] Yuzheng Cai, Jiayang Shi, Yizhuo Chen, and Weiguo Zheng. 2024. Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search. PACMMOD 2, 6 (2024). [10] Matteo Ceccarello, Alexandra Levchenko, Ioana Ileana, and Themis Palpanas. 2025. Evaluating and Generating Query Workloads for High Dimensional Vector Similarity Search. In ACM SIGKDD. [11] Moses S. Charikar. 2002. Similarity estimation techniques from rounding algorithms. In STOC. 380–388. [12] Manos Chatzakis, Yannis Papakonstantinou, and Themis Palpanas. 2025. Darth: Declarative recall through early termination for approximate nearest neighbor search. PACMMOD 3, 4 (2025), 1–26. [13] Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021. SPANN: Highly-Efficient Billion-Scale Approximate Nearest Neighborhood Search. In Advances in Neural Information Processing Systems, Vol. 34. [14] Yilun Chen, Zhiding Yu, Yukang Chen, Shiyi Lan, Anima Anandkumar, Jiaya Jia, and Jose M. Alvarez. 2023. FocalFormer3D: Focusing on Hard Instance for 3D Object Detection. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV). [15] Yannis Chronis, Helena Caminal, Yannis Papakonstantinou, Fatma Özcan, and Anastasia Ailamaki. 2025. Filtered Vector Search: State-of-the-Art and Research Opportunities. PVLDB 18, 12 (2025), 5488–5492. [16] Stuart Coles, Joanna Bawa, Lesley Trenner, and Pat Dorazio. 2001. An introduction to statistical modeling of extreme values. Vol. 208. Springer. [17] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. 2004. Locality-sensitive hashing scheme based on p-stable distributions. In SCG. 253– 262. [18] Liwei Deng, Penghao Chen, Ximu Zeng, Tianfu Wang, Yan Zhao, and Kai Zheng. 2024. Efficient Data-Aware Distance Comparison Operations for HighDimensional Approximate Nearest Neighbor Search. PVLDB 18, 3 (2024), 812– 821. [19] Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. 2024. The Faiss library. (2024). arXiv:2401.08281 [cs.LG] [20] Hao Duan, Yitong Song, Bin Yao, and Anqi Liang. 2025. PGTuner: An Efficient Framework for Automatic and Transferable Configuration Tuning of Proximity Graphs. arXiv:2508.17886 [cs.DB] https://arxiv.org/abs/2508.17886 [21] R. A. Fisher and L. H. C. Tippett. 1928. Limiting forms of the frequency distribution of the largest or smallest member of a sample. Mathematical Proceedings of the Cambridge Philosophical Society 24, 2 (1928), 180–190. [22] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast approximate nearest neighbor search with the navigating spreading-out graph. PVLDB 12, 5 (2019), 461–474.

[23] Jianyang Gao and Cheng Long. 2023. High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations. PACMMOD 1, 2 (2023). [24] E. J. Gumbel. 1958. Statistics of Extremes. Columbia University Press, New York, Chichester, West Sussex. https://doi.org/10.7312/gumb92958 [25] Sonia Horchidan, Fabian Zeiher, Henrik Boström, and Paris Carbone. 2026. ConANN: Conformal Approximate Nearest Neighbor Search. PVLDB 19, 1 (2026), 29–42. [26] Physical Intelligence, Ali Amin, Raichelle Aniceto, Ashwin Balakrishna, Kevin Black, Ken Conley, Grace Connors, James Darpinian, Karan Dhabalia, Jared DiCarlo, Danny Driess, Michael Equi, Adnan Esmail, Yunhao Fang, Chelsea Finn, Catherine Glossop, Thomas Godden, Ivan Goryachev, Lachy Groom, Hunter Hancock, Karol Hausman, Gashon Hussein, Brian Ichter, Szymon Jakubczak, Rowan Jen, Tim Jones, Ben Katz, Liyiming Ke, Chandra Kuchi, Marinda Lamb, Devin LeBlanc, Sergey Levine, Adrian Li-Bell, Yao Lu, Vishnu Mano, Mohith Mothukuri, Suraj Nair, Karl Pertsch, Allen Z. Ren, Charvi Sharma, Lucy Xiaoyang Shi, Laura Smith, Jost Tobias Springenberg, Kyle Stachowicz, Will Stoeckle, Alex Swerdlow, James Tanner, Marcel Torne, Quan Vuong, Anna Walling, Haohuan Wang, Blake Williams, Sukwon Yoo, Lili Yu, Ury Zhilin∗ : a VLA That Learns From Experience. sky, and Zhiyuan Zhou. 2025. 𝜋 0.6 arXiv:2511.14759 [cs.LG] https://arxiv.org/abs/2511.14759 [27] Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In NeurIPS, Vol. 32. [28] Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data 7, 3 (2019), 535–547. [29] Herve Jégou, Matthijs Douze, and Cordelia Schmid. 2011. Product Quantization for Nearest Neighbor Search. IEEE Transactions on Pattern Analysis and Machine Intelligence 33, 1 (2011), 117–128. [30] Conglong Li, Minjia Zhang, David G Andersen, and Yuxiong He. 2020. Improving approximate nearest neighbor search through learned adaptive early termination. In ACM SIGMOD. 2539–2554. [31] Zhenxin Li, Shuibing He, Jiahao Guo, Xuechen Zhang, Xian-He Sun, and Gang Chen. 2025. CRouting: Reducing Expensive Distance Calls in Graph-Based Approximate Nearest Neighbor Search. arXiv preprint arXiv:2509.00365 (2025). [32] Zhaoheng Li, Silu Huang, Wei Ding, Yongjoo Park, and Jianjun Chen. 2025. SIEVE: Effective Filtered Vector Search with Collection of Indexes. PVLDB 18, 11 (2025), 4723–4736. [33] Anqi Liang, Pengcheng Zhang, Bin Yao, Zhongpu Chen, Yitong Song, and Guangxu Cheng. 2024. UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search. PVLDB 18, 4 (2024), 1118–1130. [34] Zhenxi Lin, Ziheng Zhang, Xian Wu, and Yefeng Zheng. 2023. Improving Biomedical Entity Linking with Retrieval-Enhanced Learning. arXiv preprint arXiv:2312.09806 (2023). https://doi.org/10.48550/arXiv.2312.09806 [35] Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. 2007. Multiprobe LSH: efficient indexing for high-dimensional similarity search. In VLDB. 950–961. [36] Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. 2014. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems 45 (2014), 61–68. [37] Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions On Pattern Analysis And Machine Intelligence 42, 4 (2018), 824–836. [38] Jason Mohoney, Devesh Sarda, Mengze Tang, Shihabur Rahman Chowdhury, Anil Pacaci, Ihab F. Ilyas, Theodoros Rekatsinas, and Shivaram Venkataraman. 2025. Quake: Adaptive Indexing for Vector Search. In Proceedings of the 19th USENIX Symposium on Operating Systems Design and Implementation (OSDI 25). USENIX Association. [39] James Jie Pan, Jianguo Wang, and Guoliang Li. 2024. Survey of vector database management systems. VLDB 33, 5 (2024), 1591–1615. [40] Liana Patel, Peter Kraft, Carlos Guestrin, and Matei Zaharia. 2024. ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data. PACMMOD 2, 3 (2024), 1–27. [41] Zhencan Peng, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. 2025. Dynamic Range-Filtering Approximate Nearest Neighbor Search. PVLDB 18, 10 (2025). [42] Franco P Preparata and Michael I Shamos. 2012. Computational Geometry: An Introduction. Springer Science & Business Media. [43] Christoph Schuhmann, Romain Beaumont, Richard Vencu, Cade Gordon, Ross Wightman, Mehdi Cherti, Theo Coombes, Aarush Katta, Clayton Mullis, Mitchell Wortsman, Patrick Schramowski, Srivatsa Kundurthy, Katherine Crowson, Ludwig Schmidt, Robert Kaczmarczyk, and Jenia Jitsev. 2022. LAION-5B: An open large-scale dataset for training next generation image-text models. In NeurIPS, Vol. 35. 25278–25294. [44] Yitong Song, Pengcheng Zhang, Chao Gao, Bin Yao, Kai Wang, Zongyuan Wu, and Lin Qu. 2025. TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning. PACMMOD 3, 6

(2025), 1–26. [45] Ziwen Song, Bin Wang, and Xiaochun Yang. 2025. Accelerating HighDimensional ANN Search via Skipping Redundant Distance Computations. PACMMOD 3, 6 (2025), 1–29. [46] Tommaso Teofili and Jimmy Lin. 2025. Patience In Proximity: A Simple Early Termination Strategy for HNSW Graph Traversal in Approximate k-Nearest Neighbor Search. In ECIR. 401–407. [47] Godfried T. Toussaint. 1980. The relative neighbourhood graph of a finite planar set. Pattern Recognition 12, 4 (1980), 261–268. [48] Mengzhao Wang, Lingwei Lv, Xiaoliang Xu, Yuxiang Wang, Qiang Yue, and Jiongkang Ni. 2022. Navigable Proximity Graph-Driven Native Hybrid Queries with Structured and Unstructured Constraints. arXiv:2203.13601 [cs.DB] https: //arxiv.org/abs/2203.13601 [49] Zeyu Wang, Qitong Wang, Xiaoxing Cheng, Peng Wang, Themis Palpanas, and Wei Wang. 2024. Steiner-Hardness: A Query Hardness Measure for GraphBased ANN Indexes. PVLDB 17, 13 (2024), 4668–4682. [50] Maciej Wiatrak, Eirini Arvaniti, Angus Brayne, Jonas Vetterle, and Aaron Sim. 2023. Proxy-based Zero-Shot Entity Linking by Effective Candidate Retrieval. arXiv preprint arXiv:2301.13318 (2023). https://doi.org/10.48550/arXiv.2301. 13318 [51] Qian Xu, Juan Yang, Feng Zhang, Junda Pan, Kang Chen, Youren Shen, Amelie Chi Zhou, and Xiaoyong Du. 2025. Tribase: A Vector Data Query Engine for Reliable and Lossless Pruning Compression using Triangle Inequalities. PACMMOD 3, 1 (2025), 1–28. [52] Yuexuan Xu, Jianyang Gao, Yutong Gou, Cheng Long, and Christian S. Jensen. 2024. iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search. PACMMOD 2, 6 (2024). [53] Kaixiang Yang, Hongya Wang, Bo Xu, Wei Wang, Yingyuan Xiao, Ming Du, and Junfeng Zhou. 2021. Tao: A learning framework for adaptive nearest neighbor search using static features only. arXiv preprint arXiv:2110.00696 (2021). [54] Mingyu Yang, Wentao Li, Jiabao Jin, Xiaoyao Zhong, Xiangyu Wang, Zhitao Shen, Wei Jia, and Wei Wang. 2025. Effective and general distance computation for approximate nearest neighbor search. In IEEE ICDE. 1098–1110. [55] Chao Zhang and Renée J. Miller. 2025. Distribution-Aware Exploration for Adaptive HNSW Search. arXiv:2512.06636 [cs.DB] https://arxiv.org/abs/2512.06636 [56] Zili Zhang, Chao Jin, Linpeng Tang, Xuanzhe Liu, and Xin Jin. 2023. Fast, Approximate Vector Queries on Very Large Unstructured Datasets. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23). USENIX Association, 995–1011. [57] Xiaoyao Zhong, Haotian Li, Jiabao Jin, Mingyu Yang, Deming Chu, Xiangyu Wang, Zhitao Shen, Wei Jia, George Gu, Yi Xie, Xuemin Lin, Heng Tao Shen, Jingkuan Song, and Peng Cheng. 2025. VSAG: An Optimized Search Framework for Graph-Based Approximate Nearest Neighbor Search. PVLDB 18, 12 (2025), 5017–5030. [58] Chaoji Zuo, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. 2024. SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search. PACMMOD 2, 1 (2024).

23

Related documents

• TrajectoryDB: A New Database for Agent Trajectories#673620
• Preserving contextual information in cultural heritage metadata through multidimensional knowledge graphs#673621
• X-DigCheck: Co-Evolving Application Profiles and Knowledge Graphs, Demonstrated on the RTI Documentation of Rupe Magna#673622
• Open Tabular Insight Extraction: Where Do We Stand, and Where Should We Go?#673623
• Protocol effects on feature-based hardware-Trojan detection across Trust-Hub families#673624