95편 · 약 14분

PEEK: 대기 큐를 미리 보고 KV 캐시를 예약하는 LLM 서빙 최적화 (arXiv 2025.07)

요약

LLM 서빙 엔진의 KV 캐시는 이미 완료된 요청이 남긴 흔적만 재사용한다. 새 요청이 도착하면 캐시를 확인하지만, 그 시점에 필요한 블록이 이미 퇴거(evict)됐거나 아직 채워지지 않은 상태일 수 있다.

2025년 7월 arXiv에 공개된 PEEK (arXiv:2607.02525)는 발상을 뒤집는다. 캐시를 과거가 아니라 대기 큐에 있는 미래 요청을 기준으로 관리한다.

핵심 아이디어:

아직 처리 전인 대기 큐 전체를 Radix Tree로 구성해 프리픽스 공유 클러스터를 미리 파악한다.
공유 클러스터를 인식한 채로 Admission(입장)과 Eviction(퇴거)을 결정하므로, 캐시는 "곧 가장 많이 쓰일 블록"을 우선 보유한다.
SGLang과 vLLM 실험에서 기존 대비 캐시 히트율 최대 3.0×, TTFT 최대 7.9× 감소.

문제: 캐시가 항상 뒤를 돌아보는 이유

기존 캐시 흐름

SGLang RadixAttention, vLLM prefix caching은 모두 동일한 구조다.

요청이 도착한다.
캐시에서 LPM(Longest Prefix Match)을 조회한다.
히트하면 해당 KV 블록을 재사용, 미스면 새로 계산한다.
계산이 끝난 KV 블록을 캐시에 저장한다.

이 흐름에서 캐시 상태는 이미 처리가 끝난 요청들의 누적이다. 미래를 볼 수 없으므로, 자주 쓰일 블록이 퇴거된 뒤에 또 다른 요청이 와서 캐시 미스가 반복된다.

왜 미스가 많은가

프리픽스 공유 요청의 시간적 집중. 실제 워크로드에서 같은 시스템 프롬프트를 공유하는 요청은 거의 동시에 쏟아진다. 배치 처리 시작 직후, 사용자 트래픽이 급증하는 순간 등이 그렇다. 이 순간 큐에는 동일 프리픽스를 가진 수십~수백 개의 요청이 대기 중이지만, 캐시는 첫 번째 요청이 끝나기 전까지 해당 블록을 갖지 못한다. 결국 첫 번째 요청만 히트 기회를 얻고 나머지는 모두 미스한다.

기존 방식: 과거 기반 캐시

완료된 요청 KV 블록
LRU/LFU 정책으로 보유

↓ 새 요청 도착 시 조회

LPM 조회 → 히트/미스
미스: 재계산 후 저장

↔ 비교

PEEK: 미래(대기 큐) 기반 캐시

대기 큐 전체를 Radix Tree로
프리픽스 공유 클러스터 식별

↓ 클러스터 기반 Admission/Eviction

곧 가장 많이 쓰일 블록 우선 보유
Pioneer 처리 → 형제 요청 히트

기존 캐시 vs PEEK 캐시 관리 관점 비교

PEEK 핵심 설계

1. 큐 인덱스: Radix Tree over Pending Queue

PEEK는 GPU 연산 루프와 독립적으로 대기 큐 전체를 증분식 Radix Tree로 구성한다. Radix Tree는 공통 접두사를 공유하는 노드를 병합하므로, 같은 프리픽스를 가진 요청들이 자동으로 하나의 클러스터로 묶인다.

동작 방식:

새 요청이 큐에 추가될 때마다 Tree에 삽입 → O(프리픽스 길이) 비용.
요청이 스케줄되거나 취소되면 Tree에서 제거.
Tree는 어느 노드(프리픽스 범위)가 몇 개의 요청을 공유하는지 실시간으로 파악한다.

2. Dual-Walk 매칭

요청 스케줄 직전, PEEK는 두 Radix Tree를 병렬로 탐색한다.

