Prefix Caching과 RadixAttention으로 보는 vLLM과 SGLang

같은 프롬프트를 연달아 두 번 보내면 흥미로운 일이 생깁니다. 첫 번째 요청은 첫 토큰이 나오기까지 제법 기다리는데, 바로 이어 보낸 두 번째 요청은 눈에 띄게 빨리 시작됩니다. 모델도 같고 프롬프트도 같은데, 왜 두 번째만 빠를까요?

여러 요청이 똑같은 프롬프트로 시작한다면, 같은 KV를 요청마다 새로 계산하는 것은 순수한 낭비입니다. 이 글에서는 그 낭비를 없애는 prefix caching이 vLLM 안에서 실제로 어떻게 동작하는지 따라가고, 같은 문제를 트리로 풀어낸 SGLang의 RadixAttention과 나란히 놓고 비교합니다. 미리 말해두면, 흔히 알려진 “해시 방식 vLLM vs 트리 방식 SGLang”이라는 대비는 실제 구조를 뜯어보면 거의 무너집니다. 두 엔진의 진짜 차이는 다른 곳에 있습니다.

vLLM은 v0.25.1, SGLang은 2026년 7월 기준 main 브랜치를 기준으로 씁니다.

끝난 요청이 남긴 블록을 주워 쓴다

vLLM은 KV Cache를 고정 크기 블록으로 쪼개 관리하고, 동시에 살아 있는 요청들이 같은 물리 블록을 가리키게 하는 블록 공유를 지원합니다. 같은 시스템 프롬프트로 시작한 요청 A와 B가 나란히 돌고 있으면, 공통 구간의 KV는 물리 메모리에 한 번만 두고 둘이 나눠 씁니다.

그런데 실제 서비스에서 더 흔한 상황은 따로 있습니다. 요청 A가 이미 끝난 뒤에, 같은 시스템 프롬프트를 든 요청 B가 도착하는 경우입니다. A가 끝나면 A의 블록들은 풀에 반납됩니다. 여기서 vLLM의 선택이 중요합니다. 반납된 블록의 내용을 지우지 않습니다. 블록은 “빈 블록” 목록에 들어가지만, 안에 든 KV와 “이 블록이 어떤 토큰들의 KV인지” 알려주는 꼬리표는 그대로 남습니다. B가 도착했을 때 같은 접두사로 시작한다는 것만 확인되면, prefill 계산을 통째로 건너뛰고 그 블록을 다시 가리키기만 하면 됩니다.

이것이 prefix caching입니다. 블록 공유가 공간축의 공유(동시에 살아 있는 요청들 사이)였다면, prefix caching은 시간축의 재사용(끝난 요청과 새 요청 사이)입니다.

왜 하필 “prefix”, 접두사일까요? 어텐션의 인과성 때문입니다. 각 토큰의 KV는 자기 자신과 앞선 토큰들에만 의존합니다. 그래서 프롬프트의 앞부분이 완전히 같으면 그 구간의 KV도 완전히 같고, 계산 없이 가져다 써도 결과가 한 비트도 달라지지 않습니다. 반대로 중간이나 뒷부분만 같은 경우는 재사용할 수 없습니다. 같은 문장이라도 앞에 온 내용이 다르면 KV가 달라지니까요.

얼마나 이득인지 숫자로 보겠습니다. 시스템 프롬프트가 2,048토큰이고 사용자 질문이 평균 50토큰인 챗봇을 생각해봅시다.

prefill은 GPU 연산량이 병목인 compute-bound 구간입니다. 그 연산이 1/40이 되면 첫 토큰까지의 대기 시간(TTFT)이 그만큼 짧아지고, 아낀 연산은 같은 GPU 위에서 도는 다른 요청들 몫으로 돌아갑니다.

