A Probabilistic Interpretation of KV Cache Eviction

TL;DR - This paper formalizes KV-cache eviction as a computationally hard probabilistic estimation problem and proposes sampling-based eviction with decode-time correction. The approach is more robust across tasks than existing heuristic methods while remaining competitive at the same cache-compression budget.

• Recasts KV-cache eviction as expectation estimation, enabling principled sampling-based approximations.
• Introduces decode-time correction to account for entries removed from the cache.
• Interprets existing eviction methods as zero-variance biased estimators that can be adapted to support correction.
• Empirically improves cross-task robustness while preserving competitive quality and compression.