betaFeedback

WorksComputer Science

Recast: Refinement-Centered Approximate Nearest Neighbor Search Optimized for Storage

Abstract

Large-scale ANNS systems often exploit storage in addition to DRAM for supporting vector search. The central question is how to divide the work between memory and storage for achieving both high query throughput-recall and good index maintenance performance. Existing storage-optimized ANNS paradigms fall short of providing a complete answer: disk-resident graph indexes have difficulty in supporting efficient vector deletions, while posting-list systems often incur more disk I/Os for queries. In this paper, we introduce a refinement-centered paradigm for storage-optimized ANNS systems. We propose Recast as a concrete design of this paradigm. Recast stores raw vectors on disk and keeps an IVF index with our RecastQ quantization encoding in memory. For an ANNS query, Recast selects nprobe inverted lists and performs SIMD-based FastScan on their RecastQ codes to identify refinement candidates in memory. It then retrieves candidate vectors from disk, computes exact distances, and refines the top-K result. To reduce disk I/Os, RecastQ computes uncertainty intervals containing true distances with high probability. Our QUIC policy selects a minimal refinement set based on these intervals, minimizing candidate-retrieval I/Os. Both the on-disk raw vectors and the in-memory IVF structure support insertions and deletions. Experiments on real-world data sets show that Recast processes batched insertions and deletions 3.10-37.27x faster than SPFresh and OdinANN, while its QPS at 0.99 recall changes by at most 6.9% after updating 50% of the corpus. For static queries at 0.99 recall, Recast achieves 1.56-2.01x the QPS of the strongest baseline with the matched memory budget on each data set, while requiring 1.22-6.75x less external storage than the evaluated systems. At matched in-memory space, RecastQ also provides a better Recall-refinement frontier than RaBitQ.

Introduction

Approximate nearest-neighbor search (ANNS) for embedding vectors is widely used in recommendation [39], image retrieval [32], retrieval-augmented generation [30], and sparse-attention optimized KV-cache in large language model serving [12, 31]. For sufficiently large vector collections, it is often uneconomical to keep all the vectors and the search structures in DRAM. Therefore, large-scale ANNS systems often exploit storage in addition to DRAM for supporting vector search. For storage-optimized ANNS systems, the central question is how to divide the work between memory and storage for achieving high query throughput without sacrificing the recall and index maintenance performance.

Existing storage-optimized ANNS systems take two influential paradigms. Disk-resident graph indexes, such as DiskANN [42], Starling [44], and OdinANN [23], store the vectors and a proximity graph on disk and exploit memory for keeping part of the search structures and caching recent entries to accelerate graph traversal. Posting list based systems, such as SPANN [11] and SPFresh [47], store each vector into (possibly multiple) posting lists on disk and use an in-memory index to select and retrieve postings for subsequent distance evaluation. While both paradigms have shown good storage ANNS performance, neither provides a complete answer to the above question: graph-based solutions have difficulty in supporting efficient vector deletions, and posting list based systems often incur larger amount of disk I/Os for queries.

In this paper, we would like to rethink the design of storage-optimized ANNS systems. One natural way is to revisit a widely used main-memory ANNS paradigm: IVF PQ with FastScan and Refinement. IVF narrows the search to a subset of inverted lists, vector quantization keeps per-vector state compact, and PQ FastScan accelerates distance computation on compressed codes with SIMD operations [3, 28, 41]. Given the short candidate list computed by IVF PQ with FastScan, Refinement then accesses a small number of candidate vectors and computes exact distances to obtain highly accurate top-KK results. Together, these features form an effective scan-and-refine paradigm that achieves high query throughput-recall performance. At the same time, the IVF structure is known to be amenable to index maintenance.

Inspired by the main-memory IVF PQ with FastScan and Refinement, we propose Recast (Refinement-Centered Approximate nearest neighbor search optimized for Storage). Recast stores the exact vectors on disk, and keeps the IVF structure and quantization codes in memory. Note that quantization can effectively reduce the memory footprint to a small fraction (e.g., 1/4–1/10) of the original data set size. For an ANNS query, Recast selects nprobe inverted lists whose centroids are closest to the query vector, and scans the quantization codes in the nprobe lists to compute the list of refinement candidates in memory. Then, Recast performs disk I/Os to retrieve the candidate vectors, compute exact distances, and refine the top-KK result. Recast brings the following benefits:

  • Benefit 1: Efficient index maintenance. Both the on-disk and in-memory structures of Recast can efficiently support index maintenance. For on-disk structures, Recast only performs vector-record and metadata updates for vector insertions and deletions, without maintaining graph connectivity or replicated postings. In comparison, the existing paradigms have to either modify the graph structure or update potentially multiple postings for each updated vector. For in-memory structures, insertions and deletions can also be easily handled in the IVF structure of Recast.

  • Benefit 2: Independent I/O operations. Unlike the dependent I/Os due to graph traversals in graph-based solutions, Recast issues independent disk I/Os for the candidate vectors. Therefore, it is straight-forward to optimize disk accesses with asynchronous I/Os, and deduplicate and merge the I/O requests for vectors on the same disk page.

However, Recast faces and addresses two important challenges:

  • Challenge 1: Minimizing the number of disk I/Os. Compared to the refinement in the main-memory IVF index, the refinement in Recast performs disk I/Os, incurring drastically higher cost. Consequently, it is important to minimize the number of candidates to refine.

The conventional fixed-RR policy selects the top-RR candidates which are closest to the query vector. However, a fixed RR can hardly capture the difference across queries: a large RR incurs wasteful disk I/Os on easy queries, whereas a small RR downgrades the recall on difficult queries. Figure 1 shows that the per-query optimal Rq∗R_q^* for obtaining all top-10 results can be orders of magnitude different across queries on SIFT100M and DEEP100M data sets with PQ and OPQ encodings.

Distribution of per-query optimal R_q^* for obtaining all top-10 results under the fixed-R refinement policy

Figure 1. Distribution of per-query optimal Rq∗R_q^* for obtaining all top-10 results under the fixed-RR refinement policy.

To address this issue, we propose RecastQ encoding and Quic (Query-aware Uncertainty-guided Candidate selection). RecastQ enables Recast to associate the estimated distance did_i for every vector ii with an uncertainty interval [Li,Ui][L_i,U_i] so that di∈[Li,Ui]d_i \in[L_i,U_i] with high probability. In this way, Quic can select a minimal set of candidates that contain the top-KK neighbors for a query with high confidence. Moreover, RecastQ performs bit-gain-aware grouping, which assigns higher encoding bit budget to vector dimensions with higher variance for improving the encoding quality and reducing the uncertainty interval size.

  • Challenge 2: Reducing in-memory computation cost. After optimizing the disk I/O accesses, we find that the cost of in-memory IVF computation sometimes surpasses the I/O cost. The in-memory search consists of (1) selecting nprobe IVF lists, which computes the distances of all list centroids, and (2) scanning the RecastQ codes in the chosen lists. For (1), we encode the list centroids in PQ and employ FastScan to accelerate the distance computation for centroids. For (2), we implement FastScan on the RecastQ codes. We design the layout of RecastQ to be compatible with that of PQ4 FastScan, which stores codes in 32-vector packed blocks. Unlike the int8 operations in PQ FastScan, we perform 32-bit floating point SIMD operations to improve the accuracy of the distance computation.

Experiments on real-world data sets show that Recast processes batched insertions and deletions 3.10–37.27× faster than SPFresh and OdinANN, while its QPS at 0.99 recall changes by at most 6.9% after updating 50% of the corpus. For static queries at 0.99 recall, Recast achieves 1.56–2.01× the QPS of the strongest baseline with the matched memory budget on each data set, while requiring 1.22–6.75× less external storage than the evaluated systems. At matched in-memory space, RecastQ also provides a better Recall–refinement frontier than RaBitQ.

The paper makes the following contributions:

  • To our knowledge, we are the first to introduce the refinement-centered paradigm for storage-optimized ANNS systems, which provides a promising answer to the central question for achieving good query throughput, recall, and index maintenance performance. We propose Recast as a concrete design of this paradigm.

  • We propose RecastQ encoding, which supports uncertainty interval computation and fast distance estimation, and Quic policy, which for each query minimizes the set of refinement candidates to reduce the I/O overhead.

  • We build an end-to-end Recast system. Our experiments comparing Recast with state-of-the-art storage-optimized ANNS systems show that Recast achieves 1.56–2.01× the query throughput of the strongest baseline at 0.99 recall, and shows strong performance stability under dynamic workloads.

Storage-Optimized ANNS Paradigms

We compare storage-optimized ANNS paradigms in this section. Table 1 summarizes the comparison. For fair comparison, we assume the same allocated memory budget across different systems, which is used by in-memory structures for both query processing and update support.

ParadigmRepresentative systemsQuery performance (w/ same mem size)Amount of disk data accessedDependent I/OsMaintenance supportStorage footprint
Static disk graphDiskANN [42], Starling [44]HighLowYes-Moderate
Dynamic disk graphOdinANN [23]ModerateHighYesModerateModerate
Static posting listSPANN [11]ModerateHighNo-High
Dynamic posting listSPFresh [47]ModerateHighNoModerateHigh
Refinement-centeredRecastHighLowNoStrongLow

Table 1. Comparing storage-optimized ANNS paradigms.

We consider five aspects of the design in the table, including three aspects on ANNS query processing, one aspect on index maintenance, and one aspect on the space cost. (1) Query performance summarizes the ANNS throughput-query performance. (2) Amount of disk data accessed accounts for not only raw vectors but also auxiliary structures retrieved from disk during query processing. (3) Dependent I/Os indicates whether an I/O read decision can depend on information returned by previous I/Os in the same query, which may have adverse impact on I/O efficiency. (4) Maintenance support qualitatively describes whether and how efficient the systems support vector insertions and deletions. (5) Storage footprint compares the total amount of storage space consumed by vector data and auxiliary structures required by queries and updates.

In the following, Section 2.1 and 2.2 review the existing paradigms, then Section 2.3 introduce the refinement-centered paradigm.

Disk-Resident Graph Indexes

Static disk-resident graphs. DiskANN [42] is the first static disk-resident solution. It stores vertices (i.e., exact vectors along with graph adjacency lists) on disk, while keeping compressed PQ codes and preserving a vertex cache in memory. Starling [44] constructs a sampling-based in-memory navigation graph to get better entry points for the disk graph search, and improves I/O locality by placing vertices and out-neighbors in the same disk blocks as much as possible. MARGO [50] further improves the disk data layout by prioritizing out-edges based on their importance in the graph search. GPS [49] appends out-neighbors’ adjacency lists to each vertex entry on disk so that an I/O obtains more graph structure information. PipeANN [22] gives up the strict compute-I/O order across search steps and issues asynchronous I/Os based on the current candidate pool, regardless of uncompleted I/Os or computation.

Dynamic disk-resident graphs. For updates, FreshDiskANN [40] follows a main+delta design. It constructs one or more TempIndexes for insertions and a DeleteList in memory, in addition to the read-only disk-resident graph. When the memory is full, FreshDiskANN merges the three structures to compute a new disk-resident graph. IP-DiskANN [46] proposes an in-place deletion algorithm, which approximates the in-neighbors of a deleted vertex by vertices visited during the graph search, but has to periodically scan the full index to remove dangling edges. OdinANN [23] performs direct vector insertions to reduce foreground performance variation during updates. For deletions, it buffers the deleted vector IDs in memory and merges the deletes to the disk graph periodically.