멀티턴 대화에서는 효과가 더 큽니다. 대화형 API는 매 턴 “지금까지의 대화 전체 + 새 발화”를 프롬프트로 보내는데, 이 “지금까지의 대화 전체”가 정확히 직전 턴에 계산해둔 접두사입니다. 캐시가 없으면 대화가 길어질수록 매 턴 다시 계산하는 양이 계속 불어나고, 캐시가 있으면 매 턴 새 발화 몫만 계산하면 됩니다.

블록 해시가 곧 접두사다

남은 문제는 이것입니다. 새 요청이 왔을 때 “이 접두사의 KV가 이미 있다”는 걸 어떻게 알아낼까요? 지금까지 거쳐 간 요청들의 프롬프트와 일일이 문자열 비교를 할 수는 없습니다. vLLM의 답은 해시입니다.

vLLM은 KV를 16토큰짜리 블록 단위로 관리합니다. prefix caching은 여기에 한 가지를 얹습니다. 블록이 가득 차는 순간, 그 블록에 해시를 하나 매겨두는 것입니다. 그런데 이 해시를 만드는 방식이 핵심입니다.

해시의 입력에 그 블록의 토큰들만 넣는 게 아니라 바로 앞 블록의 해시를 함께 넣습니다. 이 사슬 구조가 만드는 성질을 따라가 보면, h2가 같다는 것은 블록 2의 토큰들이 같고 h1도 같다는 뜻입니다. h1이 같다는 것은 다시 블록 1의 토큰들이 같고 h0도 같다는 뜻이고, h0까지 내려가면 결국 “처음부터 여기까지의 모든 토큰이 같다”가 됩니다. 해시값 하나가 블록 하나가 아니라 접두사 전체를 보증하는 것입니다. 그래서 vLLM은 “해시 → 물리 블록” 맵 하나만 갖고 있으면 됩니다.

새 요청이 오면 프롬프트를 16토큰씩 잘라 이 해시 사슬을 만들고, 앞에서부터 맵을 조회합니다. 연속으로 걸리는 데까지가 캐시 히트고, 처음 미스가 난 지점부터만 prefill을 수행합니다.

해시 입력에는 토큰 외에 몇 가지가 더 들어갑니다. LoRA 어댑터 ID와 멀티모달 입력의 해시가 대표적입니다. 같은 토큰이라도 다른 어댑터를 거치면 KV가 다르니, 키를 분리해서 잘못된 재사용을 막는 것입니다. 요청에 cache_salt를 넣어 캐시를 사용자 단위로 격리할 수도 있습니다. 여러 테넌트가 한 서버를 쓸 때, 응답 지연의 차이를 관찰해서 다른 사용자의 캐시 내용(예: 프롬프트에 든 비밀 정보)을 추측하는 공격을 막는 용도입니다. 해시 함수는 v0.11부터 SHA-256이 기본이라 서로 다른 접두사가 같은 해시를 갖게 될 걱정은 실질적으로 없습니다.

16토큰 경계에서만 걸린다

한 가지 주의할 성질이 있습니다. vLLM은 가득 찬 블록만 해시를 매기고 캐시합니다. 반쯤 찬 블록은 해시가 없고, 따라서 재사용도 안 됩니다.

즉 캐시 히트는 항상 16토큰 경계에서 끊깁니다. 최악의 경우 15토큰이 “사실은 같은데도” 다시 계산됩니다. 이게 실무에서 문제가 될까요? 대부분 아닙니다. 손해는 접두사 길이와 무관하게 최대 15토큰으로 고정되어 있습니다. 2,000토큰짜리 시스템 프롬프트라면 1%도 안 되는 양이고, 접두사가 짧아서 비율이 커지는 경우라면 애초에 캐시로 아낄 절대량 자체가 작습니다.

공짜에 가까워서 기본으로 켠다

캐시가 좋다는 건 알겠는데, 공짜는 아닐 것 같습니다. 요청마다 해시를 계산하고 맵을 조회하는 비용은 히트가 나든 안 나든 매번 듭니다. 프롬프트가 전부 제각각이라 히트율이 0%에 가까운 서비스라면, 이 비용은 순수한 손해입니다.

