5단계: PagedAttention — OS의 가상 메모리에서 힌트를 얻다
vLLM의 PagedAttention은 운영체제의 페이지 메모리 관리 기법을 어텐션 캐시에 적용한 것이다.
OS의 페이지 메모리
운영체제는 물리 메모리를 고정된 크기의 페이지(page)로 나눈다. 프로그램이 메모리를 요청하면 연속된 공간을 통째로 주는 것이 아니라, 사용 가능한 페이지를 필요한 만큼 끊어서 준다.
물리 메모리:
[페이지0: 사용중] [페이지1: 비어있음] [페이지2: 사용중]
[페이지3: 비어있음] [페이지4: 비어있음] [페이지5: 사용중]
프로세스 A가 3페이지 요청
→ 페이지1, 페이지3, 페이지4를 배정
→ 물리적으로 흩어져 있어도 가상 주소 공간에서는 연속해 보임
페이지 테이블(page table)이 가상 주소 → 물리 주소 변환을 담당한다. 프로세스는 연속된 메모리인 것처럼 사용하지만 실제로는 흩어진 물리 페이지들을 참조한다.
PagedAttention의 적용
PagedAttention은 KV Cache를 고정 크기의 블록(block)으로 나눈다. 각 블록은 고정된 수의 토큰(예: 16개)에 해당하는 K, V를 저장한다.
블록 크기: 16토큰
물리 블록 풀:
[블록0: 비어있음] [블록1: 비어있음] [블록2: 비어있음]
[블록3: 비어있음] [블록4: 비어있음] [블록5: 비어있음]
"안녕하세요 반갑습니다" (6토큰) 처리 시:
블록 1개 요청 (16 슬롯, 6만 사용)
→ 블록0 배정
블록 테이블:
논리 블록 0 → 물리 블록 0
물리 블록 0: [K₁V₁][K₂V₂][K₃V₃][K₄V₄][K₅V₅][K₆V₆][빈슬롯×10]
생성이 진행되어 토큰이 16개를 초과하면 새 블록을 배정한다.
17번째 토큰 등장:
→ 블록1 새로 배정
블록 테이블:
논리 블록 0 → 물리 블록 0 (토큰 1~16)
논리 블록 1 → 물리 블록 1 (토큰 17~)
물리 블록은 GPU 메모리 어디에 있든 상관없다. 블록 테이블이 매핑을 관리한다.
여러 요청이 동시에 들어올 때
요청 A: "안녕하세요 반갑습니다" → 블록0
요청 B: 50토큰짜리 다른 질문 → 블록1, 블록2, 블록3
요청 C: 8토큰짜리 짧은 질문 → 블록4
블록 테이블:
요청A: 논리블록0 → 물리블록0
요청B: 논리블록0 → 물리블록1
논리블록1 → 물리블록2
논리블록2 → 물리블록3
요청C: 논리블록0 → 물리블록4
기존 방식이라면 각 요청에 max_model_len만큼의 연속 공간을 예약했을 것이다. PagedAttention은 실제로 필요한 블록만 배정하고, 그 블록들이 물리적으로 흩어져 있어도 블록 테이블로 논리적인 연속성을 제공한다.
6단계: 메모리 낭비가 줄어드는 구체적인 계산
기존 방식 vs PagedAttention
시나리오: A100 40GB, LLaMA-2-13B, max_model_len=2048
기존 방식에서 동시 요청 4개를 처리한다고 하면:
모델 가중치: ~26GB
KV Cache 예약:
요청 1: 2048 토큰 × 0.78MB = 1.6GB (실제 사용: 6토큰)
요청 2: 2048 토큰 × 0.78MB = 1.6GB (실제 사용: 50토큰)
요청 3: 2048 토큰 × 0.78MB = 1.6GB (실제 사용: 8토큰)
요청 4: 2048 토큰 × 0.78MB = 1.6GB (실제 사용: 100토큰)
총 KV Cache: 6.4GB
실제 사용량: (6 + 50 + 8 + 100) × 0.78MB ≈ 127MB
낭비: 6.4GB - 127MB ≈ 6.27GB (낭비율 98%)
PagedAttention에서는:
모델 가중치: ~26GB
KV Cache (블록 크기 16):
요청 1: 1블록 (6토큰, 10슬롯 낭비)
요청 2: 4블록 (50토큰)
요청 3: 1블록 (8토큰, 8슬롯 낭비)
요청 4: 7블록 (100토큰)
총 13블록 × 16토큰 × 0.78MB/토큰 ≈ 162MB
낭비: 블록 내부 미사용 슬롯 (18슬롯) ≈ 14MB
낭비율: 약 9%
같은 GPU로 처리할 수 있는 동시 요청 수가 크게 늘어난다. vLLM 논문에서는 기존 시스템 대비 처리량이 최대 24배 향상된다고 보고한다.
7단계: Prefill과 Decode — 두 가지 처리 단계
Prefill
입력 토큰 전체를 한 번에 처리하는 단계다. "안녕하세요 반갑습니다" 6개 토큰을 동시에 모델에 넣는다.
Prefill:
입력: [안녕, 하, 세요, 반갑, 습, 니다]
동시 처리:
안녕 → Q₁, K₁, V₁ 계산
하 → Q₂, K₂, V₂ 계산
세요 → Q₃, K₃, V₃ 계산
반갑 → Q₄, K₄, V₄ 계산
습 → Q₅, K₅, V₅ 계산
니다 → Q₆, K₆, V₆ 계산
K₁~K₆, V₁~V₆ → KV Cache에 저장
출력: 다음 토큰 예측값 (예: ".")
모든 입력 토큰을 병렬로 처리하므로 GPU 사용률이 높다. 계산 집약적(compute-bound)인 단계다.
Decode
Prefill 이후 토큰을 한 개씩 생성하는 단계다.
Decode 스텝 1:
입력: "." (새로 예측된 토큰)
KV Cache에서 K₁~K₆, V₁~V₆ 읽어옴
"."의 K₇, V₇ 계산 후 저장
출력: 다음 토큰 예측 (예: <종료>)
Decode 스텝 2:
<종료> 토큰 확인 → 생성 완료
매 스텝마다 새 토큰 1개만 처리하므로 GPU 계산이 적다. 대신 KV Cache를 읽어오는 메모리 대역폭이 병목이 된다. 메모리 집약적(memory-bound)인 단계다.
continuous batching
vLLM은 여러 요청을 동시에 처리하면서 Decode 단계의 GPU 활용률을 높인다.
GPU 처리 타임라인:
t=0: [요청A Prefill] [요청B Prefill] [요청C Prefill]
t=1: [요청A Decode-1] [요청B Decode-1] [요청C Decode-1] [요청D Prefill]
t=2: [요청A Decode-2] [요청B Decode-2] [요청C 완료→제거] [요청D Decode-1] [요청E Prefill]
한 요청이 끝나면 그 자리에 새 요청을 바로 집어넣는다. 기존 방식에서는 배치 전체가 끝날 때까지 기다렸다. continuous batching은 GPU를 쉬지 않게 한다.
전체 흐름 요약
"안녕하세요 반갑습니다"
↓
[토크나이저]
["안녕", "하", "세요", "반갑", "습", "니다"]
[12847, 589, 3301, 15622, 441, 1037]
↓
[임베딩]
각 토큰 ID → 2048차원 벡터
↓
[Prefill — 36개 레이어 × Attention 반복]
각 토큰의 Q, K, V 계산
K, V를 KV Cache에 저장 (PagedAttention: 블록 단위)
마지막 토큰의 출력 → 다음 토큰 예측
↓
[Decode 루프]
새 토큰 → K, V 계산 → 캐시에 추가
KV Cache에서 이전 K, V 읽어와 Attention 계산
다음 토큰 예측
종료 토큰 나올 때까지 반복
↓
생성 완료
vLLM이 높은 처리량을 달성하는 핵심은 두 가지다.
- KV Cache: 이미 계산한 K, V를 재사용해 중복 계산을 없앤다.
- PagedAttention: OS의 페이지 메모리 관리를 적용해 KV Cache의 메모리 낭비를 최소화하고, 같은 메모리로 더 많은 요청을 동시에 처리한다.
"안녕하세요 반갑습니다"라는 짧은 문장도 이 모든 과정을 거친다.
Step 5: PagedAttention — Bringing OS Paging to the GPU
Operating Systems Already Solved This Problem
Decades ago, computer operating systems faced the same issue. Pre-allocating a contiguous memory region for each program leads to severe waste and conflicts. Two programs that need the same address range simply cannot coexist.
OSes solved this with virtual memory and paging.
The idea behind OS paging:
Physical memory is divided into fixed-size units called "pages." Each program works with "logical addresses," and a page table translates those logical addresses into actual physical addresses. Memory that is physically scattered appears logically contiguous.
Logical address space seen by Program A: [0x0000 ~ 0x3FFF]
Actual physical memory locations:
Logical 0x0000~0x0FFF → Physical page 47
Logical 0x1000~0x1FFF → Physical page 12 (elsewhere)
Logical 0x2000~0x2FFF → Physical page 89 (somewhere else entirely)
The program treats its memory as contiguous; the OS tracks the scattered physical locations.
PagedAttention in vLLM
PagedAttention (Kwon et al., 2023) applies this same idea to KV cache management.
GPU memory is divided into fixed-size units called KV blocks. vLLM's default block size holds the K and V tensors for 16 tokens.
GPU memory partitioned into blocks:
[Block 0][Block 1][Block 2][Block 3]...[Block N]
Each block: can store KV for 16 tokens
A block table maps each request's logical block numbers to physical blocks.
Processing the "안녕하세요 반갑습니다" request (6 tokens):
Physical block 42 allocated:
Slot 0: 안녕 K₁, V₁
Slot 1: 하 K₂, V₂
Slot 2: 세요 K₃, V₃
Slot 3: 반갑 K₄, V₄
Slot 4: 습 K₅, V₅
Slot 5: 니다 K₆, V₆
Slots 6~15: empty (reserved for future generated tokens)
Block table for this request:
Logical block 0 → Physical block 42
When another request arrives on the same GPU simultaneously:
Block table for Request B:
Logical block 0 → Physical block 7 (assigned to any free block)
Logical block 1 → Physical block 23 (physical blocks need not be contiguous)
Logical block 2 → Physical block 61
Because the block table tracks each physical block's location regardless of where it sits, contiguous placement is unnecessary.
Memory Usage: Static Reservation vs. PagedAttention
Static reservation (contiguous pre-allocation):
GPU memory (100 blocks, max_model_len=2048, block size=16 tokens):
┌──────────────────────────────────┬──────────────────────────────────┐
│ Request A: blocks 0~63 reserved │ Request B: blocks 64~127 reserved │
│ Actual use: part of block 0 (6 tokens) │ Actual use: part of block 64 (8 tokens) │
│ Wasted: ~63 blocks │ Wasted: ~63 blocks │
└──────────────────────────────────┴──────────────────────────────────┘
Memory waste > 98%
PagedAttention:
GPU memory (100 blocks):
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│A:0│B:0│free│B:1│free│free│C:0│free│free│B:2│
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
Each request gets exactly as many blocks as it needs, allocated anywhere free.
Block tables:
Request A: [logical 0 → physical 0]
Request B: [logical 0 → physical 1] [logical 1 → physical 3] [logical 2 → physical 9]
Request C: [logical 0 → physical 6]
Why Waste Stays Below 4%
In PagedAttention, waste occurs in exactly one place: the last block of each request.
For a 6-token request with a block size of 16:
Last block (block 0):
Used slots: 6 (안녕, 하, 세요, 반갑, 습, 니다)
Empty slots: 10 ← this is the only waste
For a 32-token request:
Block 0: 16 tokens, fully packed → no waste
Block 1: 16 tokens, fully packed → no waste
Total waste: 0
For a 17-token request:
Block 0: 16 tokens, fully packed → no waste
Block 1: 1 token used, 15 slots empty → waste
Maximum waste: block size - 1 = 15 slots
As the number of requests grows, the average waste per request converges to less than half a block. That is why waste stays below 4%, compared to 60–80% with static reservation — a dramatic difference.
Step 6: Prefill and Decode — Two Phases of Inference
Prefill: Processing All Input Tokens at Once
In the prefill phase, all input tokens are processed in parallel. Because the GPU can perform many computations simultaneously, all 6 tokens are handled in a single pass rather than one at a time.
Input: [안녕, 하, 세요, 반갑, 습, 니다]
↓ ↓ ↓ ↓ ↓ ↓
(6 tokens processed in parallel — 36 layers)
↓
K₁~K₆, V₁~V₆ written to KV cache
↓
First output token predicted: "."
This phase is compute-bound — it fully saturates the GPU's arithmetic throughput.
Block allocation happens at the start of prefill. For 6 tokens, one block (capacity: 16 tokens) is allocated: ⌈6 ÷ 16⌉ = 1 block.
Decode: Generating One Token at a Time
After the first output token is produced, subsequent tokens are generated one at a time. Each step's output becomes the next step's input.
Step 1:
Q₇ of new token "." × K₁~K₆ in KV cache → attention scores
Next token predicted
K₇, V₇ → appended to KV cache (stored in slot 6 of block 42)
Step 2:
Q₈ of new token × K₁~K₇ in KV cache → attention scores
...
Block 42 slot usage:
[0:안녕][1:하][2:세요][3:반갑][4:습][5:니다][6:.][7:new token][empty...]
Decode is memory-bound — every step requires reading the entire KV cache from GPU memory, making memory bandwidth the bottleneck rather than compute.
When the KV cache grows beyond a block boundary during decode:
Token count exceeds 16 → allocate a new physical block
Add mapping logical block 1 → physical block X to the block table
Continue generation
Blocks are not allocated all at once upfront; they are allocated on demand as needed.
Step 7: End-to-End Flow for "안녕하세요 반갑습니다"
This section ties all the concepts together and traces the full request from start to finish.
Complete Processing Sequence
1. API request received
POST http://localhost:8000/v1/chat/completions
{
"model": "Qwen/Qwen3-4B",
"messages": [{"role": "user", "content": "안녕하세요 반갑습니다"}]
}
2. Tokenization
"안녕하세요 반갑습니다"
↓
[12847, 589, 3301, 15622, 441, 1037]
(안녕, 하, 세요, 반갑, 습, 니다)
3. Scheduler — block allocation
vLLM's scheduler allocates blocks for the request.
Found one free block in the block pool: physical block 42
Block table created:
Logical block 0 of this request → Physical block 42
4. Prefill
6 tokens processed in parallel (on GPU):
Embedding: [12847, 589, 3301, 15622, 441, 1037] → 2048-dim vector each
Attention computed across 36 layers
K, V for each layer → stored in physical block 42:
Slot 0: 안녕 K/V
Slot 1: 하 K/V
Slot 2: 세요 K/V
Slot 3: 반갑 K/V
Slot 4: 습 K/V
Slot 5: 니다 K/V
Slots 6~15: empty
First output token predicted: "."
5. Decode begins
Step 1 — processing ".":
Q of "." × K in slots 0~5 of block 42 → attention scores
Attention computed
K/V of "." → stored in slot 6 of block 42
Next token predicted: <EOS>
Block 42 state:
[안녕][하][세요][반갑][습][니다][.][empty][empty]...[empty]
6. Termination check
EOS token predicted → generation ends.
7. Response returned and blocks freed
Response returned: "안녕하세요 반갑습니다."
Physical block 42 released → returned to block pool
→ immediately available for reuse by another request
Step 8: Continuous Batching — Serving Multiple Requests Simultaneously
The Old Approach — Wait for the Whole Batch
Traditional batch inference follows a simple rule: don't accept new requests until every request in the current batch has finished.
Batch 1: [Request A (5 tokens to generate), Request B (50 tokens), Request C (3 tokens)]
A finishes quickly → waits
C finishes quickly → waits
B finishes slowly → batch 1 ends
While waiting, requests D, E, F cannot be processed until B is done.
GPU sits idle after A and C complete.
While B generates a long response, half the GPU's slots are unused.
Continuous Batching in vLLM
As soon as a request finishes, its slot is immediately filled with a new request.
Batch slots: [Request A, Request B, Request C]
↓
A finishes → slot freed immediately → [Request D, Request B, Request C]
↓
C finishes → slot freed immediately → [Request D, Request B, Request E]
↓
D finishes → slot freed immediately → [Request F, Request B, Request E]
↓
...continuously filled
GPU slots are filled with new requests without any idle time.
PagedAttention is what makes this possible. Because each request's KV cache lives in independent physical blocks, completing request A means only A's blocks need to be freed, and the newly available space can be immediately assigned to request D. There is no per-request contiguous reservation to deal with.
This design is one of the primary drivers behind the up to 23× throughput improvement over prior systems.
Step 9: Prefix Caching — Sharing a Common Prompt
When Many Users Share the Same System Prompt
In production, all users typically share the same system prompt.
System prompt: "당신은 친절한 AI 어시스턴트입니다. 항상 한국어로 답변하세요."
→ Tokenized: [당신은, 친절한, AI, 어시스턴트, 입니다, 항상, 한국어로, 답변하세요] (8 tokens)
User A: system prompt + "안녕하세요 반갑습니다"
User B: system prompt + "오늘 날씨가 어때요?"
User C: system prompt + "파이썬 코드 좀 도와줘"
The KV cache for those 8 system-prompt tokens is identical across all three requests. Recomputing and storing them independently for each request is pure waste.
Safe Sharing with Copy-on-Write
PagedAttention lets multiple requests share the physical blocks that hold the common prompt prefix. Each block tracks a reference count.
System prompt (8 tokens) → stored in physical block 5
Reference count: 3 (A, B, and C all reference it)
Block table for Request A: [logical 0 → physical block 5] [logical 1 → physical block 12]
Block table for Request B: [logical 0 → physical block 5] [logical 1 → physical block 37]
Block table for Request C: [logical 0 → physical block 5] [logical 1 → physical block 61]
Block 5 is shared read-only across all three requests.
When a new token is generated — i.e., when something must be written to the block — copy-on-write kicks in. At the moment of the write, the block is copied into a new physical block, the requesting request's block table is updated to point to the new block, and block 5 for the other requests remains untouched.
This approach reduces memory usage by 55% and increases throughput by 2.2× for parallel sampling (generating multiple responses from the same prompt).
Summary — All Concepts at a Glance
| Concept | Role | Analogy |
|---|---|---|
| Token | Smallest unit the model processes | LEGO brick |
| Embedding | Converts token ID to a semantic vector | Describing a brick by its color and shape |
| Q (Query) | Information the current token is looking for | A search query at a library |
| K (Key) | Index descriptor for each token | Index card for a book |
| V (Value) | Actual semantic content of each token | The book's content |
| Causal attention | Can only attend to previous tokens | Only referencing pages already read |
| KV cache | Stores computed K and V for reuse | Notes taken while reading |
| Prefill | Processes all input tokens in parallel | Reading the entire book in one pass |
| Decode | Generates output tokens one at a time | Taking dictation one character at a time |
| Static contiguous reservation | Pre-allocates space up to max length | Booking a 500-person hall for 50 guests |
| KV block | Fixed-size unit of GPU memory | A single parking space |
| Block table | Maps logical blocks to physical blocks | A note of where you parked |
| PagedAttention | Block-level KV cache management | Parking in whatever space is free |
| Continuous batching | Immediately fills completed slots with new requests | Seating the next guest the moment one leaves |
| Prefix caching | Multiple requests share common blocks | Sharing a single textbook among many readers |
| Copy-on-Write | Copies a shared block only when a write occurs | Copying a passage into your own notes only when you need to annotate it |
The reason vLLM achieves up to 24× higher throughput than HuggingFace Transformers on the same GPU comes down to this architecture: KV cache waste held below 4%, the freed memory used to serve more concurrent requests, and continuous batching eliminating GPU idle time — three mechanisms that reinforce each other.
Appendix: The Attention Score Formula
The attention score is computed as follows:
Attention(Q, K, V) = softmax( Q × Kᵀ / √d ) × V
Q × Kᵀ: Dot product of the current token's Query against every previous token's Key, producing a matrix of similarity scores./ √d: Divides by the square root of the dimensiondto stabilize the score magnitudes, correcting for the tendency of dot products to grow large in high-dimensional spaces.softmax(...): Normalizes all scores so they sum to 1, yielding a weight distribution over tokens.× V: Computes a weighted sum of the Value vectors using the normalized weights.
In PagedAttention, this operation is carried out by traversing physically scattered blocks via the block table — fetching the Keys from each block, computing partial scores, updating a running softmax normalization, multiplying the normalized weights by the Values, and accumulating the results, one block at a time.