发现语言模型缓存压缩敏感度呈多项式衰减，揭示了高效缓存的理论极限。
Polynomial Context-Truncation Sensitivity in Autoregressive Language Models: Sequential Wyner-Ziv Bounds for KV Cache Compression
- 将缓存压缩建模为带侧信息的序列编码问题，利用下一轮预测作为解码辅助。
- 实证显示上下文截断敏感度按幂律衰减，优于指数拟合一个数量级。
- 提出滑动窗口缓存策略，理论与实验均验证其在特定条件下最优。
我们研究自回归语言模型中在线键值缓存压缩的率失真极限，将其建模为在模型诱导滤波上带侧信息的序列Wyner-Ziv编码，以下一步查询作为解码端信息。在四个跨越两个模型族、参数量0.5-3B的模型上，我们发现下一个词分布对上下文截断的敏感度呈多项式而非几何衰减：幂律拟合比指数拟合在外推时优一个数量级；拟合指数可独立由“尾部加近期”KL测量恢复；通过位置保持消融验证该衰减不受位置编码伪影影响。在对应多项式截断敏感性假设下，我们的核心结果刻画了仅保留后缀缓存策略的每标记内存需求：滑动窗口方案以窗口大小w = O(ε^{-1/α})达到失真ε，且在额外双侧贝叶斯风险条件下，证明w = Ω(ε^{-1/α})为必要，故该类策略下缩放为Θ(ε^{-1/α})。循环或传播缓存摘要能否突破此缩放仍待探索。显式块马尔可夫方案达到上界；其收敛速率指数在附加前向衰减与正则性假设下匹配下界，否则相差两倍。实证表明，幂律能准确预测具体缓存策略的退化曲线：基于近期性的淘汰策略（滑动、尾部+近期）在同等预算下使失真降低约两个数量级，且失真随预算呈幂律下降。
原文摘要 · Abstract (English)
We study the rate-distortion limits of online KV cache compression in autoregressive language models, formulating it as sequential Wyner-Ziv source coding on the filtration induced by the model, with the next-step query as decoder side information. Empirically, across four models spanning two families and $0.5$-$3$B parameters, we find that the next-token distribution's sensitivity to context truncation decays \emph{polynomially} rather than \emph{geometrically}: a power law improves on an exponential fit by an order of magnitude in extrapolation, the fitted exponent is recovered independently from a sink-plus-recent KL measurement, and the decay is verified to be free of positional-encoding artifacts by a position-preserving ablation. Under a corresponding \emph{polynomial truncation-sensitivity} assumption, our main result characterizes the per-token memory requirement of \emph{suffix-only} cache policies: a sliding-window scheme attains distortion $\varepsilon$ with window $w = O(\varepsilon^{-1/α})$, and -- under an additional two-sided Bayes-risk condition -- a converse shows $w = Ω(\varepsilon^{-1/α})$ is necessary within this policy class, so the scaling is $Θ(\varepsilon^{-1/α})$ for suffix-only policies. Whether recurrent or propagating cache summaries can beat this scaling is left open. An explicit block-Markov scheme achieves the upper bound; its rate-of-convergence exponent matches the converse under additional forward-decay and regularity hypotheses (not implied by truncation sensitivity alone), and differs by a factor of two otherwise. Empirically, the polynomial law predicts the degradation curves of concrete cache policies: recency-based eviction (sliding, sink-plus-recent) suppresses distortion by roughly two orders of magnitude over random retention at equal budget, with a power-law decay in the budget.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。