Advanced Storage SystemsNTHU — Spring 2026
← Back to Product Quantization

Product Quantization

一億個 128 維 float32 vector 搭配 HNSW 索引，光是 vector 本身就要 51.2 GB，加上邊列表總共約 67 GB。 但我們做的是 approximate nearest neighbor search，本來就不要求精確答案。既然距離計算已經是近似的，那 vector 的表示方式是不是也可以近似？如果能把每個 vector 從 512 bytes 壓到 16 bytes，記憶體需求降 32 倍，十億筆資料只要大約 20 GB 就能塞進一台普通的機器。

PQ 的壓縮原理

切分 Sub-vector

假設原始 vector 是 128 維的 float32。PQ 的第一步是把它平均切成 MM 段 sub-vector。如果 M=8M = 8，每段就是 128/8=16128 / 8 = 16 維。

訓練 Codebook

對每個子空間，我們跑一次 K-means clustering。假設設定 k∗=256k^* = 256 個 cluster（這裡用 k∗k^* 避免和 K-means 的 kk 搞混），訓練完後得到 256 個 centroid，這 256 個 centroid 就是這個子空間的 codebook。

訓練資料通常從資料集裡隨機抽幾十萬到幾百萬筆 vector 就夠了，不需要全部。訓練是離線的一次性成本。

Centroid Encoding

訓練完 8 個 codebook 之後，每個 vector 的壓縮方式是：把每段 sub-vector 替換成它在對應 codebook 中最近的 centroid 的編號。

k∗=256k^* = 256 個 centroid，編號只需要 log⁡2256=8\log_2 256 = 8 bits，也就是 1 byte。8 段 sub-vector 各需要 1 byte，一個 vector 的壓縮表示就是 8 bytes。

Asymmetric Distance Computation（ADC）

壓縮完了，怎麼算距離？

最直覺的方法是 symmetric distance computation（SDC）：把 query 也壓縮成 PQ code，然後比較兩組 PQ code 的距離。但這等於兩邊都損失精度，誤差會疊加。更聰明的做法是 ADC：query vector 保持原始的 float32 精度，只有 database 端使用壓縮表示。這樣只有一邊有量化誤差，搜尋精度好很多。

網友筆記

ADC 的具體步驟

  1. 建表：查詢開始時，把 query vector 也切成 MM 段 sub-vector。對每一段，計算它和對應 codebook 中所有 256 個 centroid 的距離，存進一張 lookup table。這張表的大小是 M×k∗=8×256=2048M \times k^* = 8 \times 256 = 2048 個 float32 值，只有 8 KB，非常小。

  2. 查表算距離：對資料庫中每個 compressed vector （8 bytes），讀出 8 個 centroid 編號，分別去 lookup table 查對應的距離，加總就是這個 vector 和 query 的近似距離。

每次距離計算只需要 M=8M = 8 次 table lookup 與 7 次加法，而且 lookup table 只有 8 KB，整張表都在 L1 cache 裡。

精度的代價

PQ 的壓縮是 lossy 的。直覺上，256 個 centroid 要「代表」一個 16 維子空間中所有可能的 vector ，勢必有量化誤差。誤差的大小取決於：

  • MM 越大（每段維度越少）：每個子空間越簡單，centroid 能更精確地代表該子空間的分佈。但 MM 越大，壓縮後的 PQ code 也越長。
  • k∗k^* 越大（centroid 數量越多）：每個子空間的近似越精細。但 k∗k^* 翻倍代表 codebook 大小和 lookup table 都翻倍，訓練時間也翻倍。k∗=256k^* = 256（8 bits）是目前最常見的設定，因為它剛好用 1 byte 存一個編號。

實務上，M=8M = 8, k∗=256k^* = 256 用於 128 維 vector 時，即使對整個資料集逐筆做 ADC，recall@10 也只大約落在 50%-70% 左右。不夠好！ PQ 通常須要配合其他優化。

IVF-PQ

Voronoi cells （圖片來源：Similarity Search with IVFPQ ）

PQ 壓縮了 vector ，但掃描十億筆 vector 就算每筆只要 8 次 lookup，總量還是太大。我們需要一個方法先把搜尋範圍縮小。

IVF-PQ 的做法是結合 inverted file index（IVF）和 PQ。

IVF 的結構

在 PQ 之上，先對整個資料集做一次粗粒度的 K-means clustering，把所有 vector 分到 CC 個 coarse cluster（CC 通常在 n\sqrt{n} 的量級，十億筆資料大約 C≈30,000C \approx 30{,}000）。每個 cluster 有一個 centroid 和一個 inverted list，裡面存著屬於這個 cluster 的所有 vector 的 PQ code。

查詢流程

  1. 找最近的 cluster：計算 query 和所有 CC 個 centroid 的距離，選出最近的 nprobe 個 cluster。
  2. 掃描這些 cluster 的 inverted list：只對這 nprobe 個 cluster 裡的 vector 做 ADC 計算。

如果 C=30,000C = 30{,}000 且 nprobe = 64，你只需要掃描 64/30,000≈0.2%64 / 30{,}000 \approx 0.2\% 的資料。十億筆中只看大約兩百萬筆，配合 ADC 的高效距離計算，查詢時間可以壓到幾毫秒等級。

nprobe 和 HNSW 的 efSearch 角色一樣：控制 recall 和 latency 之間的 trade-off。

自問自答

試著用自己的話回答以下問題。如果卡住了，回去重讀對應的段落。

  1. 一個 256 維的 float32 vector ，使用 M=16M = 16, k∗=256k^* = 256 做 PQ 壓縮。壓縮前後各佔多少 bytes？壓縮比是多少？如果資料集有 5 億筆 vector ，壓縮前後各需要多少 GB？

  2. 為什麼 ADC 比 SDC在搜尋精度上更好？從量化誤差的角度解釋。

  1. IVF-PQ 中，nprobe 設太小會怎樣？設太大會怎樣？如果你的資料有 10 億筆、C=30,000C = 30{,}000，你希望 recall@10 達到 90% 以上，nprobe 大概要設多少才夠？（要掃描多少比例的資料?）