Embedding Geometry and Similarity

Cosine, dot product and Euclidean distance and the exact relations between them; why high-dimensional near-orthogonality is what makes retrieval possible; and the maximum-of-N problem that limits it.

RAGGraduate⏱ 3 hours11 min readembeddingscosine similaritydot productnormalisationretrieval

5 problems →

AssumesHigh-Dimensional Geometry and Concentration of the Norm · Linear Algebra for Machine Learning

An embedding model is a map $f:\Xcal\to\R^d$ from text (or images, or anything) to vectors. Retrieval ranks documents by a similarity $s(f(q), f(z))$ between a query embedding and a document embedding. This page is about the geometry that ranking lives in.

Three similarities and how they relate

PropositionCosine, dot product and Euclidean distance agree on normalised vectors

For $u,v$ with $\norm u_2 = \norm v_2 = 1$ ,

\norm{u-v}_2^2 = 2 - 2\ip uv, \qquad \cos(u,v) = \ip uv .

Hence ranking by largest dot product, largest cosine, or smallest Euclidean distance gives the identical ordering on the unit sphere.

PropositionWithout normalisation the norm dominates the ranking

For general $u,v$ ,

\ip uv = \norm u_2\norm v_2\cos(u,v), \qquad \norm{u-v}_2^2 = \norm u_2^2 + \norm v_2^2 - 2\norm u_2\norm v_2\cos(u,v).

So dot-product ranking of documents $v$ against a fixed query $u$ orders by $\norm v_2\cos(u,v)$ , which a document can increase by growing its norm at fixed direction. Euclidean ranking penalises large $\norm v_2$ instead. The three criteria therefore give three different orderings.

Near-orthogonality

TheoremDistribution of the cosine between random directions

Let $u,v$ be independent and uniform on $S^{d-1}$ , $d\ge3$ . Then $t = \ip uv$ has density

\varrho_d(t) = \frac{\Gamma\!\left(\frac d2\right)}{\sqrt\pi\,\Gamma\!\left(\frac{d-1}{2}\right)}\big(1-t^2\big)^{\frac{d-3}{2}}, \qquad t\in[-1,1],

with $\E t = 0$ , $\Var(t) = 1/d$ , and

\P\big(|t|\ge\eps\big) \le 2\,e^{-d\eps^2/2} .

Run it: Embedding geometry and retrievalCosine similarity between random unit vectors in R^d, and the separation available to a retriever.

Key idea

Two independent directions in $\R^{768}$ have cosine within about $0.036 = 1/\sqrt{768}$ of zero. So a "background" similarity of $0.04$ is what noise looks like, and a genuine match at $0.3$ stands out by a factor of eight. This is what makes dense retrieval possible at all: high dimension supplies an enormous number of nearly-orthogonal directions, so distinct meanings can be assigned distinct directions without crowding.

Quantitatively, by the tail bound plus a union bound, one can place $N$ directions with all pairwise cosines below $\eps$ as long as $N^2e^{-d\eps^2/2}<1$ , i.e. $N < e^{d\eps^2/4}$ — exponentially many in the dimension. At $d = 768$ and $\eps = 0.2$ that is $e^{7.7}\approx 2200$ strictly $\eps$ -separated directions by this crude bound, and far more with a sharper packing argument; the exact statement is the packing number of the sphere.

The maximum-of-N problem

Retrieval is not a pairwise question. The relevant document must beat all $N$ distractors, so the quantity that matters is the maximum of $N$ similarities.

TheoremThe maximum of N distractor similarities

Let $z_1,\dots,z_N$ be independent uniform directions and $q$ a fixed unit vector. Then

\E\left[\max_{j\le N}\ip{q}{z_j}\right] \le \sqrt{\frac{2\log N}{d}} ,

and with probability at least $1-\delta$ ,

\max_{j\le N}\ip q{z_j} \le \sqrt{\frac{2\log(N/\delta)}{d}} .

CorollaryA sufficient condition for correct top-1 retrieval

