Efficient Memory Management for Large Language Model Serving with PagedAttention

---

type: paper
source: https://arxiv.org/abs/2309.06180

---

Efficient Memory Management for Large Language Model Serving with PagedAttention

항목	내용
저자	Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, Ion Stoica
연도	2023
arXiv	2309.06180
분야
인용 수	— (Semantic Scholar 기준, 작성일 기준)

---

1. 배경 및 문제 정의

대규모 언어 모델(Large Language Model, LLM)이 챗봇·코드 어시스턴트·검색 보조 등 다양한 서비스에 활용되면서, 추론(inference) 단계에서의 처리량을 끌어올리는 일이 운영 비용을 결정짓는 핵심 과제가 되었다. 특히 GPT, OPT, LLaMA 같은 자동회귀(autoregressive) 트랜스포머 모델은 토큰을 한 번에 하나씩 생성하므로, 이전 토큰의 키(Key)·값(Value) 벡터를 캐시(KV cache, 어텐션 계산을 위해 토큰별로 저장하는 중간 결과)에 저장하고 매 스텝마다 누적해 사용한다. 이 KV 캐시는 시퀀스가 길어질수록 선형으로 커지며, GPU 메모리에서 가장 변동이 큰 자원이 된다.

저자들은 13B(130억) 파라미터 OPT 모델을 NVIDIA A100 한 장에서 서빙할 때의 메모리 구성을 조사하여, 모델 파라미터(약 65%)가 고정적으로 점유되는 가운데 KV 캐시(약 30%)가 요청 단위로 동적으로 (해제)할당되고, 활성화(activation) 메모리는 일시적으로만 사용됨을 보였다. 처리량을 높이려면 한 번의 배치(batch)에 더 많은 요청을 묶어 GPU 연산기를 채워야 하지만, 배치 크기는 KV 캐시가 차지할 수 있는 잔여 메모리에 의해 직접 제약된다.

Figure 1: NVIDIA A100에서 13B 파라미터 LLM 서빙 시 메모리 레이아웃

이 그림은 13B 파라미터 모델을 A100 한 장(40GB급)에 올렸을 때 메모리가 어떤 비율로 분할되는지를 트리맵 형태로 보여준다. 회색의 모델 파라미터가 가장 큰 영역을 고정 점유하고, 빨간색의 KV 캐시는 활성 요청 수에 따라 동적으로 늘어나며, 노란색의 활성화 영역은 매 스텝마다 임시로만 쓰인다. 이 시각화는 "처리량을 늘리려면 KV 캐시 영역을 얼마나 효율적으로 운용하느냐가 관건"이라는 본 논문의 출발점을 직관적으로 뒷받침한다.

Figure 2: 메모리 사용량과 처리량이 배치 크기에 따라 변하는 양상

배치 크기를 키우면 처리량이 향상되지만, 동시에 KV 캐시 점유 메모리가 가파르게 늘어 GPU 한도에 부딪히는 모습을 두 개의 서브플롯으로 대비한다. 즉 처리량 곡선은 "메모리 상한 이전까지만" 우상향하며, 이 상한선을 어떻게 늦추느냐가 시스템의 처리량을 결정한다는 사실을 보여준다.

Figure 3: 서로 다른 LLM 서빙 시스템의 평균 메모리 낭비 비율

네 개 시스템(Orca의 세 변형과 vLLM)을 동일 워크로드에서 비교하면, 기존 시스템들은 KV 캐시 영역의 60~80%를 실제 토큰 저장이 아니라 예약(reserved)·내부 단편화(internal fragmentation)·외부 단편화(external fragmentation)로 낭비하고 있음이 드러난다. 반면 vLLM은 같은 항목 기준으로 96% 이상을 실제 토큰 저장에 사용한다. 이 막대 차트는 "기존 방식이 본질적으로 비효율적"이라는 본 논문의 문제 제기를 정량적으로 압축한다.