Representative systems and performance aspects. In this paper, we consider DiskANN [42] and Starling [44] as two classical solutions, and OdinANN [23] as the state-of-the-art solution in the paradigm of disk-resident graphs. As shown in Table 1, the graph-based solutions store adjacency lists with vectors on disk, leading to a moderate storage footprint. Moreover, there are dependency among I/O operations during graph search. Furthermore, OdinANN achieves moderate index update performance. However, compared to the static solutions, OdinANN allocates large per-thread I/O buffers for improving I/O efficiency, and keeps significant metadata, such as vector mapping and allocation structures, in memory. Given the same memory budget, OdinANN has to reduce the PQ code length, which leads to less accurate distance estimation, incurring higher amount of disk I/Os and lower query performance.

Posting List Based Systems

Static posting list based systems. SPANN [11] performs hierarchical clustering to generate a large number of posting lists so that each posting fits into a small number of disk blocks (e.g., 10–100KB). Then, it assigns (boundary) vectors to multiple postings for better recall, and constructs an in-memory index on the medoids (i.e., vectors closest to the centroids of postings). A query first searches the in-memory index to obtain candidate postings, then reads the candidate postings to compute the top-KK result.

Dynamic posting list based systems. SPFresh [47] adds incremental in-place update support to SPANN. Vector updates are handled locally in posting lists. If a posting exceeds an upper threshold, SPFresh splits it into two smaller ones. If the size of a posting is smaller than a lower threshold, SPFresh deletes it and reassigns its vectors to nearby postings.

Representative systems and performance aspects. In this paper, we evaluate SPANN [11] and SPFresh [47] as two representative solutions in the paradigm of posting list based systems. As shown in Table 1, they incur high storage cost because vectors can be stored redundantly in multiple postings. Moreover, the I/Os for retrieving postings are independent of each other in a query. Furthermore, since full postings of vectors are retrieved, SPANN and SPFresh read higher amount of disk data than graph based solutions, which can adversely impact the query performance.

This Paper: Refinement-Centered Paradigm

We introduce a refinement-centered paradigm for storage-optimized ANNS systems. As shown in Table 1, it achieves a low storage footprint for storing vectors without per-vector adjacency lists or redundant assignment. Moreover, it keeps an IVF structure on compressed vector encodings in memory. Both the in-memory structure and the on-disk vectors are update friendly. Furthermore, a query searches the in-memory IVF index to obtain a list of refinement candidates, then issues selective, independent I/Os for retrieving the candidate vectors for refinement. Finally, as will be described in the Recast design, the RecastQ encoding and the QUIC policy minimize the number of candidate vectors and the amount of disk I/Os, thereby improving the query performance.

Recast Overview

We propose Recast (Refinement-Centered Approximate nearest neighbor search optimized for Storage) as a concrete design of the refinement-centered paradigm. In the following, § 3.1 overviews the Recast architecture. Then, § 3.2 and § 3.3 describe its ANNS query and update support, respectively.

Recast Architecture

Figure 2 depicts the Recast architecture. We describe the in-memory and on-disk structures, then analyze the space cost.

Recast architecture and query data flow

Figure 2. Recast architecture and query data flow.

In-memory structures. Recast constructs an IVF index in memory. It is composed of a list of centroids and the IVF lists. First, list centroids are encoded in PQ codes for saving space and reducing computation cost. The same PQ quantizer is used for build-time list assignment, post-build insertion, and query-time IVF list selection. Let DD be the number of vector dimensions. We set the codes to use DD PQ groups, each taking 4 bits. Suppose each dimension is a 32-bit floating point number. Then, this reduces the centroid size from 4D4D to 0.5D0.5D bytes, an 8× space saving. Moreover, PQ FastScan delivers 4.5× speedup for the IVF list selection.

Second, each IVF list stores RecastQ codes packed in Faiss FastScan blocks. A RecastQ code consists of MM code groups, each taking 4 bits, and three bytes, which encode the norm, the scale, and the error (cf. Section 5.2). Hence, each vector’s RecastQ code takes 0.5M+30.5M + 3 bytes. Note that we do not store any vector IDs or disk block addresses in memory because a vector’s disk location can be computed from its IVF list ID and in-list offset. For each vector, this saves at least 4B of memory space.

On-disk structures. First, Recast creates a list file for each in-memory IVF list. A list file stores the vector records in the same order as the associated IVF list. A vector record consists of a 32-bit vector ID and the exact vector. Suppose the disk page size is BB and the vector record size is SS. Each page contains nB=⌊BS⌋n_B = \left\lfloor\frac{B}{S} \right\rfloor records. Hence, for the jj-th RecastQ code in IVF list ii, the associated vector record is the (j mod nB)(j \bmod n_B) records in page ⌊jnB⌋\left\lfloor\frac{j}{n_B} \right\rfloor in list file ii.

Second, Recast also maintains an ID-to-disk-location map. It is not accessed in ANNS queries, but used only for deletions.

Finally, to support quick system restart, it is optional to store a backup copy of the in-memory structures on disk. (This is not depicted in Figure 2.) Note that if the backup copy does not exist, one can always rebuild the in-memory IVF index from the list files.

Space cost analysis. For the memory space, suppose there are NN vectors. The IVF lists take N(0.5M+3)N (0.5M + 3) bytes. Since a list ID takes 4B, the IVF list centroids take nlist(0.5D+4)nlist(0.5D + 4) bytes. In total, the in-memory IVF index takes nlist(0.5D+4)+N(0.5M+3)nlist(0.5D + 4) + N (0.5M + 3) bytes. For a given memory budget, MM can be easily derived.

For the disk footprint, the list files take about NnBB\frac{N}{n_B}B bytes, and the ID-to-disk-location map takes 8N8N bytes. In total, the on-disk structures take ⌈N⌊B/S⌋⌉B+8N\left\lceil\frac{N}{\lfloor B/S \rfloor} \right\rceil B + 8N bytes. Since the dimensions of the vector data sets are often on the order of 100–1000, S≫8S \gg8. Therefore, the disk footprint of Recast is often quite close to NSNS, the space required for storing the raw vectors.

Algorithm 1 RECAST ANNS algorithm.

Require: query qq, output size KK, number of lists to probe nprobenprobe, uncertainty interval scale ZZ, I/O queue depth QQ

1: L←SelectIVFLists⁡(q,nprobe)\mathcal{L} \gets\operatorname{SelectIVFLists}(q, nprobe) 2: C,θK←ScanWithQUIC⁡(q,L,K,Z)C, \theta_K \gets\operatorname{ScanWithQUIC}(q, \mathcal{L}, K, Z) 3: Result←AIOReadAndRefine⁡(q,C,K,Q)Result \gets\operatorname{AIOReadAndRefine}(q, C, K, Q) 4: return ResultResult

ANNS Algorithm

Algorithm 1 lists the Recast ANNS algorithm. The query data flow is illustrated in Figure 2. First, given a query, Recast selects nprobenprobe IVF lists by performing PQ FastScan on the packed centroid codes (Line 1, Step (a) and (b)). Second, it scans the packed RecastQ codes in the selected IVF lists to compute the estimated distance and the uncertainty interval for each item in the lists, while the refinement selector applies the QUIC policy (Line 2, Step (c) and (d)). Specifically, the selector computes a top-KK upper bound θK\theta_K, and obtains a minimal set of refinement candidates, whose lower bounds of the uncertainty intervals ≤θK\le\theta_K (cf. Sections 4). Finally, Recast derives the disk locations of the refinement candidates, plans and issues asynchronous I/Os, and computes accurate vector distances for refinement (Line 3, Step (e) and (f)). The vector IDs in the returned vector records are used to produce the top-KK result.

Optimizing I/O Operations for Retrieving Vectors. Given the set C\mathcal{C} of refinement candidates, Recast computes the disk locations of the ∣C∣|\mathcal{C}| vectors (cf. Section 3.1). It then sorts (list file ID, disk page ID) and merges items that are mapped to the same disk page or adjacent disk pages into a single I/O request. Given the queue depth QQ, a query worker submits QQ I/O requests initially. Whenever submitted I/O requests complete, it refills the released slots with remaining requests. In this way, Recast exploits the independent nature of the I/O requests and the parallelism of the underlying storage devices (e.g., SSDs) for improving I/O efficiency.

Cost Analysis. First, SelectIVFLists takes O(nlist⋅D)O(nlist \cdot D) work. Second, ScanWithQUIC scans an average nprobenlistN\frac{nprobe}{nlist}N RecastQ codes, computes the top-KK upper bound θK\theta_K using an O(K)O(K)-sized heap, and checks the uncertainty lower bound of each item against θK\theta_K. Third, AIOReadAndRefine takes O(∣C∣log⁡∣C∣)O(|\mathcal{C}|\log|\mathcal{C}|) work for the sorting and planning, issues up to O(∣C∣)O(|\mathcal{C}|) asynchronous I/O requests, computes ∣C∣|\mathcal{C}| full distances, and uses a heap of size O(K)O(K) to obtain the top-KK result. In summary, for an ANNS query, Recast takes O(nlist⋅D+nprobenlistN(M+log⁡K)+∣C∣(log⁡∣C∣+log⁡K+D))O(nlist \cdot D + \frac{nprobe}{nlist}N(M + \log K) + |\mathcal{C}|(\log|\mathcal{C}| + \log K + D)) computation work, and performs O(∣C∣)O(|\mathcal{C}|) I/O accesses.

Index Maintenance

The index insertion and deletion algorithms are shown in Algorithm 2. Note that the index structures are updated in place, avoiding the cost of background maintenance tasks used in previous solutions [23, 40]. Moreover, for a batch of requests, both insertion and deletion procedures divide the requests based on the relevant lists, and perform the update operations of each list in parallel.

For insertions, Recast reserves the vector IDs for the input vectors (Line 2), assigns the vectors to the IVF lists with the closest centroids (Line 3), and encodes the vectors into RecastQ codes (Line 4). Then, it groups the insert requests by the assigned lists (Line

Algorithm 2 Insertion and deletion algorithms.
1: procedure InsertBatch($X$)
2: $ID_X \leftarrow ReserveVectorIDs(|X|)$
3: $L_X \leftarrow AssignLists(X)$
4: $(Code_X,U_X) \leftarrow EncodeBatch(X)$
5: $(G,ID_G,X_G,Code_G,U_G) \leftarrow GroupInsertsByList(L_X,ID_X,X,Code_X,U_X)$
6: for each touched list $\ell \in G$ in parallel do
7: AppendPackedRecordsInMem($\ell$, $Code_G[\ell]$, $U_G[\ell]$)
8: $A_G[\ell] \leftarrow AppendRecordsOnDisk(\ell,ID_G[\ell],X_G[\ell])$
9: AddInIDtoDiskLocMap($ID_G,A_G$)
10: return $ID_X$
11: procedure DeleteBatch($ID$)
12: $A \leftarrow LookupLocations(ID)$
13: ValidateDeletes($A$)
14: $(G,A_G) \leftarrow GroupDeletesByList(ID,A)$
15: for each touched list $\ell \in G$ in parallel do
16: $P[\ell] \leftarrow PlanSwapWithLast(\ell,G[\ell])$
17: MovePackedRecordsInMem($\ell,P$)
18: MoveRecordsOnDisk($\ell,P$)
19: UpdateMovedLocAndMarkTombstones($P$)

5), and enters a parallel for loop (Line 6–8). Each parallel iteration processes a touched list, appending the inserted RecastQ codes to the in-memory IVF list, and appending the inserted vector records to the list file on disk. Finally, the IDs and the disk locations of the inserted vectors are added into the ID-to-disk-location map.

