Meaning as coordinates: embeddings, similarity and the search for neighbours

From things to points

"Vector databases are gaining popularity due to the rise of AI and ML applications", page 640 begins: "In particular, applications that use LLM + RAG (Retrieval Augmented Generation)". In retrieval-augmented generation a language model, before it answers, fetches the stored passages closest in meaning to the question and reads them. Page 641 widens the picture: vector databases allow "more efficient and semantically rich data retrieval", "enhancing search and recommendation systems". Fetching the closest items fast is the subject of this lesson.

Vector search is also a feature of databases you already know. The chart of page 644 separates "Dedicated vector databases" from "Databases that support vector search", and the second group includes Neo4j, Cassandra, Elasticsearch, MongoDB and Redis — the graph, column-family, search, document and key-value databases you practise in this course.

A vector is a list of numbers — and an arrow

"In mathematics and physics, a vector is a quantity with both magnitude and direction. In vector databases, vectors represent various attributes of an object" (p. 647). Page 648 turns a house into four of them: 3 bathrooms, 1 bedroom, an area of 130 and a price of 340000, the vector \((3, 1, 130, 340000)\). The exercise session adds two words: a vector "is a list of numbers that represent magnitude and direction", and "When most values are non-zero, it is referred to as a dense vector" (p. 1685). A vector space is "a mathematical set of vectors that can be added together and scaled", continuous "when values can take on any real number" (p. 1686).

Embedding: similar things, nearby points

What makes embeddings useful is a property of space: they "represent data (like text, images, audio, or graphs) as vectors of numbers so that similar items are close together in this vector space" (p. 1687). The drawing on that page turns three portraits into three points in one corner of a plane and two fruits into two points in another.

What does one coordinate do? The session borrows Google's food example (p. 1688; Fig. 1). On a single axis, "sandwichness", five dishes line up from borscht to shawarma; by sandwichness alone an apple strudel would fall between the hot dog and the shawarma. Add "dessertness" and it rises away from them. A third axis, "liquidness", pulls the borscht away from the salad and lifts tangyuan, sweet dumplings served in soup, high on two axes at once. Every new dimension separates things the previous ones confused.

Real embedding dimensions have no such names: the embedding model "often is black box", says the drawing on page 1684. You cannot read the meaning of the 17th coordinate; you can only measure which points are near which. That is enough: embedding lets vector databases "find relevant information through vector similarity, rather than exact text matches" (p. 653).

An embedding turns meaning into position: similar items get nearby coordinates, so "similar" becomes "near".

Where the coordinates come from

The session names two decisions before any model is built (p. 1689). First, "decide what ‘similar’ means for the data at hand (words in similar contexts, images of the same object, etc.)". The slide adds that "In Deep Learning, this is automatically inferred": you do not hand-craft the features, but the notion of similarity is still fixed — by the pairs the model is trained on. Second, "choose the number of dimensions": "more dimensions capture more detail but are slower and heavier; fewer dimensions are faster but less precise".

Then "build an encoder model that converts the data into vectors (e.g., BERT for text, CNN/ViT for images)" and "Train the encoder using metric learning so that similar items are clustered together, and dissimilar ones are separated" (p. 1690). The machinery comes from deep learning: a contrastive or triplet loss pulls an anchor towards its positive example and pushes it away from the negatives, and the vector is the network's last hidden representation, without the classification head.

• Images, CNN. Convolutional networks "capture the semantic meaning of images by processing them through their convolutional layers"; the named families are VGG, ResNet, Inception and EfficientNet (p. 1692).
• Images, ViT. "An image is divided into fixed-size patches, which are fed into a transformer encoder. Using self-attention, it learns relationships between patches across the entire image" (p. 1693).
• Text. Word embeddings place "similar words close to each other"; text/document embeddings "represent longer text units such as sentences, paragraphs, or entire documents" (p. 1694). Page 649 lists models: OpenAI's text-embedding-ada-002 and its siblings, Sentence Transformers such as all-MiniLM-L6-v2 and all-mpnet-base-v1, services such as Google Vertex AI and Elasticsearch. In the session's Vectorization notebook, all-MiniLM-L6-v2 turns four sentences into "four 384-dimensional embeddings".
• Text and images together, CLIP. It "projects text and image embeddings into the same embedding space, so ‘a photo of a dog’ and a real dog image should be closer" (p. 1695). Page 650, "Multi-modal vectorization", sends text, video and audio embeddings into one vector database.

