3-2편. Prefill, Decode, KV Cache

Gyullbb·2026년 8월 15일

LLM

목록 보기
4/7

3-1편에서는 LLM을 실제 서비스로 제공하기 위해 어떤 문제를 해결해야 하는지 전체 지도를 그렸다. Request를 받고, Tokenization을 거치고, 여러 요청을 관리하고, GPU에서 모델을 실행한 뒤 Streaming으로 결과를 전달한다. 그리고 Quantization, Batching, Speculative Decoding, KV Cache 등 다양한 최적화 방법도 살펴봤다.

그중에서도 계속 등장했던 개념이 KV Cache다.

왜 KV Cache를 별도로 깊게 다뤄야 할까? LLM Serving의 성능을 이해하려면 결국 다음 질문에 답할 수 있어야 하기 때문이다.

GPU에서 LLM은 실제로 무엇을 계산하고, 무엇을 메모리에서 읽고 있는가?

이 질문에 답하기 위해 LLM의 생성 과정을 Prefill과 Decode로 나누어 본다. 그리고 이 둘의 차이를 이해하면 왜 Prefill은 Compute-bound이고 Decode는 Memory-bound인가?라는 질문도 자연스럽게 풀린다.

1. Prefill과 Decode

1-1. Autoregressive Generation

LLM은 답변 전체를 한 번에 생성하지 않는다. 2편에서 Decoder-only Transformer를 설명하며 살펴봤듯, 다음 Token을 하나 생성하고 그 결과를 다시 입력으로 사용해 다음 Token을 생성하는 과정을 반복한다. 이를 Autoregressive Generation이라고 한다.

Serving 관점에서 보면 이 생성 과정은 크게 두 단계로 나뉜다.

Prompt
  ↓
┌──────────┐
│ Prefill  │
└──────────┘
  ↓
First Token
  ↓
┌──────────┐
│  Decode  │
└──────────┘
  ↓
Next Token → Next Token → ...

바로 Prefill과 Decode다.

1-2. Prefill — 입력 전체를 처리하는 단계

사용자가 긴 Prompt를 보냈다고 생각해보자.

Token 1
Token 2
...
Token 1000

Prefill 단계에서는 이 입력 전체를 모델에 한 번에 넣는다. 많은 Token을 GPU에서 병렬로 처리할 수 있다는 뜻이다.

T1 ─┐
T2 ─┤
... ├──→ Transformer → GPU
T1000┘

Attention, Linear Layer, FFN의 Matrix 연산이 대규모로 발생하기 때문에 GPU의 Compute 자원을 적극적으로 활용할 수 있다. 그래서 Prefill은 일반적으로 Compute-bound 특성을 가진다.

많은 Token → 대규모 Matrix 연산 → GPU Compute 활용 → Compute-bound

즉 Prefill에서는 GPU의 연산 능력이 중요한 요소가 된다.

1-3. Decode — 한 Token씩 생성하는 단계

Prefill이 끝나면 모델은 첫 번째 출력 Token을 생성한다. 그 이후부터는 Decode 단계다.

Decode에서는 한 번에 새로운 Token 하나만 생성한다. 따라서 Prefill과 달리 GPU에 들어가는 새로운 Token 수가 매우 적다.

그런데 새로운 Token을 생성하려면 이전 Token들의 Attention 정보를 참고해야 한다. 여기서 KV Cache가 등장한다.

2. KV Cache

2-1. KV Cache가 없다면?

Token 4를 생성하려면 이전 Token 1~3에 대한 Key와 Value를 계산해야 한다. Token 5를 생성할 때는 Token 1~4에 대한 Key와 Value를 다시 계산한다.

Step 1  T1
Step 2  T1 T2
Step 3  T1 T2 T3
Step 4  T1 T2 T3 T4
Step 5  T1 T2 T3 T4 T5

이미 계산한 K와 V를 매번 다시 계산하는 셈이다. 생성하는 Token이 길어질수록 이 반복은 커진다.

2-2. KV Cache가 있다면?

KV Cache는 이전 Token의 Key와 Value를 저장해둔다.

T1 → K1 V1
T2 → K2 V2
T3 → K3 V3
        ↓
     KV Cache

새로운 Token 4가 들어오면 그 Token에 대한 Q, K, V만 새로 계산한다.

T4 → Q4 K4 V4

그리고 이전 K/V는 Cache에서 그대로 가져와 사용한다.

             K1 V1
             K2 V2
Q4 ───────── K3 V3
             K4 V4

이전 Token의 K/V를 다시 계산할 필요가 없다는 것이 핵심이다.

이미 계산한 K와 V를 저장해두고, 다음 Decode Step에서 재사용한다.

2-3. Self-Attention은 서빙 관점에서 왜 비싼가

2편에서 살펴본 Self-Attention 수식을 다시 떠올려보자.

Attention(Q,K,V)=Softmax(QKTdk)VAttention(Q,K,V) = Softmax \left( \frac{QK^T}{\sqrt{d_k}} \right) V

