Why HNSW Can Speed Up Search 50× Compared to Brute‑Force? A Hands‑On Guide to Building Vector Indexes

1️⃣ Why Your Search Is Slow

A colleague complained that their document search takes 10 seconds for 100 k records because they use a naïve brute‑force scan that compares every vector, similar to flipping through every book on a shelf instead of checking the catalogue.

2️⃣ Core Concepts: Three Index Types

2.1 Flat Index (brute‑force)

import faiss
index = faiss.IndexFlatL2(dimension)
index.add(vectors)

Flat stores all vectors and compares each at query time.

Advantages : 100 % recall, simple implementation, no parameters.

Disadvantages : Linear time, slow for >100 k vectors, high latency.

Suitable for small datasets (<100 k), offline batch processing, and scenarios requiring exact recall.

2.2 IVF Index (inverted file)

import faiss
quantizer = faiss.IndexFlatL2(dimension)
index = faiss.IndexIVFFlat(quantizer, dimension, nlist=100)
# IVF needs training: K‑means to find 100 centroids
index.train(vectors)
index.add(vectors)

Key parameters : nlist: number of clusters, roughly sqrt(total vectors). Example: 100 k vectors → nlist≈316; 1 M vectors → nlist≈1000. nprobe: how many clusters are visited at query time; larger nprobe improves recall but slows search.

Construction steps :

Cluster vectors with K‑means into nlist buckets; each vector records its bucket.

At query time, locate the nearest buckets and perform exact search inside them.

Analogy: library sections – programming books in one area, literature in another, you first locate the section before scanning the shelves.

2.3 HNSW Index (hierarchical navigable small world)

import faiss
index = faiss.IndexHNSWFlat(dimension, M=16)
index.hnsw.efConstruction = 200  # build‑time search breadth
index.add(vectors)

Core parameters : M: number of edges per node (16 or 32). Larger M → higher recall, slower speed, more memory. efConstruction: breadth of the graph construction search. Larger value → better recall, slower build. efSearch: query‑time search breadth (default 64, recommended 64‑256). Larger efSearch → higher recall, slower query.

Search proceeds from a sparse top‑level graph (highway) down to dense lower layers (local roads), quickly narrowing to the nearest neighbors.

2.4 Parameter Comparison

Flat – speed ★, memory ★★★★★, accuracy 100 %, no training.

IVF – speed ★★★, memory ★★★, accuracy 90‑99 %, requires training.

HNSW – speed ★★★★★, memory ★★, accuracy 95‑99 %, moderate build time.

3️⃣ Pitfalls

Pitfall 1: Using IVF without training

# ❌ Wrong: IVF must be trained first
index = faiss.IndexIVFFlat(quantizer, dim, nlist)
index.add(vectors)  # error or very poor results

# ✅ Correct
index.train(vectors)
index.add(vectors)

Without training, cluster centroids are random, yielding recall comparable to random guessing.

Pitfall 2: Default efSearch too low

FAISS default efSearch=16 gives about 85 % recall for top_k=10. Raising efSearch improves recall:

efSearch=16 → ~85 % recall

efSearch=64 → ~95 % recall

efSearch=256 → ~99 % recall

Production environments should set efSearch ≥ 64, preferably 128 or higher.

Pitfall 3: Choosing the wrong index type

<10 k vectors → Flat (simple and exact)

10 k‑100 k → HNSW (fast and accurate)

100 k‑500 k → IVF (balanced)

> 500 k → HNSW + IVF hybrid

Pitfall 4: Dimension mismatch

# ❌ Wrong dimension
index = faiss.IndexFlatL2(768)
index.add(vectors_1024_dim)  # error or silent failure

# ✅ Correct
assert vectors.shape[1] == 768
index = faiss.IndexFlatL2(768)
index.add(vectors)

4️⃣ Code Demo: Production‑Ready Index Builder

import numpy as np
import faiss

class VectorIndexBuilder:
    def __init__(self, dimension: int = 768):
        self.dimension = dimension
        self.index = None

    def build(self, vectors, index_type="hnsw", **kwargs):
        vectors = vectors.astype('float32')
        n = len(vectors)
        if index_type == "flat":
            self.index = faiss.IndexFlatL2(self.dimension)
        elif index_type == "ivf":
            nlist = kwargs.get("nlist", int(np.sqrt(n)))
            quantizer = faiss.IndexFlatL2(self.dimension)
            self.index = faiss.IndexIVFFlat(quantizer, self.dimension, nlist)
            print(f"Training on {n} samples...")
            self.index.train(vectors)
        elif index_type == "hnsw":
            M = kwargs.get("M", 16)
            ef = kwargs.get("efConstruction", 200)
            self.index = faiss.IndexHNSWFlat(self.dimension, M)
            self.index.hnsw.efConstruction = ef
        self.index.add(vectors)
        return self

    def search(self, query, top_k=10):
        return self.index.search(query.astype('float32'), top_k)

    def optimize(self, ef=None, nprobe=None):
        if ef and hasattr(self.index, 'hnsw'):
            self.index.hnsw.efSearch = ef
        if nprobe and hasattr(self.index, 'nprobe'):
            self.index.nprobe = nprobe

Example usage selects the index type based on data volume, builds the index, tunes search parameters, and performs a query.

4.3 Performance Benchmarks (10 k vectors, dim 768, top_k = 10)

Flat – 45 ms, 100 % recall

IVF (nprobe = 1) – 2 ms, 82 % recall

IVF (nprobe = 10) – 8 ms, 95 % recall

HNSW (M = 16, ef = 64) – 0.8 ms, 97 % recall

Conclusion : HNSW provides the best balance of speed and accuracy and is the preferred choice for production.

5️⃣ Best Practices

5.1 Index Selection Decision Tree

Data < 100k → Flat

Data 100k‑1M → HNSW (M=16, ef=64)

Data 1M‑5M → IVF (nlist≈√N, nprobe=10)

Data > 5M → HNSW+IVF hybrid

5.2 Parameter Tuning Rules

HNSW: ensure efSearch ≥ top_k × 2, then adjust M for speed.

IVF: start nprobe at 5 % of nlist, increase until recall meets the target.

Any index: test on a small sample before full‑scale build.

5.3 Production Checklist

Benchmark different index types and pick the best.

Adjust efSearch / nprobe to optimal values.

Monitor P99 search latency.

Evaluate memory consumption.

Record recall via manual sampling.

6️⃣ Thought Questions

If data grows from 100 k to 10 M, how should the index type be adjusted?

Changing HNSW M from 16 to 64 – how much memory increases and does speed improve or degrade?

How to improve recall without rebuilding the index?