문법 제약 디코딩: 모든 토큰에서 LLM이 유효한 구문을 출력하도록 강제하기

LLM에게 JSON 객체를 생성하라고 요청하면, 결국 뒤에 쉼표를 붙이거나 문자열 안에 이스케이프되지 않은 줄바꿈을 넣거나, 따옴표로 묶인 키가 있어야 할 자리에 bare word를 출력한다. 이 오류는 모델의 버그가 아니다. autoregressive sampling이 작동하는 방식의 결과다: 매 단계에서 모델은 어휘의 모든 토큰을 후보로 본다. 여기에는 부분 출력을 구문적으로 invalid하게 만들 토큰도 포함된다.

이는 토큰 어휘 자체를 제한함으로써 고칠 수 있다. 모델이 3만 2천 개의 토큰 중에서 고르게 하지 말고, 부분 파스를 유효한 상태로 유지하는 부분집합만 주어라. 이 기술은 grammar-constrained decoding이라 불리며, LLM을 확률적 텍스트 생성기에서 구문 인식 코드 합성기로 바꾼다.

프롬프트 엔지니어링이 구문 유효성을 해결할 수 없는 이유

대부분의 개발자는 뻔한 접근법으로 시작한다. 시스템 프롬프트에 “Output valid JSON only”를 추가하고, 사용자 메시지에서 schema를 반복하고, 기대한다. 이는 도움이 되지만 보장은 아니다.

모델은 생성 중에 자신의 출력을 파싱하지 않는다. 프롬프트와 지금까지 생성된 모든 것을 조건으로, 어휘에 대한 확률 분포를 기반으로 다음 토큰을 예측한다. , 같은 토큰은 닫는 중괄호 뒤에 높은 확률을 가질 수 있는데, 학습 데이터에서 해당 위치에 쉼표가 자주 나타나기 때문이다. 이 특정 JSON 객체의 이 정확한 지점에서 그 쉼표가 구문적으로 합법적인지는 모델의 의사결정 과정에 포함되지 않는다.

RLHF로 미세 조정된 모델조차도 확률 질량을 일반적으로 올바른 패턴 쪽으로 이동시킬 뿐이다. invalid 경로를 제거하지 않는다. 보장이 필요한데 높은 확률로는 부족하다면, sampling mechanism 자체를 바꿔야 한다.

문법 제약 디코딩의 작동 원리

핵심 아이디어는 간단하다. LLM의 생성과 함께 parser state를 유지하고, 각 토큰 위치에서 파서를 error state로 전이시키는 모든 토큰을 마스킹한다.

t 단계에서 모델은 전체 어휘에 대한 logits 벡터를 출력한다. 보통은 temperature scaling을 적용하고 sampling한다. constrained decoding에서는 먼저 grammar engine에 묻는다. 지금까지 생성된 토큰을 고려할 때, 다음에 합법적인 토큰은 무엇인가? engine은 어휘에 대한 bitmask를 반환한다. illegal 토큰의 logits을 음의 무한대로 설정하고, 나머지에 대해 softmax를 실행한 뒤, 필터링된 분포에서 sampling한다.

grammar engine은 사후에 전체 출력을 parse할 필요가 없다. incremental하게 parse한다. 각 토큰이 수락된 후 낭비 state machine을 업데이트한다. 파서가 accepting state에 도달하면 생성을 멈출 수 있다. non-accepting state에 있으면 생성이 계속된다.

이는 모델이 여전히 모든 구문적으로 valid한 연속 작업 중에서 자유롭게 선택할 수 있다는 의미다. grammar 안에서 창의성을 유지한다. 단지 그 밖으로 나갈 수 없을 뿐이다.

구현은 어떻게 생겼는가

다음은 현대적인 parsing library인 lark를 사용하여 grammar mask를 구축하는 단순화된 Python sketch다. 프로덕션에서는 outlines, guidance 또는 llama.cpp의 내장 GBNF 지원과 같은 더 빠른 engine을 사용하겠지만, 원리는 동일하다.

from lark import Lark, Token
from transformers import AutoTokenizer, AutoModelForCausalLM
import torch

# Define a tiny grammar for a simple config DSL.
grammar = r"""
    start: pair+
    pair: KEY "=" VALUE
    KEY: /[a-z_]+/
    VALUE: /"[^"]*"/
"""

parser = Lark(grammar, parser="lalr")
tokenizer = AutoTokenizer.from_pretrained("meta-llama/Llama-2-7b-hf")
model = AutoModelForCausalLM.from_pretrained("meta-llama/Llama-2-7b-hf")

