Векторный поиск и приближённые ближайшие соседи (ANN)

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

Эта глава — про сам слой векторного поиска: семейства индексов (IVF, HNSW), сжатие (PQ, IVF-PQ, ScaNN), метрики качества recall/latency/memory и гибридный поиск. Соседняя глава про RAG использует векторный поиск как компонент, а глава про инференс LLM — про работу самой модели.

Такой взгляд помогает обсуждать выбор индекса, квантизацию, фильтрацию по метаданным и эксплуатацию (сегменты, перестроение, шардирование) как единый инженерный компромисс, а не как настройку одной библиотеки.

Практическая польза главы

ANN как размен, а не магия

Точный kNN перебирает все векторы: стоимость растёт линейно с числом векторов и размерностью, поэтому на больших коллекциях он не выживает. ANN сознательно жертвует частью recall ради скорости и памяти. Любой выбор индекса — это точка на поверхности компромиссов recall↔latency↔memory: улучшая две вершины треугольника, обычно платишь третьей.

IVF и HNSW: два пути сужения

IVF разбивает пространство k-means на nlist ячеек и проверяет только nprobe ближайших — быстрое построение, экономия памяти, но потери у границ кластеров. HNSW (Malkov & Yashunin, 2016) строит многоуровневый граф малого мира: верхние слои дают дальние прыжки, нижний — точное приближение; параметры M, efConstruction, efSearch дают лучшую пару recall/latency ценой RAM и времени построения.

Сжатие памяти: PQ, IVF-PQ, ScaNN

Сырой float32-вектор занимает 4·d байт. Продуктовая квантизация (Jégou, Douze, Schmid, 2011) делит вектор на m подвекторов и кодирует каждый байтом из кодбука, оценивая расстояния по таблицам. IVF-PQ — рабочая лошадка миллиардных коллекций. ScaNN (Guo et al., 2019) анизотропной функцией потерь точнее сохраняет ранжирование по скалярному произведению. Платой всегда выступает recall, поэтому за приближённым отбором идёт точное переранжирование.

Гибридный поиск и честный recall

Плотный путь (семантика) ловит смысл, разреженный BM25 — точные совпадения и коды; их сливают через RRF по позициям. Фильтрация по метаданным конфликтует со структурой индекса: pre-filtering точен но дорог, post-filtering быстр но рискует пустой выдачей. recall@k нужно мерить честно — против точного перебора на том же наборе запросов и метрике, иначе быстрый индекс тихо теряет релевантное.

Связанная глава

Архитектура системы генерации с извлечением контекста (RAG) на GenAI

Там векторный поиск — компонент внутри генерации с извлечением контекста (RAG); здесь мы разбираем сам слой поиска.

Читать обзор

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

Здесь разбираем сам слой : какой индекс ANN выбрать, как балансировать , и память и где включать гибридный поиск. Где проходит граница со смежными главами: соседняя глава про использует векторный поиск как компонент (гибридный поиск, , сборка контекста), а оптимизация инференса отвечает за работу самой модели. На этом слое остаются индексы, метрики расстояния и эксплуатация поиска.

Метрики расстояния

Косинусное сходство

Сравнивает угол между векторами и игнорирует их длину. Это поведение по умолчанию для текстовых : длина вектора несёт мало смысла, а важна только ориентация в пространстве.

Скалярное произведение (inner product)

Учитывает и угол, и длину. Часто используется в рекомендациях и MIPS (maximum inner product search), где норма вектора кодирует популярность или уверенность. На нормированных векторах ранжирование совпадает с косинусным.

Евклидово расстояние (L2)

Геометрическое расстояние между точками. Естественно для изображений и числовых признаков. На L2-нормированных векторах L2 и косинус дают одинаковый порядок соседей, поэтому выбор метрики и нормализация должны быть согласованы.

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

IVF против HNSW: как устроен поиск

Слева IVF разбивает пространство на ячейки (k-means) и проверяет только nprobe ближайших к запросу. Справа HNSW спускается по уровням графа: верхние слои дают «дальние прыжки», нижний — точное приближение.

Семейства индексов

Плоский индекс (Flat, точный)

Линейный перебор всех векторов. Даёт полноту (recall) = 1.0 и служит эталоном качества, но стоимость растёт линейно с числом векторов и размерностью. Подходит до сотен тысяч векторов или как честный эталон для замера полноты.

IVF (инвертированные списки)

Пространство заранее разбивается на ячейки методом k-means на nlist центроидов. Запрос идёт только в nprobe ближайших ячеек. Больше nprobe — выше и задержка. Быстрое построение, экономный по памяти, но качество падает у границ кластеров.

HNSW (многоуровневый граф)

Навигируемый граф малого мира с иерархией слоёв (Malkov & Yashunin, 2016). Параметры: M (число рёбер на узел), efConstruction (ширина поиска при построении) и efSearch (ширина при запросе). Лучшая пара « / » в памяти, но граф «дорогой» по RAM и медленнее строится.

Сжатие векторов

Продуктовая квантизация (PQ)

Вектор делится на m подвекторов, каждый кодируется ближайшим центроидом из своего кодбука (обычно 256 на подпространство = 1 байт). Jégou, Douze, Schmid (2011): вектор из 4·d байт сжимается до m байт, расстояния оцениваются по предпосчитанным таблицам.

IVF-PQ

Комбинация: IVF грубо отбирает ячейки-кандидаты, PQ хранит остатки (residuals) в сжатом виде. Это рабочая лошадка для миллиардных коллекций — память на порядок меньше, чем у Flat или HNSW, ценой части полноты (recall).

Скалярная квантизация (SQ)

