SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search

1 INTRODUCTION

• Graph-based ANN search is costly because it repeatedly accesses separately stored neighbor vectors and computes their exact distances.These accesses are random and unfriendly to cache.Source: §1 · p. 1
• NGT-QG uses compact neighbor quantization codes and batched FastScan, but its PQ estimates can fail on some real-world datasets and its explicit re-ranking adds random accesses.Its graph structure can also leave FastScan with non-full batches; about 23% of vertices on Deep-1M have them.Source: §1 · p. 2
• SymphonyQG combines RaBitQ with graph search, avoids explicit re-ranking through exact-distance updates during search, and uses multiple estimated distances to reduce the chance of missing true nearest neighbors.Its index construction is at least 8x faster than NGT-QG on real-world datasets, and graph refinement aligns vertex out-degrees with FastScan batches.Source: §1 · p. 2
• SymphonyQG is presented as an ANN algorithm, alongside an open-source library with C++ header-only implementations and Python APIs.The library is intended to let researchers and practitioners evaluate and use the method with a few lines of Python code.Source: §1 · pp. 2–3
• At 95% recall (K=10), SymphonyQG achieves 1.5x-4.5x QPS versus the most competitive baselines and 3.5x-17x QPS versus HNSWlib across tested datasets.The experiments also report scalability on two datasets with 100 million vectors.Source: §1 · p. 3

2 PRELIMINARIES

• The preliminaries define ANN as a way to seek better accuracy-efficiency trade-offs than exact nearest-neighbor search as vector databases grow.The paper focuses on in-memory queries, with vectors and indices stored in RAM.Source: §2.1 · p. 3

2.1 ANN and Graph-based Methods

• Graph-based ANN builds a graph over data vectors and uses greedy beam search to explore a limited candidate set, with larger beam sizes trading higher accuracy for greater latency.The beam set retains up to n_b candidates; search returns its nearest vector when all beam-set vectors have been visited.Source: §2.1 · p. 3

2.2 RaBitQ and FastScan

• RaBitQ uses quantization codes to estimate distances through an unbiased estimator with a theoretical error bound, and reports better empirical accuracy than PQ with shorter codes.Its normalized-vector formulation reduces distance estimation to estimating an inner product; FastScan batches code computations using SIMD-based look-up tables.Source: §2.2 · pp. 3–4

3 METHODOLOGY

• The query phase searches a graph index with FastScan and RaBitQ and avoids explicit re-ranking to reduce random memory accesses.The paper’s memory-access comparison also describes the method as avoiding random accesses during re-ranking.Source: §3 · p. 4
• The FastScan implementation is largely based on Faiss.Source: §3 · p. 4
• Graph construction uses the efficient search algorithm to accelerate candidate finding and prunes edges so each vertex’s degree is a multiple of FastScan’s batch size.The adaptive pruning rule makes each vertex’s edge count strictly a multiple of the batch size.Source: §3 · p. 4
• SymphonyQG supports ANN search only for Euclidean space and cosine similarity because its RaBitQ quantizer is designed for those metrics.Source: §3 · p. 4

3.1.1 Searching on Graphs with FastScan and RaBitQ for Boosting Search Performance.

• Neighbor vectors are normalized using the current vertex, and their RaBitQ codes are stored beside it for batched FastScan distance estimates.Because normalization varies by vertex, a vector that neighbors multiple vertices has different stored codes at each vertex.Source: §3.1.1 · pp. 4–5
• Preparing FastScan look-up tables per visited vertex would limit their reuse to that vertex’s neighbors, so the method reformulates the computation to prepare query-time tables shareable across database vectors.The reformulation uses a computation independent of the normalization center.Source: §3.1.1 · p. 5

3.1.2 Avoiding Explicit Re-Ranking for Reducing Random Memory Accesses.

• SymphonyQG implicitly re-ranks by reusing the exact distance computed for each visited vertex, returning the best exact-distance candidate without a final re-ranking pass.With its specialized data layout, this avoids extra random memory accesses for re-ranking.Source: §3.1.2 · p. 6
• The search appends unvisited neighbors even when already present in the beam set, allowing multiple estimated distances per vector to reduce the chance that an overestimated true neighbor is missed.RaBitQ gives each estimate a 50% probability of underestimating a true nearest neighbor’s distance; its error bound also limits deviations for other vectors.Source: §3.1.2 · p. 6

