The index lab · Close Enough

Fig 2.4.1Four indexes on one map

Tap the map to move the query Switch between brute force, LSH, IVF and a graph. In every mode the yellow dots are what the index returned, the rings are the true ten nearest, and blue marks what the index had to examine.

1The trade-offs at a glance

Index	Core idea	Speed	Memory	Recall	Updates	Typical home
Flat (brute force)	Check everything	slow at scale	full vectors	exact	trivial	under 1 M vectors, GPUs, re-ranking
k-d / RP trees	Split space into boxes	fine in low d	moderate	drops in high d	rebuild	geo data, Annoy
LSH	Hash so that neighbours collide	fast	many tables	needs many tables	easy	dedup, streaming, theory
IVF	k-means cells, scan a few	fast	vectors + small overhead	tunable	easy	large corpora, object storage
PQ / IVF-PQ	Compress to bytes, compare codes	fast	tiny	lossy; re-rank fixes it	needs trained codebooks	billion scale, GPUs
HNSW	Layered neighbour graph	fastest at high recall	vectors + links in RAM	high	inserts fine, deletes hard	default in vector DBs
DiskANN	Graph laid out for SSD	fast	small RAM	high	harder	billions on one node
ScaNN	Partition + ranking-aware quantization	very fast	small	high	batch rebuilds	Google products

So what is FAISS, exactly?

FAISS (Facebook AI Similarity Search, 2017) is a C++/Python library of index types: Flat, IVF, PQ, HNSW and their combinations, with GPU versions. It is the reference toolkit of the field.

It is not a database: no server, no metadata filters, no replication. Vector databases wrap ideas like these in storage, APIs, filtering and scaling. Some embed FAISS or hnswlib directly.

import faiss
index = faiss.index_factory(768, "IVF4096,PQ64")  # 4096 k-means cells, 64-byte codes
index.train(sample)            # learn centroids and PQ codebooks
index.add(X)                   # encode and file every vector
index.nprobe = 16              # cells scanned per query
D, I = index.search(q[None, :], 10)

2Two things every real system adds

Re-ranking. Fetch the top 100 with the cheap index, then re-score them with full-precision vectors or a cross-encoder.
Filtering. “Only documents this user can see, from 2025.” Surprisingly hard to combine with graph search, and a large part of what differentiates vector databases.