Часть II · Кандидатогенерация · глава 9 из 19

ANN, квантизация и semantic IDs

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

Что унести из главы

ANN приближённый по определению. Он не «иногда ошибается» — он торгует полнотой за скорость, и ручка этого размена крутится в рантайме без перестроения индекса.
Полный перебор: 5.1 млрд операций на запрос при каталоге 10 млн и размерности 256. Порядка 100 мс против бюджета в 10.
Квантизация сжимает в 32 раза — 32 байта на вектор вместо 1024 — ценой заметной ошибки в расстоянии.
Semantic ID из шести уровней по 256 — это 6 байт вместо 1024. И трёх уровней уже хватает, чтобы адресовать айтем в каталоге на 10 млн; остальные уточняют.

1. Почему точный поиск не годится

Арифметика перебора

Задача после обучения двух башен — найти $k$ айтемов с максимальным скалярным произведением. Это MIPS, maximum inner product search.

$$ \operatorname{top-}k(u) \;=\; \operatorname*{arg\,max}_{i \in \mathcal{I}}{}^{(k)}\; \langle p_u, q_i\rangle $$

Наивно это $O(|\mathcal{I}| \cdot d)$ на запрос. При каталоге 10 млн и размерности 256:

5.1 млрд операций на один запрос;
около 100 мс при 50 GFLOPS — на порядок больше бюджета ретривала;
10.2 ГБ памяти под индекс во float32.

Числа воспроизводятся скриптом _tools/ann_demo.py в этом репозитории.

И это на один запрос. Разрыв в порядок величины константами не закрывается — нужна другая структура данных.

MIPS — это не поиск ближайших соседей

Важное различие, которое любят на собеседованиях. У косинусной близости норма $\lVert q_i\rVert$ сокращается, у скалярного произведения — нет.

Поэтому MIPS систематически предпочитает айтемы с большой нормой, а норма при обучении растёт с популярностью. Это встроенный popularity bias самой геометрии, а не данных.

Практически: индекс надо строить под ту меру, которую оптимизирует модель. Варианты — либо нормировать эмбеддинги и работать с косинусом, либо строить индекс с inner-product метрикой, либо свести MIPS к обычному поиску соседей добавлением координаты.

2. HNSW: как устроен приближённый поиск

Hierarchical Navigable Small World — самая распространённая структура для ANN. Концептуально это skip-list, обобщённый на метрическое пространство: несколько слоёв, каждый следующий плотнее предыдущего, и на каждом слое граф обладает свойством small world — между любыми двумя точками есть короткий путь.

На каждом следующем уровне точек примерно в M раз меньше. Отсюда ожидаемая сложность поиска O(log N) — как в skip-list.

Построение и поиск

Построение. Точки добавляются по очереди. Для каждой сэмплируется максимальный уровень из геометрического распределения с $\lambda = 1/M$ — то есть экспоненциальное прореживание, на каждом следующем уровне точек примерно в $M$ раз меньше. Во все слои ниже максимального точка попадает автоматически. Затем ограниченный обход с очередью размера efConstruction, и найденные $M$ ближайших соединяются рёбрами.

Поиск. Стартуем с верхнего слоя, где точек мало. На каждом слое идём по соседям, пока жадно уменьшается расстояние до запроса, затем проваливаемся ниже. На нижнем слое — ограниченный обход с очередью efSearch, по дороге поддерживая кучу с топ-$k$.

efSearch — главная ручка

Размер очереди на нижнем слое — это размен «полнота против задержки» на уже построенном индексе. Крутится в рантайме, перестроение не требуется.

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

Два слабых места

Память. Граф хранит до $M$ рёбер на вершину на каждом слое, поэтому HNSW заметно прожорливее квантованных индексов. Именно из-за этого существуют IVF-PQ и ScaNN.
Обновления. Удаление делается пометкой, и индекс со временем деградирует, требуя перестроения. Для быстро обновляемого каталога это отдельная инженерная боль — и одна из причин, по которой в ленте новостей ANN может проигрывать более простым источникам.