이번에는 Q, K, V가 무엇인지가 아니라, 이 계산에 비용이 얼마나 드는지를 살펴본다.

시퀀스 길이를 LL, Head Dimension을 DD라고 하면, QKTQK^T 단계에서 모든 Query가 모든 Key와 내적을 계산한다.

        K1 K2 K3 ... KL
Q1      ●  ●  ●  ... ●
Q2      ●  ●  ●  ... ●
Q3      ●  ●  ●  ... ●
...
QL      ●  ●  ●  ... ●

즉 L×LL \times L개의 Token 쌍을 계산하고, 각 내적은 DD차원 연산이므로 Attention의 핵심 계산량은 대략

O(L2D)O(L^2D)

로 증가한다. 여기서 중요한 것은 L2L^2다.

Sequence Length  2L
Attention 관계    4배

시퀀스 길이가 2배가 되면 Token 간 관계의 수는 대략 4배가 된다. 따라서 Context가 길어질수록 Attention 계산 비용은 빠르게 늘어난다.

Autoregressive Decode에서는 문제가 더 커진다.

LLM은 Token을 하나씩 생성하기 때문에, 새로운 Token을 만들 때마다 이전 Token들과의 Attention을 계산해야 한다. KV Cache가 없다면 이전 Token들의 K와 V까지 매번 다시 계산해야 하므로, 이미 했던 계산을 계속 반복하게 된다. 이것이 Decode에서 KV Cache가 중요한 이유다.

2-4. KV Cache는 정확히 무엇을 줄이는가

여기서 정확히 짚어야 할 점이 있다. KV Cache가 Attention의 모든 계산을 O(LD)O(LD)로 만들어버리는 것은 아니다. 새로운 Token 하나를 생성할 때도 현재까지 존재하는 모든 Key와 새로운 Query의 관계는 계산해야 하므로, 해당 Decode Step의 Attention 계산량은 대략

O(LD)O(LD)

이다. KV Cache가 줄이는 것은 이전 Token들의 K/V를 다시 계산하는 반복 작업이다.

KV Cache 없음 → 이전 Token들의 K/V를 반복 계산
KV Cache 있음 → 이전 K/V는 저장된 값을 재사용, 새 Token의 K/V만 계산

따라서 생성 과정 전체에서 불필요한 반복 계산을 크게 줄일 수 있다.

2-5. 실제로 얼마나 차이가 날까

이론적으로 KV Cache가 반복적인 K/V 계산을 줄인다는 것을 확인했다. 그렇다면 실제 Inference에서는 어느 정도의 차이가 발생할까?

간단한 실험을 통해 확인해보자.

실험에서는 모델, GPU, Prompt를 동일하게 유지하고 use_cache 옵션만 변경한다.

고정 조건 : 모델, GPU, Prompt, Sampling 방식
변경 조건 : use_cache = False ↔ True
측정 방법 : 전체 Generation Wall-clock Time

여기서 생성 Token 수를 여러 단계로 변경해보면 KV Cache의 효과가 생성 길이에 따라 어떻게 달라지는지도 확인할 수 있다.

실험 환경

GPU가 없어도 Google Colab의 GPU Runtime을 사용하면 간단하게 테스트할 수 있다. 실험용 모델로는 Qwen/Qwen2.5-0.5B-Instruct를 사용한다.

Colab에서 Runtime → Change runtime type → GPU를 선택한 뒤 다음 코드를 실행한다.

먼저 GPU와 필요한 라이브러리를 확인한다.

!nvidia-smi
!pip install -q -U transformers accelerate

이후 모델을 불러온다.

import torch
import time
import pandas as pd
import matplotlib.pyplot as plt

from transformers import AutoTokenizer, AutoModelForCausalLM

MODEL_NAME = "Qwen/Qwen2.5-1.5B-Instruct"

device = "cuda" if torch.cuda.is_available() else "cpu"

print("Device:", device)

if device == "cuda":
    print("GPU:", torch.cuda.get_device_name(0))

tokenizer = AutoTokenizer.from_pretrained(MODEL_NAME)

model = AutoModelForCausalLM.from_pretrained(
    MODEL_NAME,
    torch_dtype=torch.float16 if device == "cuda" else torch.float32,
)

model = model.to(device)
model.eval()

print("Model loaded.")

실험에 사용할 prompt도 고정한다.

prompt = """
Explain why GPUs are particularly suitable for Transformer-based
large language model inference. Focus on matrix multiplication,
parallelism, and memory usage.
"""

inputs = tokenizer(
    prompt,
    return_tensors="pt"
).to(device)

input_tokens = inputs["input_ids"].shape[1]

print("Input tokens:", input_tokens)

GPU에서는 실제 연산이 비동기적으로 실행될 수 있기 때문에, 정확한 시간을 측정하려면 GPU 연산이 끝날 때까지 기다린 후 시간을 측정해야 한다. 따라서 torch.cuda.synchronize()를 사용한다.

또한 첫 실행에는 CUDA 초기화 등의 오버헤드가 포함될 수 있으므로 먼저 Warm-up을 수행한다.

