Paper Review
Error Certificates for KV-Cache Eviction via Randomized Design
This paper proves that deterministic top-k KV-cache eviction cannot certify its own damage -- evicted values can be altered so everything the serving system retains is unchanged while the true attention-output error grows unboundedly -- and shows that a cheap randomized retention scheme (Poisson sampling plus one logit correction) restores enough statistical structure to build a real per-step error certificate, though pre-registered testing finds that certificate is worth its 2x overhead only for attributing and scheduling recovery from failures, not predicting them.
이 논문은 결정적(top-k) KV 캐시 제거가 스스로의 손상을 증명할 수 없음을 증명한다 -- 서빙 시스템이 보관 중인 것은 그대로 둔 채 제거된 값을 바꿔도 진짜 attention-output 오차는 얼마든지 커질 수 있다 -- 그리고 저렴한 무작위 유지 방식(Poisson 샘플링 + logit 보정 한 번)이 진짜 per-step 오차 증명서를 만들 만큼의 통계적 구조를 되살린다는 것을 보인다. 다만 사전등록 검증 결과, 이 증명서는 실패를 예측하는 데가 아니라 실패를 원인 규명하고 복구를 스케줄링하는 데서만 2배 비용을 치를 가치가 있다.
Background Long-context LLM serving commonly evicts low-importance key-value (KV) cache entries to save memory. Existing deterministic eviction methods -- H2O, SnapKV, TOVA, StreamingLLM, PyramidKV, Ada-KV -- keep the top-k tokens under an importance score and simply discard the rest, with no uncertainty quantification about how risky that decision is.
배경 장문맥(long-context) LLM 서빙은 메모리를 아끼려고 중요도가 낮은 KV(key-value) 항목을 캐시에서 제거하는 eviction을 흔히 쓴다. H2O, SnapKV, TOVA, StreamingLLM, PyramidKV, Ada-KV 등 기존의 결정적(deterministic) eviction 방법들은 중요도 점수로 top-k만 남기고 나머지는 그냥 버리며, 그 결정이 얼마나 위험한지에 대한 불확실성 정량화는 전혀 제공하지 않는다.
Problem The paper proves deterministic eviction is structurally unable to certify its own damage (Theorem 1): evicted values can be adversarially altered so that every statistic the serving system actually retains stays bit-identical, while the true attention-output error grows arbitrarily large -- meaning no serving-time estimator of that error can be statistically consistent. This is a particularly dangerous blind spot in streaming or agent-memory settings where the question isn't known before compression happens.
문제 이 논문은 결정적 eviction이 구조적으로 자기 손상을 증명할 수 없음을 증명한다(정리 1) -- 제거된 값을 적대적으로 바꿔도 서빙 시스템이 실제로 보관 중인 모든 통계량은 완전히 동일하게 유지되는 반면, 진짜 attention-output 오차는 한없이 커질 수 있다. 즉 서빙 시점에서 그 오차를 추정하는 어떤 방법도 통계적으로 일관될(consistent) 수 없다 -- 질문을 미리 알 수 없는 streaming/에이전트 메모리 설정에서 특히 치명적인 사각지대다.
Prior limitations Prior deterministic eviction papers (H2O, SnapKV, TOVA, StreamingLLM, PyramidKV, Ada-KV) select purely by importance score with no uncertainty quantification; prior randomized approaches (MagicPIG, Nexus, VASE) sample but lack variance estimates or error certificates; sparse-attention-with-guarantees methods keep the full cache resident and so never actually evict. Classical design-based inference from survey statistics (Horvitz-Thompson, Sen-Yates-Grundy) existed but had never been applied to permanent KV eviction.
기존 한계 기존 결정적 eviction 논문들(H2O, SnapKV, TOVA, StreamingLLM, PyramidKV, Ada-KV)은 불확실성 정량화 없이 중요도 점수로만 선택하고, 무작위 방식의 선행 연구(MagicPIG, Nexus, VASE)는 샘플링은 하지만 분산 추정이나 오차 증명서가 없으며, 완전한 캐시를 유지하는 sparse-attention-with-guarantees 계열은 애초에 진짜로 제거를 하지 않는다. 고전 설문조사 통계학의 design-based inference(Horvitz-Thompson, Sen-Yates-Grundy)는 존재했지만 영구적 KV eviction에는 아무도 적용하지 않았다.
Goal Not a better importance score, but a randomized design under which the retained cache's own statistics can certify how much error the eviction introduced -- a genuine, statistically valid per-step error certificate.
목표 더 나은 중요도 점수를 찾는 것이 아니라, 유지된 캐시 자체의 통계량만으로 eviction이 만든 오차를 증명할 수 있는 무작위화 설계(randomized design) -- 즉 통계적으로 타당한 per-step 오차 증명서를 만드는 것이 목표다.
Method A certainty set (4 sink tokens plus 32 recent tokens, always kept, inclusion probability πᵢ=1) covers the protected positions; the rest of the cache is a Poisson-sampled tail (independent Bernoulli retention with inclusion probability proportional to an importance score). The Hájek correction is implemented elegantly -- add log(1/πᵢ) to the retained logit and let the softmax denominator renormalize itself. The per-step error certificate wraps a survey-sampling variance estimator in an empirical-Bernstein bound (Theorem 2), extended via an e-process for time-uniform validity across autoregressive decode steps.
방법 확실성 집합(sink 토큰 4개 + 최근 토큰 32개, 항상 유지, 포함확률 πᵢ=1)과 나머지 토큰에 대한 Poisson 샘플링 tail(중요도 점수에 비례한 독립 Bernoulli 포함확률)로 캐시를 구성한다. Hájek 보정은 구현이 우아하다 -- 유지된 로짓에 log(1/πᵢ)만 더하면 softmax의 분모가 알아서 재정규화를 해준다. per-step 오차 증명서는 설문조사 통계학의 분산 추정량을 empirical-Bernstein 경계에 넣어 만들며(정리 2), 디코딩 스텝 전체에 걸쳐 시간-균일하게 유효하도록 e-process로 확장한다.
Key idea The core insight is that randomization buys identifiability, not prediction -- like a museum curator quietly discarding boxes judged 'unimportant' with no manifest: nobody, not even the curator, can later prove what was lost or how much it mattered. Randomized retention with known inclusion probabilities keeps that manifest, so even discarded material leaves a statistically traceable footprint, and the certificate is literally the audit function over that manifest.
핵심 아이디어 핵심 통찰은 무작위화가 '예측'이 아니라 '식별가능성(identifiability)'을 사는 것이라는 점이다 -- 마치 미술관 큐레이터가 아무 목록도 없이 '안 중요하다'고 판단한 상자를 조용히 폐기하면, 나중에 무엇이 얼마나 손실됐는지 큐레이터 자신조차 증명할 수 없는 것과 같다. 알려진 포함확률로 무작위 유지를 하면 버려진 자료조차 통계적으로 추적 가능한 흔적을 남기게 되고, 증명서는 바로 그 목록에 대한 감사(audit) 함수다.
Validation Attention-level validation: the Poisson certificate achieves 96.9-97.7% empirical coverage at delta=0.1 (pass line 85%), a 0.943-0.979 Spearman correlation between certificate and true error (pass line 0.3), and a constructive impossibility demonstration -- permuting evicted values in a real model changes the true error by 64x while deterministic top-k's retained-set statistics stay bit-identical. Task-level validation: roughly 74,000 real generations across four models (Qwen2.5-1.5B/7B, Llama-3.1-8B, Mistral-7B) at 6k and 16k context on LongBench-style QA plus needle retrieval, under seven pre-registered claims with explicit kill conditions.
검증 attention 레벨 검증: Poisson 증명서의 실측 커버리지 96.9-97.7%(δ=0.1, 통과선 85%), 증명서와 실제 오차 간 Spearman 상관 0.943-0.979(통과선 0.3), 그리고 실제 모델에서 제거된 값을 뒤섞으면 진짜 오차는 64배 변하는데 결정적 top-k가 유지한 통계량은 완전히 동일하게 남는다는 구성적 불가능성 시연. 과제 레벨 검증: 4개 모델(Qwen2.5-1.5B/7B, Llama-3.1-8B, Mistral-7B)로 6k·16k 컨텍스트의 LongBench 계열 QA + needle 검색에서 약 74,000건의 생성 결과를 놓고 킬 조건이 명시된 7개 사전등록 주장을 검증했다.
Results 3 of 7 pre-registered claims were explicitly killed: prediction AUC came in at 0.555-0.572, below the 0.6 kill line, because question-aware eviction turns out nearly free (only a 4-6.2% induced-failure rate at a 25% budget) -- output log-probability actually predicts failure better (0.78-0.81 vs. 0.56-0.57); certificate-gated budget escalation adds nothing when there's no headroom left to exploit. What survives: the certificate is the only signal that beats chance at attributing a failure specifically to cache damage (AUC 0.727-0.749 vs. 0.469-0.542 for output confidence, across roughly 7,900-11,700 total failures), and under harsh streaming budgets it improves recomputation scheduling by +1.9 to +4.4 percentage points over random or confidence-based gating.
결과 사전등록된 7개 주장 중 3개가 명시적으로 기각됐다 -- 증명서의 실패 예측 AUC는 0.555-0.572로 킬 라인 0.6 아래였는데, 이는 질문을 미리 아는 eviction이 25% 예산에서도 유발 실패율 4-6.2%에 불과할 만큼 '거의 공짜'이기 때문이며, 출력 log-probability가 오히려 예측을 더 잘한다(0.78-0.81 대 0.56-0.57). 살아남은 것은 원인 규명이다 -- 증명서는 캐시로 인한 실패와 원래 있던 실패를 구분하는 유일하게 우연 수준을 넘는 신호(AUC 0.727-0.749, 출력 confidence는 0.469-0.542에 불과)이며, 혹독한 streaming 예산 아래서 무작위/confidence 게이팅 대비 재계산 스케줄링을 +1.9~4.4pp 개선한다.
Comparison Against deterministic entropy/margin signals from H2O-style methods (AUC 0.43-0.51, at or below chance for cache-induced failure) and evicted-score-mass heuristics (0.59-0.73, a partial signal that washes out at the overall-prediction level), the certificate is the only cache-side signal with a real, design-guaranteed relationship to the true compression error. Against output log-probability specifically, the certificate loses on raw prediction but wins clearly on attribution, which log-probability structurally cannot do since it conflates task difficulty with cache damage.
비교 H2O류의 결정적 엔트로피·마진 신호(AUC 0.43-0.51, 캐시로 인한 실패에는 우연 수준이거나 그 이하)나 제거된 점수 질량 휴리스틱(0.59-0.73, 전체 예측에서는 희석되는 부분적 신호)과 비교하면, 증명서는 실제 압축 오차와 설계상 보장된 관계를 갖는 유일한 캐시측 신호다. 출력 log-probability와 비교하면 순수 예측에서는 증명서가 지지만, log-probability는 구조적으로 과제 난이도와 캐시 손상을 구분하지 못하므로 원인 규명에서는 증명서가 확실히 이긴다.
Significance The paper's honest conclusion reframes what 'safe' KV eviction should even promise: in most practical regimes -- the question known ahead of time, or an application willing to trust output confidence -- plain deterministic eviction at 25-50% budgets is already close to free, and no certificate is needed. The certificate earns its 2x decode-time overhead specifically in streaming/agentic-memory settings, where the question isn't known before compression and 40-58% of failures can be silently cache-induced -- exactly the regime long-horizon agent serving is moving toward.
의의 이 논문의 정직한 결론은 '안전한' KV eviction이 무엇을 약속해야 하는지 자체를 재구성한다 -- 질문을 미리 알거나 출력 confidence를 신뢰할 수 있는 대부분의 실용적 상황에서는 25-50% 예산의 평범한 결정적 eviction만으로 이미 거의 공짜에 가깝고, 증명서는 필요 없다. 증명서가 2배 디코드 시간 오버헤드를 감당할 가치가 있는 곳은 압축 전에 질문을 알 수 없는 streaming/에이전트 메모리 설정뿐이며, 이때는 실패의 40-58%가 조용히 캐시 유발일 수 있다 -- 바로 장기 실행 에이전트 서빙이 향하고 있는 그 체제다.
Limitations The paper's own limitations section restricts its claims to contexts up to 16k and models up to 8B parameters, and explicitly flags that its 'streaming' condition is a single-turn proxy for genuine multi-turn agent memory that hasn't itself been tested. The certificate's task-level meaning is established empirically rather than by a formal end-to-end bound (only the per-layer attention-error certificate is actually proven); the measured 2x overhead comes from an unoptimized Python prototype, and a fused-kernel implementation realizing the paper's claimed asymptotic O(|tail|) cost is explicitly named as engineering work not yet done.
한계 저자 스스로 밝힌 한계로, 검증은 컨텍스트 16k 이하·모델 8B 이하로 제한되며, streaming 조건은 단일 턴 과제로 진짜 다중 턴 에이전트 메모리를 근사한 것일 뿐 아직 검증되지 않았다고 명시한다. 증명서의 과제 레벨 의미는 형식적 경계가 아니라 경험적으로 확립된 것이며(증명된 것은 레이어별 attention 오차 증명서 자체뿐), 측정된 2배 오버헤드는 최적화되지 않은 Python 프로토타입 기준으로, 논문이 주장하는 점근적 O(|tail|) 비용을 실현할 fused 커널 구현은 아직 하지 않은 엔지니어링 작업이라고 명시한다.
Future work The authors' Discussion section names concrete next steps: a fused kernel implementation to realize the O(|tail|) asymptotic cost in practice; extending the method to larger models and longer contexts; conditional/rejective Poisson sampling to hit exact fixed eviction budgets rather than expected ones; and a sketched-but-unproven extension (Remark 2) for reusing tail samples across decode steps in a block-aware way.
향후 과제 저자가 Discussion에서 명시한 다음 단계는: 점근적 O(|tail|) 비용을 실제로 구현할 fused 커널 작성, 더 큰 모델·더 긴 컨텍스트로의 확장, 기대 예산이 아니라 정확히 고정된 eviction 예산을 위한 conditional/rejective Poisson 샘플링, 그리고 디코딩 스텝 사이에서 tail 샘플을 블록 단위로 재사용하는 아직 증명되지 않은 스케치(Remark 2)다.
Released resources The paper states that roughly 98,000 scored generation logs, exact prompts, analysis scripts, and timestamped pre-registration files were released, but no actual repository URL was located in the reviewed text -- no public release verified. The arXiv paper itself is confirmed accessible.
자원 공개 논문은 약 98,000건의 채점된 생성 로그, 정확한 프롬프트, 분석 스크립트, 시간이 찍힌 사전등록 파일이 공개됐다고 서술하지만, 검토한 본문에서는 실제 저장소 URL을 찾지 못했다 -- 공개 링크 확인 안 됨. arXiv 논문 자체는 확인 가능하다.
The research thread
Where this paper sits 연구의 흐름
KV-cache eviction research grew out of an importance-score lineage running through H2O, SnapKV, StreamingLLM, TOVA, PyramidKV, and Ada-KV -- an escalating competition to score which tokens matter more precisely, with essentially no attention paid to what happens when that score is wrong. A parallel randomized-sampling line (MagicPIG, Nexus, VASE) emerged too, but it implicitly assumed that sampling itself was a safety property, without attaching any statistical certificate to what was actually sampled.
This paper's shift is to step outside the better-scoring competition entirely and change the question: not "what should we keep," but "can we prove what we threw away." It nails down, as a theorem, that the answer is structurally no under any deterministic design -- then reaches into classical survey statistics (Horvitz-Thompson-style randomized sampling design) and applies it to cache eviction for what the paper frames as the first time, turning an unanswerable question back into a tractable one. Where other papers argue "this score is better," this one argues "no score, however good, can be certified if you evict deterministically" -- a move that changes which axis the field is competing on.
As the author is careful to admit, the certificate only wins in a narrow regime -- in most practical settings where the question is known ahead of time, plain deterministic eviction is already close to free. But as serving shifts toward agents that accumulate memory over days, where at compression time nobody yet knows what question will arrive later, the question "can we prove what we just lost" only grows more load-bearing. The natural next steps are building the fused kernel needed to realize the method's O(|tail|) cost in a real deployment, and checking whether the same certificate structure holds up at far longer contexts and far larger models.
KV 캐시 eviction 연구는 H2O·SnapKV·StreamingLLM·TOVA·PyramidKV·Ada-KV로 이어지는 중요도-점수 계열에서 출발했다 -- 어떤 토큰을 남길지 점점 더 정교하게 점수 매기는 쪽으로 경쟁해 왔지만, 그 점수가 틀렸을 때 무엇이 벌어지는지는 아무도 재지 않았다. MagicPIG·Nexus·VASE 같은 무작위 샘플링 계열도 등장했지만, 이들 역시 "샘플링했다"는 사실 자체가 안전을 보장한다고 암묵적으로 가정할 뿐, 그 샘플링에 통계적 증명서를 붙이지는 않았다.
이 논문의 전환은 더 나은 점수를 찾는 경쟁에서 완전히 벗어나 질문 자체를 바꾼 데 있다: "무엇을 남길지"가 아니라 "무엇을 버렸는지 증명할 수 있는가"를 묻는다. 그리고 그 답이 결정론적 설계 안에서는 원천적으로 불가능하다는 것을 정리로 못박은 뒤, 설문조사 통계학의 고전적 도구(Horvitz-Thompson류 무작위 표본설계)를 캐시 eviction에 처음 적용해 문제를 해결 가능한 형태로 되돌린다. 다른 논문들이 "이 점수가 더 낫다"고 주장할 때, 이 논문은 "점수가 무엇이든 결정론적으로 버리면 증명서를 만들 수 없다"고 말한다 -- 경쟁의 축 자체를 바꾸는 움직임이다.
저자가 스스로 인정하듯, 이 증명서가 이기는 자리는 좁다 -- 질문을 미리 아는 대부분의 실용적 상황에서는 그냥 결정론적으로 버려도 거의 공짜다. 하지만 에이전트가 며칠에 걸쳐 메모리를 누적하고, 압축 시점에는 나중에 어떤 질문이 올지 알 수 없는 세계로 서빙이 옮겨갈수록, "지금 무엇을 잃었는지 증명할 수 있는가"라는 질문은 점점 더 중요해진다. 다음 단계는 이 방법이 실제로 배포 가능해지도록 O(|tail|) 비용을 실현하는 fused 커널을 만드는 일과, 훨씬 긴 컨텍스트·훨씬 큰 모델에서도 같은 증명서 구조가 버티는지 확인하는 일이다.
Sparks — where one could take this 아이디어의 씨앗
-
One could implement the conditional/rejective Poisson sampling the paper leaves untested -- hitting an exact fixed eviction budget rather than an expected one -- and check whether the certificate's coverage guarantee survives under the hard 'keep exactly X%' constraint real serving systems actually need. 논문이 미검증으로 남긴 conditional/rejective Poisson 샘플링(기대 예산이 아니라 정확히 고정된 eviction 예산)을 구현하면, 서빙 시스템이 실제로 요구하는 '정확히 X%만 남긴다'는 하드 제약 아래서도 증명서의 커버리지가 유지되는지 확인해볼 수 있다.
-
One could test, on a genuine multi-turn agent-memory benchmark (the paper's current 'streaming' condition is only a single-turn proxy, named as future work), whether the certificate's attribution edge (AUC 0.73-0.75) holds up, or whether the line between cache-induced and inherent failure blurs as conversations grow longer. 저자가 향후 과제로 명시한, 진짜 다중 턴 에이전트 메모리 벤치마크(지금의 streaming 조건은 단일 턴 근사에 불과하다)에서 증명서의 원인 규명 우위(AUC 0.73-0.75)가 그대로 유지되는지, 아니면 대화가 길어질수록 캐시-유발 실패와 원래 실패의 경계가 흐려지는지 측정해볼 수 있다.
Seeds grounded in the paper's own stated limitations and open questions. 논문이 스스로 밝힌 limitations와 open questions에 뿌리를 둔 씨앗입니다.
Notes
Notes
A solo-author preprint that reads unusually close to this workspace’s own research discipline: seven pre-registered claims with explicit kill conditions, three reported as failed rather than quietly reframed, and a narrow, precisely-scoped surviving claim (attribution and recomputation scheduling, not failure prediction) instead of an oversold headline. The impossibility theorem for deterministic eviction is the more citable long-term contribution — it reframes the entire KV-eviction literature’s implicit safety assumption rather than adding one more importance-score variant to it.
Linked reviews
H2O: Heavy-Hitter Oracle for Efficient Generative Inference of LLMs
A small set of "heavy-hitter" tokens dominates attention mass, so greedily evicting low-accumulated-attention entries keeps only ~20% of the KV cache while matching full-cache accuracy and raising serving throughput up to 29x.
quantizationKIVI: A Tuning-Free Asymmetric 2-bit Quantization for KV Cache
Asymmetric KV quantization derived from element-distribution analysis — per-channel keys, per-token values — pushes the KV cache to tuning-free 2 bits, cutting peak memory 2.6x and lifting serving throughput up to 3.47x.
kv-cacheWindowed-MTP: Removing the Full-Context Draft-KV Tax at Million-Token Context
Windowed-MTP names the long-context draft-attention tax in built-in Multi-Token-Prediction speculative-decoding heads -- the draft re-reads the entire KV cache every step, so at million-token context it can flip speculation net-negative -- and fixes it losslessly with a training-free sink+window applied only to the draft's attention, cutting per-decode-step cost 28-44% across three architecture families at 1M tokens.
sparse-attentionLearning What Matters: Supervising Global Context Pruning with Causal Evidence Sets
Sparse-attention routers are usually trained to imitate a dense teacher's attention pattern; this paper builds tasks with exactly known causal evidence and shows attention and causal dependence disagree, with a router trained on masking-derived causal labels reaching 0.99 routed accuracy on a 2-hop task versus 0.41 for an attention-distilled router, plus a pretrained-model result where larger models get answers right well before their attention becomes trustworthy.