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

В докладе будет представлен алгоритм TurboQuant (Amir Zandieh et al., ICLR 2026 ), предназначенный для сжатия многомерных векторов в онлайн-режиме без необходимости предварительной настройки на данных. Метод обеспечивает теоретически обоснованные границы искажений как по среднеквадратичной ошибке (MSE), так и по скалярному произведению, приближаясь к нижней границе Шеннона с точностью до небольшой константы. Это получается классно применить для сжатия KV-кеша, а также для поиска ближайших соседей.

Под капотом алгоритм использует следующие два факта:

1. Если вектор, лежащих на единичной сфере, случайным образом повернуть, то координаты полученного вектора, во-первых, будут практически независимы — и значит можно кодировать результат поэлементно, а во-вторых, будут иметь понятное распределение — и значит мы знаем, как устроено оптимальное кодирование.
2. Если вектор x, лежащих на (d-1)-мерной сфере, умножить на случайную d×d матрицу S с элементами из N(0, 1), а потом заменить элементы на их знаки, то полученный вектор z будет состоять из d бит (это и есть наша квантизация), а вектор x’ = sqrt(π/2) / d · Sᵀ · z будет обладать следующим удивительным свойством: для всякого y ⟨y, x’⟩ в среднем равно ⟨y, x⟩, а дисперсия ⟨y, x’⟩ имеет порядок O(|y|² / d).

Чтобы закодировать вектор x, лежащих на (d-1)-мерной сфере, сначала применяется кодирование с помощью первого факта, потом находится разность между x и декодированным вектором, и эта разность кодируется с помощью второго факта.