LLM 서빙 프롬프트 캐싱(Prefix Caching) 아키텍처 해부: vLLM 블록 해시 체인 vs SGLang RadixTree·LRU 메모리 방출과 TTFT 90% 단축

LLM 프롬프트 캐싱(Prefix Caching)의 블록 해시 체인 연쇄와 Radix Tree 공통 접두사 분기 흐름을 상징하는 기하학적 추상 아트워크. 실제 코드나 다이어그램 화면이 아니다.

대규모 언어 모델(LLM)을 활용한 서비스가 단발성 질의응답을 넘어 멀티턴(Multi-turn) 대화, 수천 줄의 시스템 프롬프트 및 도구 정의(Tool Calling)를 동반하는 에이전트(Agentic Workflow), 초장문 RAG(검색 증강 생성) 파이프라인으로 진화하면서 추론 서빙 인프라의 핵심 화두는 중복 프롬프트의 프리필(Prefill) 연산 낭비와 초기 응답 지연(Time-to-First-Token, TTFT) 해소로 집중되고 있다 (vLLM Documentation, SGLang Paper: Fast and Expressive LLM Serving with RadixAttention). 트랜스포머 아키텍처에서 새로운 요청이 들어올 때마다 과거 대화나 시스템 프롬프트 전체에 대해 고차원 Key-Value(KV) 행렬곱을 처음부터 다시 계산하는 것은 막대한 GPU 연산 유닛(FLOPs)과 HBM 쓰기 대역폭을 낭비시킨다. 이를 극복하기 위해 등장한 혁신이 바로 이전 요청에서 이미 계산된 KV 텐서를 재사용하는 프롬프트 캐싱 (Prefix Caching / Prompt Caching)이다.

핵심 판단 기준을 먼저 요약하면, Prefix Caching은 이전 요청에서 생성된 KV 텐서를 재계산 없이 재사용하여 중복 프리필 연산을 생략함으로써 TTFT를 최대 70~90% 단축하고 서빙 처리량(Throughput)을 2~4배 끌어올린다. 구현 방식에 따라 두 진영으로 나뉘는데, vLLM은 PagedAttention의 비연속 물리 블록 구조 위에서 이전 블록 해시를 체이닝하는 암호학적 블록 해시 체인( $H_n = \text{Hash}(H_{n-1} \parallel \text{Tokens})$ )과 전역 해시 테이블 기반의 Automatic Prefix Caching(APC)을 택해 포인터 오버헤드 없이 멀티모달 및 Multi-LoRA 격리를 자연스럽게 지원한다. 반면 SGLang은 메모리 내에 가변 길이 토큰 시퀀스를 간선(Edge)으로 보관하는 압축 트라이 구조인 Radix Tree(RadixAttention)를 구축하여, 임의 길이의 공통 접두사 탐색과 동적 노드 분할(Node Split)을 O(Prefix Length) 시간에 처리함으로써 복잡한 분기형 에이전트 및 Few-Shot 워크플로에서 극대화된 캐시 적중률을 달성한다. 양측 모두 요청이 끝나도 KV 블록을 즉시 파기하지 않고 Reference Count가 0인 상태로 캐시 풀에 보관하다가, 메모리 한계 시에만 가장 오래된 블록을 방출하는 OS 스타일 LRU(Least Recently Used) 생명주기와 CoW(Copy-on-Write) 블록 격리 불변식을 보장한다. 이 글은 vLLM 공식 소스코드와 SGLang 공식 논문/커널 명세를 바탕으로 정리한 글이며, 로컬 Python 6대 알고리즘 및 런타임 불변식 검증을 기준으로 설명한다.

1. vLLM APC vs SGLang RadixAttention 한눈에 보기

대표적인 두 고성능 추론 엔진인 vLLM과 SGLang의 Prefix Caching 아키텍처 특성 차이는 아래 표와 같다 (vLLM Automatic Prefix Caching, SGLang RadixAttention).

