Vector search - Quantization

Part 3 ended with two ways to make HNSW fit at billion-vector scale: shrink the vectors so they take a fraction of their raw size, or push them to disk and read them on demand. The on-disk article worked through pushing them to disk. This one works through shrinking them.

The technique is called quantization: replace each high-precision number with a lower-precision approximation, store the approximation, and accept a small loss of fidelity in exchange for a large reduction in size and compute. The same idea recurs across machine learning, audio codecs, image compression, and large language model weights, with different details every time. This article works through the two flavours that matter for vector search: scalar quantization, which compresses each number independently, and product quantization, which groups numbers into short chunks and compresses the chunks against a small dictionary of learned prototypes.

Scalar quantization is the simpler of the two and a good warm-up. Product quantization (PQ) is where most of the depth lives, because it is what every modern billion-scale vector index uses to drive memory and bandwidth costs down by one or two orders of magnitude. We'll spend most of the article on it.

Scalar quantization

The simplest form of compression: take each high-precision number and replace it with a lower-precision approximation, one value at a time. Three formats appear over and over.

float16 halves the cost of a float32 value (4 bytes down to 2) while keeping a similar dynamic range. Modern hardware does float16 arithmetic at the same throughput as float32 in its SIMD units (Single Instruction Multiple Data, the CPU and GPU mode that processes several numbers per instruction in parallel), so both speed and accuracy survive the swap. This is what GPUs use by default for inference.
int8 stores each value as a single signed byte: one of the 256 integer values from $- 128$ to $127$ . The mapping from float to integer needs a scaling factor. Take the largest absolute value in some unit (one vector, one matrix row, one block of weights), call it $M$ , and store $s = M /127$ alongside the encoded data. Each float $x$ is then encoded as the integer $round (x / s)$ , clamped to $[- 127, 127]$ . Decoding multiplies back: $x \approx q \cdot s$ . Worked example: a vector whose largest absolute value is $0.85$ produces $s \approx 0.0067$ , and the float $0.42$ encodes as $round (0.42/0.0067) = 63$ . Decoding gives $63 \cdot 0.0067 \approx 0.422$ , off by about $0.002$ from the original. The compression ratio is $4 \times$ over float32, and the recall loss in vector search (the fraction of true nearest neighbours that the compressed search misses) is typically around 1%.
int4 stores each value in 4 bits, half a byte. Used mostly for aggressive LLM weight compression. Compression doubles to $8 \times$ over float32, at the cost of more careful calibration to keep the loss tolerable.

Scalar quantization is a single pass over the data and easy to reason about. It is usually the first technique to reach for. For vector search at billion scale, the savings are real but not enough on their own: a 768-dimensional float32 embedding is 3 KB, and shrinking it to about 750 bytes with int8 still leaves a billion vectors taking 750 GB. Squeezing the per-vector cost down to a few percent of its raw size needs the next technique.

Product quantization

Product quantization (PQ) is the technique that makes 32× to 96× compression workable for high-dimensional vectors. It was published by Hervé Jégou, Matthijs Douze, and Cordelia Schmid in 2010, originally for image retrieval, and it's still the workhorse of every billion-scale vector search system.

The construction

Start with a single 768-dimensional vector $v$ . Split it into 96 contiguous chunks of 8 dimensions each: dimensions 1 through 8 form the first chunk, dimensions 9 through 16 the second, and so on through 96. Each chunk is itself a vector, but in a much smaller space (8 dimensions instead of 768). It lives in its own 8-dimensional subspace.

Now do this same split for every vector in the dataset. The dataset has $N$ database vectors (a billion in our running example), and every one of them contributes exactly one chunk to each subspace: vector $v$ 's dimensions 1-8 join subspace 1, its dimensions 9-16 join subspace 2, and so on. Subspace 1 ends up holding $N$ chunks, all of them 8-dimensional, one chunk per database vector. The same is true for every other subspace.

PQ compresses each subspace independently with exactly the same procedure. We'll describe what happens inside one subspace; the full PQ runs the procedure 96 times in parallel, once per subspace, with no interaction between them.

