대규모 Prefix Caching: Prefill 비용을 80% 절감하는 방법과 이득을 5%로 떨어뜨리는 Eviction 정책

당신의 챗봇은 8x H100에서 70B Llama를 배포합니다. 짧은 프롬프트에 대한 정상 상태(Steady-state) TTFT(Time To First Token)는 약 180ms이며, 팀은 이 정도면 만족합니다. 그러다 RAG(Retrieval-Augmented Generation) 기능을 켭니다. 이제 모든 요청은 검색된 문서들로 가득 찬 6,000토큰의 컨텍스트, 짧은 시스템 프롬프트, 그리고 사용자의 질문을 함께 보냅니다. TTFT는 1.4초로 급증합니다. p99는 2.1초에 달합니다. 놀랍게도 이 토큰들의 상당 부분은 모든 요청에서 동일한 것들입니다. 즉, 시스템 프롬프트, 상위 쿼리에 대해 동일한 6k 검색 청크(chunks), 도구 정의(tool definitions) 등입니다. 모델은 동일한 어텐션 상태(attention state)를 반복해서 재계산한 다음 버리고 있습니다. 이것이 Prefix Caching이 해결하는 문제입니다. 지난주 KV Cache 양자화(quantization)에 관한 포스트는 이를 다음 주제로 다루며 마무리되었습니다. 왜냐하면 이 두 기능은 상호 보완적이기 때문입니다. 양자화된 Prefix Cache는 BF16 방식보다 Warm 상태로 유지하는 비용이 더 저렴하며, 절약된 메모리를 통해 더 많은 동시 사용자(concurrent users)를 수용하거나 더 긴 공유 접두사(shared prefix)를 확보할 수 있습니다.

여기서 Prefix Caching이 실제로 무엇인지, vLLM과 SGLang이 이를 어떻게 다르게 구현하는지, 그리고 실제 운영 환경(production deployments)에서 어디서 이 이득을 조용히 잃게 되는지 설명하겠습니다.

이것이 실무에서 중요한 이유

현대적인 LLM 서빙 스택은 요청당 두 가지 단계가 있습니다: Prefill(KV Cache를 구축하기 위해 전체 프롬프트를 처리하는 단계)과 Decode(성장하는 캐시를 참조하며 한 번에 하나의 토큰을 생성하는 단계)입니다. 긴 컨텍스트(long-context) 워크로드의 경우, Prefill 단계가 지배적입니다. 8k의 입력을 가진 70B Llama-3의 경우, Prefill이 TTFT의 약 70~85%를 차지하며, Decode는 그에 비해 빠릅니다.

대부분의 "긴 입력" 워크로드는 실제로 매 요청마다 길고 고유하지 않습니다. 그것들은 길고 반복적입니다:

• RAG 파이프라인 (RAG pipelines). 동일한 검색된 청크 (chunks)가 동일한 상위 쿼리에 반복적으로 나타납니다. 시스템 프롬프트 (system prompt)와 도구 스키마 (tool schema)는 모든 요청에서 바이트 단위로 완전히 동일합니다. 사용자 질문만이 유일한 가변 부분이며, 그 크기는 매우 작습니다.
• 멀티턴 채팅 (Multi-turn chat). 각 턴은 이전 턴의 엄격한 접두사 확장 (prefix extension)입니다. 2라운드는 가장 최근의 어시스턴트 메시지와 새로운 사용자 턴을 제외한 모든 것을 공유합니다.
• 에이전트 루프 (Agent loops). 동일한 도구 스키마, 계획 프롬프트 (planning prompt), 그리고 퓨샷 예시 (few-shot examples)가 매 단계마다 앞에 붙습니다. 오직 가장 최근의 도구 결과만이 다릅니다.
• 긴 문서 QA (Long-document QA). 사용자들이 동일한 200페이지 분량의 PDF에 대해 반복적으로 질문합니다. 문서는 접두사 (prefix)이고, 질문은 접미사 (suffix)입니다.

