Metraipolis › archive › dc_a4a42adb408e
A Probabilistic Interpretation of KV Cache Eviction — arXiv:2608.28293
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.28293
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T10:48:12.759Z
- SHA-256 of the archived text
16901e9a9d967665bbaaa4c044555baebbcb352c51f25dd88e1fa00040fec9da- Stable URL of this page
https://metraipolis.com/documento/dc_a4a42adb408e
How to cite
A Probabilistic Interpretation of KV Cache Eviction — arXiv:2608.28293 — arXiv (en), https://arxiv.org/abs/2608.28293 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a4a42adb408e (Metraipolis archive dc_a4a42adb408e, sha256 16901e9a9d967665bbaaa4c044555baebbcb352c51f25dd88e1fa00040fec9da)
BibTeX
@misc{dca4a42adb408e,
title = {A Probabilistic Interpretation of KV Cache Eviction — arXiv:2608.28293},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.28293},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a4a42adb408e; sha256 16901e9a9d967665bbaaa4c044555baebbcb352c51f25dd88e1fa00040fec9da},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.28293. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The premise and promise of KV (cache) eviction is simple: higher throughput can be achieved by evicting some entries from the KV cache, at a negligible cost to quality. This holds empirically for many existing methods, though most rely on creative heuristics for selecting which entries to drop. Despite recent advances, the problem of KV eviction has remained informal in the literature. This paper aims to properly formalize this problem through the lens of probabilistic reasoning and reveal what can be learned from this perspective. Concretely, we (1) formalize the problem of KV eviction and, unfortunately, prove that it is computationally hard, (2) show that by framing it probabilistically, KV eviction reduces to the problem of expectation estimation, which can be approximated through sampling, (3) show that through this probabilistic interpretation, correcting for evicted entries during decoding---a previously ignored problem---becomes feasible, and (4) reveal that existing methods in the literature are zero-variance biased estimators that can be easily adapted in order to enable decode time correction. In practice, we show that this probabilistic version of KV eviction coupled with decode time correction is more robust to different tasks compared to existing eviction methods and achieves competitive performance at the same compression budget. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-31 in cs.AI). Categorie arXiv: Computation and Language (cs.CL) ; Artificial Intelligence (cs.AI). Pagina del lavoro: https://arxiv.org/abs/2608.28293 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-17T10:33:42.514Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-08-31?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).