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

 

GeekNews를 보다가 흥미로운 주제가 있어서 읽고 다시 정리해보는 시간을 가졌습니다. 제가 업무에서 vLLM을 주로 많이 사용합니다. 

양자화에 대한 지원이 좀 (많이) 부족하지만, 그래도 이만한 서빙용 라이브러리가 없는 것 같습니다. Aleksa Gordić의 블로그(https://www.aleksagordic.com/blog/vllm) 에서는 vLLM의 중심 알고리즘인 PagedAttention에 대해서 다루고 있습니다. 저도 그래서 한번 다루어 보도록 하겠습니다. 

 

해당 논문에 대해서 가장 먼저 요약해보자면 다음과 같습니다.

 

---

LLM 서빙의 병목은 연산이 아니라 메모리(특히 KV cache) 입니다. vLLM은 OS의 페이징 아이디어를 가져온 PagedAttention으로 KV cache를 비연속 블록으로 관리해 단편화·중복을 없애고, 프리픽스·빔 서치 등 공유 가능한 상태를 공유하는데, 그 결과, 기존 시스템(Orca, FasterTransformer) 대비 2~4× 처리량 향상을 보여준다고 합니다.

---

왜 메모리에서 병목이 발생할까?

GPU는 빠른데 메모리는 늘 부족합니다. 최신 가속기의 연산 성능 증가 속도는 메모리 용량 증가 속도를 앞지르고 있고, KV cache는 요청마다 동적으로 커지고 줄어들며 크기도 매우 큽니다 기존 방식처럼 요청별 연속 메모리를 미리 크게 잡아두면,

• (1) 예약 공간
• (2) 내부 단편화(over-provisioning)
• (3) 외부 단편화(buddy allocator 등)

가 발생해 실제로 쓸 수 있는 KV 메모리는 20~38% 수준으로 떨어질 수 있습니다.

 

---

[기존] 요청 A (최대 2048) ──────────────────────────
      [실제 300][   예약   ][   내부 단편화   ] [외부 단편화]

[기존] 요청 B (최대 512)   ──────────
      [실제 120][ 예약 ][내부 ][외부 ]

---

즉, LLM 서빙의 throughput은 메모리 배치 전략이 결정합니다. 특히, 요청 수가 늘수록 KV cache가 급증해 batch size가 잠겨버립니다.

 

논문이 제안한 해법은 “KV cache = 가상 메모리처럼” 다루기 입니다. 키·값을 고정 크기 블록(KV block) 으로 쪼개 비연속(Non-contiguous) 공간에 저장하고, 논리 블록 ↔ 물리 블록을 블록 테이블로 매핑합니다.

 

그래서:

• 필요할 때만 블록을 할당(사전 과할당 X)
• 크기가 같은 블록만 쓰므로 외부 단편화 0
• 블록 단위로 공유/복사(copy-on-write) 를 구현, 프리픽스·빔 간 KV 공유 활성화

블록 단위로 주의(쿼리)가 각 블록의 key/value에 접근 → 합산하는 블록-와이즈 어텐션으로 재구성. (Eq.4)

 

[논리 KV 블록]   B0   B1   B2   B3   ...
                  │    │    │
[물리 KV 블록]  P7 ← P1 ← P3   P9  ...
                   ^     ^
              (block table: 논리→물리 매핑 + #filled)

 

블록 테이블로 매핑하니 왼쪽→오른쪽으로 차곡차곡 채우며, 이전 블록이 다 차야 다음 블록을 할당하므로, 요청당 낭비는 최대 1블록으로 한정됩니다. 

 

공유가 성능이다: 프리픽스·패럴럴 샘플링·빔 서치

프리픽스 공유(Shared prefix)

시스템 프롬프트나 예시(few-shot) 같은 공통 프리픽스의 KV를 미리 캐시해 두고, 사용자 프롬프트는 그 뒤에만 얹어 계산합니다. 마지막 블록은 copy-on-write로 처리하게 됩니다.

 

[공유 프리픽스 KV] ==== (여러 요청이 공용 매핑)
[사용자 입력 KV]   ---- (요청별 생성)

 

패럴럴 샘플링(한 프롬프트→여러 샘플)

프롬프트 구간은 완전 공유, 생성 구간만 분기. 마지막 블록에서만 copy-on-write가 일어난다. 메모리 절감이 큽니다.

빔 서치

빔 후보들이 여러 블록을 더 넓게 공유합니다. 후보가 교체될 때는 참조 수(refcount) 0인 블록을 회수하고, 필요한 블록만 새로 할당하며, 기존 시스템처럼 대량의 KV 복사가 아니라, 블록 공유 + 필요 시 1블록 복사만 하면 됩니다.

실제 실험에서 병렬 샘플링은 6~10%, 빔 서치는 38~55% 수준의 KV 블록 절약이 관찰되었다.

---

스케줄링·스와핑·재계산: 메모리 압박을 다루는 법

요청 폭주로 GPU 블록이 바닥나면 vLLM은 FCFS + 그룹 단위 선점을 적용하고, 두 가지 복구 전략을 씁니다.

• Swapping: KV 블록을 CPU RAM으로 내보냈다가 복귀. 블록이 크면 유리.
• Recomputation: 필요 시 다시 프리필해 KV 재계산. 블록이 작으면 유리.

실험적으로 블록 16~64 구간에서는 둘의 E2E 성능이 비슷하고, 작은 블록에서는 재계산이, 큰 블록에서는 스와핑이 유리하다.

---

성능 결과: “많이 태워서(=batch) 많이 뽑는다(=throughput)”

• vLLM은 동일 지연에서 Orca(Oracle) 대비 1.7~2.7×, Orca(Max) 대비 2.7~8× 높은 요청률을 버팁니다. FasterTransformer 대비 최대 22×. 이유는 간단한데, 더 많은 요청을 한 번에 얹을 수 있게 메모리를 쪼개고 공유했기 때문입니다.
• 특히 긴 프롬프트/긴 시퀀스일수록 이득이 큽니다. 반대로 짧은 시퀀스 + 넉넉한 메모리 상황에서는 시스템이 compute-bound가 되며 이득이 줄어듭니다.

 

블록 크기, 어떻게 잡는 것이 좋을까?

블록 크기(block size) 설정은 vLLM에서 성능과 효율을 동시에 좌우하는 중요한 요소입니다.

• 너무 작게 잡으면: 병렬성이 떨어지고, GPU 메모리 접근 효율이 낮아집니다.
• 너무 크게 잡으면: 내부 단편화가 심해지고, KV 공유 기회가 줄어듭니다.

논문에서는 기본값을 16으로 권장합니다. 실제 실험에서도 ShareGPT는 16~128, Alpaca는 16~32 범위에서 안정적인 결과를 보입니다. 따라서 실무에서는 16으로 시작하여 필요할 경우 32까지 조정하는 방식이 가장 합리적입니다.

 

 

마무리 – 제 결론

vLLM의 핵심 성과는 사실 단순한 발상에서 시작합니다.

“KV 메모리를 운영체제의 가상 메모리처럼 다루자.”

 

이 단순한 접근이 LLM 서빙의 진짜 병목인 메모리 문제를 해결합니다. 모델 크기가 커지고 시퀀스가 길어질수록 vLLM은 더욱 강력해집니다. 저는 긴 프롬프트 + 샘플 여러 개 + 빔 서치 같은 워크로드에서는 vLLM을 기본값으로 설정합니다. (개꿀)

 

문제가 있긴 있습니다. 논문에서도 요청률이 시스템 용량을 넘어서는 순간, 지연 시간이 급격하게 폭발한다고 설명합니다. 하지만 그래도 핵심은 메모리를 효율적으로 관리하여 동시에 더 많은 요청을 처리하는 것입니다.

 

요청률 ↑  →  시스템 용량 초과  →  대기열 길이 ∞  →  지연(요청당/토큰당) 급증

 

 

읽어주셔서 감사합니다 ~~!!