--- title: 'Vector Databases' source: 'https://academia.sh/en/courses/embeddings-and-retrieval-augmented-generation/vector-databases' course: 'Embeddings and Retrieval-Augmented Generation' language: en updated: '2026-10-21T05:02:29+00:00' license: 'CC BY-SA 4.0' objectives: - 'Measures exhaustive search and indexed search side by side on the same query set as recall and comparison count.' - 'Counts how the number of probes in the bucket-based index changes recall and the concept precision of the first five.' - 'Measures the reachability limit of the neighborhood graph and shows that recall cannot rise above this limit.' - 'Determines the meaningful-difference threshold of this workload by measuring the difference between two index builds.' --- # Vector Databases Removing the assumption that a query is compared with the whole corpus and measuring the price of approximation. On two hundred fictional documents, exhaustive search needs 200 comparisons per query; the bucket-based index holds recall at 0.9500 with 16 buckets and 2 probes and brings the comparisons down to 47.2, and with 4 probes recall is 1.0000 and comparisons are 69.2. With 1 probe recall falls to 0.7200 and the concept precision of the first five falls from 0.4700 to 0.3800: the index damages not only the candidate set but also the answer. The neighborhood graph at degree 8 can reach only 27 documents from the entry node and its recall is 0.0800; at degree 48 it stores 9600 edges and, with 84.9 comparisons, stays at 0.7650, that is, both more expensive and worse than the bucket-based index. The difference between two index builds is 0.0100, and this is the threshold of this workload. The previous three lessons built the embedding as a search key, measured how much of the domain fit it carries, and counted where two similarity measures diverge on the same query. All three shared a silent assumption: when a query arrived, it was compared with **every document** in the corpus. With two hundred documents this assumption is cheap. When the corpus grows it stops being cheap, because the comparison count grows in direct proportion to the document count and every query has to read the entire corpus. The vector store reduces this load with an **index**: when a query arrives, only a part of the corpus is looked at. Looking at a part means the right neighbor may remain in the part that was not looked at; for this reason indexed search is called **approximate nearest neighbor search** and it does not have to give the answer that exhaustive search gives. What this lesson measures is that difference: **what the approximation costs**. Against the baseline of exhaustive search, the **recall** and the **comparison count** of two index structures are printed side by side, and it is shown that one of them stays both below the baseline and expensive even though it multiplies the storage. - **EV31.** The corpus, the embedding procedure and the query set are **fictional**; no real embedding endpoint or vector store is called. The seed is **20260218**. - **EV32.** The simulator surface first reduces the surface form to a concept and then the concept to thirty-two dimensions; the document side and the query side share no token. All measurements in this lesson are made with the in-domain embedding. - **EV33.** The baseline is **exhaustive search**: every query is compared with all two hundred documents and the first five results are taken. - **EV34. Retrieval recall** is read against the index in this lesson: the size of the intersection of the index's first five and the first five of exhaustive search, divided by five. A recall of 1.0000 means the index gave the **same** answer as the baseline, not that it gave the correct answer. - **EV35. Concept precision** is the share of the five retrieved documents that carry the target concept of the query, and it shows the quality of the baseline itself. - **EV36. The comparison count** is the number of cosine similarities computed in a single query. No time is written; the build cost of the index is counted separately as **stored edges** or as the **representative count**. - **EV37.** Index structures are named by their **behavior**: bucket-based index and neighborhood graph. No vector store, library or method name is written. - **EV38.** The build of the bucket-based index **depends on the seed**. The two runs of this lesson measure the same query set on two separate index builds; the difference between them is the **threshold** of this workload, and differences below it count as unmeasured. The nearest neighbor procedure itself was built and measured in the Unsupervised Learning course of the Machine Learning and Data Science curriculum; it is not repeated here. The only thing added is the cost of **not running the whole** of that procedure. ## The Baseline of Exhaustive Search The block below builds the fictional corpus and the embedding simulator, then prints the baseline. The baseline gives two numbers: the result set that the index will be measured against for what it misses, and the quality of that set **itself**. ```python # FICTIONAL corpus and FICTIONAL embedding simulator. No real endpoint is called. SEED, M32 = 20260218, 0xFFFFFFFF DIM = 32 def rng(t): x = ((t ^ (t >> 16)) * 2246822507) & M32 x = ((x ^ (x >> 13)) * 3266489909) & M32 s = [(x ^ (x >> 16)) & M32] def next_value(): s[0] = (s[0] * 1664525 + 1013904223) & M32 return s[0] / 4294967296 return next_value def pick(u, w): t = 0.0 for i, x in enumerate(w): t += x if u < t: return i return len(w) - 1 # ---- FICTIONAL semantic axis: each concept has a separate surface form on the document side and on the query side CLASSES = ["tariff", "fault", "meter", "outage", "maintenance"] CODE = {"tariff": "TR", "fault": "AR", "meter": "SY", "outage": "KS", "maintenance": "BK"} CONCEPTS = { # concept: (label, document-side form, query-side form) "tier": ("tariff", "tier threshold", "which band am i in"), "unit_rate": ("tariff", "unit price", "fee per cubic metre"), "subscriber_type": ("tariff", "subscriber type", "home or shop"), "switch": ("tariff", "tariff switch", "changing plan"), "fault_code": ("fault", "fault code", "error id"), "leak": ("fault", "line leakage", "water escaping"), "pressure": ("fault", "pressure drop", "weak flow"), "crew": ("fault", "field crew", "who will be sent"), "index_value": ("meter", "index value", "what the dial shows"), "reading": ("meter", "reading procedure", "how it gets saved"), "replacement": ("meter", "meter replacement", "new hardware"), "verify": ("meter", "reading verification", "typed in wrong"), "planned": ("outage", "planned outage", "announced stoppage"), "notice": ("outage", "notice channel", "where i hear about it"), "duration": ("outage", "outage duration", "how long it lasts"), "restoration": ("outage", "service restoration", "when it comes back"), "periodic": ("maintenance", "periodic maintenance", "regular checkup"), "valve": ("maintenance", "valve inspection", "tap shutoff routine"), "filter_swap": ("maintenance", "filter swap", "cleaning part"), "calibration": ("maintenance", "calibration record", "gauge accuracy"), } KEYS = list(CONCEPTS) COMMON = ["entry", "region", "term", "step", "form", "approval", "note"] DOCUMENTS = [] for i in range(200): r = rng(SEED + 7919 * i) s = CLASSES[pick(r(), [0.22, 0.24, 0.20, 0.18, 0.16])] pool = [k for k in KEYS if CONCEPTS[k][0] == s] main = pool[int(r() * len(pool))] n = 2 + int(r() * 4) paragraphs, concepts = [], [main] for _ in range(n): y = pool[int(r() * len(pool))] concepts.append(y) o = COMMON[int(r() * len(COMMON))] paragraphs.append(f"{CONCEPTS[y][1]} for {o} is kept and written together with {CONCEPTS[main][1]}") DOCUMENTS.append({"code": f"{CODE[s]}{i + 1:03d}", "label": s, "main": main, "concepts": concepts, "title": f"{CONCEPTS[main][1]} procedure", "paragraphs": paragraphs}) def doc_text(d): return d["title"] + " " + " ".join(d["paragraphs"]) def _to_concepts(m): # the surface form is first mapped to a concept v = [0.0] * len(KEYS) dm = " " + m.lower() + " " for i, k in enumerate(KEYS): if CONCEPTS[k][1] in dm: v[i] += 1.0 if CONCEPTS[k][2] in dm: v[i] += 1.0 return v PROJECTION = [] for i in range(len(KEYS)): r = rng(SEED ^ (i + 1) * 2654435761) PROJECTION.append([r() * 2 - 1 for _ in range(64)]) def embed(m, dim=DIM): # the concept is then reduced to fewer dimensions v = [0.0] * dim for i, a in enumerate(_to_concepts(m)): if a: for j in range(dim): v[j] += a * PROJECTION[i][j % 64] n = sum(x * x for x in v) ** 0.5 return [x / n for x in v] if n else v def cosine(a, b): return sum(x * y for x, y in zip(a, b)) QUERIES = [] # FICTIONAL query set: the query side is separate from the document side for i in range(40): r = rng(SEED + 104729 * i) d = DOCUMENTS[int(r() * len(DOCUMENTS))] QUERIES.append({"text": f"{CONCEPTS[d['main']][2]} {COMMON[int(r() * len(COMMON))]}", "label": d["label"], "concept": d["main"]}) K = 5 VEC = [embed(doc_text(d)) for d in DOCUMENTS] QVECS = [embed(q["text"]) for q in QUERIES] BASELINE = [sorted(range(len(VEC)), key=lambda i: -cosine(qv, VEC[i]))[:K] for qv in QVECS] def concept_precision(retrieved): hits = sum(DOCUMENTS[i]["main"] == QUERIES[n]["concept"] for n, g in enumerate(retrieved) for i in g) return hits / (len(retrieved) * K) print(f"corpus {len(DOCUMENTS)} documents , distinct vectors " f"{len({tuple(v) for v in VEC})} , queries {len(QUERIES)}") print(f"exhaustive search: {len(VEC)} comparisons per query , " f"total {len(VEC) * len(QUERIES)}") print(f"concept precision of the first {K} results {concept_precision(BASELINE):.4f}") ``` ``` corpus 200 documents , distinct vectors 52 , queries 40 exhaustive search: 200 comparisons per query , total 8000 concept precision of the first 5 results 0.4700 ``` The second line is the whole justification for an index: eight thousand cosine similarity computations for forty queries. The third line measures the baseline itself. Exhaustive search carries the target concept of the query in only 0.4700 of the five documents it retrieves. The baseline is **not perfect**; the index cannot rise above it, it can only approach it or move away from it. The last number of the first line will matter in the next section: there are two hundred documents but only **52 distinct vectors**. Documents share concept sets, so they overlap in the vector space. ## Bucket-Based Index The bucket-based index partitions the corpus in advance. A handful of documents chosen by the seed become **representatives**, and every document goes into the bucket of the representative it most resembles. When a query arrives it is first compared with the representatives, and then only the nearest **probe** count of buckets is looked into. ```python def build_buckets(buckets, seed): """FICTIONAL bucket-based index: a single-pass assignment to representatives chosen by the seed.""" r, representatives = rng(seed), [] while len(representatives) < buckets: i = int(r() * len(VEC)) if i not in representatives: representatives.append(i) members = [[] for _ in representatives] for i in range(len(VEC)): members[max(range(buckets), key=lambda c: cosine(VEC[i], VEC[representatives[c]]))].append(i) return representatives, members def bucket_search(qv, representatives, members, probes, k=K): order = sorted(range(len(representatives)), key=lambda c: -cosine(qv, VEC[representatives[c]])) candidates = [i for c in order[:probes] for i in members[c]] return sorted(candidates, key=lambda i: -cosine(qv, VEC[i]))[:k], len(representatives) + len(candidates) def recall(found, base): return len(set(found) & set(base)) / len(base) def bucket_measure(buckets, probes, seed=SEED): representatives, members = build_buckets(buckets, seed) a = comps = 0 retrieved = [] for n, qv in enumerate(QVECS): b, c = bucket_search(qv, representatives, members, probes) retrieved.append(b) a += recall(b, BASELINE[n]) comps += c return a / len(QVECS), comps / len(QVECS), concept_precision(retrieved) print("buckets probes recall comparisons concept precision") for buckets, probes in ((8, 1), (16, 1), (16, 2), (16, 4), (25, 2), (25, 4)): a, c, kk = bucket_measure(buckets, probes) print(f"{buckets:>7} {probes:>6} {a:>6.4f} {c:>11.1f} {kk:>17.4f}") u = [bucket_measure(16, 2, SEED + t)[0] for t in (0, 1)] print(f"two builds buckets=16 probes=2: {u[0]:.4f} , {u[1]:.4f}" f" -- difference {abs(u[0] - u[1]):.4f}") ``` ``` buckets probes recall comparisons concept precision 8 1 0.5800 39.7 0.4250 16 1 0.7200 34.9 0.3800 16 2 0.9500 47.2 0.4700 16 4 1.0000 69.2 0.4700 25 2 0.8900 45.0 0.4500 25 4 1.0000 61.7 0.4700 two builds buckets=16 probes=2: 0.9500 , 0.9600 -- difference 0.0100 ``` The last line gives the threshold of this lesson. The same query set, the same setting, only the seed that chooses the representatives is different: 0.9500 and 0.9600. The build difference carries **0.0100**, so differences of this size in the table do not count as measured. The bucket-based index is not a fixed structure; **which documents are the representatives** moves the result. The main reading of the table is in four numbers. With 16 buckets and 4 probes recall is **1.0000**: the index gives all five of the five documents that exhaustive search gives, and it does so with **69.2** comparisons instead of 200. Going down to 2 probes, recall falls to 0.9500 and the comparisons to 47.2. The 0.0500 in between is five times the threshold, so it is a real loss; in return a third of the comparisons is won. At 1 probe the table breaks: recall is 0.7200 and the comparisons are 34.9. Reading only one bucket fewer wins a quarter of the comparisons and takes away a quarter of the recall. The last column says what this means in the answer. The concept precision of exhaustive search was 0.4700; with 16 buckets and 1 probe it drops to **0.3800**. The index does not only narrow the candidate set, it also lowers the **correctness of the retrieved documents**. The reason the loss looks smaller than the 0.2800 drop in the recall column is that the baseline already retrieves less than half correctly: while continuing to miss what the baseline misses, the index also misses some of what the baseline catches. This is a cost that is not read in one measure, and the rule of the course asks for two columns for this reason. ## Neighborhood Graph and Reachability The second structure does not partition the corpus, it **connects** it. Every document is linked by an edge to a given number of documents it most resembles; the search starts from an entry node and moves to a neighbor if one of its neighbors is closer to the query. Comparison is made only along the path walked. ```python def build_graph(degree): """FICTIONAL neighborhood graph: every document is linked to the 'degree' most similar documents.""" g = [] for i in range(len(VEC)): s = sorted(range(len(VEC)), key=lambda j: -cosine(VEC[i], VEC[j])) g.append([j for j in s if j != i][:degree]) return g def reachable(graph, entry=0): seen, stack = {entry}, [entry] while stack: for j in graph[stack.pop()]: if j not in seen: seen.add(j) stack.append(j) return len(seen) def graph_search(qv, graph, entry=0, k=K): score, comps, expanded = {entry: cosine(qv, VEC[entry])}, 1, set() while True: pending = [i for i in score if i not in expanded] if not pending or max(score[i] for i in pending) < max(score.values()): break i = max(pending, key=lambda x: score[x]) expanded.add(i) for j in graph[i]: if j not in score: score[j] = cosine(qv, VEC[j]) comps += 1 return sorted(score, key=lambda x: -score[x])[:k], comps print("degree edges reachable recall comparisons") for degree in (8, 16, 32, 48): graph = build_graph(degree) a = comps = 0 for n, qv in enumerate(QVECS): b, c = graph_search(qv, graph) a += recall(b, BASELINE[n]) comps += c print(f"{degree:>6} {degree * len(VEC):>5} {reachable(graph):>9}" f" {a / len(QVECS):>6.4f} {comps / len(QVECS):>11.1f}") ``` ``` degree edges reachable recall comparisons 8 1600 27 0.0800 14.0 16 3200 31 0.1750 26.0 32 6400 200 0.5250 59.1 48 9600 200 0.7650 84.9 ``` The reachable column is the explanation of this table and does not depend on any query: it counts **how many documents can be reached** by following the edges from the entry node. At degree 8 this number is **27**, not 200. The graph is fragmented; the component that holds the entry node is smaller than a seventh of the corpus. However much budget the search is given, it cannot look at the remaining 173 documents, so recall hits its ceiling at 0.0800. This is a number of the **structure**, not of the search, and it is independent of the run. The cause of the fragmentation is the number 52 in the first block. Two hundred documents sit on only 52 distinct vectors, so the nearest neighbors of every document are documents with the **same** vector as its own. At degree 8 all eight neighbors of a node are its own twins and the edges do not leave that islet. At degree 32 the number of twins is exceeded, the edges reach other concepts and reachability suddenly becomes 200. Even the connected graph cannot catch the baseline. At degree 48 recall is **0.7650** and the comparisons are **84.9**. On the same query set the bucket-based index, with 16 buckets and 2 probes, gave a recall of 0.9500 with **47.2** comparisons. The graph is both less accurate and more expensive, and on top of that it stores 9600 edges; what the bucket-based index stores is 16 representatives and 200 membership records, that is, 216 values. The added scaffolding does not **improve** the work here, it worsens it on both axes at once. Which structure approximate nearest neighbor search is built with is not a matter of taste; the distribution of the corpus in the vector space makes one structure work and the other not. In a corpus with many repeated documents the graph clogs, the partitioning does not. ## Summary - Exhaustive search needs 200 comparisons per query and carries the target concept in 0.4700 of the five documents it retrieves; the baseline is not perfect and the index cannot rise above it. - The bucket-based index with 16 buckets and 4 probes holds recall at 1.0000 and brings the comparisons down to 69.2, with 2 probes to 47.2 at a recall of 0.9500; with 1 probe recall falls to 0.7200. - The index damages not only the candidate set but also the answer: with 16 buckets and 1 probe the concept precision of the first five falls from 0.4700 to 0.3800. - In the neighborhood graph the ceiling of recall is **reachability**; at degree 8 only 27 documents can be reached from the entry node, so recall stays at 0.0800, and this number is independent of the run. - Even a connected graph stays below the bucket-based index: at degree 48 there are 9600 edges, 84.9 comparisons and a recall of 0.7650; the added scaffolding loses on both axes at once here. - The difference between two index builds is 0.0100; on this workload smaller differences count as unmeasured. ## Next Step In all the measurements of this lesson the query was directed at the **whole** corpus; the index only restricted where in that corpus to look. A real retrieval request often does not arrive like this: only the documents of a certain class, of a certain period or belonging to a certain region are wanted. Is this restriction placed before or after the vector search, and what is the difference between the two. The next lesson puts a metadata filter next to the bucket-based index and counts what happens to recall as the filter selectivity increases: because the index is built over the whole corpus, as the filter narrows, the number of candidates left standing inside the buckets that are looked at collapses, and from some point on search without an index becomes both more accurate and cheaper than the indexed one.