Vector search - The problem

Suppose you have a list of N things and someone hands you a query. You want to find the thing in the list most similar to the query.

To make this tractable, you represent your things as points in some space and define a distance between points. "Most similar" becomes "closest". This reframing is the entire setup for nearest neighbor search, and it shows up everywhere:

A directory of restaurants stored as (latitude, longitude). Query: where you're standing. Closest entry: nearest restaurant.
A library of paint swatches stored as (R, G, B). Query: a color sampled from a photo. Closest entry: best matching paint.
A database of protein conformations stored as 3K-dimensional vectors (K atoms with x, y, z each). Query: a newly observed conformation. Closest entry: most structurally similar known protein.
A collection of sentences turned into 768-dimensional embedding vectors by a language model. Query: a search phrase. Closest entry: most semantically similar sentence in the database.

Same shape every time. Points in some space, a distance function, and the goal of finding the closest point to a query.

The problem has a few standard variants. Single nearest returns one closest point. k-nearest (k-NN, where NN stands for nearest neighbor) returns the k closest. Range search returns every point within distance r. Approximate nearest neighbor (ANN) returns a point that's close to the closest, accepting some error in exchange for speed.

The metric also varies. Each one captures a different notion of "how far apart":

Euclidean distance is the straight-line distance between two points, the d-dimensional Pythagoras (square root of the sum of squared coordinate differences).
Manhattan distance (also called L1, or taxicab distance) is the sum of absolute coordinate differences, named for the grid-walking distance between two intersections in a city where you can't cut through buildings.
Cosine distance measures the angle between two vectors and ignores their magnitudes entirely, which makes it the standard choice for embeddings where direction encodes meaning and length doesn't.
Hamming distance is the number of positions where two equal-length strings differ, useful for bit vectors and short binary codes.

The structure of the problem stays roughly the same regardless of which metric you pick, though the algorithms have to be careful about which one they assume. For the rest of this article I'll mean Euclidean distance and a single nearest neighbor, unless I say otherwise.

One dimension: easy

If your "points" are scalar numbers, the problem is trivial. Sort the list once. To answer a query Q, binary-search for the position where Q would fit, and check the two list entries on either side. The closer of the two is the answer.

Binary search itself is repeated halving: compare Q to the middle element of the sorted list, discard whichever half can't contain the answer, and recurse on the half that can. Each step halves the remaining search space, so after $lo g_{2} (N)$ steps you're down to a single position. Twenty steps for a million-element list, thirty for a billion.

preprocess: sort list                   O(N log N)
query:      i = binary_search(list, Q)  O(log N)
            return whichever of list[i-1], list[i] is closer to Q

The cost grows so slowly that you can stop thinking about it.

The reason this works is structural. In one dimension, sorted order is a representation of geometric proximity. Two numbers that are next to each other in the sorted array are exactly the closest pair around them on the number line. Binary search is just descending into a recursive partition of a 1D space, with the sort-order acting as a perfectly informative summary of where every point lies relative to every other.

Two dimensions: still tractable, more work

In 2D you cannot just sort by one coordinate. Two points can sit next to each other in x but be far apart in y. Sorted order along one axis tells you nothing about closeness in the plane.

You need a structure that respects both axes at once. The classical answer is the kd-tree (k-dimensional tree, where the k is a placeholder for however many dimensions you happen to be working in). It's a binary tree that recursively cuts the plane into smaller and smaller rectangles, with each cut chosen so that roughly half the points fall on each side.

To make a single cut, you pick an axis and draw a line perpendicular to it. Pick the x-axis, you get a vertical line; pick y, you get a horizontal one. The reason for axis-aligned cuts is that "which side is the query on" reduces to a single coordinate comparison: is the query's x bigger or smaller than the line's x?

Where do you draw the line? Through the median point along that axis. The phrase needs unpacking. The median of a list of numbers is the middle entry once they're sorted: in [1, 3, 5, 8, 9], the median is 5. The "median point along an axis" extends this to 2D points: take all your points, sort them by just one of their coordinates (ignore the other one entirely), and pick the middle entry. Its coordinate on the chosen axis is the splitting value, and the cutting line passes through it.

Why the median, specifically? Because it splits the points into two groups of equal size. Equal-sized children means a balanced tree of depth $lo g_{2} (N)$ , which is what makes the descent cheap. If you split at some arbitrary other point, one side could end up with most of the data and the tree would degenerate toward a list.

