Why is product quantization fast at query time? It stil...

A strong answer names the two phases: first, build an m × k table of query-to-centroid distances using k*d multiply-accumulates. Second, reduce each candidate to m lookups and m-1 adds that never touch the original 768 floats. The table build is worth about 12,288 scanned vectors at d = 768, k = 256, so the trick only pays off when the probe set is large enough. A weak answer simply claims the vectors are smaller, which fails to explain why reordered codes run faster.