Support for Binary Quantization

[nileshtrivedi]

Would love to see this capability in pgvector: https://qdrant.tech/articles/binary-quantization/

Essentially, BQ converts any vector embedding of floating point numbers into a vector of binary or boolean values.

In exchange for reducing our 32 bit embeddings to 1 bit embeddings we can see up to a 40x retrieval speed up gain!

One of the reasons vector search still works with such a high compression rate is that these large vectors are over-parameterized for retrieval. This is because they are designed for ranking, clustering, and similar use cases, which typically need more information encoded in the vector.

[jkatz]

This is just another form of product quantization -- it could be interesting, but requires testing. The biggest tradeoff (as mentioned in the article) is the impact to recall, which requires searching over a larger space to get a better representative set of the approximated results. There's also testing to see how this would work given how PostgreSQL stores data on disk, as the benefit would be towards minimizing the number of pages loaded into memory during an index scan, which is not necessarily correlated to vector size.

[ankane]

Hey @nileshtrivedi, thanks for sharing! I'm not sure it's common enough to include at this point, but seems like it'd be simpler to implement and use than scalar or product quantization, so may try it out in a branch.

[aamir-s18]

@ankane I think this will be become really relevant in the future. Cohere is providing binary embeddings out of the box. We are working on a novel form of binary quantization. I think this could work well with #429.

[ankane]

Support is now available in the bitvector branch for anyone who wants to try it (in a non-production environment).

CREATE TABLE items (id bigserial PRIMARY KEY, embedding vector(3));
INSERT INTO items (embedding) VALUES ('[1,-2,3]'), ('[-4,5,-6]');
CREATE INDEX ON items USING hnsw ((quantize_binary(embedding)::bit(3)) bit_hamming_ops);

-- no re-ranking
SELECT id FROM items ORDER BY quantize_binary(embedding)::bit(3) <~> quantize_binary('[1,-2,3]') LIMIT 5;

-- re-ranking
SELECT id FROM (
    SELECT * FROM items ORDER BY quantize_binary(embedding)::bit(3) <~> quantize_binary('[1,-2,3]') LIMIT 20
) ORDER BY embedding <=> '[1,-2,3]' LIMIT 5;

[ankane]

You can also store binary embeddings directly.

CREATE TABLE items (id bigserial PRIMARY KEY, embedding bit(3));
INSERT INTO items (embedding) VALUES (B'000'), (B'111');
CREATE INDEX ON items USING hnsw (embedding bit_hamming_ops);
SELECT * FROM items ORDER BY embedding <~> B'101' LIMIT 5;

[ankane]

Support for binary quantization been merged (94a444f) and will be included in 0.7.0 (#508). Thanks for the suggestion @nileshtrivedi!

[nileshtrivedi]

@ankane Thanks! This looks great. 👏

With the vector type (instead of say vector(3)), I am able to store vectors of different dimensions in the same column.

To get the same flexibility, can/should I store binary embeddings in a column of type bytea?

[ankane]

You can use bit varying / varbit.