Suppose the relevant document $z^\star$ satisfies $\ip{q}{z^\star} = \alpha$ and the $N$ distractors are independent uniform directions. Then top-1 retrieval succeeds with probability at least $1-\delta$ provided

\alpha > \sqrt{\frac{2\log(N/\delta)}{d}} .

Key idea

Put numbers in. At $d = 768$ and $\delta = 0.05$ :

Corpus size $N$	Required alignment $\alpha$
$10^3$	$0.16$
$10^6$	$0.20$
$10^9$	$0.24$
$10^{12}$	$0.27$

The threshold grows like $\sqrt{\log N}$ — slowly, but it grows, and there is no corpus size at which it stops. Tripling the required alignment is not possible by scaling the index; it requires a better embedding model or a re-ranking stage. Conversely, raising $d$ helps as $1/\sqrt d$ , which is the mathematical case for larger embedding dimensions.

Empirical observationReal embeddings are anisotropic

Empirical observation — a regularity seen in experiments. No theorem on this page establishes it in general.

Learned embeddings do not occupy the sphere uniformly. Ethayarajh measured average cosine similarities between random unrelated sentences in contextual models and found values of $0.3$ – $0.6$ in some layers — far above the $1/\sqrt d \approx 0.04$ the isotropic model predicts. The embeddings lie in a narrow cone.

What this does not say

Every theorem on this page assumes the distractors are independent uniform directions. Anisotropy breaks that assumption in the direction that makes retrieval harder:

the baseline similarity is inflated, so the contrast between a match and a non-match shrinks;
the distractors are correlated, so the maximum-of- $N$ bound — which is driven by the effective number of independent directions — is not the right calculation, and the effective $N$ can behave like a much larger number of truly independent draws in the cone's few informative directions;
near-duplicate documents, which real corpora are full of, are the worst case: they are highly correlated with the true match and the maximum-of- $N$ analysis says nothing about them.

The standard remedies are all attempts to restore approximate isotropy: mean-centring, whitening (BERT-flow and successors), and contrastive training with in-batch negatives, which explicitly penalises high similarity between unrelated pairs and is why models like Sentence-BERT and DPR behave far better than raw pretrained encoders.

Read this page's thresholds as a best case: the alignment actually required on real corpora is higher, and how much higher is an empirical question about the specific embedding model, not something the geometry determines.

Problems

References

PaperVladimir Karpukhin and collaborators (2020). Dense Passage Retrieval for Open-Domain Question Answering
PaperNils Reimers and Iryna Gurevych (2019). Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks
PaperKawin Ethayarajh (2019). How Contextual are Contextualized Word Representations?
PaperBohan Li and collaborators (2020). On the Sentence Embeddings from Pre-trained Language Models
BookRoman Vershynin (2018). High-Dimensional Probability: An Introduction with Applications in Data Science

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

PropositionCosine, dot product and Euclidean distance agree on normalised vectorsproof includedOn the unit sphere the three ranking criteria induce the same ordering; off it they do not.
PropositionWithout normalisation the norm dominates the rankingproof includedDot-product retrieval prefers high-norm documents independently of direction, which is a documented failure mode.
TheoremDistribution of the cosine between random directionsproof includedThe cosine between two independent uniform directions has an explicit density concentrating at zero at rate one over the square root of the dimension.
TheoremThe maximum of N distractor similaritiesproof includedThe best of N random distractor scores grows like the square root of two log N over d, so the alignment a retriever needs grows with the corpus.
CorollaryA sufficient condition for correct top-1 retrievalproof includedThe query-document alignment must exceed the maximum distractor similarity, giving an explicit threshold in terms of corpus size and dimension.
Empirical observationReal embeddings are anisotropicLearned embeddings occupy a narrow cone rather than the sphere uniformly, which inflates baseline similarities and invalidates the isotropic model.

Experiments

Embedding geometry and retrieval
Cosine similarity between random unit vectors in R^d, and the separation available to a retriever.

Problems (5)

All problems