Step 2 — Greedy search in one layer

This is the engine of HNSW. Everything else — multi-layer search and insertion — calls this one routine. It answers: within a single layer, starting from some entry node(s), what are the closest nodes to the query?

The idea: a guided "beam" walk

Pure greedy walking (always step to the single best neighbor) is fast but can get stuck before reaching the true nearest. The fix is to explore with a small beam: keep a working set of the best ef candidates found so far, and keep expanding the most promising unexplored one until none can improve the set.

We track two collections:

  • candidates — nodes we've found but not yet explored, ordered so we always expand the closest one next (a min-heap).
  • results — the best ef nodes found so far, ordered so we can quickly see the worst one (a max-heap), since that's the one a newcomer must beat.

A heap is a structure that always gives you the smallest (or largest) item instantly. Python's heapq is a min-heap; to get a max-heap we store negative distances.

The stopping rule

We stop when the closest unexplored candidate is farther than the worst node in our results. At that point nothing left to explore could improve the answer, so we're done — that's what makes it fast (we don't visit the whole layer).

The code

import heapq


def _search_layer(self, q, entry_ids, ef, level):
    """Greedy best-first search within one layer.
    Returns up to `ef` nearest nodes as a list of (distance, id)."""
    visited = set(entry_ids)
    candidates = []          # min-heap by distance: explore nearest first
    results = []             # max-heap by -distance: the best `ef` so far

    for e in entry_ids:
        d = self._dist(q, self.data[e])
        heapq.heappush(candidates, (d, e))
        heapq.heappush(results, (-d, e))

    while candidates:
        d_c, c = heapq.heappop(candidates)         # closest unexplored
        if d_c > -results[0][0]:                    # farther than our worst kept?
            break                                   # ...then nothing can improve
        for nb in self.graph[level].get(c, []):     # look at c's neighbors
            if nb in visited:
                continue
            visited.add(nb)
            d_nb = self._dist(q, self.data[nb])
            if d_nb < -results[0][0] or len(results) < ef:
                heapq.heappush(candidates, (d_nb, nb))
                heapq.heappush(results, (-d_nb, nb))
                if len(results) > ef:               # keep only the best ef
                    heapq.heappop(results)
    return [(-d, n) for d, n in results]

Reading it

  • We seed both heaps with the entry node(s).
  • Each loop: take the closest unexplored candidate c. If it's already worse than our worst kept result, stop (the key efficiency rule).
  • Otherwise, look at each unvisited neighbor of c, compute its distance, and if it's good enough (better than our current worst, or we don't yet have ef results), add it to both heaps. Trim results back to ef.
  • visited ensures we never process the same node twice.

The ef parameter is the beam width: larger ef explores more, finds better answers, and costs more — the recall/speed dial.

See it work

Eight points in 2-D: a cluster near $(5,5)$, a cluster near the origin, and two outliers. We query near $(5.2, 5.2)$ and ask for the 3 nearest:

import numpy as np
from hnsw import HNSW, brute_force_knn

pts = np.array([[0., 0.], [1., 0.], [0., 1.],      # cluster near origin
                [5., 5.], [6., 5.], [5., 6.],      # cluster near (5,5)
                [10., 0.], [0., 10.]])             # two outliers
idx = HNSW(dim=2, M=4, ef_construction=20, distance="euclidean", seed=3)
for p in pts:
    idx.add(p)

q = np.array([5.2, 5.2])
print("HNSW  top3:", [(i, round(d, 2)) for i, d in idx.search(q, k=3, ef=10)])
print("exact top3:", [(i, round(d, 2)) for i, d in brute_force_knn(pts, q, k=3)])

Output:

HNSW  top3: [(3, 0.08), (4, 0.68), (5, 0.68)]
exact top3: [(3, 0.08), (4, 0.68), (5, 0.68)]

HNSW returns exactly the three points of the $(5,5)$ cluster — ids 3, 4, 5 — identical to the exact brute-force answer. 🎯 The greedy walk hopped straight into the right cluster and the beam picked up its members.

So far this searches one layer. Next we stack layers to make it scale. 👉