Memory in one subspace. Each chunk is an 8-dimensional vector, which means 8 float32 numbers. At 4 bytes per float, one chunk takes $8 \times 4 = 32$ bytes. With $N$ chunks in this subspace, the raw storage cost is $N \times 32$ bytes, the count of chunks times the size of one chunk. (Across all 96 subspaces this multiplies up to $96 \times 32 \times N = 3072 N$ bytes, which is exactly the raw cost of the original 768-dimensional vectors.)

The goal is to shrink the per-subspace memory from $32 N$ bytes (raw chunks) to something much smaller.

The trick. Pick 256 "representative" 8-dimensional vectors that approximate the dataset's chunks. Then replace each of the $N$ chunks with whichever representative is closest to it in Euclidean distance, throwing away the chunk's exact coordinates. After the replacement, every chunk in the compressed dataset is one of those 256 representatives, no matter how diverse the original chunks were. This is lossy: a chunk that was at, say, position $(1.2, 3.4, \dots)$ is now stored as "the representative at position $(1.0, 3.5, \dots)$ ", with a small approximation error baked in. The compressed form of a chunk is just the integer index of its assigned representative.

How much memory this saves. Step through the arithmetic:

There are 256 representatives, so each one is identified by an integer between 0 and 255. That integer fits in 8 bits, or 1 byte, because $2^{8} = 256$ .
Each chunk is now stored as that 1-byte index. With $N$ chunks in this subspace, the indices total $N \times 1 = N$ bytes.
The 256 representatives themselves still have to be stored somewhere, otherwise the indices are meaningless. Each representative is an 8-dimensional float32 vector, taking $8 \times 4 = 32$ bytes. Storing all 256 of them takes $256 \times 32 = 8, 192$ bytes, about 8 KB.
Total storage for this subspace is $N$ bytes (indices) plus 8 KB (the 256 representatives), versus the raw $32 N$ bytes.

For $N$ in the millions or billions, the 8 KB constant is negligible and the compression ratio approaches $32 \times$ .

