Shrinking a vector index by 32×

A retrieval system that works is, eventually, a retrieval system with a bill.

Ten million documents. One embedding each, 1024 dimensions, four bytes per dimension. That is 40 gigabytes before you have stored a single word of the actual text, and it needs to be in memory, because the entire point of an approximate nearest-neighbour index is that it does not touch disk. Ten million documents is not a large corpus. A mid-sized e-commerce catalogue with a vector per product variant gets there. A support knowledge base chunked for RAG gets there faster.

The good news is that this number is almost entirely under your control, and the levers are simpler than the literature makes them sound. The bad news is that the metric everybody reaches for to check whether compression hurt is the wrong one, and it will talk you out of a 32× saving that costs you nothing.

What is actually in there

Skip this section if embeddings are familiar.

An embedding is a list of numbers a model produces for a piece of content — a product, a paragraph, a query. The numbers themselves mean nothing individually. What matters is that content about similar things lands in similar places, so that “how close are these two lists of numbers” is a usable stand-in for “are these two things about the same thing”.

Almost every system normalizes these vectors to length 1, which makes the similarity measure a plain dot product:

Search is then: compute that against every document, keep the best ten. An approximate index (HNSW, IVF) makes it faster by not comparing against every document — but it still holds every vector in memory to compare against the ones it does visit. So the size of the index is set by one line of arithmetic:

Three terms. You do not get to change — that is your catalogue. Which leaves two, and they are the two things this note is about.

Lever one: fewer bytes per number

A float32 spends four bytes describing one dimension to about seven decimal digits of precision. Nothing in the pipeline needs seven digits. The numbers came out of a neural network that was trained in mixed precision, they are compared against other approximate numbers, and the answer is thresholded into “top ten or not”.

Scalar quantization replaces each float with a single byte. Find the largest magnitude in the vector, divide the range into 255 steps, and store which step each dimension landed on:

Store the 1024 bytes plus the one float scale , and a vector that was 4096 bytes is now 1028. Reconstructing is one multiply, and dot products can be done directly on the integers — modern CPUs are faster at int8 dot products than float32 ones, so this is a rare change that makes both memory and latency better.

Rounding to 1 of 255 levels perturbs each dimension by at most half a step. Over 1024 dimensions those errors are independent and mostly cancel, so the error in the sum grows like while the sum itself grows like . Long vectors are much more robust to per-dimension noise than short ones — which is also why the same trick gets riskier as you cut dimensions.

Lever two: one bit per number

Push the same idea to its limit. Keep only whether each number was positive:

A 1024-dimensional vector becomes 1024 bits — 128 bytes, down from 4096. And the similarity between two of them is not a dot product at all; it is a XOR followed by a population count, which is a handful of CPU instructions on several words at once. Binary indexes are not only 32× smaller, they are roughly an order of magnitude faster to scan.

The reason this is not obviously insane: for vectors on the unit sphere, cosine similarity is a monotone function of the angle between them, and the fraction of coordinates where two vectors disagree in sign is itself an estimate of that angle. Signs preserve direction and throw away magnitude, and after normalization, direction is all there was.

The reason it is a little insane: you have kept 1 bit where there were 32, and whether the remaining bit is enough depends entirely on how crowded the neighbourhood around each query is.

Lever three: fewer numbers

The third term in the arithmetic is , and the modern answer to it is Matryoshka representation learning. An MRL-trained model is trained so that the first 512 dimensions of its output are a usable embedding on their own, and so are the first 256, and the first 128 — nested like the dolls. Truncating is then free: slice the array, renormalize, done. No re-encoding, no second model.

This only works because the model was trained for it. Chopping the tail off an embedding from a model that was not trained this way discards whatever happened to be stored there, and what was stored there is not sorted by importance.

Do it to a real index

Everything above is applied below to the same 600 synthetic embeddings, ranked against the same 60 queries. Nothing is precomputed — pick an encoding and the page re-encodes the vectors, re-ranks every query and re-scores the result.

Compression, measured two ways. The purple line is recall@10 against what exact float32 search returns. The teal line is nDCG@10 against the relevance judgments, as a share of what the uncompressed index scores. Both are averaged over 60 queries. Start on binary at full width, with the rescoring slider all the way left.

The two lines disagree, and that is the whole note

Leave the settings where they start: binary, 1024 dimensions, no rescoring. The index has gone from 40.96 GB to 1.28 GB. Now read the two numbers.

Recall@10 says

60%. Four of the ten documents that exact search would have returned are missing. On any other day, a change that dropped recall by forty points would be reverted before lunch.

nDCG@10 says

99.8%. Against the actual relevance judgments, the compressed index is delivering essentially everything the uncompressed one did. There is no detectable degradation in what the user receives.

Both numbers are correct. They are answering different questions.

Recall against exact search asks: did we return the same documents? It treats the float32 ranking as ground truth. But the float32 ranking is not ground truth — it is one model’s guess at relevance, and it scores 0.663 on nDCG, not 1.0. When binary quantization drops the document exact search ranked 7th and returns the one it ranked 12th instead, recall records a miss. The user gets a different document about the same thing, at the same quality, and notices nothing.

