【人工知能・深層学習】論文紹介：TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate

論文紹介 TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate 2026/5/9 立教大学人工知能科学研究科瀧研究室 小宮 雄太

論文概要 タイトル：TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate 概要：事前学習不要でありながら、平均二乗誤差と内積歪みの両方を理論的限界（Shannon 下限）に近いレベルで最適化するベクトル量子化手法TurboQuantの提案および検証 成果： ・ 完全並列化可能な計算アルゴリズムの設計 ・ Shannon下限の2.7倍未満で圧縮と精度の両立を行えることを証明 ・ KVキャッシュ圧縮時の精度やインデックス作成時間において既存手法を上回る結果を達成 1

量子化とは 00111111010000000000000000000000 2

量子化とは 0| 01111110 | 10000000000000000000000 符号 (1bit) 指数部 (8bit) 仮数部 (23bit) 3

量子化とは 0| 01111110 | 10000000000000000000000 符号 (1bit) 指数部 (8bit) 仮数部 (23bit) 実数値 = −1 符号 × 2(指数部−127) × 1. 仮数部 4

量子化とは 0| 01111110 | 10000000000000000000000 符号 (1bit) 指数部 (8bit) 仮数部 (23bit) 実数値 = −1 符号 × 2(指数部−127) × 1. 仮数部 −1 0 × 2(126−127) × 1.5 = 0.75 5

量子化 8bitで表すと 値−最低値 実数＝255 × 範囲 範囲を-1から1とすると 0.75 − (−1) 255 × = 233.125 2 ≒ 11011111 ←0.749019… 6

量子化 値−最低値 実数＝255 × 範囲 0.75 − (−1) 255 × = 233.125 2 ≒ 11011111 ←0.749019… 00111111010000000000000000000000 32bit ≒ 1101111 8bit 7

量子化を行う理由 1.メモリ使用量の削減 容量の削減や軽量化によるデバイスの制限を回避など 2.計算速度の向上 データ転送速度の向上や演算の簡略化 3.消費電力の抑制 計算速度向上やメモリ使用量の軽減によって 4.通信帯域の効率化 データのサイズが小さくなるため 8

既存の量子化手法 オフライン手法 手法：データの傾向を分析、データを圧縮するた めの指標を作成し、適合する数値に置換する 弱点：事前準備に時間がかかる、リアルタイムで 変動する環境には不向き オンライン手法 手法：あらかじめ空間にグリッドを引くなどし、 逐次どのグリッドがもっとも近いかを探索し丸め 込む 弱点：探索アルゴリズムにGPUとの相性の良くな い複雑な条件分岐を必要とするため結果的に計算 が遅い 9

TurboQuantの目標 ①事前学習不要 ②並列計算可能 ③理論的限界に迫る精度 The Shannon Lower Bound 𝑑 𝐷 𝑝𝑥 , 𝐵 ≥ 2 2/𝑑 ℎ 𝑥 −𝐵 2π𝑒 𝑝𝑥 ：入力ベクトルxが従う確率分布 𝐷 𝑝𝑥 , 𝐵 ：Bビット以下で達成できるMSE(平均二乗誤差)の最小期待値 𝑑 ：ベクトルの次元数 ℎ 𝑥 ：微分エントロピー 10

KVキャッシュ KVキャッシュとは すでに計算した部分の計算結果を保存し、次のトークン生成に再利用する仕組み KeyとValueの計算結果を保存し、計算コスト削減による高速化を計る。 【KVキャッシュなし】 トークン1生成: [A] のK,V計算 トークン2生成: [A,B] のK,V計算（Aを再計算） トークン3生成: [A,B,C] のK,V計算（A,Bを再計算） → 生成が進むほど同じ計算を何度も繰り返す 【KVキャッシュあり】 トークン1生成: [A] のK,V計算 → キャッシュに保存 トークン2生成: キャッシュから[A]のK,V取得 + [B]のK,V計算 トークン3生成: キャッシュから[A,B]のK,V取得 + [C]のK,V計算 → 新しいトークン分だけ計算すればOK 11

TurboQuantの仕組み 手法１(mse最適化) ①入力ベクトルにランダムな回転行列 Πを掛ける ②事前に一次元の連続k-mean問題を解き、代表値を計算しておく ③各次元を独立した一次元の比較として代表値に丸め込む 手法２(内積歪み最適化) ①入力ベクトルにランダムな回転行列 Πを掛ける ②目標ビット幅より1ビット少ない容量でMSE量子化を行う ③残差ベクトルに対して内積計算のバイアスを打ち消すQJL変換を行う 12

計算 ①入力ベクトルにランダムな回転行列 Πを掛ける 1.入力ベクトルはd次元の単位超球面の表面上に一様に分布したランダムな点へと変換される 2.超球面上のある一点が特定の座標xとなる確率は全体の面積を断面の面積で割ったものなので 補正係数を掛けて 𝑓𝑥 𝑥 ≔ = Γ 𝑑/2 1 − 𝑥 2 (𝑑−3)/2 π･Γ (d − 1)/2 13

計算 3. d次元が大きい時、 1 − 𝑥 2 (𝑑−3)/2 = 1 − 𝑥 2 𝑑/2 𝑑/2 𝑑𝑥 2 = 1− 𝑑 ネイピア数の定義式から lim 1 − 𝑑→∞ 次に、Γ 𝑑 + 1 ≈ 2π𝑑 𝑑 𝑑 𝑒 𝑑 𝑑𝑥 2 2 𝑑 −𝑑 2 ≈𝑒2𝑥 を用いて、 Γ 𝑑/2 ≈ π･Γ (d − 1)/2 よって高次元においてf(x) ≈ 𝑑 2𝜋 𝑒 −𝑑 2 𝑥 2 𝑑 2𝜋 となり、平均0、分散 1/d の正規分布に近似できた 14