2. LLM 서빙과 자동회귀 생성의 동작 원리

LLM 추론은 두 단계로 나뉜다. 먼저 프리필(prefill) 단계에서 입력 프롬프트의 모든 토큰을 한꺼번에 처리해 각 위치의 KV 벡터를 계산하고 캐시에 적재한다. 이 단계는 행렬-행렬 곱 위주여서 GPU 연산 한도(compute-bound)에 가깝게 동작한다. 이어지는 디코딩(decoding) 단계에서는 한 번에 한 토큰씩 자동회귀적으로 생성하면서 새로운 KV 벡터를 캐시에 누적한다. 이 단계는 모델 가중치와 캐시를 메모리에서 반복적으로 읽어와야 하므로 메모리 대역폭에 의해 제한되는(memory-bound) 영역이며, 단일 요청만으로는 GPU 연산기를 채우지 못한다.

따라서 처리량을 끌어올리려면 여러 요청을 묶어 디코딩 스텝을 공유하는 배칭이 필수다. 그러나 요청마다 입력 길이와 생성 길이가 제각각이고, 종료 시점도 달라서 정적인 배치보다는 토큰 단위로 흐름을 조정하는 반복 단위 스케줄링(iteration-level scheduling, 한 번의 디코딩 스텝마다 활성 요청 집합을 재구성하는 방식) 이 필요하다. Orca 같은 선행 연구가 이 스케줄링은 잘 다루지만, KV 캐시 메모리 자체의 관리 비효율은 그대로 남아 있어 결과적으로 배치 크기가 작아진다는 점이 본 논문의 핵심 관찰이다.

3. 기존 시스템의 KV 캐시 관리와 그 한계

FasterTransformer, Orca를 포함한 기존 LLM 서빙 시스템은 각 요청의 KV 캐시를 연속된(contiguous) 메모리 공간에 저장한다. 딥러닝 프레임워크가 텐서 연속성을 가정하기 때문에 자연스러운 선택이지만, KV 캐시는 두 가지 본질적인 특성을 갖는다. 첫째, 캐시 크기는 토큰 생성에 따라 동적으로 늘어난다. 둘째, 요청별 최종 길이는 실행이 끝나기 전에는 알 수 없다. 이 두 특성과 "연속 저장" 가정이 충돌하면서 세 가지 형태의 메모리 낭비가 발생한다.

• 예약(reserved) 낭비: 요청의 최대 가능 길이만큼 메모리를 미리 예약해두면, 실제 생성 길이가 그보다 짧을 때 차이만큼 비어 있는 채로 잡혀 있다.
• 내부 단편화(internal fragmentation): 요청 단위로 잡힌 청크 내부에서, 아직 채워지지 않은 미래 토큰 자리가 다른 요청에 재할당되지 못한다.
• 외부 단편화(external fragmentation): 서로 다른 크기의 연속 영역들을 반복해 (해제)할당하다 보면 메모리 곳곳에 사용 불가능한 빈틈이 남는다.

저자들이 측정한 바에 따르면, 기존 시스템에서 KV 캐시 영역의 실제 토큰 저장에 쓰인 비율은 20.4%~38.2%에 불과하다. 다시 말해 "KV 캐시용으로 잡힌 메모리 중 60% 이상이 사실상 버려지고 있다"는 의미다. 또한 OPT-13B 모델 기준으로 토큰 하나당 KV 캐시는 약 800KB가 필요하며, 단일 요청이 채울 수 있는 최대 KV 캐시 용량은 약 1.6GB에 달한다.

Figure 4: 기존 시스템의 KV 캐시 메모리 관리와 세 가지 낭비 유형

