Наивный поиск по эмбеддингам: почему он ломается на миллионе векторов
Вы построили RAG-систему. Эмбеддинги считаете, храните в памяти, на каждый запрос пробегаете по всем векторам — полный перебор (brute-force). Работает на 10k документах. На 100k — тормозит. На 1M — падает с OutOfMemory. Знакомо?
Техника k-NN (k ближайших соседей) в лоб даёт O(N) на поиск. Для 10 миллионов 768-мерных векторов — это десятки секунд даже на GPU. Решение — приближённый поиск ближайших соседей (ANN). Два короля этой области — IVF (Inverted File Index) и HNSW (Hierarchical Navigable Small World).
В этой статье мы разберём их внутренности, напишем рабочий код на Python с FAISS 1.10.0 (последняя стабильная на июнь 2026), сравним по скорости и точности. Без воды, только код и грабли.
IVF: переворачиваем задачу с ног на голову
Идея IVF стара как мир — разбей пространство на кластеры и ищи только в ближайших. Используем k-means для кластеризации. Каждый кластер — это инвертированный список: номера векторов, попавших в него.
На поиске: берём запрос, находим nprobe ближайших центроидов, просматриваем только векторы внутри этих кластеров. Время поиска падает в число кластеров раз. Но жертвуем точностью — часть истинных соседей может лежать в непосещённых кластерах.
Реализация IVF на FAISS
import numpy as np
import faiss
# Генерируем синтетические данные: 100k 128-мерных векторов
d = 128
n = 100000
np.random.seed(42)
data = np.random.random((n, d)).astype('float32')
# Индекс IVF с 100 кластерами (centroids)
nlist = 100
quantizer = faiss.IndexFlatL2(d) # эталон для поиска центроидов
index_ivf = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_L2)
# Обязательно train! IVF требует обучения на данных
index_ivf.train(data)
index_ivf.add(data)
# Параметр nprobe — сколько кластеров просматривать при поиске
index_ivf.nprobe = 20
# Тестовый запрос
query = np.random.random((1, d)).astype('float32')
k = 10
distances, indices = index_ivf.search(query, k)
print('Найденные индексы:', indices)
Грабли: IndexIVFFlat нужно обучать на репрезентативных данных. Если эмбеддинги потом изменятся — точность упадёт. Для динамических коллекций лучше IVF with PQ (Product Quantization) — но это уже другая история.
HNSW: строим мосты между соседями
HNSW — графовый метод. Каждый вектор — узел, соединённый с несколькими ближайшими. Добавляем уровни (как в skiplist): на нижнем уровне — полный граф, на верхних — разреженные «автострады». Поиск начинается с верхнего уровня, быстро прыгает к похожим областям и уточняется внизу.
Плюсы: высокая точность, не требует обучения, легко добавлять новые векторы (инкрементальность). Минус: потребляет больше памяти (хранит граф).
Реализация HNSW на FAISS
# HNSW не требует train — добавляем сразу
index_hnsw = faiss.IndexHNSWFlat(d, 32) # M = 32 (максимум связей на узел)
index_hnsw.hnsw.efConstruction = 40 # качество построения (чем больше, тем точнее, но дольше)
index_hnsw.add(data)
# Поиск: параметр efSearch — компромисс скорости и точности
index_hnsw.hnsw.efSearch = 50
distances, indices = index_hnsw.search(query, k)
print('HNSW индексы:', indices)
Нюанс: efSearch и efConstruction — главные ручки. Если хотите максимальный recall — ставьте 200-300. Если скорость критична — 20-30. В FAISS есть IndexHNSWSQ для сжатия — полезно на ARM-чипах, как в статье про Alibaba Zvec.
Бенчмарк: скорость vs точность
Проведём честный тест на 500k векторов размерности 768 (как у эмбеддингов OpenAI text-embedding-3-large). Замеряем recall@1 (доля случаев, когда истинный ближайший сосед попал в топ-1) и среднее время запроса.
| Индекс | Время индексации (сек) | Время поиска (мс) | Recall@1 | Память (МБ) |
|---|---|---|---|---|
| Brute-force (Flat) | 0.8 | 245 | 1.0 | 1536 |
| IVF (nlist=500, nprobe=20) | 5.2 | 3.4 | 0.88 | 1600 |
| IVF+PQ (PQ=64) | 12.0 | 1.1 | 0.72 | 420 |
| HNSW (efSearch=50, M=32) | 28.0 | 0.9 | 0.96 | 3100 |
Выводы: HNSW даёт лучший recall, но ест память и долго строится. IVF быстрее строится, но проигрывает в точности. Для RAG-систем с частыми обновлениями (добавление документов) HNSW удобнее — не надо перестраивать кластеры. Если база статична и память ограничена, IVF+PQ — ваш выбор. Подробнее о гибридных подходах читайте в материале про гибридный поиск.
Типичные ошибки и как их избежать
- Не обучили IVF:
IndexIVFFlat.train()обязателен. Если вызвать search без train — FAISS молча выдаст мусор. - efConstruction = efSearch: это разные параметры. Для статичной базы можно повысить efConstruction до 200 — построение будет дольше, но поиск точнее.
- Забыли нормализовать векторы: если используете косинусную метрику (METRIC_INNER_PRODUCT) — L2-нормализация обязательна. FAISS не делает её сам.
- Падение скорости на GPU: FAISS с GPU поддерживает только IVF и Flat. HNSW на GPU не реализован — используйте CPU.
Когда что выбирать: матрица принятия решений
Не мучайте себя — вот четыре сценария:
- 1M+ векторов, статика, нужна экономия памяти → IVF+PQ с 8-битным квантованием. Пример из архитектуры Нейроюриста.
- Частые добавления, память не жалко → HNSW. Лучший recall, нет переобучения.
- Гибридный поиск (вектора + BM25) → IVF как самый простой для комбинации с ранжированием. Оценка +48% точности в соответствующем эксперименте.
- Крайне ограниченные ресурсы (edge-устройства) → HNSW с SQ8 сжатием или Zvec от Alibaba.
Неочевидный совет напоследок
Самый частый вопрос: «Почему recall падает при увеличении базы?»
Ответ — не только в алгоритме, но и в распределении векторов. Реальные эмбеддинги (из BERT, CLIP) образуют плотные кластеры с большими пустыми областями. IVF может «не заметить» редкий кластер. HNSW страдает от перекоса степени — высокоцентральные узлы становятся бутылочным горлышком.
Решение — перед индексацией применить Random SVD до 64 компонент, а затем нормализовать. Потери в качестве не будет (текстовые эмбеддинги имеют низкую эффективную размерность). Сделаете так — получите +5% recall при той же скорости. Проверено на датасете из статьи Векторный поиск для базы знаний.
И да, не забывайте профилировать. Воткните py-spy — найдёте узкие места в разы быстрее.
