Wewnątrz baz danych wektorowych: IVF, drzewa, HNSW i kwantyzacja iloczynowa

Terminy takie jak RAG, bazy danych wektorowych, wyszukiwanie i dzielenie na fragmenty są ciągle używane, a brzmią poważniej, niż w rzeczywistości są. Ten tekst zaczyna się od bazy danych wektorowych: czego one przechowują i jak faktycznie działa wyszukiwanie w nich.

Pochodzenie wektorów

Modele embeddingów, szkolenie na ogromnych zbiorach tekstu, przekształcają znaczenie zdania w listę liczb. Niektóre z nich są dostępne online, np. modele embeddingów tekstowych OpenAI i Gemini od Google. Inne działają lokalnie, jak rodzina modeli embeddingów Qwen3 o pojemności 8B, 4B i 0,6B, lub model Jina v5 text-small z około 677 milionami parametrów. Przesuwając swój tekst przez jeden z tych modeli, otrzymuje się wektor, który można zapisać i później odzyskać.

Słownictwo

W każdej bazie danych wektorowych pojawia się kilka kluczowych terminów:

• Kolekcja. Przestrzeń nazw zawierająca punkty, które mają tę samą stałą wymiarowość oraz tę samą miarę odległości.
• Punkt. Wektor wraz z jego identyfikatorem i danymi metadanych.
• Miara odległości. Sposób mierzenia bliskości, zazwyczaj podobieństwo kosinowe, iloczyn skalarny lub odległość euklidesowa.
• Upsert. Operacja polegająca na wprowadzaniu danych, czyli dodawaniu nowych punktów i aktualizowaniu istniejących.
• Wyszukiwanie. Operacja zapytania, dla której istnieją wszystkie pozostałe funkcje.

Intuicja: dokładne versus przybliżone

Naiwny sposób na znalezienie wektorów powiązanych z zapytaniem wśród 10 000 lub więcej to obliczenie podobieństwa kosinowego z każdym przechowywanym wektorem i zachowanie tych k najbliższych. Rezultatem jest zbiór dokładnych najbliższych sąsiadów. Jednak przy milionach wektorów taka metoda siłowa staje się nieracjonalna ze względu na zużycie pamięci i czasu. Dlatego systemy przeszły na szukanie przybliżonych najbliższych sąsiadów (ANN), które akceptują niewielką stratę dokładności w zamian za znaczny wzrost szybkości.

Tę kompromisową decyzję można podjąć na dwa główne sposoby. Indeksowanie zmniejsza liczbę koniecznych porównań. Kwantyzacja zmniejsza koszt każdego porównania. Razem tworzą one zestaw narzędzi ANN.

Indeksowanie, opcja pierwsza: klastrowanie za pomocą IVF

Odwrócony indeks plików (IVF) dzieli wektory na klastry, z których każdy ma środek mas. Najpierw zapytanie jest porównywane wyłącznie z centrami mas. Gdy znajdzie się najbliższy klaster, zapytanie jest porównywane tylko z wektorami w tym klastrze, a następnie wybierane są najlepsze k z nich.

Warto znać jego wady:

• Przegapiane są sąsiednie elementy znajdujące się blisko granic komórek. Jeśli prawdziwy match znajduje się w komórce, która nie została sprawdzona, nigdy nie zostanie odnaleziony. Sprawdzanie większej liczby komórek pomaga, ale spowalnia wyszukiwanie i podważa jego cel.
• Jakość spada wraz ze zmianami w danych. Klasterzy są ustalane przy tworzeniu indeksu, więc nowe dane nadal trafiają do starych komórek, co powoduje pogorszenie jakości wyszukiwania. Konieczne są okresowe ponowne budowanie indeksu.

Nierówne klastry sprawiają, że szybkość jest nieprzewidywalna. Niektóre komórki rosną ogromnie, podczas gdy inne pozostają małe, więc zapytanie trafiające do dużej komórki jest wolne, natomiast to trafiające do małej komórki jest szybkie.

Wymaga danych treningowych na wstępie. Indeks nie może zostać utworzony, dopóki nie ma wystarczająco dużo danych, aby utworzyć sensowne klastry, co stanowi problem dla aplikacji, które zaczynają od zera.

Dwa ustawienia są trudne do dostosowania. Zarówno liczba klastrów, jak i liczba elementów przeszukiwanych przy każdym zapytaniu wpływają na wyniki, a błędne wartości powodują wolne lub nieprecyzyjne wyszukiwanie.

Wysoka liczba wymiarów zamazuje klastry. Przy bardzo długich wektorach klastry stają się niewyraźne, więc dokładność na jednostkę pracy jest gorsza niż w przypadku HNSW.