이 다이어그램은 두 개의 요청이 동일한 메모리 공간에 연속 저장되었을 때, 예약·내부 단편화·외부 단편화가 어떻게 동시에 발생하는지를 토큰 단위 슬롯 도식으로 보여준다. 같은 토큰 ID라도 위치가 달라지면 KV 값 자체가 달라지므로 단순히 "동일 토큰끼리 묶기"로 해결되지 않는다는 점도 함께 시사한다. 이는 곧이어 제안하는 페이징 기반 접근의 동기를 시각적으로 정당화한다.

또 다른 측면은 복잡한 디코딩 알고리즘에서의 공유 가능성이다. 단일 시퀀스 생성을 넘어, 같은 프롬프트에서 여러 출력을 뽑는 병렬 샘플링(parallel sampling)이나, 매 스텝 후보를 가지치기하는 빔 서치(beam search)에서는 여러 시퀀스가 KV 캐시의 일부를 공유할 수 있다. 저자들의 측정에 따르면 병렬 샘플링에서 프롬프트 KV 캐시는 전체의 약 12%를 차지하며 모든 샘플이 공유 가능하고, 빔 서치에서는 최대 55%까지 메모리를 절감할 수 있다. 그러나 연속 메모리 저장 구조는 이 공유를 구조적으로 막는다 — 공유하려는 영역이 서로 다른 요청의 연속 청크 한가운데에 박혀 있기 때문이다.

항목	값
KV 캐시의 실제 효율 메모리 비율(기존 시스템)	20.4% ~ 38.2%
OPT-13B 단일 요청 최대 KV 캐시	약 1.6 GB
OPT-13B 토큰당 KV 캐시	약 800 KB
병렬 샘플링에서 공유 가능한 프롬프트 KV 비율	약 12%
빔 서치 최대 메모리 절감	최대 55%

4. PagedAttention 알고리즘

저자들은 운영체제(OS)의 가상 메모리(virtual memory)와 페이징(paging) 기법에서 영감을 받아 PagedAttention을 제안한다. 핵심 아이디어는 KV 캐시를 고정 크기의 블록으로 나누어 비연속(non-contiguous)으로 저장하고, 어텐션 계산 시 블록 단위로 키·값을 끌어와 사용하는 것이다. 이 단순한 변화가 세 가지 효과를 동시에 가져온다.

1. 블록 단위 할당이므로 한 블록 내부의 미사용 슬롯(=내부 단편화)은 하나의 블록 분량으로 한정된다. 요청당 한 블록 미만 수준으로 줄어든다.
2. 모든 블록이 동일 크기이므로 외부 단편화는 원천적으로 사라진다. 임의의 빈 블록 슬롯에 어떤 요청이든 넣을 수 있다.
3. 블록 자체가 공유 단위가 될 수 있어, 여러 시퀀스가 동일 KV 블록을 가리키도록 만들면 병렬 샘플링·빔 서치에서 자연스러운 캐시 공유가 가능해진다.

수식으로 보면, 표준 어텐션 계산은 쿼리 $q_i$와 모든 이전 키 $k_j$, 값 $v_j$($j \le i$)에 대해 다음과 같이 정의된다.

$$A_{ij} = \frac{\exp(q_i^\top k_j / \sqrt{d})}{\sum_{j'=1}^{i} \exp(q_i^\top k_{j'} / \sqrt{d})}, \quad o_i = \sum_{j=1}^{i} A_{ij} v_j$$

여기서 $q_i$는 i번째 토큰의 쿼리 벡터, $k_j, v_j$는 j번째 토큰의 키·값 벡터, $d$는 헤드 차원, $A_{ij}$는 i번째 쿼리가 j번째 키에 부여하는 어텐션 가중치, $o_i$는 i번째 토큰의 출력이다. PagedAttention은 위 합산을 블록 단위로 분해해 수행한다. 블록 크기를 $B$라 하면 j번째 토큰의 KV는 $\lfloor (j-1)/B \rfloor$번째 블록의 $((j-1) \bmod B)$번째 슬롯에 저장되며, 어텐션 커널은 블록 테이블(block table)을 통해 논리적 위치를 물리 블록 주소로 변환해 읽는다.