Prefix caching (접두사 캐싱)은 다음과 같은 최적화 기법입니다: 만약 이 요청의 처음 N개 토큰이 이미 처리한 요청과 일치한다면, 이를 다시 계산하는 대신 해당 N개 토큰에 대한 KV 캐시 (KV cache)를 나에게 돌려달라. 교과서적인 사례에서 모델의 출력은 캐시를 사용하지 않았을 때와 비트 단위로 동일하지만

세 가지 사항이 중요합니다. 첫째, Prefix Caching (접두사 캐싱)은 **prefix-only (접두사 전용)**입니다. 즉, 앞부분의 토큰들만 건너뛸 수 있으며, 중간에 있는 부분 문자열(substring)은 절대 건너뛸 수 없습니다. 만약 두 요청이 10002000번 토큰을 공유하지만 0999번 토큰에서 서로 다르다면, 아무것도 재사용할 수 없습니다. 둘째, 캐시는 토큰 단위가 아닌 **block-grained (블록 단위)**입니다. 요청이 캐시 히트 (cache hit)를 얻으려면 전체 블록(기본값 16개 토큰)이 일치해야 합니다. 14,016개의 토큰을 공유하는 접두사에서 14,003번째 토큰에서 갈라지는 요청은 여전히 거의 모든 것을 다시 계산해야 합니다. 셋째, Prefix Caching은 decoding (디코딩)을 변경하지 않습니다. 절약된 모든 토큰은 절약된 prefill (프리필) 토큰입니다.

vLLM의 구현 방식: 해시 기반 블록

vLLM의 **Automatic Prefix Caching (APC, 자동 접두사 캐싱)**은 블록 기반이며 콘텐츠 주소 지정(content-addressed) 방식을 사용합니다. 각 KV 캐시 (KV-cache) 블록(기본 16개 토큰)은 세 가지 요소의 해시(hash)를 키로 사용합니다: 부모 블록의 해시, 블록 내의 토큰들, 그리고 LoRA 어댑터 ID, 멀티모달 입력 해시, 테넌트별 캐시 솔트(salt)를 위한 소수의 "추가 해시(extra hashes)"입니다.

블록 크기(block-size)의 선택은 대부분의 팀이 놓치는 핵심 레버(lever)입니다. 작은 블록(48개 토큰)은 더 세밀한 재사용을 가능하게 하여, 갈라지는 지점의 블록만 손실됩니다. 큰 블록(3264개 토큰)은 해시 테이블의 오버헤드를 줄이고 배칭 (batching)을 개선하지만, 부분 접두사 미스 (partial-prefix miss) 발생 시 더 많은 작업을 낭비하게 됩니다. 16개 토큰 기본값은 채팅용으로는 합리적인 중간 지점이며, 4k~8k 청크(chunk)를 사용하는 RAG (검색 증강 생성)의 경우 16 또는 32가 흔히 사용됩니다.

해시 함수는 v0.11 (2026년 4월)에서 보안 업그레이드가 이루어졌습니다. 그 전에는 직렬화된 블록에 대한 Python의 hash()를 기본값으로 사용했습니다. 이는 프로세스마다 무작위화되는 솔트 처리된 SipHash로, 충돌 방지에는 적합하지만 재시작 시 재현이 불가능했습니다. v0.22.1부터는 sha256이 기본값이며, 새로운 --prefix-caching-hash-algo CLI 플래그가 추가되었습니다:

알고리즘 (Algorithm)	해시 (Hash)	직렬화 (Serialization)	재현 가능성 (Reproducible)	비고 (Notes)
sha256	SHA-256	pickle	아니오	기본값. 보안상 안전하지만, pickle은 Python 버전에 민감함.
...

멀티 테넌트 (multi-tenant) 주의사항은 진지하게 받아들여야 할 부분입니다. 만약 하나의 엔진으로 여러 고객에게 서비스를 제공하고 있는데 해시 함수가 암호학적이지 않다면, 정교하게 조작된 프롬프트(prompt)를 통한 의도적인 충돌(collision)이 다른 테넌트의 캐시를 제거하거나, 심한 경우(pathological cases) 그들의 KV 블록을 공격자가 제어하는 값으로 대체할 수 있습니다. 만약 프롬프트를 직접 제어할 수 없다면, sha256 또는 sha256_cbor를 사용하십시오.

