ANN: приближённый поиск соседей (B3)

Two-tower заканчивается словами «замороженные эмбеддинги → ANN» — здесь этот ANN построен прозрачно: собственный IVF-индекс на numpy поверх реальных айтем-эмбеддингов, ручка nprobe, честный замер recall ↔ доля скана ↔ latency и boundary problem поимённо на конкретных фильмах.

⚠ На нашем каталоге (~10k айтемов) точный поиск и так укладывается в доли миллисекунды (замер — в таблице ниже, протокол — в контракте в конце страницы) — ANN здесь не нужен, и продовый /similar остаётся точным. Модуль показывает механику и цену сделки, которая становится обязательной на миллионах векторов.

строим IVF-индекс и меряем…

Теория простым языком

На больших каталогах retrieval должен укладываться в latency-бюджет без полного скана — воронка обещает «отобрать сотни кандидатов из миллионов за миллисекунды», и точный перебор ломает это обещание первым; отсюда ANN, партиционирование и candidate pruning. На малых каталогах exact может быть проще и лучше — наш /similar именно такой. ANN-индекс — инженерная цена, которой two-tower-подход оплачивает скорость на масштабе.

▸Зачем ANN, если можно посчитать точно
БылоRetrieval по эмбеддингам (two-tower): скор = скалярное произведение, кандидаты = top-K по всему каталогу.
ПроблемаТочный top-K — это O(N·d) на запрос. На нашем каталоге это единицы миллисекунд и меньше (в бюджет демо влезает), на продовых 10⁷–10⁹ айтемов — десятки-сотни миллисекунд и не влезает в бюджет retrieval.
ИдеяСогласиться на приблизительный top-K: заранее разложить векторы в структуру (кластеры/граф), в запрос сканировать только перспективную часть. Потерю точности мерить как recall@ANN и держать как guardrail.
Стало лучшеСублинейный поиск: в нашем замере nprobe=2 даёт ~96% recall, сканируя ~3% каталога — та же механика, что в FAISS/ScaNN/HNSW-индексах прода.
Осталось слабымПоявился новый источник потерь (boundary problem) и новый обслуживаемый компонент: индекс надо строить, обновлять и мониторить; recall@ANN — ещё одна цифра, которая может тихо деградировать.
ДальшеПолная воронка использует этот retrieval как первую ступень — /system-design; свежесть индекса и новые айтемы — стык с B5 cold-start.

IVF-Flat: простейший производственный индекс

Идея из двух шагов — и оба видны в лаборатории выше:

IVF-Flat
# build (офлайн, при обновлении эмбеддингов)
centroids = kmeans(item_vectors, n_clusters)   # сферический: всё L2-нормировано
lists[c] = [i for i in items if nearest(i) == c]  # inverted lists

# search (онлайн, на запрос)
probed = top_nprobe(centroids @ query)          # дёшево: n_clusters ≪ N
candidates = concat(lists[c] for c in probed)   # сканируем только их
return top_k(candidates @ query)                # точный скор на кандидатах
Boundary problem — Истинный сосед запроса может лежать в кластере, чей центроид не попал в top-nprobe — тогда его не существует для поиска, сколько бы кандидатов мы ни скорили. В этой IVF-Flat реализации без сжатия это практически единственный источник recall-потерь (§3 показывает его поимённо; внутри просканированных списков скор точный); в IVF-PQ добавляется второй — ошибка приближённого скора из-за сжатия векторов. Лечится ручкой nprobe — деньгами, а не бесплатно.
Recall@ANN ≠ Recall@K — Две разные метрики с похожими именами. Recall@K в офлайн-оценке — «нашли ли спрятанный лайк» (качество рекомендаций против таргета). Recall@ANN — «какую долю точных top-K соседей вернул приближённый индекс» (качество поиска против exact, таргет тут вообще ни при чём). Индекс с recall@ANN 0.96 теряет 4% соседей exact-поиска — как это отразится на Recall@K воронки, отдельный вопрос (обычно слабее, но не нулевой).
Метрика индекса = метрика обучения — В этой лаборатории все векторы и запросы L2-нормированы, поэтому скалярное произведение ≡ косинусная близость и сферический k-means корректен. Реальный two-tower часто обучается без нормализации — тогда retrieval-задача становится maximum inner product search (MIPS), и индекс/метрика обязаны совпадать с обучающим objective (для MIPS есть свои трюки: асимметричные преобразования, ScaNN-квантизация). «K-means + dot-product» — не универсальная схема, а следствие нормировки.

