Вечная математика TurboQuant: как сжать KV-кэш до предела Шеннона

Статья “TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate” (Zandieh et al., 2025) сейчас завирусилась после того, как попала на ICLR 2026; вот и Google Research опубликовал блогпост про неё только сейчас. Акции производителей памяти — Samsung, SK Hynix, Micron — упали на 3–6% за один день, и маркетинговые заголовки зазвучали в духе “ $450B Wiped Out – Google TurboQuant Just Crashed RAM Prices 30% Overnight“.

На это ужасно смешно смотреть, потому что на самом деле статья висит на arXiv с апреля 2025 года, ей уже год. А математика, на которой она стоит, — теория кодирования Шеннона, алгоритм Ллойда-Макса, лемма Джонсона-Линденштраусса — и вовсе вечна. Сегодня разберёмся, почему эта работа действительно красивая и важная, несмотря на несвоевременный хайп.

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

Зачем нужна квантизация: контекст проблемы

Числа с плавающей точкой — это дорого

Начнём с самого начала. Нейронные сети хранят и обрабатывают вещественные числа. Стандартный формат — float16 или bfloat16, т.е. 16 бит на число. Модель с 70 миллиардами параметров — это 70 миллиардов таких чисел, т.е. порядка 140 ГБ только на веса. А ведь при инференсе модели нужно ещё хранить промежуточные вычисления.

Самый прожорливый из промежуточных буферов — это KV-кэш (key-value cache). Напомню кратко, как работает механизм внимания в трансформере: для каждого нового токена модель вычисляет вектор запроса (query) и сравнивает его со всеми предыдущими ключами (keys), чтобы определить, на какие части контекста обратить внимание. Значения (values) затем взвешиваются по этим оценкам.

Так вот, чтобы не пересчитывать ключи и значения заново на каждом шаге, их хранят в KV-кэше.

Размер этого кэша растёт линейно с длиной контекста и пропорционален числу слоёв и голов внимания. Для модели на 70B параметров с контекстом в 32K токенов KV-кэш может занимать порядка 80 ГБ — больше, чем сами веса модели. Это главное узкое место при использовании LLM, особенно в сценариях, где нужен длинный контекст.

Идея квантизации

Квантизация — это замена “дорогих” вещественных чисел на “дешёвые” целые с малым числом бит. Давайте вместо 16-битных float хранить, скажем, четырёхбитные или даже двухбитные целые. Конечно, при этом мы теряем точность, но если потери окажутся маленькими, то за экономию памяти в 4–8 раз это звучит неплохо.

Формально задача квантизации выглядит так. Нам нужна пара функций: квантизация $Q: \mathbb{R}^d \to {0,1}^B$ и деквантизация $Q^{-1}: {0,1}^B \to \mathbb{R}^d$ , где $B = b \cdot d$ — общее число бит, а $b$ — битовая ширина (среднее число бит на координату). Цель — минимизировать искажение:

$D_{\text{MSE}} = \mathbb{E}\left[|x - Q^{-1}(Q(x))|_2^2\right].$

Это MSE (mean squared error) — квадрат ошибки реконструкции. Есть и второй критерий, который оказывается даже важнее для механизмов внимания:

$D_{\text{prod}} = \mathbb{E}\left[|\langle y, x \rangle - \langle y, Q^{-1}(Q(x)) \rangle|^2\right],$

т.е. ошибка в скалярных произведениях. Веса внимания в трансформере — это именно скалярные произведения query и key.

Типы квантизации

Квантизация бывает скалярной и векторной. Скалярная квантизация — это когда каждую координату вектора квантизуем независимо. Векторная — когда квантизуем вектор целиком, учитывая зависимости между координатами.

Также различают data-dependent (оффлайн) и data-oblivious (онлайн) квантизацию. Оффлайн-квантизация сначала смотрит на данные, строит по ним словари (codebooks), а уже потом использует их для квантизации. Классический пример — Product Quantization (PQ), который разбивает вектор на подвекторы, на каждом подвекторе обучает k-means, а потом хранит только индексы ближайших центроидов.

Недостатки этого подхода очевидны: нужна предварительная обработка, она дорогая, и если данные изменились (а KV-кэш меняется на каждом шаге порождения), то, формально говоря, всё надо переобучать заново.

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

Проблема нормализации

