Что такое Hierarchical Navigable Small World + IVF (HNSW+IVF) гибрид?

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

HNSW+IVF — это гибридный алгоритм приближённого поиска ближайших соседей (ANN), который объединяет грубую кластеризацию IVF (Inverted File Index) с точным графовым поиском HNSW (Hierarchical Navigable Small World). Сначала IVF быстро отсеивает неперспективные кластеры, затем HNSW выполняет детальный поиск внутри отобранных кластеров. Такая комбинация позволяет масштабировать поиск на миллиарды векторов, сохраняя высокую скорость и точность. Гибрид активно используется в библиотеках Faiss, LanceDB и Milvus.

1. Термины и мотивация

IVF (Inverted File Index) — метод, при котором векторы кластеризуются (например, k-means), и для каждого кластера строится инвертированный список. При поиске вычисляются расстояния до центроидов, выбирается nprobe ближайших кластеров, и поиск ведётся только внутри них. IVF даёт хорошую масштабируемость, но точность падает при увеличении числа кластеров.

HNSW (Hierarchical Navigable Small World) — графовый метод, строящий многоуровневую иерархию графов. Поиск начинается с верхнего уровня (мало узлов) и спускается вниз, используя жадный обход. HNSW обеспечивает очень высокую точность и скорость на датасетах до десятков миллионов векторов, но требует много памяти (граф хранится в RAM) и плохо масштабируется на миллиарды.

Гибрид HNSW+IVF решает проблему масштабирования: IVF разбивает пространство на кластеры, каждый из которых содержит подграф HNSW. Поиск сначала выбирает несколько кластеров (IVF-шаг), затем внутри каждого запускается HNSW. Это снижает объём памяти (граф строится только внутри кластера) и ускоряет поиск за счёт фильтрации.

2. Как работает IVF (напоминание)

1. Обучение: все векторы датасета кластеризуются алгоритмом k-means на nlist кластеров. Получаются центроиды C = {c1, ..., c_{nlist}}.
2. Индексирование: каждый вектор приписывается к ближайшему центроиду. Для каждого кластера строится инвертированный список — массив идентификаторов векторов, попавших в этот кластер.
3. Поиск: для запроса q вычисляются расстояния до всех центроидов, выбираются nprobe ближайших. Затем q сравнивается со всеми векторами в выбранных кластерах (полный перебор внутри кластера).

Недостаток: при большом nlist кластеры становятся маленькими, но точность падает, если nprobe мало. Полный перебор внутри кластера всё ещё может быть медленным, если кластеры большие.

3. Как работает HNSW (напоминание)

1. Построение: создаётся иерархия графов. Нижний уровень (уровень 0) содержит все векторы. Каждый следующий уровень содержит подмножество узлов (вероятность включения уменьшается экспоненциально). На каждом уровне узлы соединяются рёбрами с ближайшими соседями (параметр M).
2. Поиск: начиная с верхнего уровня, алгоритм жадным обходом находит ближайший узел на текущем уровне, затем спускается на уровень ниже и повторяет. На нижнем уровне выполняется более точный поиск с использованием очереди с приоритетом (параметр efSearch).

Преимущество: логарифмическая сложность по числу векторов, высокая точность. Недостаток: граф хранится в памяти целиком, для миллиардов векторов требуется сотни гигабайт RAM.

4. Комбинация HNSW+IVF: архитектура

Гибридный индекс строится так:

• Шаг 1 (IVF-кластеризация): весь датасет разбивается на nlist кластеров с помощью k-means.
• Шаг 2 (HNSW внутри кластера): для каждого кластера строится отдельный граф HNSW, содержащий только векторы этого кластера. Параметры HNSW (M, efConstruction) могут быть одинаковыми для всех кластеров.
• Шаг 3 (инвертированный указатель): сохраняется отображение «центроид → HNSW-граф кластера».

Поиск:

1. Вычислить расстояния от запроса q до всех центроидов.
2. Выбрать nprobe ближайших кластеров.
3. Для каждого выбранного кластера запустить HNSW-поиск с параметром efSearch. Результаты объединяются, сортируются по расстоянию, возвращаются top-k.

Вариант реализации в Faiss: IndexIVF может использовать HNSW в качестве квантователя (квантизатор кодов). В Faiss есть IndexIVF с HNSW как IndexHNSW для кодирования остатков (residual vectors). Но чаще используется IndexHNSW с предварительной фильтрацией через IVF — это нестандартная комбинация, доступная через IndexIVF с HNSW-квантователем.

В LanceDB и Milvus гибрид реализован как «IVF + HNSW»: сначала IVF выбирает кластеры, затем HNSW ищет внутри. Это позволяет хранить графы только для активных кластеров, экономя память.

