skip to content

Which FAISS index fits 20M 768-dim vectors in a few GB of RAM?

level: seniorimportance: must knowfreq 62%

answer

  1. Four bytes per dimension is the baseline
  2. One byte per dimension is the middle rung
  3. PQ code count is bytes per vector
  4. Compression is lossy, recall drops
  5. Refinement hands the memory back

basics

~20 s

A flat index would need about 61 GB, so the answer is a compressed IVFPQ index such as index_factory(768, "IVF16384,PQ96"): 96 code bytes plus an 8-byte id per vector is roughly 2 GB. The saving is bought with lossy distances and a mandatory training pass.

solid answer

~50 s

Start with the arithmetic. Raw float32 storage is `4 * d` bytes per vector, so 20M x 768 is 61.4 GB — far past a normal host. The intermediate step is scalar quantization (`"IVF16384,SQ8"`), one byte per dimension: 768 bytes per vector, about 15 GB, with only mild accuracy loss. The step that actually gets you to a few gigabytes is product quantization: `"IVF16384,PQ96"` stores 96 bytes of codes plus an 8-byte id, roughly 2.1 GB, plus a centroid table of `nlist * d * 4` bytes (about 50 MB here). That is a ~30x reduction, and 768 is divisible by 96, so each sub-quantizer covers 8 dimensions. What you give up is exactness: distances are computed against reconstructed codes, so ranking degrades. If that hurts, re-rank the shortlist against exact vectors with `IndexRefineFlat` — but the refine stage stores full vectors, which hands the memory back, so it usually lives on disk or in a separate store.

code

python · 11 lines
python
import faiss

d, n = 768, 20_000_000
flat_bytes = n * d * 4                 # raw float32 storage
sq8_bytes = n * d                      # one byte per dimension
pq96_bytes = n * (96 + 8)              # 96 code bytes + int64 id

print(flat_bytes / 1e9, sq8_bytes / 1e9, pq96_bytes / 1e9)

index = faiss.index_factory(d, "IVF16384,PQ96")
print(index.is_trained)                # False - needs a training sample

go deeper

for a junior

Know that raw vectors cost 4 bytes per dimension each and that FAISS offers compressed index types when that does not fit in memory.

for a middle

Be able to compute the flat, SQ8 and PQ figures on the spot and explain that PQ stores one byte per sub-quantizer, with the dimension having to divide evenly.

for a senior

Show the full trade: pick the index against a stated budget, justify nlist, name the accuracy loss, and say how you would measure recall against a flat ground truth before shipping.

for a principal

Own the cost curve end to end — hardware spend versus recall versus the rebuild pipeline a trained index commits you to — and be able to argue for a larger host instead of a lossier index when the numbers favour it.