Here's a concrete build with seven points:

Point	x	y
A	1	4
B	3	7
C	5	2
D	6	8
E	8	3
F	2	6
G	7	5

At the root we'll split on $x$ . Sort the points by their $x$ -coordinate alone: A, F, B, C, D, G, E (with $x$ values $1, 2, 3, 5, 6, 7, 8$ ). The median, the 4th of 7, is C with $x = 5$ . Draw a vertical line at $x = 5$ . The three points with $x < 5$ (A, F, B) become the left subtree. The three with $x > 5$ (D, G, E) become the right subtree. C itself sits at the root and remembers that its splitting axis was $x$ and its splitting value was $5$ .

At depth 1 we split on $y$ , alternating axes as we descend. In the left subtree, the points sorted by $y$ are A ( $y = 4$ ), F ( $y = 6$ ), B ( $y = 7$ ). Median: F with $y = 6$ . Within the left half-plane (the region where $x < 5$ ), draw a horizontal line at $y = 6$ . A is below the line, B is above, F sits at this internal node.

Symmetric work on the right. Sort D, G, E by $y$ : E ( $y = 3$ ), G ( $y = 5$ ), D ( $y = 8$ ). Median: G with $y = 5$ . Within the right half-plane ( $x > 5$ ), draw a horizontal line at $y = 5$ . E goes below, D goes above, G sits at the node.

The resulting tree:

Root: C, splits the plane on $x = 5$ .
- Left child: F, splits the left half-plane on $y = 6$ .
  - Left leaf: A.
  - Right leaf: B.
- Right child: G, splits the right half-plane on $y = 5$ .
  - Left leaf: E.
  - Right leaf: D.

The plane is now carved into four rectangles, each holding one leaf, with the cutting lines passing through C, F, and G. Each internal node is associated with a rectangular region (the part of the plane that ends up below it in the tree), and the regions get smaller as you descend.

Now the search. To find the nearest neighbor of a query Q, you walk down the tree to a leaf, then walk back up checking whether anything was missed.

The descent. Start at the root. At each internal node, compare Q's coordinate on the node's splitting axis to the node's splitting value. Go left if smaller, right if larger. Repeat until you hit a leaf. The point at that leaf is your first candidate for the nearest neighbor; track its distance from Q as your current best.

Why a single descent isn't enough. The descent only ever picked sides based on splitting lines, never on actual distances to points. It lands you in the leaf whose rectangular cell contains Q, which is a reasonable starting guess, but not necessarily the right answer. Q can sit near the edge of its cell, with the actual nearest neighbor a short hop across a splitting line in a neighboring cell. The leaf can't see across its own boundary. The backtrack pass is what catches those cases.

The pruning bound. As you walk back up, you keep track of the closest point seen so far, call its distance best. At each ancestor you have to ask: could the other subtree, the one the descent didn't enter, contain anything closer than best?

There's a clean geometric answer. Every kd-tree splitting line is axis-aligned, so the shortest distance from Q to that line is simply the gap along the splitting axis: $∣ Q_{a} - s_{a} ∣$ , where $Q_{a}$ and $s_{a}$ are the coordinates of the query and the splitting line on that axis. Any point on the far side of the line lives at least that far from Q, since reaching it from Q requires crossing the line. So the comparison is straightforward: if $∣ Q_{a} - s_{a} ∣ \geq best$ , the entire far subtree is too far away to matter and you skip it. Otherwise the line passes within $best$ of Q, the far side might genuinely contain a closer point, and you have to recurse: descend into the far subtree the same way you descended from the root, leaf-search and all.

While you're at the ancestor, also check whether the ancestor's own point (internal nodes hold real points, not just splitting lines) is closer than best, and update best if so.

A worked search. Take the tree built above and query $Q = (4, 5)$ . The actual nearest neighbor will turn out to be F, but it's a couple of levels above the leaf the descent reaches.

Descent. At C (splits $x = 5$ ), $Q_{x} = 4 < 5$ , go left. At F (splits $y = 6$ ), $Q_{y} = 5 < 6$ , go left. Hit leaf $A = (1, 4)$ . Initial best: A at distance $(4 - 1)^{2} + (5 - 4)^{2} = 10 \approx 3.16$ .

