Hubness: the vectors that turn up in everyone's results

There is a phenomenon in high-dimensional nearest-neighbour search that is easy to observe, easy to misdiagnose, and follows from the geometry rather than from anything wrong with your data. A small number of vectors become the nearest neighbour of a wildly disproportionate share of queries. They are called hubs, and once you know to look for them you find them in almost every large embedding collection.

The naive assumption

Nearest-neighbour relationships feel like they ought to be roughly reciprocal and roughly evenly distributed. If you take a collection of N vectors and ask, for each one, which 10 are nearest, then across the whole collection there are 10N neighbour slots to fill. With N vectors competing for them, each vector ought to appear in about 10 lists. Some more, some fewer, a mild spread around 10.

How that fails: the distribution is not mildly spread. It is heavily skewed. A few vectors appear in thousands of lists, and a long tail of vectors — anti-hubs — appear in none at all, meaning they are nobody’s nearest neighbour and are effectively unreachable by neighbourhood-based reasoning. The mean is still 10, because the mean has to be, which is why an average tells you nothing here.

Where the skew comes from

The mechanism is a consequence of distance concentration, and it can be built up in three steps.

Step one: there is a centre, and it matters more than it should. Any finite point cloud has a mean. Distance to that mean varies across the collection: some vectors sit closer to the middle of the cloud, some further out.

Step two: in high dimensions, being slightly closer to the centre is a large advantage. As dimensionality rises, all pairwise distances concentrate into a narrow band relative to their magnitude. The differences between distances therefore become small. Against that background, a vector’s distance to the centre of the cloud is a systematic offset that applies to its distance to every query at once — and when the random variation between distances shrinks, a small systematic offset dominates the ranking. A vector nearer the centre is slightly nearer to everything, and slightly is enough.

Step three: winning slightly, everywhere, compounds. Because that advantage applies to all queries simultaneously rather than to a particular region, the central vectors accumulate appearances across the whole query space. The neighbour count distribution develops a long right tail. This effect grows with intrinsic dimensionality and it is present for the ordinary distance functions — Euclidean, cosine — not just for exotic ones.

The consequence to internalise is that the k-nearest-neighbour relation is not symmetric, and in high dimensions it is badly asymmetric. b being in a’s top-10 says surprisingly little about whether a is in b’s top-10. Every intuition built on two-dimensional pictures, where neighbourhood is approximately mutual, is unreliable here.

Two clarifications, because this idea is easy to overstate. Hubness is a property of the geometry plus the data distribution, not a defect in the embedding model, and it appears in collections whose embeddings are perfectly good. And it is distinct from the low-contrast case where a corpus is genuinely homogeneous: hubness produces a skewed distribution of neighbour counts, whereas a homogeneous corpus produces uniformly indistinguishable scores. They can co-occur and they are not the same thing.

What hubs do to a graph index

Here is why this belongs in a discussion of internals rather than of embeddings.

A graph index is built out of exactly this relation. Each node’s edge list holds its nearest neighbours, and search is a walk over those edges. If the relation is asymmetric and skewed, so is the graph.

Hubs become high-degree nodes with strong pull. A hub appears in many nodes’ candidate lists during construction, so many nodes link to it. Its in-degree is enormous. Every walk that passes anywhere near it gets drawn towards it, because the greedy step follows whichever neighbour is closest and a hub is close to nearly everything.

This is not purely bad, and that’s worth saying. High-degree, centrally located nodes are excellent transit points. They are the long-range edges of a small-world graph arising for free from the data, and they are why a proximity graph is navigable at all — a walk can reach the general vicinity of anywhere in a few hops through the hubs. Some graph designs choose entry points because of centrality, for exactly this reason.

Anti-hubs are the real problem. A vector that is nobody’s nearest neighbour receives no incoming edges from the natural construction. It is in the graph, its own out-edges point at other nodes, and nothing points back. A node with no in-edges is unreachable by traversal. It will never be returned, no matter how large you set search breadth, because breadth widens the frontier of nodes you can reach and this node is not among them. It is, for practical purposes, absent from the index while occupying memory in it.

This is one concrete source of the recall floor a graph index can’t tune its way out of, and it explains a confusing symptom: a specific document that never appears in results even for a query that is nearly a copy of it. Not a scoring problem, not a filter problem — a connectivity problem.

The pruning heuristic is the main defence, and now you can see why it exists. When a node’s edge list overflows, a naive implementation keeps the closest M neighbours. A good implementation instead prefers neighbours that open directions no existing neighbour covers, even at slightly greater distance. Under hubness the naive rule is actively harmful: every node’s list fills up with the same handful of hubs, because the hubs really are the closest, and the graph collapses into a star with poor local structure and many unreachable nodes. The diversity-based pruning rule rejects a hub that is already represented by an existing edge in that direction, preserving links to ordinary nodes and, with them, reachability. Diversified pruning is a hubness countermeasure, whether or not it is described that way.

Reverse edges are the other defence. Some constructions explicitly add, for each node, edges back from the neighbours it selected — making the relation symmetric by force. This directly addresses the anti-hub problem: a node with no natural in-edges acquires them from the nodes it chose. It costs degree, and degree costs memory and per-hop work, which is one of the reasons connectivity settings have a floor below which recall falls off a cliff rather than degrading smoothly.

What it does to a cluster index

Less, and for a structural reason: a cluster index never uses the k-NN relation. Assignment is to the nearest centroid, and every vector has one, so nothing can become unreachable. Probe the right cell and the anti-hub is scanned along with everything else.

There is a milder version of the effect. Hubs sit near the centre of the point cloud, so they cluster into the densest cells, and those cells are probed by a large fraction of queries. The result is uneven probe load: a minority of partitions carry most of the scanning work. That has consequences for how a partitioned collection balances, and it is a load-distribution property rather than a correctness one.

Observing it

The measurement is straightforward and needs only exact search on a sample.

1. Take a sample of vectors from the collection, or better, a sample of real queries.
2. Compute exact top-k for each by brute force.
3. Count, for every vector in the collection, how many of those result lists it appears in.
4. Look at the distribution — not the mean, which is fixed by construction.

What you are looking for is the shape of the tail and the size of the zero bin. A long right tail says hubs exist. A large zero bin says a meaningful share of your collection is nobody’s neighbour, and those vectors are the ones a graph index is most likely to lose entirely.

Two follow-ups that are worth the effort:

• Compare the hub set against your top results overall. If the same few documents appear across unrelated queries, they are hubs and their appearance carries little information about relevance.
• Check whether the hubs are semantically generic. Boilerplate, template text, mixed-topic documents and near-empty chunks all tend to land near the centre of the cloud, which makes them hubs by geometry. When that’s the cause, the remedy is upstream — remove the boilerplate — rather than in the index. When the hubs are ordinary documents that simply happen to be central, the remedy is the graph’s construction rules.