Vector Search Foundations: Geometry, Distance, and Recall

The k-NN warm-up introduced embeddings as the "meaning is geometry" idea: a model maps a document to a point in R^d, and similar things land near each other. That is the right intuition, but a contributor who reasons about recall regressions, the wrong space_type, or why exact search "doesn't scale" needs the intuition made rigorous. This chapter is the math floor under everything else in the k-NN curriculum. It is deliberately not about index structures (those are in Algorithms: HNSW, IVF, PQ) or the distance kernel (Lucene SIMD, native SIMD); it is about what an embedding space actually is, what a distance metric means, why approximation is mathematically forced at scale, and how you measure whether the answer was any good.

After this chapter you can: explain the curse of dimensionality and why it makes exact nearest neighbour both necessary to approximate and hard to approximate; derive L2, inner product, and cosine and the exact relationship between them; pick the correct space_type for a given embedding model and explain what a mismatch does to recall; convert a distance to an OpenSearch _score; and define recall@k and precision@k precisely enough to compute them.

Note: This is pure linear algebra and probability — no OpenSearch internals. But every claim here shows up later as a config knob, a mapping field, or a bug class, so the cross-links point forward to where each idea becomes operational.

What an embedding space is

An embedding is a function f: object → R^d learned by a model (a sentence-transformer, a CLIP image encoder, a fine-tuned BERT) such that semantic similarity becomes geometric proximity. Three facts about the space matter:

• It has no axes you can name. Unlike a row of [price, weight, rating], the d coordinates of an embedding are not individually interpretable. Only relative position — distances and angles between points — carries meaning. This is why every operation in vector search is a pairwise distance, never a per-field filter.
• d is large. 384, 768, 1024, 1536, 3072 are typical. The whole engineering problem flows from this: a single distance is O(d) work, and there are N points, so exact search is O(N·d) per query (derived below).
• The model defines the geometry. A model trained with a cosine objective produces vectors whose meaningful comparison is the angle between them, not their Euclidean gap. Using the wrong metric doesn't error — it silently returns worse neighbours. The metric is part of the model's contract.

   "cat"  ●           ● "kitten"        meaning  →  geometry
                ● "feline"              near points = similar objects
                                        the only signal is RELATIVE position
   "tax form" ●        ● "1040"         (distances & angles), not coordinates

Where these vectors come from — the encoder models, ml-commons/neural-search, dense vs sparse vs hybrid — is the subject of the vectorization & embeddings masterclass. Here we take the vectors as given and study the space they live in.

Why exact nearest neighbour is O(N·d) — and why that is the whole problem

Exact k-NN is brutally simple: to find the k nearest of N stored vectors to a query q, compute the distance from q to every stored vector and keep the smallest k.

cost(exact k-NN) = N distance computations × O(d) each = O(N·d) per query