For deletions, given a set of vector IDs to delete, Recast retrieves their disk locations from the ID-to-disk-location map on disk (Line 12), and ensures that the disk locations are valid (i.e., not tombstones) (Line 13). Then, it groups the resulting locations by the relevant lists (Line 14), and enters a parallel for loop (Line 15–18). Each parallel iteration processes a touched list. For a list containing NlN_l vectors, if there are dld_l deletions, the list size after deletion is Nl′=Nl−dlN_l' = N_l - d_l. PlanSwapWithLast considers the deleted slots in slot [0,Nl′)[0,N_l') as target holes, and regards the entries in [Nl′,Nl)[N_l',N_l) that are not deleted as source entries. It pairs the source entries with the target holes. Subsequently, MovePackedRecordsInMem and MoveRecordsOnDisk overwrite the target holes with source entries, and truncate the list. Note that for the in-memory IVF list, overwriting an entry involves unpacking the packed code block, updating the entry, and re-packing the code block. Finally, Recast updates the ID-to-disk-location map. For a moved vector, the vector ID remains unchanged, while the disk location is updated. For a deleted vector, the disk location is marked as a special tombstone value. Note that the in-memory IVF lists do not contain any invalid tombstones, and thus there is no tombstone test or invalid-record branch in ANNS query processing.

Cost Analysis. For a batch of NinsN_{\mathrm{ins}} inserts, Recast writes O(NinsB)O\left(\frac{N_{\mathrm{ins}}}{B}\right) pages to the list files and O(8NinsB)O\left(\frac{8N_{\mathrm{ins}}}{B}\right) pages to the ID-to-disk-location map. Therefore, the total amount of disk I/Os is O((1B+8B)Nins)O\left(\left(\frac{1}{B}+\frac{8}{B}\right)N_{\mathrm{ins}}\right). Moreover, the computation cost is O(Nins⋅nlist⋅D)O(N_{\mathrm{ins}}\cdot nlist\cdot D) since the most computation intensive step, AssignLists, computes the distances of nlistnlist centroids for each inserted vector.

For a batch of NdelN_{\mathrm{del}} deletes, Recast accesses 2Ndel2N_{\mathrm{del}} pages to the list files and 2Ndel2N_{\mathrm{del}} pages in the ID-to-disk-location map in the worst case, where each deleted vector record resides in its own page, and NdelN_{\mathrm{del}} source entries are moved. Hence, the total I/O cost is O(4Ndel)O(4N_{\mathrm{del}}). Moreover, the computation cost is O(Ndel)O(N_{\mathrm{del}}).

Query-Aware Uncertainty-Guided Candidate Selection

After overviewing Recast architecture and algorithms, we delve into the Quic refinement policy in this section.

Definition 4.1 (Uncertainty interval). Let d=d(q,x)d = d(\mathbf{q},\mathbf{x}) be the true distance between the query q\mathbf{q} and vector x\mathbf{x}, and d^\hat{d} be the estimated distance. Given a constant z>0z > 0, the uncertainty interval of the distance is [L,U][L,U], where L=d^−zτL = \hat{d} - z\tau, U=d^+zτU = \hat{d} + z\tau, and τ\tau is the vector-specific uncertainty scale.

Our RecastQ encoding provides both a deterministic and a probabilistic uncertainty interval (cf. Section 5.1). The deterministic interval is distribution-free, but its bound is quite loose. The probabilistic interval reduces the deterministic bound by a factor of D\sqrt{D}.

Then, Quic selects refinement candidates as follows.

Quic policy. Let SS be the set of vectors in all probed IVF lists. Suppose for xi∈Sx_i \in S, the uncertainty interval is [Li,Ui][L_i,U_i]. Let

θK=K-th-smallest{Ui:xi∈S}.(1)\theta_K = K\text{-th-smallest}\{U_i:x_i \in S\}. \tag*{(1)}

The refinement candidate set is

C(S)={xi∈S:Li≤θK}.(2)C(S) = \{x_i \in S:L_i \leq\theta_K\}. \tag*{(2)}

Quality of Refinement Candidates

Within the set SS of vectors in the probed IVF lists, an ideal policy would keep all the true top-KK neighbors in SS as refinement candidates. (Note that candidate selection policy obviously cannot recover a true neighbor missed by IVF list selection.) In the following, we would like to understand how well Quic preserves true neighbors as refinement candidates.

Theorem 4.2 (Quic quality under deterministic intervals). If di∈[Li,Ui]d_i \in[L_i,U_i] for every xi∈Sx_i \in S, then C(S)C(S) retains all top-KK neighbors in SS.

Proof. For an excluded xix_i, di≥Li>θKd_i \ge L_i > \theta_K. However, there exists at least KK vectors xj1,…,xjKx_{j_1},\ldots,x_{j_K} s.t. djk≤Ujk≤θKd_{j_k} \le U_{j_k} \le\theta_K. Thus, xix_i cannot be a top-KK neighbor. □\square

For the probabilistic uncertainty interval, we introduce the following result with a number of assumptions for simplifying the analysis. (Please see the detailed derivation in Appendix A.) First, conditioned on the true distances, the normalized distance-estimation errors are independent standard Gaussian random variables. Second, the different vectors share a common uncertainty scale τ\tau. Finally, the upper bounds of all intervals are evenly spaced. The space between two subsequent upper bounds is denoted Δ\Delta.

Theorem 4.3 (Quic quality under probabilistic intervals). Under the above assumptions, for z>0z > 0,

E[Ref⁡@K]≥exp⁡(2zΔI(2z)).(3)\mathbb{E}[\operatorname{Ref}@K] \geq\exp\left(\frac{\sqrt{2}z}{\Delta}I(\sqrt{2}z)\right). \tag*{(3)}

where I(a)=∫a∞ln⁡Φ(x) dxI(a) = \int_a^\infty\ln\Phi(x)\,dx, and Φ(x)\Phi(x) is the CDF of the standard Gaussian distribution.

The theorem provides a lower bound for the expected recall in the refinement stage (within the set SS of vectors in the probed IVF lists). For illustration, for SIFT100M, using the empirical mean ratio E[τ]E[Δ]=20.316\frac{\mathbb{E}[\tau]}{\mathbb{E}[\Delta]} = 20.316 as a plug-in approximation to τΔ\frac{\tau}{\Delta}, Eq. (3) gives 0.9803 at z=2z = 2.

While the assumptions are very simplified, this result illustrates the quality of the probabilistic uncertainty interval to some extent.

Theorem 4.4 (Number of refinement candidates). Under the above assumptions, the number of refinement candidates is K+⌊2zτΔ⌋K + \left\lfloor\frac{2z\tau}{\Delta} \right\rfloor.

Proof. A vector xix_i is selected as a candidate iff. Li≤θKL_i \leq\theta_K. Under the above assumptions, Ui=Li+2zτU_i = L_i + 2z\tau. Hence, Ui≤θK+2zτU_i \leq\theta_K + 2z\tau. There are KK vectors with upper bounds up to θK\theta_K, and ⌊2zτΔ⌋\left\lfloor\frac{2z\tau}{\Delta} \right\rfloor selected vectors, whose upper bounds in (θK,θK+2zτ](\theta_K, \theta_K + 2z\tau]. □

We see that the number of refinement candidates increases with zz and τ\tau, and decreases with Δ\Delta. First, larger zz makes the selection more conservative. Second, smaller quantization errors lead to lower τ\tau and fewer candidates to refine. Finally, smaller Δ\Delta means more vectors with similar distances, which makes the query intrinsically harder and requires refining more candidates.

QUIC Computation

Computing θK\theta_K. During the FastScan of packed codes in the probed IVF lists, a size-KK max heap maintains the globally smallest KK upper bounds observed so far. The heap maximum gives the current curθK\mathit{cur}\theta_K, which is monotonically non-increasing after initialization. For each SIMD batch, Recast compares all upper bounds against curθK\mathit{cur}\theta_K to filter out any upper bound that is greater than or equal to curθK\mathit{cur}\theta_K for reducing heap operations. The remaining upper bounds are processed serially: each is rechecked against the latest heap maximum and, if still eligible, inserted with an O(log⁡K)O(\log K) heap update. The same heap is used across all probed IVF lists, ensuring that the bound is computed globally.

Selecting Refinement Candidates. After obtaining global θK\theta_K, Recast compares the lower bounds to select the refinement candidates. To safeguard against unhealthy growth of per-query workspace, the implementation includes a 2,000-entry transient shortlist of candidates for a query. It is almost never activated under the evaluated configurations and has no measurable effect on the reported Recall–QPS frontiers.

RecastQ Encoding

The RecastQ encoding process is as follows:

  1. Let cc be a reference center. (For example, let c=1N∑i=1Nxic = \frac{1}{N}\sum_{i=1}^{N}x_i, for vectors x1,…,xNx_1,\ldots,x_N. cc will not change upon index updates.) Let T\mathbf{T} be an orthogonal transformation.

  2. To encode vector x\mathbf{x}, RecastQ computes xc=x−c\mathbf{x}_c = \mathbf{x} - c, r=∥xc∥r = \lVert\mathbf{x}_c\rVert, and u=xcr\mathbf{u} = \frac{\mathbf{x}_c}{r}, which is the normalized vector.

  3. RecastQ encodes u\mathbf{u} using MM code groups with bit-gain-aware uneven grouping (cf. § 5.3).

  4. Three metadata bytes, i.e., norm, scale, and error, are stored with the main code to facilitate decode processing. Let y′\mathbf{y}' be the decoded vector from the main code. u^=TTy′∥y′∥\hat{\mathbf{u}} = \mathbf{T}^{\mathsf{T}}\frac{\mathbf{y}'}{\lVert\mathbf{y}'\rVert} is an estimation of u\mathbf{u}. Let the residual e=u−u^\mathbf{e} = \mathbf{u} - \hat{\mathbf{u}}. norm records rr, scale records r∥y′∥\frac{r}{\lVert\mathbf{y}'\rVert}, and error records ∥e∥\lVert\mathbf{e}\rVert (cf. § 5.2).

Given a query q\mathbf{q}, the distance to vector x\mathbf{x} is estimated as follows:

  1. Let qc=q−c\mathbf{q}_c = \mathbf{q} - c, and qc′=Tqc\mathbf{q}'_c = \mathbf{T}\mathbf{q}_c.

  2. RecastQ obtains the decoded vector y′\mathbf{y}', and estimates rr, r∥y′∥\frac{r}{\lVert\mathbf{y}'\rVert}, and ∥e∥\lVert\mathbf{e}\rVert from the three metadata bytes.

  3. The squared L2 distance is computed as follows:

