Embeddings and vector indexes

• Embedding — a fixed-length vector of floats representing a piece of text (or image) as a point in R^d.
• ANN (approximate nearest neighbour) — search that returns probably the closest vectors much faster than exact search.
• Recall@k — the fraction of the true top-k neighbours that the approximate search actually returned.
• Flat index — brute-force index that compares the query with every stored vector (exact).
• IVF (inverted file) — index that clusters vectors into cells and searches only the nearest cells.
• HNSW (Hierarchical Navigable Small World) — graph-based ANN index.
• PQ (product quantization) — lossy vector compression using per-sub-vector codebooks.
• k-means — clustering algorithm that finds k centroids by alternating assignment and averaging.
• Contrastive loss / InfoNCE — training objective that pulls matching pairs together and pushes non-matching pairs apart.
• Hard negative — a non-matching example that looks very similar to the query, so it is informative to train against.
• BM25 — classic lexical ranking function based on term frequency and inverse document frequency.
• ColBERT — retrieval model that keeps one vector per token and scores by late interaction.
• Pooling — collapsing per-token vectors into one vector (mean, CLS token, last token).
• L2 norm — vector length, sqrt(sum(x_i^2)); normalising divides by it.
• MRL (Matryoshka Representation Learning) — training so that prefixes of the vector are themselves usable embeddings.
• Selectivity / cardinality — what fraction of the corpus a filter matches / how many distinct values a field has.

What an embedding is

An embedding model maps a piece of text to a point in R^d (commonly d = 384 to 1536). The model is trained so that semantic similarity corresponds to geometric proximity: texts about the same thing land close together, unrelated texts land far apart. Retrieval then becomes geometry: embed the query, find the nearest stored vectors.

"How do I reset my password?"   -> [0.12, -0.40, 0.03, ... ]   (d floats)
"I forgot my login credentials" -> [0.10, -0.37, 0.05, ... ]   close  (cosine ~ 0.82)
"Best pizza in Naples"          -> [-0.51, 0.22, 0.60, ... ]   far    (cosine ~ 0.05)

(Illustrative values.)

The property retrieval specifically needs

The space must be good across the query-document gap. A short question (“why is my build slow”) and a long passage that answers it (three paragraphs on caching and CI) share few words, yet must embed near each other. A model that only clusters similar-looking text (paraphrase similarity) is not enough; retrieval models are trained for question -> answering passage relevance (asymmetric search).

How the space gets this property — contrastive training

Training data is pairs (query, relevant passage). In a batch of B pairs, each query should score highest against its own passage and lower against the other B-1 passages in the batch (the in-batch negatives). The InfoNCE loss for one query q with positive p+ is:

L = -log  exp(sim(q, p+) / τ)  /  sum over all passages p in batch of exp(sim(q, p) / τ)

τ is a temperature controlling how sharply the model distinguishes near-misses. Quality depends heavily on hard negatives (passages that are topically close but do not answer the question), mined with BM25 or an earlier model, because easy negatives teach little.

import torch, torch.nn.functional as F

def info_nce(q, p, temperature=0.05):         # q, p: [B, d]; row i of p is the positive for row i of q
    q, p = F.normalize(q, dim=-1), F.normalize(p, dim=-1)
    logits = q @ p.T / temperature            # [B, B] similarity matrix; diagonal = positives
    labels = torch.arange(q.size(0), device=q.device)
    return F.cross_entropy(logits, labels)    # each row: classify which column is the positive

Walkthrough: the matrix product scores every query against every passage in the batch; cross-entropy with the diagonal as the correct class means “pick your own passage out of B”, which pulls true pairs together and pushes the rest apart.

Practical consequences

• A generative LLM’s hidden states are not automatically a good retrieval space. Next-token prediction does not force similar meanings to be geometrically close; a dedicated contrastive stage does.
• Instruction/prefix conventions matter. Many models expect query: ... / passage: ... prefixes or an instruction string; omitting them quietly degrades quality.
• The space is model-specific. Vectors from model A and model B are not comparable. Changing the embedding model means re-embedding the whole corpus.
• Domain shift hurts. A general model on legal or medical text, code, or another language may separate concepts poorly; evaluate on your own queries (see Evaluating retrieval and RAG), and consider fine-tuning.
• Long inputs get blurred. One vector per passage averages over everything in it, so chunk size trades specificity against context (see Chunking and retrieval quality).