Что здесь надо увидеть

Поставьте efSearch = 1: обход посещает считанные узлы и находит малую часть настоящих соседей. ANN не гарантирует правильный ответ — он приближённый по определению.
Тяните efSearch вверх: Recall@10 доходит до 1.00, но число посещённых узлов растёт втрое. Правая кривая показывает обе величины сразу — это и есть парето-фронт «полнота против латентности».
Дальше кривая выполаживается: полнота уже единица, а обход продолжает дорожать. Работать надо в точке перегиба, а не правее.

Что сказать на собесе: «HNSW — многослойный граф с экспоненциальным прореживанием, поиск $O(\log N)$. efSearch меняет полноту на задержку в рантайме без перестроения. Слабые места — память под рёбра и деградация при удалениях».

3. Квантизация: платим точностью за память

Второе семейство индексов экономит не время обхода, а память и стоимость расстояния.

Product quantization

Вектор режется на $m$ подвекторов, для каждого куска обучается свой кодбук из $2^b$ центроидов, и вектор хранится как $m$ номеров центроидов вместо $d$ чисел.

$$ q_i \;\approx\; \bigl[\,c^{(1)}_{k_1},\; c^{(2)}_{k_2},\; \ldots,\; c^{(m)}_{k_m}\,\bigr], \qquad k_j \in \{1 \ldots 2^{b}\} $$

Расстояние считается по кодбукам через предподсчитанную таблицу: для запроса один раз считаются расстояния до всех центроидов, дальше расстояние до любого вектора — это $m$ сложений.

Сколько это экономит

Каталог 10 млн, размерность 256, $m = 32$ подвектора по 8 бит:

исходно	10.2 ГБ	1024 байта на вектор
после PQ	0.32 ГБ плюс 0.3 МБ кодбуков	32 байта на вектор
сжатие	в 32 раза

Числа воспроизводятся скриптом _tools/ann_demo.py.

Цена честная и её стоит назвать: средняя ошибка на координату после квантования — около 0.43 при разбросе координат 1.0. То есть расстояния считаются заметно приближённо, и полнота падает.

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

Когда ANN вообще не нужен

Отдельная линия, о которой стоит знать: если каталог помещается в память GPU, полный перебор может оказаться быстрее приближённого поиска на CPU. Матричное умножение — ровно та операция, под которую GPU и сделан.

Выигрыш не только в скорости. Точный перебор снимает три проблемы разом: нет потери полноты, нет перестроения индекса при обновлениях, и скор может быть не скалярным произведением — а значит две башни перестают быть обязательными, и можно считать более выразительную функцию сходства.

Ограничение простое: каталог должен влезать. Для десятков миллионов айтемов с небольшой размерностью это уже реально.

4. Semantic IDs: вектор превращается в код

Другой подход к той же проблеме. Вместо того чтобы искать по вектору, заменим вектор коротким иерархическим кодом.

Residual quantization

Кодируем вектор последовательно: первый кодбук приближает сам вектор, второй — остаток после первого приближения, третий — остаток после второго, и так далее.

$$ r_0 = q_i, \qquad k_\ell = \arg\min_j \lVert r_{\ell-1} - c^{(\ell)}_j \rVert, \qquad r_\ell = r_{\ell-1} - c^{(\ell)}_{k_\ell} $$

Айтем превращается в кортеж $(k_1, k_2, \ldots, k_L)$. Ключевое отличие от product quantization: код получается иерархическим. Первый уровень задаёт грубую область, каждый следующий уточняет.

Арифметика кода

Типичная конфигурация — 6 уровней по 256 значений:

адресуемых комбинаций	$256^6 \approx 2.8 \cdot 10^{14}$
длина кода	48 бит = 6 байт
против float32-вектора(256)	1024 байта
сжатие	в 171 раз

