Skip to content
LearnMLByDoing
Free

4.5 Embeddings, vector search and retrieval-augmented generation

38 minPro, with free previewintermediateRAGHNSWIIRCompendium

Retrieval-augmented generation answers from your own documents by embedding every chunk as a vector, finding the chunks that point the same way as the question, and putting them in the prompt.

01Embeddings and cosine similarity

An embedding model maps a piece of text to a vector di∈Rd\tok{chunk}{\mathbf{d}_i}\in\mathbb{R}^d so that texts with similar meaning point in similar directions. I want my money back and How do I get a refund? share almost no words, yet a good model puts them a few degrees apart; How do I reset my password? lands far from both. Production models use dd from a few hundred to a few thousand; this lab uses d=3d = 3 so every vector can be drawn. The sphere holds n=240n = 240 chunks of a product's documentation: five topics (billing, auth and SSO, rate limits, data retention, compute) of 40 chunks each, three groups of duplicated passages and 31 miscellaneous chunks.

cos⁡θi=q⋅di∥q∥ ∥di∥\tok{cosine}{\cos\theta_i}=\frac{\tok{query}{\mathbf{q}}\cdot\tok{chunk}{\mathbf{d}_i}}{\lVert\mathbf{q}\rVert\,\lVert\mathbf{d}_i\rVert}
Cosine similarity: 1 for the same direction, 0 for orthogonal, −1 for opposite. Length is ignored.

A worked example in 2-D. Take q=(1,0)\mathbf{q} = (1, 0) and d=(1,1)\mathbf{d} = (1, 1). The dot product multiplies matching coordinates and adds: 1⋅1+0⋅1=11\cdot1 + 0\cdot1 = 1. The lengths are ∥q∥=1\lVert\mathbf{q}\rVert = 1 and ∥d∥=2=1.41\lVert\mathbf{d}\rVert = \sqrt{2} = 1.41, so cos⁡θ=1/1.41=0.71\cos\theta = 1/1.41 = 0.71 and θ=45°\theta = 45°. Doubling d\mathbf{d} to (2,2)(2, 2) doubles the dot product to 2 but leaves the cosine at 0.71: cosine only cares about direction (lesson 0.2, Vectors).

Loading figure
Drag the query and the two documents. The long document has the larger dot product with q\mathbf{q} (2.08 against 1.60) only because it is longer; by cosine the short one is closer (0.961 against 0.824). Turn on normalise and the two rankings agree. That disagreement is the silent bug in the warning below.

The emerald arrow is the query How do I get a refund for a duplicate charge? Its best match is help/refunds.md#1 with cos⁡θ=0.995\tok{cosine}{\cos\theta}=0.995, an angle of 5.6°. Ranks 2 and 3, refund-policy.pdf#2 and refund-policy.html#2, are the same passage ingested from two more files: their pairwise cosines are 0.9999 or higher, so the three dots sit on top of each other. The translucent cone opens to the 4th neighbour, pricing.md#7 at 6.3°, so everything inside it is in the top k=4\tok{topk}{k}=4.

Normalise once, and the usual metrics agree1/4
  1. 1
    x^=x∥x∥  ⇒  ∥x^∥=1\hat{\mathbf{x}}=\frac{\mathbf{x}}{\lVert\mathbf{x}\rVert}\;\Rightarrow\;\lVert\hat{\mathbf{x}}\rVert=1

    Divide every chunk embedding by its length at ingestion, and the query at search time.

Hover cos⁡θ\tok{cosine}{\cos\theta} to draw the angle between q\tok{query}{\mathbf{q}} and the top result, or di\tok{chunk}{\mathbf{d}_i} to light up the whole corpus. Switch the query: the sphere turns so that the new question faces you.

