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

arXiv: https://arxiv.org/abs/2604.17935 · HTML: https://mlsanity.com/paper/2604.17935/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 24 references that are in the map.
- First posted on arXiv 20 Apr 2026.

## Builds on (most cited first, 12 of 12)

- [SnapKV: LLM Knows What You are Looking for Before Generation](https://mlsanity.com/paper/2404.14469/) (2024)
- [KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cache](https://mlsanity.com/paper/2402.02750/) (2024)
- [Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Time](https://mlsanity.com/paper/2305.17118/) (2023)
- [PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funneling](https://mlsanity.com/paper/2406.02069/) (2024)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [Keep the Cost Down: A Review on Methods to Optimize LLM' s KV-Cache Consumption](https://mlsanity.com/paper/2407.18003/) (2024)
- [Model Tells You Where to Merge: Adaptive KV Cache Merging for LLMs on Long-Context Tasks](https://mlsanity.com/paper/2407.08454/) (2024)
- [On Limitations of the Transformer Architecture](https://mlsanity.com/paper/2402.08164/) (2024)
- [Strassen Attention, Split VC Dimension and Compositionality in Transformers](https://mlsanity.com/paper/2501.19215/) (2025)
- [Which Heads Matter for Reasoning? RL-Guided KV Cache Compression](https://mlsanity.com/paper/2510.08525/) (2025)
- [Hold Onto That Thought: Assessing KV Cache Compression On Reasoning](https://mlsanity.com/paper/2512.12008/) (2025)
- [Understanding the Physics of Key-Value Cache Compression for LLMs through Attention Dynamics](https://mlsanity.com/paper/2603.01426/) (2026)

## Built on by (most cited first, 3 of 3)

- [DepthWeave-KV: Token-Adaptive Cross-Layer Residual Factorization for Long-Context KV Cache Compression](https://mlsanity.com/paper/2607.06523/) (2026)
- [Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning](https://mlsanity.com/paper/2609.03430/) (2026)
- [Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions](https://mlsanity.com/paper/2609.06327/) (2026)

## Abstract (arXiv)

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.