Дальше по этой же оси развиваются продовые индексы: HNSW (граф «маленького мира» вместо кластеров — жадный спуск по соседям), PQ/OPQ (сжатие векторов в коды, чтобы миллиарды влезали в память; скор становится приближённым ещё и по значению), IVF-PQ / ScaNN (комбинации). Ручки другие — сделка та же: точность ↔ скорость ↔ память.

Инженерные следствия (то, что спрашивают на дизайне)

1. Recall@ANN — guardrail, а не наблюдение. Только считать бюджет качества воронки перемножением нельзя: recall@ANN меряет пересечение с точным top-K, где все позиции равноправны, а важна судьба одного конкретного релевантного айтема — и это разные величины (замер выше показывает, насколько разные). Мониторить guardrail — значит держать эталонный набор запросов и мерить на нём сквозной recall (стык с B7).
2. Индекс живёт отдельной жизнью. Эмбеддинги переобучили — индекс надо перестроить; между ретрейнами новые айтемы либо доиндексируются инкрементально, либо их нет в retrieval вовсе — это ещё одно лицо cold-start (B5).
3. Несбалансированные кластеры → хвост latency. §2: плотные регионы дают толстые inverted-lists; p50 красивый, p95 — нет. В проде лечат балансировкой, квотами на скан, ранним выходом.

⚠️ Что может пойти не так

  • Мерить только скорость и не мерить recall@ANN — индекс может тихо резать лучших кандидатов, офлайн-метрики воронки съедут без видимой причины.
  • Считать recall@ANN константой — он зависит от распределения запросов и дрейфует вместе с ним и с каждым ретрейном эмбеддингов.
  • Забыть про обновление индекса — новые айтемы не существуют для retrieval, пока не проиндексированы (cold-start на ровном месте).
  • Тянуть ANN на маленький каталог — на десятках тысяч векторов exact-поиск проще, точнее и уже укладывается в бюджет (наш /similar — точный).
  • Сравнивать ANN-индексы по одной точке — это кривая recall↔latency↔память; сравнивают кривые при фиксированном recall.

🧠 Проверь себя: После ретрейна two-tower офлайн-NDCG вырос, а онлайн-метрики retrieval просели. ANN-индекс не перестраивали. Что проверить первым?

Где это в дорожной карте

Это B3 — ANN-под-этап retrieval-диагностики: последний недостающий кусок пути «эмбеддинги → кандидаты» (two-tower → ANN → воронка). Дальше по треку — B4 feature store и B6 re-rank constraints, ведущие к полному capstone.

Бюджет качества: почему два recall нельзя перемножать

Загружаем данные

Что дальше

Чем продолжить — прямых наследников у модуля нет — это следующий шаг по карте

System design case studies◐Четыре продукта на одном каркасе-цикле: бизнес-задача, логи, split, архитектура, A/B, мониторинг.

Можно читать параллельно — тот же блок, порядок между ними не важен

BPR — pairwise ranking◐Learning-to-rank: обучение на «позитив выше негатива», а не на предсказание оценки.NeuMF — Neural CF◐GMF + MLP и честный урок «нейросеть ≠ лучше» на этом датасете.

До финальной сборки не хватает ещё 11 модулей по этому пути.

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

Источники