R4.4 · LESSON 4 OF 6

Binary representations

Calculate vector-code storage and distinguish scalar, product and binary quantization from reranking.

THE IDEA

Binary representations

The most aggressive option keeps one bit per coordinate (its sign). Comparing two codes is a cheap Hamming distance, the number of positions that differ: between 1010 and 1111 it is 2. A 768-bit code takes 96 bytes. But signs discard magnitudes, so the geometry changes and rankings can disagree with the float version.

Click bits to flip them.

differing positions: 2, 4 Hamming distance = 2 768 bits = 96 bytes = 32× smaller than float32

query [0.9,0.1] (bits 11) A = [1,-0.01] (bits 10) float score 0.899 Hamming 1 B = [0.2,0.3] (bits 11) float score 0.21 Hamming 0 floats rank A first; bits rank B first: signs discard magnitudes, so the geometry differs

Flip bits, then compare float and binary rankings on a small example.

Predict first. What is the Hamming distance between 1010 and 1111?

Chapter context

Compressed vectors reduce storage and memory bandwidth, but approximate distance calculations can change rankings. Separate the compressed search representation from any original vectors retained for a later accurate rerank.

TRY IT YOURSELF

Part 1. Do it hands-on

Binarize and compare by hand, then write the code and find a case where binary and float rankings disagree.

Click bits to flip them.

differing positions: 2, 4 Hamming distance = 2 768 bits = 96 bytes = 32× smaller than float32

sign bits of [0.5, −0.2, 0.1, −0.9] Hamming(1010, 1111) bytes for 768 bits same ranking as floats always? (yes/no)

To do: Binarize [0.5, −0.2, 0.1, −0.9] by sign (1 if positive, else 0). Type the four bits
To do: Hamming distance between 1010 and 1111 (the number of positions that differ)?
To do: A 768-bit code occupies how many bytes?
To do: Is the ranking by Hamming distance of sign bits always the same as the ranking by the original float distance? Type yes or no

Part 2. Do it in code

binarize(v): 1 for a positive coordinate, otherwise 0.
hamming(a, b): the number of positions that differ; different lengths raise ValueError.
rank_hamming(q_bits, codes): indices nearest first (ties: lower index).
rank_float(q, docs): indices by dot product, highest first (ties: lower index).
rankings_agree(q, docs): True if rank_float and rank_hamming (on the binarized query and documents) give exactly the same order.
bit_bytes(n_bits): ceil(n_bits / 8).

import math

def binarize(v):
    pass

def hamming(a, b):
    pass

def rank_hamming(q_bits, codes):
    pass

def rank_float(q, docs):
    pass

def rankings_agree(q, docs):
    pass

def bit_bytes(n_bits):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

What is the Hamming distance between 1010 and 1111?

AOne; only the first position matters.BTwo; the codes differ in positions 2 and 4.CFour; every position differs.

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

For d float32 coordinates, raw vector bytes are 4d. For M PQ subspaces and b bits per subspace, code bytes are $Mb/8$ when packed. For equal-size subspaces, float32 codebooks total $2^b d\times4$ bytes, excluding additional index data.

Worked example

A 768D float32 vector uses 768×4=3072 bytes. With 96 subspaces and 8-bit codes it uses 96 bytes: 32 times smaller for the per-vector representation. The shared codebooks contain 256×768 float32 values, requiring 786,432 bytes. Original vectors retained for reranking are an additional cost.

Reference code

The following example uses the Python standard library and does not call a remote service.

dimension,parts,bits=768,96,8
raw=dimension*4
code=parts*bits//8
book=(2**bits)*dimension*4
assert raw == 3072 and code == 96
assert raw/code == 32
assert book == 786432
assert sum(a!=b for a,b in zip('1010','1111')) == 2

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Compression ratio for code bytes is not the total-system ratio. PQ codes are indices into learned representatives, not simply truncated float bits. Reranking cannot find missing candidates.