Как вы выбираете ANN алгоритм под ваш use case (volume, dimensionality, budget)?

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

Выбор ANN (Approximate Nearest Neighbor) алгоритма — это компромисс между скоростью, памятью и точностью. Для объёмов до 1 млн векторов оптимален HNSW (высокая точность, latency|низкая задержка). Для 1–50 млн — IVF-PQ или HNSW-PQ (сжатие через Quantization|Product Quantization). Для >50 млн — ScaNN (Google) или DiskANN (Microsoft), которые умеют работать с дисковыми индексами. При размерности >1024 HNSW даёт лучший recall, а при жёстких ограничениях по latency (миллисекунды) — HNSW или IVF с небольшим числом центроидов.

1. Термин: ANN (Approximate Nearest Neighbor)

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

Зачем ANN в RAG
Векторная БД хранит эмбеддинги документов. При запросе нужно найти топ-k похожих векторов. Полный перебор (O(N*d)) для миллионов векторов недопустим. ANN снижает сложность до O(log N) или O(sqrt(N)).

Ключевые метрики ANN

• Recall@k — доля истинных ближайших соседей среди top-k результатов.
• QPS (Queries Per Second) — пропускная способность.
• Latency (p99) — время ответа для 99% запросов.
• Memory footprint — объём RAM, занимаемый индексом.

2. Параметры выбора: volume, dimensionality, budget

2.1 Volume (объём данных)

• < 1M векторов — индекс целиком помещается в RAM, можно использовать точные методы или простые ANN.
• 1M – 50M — требуется сжатие (квантование) или иерархические структуры.
• > 50M — индекс не влезает в RAM одного узла, нужны дисковые или распределённые решения.

2.2 Dimensionality (размерность)

• Низкая (64–256) — хорошо работают tree-based методы (KD-Tree, Annoy).
• Средняя (256–1024) — HNSW, IVF.
• Высокая (>1024) — «проклятие размерности»: расстояния становятся почти одинаковыми. HNSW и ScaNN справляются лучше за счёт графовых структур.

2.3 Budget (бюджет)

• Latency budget — максимальное время ответа (например, p99 < 50 мс).
• Memory budget — доступная RAM (например, 64 ГБ).
• Throughput budget — требуемое количество запросов в секунду.
• Cost budget — стоимость инференса (облачные инстансы, GPU).

3. Сравнение основных ANN алгоритмов

Пояснения

• Product Quantization (PQ) — разбивает вектор на подвекторы, каждый квантуется в код. Позволяет хранить векторы в сжатом виде (например, 4 байта вместо 1024).
• Асимметричное квантование (ScaNN) — запрос не квантуется, а база квантуется, что даёт более точные расстояния.

4. Выбор по объёму данных

4.1 < 1M векторов

Рекомендация HNSW (или точный kNN через Faiss IndexFlatIP).

• Почему HNSW даёт recall > 0.99 при latency < 1 мс. Индекс помещается в RAM.
• Пример: Faiss IndexHNSWFlat (без квантования).
• Альтернатива Annoy (tree-based) — проще, но ниже точность.

4.2 1M – 50M векторов

Рекомендация IVF-PQ или HNSW-PQ.

• IVF-PQ настраивается число центроидов (nlist) и подвекторов (m). Типично: nlist = 4096, m = 64 → сжатие в 8 раз.
• HNSW-PQ сохраняет графовую структуру, но векторы сжаты. Точность выше, чем IVF-PQ, но обновление сложнее.
• Пример: Faiss IndexIVFPQ или IndexHNSWPQ.

4.3 > 50M векторов

Рекомендация ScaNN (если доступен GPU/TPU) или DiskANN (если только CPU и диск).

• ScaNN использует асимметричное квантование и переранжировку top-кандидатов. На GPU достигает 10k+ QPS.
• DiskANN строит граф на диске, подгружает горячие узлы в RAM. Идеален для терабайтных коллекций.
• Пример: ScaNN через scann.scann_ops.builder(), DiskANN через diskannpy.

5. Выбор по размерности

