What is a neighbor list?

A neighbor list is the data structure a single node uses to store which other nodes it is connected to at a given layer of the HNSW hierarchy, a concrete list of node identifiers a search reads to decide where to move next.
Created: Updated: 4 min read

A neighbor list is the actual data structure a single node uses to store which other nodes it’s connected to at a given layer of the HNSW hierarchy — a concrete list of node identifiers, one per connection, that a search reads whenever it visits that node and needs to know where it can move next. It’s the practical, per-node implementation of the abstract idea of a graph edge, and understanding exactly what a neighbor list contains and how it’s used clarifies how HNSW‘s more abstract concepts — degree caps, neighbor selection, connectivity — actually translate into working code.

What does a neighbor list actually contain, and how many does a single node have?

A neighbor list holds the identifiers of the other nodes a given node is directly connected to at one specific layer, typically stored as a simple array or similar compact structure of node IDs, exactly the kind of representation described more generally on the adjacency-list glossary page. Because a node can participate in multiple layers of the hierarchy simultaneously, as covered on the HNSW-layer glossary page, a single node maintains a separate neighbor list for every layer it appears in — a node whose maximum layer is three keeps four distinct neighbor lists, one each for layers zero through three, and these lists are generally unrelated to each other in content, since a node’s connections at a sparse upper layer look nothing like its connections at the dense base layer.

This means the total memory a single node consumes for graph structure isn’t captured by a single number — it’s the sum of the sizes of every neighbor list that node maintains across all the layers it participates in, with the base-layer list, capped by Mmax0, typically being by far the largest of the set, and the upper-layer lists, capped by M, considerably smaller and existing only for the comparatively rare nodes that reach those higher layers at all.

Whenever a greedy traversal — whether the simple single-best-candidate descent used in the upper layers or the fuller dual-queue search used at the base layer — arrives at a given node, it reads that node’s neighbor list for the current layer to find out which other nodes are worth considering next. Each identifier in the list gets checked against the visited set to avoid redundant work, and for each unvisited neighbor, the search computes the distance from that neighbor’s vector to the query, using the result to decide whether that neighbor is worth adding to the candidate queue for further exploration. This read-and-expand pattern, repeated at every node the traversal visits, is the fundamental operation HNSW’s search performs over and over, and the neighbor list is exactly the structure that makes each individual step of that pattern possible.

Because this read happens so frequently during a search — once per node visited, for every single query — the memory layout of a neighbor list has real, measurable performance consequences beyond just how much total memory it consumes. Storing a node’s neighbor list contiguously in memory, rather than scattered across separate allocations, generally improves cache behavior during traversal, since the CPU can load a whole neighbor list into fast cache memory in one pass rather than following a chain of separate memory accesses — exactly the kind of low-level performance consideration covered in more depth in the memory-layout and CPU-cache glossary pages under systems and hardware concepts.

How does a neighbor list’s content actually change over the life of an index, beyond its initial construction?

A node’s neighbor list isn’t necessarily fixed forever once that node is first inserted — as covered on the neighbor-list-overflow glossary page, later insertions can trigger the neighbor-selection heuristic to re-run against an existing node’s current neighbor list plus a new candidate, potentially replacing one of the node’s existing connections if the heuristic judges the new candidate to be a better fit for the node’s overall connectivity. This means a neighbor list is best thought of as a maintained, occasionally revised structure rather than a value that gets set once during insertion and never touched again, which matters directly for anyone implementing or reasoning carefully about HNSW’s insertion logic, since neighbor-list updates can ripple outward to affect nodes that were inserted long before the node currently triggering the update.

Having covered what a neighbor list actually is and how it gets read during search and modified during construction, the neighbor-list-capacity and neighbor-list-overflow glossary pages are the natural next stop, since they cover exactly the size limits and pruning behavior that govern how a neighbor list grows and gets trimmed over time. From there, the adjacency-list glossary page is worth revisiting for the more general, non-HNSW-specific version of this same underlying data structure.