Short-circuit HNSW search for similarity-based vector queries?
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
### Description
Spinoff from #15836
A KNN query [short-circuits the HNSW search](https://github.com/apache/lucene/blob/83e3f9ac24ac282ae353d0e0566f64640fe919a3/lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99HnswVectorsReader.java#L345) if the "expected" number of nodes visited is >= number of filtered nodes.
A similarity-based vector query (i.e. `[Byte|Float]VectorSimilarityQuery`) attempts to find _all_ vectors with a score above a threshold (for Euclidean similarity, this can be imagined as all vectors within a radius of the query vector).
Assuming document vectors are evenly spread out across the n-dimensional space, should vector similarity scores form a normal distribution?
If so, can we estimate the proportion of nodes visited using area under the curve (from `resultSimilarity` -> `∞`) of a normal distribution? (and apply the same short circuit logic)
Contributor guide
Research direction
Start with the HNSW short-circuit logic in Lucene99HnswVectorsReader.java and compare it with ByteVectorSimilarityQuery and FloatVectorSimilarityQuery. Determine whether similarity scores support estimating the visited-node proportion from a normal distribution, and document whether applying equivalent short-circuiting is valid.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- backend, performance, search
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Needs clarification
- Newbie friendliness
- 35/100