비교 항목	vLLM Automatic Prefix Caching (APC)	SGLang RadixAttention	실무 영향 및 아키텍처 차이
핵심 자료구조	전역 해시 테이블 + 블록 해시 체인	압축 트라이 (Radix Tree)	vLLM은 O(1) 테이블 매핑, SGLang은 접두사 트리 경로 탐색
캐시 기본 단위	고정 크기 블록 (기본 16 또는 32 토큰)	가변 길이 토큰 슬라이스 (Edge Label)	vLLM은 PagedAttention 물리 블록 단위로만 매칭, SGLang은 토큰 단위 임의 분할
접두사 일치 판별	$H_n = \text{Hash}(H_{n-1} \parallel T_n)$ 연쇄 해시	루트부터 자식 노드 간선 토큰 직접 매칭	vLLM은 이전 블록 의존성으로 충돌 방지, SGLang은 노드 분할(Split)로 공통 분기 생성
메모리 관리 방식	Paged Block Manager + Free/Cache Pool	Tree Node 기반 계층적 LRU 풀	둘 다 Ref=0 블록을 즉시 해제하지 않고 캐시 풀에 보존
메모리 방출(Eviction)	Ref=0 블록 중 전역 LRU 정책 적용	참조 없는 Leaf 노드부터 상향식 LRU 해제	메모리 부족 시 활성 요청(Ref > 0)을 보호하면서 가장 오래된 캐시 회수
Multi-LoRA / 멀티모달	블록 해시에 LoRA ID 및 이미지 해시 솔팅	트리 탐색 시 어댑터/모달리티 조건 분기	vLLM은 해시 입력에 식별자를 추가하여 캐시 오염을 손쉽게 차단
적합한 워크플로	표준 챗봇, RAG, 멀티턴 세션, 대규모 배치	Agent 도구 호출, Few-Shot 다중 분기, Tree-of-Thought	구조화된 분기 트리가 많을수록 Radix Tree의 미세 노드 공유 효과가 두드러짐

2. Prefix Caching의 5가지 핵심 기술 경계와 동작 원리

Prefix Caching이 단순한 문자열 메모이제이션을 넘어, GPU 고대역폭 메모리 위에서 정확하고 안전하게 동작하는 5가지 핵심 원리는 다음과 같다:

LLM 서빙 프롬프트 캐싱(Prefix Caching) 내부 아키텍처 비교 다이어그램: vLLM 블록 해시 체인 vs SGLang RadixTree 및 LRU 캐시 풀 생명주기