The pipeline that uses them has three steps (p. 1691, Fig. 2): convert the data into embeddings, "Store embeddings in a vector database for fast retrieval", then apply them to "semantic search, retrieval-augmented generation (RAG), classification, clustering, and recommendations". A query must be embedded by the same model as the stored data; otherwise the two sets of coordinates mean different things.

Looking at the space

Page 651 embeds sentences such as 'Sunsets are breathtaking' "using models like paraphrase-MiniLM" and gives the process: "Take a sentence", "Transform it into (numerical) vector representation", "Possibly reduce dimensionality if needed / wanted". Page 652 does it to ten sentences — "sentences to 32 dimensions vectors, and then PCA to top 2 principal components" — and the plot (Fig. 3) puts "Colds are unpleasant.", "Mosquitoes are annoying." and "Traffic jams are frustrating." on the left, "Laughter brings joy.", "Music is uplifting." and "Success is rewarding." on the right.

This is PCA, from statistics: the two directions of largest variance. It is also only a projection. "Colds are unpleasant." and "Mosquitoes are annoying." almost overlap in the plot, yet against "Rainy days make me sad" they score 0.419 and 0.296, because the scores are computed in all the dimensions. The session's Visualization notebook draws the same kind of plot for three different models.

How close is close: three ways to compare vectors

"Metrics like Cosine and Euclidean distances are used to measure the similarity between two vectors" (p. 654). The two squares on that page show the difference. The Euclidean distance is the length of the segment between two points; the cosine looks only at the angle between the two arrows drawn from the origin.

The cosine depends on the angle only (p. 655, p. 1696; Fig. 4): close to 1 when the two arrows point the same way, 0 when they are orthogonal, −1 when they are opposite. The inner product is the numerator alone, so it grows with the lengths as well.

The session's Comparison notebook works it out on two arrows, \(A = (2, 1)\) and \(B = (0, 2)\):

Positive and well below 1: the arrows are 63° apart, nearer to orthogonal than to identical. The other two measures of the same pair are the inner product, 2, and the Euclidean distance between the tips:

Three numbers, three different scales. The notebook's code, without its plotting cell:

import numpy as np

vec1 = np.array([2, 1])
vec2 = np.array([0, 2])

def cosine_similarity(vec1, vec2):
    dot_product = np.dot(vec1, vec2)
    norm_vec1 = np.linalg.norm(vec1)
    norm_vec2 = np.linalg.norm(vec2)
    similarity = dot_product / (norm_vec1 * norm_vec2)
    return similarity

similarity_score = cosine_similarity(vec1, vec2)
print(f"Cosine Similarity between vec1 and vec2: {similarity_score:.4f}")
# prints: Cosine Similarity between vec1 and vec2: 0.4472

Now read the table of page 656 with these tools. Its column holds the cosine similarity of "Rainy days make me sad" with each stored sentence, already sorted: 0.764286 for "Rainy days can be gloomy.", an angle of 40°; 0.418937 for "Colds are unpleasant.", 65°; down to 0.033636 for "Success is rewarding.", 88° — almost orthogonal. The stored vectors are not of length 1 (one coordinate printed in the table is 1.2116411), and the cosine does not care: it divides the lengths away.

Why cosine — and when the metrics disagree

The slide's reason: "Cosine similarity is commonly used due to its efficiency" (p. 654). On vectors of length 1 it is indeed a single inner product. Two further reasons are given outside the slides: the cosine ignores length, so a long text and a short one on the same topic still point the same way; and the metric should match the one the embedding model was trained with.

