구문 제약 디코딩과 로짓 마스킹의 작동 원리: 구조화된 출력의 내부 메커니즘

OpenAI가 response_format={

샘플러는 이러한 확률을 기반으로 토큰 $w_t$를 추출합니다.

제약 없는 디코딩(unconstrained decoding)의 경우, 어휘집 내 모든 토큰이 0이 아닌 확률을 가집니다. 키 이름인 "username": 바로 뒤에 닫는 중괄호 }가 샘플링될 확률이 단지 0.0001%에 불과하더라도, 수십억 개의 생성된 토큰을 거치면서 이러한 실패는 실제 운영 환경에서 수천 번 발생할 것입니다.

2. Step 1: JSON Schema를 공식 문법 상태 기계(Formal Grammar State Machine)로 컴파일하기

JSON Schema나 Pydantic 모델을 추론 엔진(inference engine, 예: vLLM의 xgrammar, SGLang의 outlines, 또는 llama.cpp의 GBNF 엔진)에 제출할 때, 해당 엔진은 스키마를 모델 가중치에 직접 공급하지 않습니다. 대신, 호스트 CPU나 GPU에서 이 스키마를 공식 문법 상태 기계로 컴파일합니다.

[ JSON Schema / Pydantic Model ]
               │
               ▼
...

JSON은 임의로 중첩된 배열과 객체({"a": {"b": [1, 2]}})를 지원하기 때문에 문맥 자유 문법(Context-Free Grammar, CFG)입니다. 표준 결정적 유한 오토마타(Deterministic Finite Automaton, DFA)는 무한한 메모리를 갖지 못하여 임의의 중첩 깊이를 추적할 수 없습니다. 따라서, 엔진은 이 스키마를 **푸시다운 오토마타(Pushdown Automaton, PDA)**로 컴파일합니다. 이는 스택이 장착된 유한 상태 기계입니다.

간단하게 문자열 name과 정수 age를 포함하는 객체를 요구하는 스키마를 추적해 보겠습니다:

