krickert opened a new pull request, #15800:
URL: https://github.com/apache/lucene/pull/15800

   ### Problem
   With the recent introduction of `LateInteractionField` and the rise of 
multi-vector models (e.g., ColBERT), a single document is often represented as 
$N$ independent vectors in the HNSW graph. Standard search treats these as $N$ 
unique targets, leading to significant CPU waste. If a document has thousands 
of chunks and one chunk is already securely in the Top-K, standard Lucene 
continues to score and traverse the remaining chunks.
   
   ### Solution
   This PR introduces a **Document-Aware Traversal** mechanism. By leveraging 
the existing `ordToDoc` mapping, we allow the `KnnCollector` to signal whether 
a document is already \"satisfied\" before the searcher performs expensive 
vector scoring or neighbor exploration.
   
   Key changes:
   1. **`KnnCollector#shouldScore(ordinal)`**: A new hook in the collector 
interface (defaults to `true`).
   2. **`HnswGraphSearcher` Hook**: The searcher now checks `shouldScore` 
before scoring a node and adding its neighbors to the frontier.
   3. **`DistinctDocKnnCollector`**: A new collector implementation that tracks 
unique DocIDs and prunes redundant chunks once a document hits the competitive 
threshold.
   
   ### Results
   In a multi-vector scenario (20 documents with 3,000 chunks each), this 
optimization achieved a **57% reduction in node visits** with **zero loss in 
recall** (Recall Parity with standard HNSW). On larger real-world graphs, the 
reduction in CPU cycles is expected to be even more substantial as the 
redundant chunk scoring is eliminated at the traversal layer.
   
   ### Trade-offs
   * **Opt-in only**: Behaviors for standard 1-vector-per-doc search remain 
unchanged.
   * **Recall Parity**: This is a pure optimization; it does not change which 
documents are returned, only how fast they are found.


-- 
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]

Reply via email to