96 - Embeddings and Semantic Search: A Vector Index Built From Scratch, and Where It Gets It Wrong

In an ordinary library you find a book if you know its title: the catalogue is sorted by a string, and if that is not the one on the spine, the book does not exist for you. Now imagine a library arranged by perceived subject, where two volumes that say the same thing in different words sit next to each other. The price fits in one sentence: "what it is about" is decided by a model, and that model has tastes of its own. This arrangement is a vector index.

We build it from scratch: a corpus of docstrings from the Python standard library, an encoder, the exact index in a few lines of NumPy, BM25 implemented from the paper, recall and MRR on labelled queries, reciprocal rank fusion and a simplified IVF. Every number you find was produced by a listing printed here, run twice with the same output. On one point I am explicit from the start: no model runs in this lesson.

How the examples are written. A real encoder (for example nomic-embed-text served locally by Ollama) needs a model runtime, and its vectors cannot be reproduced without one. That is why the examples use a fake encoder: a deterministic hashing of words and character trigrams, 768 dimensions, written below. It does not know synonyms, and that is exactly why it is useful: the index, the metrics, the fusion and the IVF behave the same way with any encoder, whereas how much the encoder understands meaning can only be measured with the real one, on your corpus. Where a figure depends on a trained encoder, the lesson does not report it. Versions used: Python 3.14.4, NumPy 2.3.5, scikit-learn 1.8.0, on a laptop with a Ryzen 5 5600H and 30 GB of RAM.

The analogy: a library sorted by meaning

The two libraries fail in opposite ways. The one sorted by title fails by omission: you search for "how do I measure how much two texts resemble each other", the book is called Sequence matching, and you do not find it - but you notice, because the result is empty. The one sorted by meaning fails by substitution: it brings you a book about comparing objects in general, plausible and wrong. And of that you do not notice.

The analogy holds on a less comforting point: the librarian who arranges by meaning has read a lot, but in one language and in one domain. And here the answer "there isn't one" does not exist: the shelf always returns the k least distant volumes, whatever the question.

What an embedding is, in operational terms

An embedding is a learned function f: text → R^d in which distance has a meaning: texts that a reader would consider related end up close together. Nothing mystical: it is trained on pairs labelled as related, and it learns the notion of relatedness contained in that data. In the example d = 768.

The first distinction that matters is between static and contextual embeddings. In the static ones - word2vec by Mikolov and colleagues, Efficient Estimation of Word Representations in Vector Space, arXiv:1301.3781 - every word has one vector, always the same. In the contextual ones, built on the Transformer from the lesson on attention, the vector depends on the whole text: key in "dictionary key" and in "front door key" gets different vectors. Calling a real encoder takes one HTTP request; the following listing is the sketch, not executed because it needs Ollama listening.

# SKETCH TO ADAPT, NOT EXECUTED: needs Ollama listening on localhost
import numpy as np, urllib.request, json

def embed(texts, model="nomic-embed-text", batch=48):
    """L2-normalised vectors, in batches: one call for every 48 texts."""
    chunks = []
    for i in range(0, len(texts), batch):
        request = urllib.request.Request(
            "http://localhost:11434/api/embed",
            data=json.dumps({"model": model, "input": texts[i:i + batch]}).encode(),
            headers={"Content-Type": "application/json"})
        with urllib.request.urlopen(request, timeout=600) as r:
            chunks.append(np.array(json.loads(r.read())["embeddings"], dtype=np.float32))
    E = np.vstack(chunks)
    return E / np.linalg.norm(E, axis=1, keepdims=True)   # never trust it: always normalise

The listing sends the texts in batches of 48 (one call per batch, not one per text) and normalises the rows: repeating the normalisation costs nothing and protects you from a service that returns non-unit vectors. The rest of the lesson uses this fake encoder instead, which has the same signature but no model behind it.

import hashlib, math, re, collections
import numpy as np

def _hash(f):
    return int.from_bytes(hashlib.blake2b(f.encode(), digest_size=8).digest(), "big")

def words_of(text):
    text = re.sub(r"([a-z])([A-Z])", r"\1 \2", text)       # camelCase -> camel Case
    return re.findall(r"[a-z0-9]+", text.lower())

def embed(texts, d=768):
    """FAKE encoder: signed hashing of words and character trigrams. No model."""
    E = np.zeros((len(texts), d), dtype=np.float32)
    for r, t in enumerate(texts):
        feat = collections.Counter()
        for w in words_of(t):
            feat["w:" + w] += 1
            s = f"^{w}$"
            for k in range(len(s) - 2):
                feat["c:" + s[k:k + 3]] += 1               # trigrams: "compress" ~ "compression"
        for f, c in feat.items():
            h = _hash(f)
            E[r, h % d] += (1 if (h >> 40) & 1 else -1) * (1 + math.log(c))
    return E / np.linalg.norm(E, axis=1, keepdims=True)    # never trust it: always normalise