print("Warm-up...")

with torch.no_grad():
    _ = model.generate(
        **inputs,
        max_new_tokens=20,
        do_sample=False,
        use_cache=True,
    )

if device == "cuda":
    torch.cuda.synchronize()

print("Warm-up complete.")

이제 use_cache=False와 use_cache=True의 실행 시간을 측정하는 함수를 만든다.

def benchmark(use_cache, max_new_tokens, runs=3):

    times = []
    generated_tokens = None

    for _ in range(runs):

        if device == "cuda":
            torch.cuda.synchronize()

        start = time.perf_counter()

        with torch.no_grad():
            output = model.generate(
                **inputs,
                max_new_tokens=max_new_tokens,
                do_sample=False,
                use_cache=use_cache,
            )

        if device == "cuda":
            torch.cuda.synchronize()

        end = time.perf_counter()

        times.append(end - start)

        generated_tokens = (
            output.shape[1] - inputs["input_ids"].shape[1]
        )

    avg_time = sum(times) / len(times)

    return {
        "use_cache": use_cache,
        "max_new_tokens": max_new_tokens,
        "generated_tokens": generated_tokens,
        "time_sec": avg_time,
        "tokens_per_sec": generated_tokens / avg_time,
    }

이제 생성 Token 수를 20, 50, 100, 200, 400으로 바꿔가며 각각 측정한다.

results = []

token_lengths = [20, 50, 100, 200, 400]

for token_length in token_lengths:

    print(f"\n===== {token_length} tokens =====")

    result_no_cache = benchmark(
        use_cache=False,
        max_new_tokens=token_length,
        runs=3,
    )

    result_cache = benchmark(
        use_cache=True,
        max_new_tokens=token_length,
        runs=3,
    )

    results.append(result_no_cache)
    results.append(result_cache)

    print(
        f"No Cache : "
        f"{result_no_cache['time_sec']:.3f}s"
    )

    print(
        f"Cache    : "
        f"{result_cache['time_sec']:.3f}s"
    )

    print(
        f"Speedup  : "
        f"{result_no_cache['time_sec'] / result_cache['time_sec']:.2f}x"
    )

생성 Token 수와 KV cache 유무에 따른 실행 시간을 확인하면 다음과 같다.

indexGenerated TokensNo Cache (sec)KV Cache (sec)Speedup
0201.93791926299998821.43296465966659531.352384547606973
1502.20165499800001862.22759187166661830.9883565414309066
21004.52848889933337254.1097222406666181.1018965842807977
32009.2260877660000158.2485789853333241.1185063248354394
440024.92411970400000216.1415059103333081.5441012655482367

결과를 통해 확인할 수 있듯이 use_cache=False에서는 Decode 과정에서 이전 Token들의 K/V를 반복적으로 계산해야 하므로 생성 길이가 길어질수록 불필요한 계산이 누적된다.
use_cache=True에서는 이전 Token의 K/V를 재사용하기 때문에 생성 길이가 증가해도 K/V를 매번 처음부터 계산하는 비용을 피할 수 있다.

다만 해당 실험은 1.5B의 작은 모델로 테스트를 수행했다.
모델 규모가 작거나 GPU에서 수행되는 다른 연산의 비중이 큰 경우에는 KV Cache가 줄여주는 계산량이 전체 실행 시간에서 차지하는 비중이 작을 수 있어, 실험 결과는 GPU와 모델에 따라 달라질 수 있다.
또한 이 실험에서 측정한 전체 시간에는 K/V 계산 외에도 Attention, Feed Forward Network, GPU Kernel 실행 등의 시간이 모두 포함되어 있다. 따라서 측정된 전체 시간의 차이를 모두 KV 계산 비용이라고 해석해서는 안 된다.

2-6. KV Cache에도 대가가 있다

KV cache는 계산을 줄이는 대신 메모리를 사용한다. 각 Transformer Layer에서 계산된 Key와 Value를 저장해야 하기 때문이다. KV Cache가 사용하는 메모리는 대략 다음과 같이 표현할 수 있다.

MemoryKV=2×Nlayers×NKV-heads×Dhead×L×B×BytesMemory_{KV} = 2 \times N_{layers} \times N_{KV\text{-}heads} \times D_{head} \times L \times B \times Bytes

각 항은 다음을 의미한다.

  • 22 : Key와 Value
  • NlayersN_{layers} : Transformer Layer 수
  • NKV-headsN_{KV\text{-}heads} : K/V Head 수
  • DheadD_{head} : Head Dimension
  • LL : Sequence Length
  • BB : Batch Size
  • BytesBytes : 데이터 정밀도에 따른 바이트 수

여기서 중요한 것은

MemoryKV∝L×BMemory_{KV} \propto L \times B

라는 점이다. Context가 길어지고 동시에 처리하는 요청이 많아질수록 KV Cache는 빠르게 커진다. 실제 GPU Memory에는

Model Weights + KV Cache + Activation + Runtime / Framework Memory