d^(q,x)=∥qc∥2+r2−2r∥y′∥⟨qc′,y′⟩(4)\hat{d}(\mathbf{q},\mathbf{x}) = \lVert\mathbf{q}_c\rVert^2 + r^2 - 2\frac{r}{\lVert\mathbf{y}'\rVert}\langle\mathbf{q}'_c,\mathbf{y}'\rangle \tag*{(4)}

We use squared L2 distance in the analysis; other supported distance metrics are discussed in § 5.1, “Other metrics”.

  1. Given a parameter z>0z > 0, RecastQ further computes the uncertainty interval as [d^(q,x)−zτ(q,x),d^(q,x)+zτ(q,x)][\hat{d}(\mathbf{q},\mathbf{x}) - z\tau(\mathbf{q},\mathbf{x}), \hat{d}(\mathbf{q},\mathbf{x}) + z\tau(\mathbf{q},\mathbf{x})], where τ(q,x)=1D2r∥qc∥∥e∥\tau(\mathbf{q},\mathbf{x}) = \frac{1}{\sqrt{D}}2r\lVert\mathbf{q}_c\rVert\lVert\mathbf{e}\rVert is the uncertainty scale (cf. § 5.1).

Uncertainty Interval

Lemma 5.1 (Distance residual). The distance estimation satisfies

d(q,x)−d^(q,x)=−2r⟨qc,e⟩(5)d(\mathbf{q},\mathbf{x}) - \hat{d}(\mathbf{q},\mathbf{x}) = -2r\langle\mathbf{q}_c,\mathbf{e}\rangle \tag*{(5)}

Proof. We have d(q,x)=∥qc−xc∥2=∥qc−ru∥2d(\mathbf{q},\mathbf{x}) = \lVert\mathbf{q}_c - \mathbf{x}_c\rVert^2 = \lVert\mathbf{q}_c - r\mathbf{u}\rVert^2. Since ⟨qc′,y′∥y′∥⟩=⟨Tqc,y′∥y′∥⟩=⟨qc,TTy′∥y′∥⟩=⟨qc,u^⟩\langle\mathbf{q}'_c,\frac{\mathbf{y}'}{\lVert\mathbf{y}'\rVert}\rangle= \langle\mathbf{T}\mathbf{q}_c,\frac{\mathbf{y}'}{\lVert\mathbf{y}'\rVert}\rangle= \langle\mathbf{q}_c,\mathbf{T}^{\mathsf{T}}\frac{\mathbf{y}'}{\lVert\mathbf{y}'\rVert}\rangle= \langle\mathbf{q}_c,\hat{\mathbf{u}}\rangle, d(q,x)=∥qc∥2+r2−2r⟨qc,u^⟩d(\mathbf{q},\mathbf{x}) = \lVert\mathbf{q}_c\rVert^2 + r^2 - 2r\langle\mathbf{q}_c,\hat{\mathbf{u}}\rangle. Subtracting the two equations gives Eq. (5). □

Then, the Cauchy–Schwarz inequality immediately gives the distribution-free bound ∣d(q,x)−d^(q,x)∣≤2r∥qc∥∥e∥|d(\mathbf{q},\mathbf{x})-\hat{d}(\mathbf{q},\mathbf{x})| \leq2r\lVert\mathbf{q}_c\rVert\lVert\mathbf{e}\rVert. However, this bound assumes the worst-case scenario, and can be too loose for the selective refinement purpose. Therefore, we derive a probabilistic uncertainty bound under the following assumption.

Assumption 5.2 (Directional isotropy). Suppose r>0r > 0, ∥qc∥>0\lVert\mathbf{q}_c\rVert> 0, and ∥e∥>0\lVert\mathbf{e}\rVert> 0. The normalized residual e∥e∥\frac{\mathbf{e}}{\lVert\mathbf{e}\rVert} is uniformly distributed on the DD-dimensional unit hyper-sphere SD−1\mathbb{S}^{D-1}.

Note that this is a high-dimensional analytical model, not necessarily a property imposed by the encoding. If r=0r = 0, ∥qc∥=0\lVert\mathbf{q}_c\rVert= 0, or ∥e∥=0\lVert\mathbf{e}\rVert= 0, the residual in Lemma 5.1 is 0. Then, the estimated distance is accurate.

Lemma 5.3 (Spherical projection law). Under Assumption 5.2, let γ=⟨qc∥qc∥,e∥e∥⟩\gamma= \left\langle\frac{\mathbf{q}_c}{\lVert\mathbf{q}_c\rVert},\frac{\mathbf{e}}{\lVert\mathbf{e}\rVert}\right\rangle. The probability density function of γ\gamma is

fD(t)=Γ(D/2)πΓ((D−1)/2)(1−t2)(D−3)/2,−1<t<1(6)f_D(t) = \frac{\Gamma(D/2)}{\sqrt{\pi}\Gamma((D-1)/2)}(1-t^2)^{(D-3)/2}, \qquad-1 < t < 1 \tag*{(6)}

or equivalently, γ2∼Beta⁡(1/2,(D−1)/2)\gamma^2 \sim\operatorname{Beta}(1/2,(D-1)/2). Moreover,

E(γ)=0,Var⁡(γ)=1D,D⋅γ→D→∞N(0,1).(7)\mathbb{E}(\gamma)=0,\qquad\operatorname{Var}(\gamma)=\frac{1}{D},\qquad\sqrt{D}\cdot\gamma\xrightarrow{D\to\infty}\mathcal{N}(0,1). \tag*{(7)}

Proof. γ\gamma is the projection of e∥e∥\frac{\mathbf{e}}{\lVert\mathbf{e}\rVert} in the direction of qc∥qc∥\frac{\mathbf{q}_c}{\lVert\mathbf{q}_c\rVert}. Hence, γ\gamma can be viewed as one coordinate of a uniform point on SD−1\mathbb{S}^{D-1}. Then, Eq. (6), its Beta representation, and its moments follow from the spherical-coordinate law [10]. The normalized coordinate converges to a standard Gaussian in high dimensions [10, 13]. □

Theorem 5.4 (RecastQ uncertainty interval). Under Assumption 5.2, let τ(q,x)=1D2r∥qc∥∥e∥\tau(\mathbf{q},\mathbf{x}) = \frac{1}{\sqrt{D}}2r\lVert\mathbf{q}_c\rVert\lVert\mathbf{e}\rVert. Then, as DD increases to infinity,

d(q,x)−d^(q,x)τ(q,x)=−Dγ→D→∞N(0,1),(8)\frac{d(\mathbf{q},\mathbf{x})-\hat{d}(\mathbf{q},\mathbf{x})}{\tau(\mathbf{q},\mathbf{x})} = -\sqrt{D}\gamma\xrightarrow{D\to\infty}\mathcal{N}(0,1), \tag*{(8)}
Pr⁡{∣d(q,x)−d^(q,x)∣≤zτ(q,x)}→D→∞2Φ(z)−1.(9)\Pr\{|\mathrm{d}(q,x)-\hat{d}(q,x)|\le z\tau(q,x)\}\xrightarrow{D\to\infty}2\Phi(z)-1. \tag*{(9)}

Proof. For Eq. (8), the left hand side =−2r⟨qc,e⟩2r∥qc∥∥e∥D=−Dγ=\frac{-2r\langle q_c,e\rangle}{2r\|q_c\|\|e\|}\sqrt{D}=-\sqrt{D}\gamma. Then, Eq. (8)} follows from Lemma 5.3, and Eq. 9} results from the standard Gaussian distribution. □

Based on Theorem 5.4, the true distance is within the uncertainty interval [d^(q,x)−zτ(q,x),d^(q,x)+zτ(q,x)][\hat{d}(q,x)-z\tau(q,x),\hat{d}(q,x)+z\tau(q,x)] with approximate probability 2Φ(z)−12\Phi(z)-1. The parameter zz controls the interval size. Our experiments in Table 2 empirically test the setting of zz (cf. § 7.4). The uncertainty interval covers 68.16–68.71% cases at z=1z=1, and 95.43–95.85% cases at z=2z=2. These are close to the 68.27% and 95.45% probabilities in the standard Gaussian.2

Data setCoverage z=1z = 1 (%)Coverage z=2z = 2 (%)Metadata overflow (%)
SIFT1M68.1695.430.0012
DEEP1M68.7195.850.0004
SPACEV1M68.3795.670.0001

Table 2. Interval calibration and metadata overflow.

Other metrics. For inner-product and cosine search, we disable reference centering because subtracting a reference vector changes both measures. We support inner product through negative similarity with uncertainty scale 1D∥q∥∥e∥\frac{1}{\sqrt{D}}\|q\|\|e\|. For cosine distance (1−cos⁡(q,x))(1-\cos(q,x)), we use 1D∥e∥\frac{1}{\sqrt{D}}\|e\| as the uncertainty scale.

Three Metadata Bytes

RecastQ represents each of norm, scale, and error in one byte. For error, since it is in [0,2][0,2], RecastQ stores ⌈error2255⌉\lceil\frac{\mathit{error}}{2}255\rceil. For norm and scale, 255 is reserved as an overflow sentinel. If a vector’s norm or scale falls outside the representable metadata range, RecastQ stores the overflow sentinel. For such cases, the uncertainty interval is treated as unbounded, which satisfies the θK\theta_K bound, and therefore the corresponding vector record is always refined. In this way, we ensure that the metadata saturation cannot erroneously exclude a vector. For non-sentinel cases, the normal distance and interval computation are performed.

Bit-Gain-Aware Uneven Grouping

PQ performs even grouping: every dimension group contains the same number of (e.g., 2) dimensions. Since a group is encoded with a fixed number of (e.g., 4) code bits, even grouping treats each dimension equally in essence. However, different dimensions can have significantly different data distributions.

We propose uneven grouping in RecastQ to capture the difference across dimensions. The basic idea is to (1) partition the dimensions (for vectors in the transformed space) into uneven groups, which can contain different numbers of dimensions, and (2) keep the fixed number of code bits (i.e., 4 bits) per group.

The benefits of uneven grouping are as follows. First, the number of code bits per dimension is lower for groups with larger number of dimensions. This reflects the data variance across dimensions, thereby improving the encoding quality and decreasing the error ∥e∥\|e\|. Second, lower errors result in narrower uncertainty intervals, leading to smaller number of refinement candidates and better query throughput. Finally, the resulting code still follows the fixed 4-bit group size, which is compatible to Faiss PQ4 FastScan, and amenable to SIMD acceleration.

Next, we answer the question how to assign dimensions to groups. Let us consider the benefit of assigning an extra code bit to a dimension. Let Dj(b)\mathcal{D}_j(b) denote the expected quantization distortion of a dimension jj under a budget of bb code bits. According to the quantization literature [21], Dj(b)=κσj22−2b\mathcal{D}_j(b)=\kappa\sigma_j^2 2^{-2b}, where σj2\sigma_j^2 is the variance of dimension jj. Then, the reduction of distortion by adding an extra bit, which is the marginal gain, is Gj(b)=Dj(b)−Dj(b+1)=34Dj(b)\mathcal{G}_j(b)=\mathcal{D}_j(b)-\mathcal{D}_j(b+1)=\frac{3}{4}\mathcal{D}_j(b). In the ideal case, if we continuously assign the next bit to the dimension with the largest marginal gain, the resulting distortion is the same across all dimensions. Suppose the total number of code bits is 4M4M, which is determined by the specified memory budget. Hence, we have bj=max⁡(0,log⁡2σj−λ)b_j=\max(0,\log_2\sigma_j-\lambda) and ∑jbj=4M\sum_j b_j=4M, where λ\lambda is a constant chosen to satisfy the bit budget. That is, the number of code bits of a dimension is proportional to the logarithm of the standard deviation log⁡2σj\log_2\sigma_j. For dimensions whose log⁡2σj≤λ\log_2\sigma_j\le\lambda, no bit is assigned.

