Ask the word vectors of the previous article which words lie nearest to money, and the answer depends on what "near" means. By dot product the five nearest are total, large, annual, tax and paid. By cosine they are raising, cash, total, sums and pay. By Euclidean distance they are raising, sums, cash, deduct and borrow. When does the choice of measure matter, and which one is right? It matters whenever the stored vectors differ in length: the three measures rank alike for every query exactly when all stored vectors have one length, which this article proves in both directions. Where they differ, the right measure is the one the vectors were trained to be compared with, because the other two rank by a quantity the training never looked at.
A similarity measure here is a function of two vectors used to order a collection of stored vectors for a query vector. The stored vectors are written $\vec{p}_1, \dots, \vec{p}_N$, as passage vectors are throughout this unit, and the query vector $\vec{q}$; all lie in $\mathbb{R}^m$. The course's article on cosine similarity defined the three measures for term vectors, proved that the cosine is a cosine, and proved three facts this article uses and does not prove again: the identity $\lvert \vec{v}_1 - \vec{v}_2 \rvert^2 = 2(1 - \cos\theta)$ for unit vectors, the agreement of the three rankings when all document vectors have one length, and the trick of one extra coordinate that turns a dot-product ranking into a distance ranking. That page is the prerequisite. This one goes further in the directions dense vectors need, since a learned vector has negative components, a length that training chose, and an index that must search millions of its kind.
Here is the route. First the three measures are set side by side on real vectors. Then we ask what each measure is blind to, and prove when the three agree, including the converse the course page left open. Next we ask which of them are distances, because indexes are built for distances. Then come the reductions that turn each of the three searches into the others, with what each reduction costs an approximate index. Finally we measure what normalizing a vector throws away, and solve five problems by hand.
Three measures on the same vectors
The running example is a set of $N = 10{,}000$ vectors in $m = 100$ dimensions: the word vectors that Word Embeddings computes from the Brown corpus by factorizing a matrix of co-occurrence statistics. Each word's vector plays the part of a passage vector, and the vector of a query word plays the query. Word vectors are used here because the whole collection fits on a page of tables and every reader can judge the neighbors. Nothing below depends on the vectors standing for words.
The three measures are these.
- The dot product $\vec{q} \cdot \vec{p} = \sum_{i=1}^{m} q_i p_i$. Larger means more similar.
- The cosine $\cos(\vec{q}, \vec{p}) = \vec{q} \cdot \vec{p} \,/\, (\lvert \vec{q} \rvert \lvert \vec{p} \rvert)$, where $\lvert \vec{p} \rvert = \sqrt{\vec{p} \cdot \vec{p}}$ is the length. Larger means more similar. It is defined for nonzero vectors.
- The Euclidean distance $\lvert \vec{q} - \vec{p} \rvert$. Smaller means more similar.
For the query money, whose vector has length 1.04, the five best under each measure are these. The word itself is left out of every list.
| Rank | Dot product | Cosine | Distance |
|---|---|---|---|
| 1 | total 0.68 | raising 0.52 | raising 0.91 |
| 2 | large 0.66 | cash 0.50 | sums 0.93 |
| 3 | annual 0.59 | total 0.46 | cash 0.94 |
| 4 | tax 0.54 | sums 0.46 | deduct 0.95 |
| 5 | paid 0.54 | pay 0.46 | borrow 0.95 |
The lengths of the retrieved vectors explain the three columns. The dot-product column holds long vectors: total 1.40, large 1.70, annual 1.44, tax 1.68, paid 1.21. The distance column holds short ones: raising 0.76, sums 0.46, cash 0.77, deduct 0.48, borrow 0.33. The cosine column mixes the two, with total at 1.40 next to sums at 0.46 and pay at 0.99.
Two identities from the course page say why. The first is $\vec{q} \cdot \vec{p} = \lvert \vec{q} \rvert \lvert \vec{p} \rvert \cos(\vec{q}, \vec{p})$. For a fixed query, ranking by dot product is ranking by the cosine multiplied by the stored vector's length, so length is rewarded. The second is the expansion of the squared distance,
$$\lvert \vec{q} - \vec{p} \rvert^2 = \lvert \vec{q} \rvert^2 + \lvert \vec{p} \rvert^2 - 2\, \vec{q} \cdot \vec{p}.$$
The term $\lvert \vec{q} \rvert^2$ is the same for every stored vector. Ranking by increasing distance is therefore ranking by decreasing $\vec{q} \cdot \vec{p} - \tfrac{1}{2} \lvert \vec{p} \rvert^2$, so length is penalized. The cosine does neither.
The vectors of the running example differ a great deal in length. The shortest has length 0.005 and the longest 2.336, a ratio of 490.8, with a median of 0.552. So the three measures should disagree often, and they do. Over all 10,000 words taken as queries, the lists of ten nearest neighbors share on average 2.80 words between dot product and cosine, 3.39 between cosine and distance, and 0.28 between dot product and distance. No query has the same ten neighbors in the same order under any two of the measures. Only 73 of the 10,000 queries have even the same first neighbor under all three.
Example (a common misreading). "Cosine, dot product and distance are interchangeable for embeddings." They are interchangeable for unit vectors, and many published models produce unit vectors, which is where the saying comes from. For the vectors above they share fewer than four of ten neighbors. The statement is true under a condition, and the next two sections establish exactly what the condition is.
What each measure is blind to
Here is the idea in one sentence: each measure is unchanged by certain transformations of the vectors, and those transformations are the information the measure cannot see.
Four transformations matter. A rotation (more precisely an orthogonal map, which also covers reflections) is a matrix $R$ with $R^{\mathsf{T}} R = I$. A scaling multiplies a vector by a positive number. A translation adds one fixed vector $\vec{t}$ to every vector it is applied to. The table states what the ranking of the stored vectors does under each. The proofs follow it.
| Transformation | Dot product | Cosine | Distance |
|---|---|---|---|
| Rotate query and stored vectors together | unchanged | unchanged | unchanged |
| Scale the query | unchanged | unchanged | changes |
| Scale each stored vector by its own factor | changes | unchanged | changes |
| Translate the stored vectors only | unchanged | changes | changes |
| Translate query and stored vectors together | changes | changes | unchanged |
Rotation. $(R\vec{q}) \cdot (R\vec{p}) = \vec{q}^{\mathsf{T}} R^{\mathsf{T}} R\, \vec{p} = \vec{q} \cdot \vec{p}$. Lengths are dot products of a vector with itself, and a squared distance is the dot product of a difference with itself, where $R\vec{q} - R\vec{p} = R(\vec{q} - \vec{p})$. So all three measures keep their values, and all three rankings are unchanged. The coordinate axes of an embedding space carry no meaning that any of these measures can use.
Scaling the query. Replace $\vec{q}$ by $\lambda \vec{q}$ with $\lambda > 0$. Every dot product is multiplied by $\lambda$ and every cosine is unchanged, so both rankings stay. The distance ranking is by $\lambda\, \vec{q} \cdot \vec{p} - \tfrac{1}{2} \lvert \vec{p} \rvert^2$, in which $\lambda$ sets the exchange rate between the dot product and the length penalty, so it can change. A later section follows it as $\lambda$ grows.
Scaling the stored vectors. Multiply $\vec{p}_i$ by $\lambda_i > 0$. The cosine is unchanged, because numerator and denominator are both multiplied by $\lambda_i$. The dot product is multiplied by $\lambda_i$, so any stored vector with a positive dot product can be moved to the top by making it long enough, and the ranking changes. The distance changes too.
Translating the stored vectors only. $\vec{q} \cdot (\vec{p} + \vec{t}) = \vec{q} \cdot \vec{p} + \vec{q} \cdot \vec{t}$, and the added term is the same for every stored vector, so the dot-product ranking is unchanged. Cosine and distance both change in general, because the lengths $\lvert \vec{p} + \vec{t} \rvert$ change by different amounts.
Translating everything. $(\vec{q} + \vec{t}) - (\vec{p} + \vec{t}) = \vec{q} - \vec{p}$, so distances are unchanged. The dot product becomes $\vec{q} \cdot \vec{p} + \vec{q} \cdot \vec{t} + \vec{t} \cdot \vec{p} + \lvert \vec{t} \rvert^2$, and the term $\vec{t} \cdot \vec{p}$ differs between stored vectors, so the ranking changes. The cosine changes as well.
Example (every "changes" in the table). Take $\vec{q} = (1, 0)$, $\vec{p}_1 = (0, 1)$ and $\vec{p}_2 = (1, 2)$. The dot products are 0 and 1, the cosines 0 and 0.447, and the squared distances 2 and 4. So the dot product and the cosine put $\vec{p}_2$ first, and the distance puts $\vec{p}_1$ first. Translate the two stored vectors by $\vec{t} = (-2, -2)$, to $(-2, -1)$ and $(-1, 0)$. The dot products become $-2$ and $-1$, with $\vec{p}_2$ still first. The cosines become $-0.894$ and $-1$, so the cosine now puts $\vec{p}_1$ first, and the squared distances become 10 and 4, so the distance now puts $\vec{p}_2$ first. Translate the query as well, to $(-1, -2)$. The squared distances are 2 and 4 again. The dot products are 4 and 1 and the cosines 0.800 and 0.447, so both now put $\vec{p}_1$ first. For scaling a stored vector, go back to the original three vectors and halve $\vec{p}_2$ to $(\tfrac{1}{2}, 1)$: its squared distance from the query falls from 4 to 1.25, below the 2 of $\vec{p}_1$. For the dot product, in Problem 1 below the vector $(2, 2)$ has dot product 6 with the query against 10 for $(4, 2)$, and doubling it gives 12. Problem 4 shows the distance ranking changing as the query is scaled.
The rows say what each measure treats as noise. The cosine treats length as noise. The distance treats position relative to the origin as noise. The dot product treats neither as noise, and that is why it needs the most care: its ranking depends on where the origin is and on how long each stored vector is.
When the three rankings agree
Here is the idea in one sentence: equal lengths make the three rankings one, and any two stored vectors of unequal length can be told apart by a query built for the purpose.
Two measures rank alike for every query if, for every nonzero query $\vec{q}$ and every two stored vectors, one measure puts the first strictly above the second exactly when the other does. Ties therefore have to coincide as well.
Theorem 1. Let $\vec{p}_1, \dots, \vec{p}_N$ be nonzero vectors in $\mathbb{R}^m$.
- If all of them have the same length, then dot product, cosine and Euclidean distance rank alike for every query.
- If two of them, $\vec{p}_i$ and $\vec{p}_j$, have different lengths, then dot product and distance do not rank alike for every query, and neither do cosine and distance. Cosine and dot product do not rank alike for every query either, unless $\vec{p}_i$ and $\vec{p}_j$ point in exactly opposite directions.
So the three measures rank alike for every query if and only if all stored vectors have one length.
Proof of part 1. This is the proposition of the course page, repeated in two lines. If every length is $L$, the dot product is $L \lvert \vec{q} \rvert$ times the cosine, a positive constant times it. The distance ranks by $\vec{q} \cdot \vec{p} - \tfrac{1}{2} L^2$, the dot product less a constant. Multiplying by a positive constant and subtracting a constant preserve strict order and ties.
Proof of part 2. Name the two vectors so that $\lvert \vec{p}_i \rvert < \lvert \vec{p}_j \rvert$, and write $\vec{u}_i = \vec{p}_i / \lvert \vec{p}_i \rvert$ and $\vec{u}_j = \vec{p}_j / \lvert \vec{p}_j \rvert$ for their directions. Each of the three claims is proved by exhibiting a query.
Dot product against distance. Take $\vec{q} = \varepsilon (\vec{p}_j - \vec{p}_i)$ with
$$\varepsilon = \frac{\lvert \vec{p}_j \rvert^2 - \lvert \vec{p}_i \rvert^2}{4\, \lvert \vec{p}_j - \vec{p}_i \rvert^2} > 0.$$
The vectors differ, since their lengths do, so the denominator is not zero and $\vec{q} \neq \vec{0}$. The dot product prefers $\vec{p}_j$: $\vec{q} \cdot \vec{p}_j - \vec{q} \cdot \vec{p}_i = \varepsilon \lvert \vec{p}_j - \vec{p}_i \rvert^2 > 0$. The distance ranks by the key $\vec{q} \cdot \vec{p} - \tfrac{1}{2} \lvert \vec{p} \rvert^2$, and the key of $\vec{p}_i$ minus the key of $\vec{p}_j$ is
$$-\varepsilon \lvert \vec{p}_j - \vec{p}_i \rvert^2 + \tfrac{1}{2}\left(\lvert \vec{p}_j \rvert^2 - \lvert \vec{p}_i \rvert^2\right) = \left(-\tfrac{1}{4} + \tfrac{1}{2}\right)\left(\lvert \vec{p}_j \rvert^2 - \lvert \vec{p}_i \rvert^2\right) > 0.$$
So the distance prefers $\vec{p}_i$, and the two measures order the pair in opposite ways.
Cosine against distance. Suppose first that the directions differ, $\vec{u}_i \neq \vec{u}_j$. Then $\vec{u}_i \cdot \vec{u}_j < 1$, because $\lvert \vec{u}_i - \vec{u}_j \rvert^2 = 2 - 2\, \vec{u}_i \cdot \vec{u}_j$ is positive. Take $\vec{q} = \lambda \vec{u}_j$ with $\lambda > 0$ to be chosen. The cosine prefers $\vec{p}_j$ for every such $\lambda$: $\cos(\vec{q}, \vec{p}_j) = 1 > \vec{u}_i \cdot \vec{u}_j = \cos(\vec{q}, \vec{p}_i)$. The distance prefers $\vec{p}_i$ when $\lambda\, \vec{u}_j \cdot \vec{p}_i - \tfrac{1}{2} \lvert \vec{p}_i \rvert^2 > \lambda \lvert \vec{p}_j \rvert - \tfrac{1}{2} \lvert \vec{p}_j \rvert^2$, that is, when
$$\lambda \left(\lvert \vec{p}_j \rvert - \vec{u}_j \cdot \vec{p}_i\right) < \tfrac{1}{2}\left(\lvert \vec{p}_j \rvert^2 - \lvert \vec{p}_i \rvert^2\right).$$
The bracket on the left is positive, since $\vec{u}_j \cdot \vec{p}_i \le \lvert \vec{p}_i \rvert < \lvert \vec{p}_j \rvert$ by the Cauchy–Schwarz inequality. The right side is positive. So $\lambda = (\lvert \vec{p}_j \rvert^2 - \lvert \vec{p}_i \rvert^2) / (4 (\lvert \vec{p}_j \rvert - \vec{u}_j \cdot \vec{p}_i))$ satisfies it, and for that query the two measures order the pair in opposite ways. Now suppose the directions are equal, $\vec{u}_i = \vec{u}_j$. Then the cosine ties the two vectors for every query. For the query $\vec{q} = \vec{p}_i$ the distance to $\vec{p}_i$ is zero and the distance to $\vec{p}_j$ is not, so the distance does not tie them.
Cosine against dot product. Write $c = \vec{u}_i \cdot \vec{u}_j$ and $r = \lvert \vec{p}_i \rvert / \lvert \vec{p}_j \rvert$, so that $-1 \le c \le 1$ and $0 < r < 1$. There are three cases.
If $-1 < c < 1$, take $\vec{q} = \vec{u}_i + (1 - \delta)\, \vec{u}_j$ with
$$\delta = \frac{(1 + c)(1 - r)}{2 (1 - rc)}.$$
Then $\delta > 0$, and $\delta < 1$ because $(1 + c)(1 - r) < 2(1 - rc)$ rearranges to $c(1 + r) < 1 + r$, which holds as $c < 1$. The query is not zero, since $\vec{u}_i$ has length 1 and $(1 - \delta)\vec{u}_j$ has length less than 1. Its dot products with the two directions are $\vec{q} \cdot \vec{u}_i = 1 + (1 - \delta) c$ and $\vec{q} \cdot \vec{u}_j = c + (1 - \delta)$. The cosine prefers $\vec{p}_i$:
$$\cos(\vec{q}, \vec{p}_i) - \cos(\vec{q}, \vec{p}_j) = \frac{\vec{q} \cdot \vec{u}_i - \vec{q} \cdot \vec{u}_j}{\lvert \vec{q} \rvert} = \frac{\delta (1 - c)}{\lvert \vec{q} \rvert} > 0.$$
The dot product prefers $\vec{p}_j$:
$$\vec{q} \cdot \vec{p}_j - \vec{q} \cdot \vec{p}_i = \lvert \vec{p}_j \rvert \left[(1 + c)(1 - r) - \delta (1 - rc)\right] = \tfrac{1}{2} \lvert \vec{p}_j \rvert (1 + c)(1 - r) > 0.$$
If $c = 1$, the two vectors point the same way. The cosine ties them for every query. For $\vec{q} = \vec{p}_i$ the dot products are $\lvert \vec{p}_i \rvert^2$ and $\lvert \vec{p}_i \rvert \lvert \vec{p}_j \rvert$, which differ. The measures do not rank alike.
If $c = -1$, then $\vec{p}_j = -(\lvert \vec{p}_j \rvert / \lvert \vec{p}_i \rvert)\, \vec{p}_i$. For any query, $\cos(\vec{q}, \vec{p}_j) = -\cos(\vec{q}, \vec{p}_i)$ and $\vec{q} \cdot \vec{p}_j$ is a negative multiple of $\vec{q} \cdot \vec{p}_i$. Both measures put $\vec{p}_i$ first when $\vec{q} \cdot \vec{p}_i > 0$, put $\vec{p}_j$ first when it is negative, and tie when it is zero. This is the exception in the statement, and it is a real one. $\blacksquare$
The last sentence of the theorem follows: if all lengths are equal, part 1 applies, and if two lengths differ, the first claim of part 2 already separates dot product from distance. The exception in part 2 concerns one pair of measures only. A collection of two vectors $\vec{p}$ and $-2\vec{p}$ has unequal lengths, and cosine and dot product still rank it alike for every query, but the distance does not.
Check on the running example. Divide each of the 10,000 vectors by its length. The lists of ten nearest neighbors by cosine and by distance between the normalized vectors are then identical, in the same order, for all 10,000 queries. For 200 queries drawn at random (one draw, seed 2026) the distances were also computed directly, by subtracting the vectors and taking the length, with no use of the expansion: the order of the ten nearest is the cosine order for every one of them, and the nearest distance equals $\sqrt{2(1 - \cos\theta)}$ to nine decimal places. The dot product of unit vectors is the cosine, so all three lists coincide. Before normalization no query had two identical lists.
The theorem is about every possible query. For a particular set of queries the measures can agree by luck, and for vectors of nearly equal length they agree nearly always. Problem 3 builds the separating query for a pair of vectors by the proof's own formula.
Which of them are distances
Indexes that avoid comparing the query with every stored vector rely on geometry, and most of that geometry needs a distance. The next unit, Vector Search, builds such indexes. So it matters which of the three measures is a distance and what can be done about the others.
A metric on a set is a function $d$ of two points such that $d(x, y) \ge 0$ with equality exactly when $x = y$, $d(x, y) = d(y, x)$, and the triangle inequality $d(x, z) \le d(x, y) + d(y, z)$ holds. The triangle inequality is what lets an index discard points unseen: if $y$ is far from the query and $z$ is close to $y$, then $z$ is far from the query.
Euclidean distance is a metric. The first two properties are immediate. For the third, put $\vec{a} = \vec{x} - \vec{y}$ and $\vec{b} = \vec{y} - \vec{z}$. Then $\lvert \vec{a} + \vec{b} \rvert^2 = \lvert \vec{a} \rvert^2 + 2\, \vec{a} \cdot \vec{b} + \lvert \vec{b} \rvert^2 \le \lvert \vec{a} \rvert^2 + 2 \lvert \vec{a} \rvert \lvert \vec{b} \rvert + \lvert \vec{b} \rvert^2 = (\lvert \vec{a} \rvert + \lvert \vec{b} \rvert)^2$ by the Cauchy–Schwarz inequality, which the course page proves. Taking square roots gives $\lvert \vec{x} - \vec{z} \rvert \le \lvert \vec{x} - \vec{y} \rvert + \lvert \vec{y} - \vec{z} \rvert$.
One minus the cosine is not a metric. The quantity $1 - \cos(\vec{x}, \vec{y})$ is often called the cosine distance. Take three unit vectors in the plane at 0, 45 and 90 degrees. From the first to the second, $1 - \cos 45^\circ = 0.293$, and the same from the second to the third. The two legs add to 0.586. From the first to the third it is $1 - \cos 90^\circ = 1$, which is more than the two legs together. The triangle inequality fails. It also gives 0 for two different vectors that point the same way.
The angle between unit vectors is a metric. Let $\theta(\vec{x}, \vec{y}) = \arccos(\vec{x} \cdot \vec{y})$ for unit vectors, a number between 0 and $\pi$. It is zero exactly when $\vec{x} \cdot \vec{y} = 1$, which for unit vectors means $\lvert \vec{x} - \vec{y} \rvert^2 = 2 - 2 = 0$, that is, $\vec{x} = \vec{y}$. It is symmetric. For the triangle inequality take unit vectors $\vec{x}, \vec{y}, \vec{z}$ and write $\alpha = \theta(\vec{x}, \vec{y})$ and $\beta = \theta(\vec{y}, \vec{z})$. If $\alpha + \beta \ge \pi$ there is nothing to prove, since no angle exceeds $\pi$. Otherwise split $\vec{x}$ and $\vec{z}$ into their parts along $\vec{y}$ and across it:
$$\vec{x} = \cos\alpha\; \vec{y} + \sin\alpha\; \vec{x}', \qquad \vec{z} = \cos\beta\; \vec{y} + \sin\beta\; \vec{z}',$$
where $\vec{x}'$ and $\vec{z}'$ are unit vectors at right angles to $\vec{y}$. (The part of $\vec{x}$ along $\vec{y}$ is $(\vec{x} \cdot \vec{y})\, \vec{y} = \cos\alpha\, \vec{y}$. What remains is at right angles to $\vec{y}$ and has squared length $1 - \cos^2\alpha = \sin^2\alpha$. If $\sin\alpha = 0$, any unit vector at right angles to $\vec{y}$ serves as $\vec{x}'$.) Multiplying out, and using $\vec{y} \cdot \vec{x}' = \vec{y} \cdot \vec{z}' = 0$,
$$\vec{x} \cdot \vec{z} = \cos\alpha \cos\beta + \sin\alpha \sin\beta\; (\vec{x}' \cdot \vec{z}') \;\ge\; \cos\alpha \cos\beta - \sin\alpha \sin\beta = \cos(\alpha + \beta).$$
The inequality holds because the sines are not negative and $\vec{x}' \cdot \vec{z}' \ge -1$. The arccosine is a decreasing function, and $\alpha + \beta$ lies between 0 and $\pi$, so $\theta(\vec{x}, \vec{z}) \le \alpha + \beta$.
So on unit vectors there are two metrics that order vectors exactly as the cosine does: the angle, and the Euclidean distance $\sqrt{2(1 - \cos\theta)}$, the chord under that angle. Cosine search over normalized vectors is therefore a metric search, and any index for Euclidean distance can run it.
The dot product is not a distance in any form. No function that decreases with the dot product can be a metric, because a metric makes every point its own nearest neighbor, and under the dot product a vector need not be its own best match. The dot product of $\vec{p}$ with itself is $\lvert \vec{p} \rvert^2$, and a longer vector in a similar direction beats it. In the running example 6,543 of the 10,000 words, 65.4%, have a larger dot product with some other word's vector than with their own. Shrivastava and Li (2014, Theorem 1) use exactly this observation to prove that no locality-sensitive hash family, in the usual sense where one hash function is applied to query and data alike, exists for maximum inner product search: a point collides with itself with probability 1, and the definition would require some other point to collide with it more often. Locality-Sensitive Hashing defines such families. A search by dot product therefore has to be turned into something else before a metric index can serve it, and the next section does that.
Turning one search into another
Three search problems have now appeared. Given the stored vectors and a query, each asks for an index $i$:
- maximum inner product search (MIPS): the $i$ that maximizes $\vec{q} \cdot \vec{p}_i$;
- nearest neighbor search (NNS): the $i$ that minimizes $\lvert \vec{q} - \vec{p}_i \rvert$;
- maximum cosine search (MCS): the $i$ that maximizes $\cos(\vec{q}, \vec{p}_i)$.
"Inner product" is another name for the dot product, kept here because the problem is always called by it. Here is the idea in one sentence: by appending one coordinate to every vector, each of these problems can be rewritten as another, so that an index built for any one of them answers all three.
A reduction from one problem to another is a pair of maps, one applied to every stored vector when the index is built and one applied to the query, such that the ranking of the transformed vectors under the second measure is the ranking of the original vectors under the first. Bachrach et al. (2014) state the four reductions below as their Theorems 1 to 4, for use in a recommender system. The proofs are written out here in this unit's notation. Each preserves the entire ranking, not only its first place.
Proposition 1 (MIPS to NNS, one more dimension). Let $M$ be any number with $M \ge \lvert \vec{p}_i \rvert$ for all $i$. Map $\vec{p}$ to $\hat{p} = (\vec{p},\ \sqrt{M^2 - \lvert \vec{p} \rvert^2})$ and $\vec{q}$ to $\hat{q} = (\vec{q},\ 0)$. Then $\lvert \hat{q} - \hat{p} \rvert^2 = \lvert \vec{q} \rvert^2 + M^2 - 2\, \vec{q} \cdot \vec{p}$, so the order by increasing distance is the order by decreasing dot product.
This is the proposition proved in the course article, where $M$ is the largest length. The proof there uses only that the square root is real: the new coordinate makes every $\hat{p}$ have length exactly $M$ and leaves every dot product with $\hat{q}$ unchanged, and the expansion of the squared distance does the rest. So any upper bound on the lengths serves as $M$.
Proposition 2 (NNS to MIPS, one more dimension). Map $\vec{p}$ to $\tilde{p} = (\vec{p},\ -\tfrac{1}{2} \lvert \vec{p} \rvert^2)$ and $\vec{q}$ to $\tilde{q} = (\vec{q},\ 1)$. Then $\tilde{q} \cdot \tilde{p} = \tfrac{1}{2}\left(\lvert \vec{q} \rvert^2 - \lvert \vec{q} - \vec{p} \rvert^2\right)$, so the order by decreasing dot product is the order by increasing distance.
Proof. $\tilde{q} \cdot \tilde{p} = \vec{q} \cdot \vec{p} - \tfrac{1}{2} \lvert \vec{p} \rvert^2$. The expansion of the squared distance gives $\vec{q} \cdot \vec{p} - \tfrac{1}{2} \lvert \vec{p} \rvert^2 = \tfrac{1}{2} \lvert \vec{q} \rvert^2 - \tfrac{1}{2} \lvert \vec{q} - \vec{p} \rvert^2$. The first term does not depend on the stored vector, and the second decreases as the distance grows. $\blacksquare$
Proposition 3 (MIPS to MCS, one more dimension). With $\hat{p}$ and $\hat{q}$ as in Proposition 1 and $\vec{q} \neq \vec{0}$, $\cos(\hat{q}, \hat{p}) = \vec{q} \cdot \vec{p} \,/\, (\lvert \vec{q} \rvert M)$, so the order by cosine is the order by dot product.
Proof. $\hat{q} \cdot \hat{p} = \vec{q} \cdot \vec{p}$, $\lvert \hat{q} \rvert = \lvert \vec{q} \rvert$ and $\lvert \hat{p} \rvert = M$. The denominator $\lvert \vec{q} \rvert M$ is the same positive number for every stored vector. $\blacksquare$
Proposition 4 (MCS to MIPS, no new dimension). Map each nonzero $\vec{p}$ to $\vec{p} / \lvert \vec{p} \rvert$ and leave the query alone. Then $\vec{q} \cdot (\vec{p} / \lvert \vec{p} \rvert) = \lvert \vec{q} \rvert \cos(\vec{q}, \vec{p})$, so the order by dot product is the order by cosine.
Proof. The identity is the definition of the cosine multiplied by $\lvert \vec{q} \rvert$, which is positive and the same for every stored vector. $\blacksquare$
The four close a circle. Nearest neighbor search becomes maximum inner product search by Proposition 2 and then maximum cosine search by Proposition 3, at a cost of two coordinates. Maximum cosine search becomes maximum inner product search by Proposition 4 and then nearest neighbor search by Proposition 1, where the appended coordinate is zero because unit vectors already have $M = 1$: this is the statement that cosine search is nearest neighbor search among unit vectors. So an exact index for any one of the three problems is an exact index for the other two.
Check on the running example. For each of 200 queries drawn at random (one draw, seed 2026), all 10,000 vectors were transformed as each proposition says, and the ten best were found by the target measure with distances computed directly. In every case the list is the list of the source measure, in the same order.
What the reduction costs an approximate index
The reductions are exact, and an exact search after a reduction returns the exact answer. Indexes at scale are approximate, and for them Proposition 1 has a price that the algebra hides.
After the reduction every stored vector sits on a sphere of radius $M$, and the squared distance from the query is $\lvert \vec{q} \rvert^2 + M^2 - 2\, \vec{q} \cdot \vec{p}$. When $M^2$ is large beside the spread of the dot products, all distances are nearly equal. In the running example $M = 2.336$. Leave the query word's own vector out of both counts. Before the reduction, the farthest of the other 9,999 vectors is 5.01 times as far from the query as the nearest, taking the median over all 10,000 queries. After it, the farthest is only 1.109 times as far as the nearest.
That matters because the guarantee of an approximate index is usually multiplicative: it promises a point whose distance is at most $(1 + \varepsilon)$ times the smallest distance. Translate that promise back into dot products. Let $\vec{p}^*$ be the true maximizer and $d_*^2 = \lvert \vec{q} \rvert^2 + M^2 - 2\, \vec{q} \cdot \vec{p}^*$ its squared distance after the reduction. A returned vector $\vec{p}$ with $\lvert \hat{q} - \hat{p} \rvert \le (1 + \varepsilon)\, d_*$ satisfies $\lvert \vec{q} \rvert^2 + M^2 - 2\, \vec{q} \cdot \vec{p} \le (1 + \varepsilon)^2 d_*^2$, and subtracting the definition of $d_*^2$ gives
$$\vec{q} \cdot \vec{p} \;\ge\; \vec{q} \cdot \vec{p}^* - \left(\varepsilon + \tfrac{1}{2}\varepsilon^2\right) d_*^2.$$
The loss in dot product is bounded by a multiple of $d_*^2$, which contains $M^2$. In the running example a guarantee with $1 + \varepsilon = 1.109$ is met, for half of the queries, by every other vector in the collection, since none is farther than that multiple of the nearest distance. A guarantee that was informative for the original distances says nothing after the reduction unless $\varepsilon$ is made much smaller. It is one reason to treat maximum inner product search as a problem of its own, as a later article does, although an exact reduction to nearest neighbor search exists.
The second cost is in maintenance. The appended coordinate depends on $M$. If a new vector arrives that is longer than $M$, every stored vector's last coordinate must be recomputed and the index rebuilt. Choosing $M$ with room to spare avoids that, and by the bound above it makes the first cost worse.
An approximate reduction by an asymmetric map
In the same year as Bachrach et al., Shrivastava and Li (2014) gave an approximate reduction, which is worth knowing because it shows how much the single square-root coordinate of Proposition 1 achieves. Scale the stored vectors by one common factor so that every length is at most some $U < 1$, and scale the query to length 1; neither changes the dot-product ranking. For a whole number $t \ge 1$, append $t$ coordinates:
$$P(\vec{p}) = \left(\vec{p},\ \lvert \vec{p} \rvert^2,\ \lvert \vec{p} \rvert^4,\ \dots,\ \lvert \vec{p} \rvert^{2^t}\right), \qquad Q(\vec{q}) = \left(\vec{q},\ \tfrac{1}{2},\ \dots,\ \tfrac{1}{2}\right).$$
Proposition 5 (Shrivastava and Li, 2014, eq. 17). For $\lvert \vec{q} \rvert = 1$, $\lvert Q(\vec{q}) - P(\vec{p}) \rvert^2 = 1 + \tfrac{t}{4} - 2\, \vec{q} \cdot \vec{p} + \lvert \vec{p} \rvert^{2^{t+1}}$.
Proof. The squared length of $P(\vec{p})$ is $\lvert \vec{p} \rvert^2 + \lvert \vec{p} \rvert^4 + \dots + \lvert \vec{p} \rvert^{2^{t+1}}$, since the square of $\lvert \vec{p} \rvert^{2^i}$ is $\lvert \vec{p} \rvert^{2^{i+1}}$. The squared length of $Q(\vec{q})$ is $1 + t/4$. Their dot product is $\vec{q} \cdot \vec{p} + \tfrac{1}{2}(\lvert \vec{p} \rvert^2 + \lvert \vec{p} \rvert^4 + \dots + \lvert \vec{p} \rvert^{2^t})$. In the squared distance, which is the two squared lengths less twice the dot product, the powers $\lvert \vec{p} \rvert^2$ to $\lvert \vec{p} \rvert^{2^t}$ cancel and the last power $\lvert \vec{p} \rvert^{2^{t+1}}$ remains. $\blacksquare$
The last term is the error. It is at most $U^{2^{t+1}}$, which falls very fast as $t$ grows: with the authors' recommended $U = 0.83$ it is at most 0.475 for one appended coordinate, 0.225 for two and 0.051 for three. So nearest neighbor search on the transformed vectors answers maximum inner product search approximately. Over all 10,000 queries of the running example, the nearest transformed vector is the true maximizer for 7,120 queries with one appended coordinate, 9,203 with two, and 9,924 with three. The exact reduction, by Proposition 1, gets every one with a single coordinate. Neyshabur and Srebro (2015) made that comparison in general: they showed that the symmetric map of Proposition 1, applied to vectors scaled into the unit ball, yields a locality-sensitive hash with better guarantees than the asymmetric one, and they credit the transformation itself to Bachrach et al. (2014). Their analysis belongs to Locality-Sensitive Hashing.
The distance ranking as the query grows
The table of invariances left one entry open: scaling the query changes the distance ranking, and the question is how. The ranking by distance from $\lambda \vec{q}$ is the ranking by $\lambda\, \vec{q} \cdot \vec{p} - \tfrac{1}{2} \lvert \vec{p} \rvert^2$.
Proposition 6. Suppose the dot products $\vec{q} \cdot \vec{p}_i$ are all different, and number the stored vectors in decreasing order of dot product. Let
$$\lambda_0 = \max_{i} \frac{\lvert \vec{p}_i \rvert^2 - \lvert \vec{p}_{i+1} \rvert^2}{2\left(\vec{q} \cdot \vec{p}_i - \vec{q} \cdot \vec{p}_{i+1}\right)},$$
the maximum taken over neighbors in that order. Then for every $\lambda > \max(\lambda_0, 0)$ the ranking by distance from $\lambda \vec{q}$ is the ranking by dot product.
Proof. A list is in decreasing order of a key exactly when each entry's key exceeds the next entry's. The key of $\vec{p}_i$ exceeds the key of $\vec{p}_{i+1}$ when $\lambda (\vec{q} \cdot \vec{p}_i - \vec{q} \cdot \vec{p}_{i+1}) > \tfrac{1}{2} (\lvert \vec{p}_i \rvert^2 - \lvert \vec{p}_{i+1} \rvert^2)$. The bracket on the left is positive by the numbering, so this holds when $\lambda$ exceeds the ratio in the definition of $\lambda_0$. If $\lambda$ exceeds every such ratio, every neighboring pair is in order. $\blacksquare$
At the other extreme, as $\lambda$ falls to zero the key tends to $-\tfrac{1}{2} \lvert \vec{p} \rvert^2$, and the nearest vectors are simply the shortest ones, whatever the query. The distance ranking thus runs from "shortest first" for a short query to the dot-product ranking for a long one. Over all 10,000 queries of the running example, with each query vector multiplied by $\lambda$:
| $\lambda$ | Ten nearest by distance that are also among the ten largest dot products (mean) |
|---|---|
| 0.01 | 0.00 |
| 0.25 | 0.00 |
| 0.5 | 0.02 |
| 1 | 0.28 |
| 2 | 1.31 |
| 4 | 3.47 |
| 8 | 5.99 |
| 16 | 7.78 |
| 64 | 9.36 |
At $\lambda = 0.01$ the ten nearest vectors are, almost without exception, the ten shortest vectors of the collection other than the query's own (a mean overlap of 9.99 out of 10). The practical reading is that distance between unnormalized vectors is only meaningful when queries and stored vectors live on the same scale. An encoder trained with a distance objective puts them there. Vectors produced for another measure, compared by distance afterwards, are ranked largely by their lengths.
What normalization discards
Normalizing a vector keeps its direction and discards its length. Whether that is a loss depends on what the length holds, and that depends on how the vectors were made.
The length is information the training put there
In the running example the length is far from arbitrary. Longer vectors belong to more frequent words: the rank correlation between a vector's length and the logarithm of its word's count in the corpus is 0.858. The pattern is not monotone at the top, though. The three shortest vectors are inquirer, a word that occurs 13 times, followed by and and the, the two most frequent words of the corpus. The three longest are whose, against and green; whose occurs 251 times. Schakel and Wilson (2015) describe the same two forces in word2vec vectors trained on abstracts from the hep-th section of arXiv: for words used in a consistent context, length grows with frequency, while words used in many different contexts, of which the frequent function words are the extreme, end up with short vectors (their §3.2 and §3.3, Tables 2 and 3). They propose reading length, together with frequency, as a measure of a word's significance. That is a finding about those vectors, and the correlation above is a measurement on these.
The reason length can carry information is that the factorization fits dot products, not angles. Word Embeddings shows that the training objective is a function of the products $\vec{w} \cdot \vec{c}$ of a word vector with a context vector and of nothing else. The dot product is the quantity the model was fitted to predict, and the length of a vector is part of that prediction. The cosine between two word vectors is something else, a measure applied afterwards because it works. The next result says how loosely the objective pins it down.
The same dot products, different cosines
Proposition 7. Let $W$ be a matrix whose rows are word vectors and $C$ one whose rows are context vectors, and let $A$ be any invertible $m \times m$ matrix. Replace $W$ by $W A$ and $C$ by $C (A^{-1})^{\mathsf{T}}$. Then every dot product of a word vector with a context vector is unchanged.
Proof. The matrix of all such dot products is $W C^{\mathsf{T}}$, and $(W A)\,(C (A^{-1})^{\mathsf{T}})^{\mathsf{T}} = W A A^{-1} C^{\mathsf{T}} = W C^{\mathsf{T}}$. $\blacksquare$
So an objective that depends on the vectors only through $W C^{\mathsf{T}}$ cannot tell $(W, C)$ from $(W A, C (A^{-1})^{\mathsf{T}})$. The cosine between two rows of $W$ can. If $A$ is a rotation, the section on invariances shows the cosines are unchanged. If $A$ stretches the coordinates by different factors, they are not: Problem 5 gives three vectors in the plane whose nearest-neighbor order by cosine reverses when one coordinate is divided by four, while every dot product with a context vector stays exactly as it was. Steck, Ekanadham and Kallus (2024) make this point for matrix factorization models in general, and show that for some regularized linear models the cosine similarities are not even determined by the training objective.
On the running example, multiply each of the 100 coordinates of the word vectors by its own factor between one third and three, drawn at random, and divide the same coordinate of the context vectors by it. This was done 30 times, with seeds 1 to 30, and the results are given as a median with quartiles. In every draw the largest change in any word-context dot product over 200 sampled rows is below $10^{-12}$, which is rounding error. The cosine neighbors change a great deal: over 200 sampled queries, a word's ten nearest neighbors before and after share 4.65 [4.46, 4.83] words on average. On a set of human judgments of word relatedness, WordSim-353 (Finkelstein et al., 2002), of which 248 pairs have both words in this vocabulary, the rank correlation between cosine and the human ratings is 0.414 before the rescaling and 0.347 [0.324, 0.369] after. Word Embeddings describes that test.
The conclusion is not that the cosine between such vectors is meaningless. The factorization used here does fix a scaling, the symmetric one, and with it the cosine agrees with human judgments better than the rescaled versions do. The conclusion is that the agreement is a property of that particular choice among equally good solutions of the fitting problem, and has to be established by measurement, as it was here.
Popular neighbors
Rewarding length has a visible effect on who gets retrieved. Radovanović, Nanopoulos and Ivanović (2010) define the k-occurrences $N_k(x)$ of a point as the number of other points that have $x$ among their $k$ nearest neighbors, call points with very large $N_k$ hubs, and measure the asymmetry of the distribution of $N_k$ by its skewness, the third moment about the mean divided by the cube of the standard deviation. The mean of $N_{10}$ is always 10, since every query names ten neighbors. In the running example:
| Measure | Largest $N_{10}$ | Words never retrieved | Skewness of $N_{10}$ | Rank correlation of $N_{10}$ with length |
|---|---|---|---|---|
| Dot product | 526 | 6,756 | 5.8 | 0.80 |
| Cosine | 103 | 55 | 2.1 | 0.31 |
| Distance | 3,076 | 1,875 | 37.2 | −0.75 |
Under the dot product, 6,756 of the 10,000 words are in nobody's top ten, and the word retrieved most often, for 526 queries, is whose, the longest vector in the collection. Under distance the hub is inquirer, the shortest vector, which is among the ten nearest for 3,076 queries: a vector at the origin is close to everything that is short. Under the cosine the largest count is 103, for hauled, and only 55 words are never retrieved. Radovanović et al. report hubs in synthetic and real high-dimensional data under Euclidean and cosine distances, and observe that points close to the data's mean tend to be the hubs. The table adds what unequal lengths do on top of that: the two measures that see length concentrate retrieval on the extremes of length.
A shared direction
The cosine is blind to length and sensitive to the origin, by the table of invariances. If all vectors share a common component, every cosine is pushed up by it. Mu and Viswanath (2018) observed that published word vectors have a mean far from zero, and found that subtracting the mean and removing a few dominant directions improved the vectors on word similarity tests and other tasks. In the running example the mean vector is short, of length 0.118 against a median vector length of 0.552. The mean cosine between two random words is 0.038, and it falls to 0.003 when the mean vector is subtracted from every vector first. The correlation with WordSim-353 goes from 0.414 to 0.399, so for these vectors centering does not help. The symmetric factorization leaves little common component to remove, and what applies to other published vectors has to be measured again on each set.
What this means for a retriever
For a trained retriever the same reasoning gives a rule. The encoder is trained so that a score $s(q, p)$ is high for relevant pairs, and the score is one particular measure of the two vectors. By Theorem 1, a different measure at search time gives a different ranking unless the stored vectors have one length. So the index must use the measure of the training objective, or the vectors must be normalized, in which case all three measures agree and the cheapest can be used.
Both choices are made in practice. The dense passage retriever of Karpukhin et al. (2020) scores by the dot product of unnormalized vectors (their eq. 1); Dense Passage Retrieval describes it. In an ablation they trained with Euclidean distance instead and report top-20 retrieval accuracy on the Natural Questions development set of 76.1, against 78.1 for the dot product (their Table 6), and they state that both were better than cosine (their §5.2). The model this unit runs, described in Sentence and Passage Encoders, normalizes its output, so its dot products are cosines.
Thakur et al. (2021, Appendix H) isolated the effect of the choice. They trained two copies of one model on the same data with the same settings, one scored by cosine and one by dot product, and evaluated both on the datasets of their BEIR benchmark. The dot-product model retrieved longer documents and the cosine model shorter ones, on every dataset. On TREC-COVID, where many documents are a title with no abstract, nDCG@10 was 0.482 for cosine and 0.635 for dot product. On Signal-1M it was 0.261 and 0.243, the other way around, and on FEVER 0.670 and 0.685 (their Table 10). Their reading is that an unnormalized vector can grow with the length of the text it encodes, and whether that helps depends on whether longer documents are more often relevant in the collection at hand. This is the same finding as in the course, where cosine normalization of term vectors favored short documents and pivoted normalization was the remedy, carried over to learned vectors.
What is proved, what is cited, what the experiment shows
Proved on this page: the table of invariances; Theorem 1 in both directions; that Euclidean distance and the angle between unit vectors are metrics and one minus the cosine is not; Propositions 1 to 4, of which the first rests on the course page's proof; the bound on the dot product lost by an approximate nearest neighbor after the reduction; Proposition 5, the identity behind the asymmetric transformation; Proposition 6 on scaling the query; Proposition 7 on rescaling the factors.
Cited, not proved: that no symmetric locality-sensitive hash exists for maximum inner product search (Shrivastava and Li, 2014), and that the symmetric transformation gives a better hash than the asymmetric one (Neyshabur and Srebro, 2015); the observations of Schakel and Wilson (2015) on vector length, of Radovanović et al. (2010) on hubs, of Mu and Viswanath (2018) on the common component, and of Steck et al. (2024) on cosine in factorization models; every retrieval result of Karpukhin et al. (2020) and Thakur et al. (2021).
Measured, on one set of 10,000 word vectors from a corpus of about a million words: every number in the tables and paragraphs about the running example. They are observations about those vectors. Another set of vectors, in particular the unit vectors of a normalized encoder, would give different numbers, and for unit vectors Theorem 1 says the disagreement vanishes altogether.
Worked problems
These problems are posed on one small exact case, three vectors in the plane, and were written for this article; the unit has no assignments. Each uses only results proved above or on the course page. The script checks every number.
Problem 1 (three rankings). Let $\vec{q} = (2, 1)$, $\vec{p}_1 = (4, 2)$, $\vec{p}_2 = (8, 1)$ and $\vec{p}_3 = (2, 2)$. Rank the three stored vectors by dot product, by cosine and by distance. Then normalize them and rank again.
Solution. The three measures give three different orders, and after normalization they give one. The dot products are $2 \cdot 4 + 1 \cdot 2 = 10$, $2 \cdot 8 + 1 \cdot 1 = 17$ and $2 \cdot 2 + 1 \cdot 2 = 6$, so the order is $\vec{p}_2, \vec{p}_1, \vec{p}_3$. The squared lengths are $\lvert \vec{q} \rvert^2 = 5$, and 20, 65 and 8 for the stored vectors. The cosines are $10/\sqrt{5 \cdot 20} = 1.000$, $17/\sqrt{5 \cdot 65} = 0.943$ and $6/\sqrt{5 \cdot 8} = 0.949$, so the order is $\vec{p}_1, \vec{p}_3, \vec{p}_2$. The squared distances are $(2-4)^2 + (1-2)^2 = 5$, $(2-8)^2 + (1-1)^2 = 36$ and $(2-2)^2 + (1-2)^2 = 1$, that is, distances 2.236, 6.000 and 1.000, so the order is $\vec{p}_3, \vec{p}_1, \vec{p}_2$.
The longest vector, $\vec{p}_2$, is first by dot product and last by the other two. The shortest, $\vec{p}_3$, is first by distance. $\vec{p}_1$ points exactly along the query and is first by cosine.
After normalization the dot product of each unit vector with the query is $\sqrt{5}$ times its cosine, so the dot-product order is the cosine order $\vec{p}_1, \vec{p}_3, \vec{p}_2$. The distance from the normalized query to each unit vector is $\sqrt{2(1 - \cos\theta)}$: 0.000, 0.338 and 0.320 for $\vec{p}_1, \vec{p}_2, \vec{p}_3$, which again gives $\vec{p}_1, \vec{p}_3, \vec{p}_2$. This is part 1 of Theorem 1 with $L = 1$.
Problem 2 (both reductions). For the vectors of Problem 1, (a) append the coordinate of Proposition 1 and verify that distance now ranks as the dot product did; (b) append the coordinate of Proposition 2 and verify that the dot product now ranks as distance did.
Solution. (a) The largest squared length is $M^2 = 65$. The appended coordinates are $\sqrt{65 - 20} = \sqrt{45} = 6.708$ for $\vec{p}_1$, $\sqrt{65 - 65} = 0$ for $\vec{p}_2$ and $\sqrt{65 - 8} = \sqrt{57} = 7.550$ for $\vec{p}_3$. The query becomes $(2, 1, 0)$. By the proposition the squared distances are $\lvert \vec{q} \rvert^2 + M^2 - 2\, \vec{q} \cdot \vec{p} = 70 - 20 = 50$, $70 - 34 = 36$ and $70 - 12 = 58$. Directly, for $\vec{p}_1$: $(2-4)^2 + (1-2)^2 + 45 = 50$. The distances are 7.071, 6 and 7.616, so the order is $\vec{p}_2, \vec{p}_1, \vec{p}_3$, the dot-product order of Problem 1. The three distances lie much closer together than the original 2.236, 6.000 and 1.000, which is the first cost described above.
(b) The appended coordinates are $-\tfrac{1}{2} \lvert \vec{p} \rvert^2 = -10$, $-32.5$ and $-4$, and the query becomes $(2, 1, 1)$. The dot products are $10 - 10 = 0$, $17 - 32.5 = -15.5$ and $6 - 4 = 2$, so the order is $\vec{p}_3, \vec{p}_1, \vec{p}_2$, the distance order of Problem 1. Each equals $\tfrac{1}{2}(\lvert \vec{q} \rvert^2 - \lvert \vec{q} - \vec{p} \rvert^2)$: $\tfrac{1}{2}(5 - 5) = 0$, $\tfrac{1}{2}(5 - 36) = -15.5$ and $\tfrac{1}{2}(5 - 1) = 2$.
Problem 3 (the separating query). Let $\vec{p}_1 = (1, 0)$ and $\vec{p}_2 = (0, 2)$. Their lengths differ, so by Theorem 1 some query is ranked differently by cosine and by dot product. Construct it with the formula in the proof.
Solution. The query is $\vec{q} = (1, \tfrac{3}{4})$: the cosine prefers $\vec{p}_1$ and the dot product prefers $\vec{p}_2$. The shorter vector is $\vec{p}_1$, so in the proof's notation $\vec{u}_i = (1, 0)$, $\vec{u}_j = (0, 1)$, $c = \vec{u}_i \cdot \vec{u}_j = 0$ and $r = 1/2$. Then $\delta = (1 + c)(1 - r) / (2(1 - rc)) = (1 \cdot \tfrac{1}{2}) / 2 = \tfrac{1}{4}$, and $\vec{q} = \vec{u}_i + (1 - \delta)\vec{u}_j = (1, \tfrac{3}{4})$, of length $\sqrt{1 + 9/16} = 1.25$. The cosines are $1/1.25 = 0.8$ with $\vec{p}_1$ and $(\tfrac{3}{4} \cdot 2)/(1.25 \cdot 2) = 0.6$ with $\vec{p}_2$. The dot products are 1 with $\vec{p}_1$ and $\tfrac{3}{2}$ with $\vec{p}_2$. The difference of the dot products, $\tfrac{1}{2}$, is $\tfrac{1}{2} \lvert \vec{p}_j \rvert (1 + c)(1 - r) = \tfrac{1}{2} \cdot 2 \cdot 1 \cdot \tfrac{1}{2}$, as the proof computes.
Problem 4 (how long must the query be?). For the vectors of Problem 1, find all $\lambda > 0$ for which distance from $\lambda \vec{q}$ ranks the stored vectors as the dot product does.
Solution. Exactly the values $\lambda > 45/14 \approx 3.214$. In decreasing order of dot product the vectors are $\vec{p}_2, \vec{p}_1, \vec{p}_3$ with dot products 17, 10, 6 and squared lengths 65, 20, 8. By Proposition 6 the first pair is in order when $\lambda > (65 - 20)/(2(17 - 10)) = 45/14$, and the second when $\lambda > (20 - 8)/(2(10 - 6)) = 3/2$. Both hold exactly when $\lambda > 45/14$; for smaller $\lambda$ the first pair is out of order or tied, so the condition is necessary as well. Check with $\lambda = 4$: the query is $(8, 4)$ and the squared distances to $\vec{p}_1, \vec{p}_2, \vec{p}_3$ are 20, 9 and 40, giving $\vec{p}_2, \vec{p}_1, \vec{p}_3$. With $\lambda = 3$ the query is $(6, 3)$ and the squared distances are 5, 8 and 17, giving $\vec{p}_1, \vec{p}_2, \vec{p}_3$, which is not the dot-product order.
Problem 5 (same dot products, different neighbors). Three word vectors are $\vec{a} = (1, 1)$, $\vec{b} = (2, 1)$ and $\vec{c} = (1, 3)$, and one context vector is $\vec{x} = (1, 2)$. Divide the first coordinate of every word vector by 4 and multiply the first coordinate of the context vector by 4. Show that every word-context dot product is unchanged and that the nearest neighbor of $\vec{a}$ by cosine changes.
Solution. Before the change, $\vec{a}$ is nearer to $\vec{b}$; after it, nearer to $\vec{c}$; and the dot products with the context vector are 3, 4 and 7 both times. The dot products with $\vec{x}$ are $1 + 2 = 3$, $2 + 2 = 4$ and $1 + 6 = 7$. After the change the word vectors are $(\tfrac{1}{4}, 1)$, $(\tfrac{1}{2}, 1)$ and $(\tfrac{1}{4}, 3)$ and the context vector is $(4, 2)$, giving $1 + 2 = 3$, $2 + 2 = 4$ and $1 + 6 = 7$. This is Proposition 7 with $A$ the diagonal matrix with entries $\tfrac{1}{4}$ and 1. The cosines before are $\cos(\vec{a}, \vec{b}) = 3/\sqrt{2 \cdot 5} = 0.949$ and $\cos(\vec{a}, \vec{c}) = 4/\sqrt{2 \cdot 10} = 0.894$, so $\vec{b}$ is the nearer. After, $\cos(\vec{a}, \vec{b}) = (\tfrac{1}{8} + 1)/\sqrt{\tfrac{17}{16} \cdot \tfrac{5}{4}} = 0.976$ and $\cos(\vec{a}, \vec{c}) = (\tfrac{1}{16} + 3)/\sqrt{\tfrac{17}{16} \cdot \tfrac{145}{16}} = 0.987$, so $\vec{c}$ is the nearer. A model fitted only to the dot products with context vectors has no reason to prefer one version over the other.
What we have learned
Dot product, cosine and Euclidean distance differ only in how they treat the length of a stored vector: the first rewards it, the second ignores it, the third penalizes it. They rank alike for every query exactly when all stored vectors have one length, and for any two vectors of different lengths a query can be written down that separates the measures. Only the distance is a metric, but one appended coordinate turns a dot-product search into a distance search exactly, and three more reductions make the three search problems equivalent. The reduction is not free for an approximate index, because it pushes all distances together. On 10,000 word vectors of very unequal length the measures shared fewer than four of ten neighbors, the dot product sent 526 queries to the longest vector, and the distance sent 3,076 to the shortest. Length was not noise in those vectors: it tracked word frequency, and it was part of what the factorization fitted. Normalizing discards it, which is right for vectors trained to be compared by angle and wrong for vectors trained by dot product.
So far each vector has stood for one word. A query or a passage is a sequence of words, and the next article, Sentence and Passage Encoders, is about turning the sequence into one vector. Searching such vectors without comparing the query with all of them begins in Nearest Neighbor Search in High Dimensions.
Every number on this page is computed by tools/experiments/dense/similarity-measures-for-embeddings.py in the site's repository, which fails if the page shows a number it did not compute. The word vectors come from brown_sgns.py in the same folder, and are the symmetric factorization with shift $\ln 5$ described in Word Embeddings.
References
- Bachrach, Y., Finkelstein, Y., Gilad-Bachrach, R., Katzir, L., Koenigstein, N., Nice, N., and Paquet, U. (2014). Speeding up the Xbox recommender system using a Euclidean transformation for inner-product spaces. In Proceedings of the 8th ACM Conference on Recommender Systems (RecSys 2014), 257–264. record · 2 pages
- Finkelstein, L., Gabrilovich, E., Matias, Y., Rivlin, E., Solan, Z., Wolfman, G., and Ruppin, E. (2002). Placing search in context: The concept revisited. ACM Transactions on Information Systems, 20(1), 116–131. record · 2 pages
- Karpukhin, V., Oğuz, B., Min, S., Lewis, P., Wu, L., Edunov, S., Chen, D., and Yih, W. (2020). Dense passage retrieval for open-domain question answering. In Proceedings of EMNLP 2020, 6769–6781. arXiv:2004.04906. record · 10 pages
- Mu, J., and Viswanath, P. (2018). All-but-the-top: Simple and effective postprocessing for word representations. In International Conference on Learning Representations (ICLR 2018). arXiv:1702.01417. record
- Neyshabur, B., and Srebro, N. (2015). On symmetric and asymmetric LSHs for inner product search. In Proceedings of the 32nd International Conference on Machine Learning, PMLR 37, 1926–1934. arXiv:1410.5518. record
- Radovanović, M., Nanopoulos, A., and Ivanović, M. (2010). Hubs in space: Popular nearest neighbors in high-dimensional data. Journal of Machine Learning Research, 11, 2487–2531. record
- Schakel, A. M. J., and Wilson, B. J. (2015). Measuring word significance using distributed representations of words. arXiv:1508.02297. record
- Shrivastava, A., and Li, P. (2014). Asymmetric LSH (ALSH) for sublinear time maximum inner product search (MIPS). In Advances in Neural Information Processing Systems 27, 2321–2329. arXiv:1405.5869. record
- Steck, H., Ekanadham, C., and Kallus, N. (2024). Is cosine-similarity of embeddings really about similarity? In Companion Proceedings of the ACM Web Conference 2024 (WWW '24), 887–890. Read here in its arXiv version, arXiv:2403.05440. record
- Thakur, N., Reimers, N., Rücklé, A., Srivastava, A., and Gurevych, I. (2021). BEIR: A heterogeneous benchmark for zero-shot evaluation of information retrieval models. In Proceedings of the NeurIPS 2021 Datasets and Benchmarks Track. arXiv:2104.08663; read in version 4 of the arXiv paper, whose Table 2 agrees with the published version. record · 7 pages