TurboQuant в Qdrant: трюки и идеи реализации

1. Введение

TurboQuant — алгоритм скалярной квантизации векторов от Google Research, опубликованный в 2026 году. На бумаге он сжимает float32-векторы в 8× практически без потерь в качестве поиска ближайших соседей и при этом не требует обучать никакие per-dataset codebook’и. Звучит как серьёзная заявка, и я потратил несколько месяцев на её реализацию в Qdrant — со всеми расширениями, без которых «алгоритм из статьи» в production не выживает. Результат зарелизен в Qdrant 1.18.

К оригинальному TurboQuant я добавил несколько расширений. Часть придумал сам по ходу работы, часть встречалась в других реализациях (в первую очередь в llama-turbo-quant и в интерактивном объяснении Arkar Min Aung) и хорошо легли на специфику Qdrant. Я не делаю вид, что всё придумал — но постараюсь объяснить, почему каждое из этих расширений хорошо подходит к Qdrant как production-grade векторной базе.

Небольшая ремарка про код. Все сниппеты в посте — на Python, для наглядности и чтобы идею можно было воспринять без знания Rust. Реальная имплементация в Qdrant — это Rust с серьёзными SIMD-оптимизациями под AVX2 / AVX-512 / NEON; про них подробно и со вкусом рассказывает мой коллега Jojii в своём посте (TODO: ссылка). Этот пост — про идеи и алгоритмические решения; пост Jojii — про то, как заставить эти идеи бежать на железе с максимальной скоростью.

2. Цифры recall

Чтобы честно измерить, что именно дают мои расширения над оригинальным алгоритмом, я написал Python-реализацию своей версии TurboQuant (читабельный референс, лежит в отдельном репо turboquant-qdrant-showcase) и прогнал её рядом с vanilla TurboQuant из открытого pip-пакета turboquant 0.2.0 — первой публичной имплементации алгоритма от Google. Сравнение algorithm-vs-algorithm: три конфигурации на одном и том же brute-force бенчмарке.

Конфигурации:

vanilla-MSE — turboquant.TurboQuantMSE, paper Algorithm 1 (MSE-вариант).
vanilla-IP — turboquant.TurboQuantIP, paper Algorithm 2 (PROD-вариант с QJL-битом).
qdrant — моя имплементация со всеми расширениями, разобранными в секции про реализацию дальше в посте.

Данные: 6 публичных датасетов, специально подобранных так, чтобы покрыть оба сценария — эмбеддинги, у которых есть выраженная анизотропия (instruction-tuned / contrastive-trained, без Matryoshka-регуляризации), и эмбеддинги, у которых её почти нет (Matryoshka-trained или post-hoc decorrelated). По 100K векторов в корпусе и 1000 запросов на датасет, корпус сэмплируется однородно через детерминированный shuffle. На датасетах, исходно крупнее 100K (gte-multilingual-ads — 1M; wiki-cohere — мультиязычный, ~5M полный — беру en-конфиг), беру первые 100K после shuffle — это совпадает с типичным production-размером сегмента в Qdrant. В ячейках — recall@10 относительно brute-force cosine ground truth. Названия датасетов во всех таблицах ниже кликабельны и ведут на страницу датасета на HuggingFace. Таблицу можно воспроизвести командой python benchmark.py из репозитория turboquant-qdrant-showcase.

Размер бенчмарка (100K) — не случайный: в Qdrant данные нарезаны на сегменты, и моя калибровка по построению применяется per-segment, независимо. Типичный production-сегмент — тех же ~100K порядков, что и бенчмарк. То есть я тестирую ровно тот scale, на котором калибровка реально работает в production.

4 бита на координату

Датасет	vanilla-MSE	vanilla-IP	qdrant
arxiv-instr	0.815	0.774	0.954
gte-mul-ads	0.791	0.740	0.967
gemini-001	0.841	0.799	0.952
openai-3-l	0.941	0.920	0.970
openai-3-s	0.938	0.916	0.969
wiki-cohere	0.937	0.920	0.973

2 бита на координату

Датасет	vanilla-MSE	vanilla-IP	qdrant
arxiv-instr	0.696	0.627	0.840
gte-mul-ads	0.684	0.732	0.885
gemini-001	0.730	0.633	0.840
openai-3-l	0.878	0.808	0.901
openai-3-s	0.877	0.806	0.901
wiki-cohere	0.883	0.827	0.914

1 бит на координату

Датасет	vanilla-MSE	qdrant
arxiv-instr	0.609	0.686
gte-mul-ads	0.720	0.786
gemini-001	0.615	0.702
openai-3-l	0.800	0.806
openai-3-s	0.798	0.807
wiki-cohere	0.819	0.840

(vanilla-IP при 1 бите вырождается: PROD отделяет 1 бит на QJL, и на codebook остаётся ноль битов. Чтобы сравнить честно, IP нужен минимум 2-битный бюджет — поэтому в этой таблице его нет.)

Дальше в посте я разбираю по одному трюку на секцию, откуда именно эти проценты в колонке qdrant берутся. Но прежде чем туда нырять — короткий бэкграунд про сам алгоритм TurboQuant и про то, почему я выбрал именно MSE-вариант. Сравнение моей TurboQuant-имплементации с другими методами квантизации в Qdrant (SQ, BQ, и f32-baseline по recall) живёт отдельно и используется в маркетинговых материалах.

3. Что такое TurboQuant и почему я выбрал MSE-вариант

Цель TurboQuant — сжать D-мерный float-вектор до 1–4 бит на координату с минимальной потерей точности при поиске ближайших соседей и без обучения per-dataset codebook’а (arXiv:2504.19874).

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

Но в двух словах MSE-версия алгоритма выглядит так. Важный момент, который надо проговорить с самого начала: алгоритм в оригинале сформулирован для единичной сферы — то есть для cosine-метрики, когда все вектора нормированы на единичную длину. На этом предположении держится вся математика: при равномерном распределении точек на сфере и случайном повороте каждая координата ведёт себя как ~N(0, 1/D) — одинаково для всех векторов в датасете, что и позволяет применить единый Lloyd-Max codebook ко всем без исключения координатам всех без исключения векторов.