Figure 5: vLLM 시스템 개요

vLLM은 중앙 스케줄러(Scheduler), KV 캐시 매니저(KV Cache Manager), 블록 할당자(Block Allocators), 그리고 GPU 워커(Workers)로 구성된다. 스케줄러가 매 스텝마다 어떤 요청을 진행할지를 결정하면, 캐시 매니저는 각 시퀀스의 논리 블록 ↔ 물리 블록 매핑을 관리하고, 워커는 PagedAttention 커널로 실제 어텐션 계산을 수행한다. 이 구조는 OS의 메모리 관리부와 사용자 프로세스를 분리한 것과 유사하며, 그래서 LLM 추론에 "가상 메모리" 개념을 도입할 수 있다는 본 논문의 비유를 그대로 시스템 구조로 옮겨놓은 그림이다.

Figure 6: PagedAttention 알고리즘 — 비연속 블록에 저장된 키·값에 대한 어텐션

이 그림은 한 쿼리 벡터가 메모리 곳곳에 흩어진 KV 블록들을 어떻게 모아 어텐션을 계산하는지를 보여준다. 핵심은 블록의 물리 주소가 연속적일 필요가 없다는 점이며, 블록 테이블이 논리 인덱스를 임의의 물리 위치로 매핑한다. 이는 표준 어텐션 수식과 동일한 결과를 산출하면서도 연속 메모리 가정에서 벗어남으로써, 앞서 살펴본 세 가지 단편화를 동시에 제거할 수 있음을 시각적으로 정당화한다.

5. vLLM의 블록 단위 메모리 관리와 디코딩

vLLM은 PagedAttention 위에서 동작하는 분산 LLM 서빙 엔진이다. 각 시퀀스에 대해 논리 KV 블록(logical block) 의 시퀀스를 두고, 매핑 테이블을 통해 물리 KV 블록(physical block) 으로 연결한다. 새 토큰이 생성되면 마지막 논리 블록이 가득 찰 때마다 새로운 물리 블록을 할당하고, 시퀀스가 종료되면 해당 블록들을 풀로 반환한다. 이 방식 덕분에 메모리 할당 단위가 "요청의 최대 길이"가 아니라 "현재까지 채워진 블록 수"로 줄어든다.

Figure 7: 블록 테이블 변환

이 다이어그램은 한 시퀀스가 토큰을 생성해가는 동안 논리 블록 인덱스가 어떻게 물리 블록 번호로 변환되는지를 단계별로 보여준다. 새 토큰이 들어올 때 마지막 블록이 가득 차 있으면 빈 물리 블록을 잡아 새로운 논리 블록과 연결하고, 그 외에는 기존 블록의 다음 슬롯에 기록한다. OS 페이지 테이블과의 일대일 대응이 분명히 드러나며, 본 논문이 도입한 "가상 메모리" 추상화가 LLM 추론에서 작동 가능한 이유를 설명한다.

Figure 8: 두 요청의 KV 캐시를 동시에 저장하는 모습

서로 다른 두 시퀀스가 동일한 물리 블록 풀을 공유한다는 점이 핵심이다. 각 시퀀스의 논리 블록은 자신의 인덱스를 따르지만, 매핑된 물리 블록은 풀 어디에도 위치할 수 있다. 한 요청의 종료로 빈 블록이 생기면 다른 요청이 즉시 그 슬롯을 차지할 수 있어, 외부 단편화 없이도 GPU 메모리를 거의 100% 활용할 수 있는 근거가 된다.

스케줄링 측면에서 vLLM은 선점형(preemptive) 스케줄러를 둔다. 메모리가 부족해지면 일부 시퀀스의 KV 블록을 CPU 메모리로 스왑(swap)하거나, 필요할 때 다시 계산(recomputation)해 복원한다. 어느 전략을 쓸지는 블록 크기와 시퀀스 길이의 함수이며, 아래 6절·8절에서 실험적으로 분석된다.

