Error Certificates for KV-Cache Eviction via Randomized Design
Merged summary
TL;DR - This paper introduces randomized KV-cache eviction that enables serving-time error certificates. The certificates help attribute failures to cache eviction and schedule recomputation, but do not reliably predict failures or improve budget escalation.
- Deterministic top-k eviction cannot consistently estimate attention-output error because discarded values are unidentifiable.
- Poisson sampling with known inclusion probabilities enables a Hájek softmax correction and retained-set variance estimator.
- The per-step certificate achieved 0.97 empirical coverage without accuracy loss.
- Certificates distinguished cache-induced failures (AUC 0.73–0.75) better than output confidence, but output log-probability better predicted overall failure.
Sources (1)
Error Certificates for KV-Cache Eviction via Randomized Design
TL;DR - This paper introduces randomized KV-cache eviction that enables serving-time error certificates. The certificates help attribute failures to cache eviction and schedule recomputation, but do not reliably predict failures or improve budget escalation.
- Deterministic top-k eviction cannot consistently estimate attention-output error because discarded values are unidentifiable.
- Poisson sampling with known inclusion probabilities enables a Hájek softmax correction and retained-set variance estimator.
- The per-step certificate achieved 0.97 empirical coverage without accuracy loss.
- Certificates distinguished cache-induced failures (AUC 0.73–0.75) better than output confidence, but output log-probability better predicted overall failure.