R4.2 · LESSON 2 OF 6

Product quantization

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

THE IDEA

Product quantization

Product quantization (PQ) splits a vector into m subvectors and learns a small codebook (say 256 representative subvectors) for each position. A vector is stored as m small indices. With 96 subspaces and one byte per code, a 768-d vector costs 96 bytes: 32× smaller. The codebooks are shared by all vectors, so they are a fixed cost.

Toy product quantizer: a 4-dimensional vector is split into two halves; each half is replaced by the index of its nearest codebook entry.

coordinate 10.9coordinate 21.2coordinate 34coordinate 46

subspace	subvector	codebook	chosen entry
0	(0.9, 1.2)	0: (0,0) 1: (1,1) 2: (2,2)	1 → (1, 1)
1	(4, 6)	0: (0,0) 1: (5,5)	1 → (5, 5)

stored code: [1, 1] instead of 4 floats reconstruction: [1, 1, 5, 5] squared error 2.05

subspaces for a 768-d vector96

8 dimensions per subvector; with 256 entries each, code = 96 bytes (32× smaller than 3,072) codebooks: 96 × 256 × 8 × 4 = 786,432 bytes (shared by every vector)

Encode a toy vector; then change the number of subspaces for a 768-d vector.

Predict first. With 96 subspaces and one byte per code, how long is one vector's code?

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

Size a product quantizer by hand, then write split, encode and decode.

Toy product quantizer: a 4-dimensional vector is split into two halves; each half is replaced by the index of its nearest codebook entry.

coordinate 10.9coordinate 21.2coordinate 34coordinate 46

subspace	subvector	codebook	chosen entry
0	(0.9, 1.2)	0: (0,0) 1: (1,1) 2: (2,2)	1 → (1, 1)
1	(4, 6)	0: (0,0) 1: (5,5)	1 → (5, 5)

stored code: [1, 1] instead of 4 floats reconstruction: [1, 1, 5, 5] squared error 2.05

subspaces for a 768-d vector96

8 dimensions per subvector; with 256 entries each, code = 96 bytes (32× smaller than 3,072) codebooks: 96 × 256 × 8 × 4 = 786,432 bytes (shared by every vector)

dims per subvector (96 subspaces) code bytes times smaller codebook bytes

To do: A 768-dimensional vector is split into 96 equal subvectors. Dimensions per subvector?
To do: Each subvector is replaced by the index of one of 256 codebook entries (one byte). Length of one vector's code in bytes?
To do: Per-vector compression against float32 (3072 bytes)?
To do: Codebook storage: 96 subspaces × 256 entries × 8 floats × 4 bytes = ? bytes

Part 2. Do it in code

split(v, m): m equal consecutive subvectors; ValueError if len(v) is not divisible by m.
encode(v, codebooks): codebooks[j] is a list of centroid vectors for subspace j. For each subvector return the index of its nearest centroid (squared L2; ties: lower index).
decode(codes, codebooks): the concatenation of the chosen centroids.
reconstruction_error(v, codebooks): squared L2 distance between v and decode(encode(v)).
code_bytes(m, bits=8): bytes for one code: ceil(m · bits / 8).
compression_ratio(dim, m, bits=8, float_bytes=4): dim · float_bytes divided by code_bytes(m, bits).
codebook_bytes(m, k, sub_dim, float_bytes=4): m · k · sub_dim · float_bytes.

import math

def split(v, m):
    pass

def encode(v, codebooks):
    pass

def decode(codes, codebooks):
    pass

def reconstruction_error(v, codebooks):
    pass

def code_bytes(m, bits=8):
    pass

def compression_ratio(dim, m, bits=8, float_bytes=4):
    pass

def codebook_bytes(m, k, sub_dim, float_bytes=4):
    pass

Ctrl/⌘ + Enter runs it

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

CHECK YOUR UNDERSTANDING

With 96 subspaces and one byte per code, how long is one vector's code?

A96 bytes: one byte (an index into 256 entries) per subspace; the 256 is the codebook size, not the code length.B768 bytes, one byte per original coordinate.C256 bytes, one byte per codebook entry.

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.