Where the geometry comes from. Retrieval embedders are bi-encoders: one transformer (lesson 4.2) encodes questions, the same or a twin encodes passages, and training is contrastive. Each batch holds (question, relevant passage) pairs; the loss raises the cosine of each true pair and lowers it against every other passage in the batch, so relevant pairs end up pointing the same way. Some models expect different prefixes for queries and documents, such as query: and passage:, because the two sides are asymmetric. Larger dd captures finer distinctions at the cost of memory and scan time; Matryoshka-trained models let you keep only the first 256 of 1,024 dimensions with a modest loss.

Introduction to Information Retrieval, Manning, Raghavan & Schütze, Ch. 6.3

Maths, CS & AI Compendium, Henry Ndubuaku

02Exact k-nearest neighbours and its O(nd) cost

Exact search is a scan: score every chunk against the query and keep the best k\tok{topk}{k}. The viewport replays it for Why do my requests fail with HTTP 429? with k=6k = 6. The cyan probe visits the 240 chunks in index order, which is document order, topic by topic, and the panel holds the current top 6 in a small heap. Watch the cone: it is wide while the heap fills with whatever came first, then closes quickly as the scan crosses the rate-limits block, where the true neighbours live (6th neighbour at 8.4°).

s=E^ q^∈Rn,top⁡k(q)=argsort⁡(−s)1:k\mathbf{s}=\hat{E}\,\tok{query}{\hat{\mathbf{q}}}\in\mathbb{R}^{n},\qquad \operatorname{top}_{\tok{topk}{k}}(\mathbf{q})=\operatorname{argsort}(-\mathbf{s})_{1:k}
One matrix-vector product scores the whole corpus; a partial sort keeps the k best. In words: the score is a count of multiplications, so doubling the corpus doubles the work.
Ê (lab corpus)[,]720 values

One unit-length row per chunk. A query costs 240 × 3 = 720 multiply-adds.

Ê (RAG paper)[,]

Lewis et al. index 21M 100-word Wikipedia passages with 768-dimensional embeddings: about 64.5 GB as float32.

The cost is n⋅dn\cdot d multiply-adds per query, plus O(nlog⁡k)O(n\log k) for the heap or O(n)O(n) for a partial sort such as np.argpartition. At n=2.1×107n=2.1\times10^{7} and d=768d=768 that is 1.6×10101.6\times10^{10} multiply-adds per query, and the whole 64.5 GB matrix has to stream through memory every time. For corpora of thousands to a few million vectors a vectorised scan is often fast enough, and it is always the ground truth used to measure approximate indexes. Beyond that, latency and memory bandwidth force approximation.

Retrieve twelve chunks for the HTTP 429 question.

Introduction to Information Retrieval, Manning, Raghavan & Schütze, Ch. 7.1

03HNSW: greedy search through a layered graph

The express-train picture. A city line has local trains that stop everywhere and express trains that stop only at big stations. To reach a small station you ride the express to the nearest big stop, then switch to the local. A skip list stores sorted data that way, and HNSW does the same for vectors: a few nodes on fast upper layers with long links, every node on the slow bottom layer with short links.

Hierarchical navigable small world (HNSW) graphs are the most widely used approximate nearest-neighbour index. Every chunk is a node on layer 0, and each node is promoted to layer ℓ\tok{layer}{\ell} with probability 6−ℓ6^{-\ell}, so layers 0, 1 and 2 hold 240, 40 and 6 nodes. Within a layer each node links to a few near neighbours: M=2M = 2 on the upper layers and 2M=42M = 4 on layer 0 in this toy index. Real indexes typically use MM between 12 and 48.

In the viewport the sphere unrolls into three stacked maps, each centred on the query: distance from the emerald axis grows with the angle to q\tok{query}{\mathbf{q}}, so moving inward means getting closer. The amber path is the search; cyan flashes are distance computations.