전형적인 vLLM 배포 방식은 서비스 시점에 APC를 활성화합니다:

vllm serve meta-llama/Meta-Llama-3-70B-Instruct \
  --tensor-parallel-size 8 \
  --enable-prefix-caching \
...

APC는 요청(per-request) 단위가 아닌 서버 수준의 결정입니다. 캐시는 공유 자원이기 때문에 이것이 맞습니다.

SGLang의 방식: 라딕스 트리 (radix tree)

SGLang은 캐싱된 접두사(prefix)들의 **라딕스 트리 (radix tree)**를 유지합니다. 각 노드는 하나 이상의 요청에 걸쳐 공유되는 접두사를 나타내며, 각 리프(leaf)는 요청별로 특화된 꼬리(tail) 부분입니다. 엔진은 요청마다 트리를 순회하며, 가장 길게 일치하는 접두사를 재사용하고, 요청이 갈라지는 지점에서 새로운 브랜치(branch)를 생성합니다.

실제 운영 환경에서 중요한 실질적인 차이점은 다음과 같습니다:

• 매칭 입도(granularity)가 블록 단위가 아닌 토큰 단위입니다. SGLang은 단 하나의 갈라지는 토큰까지 재사용합니다. 이는 프롬프트 중간에 변동(예: 삽입된 도구 결과)이 있는 대화형 워크로드에서 vLLM의 블록 단위 방식보다 더 많은 캐시를 회복합니다. 그 대가로 요청당 토큰 단위의 트리 순회(tree-walk) 오버헤드가 발생합니다.
• 제거(Eviction) 정책이 블록 단위가 아닌 노드 단위의 LRU입니다. 메모리 압박으로 인해 가지치기(prune)가 강제될 때, 가장 오래된(coldest) 노드 아래의 서브트리(subtree) 전체가 제거됩니다. 이는 vLLM의 블록 단위 LRU보다 빠르지만 더 거칠게(coarser) 작동합니다. 즉, 차가운 꼬리(cold tail)가 따뜻한 서브트리(warm subtree)를 함께 끌고 갈 수 있습니다.
• 멀티 LoRA (Multi-LoRA) / 멀티모달 (multimodal). SGLang은 리프에 요청별 메타데이터를 저장하므로, 서로 다른 LoRA 어댑터와 이미지 입력이 서로 다른 브랜치에 자연스럽게 위치합니다. vLLM은

대부분의 RAG 및 채팅 워크로드(workload)에서 두 구현 방식은 유사한 히트율(hit rate)을 제공합니다. SGLang은 많은 수의 짧은 공유 접두사(shared prefix)에서 승리하는 경향이 있으며(토큰별 매칭이 도움이 됨), vLLM은 매우 긴 공유 접두사에서 승리하는 경향이 있습니다(블록 해시 조회는 매우 작은 상수를 가진 O(1) 복잡도를 가짐).

실제 지표 수준에서 얻는 이득

워크로드	중간값 Prefill 절감량	TTFT 감소량	주의사항
6k 정적 컨텍스트를 사용하는 RAG	88–94%	70–85%	검색된 세트가 안정적이라면 히트율이 1.0에 근접함
...

히트율(Hit rate) — 요청이 도착했을 때 이미 캐시에 존재하는 블록의 비율 — 은 측정 시 가장 유용한 단일 수치입니다. 만약 APC를 활성화했는데 히트율이 30% 미만이라면 무언가 잘못된 것입니다. 접두사(prefix)가 일치하지 않거나, 재사용되기 전에 캐시가 축출(eviction)되고 있는 것입니다.

일반적인 함정

