**Correct: option A.**
The naive way to use PQ is: decode each PQ-encoded database vector back to a float vector by looking up centroids, then compute a regular float dot product or L2 distance against the query. That works but throws away most of the speed advantage.
The production fast path is **Asymmetric Distance Computation (ADC)**. The query stays as a full float vector. At the moment a query arrives, you do one chunk of work:
1. Split the query into pq_m sub-queries (32 of them, in the canonical 1024-dim / 32-byte setup).
2. For each sub-query, compute its distance to all 256 centroids in that subspace's codebook.
3. Stash the results in a pq_m x 256 lookup table (32 * 256 = 8192 floats, ~32 KB, fits comfortably in L1/L2 cache).
Now scoring any of the N database vectors is dead simple:
1. Read its 32 byte indices.
2. Look up the corresponding 32 distances in the table.
3. Sum them.
That is 32 lookups + 32 adds per database vector. No floating point multiplies, no decoding back to full vectors. Compare to a naive float distance: 1024 multiplies + 1024 adds per database vector. The ratio is roughly 30-60x in practice, depending on cache effects.
**Why the wrong options are wrong.** B (SSD I/O) misses the point: PQ vectors live in RAM, not on SSD; the speed is from CPU-side arithmetic reduction. C (GPU tensor cores) is unrelated; PQ-IVF runs on CPU in production at most companies. D (decode then compare) is the path ADC explicitly avoids; decoding to float32 destroys the speedup.
**Correct: option A. The speedup is from Asymmetric Distance Computation (ADC), not from compression alone.**
*The setup.* In PQ-encoded indexes (most often IVF-PQ), each database vector is stored as a pq_m-byte string of centroid indices, where pq_m is the number of subspaces (commonly 32 for 1024-dim embeddings). At query time you need to compute the approximate distance from the float query to every PQ-encoded candidate vector.
*The naive path: symmetric distance.* Decode each PQ code back to a reconstructed float vector by concatenating the looked-up centroids. Then compute the standard L2 or dot-product distance. This is fast per vector compared to a real ANN search, but it still does d float operations per database vector (1024 multiplies + 1024 adds for our setup). At billion-scale this is too slow.
*The fast path: ADC.* The query stays float; the database stays in code form; you compute once and reuse. Specifically:
- Once per query: split query into pq_m sub-queries. For each subspace j, compute the distance (squared L2 or dot product) from the sub-query to each of the 256 centroids in codebook j. Stash in a pq_m x 256 table. Cost: pq_m * 256 * (d / pq_m) = d * 256 = 262k float ops per query for d=1024. Done in well under a millisecond on modern CPUs with SIMD.
- Once per database vector: read the pq_m byte indices, look up the pq_m corresponding distances in the table, sum them. Cost: pq_m table lookups + pq_m floating point adds. For pq_m=32, that is 32 lookups + 32 adds. No multiplies, no per-vector float vector math.
*Why this is the right answer.* The lookup table is small enough to live in L1 or L2 cache (32 KB for pq_m=32, nbits=8), so lookups are cache-hit cheap. The per database vector cost drops from O(d) float ops to O(pq_m) integer indexed reads + adds.
Quick reference
TL;DR
Asymmetric Distance Computation (ADC): for each query, precompute a pq_m x 256 table of query to centroid distances.
Imagine you have a million items in a warehouse, each described by 32 'category tags'. A new query arrives and you want to find the closest items. The slow way is to fully expand every tag back into its full description and compare. The clever way: first, for each query, compute once how 'close' the query is to each of the 256 possible values of each tag. Now you have a small cheat-sheet. To score any warehouse item, just look up its 32 tags in the cheat-sheet and add up the 32 numbers. No real math per item, just lookups and adds. That is **asymmetric distance computation**.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example.
Single-vector lookups, not scans ADC amortizes its per query setup over many database vectors. For a one-off comparison, the table-build cost dominates.
Query is itself quantized (e.g. fully PQ-coded both sides) Then SDC (with a precomputed centroid to centroid table) is the right choice; ADC requires a float query.
Top-K rerank where exactness matters ADC is still approximate. Re-rank the top candidates with full-precision float distance for the final ordering.
Quick scan · 2–4 min
Everything important, quickly.
3 min: name ADC + per query setup vs per database cost + table size and cache fit + why ADC beats SDC + why GPU doesn't dominate.
Side-by-side
Approach
Per query setup
Per DB vector cost
Recall
Full float distance
0
O(d) multiplies + adds
Exact
Decode then compare PQ
0
O(d) multiplies + adds (after decode)
Approx (quantization)
SDC (symmetric)
0 (table precomputed at index time)
pq_m lookups + adds
Approx (both sides quantized)
ADC (asymmetric)
pq_m * 256 distance ops
pq_m lookups + adds
Approx (only DB quantized; best of the three approx options)
Real-world examples
Real products, models, and research that use this idea.
1Faiss IndexIVFPQ uses ADC by default; the fast path is hand-tuned SIMD that hits sub-10 ns per database vector.
2Faiss PQ4 fast scan packs pq_m=64 nbits=4 codes for AVX-512, hitting >2 billion distance computations per second per core.
3Milvus IVF_PQ implementation calls into Faiss for the ADC scan loop.
4ScaNN (Google) builds on the same ADC primitive with anisotropic loss training for the codebooks.
5Pinecone's serverless tier reportedly uses ADC-style table-lookup scans for its compressed cold tier.
Interviewer follow-ups
What an interviewer would ask next. Try answering before peeking at the approach.
QWhy does ADC beat SDC on recall?
Sign in or go Pro to see the approach for this follow-up.
QWhy doesn't GPU dominate PQ search?
Sign in or go Pro to see the approach for this follow-up.
QHow does PQ4 fast scan improve on standard 8-bit ADC?
Sign in or go Pro to see the approach for this follow-up.
Don't say this
Red flags and common mistakes that signal junior thinking. Click to expand.
Most common mistake
Assuming the speedup comes from compression alone. Smaller vectors do help with memory bandwidth, but the headline win is the table-lookup arithmetic: pq_m additions per vector instead of d float multiplies and adds.