Kv-cache eviction timing affects token prediction errors in language models
Divergence Timing and Cumulative Disagreement under KV-Cache Eviction
Machine Learning
Summary
When language models predict words one after another, they keep a memory (a key-value cache) to help make better guesses. The authors studied how removing parts of this memory (eviction) changes the predictions over time, causing the model's output to differ from what it would have been. They break down how soon these differences start and how they accumulate later. Using two popular language models, they show that certain eviction methods delay and reduce early errors but don't lower overall differences after divergence begins. Most mismatches come from differences after the predictions first diverge.
What this means in practice
- •For language model engineers: Optimize cache eviction strategies to reduce early token prediction errors and improve generation consistency in large autoregressive models.
- •For nlp system designers: Design better caching mechanisms for autoregressive text generation systems that balance retention rate and prediction divergence timing.
Authors
Xinyue Luo, Fei Yu
Abstract
KV-cache eviction perturbs the conditional token distributions governing autoregressive generation. We investigate how first-divergence timing and subsequent token mismatch determine cumulative disagreement. We derive an exact decomposition under a specified stepwise maximal coupling: the expected mismatch fraction equals a first-mismatch contribution plus post-divergence exposure multiplied by its mismatch rate. An explicit construction over unrestricted autoregressive kernel pairs realizes the sharp interval of risks compatible with a finite divergence-aligned observation window. Residual-branch conditional Monte Carlo provides unbiased joint estimates of occurrence, occupation, and window/tail contributions, with per-replicate variance dominance for total token loss. Complete trajectories from Meta-Llama-3.1-8B-Instruct and Qwen2.5-7B-Instruct show that SnapKV at 50% retention enters divergence later and less often than SnapKV-512 or recent-token retention with the same 50% prompt-cache budget, while post-divergence total variation (TV) remains high. In an exploratory analysis of 288 documents, post-divergence exposure accounts for 85-90% of four aggregate mismatch gaps. On 288 independent documents at 90% retention, prespecified comparisons show higher branch-aligned TV in the late than in the early window in both models.