등이 함께 존재한다. 따라서 LLM Serving에서 GPU Memory를 계산할 때는 모델의 파라미터 크기만 봐서는 안 된다.

3. Compute-bound vs Memory-bound

3-1. Prefill은 Compute-bound, Decode는 Memory-bound

앞서 KV cache 유무를 통해 확인한 계산량 차이를 그대로 병목에 대응시켜보면, 왜 Prefill과 Decode가 서로 다른 자원에서 막히는지가 자연스럽게 드러난다.

Prefill은 한 번에 많은 Token(LL개)을 처리하며 O(L2D)O(L^2D)의 Matrix Multiplication을 대규모로 수행한다. GPU의 연산 유닛을 높은 수준으로 활용할 수 있는 구조이므로, Prefill은 일반적으로 Compute-bound다. 이 구간에서는 GPU의 FLOPS와 Kernel 효율이 중요한 요소가 된다.

New Token
    ↓
    Q
    │
    └──────→ KV Cache
              ├ K1 V1
              ├ K2 V2
              ├ ...
              └ Kn Vn

반면 Decode는 Step마다 새로 계산하는 Token이 하나뿐이라 연산량은 O(LD)O(LD)로 작다. 하지만 그 하나를 계산하기 위해 지금까지 쌓인 KV Cache 전체를 GPU Memory에서 읽어와야 한다. 즉

작은 Compute(새 Token 1개) + 큰 Memory Access(KV Cache 전체) → Memory-bound

Context가 길어질수록 읽어야 하는 KV Cache는 계속 커지는데, 새로 계산하는 연산량은 그대로이므로 병목은 Compute가 아니라 Memory Bandwidth와 Memory Access로 옮겨간다. 이것이

Prefill = Compute-bound
Decode = Memory-bound

라고 말하는 이유다.

3-2. 왜 이 구분이 중요한가 — 병목을 어떻게 진단할까

병목이 다르면 최적화 방법도 달라진다. Prefill이 병목이라면 GPU Compute를 효율적으로 쓰는 것이 중요하다. Decode가 병목이라면 단순히 Compute 성능을 높이는 것만으로는 충분하지 않고,

KV Cache 메모리 효율
Memory Bandwidth
Quantization
Attention Kernel
Batching

등을 함께 고려해야 한다.

LLM Serving에서 GPU를 더 많이 쓰는 것이 항상 성능 향상으로 이어지지는 않는다.

그렇다면 실제 서비스에서 지금 어느 쪽이 병목인지는 어떻게 확인할까? 3-1편에서 다룬 TTFT/TPOT를 이 구분에 그대로 대응시키면 된다.

첫 번째 Token이 늦게 나온다면? TTFT를 확인한다. 긴 Prompt를 처리하는 Prefill이 오래 걸릴 수도 있고, Queue에서 요청이 오래 기다리고 있을 수도 있다.

첫 번째 Token은 빠른데 이후 생성이 느리다면? TPOT를 확인한다. Decode 단계의 KV Cache 접근이나 Memory Bandwidth가 병목일 수 있다.

전체 처리량이 낮다면? 다음 요소를 함께 확인한다.

Batch Size
Continuous Batching
KV Cache Memory
GPU Memory Bandwidth
Quantization
Scheduler

성능 문제를 해결하려면 먼저 어느 단계가 병목인지 분리해서 생각해야 한다.

4. KV Cache 메모리 관리 — 문제와 해결

4-1. Fragmentation — KV Cache가 커지면서 생기는 또 다른 메모리 문제

지금까지 다룬 Memory 문제는 "데이터를 얼마나 빠르게 읽어오는가", 즉 Bandwidth였다. 그런데 여러 요청을 동시에 처리하는 Serving 환경에서는 "그 데이터를 GPU Memory 어디에 저장할 것인가"라는 전혀 다른 메모리 문제가 하나 더 있다. KV Cache는 요청마다 별도로 존재한다.

Request A → KV Cache A
Request B → KV Cache B
Request C → KV Cache C

문제는 요청마다 길이가 다르다는 것이다.

A → 100 tokens
B → 1000 tokens
C → 5000 tokens

그래서 KV Cache를 GPU Memory에 효율적으로 배치하기 어렵다. 특히 요청마다 필요한 메모리 크기가 계속 변하면 메모리 공간에 빈틈이 생길 수 있다. 이를 Memory Fragmentation이라고 한다. 결국 GPU Memory에 충분한 총 공간이 남아 있어도, 필요한 형태로 메모리를 할당하지 못해 새로운 요청을 받지 못하는 상황이 생길 수 있다.

4-2. PagedAttention

이 문제를 해결하기 위한 대표적인 아이디어가 PagedAttention이다. PagedAttention은 KV Cache를 하나의 큰 연속된 메모리 공간이 아니라 작은 Block 단위로 나누어 관리한다.

Logical KV Cache (Request A)
┌────┬────┬────┬────┐
│ A1 │ A2 │ A3 │ A4 │
└────┴────┴────┴────┘

