What is a cache miss?

A cache miss is what happens when the processor needs a piece of data that is not already present in the CPU cache, forcing it to fetch a full cache line from a slower level of the memory hierarchy — another cache level, or ultimately main memory — before the requested work can continue.

What actually unfolds inside the processor when a miss occurs?

On every memory access the core checks the nearest cache level first. If the needed bytes are already there, the access is a hit and the instruction pipeline keeps moving. If they are not, that access is a miss: the hardware must locate the correct cache line farther away, bring it into the nearer cache, and only then satisfy the original request. Misses are usually described by which level failed — an L1 miss that still hits in L2 is far cheaper than an L3 miss that has to go all the way to RAM — but in every case the core either stalls or switches to other work while it waits. Because caches transfer whole lines rather than single bytes, a miss always pays for an entire line even when the program only needed a few of those bytes, which is why scattered access patterns amplify miss cost so harshly.

That stall-or-wait cost is exactly why HNSW query latency is so sensitive to how the graph and its vectors are laid out in memory.

Why do HNSW graph hops produce so many expensive misses?

Upper-layer descent and base-layer exploration both walk neighbor lists by jumping from node ID to node ID. Each hop typically touches a small amount of useful data — an ID, a distance, a short stretch of a neighbor array — then leaps to a completely different region of the index for the next candidate. Those jumps defeat the cache’s assumption that the next useful bytes are nearby, so many hops miss in L1 and often in L2 as well, waiting on outer cache or main memory even when the arithmetic per hop is trivial. Distance calculations on a single vector, by contrast, walk dimensions in order once the first line is present, so after the opening miss the rest of that vector tends to hit. The asymmetry is structural: HNSW‘s graph navigation is miss-heavy by nature, while its vector arithmetic is miss-light once each vector has been pulled in.

Cold starts and capacity pressure make the same miss machinery show up in benchmarks and production in ways that are easy to misread as algorithmic slowdowns.

How do cold caches and capacity misses change what you measure?

A cold cache — right after process start, after a large unrelated workload displaced the working set, or on the first queries against a freshly loaded index — has almost nothing useful cached yet, so the early searches pay a burst of compulsory misses while lines fill. Later queries that revisit hot entry regions, popular hubs, or recently touched vectors see far fewer misses and look much faster, which is why cold-cache and warm-cache benchmark numbers can disagree dramatically for the same index and parameters. Capacity misses are different: the working set is simply larger than the cache can hold, so even a warm run keeps evicting useful lines to make room for new ones. Large HNSW indexes routinely outgrow L3, which means a steady background of capacity misses on random graph hops is normal, not a sign that something is broken — though a pathological layout can make that background far worse than it needs to be.

Production systems that keep vectors in an explicit software cache on top of RAM, as Weaviate does with its configurable vector cache for HNSW, are managing a related miss problem one level higher: a miss there falls through to disk-backed storage rather than only to main memory, which is orders of magnitude more expensive still.

What should you do when cache misses dominate HNSW latency?

When profiling shows the core stalled on memory rather than busy computing distances, the levers are layout and reuse, not more arithmetic optimization. Packing neighbor IDs into tight contiguous arrays, keeping each node’s hot fields together, aligning vectors so sequential distance loops consume whole lines, and reducing pointless pointer chasing all cut how many misses a search incurs and how much of each missed line is wasted. Raising efSearch explores more of the graph and usually increases miss traffic; lowering it does the opposite at the cost of recall — so miss-driven latency and accuracy tuning are coupled. On machines where the index barely fits in RAM, ensuring the OS page cache and any application-level vector cache stay warm for the hot working set matters as much as micro-optimizing the distance kernel.

A cache miss is the moment the memory hierarchy stops being invisible and starts dominating HNSW’s wall-clock time. From here, the pages on cache lines and CPU caches supply the hardware units behind every miss, locality of reference explains the access-pattern idea the cache is betting on, main-memory latency covers what a miss to RAM actually costs, and the chapter on laying out HNSW’s data structures in memory shows how to design the index so fewer searches pay that cost.