5. Преимущества гибрида

6. Недостатки и подводные камни

• Двойная настройка: нужно подбирать nlist, nprobe (IVF) и M, efConstruction, efSearch (HNSW). Оптимум зависит от датасета и требований.
• Память для графов: хотя графы меньше, чем полный HNSW, они всё равно могут быть значительными при большом nlist (каждый кластер хранит свой граф). Если кластеры мелкие, накладные расходы на графы растут.
• Дисбаланс кластеров: если данные распределены неравномерно, некоторые кластеры могут быть огромными, что замедляет HNSW внутри них. Решается адаптивной кластеризацией (например, IVF с разным размером кластеров).
• Качество кластеризации: плохая кластеризация (неудачный seed k-means) снижает эффективность IVF-шага.

7. Когда выбирать HNSW+IVF

• Очень большие коллекции (сотни миллионов – миллиарды векторов), где чистый HNSW не помещается в RAM.
• Требуется высокая точность, близкая к HNSW, но при ограниченных ресурсах памяти.
• Системы с распределённым хранением: кластеры можно разместить на разных нодах, а HNSW-графы строить локально.
• Сценарии RAG: векторные БД для RAG часто используют гибридные индексы для баланса между latency и качеством поиска.

8. Реализации в популярных инструментах

• Faiss: IndexIVF может использовать IndexHNSW как квантователь (через IndexIVF с HNSW-квантизатором). Пример: index = IndexIVF(IndexHNSWFlat(d, M), d, nlist, metric).
• LanceDB: поддерживает гибридный индекс IVF_HNSW_SQ (с скалярным квантованием). Параметры: num_partitions (nlist), num_sub_vectors (для SQ), M, ef_construction.
• Milvus: использует IVF_FLAT и HNSW как отдельные типы индексов, но также поддерживает комбинацию через IVF_HNSW (в документации упоминается как экспериментальная).
• Weaviate: модуль vectorizer позволяет комбинировать IVF и HNSW через настройки pq (product quantization) и hnsw.

9. Пример кода на Python (Faiss)

import faiss
import numpy as np

# Генерация синтетических данных
d = 128  # размерность
n = 100000  # количество векторов
xb = np.random.random((n, d)).astype('float32')
xq = np.random.random((1, d)).astype('float32')

# Параметры гибрида
nlist = 100  # количество кластеров IVF
M = 32       # параметр HNSW (число соседей)
efConstruction = 200
efSearch = 64

# Строим HNSW-индекс для IVF-квантователя
hnsw_index = faiss.IndexHNSWFlat(d, M)
hnsw_index.hnsw.efConstruction = efConstruction

# Оборачиваем в IVF
index = faiss.IndexIVF(hnsw_index, d, nlist, faiss.METRIC_L2)
index.train(xb)
index.add(xb)
index.nprobe = 10  # число кластеров для поиска

# Поиск
index.hnsw.efSearch = efSearch  # важно: efSearch для HNSW внутри IVF
D, I = index.search(xq, k=5)
print("Результаты:", I)

Примечание: в Faiss IndexIVF с HNSW-квантователем использует HNSW для поиска внутри каждого кластера, но сам IVF-шаг остаётся линейным по числу кластеров. Это не чистая двухуровневая схема, но близко.

10. Сравнение с другими гибридами

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

Задача: Сравнить производительность чистого IVF, чистого HNSW и гибрида HNSW+IVF на датасете SIFT1M (1 млн векторов, 128d).

Инструменты: Python, Faiss, numpy, matplotlib, time.

Шаги:

1. Скачать SIFT1M (или сгенерировать синтетику 1M векторов).
2. Построить три индекса:
   • IVF (nlist=1000, nprobe=10).
   • HNSW (M=32, efSearch=64).
   • Гибрид (nlist=100, M=32, efSearch=64, nprobe=5).
3. Для каждого индекса измерить:
   • Время построения (train + add).
   • Потребление памяти (через faiss.Index*).
   • Recall@10 (по сравнению с брутфорс-поиском).
   • QPS (запросов в секунду) на 1000 запросов.
4. Построить таблицу и графики.

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

• IVF: низкая память, средний recall (~0.8), высокая QPS.
• HNSW: высокая память, высокий recall (~0.99), очень высокая QPS.
• Гибрид: средняя память, высокий recall (~0.95), высокая QPS (чуть ниже HNSW, но выше IVF).

Вывод: Гибрид позволяет обрабатывать датасеты, которые не влезают в RAM для HNSW, с минимальной потерей точности.

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

Навигация

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