Diagnosing dense-retrieval hubness with a 2010 distance-concentration result, and porting a cross-lingual correction into retrieval

Dense retrieval was filling its top results with items similar to each other while the document that answered the query sank below them. On a dense 50-row table, embedding retrieval fell to 17% recall@10 where plain lexical search scored 100% on the same table. There were regions where the dense leg was worse than keyword matching.

The usual response is to bolt on a reranker. But a reranker only reorders a candidate list that already exists, so whatever kept the right document out of that list is still there afterwards.

Tried first and rejected

Before the fix, three intuitive alternatives were tried and all three were rejected on measurement. The rejection criteria were written down before the experiment, together with the commit hash at the time of registration, so that it can be checked afterwards that the bar was not lowered once the results were in.

The rejected approaches are on a do-not-re-propose list, so the same wrong answer does not get proposed twice.

Diagnosis

Looking again at the symptom, the items crowding the top had something in common. They were not close to the query in particular; they were close to many queries at once.

That is not a property of retrieval but of high-dimensional space. A 2010 JMLR paper on distance concentration describes exactly this: as dimensionality rises the distribution of pairwise distances narrows, and some points end up as the nearest neighbour of many others. Those hubs rank highly regardless of the query.

A fix borrowed from another field

One field has been dealing with the same hub problem for years: cross-lingual word embeddings. Aligning two languages’ embedding spaces produces hub words in exactly this way, and the correction used there is CSLS (Cross-domain Similarity Local Scaling). It subtracts how close a point is to its neighbourhood on average, which separates “close because it is popular” from “close to this query”.

That was ported into the retrieval seeding stage. Below is the single-document result, six cases averaged over three runs.

Condition	recall@10
Lexical only	85.2
Dense seeding, before	77.5
Dense seeding with CSLS	97.0

The order in which those are read matters. What changed is dense seeding, so the two values to compare are 77.5 and 97.0. And the fact that dense seeding scored below lexical search before the change is itself the symptom of the hub problem. The gain comes entirely from the dense-table cases: a uniform 50-row table goes 22 to 100, a real 32-row table 50 to 100. The prose cases are unchanged.

The direction holds in the harder setting too, where 263 entities are merged into one workspace so the right answer competes against all of them.

Metric	Before	After
Multi-document recall@10	75.8	96.0
End-to-end answer accuracy (31 questions)	87%	97%

No additional API spend. CSLS is arithmetic over embeddings that already exist, so no extra call is made. A reranker would have added a per-query cost in exactly this position.

Re-measured at 300× the scale

Those results come from about 300 entities. Once workspaces with 100,000 entities showed up in real use, everything in between became an empirical gap, so a 100,000-label corpus was built and the measurement repeated. The corpus takes 23,859 real extracted labels as its core, fills distractor mass with wiki titles and company names, and injects 300 controlled clusters with known targets. The query set is 350, fixed and stratified.

Three things came out of it.

The small-scale result reproduced, but not entirely. At a top-10 cutoff CSLS won significantly at every scale and the gain grew with scale. At a top-40 cutoff it lost significantly. Broken out by stratum, the loss came from exactly one: when the target is itself a member of a dense series, CSLS demotes the whole cluster and pushed the target from a median rank of 21 to 854. At top 10 that costs nothing, but the product consumes down to about 40, so it is a real loss.

The repair was ten lines. The top candidate by raw cosine similarity is now guaranteed one seed slot regardless of CSLS demotion. That recovers more than half of the losing stratum while preserving every gain elsewhere, and the top-40 cutoff becomes statistically indistinguishable from the pre-port behaviour.

Making the estimate more accurate makes it worse. An oracle arm computing neighbourhood density exactly, over all pairs rather than a sample, was consistently worse than the sampled arm (46.9% against 38.9%). Sampling misses true nearest neighbours and so under-estimates density, and that bias happens to soften the demotion. Improving estimation fidelity is a regression in this system, not an improvement, and the sample size is now pinned in the code with a comment saying so.

Recording an ambiguity in the pre-registration

The scale validation had pre-registered decision criteria, and those criteria did not pin down whether the metric was seed-stage or final ranking. Under the seed-stage reading the original implementation was significantly negative overall; under the final-ranking reading it passes at top 10 and fails at top 40.

The deciding metric was settled as the one the product actually consumes — and the document records that this was settled after the results were seen. The value of pre-registration lies in fixing the criteria, not in claiming they were fixed.

Why this was adopted

A metric going up is not sufficient grounds. This was adopted because the cause is explained: the observed failure (hubs occupying the top), the diagnosis (distance concentration), the intervention (hub correction) and the result (recall rising) form one causal chain, and each step was confirmed separately. An improvement whose cause cannot be explained offers no basis for predicting whether it survives the next run.

Limits

• CSLS’s neighbourhood size was tuned on this corpus. There is no evidence that the same value is optimal on a corpus with a different distribution.
• recall@10 rising does not lift final answer quality proportionally, which is why end-to-end was measured separately and reported above.
• The improvement is confined to the retrieval seeding stage. Failure modes after ranking are a separate problem.
• One case the floor does not rescue remains: targets sitting between second and eighth by raw cosine. Widening the floor trades that against letting clusters occupy the top again.
• The scale validation goes to 100,000. Nothing above 200,000 is measured, and re-tuning the cap means re-running this harness.

Reference

Radovanović, Nanopoulos, Ivanović, Hubs in Space: Popular Nearest Neighbors in High-Dimensional Data, JMLR 11 (2010).

Measurement record

Item	Value
First measurement	28 June 2026, about 300 entities, six cases averaged over three runs with re-extraction each run
Scale validation	16 July 2026, 100,000 labels with no missing embedding, 350 queries, 41 real graphs merged (109,471 nodes, 101,812 entities)
Embeddings	google/gemini-embedding-2, 3,072 dimensions, OpenRouter, batches of 96 — the production path
Harness	flooding_fix_ab for the first run, src-tauri/src/tagging/csls_scale_eval.rs for the scale run; both #[ignore] live tests
Arms	The production functions lexical_seeds, semantic_seeds and personalized_pagerank called directly, not an eval copy
Statistics	Same queries across all arms, bootstrap 95% CI on recall deltas (10k resamples), McNemar discordance counts, per-stratum decomposition
API cost	About $2.60 for the scale validation ($0.095 of augmentation embeddings plus query generation and embedding)

The 1.4 GB of raw scale-validation data was deleted on 16 July 2026, and the numbers above are the aggregate of it. The regeneration scripts remain in the repository under docs/csls-scale-eval/, run in the order prep_corpus, pick_targets, embed_labels, gen_queries.

Bit-for-bit reproduction is not possible. The corpus depends on the application database’s labels and embeddings as they stood that day, on the wiki dump’s latest tag, and on LLM query generation above temperature zero. A re-run re-validates the same direction on a new corpus rather than recovering the same numbers. Sampling also depends on hash-map iteration order, which moves semantic recall by a few points between runs; the paired deltas and confidence intervals the decision rested on were stable across that jitter.

The primary records are docs/details/graphrag-seeding-csls.md and docs/details/csls-scale-eval-2026-07.md in the Consilience repository.