What the code does. It splits the text into words (including camelCase names), then for every word it adds to the vector one component for the whole word and one for each character trigram, with sign and position decided by a hash. It uses blake2b and not hash(), because the latter changes on every run and would make the output unreproducible. The trigrams are the only generalisation it has: compress and compression resemble each other. It does not know that "temporary" and "disappears when closed" talk about the same thing.

This is enough to know what to expect from two different retrieval routes. A trained encoder, like the one in Sentence-BERT (Reimers and Gurevych, Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks, arXiv:1908.10084), is built precisely to put related sentences close together even without words in common, and does better than an average of the vectors of the single words; by how much, on your corpus, is decided by a measurement that the lesson teaches you to make but that I cannot report here.

Cosine, and the thing almost everyone misunderstands

Cosine similarity is the cosine of the angle between two vectors: dot product divided by the product of the norms. Read it as a sentence: sum the products of the corresponding components, then remove the length by dividing by the norms. What remains is the direction, and that is why the bare dot product is not used: the norm grows with the document, and long texts would win just for being long.

cos(a, b) = (a · b) / (‖a‖ · ‖b‖)        with  a · b = Σᵢ aᵢ · bᵢ

Now the part almost everyone misunderstands: on normalised vectors, sorting by decreasing cosine is sorting by increasing Euclidean distance. The proof takes three lines, with ‖a‖ = ‖b‖ = 1.

‖a − b‖² = (a − b) · (a − b)
         = ‖a‖² − 2·(a · b) + ‖b‖²
         = 2 − 2·cos(a, b)                   ∎

The squared distance is strictly decreasing in the cosine, so the two orderings coincide. Practical consequence: the choice between cosine, dot product and Euclidean distance does not change the ranking, it changes the code - and the dot product wins, a single multiplication with no roots or divisions.

D = embed(texts); Q = embed(QUERIES)                  # (292, 768) each, unit rows
D64 = D.astype(np.float64); a = D64[0]
dist2 = ((D64 - a) ** 2).sum(axis=1); cos64 = D64 @ a
print("float64: max gap |dist^2 - (2 - 2cos)| =", f"{np.abs(dist2 - (2 - 2 * cos64)).max():.1e}")
print("float64: same order:", bool((np.argsort(dist2, kind="stable") == np.argsort(-cos64, kind="stable")).all()))
cos32 = D @ D[0]; dist32 = ((D - D[0]) ** 2).sum(axis=1)
differ = int((np.argsort(-cos32, kind="stable") != np.argsort(dist32, kind="stable")).sum())
print(f"float32: positions that differ between the two orders: {differ} out of {len(D)}")

float64: max gap |dist^2 - (2 - 2cos)| = 1.9e-07
float64: same order: True
float32: positions that differ between the two orders: 0 out of 292

On the corpus index (vectors of the fake encoder) the maximum gap between ‖a − b‖² and 2 − 2·cos in float64 is of the order of 1e-07 and the two orderings coincide on every document. In float32 the theorem still holds, but two almost equal cosines can order differently depending on the computation: if a ranking changes between two runs, look for a tie before you look for a bug.

Anisotropy: why 0.78 does not mean "78% similar"

Take two texts with no relation at all, the documentation of turtle against that of hmac. Intuition says their cosine sits around zero. For real models it is often not so: the vectors do not fill the sphere but occupy a cone, and the cosine between unrelated texts is a high number. The phenomenon is called anisotropy; Ethayarajh (How Contextual are Contextualized Word Representations? Comparing the Geometry of BERT, ELMo, and GPT-2 Embeddings, arXiv:1909.00512) shows that the contextual representations of ELMo, BERT and GPT-2 are not isotropic in any layer. The paper is about word representations in contextual models, not about every sentence encoder: whether yours has it, and how much, you find out by measuring.

Here I do not measure a model: I simulate the mechanism, which is simple enough to compute. I start from isotropic vectors and add to all of them the same direction m with weight a. The dot product of two vectors built this way is about a² and the squared norm about 1 + a², so the expected cosine between two random ones is a² / (1 + a²).

rng = np.random.default_rng(42)
m = rng.standard_normal(768); m /= np.linalg.norm(m)         # one direction shared by all vectors
G = rng.standard_normal((4000, 768))                          # isotropic vectors...
G /= np.linalg.norm(G, axis=1, keepdims=True)
print(f"{'a':>5} {'theory a^2/(1+a^2)':>20} {'mean':>8} {'1%':>8} {'99%':>8}")
for a in (0.0, 0.5, 1.0, 1.5, 2.0):
    V = G + a * m                                             # ...with a fixed component of weight a
    V /= np.linalg.norm(V, axis=1, keepdims=True)
    c = np.einsum("ij,ij->i", V[:2000], V[2000:])             # cosine over 2000 random pairs
    p1, p99 = np.percentile(c, [1, 99])
    print(f"{a:5.1f} {a*a/(1+a*a):20.4f} {c.mean():8.4f} {p1:8.4f} {p99:8.4f}")