Важно Для размерности > 1024 обычный IVF с PQ может сильно терять recall, так как квантование становится грубым. HNSW с efConstruction и efSearch позволяет тонко настраивать точность.

6. Выбор по latency и throughput

6.1 Low latency (p99 < 10 мс)

• HNSW — лучший выбор. Параметр efSearch (размер динамического списка) регулирует скорость: меньше efSearch → быстрее, но ниже recall.
• IVF с малым nprobe (число просматриваемых кластеров) — тоже быстро, но recall падает.

6.2 High throughput (> 10k QPS)

• IVF-PQ — хорошо параллелится (кластеры независимы). Можно шардировать на несколько GPU.
• ScaNN — на GPU даёт десятки тысяч QPS.
• DiskANN — для throughput нужно много дисковых IOPS (NVMe).

6.3 Memory-bound (RAM < 10 ГБ)

• IVF-PQ с сильным сжатием (m = 16, 8 байт на вектор).
• DiskANN — почти не использует RAM, но latency выше.

7. Практические соображения

7.1 Индексация и обновления

• HNSW — добавление векторов возможно, но требует перестроения графа (дорого). Лучше строить индекс батчами.
• IVF — добавление в существующий кластер дешево (просто вставка в список). Но при изменении распределения данных нужно перекластеризовать.
• DiskANN — поддерживает динамические вставки/удаления через diskannpy.

7.2 Распределённые системы

• Для > 50M векторов часто используют шардирование: разбивают данные на части, каждая часть обслуживается отдельным узлом с HNSW/IVF.
• Пример: Milvus, Qdrant, Weaviate — используют комбинацию HNSW и IVF-PQ с шардированием.

7.3 Бенчмаркинг

Перед выбором обязательно запустите ANN-benchmarks (https://github.com/erikbern/[ann-benchmarks](/wiki/ANN-benchmarks)) на своих данных. Результаты сильно зависят от:

• Типа эмбеддингов (OpenAI, BERT, CLIP).
• Распределения данных (равномерное, кластерное).
• Требуемого recall (0.9 vs 0.99).

8. Пример кода (Faiss)

import faiss
import numpy as np

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

# 1. HNSW (без квантования)
index_hnsw = faiss.IndexHNSWFlat(d, 32)  # M = 32 (число соседей в графе)
index_hnsw.train(xb)
index_hnsw.add(xb)

# Поиск
xq = np.random.random((1, d)).astype('float32')
D, I = index_hnsw.search(xq, k=10)

# 2. IVF-PQ (сжатие)
nlist = 4096  # число центроидов
m = 64  # число подвекторов (сжатие в d/m = 12 раз)
quantizer = faiss.IndexFlatIP(d)  # косинусное расстояние
index_ivfpq = faiss.IndexIVFPQ(quantizer, d, nlist, m, 8)  # 8 бит на подвектор
index_ivfpq.train(xb)
index_ivfpq.add(xb)
index_ivfpq.nprobe = 100  # число просматриваемых кластеров при поиске
D, I = index_ivfpq.search(xq, k=10)

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

Задача Сравнить HNSW, IVF-PQ и ScaNN на датасете из 5M векторов (например, эмбеддинги Wikipedia через sentence-transformers).

Инструменты

• Python, Faiss, ScaNN (Google), ann-benchmarks.
• Датасет: wikipedia-22-12-simple-embeddings (можно скачать через Hugging Face).

Шаги:

1. Загрузить 5M эмбеддингов размерности 384 (all-MiniLM-L6-v2).
2. Построить индексы HNSW (M=32), IVF-PQ (nlist=4096, m=32), ScaNN (num_leaves=10000).
3. Измерить recall@10, QPS, memory usage для разных efSearch/nprobe/reordering.
4. Построить график Pareto frontier (recall vs QPS).
5. Сделать вывод: какой алгоритм лучше для low-latency (p99<20ms) и для high-throughput (>5000 QPS).

Ожидаемый результат Таблица с метриками и рекомендация для гипотетического use case (например, чат-бот с 10M документов, latency < 100ms, RAM < 32GB → IVF-PQ с nprobe=50).

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

11. Навигация

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

Навигация

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