## Do the arithmetic first The interview question is really "can you size an index without a benchmark". Three numbers carry it: - **Flat float32**: `4 * d` bytes per vector. At d=768, 3072 bytes. 20M vectors = 61.4 GB. - **Scalar quantization to 8 bits (`SQ8`)**: `d` bytes per vector. 768 bytes. 20M = 15.4 GB. - **Product quantization with m sub-quantizers at 8 bits (`PQm`)**: `m` bytes per vector. At m=96, 96 bytes. 20M = 1.9 GB of codes. On top of the codes, an IVF index stores an int64 id per entry inside the inverted lists (8 bytes) and a centroid table of `nlist * d * 4` bytes. For `nlist = 16384` at d=768 that is about 50 MB — real but not decisive. Total for `"IVF16384,PQ96"`: about 2.1 GB. That comfortably fits the stated budget with headroom for the process, the OS page cache and query-time working memory. ## Choosing the components **Why IVF at all?** Compression alone (`"PQ96"` with no IVF) fixes memory but leaves you scanning all 20M codes per query. PQ scanning is fast — it uses precomputed lookup tables — but 20M entries per query is still far too slow interactively. The IVF stage partitions the space so a query only scans the lists nearest to it. Memory and latency are separate problems and this index solves both with separate components; conflating them is a common muddle. **Sizing nlist.** The usual heuristic is 4x to 16x the square root of the vector count. sqrt(20M) ≈ 4472, so roughly 18k to 71k lists; 16384 is a reasonable, slightly conservative pick that keeps the coarse assignment cheap. Above roughly 65k lists, the coarse quantizer's own brute-force scan over centroids starts to dominate, and the standard remedy is a factory string like `"IVF65536_HNSW32,PQ96"` where the quantizer is itself a graph index. You also need enough training vectors for the clustering to be meaningful — on the order of tens per centroid, so tens of thousands to a few million sampled vectors. **Sizing the PQ codes.** The only hard rule from the index-composition side is divisibility: `d % m == 0`. At d=768 the legal, sensible choices are 64, 96, 128 or 192 bytes per vector, spanning roughly 1.3 GB to 3.8 GB of codes for this corpus. More bytes means finer reconstruction and better ranking. If the embedding dimension is awkward, a leading transform (`PCA` or `OPQ`) reshapes it into something PQ-friendly before encoding. ## The intermediate rung people forget Teams jump straight from flat to PQ and then complain about recall. Scalar quantization is the rung in between: `SQ8` maps each dimension to one byte, giving a 4x reduction with typically small accuracy loss, because it does not restructure the vector at all — it just lowers the numeric precision per dimension. For this corpus that is 15.4 GB, which fits a large-memory host but not a small one. The decision is therefore about the host you are willing to pay for: if a 32 GB machine is acceptable, `"IVF16384,SQ8"` is a much gentler trade than PQ. If you need a few gigabytes, PQ is the only option in the family. ## What compression actually costs PQ replaces each sub-vector with the nearest entry of a learned 256-entry codebook, so the stored representation is lossy and distances computed from it are approximate. Two vectors that were distinguishable in the original space may share codes. The visible effect is a drop in recall@k, and it is worse for queries in dense regions of the space and for datasets whose variance is unevenly distributed across dimensions — which is what OPQ preprocessing exists to fix. The standard mitigation is refinement: retrieve a larger shortlist from the compressed index, then re-score those candidates against exact vectors and keep the true top-k. FAISS exposes this as `IndexRefineFlat` and the `,RFlat` factory suffix. Be honest about the consequence — the refine index stores full float32 vectors, so it costs the 61 GB you were trying to avoid. In production that stage usually reads exact vectors from disk or an external store rather than RAM, or the shortlist is re-scored by a separate service. ## Training and rebuild are part of the choice A compressed IVF index is not free operationally. It arrives with `is_trained` False, needs a representative training sample, and the learned centroids and codebooks drift as the corpus changes — a corpus that doubles or shifts domain wants retraining, which means a full rebuild and a swap. That cadence is a real cost that a flat index does not have, and a senior answer names it: you are not just picking a data structure, you are signing up for a rebuild pipeline. ## The shape of a good answer Compute the flat baseline out loud, name the compression rungs and their per-vector byte costs, pick one against the stated budget, state the divisibility constraint that makes your choice legal, and close with what you gave up and how you would measure it — recall@k against a flat ground-truth index built over a sample.

  • How would you quantify the recall you lost by compressing?
    Build a flat index over a sample of the same corpus, run a fixed query set through both, and compare the top-k id sets — the overlap fraction is recall@k. Do it on a sample large enough to be representative but small enough to fit exactly. Without that measurement you have no way to tell a bad configuration from a bad embedding model, and no baseline to judge later changes against.
  • When is scalar quantization the better answer than product quantization here?
    When the memory budget is tens of gigabytes rather than a few. SQ8 gives a 4x reduction — 15 GB for this corpus — with much gentler accuracy loss, because it only lowers per-dimension precision instead of replacing sub-vectors with codebook entries. It is also simpler to train. Choose PQ when a 4x cut is not enough and you are prepared to measure and mitigate the recall drop.
  • Does adding a refinement stage solve the accuracy loss for free?
    No. Refinement re-scores a shortlist from the compressed index against exact vectors and does recover most of the ranking quality, but it needs those exact vectors — all 61 GB of them for this corpus. So it either puts back the memory you saved or requires reading vectors from disk or another store, adding latency. It is a real technique, but it changes the deployment shape rather than being a free win.
  • What operational cost does the compressed index add that a flat one does not have?
    A training and rebuild pipeline. IVF centroids and PQ codebooks are learned from a sample, so the index cannot be built incrementally from nothing, and as the corpus grows or its distribution shifts those learned parameters go stale. That means periodic retraining, a full rebuild, and an atomic swap into serving — plus a way to measure whether the new build is better than the old one.

saying these in an interview costs you the question

  • Cannot compute flat memory as 4 bytes per dimension
  • Thinks PQ compression is lossless
  • Applies PQ without checking the dimension divides evenly
  • Uses compression alone and expects fast queries over 20M vectors
  • Adds a refine stage without accounting for storing exact vectors

context

resolving links…