HNSW Explorer: иерархический навигационный «малый мир», визуализированный

Наблюдайте за прохождением поиска по многослойному графу — от разреженного верхнего слоя (автомагистрали) до плотного нижнего слоя (местные дороги). Перетащите точку запроса на слое 0 и настройте M / ef , чтобы увидеть, как меняется граф.

Максимальное количество соседей на узел

ef8

Пул кандидатов уровня 0

Скорость450ms

На каждом этапе

Текущий шаг

14 / 14

Поиск завершён. Top-3: [3, 10, 4].

Статистика поиска

Посещённые

17 / 30

Слои

Ввод

Узел 0

Top-3

[3, 10, 4]

Распределение слоёв

Как работает « HNSW »

Многоуровневый граф: каждому узлу случайным образом назначается максимальный уровень с использованием экспоненциального распределения. Большинство узлов находятся только на уровне 0; лишь очень немногие достигают вершины.
Внутри каждого слоя: каждый узел соединяется со своими ближайшими соседями по методу « M ». Высшие слои являются разреженными (немного узлов, длинные ребра = «магистрали»). Слой 0 является плотным (все узлы, короткие ребра = «местные дороги»).
Поиск начинается сверху: от фиксированной начальной точки по алгоритму жадного поиска продвигайтесь к соседу, ближайшему к запросу, и повторяйте до тех пор, пока не будет достигнуто улучшение.
Спуститесь на один уровень вниз и повторите: положение из предыдущего уровня становится началом прохождения следующего уровня. Каждое спускание уточняет результат за счёт более мелкозернистых граней.
Уровень 0 с методом « ef »: на нижнем уровне, вместо того чтобы останавливаться на первом локальном минимуме, метод « HNSW » поддерживает пул ef лучших кандидатов и расширяет их окрестности. Более крупный ef → более точно, но медленнее.

Почему это быстро: верхние слои действуют как индекс над индексом — вы преодолеваете огромные расстояния всего за несколько шагов, а затем увеличиваете масштаб. Для N точек поиск посещает примерно O(log N) узлов вместо N.

Что такое « HNSW »?

HNSW (Hierarchical Navigable Small World) — это основанный на графах алгоритм приближённого поиска ближайших соседей. Он организует векторы в стопку навигабельных графов «малого мира»: разреженные верхние слои с ребрами большого радиуса действия для грубой маршрутизации и плотный нижний слой с короткими ребрами для окончательного тонкого прохождения. Поиск жадно перескакивает к запросу на каждом слое, а затем спускается вниз — посещая примерно O(log N) узлов вместо сканирования всех N.

HNSW — это наиболее широко используемый векторный индекс в памяти и индекс графов по умолчанию в Milvus. Milvus также предлагает HNSW_SQ и HNSW_PQ варианты, которые квантуют хранящиеся векторы для сокращения объёма памяти за счёт небольшого снижения коэффициента восстановления.

HNSW параметры в Milvus

M (время построения): максимальное количество ребер на узел; этот регулятор соответствует ползунку, показанному выше. Типичные значения — 8–64. Более высокое значение M улучшает коэффициент восстановления и связность графа, но линейно увеличивает потребление памяти и замедляет построение.
efConstruction (время построения): размер пула кандидатов, используемый при вставке узлов. Более высокие значения позволяют построить граф лучшего качества (достигается более высокий показатель recall) за счёт более медленного построения индекса. Типичные значения составляют 100–500.
ef / ef_search (время запроса): пул кандидатов, сохраняемый во время прохода по слою 0 — основной регулятор точности извлечения и задержки во время поиска. Его значение должно быть не меньше вашего top-K. Увеличивайте его до тех пор, пока точность извлечения не перестанет расти; задержка при этом растёт примерно линейно.

HNSW vs IVF vs DiskANN

HNSW обычно обеспечивает наилучшую задержку запроса при высокой точности поиска для поиска в памяти — именно поэтому он является выбором по умолчанию, когда набор данных (плюс накладные расходы графа) помещается в RAM. Его издержки — это память и время построения: граф добавляет заметные накладные расходы на каждый вектор, а вставки выполняются медленнее, чем при назначении методом k-средних в IVF. Выбирайте IVF, если вам требуется быстрое построение индекса или агрессивная квантизация, и DiskANN, если набор данных слишком велик для RAM, но вам по-прежнему требуется высокий коэффициент восстановления.

Часто задаваемые вопросы

Что регулирует параметр M в алгоритме « HNSW »?

M ограничивает количество ребер, которые каждый узел сохраняет на каждом слое. Увеличение M улучшает связность графа — повышается точность извлечения и надежность маршрутизации — но объем памяти растёт линейно с M, а построение индекса замедляется. Значения от 8 до 64 покрывают большинство рабочих нагрузок; 16–32 — это типичный оптимальный диапазон.

В чём разница между ef и efConstruction?

Оба параметра определяют размер пула кандидатов, но применяются в разное время. Параметр « efConstruction » используется при построении индекса: он определяет, насколько тщательно каждый вставляемый узел ищет соседей, тем самым контролируя качество графа. Параметр « ef » (ef_search) используется во время запроса: он контролирует широту поиска на уровне Layer-0, жертвуя задержкой ради точности поиска при каждом запросе.

Сколько памяти требуется для индекса « HNSW »?

Приблизительно исходные векторы плюс граф: около d × 4 байт на вектор для данных типа float32, плюс порядка M × 2 × 8 байт ребер на узел. Для развертываний с ограниченным объёмом памяти Milvus предлагает HNSW_SQ и HNSW_PQ, которые квантуют хранящиеся векторы, или DiskANN, который перемещает полные векторы в SSD.

Когда следует использовать « HNSW » вместо « IVF »?

Используйте « HNSW », когда приоритетом является задержка запроса при высокой точности извлечения, а индекс помещается в памяти — обычно этот вариант выигрывает в этой гонке. Отдавайте предпочтение « IVF », если вы часто перестраиваете индексы (гораздо более быстрое построение) или в сочетании с квантованием « SQ8 » / «PQ » для соответствия ограниченному объему памяти.

Узнайте больше: ознакомьтесь с документацией по «HNSW » для получения точных параметров индекса или просмотрите «Index Explained» для получения полного руководства по принятию решений.