Retrieval-Augmented Generation (RAG) Questions

Short answer

Pick by the shape of the workload, not by a benchmark headline. For a retrieval service whose corpus changes and fits in RAM, an HNSW graph index (hnswlib, or FAISS's HNSW index) is the usual default. When the vectors do not fit in memory, FAISS IVF-PQ (compressed vectors) is the tool. For a read-only index that many processes share, Annoy's memory-mapped file is the simplest fit. Use flat (exact) search while the corpus is small enough to scan, and use FAISS's GPU indexes when query volume or build time is the bottleneck.

Terms used below: an ANN (approximate nearest neighbour) index returns close vectors without comparing against every vector, and gives up some recall (the share of the true top-k it returns) for speed. IVF (inverted file) clusters the vectors and, at query time, scans only the nprobe nearest clusters. PQ (product quantization) compresses each vector into a few bytes. HNSW (hierarchical navigable small world) is a layered neighbour graph searched greedily. Recall@10 is the share of the true 10 nearest neighbours that a search returns, and p95 latency is the query time that 95 percent of queries stay under. A training step means fitting k-means (repeatedly assigning vectors to the nearest cluster centre and moving each centre to the average of its vectors) on a sample before vectors can be added. A memory-mapped file is read by the operating system on demand and shared between processes, and resident memory is the RAM a process actually holds. To re-rank a shortlist is to take the top candidates from the compressed index and rescore them with the full vectors.

For a first choice, two questions decide most cases: does the index fit in RAM, and does the corpus change? Every other choice below refines the answers to those two.

The four options on your axes

The HNSW knobs, in plain terms: M is the number of links kept per vector (more links raise recall and memory and slow the build); ef_construction is the size of the candidate list used while inserting (larger gives a better graph and a slower build, with no cost at query time); ef is the size of the candidate list during a query (larger raises recall and latency, and it must be at least the number of results requested). Annoy builds n_trees binary trees: each tree splits the vectors again and again with a random hyperplane until the pieces are small, a query descends all the trees and merges the pieces it reaches, and more trees raise recall and memory. The trees are built over the whole set and written once, so there is no place to add or remove a single vector without a rebuild.

Those update and GPU statements come from the projects' own READMEs and FAISS's wiki; other versions may differ, so check the version you deploy.

Memory arithmetic

Take 100 million vectors with $d = 768$ dimensions. Flat float32 costs $4d$ bytes per vector. IVF-PQ with 64 sub-quantizers of 8 bits costs 64 code bytes plus an 8-byte id. HNSW with $M = 32$ adds about $2M \times 4$ bytes of level-0 links per vector: in hnswlib the bottom layer allows up to $2M$ links per vector, and each link is the 4-byte integer id of a neighbour (upper layers ignored, exact overhead differs by implementation).

GiB = 2**30
N, d = 100_000_000, 768
flat = N * 4 * d
ivfpq = N * (64 + 8)            # m=64 sub-quantizers x 8 bits = 64 bytes code + 8-byte id
hnsw_flat = N * (4 * d + 2 * 32 * 4)   # float32 vector + level-0 links (2*M neighbours, 4 bytes each), M=32; upper levels ignored
hnsw_pq_links = N * (64 + 2 * 32 * 4)  # same links but vectors stored as 64-byte PQ codes
for name, b in (("flat float32", flat), ("IVF-PQ m=64 8-bit", ivfpq),
                ("HNSW M=32 on float32 vectors", hnsw_flat), ("HNSW M=32 on 64-byte PQ codes", hnsw_pq_links)):
    print(f"{name:32s} {b/GiB:8.1f} GiB  {b/N:7.1f} bytes/vector")

Output:

flat float32                        286.1 GiB   3072.0 bytes/vector
IVF-PQ m=64 8-bit                     6.7 GiB     72.0 bytes/vector
HNSW M=32 on float32 vectors        309.9 GiB   3328.0 bytes/vector
HNSW M=32 on 64-byte PQ codes        29.8 GiB    320.0 bytes/vector

The compressed index is roughly 43 times smaller than flat (286.1 / 6.7). HNSW on raw vectors is the largest. Pairing graph links with compressed vectors is possible but then distances are approximate and you normally re-rank. These are byte counts from arithmetic, not measured process memory (allocator overhead is extra).

How a PQ code is built, and what a recall sweep looks like

Product quantization cuts each vector into equal pieces, learns a small codebook of typical pieces for each position with k-means, and stores for every vector only the id of the nearest codebook entry per piece. With 768 dimensions and 64 sub-quantizers of 8 bits, each piece has 12 numbers, each codebook has 256 entries (an 8-bit id), and a vector becomes 64 bytes. The second half of the program below sweeps the one knob of an IVF index, nprobe (how many of the nearest clusters are scanned), and prints recall@10 against the share of vectors scanned on synthetic clustered vectors. Real data is harder, so the curve to produce is the one on your own embeddings; the shape to expect is recall rising quickly and then flattening while the work keeps growing.

import os
os.environ["OMP_NUM_THREADS"] = "1"
import numpy as np
from sklearn.cluster import KMeans

# Product quantization bookkeeping for d = 768 and 64 sub-quantizers of 8 bits.
d, m, bits = 768, 64, 8
print(f"each vector is cut into {m} pieces of {d // m} numbers; each piece is replaced by the id (0..{2**bits - 1}) of the nearest of {2**bits} learned piece-centres: {m} bytes")
print(f"the codebooks themselves: {m} x {2**bits} x {d // m} floats x 4 bytes = {m * 2**bits * (d // m) * 4 / 1e6:.2f} MB, shared by all vectors")

# Recall versus work for an IVF index (clusters, scan the nearest `nprobe` clusters), on synthetic clustered vectors.
rng = np.random.default_rng(0)
n, dim, nq, nlist = 20000, 32, 200, 100
centres = rng.standard_normal((60, dim))
X = centres[rng.integers(0, 60, n)] + 0.9 * rng.standard_normal((n, dim))
Q = X[rng.choice(n, nq, replace=False)] + 0.3 * rng.standard_normal((nq, dim))
km = KMeans(nlist, n_init=1, max_iter=20, random_state=0, algorithm="lloyd").fit(X)
d2 = lambda A, B: (A**2).sum(1)[:, None] - 2 * A @ B.T + (B**2).sum(1)[None, :]
truth = np.argsort(d2(Q, X), axis=1)[:, :10]
dc = d2(Q, km.cluster_centers_)
print("nprobe  recall@10  share of vectors scanned")
for nprobe in (1, 2, 4, 8, 16, 32):
    rec, scan = [], []
    for i in range(nq):
        near = np.argsort(dc[i])[:nprobe]
        cand = np.flatnonzero(np.isin(km.labels_, near))
        got = cand[np.argsort(d2(Q[i:i + 1], X[cand])[0])[:10]]
        rec.append(len(set(got) & set(truth[i])) / 10)
        scan.append(len(cand) / n)
    print(f"{nprobe:6d}  {np.mean(rec):9.2f}  {np.mean(scan):24.3f}")

Output:

each vector is cut into 64 pieces of 12 numbers; each piece is replaced by the id (0..255) of the nearest of 256 learned piece-centres: 64 bytes
the codebooks themselves: 64 x 256 x 12 floats x 4 bytes = 0.79 MB, shared by all vectors
nprobe  recall@10  share of vectors scanned
     1       0.82                     0.012
     2       0.96                     0.022
     4       0.99                     0.043
     8       1.00                     0.085
    16       1.00                     0.168
    32       1.00                     0.333

Reading it: with the codebook arithmetic, the PQ bookkeeping is 0.79 MB shared by all vectors, which is negligible next to the codes themselves. In the sweep, scanning 1.2 percent of the vectors (one cluster) gives recall 0.82, two clusters give 0.96 for 2.2 percent, and beyond eight clusters recall stays at 1.00 while the scanned share keeps doubling. That plateau is where you stop turning the knob; compare libraries at the same recall, for example 0.95, and then read off the latency or scanned share each needs.

Which fits which scenario

1. Under a few million chunks, a RAG service with live document edits. HNSW in RAM. Inserts are cheap and recall is tuned at query time with ef. Deletes are marks, so plan periodic rebuilds or slot reuse.
2. Hundreds of millions of vectors, memory-bound. FAISS IVF-PQ, with a shortlist re-ranked on full vectors stored on disk or in a cheaper tier. Rebuild or retrain when the data distribution drifts, because the k-means centroids and codebooks were fit to the old data.
3. A static corpus built offline and served by many worker processes. Annoy: the index is a file that processes map into memory and share, so adding workers does not multiply RAM. If the corpus changes, you rebuild the whole file and swap it.
4. Large batch queries or fast index builds, GPU available. FAISS GPU indexes.
5. Small corpus, or an exactness requirement (audit, evaluation ground truth). Flat search. It is also how you measure the recall of every other option.

What to measure before committing

Build each candidate on a sample of your own embeddings. Take 1,000 real queries, compute exact top-10 with flat search, and report recall@10 against p95 latency while sweeping the one knob each library exposes (nprobe, ef, Annoy's search effort). Compare at equal recall, never at equal parameter values. Also record resident memory, build time, and the cost of one document update.

Common mistakes

• Comparing libraries at default settings, which sit at different recall levels.
• Forgetting that the corpus grows: an HNSW index that fits today may not at 5x.
• Treating deletion as free. Marked-deleted points still occupy memory and graph edges.
• Ignoring metadata filters: filtering after ANN search can leave fewer than k results, and the filter strategy differs by library.

Idea in plain words

Product quantization (PQ) compresses a vector by cutting it into pieces and replacing each piece with the id of its nearest entry in a small learned dictionary (called a codebook; its entries are called centroids, meaning cluster centres). A 128-dimensional float32 vector (512 bytes) becomes, say, 16 one-byte ids. Distances are then estimated from the ids using precomputed tables, so you can search huge collections held in a fraction of the memory, at the price of approximate distances.

Mechanism, in order

1. Split. A vector $x \in \mathbb{R}^{d}$ is cut into $m$ sub-vectors of $d/m$ dimensions each.
2. Train one codebook per subspace. Run k-means (a clustering method that repeatedly assigns each point to its nearest centre, then moves each centre to the mean of the points assigned to it) separately on each subspace over a training sample, with $K$ centroids (typically $K = 256$ so one id fits in a byte). Result: $m$ codebooks, each of shape $(K, d/m)$.
3. Encode. For each sub-vector, store the index of its nearest centroid. A vector becomes $m$ small integers: $m \log_2 K$ bits. The implied reconstruction concatenates the chosen centroids.
4. Why this is powerful. Each of the $m$ pieces independently picks one of $K$ entries, so the code space has $K \cdot K \cdots K = K^{m}$ possible reconstructions (256 to the power 16 for $m = 16$) although only $m K$ centroids are stored. With 2 pieces and 3 entries each, 6 stored centroids already give 9 different reconstructions (the next section counts them). Plain k-means over the whole vector could never afford that many centroids.
5. Search with asymmetric distance computation (ADC). The query stays uncompressed. For each subspace $j$, compute the squared distance from the query's $j$-th piece to all $K$ centroids: a table of shape $(m, K)$. The estimated squared distance to a database item with code $(c_1, \dots, c_m)$ is

where $T[j, c]$ is the squared distance from the query's $j$-th piece to centroid $c$ of codebook $j$. This costs $m$ table lookups and additions per database item instead of $d$ multiply-adds, and the table is built once per query. The sum is exact for the decoded vector because a squared Euclidean distance is a sum over coordinates, so it can be grouped by piece: $\|q - \hat{x}\|^2 = \sum_{j=1}^{m} \|q_j - \hat{x}_j\|^2$, where $q_j$ and $\hat{x}_j$ are the $j$-th pieces of the query and of the decoded vector. Each term on the right is one table entry. The table distance therefore equals the exact distance to the decoded vector (not to the original $x$); both programs below check that.

IVF-PQ combines this with an inverted file (an index that groups vectors into lists by region). A coarse k-means with a modest number of centroids partitions the data into those lists. Each query ranks the coarse centroids and scans only the nprobe nearest lists (nprobe is the number of lists visited). PQ is usually applied to the residual of each vector, meaning the vector minus the centroid of its list, which is smaller and more uniform than the raw vector, so the same bytes describe it more precisely.

One vector by hand

Before the larger run, here is a 4-dimensional vector $x = (3, 5, 1, 5)$ traced through every step with $m = 2$ pieces of 2 dimensions and $K = 3$ hand-set centroids per codebook (hand-set so the numbers are easy to follow; real codebooks come from k-means).

import numpy as np

# One 4-dimensional vector, split into m = 2 pieces of 2 dimensions.
# Each piece has its own codebook of K = 3 hand-set centroids (rows).
books = [np.array([[0.0, 0.0], [4.0, 4.0], [4.0, 0.0]]),     # codebook for dimensions 0-1
         np.array([[1.0, 0.0], [1.0, 6.0], [0.0, 3.0]])]     # codebook for dimensions 2-3
x = np.array([3.0, 5.0, 1.0, 5.0])
q = np.array([0.0, 1.0, 1.0, 4.0])

pieces = [x[0:2], x[2:4]]
codes = [int(((p - B) ** 2).sum(1).argmin()) for p, B in zip(pieces, books)]
decoded = np.concatenate([B[c] for B, c in zip(books, codes)])
print("codes:", codes, "decoded vector:", decoded.tolist())

# Query side: table T[j, c] = squared distance from query piece j to centroid c of codebook j.
T = np.array([((q[2*j:2*j+2] - books[j]) ** 2).sum(1) for j in range(2)])
print("table:", T.tolist())
print("lookup sum:", float(T[0, codes[0]] + T[1, codes[1]]),
      "| explicit squared distance to decoded vector:", float(((q - decoded) ** 2).sum()),
      "| exact squared distance to x:", float(((q - x) ** 2).sum()))

# Distinct reconstructions: every pick of one centroid per piece.
recon = {tuple(np.concatenate([books[0][a], books[1][b]]).tolist()) for a in range(3) for b in range(3)}
print("stored centroids:", 2 * 3, "| distinct reconstructions:", len(recon))

Output:

codes: [1, 1] decoded vector: [4.0, 4.0, 1.0, 6.0]
table: [[1.0, 25.0, 17.0], [16.0, 4.0, 2.0]]
lookup sum: 29.0 | explicit squared distance to decoded vector: 29.0 | exact squared distance to x: 26.0
stored centroids: 6 | distinct reconstructions: 9

Reading it:

• Split and encode. The pieces are $(3, 5)$ and $(1, 5)$. The nearest entry for $(3, 5)$ in the first codebook is centroid 1, $(4, 4)$ (squared distance 2, against 34 and 26 for the others). The nearest for $(1, 5)$ in the second codebook is centroid 1, $(1, 6)$ (squared distance 1). So $x$ is stored as the two small integers [1, 1], and decoding glues the centroids back into $(4, 4, 1, 6)$.
• The table. For the query $q = (0, 1, 1, 4)$, row 0 holds the squared distance from $(0, 1)$ to each of the three centroids of codebook 0, and row 1 holds the same for $(1, 4)$ and codebook 1. It is built once per query, whatever the number of database items.
• The lookup. The code [1, 1] reads entry 1 of row 0 (25) and entry 1 of row 1 (4); $25 + 4 = 29$, which equals the squared distance from $q$ to the decoded vector. The exact squared distance to the original $x$ is 26, so compression changed the estimate from 26 to 29. That gap is the accuracy PQ gives up.
• Many reconstructions from few centroids. Six centroids are stored, yet choosing one per piece yields 9 distinct decoded vectors. With $m = 16$ and $K = 256$ the same counting gives $256^{16}$.

Worked example on 5,000 vectors (computed)

numpy 2.1.3 and scikit-learn 1.5.2. 5,000 synthetic 32-dimensional vectors (a Gaussian mixture, meaning points drawn around 40 randomly placed centres with bell-shaped scatter, a stand-in for real embeddings), $K = 256$ per subspace, 50 queries. recall@10 is the share of the true 10 nearest neighbours (found by exact search) that the method also returns in its top 10. "Exact rerank" takes the 100 best items by the compressed estimate and re-orders them by true distance.

import os
os.environ["OMP_NUM_THREADS"] = "1"
os.environ["OPENBLAS_NUM_THREADS"] = "1"
import numpy as np
from sklearn.cluster import KMeans

rng = np.random.default_rng(0)
n, d, n_q, k = 5000, 32, 50, 10
# Stand-in vectors: a 40-component Gaussian mixture in 32 dimensions.
centers = 3 * rng.normal(size=(40, d))
X = (centers[rng.integers(0, 40, n)] + rng.normal(size=(n, d))).astype(np.float32)
Q = (X[rng.choice(n, n_q, replace=False)] + 0.3 * rng.normal(size=(n_q, d))).astype(np.float32)

def train_pq(X, m, ksub):
    ds = X.shape[1] // m
    return [KMeans(ksub, n_init=1, random_state=0).fit(X[:, j*ds:(j+1)*ds]).cluster_centers_
            for j in range(m)]                       # m codebooks, each (ksub, d/m)

def encode(X, books):
    m, ds = len(books), books[0].shape[1]
    codes = np.empty((len(X), m), dtype=np.uint8)
    for j, B in enumerate(books):
        sub = X[:, j*ds:(j+1)*ds]
        dist = ((sub[:, None, :] - B[None, :, :]) ** 2).sum(-1)
        codes[:, j] = dist.argmin(1)
    return codes

def decode(codes, books):
    return np.concatenate([books[j][codes[:, j]] for j in range(len(books))], axis=1)

def adc(q, codes, books):
    """Asymmetric distance: build an (m, ksub) table of squared distances from q, then sum m lookups per code."""
    m, ds = len(books), books[0].shape[1]
    table = np.stack([((q[j*ds:(j+1)*ds] - books[j]) ** 2).sum(1) for j in range(m)])
    return table[np.arange(m)[None, :], codes].sum(1)

truth = [np.argsort(((X - q) ** 2).sum(1))[:k] for q in Q]
print("raw bytes per vector:", d * 4)
print("mean squared distance of a vector from the data mean:", round(float(((X - X.mean(0)) ** 2).sum(1).mean()), 3))
def rerank(q, codes, books, t, shortlist=100):
    short = np.argsort(adc(q, codes, books))[:shortlist]
    exact = ((X[short] - q) ** 2).sum(1)
    return len(set(short[np.argsort(exact)[:k]]) & set(t)) / k

print("m  ksub bytes_per_code ratio mean_sq_recon_err recall@10(ADC) recall@10(ADC top100, exact rerank)")
for m, ksub in ((2, 256), (4, 256), (8, 256), (16, 256)):
    books = train_pq(X, m, ksub)
    codes = encode(X, books)
    err = ((X - decode(codes, books)) ** 2).sum(1).mean()
    rec = np.mean([len(set(np.argsort(adc(q, codes, books))[:k]) & set(t)) / k for q, t in zip(Q, truth)])
    rr = np.mean([rerank(q, codes, books, t) for q, t in zip(Q, truth)])
    print(f"{m:2d} {ksub:4d} {m:14d} {d*4//m:5d}x {err:16.3f} {rec:14.3f} {rr:12.3f}")
    # lookup-table distance equals distance to the decoded vector
    ref = ((decode(codes, books) - Q[0]) ** 2).sum(1)
    assert np.allclose(adc(Q[0], codes, books), ref, atol=1e-3)
print("ADC table distances match explicit decode distances: True")

Output:

raw bytes per vector: 128
mean squared distance of a vector from the data mean: 301.016
m  ksub bytes_per_code ratio mean_sq_recon_err recall@10(ADC) recall@10(ADC top100, exact rerank)
 2  256              2    64x           24.900          0.294        0.986
 4  256              4    32x           20.808          0.378        0.982
 8  256              8    16x           11.505          0.550        1.000
16  256             16     8x            1.368          0.822        1.000
ADC table distances match explicit decode distances: True

Reading the run. The line table[np.arange(m)[None, :], codes].sum(1) inside adc is the heart of the method: codes has one row per database item and one column per piece, and the indexing picks, for every item and every piece, that piece's entry from the query's table, so the sum over the $m$ picks is the estimated squared distance for all items at once. The reconstruction error is the average squared distance between a vector and its decoded version; the average squared distance of a vector from the data mean is 301.016, so the error is about 8 percent of that at 2 bytes (24.900 / 301.016) and about 0.5 percent at 16 bytes (1.368 / 301.016). Finally, 128 raw bytes shrink to 16 down to 2 bytes per vector (8x to 64x). Reconstruction error falls as you spend more bytes (24.900 at 2 bytes to 1.368 at 16 bytes), and recall@10 from the compressed estimate alone rises with it (0.294 to 0.822). Re-ranking a 100-item shortlist with the original vectors brought recall to 0.982 or better in every row on this data. That recovery pattern (compress for the first pass, re-rank a shortlist with full precision) is the standard way PQ is deployed; the specific numbers belong to this synthetic set.

What accuracy is lost, and why

• Quantization error: each piece is replaced by a centroid, so distances are estimated. Near-ties between close neighbours are the first thing to flip, which hurts recall@k with small k most.
• Subspace independence: PQ assumes the subspaces can be quantized separately. If correlated dimensions sit in different pieces, the codebooks waste capacity. Rotating the vectors first so that correlated dimensions end up in the same piece (a learned rotation, as in optimised product quantization, OPQ) is the usual remedy.
• Training data: codebooks fit to a sample; if the live data drifts, error rises and you retrain.
• Trade-off knobs: larger $m$ (more bytes) or larger $K$ lowers error; the lookup table costs $mK$ entries per query.

Common mistakes

• Training one k-means over the whole vector and calling it PQ.
• Forgetting that ADC leaves the query uncompressed (the symmetric alternative compresses both sides and is less accurate).
• Reporting compression ratio without recall@k against exact search.
• Using a dimension $d$ that is not divisible by $m$ without padding.

Direct answer

The retriever is the fast first stage: it searches the whole collection and returns a few dozen candidate passages. The re-ranker is a slower second stage that takes those candidates and re-orders them, so the best few end up first. They differ in what they compare. A typical retriever turns the question and each passage into vectors separately (a bi-encoder: two independent encodings, each a list of numbers, compared by cosine similarity, the angle between the two lists, or by dot product, multiply matching entries and add), so passage vectors are computed once, ahead of time, and searched quickly. A typical re-ranker is a cross-encoder: it reads the question and one passage together and outputs a relevance score, which is more accurate because it sees how the words interact, but it must run once per candidate at query time.

Why you need both

• The retriever must be cheap enough to cover millions of passages, so it uses a compressed summary of each passage and cannot look at the question-passage interaction.
• The re-ranker can use a much richer comparison, but running it over every passage is impossible, so it only sees the retriever's shortlist.
• The re-ranker can only fix the order of the shortlist. If the answer passage is not among the candidates, no re-ranker recovers it, so the candidate count is a recall decision.

An example where re-ranking is necessary

Take the question "can employees take paid vacation days longer than two weeks", where the answering passage says "Vacation requests longer than two weeks need director approval." A passage that merely says employees can take paid vacation shares more of the question's individual words, so a bag-of-words score (one that counts which words occur and ignores how they are arranged) puts it first. A pair-aware scorer notices that the exact phrase "longer than two weeks" appears in the answering passage and moves that passage up.

The program below shows that on six passages and six questions, where MRR@3 (mean reciprocal rank: the average over questions of 1 divided by the rank of the answering passage within the top 3, or 0 if absent) compares the two stages. The retriever is a TF-IDF cosine (term-weight vectors compared by angle) and the re-ranker is a phrase-matching function. Both are stand-ins: a real system would use an embedding model and a trained cross-encoder. The stand-in re-ranker scores a passage as the number of two-word pairs it shares with the question, plus 0.1 for each shared word; for the first question the program prints the arithmetic for each candidate. It is a picture of the mechanism, not a measurement of any real model.

import os
os.environ["OMP_NUM_THREADS"] = "1"
import re
import numpy as np
from sklearn.feature_extraction.text import TfidfVectorizer

DOCS = ["Employees can take paid vacation after 90 days, and vacation requests go to the manager.",
        "Contractors are not eligible for paid vacation days.",
        "Contractors submit invoices on the first day of each month.",
        "Paid parental leave is available to employees after one year.",
        "Vacation requests longer than two weeks need director approval.",
        "Employees receive a laptop on their first day."]
# (query, index of the passage that answers it)
QUERIES = [("can employees take paid vacation days longer than two weeks", 4),
           ("who approves vacation requests longer than two weeks", 4),
           ("when do contractors submit invoices", 2),
           ("do contractors take paid vacation after 90 days", 1),
           ("are employees allowed paid vacation days longer than two weeks", 4),
           ("how do employees get paid vacation days longer than two weeks", 4)]

# Retriever stand-in: TF-IDF vectors for query and passages are built independently and compared by cosine
# (like a bi-encoder, whose passage vectors can be computed before any query arrives).
tf = TfidfVectorizer(stop_words="english"); P = tf.fit_transform(DOCS)
def retrieve(q, k):
    s = (P @ tf.transform([q]).T).toarray().ravel()
    return sorted(range(len(DOCS)), key=lambda i: (-s[i], i))[:k]

# Reranker stand-in: it looks at the query and ONE passage together and rewards phrases (word pairs) that occur
# in both, which a bag-of-words vector cannot see. A real cross-encoder instead feeds the pair through a neural network that lets every query word interact with every passage word.
def pairs(t):
    w = re.findall(r"[a-z]+", t.lower()); return {(a, b) for a, b in zip(w, w[1:])}
def rerank_score(q, d):
    return len(pairs(q) & pairs(d)) + 0.1 * len(set(re.findall(r"[a-z]+", q.lower())) & set(re.findall(r"[a-z]+", d.lower())))
def rerank(q, cand):
    return sorted(cand, key=lambda i: (-rerank_score(q, DOCS[i]), i))

q0 = QUERIES[0][0]
print("stand-in reranker score for the first query = shared word pairs + 0.1 x shared words")
for i in retrieve(q0, 3):
    sp = sorted(" ".join(p) for p in pairs(q0) & pairs(DOCS[i]))
    sw = len(set(re.findall(r"[a-z]+", q0.lower())) & set(re.findall(r"[a-z]+", DOCS[i].lower())))
    print(f"  passage {i}: pairs={len(sp)} {sp}  words={sw}  score={rerank_score(q0, DOCS[i]):.1f}")
print()

def rr(order, gold): return 1 / (order.index(gold) + 1) if gold in order else 0.0
K = 3
r_ret = r_rer = 0
for q, g in QUERIES:
    c = retrieve(q, K); r = rerank(q, c)
    r_ret += rr(c, g); r_rer += rr(r, g)
    print(f"{q:58s} retriever top{K}={c} -> reranked={r} gold={g}")
print(f"MRR@{K}: retriever {r_ret / len(QUERIES):.3f}  retriever+reranker {r_rer / len(QUERIES):.3f}")

# Cost: model calls and tokens per query (all sizes ASSUMED)
q_tok, pair_tok, n_chunks = 20, 300, 10_000_000
print(f"\nretriever: encode 1 query = {q_tok} tokens, then an index lookup over {n_chunks:,} precomputed vectors")
for k in (10, 50, 200):
    print(f"reranker over top {k:3d}: {k} model passes, {k * pair_tok:6d} tokens per query ({k * pair_tok // q_tok}x the query-encode tokens)")

Output:

stand-in reranker score for the first query = shared word pairs + 0.1 x shared words
  passage 0: pairs=2 ['paid vacation', 'take paid']  words=6  score=2.6
  passage 4: pairs=3 ['longer than', 'than two', 'two weeks']  words=5  score=3.5
  passage 1: pairs=2 ['paid vacation', 'vacation days']  words=3  score=2.3

can employees take paid vacation days longer than two weeks retriever top3=[0, 4, 1] -> reranked=[4, 0, 1] gold=4
who approves vacation requests longer than two weeks       retriever top3=[4, 0, 1] -> reranked=[4, 0, 1] gold=4
when do contractors submit invoices                        retriever top3=[2, 1, 0] -> reranked=[2, 1, 0] gold=2
do contractors take paid vacation after 90 days            retriever top3=[1, 0, 2] -> reranked=[0, 1, 2] gold=1
are employees allowed paid vacation days longer than two weeks retriever top3=[0, 4, 1] -> reranked=[4, 1, 0] gold=4
how do employees get paid vacation days longer than two weeks retriever top3=[0, 4, 1] -> reranked=[4, 1, 0] gold=4
MRR@3: retriever 0.750  retriever+reranker 0.917

retriever: encode 1 query = 20 tokens, then an index lookup over 10,000,000 precomputed vectors
reranker over top  10: 10 model passes,   3000 tokens per query (150x the query-encode tokens)
reranker over top  50: 50 model passes,  15000 tokens per query (750x the query-encode tokens)
reranker over top 200: 200 model passes,  60000 tokens per query (3000x the query-encode tokens)

Reading the output:

• Hand trace, first question. Passage 0 shares the pairs "paid vacation" and "take paid" (2 pairs) and 6 words, so its score is 2 + 0.6 = 2.6. Passage 4 shares "longer than", "than two" and "two weeks" (3 pairs) and 5 words, so 3 + 0.5 = 3.5. The retriever, which saw only individual word weights, put passage 0 first; the pair-aware score puts the answering passage 4 first. That is the case where re-ranking is necessary: the evidence that matters is in the word order, which the first stage threw away.
• Questions 5 and 6 are further wordings of the same question, and the re-ranker repairs them the same way. Counting them lifts the stand-in's MRR@3 from 0.750 to 0.917, but that figure shows the mechanism on one kind of failure, not a rate you should expect.
• The fourth question shows the opposite: the retriever is right (passage 1 says contractors are not eligible), and the phrase-matching stand-in demotes it because it cannot read the negation. A re-ranker is a model with its own errors, so whether it helps on your data is an empirical question. Look at the per-question changes, not only the average.
• In real systems a trained cross-encoder re-ranker is commonly found to improve the top of the list over a first-stage retriever alone, because it can read the question and passage jointly; this toy only illustrates why, and the size of the gain on your collection has to be measured on your labelled questions.

Cost trade-offs

• Latency and compute. The retriever encodes the question once (20 tokens in the run; a token is the sub-word piece a model reads) and looks up precomputed vectors. The re-ranker runs one model pass per candidate over question plus passage, so with an assumed 300 tokens per pair, 10 candidates cost 3,000 tokens, 50 cost 15,000 and 200 cost 60,000 per query: linear in the number of candidates. Passes can be batched on a GPU (a graphics processor, efficient for the large matrix products involved), which raises throughput and keeps latency down, but the number of model passes and tokens each query needs still grows linearly with the candidate count.
• Quality versus candidates. More candidates raise the chance that the answering passage is in the list and cost more re-ranker calls. Pick the smallest k at which recall@k (the share of questions with the answering passage in the top k) stops improving on your labelled set.
• Engineering cost. A second model needs training or selection, its own evaluation, deployment, a timeout and a fallback to the retriever's order when it is slow.
• Index cost. The re-ranker needs no index, since it scores pairs on the fly, but it gives no help to the first stage's recall.

Common mistakes

• Expecting the re-ranker to fix a retriever that never returns the answer.
• Sending hundreds of candidates and then blaming the re-ranker for latency.
• Adopting a re-ranker on average metrics without checking the questions it makes worse.
• Treating the two as interchangeable: the cross-encoder cannot search a large collection and the bi-encoder is less accurate on the final order.

Direct answer

Use RAG (retrieval-augmented generation: look passages up at question time and put them in the prompt) when the knowledge is large, changes often, must be cited, or has to be access-controlled per user. Use fine-tuning (continuing to train the model's weights, the learned numbers inside it that determine its behaviour, on your examples) when you need to change how the model behaves: its format, tone, domain vocabulary, or a narrow skill that prompting cannot reach. For adding domain knowledge specifically, RAG is the default and fine-tuning is the supplement; they are not exclusive, and many systems fine-tune for behaviour and retrieve for facts.

What each approach changes

• RAG changes the input. The model weights stay fixed; knowledge lives in an index you control, and each answer can name the passages it used.
• Fine-tuning changes the weights. Knowledge becomes implicit in the weights, often billions of numbers: there is no record of which training example produced a claim, and a changed fact means another training run.

The five axes

Worked example: a cost and freshness model

The rates below are assumed round numbers in abstract cost units (CU), not any provider's prices; the program computes only the consequences. The access-control lines show a per-user filter at retrieval time, which a set of weights cannot offer.

import os
os.environ["OMP_NUM_THREADS"] = "1"

# All rates below are ASSUMED round numbers in abstract "cost units" (CU); only the arithmetic is computed.
queries_per_month_list = [10_000, 100_000, 1_000_000, 10_000_000]

# Option A: RAG. Pays per query for the retrieved context tokens, plus a small fixed index cost.
rag_context_tokens = 1500          # retrieved tokens added to every prompt
cu_per_1k_input_tokens = 0.01      # price of reading 1,000 prompt tokens
index_cu_per_month = 20            # vector store hosting + re-embedding changed docs

# Option B: fine-tuning. Pays a training run per knowledge refresh, no extra prompt tokens.
train_cu_per_run = 400             # one fine-tuning run
refreshes_per_month = 2            # how often the knowledge changes enough to retrain
hosting_premium_cu = 50            # serving a custom model instead of a shared one

def monthly_rag(q):
    return index_cu_per_month + q * rag_context_tokens / 1000 * cu_per_1k_input_tokens

def monthly_ft(q):
    return train_cu_per_run * refreshes_per_month + hosting_premium_cu

print(f"{'queries/month':>14} {'RAG CU':>10} {'fine-tune CU':>13} cheaper")
for q in queries_per_month_list:
    r, f = monthly_rag(q), monthly_ft(q)
    print(f"{q:>14,} {r:>10,.0f} {f:>13,.0f} {'RAG' if r < f else 'fine-tune'}")

per_query = rag_context_tokens / 1000 * cu_per_1k_input_tokens
break_even = (monthly_ft(0) - index_cu_per_month) / per_query
print(f"break-even volume = {break_even:,.0f} queries/month")

# Freshness: days from a source change until users see it.
days_until_next_retrain = 15
print("RAG freshness lag: the re-index time (not modelled here)")
print(f"fine-tune freshness lag: up to {days_until_next_retrain} days with {refreshes_per_month} refreshes a month (assumed)")

# Access control: a retrieval filter can hide chunks per user; weights cannot be filtered per user.
chunks = [("hr-001", {"hr"}), ("pub-001", {"all"}), ("fin-001", {"finance"})]
def visible(user_groups):
    return [cid for cid, allowed in chunks if "all" in allowed or allowed & user_groups]
print("engineer sees:", visible({"eng"}))
print("finance user sees:", visible({"finance"}))

Output:

 queries/month     RAG CU  fine-tune CU cheaper
        10,000        170           850 RAG
       100,000      1,520           850 fine-tune
     1,000,000     15,020           850 fine-tune
    10,000,000    150,020           850 fine-tune
break-even volume = 55,333 queries/month
RAG freshness lag: the re-index time (not modelled here)
fine-tune freshness lag: up to 15 days with 2 refreshes a month (assumed)
engineer sees: ['pub-001']
finance user sees: ['pub-001', 'fin-001']

The arithmetic behind the first row: each RAG query adds 1,500 retrieved tokens, which at 0.01 CU per 1,000 tokens is 1.5 x 0.01 = 0.015 CU, so 10,000 queries cost 10,000 x 0.015 = 150 CU, and adding the 20 CU index gives 170. Fine-tuning costs 400 x 2 refreshes + 50 hosting = 850 CU whatever the traffic. The break-even is where 20 + 0.015 x q = 850, so q = 830 / 0.015 = 55,333.

Under these assumptions RAG is cheaper below roughly 55,000 queries a month and fine-tuning is cheaper above it, because fine-tuning's cost is nearly flat while RAG's cost grows with traffic. The break-even moves with every input: halve the retrieved tokens and it doubles; train less often and it falls. A real comparison should plug in your own measured token counts, refresh rate and prices. The cost model is also incomplete on purpose: it ignores quality. If fine-tuning cannot answer the questions correctly or cite a source, its lower price at high volume is not a win.

My recommendation and what would flip it

Commit to RAG for knowledge: it handles change and per-user access, and it gives citations. Add fine-tuning only when a measured gap remains that retrieval cannot close, for example the model must always emit a strict output format, use specialist terminology consistently, or run on a smaller model to cut serving cost. What would flip the choice toward fine-tuning first: knowledge that is small and stable, a strict latency budget that cannot afford a retrieval hop, or an on-device setting with no index available.

Common mistakes

• Fine-tuning to "teach facts" and then expecting citations or instant updates.
• Assuming RAG is free: a long retrieved context raises per-query cost and latency, and retrieval quality becomes a new failure point.
• Treating the choice as binary. A retrieval pipeline over a lightly fine-tuned model is a normal design.
• Ignoring privacy mechanics: deleting a user's record from a fine-tuned model is not possible without retraining.

Idea in plain words

Locality-sensitive hashing (LSH) uses hash functions where similar vectors collide in the same bucket more often than dissimilar ones. For cosine similarity, the hash is: draw random hyperplanes, and record on which side of each one the vector falls. One hyperplane gives one bit; n_bits hyperplanes give a bucket key. You keep n_tables independent tables. At query time you hash the query once per table, take the union of the matching buckets as candidates, and compute exact similarity only on those candidates.

Terms: a hyperplane is a flat surface through the origin that splits space in two (a line in 2-D, a plane in 3-D); in code it is stored as its normal vector, and the side a vector falls on is the sign of its dot product with that normal. To L2-normalise a vector is to divide it by its length so that it has length 1. A Gaussian row is a vector whose coordinates are drawn independently from a normal (bell-curve) distribution, which makes the hyperplane's orientation uniformly random. Candidates are the vectors found in the matching buckets, the only ones scored exactly. Recall@10 is the share of the true 10 nearest neighbours (by exact cosine) that the search returns.

Pipeline

1. Precompute embeddings once, with an image encoder, and L2-normalise them so dot product equals cosine. The program below uses synthetic clustered vectors as a stand-in for real image embeddings; a real system would store the encoder's outputs.
2. Build: for each table, multiply by an (n_bits, d) matrix of Gaussian rows, take the sign, pack the bits into an integer, and append the vector id to that bucket.
3. Update: inserting is the same hashing step on the new vectors, appended to the buckets. No rebuild is needed (deleting means removing the id from n_tables buckets).
4. Query: hash, gather candidates from n_tables buckets, score candidates exactly, return the top k.

The recall and cost trade-off

For two vectors at angle $\theta$, one random hyperplane puts them on the same side with probability $p = 1 - \theta/\pi$ (the standard random-hyperplane result). The reason: a random hyperplane splits two vectors only if it passes between them, and the share of random orientations that do so is the angle between the vectors divided by $\pi$. At 90 degrees ($\theta=\pi/2$) that is $p=0.5$, at 60 degrees (cosine 0.5) it is $p=2/3$, and at 0 degrees it is $p=1$. The code converts a cosine to an angle with arccos. A pair shares the full key of one table with probability $p^{b}$ for $b$ bits, and shares a bucket in at least one of $L$ tables with probability

More bits make buckets smaller (fewer candidates, lower recall). More tables give more chances (higher recall, more candidates, $L$ times the memory for ids and $L$ times the hashing work). The cost to watch is the number of candidates scored per query, which stands in for latency here because it is a count, not a timing. Below, numpy 2.1.3, 20,000 vectors, 64 dimensions, 100 queries, recall@10 against exact cosine search.

import os
os.environ["OMP_NUM_THREADS"] = "1"
os.environ["OPENBLAS_NUM_THREADS"] = "1"
import numpy as np
from collections import defaultdict

rng = np.random.default_rng(0)
n, d, n_q, k = 20000, 64, 100, 10
# Stand-in for image embeddings: 50 clusters of unit vectors (a real system would store CNN/ViT outputs).
centers = rng.normal(size=(50, d))
X = centers[rng.integers(0, 50, n)] + 0.6 * rng.normal(size=(n, d))
X /= np.linalg.norm(X, axis=1, keepdims=True)
Q = X[rng.choice(n, n_q, replace=False)] + 0.15 * rng.normal(size=(n_q, d))
Q /= np.linalg.norm(Q, axis=1, keepdims=True)

truth = np.argsort(-(Q @ X.T), axis=1)[:, :k]  # exact cosine top-k (unit vectors)

class CosineLSH:
    """Random-hyperplane LSH: n_tables tables, each hashes a vector to n_bits sign bits."""
    def __init__(self, d, n_tables, n_bits, seed=0):
        r = np.random.default_rng(seed)
        self.planes = r.normal(size=(n_tables, n_bits, d))
        self.pow = 1 << np.arange(n_bits)
        self.tables = [defaultdict(list) for _ in range(n_tables)]
        self.vecs = []
    def _keys(self, V):
        bits = np.einsum('tbd,nd->tnb', self.planes, V) > 0
        return bits @ self.pow                      # shape (n_tables, n)
    def add(self, V):
        start = len(self.vecs)
        keys = self._keys(V)
        for t in range(len(self.tables)):
            for i, key in enumerate(keys[t]):
                self.tables[t][int(key)].append(start + i)
        self.vecs.extend(V)
    def query(self, q, k):
        keys = self._keys(q[None, :])[:, 0]
        cand = set()
        for t, key in enumerate(keys):
            cand.update(self.tables[t].get(int(key), []))
        cand = np.array(sorted(cand))
        if len(cand) == 0:
            return [], 0
        M = np.asarray(self.vecs)[cand]
        top = cand[np.argsort(-(M @ q))[:k]]
        return list(top), len(cand)

def evaluate(L, b):
    idx = CosineLSH(d, L, b)
    idx.add(X)
    rec, cands = [], []
    for qi in range(n_q):
        got, c = idx.query(Q[qi], k)
        rec.append(len(set(got) & set(truth[qi])) / k)
        cands.append(c)
    return np.mean(rec), np.mean(cands)

print("n=%d d=%d  brute force scores %d vectors per query" % (n, d, n))
print("tables bits recall@10 candidates_scored")
for b in (8, 12, 16):
    for L in (1, 4, 16):
        r, c = evaluate(L, b)
        print(f"{L:6d} {b:4d} {r:9.3f} {c:16.0f}")

# incremental insert: add 1000 new vectors, then find one of them
idx = CosineLSH(d, 8, 12); idx.add(X)
new = X[:1000] + 0.05 * rng.normal(size=(1000, d)); new /= np.linalg.norm(new, axis=1, keepdims=True)
idx.add(new)
got, c = idx.query(new[0], 1)
print("after insert, nearest to new[0] is id", got[0], "(expected", n, ")")

# Theory check: one random-hyperplane bit agrees with probability 1 - theta/pi,
# so a pair lands in the same bucket of one table with p**bits, and in at least one of L tables with 1-(1-p**bits)**L.
for cos in (0.9, 0.5):
    p = 1 - np.arccos(cos) / np.pi
    print(f"cosine {cos}: per-bit agreement {p:.3f}")
    for L, b in ((1, 8), (16, 8), (16, 16)):
        print(f"  L={L:2d} bits={b:2d} P(share a bucket in some table) = {1 - (1 - p**b)**L:.3f}")

Output:

n=20000 d=64  brute force scores 20000 vectors per query
tables bits recall@10 candidates_scored
     1    8     0.063              109
     4    8     0.232              435
    16    8     0.663             1578
     1   12     0.009                8
     4   12     0.075               44
    16   12     0.268              169
     1   16     0.003                1
     4   16     0.018                6
    16   16     0.062               22
after insert, nearest to new[0] is id 20000 (expected 20000 )
cosine 0.9: per-bit agreement 0.856
  L= 1 bits= 8 P(share a bucket in some table) = 0.289
  L=16 bits= 8 P(share a bucket in some table) = 0.996
  L=16 bits=16 P(share a bucket in some table) = 0.753
cosine 0.5: per-bit agreement 0.667
  L= 1 bits= 8 P(share a bucket in some table) = 0.039
  L=16 bits= 8 P(share a bucket in some table) = 0.471
  L=16 bits=16 P(share a bucket in some table) = 0.024

Reading the run: with 8 bits, going from 1 to 16 tables raised recall@10 from 0.063 to 0.663 while candidates scored grew from 109 to 1578, still under a tenth of the 20,000 a brute-force scan touches. At 16 bits the buckets are so small that even 16 tables score only 22 candidates and recall is 0.062. The formula lines agree in direction: close pairs (cosine 0.9) survive 16 tables of 8 bits with probability 0.996 but 16 tables of 16 bits with 0.753, and pairs at cosine 0.5 are excluded far more often: 16 tables of 16 bits share a bucket for such a pair with probability 0.024, while 16 tables of 8 bits still do so with probability 0.471, nearly half, so the bit count is what keeps unrelated vectors out of the candidate set.

The recall values are low in absolute terms because this synthetic data has many near-ties inside each cluster and noisy queries. The point is the direction and size of the knobs, not that these numbers transfer to your data. Tune on your own embeddings against an exact baseline.

Checking the formula, reading the shapes, and reaching high recall

The next program does three things. It measures the same-side probability with 200,000 random hyperplanes at four angles. It runs the packing step on a tiny case (2 tables, 3 bits, 4 dimensions, 5 vectors): planes has shape (tables, bits, dimensions), np.einsum('tbd,nd->tnb', ...) takes the dot product of every vector with every hyperplane normal and gives shape (tables, vectors, bits), > 0 turns each into a side, and bits @ pow reads the bits as a binary number (1, 2, 4, ...) to give one integer bucket key per table and vector. Finally it searches for settings that reach high recall on the same data as the table above.

import os
os.environ["OMP_NUM_THREADS"] = "1"
os.environ["OPENBLAS_NUM_THREADS"] = "1"
import numpy as np
from collections import defaultdict

# 1. Why one bit agrees with probability 1 - theta/pi: measure it for four angles with 200,000 random hyperplanes.
r = np.random.default_rng(1)
for deg in (0, 60, 90, 180):
    th = np.radians(deg)
    u, v = np.array([1.0, 0.0]), np.array([np.cos(th), np.sin(th)])
    H = r.normal(size=(200_000, 2))
    same = np.mean((H @ u > 0) == (H @ v > 0))
    print(f"angle {deg:3d} degrees (cosine {np.cos(th):5.2f}): measured same-side {same:.3f}, formula 1 - theta/pi = {1 - th / np.pi:.3f}")

# 2. The shapes in the code, on a tiny case: 2 tables, 3 bits, 4-dimensional vectors, 5 vectors.
r = np.random.default_rng(2)
planes = r.normal(size=(2, 3, 4))            # (n_tables, n_bits, d): 3 random hyperplane normals per table
V = r.normal(size=(5, 4))                    # (n, d)
signs = np.einsum('tbd,nd->tnb', planes, V)  # dot product of every vector with every hyperplane: (table, vector, bit)
bits = signs > 0                             # which side of each hyperplane
pow2 = 1 << np.arange(3)                     # [1, 2, 4]
keys = bits @ pow2                           # bits read as a binary number: (table, vector)
print("signs shape", signs.shape, "| vector 0, table 0 bits", bits[0, 0].astype(int).tolist(), "-> key", int(keys[0, 0]))
print("bucket keys per table (rows) for the 5 vectors (columns):")
print(keys)

# 3. How much work reaches high recall on the same data as the table above.
rng = np.random.default_rng(0)
n, d, n_q, k = 20000, 64, 100, 10
centers = rng.normal(size=(50, d))
X = centers[rng.integers(0, 50, n)] + 0.6 * rng.normal(size=(n, d))
X /= np.linalg.norm(X, axis=1, keepdims=True)
Q = X[rng.choice(n, n_q, replace=False)] + 0.15 * rng.normal(size=(n_q, d))
Q /= np.linalg.norm(Q, axis=1, keepdims=True)
truth = np.argsort(-(Q @ X.T), axis=1)[:, :k]
def run(L, b):
    pl = np.random.default_rng(0).normal(size=(L, b, d))
    pw = 1 << np.arange(b)
    kx = (np.einsum('tbd,nd->tnb', pl, X) > 0) @ pw
    kq = (np.einsum('tbd,nd->tnb', pl, Q) > 0) @ pw
    rec, cnt = [], []
    for i in range(n_q):
        cand = np.flatnonzero((kx == kq[:, i:i + 1]).any(axis=0))
        got = cand[np.argsort(-(X[cand] @ Q[i]))[:k]]
        rec.append(len(set(got) & set(truth[i])) / k); cnt.append(len(cand))
    return np.mean(rec), np.mean(cnt)
print("tables bits recall@10 candidates_scored")
for L, b in ((16, 6), (32, 6), (64, 6), (64, 8), (128, 8)):
    rc, c = run(L, b)
    print(f"{L:6d} {b:4d} {rc:9.3f} {c:16.0f}")

Output:

angle   0 degrees (cosine  1.00): measured same-side 1.000, formula 1 - theta/pi = 1.000
angle  60 degrees (cosine  0.50): measured same-side 0.666, formula 1 - theta/pi = 0.667
angle  90 degrees (cosine  0.00): measured same-side 0.499, formula 1 - theta/pi = 0.500
angle 180 degrees (cosine -1.00): measured same-side 0.000, formula 1 - theta/pi = 0.000
signs shape (2, 5, 3) | vector 0, table 0 bits [1, 0, 1] -> key 5
bucket keys per table (rows) for the 5 vectors (columns):
[[5 4 6 3 3]
 [3 1 4 0 0]]
tables bits recall@10 candidates_scored
    16    6     0.900             4938
    32    6     0.989             8248
    64    6     1.000            12641
    64    8     0.985             5173
   128    8     0.999             8529

Reading it: the measured same-side shares match $1-\theta/\pi$ (0.666 against 0.667 at 60 degrees, 0.499 against 0.500 at 90). In the tiny case vector 0 falls on the sides 1, 0, 1 of table 0's three hyperplanes, which reads as the binary number 5; vectors 3 and 4 share the keys 3 and 0 in the two tables, so they land in the same buckets. A common target is recall@10 of 0.9 or more: 16 tables of 6 bits reach 0.900 while scoring 4,938 of the 20,000 vectors (about 25 percent), and 64 tables of 8 bits reach 0.985 at 5,173 (about 26 percent). The low values in the first table therefore come from using few tables, not from a broken method, and the cost of high recall is a quarter of the corpus scored per query on this data, which is why graph and IVF indexes are usually preferred.

Library alternative

In production you would normally use an ANN library (HNSW, IVF) rather than hand-rolled LSH, because graph and IVF indexes usually give a better recall-for-candidates trade-off on dense embeddings than random-hyperplane LSH. LSH remains useful when you need a simple, hardware-friendly, easy-to-update scheme with a provable collision probability.

Common mistakes

• Forgetting to normalise, so the hash reflects angle but the exact re-scoring step ranks by an unnormalised dot product.
• Choosing n_bits too large for the dataset size: buckets become empty and recall collapses.
• Judging recall on queries that are exact copies of indexed vectors.
• Reporting recall without the candidate count (or latency) next to it.