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?

Better Binary Quantization 101: An Introduction

Better Binary Quantization 101

Here's how to add passage vectors to Lucene, the benefits of doing so and how existing Lucene structures can be used to create an efficient retrieval experience.

The (kNN) problem with parents and children

Pre-joining to the rescue

Lucene vector search: Adding passage vector search to Lucene

Adding passage vector search to Lucene

Elasticsearch is out-of-the-box 2x–12x faster than OpenSearch for vector search

Up to 12x faster out-of-the-box

Exact KNN and Approximate KNN

Testing methodology

Detailed findings

Tasks

Vector engines

Vector types

Out-of-the-box and Concurrent Segment Search

2.5 million vectors, 1536 dimensions (openai_vector)

Recall

10 million vectors, 96 dimensions (dense_vector)

2 million vectors, 768 dimensions (so_vector)

Elasticsearch and Lucene as clear victors

Elasticsearch vs. OpenSearch: Vector Search Performance Comparison

This blog explains how int4 quantization works in Lucene, how it lines up, and the benefits of using int4 quantization.

Introduction to Int4 quantization in Lucene

How does `Int4` quantization work in Lucene

Storing and scoring the quantized vectors

Calculating the quantization error correction

Finding the optimal bucketing for int4 quantization

Speed vs. size for quantization

Speed part 2: more SIMD in int4

The end?

Int4 provides additional compression options. It reduces the quantization space to only 16 possible values (0 through 15).

What is Int4 quantization in Lucene?

Understanding Int4 scalar quantization in Lucene

Discover how modern Java features, including vectorization and FFI/madvise, are speeding up Lucene's performance.

Foreign memory

Foreign function

Vectorization

Lucene & Java: How vectorization & FFI/madvise speed up Lucene

Making Lucene faster with vectorization and FFI/madvise

Explore multi-graph vector search in Lucene and discover how sharing information between segment searches enhances search speed.

The previous state of multi-graph vector search in Lucene

Speeding up multi-graph vector search by sharing information between segment searches

Impact on performance

Impact on recall

Lucene vector search: Speeding up multi-graph vector search

Speeding Up Multi-graph Vector Search

Learn how to optimize vector distance computations using the Foreign Function & Memory (FFM) API to achieve faster performance.

Current state of play: The Panama Vector API

Introducing the Foreign Function & Memory (FFM) API

FFM usage example

Going foreign

Back in Java-land

Performance improvements with FFM API

Summary

Optimizing vector distance computations with the FFM API

Optimizing vector distance computations with the Foreign Function & Memory (FFM) API

2023 has been another big year for Apache Lucene, this blog reviews major milestones of 2023

Community

Vector search

Radix sort everywhere

Faster query evaluation

Closer integration with the Java virtual machine

What happened in Lucene land in 2023?

Lucene 9.9 brings major speedups to query evaluation. Here are the performance improvements observed in nightly benchmarks & optimization resources.

Key speedup benchmarks in Lucene

Lucene optimization resources

Lucene 9.9: Optimizations, performance & benchmarks insights

Apache Lucene 9.9, the fastest Lucene release ever

How we optimized vector comparisons in BBQ with hardware accelerated SIMD (Single Instruction Multiple Data) instructions.

Lucene

Smokin' fast BBQ with hardware accelerated SIMD instructions