From the above analysis, bjb_j can be viewed as the demand of dimension jj. Each of the MM code group has a code budget of 4 bits. We design a greedy algorithm to assign dimensions to groups as shown in Algorithm 3. The algorithm initializes group budgets and dimension demands (Line 1–3). Then, it sorts the dimensions (Line 4) and assigns the dimensions one by one in the descending order of the demand (Line 5–9). For each dimension, the group with the largest remaining budget is chosen to accommodate the dimension (Line 7), and the group’s budget is adjusted accordingly (Line 9). Finally, the algorithm returns the group assignment.

Algorithm 3 Bit-gain-aware uneven grouping.

Require: vectors X ∈ ℝ^{N×D}, number of 4-bit groups M
1: budget[g] ← 4 and G[g] ← ∅ for group g = 1,...,M
2: compute σ_j of X for dimension j = 1,...,D
3: choose λ s.t. b[j] ← max(0, log₂ σ_j − λ) and ∑_j b[j] = 4M
4: sort the dimensions in the descending order of b[j]
5: for i = 1 to D do
6:   j ← the dimension with the i-th largest demand
7:   g* ← argmax budget[g]
8:   assign dimension j to group g*
9:   budget[g*] ← budget[g*] − b[j], G[g*] ← G[g*] ∪ {j}
10: return G

Memory-Side Optimizations

Previously, in § 3, we have described how Recast uses the compressed coarse quantizer to accelerate the distance computation of list centroids for IVF list selection. In this section, we focus on the optimization of RecastQ code scanning in the probed IVF lists.

Why exact-float accumulation. Faiss FastScan normally quantizes the LUT entries in uint8. This is effective for approximate ranking, but introduces an additional numerical residual.

For a row mm (m=1,…,Mm=1,\ldots,M), let Tm[cm]T_m[c_m] be the exact float32 entry selected from the LUT, and T^m[cm]\hat{T}_m[c_m] be the reconstructed value from the uint8 quantization. Then, the additional residual is

δLUT=∑m(T^m[cm]−Tm[cm]),∣δLUT∣≤∑mϵm,(10)\delta_{\mathrm{LUT}}=\sum_m\left(\hat{T}_m[c_m]-T_m[c_m]\right),\qquad|\delta_{\mathrm{LUT}}|\le\sum_m\epsilon_m, \tag*{(10)}

where ϵm\epsilon_m bounds the quantization error of row mm. δLUT\delta_{\mathrm{LUT}} contributes to d^(q′,y′)\hat{d}(q',y') in Eq. (4). The squared-L2 estimate of row mm is −2r∥y′∥$,incurringanadditionalerrorupto\frac{-2r}{\|y'\|}\$, incurring an additional error up to\frac{2r}{|y'|}\sum_m\epsilon_m$. Ignoring the residual would make the uncertainty interval inconsistent with Require: 32-vector packed block BB; the lookup table in float32, LUT T[M][16]T[M][16]; an even number of groups MM

Image not extracted

Figure 4. Algorithm 4 AVX-512 exact-float RecastQ block FastScan.

Ensure: Unquantized lookup sums of 32 vectors D[0…31]D[0 \ldots31]

  1. Alo,Ahi←ZeroZmm,ZeroZmmA_{\mathrm{lo}}, A_{\mathrm{hi}} \leftarrow\mathrm{ZeroZmm}, \mathrm{ZeroZmm}

  2. for m←0,2,…,M−2m \leftarrow0, 2, \ldots, M-2 do

  3. p←B+32∗m/2p \leftarrow B + 32 * m/2

  4. X0,X1←Vmovdqu(p),Vmovdqu(p+16)X_0, X_1 \leftarrow\mathrm{Vmovdqu}(p), \mathrm{Vmovdqu}(p+16)

  5. (Q0lo,Q1lo)←Vpand((X0,X1),0x0f)(Q_0^{\mathrm{lo}}, Q_1^{\mathrm{lo}}) \leftarrow\mathrm{Vpand}((X_0,X_1), 0\mathrm{x}0f)

  6. (H0,H1)←Vpsrlw((X0,X1),4)(H_0,H_1) \leftarrow\mathrm{Vpsrlw}((X_0,X_1),4)

  7. (Q0hi,Q1hi)←Vpand((H0,H1),0x0f)(Q_0^{\mathrm{hi}}, Q_1^{\mathrm{hi}}) \leftarrow\mathrm{Vpand}((H_0,H_1),0\mathrm{x}0f)

  8. L0,L1←Vmovups(T[m,:]),Vmovups(T[m+1,:])L_0,L_1 \leftarrow\mathrm{Vmovups}(T[m,:]),\mathrm{Vmovups}(T[m+1,:])

  9. Alo←LookupAdd(Alo,Q0lo,L0)A_{\mathrm{lo}} \leftarrow\mathrm{LookupAdd}(A_{\mathrm{lo}},Q_0^{\mathrm{lo}},L_0)

  10. Alo←LookupAdd(Alo,Q1lo,L1)A_{\mathrm{lo}} \leftarrow\mathrm{LookupAdd}(A_{\mathrm{lo}},Q_1^{\mathrm{lo}},L_1)

  11. Ahi←LookupAdd(Ahi,Q0hi,L0)A_{\mathrm{hi}} \leftarrow\mathrm{LookupAdd}(A_{\mathrm{hi}},Q_0^{\mathrm{hi}},L_0)

  12. Ahi←LookupAdd(Ahi,Q1hi,L1)A_{\mathrm{hi}} \leftarrow\mathrm{LookupAdd}(A_{\mathrm{hi}},Q_1^{\mathrm{hi}},L_1)

  13. π←[0,2,4,…,14,1,3,5,…,15]\pi\leftarrow[0,2,4,\ldots,14,1,3,5,\ldots,15]

  14. D[0…15]←Vpermps(π,Alo)D[0\ldots15] \leftarrow\mathrm{Vpermps}(\pi,A_{\mathrm{lo}})

  15. D[16…31]←Vpermps(π,Ahi)D[16\ldots31] \leftarrow\mathrm{Vpermps}(\pi,A_{\mathrm{hi}})

  16. return DD

the distance, but covering it entails wider intervals and degraded refinement performance.

To avoid this problem, Recast uses the original float32 values in the LUT. Our experiments in Figure 7(a) confirms the practical effect of this design decision: exact-float accumulation reaches the same recall with fewer refinement candidates compared to uint8 accumulation (cf. § 7.4).

LUT accuracy and execution cost

Figure 7. LUT accuracy and execution cost.

Why SIMD is necessary. While having the desired numerical accuracy, the scalar exact-float computation extracts one code and performs one float32 LUT lookup for every code group of every scanned encoded vector. Our experiments in Figure 7(b) shows that scalar LUT lookup dominates the query time. Therefore, we develop an exact-float kernel that exploits the AVX-512 SIMD operations to accelerate the exact-float computation.

AVX-512 exact-float FastScan. For the packed RecastQ code block, we follow the layout of the Faiss PQ4 FastScan. Specifically, the layout requires the number of code groups MM to be an even number. Then, for every pair of (m,m+1)(m,m+1) code groups, the packed block contributes 32 bytes, storing 4-bit code words for 32 vectors in the two code groups. The first and second 16 bytes encode subquantizers mm and m+1m+1, respectively. Within each byte, the lower 4-bit nibble belongs to vectors 0–15 and the higher 4-bit nibble to vectors 16–31. Within either 16-vector half, the lanes are stored in the order of [0, 8, 1, 9, ..., 7, 15].

For the float32-based LUT, an LUT row stores 16 values, which correspond to the 16 centroids of a 4-bit code group. Hence, a row takes 64B, which fits into a 512-bit ZMM register. Then, inside LookupAdd, we use the SIMD permutation D=VPERMPS(I,L)D=\mathrm{VPERMPS}(I,L) to perform an entire 16-way lookup in parallel. For example, if LL contains the TmT_m row in the LUT, indices [3, 10, 1 ...] obtain [$T_m[3], T_m[10], T_m[1], ...].

Algorithm 4 lists the SIMD-accelerated exact-float FastScan procedure. It first initializes two 512-bit ZMM registers (i.e., AloA_{\mathrm{lo}} and AhiA_{\mathrm{hi}}) as the accumulators (Line 1), then enters the main for-loop to process MM code groups (Line 2–12). Each for-loop iteration processes a pair of (m,m+1)(m,m+1) code groups. It obtains the starting address (Line 3), and loads the first and second 16 bytes into two 128-bit XMM registers (i.e., X0X_0 and X1X_1) corresponding to group mm and m+1m+1, respectively (Line 4). After that, the procedure uses bit-wise AND and right-shift operations to obtain the lower and higher nibbles (Line 5–7), loads the two LUT rows (Line 8), and looks up and accumulates the LUT values to AloA_{\mathrm{lo}} and AhiA_{\mathrm{hi}} (Line 9–12). Here, LookupAdd(A,Q,L)LookupAdd(A,Q,L) widens the 16 bytes in QQ to 16 32-bit indices with VPMOVZXBDVPMOVZXBD, performs 16 register lookups with VPERMPSVPERMPS, and accumulates the retrieved values with VADDPSVADDPS. Finally, the procedure shuffles and returns the decoded values for the 32 vectors in the packed block (Line 13–16).

Metadata bytes and SIMD-based Quic computation. For each 32-vector code block, RecastQ stores three 32-byte arrays for the encoded norm, scale, and error. During the RecastQ FastScan, the metadata bytes are processed 16 vectors at a time. For each 16 vectors, a 16-byte array is loaded into a 128-bit XMM register. Then, each 8-bit code is widened to 32 bits and decoded in a 512-bit ZMM register. After that, the estimated distance d^\hat{d} and uncertainty interval [L,U][L,U] are computed in SIMD.

Given the computed [L,U][L,U], Quic uses a masked SIMD comparison to reject upper bounds above curθKcur\theta_K. The remaining upper bounds are inserted to the heap. Quic performs a second SIMD comparison to filter vectors with lower bounds above curθKcur\theta_K. For the surviving candidate vectors, Quic appends their estimated distances, lower and upper bounds, and computed in-list offsets to a buffer. After the RecastQ FastScan, Quic obtains the global θK\theta_K, and re-compares the lower bounds of vectors in the buffer against θK\theta_K to obtain the final refinement candidates.

In summary, the SIMD-accelerated procedure fuses metadata decoding, reconstruction of d^\hat{d} and [L,U][L,U], global-bound update, and refinement candidate selection, while avoiding the materialization cost of per-vector uncertainty intervals for most vectors.

Evaluation

In this section, we perform extensive experiments to compare Recast with state-of-the-art storage-optimized ANNS systems. We first describe the experimental setup in § 7.1. Then, we study the static query performance and the index performance under dynamic updates in § 7.2–§ 7.3, and the effectiveness of refinement, storage footprint, and scalability in § 7.4–§ 7.6.

Experimental Setup

Hardware and common protocol. The server is equipped with two 36-core Intel Xeon Platinum 8360Y processors (2.4GHz, 3.5GHz Turbo), 1 TiB DDR4 memory, and Intel NVMe SSDs. It runs CentOS 7.9 and supports AVX-512. All systems are compiled with GCC 9.3.1 and -O3 flag. Unless stated otherwise, all systems run 10,000 queries with 72 workers pinned to distinct physical cores. Each worker issues 4-KiB-aligned I/Os to the same SSD with the O_DIRECT setting and QD=8. We fix the CPU frequency at 2.4 GHz and monitor Bzy_MHz; no AVX-512 frequency reduction is observed.

