Understand what binary quantization is, how it works and its benefits. This guide also covers the math behind the quantization and examples.

Introduction

Building the Bit Vectors

Find a Representative Centroid

1 Bit, 1 Bit Only Please

The Catch

The Query

Estimated Distance

Re-ranking

Conclusion

Quantization allows for vectors to be encoded in a lossy manner, thus reducing fidelity slightly with huge space savings.

What are the benefits of binary quantization?

Binary quantization takes each vector and transforms it relative to a prototypical set of sample vectors creating a smaller representation that can be used to approximate distances at great space and computation savings.

How does binary quantization work?

Binary quantization does not really create codebooks and instead compresses each data vector down to a 1 bit representation that is the inclusion in a region around a centroid.  The authors of the ![RaBitQ paper](https://arxiv.org/pdf/2405.12497), that is a large driver for our understanding and implementation of binary quantization, mention how the codebooks in PQ are related to the regions around any given centroid so if it's more intuitive to think of these regions as codebooks then yes.

Does binary quantization create codebooks similar to PQ?

Binary quantization relies on finding regions first.  Query vectors similarly are transformed into this space using the same centroid that allowed transformation into the region that was used to quantize the data vectors.  This is what allows the distance estimation comparison to happen.

Are the query vectors converted to 1 bit prior to comparison with the codebook / regions created from the data vectors?

Yes, if the number of vectors justifies it.  Although, even for millions of vectors, we have found that only one centroid is sufficient for many datasets and models.

Are there multiple centroids?

No, since very few centroids are required they can be maintained in their float32 form without concern for scaling.

Are the centroids converted to a 1 bit representation as well?

We've found so far that we can reduce complexity, both algorithmically and performance-wise, by removing this random transformation.  While some vectors may be favored, traditionally reranking a reasonable set of data, which is required to achieve reasonable recall, seems to negate the need for this in practice.

The author's of the ![RaBitQ paper](https://arxiv.org/pdf/2405.12497) mention transforming the data with a random orthogonal matrix P why do you not include it here?

We've found so far that a single centroid for most production datasets works well.  Additionally when talking about how binary quantization works we can focus on a single centroid at a time.  As you have more vectors, >100m, you may find that recall is impacted.  When using Elasticsearch these large datasets can be pre-partitioned and multiple centroids will naturally be used.

The author's of the ![RaBitQ paper](https://arxiv.org/pdf/2405.12497) mention using multiple centroids but you focus on a single centroid here.  Why only one centroid?

Author

John Wagster

Articles

Better Binary Quantization 101