Числа воспроизводятся скриптом _tools/ann_demo.py.

Запас по адресному пространству при каталоге 10 млн — семь порядков. Значит коллизии, если они есть, возникают не от нехватки места, а от того, что два айтема действительно попали в одну ячейку по смыслу.

Иерархия — вот что здесь главное

При каталоге 10 млн:

Уровней кода	Групп	Айтемов в группе
1	256	≈ 39 062
2	65 536	≈ 153
3	16 777 216	меньше одного

Числа воспроизводятся скриптом _tools/ann_demo.py.

Трёх уровней уже хватает, чтобы адресовать конкретный айтем. Остальные уточняют, а не различают — и это не избыточность, а свойство, ради которого всё делается.

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

И отсюда — generative retrieval

Если айтем это последовательность из шести токенов, то рекомендация становится задачей генерации последовательности: модель предсказывает код токен за токеном, как языковая модель предсказывает слова.

Что это меняет:

Индекс исчезает. Нет ANN, нет перестроения, нет размена полноты на задержку — модель просто порождает код.
Скор перестаёт быть скалярным произведением. Ограничение двух башен снимается: авторегрессия видит уже сгенерированные токены.
Появляется своя проблема: модель может сгенерировать код, которому не соответствует ни один айтем. Лечится ограниченным декодированием по префиксному дереву существующих кодов.

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

Что здесь надо увидеть

Добавляйте уровни кода и смотрите на ошибку восстановления: первый даёт грубое приближение, каждый следующий срезает остаток. Кривая быстро выполаживается.
Уменьшите размер кодбука: ошибка растёт, зато код короче. Это тот же размен «память против точности», что у PQ.
Сравните с product quantization при равном числе бит: у RQ код иерархичен, а у PQ куски независимы — и общего префикса у похожих айтемов не возникает.

Что сказать на собесе: «Semantic ID — иерархический код из остаточного квантования. Даёт сжатие в сотни раз и общий префикс у похожих айтемов, откуда холодный старт и generative retrieval. Цена — потеря точности и риск сгенерировать несуществующий код».

5. Что выбрать

Подход	Когда	Чем платим
HNSW	каталог до десятков миллионов, нужна высокая полнота, обновления умеренные	память под граф, деградация при удалениях
IVF-PQ и родственники	каталог не помещается в память в исходном виде	заметная потеря точности, нужен двухфазный поиск
Полный перебор на GPU	каталог влезает в память GPU	стоимость железа; зато свобода в выборе меры сходства
Semantic IDs	нужен холодный старт и компактность, есть ресурс на исследование	потеря точности, риск невалидных кодов, зрелость подхода

И общее правило, которое стоит держать в голове: выбор индекса — это не выбор алгоритма, а выбор точки на кривой «полнота против задержки против памяти». Сравнивать варианты имеет смысл только при зафиксированных двух из трёх.

Вопросы с собеседований

Почему нельзя просто перебрать все векторы?

Арифметика не сходится. При каталоге 10 млн и размерности 256 это 5.1 млрд операций на запрос — порядка 100 мс при 50 GFLOPS, тогда как бюджет ретривала обычно 10 мс. Разрыв в порядок величины константами не закрывается.

Плюс память: 10.2 ГБ во float32 только под сами векторы.

Оговорка: если каталог влезает в память GPU, полный перебор может оказаться быстрее приближённого поиска на CPU, и тогда он предпочтительнее — нет потери полноты, нет перестроения индекса, и скор не обязан быть скалярным произведением.

Чем MIPS отличается от поиска ближайших соседей?

У косинуса норма вектора сокращается, у скалярного произведения — нет. Поэтому MIPS систематически предпочитает айтемы с большой нормой, а норма при обучении растёт с популярностью. Получается popularity bias, заложенный в саму геометрию, а не в данные.