Data sets and metrics. Storage experiments use the 100M variants of SIFT, DEEP, and SPACEV 2, whose dimensionalities are 128, 96, and 100, respectively; encoding experiments use their 1M variants. The distance metric is squared L2 in all results. We report Recall@KK, QPS, refined vectors, the number of read requests, and/or unique 4-KiB storage pages as performance metrics. Fixed-recall values are interpolated from adjacent measured Pareto points; there is no extrapolation.

Systems and fairness. We compare Recast with DiskANN [42], Starling [44], OdinANN [23], SPANN [11], and SPFresh [47]. For each system, we tune its parameters to optimize the query performance. DiskANN uses R=64R = 64, build L=100L = 100, no node cache, and beamwidth 8. Starling uses page search with use_ratio=0.3use\_ratio=0.3 and beamwidth 8. Its disk-graph (R,L)(R, L), and PQ bytes/vector are (64, 128, 19), (31, 128, 8), and (64, 128, 12) on SIFT100M, DEEP100M, and SPACEV100M, respectively. Its navigation graph uses (Rm,Lm,α)=(32,128,1.2)(R_m, L_m, \alpha) = (32, 128, 1.2); the navigation sample rates are 0.25%, 0.1%, and 0.1%. Among the settings, LL, LmL_m, and α\alpha follow the public configuration, use_ratiouse\_ratio and the 8 passes follow the paper’s recommended settings, while we tune the rest of the settings. SPANN uses ratios 0.10, 0.026, and 0.09 on SIFT100M, DEEP100M, and SPACEV100M, respectively. SPFresh uses ratios 0.065, 0.020, and 0.080 on the three data sets, respectively, with a 256-MiB RocksDB cache. OdinANN uses the official PipeANN 0.1.1 implementation with R=96R = 96, build L=128L = 128, no in-memory graph, and pipeline width 8. Its (B,PQ bytes/vector)(B, \text{PQ bytes/vector}) settings are (2.25, 21) on SIFT100M and (1.785, 16) on both DEEP100M and SPACEV100M. Recast uses 100K IVF lists, with RecastQ M=60M = 60, M=44M = 44, and M=44M = 44 on SIFT100M, DEEP100M, and SPACEV100M, respectively.

Moreover, for each 100M data set of dimension DD, we set the memory budget to be D/40D/40 GiB (3.2 GiB for SIFT100M, 2.4 GiB for DEEP100M, and 2.5 GiB for SPACEV100M). Both in-memory index and configured caches count toward this budget. The memory footprint is measured as the increase of the process’s memory before and after loading the index. To reduce the configuration effort, we allow some compared systems to exceed this budget. For DEEP, Starling and SPANN each exceed the budget by ∼63 MiB. For SPACEV, SPANN and SPFresh exceed the budget by 824 and 336 MiB, respectively.

Furthermore, we compare RecastQ with three representative quantization encodings, i.e., PQ, OPQ, and RabitQ. PQ and OPQ use the Faiss implementation [14]. RaBitQ uses RaBitQ-Library [20] and its native reranking rule in the papers [16, 17].

Static Query Performance

Figure 3 reports top-10 static query performance. Each column in the figure corresponds to a data set. The upper row reports the measured Recall–QPS frontier, while the lower row reports the number of 4-KiB disk page accesses per query.

Figure 3. Static top-10 query performance.

We see that Recast achieves the best performance across all data sets. At Recall@1010=0.99, Recast achieves 1.56–2.01× the QPS of the strongest baseline with the same memory budget, while reading 1.73–4.10× fewer pages. This suggests that the high-recall throughput of Recast comes from the reduction of the number of I/Os. Moreover, as the recall increases, the number of I/Os of Recast grows only slightly. Higher recalls typically require larger nprobe, i.e., probing more IVF lists, while our RecastQ and Quic policy effectively filter out unnecessary exact-vector refinement.

Posting list based solutions incur much higher number of disk I/Os at high recalls because of retrieving whole selected postings, resulting in less competitive query performance. In contrast, graph-based solutions issue fewer I/Os and are generally more competitive than posting list based systems in the experiments.

Interestingly, DiskANN out-performs Starling in some cases. Compared to DiskANN, Starling allocates part of its memory budget to the navigation graph and the graphing structures. As a result, the PQ code length is reduced. This pressure is the strongest on DEEP100M because DEEP100M contains float32 vectors compared to the uint8 vectors in SIFT100M and SPACEV100M. Starling has to use 8B PQ codes, incurring significant accuracy degradation of the PQ-based distance estimation. (Note that this is a memory-budget-dependent trade-off, not an inherent claim that Starling is weaker than DiskANN.)

Maintenance Efficiency and Update Stability

We start from the static 100M indexes, and perform 50 rounds of updates. Each round deletes 1M vectors, and inserts 1M new vectors, preserving a total 100M active vectors. As shown in Figure 4, after cumulative updates have replaced 0%, 1%, 5%, 10%, 20%, 30%, and 50% of the corpus, we report the top-10 query throughput at recall=0.99 in the top row, and the storage footprint in the bottom. For the update performance, we report the time for completing the each 1M delete+1M insert round in the middle row.

Figure 4 (PDF p. 10). Query performance, update performance, and storage footprint with updates.

From the figure, we see that Recast retains 93.1–97.3% of its round-0 QPS after replacing half of each measured corpus. Its update rounds take an average 13.6–14.0 seconds, while its storage footprint grows by only 0.9–2.8%. Moreover, compared to SPFresh, Recast lowers the average update latency by 3.3–20.7×; compared to OdinANN, it lowers the average by 36.1–210.5×. OdinANN retains 73.4–75.5% of its initial QPS after 50% corpus replacement, and SPFresh retains 64.7–68.5%. Furthermore, there are non-monotonic points and latency spikes in the results of SPFresh and OdinANN. They often coincide with the compaction or merging activities. For OdinANN, its active-plus-standby storage work set grows by 204.9–234.2% across the three datasets and oscillates as merged versions replace old ones. In comparison, Recast shows robust performance because Recast does not perform background tasks for index maintenance.

Refinement Effectiveness

Figure 5 studies the effectiveness of the encoding methods and refinement policies. In the left sub-figures, we compare RecastQ with PQ, OPQ, and RabitQ. Both PQ and OPQ use the fixed-RR policy. In the right sub-figures, we use Quic to enhance both PQ and OPQ, and compare the baseline PQ/OPQ and the enhanced PQ/OPQ. All methods probe the same IVF lists. We set nprobenprobe to 62/78/245 for SIFT/DEEP/SPACEV, giving unencoded coarse Recall@10 of 0.99524/0.99500/0.99007. The vertical dashed line in each sub-figure marks this ideal recall ceiling.

Figure 5. Effectiveness of RecastQ and Quic policy.

From the left sub-figures, we see that RecastQ is the overall best encoding method across all data sets. At matched encoding sizes, RecastQ refines 3.4–7.9× and 1.5–2.5× fewer number of vectors than 1-bit RabitQ at 28 bytes/vector and 2-bit RabitQ near 52 bytes/vector, respectively. The 2-bit RabitQ is the best performing encoding among the baseline methods. RabitQ’s reported sizes include its required dimension padding and auxiliary factors. For SPACEV1M, RabitQ-1bit is absent because all of its measured points at Recall@10≥0.90 exceed the Y-axis limit of 200 refinements/query.

From the right sub-figures, we see that applying Quic to PQ/OPQ leads to improved performance. (Solid curves are the baseline methods, while dashed curves correspond to the enhanced methods.) The improvement is especially pronounced for SPACEV. This confirms the benefit of Quic compared to the fixed-RR policy.

Figure 6 shows the impact of encoding size on the number of refined vectors for RecastQ at different recalls. We see that as the code size increases, the number of refined vectors quickly decreases. At Recall@10=0.99, the plotted code-size ranges reduce refinement demand by 3.3× on SIFT1M and 4.2× on DEEP1M. This is because larger code leads to more accurate estimation of the distance and the uncertainty intervals.

Impact of code size on refinement performance

Figure 6. Impact of code size on refinement performance.

Float32 vs. uint8 accumulation. fig:7a compares the refinement performance for uint8 and float32 accumulation designs. We see that the float32 accumulation achieves a stronger Recall–refinement frontier compared to uint8 accumulation. This motivates us to use float32 values in the LUT.

fig:7b reports the breakdown of the execution cost at Recall@10=0.99. For the scalar float32 design, RecastQ scan dominates the query time. Hence, we exploit SIMD acceleration to reduce the computation cost. The resulting AVX-512 based design takes 6.0 ms/query, compared with 6.8 ms for uint8 and 134.5 ms for scalar float32, a 22.4× speedup over the scalar path. Interestingly, the uint8 SIMD design in Faiss takes slightly longer time than our float32 SIMD design. This is because the uint8 SIMD design needs to perform an extra decoding step for the uint8 codes in LUT.

Quic with and without SIMD. Figure 10 uses the same SIFT100M single-worker, QD=8 operating point as fig:7b. The time is also broken down in the same fashion as fig:7b.

Figure 10. QUIC with and without SIMD.

From Figure 10, we see that enabling Quic’s SIMD pipeline reduces the green Quic stage from 6.42 to 1.42 ms/query (i.e., a 4.52× improvement) and the total time from 11.86 to 5.96 ms/query (i.e., a 1.99× improvement). In this experiment, the recall, refinement candidate count, and the number of I/O page accesses remain

unchanged. Therefore, the performance gain clearly comes from the accelerated in-memory execution.

Quality of uncertainty interval. Table 2 verifies the coverage of the uncertainty intervals for the three data sets. We see that the uncertainty intervals cover 68.16–68.71% and 95.43–95.85% of the true distances at z=1z = 1 and z=2z = 2, respectively. This is quite close to the Gaussian based estimation, which is 68.27% and 95.45% at z=1z = 1 and z=2z = 2, respectively3.

Table 2 also shows the percentage of vectors with overflowed norm or scale. We see that metadata overflow remains below 0.002%, showing that quantize uncertainty information rarely invokes the conservative overflow path.

Storage Footprint

Table 3 reports query-required storage data, excluding structures already counted in the common in-memory index budget. We see that Recast has the lowest storage footprint for every data set, using 1.22–2.88× less storage space than the system with the next lowest storage footprint. (We construct the 100M-vector indexes of Recast in 14.1–21.5 minutes using multiple GPUs to perform the K-means clustering and parallel CPU threads to produce the IVF lists. Here, the build time is mentioned to provide context for understanding Recast rather than for an equal-hardware comparison.)

SystemSIFT100MDEEP100MSPACEV100M
DiskANN38.14763.57834.679
Starling38.14747.68436.597
OdinANN54.49676.29447.684
SPANN85.717234.61360.187
SPFresh89.277178.55363.696
Recast13.23639.06413.083

Table 3. Storage footprint on 100M-vector data sets (GiB).

Query and Update Scalability

