PaperlayerView exact revision on arXiv

Source-linked AI summary

Distance Comparison Operations Are Not Silver Bullets in Vector Similarity Search: A Benchmark Study on Their Merits and Limits

Zhuanglin Zheng, Yuxiang Zeng, Chenchen Liu, Yunzhen Chi, Binhan Yang, Yongxin Tong

arXiv:2604.02801v1cs.DB

TL;DR

Whether recent DCO algorithms are ready for production vector databases remains unresolved, motivating a comprehensive benchmark across methods, datasets, and hardware. The study finds that their efficiency is conditional rather than universal, with performance affected by dimensionality, query distribution, and hardware.

  • Problem

    Whether recent DCO algorithms are production-ready remains unresolved because prior evaluations used restricted settings.

    Source: §I · p. 1

  • Method

    The paper benchmarks eight DCO methods across ten diverse datasets and hardware configurations.

    Source: §I · p. 1

  • Results

    DCO methods have no universal efficiency advantage: performance depends on dimensionality, OOD queries, and hardware, and can be worse than naive baselines.

    Source: §I · p. 1, §VII · p. 12

  • Takeaways & Limitations

    Method selection should account for dimensionality, hardware, and query distribution; simple scanning methods often perform well for OOD queries and some dimensionality ranges.

    Source: G. Summary: Recommendations, Merits,… · p. 11

    The optimal DCO varies by setting: high-dimensional in-distribution data favor different methods across CPU HNSW and GPU IVF configurations.

    Source: G. Summary: Recommendations, Merits,… · p. 11

Abstract

from arXiv · show

Distance Comparison Operations (DCOs), which decide whether the distance between a data vector and a query is within a threshold, are a critical performance bottleneck in vector similarity search. Recent DCO methods that avoid full-dimensional distance computations promise significant speedups, but their readiness for production vector database systems remains an open question. To address this, we conduct a comprehensive benchmark of 8 DCO algorithms across 10 datasets (with up to 100M vectors and 12,288 dimensions) and diverse hardware configurations (CPUs with/without SIMD, and GPUs). Our study reveals that these methods are not silver bullets: their efficiency is highly sensitive to data dimensionality, degrades under out-of-distribution queries, and is unstable across hardware. Yet, our evaluation also demonstrates often-overlooked merits: they can accelerate index construction and data updates. Despite these benefits, their unstable performance, which can be slower than a full-dimensional scan, leads us to conclude that recent algorithmic advancements in DCO are not yet ready for production deployment.

I. INTRODUCTION

The introduction presents DCOs as an operator-level approach to vector-search efficiency, while asking whether recent methods are ready for production. It motivates a broader benchmark because prior evaluations left important data, hardware, and query settings uncovered.

II. PRELIMINARY

  • A DCO tests whether a data vector’s distance from a query is within a threshold; prior methods report 2–4× throughput over full-dimensional scanning with almost no recall loss.Methods use hypothesis testing or prediction to scan partial dimensions and infer the comparison result.Source: §I · p. 1, §II · p. 2

I. INTRODUCTION

  • Prior evaluations were narrow in dimensionality, lacked direct comparisons, often disabled SIMD, and focused mainly on in-distribution queries.Source: §I · p. 1
  • The study benchmarks eight DCO methods across ten datasets and diverse hardware, then derives scenario-specific selection guidance.It also identifies future research directions and open-sources the benchmark.Source: §I · pp. 1–2
  • DCO performance varies with dimensionality, query distribution, and hardware; methods can fall behind full-dimensional scanning, and no single method dominates.Outside moderate dimensionality, advantages can degrade by up to 20%–42%; OOD queries and SIMD can also reduce or reverse gains.Source: §I · p. 1
  • DCO methods can accelerate index construction by up to 64% and data insertions by up to 63%.Source: §I · p. 1

A. Basic Concepts

  • Vector data are ordered coordinate sequences, and similarity search seeks the k nearest neighbors to a query from a dataset of N vectors with D dimensions.Source: A. Basic Concepts · p. 2

B. Definition of Distance Comparison Operation

A Distance Comparison Operation (DCO) tests whether a vector’s distance to a query is within a threshold, returning the exact distance only when the test is true. Existing methods are grouped into simple-scanning, hypothesis-testing, and classification-based approaches.

