What is a CPU cache?

A CPU cache is a small, extremely fast layer of memory sitting between the processor’s cores and the much larger, much slower main memory, holding copies of recently used data and instructions so the processor can keep working without waiting for a full trip out to RAM on every access.

Why does a processor need a cache in front of main memory at all?

Main memory can hold enormous amounts of data, but retrieving a single value from it takes dozens to hundreds of processor cycles — long enough that a core waiting on every access would spend most of its time idle rather than computing. A CPU cache solves this by keeping a tiny working set of recently touched bytes in storage that responds in just a few cycles, so when the processor needs the same data again, or data sitting nearby in memory, it can often get it from the cache instead of waiting for main memory. The trade-off is deliberate and unavoidable: cache capacity is tiny compared with RAM because the fastest storage is also the most expensive and hardest to make large, so the cache only pays off when the program’s access patterns reuse recently touched data or touch neighboring data that arrived together.

That reuse assumption is exactly where HNSW‘s real-world speed starts to depend on hardware, not just on the graph algorithm itself.

How is a modern CPU cache organized into layers?

Modern processors almost always stack several cache levels rather than one monolithic cache. The innermost level, usually called L1, is the smallest and fastest, typically private to a single core and split between instructions and data. The next level, L2, is larger and a little slower, still often private to a core. A shared outer level, commonly L3, is larger still and shared across cores on the same chip, acting as a last on-chip stop before a miss has to go out to main memory. When the processor needs a value, it checks the closest level first and only walks outward on a miss, so a hit in L1 is dramatically cheaper than a hit in L3, which is still dramatically cheaper than a miss that reaches RAM. Each level stores data in fixed-size blocks called cache lines — typically 64 bytes on common server and desktop CPUs — which means fetching one needed byte also brings in its neighbors, rewarding programs that keep related data packed together in memory.

Those layered hit-and-miss costs matter for HNSW because a single search does two very different kinds of memory work, and they stress the cache in opposite ways.

How does HNSW actually use — and often miss — the CPU cache during search?

Distance calculations between two high-dimensional vectors are naturally cache-friendly once both vectors are present: the arithmetic walks their dimensions in order, so after the first few elements land in cache, the rest of each vector tends to arrive through sequential, densely packed accesses that reuse the same cache lines. Neighbor-list traversal is the opposite pattern. Following an edge means looking up another node’s ID, then jumping to that node’s vector and neighbor list somewhere else in memory, then jumping again to the next candidate — a chain of pointer-like indirections that scatters accesses across the index. Those scattered jumps are far more likely to miss in L1 and L2, forcing the core to wait on outer cache or main memory even when the mathematical work per hop is small. In practice, a large HNSW index‘s query latency is often bounded as much by how often those random graph hops miss cache as by how many distance computations the search performs.

Production systems that keep the whole HNSW graph and its vectors in memory — including Weaviate’s in-memory HNSW index — still depend on the CPU cache to make that “in memory” promise feel fast, because RAM itself is not uniformly cheap to touch.

What does “in memory” really mean once the CPU cache enters the picture?

Saying an HNSW index lives in memory only means the operating system does not have to fetch graph structure or vectors from disk for ordinary query work. It does not mean every access costs the same. A vector already sitting in L1 can be consumed almost immediately; the same vector sitting only in main memory after a cold miss can cost tens or hundreds of cycles before the first dimensions are usable. That gap is why memory layout choices — packing neighbor IDs tightly, aligning vectors, keeping hot entry-point regions together — change measured HNSW speed even when the algorithm, the parameters, and the amount of RAM are unchanged. It is also why cold-cache and warm-cache benchmarks can disagree dramatically: the first queries after a process start or after the working set has been displaced pay the full cost of filling the cache, while later queries reuse what previous searches already pulled in.

A CPU cache is the hardware reason contiguous vector arithmetic feels cheap and random graph chasing feels expensive, even when both happen entirely inside RAM. From here, the glossary pages on cache lines and cache misses unpack the unit of transfer and what happens when a needed line is absent, the page on locality of reference explains the access-pattern idea the cache is built around, and the chapter on how HNSW’s data structures should be laid out in memory shows how those hardware facts drive concrete layout choices for a fast index.