We study the scalability of the storage-optimized ANNS solutions in this subsection. We vary the number of query worker threads from 1 to 72. Figure 8 shows the QPS at recall=0.95 and at recall=0.99 while varying the number of query workers. We use the same fixed-recall configurations and physical-core protocol at every worker count. We see that as the number of workers increases from 1 to 72, Recast scales QPS by 49.3× at Recall@10=.95 and 45.6× at .99. At 72 workers it exceeds the strongest baseline by 1.39–1.71× across the two recall targets. Graph traversal remains competitive at low concurrency, while Recast’s in-memory selection and independent exact-vector reads provide the stronger high-concurrency scaling.

Figure 8. Static query scalability on SIFT100M.

Figure 9 reports the update throughput by varying the number of threads. We start from the same 100M-vector index, then perform the same round of 1M deletes and 1M new inserts for every worker count. We see that Recast scales the update throughput by 26.6× from 1 to 72 workers and reaches 74,434 delete+insert pairs/s. At 72 workers, it is 3.1–37.3× faster than SPFresh and OdinANN. Note that all results include the work required before the updated index can serve queries.

Figure 9. Update scalability (SIFT100M).

Related Work

We have studied previous storage-optimized ANNS systems in § 2. Since Recast builds an in-memory index that stores RecastQ encodings, we discuss the related work on in-memory ANNS indexes and quantization encodings in this section.

In-memory ANNS indexes. In-memory ANN spans tree and hashing methods such as KD-tree, ball tree, VP-tree, FLANN, and LSH variants [2, 8, 9, 29, 33, 37, 48]; proximity graphs such as HNSW and NSG [15, 26, 34, 38, 43]; and cluster-based indexes such as IVF, IMI, ScaNN, and BLISS [6, 24, 25, 41]. Clustered layouts support contiguous scans that combine naturally with quantization and SIMD execution. Recast uses an IVF-compatible in-memory organization rather than introducing a new coarse-search index; its focus is deciding from compact scan results which exact vectors must subsequently be accessed from storage.

Quantization encoding and reranking

Compact vector representations include dimension-wise schemes such as VA-File [45], ITQ [19], and LVQ [1]; additive-codebook methods such as AQ [5] and LSQ [35]; and product methods such as product quantization (PQ) [28] and optimized product quantization (OPQ) [18]. PQ and OPQ encode vectors into short Cartesian-product codes and support asymmetric distance computation. PQ Fast Scan [3], Quicker ADC [4], and related kernels reorganize codes and lookup tables for SIMD execution. These methods primarily optimize approximate ranking, reconstruction, or scan throughput. RecastQ reuses a PQ4 execution substrate but stores the magnitude and directional-error information needed for refinement candidate selection.

RaBitQ [17] and Extended RaBitQ [16] combine randomized quantization with bounded distance estimators and lower-bound-guided reranking. They are the closest encoding-level baselines to RecastQ. We use the reference library and native reranking rule rather than replacing it with Recast’s selector. Recast differs in co-designing the uncertainty information, the global Top-K selector, page planning, and mutable external-store architecture as one system.

Conclusion

In conclusion, we have introduced a refinement-centered paradigm for storage-optimized ANNS systems. We have proposed and studied Recast as a concrete design of this paradigm. It enjoys a simple storage layout with low footprint and easy update support, and exploits a compact in-memory IVF index with the RecastQ encodings and the QUIC policy for efficient query processing. We believe that our proposed solution provides a promising answer to the central design question, achieving high query throughput without sacrificing the recall and index maintenance performance.

Proofs for Uncertainty-Guided Candidate Selection

Fix a query and its scanned set S={x1,…,xn}S = \{x_1,\ldots,x_n\}, with n≥Kn \ge K, true distances d1≤⋯≤dnd_1 \le\cdots\le d_n, and fixed tie-breaking. Define Rref@K=K−1∑j=1K1{Lj≤θK}R_{\mathrm{ref}@K} = K^{-1}\sum_{j=1}^{K}1\{L_j \le\theta_K\}. Expectations are conditional on the true distances and scales. The results concern the uncapped selector in Eq. (2), not coarse-list misses or additional candidate-cap truncation. We distinguish the true-distance spacing needed for the recall bound from the endpoint spacing used for counts.

Retention and a Gaussian Product Bound

Let Nj=∑i≠j1{Ui<Lj}N_j = \sum_{i\ne j}1\{U_i < L_j\}. Since Uj≥LjU_j \ge L_j, candidate jj is retained exactly when Nj≤K−1N_j \le K-1. If all intervals contain the true distances, an excluded candidate has dj≥Lj>θKd_j \ge L_j > \theta_K, whereas at least KK candidates have di≤Ui≤θKd_i \le U_i \le\theta_K. This proves Theorem 4.2, including ties.

For the probabilistic result, assume τi>0\tau_i > 0 and

d^i=di+τiZi,Zi∼iidN(0,1).(11)\hat{d}_i = d_i + \tau_i Z_i,\qquad Z_i \mathrel{\overset{\mathrm{iid}}{\sim}} \mathcal{N}(0,1). \tag*{(11)}

Independence across candidates is an additional modeling assumption; it does not follow from Gaussian marginal errors.

Proposition A.1 (Candidate-dependent recall bound). Under Eq. (11),

E[Rref@K]≥1K∑j=1K∏l=K+1nΦ(dl−dj+z(τl+τj)τl2+τj2).(12)\mathbb{E}[R_{\mathrm{ref}@K}] \ge\frac{1}{K}\sum_{j=1}^{K}\prod_{l=K+1}^{n}\Phi\left(\frac{d_l-d_j+z(\tau_l+\tau_j)}{\sqrt{\tau_l^2+\tau_j^2}}\right). \tag*{(12)}

Proof. For j≤Kj \le K, the event Aj=⋂l>K{Ul≥Lj}A_j=\bigcap_{l>K}\{U_l\ge L_j\} implies retention: only the other K−1K-1 true neighbors can contribute to NjN_j. Conditional independence given Zj=tZ_j=t gives

gjl(t)=Pr⁡(Ul≥Lj∣Zj=t)=Φ(dl−dj+z(τl+τj)−τjtτl).(13)g_{jl}(t)=\Pr(U_l\ge L_j\mid Z_j=t) =\Phi\left(\frac{d_l-d_j+z(\tau_l+\tau_j)-\tau_jt}{\tau_l}\right). \tag*{(13)}
Pr⁡(Aj)=E[∏l>Kgjl(Zj)].(14)\Pr(A_j)=\mathbb{E}\left[\prod_{l>K}g_{jl}(Z_j)\right]. \tag*{(14)}

These factors are nonnegative and nonincreasing. For any such f,gf,g and independent copies T,T′T,T',

2Cov⁡(f(T),g(T))=E[(f(T)−f(T′))(g(T)−g(T′))]≥0.(15)2\operatorname{Cov}(f(T),g(T))=\mathbb{E}[(f(T)-f(T'))(g(T)-g(T'))]\ge0. \tag*{(15)}

Products preserve this monotonicity, so induction yields Pr⁡(Aj)≥∏l>KPr⁡(Ul≥Lj)\Pr(A_j)\ge\prod_{l>K}\Pr(U_l\ge L_j). Since τlZl−τjZj\tau_lZ_l-\tau_jZ_j has Gaussian variance τl2+τj2\tau_l^2+\tau_j^2, each marginal equals the corresponding Φ(⋅)\Phi(\cdot) factor in Eq. (12). Averaging over j≤Kj\le K proves the result. This association argument is necessary: crossings share ZjZ_j and are not unconditionally independent. □\square

Integral Bound and Spacing Conditions

Set τi=τ>0\tau_i=\tau>0. Since dj≤dKd_j\le d_K for j≤Kj\le K, Proposition A.1 gives

E[Rref@K]≥∏h=1n−KΦ(dK+h−dK2τ+2z).(16)\mathbb{E}[R_{\mathrm{ref}@K}]\ge\prod_{h=1}^{n-K}\Phi\left(\frac{d_{K+h}-d_K}{\sqrt{2}\tau}+\sqrt{2}z\right). \tag*{(16)}

Assume the true-distance gap condition dK+h−dK≥hΔdd_{K+h}-d_K\ge h\Delta_d, where Δd>0\Delta_d>0. Let a=2za=\sqrt{2}z, b=Δd/(2τ)b=\Delta_d/(\sqrt{2}\tau), and f(t)=ln⁡Φ(a+bt)f(t)=\ln\Phi(a+bt).

Because ff is negative and increasing, right-endpoint Riemann sums imply

ln⁡E[Rref@K]≥∑h=1n−Kf(h)≥∫0n−Kf(t) dt≥∫0∞f(t) dt=2τΔdI(2z).(17)\ln\mathbb{E}[R_{\mathrm{ref}@K}] \ge\sum_{h=1}^{n-K}f(h) \ge\int_{0}^{n-K}f(t)\,\mathrm{d}t \ge\int_{0}^{\infty}f(t)\,\mathrm{d}t =\frac{\sqrt{2}\tau}{\Delta_d}I(\sqrt{2}z). \tag*{(17)}

The integral converges because −ln⁡Φ(x)≤2(1−Φ(x))-\ln\Phi(x)\le2(1-\Phi(x)) for x≥0x\ge0 and the Gaussian tail is integrable. Exponentiation establishes the expression in Theorem 4.3 with Δ=Δd\Delta=\Delta_d. For n=Kn=K, the empty product is one and e⋯e^{\cdots} is interpreted accordingly.

Distinguishing the two spacing models. The preceding proof requires true-distance spacing Δd\Delta_d, not random upper-endpoint spacing ΔU\Delta_U. Independent nondegenerate Gaussian errors do not preserve uniform spacing and cannot simultaneously produce deterministic uniformly spaced endpoints. Thus the recall expression is not established by endpoint spacing alone; the main text’s recall and count models must be read separately.

For the count model of Theorem 4.4, suppose the sorted upper endpoints have spacing ΔU>0\Delta_U>0 and a common scale τ\tau. Retention is equivalent to Ui≤U(K)+2zτU_i\le U_{(K)}+2z\tau, so

∣C(S)∣=min⁡{n,K+⌊2zτ/ΔU⌋}.(18)|C(S)|=\min\{n,K+\lfloor2z\tau/\Delta_U\rfloor\}. \tag*{(18)}

The main text’s count upper bound follows once this expression reaches nn. Likewise, substituting empirical mean scales and gaps is illustrative, not a guarantee: an observed endpoint gap is not a verified lower bound on true-distance gaps. The example τ/Δ=20.316\tau/\Delta=20.316, z=2z=2 yields approximately 0.9803 within the model, without establishing its assumptions for every query.

