4.5 Embeddings, vector search and retrieval-augmented generation
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 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 from a few hundred to a few thousand; this lab uses so every vector can be drawn. The sphere holds 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.
A worked example in 2-D. Take and . The dot product multiplies matching coordinates and adds: . The lengths are and , so and . Doubling to doubles the dot product to 2 but leaves the cosine at 0.71: cosine only cares about direction (lesson 0.2, Vectors).
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 , 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 .
- 1
Divide every chunk embedding by its length at ingestion, and the query at search time.
Hover to draw the angle between and the top result, or 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 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 . The viewport replays it for Why do my requests fail with HTTP 429? with . 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°).
One unit-length row per chunk. A query costs 240 × 3 = 720 multiply-adds.
Lewis et al. index 21M 100-word Wikipedia passages with 768-dimensional embeddings: about 64.5 GB as float32.
The cost is multiply-adds per query, plus for the heap or for a partial sort such as np.argpartition. At and that is 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 with probability , so layers 0, 1 and 2 hold 240, 40 and 6 nodes. Within a layer each node links to a few near neighbours: on the upper layers and on layer 0 in this toy index. Real indexes typically use 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 , so moving inward means getting closer. The amber path is the search; cyan flashes are distance computations.
On layer 2 the search starts at the fixed entry point, privacy.md#1, and moves to whichever neighbour is closer to 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 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: .
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 . 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 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.
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