Есть ещё одна тонкость, которая делает задачу квантизации KV-кэша нетривиальной. Стандартные скалярные квантизаторы работают поблочно: берём блок из $g$ координат, вычисляем для него минимум и максимум (или среднее и масштаб), и равномерно разбиваем этот диапазон на $2^b$ уровней. Но эти параметры нормализации (их тут называют zero point и scale) нужно хранить в полной точности для каждого блока! При блоке из 128 чисел и 2-битной квантизации это добавляет порядка 0.5–1 бит на число, что на самом деле довольно существенный overhead.

Именно эту проблему решает PolarQuant, о котором мы поговорим ниже. А TurboQuant избавляется от нормализации совсем другим способом — через случайные повороты.

Нижняя граница Шеннона: почему лучше почти невозможно

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

Теорема Шеннона о кодировании с искажением

В 1959 году Клод Шеннон доказал теорему о кодировании с допустимым искажением (lossy source coding); про неё нет статьи википедии, как про lossless, но это тоже знаменитый результат.

Суть теоремы в том, что для любого случайного источника $x \in \mathbb{R}^d$ с дифференциальной энтропией $h(x)$ , если мы хотим закодировать $x$ с помощью $B$ бит, то минимально достижимое MSE ограничено снизу:

$D(B) \geq \frac{d}{2\pi e} \cdot 2^{(2/d)(h(x) - B)}.$

Эта оценка, известная как Shannon Lower Bound (SLB), представляет собой фундаментальный предел, который никакой алгоритм не может преодолеть. Доказывается он через так называемый backward Gaussian test channel: если мы добавим к $x$ оптимальный гауссовский шум, создающий mutual information не более $B$ бит, то MSE реконструкции будет не меньше указанной величины.

Формально говоря, пусть $D(p_X, B) := \inf{\mathbb{E}[|x - y|_2^2] : I(x; y) \leq B}$ , где инфимум берётся по всем совместным распределениям $(x, y)$ с ограниченной взаимной информацией. Тогда SLB утверждает, что

$D(p_X, B) \geq \frac{d}{2\pi e} \cdot 2^{(2/d)(h(x) - B)}.$

Применение к единичной сфере

Теперь давайте применим SLB к случаю, который нас интересует: пусть $x$ равномерно распределён на единичной сфере $S^{d-1}$ . Это ключевой случай для TurboQuant, потому что алгоритм будет начинаться со случайного поворота, который делает вектор равномерным на сфере.

Энтропия равномерного распределения на $S^{d-1}$ равна логарифму площади сферы:

$h(x) = \log_2 A_d, \quad \text{где } A_d = \frac{2\pi^{d/2}}{\Gamma(d/2)}.$

Здесь $A_d$ — площадь поверхности единичной сферы в $\mathbb{R}^d$ . Подставим это в SLB:

$D(B) \geq \frac{d}{2\pi e} \cdot A_d^{2/d} \cdot 2^{-2B/d}.$

Теперь нужно оценить $A_d^{2/d}$ . Используя формулу Стирлинга для гамма-функции $\Gamma(d/2) \approx \sqrt{2\pi/(d/2)} \cdot (d/(2e))^{d/2}$ , получим

$A_d = \frac{2\pi^{d/2}}{\Gamma(d/2)} \geq \left(\frac{2\pi e}{d}\right)^{d/2} \cdot \sqrt{\frac{2d}{\pi}} \cdot (1 - O(1/d)).$

Возведём в степень $2/d$ :

$A_d^{2/d} \geq \frac{2\pi e}{d} \cdot (1 - O(1/d)).$

Подставим обратно:

$D(B) \geq \frac{d}{2\pi e} \cdot \frac{2\pi e}{d} \cdot 2^{-2B/d} \cdot (1 - O(1/d)) = 2^{-2B/d} \cdot (1 - O(1/d)).$

При $B = bd$ (т.е. $b$ бит на координату) мы получим, что

${D(B) \geq 2^{-2b} = \frac{1}{4^b}.}$

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

От MSE к скалярным произведениям

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

$D_{\text{MSE}} = \sum_{j=1}^{d} \mathbb{E}\left[|x_j - (Q^{-1}(Q(x)))_j|^2\right] = \sum{j=1}^{d} \mathbb{E}\left[|\langle e_j, x \rangle - \langle e_j, Q^{-1}(Q(x)) \rangle|^2\right] \geq \frac{1}{4^b},$

где $e_j$ — стандартные базисные векторы. По принципу Дирихле, существует координата $j$ , для которой

$\mathbb{E}\left[|\langle e_j, x \rangle - \langle e_j, Q^{-1}(Q(x)) \rangle|^2\right] \geq \frac{1}{d} \cdot \frac{1}{4^b}.$

