LLM WikiAccess-protected knowledge portal

WIKI

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

요약 LLM 서빙 엔진의 KV 캐시는 이미 완료된 요청 이 남긴 흔적만 재사용한다. 새 요청이 도착하면 캐시를 확인하지만, 그 시점에 필요한 블록이 이미 퇴거 evict 됐거나 아직 채워지지 않은 상태일 수 있다. 2025년 7월 arXiv에 공개된 PEEK arXiv 2607.02525 는 발상을 뒤집는다. 캐시를 과거 가 아니라 대기 큐에 있는 미래 요청 을 기준으로 관리한다. 핵심 아이디어 아직 처리 전인 대기 큐 전체

경로human/study/content/ai-frontier/95-peek-predictive-queue-kv-cache-management-llm-serving.md
카테고리Study
태그#ai-review #cache #llm #management #queue #serving #study

요약

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

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

핵심 아이디어:

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

기존 캐시 흐름

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

  1. 요청이 도착한다.
  2. 캐시에서 LPM(Longest Prefix Match)을 조회한다.
  3. 히트하면 해당 KV 블록을 재사용, 미스면 새로 계산한다.
  4. 계산이 끝난 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는 공통 접두사를 공유하는 노드를 병합하므로, 같은 프리픽스를 가진 요청들이 자동으로 하나의 클러스터로 묶인다.

동작 방식:

2. Dual-Walk 매칭

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

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

3. 클러스터 인식 Admission

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

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

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

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

5. 멀티레인 Stride 스케줄러

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

구현: Rust 코어 + Python 셰임

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

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

서빙 엔진 (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 엔진을 올리면 두 효과가 겹쳐 더 높은 개선을 기대할 수 있다. 실제 조합 실험은 아직 공개되지 않았다.

운영 체크리스트

요점 정리

References