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

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 ≥ 4k, s ≤ √n/4) requires depth L = Omega(lceil k/s rceil · lceil log2 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) · 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 ≥ log2 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 log2 k rceil doubling stages, oblivious caches give Pr[E] ≤ (s/(n-T))T + 2T3/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.