Это и есть нижняя граница на ошибку скалярного произведения для $y = e_j \in S^{d-1}$ :

${D_{\text{prod}} \geq \frac{|y|_2^2}{d} \cdot \frac{1}{4^b}.}$

Минимакс Яо

Есть ещё один тонкий момент. Нижняя граница Шеннона доказана для фиксированного случайного распределения входов (равномерного на сфере). А нам нужна граница для худшего случая по входам при рандомизированном квантизаторе.

Здесь помогает принцип минимакса Яо (Yao’s minimax principle): ожидаемая ошибка оптимального рандомизированного алгоритма на худшем входе равна ожидаемой ошибке оптимального детерминированного алгоритма на худшем случайном распределении входов. Поскольку равномерное распределение на сфере — это одно из возможных распределений, нижняя граница для него является нижней границей и для худшего сценария.

В итоге мы получили, что для любого рандомизированного квантизатора $Q$ с битовой шириной $b$ существует такой вектор $x \in S^{d-1}$ , что $D_{\text{MSE}}(Q) \geq 1/4^b$ .

PolarQuant: полярные координаты убирают overhead

Прежде чем перейти к TurboQuant, расскажем о PolarQuant (Han et al., 2025) — это другая работа того же коллектива, которая решает проблему overhead’а нормализации принципиально другим способом. Замечу, что здесь произошла коллизия в названиях: есть ещё одна независимая работа Wu et al. (NeurIPS 2025), которая тоже называется PolarQuant и тоже использует полярные координаты, но в другом контексте; путать их не надо.

Проблема: выбросы и нормализация

Стандартная скалярная квантизация (например, KIVI) работает поблочно: берём блок из $g$ координат, вычисляем для него scale и zero-point, квантизуем. Проблема в том, что в KV-кэше реальных LLM координаты содержат выбросы (outliers) — отдельные каналы с аномально большими значениями. Из-за одного выброса приходится расширять диапазон квантизации для всего блока, что убивает точность остальных координат. А параметры нормализации (scale, zero-point) нужно хранить в полной точности — при 2–4 битовой квантизации это может добавлять 1–2 бита overhead.

Идея PolarQuant

PolarQuant решает проблему в два шага:

1. Random preconditioning. Умножаем вектор $x \in \mathbb{R}^d$ на случайную матрицу $S \in \mathbb{R}^{m \times d}$ с независимыми гауссовскими элементами. По лемме Джонсона-Линденштраусса, это сохраняет нормы и скалярные произведения с малым искажением. Но ключевое свойство в том, что после такого умножения вектор $Sx$ имеет многомерное нормальное распределение $\mathcal{N}(0, |x|_2^2 I_m)$ . Выбросы исчезают, потому что координаты становятся одинаково распределёнными.

2. Переход к полярным координатам. А теперь собственно “полярная” часть. Вместо того чтобы квантизовать декартовы координаты $(x_1, x_2, \ldots, x_d)$ , PolarQuant разбивает вектор на пары $(x_1, x_2), (x_3, x_4), \ldots$ и переводит каждую пару в полярные координаты $(r, \theta)$ :

$r = \sqrt{x_1^2 + x_2^2}, \quad \theta = \arctan(x_2 / x_1).$

Затем пары радиусов снова группируются и переводятся в полярные координаты — и так рекурсивно, пока не останется один финальный радиус (по сути, норма вектора) и набор углов.

Почему это работает

После умножения на случайную матрицу углы $\theta$ в полярном разложении имеют известное и сильно концентрированное распределение. Для пары независимых гауссовских координат $(x_1, x_2) \sim \mathcal{N}(0, \sigma^2 I_2)$ угол $\theta = \arctan(x_2/x_1)$ равномерен на $[-\pi, \pi]$ .

Но на более глубоких уровнях рекурсии, когда мы берём полярные координаты от пар радиусов (которые имеют хи-распределение), распределение углов становится похожим на бета-распределение, сильно сконцентрированное вокруг $\pi/4$ .

Распределение $\theta$ на каждом уровне рекурсии авторы выводят аналитически. Для пары случайных величин $r_1 \sim \chi_{d_1}$ , $r_2 \sim \chi_{d_2}$ угол $\theta = \arctan(r_2/r_1)$ имеет плотность

$f_\Theta(\theta) = \frac{\Gamma((d_1+d_2)/2)}{\Gamma(d_1/2)\Gamma(d_2/2)} \cdot 2 \cos^{d_1-1}(\theta) \sin^{d_2-1}(\theta), \quad \theta \in [0, \pi/2].$

