Масштаб и ANN-поиск

Урок объясняет, как рекомендовать среди миллионов товаров за миллисекунды с помощью приближённого поиска ближайших соседей.

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

Проблема масштаба

Two-tower и контентные модели свели рекомендацию к поиску ближайших товарных эмбеддингов к эмбеддингу пользователя. Но точный поиск (посчитать близость со всеми миллионами товаров и отсортировать) на каждый запрос слишком дорог. Если каталог — 10 миллионов товаров, а запросов — десятки тысяч в секунду, полный перебор просто не уложится в бюджет задержки.

import math

def cosine(a, b):
    num = sum(x*y for x, y in zip(a, b))
    na = math.sqrt(sum(x*x for x in a)); nb = math.sqrt(sum(y*y for y in b))
    return num / (na * nb) if na and nb else 0.0

# наивный (точный) поиск: считаем близость со ВСЕМИ товарами
query = [0.2, 0.9, 0.1]
items = {
    "i1": [0.1, 0.8, 0.2], "i2": [0.9, 0.1, 0.1],
    "i3": [0.2, 0.85, 0.15], "i4": [0.3, 0.3, 0.9],
}
scores = sorted(((cosine(query, v), k) for k, v in items.items()), reverse=True)
print("Топ-2 (точный перебор):", [k for _, k in scores[:2]])

Вывод:

Топ-2 (точный перебор): ['i3', 'i1']

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

Идея ANN

ANN строит специальную структуру-индекс, которая позволяет находить почти-ближайших, не сравнивая запрос со всеми. Главные семейства:

HNSW (графы малого мира) — навигация по слоям графа, где каждый шаг приближает к цели. Очень быстрый и точный, индустриальный фаворит.
IVF (инвертированные списки) — каталог заранее разбит на кластеры; ищем только в нескольких ближайших кластерах, а не во всём.
PQ (product quantization) — сжимает векторы, чтобы экономить память и ускорять сравнение.

Цена — приближённость: иногда настоящий ближайший сосед может быть пропущен. Но на практике потеря качества ничтожна, а ускорение — в сотни и тысячи раз.

Связь с векторными БД

Эти индексы — ровно та технология, что лежит в основе векторных баз данных (учебник «RAG и векторные БД»): FAISS, HNSWlib, а также Qdrant, Milvus, pgvector. Рекомендатель и RAG-поиск решают одну инженерную задачу — «найди ближайшие векторы быстро». Поэтому генерацию кандидатов в больших системах часто реализуют именно как запрос к векторной БД.

Как работает под капотом

Индекс строят офлайн из всех товарных эмбеддингов и периодически пересобирают при обновлении каталога/модели. Онлайн приходит эмбеддинг пользователя, индекс возвращает top-N приближённых соседей за единицы миллисекунд независимо от размера каталога (логарифмическая, а не линейная сложность у графовых методов). Параметры индекса (например, число проверяемых соседей) дают регулируемый компромисс «скорость ↔ точность».

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

Полный перебор на масштабе. Линейный поиск не выживает на миллионах товаров; нужен ANN-индекс.
Гнаться за 100% recall ANN. Последние проценты точности стоят непропорционально дорого; обычно достаточно ~95–99%.
Забыть про пересборку индекса. Устаревший индекс не содержит новых товаров — они выпадают из кандидатов.

Итоги

На масштабе точный перебор по каталогу невозможен — выручает ANN.
HNSW, IVF и PQ находят почти-ближайших на порядки быстрее.
Это та же технология, что в векторных БД (FAISS, Qdrant, pgvector).
Параметры индекса задают компромисс между скоростью и точностью.