An HNSW graph is the layered graph structure used by HNSW indexes to search vectors quickly. It connects vectors as nodes, stores neighbor relationships as edges, and organizes those connections across multiple layers.
The graph is the reason HNSW can avoid brute force comparison. Search moves through the graph toward better candidates instead of comparing the query with every stored vector.
Short Answer
An HNSW graph is a multi-layer nearest neighbor graph. The bottom layer contains every vector. Higher layers contain fewer vectors and longer-range connections.
Search starts in an upper layer, uses shortcut connections to move near the target region, then descends through lower layers for more detailed local search.
What the Nodes Represent
In an HNSW graph, each node represents a vector entry.
That vector may represent a document chunk, product, image, user profile, audio segment, or any other embedded object. The graph does not care what the original object was. It only needs the vector and the distance metric used to compare vectors.
What the Edges Represent
Edges connect one vector node to other vector nodes.
These connections are chosen so the graph can be navigated efficiently. Most edges connect nearby vectors, but upper layers provide longer-range movement across the graph.
An edge is not a semantic label. It is a navigational link that helps search move toward closer candidates.
Layer Zero
Layer zero is the base layer of the HNSW graph.
Every indexed vector appears in this layer. It is the most detailed part of the graph and is used for final nearest neighbor refinement.
Layer zero usually has many local connections because it must support precise search near the target region.
Upper Layers
The upper layers contain fewer nodes than layer zero.
As the layers get higher, they become sparser. These sparse layers act like shortcut maps. They allow the search to make larger jumps before it reaches the dense base layer.
This is the hierarchical part of HNSW.
Why Some Nodes Appear in Multiple Layers
A vector can appear in more than one layer.
Every vector is present at layer zero, but only some vectors appear in higher layers. Those higher-layer nodes help route searches across the graph.
The result is a hierarchy where upper layers are small and broad, while lower layers are large and detailed.
Long-Range and Local Connections
The HNSW graph combines two types of movement.
- Long-range movement: upper layers help the search move quickly across distant regions.
- Local movement: lower layers help the search inspect nearby candidates in detail.
This is similar to using highways for a long trip and local streets near the destination.
How Traversal Starts
Search begins from an entry point in the graph.
The algorithm compares the query vector with candidates near the entry point, follows connections toward closer nodes, and keeps track of promising candidates.
It does not need to know the final answer at the start. It only needs a way to move from a starting point toward better regions of the graph.
How Traversal Moves Down Layers
After using an upper layer to get closer to the query region, the search descends to the next layer.
At each lower layer, it repeats the same idea with more detail. The search uses the best candidates from the previous layer as starting points for the next layer.
By the time it reaches layer zero, the search is already near a promising region of the graph.
Why the Graph Is Navigable
The graph is navigable because edges tend to guide search toward closer vectors.
If the graph is well built, following neighbor links usually improves the candidate set. The search does not wander randomly. It uses distance comparisons to choose which connected nodes are worth exploring.
Graph quality has a direct effect on recall and latency.
Graph Construction
When a vector is inserted, HNSW must place it into the graph.
The algorithm searches through existing layers to find nearby nodes, then creates connections between the new node and suitable neighbors. Construction settings affect how thoroughly it searches for good connections.
Better graph construction can improve search quality, but it takes more time during indexing.
Graph Density
Graph density describes how many connections the graph keeps.
A denser graph can be easier to navigate and may improve recall. A sparser graph uses less memory but can make search less reliable.
This is why connection limits matter in HNSW configuration.
Memory Costs
The HNSW graph consumes memory because it stores nodes and edges.
The vector values usually take a large share of memory, especially when vectors have many dimensions. But graph edges also matter, especially when there are many vectors or many connections per node.
At large scale, the graph structure itself becomes an important part of capacity planning.
Why It Is Not a Tree
An HNSW graph is not a tree.
In a tree, nodes usually have a strict parent-child structure. In an HNSW graph, nodes can have many neighbor links, and traversal can move through multiple possible routes.
This flexibility is one reason graph-based ANN search works well for high-dimensional vectors.
Why It Is Not Fully Connected
An HNSW graph is also not fully connected in the sense of every node having an edge to every other node.
A fully connected graph would be too expensive. HNSW keeps a selected set of connections that make the graph navigable without storing every possible pairwise relationship.
How Filters Affect the Graph
Filters can change how useful graph paths are.
A node may be close to the query vector but fail a metadata filter. If many useful graph paths pass through filtered-out nodes, search may need to explore more candidates or use specialized filtered-search strategies.
This is why filtered vector search can be harder than unfiltered vector search.
HNSW Graph vs HNSW Index
The HNSW graph is the connected structure of vector nodes and edges.
The HNSW index is the broader data structure maintained by the database. It includes the graph plus the operational machinery needed for search, insertion, deletion, configuration, persistence, and integration with the rest of the system.
In plain terms, the graph is the navigational map. The index is the full search structure that uses that map.
Common Misunderstandings
Common misunderstandings include:
- thinking every vector appears in every layer
- thinking graph edges are labels or categories
- assuming the graph is exact or exhaustive
- confusing HNSW with a tree structure
- ignoring the memory cost of edges
- assuming filters never affect graph traversal
Summary
An HNSW graph is a layered nearest neighbor graph used for fast approximate vector search. Layer zero contains all vectors, while upper layers contain fewer nodes and support long-range movement.
Search starts high, moves through shortcut connections, descends through lower layers, and refines in the detailed base graph. The quality, density, and memory cost of this graph determine much of the index’s practical performance.