HNSW Greedy Search Single Hopmedium

HNSW Greedy Search Single Hop

medium RAG & Retrieval 15 min

NumPy allowed · plain Python earns 10 bonus points

A query retrieves context

Embedding similarity ranks the documents before generation.

Open lesson →

01query

02embed

03retrieve

04context

What is RAG?→ embed →top context

retrieval.md44%

rag-systems.md33%

agents.md24%

Cosine-like similarity scores ranked before context assembly

Implement one greedy-descent step of HNSW's real search algorithm: from the current node, move to whichever unvisited neighbor is closest to the query, or stop if none improves.

Task

Implement hnsw_greedy_hop(current_dist, neighbor_dists, visited). neighbor_dists maps neighbor id -> its distance to the query. Among neighbors NOT in visited, find the one with the smallest distance. If that smallest distance is < current_dist, return that neighbor's id (the hop to take); otherwise return None (local minimum reached, search stops). Ties among equally-close neighbors broken by id ascending.

Function Signature

hnsw_greedy_hop(current_dist: float, neighbor_dists: dict[str, float], visited: set) -> str | None

Examples

Example 1: improving hop exists
Input: current_dist = 5
neighbor_dists = {'a': 3, 'b': 4}
visited = []
Output: 'a'

Example 2: local minimum, no improvement
Input: current_dist = 1
neighbor_dists = {'a': 2, 'b': 3}
visited = []
Output: None

Example 3: all neighbors visited
Input: current_dist = 5
neighbor_dists = {'a': 1}
visited = ['a']
Output: None

Constraints

current_dist >= 0
distances >= 0

Python3Saved ✓

def hnsw_greedy_hop(current_dist: float, neighbor_dists: dict[str, float], visited: set) -> str | None:

# Your implementation here

pass

Case 1: improving hop exists

Input: current_dist = 5
neighbor_dists = {'a': 3, 'b': 4}
visited = []

Expected: 'a'

Case 2: local minimum, no improvement

Input: current_dist = 1
neighbor_dists = {'a': 2, 'b': 3}
visited = []

Expected: None

Case 3: all neighbors visited

Input: current_dist = 5
neighbor_dists = {'a': 1}
visited = ['a']

Expected: None