Monte Carlo Estimation for KV Cache Eviction
cs.CL, cs.AI
Submitted: 2026-10-06
Updated: 2026-10-14
License: http://creativecommons.org/licenses/by/4.0/
The gist: Most KV-cache eviction methods ask, in effect, which memory appeared important while reading the prompt? We instead ask, which memory will matter while answering? Since decoding queries are
Terminology
Abstract
Most KV-cache eviction methods ask, in effect, which memory appeared important while reading the prompt? We instead ask, which memory will matter while answering? Since decoding queries are unavailable at eviction time, prior future-aware methods rely on pseudo-responses or synthetic future-query estimates. We cast fixed-budget future-aware eviction as distributional estimation over plausible model-conditional query trajectories and introduce LORE-KV (Lookahead Output-perturbation with Reliability-weighted Ensembles for Key-Value caches), a training-free method that samples short autoregressive continuations from the frozen target model and uses their response-side query states to estimate prompt-token utility. Tokens are scored by projected leave-one-out attention-output deletion cost and aggregated across sampled futures with optional trajectory weighting. The temporary continuations are discarded before final decoding, requiring no auxiliary model or training. Ablations isolate the mechanism: at B=128, a single response-side continuation recovers about 89% of the gain over the prompt-window control, while additional futures provide smaller improvements. At B=128, LORE-KV raises the LongBench average on Qwen2.5-14B from 45.49 to 48.24 (+2.75) and the 16K RULER average on Mistral-7B from 45.20 to 51.05 (+5.85). Gains diminish at larger cache budgets and coexist with task-level regressions. LORE-KV incurs 1.46-2.77x AnDPro's per-sample wall-clock time as a one-time compression overhead across six dense and hybrid-attention backbones.
Sources
- LookaheadKV: Fast and Accurate KV Cache Eviction by Glimpsing into the Future without Generation
- RocketKV: Accelerating Long-Context LLM Inference via Two-Stage KV Cache Compression
- Make Each Token Count: Towards Improving Long-Context Performance with KV Cache Eviction
- xKV: Cross-Layer KV-Cache Compression via Aligned Singular Vector Extraction
- QAQ: Quality Adaptive Quantization for LLM KV Cache
- Taming the Fragility of KV Cache Eviction in LLM Inference
- Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference
- Protection Is (Nearly) All You Need: Structural Protection Dominates Scoring in Globally Capped KV Eviction
- CAOTE: KV Cache Selection for LLMs via Attention Output Error-Based Token Eviction
- The Llama 3 Herd of Models
- OBCache: Optimal Brain KV Cache Pruning for Efficient Long-Context LLM Inference
- RULER: What's the Real Context Size of Your Long-Context Language Models?
- Mistral 7B
- GEAR: An Efficient KV Cache Compression Recipe for Near-Lossless Generative Inference of LLM
- Fast KVzip: Efficient and Accurate LLM Inference with Gated KV Eviction
- KVTuner: Sensitivity-Aware Layer-Wise Mixed-Precision KV Cache Quantization for Efficient and Nearly Lossless LLM Inference
- GraphKV: Breaking the Static Selection Paradigm with Graph-Based KV Cache Eviction
- CONF-KV: Confidence-Aware KV Cache Eviction with Mixed-Precision Storage for Long-Horizon LLM
- MiniCache: KV Cache Compression in Depth Dimension for Large Language Models
- Ministral 3
Related papers
- Exploring Solution Divergence and Its Effect on Large Language Model Problem Solving
- Ishigaki-IDS-Bench: A Benchmark for Generating Information Delivery Specification from BIM Information Requirements
- Subliminal Steering: Stronger Encoding of Hidden Signals
- MedStruct-S: A Benchmark for Key Discovery, Key-Conditioned QA and Semi-Structured Extraction from OCR Clinical Reports
- The End of Transformers? On Challenging Attention and the Rise of Sub-Quadratic Architectures
- Untangling the Mechanisms of Misleading Context in Medical Question Answering