중요한 토큰을 잘 고르는 것보다,
잃으면 안 되는 것을 먼저 지킨다

KV cache는 generation length에 선형으로 증가한다. Eviction은 budget을 넘은 KV pair를 영구 삭제해 memory를 bounded하게 만든다. Sparse attention은 일부 token만 attend해 compute를 줄이지만 pair 자체는 남기므로 peak memory는 계속 증가한다.

기존 연구는 score \(s_i\)를 개선해왔다. H2O는 cumulative attention, SnapKV는 recent-window attention, R-KV는 attention+redundancy, VaSE는 value magnitude와 stochastic fill, TriAttention은 position-dependent key statistics를 사용한다. 공통 전제는 score가 accuracy를 결정한다는 것이다.

Persistent budget \(K\)와 recent buffer \(r\)를 유지하고, buffer가 차면 candidate를 다시 K개로 줄인다. 실험 engine의 기본 trigger는 r=64다. 한번 버린 pair는 복구되지 않는다.

Algorithm 1은 rand → prompt=+∞ → topk → return keep 네 줄이다. Calibration, tuning, attention-statistics pass가 없다.

모델은 Qwen3-4B/14B/32B와 Phi-4-reasoning(14B)이다. MATH500 500문제, GPQA-D 198문제, AIME 2025/2026 각 30문제, HMMT 60문제, LiveCodeBench-v6 medium 383문제를 평가한다. AIME 두 연도는 한 column으로 pooled report한다. Maximum generation은 32k token이며 main grid는 약 4× compression, code는 약 3×다.

Budget은 MATH500 K=1024, GPQA-D K=2048, AIME/HMMT K=4096, LiveCodeBench K=3072다. Accuracy claim은 paired problem-clustered percentile bootstrap 95% CI와 exact sign test를 함께 통과해야 한다.

Main table의 60 baseline comparison 중 Random Attention은 31개에서 유의하게 앞서고, 유의하게 뒤진 경우는 Qwen3-32B LiveCodeBench의 TriAttention 한 cell이다. Math/science에서는 selector가 Random을 유의하게 앞선 사례가 없다.

Appendix의 Qwen3-14B도 큰 패턴을 재현하지만 TriAttention이 MATH500 +2.1, code +2.6 point, VaSE가 AIME +2.6 point로 유의하게 앞선다. 즉 Random이 모든 setting의 최적 policy라는 주장은 아니다.

Qwen3-4B와 Phi-4에서 2×→16×로 budget을 줄이면 2×에서는 모든 방법이 full attention 근처다. Compression pressure가 커질수록 Random과 TriAttention은 비슷하게 버티고 VaSE와의 차이는 커진다. Code는 prompt 자체가 작은 budget에 들어가지 않아 sweep에서 제외된다.

SnapKV처럼 prompt를 많이 잃던 방법은 크게 회복하고, R-KV처럼 이미 prompt retention이 높던 방법은 거의 변하지 않는다. Recency-only policy도 prompt를 보호하면 큰 폭으로 회복한다. 성능 격차의 상당 부분은 무엇을 rank했는가가 아니라 question을 잃었는가였다.

LiveCodeBench prompt는 평균 557 token으로 MATH500의 약 6배이고, 긴 경우 K=3072의 절반을 차지한다. Random은 prompt를 전부 pin하므로 code에서는 selection 전에 budget이 크게 줄어든다. 저자들은 I/O format과 harness scaffolding까지 모두 보호하는 대신 더 똑똑한 prompt budgeting을 future work로 남긴다.

Reasoning trace는 아직 필요한 intermediate value를 반복해서 다시 쓰고 요약한다. 중요한 상태가 한 position에만 존재하지 않는 경우가 많다.

모든 KV head는 각 token의 copy를 가진다. MATH500 trace에 synthetic fact를 심고 1,536 token 뒤에서 묻는 probe에서 single head는 최고 3% retrieval에 불과하지만 두 head는 60%, 세 head는 83%, 여덟 head는 99%까지 올라간다.

Fact token을 head 사이에 흩어 어느 head도 연속 문장을 갖지 않게 해도 recall은 거의 유지된다. 실제 MATH500에서도 contiguous block size 1→64는 거의 비용이 없고 256에서 head당 block 수가 너무 적어질 때 떨어진다. 어떤 모양의 copy인가보다 usable copy가 어딘가 살아 있는가가 더 중요하다.