Это масштабированное бета-распределение на $[0, \pi/2]$ , и в высоких размерностях оно очень сильно сконцентрировано, с типичным отклонением от среднего порядка $O(1/\sqrt{d})$ .

Что это даёт? Получается, что диапазон значений углов известен заранее и не зависит от данных. Не нужно вычислять min/max для каждого блока, не нужно хранить scale и zero-point. Оптимальный квантизатор для каждого угла можно предвычислить раз и навсегда, и overhead нормализации сводится буквально к нулю.

В полной точности нужно хранить только финальный радиус (норму вектора), но это единственное число на весь вектор, который имеет размерность вроде $d=128$ ; этим overhead’ом можно уже и пренебречь.

Результаты PolarQuant

На бенчмарке Needle-in-a-Haystack (где задача ставится как поиск спрятанного предложения в огромном тексте) PolarQuant набирает 0.995, а сеть с полной точностью — 0.997. Это лучше KIVI (0.981) и существенно лучше pruning-подходов типа SnapKV (0.858). Авторы также пишут, что порождение становится на 14% быстрее, чем KIVI, при лучшем качестве.

TurboQuant: ключевые идеи

Теперь к главному герою. TurboQuant — это зонтичный метод, объединяющий идеи из PolarQuant и QJL в единый пайплайн с формальными гарантиями оптимальности. Строго говоря, в самой статье TurboQuant используется не полярная декомпозиция, а покоординатная квантизация после поворота (что проще и быстрее), но философия та же: случайное преобразование приводит к известному распределению, что позволяет использовать предвычисленный codebook и свести overhead к нулю.

Шаг 0: нормализация

Сначала вектор нормализуется — его L2-норма сохраняется отдельно как float, а сам вектор проецируется на единичную сферу. Это стандартный и безобидный приём; восстановить масштаб при деквантизации — тривиальная операция.

Шаг 1: случайный поворот

Это ключевой трюк. Умножаем вектор на случайную ортогональную матрицу $\Pi \in \mathbb{R}^{d \times d}$ (получаемую QR-разложением случайной гауссовской матрицы). Получившийся вектор $\Pi x$ равномерно распределён на единичной сфере $S^{d-1}$ , вне зависимости от того, каким был исходный вектор $x$ .

Зачем это нужно? Потому что после поворота каждая координата повёрнутого вектора имеет известное распределение. Вот точная формулировка.

Лемма (распределение координат на сфере). Если $x \in S^{d-1}$ равномерно распределён на единичной сфере, то для любой координаты $j \in [d]$ :

$x_j \sim f_X(x) = \frac{\Gamma(d/2)}{\sqrt{\pi} \cdot \Gamma((d-1)/2)} \left(1 - x^2\right)^{(d-3)/2}, \quad x \in [-1, 1].$

Это отмасштабированное бета-распределение. В больших размерностях (а у нас $d$ обычно 64, 128, 256…) оно отлично приближается нормальным $\mathcal{N}(0, 1/d)$ .

Доказательство здесь элегантное и геометрическое: $f_X(x)$ равна отношению площади сферы размерности $d-2$ с радиусом $\sqrt{1-x^2}$ (это “срез” сферы на высоте $x$ ) к полной площади сферы $S^{d-1}$ , с поправкой на проекцию по теореме Пифагора:

$\begin{align*}f_X(x) &= \frac{A_{d-1}(\sqrt{1-x^2})}{A_d \cdot \sqrt{1-x^2}} \\ &= \frac{2\pi^{(d-1)/2} / \Gamma((d-1)/2) \cdot (1-x^2)^{(d-2)/2}}{2\pi^{d/2}/\Gamma(d/2) \cdot (1-x^2)^{1/2}} \\ &= \frac{\Gamma(d/2)}{\sqrt{\pi} \cdot \Gamma((d-1)/2)} (1-x^2)^{(d-3)/2}.\end{align*}$

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

Шаг 2: оптимальная скалярная квантизация (Lloyd-Max)

Раз координаты (почти) независимы и их распределение известно, мы можем квантизовать каждую координату отдельно, используя оптимальный скалярный квантизатор. Задача сводится к одномерной непрерывной задаче k-средних: нужно разбить отрезок $[-1, 1]$ на $2^b$ кластеров, минимизируя ожидаемое квадратичное отклонение от ближайшего центроида:

$C(f_X, b) = \min_{c_1 \leq \ldots \leq c_{2^b}} \sum_{i=1}^{2^b} \int_{\frac{c_{i-1}+c_i}{2}}^{\frac{c_i+c_{i+1}}{2}} |x - c_i|^2 f_X(x) \, dx.$

