What are distance computations per query?

Distance computations per query is a work metric: the number of times a search evaluates the distance or similarity function between the query vector and a candidate vector while answering one request — the dominant arithmetic cost inside HNSW and most other ANN indexes.
Created: Updated: 5 min read

Distance computations per query is a work metric: the number of times a search evaluates the distance or similarity function between the query vector and a candidate vector while answering one request — the dominant arithmetic cost inside HNSW and most other ANN indexes.

Why count distance calls instead of only timing the query?

Wall-clock latency mixes algorithm work with caches, locks, network, and object fetch. Two machines can report different milliseconds for the same walk. Counting how many times the distance kernel runs isolates the algorithmic effort: a brute-force scan of one million vectors performs about one million distance computations; an HNSW search that reaches the same recall with a few thousand computations is doing far less work. That count also explains scaling: each computation costs work proportional to dimensionality (and to how the metric is implemented), so raising dimensions or switching from a cheap quantized estimate to a full float32 distance changes cost even when the hop count is unchanged. Researchers and implementers use distance-computation curves alongside recall because they travel better across hardware than raw QPS alone.

On graph indexes, those calls happen every time the walk scores a neighbor.

Search maintains a candidate set and repeatedly expands the most promising nodes. Each time a neighbor ID is considered, the engine typically computes distance from the query to that neighbor’s vector (unless a cache already holds it for this query). Upper layers use a greedy walk with relatively few comparisons; the base layer widens into a best-first search whose dynamic list size is controlled by ef (and by k / limit). Larger ef keeps more candidates alive longer, visits more edges, and therefore executes more distance computations — usually buying recall at the expense of latency and QPS. Build-time parameters such as efConstruction and maxConnections shape how many edges exist to examine later, so they influence query-time computation counts indirectly. Filtered search can add computations on nodes that fail predicates, or switch to a flat scan over an allow-list when the candidate set is small — both change the distance-computation profile versus an unfiltered walk.

In production profiles, that kernel often dominates CPU.

Why do distance computations dominate vector-database CPU time?

Even after ANN pruning removes most of the corpus, the remaining comparisons are dense linear algebra over hundreds or thousands of dimensions. On HNSW workloads, profiling commonly attributes on the order of half of CPU time to distance evaluation. That is why SIMD implementations, careful memory layout, and quantization matter: they do not remove the need to compare vectors, but they make each comparison cheaper or let you afford more comparisons in the same budget. Rotational or scalar quantization can flip the trade: slightly weaker per-comparison fidelity, but enough extra candidates examined (higher effective search depth for the same milliseconds) that recall and throughput both improve. Rescoring after a quantized pass adds a second wave of exact distances on a shortlist — fewer than the ANN phase, but still part of the per-query total.

Weaviate exposes the same trade-off through ef, metrics, and compression.

How does Weaviate relate configuration to distance work per query?

Raising query-time ef (or using dynamic ef tied to limit, min/max, and factor) enlarges the search list and increases thoroughness — and with it the expected number of distance evaluations. Distance metric choice (cosine, dot, L2-squared, and others) changes both what “nearest” means and how expensive each kernel call is; SIMD paths exist for the common metrics on major CPU architectures. Official guidance notes that even with an ANN index, distance calculation remains a major share of overall performance, which is why compression and assembly-level kernels show up in release write-ups as QPS and latency wins. When you tune for a recall target, you are often implicitly choosing a distance-computation budget: the lowest ef (and cheapest compression mode) that still meets recall minimizes work per query and frees headroom for QPS.

Treat the metric as a diagnostic when latency moves unexpectedly.

How should you use distance computations when benchmarking?

If you can instrument or log them, plot recall versus mean distance computations per query while sweeping ef — that curve is the algorithmic twin of recall-versus-latency. Compare flat search (roughly one computation per object in the scanned set) against HNSW on the same corpus to quantify pruning. When p99 jumps without a parameter change, check whether filters, hybrid second arms, or rescoring suddenly inflated computation counts. Do not chase a lower count by starving ef below your recall SLA; wasted-looking computations that recover true neighbors are cheaper than fast wrong answers. Report dimensionality and metric with the count so others can interpret the arithmetic intensity.

Distance computations per query measure how hard the index worked to rank candidates — the main lever behind HNSW’s recall–speed trade-off. Next, read “What is build time, in benchmarking?” for the construction-side cost of parameters that later reduce query-time distance work, then “What is peak build RAM?” so memory during indexing sits beside query compute when you choose a configuration.