print("expected for isotropic vectors: std 1/sqrt(768) =", f"{1/np.sqrt(768):.4f}")

    a   theory a^2/(1+a^2)     mean       1%      99%
  0.0               0.0000   0.0017  -0.0868   0.0821
  0.5               0.2000   0.2008   0.1226   0.2759
  1.0               0.5000   0.5005   0.4492   0.5499
  1.5               0.6923   0.6927   0.6612   0.7225
  2.0               0.8000   0.8004   0.7807   0.8190
expected for isotropic vectors: std 1/sqrt(768) = 0.0361

What it tells us. The theoretical column and the measured mean coincide to the third digit, and the band between the 1st and the 99th percentile is narrow: with a = 1.5 two random vectors sit between 0.66 and 0.72, and a cosine of 0.70 means nothing. With a = 0, instead, the standard deviation is the theoretical one for isotropic vectors, 1/√768 = 0.0361. Three consequences that hold for any encoder with this flaw. A cosine is not a percentage. It is not comparable across models, because each has its own a. Only the order counts, and the metrics of the next section look at the position.

For your encoder the practical question is a single one: what is the mean cosine between pairs of documents picked at random in your corpus? If it is far from zero, any absolute threshold taken from another project falls inside the noise band. It is one line of code, the same as in the listing above with your vectors in place of V, and it must be redone at every model change.

The exercises serve to fix three ideas that are easily confused. The first point is the proof, the second the difference between dot product and cosine when the norms are not unit, the third the reading of a score. If the solution of the second surprises you, reread the section on cosine: it is trap number one in the list at the end.

The corpus and the queries, built offline

To measure an engine you need a labelled retrieval set: queries, documents, and the right answer for each query. The Python standard library contains one ready-made: every public function has a docstring that says what it does and a qualified name that is the question it answers. The label is the correspondence between the two, and nobody wrote it.

import importlib, inspect, re

MODULES = ["abc", "argparse", "array", "ast", "asyncio", "base64", "bisect", "calendar",
           "cmath", "collections", "configparser", "contextlib", "copy", "csv", "dataclasses",
           "datetime", "decimal", "difflib", "enum", "fnmatch", "fractions", "functools",
           "getpass", "glob", "graphlib", "gzip", "hashlib", "heapq", "hmac", "html",
           "importlib", "inspect", "io", "ipaddress", "itertools", "json", "keyword",
           "linecache", "locale", "logging", "math", "mimetypes", "numbers", "operator",
           "pathlib", "pickle", "pprint", "queue", "random", "re", "reprlib", "sched",
           "secrets", "selectors", "shelve", "shlex", "shutil", "signal", "smtplib",
           "socket", "sqlite3", "statistics", "string", "struct", "subprocess", "tarfile",
           "tempfile", "textwrap", "threading", "time", "timeit", "tokenize", "traceback",
           "types", "typing", "unicodedata", "uuid", "warnings", "weakref", "zipfile",
           "zlib", "zoneinfo", "http.client", "urllib.parse", "concurrent.futures",
           "email.utils", "xml.dom.minidom", "wsgiref.util"]

def first_block(doc: str) -> str:
    """The first two paragraphs of the docstring, squeezed onto one line."""
    lines = inspect.cleandoc(doc).split("\n")
    if lines and re.match(r"^[A-Za-z_][\w.]*\(.*\)?\s*(->.*)?$", lines[0].strip()):
        lines = lines[1:]                      # drop the signature line, if there is one
    blocks = re.split(r"\n\s*\n", "\n".join(lines).strip())
    return re.sub(r"\s+", " ", " ".join(blocks[:2])).strip()

def build_corpus(cap_per_module=10, lo=150, hi=900):
    count, corpus = {}, []
    for mod_name in MODULES:
        try:
            mod = importlib.import_module(mod_name)
        except Exception:
            continue                           # module missing on this platform
        for name, obj in sorted(vars(mod).items()):
            if name.startswith("_"):
                continue
            if not (inspect.isfunction(obj) or inspect.isclass(obj)):
                continue
            if getattr(obj, "__module__", None) != mod.__name__:
                continue                       # re-exports are counted by the module of origin
            doc = inspect.getdoc(obj)
            if not doc:
                continue
            text = first_block(doc)
            if not (lo <= len(text) <= hi) or count.get(mod_name, 0) >= cap_per_module:
                continue
            count[mod_name] = count.get(mod_name, 0) + 1
            corpus.append({"name": f"{mod_name}.{name}", "text": text, "full": doc})
    return sorted(corpus, key=lambda d: d["name"])