Сами шаги:

Поворот. Применяем псевдослучайное ортогональное преобразование к вектору. Это «размазывает» точки на сфере равномерно по координатам, и каждая координата начинает себя вести как гауссова с дисперсией 1/D.
Скалярная квантизация по Lloyd-Max. Каждую координату независимо квантизуем в 1, 2 или 4 бита по предпосчитанному Lloyd-Max codebook’у — это классический алгоритм из теории квантизации (Lloyd, 1957; Max, 1960), который для заданной плотности распределения итеративно находит 2^b центроид и границ между ними, минимизирующих среднеквадратичную ошибку реконструкции. Для гауссова источника он даёт известные таблицы: для 1 бита это пара ±0.798, для 4 бит — 16 центроидов от −2.733 до 2.733. Если хочется потрогать алгоритм руками — в интерактивном разборе есть отдельный раздел с виджетом, который показывает Lloyd-Max сходимость пошагово; здесь важно только то, что эти центроиды — единственная универсальная таблица в коде, и больше per-dataset codebook нигде нет.

Хранится только b·D бит индексов центроид и ничего больше — никаких per-vector scale, zero-point или сохранённых длин. Скоринг между квантизованным вектором и непрерывным запросом, прошедшим через тот же поворот, — это просто dot-product между запросом и центроидами.

Эта элегантность держится строго в рамках cosine-метрики. В Qdrant же пользователи приходят с L2 и ненормированным dot-product тоже, и для продукта это принципиально важная часть. Как я аккуратно расширяю алгоритм за пределы единичной сферы (и где у этого расширения есть честная цена) — отдельный сюжет, разберу ниже в секции про метрики.

Асимметричный и симметричный скоринг в Qdrant

Прежде чем переходить к выбору варианта, нужно проговорить одну вещь, на которой держится всё остальное: в Qdrant query-вектор не квантуется методом TurboQuant.

Когда пользователь делает поиск, оригинальный float32-запрос всё равно живёт в памяти на время одного query — он пришёл из API, и хранить его как есть бесплатно по дисковой памяти и почти бесплатно по RAM. Поэтому скоринг для пользовательского поиска идёт по асимметричной схеме: к запросу применяется только тот же поворот, что и к хранимым векторам, а дальше — обычный dot-product между непрерывным запросом и центроидами хранимого квантизованного вектора. Это сильно улучшает recall по сравнению с симметричной схемой (квантизованный-против-квантизованного), потому что весь шум квантизации остаётся только в хранимом векторе, а не удваивается.

Но в Qdrant есть и другие сценарии, где обе стороны скоринга обязательно квантизованные. При построении HNSW, при merge сегментов, при внутренней кластеризации, при rescoring внутри индекса нельзя таскать оригинальные float32-векторы — это свело бы на нет весь смысл квантизации. Для этих случаев в Qdrant отдельная ветка скоринга, работающая на двух квантизованных представлениях.

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

Почему MSE, а не PROD

В оригинальной статье есть два варианта алгоритма: TurboQuant-MSE (то, что выше) и TurboQuant-prod. Второй — это та же MSE-конструкция, но один из бит уходит не на Lloyd-Max codebook, а на бит знака случайной QJL-проекции. Зачем? Lloyd-Max центроиды по построению лежат ближе к нулю, чем оригинальные координаты, поэтому каждый dot-product на восстановленном векторе систематически усыхает (в 2/π раз для 1 бита, ≈0.88 для 2 бит, ≈0.97 для 3 бит). QJL-бит компенсирует этот bias за счёт случайного скетча, добавляя несмещённость ценой увеличения дисперсии.

Для Qdrant я целенаправленно выбрал MSE-вариант. Тому есть три причины, в порядке важности.

Во-первых, у Qdrant два равноправных пути скоринга, и они должны делить один codebook. Асимметричный путь (полный запрос против хранимого квантованного вектора) — это то, что видит пользователь во время поиска. Симметричный путь (квантованное против квантованного) — это то, что работает при построении HNSW, при merge сегментов, при rescoring и при внутренней кластеризации. TurboQuant-prod по построению асимметричен: вывод математики QJL опирается на полный запрос, без него знаковый бит не даёт сигнала. То есть на симметричном пути PROD-вариант просто не работает — пришлось бы поддерживать два независимых артефакта. MSE даёт один набор кодов, который аккуратно ложится в обе схемы: ⟨c[idx_x], c[idx_y]⟩ для симметричного, ⟨q, c[idx_x]⟩ для асимметричного. Один артефакт, два пути, ноль special case’ов.

Во-вторых, цена скоринга. QJL требует применять случайную (или Hadamard-приближённую) проекцию к каждому запросу перед тем, как комбинировать его с хранимыми битами. Это лишний O(D log D) проход поверх уже существующего поворота. MSE-путь — это «достать центроиду по индексу, накопить dot-product» — буквально несколько операций на одно скоринг-сравнение. Для онлайн-БД, скорящей миллионы кандидатов в секунду на шард, эта разница принципиальна.

В-третьих, бит-бюджет. Оба варианта асимптотически выходят на Шенноновский предел D ≈ 4^(−b), но TurboQuant-prod делит свои биты — b−1 идёт в codebook, 1 в QJL — поэтому при одинаковом суммарном бюджете подложечный MSE-codebook у PROD всегда на 1 бит беднее. Тратить весь бюджет на точность кодбука выгоднее: на bits=2 codebook уже даёт ≈0.88 fidelity, на 4 бит — ≈0.998, что и есть рабочий диапазон ANN.

Честно про trade-off. Оценка скалярного произведения через MSE имеет известный детерминированный shrinkage на низких битностях. На bits=1 теряется ≈36% от каждого dot-product, на bits=2 — ≈12%. PROD-вариант несмещённый по построению и теоретически лучше ведёт себя на adversarial-входах и в задачах, где важно абсолютное значение score (а не только ранжирование). Для Qdrant это приемлемо, потому что (а) я работаю при b ≥ 2, где shrinkage — это однородный скаляр, не влияющий на ранжирование, (б) в реальном пайплайне всегда есть rescoring top-K на оригинальных векторах, который поглощает остаточный bias до того, как он дойдёт до пользователя.

