apache / apache/lucene

Short-circuit HNSW search for similarity-based vector queries?

Open
#15,869 0 comments 0 reactions 0 assignees View on GitHub
type:enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.