kv-cache-eviction-benchmark

Author: João Felipe De Souza

---

Overview

Benchmark of KV-cache eviction policies during decode, measuring the tradeoff between:

• quality (perplexity)
• cache size
• throughput
• latency

This project closes the loop from the attention-sink-profiler: if the first tokens receive disproportionate attention, what happens when we evict them?

For architecture and implementation details, see DESIGN.md.

---

Why This Matters

Modern LLM serving engines cannot always keep the full KV-cache in memory forever. At some point, tokens must be evicted.

The key question is:

Which tokens should we keep?

This project compares realistic eviction strategies and shows that:

• naive sliding-window eviction is catastrophic
• preserving sink tokens is the best heuristic at tiny budgets
• attention-based eviction becomes dominant at moderate budgets

---

Model and Setup

Model

• GPT-2-medium (345M)

Hardware

• NVIDIA RTX 2070
• CUDA 13.0

Evaluation setup

• Prefix length: 512 tokens
• Evaluated continuation: 128 tokens
• 5 prompt types
• Teacher-forced decode with absolute position IDs preserved

Policies

• full
• sliding_64
• sliding_128
• sink4_window60
• sink8_window56
• random_64
• attention_64

Budget sweep

• budgets: 64, 128, 192, 256, 384
• compared:
  • sliding window
  • sink8 + recent window
  • attention-based eviction

---

Key Findings

Finding 1 — Sliding window alone catastrophically fails

Average over 5 prompts:

Policy	Avg PPL	Cache tokens
full	1.02	576
sliding_64	4138.37	64
sliding_128	2764.71	128

Keeping only recent tokens destroys quality.

Finding 2 — Sink-preserving eviction massively improves low-budget quality

At the same 64-token cache budget:

Policy	Avg PPL	Cache tokens
sliding_64	4138.37	64
sink4_window60	92.63	64
sink8_window56	69.62	64

At the same memory budget, preserving the first 8 sink tokens improves perplexity by roughly 59× over plain sliding window.

Finding 3 — Sink-preserving beats a much larger plain window

Policy	Avg PPL	Mean cache
sliding_128	2764.71	128
sink8_window56	69.62	64

A tiny sink-preserving cache is dramatically better than a much larger plain recent window.

Finding 4 — Attention-based eviction wins once budget is large enough

Best policy by budget:

Budget	Best policy	Avg PPL	Relative to full
64	sink8_window56	69.62	68.4×
128	attention_128	37.51	36.9×
192	attention_192	8.38	8.2×
256	attention_256	1.88	1.85×
384	attention_384	1.02	1.00×

This reveals two distinct regimes:

• Extreme compression → sink heuristic wins
• Moderate / high budget → attention-based eviction dominates

Finding 5 — Near-lossless eviction is possible

At budget = 384:

Policy	Avg PPL
full	1.0178
attention_384	1.0219

That is effectively identical quality while cutting cache from 576 to 384 tokens (~33% reduction).

Finding 6 — Throughput barely changes

Average throughput across policies stays around:

• 66–70 tok/s

So the real tradeoff is not throughput vs memory. It is:

quality vs which tokens are retained

---

Main Conclusion

This benchmark reveals a clear policy hierarchy:

1. Sliding window is the worst policy
2. Sink-preserving window is the best low-budget heuristic
3. Attention-based eviction becomes best once the cache budget is large enough

In practice:

• if you only have a tiny cache budget, preserve sink tokens
• if you can afford a moderate cache budget, attention-based eviction can approach full-cache quality

This is a strong practical validation of the attention sink hypothesis.

---

Results Files

File	Description
results/kv_eviction_results.csv	Full prompt × policy benchmark
results/kv_eviction_summary.csv	Mean metrics by policy
results/best_policy_by_prompt.csv	Best compressed policy per prompt
results/budget_sweep_results.csv	Full budget sweep
results/budget_sweep_summary.csv	Aggregated by policy type + budget
results/best_policy_by_budget.csv	Best policy at each budget
results/metadata.json	Benchmark configuration

---

Plots

File	Description
plots/avg_ppl_by_policy.png	Average perplexity by policy
plots/prompt_ppl_delta_grouped.png	Per-prompt quality degradation
plots/cache_reduction_vs_quality.png	Memory saved vs quality loss
plots/throughput_vs_quality.png	Throughput vs perplexity tradeoff
plots/best_policy_per_prompt.png	Best compressed policy per prompt
plots/budget_sweep_ppl.png	Mean PPL vs cache budget
plots/best_policy_by_budget.png	Best policy at each cache budget
plots/budget_sweep_relative_loss.png	Relative quality loss vs budget

---

Repository Structure

kv-cache-eviction-benchmark/
├── kv_eviction_benchmark.py
├── budget_sweep.py
├── plot_eviction.py
├── plot_budget_sweep.py
├── README.md
├── DESIGN.md
├── LICENSE
├── requirements.txt
├── results/
└── plots/

---

How to Run

1. Setup

python3 -m venv venv && source venv/bin/activate
pip install -r requirements.txt

2. Run the policy benchmark

python3 kv_eviction_benchmark.py

3. Run the budget sweep

python3 budget_sweep.py

4. Generate plots

python3 plot_eviction.py
python3 plot_budget_sweep.py

---

Limitations

• Only GPT-2-medium tested
• Single GPU / single batch setup
• Attention-based eviction uses accumulated attention, not a learned policy
• Teacher-forced perplexity is a proxy for quality
• Prefix and continuation lengths are fixed

---

References

• Xiao et al., Efficient Streaming Language Models with Attention Sinks (2023)
• Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention (2023)