6. 다양한 디코딩 시나리오로의 확장

PagedAttention의 블록 단위 공유는 단일 시퀀스 생성 외의 시나리오에서 더 큰 가치를 만든다.

병렬 샘플링(parallel sampling) — 같은 프롬프트로 N개의 서로 다른 출력을 뽑는 경우, 프롬프트 구간의 KV 블록을 N개 시퀀스가 모두 공유하고, 생성 단계로 들어가면서 분기되는 부분만 별도의 물리 블록을 잡으면 된다. 공유 블록을 수정하려는 시점에는 Copy-on-Write(쓰기 시 복사) 메커니즘으로 새 물리 블록을 할당해 분기시킨다.

Figure 9: 병렬 샘플링 예시

프롬프트에 해당하는 논리 블록은 두 시퀀스가 같은 물리 블록을 가리키지만, 생성이 진행되면서 한쪽이 새 토큰을 쓰는 순간 해당 블록만 복제되어 분기되는 과정이 색상과 화살표로 표시된다. 이 그림은 PagedAttention의 블록 단위 추상화가 "공유 가능한 부분만 공유"라는 정밀 제어를 자연스럽게 가능하게 함을 보여주며, 앞서 측정된 12% 프롬프트 공유 비율이 실제 메모리 절감으로 이어지는 메커니즘을 그려낸다.

빔 서치(beam search) — 매 스텝마다 점수가 높은 상위 k개의 후보(beam)를 유지하는 알고리즘이다. 후보들은 공통 조상 토큰 시퀀스를 갖고 있으므로, 그 조상 구간의 KV 블록을 공유하고 분기 지점부터만 새 블록을 잡으면 된다. 디코딩이 진행되며 가지치기와 분기가 반복될 때 블록 참조 카운트만 갱신하면 되므로, 연속 메모리 방식 대비 복사 오버헤드가 거의 사라진다.

Figure 10: 빔 서치 예시

이 그림은 빔 너비 4의 시나리오에서 네 후보가 어떤 시점부터 분기되어 갈라지는지, 그리고 공통 조상 블록이 어떻게 단일 물리 블록을 공유하는지를 트리 형태로 도식화한다. 가지치기로 어떤 후보가 폐기되면 그 가지가 점유했던 물리 블록은 참조 카운트가 0이 되어 즉시 회수된다. 이 구조 덕분에 본 논문이 측정한 "최대 55% 메모리 절감"이 빔 너비가 클수록 두드러지게 된다.

공유 프리픽스(shared prefix) — 기계 번역의 few-shot 프롬프팅처럼 여러 요청이 동일한 시스템 프롬프트나 예시를 앞에 붙이는 경우, 그 프리픽스의 KV 블록은 모든 요청이 공유할 수 있다. vLLM은 이를 위해 프리픽스 KV 블록을 명시적으로 캐싱하고 새 요청이 들어오면 즉시 재사용한다.

Figure 11: 기계 번역에서의 공유 프롬프트 예시

두 시퀀스가 동일한 시스템 지시문과 예시 묶음을 공유하고, 그 뒤에 각자의 입력 문장과 출력만 다르게 이어지는 구조가 도식화된다. 공유 구간의 길이가 길수록(예: 5-shot 프롬프트의 경우 수백 토큰) 공유 효과는 비례해 커지며, 이는 프로덕션의 챗봇·번역 워크로드가 PagedAttention의 블록 공유로부터 직접 이득을 얻을 수 있음을 보여준다.

7. 실험 환경 및 워크로드

