R4.1 · LESSON 1 OF 6

Scalar quantization

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

THE IDEA

Scalar quantization

A float32 coordinate takes 4 bytes. Scalar quantization maps each coordinate to one of a few levels over a chosen range and stores only the level number. With 8 bits, a 768-dimensional vector shrinks from 3,072 to 768 bytes (4×). The price is rounding error (at most half a step inside the range) and clipping (everything outside the range is lost). Both change distances.

bits per coordinate4value x0.37

16 levels over [0, 1.5], step 0.1 x = 0.37 → code 4 → decodes to 0.4 error 0.03 768 dimensions at 4 bits = 384 bytes (float32: 3,072)

Orange: the original value. Green ring: what the code decodes to. In range, the error is at most half a step; outside it, clipping loses everything beyond the range. These errors change distances, so rankings can change too.

Move x and the number of bits; try a value outside the range.

Predict first. Does an eight-bit code reconstruct an arbitrary float32 coordinate exactly?

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

Quantize a value by hand, then write the quantizer and measure its error.

bits per coordinate4value x0.37

16 levels over [0, 1.5], step 0.1 x = 0.37 → code 4 → decodes to 0.4 error 0.03 768 dimensions at 4 bits = 384 bytes (float32: 3,072)

bytes for 768 dims at 8 bits times smaller than float32 4-bit code of 0.37 decode of clipped 2.0

To do: A 768-dimensional vector stored with one byte (8 bits) per coordinate takes how many bytes (ignoring the scale values)?
To do: Against float32 (3072 bytes), how many times smaller?
To do: 4-bit codes (16 levels) over the range 0 to 1.5 give a step of 0.1. Code for x = 0.37 (round to the nearest level)?
To do: The value x = 2.0 is outside that range and is clipped. What does it decode to?

Part 2. Do it in code

step(lo, hi, bits): the gap between neighbouring levels: (hi − lo) / (2**bits − 1). bits < 1 or hi <= lo raise ValueError.
quantize(x, lo, hi, bits): clip x to [lo, hi], then return the integer code of the nearest level: floor((x − lo) / step + 0.5), kept within 0 … 2**bits − 1.
dequantize(code, lo, hi, bits): lo + code · step.
roundtrip(xs, lo, hi, bits): the list of dequantized values after quantizing each x.
max_error(xs, lo, hi, bits): the largest absolute difference between a value and its round trip.
bytes_per_vector(dim, bits): ceil(dim · bits / 8).

import math

def step(lo, hi, bits):
    pass

def quantize(x, lo, hi, bits):
    pass

def dequantize(code, lo, hi, bits):
    pass

def roundtrip(xs, lo, hi, bits):
    pass

def max_error(xs, lo, hi, bits):
    pass

def bytes_per_vector(dim, bits):
    pass

Ctrl/⌘ + Enter runs it

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

CHECK YOUR UNDERSTANDING

Does an eight-bit code reconstruct an arbitrary float32 coordinate exactly?

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.