Krótko mówiąc: IVF jest prosty i oszczędza pamięć, ale traci dokładność w pobliżu granic oraz nie radzi sobie dobrze z częstymi aktualizacjami, dlatego doskonale sprawdza się na skalę miliardów elementów w połączeniu z kwantyzacją danych, natomiast HNSW przewyższa go przy wysokodokładnych wyszukiwaniach w czasie rzeczywistym.

Indeksowanie, opcja druga: podział oparty na drzewach

Indeksowanie oparte na drzewach czerpie z idei wyszukiwania binarnego. Zamiast porównywać zapytanie z każdym wektorem, przestrzeń jest wielokrotnie dzielona na połowy, a sprawdzana jest tylko ta połowa, która zawiera zapytanie.

Aby stworzyć indeks, bierze się całą przestrzeń i dzieli ją linią podziału, następnie dzieli się każdą połowę ponownie, kontynuując aż każdy mały obszar będzie zawierał zaledwie kilka wektorów. Każdy taki obszar to liść. W dwóch wymiarach pierwszy podział może przebiegać wzdłuż osi x, następny wzdłuż osi y i tak dalej. Wszystkie te podziały tworzą drzewo binarne, w którym każdy węzeł to pytanie typu „tak” lub „nie”, na przykład czy x jest poniżej 5, a liście znajdują się u dołu.

Gdy przychodzi zapytanie, zaczyna się od korzenia i odpowiada na jedno pytanie po drugim: po lewej stronie tego podziału czy po prawej? Każda odpowiedź eliminuje połowę pozostałej przestrzeni. Po około log n pytańach, mniej więcej 20 dla miliona wektorów, dociera się do małego liścia i porównuje zapytanie z garstką wektorów znajdujących się w nim.

Jest jednak haczyk. Prawdziwy najbliższy sąsiad może znajdować się tuż za linią podziału, w niewielkiej odległości, ale w innej gałęzi, a pojedyncze drzewo nigdy by go nie dostrzegło. Dlatego biblioteki takie jak Annoy od Spotify budują wiele drzew, z których każde ma inne losowe podziały. Każde drzewo proponuje kandydatów, propozycje są łączone, a wybierane są te najlepsze. To, co jedno drzewo przeoczy, zazwyczaj dostrzega inne.

Wady:

• Problem granicy jest gorszy niż w metodzie IVF. W przypadku IVF pominięcie granicy oznacza konieczność sprawdzenia jednej komórki więcej. W drzewie błędny ruch w górnej części skierowuje wyszukiwanie do zupełnie innego obszaru.
• Rozwiązanie wymaga pamięci i zwiększa szybkość działania. Las składający się z 50 drzew oznacza konieczność przechowywania indeksu 50 razy oraz przeprowadzania 50 wyszukiwań na zapytanie, co pozwala na uzyskanie dokładności kosztem zasobów.

Długie wektory je pokonują. Drzewa dobrze funkcjonują w przestrzeni 2D, 3D, na mapach i w grach. Współczesne embeddingi mają setki lub tysiące wymiarów, w których prosta linia nie oddziela praktycznie niczego istotnego, ponieważ punkty po przeciwnych stronach mogą być niemal równoodległe. To główny powód, dla którego ta metoda straciła popularność w zastosowaniach do wyszukiwania embeddingów.

Indeks jest statyczny. Drzewa są budowane raz na podstawie istniejących danych i nie mogą łatwo przyjąć nowych wektorów. Na przykład Annoy wymaga całkowitej przebudowy, aby dodać nowe dane, co źle pasuje do zmiennych kolekcji.

Ogólnie jest przewyższana. Przy tej samej dokładności HNSW jest szybszy, a przy tej samej ilości pamięci IVF z kwantyzacją iloczynową pozwala na większą skalowalność. Drzewa pozostają głównie w systemach starszych oraz tam, gdzie ważne są małe pliki indeksów dostępne w pamięci.

Krótko mówiąc, drzewa są proste i szybkie w budowie, ale wysokowymiarowe embeddingi niszczą ich strukturę podziału i nie pozwalają na aktualizacje, więc obecnie służą głównie jako element pośredni do wyjaśniania, a nie jako rozwiązanie do użycia w produkcji.

Indeksowanie, opcja trzecia: HNSW

Hierarchical Navigable Small Worlds, czyli HNSW, to technika leżąca u podstaw większości baz danych wektorowych. Organizuje ona wektory w postaci grafu składającego się z kilku warstw. Warstwy górne zawierają jedynie kilka wektorów z długodystansowymi powiązaniami, podobnymi do autostrad łączących miasta, natomiast warstwy dolne zawierają coraz więcej wektorów z krótszymi powiązaniami, aż do warstwy najniższej, która obejmuje wszystkie wektory.

