GPU HBM이 꽉 차면 선택지는 두 가지뿐이다. 들어오는 요청을 거절하거나, 기존에 캐싱된 KV 블록을 버린다. 전자는 가용성 문제고, 후자는 재계산 비용 문제다. Eviction은 이 상황에서 무엇을 버릴지 결정하는 정책인데, 별 고민 없이 디폴트 LRU를 쓰고 넘어가는 팀이 많다.
LRU가 LLM 서빙에서 한계에 부딪히는 지점이 있다. prefix sharing 환경에서는 "가장 오래 안 쓴 것"이 "버려도 가장 덜 아픈 것"과 다른 경우가 빈번하다. 그리고 히트율을 끌어올리기 위해 eviction을 아끼다 보면, p99 TTFT가 반대 방향으로 치솟는 역설이 나타난다.
Eviction이 시작되는 조건
KV 캐시가 차지하는 메모리는 직접 계산해보면 생각보다 크다. FP16 기준으로 단일 토큰의 KV 캐시 크기는:
2 × num_layers × num_kv_heads × head_dim × 2 bytes
LLaMA-3 70B(80 레이어, GQA 8개 KV head, head_dim 128) 기준으로 토큰당 약 0.32 MB다. 64K 컨텍스트 요청 하나가 캐시에 올라가면 약 20 GB를 점유한다. A100 80GB에서 모델 웨이트가 35~40 GB를 이미 잡고 있으니, 64K 요청 두 개만 들어와도 KV 캐시 공간은 한계에 달한다. 실제 배치에서 eviction은 이보다 훨씬 일찍 시작된다. 더 짧은 컨텍스트 요청 수십 개가 동시에 처리되고 있으면 HBM 여유분은 금방 사라진다.
vLLM에서는 vllm:gpu_cache_usage_perc가 90%를 넘으면서 vllm:num_requests_waiting이 0이 아닌 상태가 지속되면, eviction이 직접 latency를 만들어내고 있다는 신호다.
재계산 비용이 이차적으로 늘어난다
버린 KV 블록은 다음 요청이 해당 prefix를 필요로 할 때 다시 계산해야 한다. 이 비용이 선형이었다면 eviction 정책의 중요성이 지금처럼 크지 않을 것이다. 문제는 prefill 연산이 비선형이라는 데 있다.
트랜스포머 prefill 단계의 FLOPs는 크게 두 부분으로 나뉜다. 선형 projection(Q, K, V, output 연산) 부분은 시퀀스 길이 L에 비례하지만, attention 연산은 레이어당 아래 수식으로 계산된다:
(1/2) × 4 × L² × (num_heads × head_dim)
컨텍스트가 4K → 16K로 4배 늘면 attention 비용만 16배 뛴다. 4K → 64K면 256배다. 전체 prefill 비용은 그 사이 어딘가지만, 컨텍스트가 길어질수록 이차 항이 지배적이 된다. 이 스케일링은 FlashAttention을 써도 달라지지 않는다. FlashAttention은 메모리 접근 패턴을 최적화할 뿐, FLOPs 복잡도 자체는 여전히 O(L²)다.
64K 컨텍스트 서빙 시스템에서 eviction 정책이 잘못 설계되면, 캐시 미스 한 번이 수 초짜리 TTFT 페널티로 돌아온다. p50 TTFT를 개선하기 위해 캐시를 쌓아뒀는데 캐시 미스가 나는 순간 그 요청의 TTFT가 수십 배로 치솟는 상황이 여기서 생긴다.
정책 비교: LRU, prefix-aware LRU, Radix Tree
기본 LRU
가장 오래 접근하지 않은 블록을 먼저 버린다. 구현이 단순하고 일반적인 캐시 워크로드에는 잘 맞는다. LLM 서빙에서 문제가 생기는 건 prefix sharing 때문이다. 여러 요청이 공유하는 시스템 프롬프트 prefix를 "마지막으로 접근한 시점이 오래됐다"는 이유만으로 먼저 버리면, 이후 모든 요청이 그 prefix를 재계산해야 한다. 가장 많이 재사용되는 블록이 먼저 사라지는 역설이다.
vLLM prefix-aware LRU
vLLM은 블록을 해제할 때 큐에 추가하는 순서를 뒤집는다. 한 요청이 완료되면 그 요청의 KV 블록들을 역순(suffix부터)으로 큐에 집어넣는다. "나중 블록일수록 재사용 가능성이 낮다"는 관찰을 eviction 순서에 반영한 것이다. 같은 접근 시점의 블록이 여럿 있을 때는 prefix 체인이 가장 긴 것, 즉 트리에서 가장 깊은 리프 노드를 먼저 버린다.
vLLM 공식 문서는 이 동작이 full attention 모델에서 SGLang의 RadixAttention 정책과 동일한 결과를 낸다고 명시한다.
SGLang Radix Tree eviction (Leaf-LRU)
Zheng et al. (arXiv:2312.07104)의 RadixAttention은 KV 캐시를 라딕스 트리로 관리한다. 트리 구조는 CPU 위에, 실제 KV 텐서는 GPU paged layout에 유지하면서, eviction 시에는 리프 노드 중 LRU를 먼저 버린다.
리프 노드는 자식이 없는 노드, 즉 다른 요청이 자신을 prefix로 공유하지 않는 노드다. 10개 요청이 공유하는 시스템 프롬프트 prefix는 트리에서 깊은 내부 노드가 되고, 단일 세션의 뒷부분(suffix)은 리프로 남는다. 메모리가 부족할 때 버려지는 건 항상 리프 먼저다. "접근 시점"이 아니라 "공유 여부"가 eviction 기준에 자동으로 들어가는 구조다.
동작을 단순화하면:
def evict(tree, required_blocks):
freed = 0
while freed < required_blocks:
# 현재 사용 중이지 않은(ref_count == 0) 리프 노드 중 가장 오래된 것
candidates = [n for n in tree.leaf_nodes() if n.ref_count == 0]
if not candidates:
break
node = min(candidates, key=lambda n: n.last_access_time)
tree.remove(node)
free_blocks(node.kv_blocks)
freed += node.num_blocks
LMSYS 블로그 벤치마크에서 RadixAttention은 동일 설정 대비 처리량을 최대 5배 높였다.
LFU와 비용 기반 정책
LFU(Least Frequently Used)는 접근 빈도가 낮은 블록을 먼저 버린다. 새로 들어온 prefix는 빈도가 낮을 수밖에 없어 초기에 불리하다. vLLM 커뮤니티에는 freq × compute_cost를 보존 가치로 계산하는 방식의 RFC #23641이 제안되기도 했지만, 구현 복잡도 대비 효과가 불명확하다는 이유로 닫혔다.
히트율을 높이면 꼬리 latency가 길어지는 이유
eviction을 아끼면 히트율이 올라가고 p50 TTFT는 줄어든다. 그런데 p99 TTFT는 반대로 늘어날 수 있다.
메커니즘은 이렇다. 캐시에 오래된 블록을 많이 보존하면 free block pool이 줄어든다. 이 상태에서 burst 요청이 들어오면 스케줄러가 새 요청에 KV 블록을 할당하지 못하고, 기존 요청을 선제 중단(preemption)하거나 신규 요청을 큐에 세운다. 이 순간 일부 요청의 TTFT가 크게 늘어난다. p50은 낮은데 p99가 높아지는 전형적인 분포다.
T-LRU RFC에서 보고된 수치가 이 관계를 구체적으로 보여준다. T-LRU는 기본 LRU 대비 P95 TTFT를 최대 27.4% 낮췄는데, 클리반트(clairvoyant) 오프라인 최적 대비 성능 격차의 25~79%를 줄였다고 보고한다. T-LRU는 TTFT SLO를 위반하지 않을 블록(TEL-safe)을 먼저 버리고, 위반할 블록(TEL-unsafe)은 보존하는 dual-queue 설계다. 히트율을 최대화하는 대신 꼬리 latency를 제한하는 방향으로 eviction aggressiveness를 조절한다.
이 트레이드오프를 SLO 없이 조절하는 건 사실상 불가능하다. "p99 TTFT < 2초"같은 목표가 먼저 정의돼야 eviction 정책의 공격성을 얼마나 높일지 결정할 수 있다. SLO 없이 히트율만 보다가 p99가 망가진 뒤에야 알아채는 경우가 실제로 많다.
요청 패턴과 정책 선택
| 트래픽 패턴 | 추천 정책 | 이유 |
|---|---|---|
| RAG / 고정 system prompt | Radix Tree Leaf-LRU | 공유 prefix 자동 보호 |
| Multi-turn chat | Prefix-aware LRU / T-LRU | 세션별 보존 임계값 |
| Open-ended Q&A | 정책 무관 | prefix sharing 없음 |
| 혼합 트래픽 | KV pool 분리 + 정책 조합 | 단일 정책으로 커버 불가 |
공유 prefix 비율이 높을수록 Radix Tree 기반 eviction의 효과가 크다. PGDSF 연구에서는 prefix-aware 정책이 동일 트래픽에서 기본 LRU 대비 히트율을 1.06~1.62배 기록했다. 반대로 open-ended Q&A처럼 prefix sharing이 없는 워크로드에서는 어떤 eviction 정책을 써도 히트율 차이가 거의 없다.
특정 워크로드에서 측정한 히트율이나 정책 효과를 다른 워크로드에 그대로 적용하면 오히려 성능이 나빠질 수 있다. RAG 트래픽 80%에서 튜닝한 aggressive eviction 설정을 open-ended 요청이 섞이는 환경에 가져가면, 공유 prefix가 없는데 eviction을 아껴서 free block pool만 줄이는 결과가 된다.
운영에서 Eviction 진단하기
vLLM이 노출하는 Prometheus 메트릭 중 eviction 진단에 직접 쓸 수 있는 것들:
# KV cache 사용률. 90% 이상이면 eviction 압박 구간
vllm:gpu_cache_usage_perc
# 누적 preemption 수. rate()로 보면 eviction 빈도를 실시간으로 확인
vllm:num_preemptions_total
# GPU / CPU prefix 캐시 히트율
vllm:gpu_prefix_cache_hit_rate
vllm:cpu_prefix_cache_hit_rate
gpu_cache_usage_perc가 90%를 넘으면서 num_preemptions_total rate가 함께 올라가는 시점이 eviction이 latency를 직접 만들어내는 구간이다. 이 두 지표를 함께 보지 않으면 히트율이 높은데 왜 p99가 나쁜지 원인을 잡기 어렵다.
히트율은 높은데 preemption rate도 올라가고 있다면, eviction aggressiveness를 높여 free block pool을 확보하거나 SLO 기준으로 eviction 우선순위를 재정의해야 한다. 둘 다 하지 않으면 히트율과 꼬리 latency가 반대로 움직이는 상태를 방치하는 것이다.