저자들은 OPT(13B/66B/175B), LLaMA(13B), 그리고 GPT 계열 모델을 NVIDIA A100 GPU(단일 또는 텐서 병렬 다중)에서 실험한다. 비교 대상은 FasterTransformer와 Orca의 세 변형(Orca-Max, Orca-Pow2, Orca-Oracle)이다. Orca-Max는 모델의 최대 시퀀스 길이로 메모리를 예약하는 가장 단순한 방식, Orca-Pow2는 출력 길이의 2의 거듭제곱 단위로 예약, Orca-Oracle은 실제 출력 길이를 미리 안다고 가정하는 이상적 상한이다. 이 세 변형과의 비교는 곧 "할당 정책의 정밀도가 처리량에 미치는 영향"을 분리해 보여준다.

워크로드는 두 종류를 사용한다. ShareGPT는 사용자가 ChatGPT와 주고받은 실제 대화 로그로, 입력·출력 길이의 분산이 매우 크다. Alpaca는 명령어 튜닝용 합성 데이터셋으로, 평균 길이가 더 짧고 분포가 좁다. 두 데이터셋을 같이 사용하는 이유는, 분산이 큰 워크로드일수록 "최대 길이 예약" 방식의 비효율이 두드러지기 때문이다.

Figure 12: ShareGPT 입출력 토큰 분포

이 히스토그램은 ShareGPT 요청의 입력 토큰 길이와 출력 토큰 길이가 모두 긴 꼬리(long tail) 분포를 가짐을 보여준다. 일부 요청은 수천 토큰에 달하는 반면 대부분은 짧아, 모든 요청에 최대 길이 메모리를 예약하면 평균적으로 막대한 낭비가 발생함을 시사한다.

Figure 13: Alpaca 입출력 토큰 분포

Alpaca는 ShareGPT보다 분포가 좁고 짧은 쪽으로 쏠려 있어, 최대 길이 예약 방식의 패널티가 상대적으로 작다. 이 그림과 fig12의 대비는 이후 처리량 향상폭이 ShareGPT에서 더 크게 나타나는 이유를 미리 설명한다.

8. 단일 시퀀스 생성과 디코딩 알고리즘별 평가

먼저 단일 시퀀스 생성에서의 처리량을 본다. 요청 도착률(rate)을 단계적으로 올려가며, 정상 상태에서의 정규화 지연시간(normalized latency, 토큰당 평균 지연)을 측정한다. SLO(서비스 수준 목표)를 만족시키면서 처리할 수 있는 도착률 상한이 곧 시스템의 유효 처리량이다.

Figure 14: ShareGPT 및 Alpaca에서 OPT 모델 단일 시퀀스 생성

세 모델 크기(13B/66B/175B)에 걸쳐 요청률 대 정규화 지연시간 곡선을 그린 결과, vLLM은 동일한 SLO 기준에서 Orca-Max 대비 2~4배 높은 도착률을 처리한다. 모델이 클수록(즉 토큰당 KV 캐시가 클수록) vLLM의 우위가 커지는데, 이는 PagedAttention이 KV 캐시 활용 효율을 절대값으로 끌어올리기 때문이며, 본 논문의 핵심 주장이 모델 스케일에 강건함을 보인다.

Figure 15: Alpaca에서 OPT 모델 단일 시퀀스 생성

Alpaca는 분포가 짧아 절대 처리량 자체는 ShareGPT보다 높지만, 시스템 간 상대 비교에서는 vLLM이 여전히 Orca-Pow2와 Orca-Oracle을 모두 앞서고, 이상적 상한인 Oracle과의 격차도 작다. 이는 vLLM의 메모리 관리가 "정확한 미래 길이를 알고 있다고 가정한 시스템"에 가까운 효율을 실현하고 있음을 보여준다.

Figure 16: ShareGPT에서 시스템별 동시 배치 요청 수

같은 시점에 GPU 위에서 함께 디코딩 중인 요청 수를 시스템별로 세어 보면, vLLM은 Orca-Max 대비 약 2~4배 많은 요청을 동시에 묶는다. 처리량 향상의 근본 원인이 "더 큰 배치"라는 점이 이 막대 그래프 한 장에 압축된다.

