LLM 정형 출력(Structured Outputs)과 문법 제약 디코딩(Grammar-Constrained Decoding) 원리 해부: Logit Masking부터 FSM·XGrammar까지

LLM의 로짓(Logit) 확률 분포에 문법 제약 유한 상태 기계(FSM)를 결합하여 비문법적 토큰을 마스킹하고 100% 정형 JSON 구조를 보장하는 제약 디코딩(Constrained Decoding) 아키텍처를 상징하는 추상 기하학 아트워크다. 중앙의 다면체 상태 프리즘과 오비탈 궤도망을 통해 무질서한 토큰 파동이 결정론적 데이터 격자로 정렬되는 가속 파이프라인을 표현했다.

대규모 언어 모델(LLM)을 소프트웨어 백엔드 시스템, 데이터 파이프라인, 그리고 자율형 AI 에이전트의 도구 호출(Tool Calling) 인터페이스로 결합할 때 마주치는 가장 고질적인 장애물은 '비결정론적 출력 형식 붕괴'다. 프롬프트에 아무리 "반드시 순수 JSON만 출력하라", "마크다운 코드 블록(```)을 붙이지 마라", "말미 쉼표(Trailing Comma)를 넣지 마라"고 간청해도, 모델은 확률적 샘플링 과정에서 간헐적으로 구문 오류(Syntax Error)를 일으킨다. OpenAI — Introducing Structured Outputs in the API, XGrammar — Flexible and Efficient Structured Generation Engine

결론부터 말하면 프롬프트 엔지니어링이나 사후 정규식 파싱(Parse-and-Pray)에 의존하는 방식은 90~95%의 불안정한 성공률과 치명적인 런타임 재시도 오버헤드를 유발하며, 프로덕션 레벨의 신뢰성을 확보하기 위해서는 추론 서빙 엔진 레벨에서 비문법적 토큰의 생성을 원천 차단하는 '문법 제약 디코딩(Grammar-Constrained Decoding)'이 필수적이다. 제약 디코딩은 JSON Schema나 정규식을 유한 상태 기계(FSM) 또는 문맥 자유 문법(CFG)으로 컴파일한 뒤, 매 디코딩 스텝마다 다음 상태로 전이 가능한 유효 토큰(Allowed Tokens)을 제외한 모든 토큰의 Logit을 $-\infty$ 로 마스킹하여 Softmax 확률을 0%로 강제한다. 이를 통해 단 1회의 재시도나 수동 복구 로직 없이 100% 완벽한 구문 무결성과 엄격한 타입 준수를 달성할 수 있다.

이 글에서는 전통적 파싱 방식의 한계를 살펴보고, Outlines와 XGrammar 등 현대 문법 제약 디코딩 엔진의 FSM 상태 전이 및 Logit Masking 내부 메커니즘을 상세히 해부한다. 또한 5가지 핵심 검증 시나리오를 로컬 Python 시뮬레이션 스크립트로 직접 구현·실행하여 100% 구문 준수율을 입증하고, 프로덕션 환경에서 추론 오버헤드를 최소화하기 위한 실무 최적화 체크리스트를 정리한다.

1. 전통적 'Parse-and-Pray'의 붕괴: 프롬프트 의존의 한계와 에이전트 비용 폭증

전통적인 LLM 정형 데이터 생성 파이프라인은 '생성 후 파싱(Parse-and-Pray)' 방식에 의존했다. 시스템 프롬프트에 대상 JSON의 구조와 예시를 제공하고, 모델이 생성한 텍스트를 json.loads()나 JSON.parse()로 파싱하는 구조다.

그러나 이 방식은 프로덕션 환경, 특히 수십 단계의 도구 호출을 연속으로 수행하는 자율형 AI 에이전트에서 치명적인 문제를 일으킨다.