실제로 V0 엔진에서는 이 이유로 prefix caching이 기본으로 꺼져 있었습니다. 히트율이 낮은 워크로드에서 CPU 오버헤드가 이득을 갉아먹는 경우가 있었기 때문입니다. V1은 이 오버헤드를 없애는 쪽으로 자료구조를 다시 설계했습니다.

• 블록 객체를 시작할 때 전부 만들어 둡니다. 서빙 중에 블록을 표현하는 파이썬 객체를 새로 만들지 않으니, 그만큼의 할당 비용이 매 스텝의 경로에서 사라집니다.
• 빈 블록 목록을 이중 연결 리스트로 만들고, 앞뒤 포인터를 블록 객체 안에 심었습니다. 캐시 히트가 나면 그 블록을 빈 목록의 한가운데서 즉시 꺼내야 하는데, 이 구조 덕분에 어디에 있든 O(1)에 꺼냅니다.

매 스텝 도는 코드는 상수 비용에 민감하다는 원칙이 블록 관리자에도 그대로 적용된 것입니다. vLLM 팀은 이 재설계로 히트율이 0%여도 처리량 손실이 1% 미만이라고 밝혔습니다(자체 측정치로, 별도의 벤치마크 공개는 없습니다). 잃을 게 그만큼 작으니 V1에서는 prefix caching이 기본으로 켜져 있습니다. 끄고 싶으면 --no-enable-prefix-caching을 주면 되지만, 히트가 전혀 없는 워크로드가 아니라면 끌 이유가 별로 없습니다.

메모리 걱정도 접어둬도 됩니다. prefix caching은 캐시를 위해 메모리를 따로 떼어두지 않습니다. 어차피 반납되어 빈 목록에 들어간 블록의 내용을 지우지 않고 두는 것뿐이라, 새 요청이 블록을 필요로 하면 언제든 내어줍니다. 그럼 어떤 블록부터 내어줄까요? 여기에 LRU가 들어갑니다.

• 블록 할당은 항상 빈 목록의 머리에서 꺼냅니다. 머리에 있는 블록이 가장 오래 안 쓰인 블록이고, 캐시된 내용이 있다면 이 순간 그 내용이 지워집니다(eviction).
• 캐시 히트가 난 블록은 빈 목록에서 빠지고 참조 카운트가 올라가서, 쓰는 동안에는 절대 지워지지 않습니다.
• 요청이 끝나 블록을 반납할 때는 역순으로, 즉 접두사의 끝쪽 블록부터 목록에 넣습니다. 그래서 같은 시각에 반납된 블록들 중에서는 사슬의 꼬리가 먼저 지워지고, 여러 요청이 공유할 가능성이 높은 앞쪽 블록일수록 오래 살아남습니다.

이 규칙들이 맞물린 결과가 실무에서 보는 그 동작입니다. 모두가 쓰는 시스템 프롬프트의 블록은 요청이 올 때마다 다시 히트되어 목록 밖으로 빠져나가니, 사실상 GPU에 상주하게 됩니다.

같은 아이디어를 트리로 세운 RadixAttention

이제 SGLang 차례입니다. SGLang은 LMSYS에서 만든 서빙 엔진으로, 같은 프롬프트 재사용 문제를 RadixAttention이라는 이름으로 풀었습니다. KV Cache를 radix tree 하나로 관리하는 방식입니다.

radix tree는 trie(접두사 트리)의 압축판입니다. 갈림길 없이 이어지는 구간을 노드 하나로 합쳐서, 엣지 하나에 문자 하나가 아니라 시퀀스 통째로 붙습니다. RadixAttention에서는 이 엣지에 토큰 시퀀스가 붙고, 노드가 해당 구간의 KV 텐서를 들고 있습니다.

