skip to content

When is exact flat vector search still the right choice over IVF or PQ?

level: principalimportance: should knowfreq 44%

answer

  1. approximation must be earned, not assumed
  2. multiply count by dimensions by bytes
  3. brute force is a matrix multiply
  4. perfect recall, no training, trivial deletes
  5. compression can change the deployment topology

basics

~20 s

Whenever the corpus fits in memory and exhaustive scanning meets the latency budget. Exact search gives perfect recall with no training, no tuning, no rebuild and trivial updates — approximation is a cost you should only pay once the arithmetic forces it.

solid answer

~50 s

Start from the arithmetic, not the reputation of the algorithm. 200,000 vectors at 768 dimensions in float32 is about 614 MB, and an exhaustive scan is a single dense matrix multiply that SIMD and BLAS handle in low single-digit milliseconds at modest QPS. That configuration gives 100% recall, zero training, no `nprobe` to tune, no codebook to go stale, and deletes and inserts that are just array edits. An approximate index there adds failure modes and buys nothing. The picture inverts as the corpus grows. 1.2 billion 768-dimension vectors is roughly 3.7 TB uncompressed — a cluster — while PQ at 64 bytes each brings it to about 77 GB, which fits one machine. There compression is not an optimization, it is the difference between one server and a distributed system. The deciding variables are corpus bytes versus RAM budget, QPS against scan time, the recall SLA, update rate, and how much operational complexity the team can carry.

code

python · 6 lines
python
dims = 768
small = 200_000
huge = 1_200_000_000
print(round(small * dims * 4 / 1e6, 1), "MB exact")
print(round(huge * dims * 4 / 1e12, 2), "TB exact")
print(round(huge * 64 / 1e9, 1), "GB as 64-byte PQ codes")

go deeper

for a junior

Know that exact search compares the query against every vector, always returns the true nearest neighbours, and is perfectly fine when the collection is small.

for a middle

Be ready to do the footprint arithmetic aloud — count times dimensions times bytes — and to say that an approximate index trades recall and operational complexity for memory or speed you must first prove you need.

for a senior

Show that you drive the decision from measured numbers: scan time at your QPS, memory headroom, update rate, and a recall SLA, and that you keep an exact baseline to measure the approximate index against.

for a principal

Own the staged path and its costs — when int8 buys enough headroom, when partitioning versus compression is the right lever, when one machine stops being viable — and be explicit that a learned index adds a component that degrades invisibly and therefore needs an owner.

