Pranshu-S opened a new issue, #16817: URL: https://github.com/apache/lucene/issues/16817
### Description ## Problem In document-oriented vector search, multiple documents frequently carry identical embeddings. Today `Lucene99HnswVectorsFormat` assigns each duplicate vector its own graph node rather than merging or otherwise accounting for them. When duplicates are skewed (Zipf-distributed in my case), the hot copies form a sort of a sink where many edges point into the group, but the group has very few outgoing level-0 edges (only from selective nodes) to any other distinct-vector neighborhood. When the graph's single entry point happens to land inside or adjacent to such a sink, the greedy level-0 search descends into it and dead-ends after visiting only a few dozen nodes. The result in a pretty dramatic recall collapse as shown below. ## Evidence ### Dataset generation I generated the dataset in two ways: 1. **Uniform duplication:** every one of the 1,000 distinct vectors is repeated exactly 10 times to reach 10,000 documents, so no vector is more common than any other. 2. **Skewed (Zipf) duplication:** the repeat counts follow a Zipf distribution (exponent s = 1.0): a few vectors are copied an large number of times — the hottest one appears in 1,336 of the 10,000 documents — while a long tail of vectors appears only once or a handful of times. Both datasets drew from the same 1,000 distinct source vectors; they differ only in how the duplicates are distributed. ### Recall Metrics To correctly identify the behaviour of the graph, I defined two different forms of recall. - Distinct Recall@10 — Returned docs (rank order) are mapped back to the distinct vector they carry, deduplicated, and the first 10 distinct vectors are compared against ground truth (the 10 closest distinct embeddings, brute-forced over the 1,000 unique vectors). I collect 500 results here and then run the distinct check. - Tie-aware Document Recall@10 — Of the 10 highest-ranked docs, how many are legitimately in the exact top-10? Since identical vectors score identically, a doc is credited when its score ≥ the exact 10th-place score. This avoids penalizing a "different but equally-correct" duplicate. ### Results The two data-sets behaved very differently: 1. With uniform duplication, distinct Recall@10 stayed near-perfect, averaging about 0.99 (0.9899 at maxConn 16 and 0.9921 at maxConn 32), and it was extremely stable — across all ten builds it stayed within a tight 0.9886–0.9934 range. 2. With skewed (Zipf) duplication, distinct Recall@10 collapsed to roughly 0.29–0.41 on average (mean 0.4082 at maxConn 16 and 0.2913 at maxConn 32) and swung wildly from build to build (individual builds ranged from 0.0073 to 0.6325). | Workload | Distinct R@10 | Document R@10 (tie-aware) | | --- | --- | --- | | Deduplicated | 1.0000 ± 0.0000 | 1.0000 ± 0.0000 | | Uniform duplicates | 0.9899 ± 0.0015 | 0.9973 ± 0.0006 | | **Skewed duplicates** | **0.4082 ± 0.2416** | **0.3089 ± 0.1921** | | All-unique (ref) | 1.0000 ± 0.0001 | 1.0000 ± 0.0001 | ### Possible Explanation? My hunch is that when many identical vectors are indexed, Lucene gives each one its own graph node — it does not merge them into a shared node. Because all these copies sit at distance zero from one another, the resulting structure is a **largely isolated subgraph with hub-and-spoke connectivity.** In one of the build which I tried inspecting, most of the hot group's level-0 outgoing edges all remain within the duplicate group, leaving very few directed level-0 path from those nodes to any distinct-vector group. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