BPE 토크나이저의 경계 불일치: 토크나이저는 단어 단위가 아니라 빈번하게 등장하는 서브워드 바이트 조각으로 토큰을 분할한다. 예를 들어 {"age": 뒤에 숫자가 와야 하는 상황에서, 모델의 어휘 사전(Vocab)에는 " 20", "\n", "", null 등 수만 개의 토큰이 공존한다. 확률적 샘플링(Temperature > 0) 과정에서 아주 작은 엔트로피 섭동만 발생해도 문법에 맞지 않는 토큰이 선택될 수 있다.

치명적인 구문 오류 패턴:

말미 쉼표(Trailing Comma): {"items": [1, 2, ],} — 표준 JSON 사양에서 엄격히 금지된 쉼표가 붙어 파서가 즉시 중단된다.

키 따옴표 누락 및 작은따옴표 사용: {name: 'Alice'} — Python 딕셔너리 표현식과 혼동하여 유효하지 않은 JSON을 반환한다.

불필요한 해설(Conversational Filler) 유출: Sure! Here is the JSON output you requested: {"status": "ok"}

조기 종료(Premature End-of-Sequence): 복잡한 중첩 객체 생성 도중 토큰 제한이나 어텐션 누락으로 괄호(})를 닫지 않고 생성을 종료한다.

비용 및 지연 시간(Latency)의 기하급수적 증가: 구문 분석이 실패할 때마다 전체 컨텍스트를 다시 담아 재호출(Retry)을 수행해야 한다. 에이전트 워크플로가 5단계 루프를 도는데 각 단계마다 5%의 실패율이 발생한다면, 전체 파이프라인이 한 번에 완주할 확률은 약 77%로 급락한다.

소형 오픈 모델(3B~8B) 서빙의 불가능성: 대형 상용 모델(GPT-4o, Claude 3.5 Sonnet, Gemini 1.5 Pro)은 프롬프트 지시 준수율이 비교적 높지만, 온프레미스나 엣지에서 기동하는 3B~8B 파라미터 소형 모델은 복잡한 JSON 스키마를 프롬프트만으로 일관되게 생성하는 데 빈번히 실패한다.

전통적인 Parse-and-Pray(프롬프트 자연어 지시 + 사후 JSON.parse 재시도 루프) 방식과 최신 문법 제약 디코딩(FSM 컴파일 + 매 스텝 Logit Masking) 아키텍처의 동작 흐름 비교 다이어그램이다. 불완전한 출력이 네트워크로 전달되기 전에 서빙 엔진 단계에서 비문법적 토큰을 마스킹하여 구문 오류를 원천 차단하는 원리를 도식화했다.

이러한 문제를 해결하기 위해 등장한 것이 바로 문법 제약 디코딩(Grammar-Constrained Decoding)이다.

2. 문법 제약 디코딩의 핵심 메커니즘: FSM 컴파일과 매 스텝 Logit Masking

문법 제약 디코딩의 기본 철학은 단순하면서도 강력하다: "문법에 어긋나는 토큰은 애초에 샘플링될 확률을 0으로 만들어 단 한 글자도 생성되지 못하게 막는다."

이 목표를 달성하기 위해 서빙 엔진은 크게 세 단계의 파이프라인을 거친다.

1) JSON Schema의 유한 상태 기계(FSM) / 정규식 컴파일

제약 디코딩 엔진(Outlines, XGrammar, LM Format Enforcer 등)은 사용자가 전달한 Pydantic 모델이나 JSON Schema를 입력받아 먼저 정규식(Regex) 또는 문맥 자유 문법(CFG)으로 변환한 뒤, 이를 결정론적 유한 상태 기계(Deterministic Finite Automaton, DFA)로 컴파일한다.

