ScaNN (Google) vs HNSW — сравнение для больших масштабов (>100M векторов)?

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

ScaNN и HNSW — два популярных алгоритма приближённого поиска ближайших соседей (ANN). HNSW проще в реализации, эффективен до ~50M векторов и даёт отличную точность при умеренном потреблении памяти. При масштабах >100M векторов ScaNN выигрывает за счёт анизотропного квантования и иерархической кластеризации, обеспечивая лучший баланс скорости и точности, особенно когда важна высокая пропускная способность запросов (QPS). Выбор между ними зависит от конкретных требований к latency, памяти и точности.

1. Терминология: ANN, recall, latency, quantization

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

• Recall@k — доля истинных ближайших соседей среди top-k результатов.
• Latency — время одного запроса (обычно в миллисекундах).
• Queries Per Second (QPS) — пропускная способность.
• Quantization (квантование) — снижение точности представления векторов (например, с float32 до int8) для уменьшения памяти и ускорения вычислений.

ScaNN и HNSW решают задачу ANN, но принципиально разными способами.

2. HNSW: устройство и особенности

HNSW (Hierarchical Navigable Small World) — графовый метод. Строит многослойную структуру:

• Нижний слой содержит все векторы.
• Верхние слои — разреженные подмножества, обеспечивающие быстрый «дальний» переход.
• Поиск начинается с верхнего слоя, постепенно спускаясь к нижнему, уточняя соседей.

Ключевые параметры

• M — количество связей на узел (чем больше, тем выше точность, но больше памяти).
• efConstruction — размер динамического списка при построении.
• efSearch — размер списка при поиске (контролирует компромисс скорость/точность).

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

• Высокая точность при умеренном размере данных (до 50M).
• Не требует предварительного обучения (индекс строится инкрементально).
• Хорошо поддерживается в библиотеках (hnswlib, FAISS).

Недостатки

• Потребление памяти растёт линейно с числом векторов (каждый вектор хранит связи).
• При >100M векторов граф становится слишком большим, поиск замедляется, а точность падает из-за «эффекта тесного мира».

3. ScaNN: устройство и особенности

ScaNN (Scalable Nearest Neighbors) — гибридный метод от Google, сочетающий иерархическую кластеризацию и анизотропное квантование.

Основные компоненты

1. Иерархическая кластеризация (к-d дерево или k-means) — разбивает пространство на регионы, позволяя быстро отсекать заведомо далёкие кластеры.
2. Анизотропное квантование (Anisotropic Quantization, AQ) — специальная техника квантования, которая минимизирует ошибку не равномерно, а с учётом важности разных направлений. Это даёт более точное приближение расстояний, чем стандартное Product Quantization (PQ).
3. Оптимизация под Maximum Inner Product Search (MIPS) — ScaNN изначально проектировался для поиска по скалярному произведению, но поддерживает и косинусную близость, и L2.

Ключевые параметры

• num_leaves — количество кластеров (листьев).
• num_leaves_to_search — сколько кластеров просматривать при поиске.
• training_sample_size — размер выборки для обучения квантователя.

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

• Отлично масштабируется на >100M векторов (до миллиардов).
• Высокая пропускная способность (QPS) за счёт эффективного квантования и кластеризации.
• Меньший расход памяти на один вектор (квантованные коды вместо полных float32).

Недостатки

• Требует этапа обучения (не инкрементальный).
• Более сложная настройка гиперпараметров.
• Меньшая точность на малых датасетах (<1M) по сравнению с HNSW.

4. Сравнение архитектур

5. Производительность при >100M векторов

При масштабе >100M векторов граф HNSW становится «перегруженным»: чтобы поддерживать высокий recall, приходится увеличивать M и efSearch, что резко растягивает память и latency. ScaNN, напротив, использует иерархию кластеров, которая естественным образом ограничивает область поиска.

Экспериментальные данные (на датасете BIGANN 1B, 128D):

• HNSW (hnswlib) при 100M: recall@10 ~0.95, latency ~5 мс, память ~120 ГБ.
• ScaNN при 100M: recall@10 ~0.95, latency ~2 мс, память ~40 ГБ (за счёт квантования).
• При 1B: HNSW практически не применим (память >1 ТБ), ScaNN держит recall@10 ~0.90 при latency ~10 мс.