1. State 0 (시작): 유효한 문자는 {만 가능합니다.
2. State 1 (키 예상): 유효한 문자열 시퀀스는 `

문법이 상태 $S_t$에 있을 때, 엔진은 푸시다운 오토마타(Pushdown Automaton)의 현재 상태를 기준으로 트라이(Trie)를 따라 이동합니다. 토큰 ID가 유효하려면 토큰의 바이트 문자열에 있는 모든 문자가 문법 상태 기계에서 유효한 경로를 나타내야 합니다.

4. 단계 3: 런타임 로짓 마스킹 (Runtime Logit Masking) (수학적 필터)

엔진이 현재 상태 $S_t$에 대해 유효한 토큰의 부분집합 $V_{ ext{valid}} riangleq V$를 결정하면, 로짓 마스크 벡터(Logit Mask Vector) $M riangleq ext{R}^{|V|}$을 구성합니다:

$$M_i = \begin{cases} 0 & \text{if } i \in V_{\text{valid}} \ -\infty & \text{if } i \notin V_{\text{valid}} \end{cases}$$

이 마스크는 트랜스포머 순전파(transformer forward pass)를 통해 출력된 원시 로짓 벡터 $z$에 Softmax가 계산되기 전에 직접 더해집니다:

$$\tilde{z} = z + M$$

$$\tilde{z}i = \begin{cases} z_i & \text{if } i \in V{\text{valid}} \ -\infty & \text{if } i \notin V_{\text{valid}} \end{cases}$$

이제, 유효하지 않은 토큰 $k
otin V_{ ext{valid}}$에 대한 Softmax 확률을 계산할 때 어떤 일이 발생하는지 살펴보겠습니다:

$$P(w_k) = \frac{e^{\tilde{z}k}}{\sum{j=1}^{|V|} e^{\tilde{z}j}} = \frac{e^{-\infty}}{\sum{j=1}^{|V|} e^{\tilde{z}_j}} = \frac{0}{\sum_{j=1}^{|V|} e^{\tilde{z}_j}} = 0$$

$e^{-\infty} = 0$이므로, 모든 유효하지 않은 토큰의 확률은 수학적으로 0이 됩니다.

샘플러가 다음 토큰을 선택할 때, JSON 스키마를 위반하는 것을 물리적으로는 불가능합니다. 모델이 학습한 지식과 어텐션 가중치가 어떤 유효한 토큰을 선택할지 결정하지만, 문법이 샌드박스(sandbox)를 정의합니다.

[ 트랜스포머 순전파 ] ──► 원시 로짓: [ 4.2,  1.1,  8.7,  -0.5, ... ] (128k 항목)
                                                    │
[ 문법 상태 + 어휘 트라이 ] ─► 마스크 벡터: [ 0.0, -inf,  0.0,  -inf, ... ]
...

5. 단계 4: 결정론적 점프 디코딩 (Deterministic Jump Decoding) (토큰 패스트 포워딩)

모델이 키 `

스키마에 따르면 키 이름은 고정되어 있습니다. 콜론 :도 고정입니다. 필드가 불리언(boolean)인 경우, 허용되는 토큰은 true 또는 false만 있습니다.

700억 개의 파라미터에 걸쳐 무거운 행렬 곱셈을 값비싼 GPU에서 수행하여 단지 ": " 문자나 알려진 키의 닫는 따옴표를 예측하는 데 사용할 필요가 있을까요?

현대의 제약 디코딩 엔진은 점프 디코딩(Jump Decoding) (토큰 인필(Token Infill) 또는 Speculative Schema Fast-Forwarding이라고도 함)을 구현합니다:

1. 상태 $S_t$에서, 엔진은 유효한 다음 토큰 집합 $V_{\text{valid}}$를 평가합니다.
2. 만약 $|V_{\text{valid}}| = 1$ (법적인 토큰이 정확히 하나인 경우), 또는 스키마가 리터럴 문자열 상수(literal string constant)를 지정하는 경우, 엔진은 트랜스포머 순방향 계산(forward pass)을 완전히 건너뜁니다.
3. 이는 알려진 토큰을 출력 시퀀스에 직접 추가하고, KV 캐시를 업데이트하며, 문법 상태 기계(grammar state machine)를 전진시키고, 다음 결정 지점으로 계속합니다.

Output: { "status": "active" } 
          ▲       ▲▲        ▲▲
          │       ││        ││
...

출력 토큰의 40%에서 60%가 예측 가능한 스키마 골조(keys, brackets, whitespace, punctuation)인 구조화된 추출 작업에서, 점프 디코딩은 비제약적 디코딩에 비해 전체 생성 처리량(throughput)을 2배에서 3배 증가시킬 수 있습니다.

6. 엔지니어링 병목 현상: 마스킹 지연 시간 대 GPU 처리량

로짓 마스킹(logit masking)은 이론적으로는 간단하게 들리지만, 순진한 구현 방식은 심각한 추론 병목 현상을 초래합니다.

고처리량 서비스(high-throughput serving)를 고려해 봅시다:

• NVIDIA H100에서 토큰을 생성하는 64개 요청 배치.
• 어휘 크기: 128,000개의 토큰.
• 각 디코드 단계는 GPU에서 약 8ms가 소요됩니다.
• 만약 PDA를 평가하고 CPU에서 Python으로 128,000개의 로짓을 업데이트하는 데 한 단계당 10ms가 걸린다면, GPU는 텐서 산술(tensor arithmetic)을 수행하기보다 CPU 마스크를 기다리는 데 더 많은 시간을 보내게 됩니다!

현대 엔진의 해결책 (vLLM xgrammar & SGLang):

현대 엔진의 해결책 (vLLM xgrammar & SGLang):

1. 사전 할당된 비트셋 조회 테이블(Pre-allocated Bitset Lookup Tables): 마스크를 실시간으로 계산하는 대신, 정적 상태(키워드, 불리언 분기, 구두점 등)는 각 비트가 $V$의 토큰 ID에 대응하는 비트셋으로 미리 컴파일됩니다.
2. 커스텀 CUDA 로짓-마스킹 커널(Custom CUDA Logit-Masking Kernels): 이 비트셋은 GPU 메모리에 한 번 복사됩니다. 전용 CUDA/Triton 커널이 128k 개의 모든 로짓에 $-\infty$ 마스크를 50 마이크로초(0.05ms) 미만으로 병렬 적용합니다.
3. 적응형 토큰 트라이 가지치기(Adaptive Token Trie Pruning): 고빈도 접두사(prefix)는 L1/L2 CPU 캐시에 캐시되어, 문법 전환 중 포인터 추적(pointer chasing)을 최소화합니다.

7. 개발자가 알아야 할 실질적인 함정 (Practical Gotchas)

구조화된 출력이 구문 유효성(syntax validity)을 보장하더라도, 실제 엔지니어링 상의 트레이드오프가 존재합니다:

1. 모델 분포 왜곡 (Model Distribution Distortion)

LLM에게 엄격한 스키마를 따르도록 강제할 경우, 이는 모델의 자연적인 확률 분포(natural probability distribution)를 잘라내는 것과 같습니다. 만약 스키마가 모델이 추론하는 방식(예: `

실제 운영 환경에서 Structured Outputs를 사용할 때는 실제로 무슨 일이 일어나고 있는지 기억해야 합니다:

1. 스키마 → PDA: 사용자의 JSON 스키마는 객체/배열 중첩을 추적하기 위한 명시적 스택(stack)을 가진 푸시다운 오토마타(Pushdown Automaton, PDA) 상태 기계로 컴파일됩니다.
2. 어휘 트라이 순회 (Vocab Trie Traversal): 토크나이저의 어휘(vocabulary)는 이 오토마타와 일치시켜 유효한 토큰 ID의 정확한 부분집합을 찾습니다.
3. 로짓 마스킹 (Logit Masking): Softmax를 수행하기 전에 유효하지 않은 토큰 위치들은 $-\infty$로 덮어쓰여지며, 이들의 샘플링 확률은 정확히 0%가 됩니다.
4. 점프 디코딩 (Jump Decoding): 결정론적인 스키마 골격(keys, colons, brackets)은 GPU 계산을 완전히 우회하고 KV 캐시(KV cache)에 직접 주입됩니다.

LLM으로부터의 보장된 JSON 출력은 마법 같은 프롬프트 엔지니어링이 아닙니다. 그것은 확률적 토큰 샘플링을 제어하는 결정론적인 형식 언어 이론입니다.