Once words are vectors, "how similar are these two words?" becomes "how close are these two points?". But close can mean several things, and the choice matters a great deal. Attention in a Transformer uses one notion, vector databases usually another, and a surprising amount of confusion (and many bugs) comes from mixing them up.

This section builds the three tools you'll use for the rest of the book (dot product, cosine similarity, and Euclidean distance), shows exactly how they relate, and then takes a trip into high-dimensional space, where your 3-D intuition quietly breaks. We finish with the trick that makes similarity search over millions of vectors possible, random hyperplanes.

The dot product measures alignment times magnitude

For $\mathbf{u}, \mathbf{v} \in \mathbb{R}^d$ the dot product has two equivalent definitions, one algebraic and one geometric,

where $\theta$ is the angle between the vectors (in this section only, $\theta$ is an angle, not the model's parameters) and $\lVert\mathbf{u}\rVert = \sqrt{\mathbf{u}^\top\mathbf{u}}$ is the length.

In plain words, multiply matching coordinates and add them up. Geometrically, that equals the product of the two lengths times the cosine of the angle between them.

So the dot product mixes two different things. It's large when the vectors point the same way (large $\cos\theta$) or when they're long (large norms). It's zero when they're perpendicular and negative when they point in opposing directions.

There's a second, very useful reading. $\mathbf{u}^\top\hat{\mathbf{v}}$, where $\hat{\mathbf{v}} = \mathbf{v}/\lVert\mathbf{v}\rVert$, is the length of the shadow that $\mathbf{u}$ casts onto the direction of $\mathbf{v}$. That shadow is called the scalar projection, and it answers "how much of $\mathbf{u}$ points along $\mathbf{v}$?" In §1.9 we'll use exactly this to measure how much gender a word's vector carries.

A worked example. Take $\mathbf{u} = (3, 4)$ and $\mathbf{v} = (4, 3)$. The dot product is $3\cdot4 + 4\cdot3 = 24$. Both lengths are 5, so $\cos\theta = 24/25 = 0.96$ and $\theta \approx 16.3°$. The shadow of $\mathbf{u}$ on $\mathbf{v}$ has length $24/5 = 4.8$. Now double $\mathbf{u}$ to $(6, 8)$. The dot product doubles to 48, the shadow doubles to 9.6, and the angle and cosine do not change at all.

Cosine similarity measures direction only

If we only care about direction, we divide out the lengths,

In plain words, cosine similarity is the dot product of the two vectors after scaling each to length 1. (The range $[-1, 1]$ is the Cauchy–Schwarz inequality, $\lvert\mathbf{u}^\top\mathbf{v}\rvert \le \lVert\mathbf{u}\rVert\lVert\mathbf{v}\rVert$.)

It's invariant to rescaling, since $\cos(3\mathbf{u}, \mathbf{v}) = \cos(\mathbf{u},\mathbf{v})$. That's usually what you want when comparing word vectors, because the length of a word vector tends to carry other information. In word2vec, vector norms are empirically correlated with word frequency and with how consistently a word is used (Schakel & Wilson, 2015). If you used raw dot products for "most similar word", long, frequent words would win just for being long.

Euclidean distance, and the identity that ties everything together

The ordinary straight-line distance is $\lVert\mathbf{u}-\mathbf{v}\rVert$. Expand its square,

(You used this in Exercise 1.1d.) Now suppose both vectors are unit length. Then $\lVert\mathbf{u}\rVert^2 = \lVert\mathbf{v}\rVert^2 = 1$, and

In plain words, for unit vectors, squared distance is a decreasing function of cosine. For example, two unit vectors with cosine 0.8 are $\sqrt{0.4} \approx 0.632$ apart, and two with cosine 0 are $\sqrt 2$ apart, like the one-hot vectors of §1.1.

This is one of the most practically important facts in the chapter. Once vectors are normalized, ranking by Euclidean distance, by cosine, and by dot product all give the same order. That's why vector databases usually say "normalize your embeddings, then use inner product". Maximum inner-product search on unit vectors is cosine search, which is nearest-neighbor search.

Tick "Normalize" in the playground above to check the identity numerically.

Which one should you use?

Let's put this into code. Here are a few hand-made 4-D "word vectors", with one deliberately long.

Read the table row by row. The dot product ranks "the" first (4.07, nearly three times kitten's 1.46), purely because it is long. Cosine ranks kitten first (0.987) and puts "the" third (0.738). Euclidean distance also ranks kitten first, but it is fooled in a different way, because "the" is far away for being long.

import numpy as np

def cosine_sim_matrix(A, B, eps=1e-12):
    """A: (n, d), B: (m, d) -> (n, m) cosine similarities"""
    raise NotImplementedError

import numpy as np

def top_k_cosine(q, E, k, exclude=()):
    """returns an int array of k row indices of E, most similar first"""
    raise NotImplementedError

When lengths differ, inner-product search is a different problem

Recommenders often score items by a raw dot product $\mathbf{q}^\top\mathbf{x}$, because the item vector's length carries meaning (popularity, quality). Finding the best item is then maximum inner-product search (MIPS), and it is not nearest-neighbor search. A long item can beat a closer short one, and a vector need not even be its own best match ($\mathbf{x}^\top\mathbf{x} < \mathbf{x}^\top(2\mathbf{x})$).

There is a neat reduction (Bachrach et al., 2014; Neyshabur & Srebro, 2015). Let $M = \max_i \lVert\mathbf{x}_i\rVert$. Append one coordinate to every item, $\tilde{\mathbf{x}}_i = (\mathbf{x}_i, \sqrt{M^2 - \lVert\mathbf{x}_i\rVert^2})$, so every augmented item has length exactly $M$, and append a 0 to the query, $\tilde{\mathbf{q}} = (\mathbf{q}, 0)$. Then

In plain words, the first two terms are the same for every item, so the nearest augmented item is the one with the largest inner product. Any nearest-neighbor index can now answer MIPS.

A trip into high dimensions

Embeddings live in hundreds or thousands of dimensions. Geometry there is not a scaled-up version of 3-D, and three facts will shape everything we do.

Fact 1. Random vectors are almost orthogonal

Draw $\mathbf{u}, \mathbf{v}$ with independent $\mathcal{N}(0,1)$ entries. The dot product $\mathbf{u}^\top\mathbf{v} = \sum_j u_j v_j$ is a sum of $d$ independent terms, each with mean 0 and variance 1. So it has mean 0 and variance $d$, a typical size of $\sqrt d$. Meanwhile each norm is about $\sqrt d$ (next fact). Therefore

In fact the variance is exactly $1/d$, and the derivation is short enough to carry around.

In plain words, in $d$ dimensions, the cosine between two random directions is typically about $\pm 1/\sqrt d$. At $d = 768$ that's $\pm 0.036$, and at $d = 4{,}096$ it's $\pm 0.016$.

Two consequences follow.

• "Small" cosines can be big signals. A cosine of 0.3 between two 768-dimensional embeddings is about 8 standard deviations above chance ($0.3/0.036 \approx 8.3$).
• There's room for a huge number of almost-orthogonal directions. You can fit exponentially many (in $d$) vectors whose pairwise cosines are all below any fixed $\varepsilon$. That's what lets a model with $d=4096$ represent far more than 4096 features by giving each a nearly orthogonal direction. This phenomenon, called superposition, is central to understanding what is inside large models, and it is one reason why the features a model learns rarely line up with single coordinates.

Fact 2. Norms and distances concentrate

The squared norm $\lVert\mathbf{u}\rVert^2 = \sum_j u_j^2$ is also a sum of $d$ independent terms, each with mean 1 and variance 2. So $\mathbb{E}\lVert\mathbf{u}\rVert^2 = d$ and $\operatorname{Var}\lVert\mathbf{u}\rVert^2 = 2d$, which means $\lVert\mathbf{u}\rVert^2/d \to 1$. A first-order expansion of the square root gives $\lVert\mathbf{u}\rVert \approx \sqrt d \pm \tfrac{1}{\sqrt2}$. At $d = 768$ that is $27.7 \pm 0.71$. Random Gaussian vectors don't fill the ball. They live on a thin shell, whose absolute thickness stays constant while its radius grows like $\sqrt d$.

Volume behaves the same way. The fraction of a $d$-dimensional ball's volume that lies within radius $1 - \varepsilon$ of its center is $(1-\varepsilon)^d$. For $d = 768$ and $\varepsilon = 0.01$, that is $0.99^{768} \approx 0.00044$. More than 99.9% of the volume sits in the outer 1% of the radius.

The same thing happens to distances. For random data, the ratio between the farthest and the nearest neighbor of a query tends to 1 as $d$ grows (Beyer et al., 1999). The widget's "distance contrast" shows this. It's the precise sense in which nearest-neighbor search gets harder in high dimensions. A related effect, hubness, is that a few points become the nearest neighbor of a disproportionate number of others (Radovanović et al., 2010), and it plagues retrieval with high-dimensional embeddings. Real embeddings are useful only because they are not random. Their meaningful structure lives near much lower-dimensional patterns.

Fact 3. Random projections preserve distances (Johnson–Lindenstrauss)

Here's the good news. You can squash high-dimensional points into far fewer dimensions with a random matrix and barely distort their distances.

Johnson–Lindenstrauss lemma. For any $0 < \varepsilon < 1$ and any $n$ points $\mathbf{x}_1,\dots,\mathbf{x}_n \in \mathbb{R}^D$, if the target dimension $k$ satisfies

then there exists a linear map $f: \mathbb{R}^D \to \mathbb{R}^k$ (a random Gaussian matrix scaled by $1/\sqrt{k}$ works with probability at least $1/n$ by this proof, and in practice a single draw almost always works, as the cell below shows) such that for all pairs,

In plain words, $n$ points can be squeezed into about $\log n / \varepsilon^2$ dimensions while every pairwise distance stays within a factor $1\pm\varepsilon$. This is the form proved by Dasgupta and Gupta (2003). Notice what's missing, namely the original dimension $D$. The target dimension depends only on the number of points, and only logarithmically.

Worked numbers make the bound concrete. For $n = 300$ points and $\varepsilon = 0.3$, the bound asks for $k \ge 4 \ln 300 / (0.045 - 0.009) \approx 634$. For a million points and $\varepsilon = 0.1$, it asks for 11,842 dimensions, and going to a billion points only raises that to about 17,800. The bound is conservative (you'll measure how conservative in the exercise), but its shape is the lesson. The logarithm is the deep reason why modest dimensions can serve enormous vocabularies, and in practice the dimensions needed are smaller still, because real data is far from the worst case and an embedding only has to keep the distances that matter for its task. It's also the theory behind random-projection tricks in sketching, hashing, and approximate nearest-neighbor search.

import numpy as np

def jl_min_dim(n, eps):
    raise NotImplementedError

# Your investigation: is the bound tight for n=300, eps=0.3?
# X = np.random.default_rng(1).normal(size=(300, 2000))
# print(jl_min_dim(300, 0.3), max_distortion(X, jl_min_dim(300, 0.3)))

Random hyperplanes, and search that skips most of the data

Johnson–Lindenstrauss projects to fewer real numbers. Push the idea to its extreme and keep only the sign of each random projection, one bit per hyperplane. This is SimHash (Charikar, 2002), the simplest locality-sensitive hashing (LSH) scheme for cosine similarity, and it comes with an exact formula.

Draw a random direction $\mathbf{r}$ with independent Gaussian entries and record the bit $h(\mathbf{x}) = [\mathbf{r}^\top\mathbf{x} > 0]$. The hyperplane orthogonal to $\mathbf{r}$ splits space in two, and two vectors get different bits exactly when the hyperplane passes between them. Then

In plain words, each random hyperplane is a coin that comes up "different" with probability equal to the angle between the vectors, as a fraction of 180°. For cosine 0.9 ($\theta \approx 25.8°$) the coin says "different" 14.4% of the time. For cosine 0 ($\theta = 90°$) it says "different" half the time.

Now build an index. Concatenate $b$ bits into a bucket key, so two vectors share a bucket only if all $b$ hyperplanes agree, with probability $p^b$ where $p = 1 - \theta/\pi$. One table with large $b$ is precise but misses true neighbors, so use $L$ independent tables and take every point that shares a bucket with the query in any table as a candidate. The candidate probability is

In plain words, $b$ makes buckets picky and $L$ gives each neighbor several chances, and together they turn a gentle function of the angle into a steep S-curve. With $b = 16$ and $L = 20$, a neighbor at cosine 0.9 becomes a candidate with probability 0.83, one at cosine 0.5 with probability 0.03, and an unrelated vector at cosine 0 with probability 0.0003. Then we rank only the candidates by exact cosine. Search cost drops from all $n$ points to a small candidate set, at the price of occasionally missing a neighbor.

import numpy as np

def collision_prob(cos_sim, n_bits, n_tables):
    raise NotImplementedError

import numpy as np

class LSHIndex:
    def __init__(self, E, n_bits, n_tables, seed=0):
        raise NotImplementedError

    def query(self, q, k):
        """-> (ids of the top-k candidates by cosine, most similar first; number of candidates)"""

Real systems mostly use graph indexes (HNSW) and product quantization rather than plain LSH, because those adapt to the data instead of using random hyperplanes. But LSH is the one whose behavior you can derive exactly, and the trade-off it exposes (more candidates means higher recall and more work) is the same knob every vector index turns. §7.4 builds the rest.

In PyTorch

Read more

• Blum, Hopcroft & Kannan. Foundations of Data Science, Chapter 2. High-dimensional geometry, Gaussian annuli, and random projection.
• Vershynin. High-Dimensional Probability. Concentration of norms (§3.1) and Johnson–Lindenstrauss (§5.3), rigorously.
• Dasgupta & Gupta (2003). An Elementary Proof of the Johnson–Lindenstrauss Theorem. The bound used in this section.
• Charikar (2002). Similarity Estimation Techniques from Rounding Algorithms. SimHash and the θ/π collision probability.
• Beyer et al. (1999), When Is Nearest Neighbor Meaningful?, and Radovanović, Nanopoulos & Ivanović (2010), Hubs in Space. Distance concentration and hubness.
• Neyshabur & Srebro (2015). On Symmetric and Asymmetric LSHs for Inner Product Search. The norm-augmentation reduction from inner-product search to nearest-neighbor search.
• Prince (2023). Understanding Deep Learning. Notebook 8.4 explores high-dimensional spaces interactively.

Watch next

▶

▶