corpus = build_corpus()
texts = [d["text"] for d in corpus]
QUERIES = [d["name"] for d in corpus]          # the query is the qualified name
N = len(corpus)
wc = np.array([len(t.split()) for t in texts])
print(f"documents: {N}   distinct modules: {len({d['name'].rsplit('.', 1)[0] for d in corpus})}")
print(f"words per document: median {int(np.median(wc))}  mean {wc.mean():.1f}  min {wc.min()}  max {wc.max()}")
own = sum(d["name"].split(".")[-1] in d["text"] for d in corpus)
print(f"documents whose text contains their own name: {own} ({100 * own / N:.1f}%)")
print("example:", corpus[0]["name"])
print("   " + corpus[0]["text"][:90] + "...")

documents: 292   distinct modules: 66
words per document: median 40  mean 45.0  min 11  max 133
documents whose text contains their own name: 86 (29.5%)
example: abc.ABCMeta
   Metaclass for defining Abstract Base Classes (ABCs). Use this metaclass to create an ABC. ...

What the code does. It keeps only functions and classes defined in that module - the check on __module__ prevents os.path.join from ending up under three names - reduces the docstring to the first two paragraphs and puts a cap of ten entries per module, because turtle and inspect would fill half the corpus. The number of documents depends on the Python version and the modules present: with another version you will get a slightly different corpus and close but not identical numbers, and that is fine, because what matters is the method.

The limits of the set, declared instead of hidden. It is single-topic and in English: it favours whoever knows the jargon and says nothing about other languages. It has a single right answer per query, and that makes the metrics pessimistic - statistics.median_low in front of statistics.median counts as a full miss. And the queries are names, not questions: maximum advantage to the lexical side, and that is on purpose.

The exact index, in NumPy

With the vectors normalised in an (N, d) matrix, search is one multiplication and one partial selection. No library is needed: you only need to remember that argsort sorts all N elements when you need ten, whereas argpartition selects them in linear time.

import time

class ExactIndex:
    """Exact vector index: a normalised matrix and a dot product."""

    def __init__(self, vectors, labels):
        norms = np.linalg.norm(vectors, axis=1, keepdims=True)
        self.D = np.ascontiguousarray(vectors / norms, dtype=np.float32)
        self.labels = labels

    def search(self, q, k=10):
        q = np.asarray(q, dtype=np.float32)
        q = q / np.linalg.norm(q)
        scores = self.D @ q                        # (N,) cosines, in one go
        top = np.argpartition(-scores, k)[:k]      # the k best, unordered among themselves
        top = top[np.argsort(-scores[top])]
        return [(self.labels[i], float(scores[i])) for i in top]

def ms_per_query(n, repeats, d=768, seed=0):
    r = np.random.default_rng(seed)
    X = r.standard_normal((n, d), dtype=np.float32)
    idx = ExactIndex(X, list(range(n)))
    q = r.standard_normal(d).astype(np.float32)
    idx.search(q)                                  # warm-up
    t = []
    for _ in range(repeats):
        t0 = time.perf_counter(); idx.search(q); t.append((time.perf_counter() - t0) * 1000)
    return float(np.median(t)), idx.D.nbytes / 2**20

        N     memory  ms/query
     1000      3 MiB   0.66-0.67
    10000     29 MiB     6.5-11
   100000    293 MiB     63-113
   400000   1172 MiB    251-667

How to read the table. Random float32 matrices with 768 dimensions, median per point over several searches, six complete runs on this laptop with BLAS limited to two threads, on a machine shared with other jobs: the time is a range, not a number. The left end is the fastest of the six runs, the right end is their median; the gap is what the load added. The cost is O(N·d): every query touches all the numbers in the index, and growth is almost linear. Memory is pure arithmetic: N·768·4 bytes, so a million documents is about 2.9 GiB (computed, not allocated). In practice the exact index holds up at tens of milliseconds for a hundred thousand documents; beyond that, 250 ms and more per query make an approximate index useful. Below tens of thousands of documents nothing is needed other than this class.

How you measure whether it works

Three metrics, all defined on the rank of the right document. None looks at the score: after the section on anisotropy you know why.

recall@k = (1/|Q|) · Σ_q  1[ rank(q) ≤ k ]                 fraction of queries solved within k
MRR      = (1/|Q|) · Σ_q  1 / rank(q)                      rewards first place
nDCG@10  = (1/|Q|) · Σ_q  1 / log₂(rank(q) + 1)            if rank ≤ 10, otherwise 0

They are three different questions. Recall@k: "is the answer among the first k?". MRR: "how high is it?", with a gain of 1 in first place, 0.5 in second, 0.2 in fifth. nDCG@10: the same idea with a logarithmic discount, the form used in the information retrieval literature.