4. Особенности реализации в Qdrant

Дальше пойду по конкретным трюкам и решениям из моей реализации, в порядке от самого простого к самому содержательному:

Трюк 1. Ренормализация — bias-correction без QJL
Трюк 2. Чистое, обратимое, не персистентное вращение
Трюк 3. Компенсация анизотропии
Трюк 4. P-Square квантили вместо mean+std
Поддержка L2 и ненормированного dot-product

Откуда именно проценты в главной таблице recall берутся — разбирается ниже, по одному трюку на секцию.

5. Трюк 1. Ренормализация — bias-correction без QJL

Самый простой из трюков, и самый «перевыполняющий» по эффекту. Сразу проговорю: этот приём придумал не я. Лично я впервые увидел его в llama-turbo-quant, он же встречается и в других реализациях TurboQuant. Я взял этот приём у сообщества и применил в Qdrant — но не упомянуть его было бы нечестно, потому что именно он закрывает большую часть разрыва между vanilla и моей имплементацией.

Что он делает. Когда декодируется сохранённый вектор, получается не оригинальный X, а его аппроксимация через ближайшие центроиды. Из-за того, что центроиды Lloyd-Max лежат ближе к нулю, чем оригинал, у декодированного вектора L2-длина систематически меньше — он смещён по амплитуде. Это и есть тот самый shrinkage, который PROD-вариант исправляет через QJL.

Я делаю проще, без QJL. На этапе квантизации дополнительно сохраняю измеренную L2-длину центроидного вектора cn = ‖c[idx]‖. Эта длина — постоянная цена в 4 байта на вектор, которая окупается с лихвой.

При скоринге сохранённое отношение l2 / cn используется как scaling factor, заменяющий наивное 1/√D. То есть когда нужно восстановить настоящий dot-product из «нормализованного» raw_dot, я делю не на детерминированное √D (которое было бы правильным, если бы шума квантизации не было), а на фактически измеренную длину центроидного вектора. Это убирает per-vector shrinkage точно, без случайных проекций.

Сколько это даёт

Сравним в чистом виде: vanilla-MSE против моей имплементации с одной только ренормализацией, без других расширений. Цифры — recall@10 при 4 битах:

Датасет	vanilla-MSE	+ ренормализация	Δ, pp
arxiv-instr	0.815	0.937	+12.2
gte-mul-ads	0.791	0.944	+15.3
gemini-001	0.841	0.937	+9.6
openai-3-l	0.941	0.969	+2.8
openai-3-s	0.938	0.967	+2.9
wiki-cohere	0.937	0.972	+3.5

Важное уточнение: в этой таблице + ренормализация — это моя имплементация только с ренормализацией, без всех остальных трюков из этого поста. Чистый изолированный эффект приёма из llama-turbo-quant. Полная имплементация (со всеми трюками) даёт ещё больше — её цифры в главной таблице recall выше.

Надо обратить внимание на разрыв: на anisotropic-датасетах ренормализация одна делает +9–15pp, на изотропных — +3pp. Этот эффект коррелирует с анизотропией данных не случайно (на anisotropic-датасетах вариация cn между векторами больше, и per-vector коррекция работает заметнее), но детально это отдельная тема.

На 1-битной квантизации ренормализация почти ничего не даёт: при двух центроидах ±c норма центроидного вектора cn = c·√D одинакова для всех векторов независимо от индексов — per-vector коррекция вырождается в константный масштаб, который не меняет ранжирования. Поэтому весь выигрыш ренормализации сидит на 2 и 4 битах.

6. Трюк 2. Чистое, обратимое, не персистентное вращение

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

Чистой функцией. Нет никакого глобального состояния — поворот детерминирован относительно своих аргументов и константных захардкоженных seed’ов.
Не персистентным. Я не сохраняю матрицу вращения ни на диск, ни в metadata. Вращение полностью описывается размерностью + константами в коде.
Полностью обратимым. Есть обратный поворот, который возвращает оригинал точно (до численной ошибки), и он тоже чистый.

Hadamard как приближение случайного поворота

Я использую, как и многие другие имплементации quant-алгоритмов, преобразование Адамара. Это известный приём: Walsh-Hadamard Transform (WHT) аппроксимирует случайный ортогональный поворот за O(D log D) вместо O(D²). В этом нет ничего уникального.

Но WHT работает только на размерностях, кратных степени двойки. Реальные эмбеддинги — 384, 768, 1024, 1536, 3072 — иногда укладываются, иногда нет.

Декомпозиция на блоки степеней двойки

Дополнять до ближайшей степени двойки — расточительно (для 1025 пришлось бы дополнять до 2048). Поэтому я раскладываю размерность на сумму степеней двойки жадно: для D=300 это [256, 32, 8, 4]. Каждый блок проходит свой собственный WHT с нормировкой 1/√(block_size).

Почему одного раунда мало

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

В моей реализации — 3 раунда (permute + WHT) после первоначального WHT, итого 4 применения WHT и 3 применения пермутации. Этого эмпирически достаточно, чтобы добиться качественного перераспределения на всех датасетах, что я тестировал — на сильно неоднородном входе stddev по координатам после поворота падает в ~500 раз по отношению к исходному.

Проблемы с обычной случайной пермутацией

Если делать random permutation в лоб — нужно где-то хранить массив индексов размера D. Это:

O(D) память на каждую пермутацию (а у меня их 3).
Этот массив надо персистить в metadata — иначе после рестарта нельзя будет декодировать вектора.
Чтобы получить inverse, нужно либо построить и хранить ещё один массив, либо проходить вперёд каждый раз, что дорого.

Всё это нарушает три моих свойства (чистота, не-персистентность, обратимость). Хотелось бы уметь по чуть-чуть, без всего этого.

Мой способ: reversible LCG + Fisher-Yates