큐 트리: 현재 대기 요청들의 구조.
캐시 트리: 현재 KV 캐시에 있는 블록 구조.

두 트리를 동시에 내려가며 Longest Common Prefix Match를 계산한다. 이 과정에서 "큐에 있지만 캐시에 없는" 프리픽스 구간을 파악해 Admission 우선순위를 결정한다.

3. 클러스터 인식 Admission

캐시에 새 블록을 넣을 때, PEEK는 단순 LRU/LFU 대신 큐 트리에서의 참조 횟수를 기준으로 우선순위를 정한다.

큐 트리에서 많은 요청이 공유하는 프리픽스 노드는 높은 우선순위.
"Pioneer" 전략: 클러스터 첫 번째 요청(Pioneer)을 GPU에서 계산하는 동안 해당 KV 블록을 캐시에 확보해 두고, 뒤따라오는 형제 요청들이 모두 히트하도록 보장.
Pioneer가 계산 중일 때 동일 프리픽스의 형제 요청들은 스케줄을 잠시 늦추어(아주 짧은 대기) 캐시 블록이 완성된 직후 히트 상태로 실행된다.

4. Eviction Hook: 쫓아내지 말아야 할 블록 보호

기존 퇴거 정책(LRU/FIFO)은 캐시 공간이 부족하면 가장 오래된 블록을 쫓아낸다. 문제는 그 블록이 큐에서 곧 필요한 경우다.

PEEK의 Eviction Hook은 퇴거 대상 블록을 큐 트리와 조회한다.

큐에서 아직 참조 요청이 남아 있는 블록은 퇴거 금지 목록에 추가.
퇴거 금지 블록이 너무 많으면 Pioneer 대기 전략을 조정해 캐시 압박을 완화.
이 메커니즘으로 "계산해서 넣었더니 바로 쫓겨나는" 낭비 사이클을 제거.

5. 멀티레인 Stride 스케줄러

클러스터 인식 스케줄링만 하면 인기 프리픽스가 항상 우선 처리되어 다른 요청이 굶어(starvation) 죽는다. PEEK는 이를 막기 위해 멀티레인 Stride 스케줄러를 사용한다.

각 클러스터는 자체 "레인"을 가진다.
Stride 알고리즘이 레인마다 처리 할당량을 비례적으로 부여해 공정성을 보장.
인기 클러스터는 더 많은 할당량을 받지만 독점하지 않는다.

구현: Rust 코어 + Python 셰임

PEEK의 Radix Tree 연산 코어는 Rust로 구현되어 있다. Python GIL의 영향을 받지 않고 백그라운드 스레드에서 큐 트리를 유지할 수 있다.

서빙 엔진 연동은 Python 셰임(shim) 약 800줄 수준이다.

SGLang 연동: scheduler.py 패치 포인트 3곳.
vLLM 연동: block_manager.py + scheduler.py 패치.
두 경우 모두 엔진 내부를 크게 수정하지 않고 후킹(hooking) 방식으로 통합.

서빙 엔진 (SGLang / vLLM)

요청 수신 → 대기 큐

↓ shim hook

PEEK 큐 트리 갱신 (Rust)
증분 Radix Tree 삽입/삭제

↓ Dual-Walk 매칭

PEEK 의사결정 레이어

Cluster-aware Admission
Pioneer 선택 + 형제 대기

Eviction Hook
큐 참조 블록 보호

Stride Scheduler
레인별 공정 할당

↓ 스케줄 결정

GPU 실행

Pioneer 계산 → KV 블록 캐시 적재
형제 요청 → 캐시 히트 실행

PEEK 시스템 구성도

성능 결과

SGLang과 vLLM 각각에 통합한 실험 결과:

지표	SGLang 기준 향상	vLLM 기준 향상
KV 캐시 히트율	3.0×	2.6×
TTFT (Time-To-First-Token)	7.9× 감소	7.1× 감소
E2E 요청 지연	6.7× 감소	5.5× 감소
처리량 (req/s)	3.6×	4.5×

