Как работает HNSW (Hierarchical Navigable Small World) алгоритм внутренне?

Краткий тезис

HNSW (Hierarchical Navigable Small World) — это алгоритм приближённого поиска ближайших соседей (ANN), основанный на многослойном графе. Верхние слои содержат редкие связи (long jumps), позволяющие быстро перемещаться в нужную область пространства, а нижние слои — плотные связи для точного поиска. Поиск начинается с самого верхнего слоя и последовательно спускается вниз, выполняя на каждом уровне жадный обход графа. Это даёт логарифмическую сложность поиска и высокую точность, что делает HNSW стандартом для векторных БД (FAISS, Qdrant, Weaviate).

1. Термин: Приближённый поиск ближайших соседей (ANN)

Приближённый поиск ближайших соседей (Approximate Nearest Neighbor, ANN) — это класс алгоритмов, которые находят не гарантированно точных, а «достаточно близких» соседей, жертвуя точностью ради скорости. В отличие от точного поиска (kNN), ANN обрабатывает миллиарды векторов за миллисекунды.

Зачем нужен ANN в RAG

• Векторные БД хранят миллионы эмбеддингов (например, 768-мерных от text-embedding-3-small)
• Точный поиск (полный перебор) требует O(N * D) операций — неприемлемо для реального времени
• ANN даёт O(log N) или O(sqrt(N)) — приемлемо для интерактивных систем

HNSW — один из самых популярных ANN-алгоритмов (наряду с IVF, PQ, ScaNN).

2. Проблема: Почему нельзя просто построить полный граф?

Наивная идея: соединить каждый вектор с K ближайшими соседями. Тогда поиск — это жадный обход по рёбрам. Проблемы:

• Размер графа для N=1M и K=32 нужно хранить 32M рёбер — много памяти
• Качество поиска жадный обход легко застревает в локальном оптимуме (далеко от глобального ближайшего соседа)
• Скорость в худшем случае нужно обойти O(N) вершин

HNSW решает обе проблемы через иерархию и вероятностное распределение слоёв.

3. Идея: Navigable Small World (NSW)

Navigable Small World (NSW) — предшественник HNSW. Идея: построить граф, где есть как короткие связи (между близкими точками), так и длинные (между удалёнными). Длинные связи позволяют быстро «перепрыгивать» в разные области пространства — как в социальных сетях через «знакомых знакомых».

Проблема NSW при вставке новых точек длинные связи могут теряться, и граф деградирует. HNSW решает это через иерархию.

4. Иерархическая структура HNSW

HNSW строит несколько слоёв графа (обычно 5–16). Каждый слой — это подграф, содержащий подмножество точек.

Правила построения слоёв

• Самый верхний слой (Layer L): содержит ~1% всех точек, связи очень редкие (длинные прыжки)
• Средние слои ~10–30% точек, связи средней плотности
• Нижний слой (Layer 0): содержит 100% точек, связи плотные (точный поиск)

Как точка попадает на слой при вставке случайным образом выбирается уровень l по экспоненциальному распределению:

P(level = l) = exp(-l / mL)

где mL — параметр (обычно 0.3–0.5). Точка появляется на всех слоях от 0 до l.

Визуализация

Layer 2 (верхний):  ●──●──●
Layer 1 (средний):  ●──●──●──●──●
Layer 0 (нижний):   ●──●──●──●──●──●──●──●

Чем выше слой, тем меньше точек и длиннее связи.

5. Построение графа (вставка точки)

При вставке новой точки q:

1. Выбор уровня генерируем случайный l (экспоненциальное распределение)
2. Поиск точки входа начинаем с верхнего слоя, выполняем жадный обход до слоя l+1
3. Вставка на слоях от l до 0: на каждом слое:
   • Находим efConstruction ближайших соседей (параметр, обычно 100–200)
   • Соединяем q с M ближайшими из них (M — параметр, обычно 16–32)
   • Применяем эвристику pruning (обрезка): если у соседа уже много связей, удаляем самые длинные, чтобы сохранить баланс

Параметр M максимальное количество рёбер у вершины на каждом слое. Чем больше M, тем точнее поиск, но больше памяти.

Эвристика обрезки (pruning): при добавлении новой связи проверяем, не превышает ли степень вершины Mmax. Если превышает — удаляем самое длинное ребро (по евклидову расстоянию). Это сохраняет свойство small-world.

6. Поиск (жадный обход сверху вниз)

Поиск ближайших соседей для запроса q:

1. Начинаем с верхнего слоя берём точку входа (обычно первая вставленная точка)
2. На каждом слое выполняем жадный обход:
   • Идём по рёбрам, выбирая соседа, ближайшего к q
   • Повторяем, пока не достигнем локального минимума (все соседи дальше текущей точки)