상태 $S_0$ (시작): 오직 { 토큰만 허용

상태 $S_1$ (객체 내부): 오직 따옴표(") 토큰만 허용

상태 $S_2$ (키 명칭): 스키마에 정의된 프로퍼티 이름("name", "age")만 허용

상태 $S_3$ (콜론 구분자): 오직 : 토큰만 허용

상태 $S_4$ (타입 제약 값): 해당 필드의 데이터 타입(정수면 숫자 토큰, 불리언이면 true|false, enum이면 지정된 문자열)만 허용

2) 토크나이저 어휘 사전과 FSM 상태의 사전 색인(Pre-indexing)

LLM의 출력 단위는 단일 문자가 아니라 서브워드 토큰(예: "name", ": ", ",\n ")이다. 따라서 FSM은 단순 문자 단위 전이가 아니라, "현재 FSM 상태에서 해당 서브워드 토큰의 모든 바이트를 차례로 소비했을 때 유효한 다음 상태로 도달할 수 있는가?"를 검사해야 한다.

고성능 엔진인 XGrammar는 모델의 어휘 사전(Vocabulary, 통상 32,000~128,000개 토큰) 전체에 대해 각 FSM 상태별로 전이 가능한 유효 토큰 ID 집합(Allowed Token Bitmask)을 사전에 계산하고 압축 인덱스로 캐싱한다.

이를 통해 런타임 추론 시 복잡한 정규식 파싱을 반복하지 않고, 고정된 비트마스크 연산만으로 마이크로초 단위의 초고속 토큰 필터링을 달성한다.

3) 매 스텝 Logit Masking 연산 수학

디코딩 스텝 $t$ 에서 LLM 백본 신경망이 생성한 생 로짓(Raw Logit) 벡터를 $z \in \mathbb{R}^{|V|}$ 라고 하자. 현재 FSM 상태 $S_t$ 에서 허용된 유효 토큰의 인덱스 집합을 $A(S_t) \subseteq \{0, 1, \dots, |V|-1\}$ 라 할 때, 마스킹된 로짓 $z'$ 는 다음과 같이 계산된다.

z'_i = \begin{cases} z_i & \text{if } i \in A(S_t) \\ -\infty & \text{if } i \notin A(S_t) \end{cases}

이후 온도(Temperature) 파라미터 $T$ 를 적용한 Softmax 확률 분포는 다음과 같다.

P(t_{k}) = \frac{\exp(z'_k / T)}{\sum_{j \in A(S_t)} \exp(z'_j / T)}

허용 집합에 속하지 않는 모든 토큰은 분자의 $\exp(-\infty) = 0$ 이 되므로, 비문법적 토큰이 샘플링될 확률은 수학적으로 완벽하게 $0.0000\%$ 로 수렴한다.

JSON Schema를 따르는 유한 상태 기계(FSM)의 상태 전이 단계(S0 시작부터 S5 완료까지)와 특정 스텝에서의 LLM Raw Logits이 FSM Allowed Filter를 거쳐 최종 Softmax 확률 0%로 마스킹되는 텐서 변환 메커니즘을 상세히 나타낸 다이어그램이다.

결과적으로 모델은 오직 유효한 문법 경로만을 순회하며 토큰을 생성하게 되며, 최종 완성된 문자열은 단 한 번의 예외도 없이 100% 온전한 JSON으로 귀결된다.

3. 정형 데이터 생성 기법 비교

정형 데이터 생성을 구현하는 주요 기술들의 특성과 실무 적합성을 비교하면 다음과 같다.