이 Block들이 GPU Memory에서 반드시 연속적으로 존재할 필요는 없다.

GPU Memory
┌────┬────┬────┬────┬────┬────┬────┬────┐
│ A2 │ B1 │ A4 │ C1 │ B3 │ A1 │ B2 │ A3 │
└────┴────┴────┴────┴────┴────┴────┴────┘

Logical Block과 Physical Memory Block의 매핑을 관리하기 때문에 GPU Memory를 더 유연하게 쓸 수 있다. 결과적으로 메모리 낭비를 줄이고 더 많은 요청을 동시에 처리할 수 있다.

5. KV Cache를 줄이는 최적화 기법들

5-1. KV Cache를 줄이는 아키텍처 — MQA, GQA

KV Cache가 너무 커진다면 Serving 단계에서만 해결할 필요는 없다. 모델의 Attention 구조 자체를 바꾸는 방법도 있다. 대표적인 것이 Multi-Query Attention(MQA)과 Grouped-Query Attention(GQA)이다.

일반적인 Multi-Head Attention에서는 각 Query Head마다 대응하는 K/V Head가 존재한다.

MHA
Q1 → K1 V1
Q2 → K2 V2
Q3 → K3 V3
Q4 → K4 V4

MQA에서는 여러 Query Head가 K/V를 공유한다.

Q1 ─┐
Q2 ─┤
Q3 ─┼→ K V
Q4 ─┘

저장해야 하는 K/V의 수가 줄어든다. GQA는 MHA와 MQA의 중간 형태로, 여러 Query Head가 하나의 K/V Group을 공유한다.

Q1 Q2 → K1 V1
Q3 Q4 → K2 V2

KV Cache 문제는 Serving Engine뿐 아니라 모델 아키텍처에서도 해결할 수 있다.

5-2. FlashAttention — Memory Access 자체를 최적화하다

Attention의 문제는 연산량(O(L2D)O(L^2D))만이 아니다. 1편에서 CPU를 다루며 봤듯, 메모리는 항상 "빠르지만 작은 것"과 "느리지만 큰 것"의 계층으로 나뉜다(Register → Cache → DRAM). GPU도 마찬가지다. SM 안의 Register/Shared Memory/L1 Cache처럼 아주 빠르지만 용량이 작은 SRAM(On-chip Memory)이 있고, 그 바깥에 모델 Weight와 KV Cache 같은 큰 데이터가 실제로 저장되는 크지만 상대적으로 느린 HBM(GPU Memory)이 있다. 실제 성능은 이 둘 사이에서 데이터를 얼마나 적게, 효율적으로 옮기느냐에 좌우된다.

문제 — Naive Attention은 HBM을 몇 번이나 오간다

일반적인(Naive) Attention 구현은 수식 그대로 단계별로 계산하면서, 각 단계의 중간 결과를 매번 HBM에 썼다가 다시 읽는다.

Q, K, V (HBM)
     │
     ▼  read
S = QK^T          ── L×L 행렬 ──▶  write HBM
     │
     ▼  read
P = softmax(S)    ── L×L 행렬 ──▶  write HBM
     │
     ▼  read
O = PV                          ▶  write HBM

여기서 SS, PP는 모두 L×LL \times L 크기의 행렬이다. Sequence가 길어질수록 이 행렬을 HBM에 쓰고 다시 읽는 비용 자체가 커진다. 즉 Attention은 연산량뿐 아니라 HBM Read/Write 횟수 때문에도 느려질 수 있다.

해결 — Tiling과 Online Softmax

FlashAttention은 SS, PP 같은 L×LL \times L 크기의 중간 행렬을 한 번도 HBM에 만들지 않는다. 대신 Q, K, V를 작은 Block으로 잘라 SRAM에 올리고, 그 Block 안에서 Attention 계산을 전부 끝낸 뒤 결과만 HBM에 쓴다.

Q ─▶ [Q1][Q2][Q3]...
K ─▶ [K1][K2][K3]...
V ─▶ [V1][V2][V3]...

for Q_i (SRAM):
    for K_j, V_j (SRAM):
        S_ij  = Q_i K_j^T           ← SRAM 안에서만 계산
        누적 max, 누적 sum 갱신      ← Online Softmax
        O_i  += 부분 Attention 결과  ← SRAM에서 누적
    O_i 최종값만 HBM에 write

핵심은 Online Softmax다. Softmax는 전체 LL개의 Key에 대한 값을 한 번에 봐야 정규화할 수 있는데, FlashAttention은 이를 Block 단위로 나눠 계산하면서 지금까지 본 Block들의 최댓값과 합을 계속 보정(rescale)해 나간다. 이렇게 하면 전체 Score 행렬을 동시에 들고 있지 않아도 수학적으로 동일한 Softmax 결과를 만들 수 있다.

Naive        : S, P를 HBM에 전부 저장 → 여러 번 read/write
FlashAttention: Block 단위로 SRAM에서 계산 → 최종 O만 HBM에 write