Back up to $F = (2, 6)$ . Distance from Q to F is $2^{2} + 1^{2} = 5 \approx 2.24$ , better than $3.16$ , so best becomes F at $2.24$ . F's splitting line is $y = 6$ . Gap from Q to the line: $∣5 - 6∣ = 1$ , which is less than $2.24$ . The far subtree might hold a closer point, so descend into it. The far side is the single leaf $B = (3, 7)$ , at distance $1 + 4 = 5 \approx 2.24$ . Tie; nothing changes.

Back up to $C = (5, 2)$ . Distance from Q to C is $1 + 9 = 10 \approx 3.16$ , worse than $2.24$ . C's splitting line is $x = 5$ . Gap: $∣4 - 5∣ = 1$ , less than $2.24$ , can't prune. Descend the right subtree. At $G = (7, 5)$ , distance to Q is $3$ , worse than $2.24$ . G's split is $y = 5$ , $Q_{y} = 5$ sits exactly on the line, gap is $0$ , so both sides have to be searched: $E = (8, 3)$ gives distance $20 \approx 4.47$ , $D = (6, 8)$ gives $13 \approx 3.61$ , neither beats $2.24$ .

Final answer: F at distance $5 \approx 2.24$ .

The animation below walks through the build and the search one move at a time. Dashed gray lines are partitions; the yellow ring marks the node we're currently examining; the green ring is the running best, with a green segment to Q showing its distance; faded gray segments are points already visited that didn't improve on the best; the blue circle is the search radius (current best distance); the orange perpendicular shows the pruning bound, the minimum distance to anything in the far subtree.

1 / 16

Seven points

Seven points labeled A through G. We'll build a kd-tree on them, then search for the nearest neighbor of Q=(4, 5).

This particular query landed near every splitting line, so almost no pruning fired and the search visited every node. That's the worst case. On a typical query with reasonably spread-out data, most splits sit well away from Q, the bound fires at most levels, and the average cost works out to about $O (lo g N)$ . That's what earns the structure its keep.

There's another structure worth knowing about, the Voronoi diagram: a partition of the plane into cells, where each cell consists of all locations closest to one specific point. In 2D, you can precompute it in $O (N lo g N)$ time, store it in $O (N)$ space, and answer queries in $O (lo g N)$ by point-locating Q in the diagram. This gives you provably optimal query time in 2D.

Three dimensions, and a bit beyond

Both ideas extend to 3D. The kd-tree alternates among three axes instead of two. Pruning still works because a 3D bounding box still gives you a usable lower bound on the distance from Q to any point inside it. The Voronoi diagram extends too, but its combinatorial complexity grows, and it stops being a clean win past 3D.

Up to maybe 10 or 15 dimensions, kd-trees and their relatives (ball trees, R-trees, cover trees) give you sublinear search on roughly uniform data. The exact crossover depends on the data and the implementation, but the regime is well understood.

Above that, something starts to break. Pruning fires less and less. The tree starts to behave like a linear scan with bookkeeping overhead. To see why, we need to compute the expected distance and its variance, and to do that precisely we'll first lock down what those terms mean.

A short detour: density, expectation, variance

Three ideas show up in the next derivation and deserve a clean definition.

Probability density. Pick a uniformly random number from $[0, 1]$ . What's the probability of landing exactly at $0.5$ ? Zero. The interval has uncountably many points, and if any single one of them carried positive probability the total across all of them would exceed 1. So probability has to live in intervals, not in points. The probability of landing in $[0.4, 0.6]$ , for instance, is $0.2$ , since that interval covers 20% of the line. The general pattern declares a density $f (x)$ , probability per unit length, and reads probabilities as areas under it:

Pr (a \leq X \leq b) = \int_{a}^{b} f (x) d x

The total area must be 1, since $X$ has to land somewhere. For uniform on $[0, 1]$ , "every value equally likely" forces the density to be the same at every point in the interval. Call that constant $c$ . The area under $f$ over the interval is then a rectangle of width 1 (the length of $[0, 1]$ ) and height $c$ , so its area is $c$ . Setting that equal to 1 gives $c = 1$ . Hence $f (u) = 1$ on $[0, 1]$ and $0$ elsewhere.

Expectation. A plain average of $g$ over an interval $[a, b]$ is $\frac{1}{b - a} \int_{a}^{b} g (x) d x$ : integrate the values and divide by the total weight, which here is just the interval's length. A weighted average gives each point its own weight $f (x)$ instead of treating them all equally, and divides by the total weight $\int f (x) d x$ . Probability densities are built to integrate to 1, so that division is already implicit, and the formula collapses to:

