推理需要多少缓存？ KV 压缩 Transformer 中的深度缓存权衡

键值 (KV) 缓存是 Transformer 推理期间的主要内存瓶颈，但从理论上讲，在多步推理降级之前可以如何积极地压缩它，人们知之甚少。我们通过在大小为 $s$、注意力维度 $m$、$H$ 头、$p$ 位精度和尊重局部性的缓存控制器（满足所有标准 KV 压缩方法）的共享 KV 缓存下追踪 $n$ 词元的 $k$-hop 指针来研究这一点。我们给出三个结果。 (1) 产品深度下限（推测）。我们推测任何这样的 Transformer ($n \geq 4k$, $s \leq \sqrt{n}/4$) 需要深度 $L = Ω(\lceil k/s \rceil \cdot \lceil \log_2 n/(Hmp) \rceil)$，并将唯一剩余的间隙隔离为缓存跟踪和指针链联合分布的概率步骤。无条件地，我们通过窗口指针加倍证明匹配上限 $L = O(\min(k, \lceil k/s \rceil \log s) \cdot \log n/(mp))$ ，以及最大边界 $L = Ω(\max(\lceil k/s \rceil, \log n/(Hmp)))$。结束猜想相当于将max升级为product。 (2)带宽障碍。仅当 $Hmp \lesssim \log n$ 时，乘积才会结合。通过每个窗口可区分性计数可证明的任何下限（包括可达性、带宽和组合）一旦 $Hmp \geq \log_2 n$ 都不能超过 $\lceil k/s \rceil$。打破这一点需要将指针追踪的无条件通信复杂性界限提升到 Cache-Transformer 深度。 (3) 自适应误差缩放与不经意误差缩放。在 $T = \lceil \log_2 k \rceil$ 加倍阶段的随机缓存下，不经意缓存给出 $\Pr[\mathcal{E}] \leq (s/(n-T))^T + 2T^3/n$ （$T$ 中的指数），而自适应局部性缓存则准确地实现 $\Pr[\mathcal{E}] = s/n$，与 $T$ 无关。 $Ω((n/s)^{T-1})$ 分离解释了为什么重击逐出在经验上主导了多跳推理的随机逐出。