FlashAttention은 연산량(FLOPs)을 줄이는 최적화가 아니라, 같은 연산을 하면서 HBM Read/Write 횟수를 줄이는 최적화다.

이는 1편에서 살펴봤던 Compute와 Memory 사이의 데이터 이동 문제, 그리고 이번 편에서 계속 강조한 "병목은 연산량만이 아니라 어디서 데이터를 읽어오는가"라는 관점과 정확히 같은 맥락이다. Prefill에서는 거대한 L×LL \times L 행렬의 HBM 왕복을 줄여주고, Decode에서는 매 Step 읽어야 하는 KV Cache를 Block 단위로 스트리밍하듯 처리해 Memory Access 패턴을 개선한다.

5-3. Chunked Prefill

긴 Prompt가 들어오면 Prefill이 GPU Compute 자원을 오랫동안 점유할 수 있다. 그동안 Decode 중인 다른 요청이 기다려야 한다면 전체 서비스의 Latency가 나빠질 수 있다. 이를 해결하기 위해 Prefill을 작은 Chunk로 나누어 처리하고 Decode 요청과 적절히 섞는 Chunked Prefill이 쓰인다.

무엇을 기준으로 나누는가

2편에서 살펴본 Decoder-only Transformer의 구조를 다시 떠올려보자.

Token들 → Embedding → Positional Encoding → [Self-Attention → FFN] × N Layer → 다음 Token 예측

Chunked Prefill이 나누는 것은 이 Layer 스택이 아니다. Layer 수를 줄이거나 일부 Layer만 먼저 계산하는 것이 아니라, 한 번의 GPU 실행(Iteration)에 몇 개의 Token을 태울 것인가, 즉 입력 Token 시퀀스(LL) 축을 기준으로 나눈다.

전체 Prompt (1000 Tokens)
┌─────────────────────────────────────┐
│ Chunk 1(256) │ Chunk 2(256) │ Chunk 3(256) │ Chunk 4(232) │
└─────────────────────────────────────┘

각 Chunk는 그 자체로 작은 Prefill 하나다. Chunk 1이 Embedding부터 마지막 Layer까지 전체 스택을 통과하고, 그다음 Chunk 2가 다시 Embedding부터 마지막 Layer까지 전체 스택을 통과하는 식이다. 즉 한 Chunk는 반드시 모든 Layer를 다 거친 뒤에야 다음 Chunk로 넘어간다 — Layer 축이 아니라 Token 축으로 나뉘는 것이다.

나누는 기준 — Token Budget

Chunk의 크기는 임의로 정하는 것이 아니라, Scheduler가 한 Iteration에서 GPU에 태울 수 있는 Token Budget(예: Iteration당 최대 512 Token)으로 결정된다. 이 예산 안에서 Prefill Chunk와, 그 사이에 끼어드는 다른 요청들의 Decode Token(각 요청당 1개씩)을 함께 채워 하나의 Batch로 실행한다.

Iteration N   : [Prefill Chunk 1(256)] + [Decode A(1)] + [Decode B(1)] + ...
Iteration N+1 : [Prefill Chunk 2(256)] + [Decode A(1)] + [Decode B(1)] + ...

Chunk를 크게 잡으면 GPU Compute 활용은 좋아지지만 그만큼 다른 요청의 Decode가 한 Iteration 동안 밀린다. Chunk를 작게 잡으면 Decode 요청들의 TPOT는 안정적으로 유지되지만 Prefill 자체는 더 여러 Iteration에 걸쳐 끝난다. 즉 Chunk Size는 Prefill 처리량과 동시 요청들의 Decode Latency 사이의 Trade-off를 조절하는 값이다.

어디서 다시 합쳐지는가 — KV Cache

Chunk로 나눠 계산해도 결과가 흩어지는 것은 아니다. Chunk 1을 처리하면서 각 Layer에서 계산된 K/V는 그 요청의 KV Cache에 그대로 Append된다. Chunk 2의 Attention은 "Chunk 1이 만들어 KV Cache에 저장해 둔 K/V" + "Chunk 2 자신의 K/V"를 함께 참조하며 계산되고, 그 결과 역시 같은 KV Cache에 이어 붙는다.

Chunk 1 처리 → KV Cache: [K/V(1~256)]
Chunk 2 처리 → KV Cache: [K/V(1~256)] + [K/V(257~512)]
Chunk 3 처리 → KV Cache: [K/V(1~512)] + [K/V(513~768)]
...
마지막 Chunk 처리 완료 → KV Cache: [K/V(1~1000)]  ← 한 번에 Prefill한 것과 동일

즉 나눠지는 지점은 "Token을 몇 개씩 모델에 넣을 것인가"이고, 합쳐지는 지점은 Transformer 내부 연산이 아니라 KV Cache다. 모든 Chunk가 끝나고 나면 KV Cache에는 마치 Prompt 전체를 한 번에 Prefill한 것과 동일한 상태가 만들어지고, 그 이후부터는 평소와 같은 Decode가 시작된다.