Оптимальное решение подчиняется двум условиям:

границы кластеров — это средние точки между соседними центроидами (разбиение Вороного в 1D);
центроиды — это условные математические ожидания $f_X$ на каждом кластере.

Эту задачу решает классический алгоритм Ллойда-Макса шестидесятилетней давности (Lloyd, 1957/1982; Max, 1960), итеративно чередующий обновление границ и центроидов.

Здесь можно буквально подсчитать конкретные значения: при достаточно больших $d$ , когда $f_X \approx \mathcal{N}(0, 1/d)$ , оптимальные центроиды для $b=1$ — это $\pm\sqrt{2/(\pi d)}$ , а для $b=2$ — это ${\pm 0.453/\sqrt{d}$ и $\pm 1.51/\sqrt{d}}$ .

Ключевой момент: словари (codebooks) здесь зависят только от размерности $d$ и битовой ширины $b$ , но не от данных. Их можно один раз подсчитать и сохранить, не нужно никакой калибровки и никакого обучения.

Процедура квантизации тогда тривиальна: для каждой координаты повёрнутого вектора находим ближайший центроид и сохраняем его индекс как $b$ -битное целое. Деквантизация состоит в том, чтобы по индексам восстановить центроиды и повернуть обратно через $\Pi^\top$ .

Теорема 1 (MSE-гарантия TurboQuant)

Теперь можно дать точную формулировку. Для любой битовой ширины $b \geq 1$ и любого вектора $x \in S^{d-1}$ , MSE-оптимальный TurboQuant $Q_{\text{mse}}: \mathbb{R}^d \to {0,1}^{bd}$ для любого $b \geq 0$ удовлетворяет

$D_{\text{MSE}}(Q_{\text{mse}}) := \mathbb{E}\left[|x - Q_{\text{mse}}^{-1}(Q_{\text{mse}}(x))|_2^2\right] \leq \frac{\sqrt{3\pi}}{2} \cdot \frac{1}{4^b}.$

При конкретных малых $b$ результаты ещё лучше:

b	1	2	3	4
$D_{\text{MSE}}$	0.36	0.117	0.030	0.009
Нижняя граница	0.25	0.0625	0.0156	0.0039
Отношение	1.44	1.87	1.92	2.31

При $b=1$ зазор с нижней границей Шеннона составляет всего $\approx 1.44$ — это почти оптимально.

Схема доказательства. Ключевое наблюдение здесь такое: поскольку $\Pi$ — ортогональная матрица, $|x - \tilde{x}|_2 = |\Pi x - \tilde{y}|_2$ , где $\tilde{y}$ — покоординатная реконструкция повёрнутого вектора. Поэтому $D_{\text{MSE}} = \sum_{j=1}^d \mathbb{E}[|y_j - \tilde{y}_j|^2]$ . Поскольку все координаты $y_j = (\Pi x)_j$ одинаково распределены по $f_X$ , получаем $D_{\text{MSE}} = d \cdot C(f_X, b)$ .

Остаётся оценить $C(f_X, b)$ — оптимальную цену скалярной квантизации. Для малых $b$ это делается численно (отсюда точные значения в таблице). Для больших $b$ можно применить ещё один классический результат — формулу Пантера-Дите (Panter, Dite, 1951):

$C(f_X, b) \leq \frac{1}{12} \cdot \left(\int f_X(x)^{1/3} dx\right)^3 \cdot \frac{1}{4^b} = \frac{\sqrt{3\pi}}{2d} \cdot \frac{1}{4^b}.$

Умножая на $d$ , получаем окончательную оценку.

Проблема смещения: зачем нужен второй этап

Казалось бы, дело сделано: $Q_{\text{mse}}$ даёт почти оптимальное MSE. Но для трансформера нам нужно не MSE, а скалярные произведения $\langle y, x \rangle$ . И тут обнаруживается неприятный сюрприз: MSE-оптимальная квантизация смещена (biased) в оценке скалярных произведений.

Почему? Рассмотрим простой случай $b=1$ . Оптимальный квантизатор при большом $d$ — это по сути функция sign, а его деквантизованные значения — это $\pm\sqrt{2/(\pi d)}$ . Можно показать, что оценка скалярного произведения при этом получает мультипликативное смещение $2/\pi \approx 0.637$ , то есть все веса внимания будут систематически занижены на 36%. С ростом $b$ смещение уменьшается, но нам ведь интересна как раз маленькая битовая ширина, а там смещение может сильно помешать.

Так что для поиска ближайших соседей, а также для внимания в трансформерах, нам нужна несмещённый (unbiased) оценка:

$\mathbb{E}\left[\langle y, Q^{-1}(Q(x)) \rangle\right] = \langle y, x \rangle.$

QJL: однобитовый метод

Здесь на сцену выходит ещё одна важная компонента TurboQuant: метод Quantized Johnson-Lindenstrauss (Zandieh et al., 2024). Идея такая: берём случайную гауссовскую матрицу $S \in \mathbb{R}^{d \times d}$ , проецируем вектор $x$ и берём знак:

$Q_{\text{qjl}}(x) := \text{sign}(S \cdot x), \quad Q_{\text{qjl}}^{-1}(z) := \frac{\sqrt{\pi/2}}{d} \cdot S^\top \cdot z.$

Лемма (гарантии QJL). Для любого $x \in S^{d-1}$ и любого $y \in \mathbb{R}^d$ верны два утверждения:

несмещённость:
$\mathbb{E}[\langle y, Q_{\text{qjl}}^{-1}(Q_{\text{qjl}}(x)) \rangle] = \langle y, x \rangle;$
оценка дисперсии:
$\text{Var}[\langle y, Q_{\text{qjl}}^{-1}(Q_{\text{qjl}}(x)) \rangle] \leq \frac{\pi}{2d} \cdot |y|_2^2.$

Доказательство оценки дисперсии здесь довольно интересное. Пусть $s_1, \ldots, s_d$ — строки матрицы $S$ . Тогда оценка скалярного произведения есть среднее из $d$ независимых одинаково распределённых случайных величин $z_i = \sqrt{\pi/2} \cdot (s_i^\top y) \cdot \text{sign}(s_i^\top x)$ . Дисперсия одной такой величины:

$\text{Var}(z_i) = \frac{\pi}{2} \cdot \text{Var}[s_i^\top y \cdot \text{sign}(s_i^\top x)] \leq \frac{\pi}{2} \cdot \mathbb{E}[(s_i^\top y)^2] = \frac{\pi}{2} |y|_2^2,$

поскольку $s_i^\top y \sim \mathcal{N}(0, |y|_2^2)$ . А дисперсия среднего из $d$ независимых слагаемых — это $1/d^2$ от суммы дисперсий, т.е. $\frac{\pi}{2d} |y|_2^2$ .

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

Собственно TurboQuant

В итоге собственно метод TurboQuant комбинирует оба метода. Если мы хотим получить битовую ширину $b$ , то мы делаем следующие шаги.

Применяем $Q_{\text{mse}}$ с битовой шириной $b-1$ — это даёт хорошую реконструкцию.
Вычисляем невязку (residual): $r = x - Q_{\text{mse}}^{-1}(Q_{\text{mse}}(x))$ .
Применяем QJL к невязке: храним $\text{sign}(S \cdot r)$ и $|r|_2$ .

Итого мы получаем $b$ бит на координату: $(b-1)$ бит на MSE-часть + 1 бит на QJL.

При деквантизации складываем обе части: восстановленный вектор из MSE-квантизатора плюс масштабированная QJL-реконструкция невязки.

Теорема 2 (качество квантизации для скалярных произведений)

Для любой битовой ширины $b \geq 1$ и любых $x \in S^{d-1}$ , $y \in \mathbb{R}^d$ , TurboQuant даёт отображение $Q_{\text{prod}}: S^{d-1} \to [2^{b-1}]^d \times {-1,1}^d \times \mathbb{R}$ , которое имеет следующие свойства.

Несмещённость:
$\mathbb{E}[\langle y, \tilde{x} \rangle] = \langle y, x \rangle.$
Оценка искажения:
$D_{\text{prod}} := \mathbb{E}[|\langle y, x \rangle - \langle y, \tilde{x} \rangle|^2] \leq \frac{\sqrt{3\pi}}{2} \cdot \frac{|y|_2^2}{d} \cdot \frac{1}{4^b}.$

Конкретные значения:

b	1	2	3	4
$D_{\text{prod}} \cdot d / \|y\|_2^2$	1.57	0.56	0.18	0.047

Доказательство использует conditioning. Фиксируем $\tilde{x}_{\text{mse}}$ (выход первого этапа) и считаем условное ожидание:

$\begin{align*}\mathbb{E}[\langle y, \tilde{x} \rangle | \tilde{x}_{\text{mse}}] =& \langle y, \tilde{x}_{\text{mse}} \rangle + \mathbb{E}[\langle y, \tilde{x}_{\text{qjl}} \rangle | \tilde{x}_{\text{mse}}] \\ =& \langle y, \tilde{x}_{\text{mse}} \rangle + \langle y, r \rangle = \langle y, x \rangle,\end{align*}$

где второе равенство — несмещённость QJL, а последнее — определение невязки $r = x - \tilde{x}_{\text{mse}}$ .

Условная дисперсия:

$\mathbb{E}[|\langle y, x \rangle - \langle y, \tilde{x} \rangle|^2 | \tilde{x}_{\text{mse}}] = \text{Var}[\langle y, \tilde{x}_{\text{qjl}} \rangle | \tilde{x}_{\text{mse}}] \leq \frac{\pi}{2d} \cdot |r|_2^2 |y|_2^2.$

Вот и получается, что

$D_{\text{prod}} \leq \frac{\pi}{2d} \cdot |y|_2^2 \cdot \mathbb{E}[|r|_2^2] = \frac{\pi}{2d} \cdot |y|_2^2 \cdot D_{\text{MSE}}(Q_{\text{mse}}, b-1).$

Подставляя оценку MSE из Теоремы 1 для битовой ширины $b-1$ , получаем результат.

Эксперименты: что на практике

KV-кэш

На бенчмарке Needle-in-a-Haystack TurboQuant с 4x сжатием получает ровно такой же результат, что и модель с полной точностью — 0.997. Вот для сравнения результаты других методов:

На LongBench (набор задач для длинных контекстов) модель Llama-3.1-8B-Instruct с 3.5-битным TurboQuant набирает 50.06 — ровно столько же, сколько модель с полной точностью; а с 2.5 битами — 49.44, т.е. работает с почти незаметной деградацией. При этом сжатие составляет более 4.5x.

Нецелые битовые ширины (2.5, 3.5) здесь получаются из-за стратегии выделения выбросов: 32 “выбросных” канала квантизуются с большей точностью (3 бита), остальные 96 каналов — с меньшей (2 бита), итого $(32 \times 3 + 96 \times 2)/128 = 2.5$ .

Авторы также показывают ускорение вычисления внимания на H100: 4-битный TurboQuant даёт до 8x ускорения по сравнению с 32-битным базовым вариантом.

Поиск ближайших соседей

TurboQuant превосходит Product Quantization и RabitQ по recall на всех протестированных датасетах (GloVe для d=200, OpenAI embeddings с d=1536 и d=3072). При этом время индексации практически нулевое (0.0013 секунды для 100K векторов в $d=1536$ ), потому что codebooks здесь предвычислены, в отличие от PQ, которому нужно запускать k-means (239.75 секунд).

Что сделало сообщество

Когда статья, опубликованная, напомню, в апреле 2025 года, всё-таки получила вполне заслуженный хайп, за неё тут же взялось сообщество, которое начало воспроизводить результаты и двигаться дальше. За неделю после блог-поста Google появились реализации на PyTorch, Rust, MLX (Apple Silicon) и Triton, а в llama.cpp развернулась масштабная дискуссия с 30+ участниками.

Уже есть интересные практические находки.

1. MSE-only часто лучше MSE+QJL для attention. Это подтвердили уже несколько независимых команд исследователей. Причина в том, что QJL убирает bias, но добавляет дисперсию. А softmax усиливает дисперсию: ошибки в скалярных произведениях экспоненциируются, и шум в одном весе внимания может перетянуть на себя всю голову. В режимах с b порядка 2-4 при типичных размерностях голов ( $d=64$ , $d=128$ ) MSE без QJL даёт лучше top-1 token matching. Замечу, что это не опровергает теорию — теоретический анализ TurboQuant оптимизирует MSE скалярного произведения до softmax, а практическая метрика — top-1 accuracy после softmax, что не одно и то же.

2. Ключи и значения надо квантизовать по-разному. Выяснилось, что нормы ключей и значений сильно различаются (в моделях типа Qwen — до 100x). Ошибки в ключах напрямую влияют на веса внимания, а ошибки в значениях усредняются. Оптимальная стратегия получается в том, чтобы при фиксированном бюджете давать ключам больше битов (например, 4), а значениям меньше (например, 2).

3. Обновление (конец марта 2026): комбинация Walsh-Hadamard Transform + QJL + MSE, где для MSE и QJL используются независимые случайные преобразования, оказалась лучшей стратегией. Проблема ранних реализаций была в том, что одна и та же случайная матрица использовалась для обоих этапов, что создавало корреляции. С независимыми проекциями QJL действительно помогает.