The difference between "it is among the first five" and "it is first" becomes decisive in the next lesson on RAG. If you pass the model five fragments and the right one is among them, the system can still answer well: recall@5 counts. If you pass one, only recall@1 counts, and a system that looks good on the first can be broken for half the questions on the second.

def rank_of(scores, right_index):
    """1-based rank, with the mean rank over ties."""
    v = scores[right_index]
    greater = int((scores > v).sum())
    ties = int((scores == v).sum())
    return greater + (ties - 1) / 2 + 1        # exactly 1 only if it is truly the best

def metrics(ranks):
    r = np.asarray(ranks, dtype=float)
    return {"recall@1": float((r <= 1).mean()),
            "recall@5": float((r <= 5).mean()),
            "MRR": float((1 / r).mean()),
            "nDCG@10": float(np.mean(np.where(r <= 10, 1 / np.log2(r + 1), 0.0)))}

The detail that separates a measurement from an illusion: ties. BM25 gives zero to every document that contains none of the query terms, and on this corpus that happens to the right document in 71 queries out of 292; in 26 of those no document gets a score. With the rank as "how many beat it, plus one", whoever gives zero to everything would get rank 1 on those 26 queries: 8.9 points of recall@1 given away. With the mean rank, a tie among 292 documents is worth 146.5.

The comparison that brings you back down to earth

Lexical retrieval is not a fossil. BM25 (Robertson and Zaragoza, The Probabilistic Relevance Framework: BM25 and Beyond, Foundations and Trends in Information Retrieval 3(4), 2009) is still the baseline to beat, and it is twenty lines: it weights every term by rarity, saturates repetitions, normalises by length.

score(q, D) = Σ_{t ∈ q}  IDF(t) · ( tf(t,D) · (k₁ + 1) ) / ( tf(t,D) + k₁ · (1 − b + b · |D| / avgdl) )
IDF(t)      = ln( 1 + (N − df(t) + 0.5) / (df(t) + 0.5) )
with k₁ = 1.5 and b = 0.75

class BM25:
    def __init__(self, tokenised_docs, k1=1.5, b=0.75):
        self.k1, self.b, self.docs = k1, b, tokenised_docs
        self.N = len(self.docs)
        self.length = np.array([len(d) for d in self.docs], dtype=np.float64)
        self.avg_length = self.length.mean()
        self.freq = [collections.Counter(d) for d in self.docs]
        df = collections.Counter()
        for c in self.freq:
            df.update(c.keys())                 # once per document, not per occurrence
        self.idf = {t: math.log(1 + (self.N - n + 0.5) / (n + 0.5)) for t, n in df.items()}

    def scores(self, query_tokens):
        s = np.zeros(self.N)
        for t in query_tokens:
            if t not in self.idf:
                continue                        # a term never seen says nothing
            tf = np.array([c.get(t, 0) for c in self.freq], dtype=np.float64)
            denom = tf + self.k1 * (1 - self.b + self.b * self.length / self.avg_length)
            s += self.idf[t] * (tf * (self.k1 + 1)) / np.where(denom == 0, 1, denom)
        return s

What the code does. It counts the frequencies at construction, derives the IDF from them, and at query time sums the contribution of each term in vector form. The tokenisation does one thing that matters: it splits get_terminal_size into words, otherwise a function name would be a single term that never appears in prose.

I compare the two systems, plus two fusions, on the same 292 queries (the qualified name) and the same corpus. Pay attention to how you read the "fake encoder" row: it is not a semantic model, it is retrieval by words and trigrams, so the table says how the procedures behave (rank, fusion, tuning) and not how much a trained encoder is worth.

The hybrid with the parameters from the paper - the reciprocal rank fusion of Cormack, Clarke and Buettcher (Reciprocal Rank Fusion outperforms Condorcet and individual Rank Learning Methods, SIGIR 2009), which sums 1/(k + rank) with k = 60 - gains one point of recall@1 but loses six and a half points of recall@5 against the dense side alone: fusing lists of different quality drags the better one toward the worse. With k = 10 and weight 0.7 on the dense side the fusion wins on all four metrics, but I chose those parameters by looking at the same queries I measure them on: the advantage is optimistic, and has to be confirmed on a partition you did not use for tuning.

def rrf(score_lists, weights=None, k=60, cutoff=50):
    """Reciprocal rank fusion over the first `cutoff` positions of each list."""
    n = len(score_lists[0])
    weights = weights or [1.0] * len(score_lists)
    s = np.zeros(n)
    for scores, weight in zip(score_lists, weights):
        order = np.argsort(-np.asarray(scores), kind="stable")[:cutoff]
        for position, index in enumerate(order, start=1):
            s[index] += weight / (k + position)      # only the rank, not the score
        # a document outside the first `cutoff` adds nothing for this system
    return s