Figure 17: Alpaca에서 시스템별 동시 배치 요청 수

짧은 분포의 Alpaca에서도 vLLM의 배치 우위는 유지되며, 이상적인 Orca-Oracle에 근접한다. 즉 메모리 관리가 정밀해질수록 배치 크기는 한계에 가까워지고, vLLM은 그 한계 근처에서 동작한다.

다음으로 더 복잡한 디코딩 — 병렬 샘플링과 빔 서치 — 에서의 결과를 본다.

Figure 18: Alpaca에서 OPT-13B 병렬 생성과 빔 서치 처리량

세 개의 서브플롯에 걸쳐 vLLM은 병렬 샘플(샘플 수 2/4/6)과 빔 너비(2/4/6) 시나리오 모두에서 Orca 변형 대비 큰 폭의 처리량 우위를 보인다. 특히 빔 서치처럼 시퀀스 간 KV 공유 비율이 높은 워크로드에서 격차가 가장 크게 벌어진다.

Figure 19: 빔 너비별 정규화 지연시간 곡선

빔 너비를 2→4→6으로 키울수록 vLLM과 Orca의 격차가 커진다. 너비 6에서는 vLLM이 동일 SLO에서 Orca-Max 대비 수 배의 도착률을 처리하며, 이는 빔 후보들 사이의 공유 KV 블록을 PagedAttention이 추가 비용 없이 재사용한 결과다.

Figure 20: 병렬 샘플링에서의 메모리 절감

샘플 수가 늘수록 메모리 절감률이 커지지만, 절감의 대부분은 프롬프트 구간(전체 KV의 약 12%)에서 비롯된다. 즉 생성 구간에서 분기된 후로는 더 이상 공유가 일어나지 않기 때문에 절감의 상한이 비교적 일찍 포화된다.

Figure 21: 빔 서치에서 빔 너비별 메모리 절감

빔 너비가 2→4→6으로 늘어나면서 vLLM이 절감하는 메모리 비율이 단조 증가하여 최대 약 55%에 도달한다. 빔 서치의 후보들이 공통 조상 시퀀스를 길게 공유하기 때문이며, 이는 본 논문이 PagedAttention의 가장 강한 이점으로 강조하는 부분과 정확히 일치한다.

Figure 22: 공유 접두사 번역 워크로드 — 1-shot vs 5-shot

두 라인 플롯은 공유 프리픽스가 80개 토큰(1-shot)에서 341개 토큰(5-shot)으로 길어졌을 때의 처리량 변화를 보여준다. 프리픽스가 길수록 vLLM의 우위가 더 커지는데, 이는 해당 구간의 KV 블록을 모든 요청이 단 한 번 저장하고 재사용하기 때문이다. 시스템 프롬프트가 긴 프로덕션 챗봇에 그대로 적용되는 시사점이다.

Figure 23: 챗봇 워크로드 성능

챗봇은 누적된 대화 이력이 매번 입력으로 들어가는 특성 때문에, 입력 길이가 점점 길어진다. vLLM은 4개 시스템 비교에서 가장 낮은 정규화 지연시간을 유지하며, 도착률이 올라갈수록 격차가 더 벌어진다. 누적 컨텍스트로 인해 KV 캐시가 큰 워크로드에서 PagedAttention의 효과가 직접적으로 드러난다.

9. 마이크로벤치마크 — 커널과 블록 크기

PagedAttention은 비연속 메모리 접근을 동반하므로 어텐션 커널 자체의 오버헤드가 우려될 수 있다. 저자들은 이를 직접 측정한다.

Figure 24: 어텐션 커널 지연 시간 (다양한 배치 크기)