Architectures side by side

BI-ENCODER                                   CROSS-ENCODER
query -> [Transformer] -> vq --+             [CLS] query [SEP] document [SEP]
                               +- dot(vq,vd)              |
doc   -> [Transformer] -> vd --+             [Transformer]  (query and doc tokens attend to each other)
(doc side computed offline, once)                         |
                                                   relevance score

• Bi-encoder encodes query and document independently; relevance is a cheap vector operation. Documents are encoded once at index time, so millions can be pre-computed and searched with an ANN index. The cost: there is no interaction between query and document inside the model, so subtle relevance signals (negation, which entity a question is about, numeric constraints) are compressed into a single vector and partly lost.
• Cross-encoder concatenates query and document and passes them together through the transformer, which outputs one score. Every query token can attend to every document token, so accuracy is much higher. But it must run once per (query, document) pair at query time, and nothing can be pre-computed, so it cannot scan a corpus.

Cost arithmetic

For a corpus of N = 10M passages and one query:

Approach	Model forward passes at query time	Rough latency
Cross-encoder over everything	10,000,000	hours
Bi-encoder + ANN	1 (the query) + an index lookup	milliseconds
Bi-encoder top-100 -> cross-encoder re-rank	1 + 100	tens to a few hundred ms on a GPU

The standard two-stage pipeline

from sentence_transformers import SentenceTransformer, CrossEncoder

bi = SentenceTransformer("BAAI/bge-base-en-v1.5")
ce = CrossEncoder("cross-encoder/ms-marco-MiniLM-L-6-v2")

# Index time: encode the corpus once
doc_vecs = bi.encode(docs, normalize_embeddings=True)

# Query time
q = bi.encode(query, normalize_embeddings=True)
cand = (doc_vecs @ q).argsort()[::-1][:100]                       # stage 1: cheap, recall-oriented
scores = ce.predict([(query, docs[i]) for i in cand])             # stage 2: expensive, precision-oriented
top = [cand[i] for i in scores.argsort()[::-1][:10]]

Stage 1 is tuned for recall (the right answer must be somewhere in the 100), stage 2 for precision (put it first). If the correct document is not in the candidate set, the re-ranker can never fix it, so measure recall@100 of stage 1 separately.

ColBERT — late interaction as the middle ground

ColBERT keeps one vector per token for query and document, encoded independently (so documents can still be pre-computed), then scores with MaxSim: for each query token, take its best-matching document token, and sum those maxima.

score(q, d) = sum over query tokens i of  max over doc tokens j of  dot(q_i, d_j)

This restores much of the token-level interaction of a cross-encoder at close to bi-encoder serving cost, at the price of a larger index (a vector per token instead of per passage), mitigated by compression.

When to use which

• Bi-encoder only: latency-critical, huge corpus, “good enough” relevance.
• Add a cross-encoder re-ranker: when top-5 precision matters (RAG context windows are small and every irrelevant chunk hurts) and a ~100-300 ms budget exists.
• Cross-encoder as a labeller/evaluator offline, to build training data or judge retrieval quality.

The geometry

Many retrieval models are trained, or recommended for use, with L2-normalized vectors: every vector divided by its length so |v| = 1. All vectors then lie on the unit hypersphere, which makes three common measures collapse into one ranking:

cosine(a, b)  = a·b / (|a||b|)       = a·b                    (denominator is 1)
‖a − b‖²      = |a|² + |b|² − 2a·b   = 2 − 2(a·b)             (squared Euclidean decreases as dot increases)

So for unit vectors, maximising dot product, maximising cosine, and minimising Euclidean distance all return the same neighbours in the same order. An index built for inner product (IP) or for L2 gives identical results.

Without normalisation

Raw dot product a·b = |a||b|cos θ lets vector magnitude influence the score: a long vector can beat a better-aligned short one.

import numpy as np
q = np.array([1.0, 0.0])
a = np.array([0.9, 0.1])        # nearly the same direction as q, short
b = np.array([3.0, 3.0])        # 45 degrees away, but long

print(q @ a, q @ b)             # 0.9  3.0   -> dot product prefers b
cos = lambda x, y: x @ y / (np.linalg.norm(x) * np.linalg.norm(y))
print(cos(q, a), cos(q, b))     # 0.99 0.71  -> cosine prefers a, the better-aligned one

