Как вы выбираете параметры HNSW (M, ef_construction, ef_search) под свои данные?

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

HNSW (Hierarchical Navigable Small World) — это графовый алгоритм для приближённого поиска ближайших соседей (ANN). Три ключевых параметра — M (количество связей на узел), ef_construction (размер динамического списка при построении) и ef_search (размер динамического списка при поиске) — управляют trade-off между точностью (recall), скоростью запросов (QPS) и потреблением памяти. Выбор зависит от размера базы векторов, требуемой latency и доступных ресурсов. Оптимальные значения находятся эмпирически через бенчмаркинг на репрезентативной выборке данных.

1. Что такое HNSW и зачем он нужен в RAG

HNSW — это алгоритм для приближённого поиска k ближайших соседей (Approximate Nearest Neighbor, ANN). В RAG-системах он используется в векторных базах данных (FAISS, Milvus, Qdrant) для быстрого поиска релевантных чанков среди миллионов эмбеддингов.

Принцип работы

• Строится многоуровневая иерархия графов: нижний уровень содержит все векторы, верхние — разреженные подмножества.
• Поиск начинается с верхнего уровня (грубый проход) и спускается вниз, уточняя соседей.
• Каждый узел (вектор) соединён с M другими узлами на том же уровне.

Почему HNSW популярен

• Логарифмическая сложность поиска O(log N) при высокой точности.
• Хорошо масштабируется до сотен миллионов векторов.
• Поддерживает index update|динамическое добавление/удаление (вставка без перестроения всего графа).

2. Параметр M (количество связей на узел)

M определяет максимальное количество исходящих рёбер из каждого узла на каждом уровне графа (кроме верхнего, где может быть меньше).

Влияние на характеристики

Рекомендации

• Для большинства задач: M = 16–32.
• Если память критична (например, мобильные устройства): M = 8–12.
• Если требуется максимальная точность и память не ограничена: M = 48–64.

Формула памяти на один вектор примерно M * 4 байта (int) * 2 (двунаправленные рёбра) + служебные данные. Для 1 млн векторов при M=32 это ~256 МБ только на рёбра.

3. Параметр ef_construction (размер динамического списка при построении)

ef_construction — это размер очереди с приоритетом (dynamic candidate list), используемой во время вставки нового узла в граф. Чем больше ef_construction, тем тщательнее выбираются соседи для нового узла.

Влияние

Важно ef_construction влияет только на качество индекса, не на скорость поиска. После построения индекс можно использовать с любым ef_search.

Рекомендации

• Старт: ef_construction = 200–500.
• Для больших датасетов (>10 млн) можно увеличить до 500–800, чтобы компенсировать разреженность графа.
• Если время построения не критично (однократная индексация), ставьте 400–600.

4. Параметр ef_search (размер динамического списка при поиске)

ef_search — размер очереди с приоритетом во время поиска. Контролирует, сколько кандидатов будет рассмотрено на каждом уровне.

Влияние

Рекомендации

• Для RAG-систем с требованием latency < 50 мс: ef_search = 128–256.
• Если точность важнее скорости (offline batch processing): ef_search = 400–800.
• Для real-time приложений с жёстким SLA: ef_search = 64–128.

Связь с k (количество возвращаемых результатов): ef_search должен быть >= k. Обычно ef_search = 2–3 * k.

5. Trade-off: память vs скорость vs точность

Все три параметра образуют тройной компромисс. Таблица ниже показывает типичные сценарии:

Как интерпретировать

• QPS (Queries Per Second) — количество запросов в секунду, обратное latency.
• Recall@10 — доля истинных ближайших соседей среди 10 возвращаемых.

6. Как выбирать параметры под свои данные: пошаговый процесс

Шаг 1. Определите ограничения

• Размер базы: N векторов.
• Размерность эмбеддингов: d (обычно 384, 768, 1024).
• Требования к latency: максимальное время ответа (например, 100 мс).
• Доступная оперативная память: RAM.
• Частота обновления данных: статический или динамический индекс.

Шаг 2. Выберите начальные значения

• M = 16 (если память не критична) или 8 (если память ограничена).
• ef_construction = 200 (для быстрой индексации) или 400 (для лучшего качества).
• ef_search = 128 (для первого теста).

Шаг 3. Запустите бенчмарк на подвыборке

• Возьмите 10% данных для построения индекса и 1000 запросов с известными ground-truth соседями (можно получить точным kNN).
• Измерьте recall@k, QPS, потребление памяти.

Шаг 4. Итеративно настраивайте

