Topic 3.5
Making Vectors Smaller
In one line
Quantisation stores each number of a vector with fewer bits, which shrinks memory and speeds up comparisons while the ranking barely changes. Re-scoring a small shortlist with the full vectors wins back most of the accuracy that heavy compression loses.
Think of it like this
A shop writes every price to the nearest cent in its books, but a customer who only wants to know which of two shirts is cheaper does not need the cent: prices rounded to the nearest 10 cents give almost always the same answer, on a much shorter receipt. Quantisation rounds the numbers of a vector the same way, to save space and keep the ranking.
Words you'll meet
New words in this topic, in plain English. Come back here whenever one feels fuzzy.
- Quantisation
- Storing numbers with fewer distinct values (and so fewer bits) than the original.
- Scalar quantisation
- Rounding each number of a vector separately to one of a small number of levels.
- Code
- The small whole number stored instead of the original number, such as 0 to 255 in one byte.
- Binary vector
- A vector with one bit per number, usually just its sign.
- Product quantisation (PQ)
- Cutting a vector into pieces and replacing each piece with the id of its nearest entry in a learned codebook.
- Codebook
- The table of typical values (here: typical pieces of a vector) that codes point to.
- Shortlist
- The best candidates found cheaply, to be checked more carefully.
- Re-scoring
- Recomputing similarity for a shortlist with the full-precision vectors and re-sorting it.
Step by step
01Step 1: the memory problem
Write down the size of your collection: vectors times numbers times 4 bytes. 1,536 MB for a million 384-number vectors, 61,440 MB for ten million 1,536-number vectors. Every byte saved per number is saved for every vector.
02Step 2: map numbers to steps
Scale a number from [-1, 1] to [0, 1], multiply by the number of levels, and round to the nearest whole number. Rounding is floor(x + 0.5) in all three languages here, which avoids differences in how each rounds halves.
def quantise(vec, levels=255):
return [math.floor((x + 1) / 2 * levels + 0.5) for x in vec]
def restore(codes, levels=255):
return [c / levels * 2 - 1 for c in codes]03Step 3: measure the error
Restore the vector and compare. The biggest error is under half a step (0.0038 against 0.0039). A cosine barely moves: -0.0760 against -0.0785. The ranking of passages is what matters, and that is tested next.
04Step 4: search with the small copy
The second example keeps the question at full precision and compares it with the compressed copy of each of 1,000 vectors. It then counts how many of the true top 3 are in the compressed top 3.
05Step 5: re-score a shortlist
Take the compressed top 10 and recompute those 10 with the full vectors. The two columns of the table compare the compressed result with the re-scored one, from 8 bits down to 1.
06Step 6: choose the compression and the shortlist together
The more you compress, the larger the shortlist must be to recover recall. Topic 3.6 turns this into a measurement loop, and Topic 3.9's harness compares candidates such as "4-bit with a shortlist of 5" against "exact".
Try it yourself
- 1
Predict the error
In the first example change the number of levels from 255 to 15. Predict the biggest error (one step is 2/15) before running. Then change it to 1. What does the restored vector look like?
- 2
Grow the shortlist
In the second example set
SHORTLISTto 3, then 30. For the 2-bit row, how does re-scored recall change? Where would you stop? - 3
Longer vectors
Change the vector length in the second example from 16 to 64 (
make_vectors(1000, 64, 42)and the same for the queries). Do the compressed-only recalls go up or down for the 1-bit row? Why might longer vectors survive compression better?
Code & diagrams
The numbers are random values between -1 and 1 from the course's generator. Real embeddings are usually concentrated nearer zero, which makes a per-dimension range (learned from the data) better than a fixed -1 to 1.
Expected output
original: -0.998 0.143 -0.486 -0.105 0.308 0.934 0.258 0.433
codes: 0 146 65 114 167 247 160 183
restored: -1.000 0.145 -0.490 -0.106 0.310 0.937 0.255 0.435
biggest error 0.0038 (one step is 0.0078, so the error is at most half of that)
cosine(a, b) = -0.0760 cosine(restored a, b) = -0.0785
1000000 vectors of 384 numbers: 1536 MB as 32-bit floats, 384 MB as 8-bit codes
10000000 vectors of 1536 numbers: 61440 MB as 32-bit floats, 15360 MB as 8-bit codes1,000 random 16-number vectors are a hard case for compression. Treat the recall values as a demonstration of the pattern, not as numbers to expect on your own embeddings.
Expected output
levels bits recall@3 from codes only recall@3 after re-scoring a shortlist of 10
255 8 1.000 1.000
15 4 0.883 1.000
3 2 0.617 0.917
1 1 0.317 0.583Break it on purpose
Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.
Break #1
Quantise with the wrong range
In the Python tab of the first example, change (x + 1) / 2 * levels to x * levels inside quantise, as if the numbers were between 0 and 1.
Break #2
Re-score with the compressed numbers
In the Python tab of the second example, change full = {i: dot(q, vectors[i]) for i in shortlist} to full = {i: rough[i] for i in shortlist}.
Myth vs fact
Myth
Compressing vectors ruins search quality.
Fact
8-bit scalar quantisation usually changes recall very little and cuts memory 4 times. Heavier compression loses more, and re-scoring recovers much of it.
Myth
Quantisation is only for huge systems.
Fact
It also makes small systems faster, because less memory has to be read for each comparison. It matters most where memory is the limit.
Myth
Binary vectors are always worse than floats.
Fact
They lose accuracy, but at 32 times smaller they allow a much larger first stage, and with re-scoring the final results can be close to full precision. The outcome depends on the embedding model, so measure.
Pro corner
Extra depth for experienced readers. New to this? Skip it for now and come back later.
- ▸
Fixed -1 to 1 wastes levels because real embedding numbers cluster around zero. Production implementations learn a range from the data (per dimension, or by using percentiles so a few outliers do not stretch the scale), then store it with the index.
- ▸
Compare the question at full precision with compressed stored vectors (as in the example) when you can: only one side has quantisation error. Compressing both is faster but adds error from both.
- ▸
Re-scoring needs random reads of full vectors. Memory-resident codes with disk-resident full vectors work well when the shortlist is small (tens to a few hundred) and the disk is fast; for huge shortlists the disk reads become the bottleneck.
- ▸
Quantisation interacts with the index: IVF and HNSW can both store codes instead of full vectors, and their recall is then limited by both the index approximation and the compression, so measure the combination (Topic 3.6), not the parts separately.
Remember this
- 1
Why this exists. Topic 3.1 counted memory: a million vectors of 384 numbers take 1,536 MB, and ten million vectors of 1,536 numbers take 61,440 MB. The vectors are usually the biggest part of a vector index, and memory is what you pay for. Reading less memory also makes each comparison faster. Seven digits of precision per number is far more than a ranking needs.
- 2
Scalar quantisation, by hand. Embedding numbers usually lie between -1 and 1. Cut that range into 255 equal steps and store, for each number, the *step it falls in*: a whole number from 0 to 255 that fits in one byte. To read it back, turn the step into the middle number again. In the first example the vector
-0.998 0.143 -0.486 ...becomes the codes0 146 65 ...and is restored as-1.000 0.145 -0.490 .... One step is 2/255 = 0.0078, so no number is off by more than half a step, 0.0039; the biggest error here is 0.0038. This is called 8-bit scalar quantisation, and it makes the vectors 4 times smaller (1 byte instead of 4 per number). - 3
Why the ranking survives. Every number moves by a tiny random-looking amount, and a similarity is a sum over hundreds of numbers, so most of those errors cancel. In the example, the cosine between two vectors changes from -0.0760 to -0.0785. The gaps between a question's best and second-best passages are usually much larger than that. In the second example 8-bit codes keep recall@3 at 1.000.
- 4
Fewer bits, more loss. Keep fewer steps and the vector shrinks further but errors grow: 4 bits (16 levels), 2 bits (4 levels) or 1 bit (only the sign of each number survives, a binary vector). The second example measures recall@3 from the compressed vectors alone: 8-bit 1.000, 4-bit 0.883, 2-bit 0.617, 1-bit 0.317 (on random 16-number vectors, a hard case: higher-dimensional real embeddings keep more under compression, and some embedding models are trained to survive binary storage, so check your own model). A binary vector is 32 times smaller than float32, and two of them can be compared with a fast bit operation (the number of differing bits, the Hamming distance).
- 5
Re-scoring wins the accuracy back. Use the compressed vectors only to find a shortlist (here the best 10), then compute the exact similarity for just those 10 with the original full-precision vectors, and sort them. Recall@3 becomes 1.000 for 4-bit, 0.917 for 2-bit and 0.583 for 1-bit: a large recovery for 10 extra full comparisons. The shortlist must be bigger than k, often several times k; how much bigger is found by measuring (Topic 3.6). In real systems the compressed vectors stay in fast memory and the full vectors can live on disk, read only for the shortlist.
- 6
Product quantisation, as an idea. Scalar quantisation shrinks each number separately. Product quantisation (PQ) cuts a vector into pieces (say 48 pieces of 8 numbers for a 384-number vector), learns by k-means (Topic 3.3) a codebook of 256 typical pieces for each position, and stores for each piece only the number of its nearest typical piece: 1 byte. A 1,536-byte vector becomes 48 bytes, 32 times smaller, at a higher loss than 8-bit scalar quantisation. Distances can then be computed from small lookup tables. Faiss combines it with IVF as IVFPQ. You do not need to implement it to understand its trade: more compression, less accuracy, repaired by re-scoring.
- 7
The memory maths. For one million vectors of 384 numbers: float32 1,536 MB, 8-bit 384 MB, binary 48 MB (384 bits = 48 bytes each). For ten million of 1,536 numbers: 61,440 MB, 15,360 MB and 1,920 MB. Compression is often what decides whether an index fits on one machine at all.
Explain it without notes
What is 8-bit scalar quantisation, how much memory does it save, and what is the largest error on a number between -1 and 1?
Why can a ranking stay nearly unchanged when every number in the vectors is slightly wrong?
What is re-scoring a shortlist, and why does it recover accuracy lost to compression?
Give the memory for 5 million vectors of 768 numbers as float32, 8-bit and binary.
Practice
Write quantise(vec, levels) and restore(codes, levels) for numbers between -1 and 1 (round with math.floor(x + 0.5)). For the vector [-1.0, 0.0, 0.5, 1.0] print the 8-bit codes (levels 255), the restored values with 3 decimals, and the 1-bit codes (levels 1).
A collection has 2,000,000 vectors of 768 numbers. Print the memory in megabytes (1 MB = 1,000,000 bytes) as 32-bit floats, 8-bit codes and 1-bit codes.
Trade-offs
- ↔
More compression: less memory and faster scans, with lower recall in the first stage.
- ↔
A larger shortlist: more of the lost accuracy comes back, with more full-precision comparisons and more reads of the original vectors.
- ↔
Keeping full vectors as well as codes: memory or disk for both, in return for being able to re-score.
Done when you can
Done when you can quantise and restore a vector by hand and state the largest error.
Done when you can compute the memory of a collection at 32, 8 and 1 bit per number.
Done when you can explain why re-scoring a shortlist recovers recall.
Done when you can describe product quantisation in two sentences.