Векторный поиск без перебора: как работают IVF и HNSW

Когда вектор-БД содержит миллионы эмбеддингов, поиск похожих векторов методом полного перебора становится невозможен. Два алгоритма — IVF и HNSW — решают эту задачу приблизительным поиском, находя ответ за миллисекунды вместо минут. Новая подробная статья на Habr разбирает оба подхода от математической теории к реализации на Python.

Почему точный поиск не работает В низких размерностях (2D, 3D) можно

построить пространственные индексы — k-d деревья, R-деревья. Они используют геометрию: если запрос далеко от одной части пространства, её можно исключить из поиска без потери результатов. Но в высоких размерностях (768D для BERT, 3072D для GPT-4 Turbo) эта идея ломается. Расстояния становятся нелокальными — почти все точки находятся на почти одинаковом расстоянии друг от друга. Это явление называют проклятием размерности. Традиционные индексы теряют эффективность, перестают сокращать пространство поиска, и мы возвращаемся к полному перебору — сравнению запроса со всеми миллионами векторов в БД.

IVF: кластеризация спешит на помощь IVF (Inverted

File Index) решает задачу через предварительную кластеризацию. Алгоритм использует классический k-means для разбиения пространства на условные «вёдра»-кластеры. Интуиция простая: если вектора близки в пространстве, они должны быть в одном кластере, и при поиске нужно проверить лишь несколько релевантных кластеров, а не всю базу. Процесс работает в два этапа. Во время индексации каждый вектор в БД определяется в ближайший к нему кластер (его центроид). Во время поиска система сначала находит K ближайших кластеров к запросу через быстрый поиск, потом ищет точное совпадение только внутри них. Это резко снижает количество сравнений — вместо миллионов сравнений нужно сделать несколько тысяч.

• Первый этап: k-means разбивает пространство на сотни или тысячи кластеров Второй этап: каждый вектор БД индексируется в свой кластер (сохраняется ID центроида) При поиске: находим K ближайших кластеров, потом полный поиск только внутри них IVF хорошо масштабируется на миллиарды векторов и требует относительно мало памяти. На Habr разбирают реализацию на Python с конкретными примерами кода и метриками производительности.

HNSW: иерархический граф соседства HNSW (Hierarchical

Navigable Small World) использует совсем другой подход — строит граф соседства вместо кластеров. Каждый вектор становится узлом графа, рёбра соединяют соседних (близких) векторов. Граф строится иерархически: на нижних уровнях плотное локальное окружение каждого вектора, на верхних уровнях — редкие дальние соединения для быстрого глобального приблизительного спуска. Во время поиска алгоритм начинает с точки входа на верхнем уровне и спускается вниз по иерархии, выбирая на каждом шаге соседей, которые ближе к целевому запросу. Это похоже на навигацию в большом городе: сначала едешь по магистралям, потом переходишь на местные улицы, пока не найдёшь нужный адрес.

«HNSW работает как навигатор в незнакомом городе: начнёшь с главных магистралей, потом спускаешься на местные улицы», — объясняют авторы статьи на Habr.

На практике HNSW обычно быстрее IVF для поиска с низкой задержкой, но требует больше памяти на хранение структуры графа и связей между узлами.

Что это значит

Оба алгоритма используются в современных вектор-БД: Pinecone, Weaviate, Qdrant, Milvus. Для LLM-приложений — RAG систем, поиска по документам, семантических рекомендаций, интеллектуальных чатботов — выбор алгоритма поиска напрямую влияет на скорость ответа и опыт пользователя. IVF лучше выбирать для огромных БД с ограниченной памятью, HNSW даёт преимущество при требовании минимальной задержки и при работе с более компактными наборами данных.