Quantization: trading memory for recall

Vectors are stored as float32 by default: four bytes per dimension. At 768 dimensions that’s about 3 KB per vector, and ten million of them is over 30 GB before any index structure.

Quantization is the family of techniques for storing them in less space. All of them work by throwing information away. The interesting part is which information, and why the results survive it better than you’d expect.

The naive approach

Store every component as a full-precision float. Exact, simple, and the memory cost is vectors × dimensions × 4 bytes.

How it fails: it doesn’t fit. Past some collection size you either buy more RAM, shard across more machines, or serve from disk — and serving a graph index from disk is a non-starter because traversal needs random access at memory speed.

So: can we store the vectors in less space and still rank them correctly?

The observation that makes this possible

We don’t need exact distances. We need the right ordering of the top few results.

That’s a much weaker requirement. If every distance is off by a small amount but the errors are roughly unbiased, the ranking mostly survives — especially at the top, where the genuinely-close vectors are separated from the rest by a margin larger than the noise.

And there’s a second, stronger idea: use approximate distances to get a candidate list, then compute exact distances for just those candidates and re-sort. Now the compression only has to be good enough to get the right answers into the shortlist, not to rank them. This is reranking, and it’s what makes aggressive quantization practical.

Scalar quantization

The simplest version: use fewer bits per component.

Find the range of values each dimension takes across the collection, then map that range onto a smaller integer type. For int8:

quantize(x, min, max):
    return round( (x − min) / (max − min) × 255 ) − 128

dequantize(q, min, max):
    return (q + 128) / 255 × (max − min) + min

Four bytes becomes one. 4× memory reduction.

What’s discarded: precision within each dimension. A component’s true value is replaced by the nearest of 256 levels. The error per component is bounded by half a level, and across many dimensions those errors partially cancel — which is why the damage is far less than “we deleted 75% of the bits” suggests.

Where it hurts: dimensions with outliers. If one dimension mostly sits in [−0.1, 0.1] but has a few values at 8.0, the range is dominated by the outliers and the 256 levels are spread across territory almost nothing occupies. Effective precision for the typical case collapses. Implementations often handle this by clipping percentiles rather than using the true min and max.

float16 deserves mention as the conservative option: 2× reduction, and for most text embeddings the recall cost is very small, because float16 still carries more precision than the underlying signal meaningfully has. It’s the easiest win available and often the right first step.

Product quantization

The more powerful technique, and the one with the interesting idea.

Split the vector into chunks, and replace each chunk with a reference to one of a small set of learned representative chunks.

Concretely, for a 768-dimensional vector split into 96 sub-vectors of 8 dimensions each:

1. Train. For each of the 96 sub-vector positions independently, run k-means over that slice of the training data to learn 256 representative sub-vectors. That’s a codebook per position.
2. Encode. For a new vector, split it into 96 slices. For each slice, find the nearest entry in that position’s codebook. Store its index — one byte, since there are 256 entries.
3. Result. The vector is now 96 bytes instead of 3,072. 32× reduction.

The reason this beats scalar quantization at the same bit budget: the codebook entries are placed where the data actually is. K-means puts representatives in dense regions and spends nothing on empty space. Scalar quantization spreads its levels uniformly across a range regardless of where the data sits.

Computing distances without decompressing. The mechanism that makes PQ fast at query time is worth seeing. Given a query, for each of the 96 positions, precompute the distance from the query’s slice to all 256 codebook entries in that position. That’s a small lookup table — 96 × 256 entries, computed once per query.

Then the approximate distance to any stored vector is a sum of 96 table lookups:

approx_distance(query_tables, code):
    return Σ over positions p of query_tables[p][code[p]]

No decompression, no floating-point multiplication per dimension — just table lookups and additions. This is called an asymmetric distance computation, because the query stays full-precision while the stored vectors are compressed. Keeping the query exact matters: quantizing both sides would add error twice for no memory benefit, since there’s only ever one query in flight.

What’s discarded: the true position within each sub-space, replaced by the nearest of 256 centroids. Also all correlation between sub-vectors — each slice is quantized independently, so structure spanning slice boundaries is lost. Some implementations mitigate this by applying a learned rotation first, redistributing information more evenly across the slices.

The parameters: number of sub-vectors (more means finer, larger codes, better recall) and bits per code (usually 8). Both trade memory against accuracy directly.

Binary quantization

The extreme: one bit per dimension. Store the sign, discard the magnitude.

encode(v):  return [1 if vᵢ > 0 else 0 for vᵢ in v]

768 dimensions becomes 96 bytes — the same size as the PQ example, and vastly cheaper to compute with. Distance between two binary codes is Hamming distance: XOR the two bit strings and count the set bits. That’s a couple of CPU instructions per 64 dimensions.

32× memory reduction and distance computation an order of magnitude cheaper.

What’s discarded: everything except the sign pattern. This is a lot, and whether it works depends heavily on the embedding model. Some models produce representations where the sign pattern carries most of the discriminative signal and binary quantization performs surprisingly well; others degrade severely. There’s no way to know but to test on your own data against a known query set.

Binary quantization is almost always paired with reranking, because it’s most useful as a very fast first-stage filter.

Reranking, which is the point

Here’s why aggressive compression is viable at all.

search(query, k):
    candidates ← approximate_search(query, k × oversample)   # compressed, fast
    exact      ← full_precision_distance(query, c) for c in candidates
    return top k of candidates by exact

Retrieve more candidates than you need using compressed vectors, then compute exact distances for just those and re-sort.

The compressed representation only has to get the right answers into the candidate list. Ordering them is the exact stage’s job. Since the candidate list is small — a few hundred at most — the exact stage is cheap even though it needs full-precision vectors.

That last point is the catch: reranking requires the full-precision vectors to be available somewhere. Usually on disk or in a separate store, fetched for the candidates only. This is fine — it’s a small number of random reads rather than a traversal — but it means quantization reduces your memory footprint, not your total storage. If you discarded the originals, you can’t rerank.

The oversampling factor is the knob: more candidates means better final recall and more exact distance computations. It’s a runtime parameter, so it’s cheap to tune.

Choosing

Technique	Reduction	Discards	Notes
float16	2×	Low-order precision	Easiest win, usually near-free
Scalar (int8)	4×	Within-dimension precision	Sensitive to outliers
Product (PQ)	8–64×	Sub-space position, cross-slice correlation	Needs training; the workhorse
Binary	32×	Everything but sign	Model-dependent; needs reranking

A reasonable progression: start at float32. If memory gets tight, try float16 — it’s a small change with a small cost. If that isn’t enough, scalar quantization. Past that, PQ, usually combined with a cluster index as IVF-PQ, which is the standard configuration for very large collections.

Always measure recall before and after against a fixed query set with known-good results. Every technique here has a recall cost, the cost is entirely dependent on your embedding distribution, and published figures from other datasets do not transfer. A compression that’s free on one model can be ruinous on another.

Quantization is one of three ways to move along the same trade-off surface — the other two are the index parameters. The recall-latency curve is where they all meet.