배치 크기를 키워가며 vLLM의 PagedAttention 커널과 FasterTransformer의 표준 어텐션 커널 지연을 비교한 그래프다. vLLM 커널은 작은 배치에서는 약간 느리지만, 큰 배치에서는 둘이 거의 동일한 수준으로 수렴한다. 즉 비연속 접근의 비용은 메모리 절감으로 가능해진 더 큰 배치의 이득에 의해 충분히 상쇄된다.

Figure 25: 블록 크기별 정규화 지연시간 (ShareGPT/Alpaca)

블록 크기를 1, 2, 4, 8, 16, 32, 64로 변화시키며 두 데이터셋에서 측정한 결과, 블록 크기 16 부근이 거의 모든 조건에서 최적이다. 너무 작으면 메타데이터 오버헤드(블록 테이블 조회)가, 너무 크면 내부 단편화가 다시 늘어나기 때문이다.

Figure 26: 블록 크기별 재계산 vs 스왑 시간

선점이 발생했을 때 블록을 CPU로 스왑할지(swap) 폐기 후 재계산할지(recomputation)는 비용 트레이드오프를 따른다. 작은 블록에서는 재계산이 유리하고, 큰 블록에서는 스왑이 유리한 교차 지점이 명확히 드러난다. vLLM은 블록 크기와 시퀀스 길이를 함께 보고 두 전략을 선택한다.

Figure 27: 블록 크기에 따른 정규화 지연 시간

앞 두 그림과 결합해 보면, 블록 크기 16이 메모리 효율·커널 비용·선점 회복 비용의 균형점에 위치함을 확인할 수 있다. 본 논문이 권장하는 기본값이 임의가 아니라 마이크로벤치마크에서 직접 도출된 값임을 보여주는 마지막 근거다.

10. 한계와 향후 과제

PagedAttention과 vLLM이 모든 상황에서 절대 우위를 갖는 것은 아니다. 워크로드의 분산이 매우 작아 모든 요청 길이가 비슷하면 기존 연속 할당 방식과 vLLM의 차이는 줄어든다. 또한 PagedAttention 커널은 GPU에서 비연속 KV 접근을 처리하기 위해 별도 구현이 필요하며, 새로운 어텐션 변형(예: 슬라이딩 윈도우, ALiBi 등)을 도입할 때마다 블록 인덱싱 로직을 맞춰야 한다는 구현 부담이 있다.

스케줄러 측면에서는 선점이 일어났을 때 어떤 요청을 우선 회복시킬지의 정책이 SLO 만족률에 영향을 미친다. 본 논문은 단순한 FCFS(first-come-first-served) 변형을 사용했으나, 향후 우선순위·페널티를 반영한 정책 연구의 여지가 남아 있다. 또한 멀티테넌시(다수의 사용자·모델 동시 호스팅) 환경에서 KV 캐시 풀을 모델 간에 어떻게 분할·공유할지도 후속 과제다.

참고: 핵심 선행 연구

• Orca: 반복 단위 스케줄링(iteration-level scheduling)을 도입해 LLM 추론의 배칭 한계를 끌어올린 시스템. vLLM은 Orca의 스케줄링 아이디어를 계승하면서, Orca가 다루지 못한 KV 캐시 메모리 자체의 비효율을 PagedAttention으로 해결한다.
• FasterTransformer: 트랜스포머 추론을 위한 고성능 GPU 커널 라이브러리. 본 논문에서 단일 요청 커널 성능의 비교 기준으로 사용된다.
• 운영체제의 가상 메모리·페이징: PagedAttention의 직접적인 모티브. 프로세스에 연속된 가상 주소 공간을 보장하면서 물리 메모리는 페이지 단위로 흩어 저장하는 OS 기법을, KV 캐시 관리에 처음 적용한 사례가 본 논문이다.
• 트랜스포머의 KV 캐싱: 자동회귀 디코딩 가속을 위해 GPT 시대부터 표준화된 기법. KV 캐시가 불가피하게 도입한 메모리 압박이 곧 본 논문이 해결하려는 대상이다.