블록 해시 체이닝(Block Hash Chaining)을 통한 컨텍스트 무결성 보장: 만약 단순히 개별 16개 토큰의 내용만으로 해시를 생성한다면, 서로 다른 맥락에서 우연히 동일한 16개 단어가 등장했을 때 이전 컨텍스트의 잘못된 KV 캐시를 참조하는 치명적인 캐시 충돌(Cache Collision)이 발생한다. vLLM은 이를 방지하기 위해 블록 해시 $H_n$ 을 계산할 때 현재 블록의 토큰 ID뿐만 아니라 직전 블록의 해시 $H_{n-1}$ 을 필수 입력값으로 결합하는 블록체인형 해시 연쇄 구조를 채택한다 (vLLM Issue #5633). 이를 통해 프롬프트의 전체 경로가 완벽히 일치할 때만 캐시 히트가 발생하도록 수학적 불변식을 성립시킨다.

Radix Tree의 동적 노드 분할(Dynamic Node Splitting): SGLang의 RadixAttention은 토큰 시퀀스를 간선(Edge) 레이블로 갖는 압축 트라이를 사용한다. 새로운 요청이 들어왔을 때 기존에 저장된 간선의 토큰 시퀀스와 앞부분 $K$ 개만 일치하고 뒷부분이 달라지는 분기가 발생하면, 기존 노드를 $K$ 번째 위치에서 즉시 2개의 하위 노드로 분할(Split)한다. 앞부분의 공통 KV 텐서는 그대로 공유되고, 뒷부분의 서로 다른 토큰만 새로운 가지(Branch)로 뻗어나가므로, 트리 탐색(Tree-of-Thought)이나 멀티 브랜치 에이전트 환경에서 단 1개의 토큰도 낭비하지 않고 공통 프리픽스를 재사용한다 (SGLang Paper).

OS Page Cache 스타일의 Reference Counting과 LRU Eviction Pool: 사용자의 요청 디코딩이 완료되어 HTTP 응답이 전송되었을 때, 해당 세션이 점유하던 물리 GPU 블록을 즉시 free()로 해제하면 다음 턴 대화에서 캐시를 재활용할 수 없다. 고성능 엔진들은 OS 커널의 페이지 캐시처럼 Reference Count가 0이 된 블록을 캐시 풀(Cached Pool)로 전환하여 전역 해시 테이블에 그대로 유지한다. 만약 동일한 세션이나 다른 사용자가 해당 접두사를 다시 요청하면 Ref Count를 다시 1로 올리며 즉시 재사용(Cache Hit)한다. 오직 새로운 요청을 위한 가용 블록이 완전히 고갈되었을 때만 Ref=0인 블록 중 last_accessed_time이 가장 오래된 블록부터 순차적으로 방출(LRU Eviction)한다.

CoW(Copy-on-Write)를 통한 블록 격리 및 불변성 유지: 여러 요청이 동일한 시스템 프롬프트의 물리 블록을 공유하고 있을 때(Ref Count > 1), 특정 요청이 다음 토큰을 생성하여 해당 블록의 남은 슬롯에 새 KV 값을 써야 하는 상황이 올 수 있다. 이때 공유 블록을 직접 수정하면 다른 세션의 데이터가 오염된다. 엔진의 블록 관리자(Block Manager)는 대상 블록의 Ref Count가 1보다 크면 새로운 물리 블록을 할당하여 기존 데이터를 복제한 뒤 단독 소유권을 부여하는 Copy-on-Write (CoW) 메커니즘을 수행하여 완벽한 세션 격리를 보장한다.

Multi-LoRA 및 테넌트 격리를 위한 Salted Hashing: 동일한 베이스 모델 위에서 여러 개의 LoRA 어댑터나 서로 다른 고객 테넌트(Tenant)를 서빙할 때, 프롬프트 텍스트가 완전히 같더라도 적용된 가중치가 다르므로 KV 캐시가 공유되어서는 안 된다. vLLM의 Prefix Caching은 블록 해시 계산 시 LoRA_ID나 Tenant_ID를 솔트(Salt)로 주입하여, 어댑터가 다른 요청 간에는 해시값이 완전히 달라지도록 강제함으로써 보안 격리와 올바른 추론을 보장한다.

3. 실무 서빙 설정 및 최적화 패턴

3.1 vLLM에서 Automatic Prefix Caching 활성화

vLLM에서는 서버 실행 시 --enable-prefix-caching 플래그를 추가하는 것만으로 즉시 전역 블록 해시 체인 캐싱이 활성화된다 (vLLM Best Practices).

Python 스크립트나 인라인 LLM 파이프라인에서 EngineArgs로 설정할 경우:

3.2 SGLang에서 RadixAttention 기반 고속 서빙

SGLang은 기본 런타임 아키텍처 자체가 RadixAttention을 기반으로 동작하므로, 별도의 복잡한 설정 없이도 고속 프리픽스 트리가 활성화된다 (SGLang Documentation).

4. 로컬 Python 6대 런타임 불변식 검증 시뮬레이션

아래 스크립트는 Prefix Caching의 6대 핵심 런타임 불변식(블록 해시 체인 컨텍스트 격리, Radix Tree 동적 노드 분할, Reference Counting 기반 LRU 캐시 풀 생명주기, TTFT 및 FLOPs 연산 절감 수치, Multi-LoRA 솔트 격리, Logical-to-Physical 블록 매핑 및 Copy-on-Write 무결성)을 시뮬레이션하여 검증한다.

로컬 환경에서 위 스크립트를 실행한 결과는 다음과 같았다:

5. 실무 도입 및 운영 점검 체크리스트

프롬프트 접두사 정규화 및 순서 고정: 시스템 프롬프트, 도구 스키마(Tool Definitions), Few-Shot 예제의 배치 순서를 요청마다 무작위로 섞지 않고 결정론적으로 고정해야 한다. 토큰이 1개라도 앞에 추가되면 이후 모든 블록의 해시 체인이 바뀌어 캐시 미스가 발생한다.

블록 크기(Block Size 16 vs 32)와 단편화 트레이드오프 측정: 블록 크기를 16으로 설정하면 접두사 매칭 정밀도가 높아져 적중률이 상승하지만 블록 관리 오버헤드가 증가하며, 32로 설정하면 관리 오버헤드는 줄어들지만 끝부분 미달 토큰(Internal Fragmentation)으로 인한 캐시 손실이 커질 수 있다. 워크플로 평균 턴 길이에 맞춰 벤치마크 후 결정한다.

GPU 가용 메모리 풀(gpu_memory_utilization) 튜닝: Prefix Caching의 효과를 극대화하려면 완료된 세션의 블록을 캐시 풀에 오래 유지할 수 있어야 한다. gpu_memory_utilization을 너무 낮게 잡으면 동시 요청이 조금만 몰려도 Ref=0 캐시 블록이 즉시 퇴출되므로, OOM이 나지 않는 선(보통 0.90~0.95)에서 넉넉하게 할당한다.

동적 배치 스케줄러(Continuous Batching) 연동 점검: 긴 프롬프트의 프리필이 캐시에서 즉시 반환될 때 디코딩 단계의 동시 실행 배치 크기가 급증할 수 있다. max_num_batched_tokens 및 max_num_seqs 한계치를 적절히 조정하여 배치 간 지연 스파이크를 방지한다.

Multi-LoRA 및 가상 테넌트 간 캐시 분리 감사: 다중 고객 테넌트나 다양한 파인튜닝 어댑터를 단일 서빙 인스턴스에서 호스팅할 경우, 해시 계산 루틴에 테넌트 식별자와 어댑터 ID가 확실히 바인딩되어 데이터 유출이나 오염이 없는지 단위 테스트로 검증한다.