At N = 100,000,000 vectors and d = 768, that is ~7.7 × 10^10 multiply-adds per query. Even at the SIMD rates from the SIMD chapters, that is hundreds of milliseconds to seconds per query — and it is linear in corpus size, so it only gets worse. Exact search is correct and is the right answer for small N (and is exactly what OpenSearch's script_score brute force and the "exact" k-NN path do, and what you use as ground truth to measure recall). But for large N it is hopeless.

So the field gives up exactness and builds index structures — HNSW, IVF — that examine only a tiny, cleverly-chosen subset of the N vectors and return the true neighbours most of the time. That is Approximate Nearest Neighbour (ANN). The entire k-NN plugin exists to make ANN fast and to let you trade a little correctness (recall) for a lot of speed. The two big questions — why is approximation necessary and why is it hard — are both answered by the geometry of high dimensions.

The curse of dimensionality

In low dimensions, "nearest neighbour" is a sharp, well-defined notion. In high dimensions, it softens — and understanding why explains both the need for ANN and its limits.

Distances concentrate

Take N random points in [0,1]^d. Look at the distance from a query to its nearest point versus its farthest point. As d grows, those two distances converge:

   d = 2:    nearest ●   ........   ● farthest      (clear winner)
   d = 1000: nearest ●..............● farthest      (nearly tied)

   relative contrast  (D_far − D_near) / D_near  →  0   as d → ∞

The reason is concentration of measure. For independent coordinates, the squared distance between two random points is a sum of d i.i.d. terms; by the law of large numbers its mean grows like d while its spread grows only like √d. So the relative variation in pairwise distances shrinks as 1/√d. Every point ends up at roughly the same distance from every other point. (Beyer et al., "When Is 'Nearest Neighbor' Meaningful?", 1999, made this precise.)

Two consequences a k-NN engineer lives with:

1. Exact NN gets less discriminative as d grows — the "nearest" point is only slightly nearer than many others. This is why real embeddings are not uniformly random: useful embeddings live on a low-dimensional manifold inside R^d where meaningful structure (clusters, directions) survives. ANN indexes work because they exploit that structure; they would fail on truly uniform high-dimensional data — which is exactly the worst case for HNSW recall.
2. Tree methods that work in 2-D/3-D collapse. KD-trees and the BKD trees Lucene uses for points prune by axis-aligned boxes; in high d, a box that excludes a useful fraction of points is astronomically rare, so the tree degenerates to a full scan. This is the reason vector search needs HNSW/IVF instead of reusing the existing numeric-points machinery — a question every newcomer asks.

Volume flees to the shell

A second high-d surprise that justifies normalization: almost all the volume of a high-dimensional ball sits in a thin shell near its surface. The fraction of a d-ball's volume within the outer ε is 1 − (1−ε)^d → 1. Combined with the fact that most random pairs of high-d vectors are nearly orthogonal (their cosine ≈ 0), this is why the angle between vectors is often a more stable signal than their Euclidean gap — motivating cosine/inner-product metrics and unit normalization, next.

The three distance metrics

OpenSearch's space_type selects the geometry. Three matter; they are not interchangeable, and the right one is dictated by the model that produced the vectors.

L2 (Euclidean) — straight-line distance

   d_L2(a, b) = sqrt( Σ_i (a_i − b_i)^2 )            # the SIMD kernels compute the squared form
   d_L2²(a, b) = Σ_i (a_i − b_i)^2                    # monotonic in d_L2; avoids the sqrt

L2 measures positional gap. It is sensitive to vector magnitude: two vectors pointing the same direction but with different lengths are far apart in L2. Use it when the model was trained with a Euclidean objective or when magnitude is meaningful. space_type: "l2". (Engines store and compare the squared distance because it is cheaper and ranks identically.)

Inner product (dot) — projection, magnitude-aware

   dot(a, b) = a · b = Σ_i a_i · b_i = |a| · |b| · cos(θ)

The dot product grows with both the alignment (cos θ) and the magnitudes of the two vectors. It is the cheapest to compute (the bare SIMD kernel, no subtract, no sqrt) and is the correct metric for models trained with an inner-product objective (many retrieval models, MIPS — maximum inner product search). space_type: "innerproduct". Note the ordering is reversed from a distance: larger dot = more similar, which is why score conversion (below) differs from L2.

Cosine — angle only, magnitude-blind

   cos(a, b) = (a · b) / (|a| · |b|)        ∈ [−1, 1]      # 1 = same direction, 0 = orthogonal, −1 = opposite
   d_cos(a, b) = 1 − cos(a, b)              ∈ [0, 2]       # a distance: smaller = more similar

Cosine ignores magnitude entirely — it is purely the angle between the vectors. It is the right metric for most text-embedding models (sentence-transformers, OpenAI/Cohere text embeddings), where a document's direction encodes meaning and its length is an artifact. space_type: "cosinesimil".

Cosine is a normalized dot product

This identity is the single most useful fact in the chapter, and the reason production systems rarely run a true cosine kernel in the hot loop. If you L2-normalize every vector to unit length — â = a / |a|, so |â| = 1 — then:

   cos(a, b) = (a · b)/(|a||b|) = (a/|a|) · (b/|b|) = â · b̂ = dot(â, b̂)

Cosine on raw vectors equals the plain dot product on unit-normalized vectors. And on unit vectors, L2 and dot are monotonically linked:

   d_L2²(â, b̂) = |â|² + |b̂|² − 2(â·b̂) = 2 − 2·dot(â, b̂)          # since |â|²=|b̂|²=1

So once vectors are normalized, L2 ranking, cosine ranking, and inner-product ranking all produce the identical neighbour order. This is why faiss and OpenSearch prefer to normalize once at index time and then run the cheap inner-product (or L2) SIMD kernel instead of the three-accumulator cosine kernel — you get cosine semantics at dot-product cost. It is also why the lucene engine maps DOT_PRODUCT similarity but requires unit vectors: the requirement is this identity.

Picking the metric — and what a mismatch costs

Warning: A metric mismatch does not raise an error. The query runs, returns k results, and they are simply worse than they should be — a recall bug with no stack trace. The first thing to check on a "k-NN results look subtly wrong" report is whether the space_type matches the embedding model's training objective, and whether vectors are normalized when the metric assumes it. This is the most common silent vector-search bug.

From distance to _score

OpenSearch ranks by _score, where higher is better. But L2 and cosine-distance are the opposite — smaller is better — and they live on different ranges. So the engine converts each metric's raw distance into a bounded, monotonically-increasing similarity score. The conversions (verify the exact forms for your version by grepping SpaceType in a k-NN checkout — KNNScoringUtil/SpaceType):

The point of the conversion is to give a single, comparable, larger-is-better scale so vector scores can be combined with BM25 lexical scores in hybrid search. The exact algebra is less important than the principle: a _score is a transformed distance, not the distance itself, so never compare a k-NN _score directly against a raw distance you computed by hand — convert first.

# Where the distance→score translation lives (names vary by version):
grep -rn "class SpaceType\|scoreTranslation\|score(\|1 / (1 +\|KNNScoringUtil" \
  src/main/java/org/opensearch/knn/index/ src/main/java/org/opensearch/knn/plugin/script 2>/dev/null | head

Measuring quality: recall@k and precision@k

ANN trades exactness for speed, so you need a number for how much exactness you gave up. The metric is recall@k, and you compute it against the exact (brute-force) result as ground truth.

   Let T  = the TRUE top-k for a query (from an exact O(N·d) scan).
   Let A  = the APPROXIMATE top-k the ANN index returned.

   recall@k    = |A ∩ T| / k        # of the k true neighbours, what fraction did we find?
   precision@k = |A ∩ T| / |A|      # of what we returned, what fraction was correct?

For k-NN, where the index returns exactly k results, |A| = k, so recall@k and precision@k are numerically equal — both are "fraction of the true top-k recovered." (They diverge only when |A| ≠ k, e.g. with a post-filter that drops results.) In ANN practice the term of art is almost always recall@k, and the engineering target is something like "recall@10 ≥ 0.95 at p99 latency ≤ X ms."

The whole point of the algorithms and their knobs (ef_search, nprobes, PQ aggressiveness) is to move along the recall–latency frontier: raising a knob buys recall at the cost of latency. You measure recall by comparing against an exact baseline — Lab K6 operationalizes exactly this, and Lab VI4 plots the frontier so you can see the trade-off.

Note: Recall is per query, then averaged. A single number ("recall@10 = 0.97") is a mean over a query set; the distribution matters — a high mean can hide a tail of queries near Voronoi boundaries or graph-disconnected regions that return poor neighbours. When triaging a recall complaint, look at the worst queries, not just the average.

Validation: prove you understand this

1. Derive the cost of exact k-NN in terms of N and d, and explain why ANN is necessary at large N and why exact search is still the right tool for ground truth.
2. State the curse of dimensionality precisely: what concentrates, at what rate, and the two consequences (less discriminative NN; tree methods collapse). Why do real embeddings escape the worst case?
3. Why can't OpenSearch just reuse its existing numeric points/BKD-tree machinery for vectors?
4. Write L2, inner product, and cosine. Prove cosine = dot product on unit-normalized vectors, and that on unit vectors L2 ranking equals dot ranking. What does this identity let production systems do in the hot loop, and why?
5. A text-embedding model trained with cosine similarity is indexed with space_type: l2 and un-normalized vectors. Describe the symptom, why there is no error, and the fix.
6. Convert an L2 squared distance of 0.25 and a cosine of 0.8 to _score. Why is the conversion monotonic, and why must scores (not raw distances) be used when combining with BM25?
7. Define recall@k and precision@k; explain why they coincide for standard k-NN and when they would not. Why is the distribution of per-query recall more informative than the mean?

When you can do all seven, the rest of the k-NN curriculum reads as engineering on top of this math: the algorithms are how you avoid the O(N·d) scan, the SIMD chapters are how you make the surviving distance computations fast, quantization is how you shrink them, and Lab VI4 lets you see all of it. Continue to the k-NN plugin architecture to leave the math and enter the running system.