Решение — детерминированный Fisher-Yates shuffle, прокручиваемый из обратимого LCG. Распакуем по слоям.

Fisher-Yates — это классический алгоритм равномерного перемешивания массива на месте. Идём с конца к началу: на шаге i (от n − 1 до 1) берётся «случайное» число j ∈ [0, i] и arr[i] меняется местами с arr[j]. На выходе — каждая из n! возможных перестановок имеет равную вероятность. Алгоритм линейный по времени, O(1) по дополнительной памяти и тратит ровно одно случайное число на шаг.

Как сделать Fisher-Yates обратимым? Очевидное наблюдение: swap — это операция, обратная самой себе. Значит, если знать ту же последовательность чисел j и применить swap’ы в обратном порядке, то пермутация развернётся обратно в оригинал.

Самый прямой путь — сохранить эти числа где-нибудь. Но это O(n) памяти на пермутацию — те самые O(D) индексов, которых изначально и хотелось избежать. Тупик.

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

Самый наивный «обратимый» источник — это детерминированная функция от индекса: j_i = hash(seed, i) mod (i + 1). Обратимость тривиальна — на шаге i снова считается hash(seed, i), получается то же число. Работает корректно, но Qdrant заточен под максимальную производительность, а crypto-grade хеш на каждом шаге — это десятки наносекунд работы; на сегментах в сотни тысяч векторов чистая стоимость поворота начинает чувствоваться.

Поэтому я использую более элегантную и быструю конструкцию — reversible LCG.

LCG (Linear Congruential Generator) — это простейший псевдослучайный генератор, известный со времён первых компьютеров. Состояние — одно целое число, шаг вперёд: state = (A · state + C) mod 2^64 для константных A и C (я использую известную пару от Knuth для MMIX). Один шаг — одно умножение и одно сложение, работает мгновенно. По качеству распределения LCG, конечно, проигрывает современным cryptographic-grade RNG, но для задачи «дать псевдослучайный индекс для Fisher-Yates» этого с лихвой хватает — здесь не криптография, а перемешивание координат.

Ключевой трюк: уравнение шага можно алгебраически развернуть. Если state' = (A · state + C) mod 2^64, то state = A_inv · (state' − C) mod 2^64, где A_inv — модулярная инверсия A по модулю 2^64. Эту инверсию я посчитал один раз и записал константой в код. В итоге обратный шаг LCG такой же дешёвый, как прямой — то же одно умножение и одно вычитание. На Python это выглядит так:

A      = 6364136223846793005    # Knuth MMIX multiplier
C      = 1442695040888963407
A_INV  = 13877824140714322085   # A * A_INV ≡ 1  (mod 2^64)
MASK64 = (1 << 64) - 1

def lcg_step(state):
    return (A * state + C) & MASK64

def lcg_step_back(state):
    return (A_INV * (state - C)) & MASK64

# Обратный шаг — точная инверсия прямого:
assert lcg_step_back(lcg_step(42)) == 42

Дальше Fisher-Yates на этом LCG: проход вперёд даёт пермутацию, проход назад её отменяет. На каждом шаге используются верхние 32 бита состояния (об этом — ниже):

def shuffle(arr, seed):
    """Fisher-Yates на LCG. Возвращает end_state, чтобы можно было
    воспроизвести inverse только по нему."""
    state = seed
    for i in range(len(arr) - 1, 0, -1):
        state = lcg_step(state)
        j = (state >> 32) % (i + 1)
        arr[i], arr[j] = arr[j], arr[i]
    return state

def unshuffle(arr, end_state):
    """Шагаем LCG назад, отменяем swap'ы в обратном порядке."""
    state = end_state
    for i in range(1, len(arr)):
        j = (state >> 32) % (i + 1)
        arr[i], arr[j] = arr[j], arr[i]
        state = lcg_step_back(state)

В итоге вся пермутация полностью описывается тройкой (seed, count, end_state) — три 64-битных целых независимо от размерности. Сами seed’ы у меня захардкожены — их три (по одному на раунд) и менять их нельзя, потому что они вшиты в encoding каждого квантизованного вектора.

Маленькая деталь, на которой я поймал баг: брать остаток от LCG-выхода надо из верхних 32 битов, а не из нижних. Нижние биты LCG имеют короткие периоды и дают вырожденные пермутации — для count=4 мой изначальный код покрывал только 12 из 24 возможных перестановок вместо всех. Поэтому в коде выше — (state >> 32) % (i + 1), а не state % (i + 1).

В сумме: O(1) состояние на любую размерность, обратимость бесплатно, никакой персистентности.

7. Трюк 3. Компенсация анизотропии

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

Проблема: алгоритм работает для изотропных данных

TurboQuant теоретически элегантен строго на изотропных данных — на векторах, равномерно распределённых по единичной сфере. Это и было исходное предположение Google в статье: при равномерности на сфере и случайном повороте каждая координата ведёт себя как ~N(0, 1/D), и один и тот же Lloyd-Max codebook оказывается оптимальным для каждой координаты каждого вектора в датасете.

Слово «изотропный» страшно звучит, но в одном предложении это значит «нет выделенного направления — точки распределены вокруг центра одинаково во все стороны». На картинке проще:

Слева: изотропные данные. Справа: один пример того, как могут выглядеть анизотропные данные.

тяни мышью чтобы повернуть

С реальными эмбеддингами трансформеров проблема в том, что они анизотропны: внутри них есть выделенные направления с большой дисперсией («spike directions») и направления, по которым почти ничего не происходит. Поворот размазывает эту анизотропию по координатам, но не убирает её — после поворота у каждой координаты своя эмпирическая дисперсия, не равная универсальной 1/D.

Lloyd-Max codebook рассчитан строго на N(0, 1/D). Если реальные координаты имеют другое распределение — биты тратятся впустую: часть центроидов оказывается в области, где точек почти нет, а в области с большой плотностью разрешения не хватает. Вот реальный пример — распределение одной координаты после поворота на датасете dbpedia 100K — оно явно не попадает в разметку Lloyd-Max:

Распределение значений 122-й координаты после Hadamard-поворота на dbpedia-100K — гистограмма с тяжёлыми хвостами, не совпадающая с N(0, 1/D)

TurboQuant на сферически-равномерных данных доказывает, что после поворота координаты распределены как N(0, 1/D). Но это доказательство не работает для произвольных эмбеддингов — там получается что-то похожее, но не то же самое. И на квантильных границах codebook’а (где разница между «попал в правильный bin» и «не попал» определяет recall) это «не то же самое» начинает чувствоваться очень больно.

Решение: сегментация + per-coord shift+scale

В Qdrant есть архитектурная фора. В отличие от оригинального TurboQuant, который по дизайну динамический и не предполагает никакого анализа датасета, данные в Qdrant нарезаны на сегменты — обозримые куски ~100K векторов, к которым можно применить отдельный анализ. И вот что я делаю: после поворота и нормировки длины — первый pass по сегменту, для каждой координаты оцениваются shift и scale, и применяется покоординатное преобразование, которое подгоняет реальное распределение под тот участок, где Lloyd-Max codebook действительно умеет точно квантовать:

X⁺ᵢ = (Xᵢ + shiftᵢ) · scaleᵢ

После этой подгонки распределение каждой координаты ложится на Lloyd-Max codebook ровно, и центроиды используются равномерно. Та же 122-я координата dbpedia-100K, что была сверху, после shift+scale выглядит так:

Та же 122-я координата dbpedia-100K после применения shift+scale — гистограмма аккуратно ложится в разметку Lloyd-Max codebook'а

Какие именно статистики оцениваются (и почему не «просто mean+stddev») — отдельный вопрос, ему посвящён трюк 4 про P-Square. Пока для понимания идеи компенсации анизотропии достаточно того, что есть пара чисел (shift, scale) на каждую координату, и они применяются так, как написано выше.

Почему это бесплатно при скоринге

Вот тут включается асимметричность скоринга, про которую шла речь выше. Хранимый вектор квантованный, а запрос — нет. Поэтому компенсацию можно полностью переложить на сторону запроса:

Пусть M = -shift, D' = 1/scale (диагональная матрица). Хранимый вектор после shift+scale: X⁺ = (X − M) ⊘ D'. Тогда

⟨Q, X⟩ = ⟨Q, X⁺ ⊙ D' + M⟩
       = ⟨Q ⊙ D', X⁺⟩ + ⟨Q, M⟩

Повёрнутый запрос предумножается покоординатно на D', и к итоговому скору добавляется скалярная поправка qm = ⟨Q, M⟩. Формула скоринга не меняется вообще — это по-прежнему одна uniform-weight dot-сумма, просто запрос пришёл уже масштабированный. Сама поправка qm — это один float, который добавляется к raw_dot перед применением scaling-формул для конкретной метрики.

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

Сколько это даёт

Сравним мою имплементацию без компенсации анизотропии (то есть только ренормализация из трюка 1 + моё вращение из трюка 2) против полной имплементации (с shift+scale). Чистый изолированный эффект компенсации анизотропии:

На anisotropic-датасетах

Датасет	1b без	1b с	Δ	2b без	2b с	Δ	4b без	4b с	Δ
arxiv-instr	0.602	0.686	+8.4	0.792	0.840	+4.8	0.937	0.954	+1.7
gte-mul-ads	0.722	0.786	+6.4	0.840	0.885	+4.5	0.944	0.967	+2.3
gemini-001	0.614	0.702	+8.8	0.795	0.840	+4.5	0.937	0.952	+1.5

На близких к изотропным датасетах

Датасет	1b без	1b с	Δ	2b без	2b с	Δ	4b без	4b с	Δ
openai-3-l	0.801	0.806	+0.5	0.897	0.901	+0.4	0.969	0.970	+0.1
openai-3-s	0.797	0.807	+1.0	0.896	0.901	+0.5	0.967	0.969	+0.2
wiki-cohere	0.820	0.840	+2.0	0.907	0.914	+0.7	0.972	0.973	+0.1

(«без» / «с» = без / с компенсацией анизотропии. Δ — прирост recall в percentage points от включения компенсации.)

Картина такая: метод сильно улучшает recall на anisotropic-эмбеддингах (особенно на низких битностях, где margin меньше всего) и практически не делает ничего на изотропных. Это не баг и не недоработка — это в точности ожидаемое поведение, и важно, что он никогда не делает хуже. Поэтому в production он включён по умолчанию: если данные пользователя анизотропные, он бесплатно даст им заметный прирост recall’а; если изотропные — он аккуратно сводится к identity и не вносит шума.

Почему он не делает хуже

Ключевое свойство моей формулы оценки (shift, scale) (детали в трюке 4 про P-Square) — для идеально N(0, 1/D)-данных она вырождается в identity. Конкретно: shift = 0, scale = 1. Я оцениваю не mean/stddev (которые дают «по-разному настроенный» Lloyd-Max codebook на гауссовых данных и слегка ломают вещь), а квантили на тех же вероятностных уровнях, на которых лежат границы codebook’а. Если данные действительно гауссовы, эмпирические квантили совпадают с теоретическими, формула выдаёт (0, 1), и калибровка ничего не делает — буквально не вносит ни одного бита изменения в encoded вектор.

Поэтому таблица выше: на изотропных данных Δ ≈ 0 не из-за того, что калибровка «случайно ничего не сломала», а из-за того, что она по построению не должна ничего делать на изотропных данных. Это математическая гарантия, а не эмпирическое везение.

Симметричный скоринг: компенсация намеренно не применяется

