08. HNSW Construction

Chapter 8 of 18 · 25 min

KEY INSIGHT

HNSW construction is O(n log n) if done correctly—each insertion costs roughly O(log n) to find its layer and position, then O(m log n) to maintain connections. But the quality of connections matters for search performance. ### Insertion Algorithm When inserting a new vector: 1. **Determine its maximum layer** via geometric distribution 2. **For each layer up to max_layer:** - Search from current entry point to find where the new vector fits - Connect to nearest neighbors at that layer 3. **Update entry point** if new node is closer to origin ```python import heapq def hnsw_insert(hnsw, vector: np.ndarray, ef_construction: int = 100): """ Insert a vector into HNSW. Args: hnsw: HNSW index vector: vector to insert ef_construction: size of candidate pool during construction """ node_id = len(hnsw.nodes) node = Node(id=node_id, vector=vector, neighbors={}) # Determine max layer for this node max_layer = int(-np.log(np.random.random()) * 1.0 / np.log(2)) max_layer = min(max_layer, hnsw.max_layers or 10) # Start from entry point current_entry = hnsw.entry_point level = hnsw.max_layers or 10 # Descend from top to max_layer for l in range(level, max_layer, -1): candidates = [(np.linalg.norm(current_entry.vector - vector), current_entry)] visited = {current_entry.id} while candidates: dist, candidate = heapq.heappop(candidates) entry_dist = np.linalg.norm(current_entry.vector - vector) if dist > entry_dist: break for neighbor_id in candidate.neighbors.get(l, []): if neighbor_id in visited: continue visited.add(neighbor_id) neighbor = hnsw.nodes[neighbor_id] d = np.linalg.norm(neighbor.vector - vector) if d < entry_dist or len(candidates) < ef_construction: heapq.heappush(candidates, (d, neighbor)) # Track best entry for this layer if d < entry_dist: current_entry = neighbor entry_dist = d # Now at max_layer, begin actual insertion for l in range(max_layer, -1, -1): node.neighbors[l] = set() # Search for neighbors at this layer candidates = [(np.linalg.norm(current_entry.vector - vector), current_entry)] visited = {current_entry.id} results = [] while candidates: dist, candidate = heapq.heappop(candidates) results.append((dist, candidate)) for neighbor_id in candidate.neighbors.get(l, []): if neighbor_id in visited: continue visited.add(neighbor_id) neighbor = hnsw.nodes[neighbor_id] d = np.linalg.norm(neighbor.vector - vector) heapq.heappush(candidates, (d, neighbor)) # Sort and take closest m neighbors results.sort() neighbors = [node for _, node in results[:hnsw.m]] for neighbor in neighbors: node.neighbors[l].add(neighbor.id) neighbor.neighbors[l].add(node_id) hnsw.nodes[node_id] = node # Update entry point if necessary if hnsw.entry_point is None or \ np.linalg.norm(vector) < np.linalg.norm(hnsw.entry_point.vector): hnsw.entry_point = node return node_id ``` ### ef_construction Parameter ef_construction controls how thoroughly you search during construction. Higher values produce better connections but slow construction. - ef_construction = 100-200 is typical for production - Too low (ef_construction = m): edges may not connect to true nearest neighbors - Too high: diminishing returns, much slower construction ### Construction Order Matters HNSW is sensitive to insertion order. If you insert similar vectors in sequence, they form local clusters but miss connections to distant clusters. Random shuffling of insertions typically produces better results. ```python def build_hnsw_batched(vectors: np.ndarray, m: int = 16, ef_construction: int = 100): """ Build HNSW index with randomized insertion order. """ hnsw = HNSW(m=m) # Shuffle indices for better graph structure indices = np.random.permutation(len(vectors)) shuffled = vectors[indices] # Insert with shuffled order for i, vec in enumerate(shuffled): hnsw_insert(hnsw, vec, ef_construction) if (i + 1) % 10000 == 0: print(f"Inserted {i+1}/{len(vectors)} vectors") return hnsw # Benchmark construction import time vectors = np.random.randn(100_000, 128).astype('float32') start = time.time() hnsw = build_hnsw_batched(vectors, m=16, ef_construction=100) elapsed = time.time() - start print(f"Construction time: {elapsed:.2f}s for {len(vectors)} vectors") print(f"Rate: {len(vectors)/elapsed:.0f} vectors/sec") ```

Building HNSW involves inserting vectors one at a time, finding their position via search at each layer, and connecting to nearby neighbors. The order of insertion affects the final structure.

EXERCISE

Build HNSW indexes with different insertion orders (sequential, random, sorted by L2 norm). Measure search quality for each. Observe how insertion order affects the final graph.

def compare_insertion_orders(vectors, n_queries=100):
    """Compare HNSW built with different insertion orders."""
    results = {}
    
    orders = {
        'sequential': vectors,
        'random': vectors[np.random.permutation(len(vectors))],
        'sorted_norm': vectors[np.argsort(np.linalg.norm(vectors, axis=1))]
    }
    
    queries = np.random.randn(n_queries, vectors.shape[1])
    gt = brute_force_ground_truth(vectors, queries, k=10)
    
    for name, ordered_vectors in orders.items():
        hnsw = build_hnsw_batched(ordered_vectors, m=16, ef_construction=100)
        recall = measure_hnsw_recall(hnsw, queries, gt, k=10)
        results[name] = recall
        print(f"{name}: recall@10 = {recall:.4f}")
    
    return results

# Run comparison
results = compare_insertion_orders(vectors[:20000])