Каждая компонента float32 кодируется в int8 (или меньше). Проще PQ, сжатие ~4x, потеря полноты (recall) небольшая. Часто первый шаг экономии памяти перед более агрессивным PQ.

ScaNN (анизотропная квантизация)

Guo et al. (2019): функция потерь сильнее штрафует параллельную компоненту остатка относительно ортогональной, что точнее сохраняет ранжирование по скалярному произведению (MIPS). Сильный результат на публичных бенчмарках при сильном сжатии.

Метрики качества и эксплуатации

Recall@k

цель ≥ 0.95

Доля истинных ближайших соседей, найденных приближённо. Считается честно только против на том же наборе запросов и той же метрике расстояния.

Запросы в секунду (QPS) и латентность

p50 / p99

измеряют вместе с : средняя задержка скрывает деградацию, а ползунок между и регулируется параметрами поиска.

Память на вектор

байты / вектор

Сырой float32-вектор размерности d занимает 4·d байт. Граф HNSW добавляет накладные расходы на рёбра; квантизация снижает память в разы ценой полноты (recall).

Время построения

build time

HNSW и IVF-PQ строятся заметно дольше, чем Flat. Время и стоимость пересборки определяют, насколько часто можно перестраивать индекс при потоке обновлений.

Гибридный поиск и фильтрация

Плотный путь: по индексу приближённого поиска (ANN) ловит смысл и синонимы, но проседает на точных совпадениях, кодах, артикулах и редких терминах.
Разреженный путь: и инвертированный индекс точны на ключевых словах и точных совпадениях, но не понимают перефразирование и синонимы.
Слияние: Reciprocal Rank Fusion (RRF) объединяет два ранжированных списка по позициям, а не по несопоставимым по шкале оценкам. Часто за слиянием идёт — это уже зона соседней главы про (RAG).
Фильтрация по метаданным: pre-filtering сужает кандидатов до поиска (точно, но ломает структуру графа/ячеек и может опустошить поиск), post-filtering фильтрует после (быстро, но рискует вернуть мало или ноль результатов при жёстком фильтре).

Обновления и масштаб

Добавление: HNSW поддерживает инкрементальную вставку, IVF-PQ обычно требует обученных центроидов и хуже переносит дрейф распределения новых данных.
Удаление: во многих индексах оно мягкое — через метку удаления (tombstone): вектор помечается удалённым, но остаётся в графе или списке до перестроения, поэтому память и полнота (recall) со временем деградируют.
Перестроение и сегменты: системы держат свежие данные в небольших растущих сегментах и периодически сливают и перестраивают индекс в фоне, чтобы вставки не блокировали поиск.
делит коллекцию между узлами ( по шардам), а повышает доступность и на чтении.

Системы: что выбирать

FAISS

Библиотека от Facebook AI Research, не сервис. Эталонный набор индексов (Flat, IVF, HNSW, PQ, IVF-PQ) с GPU-ускорением. Встраивается в свой сервинг, когда нужен полный контроль и нет требований к транзакциям и метаданным.

pgvector

Расширение PostgreSQL: типы vector и операторы расстояния (косинус, L2, inner product), индексы HNSW и IVFFlat. Если векторы живут рядом с реляционными данными, отдельная система — лишняя операционная нагрузка, и pgvector снимает этот выбор.

Milvus / Qdrant / Weaviate

Специализированные векторные БД с шардированием, репликацией, фильтрацией по метаданным и гибридным поиском из коробки. Выбор под высокое число запросов в секунду (QPS), большие коллекции и продуктовые требования к фильтрам и обновлениям.

Ключевые компромиссы

Полнота (recall), латентность и память — это треугольник: улучшая две вершины, обычно платишь третьей. Любой выбор индекса есть точка на этой поверхности компромиссов.
HNSW даёт лучшую пару «полнота / задержка» (recall/latency), но дорог по RAM и медленно строится; на миллиардных коллекциях память часто решает выбор в пользу IVF-PQ.
Квантизация (PQ/SQ/ScaNN) экономит память в разы, но снижает полноту (recall); типичный приём — приближённый отбор кандидатов по сжатым кодам с последующим точным переранжированием по сырым векторам.
Жёсткая фильтрация по метаданным конфликтует со структурой индекса приближённого поиска (ANN): pre-filtering точен, но дорог, post-filtering быстр, но может вернуть пустую выдачу.

Частые ошибки

Гнаться за числом запросов в секунду (QPS), не измеряя полноту в топ-K (recall@k) против точного перебора, — легко получить быстрый индекс, который тихо теряет релевантные результаты.

Рассогласование метрики и нормализации: индекс на L2, эмбеддинги под косинус и забытая нормализация дают бессмысленное ранжирование.

Считать индекс статичным: без стратегии удаления, перестроения и сегментов полнота (recall) и память деградируют по мере потока обновлений.

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

Связанные главы

Архитектура системы генерации с извлечением контекста (RAG) на GenAI - Соседняя глава: здесь векторный поиск — это один компонент внутри генерации с извлечением контекста (RAG), рядом с гибридным поиском, переранжированием и сборкой контекста для большой языковой модели (LLM).
Оптимизация инференса большой языковой модели (LLM) - Про инференс самой модели: prefill/decode, KV-cache, батчинг и квантизация весов — параллельный слой к слою векторного поиска.
Проектирование поисковой системы - Классический поиск с инвертированным индексом и ранжированием — основа разреженной части гибридного поиска.
Архитектура ранжирования и рекомендаций - Приближённый поиск ближайших соседей (ANN) как этап генерации кандидатов в рекомендациях: похожие пользователи и товары по эмбеддингам.