Chunked Prefill이 나누는 것은 모델 구조가 아니라 한 Iteration에 태우는 Token 수이고, 나뉘어 처리된 결과가 다시 만나는 곳은 KV Cache다.

5-4. Disaggregated Prefill / Decode

더 나아가면 Prefill과 Decode 자체를 서로 다른 서버나 GPU 자원에서 처리하는 구조도 생각할 수 있다. 3-1에서 확인했듯 Prefill은 Compute-bound, Decode는 Memory-bound이므로, 애초에 필요한 자원의 성격이 다른 두 작업을 같은 GPU에 억지로 함께 두지 않는다는 것이 핵심 아이디어다.

User Request
     │
     ▼
┌───────────────┐        KV Cache        ┌───────────────┐
│ Prefill Server │ ──── (NVLink/RDMA) ───▶│ Decode Server  │──▶ Streaming Response
└───────────────┘                        └───────────────┘
  Compute-heavy GPU                        Memory-heavy GPU

각 구성 요소는 어떤 자원이 맞는가

구성 요소필요한 특성이유
Prefill Server (GPU)높은 FLOPS(연산 성능)대규모 Matrix Multiplication을 수행하는 Compute-bound 작업이므로, Tensor Core 연산 성능이 좋은 GPU가 유리하다
Decode Server (GPU)큰 Memory 용량 + 높은 Memory Bandwidth여러 요청의 KV Cache를 동시에 들고 있어야 하고, Step마다 이를 빠르게 읽어야 하는 Memory-bound 작업이기 때문이다
Router / Scheduler (CPU)낮은 지연, 가벼운 연산어떤 요청을 Prefill Server로, 어떤 요청을 Decode Server로 보낼지 결정하고 KV Cache 전송 시점을 관리한다. GPU 연산이 필요 없는 경량 작업이라 CPU에서 처리한다
Tokenizer / Detokenizer (CPU)낮은 지연문자열 ↔ Token ID 변환은 GPU 연산이 아니라 CPU에서 수행하는 것이 일반적이다
KV Cache 전송 경로빠른 InterconnectPrefill Server가 만든 KV Cache(요청·길이에 따라 수백 MB~수 GB)를 Decode Server로 옮겨야 하므로, 같은 노드라면 NVLink, 다른 노드라면 InfiniBand/RDMA처럼 빠른 연결이 필요하다. 이 전송 자체가 느리면 새로운 병목이 된다

구체적인 예시

예를 들어 8,000 Token 분량의 문서를 요약해달라는 요청이 들어왔다고 하자.

1. Router가 요청을 받아 Prefill Server로 전달
2. Prefill Server(FLOPS가 높은 GPU, 예: H100 여러 장을 Tensor Parallel로 구성)가
   8,000 Token 전체를 한 번에(또는 Chunked Prefill로) 처리 → KV Cache 생성
3. 생성된 KV Cache를 NVLink/RDMA로 Decode Server에 전송
4. Decode Server(Memory 용량·대역폭이 큰 GPU)가 이 요청의 Decode를
   다른 요청들과 Continuous Batching으로 묶어 함께 처리
5. 생성되는 Token을 Streaming으로 사용자에게 전달

이렇게 나누면 Prefill Server는 짧은 시간에 최대한 많은 연산을 처리하는 데 집중하고, Decode Server는 동시에 얼마나 많은 요청의 KV Cache를 붙들고 있을 수 있는지에 집중할 수 있다. 실제로 이런 구조는 vLLM의 Prefill/Decode Disaggregation, DistServe, Splitwise 같은 이름으로 프로덕션 Serving 시스템에 적용되고 있다.

Prefill과 Decode는 병목의 성격이 다르므로, 굳이 같은 GPU에서 처리할 필요가 없다. 서로 다른 자원을 붙이고, 그 사이는 빠른 Interconnect로 KV Cache를 옮겨 연결한다.

6. vLLM으로 보는 실전 시스템

6-1. PagedAttention과 vLLM — 그리고 아직 남은 문제

지금까지 KV Cache의 크기를 줄이거나(MQA/GQA), 접근 방식을 최적화하거나(FlashAttention), 처리 시점을 조절하거나(Chunked Prefill), 아예 물리적으로 분리하는(Disaggregated Prefill/Decode) 여러 방법을 봤다. 이 기법들이 실제 Serving Engine 안에서 어떻게 하나로 합쳐지는지 살펴보자.

PagedAttention을 대표적으로 활용하는 Serving Engine이 vLLM이다. vLLM의 핵심은 단순히 Transformer 모델을 실행하는 것이 아니라, Inference 과정에서 발생하는 GPU Memory와 KV Cache를 효율적으로 관리하고, 여러 요청을 높은 Throughput으로 처리하는 것이다.

Transformer → 모델의 구조
vLLM        → 모델을 효율적으로 Serving하기 위한 시스템

그런데 PagedAttention은 "이미 들어온 KV Cache를 메모리에 어떻게 배치할 것인가"라는 공간 배치 문제를 푼 것이지, "어떤 요청을 지금 GPU에 올려 실행할 것인가"라는 시간(스케줄링) 문제까지 푼 것은 아니다.
vLLM이 실제로 높은 Throughput을 내려면 이 두 번째 문제도 함께 풀어야 한다.