B. Definition of Distance Comparison Operation

  • A DCO tests whether dis(o, q) ≤ τ and returns the exact distance when true, but only false otherwise.The paper notes that most DCOs return false, so exact distance calculation is needed for only a small subset.Source: B. Definition of Distance Comparison… · p. 2

A. Method Taxonomy

  • Existing optimization algorithms fall into simple-scanning, hypothesis-testing, and classification-based categories.The taxonomy treats these algorithms as complementary to GPU and SIMD hardware accelerators.Source: A. Method Taxonomy · p. 3, Figure 2 · p. 3, §III · p. 3

B. Simple Scanning Based Method

  • Simple-scanning methods include FDScanning, which scans all dimensions, and PDScanning, which stops when the partial distance proves dis(o, q) > τ.PDScanning therefore avoids computation on the remaining dimensions for rejected comparisons.Source: B. Simple Scanning Based Method · p. 3
  • SIMD processes multiple dimensions in a batch, while PCA-based PDScanning+ orders dimensions by variance and preserves Euclidean distances.The PCA transformation rotates the vector space rather than reducing its dimensionality.Source: B. Simple Scanning Based Method · p. 3

C. Hypothesis Testing Based Method

Hypothesis-testing DCO methods estimate the full distance from partial dimensions and test whether it exceeds the threshold. They use residual-distance or cross-term estimators, with methods differing in their assumptions and supported distance measures.

C. Hypothesis Testing Based Method

  • Hypothesis-testing methods estimate the full distance from a partial distance, then use a probability inequality to test whether dis(o, q) ≤ τ.They can terminate early when the estimated distance exceeds a statistically derived error bound.Source: C. Hypothesis Testing Based Method · pp. 4–5
  • Residual-distance estimators either scale partial distance under equal per-dimension contributions or use PCA to prioritize dimensions with differing contributions.ADSampling uses a random projection and provides an error bound; DADE uses PCA loadings and supports differently weighted dimensions.Source: C. Hypothesis Testing Based Method · p. 4
  • The cross-term strategy computes norms and the scanned-dimension inner product, then estimates the remaining cross-term.DDCres centers vectors and assumes query and data vectors follow a Gaussian distribution; PCA is used to tighten its lower bound.Source: C. Hypothesis Testing Based Method · p. 4
  • Hypothesis-testing methods can extend to inner product and cosine similarity after the vector dataset is normalized.For normalized vectors, cosine similarity is equivalent to the inner product.Source: C. Hypothesis Testing Based Method · p. 5

D. Classification Based Method

Classification-based DCO methods predict whether the full distance exceeds the threshold using models trained from sampled queries and a known query workload. DDCopq instead uses product-quantization-derived approximate distances and verifies negative predictions with a full scan.

D. Classification Based Method

  • Classification-based methods predict whether dis(o, q) ≤ τ from the partial distance and threshold, typically assuming the query workload is known in advance.Sampled queries and a fixed vector index generate training samples for separate linear models indexed by query parameter k and scanned dimensions d.Source: D. Classification Based Method · p. 5
  • DDCopq trains one linear model per query parameter k using product-quantization-derived approximate distances, then verifies negative predictions with a full-dimensional scan.This differs from DDCpca’s models for combinations of k and scanned dimensions.Source: D. Classification Based Method · p. 5

E. Summary

The comparison distinguishes methods by exactness, assumptions, and time-complexity accounting. Their applicability depends on metric, distribution, query-parameter, and index requirements.

E. Summary

  • Simple-scanning algorithms are exact, while the other methods trade slight accuracy for efficiency; DADE alone provides an unbiased distance estimator.Source: E. Summary · p. 5
  • Most methods are limited to Euclidean or transformable metrics, and several assume matching query and data distributions; classification methods require prior k and a specific index.DDCres further assumes a Gaussian distribution, while PDScanning and PDScanning+ also support monotonic distances.Source: E. Summary · p. 5
  • Only FDScanning, PDScanning, and ADSampling provide explicit time-complexity analyses, and online preprocessing can dominate at sufficiently high dimensions.The analysis identifies an omitted O(D^2) query-projection cost in ADSampling and includes offline preprocessing such as PCA computation and model training.Source: E. Summary · p. 5