• Если recall < 0.95: увеличьте ef_search (до 256, 512) или M (до 32).
• Если latency превышает лимит: уменьшите ef_search или M.
• Если память переполнена: уменьшите M.

Шаг 5. Проверьте на полном датасете

• После настройки на подвыборке перестройте индекс на всех данных и финально замерьте.

7. Пример кода на Python (FAISS) для подбора параметров

import faiss
import numpy as np
import time

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

# Ground truth (точный поиск)
index_flat = faiss.IndexFlatL2(d)
index_flat.add(xb)
D, I_gt = index_flat.search(xq, 10)

def benchmark_hnsw(M, ef_construction, ef_search):
    # Построение индекса
    index = faiss.IndexHNSWFlat(d, M)
    index.hnsw.efConstruction = ef_construction
    index.add(xb)
    
    # Поиск
    index.hnsw.efSearch = ef_search
    start = time.time()
    D, I = index.search(xq, 10)
    elapsed = time.time() - start
    
    # Recall@10
    recall = np.mean([len(set(I[i]) & set(I_gt[i])) / 10 for i in range(len(xq))])
    
    # QPS
    qps = len(xq) / elapsed
    
    # Память (приблизительно)
    memory_mb = index.ntotal * (d * 4 + M * 4 * 2) / (1024**2)
    
    return recall, qps, memory_mb

# Тестируем разные комбинации
params = [
    (16, 200, 128),
    (32, 400, 256),
    (48, 800, 512),
    (8, 200, 128),
]

for M, ef_c, ef_s in params:
    recall, qps, mem = benchmark_hnsw(M, ef_c, ef_s)
    print(f"M={M}, ef_c={ef_c}, ef_s={ef_s}: recall={recall:.4f}, QPS={qps:.0f}, mem={mem:.0f} MB")

Ожидаемый вывод

M=16, ef_c=200, ef_s=128: recall=0.9210, QPS=5200, mem=210 MB
M=32, ef_c=400, ef_s=256: recall=0.9730, QPS=3100, mem=410 MB
M=48, ef_c=800, ef_s=512: recall=0.9940, QPS=1100, mem=610 MB
M=8, ef_c=200, ef_s=128: recall=0.8530, QPS=6100, mem=110 MB

8. Особенности для разных типов данных

Важно Для разреженных векторов HNSW теряет преимущество — используйте SPANN или IVF с разреженными индексами.

9. Продвинутые техники

• Многократное построение с разными параметрами автоматический поиск по сетке (grid search) с метрикой recall@k при фиксированном бюджете latency.
• Профилирование памяти используйте faiss.index_memory или sys.getsizeof для точной оценки.
• Квантование (PQ, SQ): уменьшает размер векторов в 4–8 раз, позволяя увеличить M без роста памяти.
• Динамическое обновление если данные часто добавляются, выбирайте M с запасом (32 вместо 16), чтобы граф оставался связным.
• Гибридный поиск комбинируйте HNSW с фильтрацией по метаданным (pre-filtering) — параметры ef_search нужно увеличить на 20–30%.

10. Связь с RAG: почему HNSW — стандарт де-факто

• Скорость HNSW обеспечивает latency < 10 мс для 1 млн векторов при recall > 0.95, что критично для диалоговых систем.
• Гибкость поддерживает L2, косинусную, IP метрики — все популярные меры для эмбеддингов.
• Интеграция FAISS, Milvus, Qdrant, Weaviate — все используют HNSW как основной алгоритм.
• Недостаток чувствителен к "проклятию размерности" при d > 1000 — тогда лучше IVF+PQ или SCANN.

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

Задача Написать скрипт для автоматического подбора параметров HNSW под датасет эмбеддингов (например, 50k чанков из вашей RAG-системы).

Инструменты Python, FAISS, matplotlib, pandas.

Шаги:

1. Загрузите реальные эмбеддинги (или сгенерируйте синтетические с размерностью 768).
2. Разделите на обучающую выборку (90%) и тестовые запросы (10%) с ground truth через точный kNN.
3. Определите сетку параметров: M = [8, 16, 24, 32], ef_construction = [100, 200, 400, 600], ef_search = [64, 128, 256, 512].
4. Для каждой комбинации постройте индекс, измерьте recall@10, QPS, память.
5. Постройте 3D-график (M, ef_search, recall) или heatmap.
6. Выберите комбинацию, максимизирующую recall при QPS > 2000 и памяти < 500 MB.

Ожидаемый результат Таблица с лучшими параметрами и визуализация trade-off.

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

Навигация

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