R4.3 · LESSON 3 OF 6

Codebooks and lookup tables

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

THE IDEA

Codebooks and lookup tables

To score a compressed candidate you do not need to decode it. For each query, precompute a lookup table: the distance from every query subvector to every codebook entry. A candidate's approximate distance is then the sum of m table entries chosen by its code: 96 additions of lookups instead of 768 coordinate operations.

Query (1, 1 | 5, 4). The table holds the squared distance from each half of the query to every codebook entry. It is built once per query.

subspace	entry 0	entry 1	entry 2
0	2	0	2
1	41	1	-

score of [1, 1] = table[0][1] = 0 + table[1][1] = 1 = 1 smaller is closer; ranking: [1,1]=1 < [0,1]=3 < [2,0]=43 for a real 768-d index each candidate costs 96 lookups instead of 768 coordinate operations; the table has 96 × 256 = 24,576 numbers

The codebooks (96 × 256 × 8 floats = 786,432 bytes) are shared metadata: small next to millions of codes, but part of the memory you must account for.

Pick a candidate and watch its score being assembled from the table.

Predict first. Are codebooks part of memory use?

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

Score codes from a table by hand, then write the table builder and the scorer.

Query (1, 1 | 5, 4). The table holds the squared distance from each half of the query to every codebook entry. It is built once per query.

subspace	entry 0	entry 1	entry 2
0	2	0	2
1	41	1	-

The codebooks (96 × 256 × 8 floats = 786,432 bytes) are shared metadata: small next to millions of codes, but part of the memory you must account for.

table numbers (96 × 256) score of [0, 1] best candidate codebooks count toward memory? (yes/no)

To do: For a query, a lookup table holds one distance to every codebook entry: 96 subspaces × 256 entries = ? numbers
To do: Toy codebooks: subspace 0 has entries (0,0), (1,1), (2,2); subspace 1 has (0,0), (5,5). Query (1,1 | 5,4). Squared distances in subspace 0: 2, 0, 2; in subspace 1: 41, 1. Score (sum of table entries) of the code [0, 1]?
To do: Candidates [1,1], [0,1] and [2,0]: which has the smallest score? Type it like 1,1
To do: Do the shared codebooks count toward memory use? Type yes or no

Part 2. Do it in code

build_table(query, codebooks): for every subspace j and entry k the squared L2 distance between the query's j-th subvector and that entry; table[j][k].
adc_score(table, code): the sum over subspaces of table[j][code[j]] (a smaller sum is closer).
rank_codes(table, codes): indices of the candidate codes, best (smallest score) first; ties: lower index.
table_entries(m, k): the number of numbers in the table.
ops_per_candidate(m, dim, use_table): additions needed to score one candidate: m lookups with the table, dim coordinate differences without it.
total_memory(n, m, bits, codebook_bytes): n codes of m·bits/8 bytes (rounded up) plus the shared codebooks.

import math

def build_table(query, codebooks):
    pass

def adc_score(table, code):
    pass

def rank_codes(table, codes):
    pass

def table_entries(m, k):
    pass

def ops_per_candidate(m, dim, use_table):
    pass

def total_memory(n, m, bits, codebook_bytes):
    pass

Ctrl/⌘ + Enter runs it

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

CHECK YOUR UNDERSTANDING

Are codebooks part of memory use?

AYesBNo

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.