Magnitude sometimes carries signal (confidence, popularity in recommenders), but for text similarity it is mostly noise, for example longer passages having larger norms.

Practical rules

1. Use the metric the model card specifies. Models trained with cosine should be queried with cosine (or normalised + IP).
2. Normalise at both index time and query time, or at neither. Normalising only one side gives meaningless scores.
3. Normalise once, store normalised, then use inner product everywhere; it is faster than computing cosine each time and works with FAISS IndexFlatIP and HNSW IP.
4. Mind the pooling step. Models differ (mean pooling, CLS token, last token). Normalisation comes after pooling; the wrong pooling gives poor vectors no normalisation can fix.
5. Matryoshka truncation requires re-normalising the shortened vector.

import numpy as np

def l2norm(x, eps=1e-12):
    return x / np.maximum(np.linalg.norm(x, axis=-1, keepdims=True), eps)

index_vecs = l2norm(raw_doc_vecs).astype("float32")   # store these
query_vec  = l2norm(raw_query_vec).astype("float32")  # same function at query time

Pitfall

A vector DB configured for cosine on already-normalised data is fine. One configured for L2 on unnormalised data from a cosine-trained model gives subtly worse rankings that look plausible, so the problem goes unnoticed. As a sanity test, check that a known-relevant pair scores in the range the model documentation expects.

The problem it solves

A flat (brute-force) index compares the query against all N vectors: exact, but O(N·d) per query. At tens of millions of vectors that is too slow. IVF is the oldest and simplest approximate-nearest-neighbour (ANN) trick: don’t look everywhere, look only in the few regions of space where the answer is likely to be. The name comes from the classic text-search inverted file: a map from a key (here a cluster id, there a word) to the list of items that belong to it.

How it works

1. Train (once). Run k-means on a sample of the vectors to find nlist centroids. Each centroid defines a cell (a Voronoi region): every point in space belongs to the cell of its nearest centroid.

2. Add (index time). For every vector, find its nearest centroid and append (id, vector) to that centroid’s inverted list.

3. Search (query time).

1. Compare the query to all nlist centroids (cheap: nlist ≪ N).
2. Take the nprobe closest centroids.
3. Scan every vector in those nprobe lists exactly and return the top-k.

2-D picture, nlist = 4, nprobe = 1:

        cell A          |        cell B
     .  .   *A          |    *B   .   .
   .   .  .             |      .  .  .
  ---------------------+---------------------
        cell C          |        cell D
     .   *C  . .        |   .  *D   .
       .  .   Q         |      .    .  .        Q = query -> nearest centroid C
                                                 scan only cell C (~N/4 vectors)

Miss case: Q sits near the C|D boundary. Its true nearest neighbour is a
point just across the border in cell D. With nprobe = 1 we never look there.

Cost per query is roughly:

nlist·d   (centroid comparisons)   +   nprobe · (N / nlist) · d   (list scans, if lists are balanced)

With N = 10M, nlist = 4096, nprobe = 16: about 4k + 16·2.4k ≈ 43k distance computations instead of 10M, a ~230x reduction.

Example (FAISS)

import faiss, numpy as np

d, N = 768, 1_000_000
xb = np.random.rand(N, d).astype("float32")
xq = np.random.rand(10, d).astype("float32")

nlist = 1024                                  # about sqrt(N) .. 4*sqrt(N)
quantizer = faiss.IndexFlatL2(d)              # the "coarse quantizer": holds the centroids
index = faiss.IndexIVFFlat(quantizer, d, nlist)

index.train(xb[:100_000])                     # k-means on a sample (needs >= ~40 * nlist points)
index.add(xb)                                 # assign every vector to a list

index.nprobe = 16                             # query-time dial
D, I = index.search(xq, k=10)

# Measure recall against the exact answer before trusting any setting
exact = faiss.IndexFlatL2(d); exact.add(xb)
_, I_true = exact.search(xq, 10)
recall = np.mean([len(set(a) & set(b)) / 10 for a, b in zip(I, I_true)])

Walkthrough: IndexIVFFlat stores full vectors inside the lists (“Flat” = no compression). train learns the centroids; add routes each vector; nprobe is set per index object and can be changed at any time without rebuilding.

