What is locality of reference?

Locality of reference is the tendency of a program to reuse the same memory locations again soon, or to touch addresses near ones it just used — the access-pattern assumption that makes CPU caches, cache lines, and TLBs worth building at all.

What are temporal locality and spatial locality, and how do they differ?

Temporal locality means that if a program touches a particular piece of data now, it is likely to touch that same piece again in the near future — a loop counter, a hot entry-point node, a query vector kept in registers or L1 while candidates are scored. Spatial locality means that if a program touches one address, it is likely to touch neighboring addresses soon after — walking the dimensions of a vector in order, or scanning a packed array of neighbor IDs. Hardware caches bet on both: they keep recently used lines hoping for temporal reuse, and they fetch whole cache lines hoping nearby bytes will be needed next. When a workload has strong locality, most accesses hit in cache and the memory hierarchy stays almost invisible. When a workload has weak locality, every clever cache in the machine still spends its time missing.

HNSW is interesting precisely because one algorithm mixes strong locality in one phase with weak locality in another.

Where does HNSW show strong locality, and where does it deliberately break it?

Distance calculation over a contiguous vector is a textbook spatial-locality win: once the first cache line arrives, the loop streams through neighboring dimensions with high hit rates and friendly prefetching. Temporal locality appears when the same query vector is reused across many candidate comparisons, when a search revisits a small set of frontier nodes, or when repeated queries share popular hub regions near common entry points. Graph hops break spatial locality on purpose in the algorithmic sense — the next useful neighbor is chosen by distance in embedding space, not by adjacency in memory — so successive loads jump across the index with little relationship between consecutive physical addresses. That is not a bug in the implementation; it is the cost of navigating a proximity graph. The engineering question is how much locality you can restore around those hops without changing what the graph means.

Restoring locality is mostly about layout, working-set size, and how much of the graph a single query is allowed to touch.

How do memory layout and search parameters change HNSW’s effective locality?

Packing each node’s neighbor IDs into a tight contiguous array improves spatial locality for the scan of one neighbor list, even though the jump to the next node remains random. Storing vectors in dense, aligned blocks does the same for distance loops. Keeping related metadata together so one cache line carries more than one useful field raises the payoff of every miss. On the parameter side, a small efSearch keeps the working set of candidates and visited nodes smaller, which improves temporal locality inside the caches and TLB; a large efSearch explores more of the graph, touches more pages, and dilutes reuse. Construction with a large efConstruction builds a richer graph but also performs more miss-heavy searches during the build. None of these knobs create locality that is not there in the access pattern — they only decide how much scattered work you ask the memory system to absorb per operation.

Production systems also see locality across queries, not only inside one search, which is why warm caches and skewed traffic matter.

Why do repeated queries and hot regions create locality that a single random query does not?

Real workloads are rarely uniformly random. Many queries land near the same popular regions of the embedding space, share entry-point neighborhoods, or repeatedly retrieve overlapping candidate sets. That cross-query temporal locality leaves hub nodes, common neighbor lists, and frequently compared vectors resident in cache and in the OS page cache long after any one search ends. Cold, one-off, or adversarially scattered queries see none of that reuse and pay full miss costs. In-memory vector databases such as Weaviate rely on keeping the HNSW index in RAM so disk stays out of the path, but the CPU cache and TLB still only help to the extent successive work reuses the same lines and pages. Benchmarks that flush state between queries measure a low-locality lower bound; benchmarks that stream realistic traffic measure the locality the deployment will actually get.

Locality of reference is the access-pattern idea behind every cache benefit HNSW enjoys and every miss it pays for. From here, the pages on CPU caches, cache lines, and cache misses show how hardware exploits or suffers those patterns, pointer chasing names the dependent jumps that destroy spatial locality on graph hops, and the chapter on laying out HNSW’s data structures in memory shows how to give the hardware as much locality as the algorithm will allow.