IV. BENCHMARK SETUP

The benchmark evaluates DCO methods across varied datasets, workloads, indexes, and hardware. It implements eight methods in a unified framework and tests them under multiple query and data conditions.

A. Overview

  • The benchmark covers query processing, OOD queries, three distance metrics, index construction, dynamic updates, and varied hardware.It evaluates HNSW and IVF and includes CPU and GPU configurations.Source: A. Overview · pp. 5–6

B. Dataset and Query Workload

  • Ten public datasets vary in dimensions, sizes, and raw data types; Laion and Text2Image provide OOD queries through image–text distribution shifts.XUltra is a synthetic 12,288-dimensional dataset built by concatenating MSMARCO token embeddings.Source: B. Dataset and Query Workload · p. 6

C. Compared DCO Algorithms and Their Implementations

  • Eight DCO methods are implemented from scratch in a unified framework, including three baselines and five state-of-the-art methods.The methods are FDScanning, PDScanning, PDScanning+, ADSampling, DADE, DDCres, DDCpca, and DDCopq.Source: C. Compared DCO Algorithms and Their… · p. 6
  • Implementations compare HNSW on CPUs with IVF on GPUs, with CPU variants tested both with and without SIMD.All methods use identical data layouts; GPU IVF is preloaded into device memory, and online query processing is written in C++.Source: C. Compared DCO Algorithms and Their… · p. 6

D. Parameter Setting

Across the reported query-processing results, DCO methods improve throughput in some settings but do not consistently outperform FDScanning. Their performance depends on dimensionality, and pruning can preserve recall while still failing to deliver a speedup.

D. Parameter Setting

  • Search settings use HNSW efSearch from 100 to 1500, IVF nprobe from 20 to 400, and k values of 20 and 100.Defaults are efSearch = 200 and nprobe = 80; HNSW uses M = 16 and efConstruction = 500, while IVF uses 4096 partitions.Source: D. Parameter Setting · pp. 6–7

E. Evaluation Metric

  • Evaluation measures recall, QPS, dimension-pruning ratio, and index-construction and insertion time; QPS–recall curves vary search parameters that trade throughput for recall.Increasing efSearch or nprobe raises recall while decreasing QPS.Source: E. Evaluation Metric · p. 7

F. Experimental Environment

  • Experiments run on an AMD Ryzen 9 5950X server with 128GB RAM and an NVIDIA GeForce RTX 3090 GPU.The system ran Ubuntu 24.04.2 with CUDA 12.4.Source: F. Experimental Environment · p. 7

A. Query Processing

  • Only 4 of 14 subfigures show hypothesis-testing and classification methods consistently outperforming FDScanning; their QPS gains reach 1.4–1.9× and 1.6–2.1×, respectively, with recall changing by at most 2%.The comparison is reported for hypothesis-testing methods and DDCpca/DDCopq against FDScanning.Source: A. Query Processing · p. 7, Figure 4 · p. 7
  • On Deep and Trevi, baseline methods can outperform state-of-the-art methods; skipped dimensions on Deep save only marginal time, while Trevi's online preprocessing can bottleneck performance.On Trevi, preprocessing costs are not effectively amortized before recall reaches 94%.Source: A. Query Processing · pp. 7–8
  • On XUltra, FDScanning and PDScanning exceed all state-of-the-art methods in QPS, whose QPS falls by up to 77%–79%× relative to FDScanning.The result holds for both tested k values on the highest-dimensional dataset.Source: A. Query Processing · p. 8, Figure 5 · p. 8
  • DCO pruning varies with dimensionality and method, while all methods maintain comparable recall, indicating minor approximation errors do not compromise recall.DDCopq has the highest pruning ratio on Deep and GIST; DDCres performs best on the higher-dimensional dataset.Source: A. Query Processing · p. 8, Figure 6 · p. 8

B. Out-of-Distribution (OOD) Queries

On OOD queries, DCO methods often lose their efficiency advantage over FDScanning, while results for inner product resemble Euclidean-distance results but remain dataset-dependent. DCOs can also accelerate index construction while maintaining near-identical search performance.