3. Спуск на слой ниже берём лучшую найденную точку как стартовую для следующего слоя
4. На нижнем слое (Layer 0): выполняем более широкий поиск с параметром efSearch (обычно 100–500):
   • Используем приоритетную очередь (кучу)
   • Продолжаем, пока не найдём efSearch кандидатов
   • Возвращаем top-k из них

Псевдокод поиска

def search_hnsw(q, layers, entry_point, efSearch, k):
    # Фаза 1: спуск по верхним слоям
    curr = entry_point
    for layer in reversed(range(len(layers)-1, 0, -1)):
        curr = greedy_search(q, layer, curr)
    
    # Фаза 2: поиск на нижнем слое
    candidates = priority_queue()
    visited = set()
    candidates.push((dist(q, curr), curr))
    
    while len(candidates) < efSearch:
        d, node = candidates.pop()
        for neighbor in layers[0].neighbors[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                candidates.push((dist(q, neighbor), neighbor))
    
    return top_k(candidates, k)

7. Параметры HNSW и их влияние

Практические рекомендации

• Для высокой точности (recall@10 > 0.99): M=32, efConstruction=200, efSearch=500
• Для низкой латентности (< 10ms): M=16, efConstruction=100, efSearch=100
• Для больших датасетов (> 10M): увеличивайте mL до 0.5–0.7

8. Сравнение HNSW с другими ANN-алгоритмами

Когда выбирать HNSW

• Нужна максимальная точность (RAG с критичными ответами)
• Память не является ограничением (до 10M векторов)
• Индекс строится один раз, поиск — часто

9. Преимущества и недостатки HNSW

Преимущества

• Логарифмическая сложность поиска O(log N) в среднем
• Высокая точность recall@10 часто > 0.98
• Поддержка динамических вставок можно добавлять векторы без перестроения индекса
• Параллелизм поиск легко распараллеливается (batch processing)

Недостатки

• Высокое потребление памяти каждый вектор хранит M рёбер (32–64 int32 на точку)
• Медленная вставка efConstruction требует поиска соседей на каждом слое
• Чувствительность к размерности при D > 1000 точность падает (проклятие размерности)
• Не подходит для разреженных векторов граф строится на плотных эмбеддингах

10. HNSW в контексте Agentic RAG

В архитектуре Agentic RAG HNSW используется как основной индекс для векторной памяти агента. Агент может:

• Хранить историю диалогов в HNSW-индексе для поиска релевантных контекстов
• Использовать несколько HNSW-индексов для разных типов знаний (факты, процедуры, примеры)
• Динамически добавлять новые знания через вставку в HNSW без перестроения

Пример: агент поддержки клиентов хранит 500K предыдущих обращений. При новом запросе HNSW находит top-10 похожих кейсов за 5ms, агент использует их для генерации ответа.

Пет-проект для закрепления

Задача Реализовать упрощённый HNSW на Python с нуля (без FAISS) для поиска по 10K случайных 128-мерных векторов.

Инструменты Python, NumPy, Matplotlib (для визуализации графа).

Шаги:

1. Сгенерируйте 10K случайных векторов (np.random.randn)
2. Реализуйте класс HNSWIndex с методами insert() и search()
3. Используйте евклидово расстояние
4. Реализуйте жадный поиск на одном слое (greedy_search)
5. Добавьте иерархию: при вставке выбирайте уровень по экспоненциальному распределению
6. Реализуйте поиск с efSearch (приоритетная очередь)
7. Сравните точность с точным kNN (sklearn.neighbors.NearestNeighbors)

Ожидаемый результат

• Индекс строится за < 1 минуты
• Поиск top-10 выполняется за < 10ms
• Recall@10 > 0.90 при efSearch=100

Код-скелет

import numpy as np
from heapq import heappush, heappop

class HNSWIndex:
    def __init__(self, M=16, efConstruction=100, efSearch=100, mL=0.3):
        self.M = M
        self.efConstruction = efConstruction
        self.efSearch = efSearch
        self.mL = mL
        self.layers = []  # список слоёв, каждый слой - dict {id: neighbors}
        self.vectors = []
        self.entry_point = None
    
    def _random_level(self):
        return int(-np.log(np.random.random()) * self.mL)
    
    def insert(self, vector):
        # TODO: реализовать вставку
        pass
    
    def search(self, query, k=10):
        # TODO: реализовать поиск
        pass

Связь с другими вопросами

Навигация

• Предыдущий: 220
• Следующий: 222
• Индекс: 00. Индекс разборов