LLM 추론은 왜 두 개의 다른 병목을 가지는가

Prefill의 compute-bound와 decode의 memory-bound가 같은 모델에서 공존하는 이유부터 Roofline 분석과 batch 최적화의 한계까지, LLM 서빙의 물리적 제약을 추적한다.

LLM은 같은 모델, 같은 forward pass를 실행하면서도 완전히 다른 두 가지 병목을 오간다. 첫 번째 토큰이 나오기 전까지는 GPU 연산 능력이 한계이고, 그 이후 토큰을 하나씩 생성하는 동안은 메모리 대역폭이 한계다. 왜 하나의 모델이 두 개의 서로 다른 병목을 갖는가?

두 단계로 분해되는 생성 과정

Autoregressive generation은 수식으로 표현하면 단순해 보인다.

x_{t+1} \sim p_\theta(x_{t+1} \mid x_{1:t}), \quad t = L, L+1, \ldots, L+T-1

하지만 실행 관점에서 이 과정은 두 개의 질적으로 다른 단계로 분리된다.

Prefill은 입력 프롬프트 $x_{1:L}$ 을 한 번의 forward pass로 처리한다. $L$ 개의 토큰이 동시에 attention 레이어를 통과하므로 $\mathcal{O}(L^2 d)$ 의 연산이 한 번에 집중된다. 이 단계의 산출물은 첫 번째 토큰의 logits와, 이후 단계에서 재사용할 KV cache다.

Decode는 그 이후 매 스텝마다 새 토큰 하나만 처리한다. 이전 토큰들의 KV cache를 읽어 attention을 계산하고, FFN을 통과해 다음 토큰을 샘플링한다. 이 과정을 $T$ 번 반복한다.

사용자가 경험하는 latency는 이 두 단계의 합으로 분해된다.

\boxed{T_{\mathrm{total}} = \mathrm{TTFT} + (T-1) \cdot \mathrm{TPOT}}

TTFT(Time to First Token)는 prefill이 끝나는 시점이고, TPOT(Time per Output Token)는 각 decode 스텝의 평균 시간이다. 두 지표는 서로 다른 GPU 리소스에서 비롯되므로, 하나를 최적화하는 기법이 반드시 다른 것도 개선하지는 않는다.

Prefill이 compute-bound인 이유

Prefill의 FLOPs와 메모리 접근량을 계산하면 패턴이 드러난다.

$N$ 을 모델 파라미터 수라 하면:

FLOPs: $2LN$ (프롬프트 길이 $L$ 에 선형 비례)
Bytes: $2N$ (가중치를 1회 읽음, $L$ 과 무관)
Arithmetic Intensity: $I = \frac{2LN}{2N} = L$

Arithmetic intensity란 메모리에서 읽어온 바이트 당 수행하는 연산 수다. Prefill의 경우 이 값이 정확히 프롬프트 길이 $L$ 이 된다.

A100(FP16)의 ridge point는 $I^* = 312 \text{ TFLOPS} / 1.5 \text{ TB/s} \approx 208$ 이다. $L > 208$ 이면 prefill은 compute-bound 구간에 진입한다. 일반적인 서빙 환경에서 $L = 256 \sim 2048$ 이므로, prefill은 항상 compute-bound다.

명제 1 · Prefill의 이론적 latency 하한

LLaMA-7B( $N = 7 \times 10^9$ ), A100 FP16, $L = 512$ 일 때:

$T_{\mathrm{prefill}} \ge \frac{2LN}{\pi_{\mathrm{peak}}} = \frac{2 \times 512 \times 7 \times 10^9}{312 \times 10^{12}} \approx 23 \text{ ms}$

▷ 증명

Compute-bound regime에서 실행 시간의 하한은 $\mathrm{FLOPs} / \pi_{\mathrm{peak}}$ 이다. 이는 GPU가 peak throughput에 도달했을 때의 이론값이며, 실제 커널 오버헤드와 메모리 경합을 고려하면 50~100ms가 일반적이다. $\square$

∎

Prefill에서 Flash Attention이 극적인 속도 향상을 주는 이유도 여기서 나온다. FLOPs 자체는 변하지 않지만, intermediate matrix $S = QK^\top \in \mathbb{R}^{L \times L}$ 을 HBM에 쓰고 읽는 과정을 제거해 실제 메모리 이동량을 $\mathcal{O}(L^2 d) \to \mathcal{O}(Ld)$ 로 줄이면 wall-clock 성능이 1.5~2× 향상된다.

Decode가 memory-bound인 이유

Decode는 정반대다. 매 스텝마다 토큰 하나를 처리하므로:

FLOPs: $2N$ ( $L$ 과 무관, FFN 연산이 지배)
Bytes: $2N$ (가중치 전체를 1회 읽음)
Arithmetic Intensity: $I = \frac{2N}{2N} = 1$

$I = 1$ 은 A100의 ridge point 208보다 208배 낮다. 모든 현대 GPU에서 decode는 memory-bound다.

GPU Performance Timeline (A100, decoding 1 token)

