08 · LLM · 4 min czytania · Interaktywne · aktualizacja
Jak działa wyszukiwanie wektorowe i czym są indeksy typu HNSW?
W skrócie
Wyszukiwanie wektorowe znajduje wektory najbliższe zapytaniu. Przy milionach wpisów używa indeksów przybliżonych, które oddają trochę trafności za szybkość.
Co to jest
Wyszukiwanie wektorowe (semantyczne) to znajdowanie w zbiorze wektorów tych, które są najbliżej wektora zapytania według wybranej miary: podobieństwa cosinusowego, iloczynu skalarnego lub odległości euklidesowej. Teksty, obrazy czy produkty zamienia się najpierw na embeddingi, więc „najbliższy wektor” oznacza „najbardziej podobną treść”. To problem k najbliższych sąsiadów (kNN); w dużej skali rozwiązuje się go w przybliżeniu (ANN, approximate nearest neighbors).
W odróżnieniu od wyszukiwania po słowach kluczowych, wektorowe dopasowuje znaczenie: zapytanie „jak wziąć wolne” znajdzie akapit o „urlopie wypoczynkowym”, choć nie mają wspólnych słów. Jest podstawą RAG, wyszukiwarek semantycznych, systemów rekomendacji i wykrywania duplikatów.
Bazy wektorowe to w gruncie rzeczy indeks ANN plus zwykłe funkcje bazy danych: filtrowanie po metadanych, aktualizacje, replikacja.
Mechanizm — dlaczego tak działa
Miary podobieństwa. Cosinus mierzy kąt między wektorami i ignoruje ich długość: cos(u, v) = u·v / (‖u‖·‖v‖). Iloczyn skalarny uwzględnia też długość, co bywa celowe (dłuższy wektor = „silniejszy” sygnał). Odległość euklidesowa mierzy dystans punktów. Dla wektorów znormalizowanych do długości 1 wszystkie trzy dają ten sam ranking, bo ‖u − v‖² = 2 − 2·cos(u, v). Dlatego embeddingi zwykle się normalizuje — i trzeba używać miary, z którą trenowano model embeddingów.
Dlaczego przeszukiwanie wszystkiego jest drogie. Dokładne wyszukiwanie porównuje zapytanie z każdym wektorem: n · d mnożeń. Przy milionach wektorów i setkach wymiarów to już zauważalny koszt na każde zapytanie, a klasyczne struktury przestrzenne (drzewa k-d) w wysokich wymiarach przestają pomagać — to przekleństwo wymiarowości.
HNSW — graf małego świata. Malkov i Yashunin (2020) budują wielopoziomowy graf: każdy wektor łączy się krawędziami z kilkoma bliskimi sąsiadami, a wyższe poziomy zawierają coraz mniej węzłów z dalekimi połączeniami, jak autostrady nad siecią lokalnych dróg. Wyszukiwanie zaczyna od góry, zachłannie przechodzi do sąsiada bliższego zapytaniu, schodzi poziom niżej i powtarza. Odwiedza się ułamek zbioru, a czas rośnie w przybliżeniu logarytmicznie z liczbą wektorów. Ceną jest pamięć na graf i to, że czasem prawdziwy najbliższy sąsiad zostanie pominięty.
IVF i kwantyzacja produktowa. Inna rodzina metod dzieli przestrzeń na skupiska (k-średnich) i przeszukuje tylko kilka najbliższych zapytaniu. Kwantyzacja produktowa (Jégou i in., 2011) dzieli wektor na kawałki i każdy zapisuje jako numer najbliższego centroidu — wektor 768 liczb kurczy się do kilkudziesięciu bajtów. Biblioteka FAISS (Johnson i in., 2019) łączy te techniki.
Kompromis trafności i szybkości. Jakość indeksu ANN mierzy się recall@k: jaki odsetek prawdziwych k najbliższych sąsiadów zwrócił. Parametry (w HNSW m.in. liczba krawędzi i szerokość przeszukiwania) przesuwają punkt na krzywej: więcej pamięci i czasu — wyższy recall. Pamiętaj też, że „najbliższy wektor” to nie zawsze „najlepsza odpowiedź”: jakość wyników zależy przede wszystkim od modelu embeddingów.
Na przykładzie
Weźmy wektor zapytania a = (3, 4, 0) i dwa dokumenty: b = (6, 8, 0) oraz c = (4, 3, 0). Iloczyn skalarny a·b = 50, cosinus = 1 (ten sam kierunek). Dla c: a·c = 24, cosinus 24 / (5 · 5) = 0,96. Odległość euklidesowa daje odwrotny ranking: ‖a − b‖ = 5, a ‖a − c‖ ≈ 1,41. Wybór miary zmienił „najbliższy” dokument. Po normalizacji wektorów do długości 1 rozbieżność znika.
Teraz skala. Milion embeddingów po 768 wymiarów w float32 to 10⁶ · 768 · 4 B ≈ 3,07 GB pamięci, a dokładne przeszukanie to 768 mln mnożeń na każde zapytanie. Kwantyzacja produktowa do 96 bajtów na wektor zmniejsza indeks do 96 MB. Ciekawostka z wysokich wymiarów: cosinus dwóch losowych wektorów w 768 wymiarach ma średnią 0 i odchylenie standardowe około 1/√768 ≈ 0,036 (symulacja na 1000 parach dała 0,036). Losowe wektory są niemal prostopadłe, więc nawet podobieństwo 0,3 jest silnym sygnałem — ale progi trzeba kalibrować dla konkretnego modelu.
W praktyce
- Do kilkudziesięciu tysięcy wektorów wystarczy dokładne przeszukiwanie:
numpy(macierz × wektor) lubsklearn.neighbors.NearestNeighbors(metric="cosine"). - W większej skali:
faiss.IndexFlatIP(dokładnie),faiss.IndexHNSWFlat,faiss.IndexIVFPQ(przybliżenie z kompresją). - Normalizuj wektory (
faiss.normalize_L2) i używaj iloczynu skalarnego jako cosinusa. - Mierz recall@k indeksu względem wyszukiwania dokładnego na próbce zapytań, zanim go wdrożysz.
- Typowy błąd: mieszanie wektorów z różnych modeli embeddingów lub różnych wersji jednego modelu w jednym indeksie — ich przestrzenie są nieporównywalne.
Najczęstsze pytania
- Cosinus czy iloczyn skalarny?
- Taki, z jakim trenowano model embeddingów; większość modeli zdaniowych zakłada cosinus. Po normalizacji wektorów obie miary dają identyczny ranking, a iloczyn skalarny jest szybszy.
- Czy wyszukiwanie wektorowe zastąpi wyszukiwanie po słowach kluczowych?
- Nie całkiem. Słowa kluczowe lepiej radzą sobie z nazwami własnymi, kodami produktów i dokładnymi frazami. W praktyce najlepiej działa wyszukiwanie hybrydowe łączące oba rankingi.
- Czym jest baza wektorowa?
- To system przechowujący wektory razem z metadanymi i indeksem ANN, z funkcjami takimi jak filtrowanie, aktualizacje i skalowanie. Sam indeks (np. FAISS) to tylko część takiej bazy.
Źródła
- Malkov Y. A., Yashunin D. A., 2020, „Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs”, IEEE TPAMI 42(4), arXiv:1603.09320.
- Jégou H., Douze M., Schmid C., 2011, „Product Quantization for Nearest Neighbor Search”, IEEE TPAMI 33(1).
- Johnson J., Douze M., Jégou H., 2019, „Billion-scale similarity search with GPUs”, IEEE Transactions on Big Data.
- Karpukhin V. i in., 2020, „Dense Passage Retrieval for Open-Domain Question Answering”, EMNLP 2020.
- Dokumentacja FAISS, https://github.com/facebookresearch/faiss/wiki