How Much Cache Does Reasoning Need? Depth-Cache Tradeoffs in KV-Compressed Transformers

arXiv:2604.17935v1 Announce Type: new Abstract: 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 = Omega(lceil k/s rceil dot 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) dot log n/(mp)) via windowed pointer doubling, and a max-bound L = Omega(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[E] leq (s/(n-T))^T + 2T^3/n (exponential in T), while adaptive locality-respecting caches achieve Pr[E] = s/n exactly, independent of T. The Omega((n/s)^{T-1}) separation explains why heavy-hitter eviction empirically dominates random eviction for multi-hop reasoning.

Source: arXiv cs.LG | 2026-04-21

Related