Poszukiwanie rozpoczyna się od góry i chciwie przemieszcza się w kierunku sąsiedniego węzła najbliższego zapytaniu. Gdy nie ma bliższego sąsiada, schodzi o jeden poziom i powtarza proces od tego miejsca, używając bardziej szczegółowych powiązań. Na najniższym poziomie bada szerszy obszar sąsiedztwa i zwraca najlepsze wyniki. Długie skoki szybko pokonują dużą odległość, a krótkie ruchy udoskonalają odpowiedź, dlatego liczba porównań pozostaje niska nawet przy bardzo dużych zbiorach.

Kilka parametrów kontroluje równowagę między szybkością a dokładnością:

• M określa, ile powiązań zachowuje każdy wektor. Więcej powiązań poprawia dokładność i wskaźnik odnalezienia, ale zużywa więcej pamięci.
• efConstruction określa, jak szerokie ma być obszar poszukiwań podczas budowy grafu. Wyższe wartości dają lepszy graf, ale powolniejszą jego budowę.
• efSearch określa szerokość listy kandydatów podczas wyszukiwania. Jej zwiększenie powoduje jednoczesny wzrost dokładności i opóźnienia.

Zrozumienie, w jaki sposób zapytanie przechodzi przez poszczególne warstwy oraz jak te ustawienia kształtują jego trasę, wyjaśnia, dlaczego ich zmiana wpływa na zachowanie wyszukiwarki.

Kwantyzacja: obniżanie kosztu każdego porównania

Indeksowanie zmniejsza liczbę porównań. Kwantyzacja obniża koszt każdego z nich. Jeden wektor o 1536 wymiarach i wartościach typu 32-bitowe float zajmuje 1536 razy 4, czyli 6144 bajty. Dla miliarda wektorów oznacza to terabajty pamięci, co jest znacznie więcej, niż mieści się w RAM.

Kwantyzacja iloczynowa

Kwantyzacja produktowa dzieli każdy duży wektor na mniejsze fragmenty o równej długości. Wektor 16-wymiarowy może stać się na przykład czterema fragmentami po cztery wymiary. Dla każdej pozycji fragmentu trenowany jest księga kodów na podstawie przechowywanych danych, zawierająca 256 wpisów, z których każdy reprezentuje typowy podwektor. Każdy fragment jest następnie zastępowany numerem najbliższego wpisu z księgi kodów, który wymaga zaledwie jednego bajtu.

Zatem wektor, który zajmował tysiące bajtów, staje się krótkim ciągiem małych liczb całkowitych. Aby przeprowadzić wyszukiwanie, zapytanie jest dzielone w ten sam sposób, a odległości do wpisów z księgi kodów są obliczane raz i ponownie wykorzystywane podczas wyszukiwania każdego przechowywanego wektora. Obliczenia są bardzo przybliżone, ale przyspieszenie i oszczędności pamięci są znaczne.

Wybór spośród nich

Szybkie porównanie podsumowuje sytuację:

• IVF jest prosty i wymaga niewiele pamięci. Można go połączyć z kwantyzacją wektorów w celu obsługi bardzo dużych, statycznych zbiorów.
• Drzewa są łatwe do zrozumienia i tanie w budowie, ale nadają się do danych o niskiej liczbie wymiarów i niezmieniających się wartościach.
• HNSW zapewnia wysoką dokładność oraz szybkie wyszukiwanie w czasie rzeczywistym, ale wymaga większej ilości pamięci.
• Kwantyzacja wektorów kompresuje wektory i przyspiesza obliczanie odległości, powodując kontrolowaną utratę precyzji; może być łączona z powyższymi indeksami.

Znajomość tych kompromisów pomaga podjąć decyzję o tym, kiedy odpowiednie jest przybliżone wyszukiwanie, który algorytm pasuje do danego obciążenia, a kiedy siła bruta pozostaje najlepszym rozwiązaniem, np. w przypadku małych zbiorów, gdzie dokładność nie ma dużego znaczenia.

Literatura pokrewna

• Debugowanie łańcucha przetwarzania, a nie modelu LLM: model mentalny do rozwiązywania problemów w RAG — Gdy bot RAG podaje błędne odpowiedzi, rzadko jest to wina modelu. Śledź błędy na etapach pobierania danych, wyszukiwania, generowania, oceny oraz pętli agencyjnych, aby znaleźć uszkodzony element.
• Praktyczne notatki: Granice wyszukiwania wektorowego w RAG — Podobieństwo kosinowe i inne — Szczegółowy przewodnik po praktycznych notatkach dotyczących ograniczeń wyszukiwania wektorowego w RAG — podobieństwa kosinowego oraz innych aspektów, wraz z kontraktami, kontrolami i gotowymi fragmentami kodu dla zespołów wdrażających ten model.