Ignoring length matters, because the metrics can disagree. Take \(a = (1, 1)\), \(b = (2, 2)\), \(c = (1, 0)\). By cosine, the nearest neighbour of \(a\) is \(b\): same direction, cosine 1. By Euclidean distance it is \(c\), 1 away, while \(b\) is 1.414 away. Normalise the three vectors to length 1 and the disagreement disappears, for a reason worth deriving once:

1. Write the squared distance as the inner product of the difference with itself:

   \[ \norm{A - B}^2 = (A - B)\cdot(A - B) \]

2. Expand it like \((a - b)^2\); the inner product distributes and \(A\cdot B = B\cdot A\):

   \[ \norm{A - B}^2 = \norm{A}^2 + \norm{B}^2 - 2\,A\cdot B \]

3. Normalise: divide every vector by its length, so that \(\norm{A} = \norm{B} = 1\):

   \[ \norm{A - B}^2 = 2 - 2\,A\cdot B \]

4. With lengths 1 the denominator of the cosine is 1, so the inner product is the cosine:

   \[ A\cdot B = \cos\theta \] \[ \norm{A - B} = \sqrt{2 - 2\cos\theta} \]

5. Read it: the distance shrinks exactly when the cosine grows. Sorting by smallest Euclidean distance, by largest inner product or by largest cosine gives the same list. For the best match of page 656 the unit-length distance would be \(\sqrt{2 - 2 \cdot 0.764} \approx 0.687\), still first.

That is why FAISS can run a cosine search with an inner-product index on normalised vectors, and why an inner-product search — the "metric_type": "IP" printed in the Zilliz call of the exam of 11 Feb 2025 (lesson 28) — ranks exactly like a cosine search once the vectors have length 1. Try the three metrics on one query:

Exact search, and why it stops working

Finding the k stored vectors most similar to a query is k-nearest-neighbour search. Without an index it means "computing the distance from the query to each point in the database" (p. 658): \(n\) vectors of \(d\) numbers cost \(n \cdot d\) multiplications per query. A million 384-dimensional vectors make \(3.84 \times 10^8\) of them, for every single query. Hence: "Let’s create indexes with tree-based exact vector search techniques" (p. 658).

K-D trees: cut the space in halves

"k-d trees are a special case of binary space partitioning trees": "a binary tree in which every node is a k-dimensional point. Every non-leaf node implicitly generates splitting hyperplane that divides the space into two parts. The split is on the median value" (p. 659). Each cut is perpendicular to one axis, and the axis changes with the depth: the cube of page 659 is cut first by a red plane on the first coordinate, then by green planes on the second, then by blue ones on the third. Cutting at the median puts half of the points on each side, so the tree stays balanced.

Page 660 grows such a tree over records with three attributes — Name, Age, Salary — and cycles through them level by level. Its inner nodes keep only the split value and the records sit in the leaves, a common variant of the definition. Follow a query record down it, Ivan, 61, $55k (Fig. 5): four comparisons reach one leaf out of twenty.

For a nearest-neighbour query the leaf is only a first candidate. The search then climbs back and looks into a sibling subtree whenever its splitting plane is closer to the query than the best candidate so far: the true neighbour may lie just across a cut.

Page 661 gives the cost together with its condition: "Complexity of search (and other operations): O(log n)", under the hypothesis \(n \gg 2^k\), where \(n\) is the number of vectors and \(k\) their dimensionality. Careful: on this slide \(k\) is the number of dimensions (the \(d\) above), not the \(k\) of k-nearest neighbours. The O(log n) is the cost to expect when the hypothesis holds; in the worst case the search visits every leaf. The tree needs many points in every cell for its cuts to rule anything out. Table 1 shows what the condition asks for.

No collection will ever hold \(10^{115}\) vectors. For embeddings the last line of the slide applies: "With high-dimensional data, most of the points in the tree will be evaluated and the efficiency is no better than exhaustive search" (p. 661).

