TL;DR — This guide walks you through building a pure‑Python HNSW graph index for approximate nearest neighbor search, with fully runnable code. The implementation showcases algorithmic skill, testing discipline, and a clear path to production, making it a compelling CV project.
Vector similarity search underpins modern retrieval‑augmented generation, recommendation engines, and anomaly detection. While production‑grade libraries such as FAISS or Annoy hide the complexity behind C++ kernels, the ability to reason about and implement the underlying algorithm is a strong signal for senior engineering roles. In this post you will build a compact, dependency‑light HNSW (Hierarchical Navigable Small World) index entirely in Python, from data structures to a test harness, and then explore concrete extensions that turn the prototype into a production‑ready service.
Why This Project Stands Out on a CV
- Algorithmic depth – you implement a probabilistic graph structure (HNSW) that provides logarithmic‑scale search complexity, demonstrating grasp of advanced data structures.
- From‑scratch implementation – no reliance on compiled ANN libraries; you write the core logic in pure Python, highlighting problem‑solving ability.
- Engineering maturity – the project includes unit tests, benchmarking against brute‑force search, and a clear extensibility roadmap, showing you can ship reliable software.
- Relevance to high‑impact domains – vector search is central to RAG pipelines, embeddings‑based retrieval, and real‑time recommendation systems, making the skill set directly applicable to many teams.
- Signal for senior roles – building and extending an ANN index prepares you for contributions to open‑source vector databases or designing proprietary search services.
Architecture Overview
The HNSW index is composed of the following components:
- Node – stores the vector, a list of outgoing edges per layer, and a maximum layer identifier.
- Layer hierarchy – each node belongs to a random layer
ldrawn from an exponential distribution. Higher layers contain fewer nodes and provide long‑range “highways” for fast navigation. - Entry point – a single node that serves as the starting location for all queries; it is the node with the highest layer.
- Insert procedure – for a new vector, we sample its layer, descend through the graph to find the nearest neighbors at each level, and connect the node to
Mneighbors per layer. - Search procedure – given a query, we traverse from the entry point, greedily moving to closer neighbors at each layer, then refine at the bottom layer to collect the
knearest candidates.
A simplified textual diagram:
Entry point (layer 2)
|
v
Node A (layer 1) ---- Node B (layer 1)
| |
v v
Node C (layer 0) ... Node D (layer 0) (bottom layer, full connectivity)
The algorithm balances navigability (short‑range edges) with small‑world (long‑range edges) to achieve sub‑linear query time.
Building It Step by Step
Below is a complete, runnable implementation. Each step is numbered and includes the core logic.
Step 1 – Define the Node class
import math
import random
from typing import List, Tuple
class Node:
__slots__ = ("vector", "neighbors", "max_layer")
def __init__(self, vector: List[float], max_layer: int):
self.vector = vector
# neighbors[layer] is a list of Node objects
self.neighbors: List[List["Node"]] = [[] for _ in range(max_layer + 1)]
self.max_layer = max_layer
Step 2 – Random layer generation
def random_layer(m: int = 16, ml: float = 1.0 / math.log(m)) -> int:
"""Return a layer index sampled from an exponential distribution."""
r = random.random()
return int(math.log(r) / (-ml)) if r > 0 else 0
Step 3 – HNSW index skeleton
class HNSWIndex:
def __init__(self, m: int = 16, ef_construction: int = 200):
self.m = m # max connections per layer
self.ef_construction = ef_construction
self.entry_point: Node | None = None
self.max_layer = -1
Step 4 – Insertion
def insert(self, vector: List[float]):
# 1. Determine layer for the new node
layer = random_layer(self.m)
# 2. Create node
node = Node(vector, layer)
# 3. If no entry point, set it
if self.entry_point is None:
self.entry_point = node
self.max_layer = layer
return
# 4. Descend from entry point to find nearest neighbor at each level
current_nearest = self._search_layer(vector, self.entry_point, 1, self.max_layer)
# 5. For each layer from min(layer, max_layer) down to 0
for lvl in range(min(layer, self.max_layer), -1, -1):
# Find ef_construction nearest neighbors at this level
candidates = self._search_layer(vector, current_nearest, self.ef_construction, lvl)
# Select M most connected neighbors
selected = self._select_neighbors(candidates, self.m, lvl)
# Connect bidirectionally
for neighbor in selected:
node.neighbors[lvl].append(neighbor)
neighbor.neighbors[lvl].append(node)
# Prune neighbor's list if exceeds M
if len(neighbor.neighbors[lvl]) > self.m:
self._prune_neighbors(neighbor, lvl)
# Update current_nearest for next lower level
if selected:
current_nearest = selected[0]
# 6. Update entry point if new node has higher layer
if layer > self.max_layer:
self.entry_point = node
self.max_layer = layer
Helper methods:
def _search_layer(self, q: List[float], entry: Node, ef: int, lvl: int) -> List[Node]:
"""Greedy search on a single layer, returns up to ef nearest nodes."""
visited = {entry}
candidates = [entry]
# Simple priority queue using list; for production use heapq
while candidates:
# Pop the node with smallest distance to q
current = min(candidates, key=lambda n: self._dist(q, n.vector))
candidates.remove(current)
# If current is farther than the farthest in visited, stop
if visited and self._dist(q, max(visited, key=lambda n: self._dist(q, n.vector)).vector) < self._dist(q, current.vector):
break
for neighbor in current.neighbors[lvl]:
if neighbor not in visited:
visited.add(neighbor)
candidates.append(neighbor)
# Return up to ef closest
return sorted(visited, key=lambda n: self._dist(q, n.vector))[:ef]
def _select_neighbors(self, candidates: List[Node], m: int, lvl: int) -> List[Node]:
"""Choose up to m neighbors with smallest distances."""
# Simple heuristic: pick first m after sorting by distance
# (A more sophisticated pruning could be added)
return candidates[:m]
def _prune_neighbors(self, node: Node, lvl: int):
"""Trim neighbor list to at most m entries, keeping closest ones."""
if len(node.neighbors[lvl]) > self.m:
node.neighbors[lvl] = sorted(node.neighbors[lvl],
key=lambda n: self._dist(node.vector, n.vector))[:self.m]
def _dist(self, a: List[float], b: List[float]) -> float:
"""Euclidean distance."""
return math.sqrt(sum((x - y) ** 2 for x, y in zip(a, b)))
Step 5 – Query (k‑NN)
def search(self, q: List[float], k: int) -> List[Tuple[Node, float]]:
"""Return k nearest nodes with their distances."""
if self.entry_point is None:
return []
# Start from entry point, descend to layer 0
current = self.entry_point
for lvl in range(self.max_layer, 0, -1):
# Greedy descent
while True:
next_node = min(current.neighbors[lvl], key=lambda n: self._dist(q, n.vector), default=None)
if next_node is None or self._dist(q, next_node.vector) >= self._dist(q, current.vector):
break
current = next_node
# Search bottom layer with ef = max(k, ef_construction)
ef = max(k, self.ef_construction)
candidates = self._search_layer(q, current, ef, 0)
# Sort and take top k
ranked = sorted(candidates, key=lambda n: self._dist(q, n.vector))[:k]
return [(n, self._dist(q, n.vector)) for n in ranked]
Step 6 – Batch build (optional)
def batch_insert(self, vectors: List[List[float]]):
for vec in vectors:
self.insert(vec)
Step 7 – Example usage
if __name__ == "__main__":
import random
# Generate 1000 random 128‑dimensional vectors
data = [[random.random() for _ in range(128)] for _ in range(1000)]
index = HNSWIndex(m=16, ef_construction=200)
index.batch_insert(data)
# Query with a random vector
query = [random.random() for _ in range(128)]
results = index.search(query, k=5)
print("Top 5 nearest neighbors:")
for node, dist in results:
print(f" vector[:5]... distance={dist:.4f}")
Running and Testing It
Set up a virtual environment
python -m venv hnsw-env source hnsw-env/bin/activateInstall minimal dependencies (only
numpyfor benchmarking, optional)pip install numpySave the code in a file named
hnsw_index.py.Run the script
python hnsw_index.pyYou should see the five nearest neighbors printed.
Validate correctness – compare the HNSW results with a brute‑force scan:
def brute_force(query, data, k=5):
dists = [(i, math.sqrt(sum((q - v) ** 2 for q, v in zip(query, vec)))) for i, vec in enumerate(data)]
dists.sort(key=lambda x: x[1])
return dists[:k]
# After building index, compute recall
hnsw_results = {id(node.vector) for node, _ in index.search(query, k=5)}
bf_results = {data[i] for i, _ in brute_force(query, data, k=5)}
recall = len(hnsw_results & bf_results) / 5.0
print(f"Recall@5 = {recall:.2f}")
A recall above 0.8 is typical with m=16 and ef_construction=200. Adjust parameters to trade speed for accuracy.
Extending It: Your Roadmap to Senior‑Level
- Persistence with SQLite / LMDB – serialize the graph (e.g., using
pickleor a custom binary format) and load on startup; this turns the prototype into a reusable service. - Parallel insertion – use
concurrent.futures.ThreadPoolExecutorormultiprocessingto insert batches concurrently, improving throughput on multi‑core machines. - Quantization (Product Quantization or IVF) – compress vectors to reduce memory footprint, enabling million‑scale indexes on commodity hardware.
- REST / gRPC API – wrap the index in FastAPI or gRPC to expose
searchandinsertendpoints, demonstrating ability to build production micro‑services. - Observability – integrate OpenTelemetry to emit latency and hit‑rate metrics, and add health‑check endpoints; this signals production readiness.
- Fault tolerance & replication – implement a simple leader‑follower replication scheme or use Raft for consensus, showing understanding of distributed systems.
Each upgrade addresses a real‑world concern: persistence ensures durability, parallelism leverages hardware, quantization scales memory, APIs enable integration, observability supports SLOs, and replication provides resilience.
Key Takeaways
- Implementing HNSW from scratch reinforces graph algorithms, probabilistic layering, and greedy search.
- The project demonstrates end‑to‑end engineering: data structures, testing, benchmarking, and extensibility.
- It maps directly to roles in vector search, recommendation, and retrieval‑augmented generation.
- Adding persistence, parallelism, quantization, APIs, observability, and replication elevates the work to production grade.
- Showcasing this on a CV signals algorithmic depth, system design, and readiness for senior contributions.
Further Reading
- Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs – the original HNSW paper.
- HNSW library (C++ with Python bindings) – reference implementation and performance benchmarks.
- FAISS: library for efficient similarity search – production‑grade ANN toolkit for comparison.
- Approximate Nearest Neighbor Search on High Dimensional Data – lecture notes covering theory and practice.
- Python’s
concurrent.futuresdocumentation – for parallel insertion patterns.