┌─────────────────────────────────────────────────┐
│  1. Read model weights from HBM               │ ← 1.5 TB/s
│     2N bytes = 14 GB (LLaMA-7B FP16)          │
│     Time: 14 / 1500 ≈ 9.3 ms                  │
│                                               │
│  2. GPU compute cores: 대부분 대기              │
│     실제 계산 시간: ~0.045 ms                   │
└─────────────────────────────────────────────────┘

GPU compute utilization을 계산하면:

$U_{\mathrm{compute}} = \frac{T_{\mathrm{compute}}}{\mathrm{TPOT}} = \frac{0.045 \text{ ms}}{9.3 \text{ ms}} \approx 0.5\%$

GPU의 FLOPs capacity 중 0.5%만 사용되고, 나머지 99.5%는 메모리 I/O를 기다린다. TPOT의 이론적 하한은 가중치를 읽는 데 걸리는 시간이다.

$\mathrm{TPOT} \ge \frac{2N}{\beta_{\mathrm{HBM}}} = \frac{14 \times 10^9}{1.5 \times 10^{12}} \approx 9.3 \text{ ms}$

Roofline으로 두 단계를 한 그래프에

Williams(2009)의 Roofline model은 이 두 단계의 차이를 하나의 그래프로 보여준다.

$\mathrm{Performance}(I) = \min\bigl(\pi_{\mathrm{peak}},\ \beta_{\mathrm{HBM}} \cdot I \bigr)$

Performance (TFLOPS/s)
│
│ 312 ┌──────────────────── compute-bound
│     │╱ ridge I*=208
│    ╱│
│   ╱ │
│  ╱  │
│ ╱   │  ← Decode: I=1, perf=1.5 TFLOPS (0.5%)
├╱────●──────────────────●── Prefill: I=512, perf=312 TFLOPS
│    I*=208              I=512
└────────────────────────────
      Arithmetic Intensity

주요 GPU별 ridge point를 비교하면:

GPU	Peak FLOPs	Bandwidth	Ridge $I^*$
A100 FP16	312 TFLOPS	1.5 TB/s	208
H100 FP16	989 TFLOPS	3.35 TB/s	295
MI300X FP16	1300 TFLOPS	5.3 TB/s	245

Decode의 $I = 1$ 은 모든 GPU에서 ridge보다 수백 배 낮다. GPU를 업그레이드해도 decode는 여전히 memory-bound다. 이 구조적 사실이 모든 decode 최적화의 출발점이다.

Batching으로 Arithmetic Intensity를 끌어올리기

Decode의 $I = 1$ 을 높이는 방법이 있다. Batch size $B$ 로 여러 요청을 동시에 처리하면:

FLOPs: $2BN$ (각 샘플의 forward 합산)
Bytes: $2N$ (가중치는 공유, 1회만 읽음)
Arithmetic Intensity: $I^{(B)} = \frac{2BN}{2N} = B$

Batch size가 곧 arithmetic intensity가 된다. $B^* = I^* \approx 208$ 이면 decode도 compute-bound에 진입한다.

⚠ 트레이드오프: KV cache 메모리 폭발

Batch size를 늘리면 각 샘플의 KV cache를 동시에 HBM에 올려야 한다.

$M_{KV} = B \times T \times L_{\mathrm{layers}} \times d_{\mathrm{model}} \times 2 \text{ bytes}$

LLaMA-7B MHA, $T=2048$ 기준: 샘플당 ~0.43 GB. A100 80GB에서 $B_{\max} \approx 20$ 으로, ridge point 208까지는 KV cache만으로도 메모리가 부족하다.

결론: batching의 효과는 KV cache 메모리 제약에 의해 상한이 결정된다.

이 제약을 완화하는 기법들이 GQA, KV quantization, PagedAttention이다.

GQA ( $n_{kv} = 8$ 그룹): KV dimension이 $d \to d/8$ 로 줄어 같은 메모리로 8배 더 많은 배치 가능
INT8 quantization: bytes-per-value를 2 → 1로 줄여 $B_{\max}$ 2배
PagedAttention: fragmentation 60% → 4%로 줄여 실제 가용 메모리 증가

조합하면 A100 80GB에서도 $B = 200$ 근방까지 도달할 수 있다. 단, $B > B^*$ 를 넘으면 throughput 증가가 멈춘다. Compute-bound 구간에서는 batch를 더 늘려도 이득이 없고, 오히려 prefill cluster와 decode cluster를 물리적으로 분리하는 disaggregated serving이 더 효과적이다.

정리

LLM 추론은 prefill(compute-bound, $I = L$ )과 decode(memory-bound, $I = 1$ )로 나뉘며, 두 단계는 Roofline 그래프의 서로 다른 위치에 있다.
TTFT는 prefill 연산 속도가 결정하고, TPOT는 HBM 대역폭이 결정한다. 같은 기법으로 동시에 최적화할 수 없다.
Decode의 GPU compute utilization은 0.5% 수준이며, 이를 개선하는 유일한 경로는 batch size를 통한 arithmetic intensity 상승이다.
GQA, quantization, PagedAttention은 모두 “KV cache 메모리 제약을 낮춰 batch를 더 크게 만든다”는 같은 목표를 다른 방법으로 달성한다.

두 개의 병목이 하나의 모델 안에 공존한다는 사실이, LLM 서빙 시스템 설계의 모든 복잡성을 만들어낸다.