새 요청이 오면 루트에서 출발해 프롬프트와 일치하는 경로를 끝까지 따라갑니다. 따라간 만큼이 캐시 히트입니다. 일치가 노드 중간에서 끝나면 그 노드를 그 지점에서 둘로 쪼개 경계를 만들고(데이터 복사는 일어나지 않습니다), 거기서부터 새 가지가 자랍니다. 같은 시스템 프롬프트를 쓰는 요청들은 자연스럽게 한 몸통을 공유하고 질문 부분에서만 갈라지는 나무가 됩니다.

지우는 규칙도 vLLM과 비슷한 결을 갖습니다. 메모리가 부족하면 잎(leaf)부터 LRU 순서로 지웁니다. 지금 돌고 있는 요청이 쓰는 경로는 매치된 노드부터 루트까지 통째로 참조 카운트가 잡혀 있어 지워지지 않습니다. 안쪽 노드, 즉 여러 요청이 공유하는 접두사는 자식들이 다 사라지기 전에는 지울 수 없으니, 자연히 마지막까지 살아남습니다.

여기까지 읽고 나면 어딘가 익숙할 겁니다. 그럴 수밖에 없습니다. 위 그림의 위쪽과 아래쪽은 그린 방식만 다를 뿐 같은 구조이기 때문입니다.

vLLM의 해시 사슬을 다시 보겠습니다. 블록의 키는 hash(부모 해시, 토큰들)입니다. 부모의 해시가 키에 들어간다는 것은, 루트에서 그 블록까지의 경로 전체가 키에 새겨져 있다는 뜻입니다. 두 요청의 블록이 같은 키를 갖는 것은 접두사 경로 전체가 같을 때뿐입니다. 이것은 엣지 길이를 16토큰으로 고정한 radix tree를, 포인터 대신 해시맵으로 구현한 것과 같습니다. 최장 공유 접두사를 찾고, 공유되는 앞쪽을 마지막까지 남기고, 참조 카운트로 사용 중인 구간을 보호하는 동작까지 두 엔진이 같습니다. “해시 테이블은 트리와 달리 접두사를 공유할 수 없다”는 설명을 종종 보는데, 부모 해시 체이닝이 정확히 그 공유를 만들기 때문에 사실이 아닙니다.

그럼 매칭 입도의 차이는 뭘까요? SGLang은 토큰 단위로 매치하고 vLLM은 16토큰 경계에서 끊긴다고 했습니다. 이것도 트리 덕분이 아닙니다. SGLang의 KV 페이지 크기(page_size)가 기본 1토큰이라서 생기는 차이입니다. SGLang을 --page-size 16으로 띄우면 매칭 입도는 vLLM의 block_size=16과 정확히 같아집니다. 토큰 단위 페이지는 공짜가 아니어서(페이지가 작아질수록 관리할 단위가 늘어납니다) SGLang도 일부 GPU 백엔드에서는 기본값을 64로 잡습니다. 결국 “최대 15토큰 재계산 vs 잘게 쪼개진 페이지의 관리 비용”이라는 트레이드오프에서 두 엔진이 다른 기본값을 골랐을 뿐입니다.

진짜 차이는 스케줄러에 있다

같은 자료구조에 도달했다면, 두 엔진은 어디서 갈라질까요? 캐시 자체가 아니라 캐시를 대하는 스케줄러의 태도에서 갈라집니다.

이런 상황을 생각해봅시다. 캐시 공간은 빠듯한데, 접두사 X를 공유하는 요청들과 접두사 Y를 공유하는 요청들이 번갈아 도착합니다. 도착 순서대로(FCFS) 처리하면 X를 올렸다가 Y에 밀려 지우고, 다시 X를 올리는 일이 반복될 수 있습니다. 캐시는 있는데 히트가 안 나는, 캐시 스래싱입니다.

