Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Vector Similarity Search: Metrics & Approximate Methods › Code Implementation with FAISS

Michael BrenndoerferJanuary 25, 20269 min read

Language AI HandbookAll chapters

Part 44 of 67Retrieval-Augmented Generation

Chapter 338Vector Similarity Search: Metrics & Approximate Methods › Code Implementation with FAISS

Reading section 7 of 11 · Code Implementation with FAISS · 9 minSection 7 of 11 · 9 min

Section 7 of 11 · 9 min read

Vector Similarity Search: Metrics & Approximate Methods › Code Implementation with FAISSOne section · Sections in this chapter7 / 11 ↓

Sections in this chapter11

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

FAISS (Facebook AI Similarity Search) is the most widely used library for vector similarity search. Developed by Meta AI, it provides efficient implementations of exact search, IVF, HNSW, PQ, and their combinations, with both CPU and GPU backends. Let's use it to compare exact and approximate search on a realistic dataset.

Setting Up and Generating DataLink Copied

We will create a synthetic dataset that mimics the scale and dimensionality of a real embedding collection.

In[12]:

Code

uv pip install faiss-cpu

Out[12]:

Console

/private/tmp/mb-language-ai-modern-plots/books/_quarto_language-ai-handbook/.venv/bin/python: No module named uv

Note: you may need to restart the kernel to use updated packages.

In[3]:

Code

import faiss
import numpy as np

# Simulate 100,000 document embeddings of dimension 384
np.random.seed(42)
n_docs = 100_000
dim = 384
data = np.random.randn(n_docs, dim).astype("float32")

# Normalize to unit vectors (as most embedding models do)
faiss.normalize_L2(data)

# Create 5 query vectors
n_queries = 5
queries = np.random.randn(n_queries, dim).astype("float32")
faiss.normalize_L2(queries)

Our collection occupies about 146 MB, which is modest enough for exact search on a laptop. At 10x or 100x this scale, approximate methods become needed.

FAISS works by building an index object, adding vectors to it, and then calling search() to retrieve the top-k results. Different index types expose different trade-offs. IndexFlatIP is exact inner product search with no index overhead. IndexIVFFlat partitions the space into $K$ clusters and searches only nprobe of them. IndexHNSWFlat builds the navigable small-world graph. All three have the same add() and search() interface, which makes it easy to swap between them as your requirements change.

Exact Search with FAISSLink Copied

FAISS provides IndexFlatIP for exact inner product search and IndexFlatL2 for exact Euclidean distance search. Since our vectors are normalized, inner product is equivalent to cosine similarity.

In[6]:

Code

import time

# Build exact search index (inner product for normalized vectors = cosine similarity)
index_flat = faiss.IndexFlatIP(dim)
index_flat.add(data)

# Search for k=5 nearest neighbors
k = 5
start = time.time()
scores_exact, ids_exact = index_flat.search(queries, k)
time_exact = time.time() - start

The exact search returns the true nearest neighbors with cosine similarities. These results serve as our ground truth for evaluating approximate methods.

Notice that the similarity scores for nearest neighbors are typically in the range of 0.2-0.4 for random synthetic data, considerably lower than what you would see with real text embeddings. This is because random Gaussian vectors in high dimensions tend to be nearly orthogonal to each other by the curse of dimensionality. With real embeddings trained on meaningful text, similarity scores for relevant document pairs routinely reach 0.7-0.9.

Approximate Search with IVFLink Copied

The IVF (Inverted File) index partitions vectors into clusters, then only searches the clusters closest to the query. The nprobe parameter controls how many clusters to search: higher nprobe means higher recall but slower search.

A rule of thumb for choosing the number of clusters is $K \approx \sqrt{n}$ for good recall-speed balance. For 100,000 vectors, this suggests around 316 clusters. Using 100 here is slightly under this guideline, which is fine for demonstration.

In[9]:

Code

# Build IVF index with 100 clusters
n_clusters = 100
quantizer = faiss.IndexFlatIP(dim)
index_ivf = faiss.IndexIVFFlat(
    quantizer, dim, n_clusters, faiss.METRIC_INNER_PRODUCT
)

# IVF requires training on representative data to learn cluster centroids
index_ivf.train(data)
index_ivf.add(data)

# Search with different nprobe values
nprobe_values = [1, 5, 10, 20, 50]
ivf_results = {}

