What does complete HNSW pseudocode look like, paper-style and implementation-style?
Complete HNSW pseudocode looks different depending on the audience it’s written for: a paper-style version stays close to the conceptual procedures described narratively throughout this site, using the notation established in the previous appendix, while an implementation-style version reads closer to real code, with named functions and explicit data structures standing in for the more abstract steps a formal description leaves unspecified.
What does the search procedure look like in paper-style pseudocode?
The following expresses the layered search process described in this site’s page on how HNSW searches a graph, step by step, using the notation from the previous appendix:
function GREEDY-DESCEND(graph, query, entryPoint, layer):
current ← entryPoint
loop:
nearest ← the neighbor of current in layer with smallest
distance(query, neighbor)
if distance(query, nearest) ≥ distance(query, current):
return current
current ← nearest
function LAYER-SEARCH(graph, query, entryPoints, ef, layer):
visited ← entryPoints
candidates ← a min-priority-queue ordered by distance(query, ·),
initialized with entryPoints
results ← a max-priority-queue ordered by distance(query, ·),
initialized with entryPoints
while candidates is not empty:
c ← candidates.pop-closest()
f ← results.peek-farthest()
if distance(query, c) > distance(query, f) and |results| ≥ ef:
break
for each neighbor of c in layer not in visited:
visited.add(neighbor)
f ← results.peek-farthest()
if distance(query, neighbor) < distance(query, f) or |results| < ef:
candidates.push(neighbor)
results.push(neighbor)
if |results| > ef:
results.pop-farthest()
return results
function K-NEAREST-NEIGHBORS(graph, query, k, efSearch):
entryPoint ← graph.topEntryPoint
for layer from graph.topLayer down to 1:
entryPoint ← GREEDY-DESCEND(graph, query, entryPoint, layer)
candidates ← LAYER-SEARCH(graph, query, {entryPoint}, efSearch, 0)
return the k closest elements of candidates to queryWhat does the insertion procedure look like in paper-style pseudocode?
The insertion process described in this site’s page on how an HNSW graph is actually built follows the same layered pattern in reverse, using a diversified neighbor-selection step covered in this site’s page on why the neighbor-selection heuristic matters:
function ASSIGN-LEVEL(mL):
U ← a uniform random draw from (0, 1)
return floor(-ln(U) × mL)
function INSERT(graph, newVector, M, efConstruction, mL):
level ← ASSIGN-LEVEL(mL)
entryPoint ← graph.topEntryPoint
for layer from graph.topLayer down to level + 1:
entryPoint ← GREEDY-DESCEND(graph, newVector, entryPoint, layer)
for layer from min(level, graph.topLayer) down to 0:
candidates ← LAYER-SEARCH(graph, newVector, {entryPoint},
efConstruction, layer)
neighbors ← SELECT-DIVERSE-NEIGHBORS(candidates, M)
for each neighbor in neighbors:
ADD-BIDIRECTIONAL-EDGE(newVector, neighbor, layer)
if neighbor now has more than the layer's connection limit:
PRUNE-NEIGHBORS(neighbor, layer)
entryPoint ← the closest element of candidates to newVector
if level > graph.topLayer:
graph.topLayer ← level
graph.topEntryPoint ← newVectorHow does this translate into implementation-style pseudocode closer to real code?
A practical implementation replaces the abstract priority queues and neighbor sets above with concrete data structures, and makes memory and identity concerns explicit in a way paper-style pseudocode deliberately leaves out:
class HnswIndex:
vectors: array of float-vectors, indexed by internalId
neighborLists: array of (layer -> list of internalId), indexed by internalId
externalToInternal: hash-map from externalLabel to internalId
topLayer: integer
entryPointId: internalId
function search(queryVector, k, efSearch):
current ← this.entryPointId
for layer from this.topLayer down to 1:
current ← greedyStep(queryVector, current, layer)
candidateHeap ← newMinHeap(); resultHeap ← newMaxHeap()
visitedSet ← newBitset(size = length(this.vectors))
pushCandidate(current, candidateHeap, resultHeap, visitedSet, queryVector)
while not candidateHeap.isEmpty():
c ← candidateHeap.popMin()
if shouldStop(c, resultHeap, efSearch): break
for n in this.neighborLists[c][0]:
if not visitedSet.contains(n):
visitedSet.set(n)
pushCandidate(n, candidateHeap, resultHeap, visitedSet, queryVector)
return topK(resultHeap, k)
function insert(externalLabel, vector, M, efConstruction, mL):
internalId ← allocateInternalId()
this.vectors[internalId] ← vector
this.externalToInternal[externalLabel] ← internalId
level ← sampleLevel(mL)
# descend, connect at each layer from level down to 0, prune as needed
# (same structure as INSERT above, expressed against concrete arrays
# and hash maps instead of abstract graph/candidate notation)
updateEntryPointIfHigher(internalId, level)What should a reader take away from comparing the two styles side by side?
The paper-style version is precise about what the algorithm does at a conceptual level — which candidates get considered, in what order, and under what stopping condition — while staying deliberately silent about how any of it should actually be stored or executed efficiently. The implementation-style version fills in exactly those silences: concrete arrays instead of abstract sets, an explicit label-to-ID mapping, and a visited-tracking structure chosen for performance rather than left unspecified. Neither version is more “correct” than the other; they answer different questions, and the gap between them is precisely the space this site’s Part IV, on building HNSW from scratch, and Part V, on reading real implementations, spend their time exploring in depth.
With both search and construction now expressed as pseudocode rather than only prose, the next appendix turns to a related practical question: which distance function to actually choose for a given kind of data, and when. Readers implementing any of the procedures above for the first time should pair them with this site’s page on what a minimal, correct implementation looks like, which covers the testing discipline needed to verify an implementation like this one actually behaves correctly.