def legal_next_tokens(partial_text: str) -> set[int]:
    """Return token IDs that do not cause a parse error."""
    legal = set()
    for token_id in range(tokenizer.vocab_size):
        candidate = tokenizer.decode([token_id], skip_special_tokens=True)
        try:
            # Try parsing partial_text + candidate as a prefix.
            parser.parse(partial_text + candidate)
            legal.add(token_id)
        except Exception:
            # Some exceptions are expected mid-parse.
            # A production engine tracks parser state, not exceptions.
            pass
    return legal

# Generate one token at a time with grammar masking.
prompt = "Generate a config: "
input_ids = tokenizer.encode(prompt, return_tensors="pt")
generated = input_ids.clone()

for _ in range(50):
    outputs = model(generated)
    logits = outputs.logits[:, -1, :]

    partial = tokenizer.decode(generated[0], skip_special_tokens=True)
    legal_ids = legal_next_tokens(partial)

    mask = torch.full_like(logits, float("-inf"))
    for tid in legal_ids:
        mask[0, tid] = logits[0, tid]

    next_token = torch.argmax(mask, dim=-1).unsqueeze(0)
    generated = torch.cat([generated, next_token], dim=-1)

    # Stop if the parser is in an accepting state.
    if parser.parse(partial):
        break

print(tokenizer.decode(generated[0], skip_special_tokens=True))

이는 naive한 구현이다. 실제 시스템은 각 단계에서 vocabulary 전체를 반복하지 않는다. 미리 grammar에서 finite-state automaton을 구축하고, 각 automaton state에서 어떤 vocabulary 토큰이 valid한지 사전 계산한다. 생성 시점에는 mask가 단일 table lookup이다.

bounded context에서 constrained decoding이 맞는 위치

Domain-Driven Design의 bounded contexts는 ubiquitous language로 정의된다. 그 언어는 종종 작은 DSL로 형식화된다. query syntax, rule grammar, config format, 또는 expression language다. LLM에게 해당 context 내에서 artifact를 생성하거나 편집하라고 요청할 때, 올바른 언어를 사용하길 원한다.

grammar constraints는 boundary를 강제한다. LLM은 DSL에 존재하지 않는 field를 발명할 수 없고, mismatched brackets를 출력할 수 없으며, 허용된 enum set 밖의 값을 생성할 수 없다. 구문은 compile-time guarantee가 되며, runtime prayer가 아니다.

이는 특히 LLM 출력이 직접 parser나 interpreter로 전달될 때 가치가 있다. DSL이 strict한 recursive descent parser로 parse된다면, 단일 unexpected token으로 파이프라인 전체가 중단된다. constrained decoding은 그 failure mode를 제거한다.

알아야 할 트레이드오프

constrained decoding은 공짜가 아니다. overhead는 grammar engine을 어떻게 구현하느냐에 달려 있다.

처리량. 각 forward pass에서 mask를 구축하면 지연이 추가된다. outlines나 GBNF를 사용하는 llama.cpp 같은 빠른 engine은 token-to-state mapping을 사전 계산하여 단계당 비용을 약 5~10% overhead로 줄인다. 각 후보 토큰에서 re-parse하는 naive한 구현은 생성을 수 차례 느리게 할 수 있다.

grammar expressiveness. 모든 구문이 token mask에 깔끔하게 매핑되는 grammar로 쉽게 표현되는 것은 아니다. “이 identifier는 scope에서 더 일찍 선언되어야 한다”와 같은 문맥 의존 규칙은 표준 context-free grammars에서 포착되지 않는다. grammar로 구문을 제약할 수 있다. 추가 machinery 없이 의미를 제약할 수는 없다.

model compatibility. 일부 inference API, 특히 호스팅되는 cloud API는 logits를 노출하거나 custom masking을 허용하지 않는다. OpenAI API는 JSON mode를 제공하는데, 이는 JSON 전용의 hardcoded grammar constraint이지만, 자신의 grammar는 가져올 수 없다. custom DSL의 경우 보통 local inference나 logits를 노출하는 framework가 필요하다.

partial token problems. token boundary가 항상 grammar boundary와 일치하는 것은 아니다. grammar가 quoted string을 기대할 수 있지만, 다음 토큰은 "hel에 이어 lo"일 수 있다. grammar engine은 전체 토큰이 아닌 partial token matches에 대해 추론해야 한다. production libraries는 토큰을 character prefixes에 매핑하고 prefix validity를 grammar에 대해 검사함으로써 이를 처리한다.

오늘 실제로 이를 구현하는 방법

