HNSW
Jak działa
Budowa: (1) Dla każdego nowego wektora losuje się jego maksymalną warstwę l ~ Geometric(1/ln(M)) — większość ląduje w l=0, nieliczne sięgają wyżej. (2) Wektor jest wstawiany od warstwy l w dół. W każdej warstwie szuka się ef_construction kandydatów na sąsiadów (rozszerzone wyszukiwanie greedy), a następnie wybiera M (lub M_max0 dla warstwy 0) finalnych sąsiadów przez heurystykę pruningu — preferuje się punkty leżące w „różnych kierunkach" od wstawianego węzła, nie tylko najbliższe. (3) Krawędzie są dwukierunkowe; gdy sąsiad przekroczy M_max połączeń, jego krawędzie też są re-pruningowane. Wyszukiwanie: (a) start od entry pointu w najwyższej istniejącej warstwie, (b) greedy search w każdej warstwie aż do lokalnego minimum, ze stałym ef=1 w warstwach >0, (c) w warstwie 0 uruchamia się rozszerzony search z priority queue rozmiaru ef (search-time), (d) zwracane jest top-k z tej kolejki. Parametry M (typowo 16–48), ef_construction (100–500) i ef (50–500) sterują trade-offem build time / memory / recall / latency. Filtrowanie (np. WHERE category='X') zwykle realizowane jest jako filtered search z dynamicznym ef lub jako oddzielne grafy per kategoria.
Rozwiązany problem
Dokładne k-NN w przestrzeniach wysokowymiarowych ma koszt O(N · D) per zapytanie — niewykonalne dla miliona wektorów przy SLO milisekundowym. IVF i drzewa KD/ball-tree zawodzą w wysokich wymiarach z powodu „przekleństwa wymiarowości". HNSW rozwiązuje ten problem grafowo: zapewnia empirycznie czas O(log N) i recall ≥ 95% przy bardzo niskim opóźnieniu, dzięki czemu jest dziś faktycznym standardem do wyszukiwania wektorowego dla embeddingów AI w skali pojedynczego serwera.
Komponenty
Warstwy 0..L: wyższe rzadkie (skróty long-range), niższe gęste. Liczba warstw wektora losowana geometrycznie z parametrem 1/ln(M).
W warstwach >0: ef=1 (czysta nawigacja). W warstwie 0: priority queue rozmiaru ef (search-time) kontroluje recall/latency.
Zamiast brać po prostu M najbliższych kandydatów, HNSW preferuje kandydatów rozłożonych w różnych kierunkach (relative-neighborhood-graph style). Klucz do wysokiego recall.
Oficjalna
Każdy węzeł ma w każdej warstwie listę co najwyżej M (M_max0 w warstwie 0) krawędzi. Bidirectional — wstawianie aktualizuje obie strony.
Implementacja
Domyślne ef=10–32 daje recall <90% na realnych embeddingach AI (D≥384). To najczęstsze źródło „HNSW jest słaby" w blogach benchmarkowych.
Klasyczny HNSW jest append-mostly. Usunięcia oznaczane są jako tombstones, a wstawianie nowych wersji nie zawsze przewiązuje krawędzi optymalnie — po wielu mutacjach recall spada i konieczny jest pełny rebuild.
Filtry typu WHERE category='X' aplikowane post-hoc na top-ef wynikach mogą zwrócić mniej niż k pasujących wektorów. Trzeba dynamicznie zwiększać ef albo używać filtered-HNSW (predykat sprawdzany podczas traversal).
HNSW trzyma pełne wektory + krawędzie w RAM. Dla 100M wektorów D=1536 (OpenAI embeddings) przy M=32 to ~700 GB RAM — szybko staje się ekonomicznie nieracjonalne.
Entry point HNSW to pojedynczy węzeł najwyższej warstwy. Po pełnym rebuildzie nieoptymalny entry point podbija liczbę kroków per zapytanie — czasem widoczne jako regresja latency bez zmiany recall.
Ewolucja
Poprzednik HNSW: jedna warstwa, idea grafu „small world" z krótkimi i długimi krawędziami. Już konkurencyjny, ale wolniejszy od HNSW.
Pierwsza publikacja HNSW: dodanie warstw hierarchicznych i heurystyki pruningu różnorodności. Przełom w jakości i prędkości ANN.
Open-source HNSW w nmslib (Non-Metric Space Library) — pierwsza szeroko używana implementacja, źródło dla wielu portów.
Oficjalna publikacja w IEEE TPAMI. Yury Malkov udostępnia hnswlib — wydzieloną, szybką bibliotekę C++/Python wykorzystywaną do dziś jako referencja.
Qdrant, Pinecone, Weaviate, pgvector (≥ 0.5), Elasticsearch (8.0+), OpenSearch i Milvus — wszystkie wystawiają HNSW jako podstawowy lub jedyny indeks ANN.
Qdrant, Milvus, Lucene i pgvector dodają kompresję wektorów w grafie HNSW (PQ, scalar quantization, INT8) by zmniejszyć RAM bez utraty grafu.
Hiperparametry (konfigurowalne osie)
Maksymalna liczba sąsiadów per węzeł w warstwach >0 (w warstwie 0 zwykle M_max0 = 2·M). Większe M = wyższy recall, większe RAM, wolniejsza budowa.
Rozmiar dynamicznej listy kandydatów podczas budowy grafu. Większe = lepsza jakość grafu (wyższy recall) kosztem dłuższej budowy.
Rozmiar priority queue podczas zapytania w warstwie 0. Główne pokrętło runtime recall vs latency — można zmieniać per-zapytanie bez przebudowy.
Maksymalna liczba sąsiadów w warstwie 0 (najgęstszej). Typowo 2·M; podbicie poprawia recall ale podwaja RAM warstwy 0.
Złożoność obliczeniowa
Złożoność czasowa: Query: O(log N) (empirical); Insert: O(log N · ef_construction · D). Złożoność przestrzenna: O(N · (D · 4B + M · 8B · L_avg)).
Wąskie gardło obliczeniowe
Większość czasu zapytania to dot products / L2 distance między query a wektorami napotkanych węzłów. Implementacje SIMD (AVX-512, NEON) są kluczowe dla wydajności.
Paradygmat wykonania
Tylko niewielki podzbiór węzłów grafu jest odwiedzany per zapytanie (sparse traversal). To stoi w kontraście do PQ (dense scan) i bliżej DiskANN.
Równoległość
Zapytania są niezależne — throughput skaluje się liniowo z liczbą rdzeni. Budowa grafu jest częściowo równoległa (lock per node przy aktualizacji krawędzi).
Wymagania sprzętowe
Wyszukiwanie HNSW dominują obliczenia dystansu (dot product / L2) na małych zestawach wektorów per krok. AVX2/AVX-512 zapewnia wymaganą przepustowość. GPU nie ma przewagi z powodu małych batchy per zapytanie i nieregularnego dostępu do pamięci.
Implementacje HNSW działają wydajnie na ARM (Graviton, Apple Silicon, NEON) i x86. Kluczowa jest przepustowość pamięci i SIMD, nie konkretna ISA.
Nieregularne odczyty grafu i mały batch per zapytanie nie mapują się dobrze na Tensor Cores zaprojektowane pod gęste GEMM. GPU może przyspieszyć budowę indeksu i ekstremalnie wysokoprzepustowe scenariusze, ale nie typowe pojedyncze zapytanie.