for ℓ=L,…,1:  e←greedy⁡ℓ(q,e);W←beam⁡0(q,e,ef);return the k nearest in W\text{for } \tok{layer}{\ell}=L,\dots,1:\ \ e\leftarrow\operatorname{greedy}_{\ell}(\mathbf{q},e);\qquad W\leftarrow\operatorname{beam}_{0}(\mathbf{q},e,\tok{ef}{\mathit{ef}});\qquad \text{return the } k \text{ nearest in } W
Search: greedy descent with a beam of 1 on the upper layers, then a beam of width ef on layer 0 (Malkov and Yashunin, Alg. 5).

On layer 2 the search starts at the fixed entry point, privacy.md#1, and moves to whichever neighbour is closer to q\mathbf{q} until none improves: one hop, to regions.md#4. That node also lives on layer 1, so the search drops down and continues through autoscaling.md#2 to changelog.md#5. On layer 0 a beam of ef=4\tok{ef}{\mathit{ef}} = 4 candidates walks through instances.md#8, charges.md#3 and credits.md#2 into the refund passages. In total it computes 24 distances instead of 240.

Widen the beam by a single slot: ef=5\mathit{ef} = 5.

Why it works: upper layers are sparse, so their links are long and a few hops cross the whole map, while the dense bottom layer has short links that refine locally. The number of hops grows roughly logarithmically with nn. Insertion runs the same search to find each new node's neighbours and keeps a candidate only if it is closer to the new node than to every neighbour already kept, so links fan out in different directions instead of piling onto near-duplicates. The links cost memory too: about 2M2M neighbour ids of 4 bytes per vector on layer 0, on top of the vectors themselves, which is one reason very large corpora move to compressed IVF-PQ indexes.

Efficient and Robust Approximate Nearest Neighbor Search Using HNSW Graphs, Malkov & Yashunin, 2018, Sec. 4, Alg. 1–5

The rest of this lesson is in Pro

  • 04Recall versus latency: ef, IVF and product quantisation
  • 05The RAG pipeline: chunk, embed, index, retrieve, augment, generate
  • 06Re-ranking: MMR, hybrid search and cross-encoders
  • 07Evaluating retrieval and grounding
  • Python challenge: Build the retrieval core of a RAG system
  • Knowledge check, 4 questions

Pro opens all 45 lessons, every graded Python challenge and the full 3D labs.

Compiling scene

The Python challenge and knowledge check for this lesson are part of Pro.

Questions learners ask

What is retrieval-augmented generation (RAG)?
RAG makes a language model answer from a specific body of documents. The documents are split into chunks, each chunk is turned into an embedding vector, and the vectors are stored in an index. At question time the question is embedded with the same model, the most similar chunks are retrieved, and they are added to the prompt so the model can answer from them and cite them. Updating the knowledge means updating the index, not retraining the model.
How does HNSW vector search work?
HNSW builds a graph in layers. Every vector is a node on the bottom layer, and a random, geometrically shrinking subset also appears on higher layers, which therefore have fewer nodes and longer links. A search starts at the top, moves greedily to whichever neighbour is closer to the query, drops a layer when it cannot improve, and on the bottom layer keeps a candidate list of size ef. It computes far fewer distances than a full scan, at the cost of sometimes missing a true nearest neighbour; a larger ef raises both recall and latency.
What is maximal marginal relevance (MMR) in retrieval?
Maximal marginal relevance is a re-ranking method that builds the result list one item at a time. Each step picks the candidate with the best balance between similarity to the query and dissimilarity to the items already picked, weighted by a parameter lambda between 0 and 1. It removes near-duplicate chunks from the context so the prompt carries more distinct information; with lambda equal to 1 it is plain similarity search.

Next in Transformers and LLMs

4.6Alignment: reward models, RLHF and DPOFrom instruction tuning to preference optimisation: reward models, the KL leash of RLHF, and the closed-form shortcut DPO takes.

Sources

  • Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks, Lewis et al., 2020
  • Efficient and Robust Approximate Nearest Neighbor Search Using HNSW Graphs, Malkov & Yashunin, 2018
  • Introduction to Information Retrieval, Manning, Raghavan & Schütze
  • Maths, CS & AI Compendium, Henry Ndubuaku