What is an adjacency list?

An adjacency list represents a graph by storing, for each individual node, a direct list of the other nodes it connects to, and this exact representation is how HNSW actually stores its own layered graph structure, with each vector keeping its own list of neighboring vectors at every layer it belongs to.

How does an adjacency list actually represent a graph’s connections?

Rather than trying to represent an entire graph’s connections all at once in some single large structure, an adjacency list breaks the problem down node by node: each node in the graph gets its own list, and that list simply contains every other node it’s directly connected to. Looking up which nodes a specific node connects to just means retrieving that one node’s own list directly, without needing to search through information about every other node in the graph to find the relevant connections. This node-by-node organization makes an adjacency list a natural fit for graphs where each individual node only connects to a relatively small number of others, which is exactly the situation in a graph like HNSW‘s, where each vector maintains only a bounded number of connections rather than being connected to every other vector.

How does this adjacency-list structure map directly onto HNSW’s own layered graph?

Every vector inserted into HNSW’s graph, covered throughout this site’s coverage of building the algorithm from scratch, maintains its own neighbor list at each layer it belongs to, recording exactly which other vectors it’s connected to at that specific layer, which is precisely an adjacency list applied separately to each layer of the structure. Searching the graph, covered in this site’s coverage of how the algorithm searches step by step, means repeatedly retrieving a vector’s own neighbor list at the current layer and checking each of those listed neighbors, which is exactly the kind of direct, node-by-node lookup an adjacency list is built to support efficiently.

Why is an adjacency list a better fit for HNSW’s graph than an alternative representation that tracks every possible pairwise connection directly?

An alternative graph representation that tracks every possible pair of nodes directly, checking a fixed position for every conceivable connection whether it exists or not, would require space proportional to the square of the total number of nodes, which becomes wildly impractical for a graph with many thousands or millions of vectors, most of which aren’t directly connected to each other at all. An adjacency list instead only stores space for the connections that actually exist, which fits HNSW’s structure well since each vector deliberately maintains only a small, bounded number of connections rather than being densely connected to most other vectors in the graph, covered elsewhere on this site’s parameters governing connection counts like M.

An adjacency list’s node-by-node organization is exactly the representation HNSW relies on to store its layered graph efficiently, keeping memory usage proportional to the actual connections that exist rather than to every conceivable pair of vectors. From here, the pages on array and on how HNSW’s data structures should be laid out in memory for performance dig further into how these neighbor lists actually get stored in practice.