IVF
Jak działa
Trening (offline): (1) pobierz próbkę zbioru (np. 1–5%), (2) uruchom k-means z k = nlist i otrzymaj centroidy c₁…c_nlist, (3) dla każdego wektora z bazy znajdź najbliższy centroid i dopisz go do listy odwróconej tej komórki. Indeks fizycznie to słownik: centroid → tablica (id wektora, wektor). Zapytanie: (a) policz odległości od q do wszystkich nlist centroidów — koszt O(nlist · D), (b) wybierz nprobe komórek o najmniejszej odległości, (c) zeskanuj wektory z wybranych list i utrzymuj heap top-k, (d) zwróć top-k. Klucz to dobranie nlist (typowo √N — np. nlist=4096 dla 16M wektorów) i nprobe (zwykle 1–10% nlist). Wariant IVF-PQ zastępuje pełne wektory w listach kodami PQ (np. 8–16 bajtów per wektor) — odległości liczone są przez Asymmetric Distance Computation (ADC) z pretrenowanej tablicy LUT, co dramatycznie obniża zużycie RAM i przyspiesza skan komórki. IVF-OPQ dodaje wstępną rotację ortogonalną optymalizującą rozproszenie wymiarów między subkwantyzery PQ.
Rozwiązany problem
Dokładne k-NN na milionach lub miliardach wektorów wymaga przeszukania całego zbioru przy każdym zapytaniu, co jest niewykonalne czasowo. IVF rozwiązuje ten problem przez wstępne partycjonowanie zbioru: zamiast O(N · D) operacji na zapytanie wystarczy O((nlist + nprobe · N/nlist) · D), a parametr nprobe daje administratorowi twardą kontrolę nad balansem recall vs. latency.
Komponenty
Wytrenowane centroidy k-means definiują nlist komórek Voronoi. Liczba i jakość centroidów decydują o tym, jak rozkład danych mapuje się na listy odwrócone.
Oficjalna
Dla każdego centroida przechowywana jest lista ID i (opcjonalnie skompresowanych) wektorów przypisanych do jego komórki — analogicznie do inverted index w wyszukiwaniu tekstowym.
Podczas zapytania liczone są odległości q→centroid i wybierane nprobe najbliższych komórek. nprobe to główny pokrętło recall/latency.
W wariancie IVF-PQ wektory w listach trzymane są jako krótkie kody PQ; odległości liczone są z LUT przez Asymmetric Distance Computation, co radykalnie obniża RAM i przyspiesza skan.
Oficjalna
Implementacja
Jeśli próbka do k-means nie reprezentuje rozkładu produkcyjnego (np. zła stratyfikacja, za mały rozmiar), powstają „mega-komórki" zawierające większość danych, co degraduje recall i niweluje zysk z indeksu.
Domyślne nprobe=1 daje często recall poniżej 50% na realnych zbiorach. To najczęstsze źródło „IVF jest słaby" w benchmarkach.
Mieszanie metryk (cosine vs L2) lub brak L2-normalizacji embeddingów dla cosine prowadzi do całkowicie błędnych centroidów i wyników wyszukiwania.
IVF jest semi-statyczny — gdy rozkład danych dryfuje, centroidy przestają być reprezentatywne, recall spada. Dodawanie wektorów bez retreningu pogłębia problem.
W IVF-PQ wymiar D musi być podzielny przez m. Wybór m, który nie pasuje (np. m=8 dla D=384 dobre, m=10 — błąd) powoduje błędy konstrukcji lub konieczność paddingu, a źle dobrane m drastycznie obniża recall.
Ewolucja
Pomysł indeksu odwróconego dla cech wizualnych: każdy „visual word" (centroid) ma listę dokumentów, w których występuje. Praktyczna geneza IVF dla wektorów.
Połączenie IVF z PQ („Product Quantization for Nearest Neighbor Search", IEEE TPAMI 2011) — fundament współczesnych ANN w skali miliardów.
Facebook AI Research udostępnia FAISS — najpopularniejszą implementację IVF i jej wariantów, z akceleracją GPU.
Milvus, Qdrant, Weaviate, pgvector i inne wystawiają IVF / IVF-PQ jako podstawowy indeks ANN obok HNSW.
Hiperparametry (konfigurowalne osie)
Liczba centroidów k-means / komórek Voronoi. Większe nlist = krótsze listy = szybszy skan, ale większy koszt selekcji centroidów i dłuższy trening. Typowo nlist ≈ √N.
Liczba komórek odwiedzanych podczas zapytania. Główne pokrętło recall vs latency — większe nprobe = wyższy recall i wolniejsze zapytanie.
Liczba wektorów użytych do treningu kwantyzatora k-means. Zalecane ≥ 30 · nlist; zbyt mała próbka prowadzi do nierównych komórek i degradacji recall.
Wariant IVF-PQ: liczba pod-kwantyzerów PQ. Wektor dimD jest dzielony na m równych segmentów, każdy kwantyzowany niezależnie. Większe m = wyższy recall, większy RAM.
Złożoność obliczeniowa
Złożoność czasowa: O((nlist + nprobe · N/nlist) · D) per query. Złożoność przestrzenna: O(nlist · D + N · D) (IVF) / O(nlist · D + N · b_PQ) (IVF-PQ).
Wąskie gardło obliczeniowe
Najwięcej cykli zjada liniowy skan wektorów w nprobe wybranych komórkach. Dla IVF-Flat to dot-product na pełnych wektorach, dla IVF-PQ to ADC z tablicą LUT — w obu przypadkach to operacje wektorowe na CPU.
Paradygmat wykonania
Tylko nprobe z nlist komórek jest aktywnych na zapytanie — paradygmat „sparse cell activation".
Równoległość
Zapytania są niezależne. Wewnątrz jednego zapytania skan różnych komórek można też puścić równolegle — IVF jest klasycznie data-parallel.
Wymagania sprzętowe
Skanowanie list i obliczanie odległości to gęste operacje wektorowe — idealne dla SIMD CPU (AVX2/AVX-512). IVF-PQ z ADC dodatkowo intensywnie korzysta z LUT, które trzymają się w cache L1/L2.
FAISS GPU akceleruje IVF / IVF-PQ — duża równoległość zapytań i regularne pętle pasują do GPU, choć Tensor Cores wykorzystywane są ograniczenie (operacje nie są klasycznym GEMM).
IVF działa wydajnie na ARM (Graviton, Apple Silicon) i x86; wymaga głównie dobrej przepustowości pamięci i SIMD.