워크로드 조건: 프리픽스 공유율이 높은 워크로드(공통 시스템 프롬프트, RAG 공유 문서)에서 효과가 최대화된다. 완전히 랜덤한 프롬프트 패턴에서는 개선 폭이 작다.

왜 TTFT 개선이 처리량 개선보다 큰가

TTFT는 캐시 히트 여부에 직접 영향을 받는다. 히트하면 수십만 토큰 어텐션 계산을 건너뛰므로 TTFT가 수초에서 수십 밀리초로 줄 수 있다. 반면 처리량은 GPU 포화 상태에서 결정되므로 히트율 개선이 처리량에 미치는 영향은 상대적으로 작다.

DualMap과 PEEK: 두 최적화의 관계

DualMap(ai-frontier/94)은 라우팅 계층에서 캐시 어피니티와 부하 분산을 동시에 해결한다. PEEK는 엔진 내부 캐시 관리 계층에서 퇴거와 입장을 최적화한다.

두 기술은 역할이 다르다.

DualMap: 같은 프리픽스 요청을 어느 인스턴스로 보낼지 결정.
PEEK: 인스턴스 안에서 어떤 KV 블록을 캐시에 유지할지 결정.

이론적으로 DualMap 라우팅 위에 PEEK 엔진을 올리면 두 효과가 겹쳐 더 높은 개선을 기대할 수 있다. 실제 조합 실험은 아직 공개되지 않았다.

운영 체크리스트

[ ] 큐 트리 메모리 예산 설정: 대기 큐가 수천 개 요청으로 채워질 경우 Radix Tree 메모리 사용량 측정 (실제 서비스 피크 큐 깊이 기준으로 사전 벤치마크 권장)
[ ] Pioneer 대기 시간 임계값 설정: 형제 요청 대기 시간이 SLO를 초과하지 않도록 max_sibling_wait_ms 값을 SLO의 10% 이내로 설정
[ ] 프리픽스 공유율 측정: PEEK 도입 전 기존 엔진의 KV 히트율 메트릭으로 개선 여지 파악 (히트율이 이미 90% 이상이면 효과 미미)
[ ] SGLang vs vLLM 결정: 두 엔진 중 하나를 선택한 후 해당 셰임 적용 (현재 두 엔진 동시 지원이나 크로스 엔진 실험은 아직 없음)
[ ] Eviction Hook 충돌 확인: 기존 커스텀 퇴거 정책이 있다면 PEEK Hook과 우선순위 충돌 여부 점검
[ ] Stride 레인 수 설정: 동시에 서비스하는 프리픽스 클러스터 수가 많을 경우 레인 수를 늘려 스케줄러 오버헤드 확인
[ ] A/B 실험 설계: KV 히트율, TTFT P99, E2E 지연, 처리량 4가지 지표로 기존 방식과 비교 (워크로드 재현성 확보 필수)

요점 정리

KV 캐시를 과거(완료된 요청)가 아니라 미래(대기 큐)를 기준으로 관리하면 프리픽스 공유 클러스터를 미리 인식할 수 있다.
PEEK는 증분 Radix Tree로 큐를 색인하고, Dual-Walk 매칭으로 캐시와 큐를 동시에 탐색해 Pioneer 전략과 Eviction Hook을 결합한다.
Rust 코어 + Python 셰임 약 800줄로 SGLang/vLLM 모두에 최소 수정으로 통합 가능하다.
프리픽스 공유율이 높은 워크로드에서 캐시 히트율 3.0×, TTFT 7.9× 감소.

References

PEEK 논문 (arXiv:2607.02525): https://arxiv.org/abs/2607.02525
SGLang RadixAttention 설계: https://lmsys.org/blog/2024-01-17-sglang/
vLLM prefix caching 문서: https://docs.vllm.ai/en/stable/design/prefix_caching/
Power of Two Choices (Mitzenmacher 2001): https://www.eecs.harvard.edu/~michaelm/postscripts/tpds2001.pdf
DualMap (arXiv:2602.06502, ICLR 2026): https://arxiv.org/abs/2602.06502