02. tokenization, prefill, decode

핵심 질문

• 하나의 요청은 어떤 계산 phase들을 순서대로 지나는가?
• "첫 토큰이 나온다"는 것은 시스템 안에서 정확히 무슨 사건인가?

목표

• tokenization → prefill → decode의 계산 phase를 구분한다.
• 출력 이벤트(첫 토큰, 이후 토큰)와 streaming completion을 정의로 못 박는다.

여정의 확대: 첫 계산 구간

01장에서 요청이 API → tokenizer → 스케줄러 → 워커/GPU를 지난다고 그렸습니다. 이 장은 그중 GPU 위에서 실제 무슨 계산이 일어나는가를 확대합니다. 계산은 크게 두 phase — prefill과 decode — 로 나뉘고, 그 앞에 tokenization이 있습니다.

flowchart LR
    TXT[프롬프트 텍스트]:::req --> TOK[tokenization<br/>텍스트→토큰 id 열]:::comp
    TOK --> PRE[prefill<br/>프롬프트 전체를 한 번에 처리]:::comp
    PRE --> FT((첫 토큰)):::result
    FT --> DEC[decode<br/>토큰 1개씩 반복 생성]:::comp
    DEC --> DEC
    DEC --> STOP{종료 조건?}:::ctrl
    STOP -->|아니오| DEC
    STOP -->|예| END[completion]:::result

    classDef req fill:#fff3bf,stroke:#f59f00,color:#000;
    classDef comp fill:#d0ebff,stroke:#1971c2,color:#000;
    classDef ctrl fill:#c3fae8,stroke:#0ca678,color:#000;
    classDef result fill:#d3f9d8,stroke:#2f9e44,color:#000;

1단계: tokenization

tokenization(토큰화)은 사람이 읽는 텍스트를 모델이 다루는 토큰(token) id의 열로 바꾸는 일입니다. 토큰은 대략 단어 조각(subword)이며, "토큰 하나 = 단어 하나"가 아닙니다. 영어는 대략 단어당 1~2 토큰, 언어·문자에 따라 크게 다릅니다.

역방향인 detokenization은 생성된 토큰 id를 다시 텍스트로 되돌립니다. 사용자가 화면에서 보는 글자는 항상 detokenization을 거친 결과입니다.

🔎 왜 중요한가: 모든 지표의 분모·비용이 토큰 수로 계산됩니다. "긴 프롬프트"란 결국 "토큰이 많은 프롬프트"이고, 뒤에 볼 KV 캐시 크기·prefill 비용이 여기서 정해집니다.

2단계: prefill — 프롬프트를 한 번에 삼키기

prefill은 입력 프롬프트 전체를 모델에 통과시켜, 각 레이어에서 필요한 중간 상태를 계산하는 phase입니다. 핵심 성질은 이것입니다: 프롬프트의 여러 토큰을 동시에(병렬로) 처리할 수 있습니다. 이미 모든 입력 토큰을 알고 있으므로, 서로를 기다릴 필요가 없기 때문입니다.

prefill의 결과로 두 가지가 생깁니다.

1. 첫 번째 출력 토큰 — 프롬프트 다음에 올 토큰의 예측.
2. KV 캐시(key-value cache) — 각 레이어·각 입력 토큰에 대한 key/value 상태. 다음 phase에서 재사용하려고 저장합니다. (자세히는 05장.)

🔎 약어 풀이 — KV 캐시
KV는 Key-Value의 약자입니다. attention 계산에서 각 토큰은 key와 value 벡터를 갖는데, 이후 토큰을 생성할 때 앞 토큰들의 key/value를 다시 계산하지 않고 꺼내 쓰려고 저장해 둔 것이 KV 캐시입니다. 왜 이게 메모리를 잡아먹는 주범이 되는지는 04~05장에서 계산과 함께 봅니다.

3단계: decode — 한 번에 한 토큰씩

decode는 토큰을 하나 생성 → 그 토큰을 입력에 붙여 다시 하나 생성을 반복하는 phase입니다. 이것을 autoregressive(자기회귀) 생성이라 부릅니다. 다음 토큰은 앞 토큰이 정해져야 계산할 수 있으므로, decode는 본질적으로 순차적(sequential)입니다 — prefill의 병렬성과 대비되는 결정적 차이입니다.

각 decode 스텝은 KV 캐시에서 앞 토큰들의 상태를 읽고, 새 토큰 하나의 key/value를 캐시에 덧붙입니다. 그래서 KV 캐시는 생성이 진행될수록 계속 자랍니다.

decode는 종료 조건을 만나면 멈춥니다: 종료 토큰(EOS)이 나오거나, 최대 토큰 수에 도달하거나, 사용자가 중단하는 경우 등입니다.

출력 이벤트를 정의로 못 박기

지표를 이야기하려면(14장) 이벤트를 흐릿하게 두면 안 됩니다. 여기서 미리 정의합니다.

조건 명시: 이 phase 구분이 성립하는 조건 / 흔들리는 경계

• 성립하는 조건: 표준적인 decoder-only autoregressive 모델을, 토큰을 왼쪽에서 오른쪽으로 하나씩 생성하는 방식으로 서빙할 때. 대다수 텍스트 생성 LLM이 여기 해당합니다.
• 경계가 흔들리는 경우:
  • chunked prefill: 긴 prefill을 조각내어 decode 스텝들 사이에 끼워 넣는 스케줄링에서는, "prefill 구간과 decode 구간이 시간상 깔끔히 나뉜다"는 그림이 흐려집니다(08·14장).
  • speculative decoding / MTP: 한 스텝에 토큰을 여러 개 후보로 내고 검증하는 방식에서는 "1 스텝 = 1 토큰"이 깨집니다(12장).
  • 스케줄링 관점에서 prefill/decode를 균일하게 다루는 엔진(예: vLLM V1)에서는 스케줄러 코드상의 구분이 사라지지만, 계산의 성격(병렬 vs 순차)은 남습니다.

📌 핵심

• 계산은 tokenization → prefill → decode로 흐른다.
• prefill: 프롬프트 전체를 병렬 처리, 첫 토큰과 초기 KV 캐시 생성.
• decode: 토큰을 하나씩 순차 생성, KV 캐시는 계속 성장.
• 첫 토큰까지의 시간 ≠ prefill 계산 시간(큐·네트워크 포함).
• streaming은 전달 방식, prefill/decode는 계산 phase — 다른 층위.

🔎 이 장의 '지지하지 않는 결론'

• 이 장은 phase의 성격(병렬 vs 순차)만 말합니다. "그래서 prefill이 compute-bound고 decode가 memory-bound다"는 아직 말할 수 없습니다 — 그건 하드웨어·배치 조건이 필요한 별개 주장이며 다음 장의 주제입니다.
• phase가 "시간상 깔끔히 두 구간으로 나뉜다"고 일반화할 수 없습니다(chunked prefill 등에서 겹침).

✍️ 확인 문제

1. prefill이 병렬 처리에 유리하고 decode가 순차적일 수밖에 없는 이유를, "다음 토큰을 계산하려면 무엇이 필요한가"로 각각 설명하세요.
2. streaming을 끈(non-streaming) 응답에서도 내부적으로 decode phase가 존재합니까? 그 이유는?
3. (조건 유형) "첫 토큰까지 500ms 걸렸으니 prefill이 500ms 걸린 것"이라는 주장이 성립하려면 어떤 조건들이 모두 참이어야 합니까? 최소 두 가지를 드세요.

다음 장: 03 · prefill과 decode의 서로 다른 병목