bm25 = BM25([words_of(t) for t in texts])
S_lex = np.array([bm25.scores(words_of(q)) for q in QUERIES])   # lexical scores, (N, N)
S_den = Q @ D.T                                                  # dense scores, (N, N)
r_lex = [rank_of(S_lex[i], i) for i in range(N)]
r_den = [rank_of(S_den[i], i) for i in range(N)]
lex = np.array(r_lex) <= 1; sem = np.array(r_den) <= 1
print("queries where only the dense side puts the document first: ", int((sem & ~lex).sum()))
print("queries where only the lexical side puts it first:         ", int((~sem & lex).sum()))
print("queries where both put it first:                           ", int((sem & lex).sum()))
print("queries where neither of the two puts it first:            ", int((~sem & ~lex).sum()))
print(f"oracle (the better of the two for each query): recall@1 = {(sem | lex).mean():.3f}")

queries where only the dense side puts the document first:  28
queries where only the lexical side puts it first:          28
queries where both put it first:                            90
queries where neither of the two puts it first:             146
oracle (the better of the two for each query): recall@1 = 0.500

The point of the section. There are 28 queries that only the lexical side solves and 28 that only the dense side solves: the two fail in a different, uncorrelated way. An oracle that chose the better of the two for each query would reach 0.500 of recall@1 against 0.404, and fusion serves to capture that margin: with k = 10 and weight 0.7 it captures about a third of it (0.435). Fusing is not a whim: it is the only way not to throw away the queries that one of the two solves alone. But it has to be tuned: adopted by eye, here it loses on recall@5.

Where one wins, where the other wins

Where the dense side wins, the name shares character trigrams with the text without sharing whole words (it is a hypothesis, I did not verify it): string.capwords (rank 14 against the lexical 178), smtplib.SMTPResponseException (2 against 155.5), abc.update_abstractmethods (2 against 150). Where the lexical side wins, the query is an identifier that appears whole in the text: statistics.kde_random (1 against 10), ipaddress.ip_network (1 against 6), collections.ChainMap (1 against 5). If your domain has error codes or identifiers, the lexical side is a component to keep.

Paraphrases, a separate set

Paraphrases are a case apart: the twelve queries I wrote in English without the function name (for example "a file that disappears by itself when I close it", right answer tempfile.TemporaryFile) give, on this corpus, recall@1 of 0.250 for BM25 and 0.333 for the fake encoder, recall@5 of 0.583 and 0.667. Neither understands meaning: these are low numbers by construction, and that is the point. With a trained encoder this is the measure that has to go up, and you cannot deduce it from the measure on names, because the two families of queries reward different things. Keep them in a separate set.

The exercise ties together two things that sit far apart in the code: the rank of the right document in a list and its placement after fusion. If your result at point 2 differs from mine, check that you counted ranks from 1 and not from 0.

Approximate indexes: IVF measured, HNSW described

When the 61-72 ms per query at a hundred thousand documents become a problem, you stop comparing the query with everything and accept being wrong sometimes. That is the pact of approximate indexes: speed is bought in exchange for recall.

IVF (inverted file, in the form described by Johnson, Douze and Jégou in Billion-scale similarity search with GPUs, arXiv:1702.08734) starts from an elementary idea: group the vectors into nlist partitions with k-means and, at query time, compare first the centroids and then only the nprobe most promising partitions. If the right neighbour sits in a partition whose centroid is not among the closest, it is lost: hence the error.

from sklearn.cluster import KMeans

class IVF:
    """Minimal IVF: k-means to partition, then a scan of the probed cells only."""

    def __init__(self, D, nlist=16, seed=0):
        self.D = D
        km = KMeans(n_clusters=nlist, n_init=3, random_state=seed).fit(D)
        C = km.cluster_centers_.astype(np.float32)
        self.C = C / np.linalg.norm(C, axis=1, keepdims=True)
        self.cells = [np.where(km.labels_ == c)[0] for c in range(nlist)]

    def search(self, q, k=10, probes=1):
        closeness = self.C @ q                              # which cells are worth opening
        chosen = np.argpartition(-closeness, probes - 1)[:probes]
        candidates = np.concatenate([self.cells[c] for c in chosen])
        scores = self.D[candidates] @ q                     # the scan, but only in here
        k = min(k, len(candidates))
        top = candidates[np.argpartition(-scores, k - 1)[:k]]
        return top[np.argsort(-(self.D[top] @ q))]