57 compression round 전에 한 번만 제시되고 재서술되지 않은 passcode에서는 Random이 완전히 실패한다. Content-dependent signal이 실제로 필요한 경계다. 다만 R-KV의 강한 needle retrieval이 aggregate reasoning accuracy 우위로 직결되지는 않는다.

Random은 age score가 없지만 살아남은 token도 매 eviction마다 다시 추첨되므로 오래된 token의 생존률이 기하급수적으로 줄어든다. K=1024, r=64에서는 약 \(0.94^n\)이며 결과적으로 soft recency window + thin random tail처럼 동작한다.

모든 head가 같은 keep-set을 쓰는 shared draw는 real MATH500에서 Random과 거의 같은 accuracy를 보인다. Text redundancy가 충분한 경우 cross-head diversity는 load-bearing이 아니지만, once-stated fact처럼 text redundancy가 없을 때는 중요하다.

한 H200, K=2048, 1k prompt, 32k generation에서 Random은 TriAttention과 같은 paging/kernel/scheduler를 쓰면서 selector만 바꾼다. 논문의 method-level headline은 동일 runtime에서 +32–43% throughput이다.

Single stream eviction round는 Random 약 .30 ms, TriAttention 1.47–1.64 ms다. 하지만 128 concurrent request가 각각 64 generated token마다 압축되면 workload당 약 62k compression event가 생기고, batch synchronization point에서 다른 request가 기다린다. Paged KV를 읽어 content score를 계산하는 추가 pass가 반복되면서 작은 per-call cost가 큰 serving margin으로 증폭된다.

K=3072, 32k generation의 unpaged equal-memory 실험에서 Qwen3-4B는 Full batch 28/178 tok/s에 비해 Random batch 200/1779 tok/s, 즉 10.01×다. Qwen3-14B는 Full 20/164 대비 Random 120/1436, 8.78×다. K=1024의 Qwen3-4B에서는 batch 584, 5110 tok/s, 28.79×까지 커진다.

8k처럼 compute-bound인 짧은 generation에서는 compression 자체가 full attention보다 느릴 수 있다. Random은 Qwen3-4B/14B/32B에서 .52×/.70×/.96×, Phi-4에서 .76× full-attention throughput이다. 그럼에도 TriAttention 대비 margin은 유지된다.

저자들은 released vLLM benchmark가 requested output length를 무시해 compression threshold에 도달하지 않는 문제와, deduplication guard가 이후 compaction을 비활성화할 수 있는 문제를 수정했다. Reported run은 applied-event counter로 compression 실행을 검증했다.

Keep-log에서 Random의 slot coverage는 .999–1.000이며 prompt survival은 union/per-head 모두 .994–.999 수준이다. SnapKV는 prompt survival이 가장 낮다. Generation length 분석에서 Random은 Qwen3-4B와 14B에서 evictor 중 평균 generation이 가장 짧고, 다른 두 모델에서도 최단 방법의 약 5% 안쪽이다. 따라서 accuracy parity가 더 긴 reasoning으로 얻어진 것은 아니다.

Run-to-run standard deviation은 대체로 MATH500 1 point 이하, GPQA-D/LiveCodeBench 1–3 point, competition math 2–5 point다. Engine은 per-KV-head physical eviction, chronological compaction, post-RoPE key storage를 사용하고 accuracy generation은 H200 fleet, efficiency는 single H200에서 측정한다.

논문은 long-context KV quantization/eviction, StreamingLLM attention sink, SnapKV, R-KV, VaSE, TriAttention, LazyEviction, SpeContext, Prefix Sliding, random cache management과 연결된다. 차별점은 short prompt + long self-generated trace regime에서 prompt protection을 맞춘 controlled comparison과 redundancy probe다.

저자들은 LLM coding/writing assistant를 drafting/editing, analysis·plotting code, table typesetting에 사용했지만 experiment design, hypothesis/threshold selection, reported measurement에는 사용하지 않았다고 밝힌다. AI-assisted artifact는 저자가 검토하고 통계는 released per-instance logs에서 재계산했다고 명시한다.

이 논문은 KV eviction의 성능을 세 층으로 분해한다. 첫째, irreplaceable prompt를 보호하는 규칙. 둘째, reasoning trace가 자체적으로 제공하는 text/cross-head redundancy. 셋째, selector가 실제 serving runtime에서 지불하는 scoring and synchronization cost다.

따라서 새로운 selector는 동일 K, 동일 prompt protection, 동일 runtime에서 score 없는 Random Attention이라는 null hypothesis보다 낫다는 것을 입증해야 한다.