goankur opened a new issue, #16903: URL: https://github.com/apache/lucene/issues/16903
### Description With an asymmetric encoding such as `SINGLE_BIT_QUERY_NIBBLE`, a merge writes a temporary file of query-side records (4-bit) next to the index-side codes (1-bit). The graph merge scores with `AsymmetricQuantizedRandomVectorScorerSupplier`, whose `setScoringOrdinal(node)` reads that node's query record (`Lucene104ScalarQuantizedVectorScorer`, lines 173-175 on main). The read for the node being inserted is fine: it happens once per node, in order (`HnswGraphBuilder`, lines 394 and 400). But the diversity checks call `setScoringOrdinal` on other nodes: - on every candidate for the new node's neighbors (`HnswGraphBuilder`, line 515) - on each neighbor whose list overflows, and on each node in that list (`NeighborArray`, lines 141 and 301) Those are random reads of the query-record file, several per insertion. At 4 bits against 1 bit, a query record is about 4x the size of a code. So the random-access working set of the merge grows from the codes alone to about 5x that. When the codes fit in RAM but the query records do not, the merge thrashes the page cache. ### What we saw On Amazon internal 4K dim embeddings, with the 1-bit format from #16902, merges into segments of over a hundred million vectors had a query-record file larger than the RAM of the box. The graph phase stalled on major faults in that file and used 17 of 64 cores. As a prototype, we scored the diversity checks code against code (1-bit x 1-bit, the symmetric form of the same estimate), so the query records are read only for the node being inserted. Both sides of each comparison then come from the same estimator. With that change: - the same merge used 44 of 64 cores; - on a smaller A/B, recall was the same at ef_search 100 to 700, with 0.4-0.9% more visited nodes per query. ### Proposal Use the symmetric code-to-code estimate for diversity checks in merges with asymmetric encodings, either always or as a format option. The searches during insertion keep the asymmetric score. Open questions: 1. Our prototype covers only `SINGLE_BIT_QUERY_NIBBLE`. `DIBIT_QUERY_NIBBLE` would need its own symmetric estimate. 2. Always on, or opt-in? It changes the graph a little, and we have seen no recall change so far. We are running the same A/B on a public float dataset (luceneutil Cohere-v3, 1024 dims), both with everything in RAM and under a memory limit that holds the codes but not the query records. We will post the results here. The prototype is ready for a PR once the direction is agreed. -- 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]