R-trees: boxes inside boxes

The R stands for rectangle. The idea of page 662 is "to group nearby objects and represent them with their minimum bounding rectangle in the next higher level of the tree", which gives the pruning rule: "a query that does not intersect the bounding rectangle also cannot intersect any of the contained objects". At the leaves each rectangle is one object; higher up, each covers more of them — "an increasingly coarse approximation of the data set" (Fig. 6).

An R-tree is balanced and "Organizes data in pages"; each page has a maximum and a minimum filling, and the slide reports the "Best performance with min filling around 40%" (p. 663). Building a good one is the hard part: it must stay balanced, its rectangles must not "cover too much empty space", and they must "not overlap too much (so that during search, fewer subtrees need to be processed)". The M-tree variant uses "circles / spheres" instead of rectangles.

Both trees hit the same wall: "For high-dimensional data, also tree-based exact vector search techniques such as the k-d tree and R-tree do not perform well enough because of the curse of dimensionality". For the R-tree the wall looks like this: in hundreds of dimensions a box around even a few points spans most of the range of most coordinates, so the boxes overlap and almost every query intersects almost every box. So "Vector databases use Approximate Nearest Neighbor algorithms" (p. 665).

Exact trees prune by geometry; in hundreds of dimensions almost nothing can be pruned, and the search falls back to a scan.

Approximate search: hashes and graphs

An approximate nearest neighbour (ANN) search returns vectors that are very probably the nearest. HNSW, page 670 says, "sacrifices a small amount of accuracy to achieve much faster search times". The distances HNSW computes are exact; what it may do is miss a vector it never looked at (IVFPQ, at the end of the lesson, adds a second error: distances estimated from compressed codes). The usual measure is recall, the share of the true nearest neighbours that the search returns. Page 666 lists four such algorithms: LSH, HNSW, IVFADC and IVFPQ — the last two are in fact one method (section 6).

LSH: a hash that wants collisions

"locality-sensitive hashing (LSH) is a fuzzy hashing technique that hashes similar input items into the same ‘buckets’ with high probability"; "The number of buckets is much smaller than the universe of possible input items"; and the key sentence: "It differs from conventional hashing techniques in that hash collisions are maximized, not minimized" (p. 667). Compare the CRC16 hash of Redis Cluster (lesson 19), built to spread keys evenly over the slots. A query is hashed, and only the items of its bucket are compared exactly. Since a long vector becomes a short bucket code, "LSH can be seen as a way to reduce the dimensionality of high-dimensional data".

One classic family for the cosine makes "with high probability" precise (background, not on the slides): draw a random hyperplane through the origin and record on which side a vector falls — one bit. A few such cuts give every vector a short code, and the code is its bucket (Fig. 7).

Two vectors at angle \(\theta\) get the same bit with probability \(1 - \theta / 180^\circ\). For the rainy-day pair at 40° that is 0.78; with 8 such bits as the bucket code, they share a bucket with probability \(0.78^8 \approx 0.13\), two orthogonal sentences with \(0.5^8 \approx 0.004\). One code alone would miss the good pair most of the time, so an LSH index keeps several tables with different random hyperplanes and looks into the query's bucket in each: with 20 tables the rainy-day pair meets at least once with probability 0.94, the orthogonal pair with 0.08.

HNSW: a skip list made of graphs

Hierarchical Navigable Small World is "an efficient algorithm for approximate nearest neighbor (ANN) search in high-dimensional spaces" (p. 668). Two ideas meet in its name. "Navigable Small-World Graphs" are "graphs where most nodes can be reached from any other in a small number of hops": every vector is a node, linked to vectors near it. The "Hierarchical Structure" organises the graph "into multiple layers, each containing fewer nodes than the layer below", and the lowest layer holds all the data.

Page 669 explains the search with a skip list, "looking for 11" (Fig. 8). The top layer has few nodes and long links, so one hop jumps over most of the data; when the next hop would overshoot, the search drops a layer and continues with shorter hops.

