通过语言结构压缩注意力缓存，效率远超传统方法。
Sequential KV Cache Compression via Probabilistic Language Tries: Beyond the Per-Vector Shannon Limit
- 利用语言模型的预测能力，分两层压缩缓存：前缀去重+残差编码。
- 在典型困惑度下，每令牌熵仅3.3-4.3比特，比现有方法低近10倍。
- 适合长序列生成场景，尤其对大模型推理内存优化有显著价值。
近期的键值缓存量化工作，以TurboQuant为代表，已接近单向量压缩的香农熵极限。我们发现该极限适用于一个更弱的问题——而实际关键在于序列级压缩。缓存中的令牌并非任意浮点数据，而是模型训练所用形式语言的样本，且模型本身是该语言的近优预测器。本文提出序列化KV压缩，采用双层架构：第一层为概率前缀去重，利用概率语言树（PLTs）的度量d_T(s, s') = -log₂ P_M(s ^ s')识别跨会话语义等价前缀；第二层为预测残差编码，仅存储新KV向量与模型自身预测之间的残差，实现每令牌熵上界H(KV_{i+1} | KV_{<=i}) ≤ H(token_{i+1} | token_{<=i})。在典型语言模型困惑度（10-20）下，该上界平均为3.3-4.3比特/令牌位置，而TurboQuant为3比特/向量分量（典型注意力头含64-128分量）。理论压缩比在香农极限下达约914,000倍；即使在高于熵底限1000倍的悲观情形下，压缩比仍达约914倍，且随上下文长度增加而提升。两层结构相互独立，可与现有向量量化方法（如TurboQuant）组合使用。
原文摘要 · Abstract (English)
Recent work on KV cache quantization, culminating in TurboQuant, has approached the Shannon entropy limit for per-vector compression of transformer key-value caches. We observe that this limit applies to a strictly weaker problem than the one that actually matters: compressing the KV cache as a sequence. The tokens stored in a KV cache are not arbitrary floating-point data -- they are samples from the exact formal language the model was trained on, and the model is by construction a near-optimal predictor of that language. We introduce sequential KV compression, a two-layer architecture that exploits this structure. The first layer, probabilistic prefix deduplication, identifies semantically equivalent shared prefixes across sessions using the trie metric d_T(s, s') = -log_2 P_M(s ^ s') from Probabilistic Language Tries (PLTs). The second layer, predictive delta coding, stores only the residual of each new KV vector from the model's own prediction of it, achieving a per-token entropy bound of H(KV_{i+1} | KV_{<=i}) <= H(token_{i+1} | token_{<=i}). We prove that at typical language model perplexity -- approximately 10-20 for fluent English text -- this bound is 3.3-4.3 bits on average per token position, compared to TurboQuant's 3 bits per vector component (with typical attention heads having 64-128 components). The theoretical compression ratio over TurboQuant is approximately 914,000x at the Shannon limit. Even at 1000x above the entropy floor -- a deliberately pessimistic worst-case overhead, two orders of magnitude above the 2-5x typical of practical source coders -- the ratio remains approximately 914x over TurboQuant, with compression improving rather than degrading as context length grows. The two layers are orthogonal and compose with existing per-vector quantization methods including TurboQuant.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。