← 回首頁

向量壓縮 PQ/IVF（乘積量化 + 倒排索引）

當你手上有幾億條向量（每張照片、每段文字都有一串數字「指紋」），兩個麻煩就冒出來：全部存完整數字太佔記憶體， 每次搜尋又得跟每一條比對太慢。PQ（乘積量化）像描述顏色時不記精確數值、改從一小盒蠟筆裡挑「最接近的那支」， 只存編號就省下大半空間；IVF（倒排索引）則像圖書館先把書分區，找書只翻相關那幾櫃、不必逐本翻遍。兩招都是 「用一點點不精準，換巨大的空間與速度」。下面你會看到這份代價——量化誤差與漏標——具體長什麼樣子。

向量搜尋除了「怎麼快找」（HNSW 等圖索引），還有另一半課題：怎麼壓縮與怎麼縮小掃描範圍。 Product Quantization（PQ，乘積量化）把高維向量切成多個子空間，各自訓練一份小碼本，原向量只需存幾個 小整數「碼」而非完整浮點數，查詢時用查表加總的近似距離（ADC）取代逐維重算，換取記憶體節省； IVF（Inverted File Index，倒排索引）則用 k-means 把全部向量粗量化成 k 群，查詢時只探最近的 nprobe 個群，避免暴力全表掃描。兩者都是「用近似換代價」的手法，本頁誠實展示各自的量化誤差與漏標代價 長什麼樣子。

為什麼 AI 時代重要

FAISS（Facebook AI Similarity Search）等向量資料庫的索引家族裡，PQ 與 IVF 是與 HNSW 並列的核心成員： HNSW 負責「快找」（圖索引逐層貪婪導覽縮小候選範圍），PQ 負責「省記憶體」（把向量本身壓成碼本）， IVF 負責「粗篩」（倒排分群限縮候選範圍）——十億級向量資料庫若只有 HNSW，索引本身佔用的記憶體就 可能超出可負擔範圍；只有 PQ/IVF 而沒有快速索引，查詢又會退化成大範圍線性掃描。三者缺一不可， 常見組合如 FAISS 的 IndexIVFPQ（IVF 粗篩 + 群內 PQ 壓縮距離計算）。

它是 k-means 分塊與倒排索引的合體

PQ 的碼本訓練與 IVF 的粗量化，本質上都是同一套決定性 k-means：把向量分塊、用少數質心代表一群點—— PQ 對每個子空間各分一次塊（碼本），IVF 對完整向量分一次塊（群），IVF 再把分塊結果攤平成經典的 倒排清單（inverted list）結構。這與負責「快找」的 近似最近鄰 HNSW 是互補關係：HNSW 管索引結構、PQ/IVF 管壓縮與範圍縮減， 向量搜尋系統通常需要兩邊手法一起用。

1. Product Quantization（乘積量化：子空間碼本 + ADC 誤差對照）

子空間切分：4 維向量切成 A（維度 0-1）、B（維度 2-3）兩個子空間，各自以決定性 k-means（初始質心固定 取索引 0、2，逐一比較距離平方取最小者，嚴格小於比較，等距離時保留索引較小的質心，不更新；空群 保留前一輪質心）訓練 k=2 個質心，收斂後的分群指派即為該子空間的「碼」。編碼：合併兩子空間的碼組出 完整編碼表，並獨立算出「碼→拼回質心」的重建向量與原向量的重建誤差。查詢：對查詢向量的每個子空間 各建一份 LUT（對該子空間 k 個質心的距離平方表），ADC（Asymmetric Distance Computation，非對稱距離 計算）近似距離 = 依碼查各子空間 LUT 直接加總，不重算精確距離；本頁同幀對照 ADC 近似值與獨立全算的 exact 精確值，誠實列出誤差。

固定資料：8 個 4 維整數向量（座標 0..9）[1,2,8,9] [2,1,9,8] [8,9,1,2] [9,8,2,1] [1,1,1,2] [2,2,2,1] [8,8,8,9] [9,9,9,8]；子空間 A=維度(0,1)、B=維度(2,3)，各 k=2 質心，決定性初始質心取索引 0、2。 查詢固定跑兩輪：Q2=[2,3,7,8]（主示範，非對稱，ADC 排序有區分度）→ Q（對稱邊界）=[5,5,5,5]（恰為 兩子空間質心的對稱中點，示範 ADC 排序打平的最壞情況）。
累計步驟數（steps）：0 階段：kmeans
列 = 8 個 4 維向量（索引 0-7）；欄 0-3 = 原始座標（常數，不隨 frame 改變）；欄 4 = 子空間 A 碼 （codeA）；欄 5 = 子空間 B 碼（codeB）。藍色外框（active）標示本步驟正在指派/查表/計算的列； 粉紅（pivot）標示本次操作聚焦的列（如編碼逐向量幀的目前向量、誤差表終幀的 ADC 最近鄰）。碼欄 於 k-means 收斂前會隨每輪重新指派而改變，收斂後鎖定即為最終碼。
教學縮尺：本頁僅 8 個 4 維向量、m=2 子空間、k=2 質心——每個向量編碼後仍要存 2 個碼 外加兩份碼本，教學規模下不會比直接存 4 個原始整數座標更省空間，PQ 的記憶體優勢要在十億級向量、 生產參數（m=8 以上子空間、每子空間 k=256 質心）下才會顯現，這裡只看得出「壓縮 + 量化誤差」長 什麼樣子，看不出真正的空間節省。
誠實揭露——查詢恰落於碼本對稱點時 ADC 完全失去排序能力：查詢 Q（對稱邊界）=[5,5,5,5] 恰為兩子空間各自兩質心的對稱中點，ADC 對全部 8 個向量查表結果打平成同一個值，無法分辨誰更近， 這是 PQ 的最壞情況；主示範查詢 Q2=[2,3,7,8] 則 ADC 近似排序與 exact 精確排序找到同一個最近鄰， 示範一般情況下 ADC 仍保有排序區分度，下方誤差表逐向量列出兩種查詢的對照。
與 HNSW 互補：HNSW 負責「快找」（索引結構縮小候選範圍），PQ 負責「省記憶體」（壓縮 向量本身），PQ 本身仍需搭配某種索引（如下方 IVF）縮小候選範圍才能避免全表掃描。