Вывод ScaNN выигрывает по всем фронтам при >100M, особенно по памяти и QPS.

6. Потребление памяти

• HNSW: хранит для каждого вектора список соседей (int32) и сам вектор (float32). Для 100M векторов размерности 768: ~100M * (7684 + M4) байт. При M=32 это ~100M * (3072 + 128) ≈ 320 ГБ.
• ScaNN: хранит квантованные коды (обычно 2–4 байта на компоненту) и центроиды кластеров. Для 100M векторов с PQ-кодом 64 байта: ~6.4 ГБ + центроиды (пренебрежимо). Память в 10–50 раз меньше.

7. Время построения индекса

• HNSW: построение O(N log N), инкрементальное. Для 100M векторов может занять несколько часов, но можно добавлять порциями.
• ScaNN: обучение квантователя (выборка ~100K векторов) + кластеризация (k-means) + кодирование. Время построения сопоставимо с HNSW, но требует однопроходного обучения.

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

• Размер базы < 50M векторов.
• Важна возможность динамически добавлять/удалять векторы.
• Нет жёстких ограничений по памяти (можно хранить полные векторы).
• Нужна максимальная точность (recall >0.98) на небольших датасетах.
• Простота внедрения (hnswlib — одна из самых лёгких библиотек).

9. Когда выбирать ScaNN

• Размер базы > 100M (до миллиардов).
• Критично низкое потребление памяти (например, развёртывание на GPU или в облаке).
• Высокие требования к QPS (сотни тысяч запросов в секунду).
• Возможность выполнить пакетное обучение индекса.
• Размерность векторов > 256 (ScaNN показывает лучший прирост).

10. Реализации и библиотеки

• HNSW: hnswlib (C++/Python), FAISS (режим IndexHNSW), nmslib.
• ScaNN: официальная библиотека Google scann (Python/C++), также частично реализован в FAISS как IndexIVF с квантованием, но без анизотропного квантования.

Пример кода для сравнения (синтетические данные):

import numpy as np
import hnswlib
import scann

# Генерация 1M векторов размерности 128
data = np.random.random((1_000_000, 128)).astype(np.float32)
queries = np.random.random((1000, 128)).astype(np.float32)

# HNSW
hnsw = hnswlib.Index(space='l2', dim=128)
hnsw.init_index(max_elements=1_000_000, ef_construction=200, M=32)
hnsw.add_items(data)
hnsw.set_ef(50)
labels_hnsw, distances_hnsw = hnsw.knn_query(queries, k=10)

# ScaNN (требуется обучение)
searcher = scann.scann_ops.builder(data, 10, "dot_product").tree(
    num_leaves=2000, num_leaves_to_search=100, training_sample_size=250000
).score_ah(2, anisotropic_quantization_threshold=0.2).build()
labels_scann, distances_scann = searcher.search_batched(queries)

11. Влияние на RAG-системы

В Agentic RAG retrieval — критический этап. Выбор ANN напрямую влияет на:

• Latency ответа: ScaNN быстрее при больших корпусах, что важно для real-time агентов.
• Качество контекста: HNSW может дать более релевантные документы на малых корпусах, но на больших ScaNN не уступает.
• Стоимость инфраструктуры: ScaNN требует меньше памяти, что снижает затраты на RAM/GPU.

Для гибридного поиска (sparse + dense) часто используют HNSW как базовый слой, а ScaNN — для dense-only сценариев с миллиардами векторов.

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

Задача Сравнить HNSW и ScaNN на датасете из 10M синтетических векторов (128D) и измерить recall@10, QPS, память.

Инструменты Python, hnswlib, scann, psutil (для памяти), timeit.

Шаги:

1. Сгенерировать 10M векторов (np.random.random) и 1K запросов.
2. Построить индекс HNSW (M=32, efConstruction=200) и ScaNN (num_leaves=2000, num_leaves_to_search=100, score_ah).
3. Измерить время построения, размер индекса на диске/в памяти.
4. Выполнить поиск с разными efSearch (HNSW) и num_leaves_to_search (ScaNN), замерить recall@10 и среднюю latency.
5. Построить графики зависимости recall vs QPS.

Ожидаемый результат ScaNN покажет в 2–3 раза меньшую память и более высокий QPS при том же recall, особенно при увеличении числа векторов до 100M (можно сгенерировать дополнительно).

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

Навигация

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