HNSW Greedy Graph Search

Background

HNSW (Hierarchical Navigable Small World) is the dominant graph-based ANN index for in-memory retrieval at scale. The greedy search kernel: start at an entry node, maintain a candidates set; at each step, pick the closest candidate, explore its neighbours, stop when no candidate is closer than the farthest result already kept.

Problem statement

Implement hnsw_search(query, embeddings, graph, entry, k). Single-layer NSW search:

1. Init: visited = {entry}. candidates (min-heap by distance) starts with entry. results (max-heap by distance, capped at $k$) starts with entry.
2. Loop: pop the closest candidate; if its distance > the farthest result's distance, stop. Otherwise iterate the candidate's neighbours: if unvisited, mark visited, push to both heaps (results trims to $k$).
3. Return result indices sorted by ascending distance.

Input

• query — 1-D np.ndarray of length $d$.
• embeddings — 2-D np.ndarray shape $(N, d)$.
• graph — dict[int, list[int]], adjacency list. Missing keys map to no neighbours.
• entry — int, starting node index.
• k — int >= 1, target result count.

Output

Returns list[int] of length $\le k$, in ascending-distance order.

Examples

Example 1 — finds the closest reachable node

embeddings = [[0,0], [1,1], [10,10]]
graph = {0:[1,2], 1:[0,2], 2:[0,1]}
hnsw_search([0.1,0.1], embeddings, graph, entry=2, k=1) → [0]

Example 2 — k nearest in ascending distance

A connected 1-D chain; query at 0; entry at the far end
hnsw_search returns the nearest k nodes

Example 3 — k larger than graph returns the reachable subgraph

Constraints

• Distance is squared L2 (cheaper than sqrt and gives the same ordering).
• Use heaps for both candidates (min-heap) and results (max-heap as negated distances).
• Returns Python int indices.

Notes

• Single-layer NSW vs full HNSW. The full HNSW has multiple layers; you greedy-search the top layer first to find a good entry into the next layer, etc. This kernel is the per-layer routine.
• ef parameter. Real HNSW exposes ef_search — the size of the candidate set. Larger $ef$ → higher recall, more compute. This kernel uses ef = k implicitly.