Выше всё хорошо ложится для асимметричного пути: запрос непрерывный, и компенсация (D'-предумножение и поправка qm) бесплатно встраивается в существующий скоринг-цикл без потери точности. Но в Qdrant есть и второй путь — симметричный скоринг, когда обе стороны квантизованные (HNSW build, merge сегментов, внутренние сравнения). Здесь история сильно отличается, и важно проговорить, что я делаю по-другому и почему.

Чисто формально, та же алгебра, что в асимметричном случае, прекрасно раскрывается и для двух квантизованных векторов:

⟨X_a, X_b⟩ = Σ X⁺_a_i · X⁺_b_i · D'_i² + xm_a + xm_b − ⟨M, M⟩

Здесь X⁺ — это закодированный вектор (после shift+scale), D'_i² = 1/scale_i² — per-coord вес, а xm = ⟨X, M⟩ — скалярная поправка, которую можно сохранить рядом с квантизованным вектором при кодировании. Казалось бы, можно просто применять эту формулу и получать «честный» ⟨X_a, X_b⟩ для всех внутренних путей.

На практике это ломает recall. И вот почему.

В асимметричном пути per-coord вес D' живёт на стороне непрерывного запроса. Шум квантизации сидит только в X⁺ (одна сторона), и при суммировании произведений вида Q_i · D'_i · c_i ошибки шума усредняются по координатам, а большой D'_i в одной координате уравновешивается соседями. Шум усреднён, и амплификация безболезненна.

В симметричном пути обе стороны — квантизованные, и шум сидит и в c1, и в c2. Ключевая операция — c1_i · c2_i · D'_i². Тут уже произведение двух шумов умножается на D'², а D'_i² = 1/stddev_i² имеет огромный динамический диапазон: на координатах с маленькой исходной дисперсией D'² может быть в десятки и сотни раз больше, чем на координатах с большой. Эффективно получается взвешенная сумма, где несколько «шумных» координат с большим весом доминируют над всем остальным сигналом — и итоговый score становится практически случайным относительно истинной близости.

Поэтому в симметричном пути с компенсацией анизотропии я не применяю ни per-coord weighting D'², ни скалярные поправки xm + xm − ⟨M, M⟩. Считается простой uniform-weight dot между двумя квантизованными представлениями — то есть ровно та же формула скоринга, что и без компенсации. Никаких дополнительных операций, никакой ветки «если есть калибровка, то…» при скоринге.

Что при этом фактически считается? Поскольку хранимые центроиды аппроксимируют X⁺ (закодированный вектор после shift+scale), uniform-weight dot даёт приближение ⟨X⁺_a, X⁺_b⟩ — близость двух векторов в EC-пространстве, а не в оригинальном. Это другая метрика, но она полностью согласована: HNSW-граф, который строится через симметричный скоринг, оптимизируется под близость в этом же EC-пространстве, и кандидаты, найденные обходом графа, в нём же близки к запросу. Финальный top-K, который видит пользователь, всё равно скорится через асимметричный путь — где компенсация применяется честно.

1-битная метрика: запрос приходится расширять до 12 бит

На 1-битном хранении при включённой компенсации анизотропии есть отдельный нюанс — без него на этой битности recall заметно проседает.

Сначала контекст. На 1-битном хранении codebook — это просто две точки ±c, где c = sqrt(2/π) ≈ 0.798 (Lloyd-Max для N(0, 1)), то есть индекс в codebook совпадает со знаковым битом хранимой координаты. Хранимый вектор — плотная упаковка знаков (8 dim в байт), а запрос квантуется в знаковые целые BITS бит (по умолчанию 8) и комбинируется с битами данных в финальный dot. Конкретный способ того, как это эффективно вычисляется на CPU — тема отдельного поста про SIMD-оптимизации; здесь важно одно: разрядность запроса — это свободный параметр, который можно крутить без изменения формата хранилища.

Ключевой момент: на 1-битном хранилище сторона данных имеет минимальное возможное разрешение — один знаковый бит. Это значит, что точность асимметричного скоринга упирается в сторону запроса. На 2 и 4 битах данные сами несут достаточно разрешения, и шум 8-битного запроса теряется в шуме квантизации центроид. На 1 бите всё не так: каждое скалярное произведение в координате фактически равно q_i · sign(x_i), и любая ошибка в q_i идёт напрямую в финальный score без амортизации шумом данных.

Дальше включается специфика компенсации анизотропии. В обычном режиме (без shift+scale) после Hadamard-поворота координаты запроса распределены довольно равномерно, и диапазона int8 [-127, 127] хватает с запасом. Но при включённой компенсации повёрнутый запрос предумножается покоординатно на D' = 1/scale. Per-coord scale_i в реальных эмбеддингах сильно различаются — это ровно та анизотропия, ради которой и делается shift+scale. После предумножения распределение query-координат становится резко неоднородным: координаты, которым соответствует большая дисперсия в данных (scale_i большой → D'_i маленький), сжимаются почти к нулю; координаты с малой дисперсией наоборот раздуваются.

Когда дальше запрос нормируется как q_scale = 127 / max(|q|), координаты из «маленькой» группы получают целые значения вроде 0, ±1, ±2 — а это уже не сигнал, а шум округления. Скоринг на этих координатах работает фактически вхолостую: их вклад в финальный dot близок к нулю, хотя в оригинальном непрерывном запросе они имели какую-то осмысленную (пускай и небольшую) информацию.

Решение — расширить квантизацию запроса с 8 до 12 бит на случай «компенсация + 1 бит на хранилище». Тогда q_scale = 2047 / max(|q|), и даже сжатые координаты получают по ~16 уровней разрешения. Замеры показывают: 8 бит запроса даёт relative error до ~2%, 12 бит — до ~0.2%, то есть в 10 раз меньше scoring error на той же входной паре.

Цена. Сторона запроса занимает на 50% больше памяти. Но query precomputation делается один раз на поисковый запрос и переиспользуется для миллионов кандидатов в шарде — в пересчёте на одно скоринг-сравнение эта добавка размазывается до бесплатной. Сторона данных не меняется вообще: хранилище по-прежнему 1 бит на dim. Формула скоринга тоже не меняется по структуре — разрядность запроса входит в неё как параметр.

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

8. Трюк 4. P-Square квантили вместо mean+std

В предыдущем трюке shift+scale применялся на каждую координату без уточнения, как именно их оценивать. Можно было пойти простым путём: пройтись по сегменту и посчитать per-coord mean и stddev, считая, что после поворота данные нормально распределены — пускай и с произвольным mean и дисперсией. На большинстве реальных датасетов это близко к правде, но не идеально: даже после Hadamard-поворота гауссовость восстанавливается асимптотически, и на конечной размерности (особенно на низких bit-widths, где границы codebook’а очень чувствительны к хвостам) эта аппроксимация течёт.

