PQ
Jak działa
Trening (offline): (1) zbierz reprezentatywną próbkę wektorów z bazy, (2) wybierz hiperparametry — liczbę podkwantyzerów m (musi dzielić D) oraz liczbę bitów na kod (zwykle 8, czyli k=256 centroidów per podprzestrzeń), (3) podziel każdy wektor próbki na m segmentów po D/m wymiarów, (4) uruchom k-means oddzielnie na każdym z m zbiorów segmentów — otrzymujesz m kodbooków po 256 centroidów. Encoding bazy: każdy wektor v dzieli się na (v₁,…,v_m), dla każdego segmentu znajduje się najbliższy centroid c_j w odpowiednim kodbooku, wektor zapisywany jest jako m bajtów (id centroidów). Zapytanie (ADC): (a) podziel zapytanie q na (q₁,…,q_m), (b) dla każdej podprzestrzeni j oblicz tablicę LUT_j[i] = dist(q_j, c_j^i) dla i=0..255 — łącznie m × 256 obliczeń, (c) dla każdego wektora z bazy o kodzie (i₁,…,i_m) odległość przybliżona = Σ LUT_j[i_j] — m sumowań plus m lookupów w cache, (d) utrzymuj top-k heap. Wariant OPQ poprzedza PQ ortogonalną rotacją R wyznaczaną tak, by zminimalizować błąd kwantyzacji — istotnie poprawia recall na danych skorelowanych między wymiarami. Wariant RQ (Residual Quantization) iteracyjnie kwantyzuje residua — kolejne kodbooki uczą się różnicy między wektorem a jego dotychczasową aproksymacją.
Rozwiązany problem
Embeddingi z modeli AI (BERT, CLIP, OpenAI) mają zwykle D=384–1536 wymiarów po 4 bajty (float32), co daje 1.5–6 KB na wektor. Dla miliarda wektorów to 1.5–6 TB RAM — niewykonalne na pojedynczym serwerze. PQ rozwiązuje ten problem: ten sam miliard wektorów po PQ zajmuje 16–64 GB RAM (kompresja 50–100×) przy minimalnym spadku recall, co umożliwia trzymanie ogromnych indeksów na jednym węźle i kilkukrotnie tańszą infrastrukturę.
Komponenty
Wektor D-wymiarowy jest dzielony na m rozłącznych segmentów po D/m wymiarów. m musi być dzielnikiem D; dobór m kontroluje trade-off kompresja vs jakość.
m niezależnych kodbooków, każdy zwykle z k=256 centroidami (8 bitów). Trenowane k-means na próbce z odpowiedniej podprzestrzeni.
Oficjalna
Reprezentacja każdego wektora jako m-tuple indeksów centroidów (m bajtów dla k=256). To właśnie tę reprezentację trzymają indeksy w RAM/SSD.
Wstępne obliczenie LUT_j[i] = dist(q_j, c_j^i) per podprzestrzeń, potem skan bazy = m lookupów + m sumowań per wektor. Symmetric DC kwantyzuje też zapytanie (szybciej, ale gorszy recall).
OPQ uczy ortogonalnej macierzy R, która rotuje wektory tak, by wariancja była równomiernie rozłożona między podprzestrzenie — zwykle 2–5 p.p. wyższy recall przy tej samej kompresji.
Oficjalna
Implementacja
Klasyczny PQ wymaga, by D było dzielnikiem m. Np. dla D=384 dopuszczalne m: 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192. Wybór m=10 lub m=20 spowoduje błąd lub konieczność paddingu.
PQ jest agnostyczne wobec metryki, ale jeśli używasz cosine, musisz zł2-normalizować embeddingi przed treningiem kodbooków — inaczej centroidy będą reprezentować różne normy zamiast różnic kierunkowych.
Kodbooki k-means są zafiksowane po treningu. Jeśli próbka treningowa nie pokrywa rozkładu produkcyjnego, recall dramatycznie spada (efekt drift).
Dla embeddingów AI (BERT/CLIP/OpenAI) wymiary są często skorelowane. Klasyczny PQ daje wtedy znacząco gorszy recall niż OPQ przy tym samym budżecie bajtów.
ADC daje przybliżone odległości. Bez re-rankingu top-N kandydatów pełnymi wektorami z dysku, recall@10 może być znacząco gorszy niż recall@100 po re-rankingu.
Ewolucja
Oryginalna praca wprowadza PQ wraz z ADC i dwoma trybami: SDC (symmetric) i ADC (asymmetric). Eksperymenty na SIFT/GIST pokazują kompresję 32× przy niewielkim spadku recall.
OPQ uczy ortogonalnej rotacji minimalizującej błąd kwantyzacji. Stało się domyślnym wariantem PQ w FAISS.
Rodzina metod (AQ, RQ, LSQ) generalizująca PQ — wektor jako suma centroidów z kilku kodbooków. Wyższy recall kosztem droższego encodingu.
Meta AI udostępnia FAISS, w tym PQ4 Fast Scan z AVX-512 — przełom w wydajności PQ na CPU.
ScaNN poprawia PQ przez funkcję straty świadomą dot-product (anizotropowa) — wyższy recall dla cosine/IP, szeroko używany w produkcji Google.
Hiperparametry (konfigurowalne osie)
Liczba podprzestrzeni / bajtów per wektor po PQ. Większe m = wyższy recall i większa pamięć; m musi dzielić D.
Liczba bitów na kod centroida (k = 2^bits). 8 bitów (k=256) to standard z powodu dopasowania do bajtów i SIMD; 4 bity → 16 centroidów (PQ4) — ekstremalna kompresja, lower recall.
Liczba wektorów do treningu kodbooków. Zalecane ≥ 30 · k per podprzestrzeń (FAISS); za mała próbka → niereprezentatywne centroidy.
Wybór: brak rotacji (klasyczny PQ), OPQ (uczona ortogonalna), random rotation (tani kompromis). OPQ niemal zawsze daje +2-5 p.p. recall.
Złożoność obliczeniowa
Złożoność czasowa: Encoding: O(D · k); Query (ADC): O(m · k) LUT + O(m) per database vector. Złożoność przestrzenna: O(N · m) per dataset + O(m · k · D/m) = O(m · k · D/m) codebooks.
Wąskie gardło obliczeniowe
Wąskim gardłem jest gęsty skan tablicy LUT + akumulacja per wektor. Współczesne implementacje (FAISS, ScaNN) używają SIMD/AVX-512 do równoległego sumowania LUT dla wielu wektorów na raz (SIMD-based ADC, „PQ Fast Scan").
Paradygmat wykonania
W odróżnieniu od IVF/HNSW, PQ przy zapytaniu zwykle skanuje WSZYSTKIE wektory z (sub)zbioru — siła tkwi w taniości pojedynczej operacji (LUT lookup), nie w sparsity.
Równoległość
Encoding i skan są trywialnie data-parallel; trening k-means można puścić per podprzestrzeń równolegle.
Wymagania sprzętowe
PQ Fast Scan zaprojektowane pod AVX2/AVX-512 — równoległe sumowanie LUT dla wielu wektorów per instrukcja. LUT trzymają się w L1, co daje throughput rzędu setek mln porównań/s na rdzeń.
FAISS GPU akceleruje IVF-PQ i PQ — duże batche zapytań × baza dobrze pasują do GPU memory bandwidth; Tensor Cores wykorzystywane częściowo (operacje to lookup + add, nie GEMM).
PQ działa wydajnie na ARM (NEON) i x86 (AVX). Kluczowa jest przepustowość pamięci i cache locality, nie konkretna ISA.