SGLang 논문의 답이 cache-aware scheduling입니다. 대기 중인 요청들을 도착 순서가 아니라 radix tree와의 매치 길이 순으로 정렬해서, 같은 접두사를 공유하는 요청들을 몰아서 처리합니다. X 팀을 먼저 다 처리하고 Y 팀으로 넘어가면 지웠다 다시 올리는 낭비가 사라집니다. 논문은 이 정렬(longest prefix match)이 실측 워크로드에서 이론적 최적 히트율의 96%에 도달했다고 보고합니다. vLLM의 V1 스케줄러에는 이에 해당하는 정책이 없습니다. 도착 순서대로 처리하는 FCFS와 우선순위 정책이 전부고, 캐시 상태는 스케줄 순서에 영향을 주지 않습니다. 논문의 기여 중 시간이 지나도 남는 것은 트리 그 자체가 아니라 이 스케줄링입니다.

다만 정직하게 덧붙이면, SGLang도 기본 정책은 FCFS입니다. 매치 길이 정렬은 옵션(--schedule-policy lpm)이고, 켜더라도 대기 큐가 128개를 넘으면 FCFS로 조용히 내려갑니다. 매 스케줄링마다 대기 큐 전체를 트리에 대조하고 정렬하는 비용이, 큐가 길어지면 히트율로 버는 것보다 커지기 때문입니다. 여기에 정렬이 도착 순서를 흐트러뜨리니 접두사가 안 겹치는 요청이 뒤로 밀리는 공정성 문제도 따라옵니다. 스케줄러는 매 스텝 도는 코드라, 영리한 정책에도 가격표가 따라붙습니다.

두 엔진을 정리하면 이렇게 됩니다.

항목	vLLM (APC)	SGLang (RadixAttention)
자료구조	블록 해시 사슬 (사실상 엣지 16토큰의 radix tree)	radix tree
매칭 입도 (기본)	16토큰 (block_size)	1토큰 (page_size)
지우는 순서	LRU + 사슬 꼬리 우선	LRU + 잎 우선
기본 활성화	켜짐	켜짐
캐시 인지 스케줄링	없음	있음 (옵션, 기본은 FCFS)

표의 위쪽 세 줄이 “구현이 다를 뿐 결과가 같은” 부분이고, 마지막 줄이 설계 사상이 실제로 갈라지는 부분입니다.

마치며

prefix caching은 한 문장으로 줄이면 “이미 한 계산은 두 번 하지 않는다”입니다. vLLM은 부모 해시를 물고 이어지는 블록 사슬로, SGLang은 radix tree로 이 문장을 구현했고, 뜯어보면 두 구현은 같은 구조의 두 표현입니다. 남는 차이는 캐시를 알고 스케줄을 짤 것인가라는 정책의 문제였습니다.

그런데 재사용이 아껴주는 것은 어디까지나 이미 계산한 것입니다. 캐시에 담기는 KV 그 자체의 크기, 그리고 매 스텝 GPU가 읽어야 하는 모델 가중치의 크기는 재사용으로 줄지 않습니다. 다음 글에서는 이 크기 자체를 줄이는 방법, 양자화를 살펴봅니다. FP8, AWQ, GPTQ가 각각 무엇을 몇 비트로 줄이는지, 그리고 GPU 세대에 따라 무엇을 골라야 하는지 정리합니다.

함께 보면 좋은 글

• Prefill과 Decode로 이해하는 LLM 추론 과정
• vLLM의 핵심 원리 PagedAttention 파헤치기
• Continuous Batching과 Chunked Prefill 완전 이해

참고자료

• Automatic Prefix Caching (vLLM Design Document)
• Hybrid KV Cache Manager (vLLM Design Document)
• vLLM V1: A Major Upgrade to vLLM’s Core Architecture (vLLM Blog)
• SGLang: Efficient Execution of Structured Language Model Programs (arXiv 2312.07104)
• Fast and Expressive LLM Inference with RadixAttention and SGLang (LMSYS Blog)