E [g (X)] = \int g (x) f (x) d x

For uniform on $[0, 1]$ , $f (u) = 1$ on the interval, so weighting by it doesn't change anything and the integral simplifies to $\int_{0}^{1} g (x) d x$ . That is why the earlier derivation could write $E [U^{2}] = \int_{0}^{1} u^{2} d u$ .

Variance. Variance is the expected squared deviation from the mean:

Var [X] = E [(X - E [X])^{2}] = E [X^{2}] - (E [X])^{2}

It quantifies how far values typically sit from the mean. The standard deviation $sd [X] = Var [X]$ has the same units as $X$ and is the more interpretable form.

The normal distribution. The bell-shaped density specified by a mean $μ$ and a variance $σ^{2}$ :

f (x) = \frac{1}{σ 2 π} exp (- \frac{( x - μ ) ^{2}}{2 σ ^{2}})

It dominates probability theory because of the central limit theorem: a sum of many independent random variables tends toward a normal distribution, regardless of the shape of the individual terms. Squared distance between two random points is exactly such a sum, with one term per dimension, which is why we will see its distribution become more and more bell-shaped (and tighter) as $d$ grows.

The chart below bundles all four ideas. The blue curve is the density; the green vertical line is the mean $μ$ ; the dashed yellow lines mark $μ \pm σ$ . Drag the sliders, or click Animate σ to see the curve breathe.

μ0.0σ1.00

blue: density · green: mean μ · dashed yellow: μ ± σ

With those tools in place, we can ask precisely how distances behave when $d$ grows.

What happens to distances as the dimension grows

Pick two random points $X$ and $Y$ in $d$ dimensions. Each coordinate is a fresh random number between 0 and 1, picked so that every value in $[0, 1]$ is equally likely (a uniform distribution: no clustering toward any part of the range, no bias) and so that knowing any one coordinate tells you nothing about any of the others (the coordinates are independent). $X$ and $Y$ are two random points scattered into the unit cube $[0, 1]^{d}$ with no preferred direction or region.

The squared distance between them is a Pythagoras sum over $d$ terms:

∥ X - Y ∥^{2} = (X_{1} - Y_{1})^{2} + (X_{2} - Y_{2})^{2} + \dots + (X_{d} - Y_{d})^{2}

What follows is the full derivation that the mean of this sum grows like $d /6$ , the variance like $7 d /180$ , and their ratio (the coefficient of variation) shrinks like $1/ d$ . If you trust the result, skip past it; the table and demo right after make the same point in concrete numbers.

▸ Show the full derivation (mean, variance, and coefficient of variation)

We want $E [∥ X - Y ∥^{2}]$ , the expected value of this $d$ -term sum. Two facts about expectation reduce the whole thing to a one-term computation.

First, expectation is linear: for any random variables $A$ and $B$ , $E [A + B] = E [A] + E [B]$ . (This drops out of the integral definition of expectation, since the integral of a sum is the sum of the integrals.) Applied to our $d$ -term sum:

E [∥ X - Y ∥^{2}] = E [(X_{1} - Y_{1})^{2}] + E [(X_{2} - Y_{2})^{2}] + \dots + E [(X_{d} - Y_{d})^{2}]

Second, every term has the same distribution. Each pair $(X_{i}, Y_{i})$ is two independent uniform draws on $[0, 1]$ , identical setup to every other pair, so $E [(X_{i} - Y_{i})^{2}]$ comes out to the same value for every $i$ . The sum collapses to $d$ copies of one number:

E [∥ X - Y ∥^{2}] = d \cdot E [(U - V)^{2}]

where $U$ and $V$ stand in for one independent uniform pair. The $d$ -dimensional answer is just $d$ times the one-term mean, so the rest of this section computes that one term.

Expand the square and take expectations of each piece. The cross-term factors because $U$ and $V$ are independent ( $E [U V] = E [U] \cdot E [V]$ when the variables are independent), so:

E [(U - V)^{2}] = E [U^{2}] - 2 E [U] E [V] + E [V^{2}]

To evaluate the right-hand side, we need $E [U]$ and $E [U^{2}]$ . From the detour, the expected value of any function $g (U)$ for $U$ uniform on $[0, 1]$ is the plain integral of $g$ over the interval:

E [g (U)] = \int_{0}^{1} g (u) d u

Apply that with $g (u) = u$ and $g (u) = u^{2}$ :

E [U] E [U^{2}] = \int_{0}^{1} u d u = [\frac{u ^{2}}{2}]_{0}^{1} = \frac{1}{2} = \int_{0}^{1} u^{2} d u = [\frac{u ^{3}}{3}]_{0}^{1} = \frac{1}{3}

$E [U] = 1/2$ is the midpoint of the interval, the obvious answer for a uniform distribution. $E [U^{2}] = 1/3$ is less obvious: squaring shrinks fractions ( $u = 0.5$ gives $u^{2} = 0.25$ , $u = 0.1$ gives $u^{2} = 0.01$ ), so $u^{2}$ is biased toward small values, and its average lands at $1/3$ , well below the midpoint $1/2$ of the range $[0, 1]$ .

$V$ has the same moments by symmetry. Plug everything in:

E [(U - V)^{2}] = \frac{1}{3} - 2 \cdot \frac{1}{2} \cdot \frac{1}{2} + \frac{1}{3} = \frac{1}{3} + \frac{1}{3} - \frac{1}{2} = \frac{1}{6}

Each squared coordinate difference has mean $1/6$ . Multiply by $d$ from the bridge above:

E [∥ X - Y ∥^{2}] = d \cdot \frac{1}{6} = \frac{d}{6}

So the expected squared distance grows linearly with $d$ . The expected distance grows like $d /6$ , which keeps getting larger as $d$ increases.

That's the mean. But the mean alone doesn't tell us whether all pairs of points sit close to it or whether they spread out around it. To know that, we need the variance.

Now the variance of $(U - V)^{2}$ . From the detour, $Var [X] = E [X^{2}] - (E [X])^{2}$ . Apply that with $X = (U - V)^{2}$ :

Var [(U - V)^{2}] = E [(U - V)^{4}] - (E [(U - V)^{2}])^{2}

The squared piece is just $(1/6)^{2} = 1/36$ , since we already have $E [(U - V)^{2}] = 1/6$ .

For the fourth moment, the same expand-and-take-expectations strategy from before applies. Expand $(U - V)^{4}$ :

(U - V)^{4} = U^{4} - 4 U^{3} V + 6 U^{2} V^{2} - 4 U V^{3} + V^{4}

Take expectations term by term. By independence every cross-term factors into a product of expectations. The single-variable moments for a uniform on $[0, 1]$ are $E [U^{k}] = \int_{0}^{1} u^{k} d u = 1/ (k + 1)$ , so $E [U^{2}] = 1/3$ , $E [U^{3}] = 1/4$ , $E [U^{4}] = 1/5$ (and the same for $V$ by symmetry). Plug in:

E [(U - V)^{4}] = \frac{1}{5} - 4 \cdot \frac{1}{4} \cdot \frac{1}{2} + 6 \cdot \frac{1}{3} \cdot \frac{1}{3} - 4 \cdot \frac{1}{2} \cdot \frac{1}{4} + \frac{1}{5} = \frac{2}{5} - 1 + \frac{2}{3} = \frac{1}{15}

Putting the two pieces together:

Var [(U - V)^{2}] = \frac{1}{15} - \frac{1}{36} = \frac{7}{180}

For independent random variables (which our coordinate differences are, by construction), variance is additive: $Var [A + B] = Var [A] + Var [B]$ . (The cross-term in $Var [A + B]$ vanishes when $A$ and $B$ are independent.) Combined with identical distribution, the $d$ -term sum collapses the same way the mean did:

Var [∥ X - Y ∥^{2}] = d \cdot \frac{7}{180}

And the standard deviation is:

sd [∥ X - Y ∥^{2}] = \frac{7 d}{180}

Now the interesting ratio. Divide the standard deviation by the mean:

CV = \frac{7 d /180}{d /6} = \frac{6 7/180}{d} = \frac{7/5}{d} \approx \frac{1.183}{d}

This is the coefficient of variation ( $CV$ ) of the squared distance. It tells you how big a typical fluctuation is, measured in units of the mean. As $d$ grows, the $CV$ shrinks like $1/ d$ . Concretely:

Dimension $d$	$E [∥ X - Y ∥^{2}]$	$sd [∥ X - Y ∥^{2}]$	$CV$
1	0.167	0.197	1.183
2	0.333	0.279	0.837
3	0.500	0.342	0.683
10	1.667	0.624	0.374
100	16.67	1.972	0.118
768	128.0	5.465	0.043
10000	1666.7	19.72	0.012

The same effect, plotted: the distribution of squared distances normalised so the mean sits at 1. At low d the curve is a wide bump; bumping d up a couple of orders of magnitude collapses it into a near-spike. The clipping at the top of the chart for large d is the visual signature of the concentration.

dimension d2

density of normalised squared distance, mean fixed at 1 (log-scaled slider, d ranges 1 → 1000)

In 1D, the standard deviation is bigger than the mean. Distances are wildly variable. A pair of random points might be very close or very far apart, with no particular preference.

In 100D, the standard deviation is about 12% of the mean. Most random pairs sit within about 12% of the average squared distance.

In 768D, the standard deviation is 4% of the mean. Almost every pair has nearly the same squared distance.

In 10000D, it's 1%. The whole distribution of pairwise distances has collapsed into a tight band.

In short, for anyone who skipped the algebra: this is the law of large numbers wearing a geometric hat. Squared distance is a sum of $d$ independent contributions, one per coordinate. Adding more dimensions means more terms in the sum, and as you sum more independent random terms, the total settles closer to its expected value in relative terms. The typical distance grows, and the absolute spread between different pairs' distances grows too, but slower: the spread as a fraction of the typical distance shrinks as $1/ d$ . By 768 dimensions, that fraction is around 4%, and every pair of random points sits at almost the same distance from every other. That is the curse of dimensionality, derived from first principles.

What this means for the algorithm

In 768 dimensions, take a query point and a million random database points. Compute the distance from the query to each. The numbers all come out around $128 \approx 11.3$ , with a spread of about 2%. The closest of the million is around 11.0 from the query. The farthest is around 11.6. The "nearest neighbor" is about 5% closer than the "farthest neighbor", out of a million candidates.

When everything is roughly equidistant, "nearest" stops being a useful concept. And exact algorithms that rely on geometric pruning lose their grip.

Recall how the kd-tree pruning works. At each node, you compare the splitting hyperplane's distance from Q against your current best distance. If the hyperplane is farther, you skip the other subtree. If closer, you descend.

In 2D with real spread in distances, your current best might be 0.1 while a hyperplane sits 0.3 away. You skip cleanly. Pruning fires.

In 768D, your current best is around 11.0, because that's roughly what every point's distance to Q is. The hyperplanes inside your unit cube are all closer than 11.0 to a typical query, because the cube's "size" along any axis is just 1, much smaller than the typical pair distance. Every hyperplane is closer than your best. Pruning never fires. You descend every branch of the tree. Linear scan with bookkeeping overhead.

This is not a kd-tree-specific problem. Every exact nearest-neighbor structure that relies on geometric separation, ball trees, R-trees, cover trees, locality-sensitive hashing in its provable forms, hits the same wall. The space itself stops carrying useful information about which points are closer than which. No partitioning scheme can extract progress from a uniform distribution of distances.

Why this matters in practice

The natural objection is: who cares about random points in [0, 1]^d? Real data isn't random. And that's correct. The curse as derived above applies to data that's uniformly random in the full ambient dimension. Real embedding vectors aren't.

A 768-dimensional sentence embedding doesn't fill the 768D space. It sits on a much lower-dimensional manifold inside it. The model that produced the embedding was trained to place semantically related sentences near each other and unrelated ones far apart, which means the data is structured, not random. The intrinsic dimension of the data, whatever it actually is, is much lower than 768. This is what makes nearest-neighbor search meaningful at all on real embeddings: the relevant variation lives in a small number of effective dimensions, and distances along those directions still discriminate.

But the engineering still has to fight the curse. Indexes that assume nice geometry in the ambient space, like kd-trees do when they prune based on coordinate-aligned hyperplanes, get fooled by the high ambient dimensionality even when the underlying data is intrinsically low-dimensional. The pruning bound is computed in the full 768D space, where the bound is too weak to be useful, even if the data only varies along 30 directions.

So we need algorithms that don't rely on partitioning the ambient space. And we typically also accept approximation, because exact answers in high dimensions are too expensive to be worth chasing when "close to closest" is good enough for the application.

That's where the field of approximate nearest neighbor search begins, and that's what the next article in this series picks up.