Другой подход: KVTC от Nvidia

TurboQuant — не единственная работа по сжатию KV-кэша на ICLR 2026. Nvidia представила KVTC (KV Cache Transform Coding; Staniszewski, Łańcucki, 2025), которая достигает 20x сжатия с менее чем 1% потерей качества. Подход совершенно другой: PCA-декорреляция (вычисленная по калибровочному датасету) + адаптивная квантизация + энтропийное кодирование (DEFLATE). По сути, это классический метод transform coding из мира JPEG, адаптированный для KV-кэша.

KVTC эксплуатирует низкоранговую структуру KV-кэша: оказывается, KV-тензоры сильно скоррелированы, и PCA позволяет выделить главные компоненты и раздать им больше бит, а хвостовым компонентам — ноль бит, фактически отбросив их. Это даёт гораздо бо́льшее сжатие, но KVTC от этого становится оффлайн-методом (data-dependent): PCA-матрицу нужно вычислять на калибровочных данных (~200K токенов на H100), и она будет своей для каждой модели.

Получается такое вот сравнение.

	TurboQuant	KVTC
Сжатие	~6x	~20x (до 40x)
Калибровка	Не нужна	PCA на ~200K токенов
Теория	$\leq 2.7 \times$ Шеннон	Нет формальных гарантий
Протестировано	до ~8B параметров	1.5B – 70B
Online	Да	Нет
Подход	Геометрический (поворот + квантизация)	Статистический (PCA + entropy coding)

Это два совершенно разных подхода, и они не конкурируют, а дополняют друг друга. TurboQuant — элегантная теоретическая работа, метод data-oblivious, формально оптимальный, подключается без настройки. KVTC — более инженерный подход, он использует структуру данных и жертвует универсальностью, но получает более сильное сжатие.

Проясню один небольшой вопрос, который мог возникнуть у читателя: если TurboQuant уже близок к пределу Шеннона, как KVTC может быть существенно лучше? Дело в том, что предел Шеннона, который мы обсуждали, верен для входных векторов в худшем случае. А KVTC вследствие своего обучения активно использует тот факт, что реальные KV-кэши — далеко не худший случай; они имеют низкоранговую структуру и корреляции между координатами.

Заключение

Мимо истории TurboQuant пройти было невозможно.

Во-первых, это тот самый пример, когда вечная математика — в данном случае теория информации и довольно глубокие результаты из теории вероятностей — напрямую приводит к state-of-the-art результатам в задаче, которая имеет очень большое практическое значение. Для TurboQuant не нужно обучать мета-модель, не нужен reinforcement learning, не нужны архитектурные или инженерные трюки. Только случайный поворот, оптимальный скалярный квантизатор шестидесятилетней давности и однобитовая добавка на невязку, и всё.

Во-вторых, результат доказуемо близок к оптимальному. Не “в среднем на бенчмарках лучше предыдущего SOTA на 2%”, а математически не более чем в 2.7 раза хуже любого возможного алгоритма. Это тоже редко бывает в машинном обучении, и это всегда приятно и интересно видеть.

В-третьих, это data-oblivious алгоритм, работающий онлайн. Его codebooks зависят только от размерности и числа бит, и один и тот же квантизатор работает для любой модели. Для практического использования это важное преимущество: TurboQuant может войти в стандартный стек, не зависящий от модели.

В-четвёртых, опять подтвердилась восходящая по крайней мере к 1880-м годам цитата: “In theory, there is no difference between theory and practice; in practice, there is”. Практические реализации тут же показали, что QJL-этап, который теоретически необходим для несмещённости, на практике может вредить, или что ключи и значения нужно квантизовать асимметрично.

Ну и наконец, сам по себе факт того, что сжатие KV-кэша подходит к пределу Шеннона, означает, что гонка за сжатие в этом конкретном направлении приближается к завершению. В рамках data-oblivious подхода выжать сильно больше уже невозможно, так что дальнейший прогресс будет за счёт data-dependent методов (как KVTC) или гибридных подходов; а может, появятся какие-то совершенно другие парадигмы.

А математика и правда вечна. В этом посте мы упоминали работы Шеннона (1948, 1959), Ллойда (1957) и Макса (1960), Джонсона и Линденштраусса (1986) — и именно они оказались ключевыми для самой громкой инженерной новости марта 2026 года. Занимайтесь математикой, не прогадаете!

Сергей Николенко

P.S. Прокомментировать и обсудить пост можно в канале «Sineкура»: присоединяйтесь!