B. Out-of-Distribution (OOD) Queries

  • On OOD queries, FDScanning and PDScanning outperform most state-of-the-art methods; DDCpca shifts from up to 1.5× higher QPS in-distribution to up to 1.6× slower than FDScanning.Most methods' pruning ratios drop by over 60% on OOD queries; DDCopq leads QPS on Laion with over 95% prediction accuracy.Source: B. Out-of-Distribution (OOD) Queries · p. 8, Figure 8 · p. 9

C. Beyond Euclidean Distance

  • For inner product, DADE, DDCres, DDCpca, and DDCopq improve QPS by up to 1.3–1.7× on OpenAI, but FDScanning leads on GloVe and XUltra.Most methods convert inner product to Euclidean distance; online preprocessing remains a bottleneck, and similar trends are reported for cosine similarity.Source: C. Beyond Euclidean Distance · p. 9

D. Index Construction

  • Using fixed FDScanning query processing for fair comparison, all DCO-built indexes achieve nearly identical average recall and QPS across datasets, with recall gaps to FDScanning no more than 0.1%.On high-dimensional GIST and OpenAI, DDCres reduces index construction time by up to 39%.Source: D. Index Construction · p. 9, Figure 9 · p. 9

E. Robustness on Dynamic Data

DCO performance depends on dimensionality, query distribution, and hardware, so method selection is scenario-specific. The benchmark also finds benefits for dynamic updates alongside important performance limits.

E. Robustness on Dynamic Data

  • During incremental GIST insertions into HNSW, DDCres QPS falls by up to 11%, while it reduces total update time by up to 39%.Recall declines for all methods as the dataset grows, while ADSampling QPS remains relatively stable.Source: E. Robustness on Dynamic Data · p. 10
  • With only 1% of the full dataset for training, PDScanning+, DADE, and DDCres prune effectively, while DDCopq and DDCpca need at least 5% for stable recall and pruning.DDCopq and DDCpca also require at least 10,000 training vectors.Source: E. Robustness on Dynamic Data · p. 10

F. Diversified Hardware Condition

  • On SIFT, enabling CPU SIMD changes DDCopq from the least efficient method to the most efficient; SIMD also narrows DCO speedups over FDScanning on IVF and HNSW.For IVF, the speedup range drops from 2.0–4.4× to 1.2–3.8×; for HNSW, it drops from 1.9–3.1× to 1.1–2.1×.Source: F. Diversified Hardware Condition · pp. 10–11

G. Summary: Recommendations, Merits, and Limitations

  • For in-distribution queries, the best choice shifts with dimensionality and index: DDCpca often leads on high-dimensional HNSW/CPU, while DDCres often leads on high-dimensional IVF/GPU.Simple scanning methods often outperform alternatives for OOD queries and on low- or ultra-high-dimensional in-distribution data.Source: G. Summary: Recommendations, Merits,… · p. 11
  • On HNSW with CPU SIMD, PDScanning+, ADSampling, DADE, DDCres, DDCpca, and DDCopq improve QPS by up to 1.9, 1.4, 1.8, 1.9, 2.1, and 1.6×, respectively.On IVF, GPU gains over CPU without SIMD reach 3.0–4.3×, but fall to roughly 1.1–2.2× against CPU with SIMD.Source: F. Diversified Hardware Condition · p. 11, G. Summary: Recommendations, Merits,… · p. 12
  • Most DCO methods preserve the underlying index's native recall, with hypothesis-testing methods usually varying by less than 2%.Several methods also accelerate index building and data insertion; DCOs can be adapted to inner product and cosine similarity while maintaining recall.Source: G. Summary: Recommendations, Merits,… · p. 12
  • On low- and ultra-high-dimensional datasets, most SOTA methods are slower than simple-scanning baselines, with QPS reductions up to 8%–42% and 77%–79%, respectively.On multimodal OOD datasets, FDScanning can also outperform several SOTA methods.Source: G. Summary: Recommendations, Merits,… · p. 12
  • DCO gains vary with hardware, and methods such as DDCpca also rely on restrictive assumptions about workload, training data, and distance metrics.DDCpca requires prior knowledge of the query workload and parameter k, sufficient training data, and is primarily designed for Euclidean and inner-product distances.Source: G. Summary: Recommendations, Merits,… · p. 12

VI. RELATED WORK

