apache / apache/lucene

Explore more granular vector quantization?

Open
#15,734 6 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

Today, Lucene supports [8, 4, 2 and 1](https://github.com/apache/lucene/blob/e1879e450b75b3a58fde2b0dad77ae6b499504dd/lucene/core/src/java/org/apache/lucene/codecs/lucene104/Lucene104ScalarQuantizedVectorsFormat.java#L119-L148) bit quantization.

Each quantization level typically has an upper bound of recall with exact KNN that it can produce (which is "exact KNN with quantized scores" v/s "exact KNN with original scores", see https://github.com/mikemccand/luceneutil/issues/528) -- this is the information loss due to quantization itself (before approximate-ness from search algorithms like HNSW comes into picture).

Any algorithm operating on quantized scores _alone_ cannot go beyond this recall (e.g. tweaking parameters like `maxConn`, `beamWidth`, `fanout`, etc. for HNSW) without using the original scores from un-quantized vectors for re-ranking -- which may not be feasible for some use cases (e.g. keeping the index in-memory for performance, where using un-quantized vectors increases memory footprint by \~4x in case of byte-quantized vectors).

In such cases, I wonder if Lucene could support more granular quantization options (say _the equivalent of!_ 6-bit quantization) -- for more granular recall v/s memory requirements?

Contributor guide

Open the contributing guide

Research direction

Start with Lucene104ScalarQuantizedVectorsFormat.java, especially the current 8-, 4-, 2- and 1-bit quantization options, and review the linked exact-KNN discussion. Determine whether more granular quantization such as 6-bit is feasible, then define the recall, memory, and implementation criteria needed for a concrete design.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.