• 축출(Eviction)은 소리 없는 살인자입니다. vLLM은 GPU 메모리 압박이 있을 때 LRU(Least Recently Used) 방식으로 블록을 축출합니다. 긴 접두사와 짧은 접두사 트래픽이 섞여 있으면 종종 긴 접두사 블록이 먼저 축출됩니다(더 많은 슬롯을 차지하기 때문). 그리고 이 블록들이야말로 손실 시 실제로 타격이 큰 유일한 블록들입니다. --gpu-memory-utilization을 0.85에서 0.92로 높이면 캐싱된 접두사의 작업 세트(working set)가 일반적으로 두 배로 늘어납니다. 60초의 웜업(warmup) 이후의 캐시 히트율을 모니터링하십시오. 하루 동안 감소하는 비율은 워크로드의 문제가 아니라 축출 문제입니다.
• 솔트(salt)를 잊으면 LoRA와 멀티모달(multimodal)이 심하게 섞입니다. vLLM의 블록 해시는 LoRA ID와 이미지 해시를 포함합니다. 요청 시점에 어댑터를 교체하면 캐시 스래싱(cache thrash)이 발생합니다. 요청마다 달라지는 이미지 입력도 마찬가지입니다. 멀티모달 접두사를 캐싱하는 것은 본질적으로 무용지물입니다.
• 접두사 캐싱은 디코딩(decode)을 절약하지 못합니다. 대시보드에서 흔히 하는 실수는 전체 속도 향상의 공을 모두 APC 덕분으로 돌리는 것입니다. 디코딩 시간은 변하지 않습니다. 만약 워크로드가 디코딩 바운드(decode-bound)라면, APC는 거의 도움이 되지 않습니다.
• 해시 알고리즘 마이그레이션은 투명하게 이루어지지 않습니다. 배포 사이에 --prefix-caching-hash-algo를 변경하면, 새로운 엔진은 다시 웜업될 때까지 히트율이 0인 상태를 보게 됩니다. 일회성 비용이지만, 예상치 못한 상황에서는 실제 장애(incident)가 될 수 있습니다.

알고리즘을 Helm 차트에 포함시키세요.

• 복제본 간 캐시 공유(Cross-replica cache sharing)는 어렵습니다. vLLM의 APC는 GPU 메모리에 상주하며, 각 복제본(replica)은 자신만의 캐시를 가집니다. 콜드(cold) 상태인 복제본에 요청이 도달하면 전체 Prefill 비용을 지불해야 합니다. 분리형 아키텍처(Disaggregated architectures, vLLM v0.22의 kv_connector, SGLang의 DistServe)를 사용하면 프리픽스(prefix)가 일치하는 요청을 웜(warm) 상태의 복제본으로 라우팅할 수 있지만, 이를 위해서는 명시적인 설정이 필요합니다.
• "재시작 후 첫 번째 요청" 문제입니다. 롤링 배포(Rolling deploy)는 전체 캐시를 무효화합니다. 각 배포 후 첫 30~60초 동안은 Prefill에 의한 병목(prefill-bound) 현상이 발생합니다. 트래픽이 적은 시간대에 롤링 배포를 예약하거나, 합성 트래픽(synthetic-traffic) 사이드카를 사용하여 사전 웜업(pre-warm)을 수행하세요.

사용하지 말아야 할 때

다음과 같은 경우에는 Prefix caching이 잘못된 선택이거나(또는 낭비되는 플래그가 됩니다):

• 프롬프트에 공유되는 구조가 없는 경우. 개방형 완성(Open-ended completion) API, 요청마다 새로운 저장소에서 수행되는 코드 생성(code-gen), 시스템 프롬프트가 없는 단발성 Q&A 등은 재사용할 수 있는 것이 없습니다. 히트율(Hit rate)이 0에 가까워지며, 아무런 이득 없이 해시 테이블(hash-table) 오버헤드 비용만 지불하게 됩니다.

• 캐시 상태를 포함하는 엄격한 결정론적 SLO(Determinism SLO)를 준수해야 하는 경우. 동일한 모델과 동일한 프롬프트에 대해 캐시 히트(cache hit)와 캐시 미스(cache miss)는 동일한 출력을 생성하지만, 어텐션 커널(attention kernel)에서의 부동 소수점 반올림(float-rounding)으로 인해 극도로 깊은 층(extreme depths)에서 토큰이 달라질 수 있습니다. 요청 간에 비트 단위로 정확한 재현성(bit-exact reproducibility)이 필요하다면, APC를 비활성화하고 Prefill 비용을 감수하십시오.