Хуже того, Qdrant — production-grade БД, и нельзя полагаться на «обычно нормально». Что если на проде окажется датасет с тяжёлыми хвостами, бимодальный, или специально подобранный adversarial? Калибровка должна выдавать предсказуемое качество без знания о датасете.

Поэтому вместо mean/stddev я использую dataset-agnostic подход — алгоритм P-Square (Jain & Chlamtac, 1985). Это онлайн-оценка квантилей с константной памятью, не делающая никаких предположений о распределении. Эстиматор держит компактный набор «маркеров» (я использую 7 — обобщение оригинального P-Square с 5 маркерами, дающее лучшую точность в хвостах), которые двигаются с каждой новой точкой так, чтобы средний маркер сходился к нужному квантилю. Под капотом — параболическая интерполяция позиций маркеров с фоллбэком на линейную, когда параболическая выходит за пределы соседей. Состояние эстиматора — несколько чисел, обновление формально O(1) на точку.

Как используется результат

Эстиматор не один на сегмент, а по одному на каждую координату — итого dim независимых P-Square инстансов, считающих симметричный per-coord интервал [q_lo, q_hi]. Уровни квантилей выбираются хитро: пусть c_outer — самая крайняя центроида кодбука Lloyd-Max (≈0.798 для 1 бита, ≈2.733 для 4 бит). Для идеально N(0, 1) данных вероятностная масса в интервале [-c_outer, c_outer] равна 2·Φ(c_outer) − 1, где Φ — стандартная нормальная CDF. Поэтому я запрашиваю у P-Square per-coord квантили ровно на уровнях 1 − Φ(c_outer) и Φ(c_outer) — то есть на тех вероятностных позициях, на которых лежат края codebook’а в эталонной модели.

Дальше из эмпирических q_lo, q_hi собираются shift и scale:

shift = -(q_lo + q_hi) / 2           # recenter
scale =  2 · c_outer / (q_hi - q_lo) # stretch to [-c_outer, c_outer]

Ключевое свойство, ради которого этот вид калибровки и выбран: для идеально N(0, 1) данных q_lo == -c_outer и q_hi == +c_outer, поэтому shift == 0 и scale == 1 — калибровка становится identity и не делает ничего лишнего, не вносит шума на уже хорошо распределённых данных. Это и есть то самое математически-гарантированное свойство «не делает хуже», на которое опиралось обсуждение в трюке 3. Для анизотропных данных формула аккуратно растягивает per-coord эмпирический «хвостовой» интервал на тот участок, который codebook реально умеет точно квантовать. Никакой привязки к гауссовой модели — калибровка делается в той точке распределения, где находится граница codebook’а, и эта точка может находиться где угодно в реальных данных.

Стриминг через резервуар вместо all-stream P-Square

Изначально я заводил один P-Square на координату и пушил туда каждое значение из потока — буквально применяя алгоритм по его прямому назначению. Идея простая, но на production-нагрузке оказалась слишком дорогой. Формально P-Square — это O(1) на push, но за этим O(1) скрывается ~50 ns параболической интерполяции, проверок и движения маркеров. На сегменте в 100k+ векторов × 1k+ координат суммарная работа калибровки начинала доминировать над всей остальной квантизацией — настолько, что pre-pass становился самой дорогой стадией.

Поэтому стриминговую и оценочную фазы я развёл:

На стриминге — резервуарная выборка per-coord (классический Vitter’s Algorithm R). Push в резервуар — это ~5 ns: один RNG draw, один branch, один возможный store. На порядок дешевле P-Square push, и на реальных данных эта разница окупается с лихвой.
После того, как поток закончился — по содержимому каждого резервуара (параллельно по координатам) гоняется настоящий P-Square. Размер резервуара R фиксирован — ~4–8 тысяч в зависимости от того, насколько глубокий хвостовой квантиль нужен (для bits=1 анкер сидит на p≈0.79 и хватает R≈4096; для bits=4 анкер на p≈0.997 и нужен R≈8192) — и на этой ограниченной выборке P-Square уже не дорогой.

Корректность: резервуарная выборка по конструкции даёт равномерную i.i.d. выборку из всего потока — каждое из N значений имеет одинаковую вероятность R/N оказаться в резервуаре. P-Square — сходящийся алгоритм на любой равномерной выборке из распределения, что и даёт резервуар. Маркеры дополнительно сглаживают шум хвостовых порядковых статистик: брать просто sorted[k] на R≈8k и квантиле p=0.997 даёт сильно дрожащий ответ — P-Square с параболической интерполяцией на той же выборке существенно стабильнее.

Хорошее свойство: при N < R резервуар вмещает весь поток в исходном порядке, и новая схема выдаёт бит-в-бит тот же ответ, что и старая «P-Square по всему потоку». На малых сегментах ничего не теряется и ничего не меняется.

Сам стрим устроен как producer/consumer pipeline. Producer на отдельном потоке тянет векторы из входа в переиспользуемые chunk-буферы (capacity ~4k векторов, аллоцированы один раз и переиспользуются), rayon-параллельно прогоняет каждый вектор через preprocess (Hadamard rotation + length rescale) прямо в тот же буфер. Consumer (главный поток) забирает заполненный блок и rayon-параллельно сливает его в per-coord резервуары — каждый поток получает свою координату и пушит её колонку. Producer и consumer работают одновременно: пока consumer сливает один блок, producer уже наполняет следующий.

Память — это уже не бесплатно

Резервуар хранит R f64-чисел на каждую координату, итого 8 · R · D байт на время pre-pass’а. Для типичной размерности D=1024 при R=8192 это ~67 МБ, для D=3072 — ~200 МБ. Плюс пара chunk-буферов (~32 МБ при D=1024). После того как калибровка завершилась, всё это освобождается — финальный квантизованный артефакт на диске остаётся таким же компактным, как раньше (b·D бит индексов + extras).