Практическое следствие: индекс надо строить под ту меру, которую оптимизирует модель. Либо нормировать эмбеддинги и работать с косинусом, либо брать индекс с inner-product метрикой, либо свести MIPS к обычному поиску соседей добавлением дополнительной координаты.

Как устроен HNSW и что такое efSearch?

Многослойный граф — по сути skip-list, обобщённый на метрическое пространство. Уровень точки сэмплируется из геометрического распределения, поэтому на каждом следующем слое точек примерно в M раз меньше. Поиск начинается сверху, где точек мало, жадно спускается по рёбрам и проваливается на слой ниже. Ожидаемая сложность $O(\log N)$.

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

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

Что даёт product quantization и чем за это платят?

Вектор режется на m подвекторов, каждый кодируется номером центроида из своего кодбука. При 256 измерениях, 32 подвекторах по 8 бит вектор занимает 32 байта вместо 1024 — сжатие в 32 раза, каталог на 10 млн ужимается с 10.2 ГБ до 0.32 ГБ.

Плюс расстояния считаются быстрее: для запроса один раз считаются расстояния до всех центроидов, дальше расстояние до любого вектора — m сложений по таблице.

Платят точностью: средняя ошибка на координату около 0.43 при разбросе 1.0. Поэтому используют двухфазный поиск — по сжатому индексу отобрать сотни кандидатов, затем пересчитать точные расстояния только для них.

Что такое semantic IDs и зачем они нужны?

Иерархический код, получаемый остаточным квантованием: первый кодбук приближает вектор, второй — остаток, третий — остаток от остатка. Айтем становится кортежем из нескольких токенов.

Арифметика: 6 уровней по 256 дают $2.8 \cdot 10^{14}$ комбинаций при длине кода 6 байт против 1024 у float32-вектора — сжатие в 171 раз. При каталоге 10 млн трёх уровней уже хватает, чтобы адресовать айтем; остальные уточняют.

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

Что такое generative retrieval и в чём его риск?

Если айтем — последовательность токенов, рекомендация становится генерацией: модель предсказывает код токен за токеном, как языковая модель предсказывает слова. Индекс при этом исчезает вовсе: нет ANN, нет перестроения, нет размена полноты на задержку.

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

Риск специфический: модель может сгенерировать код, которому не соответствует ни один существующий айтем. Лечится ограниченным декодированием по префиксному дереву валидных кодов. И оценивать подход стоит сдержанно — до масштаба десятков миллионов айтемов его довели немногие.

Шпаргалка одним экраном

Почему ANN

5.1 млрд операций и 100 мс на запрос при 10 млн × 256. Бюджет 10 мс.

MIPS ≠ NN

Норма не сокращается и растёт с популярностью. Индекс строить под метрику модели.

HNSW

Слои с прореживанием в M раз, поиск $O(\log N)$. efSearch — ручка полноты в рантайме.

PQ

32 байта вместо 1024, сжатие 32×, ошибка 0.43 на координату. Отсюда двухфазный поиск.

Semantic ID

6 уровней × 256 = 6 байт, сжатие 171×. Трёх уровней хватает адресовать, остальные уточняют.

Выбор

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

Первоисточники

Y. Malkov, D. Yashunin. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs, 2016 — оригинальная работа по HNSW.
H. Jégou, M. Douze, C. Schmid. Product Quantization for Nearest Neighbor Search, TPAMI 2011.
R. Guo, P. Sun et al. Accelerating Large-Scale Inference with Anisotropic Vector Quantization, ICML 2020 — ScaNN и квантизация, заточенная под MIPS.
S. Rajput, N. Mehta et al. Recommender Systems with Generative Retrieval, NeurIPS 2023 — semantic IDs и генеративный ретривал.
Числа главы: _tools/ann_demo.py в этом репозитории.

адресуемых комбинаций	\(256^6 \approx 2.8 \cdot 10^{14}\)
длина кода	48 бит = 6 байт
против float32-вектора(256)	1024 байта
сжатие	в 171 раз