Приближённый поиск соседей (ANN): идея HNSW и IVF

Как векторные базы ищут быстро: соглашаемся на «почти точно» в обмен на скорость.

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

Главная сделка: скорость за точность

Точный k-NN гарантирует найти самых близких, но платит полным перебором. ANN говорит: «давайте искать не везде, а только в перспективных местах». Иногда он промахнётся мимо одного-двух идеальных соседей, но станет в сотни раз быстрее. Для RAG это отличная сделка: разница между 1-м и 3-м по близости чанком обычно несущественна.

Идея IVF: разбить пространство на ячейки

IVF (Inverted File Index) заранее кластеризует все векторы на группы и запоминает «центр» каждой. На запрос: сначала находим несколько ближайших центров, потом перебираем векторы только внутри этих кластеров, а не всю базу.

Без IVF: сравнить запрос со ВСЕМИ 1 000 000 векторов
С IVF:   найти 3 ближайших кластера из 1000
         перебрать только ~3000 векторов внутри них

Это аналогия с библиотекой: вы не читаете все книги, а идёте к нужному стеллажу. Параметр nprobe (сколько кластеров проверять) регулирует баланс точность/скорость.

Идея HNSW: граф «коротких путей»

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

HNSW сегодня — самый популярный индекс в векторных БД: отличное качество и скорость, хотя памяти он ест больше IVF.

Грубая модель выигрыша IVF

Покажем на цифрах, почему «искать в нескольких кластерах» в разы дешевле полного перебора.

import math

def ivf_cost(n, n_clusters, nprobe):
    # сравнения с центрами + векторы внутри проверяемых кластеров
    per_cluster = n / n_clusters
    return int(n_clusters + nprobe * per_cluster)

n = 1_000_000
clusters = 1000           # ~ sqrt(n) — частая эвристика
for nprobe in (1, 5, 20):
    cost = ivf_cost(n, clusters, nprobe)
    speedup = n / cost
    print(f"nprobe={nprobe:2}: ~{cost:>7,} сравнений, в {speedup:5.1f}x быстрее перебора")

Вывод:

nprobe= 1: ~  2,000 сравнений, в 500.0x быстрее перебора
nprobe= 5: ~  6,000 сравнений, в 166.7x быстрее перебора
nprobe=20: ~ 21,000 сравнений, в  47.6x быстрее перебора

Чем больше nprobe, тем выше точность (проверяем больше кластеров), но тем меньше выигрыш в скорости. Это и есть ручка «точность ⇄ скорость», которую крутят на практике.

Итог

ANN меняет крошечную точность на огромную скорость — для RAG это выгодно.
IVF: кластеры + проверка только ближайших (ручка nprobe).
HNSW: навигируемый граф, лидер по умолчанию в векторных БД.