A Probabilistic Interpretation of KV Cache Eviction

• URL: http://arxiv.org/abs/2608.28293v1
• Date: Fri, 28 Aug 2026 12:57:07 GMT
• Title: A Probabilistic Interpretation of KV Cache Eviction
• Abstract summary: Cache eviction can achieve higher throughput by evicting some entries from the KV cache.<n>This paper formalizes the problem of KV eviction through the lens of probabilistic reasoning.<n>We show that this probabilistic version of KV eviction coupled with decode time correction is more robust to different tasks.
• Score: 52.196873305708955
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Revisiting Lossy Verification in Speculative Decoding: Mechanisms, Trade-offs, and Failure Modes [19.68865985432786]
  We present a principled analysis of the distributions induced by lossy verification methods.<n>We show that many seemingly distinct approaches differ only superficially and can be classified into two categories: truncation-based verification and collaborative verification.
  arXiv  Detail & Related papers  (2026-07-29T08:54:27Z)
• Error Certificates for KV-Cache Eviction via Randomized Design [3.860898721527665]
  KV-cache eviction keeps the top-$k$ tokens under an importance score and deletes the rest.<n>We prove that this design cannot know what it destroyed.<n>We show that Randomized eviction restores identifiability.
  arXiv  Detail & Related papers  (2026-07-23T16:16:59Z)
• Make Each Token Count: Towards Improving Long-Context Performance with KV Cache Eviction [65.710271475739]
  We introduce a global retention-based KV eviction method that learns each token's future utility under a unified memory budget.<n>We show that our method substantially reduces KV memory while matching or surpassing full-cache inference.<n>These results suggest that learned, globally calibrated KV eviction is not only a compression technique, but also a mechanism for improving long-context reasoning.
  arXiv  Detail & Related papers  (2026-05-10T16:47:50Z)
• When Hidden States Drift: Can KV Caches Rescue Long-Range Speculative Decoding? [19.77569541429818]
  Speculative decoding accelerates LLM inference, but SOTA hidden-state-based drafters suffer from long-range decay.<n>We revisit long-range decay from the perspective of context information preservation.<n>We introduce KVShot, a diagnostic framework that compares three reuse paradigms.
  arXiv  Detail & Related papers  (2026-04-29T08:25:01Z)
• Learning from Emptiness: De-biasing Listwise Rerankers with Content-Agnostic Probability Calibration [76.08899010904652]
  CapCal is a training-free framework that mechanically decouples positional bias from ranking decisions.<n>It achieves superior performance among training-free methods while preserving single-pass efficiency.
  arXiv  Detail & Related papers  (2026-04-11T10:47:22Z)
• ForesightKV: Optimizing KV Cache Eviction for Reasoning Models by Learning Long-Term Contribution [84.41751286055909]
  We develop a training-based KV cache eviction framework that learns to predict which KV pairs to evict during longtext generations.<n>We formulate cache eviction as a Markov Decision Process and apply the GRPO algorithm to mitigate the significant language modeling loss increase on low-entropy tokens.
  arXiv  Detail & Related papers  (2026-02-03T07:16:51Z)
• SkipKV: Selective Skipping of KV Generation and Storage for Efficient Inference with Large Reasoning Models [25.509962883211]
  Large reasoning models (LRMs) often cost significant key-value (KV) cache overhead, due to their linear growth with the chain-of-thought (CoT) reasoning process.<n>We present textbfSkipKV, a KV compression method for selective textiteviction and textitgeneration operating at a coarse-grained sentence-level sequence removal.
  arXiv  Detail & Related papers  (2025-12-08T19:32:06Z)
• Judge Q: Trainable Queries for Optimized Information Retention in KV Cache Eviction [53.83828564664595]
  Large language models (LLMs) utilize key-value ( KV) cache to store historical information during sequence processing.<n>Current methods for KV cache eviction typically utilize the last window from the pre-filling phase as queries to compute the KV importance scores for eviction.<n>We propose Judge Q, a novel training method which incorporates a soft token list.
  arXiv  Detail & Related papers  (2025-09-13T03:34:12Z)
• CaliDrop: KV Cache Compression with Calibration [44.722738059962296]
  Large Language Models (LLMs) require substantial computational resources during generation.<n> KV cache compression techniques have been proposed to mitigate this bottleneck.<n>This paper focuses on enhancing token eviction strategies.
  arXiv  Detail & Related papers  (2025-07-26T10:34:53Z)
• Latent Veracity Inference for Identifying Errors in Stepwise Reasoning [78.29317733206643]
  We introduce Veracity Search (VS), a discrete search algorithm over veracity assignments.<n>It performs otherwise intractable inference in the posterior distribution over latent veracity values.<n>It generalizes VS, enabling accurate zero-shot veracity inference in novel contexts.
  arXiv  Detail & Related papers  (2025-05-17T04:16:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.