Hubness in High-Dimensional Retrieval

\(N_k(x)\) is the number of points that have \(x\) among their \(k\) nearest neighbours.

In low dimensions the distribution is roughly symmetric. As dimensionality rises it becomes strongly right-skewed: a few hubs appear in a disproportionate share of neighbour lists, while many anti-hubs appear in none (Radovanović et al., JMLR 2010).

Crucially this emerges even in i.i.d. random data with no structure, so it is a property of the geometry, not of your embedder or your chunking.

Concentration of distances. In high dimensions the distances from a query to all data points cluster around a similar value, so rankings are decided by small deviations rather than large gaps.

Points sitting slightly closer to the data mean than average are marginally closer to everything. Because the top-k decision rests on those tiny margins, the same points win repeatedly across unrelated queries.

Anisotropy makes it worse: learned embeddings occupy a narrow cone rather than the full sphere, raising effective concentration above the i.i.d. baseline.

Because they are invisible. A hub shows up as an irrelevant document appearing in results, which someone notices and reports. An anti-hub is a document that is nobody's nearest neighbour, so it is effectively absent from the index and never appears at all.

Aggregate recall metrics do not reveal it, since the queries whose answers are anti-hubs are a small fraction of any test set. It surfaces instead as "the system never finds our policy documents", a complaint with no failing test behind it.

Corpus centring: subtract the mean embedding before search, removing the common component that pulls hubs toward everything. Two lines, but it invalidates thresholds tuned on raw cosine values.

Mutual proximity / mutual-kNN rescoring: replace raw similarity with whether two points are each other's neighbours, stripping one-sided popularity. Cheap on a shortlist; changes score semantics.

Cross-encoder reranking: scores pairs jointly rather than by shared-space geometry, so it does not inherit hubness at all. Most effective, most expensive.

Hybrid retrieval also helps, since BM25 has no metric space and therefore no hubs.

Both show up as the same documents dominating results, but the diagnosis differs. Compute the k-occurrence distribution over the index: hubness is a long right tail with a few documents at ten or twenty times the mean, spread across unrelated queries.

Duplicates instead show up as tight clusters of near-identical vectors that co-occur in results for related queries.

Check duplicates first, because deduplication is far cheaper than any geometric correction and fixes a large share of apparent hub reports.

Lower dimensionality does reduce distance concentration, so it reduces hubness. But an uninformed reduction (random projection, an untrained PCA cut) discards discriminative information, and you trade hub pollution for outright recall loss with no guarantee the net is positive.

Matryoshka truncation is safer, because the model was trained so that dimension prefixes remain usable representations, which decouples the dimensionality cut from information loss.

Measure recall at k before and after; the geometry argument alone does not tell you which effect wins.

\(N_k(x)\) is the number of points that have \(x\) among their \(k\) nearest neighbours.

In low dimensions the distribution is roughly symmetric. As dimensionality rises it becomes strongly right-skewed: a few hubs appear in a disproportionate share of neighbour lists, while many anti-hubs appear in none (Radovanović et al., JMLR 2010).

Crucially this emerges even in i.i.d. random data with no structure, so it is a property of the geometry, not of your embedder or your chunking.

Concentration of distances. In high dimensions the distances from a query to all data points cluster around a similar value, so rankings are decided by small deviations rather than large gaps.

Points sitting slightly closer to the data mean than average are marginally closer to everything. Because the top-k decision rests on those tiny margins, the same points win repeatedly across unrelated queries.

Anisotropy makes it worse: learned embeddings occupy a narrow cone rather than the full sphere, raising effective concentration above the i.i.d. baseline.

Because they are invisible. A hub shows up as an irrelevant document appearing in results, which someone notices and reports. An anti-hub is a document that is nobody's nearest neighbour, so it is effectively absent from the index and never appears at all.

Aggregate recall metrics do not reveal it, since the queries whose answers are anti-hubs are a small fraction of any test set. It surfaces instead as "the system never finds our policy documents", a complaint with no failing test behind it.

Corpus centring: subtract the mean embedding before search, removing the common component that pulls hubs toward everything. Two lines, but it invalidates thresholds tuned on raw cosine values.

Mutual proximity / mutual-kNN rescoring: replace raw similarity with whether two points are each other's neighbours, stripping one-sided popularity. Cheap on a shortlist; changes score semantics.

Cross-encoder reranking: scores pairs jointly rather than by shared-space geometry, so it does not inherit hubness at all. Most effective, most expensive.

Hybrid retrieval also helps, since BM25 has no metric space and therefore no hubs.

Both show up as the same documents dominating results, but the diagnosis differs. Compute the k-occurrence distribution over the index: hubness is a long right tail with a few documents at ten or twenty times the mean, spread across unrelated queries.

Duplicates instead show up as tight clusters of near-identical vectors that co-occur in results for related queries.

Check duplicates first, because deduplication is far cheaper than any geometric correction and fixes a large share of apparent hub reports.

Lower dimensionality does reduce distance concentration, so it reduces hubness. But an uninformed reduction (random projection, an untrained PCA cut) discards discriminative information, and you trade hub pollution for outright recall loss with no guarantee the net is positive.

Matryoshka truncation is safer, because the model was trained so that dimension prefixes remain usable representations, which decouples the dimensionality cut from information loss.

Measure recall at k before and after; the geometry argument alone does not tell you which effect wins.