The tuning knobs

Knob	Set when	Effect	Trade-off
nlist	Build	Number of cells.	More cells -> shorter lists -> cheaper scans, but more centroid comparisons, more training time, and more boundaries to miss across.
nprobe	Query	Cells scanned per query.	Higher -> higher recall, higher latency. nprobe = nlist is exact brute force.
Training sample size	Build	Quality of the centroids.	Too small -> unbalanced, poor cells. Use at least ~30-100 points per centroid.
Coarse quantizer type	Build	How centroids are searched.	Flat is fine for nlist up to ~tens of thousands; use an HNSW quantizer (IVF…_HNSW32) for very large nlist.
Compression of list contents	Build	IVFFlat (full), IVFSQ8 (8-bit), IVFPQ (product quantization).	Memory vs accuracy (see PQ below).

Choosing nlist. The classic rule is nlist ≈ sqrt(N) up to 4·sqrt(N), balancing the two cost terms above (the centroid scan and the list scan are equal around nlist = sqrt(N·nprobe)). In practice: ~1k-4k for 1M vectors, 16k-64k for 100M. Bigger is better for latency but needs a larger nprobe for the same recall, so tune the pair together.

Choosing nprobe. Plot recall@k and latency against nprobe (1, 2, 4, 8, 16, 32, 64…) on real queries and pick the knee. Typical working values are 1-10% of nlist. Recall rises quickly at first, then saturates; the last few percent are expensive.

nprobe   recall@10   latency
   1       0.55       0.3 ms
   8       0.87       1.2 ms
  32       0.97       4.1 ms
 128       0.995     15   ms      <- diminishing returns

(Illustrative numbers; the shape is what matters.)

Why recall is lost, and what makes it worse

• Boundary effect. The true neighbour lives in a different cell than the query’s nearest centroid. Raising nprobe is the fix. This gets worse in high dimensions, where many points sit near the boundaries of many cells at once.
• Clustering mismatch. k-means assumes roughly spherical, similarly sized clusters. Heavily skewed data produces some huge lists (slow queries, since scan cost is set by the biggest probed list) and many tiny ones.
• Distribution drift. Centroids are fixed after training. If new data differs from the training sample (new language, new domain, a new embedding model), lists become unbalanced and recall silently drops. Retrain and re-add periodically, and monitor list-size skew.
• Metric mismatch. For cosine similarity, normalise vectors and use inner product; k-means with L2 on unnormalised vectors clusters by magnitude as well as direction.

Pitfalls

• Forgetting to train before add (an error in FAISS) or training on too few or unrepresentative points.
• Evaluating on queries drawn from the training sample, which flatters recall; hold queries out.
• Filters and deletes. A metadata filter applied after probing can leave fewer than k results; a filter applied before may need a larger nprobe. Deleting vectors leaves stale centroids but is otherwise fine.
• No incremental training. Adding data is cheap; re-clustering is a full rebuild.

When to choose IVF

	IVF	HNSW
Memory	Low (especially with PQ)	High (graph links, ~100-200 bytes extra per vector)
Build time	Fast (k-means + assign)	Slow (graph construction)
Recall at low latency	Good, needs tuning	Usually better out of the box
Updates	Cheap adds; periodic retrain	Cheap adds; deletes awkward
Disk-friendly	Yes: probe a few lists, read sequentially	Poor: random access across the graph

Choose IVF (usually IVF-PQ) when the dataset is huge relative to RAM, when memory cost dominates, or when the index lives on disk or SSD; choose HNSW when RAM is available and the best recall at low latency matters. IVF is also the usual first stage in billion-scale systems, with a re-ranking step on full-precision vectors afterwards.

Why approximate at all

Finding the exact nearest neighbour by brute force (a flat index) means comparing the query against every stored vector — O(n) per query. That is fine for thousands of vectors and prohibitively slow for millions on every request. ANN indexes such as HNSW pre-build a structure at indexing time so a query touches only a small fraction of the data, at the cost of occasionally returning a very close neighbour instead of the literally closest one. That small, measurable recall loss in exchange for orders-of-magnitude lower latency is a deliberate engineering choice, not a defect: most production search and RAG systems at real scale run entirely on ANN indexes, and you control the trade-off with the knobs below.

The idea: navigable small worlds, plus a skip-list hierarchy