구분	1. 순수 프롬프트 지시 (Prompt Only)	2. 사후 파싱 & 수동 복구 (JSON Repair)	3. Outlines (Regex FSM)	4. XGrammar (MLC / vLLM / SGLang)
작동 계층	어플리케이션 레이어	어플리케이션 레이어	추론 서빙 미들웨어	서빙 엔진 네이티브 커널
구문 무결성 보장	보장 불가 (90~95%)	일부 휴리스틱 복구 (96~98%)	100% 완벽 보장	100% 완벽 보장
컴파일 오버헤드	없음 (0ms)	없음 (0ms)	보통 (수십~수백 ms)	초고속 AOT/JIT 최적화
토큰 생성 지연 오버헤드	없음 (기본 속도)	사후 파싱 지연만 발생	상태 전이에 따른 약간의 지연	비트마스크 최적화로 <1% 오버헤드
소형 모델(3B~8B) 안정성	매우 취약 (빈번한 붕괴)	불안정 (복구 실패 빈번)	매우 우수 (100% 성공)	매우 우수 (100% 성공)
지원 문법 범위	자연어 유도	일반 JSON 한정	정규식, JSON Schema, CFG	JSON Schema, EBNF, 구조화 언어
주요 채택 생태계	초기 프로토타입	jsonrepair 라이브러리	vLLM, HuggingFace Transformers	vLLM, SGLang, MLC-LLM, Ollama

4. 로컬 Python으로 검증하는 FSM 제약 디코딩 및 로짓 마스킹 시뮬레이션

실제 문법 제약 디코딩의 토큰 상태 전이와 로짓 마스킹 메커니즘을 로컬 Python 스크립트(test_constrained_decoding.py)로 구현하여 검증했다.

직접 실행해 확인한 5가지 핵심 검증 시나리오

로컬 터미널 환경에서 위 검증 스크립트를 직접 실행하여 5가지 시나리오가 모두 정상 통과(All 5 Constrained Decoding verification checks passed successfully!)함을 확인했다.

초기 상태 루트 구문 제약 (Case 1): 생성 시작 시점(State 0)에서 오직 여는 중괄호({) 토큰 하나만 허용 집합에 포함되며, 알파벳이나 숫자, 닫는 괄호 등 기타 모든 토큰이 배제됨을 확인했다.

키 따옴표 및 순차 스키마 전이 (Case 2): 객체 시작 후 반드시 큰따옴표(")가 유도되고, 이후 대상 스키마가 규정하는 프로퍼티 이름("name")만 활성화되며 무관한 임의 텍스트가 차단됨을 확인했다.

엄격한 값 타입 제약 및 로짓 마스킹 (Case 3): 나이("age") 필드의 값 입력 단계(State 13)에서 모델이 환각으로 인해 불리언("true", Logit +100.0)이나 문자열에 가장 높은 점수를 부여했더라도, 마스킹을 통해 해당 토큰들이 즉시 $-\infty$ 로 처리되고 오직 유효한 정수형 토큰("25")만 샘플링됨을 검증했다.

조기 종료 및 불완전 종결 차단 (Case 4): 필수 필드(name, age, is_admin)가 모두 온전하게 생성되기 전에는 종료 토큰(} 또는 <eos>) 생성이 원천 차단되며, 쉼표(,)를 거쳐 마지막 필드까지 도달한 후에만 종료가 승인됨을 확인했다.

극단적 로짓 노이즈 하에서의 100회 엔드투엔드 무작위 생성 (Case 5): 매 스텝마다 $[-50.0, +50.0]$ 범위의 극단적인 무작위 로짓 노이즈를 주입하고 높은 온도( $T = 1.2$ )로 샘플링을 진행했음에도, 100회 생성 시도 모두에서 단 한 번의 구문 에러 없이 100% 스키마를 만족하는 유효한 JSON({"name":"Charlie","age":20,"is_admin":true} 등)이 생성됨을 입증했다.

검증 범위 명시: 위 결과는 단일 프로세스 메모리 상에서의 토크나이저 어휘 매핑, FSM 상태 전이, 로짓 마스킹 및 Softmax 샘플링 로직의 수학적·구조적 무결성 검증이다. 실제 거대 GPU 클러스터 서빙 시의 텐서 병렬화(TP), 플래시어텐션 커널과의 메모리 대역폭 간섭, 멀티배치 융합 오버헤드는 별도의 분산 서빙 벤치마크 환경에서 측정되어야 한다.