3.1.3 Summary of Querying Algorithm.

• Each object’s sequential memory block stores its raw vector, FastScan data, and graph neighbors, so visiting a vertex accesses a continuous memory segment.The algorithm repeatedly selects the unvisited vertex with the smallest estimated distance, computes its exact distance, then estimates its neighbors’ distances and returns the maintained nearest neighbor.Source: §3.1.3 · p. 6

3.1.4 Implementation Techniques.

• Implementation techniques include prefetching the next vertex’s data, extending SIMD acceleration through the algorithm with AVX512 support, and using Fast Hadamard Transformation for faster random rotation.Fast JLT reduces random-rotation complexity from O(D^2) to O(D log D), where D is the vector dimension.Source: §3.1.4 · p. 7

3.2.1 Leveraging FastScan for Building Graph-based Indices Effi-

• Indexing is at least 8x faster than NGT-QG, while the query-based construction is at least 2.5x faster than original NSG without harming search performance.The NSG comparison concerns the indexing algorithm described for candidate generation and pruning.Source: §3.2.1 · p. 7

3.2.2 Refining Graph-based indices towards Better Alignment with FastScan.

• Adaptive pruning supplements vertices with fewer than R edges until each has exactly R out-edges, aligning graph degrees with FastScan batches.The pruning threshold is chosen by binary search and may differ across vertices.Source: §3.2.2 · pp. 7–8
• Because FastScan estimates distances in batches, filling batches with edges does not increase distance-estimation time; refinement consistently improves search performance on tested datasets.The passage links the additional edges to a lower likelihood of missing the true nearest neighbor during graph search.Source: §3.2.2 · p. 8

3.2.1 Leveraging FastScan for Building Graph-based Indices Effi-

• Each iteration prepares FastScan data, generates neighbor candidates with the querying algorithm, applies NSG pruning, and adjusts the graph; vertex operations are highly parallelizable.The graph is randomly initialized and adjusted for 3 or 4 iterations in practice.Source: §3.2.1 · p. 7, §3.2.2 · p. 8

• For ANN queries, SymphonyQG uses RaBitQ and FastScan and avoids explicit re-ranking; its graph refinement aligns out-degrees with FastScan’s batch size.When candidates are fewer than the maximum out-degree, randomly selected neighbors can fill out-degrees to a multiple of 32.Source: §3.3 · p. 8
• At 95% recall (K=10), SymphonyQG achieves 1.5x-4.5x QPS versus the most competitive baselines and 3.5x-17x versus HNSWlib on tested datasets.Source: §3.3 · p. 8
• Indexing is at least 2.5x faster than NSG and at least 8x faster than NGT-QG.Source: §3.3 · p. 8
• Neighbor-code storage adds D×R bits per vector; at R=32 or 64, this equals 1x or 2x the storage for raw vectors, respectively.Source: §3.3 · p. 8

4.1 Experimental Setup

• Experiments benchmark six million-scale datasets against four optimized graph-based libraries, using QPS, recall, and average distance ratio to assess search trade-offs.The study also reports indexing time and memory footprint, and uses two 100-million-vector datasets for scalability evaluation.Source: §4.1 · pp. 8–9, §4 · p. 8

4.2.1 Performance Study.

• At K=10, SymQG achieves 1.5x–4.5x QPS over the most competitive baselines at 95% recall across six datasets, and leads QPS-ADR at both K=10 and K=100.It also achieves 3.5x–17x QPS over HNSWlib at 95% recall.Source: Figure 4 · p. 9, Figure 5 · p. 10, §4.2.1 · p. 11

4.2.2 Scalability Study.

• On Deep-100M and MSTuring-100M, SymQG delivers at least 2.5x QPS over OG-LVQ at 95% recall.NGT-QG could not build an index within one day using 1TB memory, while SymQG finished indexing within two hours; SymQG’s memory footprint was larger than other methods.Source: Figure 7 · p. 12, §4.2.2 · p. 12

