研究推理中键值缓存压缩极限，揭示深度与缓存大小的权衡关系。
How Much Cache Does Reasoning Need? Depth-Cache Tradeoffs in KV-Compressed Transformers
- 通过指针追踪模型分析缓存大小对推理深度的影响。
- 证明缓存越小，所需推理深度越大，且存在理论下界。
- 揭示自适应缓存比随机缓存更优，解释实际系统设计原理。
键值（KV）缓存是Transformer推理中的主要内存瓶颈，但其可压缩程度与多步推理性能下降之间的理论关系尚不明确。本文在共享缓存大小为 $s$、注意力维度 $m$、$H$ 头、$p$ 位精度、局部性尊重的缓存控制器条件下，研究了在 $n$ 个标记上进行 $k$-跳指针追踪时的深度下界。提出一个猜想：当 $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))$。进一步发现，当 $Hmp \gtrsim \log n$ 时，传统可区分性计数方法无法突破 $\lceil k/s \rceil$ 的界限。最后，对比自适应与盲目缓存策略，在 $T = \lceil \log_2 k \rceil$ 次加倍阶段下，后者错误概率为 $\Pr[\mathcal{E}] \leq (s/(n-T))^T + 2T^3/n$，而前者为 $\Pr[\mathcal{E}] = s/n$，独立于 $T$，说明重热点淘汰优于随机淘汰。
原文摘要 · Abstract (English)
The key-value (KV) cache is the dominant memory bottleneck during Transformer inference, yet little is known theoretically about how aggressively it can be compressed before multi-step reasoning degrades. We study this through $k$-hop pointer chasing on $n$ tokens under a shared KV cache of size $s$, attention dimension $m$, $H$ heads, $p$-bit precision, and a locality-respecting cache controller (satisfied by all standard KV-compression methods). We give three results. (1) Product depth lower bound (conjectured). We conjecture that any such Transformer ($n \geq 4k$, $s \leq \sqrt{n}/4$) requires depth $L = Ω(\lceil k/s \rceil \cdot \lceil \log_2 n/(Hmp) \rceil)$, and isolate the sole remaining gap as a probabilistic step on the joint distribution of cache trace and pointer chain. Unconditionally, we prove a matching upper bound $L = O(\min(k, \lceil k/s \rceil \log s) \cdot \log n/(mp))$ via windowed pointer doubling, and a max-bound $L = Ω(\max(\lceil k/s \rceil, \log n/(Hmp)))$. Closing the conjecture amounts to upgrading max to product. (2) Bandwidth barrier. The product bound binds only when $Hmp \lesssim \log n$. Any lower bound provable via per-window distinguishability counting -- including reachability, bandwidth, and combinations -- cannot exceed $\lceil k/s \rceil$ once $Hmp \geq \log_2 n$. Breaking this requires lifting unconditional communication-complexity bounds for pointer chasing to Cache-Transformer depth. (3) Adaptive vs oblivious error scaling. Under random cache over $T = \lceil \log_2 k \rceil$ doubling stages, oblivious caches give $\Pr[\mathcal{E}] \leq (s/(n-T))^T + 2T^3/n$ (exponential in $T$), while adaptive locality-respecting caches achieve $\Pr[\mathcal{E}] = s/n$ exactly, independent of $T$. The $Ω((n/s)^{T-1})$ separation explains why heavy-hitter eviction empirically dominates random eviction for multi-hop reasoning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。