6-2. Continuous Batching과 Scheduler — 시간 축의 문제

앞서 남겨둔 스케줄링 문제가 바로 3-1편에서 살펴본 Continuous Batching이다. 이번엔 Prefill/Decode 관점에서 다시 보자.
Decode는 한 번에 하나의 Token을 생성하기 때문에 요청마다 생성 과정이 계속 진행되고, 요청마다 종료 시점도 다르다.
Continuous Batching은 실행 중인 요청이 끝났을 때 새로운 요청을 동적으로 추가해, GPU가 특정 요청의 종료를 기다리는 시간을 줄이고 더 많은 요청을 지속적으로 처리한다.

여기서 핵심은 Scheduler다. Scheduler는 어떤 요청을 Batch에 넣고, 언제 제거하고, GPU에 어떤 작업을 실행할지 결정한다. PagedAttention이 메모리 공간을, Continuous Batching이 실행 시점을 관리한다는 점에서 둘은 vLLM 안에서 서로 다른 축을 담당하는 짝이다. 이것이 이후 편에서 직접 Serving Service를 구현할 때 중요한 부분이 된다.

6-3. Streaming은 어떻게 연결되는가

LLM은 Token을 하나씩 생성하기 때문에 생성할 때마다 사용자에게 전달할 수 있다.

Model → Token 1 → User
      → Token 2 → User
      → Token 3 → User

Streaming은 모델의 전체 계산량을 줄이는 것은 아니다. 하지만 사용자가 첫 번째 결과를 빠르게 볼 수 있기 때문에 체감 Latency를 낮추는 데 중요하다. Serving System에서는 모델 계산 속도, Token 생성 속도, 전송 방식을 함께 고려해야 한다.

마무리

  • Self-Attention : 모든 Token 쌍의 관계를 계산하므로 O(L2D)O(L^2D)의 계산량을 가진다.
  • KV Cache : 이전 Token의 K/V를 저장해 다시 계산하지 않는다. Decode에서 반복되는 K/V 계산을 없앤다.
  • Prefill : 많은 Token을 병렬로 처리 → Compute-bound
  • Decode : 새로운 Token은 하나지만 이전 Token의 KV Cache를 계속 읽어야 함 → Memory-bound
  • PagedAttention : KV Cache를 Block 단위로 관리해 GPU Memory를 효율적으로 사용한다.
  • Continuous Batching : 요청의 종료 시점이 달라도 실행 중인 Batch에 새 요청을 계속 추가해 GPU 활용률과 Throughput을 높인다.
  • MQA / GQA : 여러 Query Head가 K/V Head를 공유하도록 모델 아키텍처 자체를 바꿔 KV Cache 크기를 줄인다.
  • FlashAttention : 연산량이 아니라 HBM Read/Write 횟수를 줄여, Attention 계산이 GPU Kernel 레벨에서 Memory에 덜 의존하게 만든다.
  • Chunked Prefill : 긴 Prefill을 Token 축으로 잘라 Decode 요청과 한 Iteration 안에서 함께 실행해, Prefill이 Decode의 Latency를 밀어내지 않게 한다.
  • Disaggregated Prefill/Decode : Compute-bound인 Prefill과 Memory-bound인 Decode를 아예 다른 서버로 분리하고, 그 사이를 빠른 Interconnect로 연결해 KV Cache를 전달한다.

1편에서는 GPU의 구조를 살펴봤다. GPU는 많은 연산을 병렬로 수행하기 때문에 Matrix 연산에 강하다.

2편에서는 Transformer를 살펴봤다. Attention과 FFN은 GPU가 잘 처리할 수 있는 대규모 연산을 수행한다.

3-1편에서는 이 모델을 실제 서비스로 가져왔다.

Request → Tokenization → Scheduling → Batching → GPU Inference → Streaming

그리고 3-2편에서는 그 내부에서 실제로 어떤 일이 일어나는지 살펴봤다.

Prompt → Prefill → First Token → Decode → KV Cache → Next Token → ...

여기서 중요한 사실이 하나 드러난다.

LLM Serving의 병목은 항상 Compute가 아니다. Prefill에서는 GPU Compute가 중요하지만, Decode에서는 KV Cache와 Memory Bandwidth가 중요하다. 따라서 좋은 Serving System은 단순히 더 강한 GPU를 쓰는 것이 아니라,

현재 어떤 단계가 병목인지 파악하고, 그 병목에 맞는 최적화를 적용해야 한다.

여기까지 이해했다면 이제 이론을 실제 시스템으로 옮겨볼 차례다.

다음편에서는 Serving System을 직접 만든다면 어떻게 구현해야 할지 확인해본다.

profile
Gyullbb
이전 포스트

3-1편. LLM 모델 서빙과 최적화

다음 포스트

4-1편. LLM Serving Service(Single Model Serving)

0개의 댓글