4.2.3 Ablation Study.

• SymQG builds indexes at least 2.5x faster than SymQG-NSG while retaining competitive or better query performance across six datasets.SymQG also has higher memory use than vanilla graph methods but lower memory use than NGT-QG, and its indexing time is comparable with HNSWlib.Source: §4.2.1 · p. 11, Table 3 · p. 11, §4.2.3 · p. 12
• Removing multiple estimated distances or graph refinement reduces query performance; without refinement, vertex out-degrees are not aligned with FastScan’s batch size.With refinement, each vertex’s out-degree is guaranteed to be 32.Source: §4.2.3 · p. 12, Table 5 · p. 13

4.2.4 Parameter Study.

• Search performance remains stable from three graph-construction iterations onward on two datasets, motivating a default of three or four iterations.Figure 9 reports QPS at 95% recall for K=10 across iteration counts.Source: Figure 9 · p. 13, §4.2.4 · p. 13

5 RELATED WORK

• ANN methods are grouped into graph-based, quantization-based, hashing-based, and tree-based approaches, with graph methods offering state-of-the-art time-accuracy trade-offs on real-world datasets.Quantization estimates distances from compressed codes; hashing offers theoretical guarantees but often struggles with high practical recall and efficiency, while trees suffer in high dimensions.Source: §5 · p. 13
• Prior work optimizes graph structure, distance computation, memory footprint, and index construction, while SymphonyQG targets tighter integration of quantization and graph indices.The paper leaves applying or adapting those optimization techniques to SymphonyQG as future work.Source: §5 · p. 13
• The library focuses on Euclidean ANN, including Euclidean distance and cosine similarity; adapting its ideas to other similarity-search tasks is outside this paper’s scope.The authors note that such development involves non-trivial challenges and workloads.Source: §5 · p. 13

6 CONCLUSION AND DISCUSSION

• SymphonyQG establishes a new state-of-the-art time-accuracy trade-off and significantly speeds up index construction.Its approach combines RaBitQ, multiple estimated distances during graph search, and a graph structure refined for FastScan's in-batch computations.Source: §6 · p. 13
• SymphonyQG stores duplicated quantization codes, increasing space consumption and potentially making it unsuitable for memory-limited scenarios.The paper names cloud functions as an example of such a scenario.Source: §6 · p. 13
• RaBitQ limits SymphonyQG to Euclidean distance and cosine similarity; the paper identifies extending techniques to other metrics as future work.The conclusion also notes that compression, such as dimension reduction, can reduce memory consumption.Source: §6 · pp. 13–14

A INDEXING PARAMETERS FOR DIFFERENT METHODS

• Parameters were selected for different methods to maximize QPS at 95% recall with K=10.The appendix says the settings are presented in Table 6.Source: A INDEXING PARAMETERS FOR DIFFERENT… · p. 17, Table 6 · p. 17
• For SymQG, OG-LVQ, Glass-NSG, and HNSWlib, the appendix omits the common EF=400 parameter.For NGT-QG, it shows only the chosen index's group name and refers readers to ANN-Benchmark for details.Source: A INDEXING PARAMETERS FOR DIFFERENT… · p. 17

B ABLATION STUDY OF PROPOSED TECHNIQUES

• SymQG surpasses SymQG(w/o ME) and SymQG(w/o GR) on all six tested datasets with different settings.The appendix presents the ablation study in Figure 10.Source: B ABLATION STUDY OF PROPOSED TECHNIQUES · p. 17, Figure 10 · p. 17
• The ablation varies EF, R, and K to test the techniques' performance gain and generality.The comparison includes SymQG and the variants without multiple estimated distances (ME) or graph refinement (GR).Source: B ABLATION STUDY OF PROPOSED TECHNIQUES · p. 17
• The study's base setting uses R=32 and EF=400 for indexing and K=10 for searching.These are the settings specified for the initial effectiveness study in Section 4.2.3.Source: B ABLATION STUDY OF PROPOSED TECHNIQUES · p. 17