What is approximate distance computation?

Approximate distance computation is any scoring of how far a query is from a candidate that deliberately skips a full, exact metric evaluation – using compressed codes, reduced precision, lookup tables, or other shortcuts – so HNSW can rank neighbors fast enough to traverse the graph under tight latency and memory budgets.

How is approximate distance different from approximate nearest-neighbor search itself?

HNSW is already an approximate search algorithm: it does not compare the query to every vector in the collection, only to those along a greedy walk and beam. That approximation is about which candidates you score. Approximate distance computation is about how you score the ones you do touch. You might still visit the same nodes, but each comparison returns an estimate of L2, cosine, or inner product rather than the exact float32 result on full-precision coordinates. The two layers stack: graph search limits how many distances you compute; approximate kernels limit how expensive each of those computations is. Confusing them leads to mis-tuning – raising efSearch explores more of the graph, while changing quantizers changes the quality of every edge decision inside that exploration.

Those cheaper scores come from several concrete mechanisms that show up throughout compressed indexes.

What techniques turn an exact metric into a fast estimate?

Product quantization replaces subspaces with centroid IDs and estimates distance from codebook tables, often asymmetrically (float query versus codes). Scalar and int8 quantization map each dimension to a small alphabet and compare in integer or dequantized arithmetic. FP16 and BF16 keep floating values but with fewer bits, so the “approximation” is rounding rather than a learned codebook. Binary codes turn distance into Hamming-style bitwise work. Some pipelines use a cheap estimate to filter, then an exact distance only for survivors – that is approximate computation in the hot path plus full-precision reranking at the end. SIMD-friendly layouts and precomputed lookup tables are implementation details; the shared idea is trading a bounded amount of geometric fidelity for fewer bytes and fewer expensive floating operations per hop.

Because the beam trusts those scores, estimate error reshapes which path the search takes.

How do approximate distances change HNSW traversal behavior?

At each node, HNSW expands neighbors that look closest under the score it has. If estimates reorder two neighbors, the walk may expand the wrong branch first, or drop a true near neighbor from the candidate heap when efSearch is tight. Mild error often looks like a small recall dip fixable by a larger beam or a rescoring stage. Severe error – bad codebooks, mismatched metrics, or build-time exact distances paired with query-time coarse codes – can strand the search in the wrong region of the graph. Compression-aware construction tries to grow edges using the same approximate distances search will use, so the topology matches the scorer. Systems such as Weaviate that run quantized HNSW therefore treat distance estimation, over-fetch, and rescoring as one package rather than an afterthought bolted onto an uncompressed walk.

Operators still need a way to judge whether the estimates are good enough for the product.

How should you evaluate and tune approximate distance computation?

Compare recall and ranking correlation against an exact-distance baseline on the same candidate sets, not only end-to-end ANN recall – that separates “bad scorer” from “bad graph coverage.” Sweep efSearch and rescore depth after any quantizer change; the operating point that worked for float32 rarely transfers unchanged. Watch latency: a fancier estimate that saves little bandwidth is not a win. Keep query-side assumptions consistent (normalization, metric identity) with whatever the approximate kernel implements. Approximate distance computation is the numeric engine under modern compressed HNSW; tune it as carefully as M and efConstruction.

Approximate distance computation scores HNSW candidates with fast, inexact metrics so each graph hop stays cheap, at the cost of ranking noise you manage with beam width and reranking. From here, quantization error names what those estimates get wrong, full-precision reranking and two-stage retrieval show the usual correction pattern, scalar and product quantization detail the main estimators, and compression-aware graph construction covers building edges for the distances you will actually compute at query time.