How do distance calculations and CPU optimization affect HNSW’s speed?

Distance calculations and CPU optimization affect HNSW’s speed directly because every single step of graph traversal, at both construction and query time, requires computing a distance between the current vector and one of its candidate neighbors — a search that visits a few hundred nodes performs a few hundred of these calculations, and how fast each one runs sets a hard floor under how fast the entire search can possibly go, no matter how good the graph structure itself is.

Why do distance calculations dominate search time in the first place?

Every hop the search takes, every candidate it considers, and every neighbor it evaluates during construction requires a fresh distance computation between two vectors, and each of those computations touches every dimension of both vectors involved. For high-dimensional embeddings — hundreds or thousands of numbers per vector — this per-comparison cost is far from trivial, and it gets paid repeatedly throughout a single search rather than once. A graph traversal algorithm that’s structurally efficient can still end up slow in practice if the underlying distance calculation it depends on hasn’t been optimized, since the graph’s efficiency only reduces how many comparisons are needed, not how expensive each individual comparison is.

How does SIMD speed up a single distance calculation?

Modern CPUs can perform the same arithmetic operation on several numbers simultaneously using a capability generally called SIMD, short for applying a single instruction to multiple pieces of data at once. A straightforward, scalar implementation of a distance calculation processes one dimension at a time in a loop; a version written to take advantage of SIMD instead processes several dimensions per instruction, which can produce a meaningful speedup for exactly the kind of repetitive, uniform arithmetic that computing a distance across many dimensions actually is. This optimization applies whether the underlying metric is Euclidean distance, inner product, or cosine similarity computed via a normalized inner product, since all of them boil down to the same basic pattern of multiplying and accumulating values across corresponding dimensions of two vectors.

Does reducing numeric precision actually help, and what does it cost?

Storing and computing with lower-precision numbers — a compact 16-bit floating-point format instead of the usual 32-bit one, or an even more compact 8-bit integer representation — reduces both the memory a vector occupies and the amount of data that has to move through the CPU’s memory hierarchy to compute a distance, which speeds up exactly the kind of memory-bound workload distance calculations often are. The cost is a small amount of numerical accuracy in every individual distance computation, since lower-precision numbers simply can’t represent values as exactly as higher-precision ones. In practice, this loss is frequently acceptable for approximate nearest-neighbor search specifically, because the search is already tolerating some approximation by design, and small errors in individual distance calculations tend to average out rather than systematically distorting which candidates end up ranked as closest.

How do you tell whether a distance-calculation bottleneck is about compute or about memory?

Two very different problems can both show up as “distance calculations are slow,” and they call for different fixes. A compute-bound bottleneck means the CPU’s arithmetic units are the limiting factor, and it responds well to SIMD and to batching multiple distance calculations together so the CPU can pipeline its work more efficiently. A memory-bound bottleneck means the CPU is spending most of its time waiting for vector data to arrive from memory rather than actually computing anything, and it responds better to reduced-precision storage and to prefetching — deliberately requesting the next piece of data before it’s actually needed, so it has time to arrive before the CPU is ready for it. Distinguishing between these two situations, rather than assuming one particular optimization will always help, is what separates a targeted performance fix from a change that adds complexity without actually addressing the real bottleneck.

Fast distance calculations only help if a system can also serve many of them at once, which is exactly the concurrency picture the next page turns to — how HNSW behaves when multiple threads read from and write to the same graph simultaneously. For the underlying vocabulary used throughout this page, including what a cache line and memory bandwidth actually are, this site’s systems-and-hardware glossary section has a dedicated page for each term.