vocab = sorted({w for t in texts for w in re.findall(r"[a-z]{3,}", t.lower())})
W = embed(vocab)                                            # one vector per distinct word
ivf = IVF(W, nlist=16)
rg = np.random.default_rng(0)
queries = rg.choice(len(W), size=200, replace=False)
# exact ground truth: the 10th-nearest score, ties with it count as correct
truth = [np.sort(W @ W[q])[::-1][10] - 1e-6 for q in queries]
sizes = sorted(len(c) for c in ivf.cells)
print(f"indexed set: {len(W)} vectors of {W.shape[1]} dimensions; {len(queries)} queries")
print(f"IVF with 16 cells: smallest size {sizes[0]}, median {sizes[len(sizes)//2]}, largest {sizes[-1]}")
print(" probes   visited   % corpus   recall@10")
for probes in (1, 2, 4, 6, 8, 12, 16):
    recall, visited = [], []
    for q, v in zip(queries, truth):
        found = [x for x in ivf.search(W[q], k=11, probes=probes).tolist() if x != q][:10]
        recall.append(sum(float(W[x] @ W[q]) >= v for x in found) / 10)
        visited.append(sum(len(ivf.cells[c]) for c in np.argpartition(-(ivf.C @ W[q]), probes - 1)[:probes]))
    print(f"{probes:6d} {np.mean(visited):9.0f} {100*np.mean(visited)/len(W):9.1f}% {np.mean(recall):11.3f}")

To measure recall you need a set with a known exact answer. I indexed the 1,874 vectors of the distinct words in the docstrings (same fake encoder, 768 dimensions), with 200 words as queries; the truth is the exact search, and ties with the tenth neighbour count as correct, because with sparse vectors many scores coincide and an arbitrary label would falsify the measurement. I declare it: these are vectors of the fake encoder, not of a trained model, so the shape of the curve is informative and the values are not.

indexed set: 1874 vectors of 768 dimensions; 200 queries
IVF with 16 cells: smallest size 34, median 69, largest 543
 probes   visited   % corpus   recall@10
     1       236      12.6%       0.607
     2       412      22.0%       0.733
     4       712      38.0%       0.862
     6       929      49.6%       0.917
     8      1126      60.1%       0.952
    12      1491      79.5%       0.982
    16      1874     100.0%       1.000

How to read the curve. With one probe you visit 12.6% of the vectors and recover 60.7% of the ten true neighbours. With four probes you visit 38% of the corpus for 0.862, with eight 60% for 0.952. The shape is the expected one: recall rises quickly and then pays more and more for the last points, from 0.952 to 1.000 costs 40% more of the corpus. Note the cell sizes (from 34 to 543 vectors): k-means does not balance them, and a large cell weighs more in time. That is why nobody looks for full recall: you decide how much to lose and you tune nprobe. At this size the IVF does not save time, because the bookkeeping in Python costs more than the scan it avoids; the lesson measures recall, not speed.

HNSW (Malkov and Yashunin, Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, arXiv:1603.09320) uses a graph in which every vector is connected to M neighbours across several stacked levels: at the top few nodes with long links, like intercontinental routes, at the bottom all the nodes with short links, like city streets. The search enters from the top, goes greedily toward the node closest to the query and, when it no longer improves, drops one level. Three parameters: M (richer graph, more memory), efConstruction (better graph, slower construction) and efSearch, the recall-latency knob, like nprobe.

Described and not measured: hnswlib is not installed, and an HNSW written from scratch in Python would give latencies that say nothing about the real implementation. The official Redis documentation on vectors (Redis, vector indexes) shows both structures as a field type: FLAT, the exact scan of our class, and HNSW. On a small corpus FLAT does very well.

Trade-offs

• Exact versus approximate. The exact index is never wrong and costs O(N·d): about 0.7 ms at a thousand documents, 63 ms at a hundred thousand, 251 ms at four hundred thousand (fastest runs). The approximate one buys time with recall: at four probes out of sixteen we lose 14% of the true neighbours. Mitigation: start exact, move to the approximate one when the measured latency leaves the budget.
• Vector size versus memory. The 292 documents take less than 1 MiB; a million at 768 dimensions in float32 takes about 2.9 GiB, and that is why every real service quantises or reduces the dimensions. Both cost recall: the reduction is not free just because the library offers it as a parameter.
• Short versus long fragments. The short one gives a sharp vector and a poor context; the long one contains the answer but dilutes it, and above the encoder's limit it is truncated. There is no right size: there is a size to measure on your corpus.
• One index versus two. Lexical and dense together give the best result (recall@1 0.435 against 0.404 on the test corpus), but they are two indexes to keep aligned and two sets of parameters to tune. On a small corpus, one index with the measured metric is worth more than two with the hoped-for metric.
• Generic model versus domain model. The generic one works at once and badly on jargon; the specialised one requires data and an evaluation set of your own. Middle way: start from the generic one, build the evaluation as here with inspect, and use that number to decide whether the jump is worth it.

The five items are the same question asked on different axes: how much you are willing to pay, in latency, memory or maintenance, to recover recall. The common thread is that no answer is right in the abstract, and each is decided with a measurement on your corpus: changing the order of the items changes nothing, which is why they are a list.

The traps you really fall into