grammar engine을 처음부터 작성할 필요는 없다. 여러 library가 어려운 부분을 처리한다.

**outlines**는 Python 사용자가 가장 쉽게 접근할 수 있다. Pydantic model이나 regular expression을 정의하면, constraint를 효율적인 finite-state automaton으로 컴파일하여 Hugging Face transformers와 vLLM과 통합한다.

from outlines import models, generate

model = models.transformers("microsoft/Phi-3-mini-4k-instruct")
generator = generate.regex(model, r'\{[a-z_]+\}')
result = generator("Extract the key: ")

**guidance**는 Microsoft가 제공하는 더 풍부한 templating system이다. grammar constraints를 prompt template과 뒤섞고, masking은 내부적으로 처리한다.

**llama.cpp**는 GBNF(GGML BNF), BNF와 유사한 grammar format을 지원한다. inference 시 .gbnf 파일을 전달하면 engine이 C++ 수준에서 이를 강제한다. 이는 local inference에 가장 빠른 선택지다.

**jsonformer**와 **instructor**는 JSON 전용의 더 가벼운 대안이다. grammar-like constraints를 사용하지만 JSON schema로 제한된다. bounded context DSL이 우연히 JSON-shaped라면, 가장 쉬운 starting point이다.

constrained decoding이 고치지 못하는 것

grammar-constrained LLM도 여전히 semantically 잘못된 출력을 생성할 수 있다. 존재하지 않는 table을 참조하는 valid한 SQL query나, invalid한 port number를 설정하는 valid한 config를 출력할 수 있다. 구문은 필요한 guardrail이지만, 충분한 guardrail은 아니다.

LLM 아래에는 여전히 validation layer가 필요하다. 출력을 parse하고, domain model에 대해 type-check를 하며, 의미가 틀리면 reject하거나 retry한다. constrained decoding은 failure mode를 “syntax error”에서 “logic error”로 줄인다. 이는 큰 개선이지만 free pass는 아니다.

또한 grammar constraints는 모델을 더 똑똑하게 만들지 않는다. grammar가 너무 permissive하면 모델은 여전히 무의미하지만 구문적으로 valid한 영역으로 빠질 수 있다. grammar가 너무 restrictive하면 모델에 올바른 답을 표현할 valid한 path가 없어, low-probability garbage나 repetitive loop가 나온다. grammar 설계는 engineering 작업의 일부다.

모델이 아닌 출력 형식부터 시작하라

프롬프트를 튜닝하거나 더 큰 모델로 전환하기 전에, 문제가 정말 reasoning인지 syntax인지 자문하라. LLM이 원하는 것을 이해하지만 가끔 포맷을 틀리면, grammar constraints가 올바른 수정이다. fine-tuning보다 저렴하고, prompt engineering보다 신뢰할 수 있으며, sampling 단독으로는 얻을 수 없는 보장을 준다.

bounded context DSL의 grammar를 정의하고, constrained decoder에 연결하고, 모델이 선 안에서 생성하게 하라. 출력은 여전히 가끔 놀랍겠지만, syntax error는 결코 아닐 것이다.

FAQ

grammar-constrained decoding이란 무엇인가?

grammar-constrained decoding은 형식 문법을 사용하여 각 생성 단계에서 LLM의 어휘를 필터링하는 기술이다. 부분 출력을 구문적으로 valid하게 유지하는 토큰만 고려되며, 최종 출력이 문법을 준수함을 보장한다.

constrained decoding은 출력 품질을 떨어뜨리는가?

구문에 묶인 작업에서는 그렇지 않다. 모델은 여전히 모든 문법적으로 valid한 연속 작업 중에서 자유롭게 선택한다. 열린 창작 글쓰기에서는 제약이 품질을 해칠 것이다. 코드, config, DSL 생성에서는 correctness와 reliability를 모두 향상시킨다.

OpenAI나 Claude API에서 이를 사용할 수 있는가?

OpenAI는 JSON mode를 제공하는데, 이는 JSON 전용의 built-in grammar constraint이다. 자신의 grammar는 가져올 수 없다. Anthropic은 현재 grammar constraints를 노출하지 않는다. custom DSL의 경우 보통 vLLM, llama.cpp, 또는 유사한 engine을 이용한 local inference가 필요하다.

어떤 grammar format이 지원되는가?

일반적인 format에는 EBNF, BNF, PEG, GBNF가 포함된다. outlines 같은 library는 regular expression과 Pydantic model을 받는다. llama.cpp는 GBNF를 사용한다. inference engine이 지원하는 format을 선택하라.