HNSW (Hierarchical Navigable Small World) builds a proximity graph: each vector is a node, linked to some of its near neighbours. To search, you start somewhere and greedily walk: look at the current node’s neighbours, move to whichever is closest to the query, repeat until no neighbour improves. On a well-built graph this reaches the neighbourhood of the answer in a handful of hops, because the graph has “small world” structure (a few long-range links make any region reachable quickly).

A single flat graph has a weakness: greedy walking from an arbitrary start crosses the space in many small steps. HNSW adds layers, like a skip list:

layer 2:   A ─────────────────────── F                   few nodes, long-range links
            \                       /
layer 1:   A ──── C ──── E ──────── F ── H               more nodes, medium links
            \     |      |          |    |
layer 0:   A─B─C─D─E─G─...(every vector)...─Z            all nodes, short links to near neighbours

search for Q:  enter at top layer, greedy-walk to the closest node (coarse jump),
               drop to the next layer starting from that node, walk again (finer),
               ...at layer 0 run a wider beam search of width efSearch, return top-k.

Upper layers contain a random, exponentially thinning subset of vectors, so the top layers cover the space with a few long edges and the bottom layer gives precise local resolution.

Search in more detail

At layer 0 the search keeps a candidate list of size efSearch: a priority queue of the best nodes seen so far. It repeatedly expands the closest unexpanded candidate (visiting its neighbours), inserts any that beat the current worst, and stops when the closest unexpanded candidate is farther than the worst in the list. The top k of the list are returned. Larger efSearch means a wider beam, so fewer local optima are missed.

The knobs

Knob	When	Effect	Cost
M	Build	Max neighbours per node per layer (layer 0 usually allows 2*M). Typical 8-64.	More recall, more memory (links), slower build. Higher-dimensional or harder data needs larger M.
efConstruction	Build	Beam width during insertion. Typical 100-500.	Better graph quality, slower build. Set high once; it costs nothing at query time.
efSearch	Query	Beam width during search. Must be >= k.	The recall/latency dial; tune it per workload without rebuilding.

Example (hnswlib)

import hnswlib, numpy as np

d, N = 384, 200_000
data = np.random.rand(N, d).astype("float32")

index = hnswlib.Index(space="cosine", dim=d)      # "l2", "ip", or "cosine"
index.init_index(max_elements=N, M=16, ef_construction=200)
index.add_items(data, np.arange(N))               # incremental inserts; no training step

index.set_ef(64)                                  # efSearch; try 32, 64, 128, 256 and measure recall
labels, dists = index.knn_query(data[:5], k=10)

Why it became the default

• Excellent recall at low latency, often 95-99% recall in about a millisecond for millions of vectors.
• No training step and incremental inserts: unlike IVF, you do not need a representative sample up front, and drift does not invalidate centroids.
• Graceful degradation: raising efSearch smoothly buys recall.
• Search cost grows roughly logarithmically with N.

Costs and limits

• Memory. The full-precision vectors must be resident in RAM, plus the links: roughly d*4 bytes for the vector plus about M*2*4 bytes (layer 0) for edges per node. For 100M vectors at 768 dims that is on the order of 300+ GB, which is why billion-scale systems combine graphs with compression or use disk-based variants (DiskANN/Vamana).
• Build time is slow compared with IVF and scales with efConstruction.
• Deletions are awkward. Removing a node breaks the paths other nodes relied on; most implementations mark the node as deleted (tombstone) and rebuild periodically. Heavy delete/update workloads degrade recall.
• Random memory access. Walking the graph jumps around memory, so it is cache-unfriendly and poor for disk, compared with IVF’s sequential list scans.
• Filtering is tricky (see the filtering concept below).

Insertion, one vector at a time

There is no separate “build” pass; the graph is constructed by inserting vectors one at a time, which is also why HNSW supports incremental inserts (unlike IVF’s upfront k-means training):