碼本（codebooks）

編碼表（codes，逐向量累積）

向量碼(A,B)重建座標重建誤差²

Q2 主示範誤差表（ADC 近似 vs exact 精確，逐向量對照）

向量exact d²ADC d²誤差²

Q（對稱邊界）打平現象說明

（尚無資料）

已執行操作紀錄（opLog）

（空）

2. IVF 倒排索引（粗量化分群 + nprobe 掃描 + 暴力對照）

粗量化（coarse quantization）直接重用上方 PQ 的決定性 k-means 引擎（同一套初始化/tie-break/收斂 規則），對完整 4 維向量（不切子空間）訓練 k=2 群；依收斂後的群指派攤平出倒排清單（各群成員依原 向量索引升冪排列）。查詢：先算查詢對各群質心的距離平方，由近到遠排序（tie-break 取群索引小）取前 nprobe 個為 probedGroups，只在這些群的候選內逐一計算精確距離平方，取最小者為結果；scanned=候選數， 與獨立暴力全算的真最近鄰同幀對照，nprobe 太小可能漏掉真正最近鄰，本頁誠實標示。

固定資料：與上方 PQ 相同的 8 個 4 維向量；粗量化 k=2 群（重用 pq.js 之 kMeans 引擎，決定性初始質心 取索引 0、2）。查詢固定跑三輪：Qa=[2,3,8,9](nprobe=1，命中真最近鄰) → Qb=[2,2,3,2](nprobe=1，漏掉 真最近鄰) → Qb=[2,2,3,2](nprobe=2，找回真最近鄰)。
累計掃描/比較次數（scans）：0 階段：kmeans
列 = 8 個 4 維向量（索引 0-7，與上方 PQ 使用同一組資料）；欄 0-3 = 原始座標（常數）； 欄 4 = 粗量化群指派（群 0/1）；欄 5 = 掃描標記（該向量與「目前查詢」的精確距離平方，只在被掃描 到時寫入，不同查詢輪次覆寫同一格，故終幀掃描欄反映的是最後一輪查詢 Qb(nprobe=2) 的掃描結果—— 該輪掃遍全部 8 點，故終幀掃描欄=逐向量對 Qb 的精確距離平方）。藍色外框（active）標示本步驟正在 掃描的列；粉紅（pivot）標示目前最小距離所在的列。
教學縮尺：本頁僅 8 個向量、k=2 群，nprobe=2 時掃描量（8）等同暴力全算（8），完全看不 出速度優勢——IVF 的優勢要在十億級向量、生產粗量化群數遠大於 2（常見 √n 量級）、nprobe 遠小於 群數的設定下才會顯現，這裡只看得出「粗篩 + 漏標代價」長什麼樣子。
誠實揭露——nprobe 太小可能漏掉真最近鄰：查詢 Qb=[2,2,3,2] 在 nprobe=1 時只探最近的 1 個群，真正最近鄰落在未被探索的另一群，結果漏標；把 nprobe 提高到 2（探索全部群，等同暴力 全算）才找回真正最近鄰，下方查詢對照表逐列列出三輪查詢的差異，漏標列會醒目標紅。
與 HNSW 互補：HNSW 負責「快找」（圖索引逐層貪婪導覽），IVF 負責「粗篩」（倒排分群 限縮候選範圍），概念上都是「用近似手法換速度」，十億級向量資料庫常見疊加使用（如 FAISS IndexIVFPQ：先用 IVF 粗篩候選群，群內再用 PQ 壓縮向量並計算 ADC 距離）。

質心 / 倒排清單（centroids / groups）

查詢對照表（IVF 結果 vs 暴力全掃真值）

查詢nprobe探索群IVF 結果暴力 NNscannedtotal漏標

已執行操作紀錄（opLog）

（空）