In HNSW the layers hold vectors, and "overshoot" becomes "no linked node is closer to the query". The search starts at an entry point in the top layer and moves to whichever linked node is closest to the query; when none is closer it descends a layer from where it stands, "refining the result by looking at more nodes" (p. 669), down to layer 0, where it may keep several candidates at once (the parameter ef of the HNSW paper; background). New vectors arrive "in a probabilistic manner": "the algorithm randomly selects a level in the hierarchy where the point should be placed. It then connects the new point to its closest neighbors at that level" (p. 670) — and, the slide leaves this out, at every level below it too, down to layer 0.

Page 671 lists four advantages: "Scalability", up to "millions or even billions of vectors"; "Speed", because the hierarchy "significantly reduces the number of comparisons needed to find a similar vector"; "Adaptability", "dynamic insertion and deletion of data points"; and "Memory Efficiency" — the one that does not hold.

Cells and codes: IVFPQ

The Inverted File with Product Quantization "Combines coarse quantization (to partition the vector space) and product quantization (to compress vectors)" (p. 672). Two independent ideas: the first reduces how many vectors a query meets, the second how much each of them costs to store and to compare.

Coarse quantization: cells and an inverted file

"The entire dataset is divided into clusters using a clustering algorithm like k-means. Each vector is assigned to its nearest cluster center (called a coarse centroid)", and the centroids become the "bins" of the space (p. 673). It is k-means clustering. Around each centroid lies the region of points nearer to it than to any other centroid, a Voronoi cell — the polygons drawn on page 673. For each centroid the index keeps the list of its vectors: an inverted file, like the term-to-documents lists of an inverted index (Fig. 9). "During a search, instead of searching the entire dataset, the algorithm only searches within the relevant clusters".

The lower drawing of page 673 shades the "Filtered Cell" and puts the "Query Vector" right on its border. That is the risk: the query's true nearest neighbour may lie in the next cell, which is never opened. Searching more cells — nprobe of them, in FAISS's vocabulary — buys back the recall, at the price of more distances.

Product quantization: four bytes instead of 512

"Product quantization works by dividing each vector into smaller sub-vectors and then quantizing each sub-vector separately" (p. 674). Each sub-space gets its own codebook, a small set of centroids learned by k-means, and each sub-vector is replaced by the number of its nearest centroid. With 256 centroids per codebook that number fits in one byte (the usual choice; the slide says only "with fewer bits"). Fig. 10 does it to a 128-dimensional vector of 4-byte numbers.

Four bytes of 256 values each give \(256^4 \approx 4.3 \times 10^9\) different codes from only \(4 \times 256 = 1024\) stored sub-centroids: that Cartesian product is the "product" in the name. The price is the slide's NOTE: "the reconstructed vector is not identical to the original vector" (p. 674), so distances computed on codes are estimates.

The search runs in two steps (p. 675). "Coarse Search": the algorithm "first identifies the relevant clusters (coarse centroids) where similar vectors are likely to be found". "Refined Search": inside them, "product quantization is used to compare the query vector with the compressed representations of the vectors in those clusters". Two sources of error follow — a neighbour in an unopened cell, a distance misjudged through its code — so IVFPQ "may not find the exact nearest neighbors". Its advantages (p. 676) mirror the two ideas: "Memory Efficiency" from the codes, "Fast Search" from the cells, "Scalability", and "Customizable Accuracy" through parameters "like the number of clusters or the precision of quantization".

The rainy day, solved

Back to page 656. "Colds are unpleasant." came second because an encoder trained, as page 1690 asks, to cluster similar items placed it 65° from "Rainy days make me sad", while an unrelated sentence such as "Success is rewarding." sits at 88°. The inverted index never had a chance: the two sentences share no word. And a real vector database would not compare the query with every stored sentence: an HNSW walk or a few IVF cells meet a few dozen candidates — 32 instead of 400 in the widget. The price is the word "approximate": now and then the true best match lies just outside what the search looked at.