Prior vector-search research has emphasized index structures, while this paper benchmarks the underlying distance comparison operation across broader settings. It concludes that current DCO methods have scenario-dependent limits and identifies directions for improving their generality and robustness.

VI. RELATED WORK

  • Vector similarity search spans exact and approximate approaches, with graph-, partition-, and hash-based indexes among the common structures.Graph and partition-based indexes are described as widely adopted in production vector databases and search engines.Source: §VI · p. 12
  • This work shifts attention from index structures to DCOs, one of several distance operations involved in indexed query processing.Related DCO methods include FDScanning, PDScanning, PCA-prioritized PDScanning+, and hypothesis-testing or classification-based approaches.Source: §VI · p. 12

VII. CONCLUSION AND FUTURE DIRECTION

  • Across eight SOTA methods and ten datasets, the benchmark finds no silver bullet: methods can increase latency for OOD queries and low- or ultra-high-dimensional datasets.Source: §VII · p. 12
  • Future work directions include specialized methods for low- or ultra-high-dimensional data, greater OOD robustness, hardware-aware design, and broader metrics and assumptions.Source: §VII · p. 12

APPENDIX A DETAILED IMPLEMENTATION

The appendix details a unified implementation and tests DCO query performance across CPU SIMD settings, query distributions, similarity metrics, and hardware. Results vary by setting: SIMD can narrow DCO advantages, OOD queries can reverse them, and GPU performance differs from CPU performance.

APPENDIX A DETAILED IMPLEMENTATION

  • The unified framework keeps each algorithm on the same search framework, index layout, and sequential independent batch-query protocol, with online processing in C++.For HNSW, SIMD distance routines come from Hnswlib; for GPU IVF, one CUDA kernel runs per partition with one candidate vector per thread.Source: Appendix A · p. 15

APPENDIX B QUERY PROCESSING VIA HNSW ON CPUS WITH SIMD

  • With SIMD disabled, hypothesis-testing methods improve QPS by up to 1.9–2.5× and classification methods by 2.1–3.1× over FDScanning on HNSW.SIMD accelerates distance computation but not termination-decision overhead, diluting DCOs’ relative benefit when SIMD is active; PDScanning can lead before 98% recall on some ultra-high-dimensional datasets because online preprocessing is also a bottleneck.Source: Appendix B · p. 15

INSTRUCTION SET

  • Under AVX2, performance trends resemble SSE: most DCO methods fail to beat FDScanning on low-dimensional GloVe, while FDScanning and PDScanning lead on Trevi until recall exceeds 98%.AVX2 typically speeds distance computation and diminishes DCOs’ relative speedup; FDScanning can surpass newer methods, including ADSampling on GIST.Source: INSTRUCTION SET · p. 15, Figure 18 · p. 17

APPENDIX D OUT-OF-DISTRIBUTION (OOD) QUERIES ON CPUS WITH

  • On OOD queries, DDCpca shifts from highest QPS in-distribution to least efficient, running up to 1.6× and 1.8× slower than FDScanning and PDScanning, respectively.For recall over 97%, PDScanning and PDScanning+ lead on both datasets, except DDCopq on Laion.Source: Appendix D · p. 16, Figure 19 · p. 17

APPENDIX E EXPERIMENT WITH COSINE SIMILARITY

  • For cosine similarity, low-dimensional DCO advantages are less pronounced and can lose to FDScanning, while online-preprocessing bottlenecks persist on ultra-high-dimensional Trevi.The reported pattern is attributed to cosine extensions derived from Euclidean methods and cosine’s equivalence to inner product for normalized vectors.Source: Appendix E · p. 16

ON XULTRA DATASET

  • On XUltra, DDCres improves QPS by up to 1.7× and 2.9× over FDScanning on CPUs with and without SIMD, respectively, and DCOs improve QPS by up to 1.4–5.6× over FDScanning on GPU.On CPU, PDScanning leads before recall reaches 89%; the CPU online-preprocessing bottleneck does not manifest on GPU.Source: ON XULTRA DATASET · pp. 16–17

APPENDIX G PRUNING CAPABILITY OF DCO UNDER THE IVF INDEX