1. Dot product on non-normalised vectors, called cosine. Symptom: long documents at the top of any query. Cause: the norm entered the score, length became relevance. Remedy: normalise at indexing time and put an assert on the norms.
2. Comparing cosines across two models. Symptom: "the new model gives lower scores, so it is worse". Cause: each space has its own distribution, as the simulation with a different a shows. Remedy: order metrics only, on the same set of queries.
3. Choosing a threshold by eye. Symptom: with 0.8 the system almost never answers, with 0.5 it always answers and at random. Cause: the threshold comes from another space. Remedy: derive it from the percentiles of your corpus and redo it at every model change.
4. Fragments longer than the encoder's maximum. Symptom: none, and that is the point - the service truncates and returns a valid vector of the prefix. Every encoder declares its limit in the model card. An estimate without a tokeniser, in words: of the 292 whole docstrings in the corpus, 23 (7.9%) exceed 190 words, and the words over that limit are 2,310 out of 24,134 (9.6% of the text). The 190 is a prudent estimate of a limit of 256 tokens, not a measurement; the real count requires the tokeniser of your encoder. Remedy: count the tokens before indexing and log every truncation.
5. Index built with one model, queried with another. Symptom: random but not empty results. Cause: the two spaces have nothing in common, and if they have the same number of dimensions the bug survives deployment. Also in a subtle version: the card of nomic-embed-text-v1.5 prescribes the prefixes search_document: and search_query:, and changing them on one side only shifts the results. Remedy: model and prefixes in the index metadata.
6. Querying in a language different from the corpus. Symptom: plausible and wrong results, with no errors. Remedy: multilingual encoder, query translation or an index in two languages, measuring each route with your own paraphrases in the second language; do not trust a "multilingual" label you have not measured.
7. Measuring a single k. Symptom: retrieval "works" in evaluation and the downstream system answers badly, because you measured recall@5 and your RAG passes a single fragment. Remedy: always report recall@1, recall@5 and MRR together.

Seven traps, a single root: treating the similarity score and the model as stable facts, when they are properties of the corpus-encoder pair. The first three are errors in reading the number, the fourth and the fifth are pipeline errors that raise no exception, the last two are errors of measurement. The order here does not matter, but it is worth starting the checks from the fifth: it is the hardest to see.

The exercises with solutions are in the file esercizi.py (Python 3.12+, NumPy 2.3), on a new corpus of twelve mechanic's workshop adverts (in Italian): normalisation and order check, BM25 from scratch with the arithmetic that checks out by hand, the three metrics plus reciprocal rank fusion. The file was not run in this revision of the article.

What to take away

A vector index is a library sorted by meaning, and the meaning is that of the model you chose: the quality of retrieval is a property of the corpus-encoder pair, not of the code. The code is small - a normalised matrix, a dot product, argpartition - and below tens of thousands of documents nothing else is needed. The serious work lies elsewhere: a labelled set of queries, recall@1 and recall@5 measured separately, and lexical search switched on, which on 28 queries out of 292 was the only one to find the answer.

What sends people off course most often is not an architecture choice: it is taking the similarity score for an absolute measure. If the vectors sit in a cone, two unrelated texts already have a high cosine, and a threshold written by hand falls into that band by chance. Order, measure the positions, and remember that a vector index cannot say "it isn't there". Your job is not to make a score go up, it is to know at which position the right answer ends up - and what you do when it isn't there.

Sources

• Ethayarajh, How Contextual are Contextualized Word Representations? Comparing the Geometry of BERT, ELMo, and GPT-2 Embeddings (arXiv:1909.00512) - the claim that contextual representations are not isotropic in any layer; consulted on 2026-11-12.
• Malkov and Yashunin, Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (arXiv:1603.09320) - the multi-level structure of HNSW and the random choice of the maximum layer; consulted on 2026-11-12.
• Johnson, Douze and Jégou, Billion-scale similarity search with GPUs (arXiv:1702.08734) - the reference for the IVF index; consulted on 2026-11-12.
• Reimers and Gurevych, Sentence-BERT (arXiv:1908.10084) - why encoders trained for sentences exist; consulted on 2026-11-12.
• Model card of nomic-embed-text-v1.5 on Hugging Face - the prefixes search_document and search_query; consulted on 2026-11-12.
• Redis, documentation of vector indexes - existence of the FLAT and HNSW index types; consulted on 2026-11-12.
• NumPy, documentation of numpy.argpartition - the partial selection used in the exact index; consulted on 2026-11-12.
• The figures in the lesson come from the listings printed here, run twice with identical output (the timings: six runs, reported as a range). The citations of BM25 (Robertson and Zaragoza, 2009) and of Reciprocal Rank Fusion (Cormack, Clarke and Buettcher, SIGIR 2009) are bibliographic and I did not reopen them in this revision.

The first seven sources are primary and I opened them on 2026-11-12 to check the title and the content cited; the last entry instead declares where the figures come from, because a measurement made in the repository is cited with the command that produces it.