PQ based distance computation outruns full float32 distance even after decoding the vectors. Why?

**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.