## Do the arithmetic first Every sensible index decision here starts with three numbers: vector count, dimensionality, and bytes per component. Multiply them. - 200,000 x 768 x 4 bytes = **614 MB**. Fits in the heap of a mid-sized instance. - 50,000,000 x 768 x 4 = **154 GB**. Fits one large-memory machine, uncomfortably. - 1,200,000,000 x 768 x 4 = **~3.7 TB**. Does not fit anything ordinary. That third case with 64-byte PQ codes is about **77 GB** — plus roughly 10 GB of 8-byte ids and modest list overhead — which does fit a single large machine. That is the whole argument for compression stated in numbers: it is not that quantized search is *faster* per candidate so much as that it changes the deployment topology. ## What exact search actually costs Exhaustive search has an undeserved reputation for slowness. It is a matrix multiply: stack the corpus as an N x d matrix, multiply by the query (or a batch of queries), take the top k. This is the most heavily optimized operation in computing — SIMD, cache-blocked BLAS kernels, and near-perfect sequential memory access. Modern CPUs sustain on the order of a few GB/s per core of streamed comparison; 614 MB is therefore milliseconds, and it parallelizes linearly across cores and shards. Batching helps disproportionately: scoring 64 queries at once against the same resident corpus amortizes the memory traffic across all of them, which is why offline and analytical workloads often keep exact search far past the corpus size where an online service would have abandoned it. ## What you give up by approximating Approximate indexes are not merely "exact search with a small recall haircut". They import a list of ongoing obligations: - **A training phase**, whose sample quality silently determines recall, and which must be repeated as the distribution drifts. - **Tuning parameters** (`nprobe`, code size, shortlist size) that have to be swept against ground truth and re-swept as the corpus changes. - **A ground-truth harness**, because without it you cannot tell a healthy index from a degraded one — approximate search never reports that it missed something. - **Rebuild machinery**: compute budget, a blue/green swap, and the operational runbook to go with it. - **Harder updates.** Exact search deletes a row; a compressed partitioned index needs assignment, encoding, tombstoning and eventual compaction. For a 200k-vector corpus, all of that is pure liability. The exact baseline wins on recall, on latency, and on total operational cost simultaneously — a rare clean sweep, and one interviewers like to see a candidate name out loud rather than reflexively reaching for an ANN library. ## The variables that actually decide it **Footprint vs RAM budget.** The primary driver. If uncompressed vectors fit with headroom, do not compress. **QPS x scan time.** A 5 ms exact scan at 20 QPS uses a tenth of a core; at 2000 QPS it needs ten cores of pure scanning. High query volume can force approximation long before memory does. **Recall SLA.** Some workloads genuinely need exactness — deduplication, near-duplicate and plagiarism detection, entity matching, compliance lookups — where a 95%-recall answer is not a slightly worse answer but a wrong one. Approximation is a product decision there, not an infrastructure one. **Freshness and churn.** A corpus with heavy inserts and deletes pays continuous maintenance cost in a learned index and none in a flat one. **Team and blast radius.** A learned index adds a component that degrades invisibly. If nobody owns the recall dashboard, the degradation will be discovered by users. **Dimensionality.** Bytes per vector scale with d, so the same vector count crosses the memory threshold much earlier at 3072 dimensions than at 384. Model choice and index choice are coupled. ## The staged path A defensible progression, each step taken only when the previous one measurably fails: 1. **Exact flat.** Always the baseline and always the source of ground truth, even after you stop serving from it. 2. **Exact, but smaller per vector.** Scalar quantization to int8 gives roughly 4x with very little error and none of the partitioning machinery — often the highest-value single change. 3. **Partition** (IVF) when scan time, not memory, is the binding constraint. 4. **Compress hard** (PQ or binary) when footprint is the binding constraint, and pair it with rescoring against retained full-precision vectors. 5. **Shard** when one machine cannot hold the working set at any acceptable fidelity. The steps are independent. Plenty of production systems partition without compressing, or compress without partitioning; treating them as one package is a common mistake. ## The one line to carry into an interview Keep the exact index no matter what you serve from. It costs an offline job, and it is the only instrument that tells you whether the approximate index you deployed is still working.

  • Which workloads should never accept approximate recall?
    Ones where a missed neighbour is a wrong answer rather than a worse ranking: deduplication and near-duplicate detection, entity resolution and record matching, plagiarism or content-fingerprint checks, and compliance or legal-hold lookups. In those cases exactness is a product requirement, so the right move is to shard exact search or reduce the candidate universe with filters, not to trade recall for latency.
  • If exact search stops fitting, what is the cheapest first step?
    Scalar quantization to int8 — roughly 4x smaller per vector with small, well-behaved error, and no partitioning, no codebook training and no nprobe to tune. It preserves the operational simplicity of a flat scan while buying a factor of four of headroom, which frequently postpones the move to a partitioned or product-quantized index by a long way.
  • Should you keep an exact index after moving to an approximate one?
    Yes, at least offline. Approximate search never reports what it missed, so recall can only be measured against exact results on a held-out query set. Keeping the ability to brute-force a few thousand queries — even slowly, even on a batch machine — is what turns a silent degradation into a monitored metric, and it is cheap relative to the cost of finding out from users.

saying these in an interview costs you the question

  • Reaches for an ANN index before computing the footprint
  • Assumes exhaustive search is always too slow
  • Treats partitioning and compression as one inseparable package
  • Ignores update rate and rebuild cost in the comparison
  • Accepts approximate recall for deduplication or matching workloads

context

resolving links…