1. Pick the new node’s top layer. Each vector is assigned a random max layer by sampling an exponential distribution: level = floor(-ln(rand) * mL) with mL = 1 / ln(M). Most vectors land only at layer 0 (which contains every vector); a shrinking fraction reach layer 1, 2, and so on. This is what makes the structure “hierarchical.”
2. Descend from the entry point, searching greedily. Starting at the graph’s single global entry point (a node on the highest layer), greedily walk toward the new vector layer by layer, moving to whichever neighbour is closest until no neighbour improves. Above the new node’s own top layer a beam of 1 is enough (we only need a good starting point). Once a layer is exhausted, drop to the layer below and continue from where you ended.
3. Search wider and link at the new node’s own layer and below. From its assigned top layer down to layer 0, run a beam search with breadth efConstruction to collect candidates, select up to M of them, and connect the new node to them bidirectionally.
4. Prune with a heuristic, not just “keep the M closest.” If a neighbour’s degree now exceeds its cap (M per layer, typically 2*M at layer 0), HNSW’s neighbour-selection heuristic reconsiders its links. It discards a candidate if it is closer to an already-selected neighbour than to the node itself, since the already-selected neighbour covers that direction. This favours spread-out, diverse connections over a tight local clique, which keeps greedy search able to jump across the space instead of getting stuck in one neighbourhood. That is what makes the graph “navigable.”
5. Update the entry point if the new node’s layer is higher than the current maximum.

The pruning heuristic in code

def select_neighbors(q, candidates, M, dist):
    """candidates: list of (distance_to_q, node). Returns up to M diverse neighbours."""
    selected = []
    for d_qc, c in sorted(candidates):                  # closest to q first
        # keep c only if it is closer to q than to every neighbour already selected
        if all(d_qc < dist(c, s) for s in selected):
            selected.append(c)
        if len(selected) == M:
            break
    return selected

Why this matters: suppose a dense cluster of ten near-duplicates sits to the left of q and one lone point sits to the right. “Keep the M closest” would link only to the cluster, leaving no edge pointing right. The heuristic keeps one cluster member (the others are closer to it than to q, so they are redundant) and the right-hand point, giving the graph edges in several directions.

Worked picture

insert X (assigned top layer = 1)