References

  1. [1]Cecilia Aguerrebere, Ishwar Singh Bhati, Mark Hildebrand, Mariano Tepper, and Theodore Willke. 2023. Similarity Search in the Blink of an Eye with Compressed Indices. Proceedings of the VLDB Endowment 16, 11 (2023), 3433–3446.
  2. [2]Alexandr Andoni and Piotr Indyk. 2008. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM 51, 1 (2008), 117–122.
  3. [3]Fabien André, Anne-Marie Kermarrec, and Nicolas Le Scouarnec. 2015. Cache locality is not enough: high-performance nearest neighbor search with product quantization fast scan. Proceedings of the VLDB Endowment 9, 4 (2015), 288–299.
  4. [4]Fabien André, Anne-Marie Kermarrec, and Nicolas Le Scouarnec. 2021. Quicker adc: Unlocking the hidden potential of product quantization with SIMD. IEEE transactions on pattern analysis and machine intelligence 43, 5 (2021), 1666–1677.
  5. [5]Artem Babenko and Victor Lempitsky. 2014. Additive quantization for extreme vector compression. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 931–938.DOI
  6. [6]Artem Babenko and Victor Lempitsky. 2015. The inverted multi-index. IEEE transactions on pattern analysis and machine intelligence 37, 6 (2015), 1247–1260.DOI
  7. [7]Artem Babenko and Victor Lempitsky. 2016. Efficient indexing of billion-scale datasets of deep descriptors. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2055–2063.
  8. [8]Mayank Bawa, Tyson Condie, and Prasanna Ganesan. 2005. LSH forest: self-tuning indexes for similarity search. In Proceedings of the 14th international conference on World Wide Web, 651–660.
  9. [9]Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching. Commun. ACM 18, 9 (1975), 509–517.DOI
  10. [10]Tony Cai, Jianqing Fan, and Tiefeng Jiang. 2013. Distributions of Angles in Random Packing on Spheres. Journal of Machine Learning Research 14, 57 (2013), 1837–1864. https://jmlr.org/papers/v14/cai13a.htmlarxiv.org/abs/1306.0256
  11. [11]Qi Chen, Bing Zhao, Haidong Wang, Mingxin Liu, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021. SPANN: Highly-efficient Billion-scale Approximate Nearest Neighborhood Search. Advances in Neural Information Processing Systems 34 (2021), 5199–5212.
  12. [12]Yangshen Deng, Zhengxin You, Long Xiang, Qilong Li, Peiqi Yuan, Zhaoyang Hong, Yitao Zheng, Wanting Li, Runzhong Li, Haotian Liu, Kyriakos Mouratidis, Man Lung Yiu, Huan Li, Qiaomu Shen, Rui Mao, and Bo Tang. 2025. AlayaDB: The Data Foundation for Efficient and Effective Long-term Inference. In Companion of the 2025 International Conference on Management of Data. ACM, New York, NY, USA, 364–377. https://doi.org/10.1145/3722212.3724428
  13. [13]Persi Diaconis and David Freedman. 1987. A Dozen of Finetti-Style Results in Search of a Theory. Annales de l’Institut Henri Poincaré, Probabilités et Statistiques 23, 52 (1987), 397–423. https://numdam.org/item/AIHPB_1987__23_ S2_397_0/
  14. [14]Matthijs Douze, Alexandre Guzhva, Cheng Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazare, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. 2024. The Faiss library. (2024). arXiv:2401.08281 [cs.LG]arxiv.org/abs/2401.08281
  15. [15]Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph. Proceedings of the VLDB Endowment 12, 5 (2019), 461–474.arxiv.org/abs/1707.00143
  16. [16]Jianyang Gao, Yutong Guo, Yuexuan Xu, Yongyi Yang, Cheng Long, and Raymond Chih-Wing Wong. 2025. Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data 3, 3 (2025), 1–26. https://doi.org/10.1145/3752413
  17. [17]Jianyang Gao and Cheng Long. 2024. RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data 2, 3 (2024), 1–27.arxiv.org/abs/2405.12497
  18. [18]Tiezhe Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized Product Quantization for Approximate Nearest Neighbor Search. In Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition. 2946–2953.DOI
  19. [19]Yunchao Gong, Svetlana Lazebnik, Albert Gordo, and Florent Perronnin. 2013. Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval. IEEE transactions on pattern analysis and machine intelligence 35, 12 (2013), 2916–2929.DOI
  20. [20]Yutong Gu, Jianyang Gao, Yuexuan Xu, Jifan Shi, and Zhonghao Yang. 2026. The RaBitQ Library. https://github.com/VectorDB-NTU/RaBitQ-Library
  21. [21]Robert M. Gray and David L. Neuhoff. 1998. Quantization. IEEE Transactions on Information Theory 44, 6 (1998), 2325–2383. https://doi.org/10.1109/18.720541
  22. [22]Hao Guo and Youyou Lu. 2026. OdinANN: Direct Insert for Consistently Stable Performance in Billion-Scale Graph-Based Vector Search. In 24th USENIX Conference on File and Storage Technologies (FAST 26). USENIX Association, Santa Clara, CA, 133–147. https://www.usenix.org/conference/fast26/presentation/guoDOI
  23. [23]Hao Guo and Youyou Lu. 2026. OdinANN: Direct Insert for Consistently Stable Performance in Billion-Scale Graph-Based Vector Search. In 24th USENIX Conference on File and Storage Technologies (FAST 26). USENIX Association, Santa Clara, CA, 133–147. https://www.usenix.org/conference/fast26/presentation/guo
  24. [24]Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020. Accelerating large-scale inference with anisotropic vector quantization. In Proceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research), Hal Daumé III and Aarti Singh (Eds.), Vol. 119. PMLR, 3887–3896. https://proceedings.mlr.press/v119/guo20h.html
  25. [25]Aaron Gupta, Tharun Medini, Anshumali Shrivastava, and Alexander J Smola. 2022. Bliss: A billion scale index using iterative re-partitioning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 486–495.
  26. [26]Ben Harwood and Tom Drummond. 2016. Fanng: Fast approximate nearest neighbour graphs. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 5713–5722.DOI
  27. [27]Herve Jegou and Laurent Amsaleg. 2010. Datasets for approximate nearest neighbor search. http://corpus-texmex.irisa.fr
  28. [28]Herve Jegou, 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.DOI
  29. [29]Bastian Leibe, Krystian Mikolajczyk, and Bernt Schiele. 2006. Efficient clustering and matching for object class recognition.. In BMVC. 789–798.DOI
  30. [30]Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Manos Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. 2020. Retrieval-augmented generation for knowledge-intensive nlp tasks. Advances in Neural Information Processing Systems 33 (2020), 9459–9474.arxiv.org/abs/2005.11401
  31. [31]Di Liu, Meng Chen, Baotong Lu, Huiqiang Jiang, Zhenhua Han, Qianxi Zhang, Qi Chen, Chengruidong Zhang, Bailu Ding, Kai Zhang, Chen Chen, Fan Yang, Yuqing Yang, and Lili Qiu. 2025. RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval. In Advances in Neural Information Processing Systems, D. Belgrave, C. Zhang, H. Lin, R. Pascanu, P. Koniusz, M. Ghassemi, and N. Chen (Eds.), Vol. 38. Main Conference. Curran Associates, Inc., 54358–54385. https://doi.org/10.52202/08713-1816
  32. [32]Ying Liu, Dengsheng Zhang, Guojun Lu, and Wei-Ying Ma. 2007. A survey of content-based image retrieval with high-level semantics. Pattern recognition 40, 1 (2007), 262–282.DOI
  33. [33]Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. 2007. Multi-probe LSH: efficient indexing for high-dimensional similarity search. In Proceedings of the 33rd international conference on Very large data bases. 950–961.
  34. [34]Yu A Malkov and Dmitry A Yashunin. 2020. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence 42, 4 (2020), 824–836.
  35. [35]Julieta Martinez, Joris Clement, Holger H Hoos, and James J Little. 2016. Revisiting additive quantization. In Computer Vision–ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11–14, 2016, Proceedings, Part II 14. Springer, 137–153.DOI
  36. [36]Microsoft Research. 2021. SPACEV1B: A Billion-Scale Vector Dataset for Text Descriptors. https://github.com/microsoft/SPTAG/tree/main/datasets/SPACEV1B
  37. [37]Marius Muja and David G Lowe. 2014. Scalable nearest neighbor algorithms for high dimensional data. IEEE transactions on pattern analysis and machine intelligence 36, 11 (2014), 227–2240.DOI
  38. [38]Yun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang, and Jianliang Xu. 2023. Efficient approximate nearest neighbor search in multi-dimensional databases. Proceedings of the ACM on Management of Data 1, 1 (2023), 1–27.DOI
  39. [39]J Ben Schafer, Dan Frankowski, Jon Herlocker, and Shilad Sen. 2007. Collaborative filtering recommender systems. In The adaptive web: methods and strategies of web personalization, Peter Brusilovsky, Alfred Kobsa, and Wolfgang Nejdl (Eds.). Lecture Notes in Computer Science, Vol. 4321. Springer Berlin Heidelberg, 291–324. https://doi.org/10.1007/978-3-540-2079-9_9
  40. [40]Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. 2021. FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search. arXiv preprint arXiv:2105.09613 (2021). https://arxiv.org/abs/2105.09613
  41. [41]Josef Sivic and Andrew Zisserman. 2003. Video Google: A text retrieval approach to object matching in videos. In Proceedings of the Ninth IEEE International Conference on Computer Vision, Vol. 2. IEEE, 1470–1477. https://doi.org/10.1109/ICCV.2003.1238663
  42. [42]Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. 2019. DiskANN: fast accurate billion-point nearest neighbor search on a single node. In Proceedings of the 33rd International Conference on Neural Information Processing Systems. 13766–13776.
  43. [43]Godfried T Touissant. 1980. The relative neighbourhood graph of a finite planar set. Pattern recognition 12, 4 (1980), 261–268.
  44. [44]Mengzhao Wang, Weizhi Xu, Xiaomeng Yi, Songlin Wu, Zhangyang Peng, Xinyu Wang, Yunjun Gao, Xiaoliang Xu, Rentong Guo, and Charles Xie. 2024. Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment. Proceedings of the ACM on Management of Data 2, 1 (2024), 1–27.DOI
  45. [45]Roger Weber, Hans-Jörg Schek, and Stephen Blott. 1998. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In VLDB, Vol. 98. 194–205.
  46. [46]Haike Xu, Magdalen Dobson Manohar, Philip A. Bernstein, Badrish Chandramouli, Richard Wen, and Harsha Vardhan Simhadri. 2025. In-Place Updates of a Graph Index for Streaming Approximate Nearest Neighbor Search. arXiv preprint arXiv:2502.13826 (2025). https://doi.org/10.48550/arXiv.2502.13826
  47. [47]Yuming Xu, Hengyu Liang, Jin Li, Shuotao Xu, Qi Chen, Qianxi Zhang, Cheng Li, Ziyue Yang, Fan Yang, Yuqing Yang, Peng Cheng, and Mao Yang. 2023. SPFresh: Incremental In-Place Update for Billion-Scale Vector Search. In Proceedings of the 29th Symposium on Operating Systems Principles. ACM, 545–561. https://doi.org/10.1145/3600006.3613166
  48. [48]Peter N Yanilos. 1993. Data structures and algorithms for nearest neighbor search in general metric spaces. In Proceedings of the fourth annual ACM-SIAM symposium on Discrete algorithms. 311–321.
  49. [49]Peiqi Yin, Xiao Yan, Qihui Zhou, Hui Li, Xiaolu Li, Meiling Wang, Lin Zhang, Xin Yao, and James Cheng. 2026. GPS: Revisiting the Data Layout for Disk-based High-Dimensional Vector Search. Proceedings of the ACM on Management of Data 4, 3 (2026), 1–29. https://doi.org/10.1145/3802696
  50. [50]Ziyang Yue, Bolong Zheng, Ling Xu, Kanru Xu, Shuhao Zhang, Yayuan Du, Yunjun Gao, Xiaofang Zhou, and Christian S. Jensen. 2025. Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-based ANN Search. Proceedings of the VLDB Endowment 18, 11 (2025), 4337–4349. https://doi.org/10.14778/3749646.3749697

Paper details

vlnc:W_zj3g6pb2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents