確率的言語トライによる逐次KVキャッシュ圧縮：1ベクトルあたりのシャノン限界を超えて

要旨: KVキャッシュの量子化に関する最近の研究は、TurboQuantによって頂点に達し、トランスフォーマーのキー・バリュー（KV）キャッシュを1ベクトルごとに圧縮する際のシャノンエントロピー限界に近づいてきました。私たちは、この限界が、実際に重要な問題よりも厳密に弱い（より小さい）問題に対して成り立つことを観察します。すなわち、KVキャッシュを「列」として圧縮する問題です。KVキャッシュに格納されるトークンは、任意の浮動小数点データではありません。これらは、モデルが学習された厳密な形式言語からのサンプルであり、モデルはその言語の近傍最適な予測器として（構成上）振る舞います。私たちは、この構造を活用する2層アーキテクチャである逐次KV圧縮を提案します。第1層は確率的プレフィックス重複排除で、Probabilistic Language Tries（PLTs）のトライ指標 d_T(s, s') = -log_2 P_M(s ^ s') によって、セッション間で意味的に同等な共有プレフィックスを特定します。第2層は予測デルタ符号化で、各新しいKVベクトルを、モデル自身によるその予測から得られる残差のみとして格納し、1トークンあたりのエントロピー上界を H(KV_{i+1} | KV_{<=i}) <= H(token_{i+1} | token_{<=i}) として達成します。流暢な英語テキストに対する典型的な言語モデルのパープレキシティ（概ね10〜20）では、この上界は、TurboQuantの「ベクトル成分あたり3ビット」（典型的な注意ヘッドは64〜128成分を持つ）と比べて、各トークン位置あたり平均で3.3〜4.3ビットであることを証明します。シャノン限界における理論的な圧縮率は、TurboQuantに対して約914,000xです。エントロピー下限からさらに1000x上（意図的に悲観的な最悪ケースのオーバーヘッドであり、実際のソースコーダで典型的に見られる2〜5xのオーダーより2桁大きい）であっても、圧縮率はTurboQuantに対して約914xのままで、圧縮は文脈長が伸びるにつれて劣化するどころか改善します。2つの層は互いに直交しており、TurboQuantを含む既存の1ベクトル量子化手法と組み合わせ可能です。