layer 2:  entry E ──────────── (beam=1) greedy walk ──> best node P2   (X not present at layer 2)
layer 1:  start at P2, beam efConstruction  -> candidates -> pick <= M, link X <-> them
layer 0:  start at best of layer 1, beam efConstruction -> pick <= 2M, link X <-> them
          for each neighbour N that now exceeds its cap: re-run select_neighbors(N, N's links + X)

How the build knobs act on this process

M caps how many edges each insertion creates (and each node keeps); efConstruction sets how thorough each insertion’s candidate search is. Together they trade build time for graph quality, and graph quality sets the best recall you can ever reach at query time, however large efSearch is.

Practical consequences

• Insertion order matters slightly: the first vectors seed the structure. Inserting data sorted by cluster can produce worse graphs than shuffled order; shuffle before bulk loading.
• Parallel builds are common (threads insert concurrently with locks), at the cost of non-determinism.
• Quality check: build, then measure recall@k against a flat index on held-out queries. If recall plateaus below target as efSearch grows, the graph itself is limiting: raise M or efConstruction and rebuild.

The problem

A 768-dim float32 vector takes 3,072 bytes. 1 billion vectors = about 3 TB of RAM, which is unaffordable. PQ shrinks each vector to tens of bytes while still allowing approximate distance computation.

How it works

1. Split each d-dim vector into m contiguous sub-vectors of dimension d/m.
2. Train a codebook per subspace: run k-means with k = 256 on that subspace’s sub-vectors, giving 256 centroids (a codebook).
3. Encode each vector by replacing every sub-vector with the 1-byte id of its nearest centroid. The vector becomes m bytes.

vector (d = 768, 3072 bytes)
 [ sub 1 | sub 2 | ... | sub 96 ]      m = 96 sub-vectors of 8 dims each
     |       |             |
   nearest  nearest      nearest        centroid in that subspace's 256-entry codebook
     |       |             |
   [ 17  |  203  | ... |  88 ]         96 bytes  ->  32x smaller

Computing distances without decompressing — ADC

At query time (asymmetric distance computation) the query stays uncompressed:

1. For each subspace j, compute the distance from the query’s sub-vector to all 256 centroids and store them in a lookup table T[j][c] (a m x 256 table, built once per query).
2. The approximate distance to a stored vector with codes [c1..cm] is just sum_j T[j][c_j]: m table lookups and adds, no floating-point vector arithmetic.

import faiss, numpy as np

d, N, m = 768, 1_000_000, 96                         # d must be divisible by m
xb = np.random.rand(N, d).astype("float32")

pq = faiss.IndexPQ(d, m, 8)                          # 8 bits per code = 256 centroids per subspace
pq.train(xb[:100_000])
pq.add(xb)
print(pq.sa_code_size(), "bytes per vector")         # 96

# Typical large-scale combination: IVF narrows the search, PQ compresses the lists
nlist = 1024
quantizer = faiss.IndexFlatL2(d)
ivfpq = faiss.IndexIVFPQ(quantizer, d, nlist, m, 8)
ivfpq.train(xb[:200_000]); ivfpq.add(xb)
ivfpq.nprobe = 16

What it costs

• It is lossy. Each sub-vector is replaced by its centroid; the distance error lowers recall. Fewer bytes (smaller m) mean more error. The compression ratio and the accuracy trade directly: m = 96 bytes/vector is a common balance; m = 16 is extremely compact and noticeably less accurate.
• Training needed. Codebooks are learned from a sample; a mismatched sample gives poor codes, and a model change means retraining.
• Distances are approximate, so the ranking among near candidates can be off, even if the right items are in the top 100.

The standard fix: re-scoring

Use PQ to find, say, the top 200 candidates cheaply, then fetch the full-precision vectors (from disk or a slower store) for just those 200 and re-rank them exactly. This recovers most of the lost accuracy while keeping RAM for the compressed codes only.

Alternatives and variants

Method	Compression	Accuracy loss	Notes
Scalar quantization (float32 -> int8)	~4x	Low	Simple, fast SIMD, little tuning
Product quantization	16-64x or more	Moderate	Needs training; best memory per vector
Binary quantization (1 bit per dim)	32x	High alone	Hamming distance via XOR + popcount is extremely fast; works best on high-dim, normalised vectors and with re-scoring
OPQ	Like PQ	Lower than PQ	Learns a rotation first so sub-vectors are better balanced
Matryoshka truncation	2-12x	Depends	Drops dimensions instead of precision (see below); can combine with the others

Choosing

If vectors fit in RAM, prefer HNSW or flat with scalar quantization. When they do not, IVF-PQ with re-scoring is the classic billion-scale recipe, and it composes well with disk storage.

Why the naive approaches fail

Real queries are rarely “nearest vectors, period”; they are “nearest vectors where tenant = 42 AND date > 2024”.

• Pre-filter, then search. Restrict to matching vectors first, then do ANN. But the index structure was built over all vectors. Under HNSW, a tiny matching subset is a scattered sliver of the graph whose nodes are mostly linked to non-matching nodes, so the search cannot walk between them. Under IVF, the matching points may be spread thinly across cells.
• Post-filter. Run ANN for top-k, then drop non-matching results. If the filter keeps 1% of the data, a top-10 search returns on average 0.1 usable results, often none.

corpus = 1,000,000 vectors, filter keeps 0.5% (5,000 vectors)

post-filter, k = 10:   expected hits after filtering = 10 * 0.005 = 0.05   -> usually empty
over-fetch k' = k/0.005 = 2000 candidates, then filter -> works but expensive and approximate

Approaches that work

• Filter-aware ANN — the index traverses the graph but only returns nodes passing the predicate (and keeps exploring through non-matching nodes so it does not get stuck). Used by Qdrant, Weaviate, pgvector (with iterative scan), Elasticsearch and others. Works well until the filter is extremely selective.
• Partitioned indexes — a separate index per high-cardinality filter value (per tenant, per language), so the filter becomes index selection. Very robust; costs overhead for many tiny indexes.
• Over-fetch and post-filter — retrieve k / selectivity candidates, then filter. Fine when the filter keeps a reasonable fraction.
• Fall back to exact search — when the filtered set is small (a few thousand vectors), use an inverted/B-tree index to find matching ids and brute-force just those vectors. This is exact and cheap, and good engines choose it automatically with a query planner.
• Filterable graph variants (e.g. per-attribute subgraphs or extra edges) — an active research area with growing production support.

A decision procedure

estimate selectivity s of the filter (matches / total)
  s > ~30%        -> filter-aware ANN or post-filter with small over-fetch
  1% < s < 30%    -> filter-aware ANN with higher efSearch, or over-fetch
  s < ~1% (or matched set < ~10k vectors)  -> brute force over the matched set
high-cardinality key used in every query (tenant_id) -> partition by it

Measure cardinality and selectivity, don’t assume

• Cardinality — how many distinct values the field takes across the corpus. status (active/inactive) is low cardinality; tenant_id across 50,000 tenants is high cardinality.
• Selectivity — what fraction of the corpus a specific filter value matches. tenant_id = 42 out of 50,000 evenly sized tenants is highly selective (~0.002% of the corpus); language = "en" on a mostly-English corpus is not.

High cardinality tends to produce high-selectivity filters, which is the dangerous combination: if tenant 42’s vectors are a tiny, scattered sliver of the HNSW graph, its nodes are mostly linked to other tenants’ vectors, so a filter-aware greedy search can fail to find enough true neighbours and recall collapses even though the right vectors are in the index. (The IVF analogue: the filter is fine only if that tenant’s vectors happen to cluster into a few cells; otherwise you probe mostly-empty cells.)

How to test for it

This failure is invisible with match_all and only shows up with realistic filters. Evaluate recall by comparing filtered ANN results to exact filtered search, per filter value:

def filtered_recall(index, flat_vectors, ids_by_filter, queries, k=10):
    out = {}
    for value, ids in ids_by_filter.items():
        sub = flat_vectors[ids]
        for q in queries:
            truth = set(ids[(sub @ q).argsort()[::-1][:k]])
            got = set(index.search(q, k, filter=value))
            out.setdefault(value, []).append(len(truth & got) / k)
    return {v: sum(r) / len(r) for v, r in out.items()}      # look at the worst filter values, not the mean

Report the worst and 10th-percentile filter values; an overall average hides the narrow filters that fail.

The trade-off

Dimensionality d is a cost multiplier on everything:

storage   = N × d × bytes_per_value
compute   = O(d) per distance comparison
RAM for an ANN index scales the same way

d	10M vectors, float32	10M vectors, int8
384	15 GB	3.8 GB
768	31 GB	7.7 GB
1536	61 GB	15 GB
3072	123 GB	31 GB

Higher d gives more capacity to separate concepts, but returns diminish: moving from 384 to 1536 dims typically improves retrieval benchmarks by a few points, not 4x. Common retrieval models sit at 384-1536. The right d is the smallest that meets your recall target on your data.

Matryoshka Representation Learning (MRL)

MRL trains the model so that the first k dimensions of its output are themselves a good embedding, for several nested sizes (e.g. 64, 128, 256, 512, 1024). The training loss is applied to each prefix at once, so information is ordered by importance, like nested Russian dolls.

import torch.nn.functional as F

dims = [64, 128, 256, 512, 1024]
def mrl_loss(q, p, temperature=0.05):
    total = 0
    for k in dims:                              # same contrastive loss on every prefix
        total = total + info_nce(F.normalize(q[:, :k], dim=-1),
                                 F.normalize(p[:, :k], dim=-1), temperature)
    return total / len(dims)

Using it: truncate and re-normalise

import numpy as np

def truncate(vecs, k):
    v = vecs[:, :k]
    return v / np.linalg.norm(v, axis=1, keepdims=True)    # re-normalise after truncating!

full = embed(corpus)                                       # e.g. 1536 dims from an MRL-trained model
small = truncate(full, 256)                                # 6x less memory

(OpenAI’s text-embedding-3 models and several open models expose a dimensions parameter that does this properly.) Truncating a non-MRL model’s vectors also “works” but loses far more quality.

A two-stage search that uses it

1. Store the full 1536-dim vectors on disk or in a cheap tier; keep the 256-dim prefixes in the fast ANN index.
2. Search with the 256-dim prefix to get the top ~200 candidates.
3. Re-rank those 200 with the full-dimensional dot product.

This decouples the storage decision from the search speed decision without running two models, and composes with quantization (e.g. 256 dims at int8 is 24x smaller than 1536 at float32).

Pitfalls

• Truncate only models trained for it, and only to the nested sizes they report quality for.
• Always re-normalise after truncation, or cosine/IP scores are distorted.
• Mixed dimensions in one index are not comparable; pick one and re-embed queries the same way.
• Measure on your corpus: published benchmark curves (quality vs d) are averages; your domain may need more or fewer dims.