The 256 representatives are called centroids, the geometric word for "average point of a group" (think of a centroid as the cluster's balance point if its members were equal weights). They are produced by an algorithm called $k$ -means clustering (the $k$ in the name is the number of clusters; here $k = 256$ ).

The objective. We need to pick the 256 representatives well. The natural goal is to minimise the total error introduced by replacing each chunk with its assigned representative. Quantify error as squared Euclidean distance and sum across all chunks:

error (c_{1}, \dots, c_{256}) = x \sum ∥ x - c_{nearest (x)} ∥^{2}

where the sum is over all $N$ chunks $x$ , and each chunk is assigned to whichever of the 256 representatives is closest to it. Lower error means the representatives are doing a better job of standing in for the chunks.

Two optimality facts about this error. They are the engine of the algorithm.

The first fact is almost too obvious to state. If the 256 representative positions are fixed, the best assignment is "each chunk to its closest representative." Suppose chunk $x$ is at distance 1 from representative $A$ and distance 5 from representative $B$ . Assigning $x$ to $A$ contributes $1^{2} = 1$ to the total error; assigning it to $B$ contributes $5^{2} = 25$ . Picking the closer one always gives a smaller error contribution, no matter which other chunks exist. So whenever we know the representative positions, the assignment is forced: it has to be "every chunk to its nearest representative."

The second fact takes a moment to absorb but is just as concrete. Given a cluster of chunks (any group of chunks all sharing a representative), the single point that minimises the sum of squared distances to all of them is their arithmetic mean. Take a 1-dimensional toy: three numbers ${2, 5, 8}$ , whose mean is $5$ . From the mean, the sum of squared distances is $3^{2} + 0^{2} + 3^{2} = 18$ . Try other candidates: from $4$ it would be $2^{2} + 1^{2} + 4^{2} = 21$ ; from $6$ it would be $4^{2} + 1^{2} + 2^{2} = 21$ ; from $3$ , $1^{2} + 2^{2} + 5^{2} = 30$ . Anywhere off the mean is worse. The same holds in 8 dimensions, and in fact in any number of dimensions, coordinate by coordinate:

c^{*} = \frac{1}{n} i = 1 \sum n p_{i}

is the unique point minimising the cluster's total squared error. So whenever we know which chunks are assigned to a cluster, the cluster's best representative position is forced too: it must be the mean of the cluster's chunks.

Why we can't solve this in one shot. The assignment step is one-shot in a precise sense: given the 256 representative positions, a single pass over the data places every chunk in its cluster. The trouble is, we don't know the right positions to begin with. The positions are exactly what we are trying to solve for, jointly with the assignment.

Could we enumerate every possible way of grouping the $N$ chunks into 256 clusters, and pick whichever grouping leads to the lowest error (with each cluster's optimal representative position computed as the cluster's mean)? In principle yes, in practice no. Each of the $N$ chunks can land in any of 256 clusters independently, so the total number of possible assignments is $25 6^{N}$ .

$N$ (chunks)	Total possible assignments $25 6^{N}$
10	$\approx 1.2 \times 1 0^{24}$
50	$\approx 1.5 \times 1 0^{120}$
1,000,000,000	a number with several billion digits

By comparison, the number of atoms in the observable universe is roughly $1 0^{80}$ . So even the demo's tiny dataset of 50 points has more possible assignments than every computer cluster on the planet could enumerate before the heat death of the universe. The full billion-vector case is in a different category of impossible.

Putting the two facts together: $k$ -means. Each fact lets us improve one half of the answer once the other half is held fixed:

If we know the current representative positions, fact 1 hands us the best assignment (each chunk to its nearest representative). The total error goes down or stays the same.
If we know the current assignment, fact 2 hands us the best representative positions (each one the mean of its assigned chunks). The total error goes down or stays the same again.

The $k$ -means algorithm is what you get when you alternate these two updates:

Initial positions. Start with 256 representative positions somewhere. The simplest choice is 256 chunks picked at random from the dataset.
Assignment step. For every chunk, compute its distance to each of the 256 current representatives, and assign the chunk to the closest one. The chunks are now sorted into 256 groups.
Update step. For each group, compute the average of its chunks (coordinate by coordinate). Move that group's representative to the average.
Repeat steps 2 and 3 until no chunk changes its assigned representative between one iteration and the next.

Each step either strictly reduces the total error or leaves it unchanged, and error can't go below zero, so the algorithm has to stop after a finite number of iterations. On real data, it stops after tens of iterations.

What $k$ -means actually costs. Each iteration is dominated by the assignment step: every chunk computes its distance to each of the 256 representatives. A distance in 8 dimensions takes about 16 floating-point operations (eight subtractions, eight squares, seven additions, plus a square root), so an assignment step costs about $N \times 256 \times 16 \approx 4, 000 N$ operations. The update step is a single pass over the chunks accumulating cluster means, roughly $8 N$ more operations. With around 20 iterations to convergence, the total cost is on the order of $80, 000 N$ operations.

Compare with the cost of enumeration:

$N$ (chunks)	Enumeration ( $25 6^{N}$ assignments)	$k$ -means ( $\approx 80, 000 N$ ops)
10	$\sim 1.2 \times 1 0^{24}$	$\sim 8 \times 1 0^{5}$
50	$\sim 1.5 \times 1 0^{120}$	$\sim 4 \times 1 0^{6}$
1,000,000,000	unimaginably large	$\sim 8 \times 1 0^{13}$

The shape of the difference is what matters: enumeration is exponential in $N$ (each extra chunk multiplies the cost by 256), while $k$ -means is linear in $N$ (each extra chunk adds a small constant). Even at a billion chunks, $k$ -means' $8 \times 1 0^{13}$ operations run in tens of seconds on a modern multi-core machine with SIMD distance kernels. The cost is approximate, not optimal: $k$ -means converges to a local minimum of the error, not necessarily the global one. In exchange, the algorithm is fast enough to actually run.

The codebook. When the algorithm stops, every one of the 256 representatives is sitting at the average of its assigned chunks (because the last step we ran was an update). The collection of those 256 final centroids is called the codebook for this subspace, by analogy with the codebook of a cipher: a small fixed list of entries that the rest of the data refers back to by index.

Encoding a chunk. Once the codebook is built, compressing any 8-dimensional chunk (a database chunk, or a chunk from a vector being inserted later) is a single step: compute the Euclidean distance from the chunk to each of the 256 centroids, find the nearest one, and record that centroid's index (a number from 0 to 255, fitting in one byte). The compressed chunk is just that one byte.

Encoding a full 768-dimensional vector. Split the vector into 96 chunks of 8 dimensions each, and for each chunk find the nearest centroid in that subspace's codebook (256 distance computations per chunk). Record the 96 centroid indices. The compressed vector is 96 bytes, one byte per subspace.

For $d = 768$ , $m = 96$ , $K = 256$ :

Original: $768 \times 4 = 3072$ bytes per vector.
Compressed: $96 \times 1 = 96$ bytes per vector. A 32× ratio.
Codebooks (one per subspace): $96 \times 256 \times 8 \times 4 = 786, 432$ bytes ≈ 768 KB total, fixed regardless of dataset size.

Why "product"?

A compressed vector is described by 96 independent choices: for each subspace, which of the 256 centroids did this vector's chunk get assigned to? The total number of distinguishable compressed vectors is the product of the choice counts:

96 subspaces 256 \times 256 \times \dots \times 256 = 25 6^{96} \approx 1 0^{231} .

That is the vocabulary of compressed forms PQ can produce, and it is enormous: more entries than there are atoms in the observable universe ( $\sim 1 0^{80}$ ). The actual storage required is only the 96 codebooks themselves, $96 \times 256 = 24, 576$ centroids, about 768 KB. So PQ's encoding can effectively distinguish $1 0^{231}$ different vectors using $1 0^{4}$ stored centroids. The huge vocabulary is implicit, never materialised; each compressed vector picks one element from it by selecting 96 centroid IDs.

The mathematical name for this kind of construction is the Cartesian product. Given several sets, the Cartesian product is the collection of every possible tuple you can form by picking one item from each set. For two sets $A = {red, blue}$ and $B = {1, 2, 3}$ , the Cartesian product $A \times B$ contains six pairs: $(red, 1), (red, 2), (red, 3), (blue, 1), (blue, 2), (blue, 3)$ . The size of $A \times B$ is the size of $A$ times the size of $B$ : $2 \times 3 = 6$ .

PQ does the same construction with 96 sets instead of 2. The 96 input sets are the per-subspace codebooks, each holding 256 centroids; every compressed PQ vector is one tuple from the Cartesian product of those 96 codebooks (a sequence of 96 centroid choices, one per subspace). The total tuple count is $256 \times 256 \times \dots \times 256$ (96 times) $= 25 6^{96}$ , the same multiplication we already saw above. That product is where "product quantization" gets its name.

The structural payoff is exponential expressiveness from a linear amount of stored data; you couldn't get the same expressiveness with a single flat 768-dimensional codebook because storing $1 0^{231}$ centroids is impossible.

The catch. The $1 0^{231}$ vocabulary entries are not freely placed in 768-dimensional space. Each one is implicitly the concatenation of one centroid per subspace, and the subspace centroids were trained independently. If subspaces are correlated in the original data (knowing one subspace's values tells you a lot about another's), many compound encodings land in regions of 768-dimensional space where no real data lives, and the effective vocabulary is smaller than $1 0^{231}$ in practice. PQ works well when subspaces are roughly independent of each other. A common refinement called OPQ (Optimized Product Quantization) learns a rotation of the original space and applies it before splitting into chunks, so that the post-rotation subspaces are as independent as possible. OPQ is a drop-in replacement for the splitting step; everything downstream (codebook training, encoding, querying) is identical.

Asymmetric distance computation (ADC)

At search time, every database vector is no longer a list of 768 floats; it is a list of 96 centroid IDs, one per subspace. The query $Q$ , on the other hand, is the original 768 floats. Computing the distance between a full-precision $Q$ and a 96-byte ID list looks impossible at first: there are no float coordinates to subtract from $Q$ on the database side, only ID numbers.

The technique that solves this is called asymmetric distance computation, abbreviated ADC. The "asymmetric" word will become clear at the end of this section. The core idea is to do the precision-heavy work once per query and reuse it across every database vector the search visits.

There are only two precision-rich kinds of objects in the system: the query $Q$ (one vector per search) and the centroids in the codebooks (a fixed $96 \times 256 = 24, 576$ of them, shared across every database vector). So before scanning the database, compute every distance that involves $Q$ and a centroid up front, and store those distances. After that, each database vector's distance to $Q$ is reduced to picking the right precomputed numbers and adding them up.

Step 1: build the lookup table

A lookup table (LUT) is just a precomputed array of answers. Instead of running a calculation each time you need a number, you run it once, store the result in a fixed slot, and from then on read the slot instead of recomputing. Multiplication tables that schoolchildren memorise are the everyday example: rather than recomputing $7 \times 8$ each time, you remember it is $56$ and look up the entry.

PQ's lookup table is two-dimensional, indexed by (subspace, centroid_id). Each entry holds the squared distance between $Q$ 's chunk in that subspace and one centroid in that subspace's codebook.

Construction:

Split $Q$ into its $m$ chunks: $Q_{1}$ holds dimensions 1-8, $Q_{2}$ holds 9-16, and so on through $Q_{96}$ .
For each subspace $s$ and each of the $K = 256$ centroids $c_{s, j}$ in that subspace's codebook, compute the squared distance $∥ Q_{s} - c_{s, j} ∥^{2}$ and write it into row $s$ , column $j$ of the table.

For a tiny example with $m = 2$ subspaces and $K = 3$ centroids each, the LUT is a 2-by-3 array of floats, with one row per subspace:

	centroid 0	centroid 1	centroid 2
subspace 0	0.42	1.07	0.18
subspace 1	0.91	0.05	0.63

Each cell is "the squared distance from $Q$ 's chunk in this subspace to this centroid in this subspace's codebook". Cell $(0, 2) = 0.18$ means $Q$ 's first chunk is at squared distance $0.18$ from centroid 2 of subspace 0.

In the production setting ( $m = 96$ , $K = 256$ ) the table is 96 rows by 256 columns: $96 \times 256 = 24, 576$ float32 entries, taking $24, 576 \times 4 = 98, 304$ bytes, about 96 KB. Building it costs $24, 576$ small distance computations in 8-dimensional space, all done at the start of the query in a fraction of a millisecond.

Step 2: distance to a compressed database vector

Now take any compressed database vector $x$ , stored as the 96 centroid IDs $x_{1}, x_{2}, \dots, x_{96}$ (one byte each). The squared distance from $Q$ to $x$ is approximately:

∥ Q - x ∥^{2} \approx s = 1 \sum m LUT [s] [x_{s}]

In words: walk through the 96 subspaces. In subspace $s$ , $x$ 's chunk was encoded as centroid number $x_{s}$ . The distance from $Q$ 's chunk in that subspace to that centroid is sitting in row $s$ , column $x_{s}$ of the LUT. Read it out. Add the 96 numbers together.

Going back to the tiny $m = 2, K = 3$ example: if a database vector is encoded as $x = (2, 1)$ (centroid 2 in subspace 0, centroid 1 in subspace 1), its squared distance to $Q$ is $LUT [0] [2] + LUT [1] [1] = 0.18 + 0.05 = 0.23$ .

The total work per database vector is $m$ memory reads from the LUT and $m - 1$ floating-point additions, roughly 100 nanoseconds for $m = 96$ . There is no decompression, no full-precision distance calculation, and nothing about the 768-dimensional ambient space appears in the inner loop. The LUT is built once at the start of each query and reused for every database vector the search evaluates.

Why this works as an approximation: the squared Euclidean distance over 768 dimensions is the sum of squared distances over disjoint chunks of dimensions (because squaring then summing is the same whether you split the dimensions into groups or not). So the true distance from $Q$ to $x$ is exactly the sum of per-subspace squared distances. ADC plugs in the centroid that stood in for $x$ 's chunk in each subspace's distance, instead of $x$ 's actual chunk. The error is bounded by how far each chunk drifted from its centroid, which is small when $k$ -means has done its job.

Symmetric vs asymmetric

The "asymmetric" in the name reflects an asymmetry between $Q$ and $x$ . In the algorithm above, $Q$ is left at full float32 precision and only $x$ is compressed; the LUT entries are exact distances on $Q$ 's side. There is a less common variant called symmetric distance computation that compresses $Q$ too: encode $Q$ against the codebooks like any database vector, store its 96 centroid IDs, and look up centroid-to-centroid distances in a precomputed $K \times K$ table per subspace (which can be cached because the codebooks are fixed). The inner loop is slightly faster, but recall drops noticeably because $Q$ 's coordinates have been snapped to the same coarse grid as the database, doubling the approximation error. Most production systems run ADC.

A subspace, in pictures

The demo below shows what PQ does inside a single subspace. The 50 points are the chunks of the dataset's vectors in this one subspace ( $d = 2$ for visibility). $k$ -means with $K = 4$ clusters them into the four marked centroids (the codebook for this subspace). Each point is then encoded as the index of its nearest centroid. For ADC, the query Q's distance to each of the four centroids is precomputed (the LUT entries shown below the chart), and any compressed point's contribution to $∥ Q - x ∥^{2}$ in this subspace becomes a single array lookup.

1 / 5

Fifty raw points in the subspace

Each point is the projection of one database vector onto this 2-dimensional subspace. The full PQ would do this for 96 subspaces in parallel; here we look at one of them.

The full PQ does this independently for each of the $m$ subspaces. The compressed representation of a 768-dimensional vector is then $m = 96$ such cluster indices, and the distance from Q to any compressed vector is the sum of $m$ subspace lookups.

Recall

PQ is approximate: the distances it computes are estimates, not exact, so the top- $k$ neighbours it returns can differ from the true top- $k$ that an exhaustive float32 comparison would have produced. Some queries return all the right answers; others swap one or two correct neighbours for slightly-wrong ones; very rarely a query returns badly wrong results. We need a single number that summarises how often this approximation produces the correct answer.

The standard metric is recall@k. The recipe:

Pick a test query.
Run an exact brute-force search: compare the query against every full-precision database vector, sort by true distance, keep the top $k$ . Call this set $G$ for "ground truth".
Run the approximate search (PQ in our case) and keep its top $k$ . Call this set $A$ .
Recall@k for this query is $∣ A \cap G ∣/ k$ : how many vectors are in both lists, divided by $k$ .
Repeat for many queries (a held-out test set of a few thousand is typical) and average.

Concrete example with $k = 10$ . Suppose the brute-force top 10 for some query is $G = {A, B, C, D, E, F, G, H, I, J}$ . The approximate search returns $A_{pq} = {A, B, C, D, E, F, G, H, I, X}$ , with $X$ a wrong vector that snuck in instead of $J$ . The intersection is ${A, B, C, D, E, F, G, H, I}$ , size $9$ , so recall@10 for this query is $9/10 = 0.9$ . Average that over the test set to get the overall recall@10. A configuration scoring 0.99 means that, on average, the search returns 9.9 of the 10 true neighbours per query.

Recall is a number between $0$ (none of the true neighbours found) and $1$ (every true neighbour found). Production targets vary: for semantic search on top of an LLM, recall@10 around 0.95-0.99 is the usual band, since the downstream application is forgiving of swapping near-equivalent neighbours but breaks if the search returns something irrelevant.

PQ does not lose much recall in practice, but the loss is not free. Three knobs shape the error in distance estimation, and therefore the recall:

Subspace dimension $d / m$ . Smaller subspaces (more chunks for the same $d$ ) give a higher compression ratio per vector but introduce more error per chunk, because each centroid has to stand in for a wider variety of inputs in its small subspace.
Codebook size $K$ . More centroids per subspace mean a finer-grained approximation, so the encoded chunk is closer to its original value. Diminishing returns kick in past $K = 256$ , which is why 1-byte indices are the production sweet spot.
Data distribution. If the data within each subspace lies on a low-dimensional manifold (most chunks cluster in a thin slice of the 8-dimensional space), $k$ -means picks centroids on top of the dense regions and the per-chunk error stays small. If the data fills the subspace uniformly, the same number of centroids has to spread out and the per-chunk error grows.

Typical configuration on 768-dimensional sentence embeddings: $m = 96$ , $K = 256$ gives around 99% recall@10 compared to brute-force float32 search. The 1% recall loss is barely visible in downstream applications.

Training the codebook, and what to do when the data drifts

The codebook is trained once on a representative sample of the dataset, not on every database vector. A sample of a few hundred thousand to a few million chunks per subspace is enough to capture the distribution; $k$ -means on a million chunks runs in seconds with a SIMD distance kernel. Once the codebook is trained, it is used to encode all $N$ database vectors and any vectors that arrive later: each new vector is split into 96 chunks, and each chunk is mapped to the nearest centroid in its subspace's codebook. The centroids themselves don't move when new vectors are inserted.

This raises a real problem. If the data distribution shifts over time, the existing centroids stop being a good fit. Newly inserted chunks land far from any centroid; the per-chunk approximation error grows; distance estimates lose accuracy; recall drops. For a stable workload the drift is slow and the codebook stays useful for a long time, but for an evolving one (e.g., user-generated content or a model that gets re-trained) the codebook can become stale within weeks.

Production systems handle this in two ways:

Periodic retraining. On a schedule (weekly, daily, hourly depending on how fast the data moves), draw a fresh sample, re-run $k$ -means to get a new codebook, and re-encode the dataset against it. The cost is moderate: $k$ -means on the sample plus one re-encoding pass over the database. Done in the background, the index never sees downtime.
Streaming / online $k$ -means. Update centroids incrementally as new vectors are inserted, nudging each centroid towards the chunks newly assigned to it. This keeps the codebook fresh without explicit retraining, at the cost of a more complex insertion path. Less common in practice because the periodic-retrain approach is simpler and good enough for most workloads.

Whatever the cadence, the codebook is treated as a slowly-aging artefact: trained once, used for a while, retrained and replaced when the recall numbers say it's time.

Beyond vector search

The same idea recurs everywhere precision can be traded for size. The clearest case is large language model weight compression: a 70-billion-parameter model with float16 weights takes 140 GB, INT8 halves that to 70 GB, and INT4 halves it again to 35 GB, the difference between needing a small server and fitting on a single consumer GPU. The bookkeeping differs from PQ (no chunking into subspaces, just per-row or per-block scaling factors plus integer storage), but the high-level move is the same: replace each value with a coarse approximation and accept a small accuracy loss in exchange for a large saving in memory and bandwidth. Modern variants (GPTQ, AWQ, the GGUF Q4 family) layer calibration data and per-block scaling on top to push that trade further at 4 bits without breaking model accuracy.

The codebook construction itself recurs in audio and image compression, where a small dictionary of learned prototypes stands in for the raw signal. Different domains, different details, the same trade.

The series so far, and what's next

Four articles, working from the geometry outward:

The problem. Why nearest neighbor search is easy in 1D, manageable in 2D, and breaks in 768D. The curse of dimensionality, derived from first principles.
Small worlds. How to do approximate nearest neighbor search by walking on a graph. Naive proximity graphs and their failures, Watts-Strogatz, NSW, HNSW.
On disk. How to scale HNSW to billions by serving the heavy data from SSD with DiskANN and Vamana, where each graph hop is one disk page read.
Quantization. How to compress the heavy data instead, so the same graph index can hold a much larger dataset in the same RAM budget. Scalar quantization for the easy cases, product quantization for the hard ones, with $k$ -means as the engine and ADC as the inner loop.

The arc so far, in one sentence: pairwise distance information collapses in high dimensions, but graph-based search avoids partitioning the ambient space, the graph can be laid out so each hop is one disk page read, and quantization shrinks the per-vector cost so billion-scale indexes fit in budgets that float32 vectors never could.

Upcoming parts will cover GPU-accelerated indexes, hybrid search combining vector NN with metadata filters, and streaming indexes for continuously-changing datasets.