Recall-against-exact is the default metric in every vector database benchmark, because it is the only one you can compute without relevance judgments. That convenience is exactly why teams reject compression that would have been free. If you have judgments — or clicks, or any downstream metric — score the compression with those instead, and treat recall as a diagnostic rather than a verdict.

The failure mode runs the other way too. Switch to float32 at 128 dimensions: recall@10 is 45%, worse than binary at full width, and nDCG has fallen to 76% of baseline. Here the recall loss is real. Truncation to an eighth of the width removed information the ranking actually needed, and the users’ metric agrees. Two settings with similar recall, completely different verdicts — which is why recall alone cannot make this decision.

Rescoring: how to have both

You do not have to accept the cheap ranking. Retrieve more than you need with the compressed index, then re-score that shortlist with the original vectors and keep the best ten.

Keep the binary index in memory — 1.28 GB for 10M documents — and the float32 vectors wherever they are cheap to hold: on disk, on SSD, in a cold tier.
Encode the query. Compare it against the binary index and take the top , where is a small multiple of the ten you need.
Fetch the full-precision vectors for those candidates only.
Re-score those with an exact dot product, sort, return the top 10.

Drag the rescoring depth slider. At — asking the cheap index for twenty candidates instead of ten — binary recall climbs from 60% to 89%. At it is 99%. The index is still 1.28 GB.

There is a small, useful piece of reasoning behind why that curve rises so fast, and it is worth stating exactly:

The rescoring pass scores candidates with the same function that defined the ground truth. So any true top-10 document that appears anywhere in the first candidates will be scored correctly and will make the final list. Nothing that got into the shortlist can be lost by rescoring it.

Which means:

Compression does not have to put the right documents in the right order. It only has to put them somewhere in the first . That is a far weaker requirement, and it is why a 2–4× over-fetch buys back almost all of the loss.

The cost is bounded and small: full-precision dot products, plus random reads to fetch those vectors. At and 1024 dimensions that is about 40,000 multiply-adds — microseconds. The random reads are the part to watch, not the arithmetic.

What this looks like as a decision

Work down the widget’s four settings and the shape of the trade is clear.

int8, full width — take it 4× smaller, faster to scan, and in this corpus it does not lose a single result. If your index is float32 today, this is the change to make first, and it barely needs an experiment.
binary, full width — take it, with rescoring 32× smaller, an order of magnitude faster, and with a 2–4× over-fetch the answers are indistinguishable. This is what makes a 40 GB index fit on one machine. Budget for keeping the float32 vectors somewhere reachable.
Matryoshka truncation — only with an MRL model Halving the width costs almost nothing here and halves memory again. Going to a quarter starts to hurt, and an eighth is broken. Verify against your own data at every step; the point where it breaks is a property of your corpus, not a constant.
binary and aggressive truncation — measure very carefully The losses compound. Binary at 128 dimensions is 256× smaller and retains half the quality, which is not a trade anyone wants. Compress along one axis at a time and stop when the quality metric moves.

Five things the demo does not show you

Centre your vectors before binarizing. Most embedding models have a strong common direction — every vector has a positive component along it. If you take signs without subtracting the corpus mean first, that dimension’s bit is 1 for almost every document and carries no information at all. Subtracting the mean before binarizing is a one-line change that routinely recovers several points.

Consider a rotation. Binary quantization implicitly assumes each dimension matters equally, because each gets exactly one bit. Real embeddings are anisotropic: a few dimensions carry much more variance than the rest. Applying a fixed random rotation before taking signs — cheaply, with a sign flip and a fast Hadamard transform — spreads the energy out and makes the bits more equally useful. This is the core idea behind ITQ and, more recently, RaBitQ.

Product quantization is the other family. PQ splits the vector into chunks, runs k-means on each chunk, and stores which centroid each chunk landed nearest. It reaches similar or better compression than binary at a given quality, and it is what FAISS has done for a decade. It is also more machinery: a codebook to train, keep, version and re-train when the embedding model changes. Binary quantization has become popular partly because it has no state — the encoder is v >= 0, and nothing about it can drift.

Compression interacts with filtering. A query that also filters on in_stock = true or language = 'bn' needs the shortlist to survive the filter. If your filter removes 95% of the corpus, an of 40 might leave you two candidates. Over-fetch has to be set against the filter’s selectivity, not just against .

Re-encoding is a migration. Changing the embedding model means re-encoding every document, and while that runs, part of the index is in the old space and part in the new one. Vectors from two models are not comparable, so this is a dual-write and a swap, not a rolling update. Whatever compression you choose, the encode step should be cheap enough to run over the whole corpus without it being an event.

How I would actually decide

Pick the metric first, and make it one a person outside the team can defend: nDCG against a judged set, or click-through on the surface itself, not recall against exact search. Fix a latency budget and a memory budget. Then walk the encodings from cheapest to most expensive and take the first one that clears both.

In practice that walk almost always ends at int8 for a small index, and at binary plus rescoring for a large one — and the reason it does not end there more often is that somebody ran a recall benchmark, saw 60%, and stopped.