• 작업 세트(working set)를 위한 GPU 메모리 예산을 충분히 확보할 수 없는 경우. 히트보다 미스가 더 많은 캐시는 캐시가 없는 것보다 나쁩니다. 재사용되지 않는 항목에 메모리를 소비하여 디코드 배치 크기(decode batch sizes)를 낮추기 때문입니다. 먼저 측정하고, 그 다음에 활성화하십시오.

• 트래픽의 대부분이 프롬프트 중간 삽입(mid-prompt insertions)으로 이루어진 경우. 에이전트 루프(Agent loops), 턴마다 이미지가 삽입되는 멀티모달 채팅, 동적 청크 재정렬(dynamic chunk re-ordering)이 포함된 RAG 등은 프롬프트 중간에 새로운 토큰을 빈번하게 삽입하여 프리픽스(prefix)를 깨뜨립니다. SGLang의 토큰 단위 매칭(per-token matching)이 이 상황에서 더 많은 것을 회복해주지만, 중간 삽입이 50% 이상인 워크로드의 경우 두 엔진 모두에서 히트율이 30% 미만으로 나타납니다.

• 이미 단일 거대 요청에 대해 Prefill 병목(prefill-bound) 상태입니다. 요청당 100k 토큰의 분석 패스(analysis pass)를 한 번에 하나씩 처리한다면, 첫 번째 호출에서는 100% 미스(miss)가 발생하고, 두 번째 호출이 발생한다 하더라도 100% 히트(hit)가 발생할 것입니다. 분할 상환된 이득(amortized win)은 해당 요청들이 반복되는지 여부에 전적으로 달려 있으며, 대부분의 일회성 분석 워크로드(one-shot analytics workloads)는 반복되지 않습니다.

요약 (TL;DR)

• **Prefix Caching (접두사 캐싱)**은 이전 요청이 이미 계산한 토큰들이 현재 요청의 앞부분에 있을 때, 해당 토큰들의 KV 캐시(KV cache)를 재사용합니다. 이는 Prefill 단계에만 영향을 미치며, Decode 단계는 변경되지 않습니다.
• **vLLM의 Automatic Prefix Caching (APC, 자동 접두사 캐싱)**은 콘텐츠 주소 지정 방식의 블록 저장소(content-addressed block store)입니다. 각 블록은 부모 해시(parent hash) + 블록 토큰 + LoRA/멀티모달/솔트(salt) 추가 정보에 의해 해싱됩니다. 기본 블록 크기는 16 토큰입니다. v0.22.1 버전부터 기본 해시 알고리즘은 SHA-256이며, --prefix-caching-hash-algo를 통해 sha256_cbor, xxhash, xxhash_cbor를 사용할 수 있습니다.
• **SGLang은 토큰 수준 접두사의 Radix Tree (기수 트리)**를 사용하며, 이는 요청당 트리 탐색(tree-walk) 오버헤드를 대가로 더 세밀한 매칭(finer-grained matching)을 제공합니다.
• 이득은 실재하지만 워크로드의 형태에 따라 다릅니다. 안정적인 검색 세트를 사용하는 RAG(검색 증강 생성)의 경우: Prefill 비용의 8894% 절감. 멀티턴 채팅(Multi-turn chat): 평균 6080% 절감. 개방형 질의응답(Open-ended Q&A): 0~5% 절감. 마케팅 수치를 신뢰하기 전에 반드시 히트율(hit rate)을 직접 측정하십시오.
• Eviction (방출)은 소리 없는 살인자입니다. 메모리 압박이 발생하면 긴 접두사(long-prefix) 블록이 가장 먼저 방출됩니다. 캐시 예산을 명시적으로 설정하고, 시작 시점뿐만 아니라 하루 동안의 히트율을 모니터링하십시오.
• 개방형 워크로드, 비암호화 해시를 사용하는 멀티 테넌트(multi-tenant) 엔진, 또는 작업 세트(working-set) 메모리를 감당할 수 없는 경우에는 이를 활성화하지 마십시오. 먼저 측정부터 하십시오.