The appendix examines DCO dimension pruning on IVF, parameter sensitivity, and query behavior under SIMD-disabled and AVX2 HNSW settings. Pruning and query-speed effects depend on dimensionality, index, and hardware, while some baselines outperform DCO methods in particular settings.

APPENDIX G PRUNING CAPABILITY OF DCO UNDER THE IVF INDEX

  • On IVF, higher DCO pruning ratios occur consistently on high- and ultra-high-dimensional datasets, but DDCopq’s quantized-distance overhead can undermine its query performance when SIMD is disabled.With SIMD enabled, DDCopq’s performance aligns more closely with its pruning capability; all methods maintain comparable recall.Source: Appendix G · p. 17

APPENDIX H PARAMETER STUDY

  • Jointly optimal ∆0 and ∆d settings boost QPS by up to 1.5× for ADSampling and 1.8× for DADE and DDCres over prior-work settings.Most algorithms are sensitive to ∆d; optimal values are 64, 96, or 160 for HNSW and 64 for IVF, and tuning ∆0 gains more on cache-friendly IVF than HNSW.Source: Appendix H · p. 18

APPENDIX I DETAILED IMPLEMENTATION

  • The implementation appendix describes a common framework and index layout, sequential independent query processing, and C++ online processing across the compared methods.The GPU IVF setup preloads the index in device memory and assigns each thread one candidate vector within a per-partition CUDA kernel.Source: Appendix I · p. 19

APPENDIX J QUERY PROCESSING VIA HNSW ON CPUS WITH SIMD

  • With SIMD disabled on HNSW, hypothesis-testing methods improve QPS by up to 1.9–2.5× and classification methods by 2.1–3.1× over FDScanning.PDScanning can nevertheless lead before 98% recall on some ultra-high-dimensional datasets, where online preprocessing is a bottleneck; enabling SIMD narrows DCO speedups to 1.1–2.1×.Source: Appendix J · p. 20

APPENDIX K QUERY PROCESSING VIA HNSW WITH AVX2 SIMD

  • With AVX2 on HNSW, FDScanning and PDScanning lead on ultra-high-dimensional Trevi until recall exceeds 98%, and FDScanning can outperform ADSampling on GIST.The overall AVX2 trends are similar to SSE, including most DCO methods failing to outperform FDScanning on low-dimensional GloVe.Source: Appendix K · p. 20

APPENDIX M EXPERIMENT WITH COSINE SIMILARITY

The appendix tests cosine similarity, hardware variation, IVF pruning, and DCO parameter tuning. Across these experiments, DCO performance and pruning depend on dimensionality, hardware, index, and parameter choices.

APPENDIX M EXPERIMENT WITH COSINE SIMILARITY

  • For cosine similarity, low-dimensional DCO advantages are less pronounced and can lose to FDScanning, while online-preprocessing bottlenecks persist on ultra-high-dimensional Trevi.The reported pattern is attributed to cosine extensions derived from Euclidean methods and cosine’s equivalence to inner product for normalized vectors.Source: Appendix M · p. 20

ON XULTRA DATASET

  • On XUltra, DDCres improves QPS by up to 1.7× and 2.9× over FDScanning on CPUs with and without SIMD, respectively, and by up to 1.4–5.6× over FDScanning on GPU.PDScanning leads on CPU before 89% recall; the CPU preprocessing bottleneck does not manifest on GPU.Source: ON XULTRA DATASET · p. 20

APPENDIX O PRUNING CAPABILITY OF DCO UNDER THE IVF INDEX

  • On IVF, pruning ratios are higher on high- and ultra-high-dimensional datasets; DDCopq typically prunes most, but its query performance suffers when SIMD is disabled due to quantized-distance overhead.Pruning capability remains relatively stable on HNSW but increases with IVF nprobe, as IVF retrieves more distant candidates that can be rejected after scanning few dimensions.Source: Appendix O · pp. 20–21

APPENDIX P PARAMETER STUDY

  • Jointly optimal ∆0 and ∆d settings boost QPS by up to 1.5× for ADSampling and 1.8× for DADE and DDCres over prior-work settings.Optimal ∆d varies by index, and tuning ∆0 gains more on IVF than HNSW; optimal parameters depend on datasets, indexes, and DCO methods.Source: Appendix P · pp. 21–22

Related papers

Loading 2604.02801v1…