Distance Concentration and Hubness in Embedding Spaces

Retrieval systems that work acceptably on a few dozen dimensions often behave strangely when the vectors are 512 or 768 wide. The nearest neighbours of a query are barely nearer than its farthest points, and a small set of vectors appears in the result list for almost every query. Both effects are properties of high-dimensional geometry rather than bugs in the index, and both can be predicted from a few counts.

The ratio, not the distance, is what collapses

Consider points drawn independently from a distribution with bounded support, and compare the distance from a query to its nearest neighbour with the distance to its farthest. In one dimension, with points spread over an interval, the nearest point is typically much closer than the farthest. As the dimension grows, the two distances converge in relative terms: the difference between the maximum and minimum distance shrinks faster than the distances themselves, so the ratio of nearest to farthest approaches one.

The precise statement depends on the distribution. For independent and identically distributed coordinates with finite moments, the variance of the squared distances grows linearly in the dimension while the mean also grows linearly, so the coefficient of variation of the distance distribution falls as the inverse square root of the dimension. The absolute spread of distances still increases, but the relative spread goes to zero. A query at the centre of a high-dimensional ball finds its nearest neighbour only marginally closer than a point at the edge, and the notion of “close” loses contrast.

The practical threshold is not a fixed dimension. What matters is the ratio of the intrinsic dimension of the data to the number of points available. If a dataset of a thousand points lives on a manifold that is effectively ten-dimensional, distances remain informative; if the same thousand points are spread through five hundred dimensions, the contrast is gone. This is why dimensionality reduction before indexing sometimes improves recall rather than costing it.

Learned embeddings are not independent Gaussian noise, and the concentration argument does not apply to them unmodified. Training pushes points into clusters and spreads them to satisfy a loss, which restores contrast along the directions the objective cares about. But the residual dimensions that the objective left unconstrained behave like noise, and they contribute variance to every distance without contributing discrimination. An embedding of width 768 trained on a task with a few hundred effective degrees of freedom is mostly noise dimensions from the point of view of a downstream nearest-neighbour query.

Why some vectors become hubs

The second effect is asymmetric and does not follow from concentration alone. In a set of points with a distance measure, some points appear among the nearest neighbours of many other points far more often than their share of the data would suggest. These are hubs. Their existence was documented for high-dimensional Euclidean and cosine spaces, and it grows with dimension.

import numpy as np

def hubness(X, k=10):
    # X: n x d, rows are unit-normalized embeddings
    sims = X @ X.T
    np.fill_diagonal(sims, -np.inf)
    nn = np.argsort(-sims, axis=1)[:, :k]
    counts = np.bincount(nn.ravel(), minlength=len(X))
    return counts          # counts[i] = how many points list i as a neighbour

A vector’s hubness score is the number of other points for which it is among the top k. Under a uniform distribution over a sphere, the scores are roughly balanced. Under any distribution with a dense centre and a sparse periphery, points near the centre of the cloud are close to everything and accumulate high scores, while peripheral points are close to almost nothing. The skew is a geometric consequence of the density profile, not of the specific data.

Learned spaces develop the same profile for a second reason. A vector that sits in a region where many training examples were similar, such as a generic function word in a language model or a common category prototype in a classifier’s penultimate layer, is genuinely close to many things. Its high score is correct in the sense that the distances are small. The problem is that it carries little information: returning it for a query says only that the query is unremarkable.

Hubness interacts badly with the usual evaluation. Recall at k computed over a query set that is itself drawn from the same distribution will be dominated by the hub region, so a system can score well while being uninformative on the queries that matter. Comparing two embedding spaces by average precision can also favour the space with a more concentrated density, because concentrated spaces have more high-scoring neighbours that happen to be correct.

Cosine similarity hides magnitude, and that is a choice

Most embedding comparisons use cosine similarity, which is the dot product of unit-normalized vectors. Normalization removes the norm, so a vector’s length carries no information in the comparison, and two vectors pointing in nearly the same direction are similar regardless of how far from the origin they sit.

The alternative, raw inner product, lets magnitude participate. If training encouraged frequent items to have larger norms, inner product retrieval favours them, which is sometimes exactly the desired ranking and sometimes a bias to be removed. Matrix factorization with a dot-product objective tends to inflate the norms of popular items because a large norm helps satisfy many pairwise constraints at once, and this is a documented source of popularity bias in recommendation.

Cosine similarity has a geometric quirk of its own. For vectors with non-negative entries, all similarities are non-negative, and the effective range of the measure is compressed into a narrow band. The angle between two independent non-negative vectors of dimension d concentrates near 90 degrees with a spread that shrinks as d grows, so two unrelated vectors of moderate width have a cosine near zero with a narrow distribution, and the interesting variation occupies a small interval. Thresholds chosen on a small sample do not transfer.

Centring the vectors before comparison removes a shared mean direction that would otherwise dominate every dot product. A set of embeddings whose mean is far from the origin has a large common component, and subtracting it changes the ranking of neighbours substantially. Whether to centre is a decision about what “similar” means, not a numerical detail.

What the index actually has to do

Approximate nearest-neighbour structures rely on the contrast that concentration destroys. A tree that partitions space by coordinate medians prunes a branch when the query’s distance to the splitting plane exceeds the current best candidate distance; when all distances are nearly equal, the pruning condition rarely holds and the search degenerates toward scanning. Hashing methods that map similar vectors to the same bucket rely on a gap between the similarity of near pairs and far pairs; when the gap narrows, either the bucket count rises or recall falls.

Graph-based indexes tolerate this better because they navigate by local structure rather than by a global distance threshold, but they inherit the hub problem. A hub node is connected to many others and is traversed constantly, which is efficient; a peripheral node may be reachable only through a long path, which is where recall failures concentrate. The usual mitigation is to build the graph with a diversity criterion that rejects neighbours too close to already-selected ones, which deliberately reduces the hub’s degree.

Dimension reduction before indexing is the blunt instrument. Random projection preserves pairwise distances up to a distortion that depends on the target dimension and the number of points, so projecting from 768 to 128 dimensions can retain most of the ranking while cutting distance computations by a factor of six. The projection must be applied consistently to queries and to the index, and the reduced space must be re-evaluated rather than assumed equivalent.

Quantization is the other lever. Product quantization splits a vector into subvectors and encodes each with a codebook index, so a 768-dimensional float vector becomes a few dozen bytes. The approximation error adds noise to every distance, which worsens contrast; the usual response is to retrieve a larger candidate set with the quantized distances and rescore the candidates with exact distances.

Symptoms that point at geometry rather than at code

A retrieval system whose top result is correct for many queries but whose second through tenth results are near-duplicates of the first is showing hub behaviour. One whose results are plausible for common queries and arbitrary for rare ones is showing the density profile of the training data. One whose recall falls sharply as the candidate set grows is showing the loss of contrast that makes pruning useless.

These are not fixed by tuning k or switching the index. They are fixed, when they can be fixed at all, by changing the space: normalizing or centring, reducing dimension, or training the embedding with an objective that explicitly rewards spread. That last option is the subject of Alignment and Uniformity as Separate Objectives, and the contrastive objectives that shape the space in the first place are covered in InfoNCE and the Temperature Parameter.