프롬프트가 길어지면 첫 토큰이 늦게 나온다는 건 다들 안다. 문제는 얼마나 늦어지는가다. 2배? 4배? 아니면 그 이상? Flash Attention이 나온 뒤에도 이 질문의 답이 명쾌하지 않았는데, 이유는 단순하다 — FLOP 복잡도와 IO 복잡도를 같은 것으로 취급하기 때문이다.
Prefill은 왜 시퀀스 길이에 민감한가
Transformer Self-Attention에서 병목은 QK^T 행렬곱이다. 배치 크기 1, 시퀀스 길이 n, hidden_dim d, 레이어 수 L일 때 Prefill의 총 FLOPs는 두 항으로 나뉜다.
Total FLOPs = L × (24nd² + 4n²d)
첫째 항(24nd²)은 선형 레이어에서 나온다. Q·K·V 투영 각 2nd², 출력 투영 2nd², FFN 16nd²를 합하면 24nd²이고, 이 항은 n에 선형이다. 둘째 항(4n²d)은 Attention 행렬곱(QK^T와 AV 각각 2n²d)에서 나오고, n에 이차다.
d=4096, L=32 기준(7B급 MHA 모델)으로 구간별 FLOPs를 수치화하면 이렇다.
| 시퀀스 길이 | 선형 항 (TFLOPs) | Attention 항 (TFLOPs) | 합계 (TFLOPs) | Attention 비율 |
|---|---|---|---|---|
| 512 | 6.6 | 0.1 | 6.7 | 2% |
| 1K | 13.2 | 0.5 | 13.7 | 4% |
| 2K | 26.4 | 2.2 | 28.6 | 8% |
| 4K | 52.8 | 8.8 | 61.6 | 14% |
| 8K | 105.5 | 35.2 | 140.7 | 25% |
| 32K | 422 | 563 | 985 | 57% |
| 128K | 1,688 | 9,007 | 10,695 | 84% |
4K 이하에서는 선형 항이 압도적이다. 8K부터 Attention 항이 체감되기 시작하고, 32K를 넘으면 두 항이 역전된다. 128K에서는 전체 FLOPs의 84%가 Attention에서 나온다.
두 항이 같아지는 crossover point는 4n²d = 24nd²를 풀면 n = 6d다. d=4096이면 n ≈ 24,576, 즉 약 24K 토큰 근방이다.
Flash Attention 이후에도 비선형성이 남는 이유
Flash Attention 2(Dao, 2023)가 해결한 문제는 HBM I/O 복잡도다. 표준 Attention은 n×n 점수 행렬을 HBM에 기록하고 다시 읽어야 해서 I/O가 O(n²)이다. Flash Attention은 블록 단위 타일링과 온라인 softmax로 이 행렬을 HBM에 쓰지 않아 I/O를 O(n)으로 줄였다.
산술 FLOPs는 그대로다. Forward pass에서 동일한 O(n²d)의 연산을 수행하고, 다만 HBM을 덜 읽고 쓸 뿐이다.
Prefill이 compute-bound인지 memory-bound인지를 판단하는 도구는 roofline 분석이다. arithmetic intensity(AI)부터 구한다.
Flash Attention에서 한 레이어의 AI:
AI = FLOPs / Bytes = O(n²d) / O(nd) = O(n)
Q·K·V·O를 nd 크기 블록으로 HBM에서 읽고 쓰므로 메모리 접근은 O(nd), FLOPs는 O(n²d) — AI가 n에 비례한다.
GPU 스펙과 roofline threshold를 대입하면:
| GPU | FP16 Peak | HBM BW | Threshold (FLOP/Byte) |
|---|---|---|---|
| A100 SXM4 | 312 TFLOPS | 2.04 TB/s | 153 |
| H100 SXM5 | 495 TFLOPS | 3.35 TB/s | 148 |
AI = n이므로 n > 153이면 A100 기준 compute-bound다. 256 토큰짜리 Prefill도 이미 compute-bound다. 선형 레이어도 AI = n으로 같은 구조를 갖는다(가중치 2d² bytes, FLOPs 2nd² → AI = n).
Flash Attention이 나온 뒤 Prefill은 거의 항상 compute-bound이고, TTFT는 총 FLOPs를 GPU peak FLOP/s로 나눈 값에 비례한다. 따라서 FLOPs가 O(n²) 방향으로 성장하는 구간에서는 TTFT도 같은 속도로 늘어난다.
n이 2배가 됐을 때 TTFT 배율을 직접 계산하면:
ratio(n→2n) = (48nd² + 16n²d) / (24nd² + 4n²d)
= (48d + 16n) / (24d + 4n)
- n ≪ 24K (선형 지배): 48d/24d = 2배
- n ≈ 24K (crossover): 144d/48d = 3배
- n ≫ 24K (Attention 지배): 16n/4n = 4배에 수렴
실측: 컨텍스트 길이별 TTFT
이론이 실제로 드러나는지 확인한다. Llama-3-8B, A100 SXM4, FlashAttention-2, 배치 크기 1 고정 조건에서의 실측 TTFT:
| 입력 길이 | TTFT (ms) | 직전 대비 토큰 배율 | TTFT 배율 | log-log 기울기 |
|---|---|---|---|---|
| 1K | 81 | — | — | — |
| 10K | 832 | 10× | 10.3× | ≈ 1.01 |
| 50K | 7,717 | 5× | 9.3× | ≈ 1.39 |
| 100K | 21,731 | 2× | 2.82× | ≈ 1.50 |
| 128K | 32,863 | 1.28× | 1.51× | ≈ 1.72 |
1K→10K 구간(기울기 ≈ 1.0)은 선형 항이 지배하는 구간이라 TTFT가 토큰 수에 거의 비례한다. 10K→50K에서 기울기가 올라가며, 100K 근방에서 1.5~1.7에 도달한다.
128K에서도 기울기가 아직 2.0에 미치지 못하는 이유가 있다. Llama-3-8B는 GQA 구조(KV 헤드 8개)라 crossover가 ~21K 토큰 근방이고, 128K는 그 6배 초과 지점이므로 이론적 상한 2.0에 수렴하는 도중이다. 수렴이 완전히 이뤄지지 않는 이유는 선형 항이 128K에서도 전체 FLOPs의 16%를 차지하기 때문이다.
현장에서 자주 보는 착각이 "TTFT가 길이에 선형으로 늘어난다"는 것인데, 이 데이터를 보면 10K까지는 그게 맞고, 32K부터는 완전히 다른 게임이 된다.
모델 크기·헤드 구조가 crossover를 어디로 옮기는가
GQA 모델은 K·V 투영 행렬이 작다. Llama-3-8B(GQA, KV 헤드 8)를 Llama-2-7B(MHA, KV 헤드 32)와 비교하면:
- MHA 선형 항: 24nd²
- GQA 선형 항: 21nd² (K·V 투영이 각 d_kv=d/4 크기로 줄어, K+V 합산 투영이 4nd²에서 nd²로 감소해 총 3nd² 절감)
두 모델의 Attention FLOP(4n²d)은 동일하다. GQA는 선형 항을 12.5% 줄이는 것이지, 이차 항에는 손댈 수 없다.
| 모델 | 구조 | 선형 항 (n=4K) | Attention 항 (n=4K) | 합계 | crossover |
|---|---|---|---|---|---|
| Llama-2-7B | MHA, d=4096, L=32 | 52.8 TFLOPs | 8.8 TFLOPs | 61.6 TFLOPs | ~24K |
| Llama-3-8B | GQA G=4, d=4096, L=32 | 46.2 TFLOPs | 8.8 TFLOPs | 55.0 TFLOPs | ~21K |
| Llama-3-70B | GQA G=8, d=8192, L=80 | ~451 TFLOPs | ~43.9 TFLOPs | ~495 TFLOPs | ~168K |
Llama-3-70B는 d=8192이라 crossover가 ~168K 토큰으로 밀려난다. 70B 모델로 128K 컨텍스트를 처리해도 아직 선형 지배 구간이고, TTFT 기울기가 1에 가까울 수 있다. 반면 7B-8B 모델은 32K부터 이미 기울기가 가파르게 오른다.
GQA의 실질적 이점은 Decode 단계에서 KV cache 로딩 메모리를 줄이는 것이지, Prefill의 TTFT 비선형성을 완화하는 게 아니다.
배치 안 긴 요청 하나가 p99를 망치는 이유
continuous batching 환경에서는 긴 Prefill 요청이 시작되면 해당 forward pass가 끝날 때까지 같은 배치 내 Decode가 블로킹된다. 10K 토큰짜리 Prefill이 832ms 걸린다면, 함께 배치된 100 토큰짜리 요청은 그 832ms가 끝날 때까지 첫 토큰을 받지 못한다. 요청 하나가 배치 전체의 TTFT 분포를 오염시키는 구조다.
Chunked Prefill은 이 버블을 잘라낸다. 큰 Prefill을 max_num_batched_tokens 크기의 청크로 쪼개 매 step에 Decode 요청과 함께 처리한다. vLLM의 기본값은 512 토큰이고, 이 값이 A100에서 ITL(inter-token latency) 최소화에 실측상 최적이라고 공식 문서에 명시돼 있다.
# vLLM에서 Chunked Prefill 활성화
llm = LLM(
model="meta-llama/Llama-3-8B",
enable_chunked_prefill=True,
max_num_batched_tokens=512, # 기본값; ITL 우선 시 낮게, TTFT 우선 시 높게
)
트레이드오프는 명확하다. chunk_size를 작게 할수록 짧은 요청의 ITL이 개선되지만, 10K 프롬프트는 20개 step으로 나뉘어 TTFT가 올라간다. 반대로 chunk_size를 크게 하면 긴 요청의 TTFT는 빨라지지만 Prefill 버블이 다시 커진다.
TTFT SLA를 단일 숫자(예: "500ms 이내")로 정의하면 컨텍스트 길이 분포가 넓은 서비스에서는 항상 깨진다. 실무에서 쓸 수 있는 접근은 두 가지다. 첫째, 입력 길이 버킷별 SLA를 분리하는 것 — 4K 이하 200ms, 4K~16K 1s, 16K 초과 5s처럼. 둘째, SLA 역산으로 chunk_size를 정하는 것 — 짧은 요청의 p99 TTFT 목표가 T_max라면 한 청크 처리 시간이 T_max 이내여야 하므로 상한을 chunk_size ≤ T_max × GPU peak FLOP/s / (FLOPs per token)으로 구할 수 있다.
덧붙이자면, 16K를 초과하는 요청만 전담 엔드포인트로 라우팅하는 길이 기반 라우팅도 현실적인 선택이다. 이 구간부터 단일 Prefill이 배치 전체를 블로킹하는 위험이 급격히 커지고, 범용 배치와 분리해야 p99 보장이 가능하다.