MSE量子化 1. 連続的なk-meansによって最適な代表値を算出 ランダム回転させた入力ベクトルが特定の分布に従うことを利用して1次元の連続的なkmeans問題（Lloyd-Maxアルゴリズム）を解き、MSEコスト関数 𝐶(𝑓𝑥 , 𝑏)が最も小さくなる ような理想的な代表値を導出 目標とするビット幅 b に応じて値の取りうる範囲を 2b 個の区間に分割し、代表値を求め る。1ビットであれば代表値は±2/πd 、2ビットであれば ±0.453/dと±1.51/d 2. 最も近い代表値への丸めこみ ランダム回転をかけた入力ベクトルに対して、最も距離が近い代表値に置き換えを行う 15

Shannon’s lower bound シャノン下限 TurboQuant上限 Panter-Diteの高解像度公式より この式に正規分布の確率密度関数を代入して積分を解くと、 3π 1 𝑇𝑢𝑟𝑏𝑜𝑄𝑢𝑎𝑛𝑡上限 3π 2𝑑 4𝑏 ≤ = 1 シャノン下限 2𝑑 4𝑏 16

TurboQuantの仕組み 手法１(mse最適化) ①入力ベクトルにランダムな回転行列 Πを掛ける ②事前に一次元の連続k-mean問題を解き、代表値を計算しておく ③各次元を独立した一次元の比較として代表値に丸め込む →内積に関しては操作していないので内積計算ではバイアスがかかる 手法２(内積歪み最適化) ①入力ベクトルにランダムな回転行列 Πを掛ける ②目標ビット幅より1ビット少ない容量でMSE量子化を行う ③残差ベクトルに対して内積計算のバイアスを打ち消すQJL変換を行う →1ビットを内積歪みの是正に用いることで低ビットでも内積に歪みが出ない 17

実験1：理論的結果の検証 •実験目的：提案された2つの手法について、数学的に証明された理論上の歪み限界が、実 際のデータでも成り立つかを確認する •使用データ: OpenAI3の埋め込みモデルを使って1536次元ベクトルに変換された「DBpedia Entities」のデータセットを使用 •サンプリング: データセットからランダムに10万件をトレーニングセットとして抽出し、 全く別の1,000件をクエリセットとして用意 •検証手順: 抽出したデータを𝑇𝑢𝑟𝑏𝑜𝑄𝑢𝑎𝑛𝑡𝑝𝑟𝑜𝑑 (内積最適化）と𝑇𝑢𝑟𝑏𝑜𝑄𝑢𝑎𝑛𝑡𝑚𝑠𝑒 (MSE最適化) の2つの手法で量子化し、1〜4ビット幅でクエリとの内積を計算しする 実際の計算結果の誤差の分布をヒストグラム化し、その結果が理論上の限界と一致するか をグラフにマッピングして確認する 18

実験1：理論的結果の検証 1.ビット数の変化と結果 MSE最適化では内積歪みが確認 されるが、ビット数の増加とと もに改善される 2.平均内積の変化と結果 内積歪み最適化では内積誤差の 分散は一定のまま MSE最適化では平均内積に応じ て増加している 19

実験1：理論的結果の検証 ビット数と誤差のグラフと理論的限界 ・内積歪み最適化、MSE最適化ともにシャノ ン下限の限界を超えない範囲に収まっている ・内積歪みにおいて、mse最適化はビット数 が少ないうちはエラーが大きいが、ビット数 が大きくなると内積歪み最適化と大差 20

実験2：Needle-In-A-Haystack 実験手法 大量の文章の中に隠された、1つの特定 の情報を正確に見つけ出せるかを測る KVキャッシュのメモリサイズを本来の 25%にまで圧縮してテスト 実験結果 既存手法を超える精度を示し、かつ非 圧縮のモデルにも引けを取らない性能 を示した 21

実験3：End-to-end Generation on LongBench 実験内容 実験結果 単一の情報検索ではなく、長文の質問応答、要約、 より小さなビット数に量子化しても既存手法と遜 コード補完といった、より実践的で多様なエンド 色のない精度を達成 ツーエンドの長文コンテキストタスクにおける総 合的なパフォーマンスを測る 22

実験4：最近傍探索 •使用データ: 次元数の異なる3種類のデータセット( OpenAI3の1536次元および3072次元の DBpediaデータ、 GloVe の200次元データ)を用意し、それぞれ検索対象として10万件をサン プリングし、クエリとしての1,000件（GloVeは10,000件)を用意 •評価指標: 最も類似度が高いデータが、量子化して近似計算した際の検索結果の上位 k 件 の中にどれくらいの確率で含まれているかを測るRecall@1@kを使用 •比較手法の設定: 既存のオフライン手法であるProduct Quantization (PQ)、オンライン手法の RabitQの2ビットおよび4ビット量子化で比較。 PQについては速度と精度のバランスを取るため、256個の代表値を持つ「LUT256」という 設定を使用。またRabitQはGPUによる並列化計算が不可能なアルゴリズムであるため、CPU 上で実行させてインデックス作成時間や精度を計測 23

実験4：最近傍探索 実験結果 精度 すべての実験条件において、 TurboQuantが既存手法の検索精度 を一貫して上回る結果を示した 速度 量子化の速度において次元問わず 既存手法を圧倒する速度を記録 24