Бюджет не зависит от размера датасета — только от dim и R. Если pre-pass упирается в память, можно уменьшить R ценой роста дисперсии оценки квантиля (на хвостовых уровнях типа p≈0.997 это плохо ощущается раньше всего) или вообще отключить компенсацию для данной коллекции.

Тестовые распределения

P-Square покрыт прицельным набором распределений с очень разным поведением хвостов: uniform, N(0, 1), Poisson(λ=2) (асимметричное, не-нормальное), Student-T с 2 степенями свободы (heavy tails, формально бесконечная дисперсия). На всех — относительная ошибка оценки квантиля укладывается в 5–10%. Это и есть главный смысл трюка: поведение калибровки перестаёт зависеть от того, насколько датасет похож на нормальное распределение — и это именно та гарантия, которая нужна production-БД, не знающей заранее, какие эмбеддинги в неё прилетят.

9. Метрики: L2 и ненормированный dot-product

Возвращаемся к ограничению, зафиксированному в начале поста: TurboQuant в оригинале живёт строго на единичной сфере — для cosine-метрики и нормированных эмбеддингов. Это ограничение алгоритма, и в обмен на него вы получаете нулевой overhead на хранение (только b·D бит индексов, ничего больше). Но Qdrant — production-БД, и для неё неприемлемо сказать пользователю «умеем только cosine». L2 — самая популярная метрика после cosine, и ненормированный dot-product тоже встречается, особенно в production-эмбеддингах с обученным масштабом.

Поэтому я аккуратно расширяю алгоритм за пределы сферы. Цена — +4 байта на вектор на сохранённую длину (L2-норму). На фоне b·D бит индексов это микроскопическая надбавка, но именно она открывает дверь к двум новым метрикам.

Ненормированный dot-product. L2-длина оригинального вектора ‖v‖ сохраняется рядом с квантизованным представлением. Внутри хранилище работает с нормированным до √D представлением (это моё расширение по сравнению с оригиналом — любой вектор превращается в «эквивалент точки на сфере» простой нормировкой), но при скоринге raw_dot умножается обратно на ‖v‖ — это восстанавливает абсолютный масштаб. Для запроса делается то же самое: ‖q‖ хранится в precomputed-структуре. Никаких ограничений на нормировку входа.

L2-метрика. L2-расстояние раскрывается через классическое тождество:

‖q − v‖² = ‖q‖² + ‖v‖² − 2⟨q, v⟩

⟨q, v⟩ уже умеем считать (по предыдущему пункту), а ‖q‖² и ‖v‖² сохранены. Складываем — получаем L2 без какой-либо потери точности относительно того, что даёт основная схема скоринга. То есть L2 стоит ровно столько же, сколько dot-product — потому что вся специфика L2 сводится к одному скалярному вычислению из уже имеющихся данных.

А что с L1?

К сожалению, для L1 трюков нет, и это не лень — поворот не сохраняет L1-норму. Любая ортогональная матрица сохраняет L2 (и косинус, потому что косинус — это нормированный dot-product), но в общем случае ‖Rx‖₁ ≠ ‖x‖₁. То есть вся математика, на которой держится быстрый скоринг через rotated quantized representation, опирается на L2-инвариантность поворота — а для L1 эта подложка просто не работает: разница между двумя векторами после поворота может иметь совершенно другую L1-норму, чем была у исходных.

Это не мешает использовать MSE TurboQuant, если у вас L1 в качестве метрики — но скоринг здесь идёт через полную деквантизацию: центроиды достаются по индексам, длина восстанавливается, применяется обратный поворот, возвращаемся в оригинальное пространство, и уже там считается честный L1. Корректно, но сильно бьёт по производительности и теряет почти весь performance-выигрыш квантизации (обратный поворот за O(D log D) на каждое скоринг-сравнение — катастрофа). Поэтому L1 в TQ — это аварийный fallback, который я не рекомендую в production-нагрузке: если у вас L1, лучше посмотреть на другие способы квантизации в Qdrant, которые с L1 совместимы по дизайну.

10. Заключение

TurboQuant — красивый алгоритм, и MSE-вариант особенно хорошо ложится на специфику векторной БД. Но между «алгоритм из статьи» и «production-grade имплементация в Qdrant» есть пропасть, которую я попытался закрыть несколькими расширениями:

Ренормализация через хранимый centroid-norm убирает quantization shrinkage без QJL и без удвоения сложности скоринга. Простой приём из llama-turbo-quant, который в одиночку даёт +9–15pp recall на anisotropic-датасетах при 4 битах.
Hadamard rotation на тройном (permute + WHT) с reversible-LCG-пермутациями — полностью чистая, обратимая, не персистентная — даёт качество близко к случайному ортогональному вращению при O(D log D) сложности и нулевой metadata.
Компенсация анизотропии через per-coord shift+scale, переложенный на сторону запроса — бесплатно по compute, заметно по recall на анизотропных эмбеддингах. На датасетах, где анизотропии нет, она по построению вырождается в identity и не вносит шума.
P-Square калибровка через эмпирические per-coord квантили, привязанные к границам codebook’а — на идеально-нормальных данных она identity, на любых других даёт корректный shift+scale без предположений о распределении.
Wide query для 1-битных центроидов в режиме компенсации анизотропии восстанавливает recall, который иначе терялся на rounding-шуме в нижней части 8-битного диапазона.
L2 и ненормированный dot вытащены за пределы единичной сферы, на которой формально живёт алгоритм, ценой +4 байта на вектор для хранимой длины. L1 расширению не поддаётся (поворот не сохраняет L1) — и это честное ограничение, в production с L1 я не рекомендую TQ.

Имплементация открыта и лежит в репозитории Qdrant — production-вариант на Rust в lib/quantization/src/turboquant/, а максимально читабельный Python-референс (с тем же набором алгоритмических трюков, без SIMD-обвески) — в отдельном репо turboquant-qdrant-showcase, оттуда же можно воспроизвести таблицу recall’а одной командой. Если что-то непонятно или интересно — пишите, обсудим.