for nprobe in nprobe_values:
    index_ivf.nprobe = nprobe
    start = time.time()
    scores_ivf, ids_ivf = index_ivf.search(queries, k)
    elapsed = time.time() - start

    # Calculate recall against exact results
    recall = np.mean(
        [len(set(ids_ivf[i]) & set(ids_exact[i])) / k for i in range(n_queries)]
    )

    ivf_results[nprobe] = {
        "time_ms": elapsed * 1000,
        "recall": recall,
        "scores": scores_ivf,
        "ids": ids_ivf,
    }

You can see the speed-accuracy trade-off in action. With nprobe=1 (searching only the single nearest cluster), the search is very fast but misses some true neighbors. As nprobe increases, recall improves but search time grows. At nprobe=50 (searching half of all clusters), recall is typically near perfect, but you are examining so many clusters that the speed advantage over exact search is diminishing. In production, you would choose nprobe based on your latency budget, typically achieving recall above 0.95 with nprobe around 5-20% of the total cluster count.

Approximate Search with HNSWLink Copied

FAISS also provides an HNSW index, which builds a navigable graph structure. The key parameter is efSearch, which controls how many candidates to evaluate during the graph traversal. Higher values explore a broader region of the graph, improving recall at the cost of latency.

The M parameter (set during index construction) controls the number of neighbors each node connects to in the graph. Higher M values improve recall and search speed but increase both memory usage and index build time. Common values range from 16 to 64 for most applications.

In[12]:

Code

# Build HNSW index
# M = number of connections per node (higher = better recall, more memory)
M = 32
index_hnsw = faiss.IndexHNSWFlat(dim, M, faiss.METRIC_INNER_PRODUCT)

# Add data (HNSW builds the graph during insertion, no separate training step)
index_hnsw.add(data)

# Search with different efSearch values
ef_values = [16, 32, 64, 128, 256]
hnsw_results = {}

for ef in ef_values:
    index_hnsw.hnsw.efSearch = ef
    start = time.time()
    scores_hnsw, ids_hnsw = index_hnsw.search(queries, k)
    elapsed = time.time() - start

    recall = np.mean(
        [
            len(set(ids_hnsw[i]) & set(ids_exact[i])) / k
            for i in range(n_queries)
        ]
    )

    hnsw_results[ef] = {
        "time_ms": elapsed * 1000,
        "recall": recall,
    }

HNSW generally achieves higher recall at lower latency than IVF for a given collection size, especially at moderate to high recall targets. The next chapter dives deep into exactly how the HNSW graph structure achieves this.

Visualizing the Trade-offLink Copied

Out[13]:

Visualization

Scatter plot with recall on the y-axis and query time on x-axis, comparing IVF and HNSW operating points. — Representative recall@5 versus query time benchmark for IVF and HNSW indexes on 100,000 vectors. Each point represents a different parameter setting (nprobe for IVF, efSearch for HNSW). HNSW reaches high recall faster, giving a better recall-latency frontier. The vertical dashed line marks exact search latency; all approximate methods fall to its left while achieving near-perfect recall.

The plot shows the basic trade-off that defines ANN search. Each point represents a different parameter setting, and the goal is to get as close to the upper-left corner as possible (high recall, low latency). The curve connecting the points for each method is called the Pareto frontier: no operating point on that curve is dominated by another point (you cannot simultaneously improve both recall and speed without changing the index type). In practice, you would benchmark your specific collection and choose the operating point that balances your latency budget with your recall requirements.

Key ParametersLink Copied

The key parameters for the FAISS index implementations are:

n_clusters: The number of clusters (Voronoi cells) to partition the vector space into for the IVF index. A common starting point is $K \approx \sqrt{n}$ , where $n$ is the collection size.
nprobe: The number of closest clusters to search during an IVF query. Higher values increase recall but reduce speed. Typical production values range from 5 to 50.
M: The number of edges (neighbors) per node in the HNSW graph. Controls graph connectivity and memory usage. Values between 16 and 64 cover most use cases.
efSearch: The size of the dynamic candidate list during HNSW search. Higher values improve recall at the cost of latency. Must be at least $k$ (the number of results requested).
efConstruction: A build-time parameter for HNSW that controls the quality of the graph structure. Higher values produce better graphs but increase build time.