apache / apache/lucene

For 4-bit quantized vectors, should we change the scheme of unpacking nibbles?

Open
#15,697 8 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

4-bit quantized vectors are stored as nibbles, two packed in a single byte -- where the "upper" half bits in the byte contain the first `N / 2` dimensions, and the "lower" half bits contain the remaining ones.

Example: `[1 5][2 6][3 7][4 8]`

For performing individual vector computations, we "unpack" the nibbles into a `byte[]` -- [where we take the second nibble from each byte and place it at the end](https://github.com/apache/lucene/blob/448c7d8e2414eaae43b68cc398fcb3e2191b4132/lucene/core/src/java/org/apache/lucene/codecs/lucene104/OffHeapScalarQuantizedVectorValues.java#L188-L194)

Example: `[1][2][3][4][5][6][7][8]`

Now for individual dot-product computations b/w a packed and unpacked vector: we [read the first byte of the packed vector (dimensions 1, 5) and multiply individual nibbles against byte number 1 and 5 of the unpacked vector](https://github.com/apache/lucene/blob/448c7d8e2414eaae43b68cc398fcb3e2191b4132/lucene/core/src/java/org/apache/lucene/internal/vectorization/DefaultVectorUtilSupport.java#L171-L182).

For higher dimension vectors, can this lead to CPU cache line misses?
If so, can we "unpack" the nibbles in dimension order for performance gains?

Contributor guide

Open the contributing guide

Research direction

Start with OffHeapScalarQuantizedVectorValues.java and DefaultVectorUtilSupport.java, focusing on the linked unpacking and dot-product code. Measure whether the current layout causes cache-line misses for higher-dimensional vectors, then compare it with dimension-order unpacking; done means a supported performance conclusion and an agreed implementation direction.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
performance
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.