Simulador de políticas de eviction para prefix KV-cache em servidores LLM.
Stack: C++20 (core) · Python (análise/plots) · CMake + Ninja · WSL/VSCode
Servidores LLM modernos (vLLM, SGLang) reutilizam o KV-cache de prefixes repetidos entre requests. Se dois requests compartilham o mesmo prefixo (ex.: system prompt), o KV-cache desse prefixo pode ser reutilizado sem recomputação — reduzindo latência de prefill de O(n²) para O(1) por token.
Este simulador mede hit rate, prefill saved e latência para diferentes políticas de eviction, tamanhos de cache e padrões de workload.
python3 -m venv .venv && source .venv/bin/activate
pip install matplotlib pandas numpy
mkdir build && cd build
cmake .. -G Ninja -DCMAKE_BUILD_TYPE=Release
ninja && cd ..
# Gera workload
python3 experiments/workload_gen.py \
--mode multi \
--n-sessions 60 \
--turns-per-session 5 \
--out experiments/trace.csv
# Simula
./build/prefix_cache_sim \
--trace experiments/trace.csv \
--out results/run \
--strategy LFU \
--cache-max-pages 256
# Sweep completo
python3 experiments/sweep_cache_size.py
python3 plots/plot_metrics.py
Flags principais
Flag Default Descrição
--trace PATH — CSV de entrada (obrigatório)
--strategy STR LRU LRU · LFU · FIFO · SizeLRU
--cache-max-pages N 512 Máximo de páginas no prefix cache
--total-pages N 2048 Total de páginas físicas
--tokens-per-page N 16 Tokens por página de KV
--prefix-length N 128 Tamanho do system prompt compartilhado
--n-prefix-groups N 5 Número de prefixes distintos
--size-lru-alpha F 5.0 Peso do page_count no score do SizeLRU
--gpu-tflops F 312 TFLOPS da GPU (para custo de prefill)
--max-ticks N 50000 Duração máxima da simulação
Arquitetura
PageAllocator — pool de páginas físicas, free-list embaralhada
RadixTree — lookup exato e parcial de prefixes por token_id
└── PrefixNode — segmento de tokens + páginas KV + metadados LRU/LFU
IEvictionPolicy — interface de eviction (opera em folhas da RadixTree)
├── LRUEviction
├── LFUEviction
├── FIFOEviction
└── SizeLRUEviction — score = last_access + alpha × page_count
Simulator (tick loop) — arrivals → lookup → insert → decode → timeseries
Workload
# single-turn: requests independentes com prefixes compartilhados
python3 experiments/workload_gen.py --mode single \
--shared-prefix-ratio 0.55 --repeat-ratio 0.15
# multi-turn: sessões conversacionais (histórico acumulativo)
python3 experiments/workload_gen.py --mode multi \
--n-sessions 60 --turns-per-session 5
# mixed
python3 experiments/workload_gen.py --mode mixed \
--multi-fraction 0.7
Achados experimentais
1. Multi-turn vs Single-turn
Métrica Multi-turn Single-turn Ganho
Partial hit rate (cache saturado) 98.1% 76.1% 1.29×
Prefill saved total 211 ms 79.8 ms 2.64×
Cache para saturar ≥ 256 páginas ≥ 512 páginas 2× menos
Prefix caching é 2.6× mais efetivo em workloads multi-turn.
Cada turn reutiliza 100% do histórico dos turns anteriores.
2. Ranking de políticas (cache limitado)
LFU > LRU > FIFO ≥ SizeLRU(α=100) — regra geral
LFU > SizeLRU(α=5) > LRU — single-turn, cache médio
Política Melhor regime Pior regime
LFU qualquer cache limitado cache grande (empata)
LRU cache grande cache muito pequeno
FIFO sem overhead de tracking cache pequeno
SizeLRU(α=5) single-turn + cache médio single-turn + cache pequeno
3. SizeLRU: onde usar
Único regime onde SizeLRU supera LRU e LFU simultaneamente:
workload: single-turn
cache: ~256 páginas (intermediário)
alpha: 5
resultado: partial_hit_rate = 81.0%
vs LRU = 79.5% (+1.5 pp)
vs LFU = 77.2% (+3.8 pp)
Por que alpha=5 funciona aqui:
prompts single-turn têm tamanhos heterogêneos (8–32 páginas/nó).
Alpha=5 dá leve vantagem a nós pequenos (prefixes compartilhados curtos),
protegendo-os da eviction sem travar novas inserções.
Por que falha em multi-turn:
todos os nós crescem com o histórico — page_count fica similar entre nós.
Alpha não consegue discriminar; SizeLRU degenera para LRU.
Por que falha com cache pequeno:
alpha alto bloqueia a entrada de novos prefixes.
Hit rate cai monotonicamente com alpha crescente.
Recomendação:
Cenário Política
Workload desconhecido LFU
Multi-turn (qualquer cache) LFU
Single-turn, prompts variados, cache médio SizeLRU(α=5)
Cache grande, sem pressão de eviction qualquer uma
4. Sweep de alpha (SizeLRU)
Regime Melhor α PHR vs LRU vs LFU
multi-turn, c=64 200 86.6% +1.9 pp −5.6 pp
multi-turn, c=256 50 97.8% +0.4 pp −0.4 pp
multi-turn, c=2000 qualquer 98.1% 0 pp 0 pp
single-turn, c=64 0.1 53.4% −1.1 pp −29.1 pp
single-turn, c=256 5 81.0% +1.5 pp +3.7 pp
single-turn, c=2000 qualquer 76.1% 0 pp 0 pp
Alpha muito alto (≥50) destrói o hit rate em single-turn com cache pequeno.
Não existe alpha universalmente bom — tuning é necessário por workload.
Estrutura do repositório
prefix-cache-sim/
├── include/
│ ├── allocator.hpp PageAllocator (free-list embaralhada)
│ ├── block_table.hpp BlockTable (mapeamento lógico→físico)
│ ├── prefix_tree.hpp RadixTree + PrefixNode + PrefixLookupResult
│ ├── cache_policy.hpp IEvictionPolicy + LRU/LFU/FIFO/SizeLRU
│ └── simulator.hpp PrefixSimConfig, PrefixSimSummary, TimeSeriesRow
├── src/
│ ├── prefix_tree.cpp RadixTree: lookup, insert, split, evict
│ ├── simulator.cpp Tick loop: arrivals, admit, decode, timeseries
│ └── main.cpp CLI + load_trace + build_requests
├── experiments/
│ ├── workload_gen.py Gera traces: single/multi/mixed
│ ├── sweep_cache_size.py Sweep: 4 políticas × 7 cache sizes
│ ├── sweep_multi.py Sweep: multi vs single, 48 runs
│ └── sweep_alpha.py Sweep: 11 alphas × 3 caches × 2 modos
├── plots/
│ ├── plot_metrics.py Hit rate, Pareto, latência, tabela
│ ├── plot_alpha.py PHR vs alpha, heatmap, bar comparison
│ └── output/ PNGs gerados
├── scripts/
│ ├── analyze_cache.py Regimes + Pareto + LaTeX
│ ├── analyze_alpha.py Melhor alpha por regime + veredicto
│ └── compare_modes.py Multi vs single: ganho relativo
└── results/
├── sweep/ Resultados sweep_cache_size
├── sweep_multi/ Resultados sweep_multi
└── sweep_alpha/ Resultados sweep_alpha
Reprodução completa
# 1. Build
mkdir build && cd build && cmake .. -G Ninja && ninja && cd ..
# 2. Workloads
python3 experiments/workload_gen.py --mode single --n-requests 268 \
--shared-prefix-ratio 0.55 --repeat-ratio 0.15 \
--out experiments/trace_single.csv
python3 experiments/workload_gen.py --mode multi --n-sessions 60 \
--turns-per-session 5 --out experiments/trace_multi.csv
# 3. Sweeps
python3 experiments/sweep_cache_size.py
python3 experiments/sweep_multi.py
python3 experiments/sweep_alpha.py
# 4. Análise
python3 scripts/analyze_cache.py
python3 scripts/compare_modes.py
python3 scripts/analyze_alpha.py
# 5. Plots
python3 plots/plot_metrics.py
python3 plots/plot_alpha.py
Autor: João Felipe De Souza