모델은 유효한 JSON이 어떻게 생겼는지 알고 있음에도 불구하고, 여러분의 파서(Parser)가 거부하는 응답을 생성할 수 있습니다.

예를 들어, 다음 응답들은 각각 유효해 보이는 JSON 객체를 포함하고 있습니다.

결과입니다:

```json
{"answer": "72"}
```

{"answer": "72"}

계산식은 48 + 24입니다.

{"answer": "72"}
{"answer": "72"}

사람은 즉시 정답을 식별할 수 있습니다.

하지만 정확히 하나의 JSON 값만을 기대하는 프로그램은 그렇지 못합니다.

이것이 제가 더 구체적으로 이해하고 싶었던 차이점입니다:

프롬프팅(Prompting)은 어떤 출력이 나타날 가능성이 높은지를 변경합니다. 제약 디코딩(Constrained decoding)은 어떤 출력이 허용되는지를 변경합니다.

저는 토크나이저(Tokenizer), 생성(Generation), 검증(Validation), 그리고 로짓 프로세싱(Logit-processing) 단계에서 그 차이를 조사하기 위해 Qwen2.5-0.5B-Instruct를 기반으로 작은 로컬 실험실을 구축했습니다.

해당 저장소(Repository)에는 스크립트, 원시 생성물(Raw generations), 관찰 내용, 그리고 JSONL 평가 로그가 포함되어 있습니다:

github.com/Vaibhav701161/constrained-decoding-lab

실험

저는 세 가지 간단한 초등 수학 문제를 사용하여 두 가지 생성 조건(Generation conditions)을 비교했습니다.

자유 형식(Free-form) 프롬프트는 모델에게 짧은 추론 과정을 보여주고 숫자로 된 정답으로 끝내도록 요청했습니다.

구조화된(Structured) 프롬프트는 정확히 하나의 JSON 객체를 반환하도록 요청했습니다:

{
  "reasoning": "여기에 추론 내용을 작성하세요",
  "answer": "여기에 최종 숫자 정답을 작성하세요"
...

생성은 다음을 사용하여 결정론적(Deterministic)으로 수행되었습니다:

do_sample=False

모든 예시에 대해 평가 스크립트는 다음 항목을 기록했습니다:

• 프롬프트 및 원시 출력(Raw output)
• 파싱된 표현(Parsed representation)
• JSON 유효성(Validity)
• 스키마(Schema) 유효성
• 추출된 정답
• 완전 일치(Exact-match) 정확도
• 프롬프트 및 생성된 토큰 수
• 지연 시간(Latency)
• 파싱 또는 검증 오류

초기 스모크 테스트(Smoke-test) 결과는 다음과 같습니다:

이 결과를 벤치마크(Benchmark)로 취급해서는 안 됩니다.

직접 선별한 세 가지 예시는 너무 적으며, 추출 로직 또한 의도적으로 단순하게 설계되었습니다.

실패 사례(failure modes)들은 여전히 유용했습니다.

JSON 프롬프트가 적용된 출력물에는 다음과 같은 것들이 포함되었습니다:

• Markdown 코드 블록으로 감싸진 JSON (Markdown-fenced JSON)
• 유효해 보이는 JSON 뒤에 산문(prose)이 이어지는 경우
• 하나의 응답에 여러 개의 JSON 객체가 포함된 경우
• 완전한 객체가 생성된 후에도 생성이 계속되는 경우

여러 사례에서 정답은 눈에 보이게 존재했습니다.

하지만 전체 응답은 여전히 JSON 파싱(parsing)에 실패했습니다.

이것이 바로 다음과 같은 지침(instructions)에만 의존할 때 발생하는 실질적인 한계입니다:

유효한 JSON만 반환할 것.
Markdown 금지.
추가 텍스트 금지.

이러한 지침은 준수하는 출력(compliant output)이 나올 확률을 높여줄 수는 있습니다.

하지만 모델의 가능한 디코딩 경로(decoding paths)에서 비준수 출력(non-compliant output)을 제거하지는 못합니다.

검증은 실수가 발생한 후에 일어난다

JSON 파서(parser)는 생성 후에 출력이 유효하지 않다는 것을 알려줄 수 있습니다.

스키마 검증기(schema validator)는 파싱된 객체에 잘못된 키(key)나 값의 타입(value types)이 포함되어 있다는 것을 알려줄 수 있습니다.

복구 로직(Recovery logic)은 긴 응답에서 첫 번째 완전한 객체를 추출해낼 수도 있습니다.

이것들은 모두 유용한 기술들이지만, 서로 다른 문제를 해결합니다.

생성 후 검증(Post-generation validation)은 다음과 같이 묻습니다:

모델이 수용 가능한 무언가를 생성했는가?

제약 디코딩(Constrained decoding)은 다음과 같이 묻습니다:

모델이 다음에 법적으로 생성할 수 있는 토큰(tokens)은 무엇인가?

전자는 실패를 감지합니다.

후자는 구조적 실패를 방지하려고 시도합니다.

그렇다고 해서 제약 디코딩이 자동으로 정답을 만들어준다는 뜻은 아닙니다.

이는 단지 생성된 시퀀스(sequence)가 정의된 언어 내에 머물도록 강제된다는 것을 의미할 뿐입니다.

완벽하게 유효한 JSON 객체라 할지라도 여전히 틀린 답을 포함할 수 있습니다.

구조적 유효성(Structural validity)과 의미론적 정확성(semantic correctness)은 별개의 평가 차원입니다.

디코딩 루프(decoding loop) 건드리기

근본적인 메커니즘을 이해하기 위해, 저는 작은 Hugging Face LogitsProcessor를 구현했습니다.

이 프로세서는 토크나이저 어휘(tokenizer vocabulary)를 스캔하여, 개별적으로 디코딩된 텍스트에 숫자가 포함된 토큰 ID(token IDs)를 기록합니다:

for token_id in range(len(tokenizer)):
    piece = tokenizer.decode(
        [token_id],
...

매 생성 단계마다, 프로세서는 해당 토큰들의 점수(scores)를 수정합니다:

scores[:, self.banned_token_ids] = -float("inf")

Softmax를 거친 후, 해당 토큰들은 0의 확률을 받게 됩니다.

디코더는 이 토큰들을 선택할 수 없습니다.

이것은 문법 제약 디코더 (grammar-constrained decoder)가 아닙니다.

이는 기본적인 디코딩 시점의 동작을 직접 관찰하기 위해 사용된 정적 토큰 마스크 (static token mask)입니다.

결과는 단순히 "모델이 숫자 생성을 중단했다"는 것보다 더 흥미로웠습니다.

모델은 일반적인 ASCII 숫자는 피했지만, 원형 숫자 (circled numbers)와 같이 숫자와 유사한 Unicode 문자를 생성했습니다.

형식 (formatting)과 출력 품질 또한 저하되었습니다.

이는 두 가지 중요한 문제를 드러냈습니다.

제약 조건은 의도가 아닌 구현을 강제한다

"모델이 숫자를 출력하지 못하게 한다"는 것은 비공식적인 의도 (informal intention)입니다.

"개별적으로 디코딩된 문자열에 숫자가 포함된 토큰의 로짓 (logits)을 음의 무한대로 설정한다"는 것은 구현 (implementation)입니다.

이 둘은 동일하지 않습니다.

숫자는 다음과 같은 방식으로 표현될 수 있습니다:

• ASCII 숫자
• 기타 Unicode 숫자 문자
• 숫자 단어 (number words)
• 시각적으로 숫자와 유사한 기호
• 단순한 어휘 스캔 (vocabulary scan)으로 놓칠 수 있는 토큰 조합

디코더는 실제로 인코딩된 규칙만을 보장합니다.

이는 사람들이 제약 디코딩 (constrained decoding)이 유효한 출력을 보장한다고 말할 때 특히 중요합니다.

그 보장은 다음 요소들에 상대적입니다:

• 강제되는 문법 (grammar)
• 토크나이저 표현 (tokenizer representation)
• 파서 상태 (parser state)
• 바이트 및 Unicode 처리
• 수락 상태 (accepting state)의 정의
• 정지 동작 (stopping behaviour)

좁거나 잘못된 정식화 (formalisation)는 잘못된 언어에 대해 강력한 보장을 제공할 수 있습니다.

하드 제약 (Hard constraints)은 출력 품질을 손상시킬 수 있다

원래의 모델 분포 (model distribution)는 소수의 자연스러운 연속 문구에 대부분의 확률 질량 (probability mass)을 할당할 수 있습니다.

이러한 연속 문구들이 마스킹 (masked)되면, 디코더는 남은 것들 중에서 선택해야 합니다.

남은 토큰은 구조적으로는 합법적일 수 있지만, 어색하거나, 가능성이 낮거나, 또는 의미론적으로 좋지 않을 수 있습니다.

이것이 제약 디코딩을 단순히 유효성 백분율 (validity percentage)로만 평가하는 것이 불완전한 이유입니다.

유용한 비교를 위해서는 다음 사항들도 측정해야 합니다:

• 작업 정확도 (task accuracy)
• 지연 시간 오버헤드 (latency overhead)
• 생성된 토큰 수 (generated token count)
• 막다른 길 (dead ends)
• 제거된 확률 질량 (probability mass removed)
• 출력 품질 (output quality)
• 복구 동작 (recovery behaviour)
• 다양한 스키마 (schemas) 및 프롬프트 스타일에서의 동작 (behaviour across different schemas and prompt styles)

시스템이 구문론적으로 100% 유효한 JSON을 생성할 수 있더라도, 실제 작업 측면에서는 더 나쁠 수 있습니다.

진짜 어려움: 문법(grammars)은 바이트(bytes) 단위로 작동하고, 모델은 토큰(tokens)을 출력한다

선택된 로짓(logits)을 음의 무한대(-infinity)로 설정하는 것은 간단합니다.

어떤 로짓을 마스킹(masking)해야 하는지 결정하는 것이 어려운 부분입니다.

문법(grammar)은 보통 문자(characters) 또는 바이트(bytes)를 기준으로 정의됩니다.

언어 모델은 토큰(tokens)을 출력합니다.

하나의 토큰은 다음과 같은 것들을 포함할 수 있습니다:

• 하나의 문자
• 여러 개의 문자
• 공백과 문장 부호의 결합
• 하나의 완전한 단어
• 멀티바이트 문자(multibyte character)의 일부
• 주변 토큰에 따라 동작이 달라지는 파편(fragment)

파서(parser)가 현재 0으로 시작하는 숫자를 허용한다고 가정해 봅시다.

유효한 어휘 집합(vocabulary)에는 다음과 같은 토큰들이 포함될 수 있습니다:

0
0.
0.4
...

각 토큰이 적법한지 여부는 문법(grammar)과 현재 파서 상태(parser state)에 따라 달라집니다.

단순히 토큰이 다음 유효한 문자와 일치하는지 묻는 것만으로는 충분하지 않습니다.

디코더(decoder)는 토큰의 전체 바이트 시퀀스(byte sequence)를 소비(consuming)하는 과정을 시뮬레이션해야 합니다.

개념적으로는 다음과 같습니다:

현재 파서 상태 (current parser state)
        ↓
후보 토큰 바이트 (candidate token bytes)
...

토큰의 전체 바이트 시퀀스가 문법을 무효화하지 않고 소비될 수 있을 때만 해당 토큰이 사용 가능한 상태로 유지되어야 합니다.

하나의 토큰이 생성되면 파서 상태(parser state)가 변경됩니다.

따라서 유효한 어휘 집합(vocabulary set)을 다시 계산해야 합니다.

이로 인해 실제 제약 조건은 상태 의존적(state-dependent)이 됩니다.

정적인 숫자 금지(static digit ban)는 모든 생성 단계에서 동일한 마스크(mask)를 사용합니다.

반면 JSON 문법(JSON grammar)은 다음과 같은 상황마다 서로 다른 마스크가 필요합니다:

{

이후의 상황:

{"answer":

또는:

{"answer":"72"

적법한 연속성(continuation)은 파서가 현재 어디에 위치하느냐에 따라 달라집니다.

모든 토큰을 무작정 확인하는 것이 비용이 많이 드는 이유

현대적인 토크나이저(tokenizer)는 수만 개에서 수십만 개의 토큰을 포함할 수 있습니다.

매 생성 단계(generation step)마다 파서(parser)를 통해 모든 토큰을 검사하는 것은 상당한 오버헤드(overhead)를 발생시킵니다.

이 지점에서 토큰 트라이(token tries) 및 캐시된 파서 전이(cached parser transitions)와 같은 기술이 유용해집니다.

토큰 트라이(token trie)는 공유된 바이트 접두사(byte prefixes)를 기준으로 어휘(vocabulary) 토큰들을 그룹화합니다.

디코더는 모든 토큰을 파서를 통해 독립적으로 다시 실행하는 대신, 공유된 접두사를 한 번만 탐색하고 접두사가 유효하지 않게 되는 즉시 전체 브랜치(branch)를 가지치기(prune)할 수 있습니다.

상위 수준의 루프(high-level loop)는 다음과 같습니다:

1. 현재 파서 상태(parser state)를 읽습니다.
2. 가능한 토큰-바이트 접두사(token-byte prefixes)를 탐색합니다.
3. 문법(grammar)을 위반하는 브랜치를 가지치기(prune)합니다.
4. 유효한 브랜치로 끝나는 토큰 ID(token IDs)를 수집합니다.
5. 나머지 어휘(vocabulary)를 마스킹(mask)합니다.
6. 하나의 토큰을 생성합니다.
7. 파서 상태(parser state)를 진행시킵니다.
8. 수락 상태(accepting state)에 도달할 때까지 반복합니다.

재귀 구조(recursive structures), 문자열(strings), 이스케이프(escaping), 숫자(numbers), UTF-8, 그리고 모호한 파서 상태(ambiguous parser states)의 경우 구현이 더 복잡해집니다.

하지만 핵심적인 매핑(mapping)은 그대로 유지됩니다:

파서 상태(Parser state) → 유효한 토큰 ID(legal token IDs)

이 실험이 증명하지 못하는 것

현재 설정에는 몇 가지 한계가 있습니다.

데이터셋이 매우 작음

세 개의 예시는 스모크 테스트(smoke test)에는 충분하지만, 디코딩 전략(decoding strategies)을 비교하기에는 부족합니다.

JSON 추출기가 의도적으로 엄격하고 단순함

이 추출기는 첫 번째 여는 중괄호와 마지막 닫는 중괄호 사이의 콘텐츠를 가져옵니다.

따라서 여러 개의 유효한 객체(objects)가 하나의 유효하지 않은 후보가 되어 버립니다.

더 강력한 평가는 다음 항목들에 대해 별도의 지표를 보고해야 합니다:

• 전체 응답 유효성 (whole-response validity)
• 첫 번째 객체 복구 가능성 (first-object recoverability)
• 스키마 유효성 (schema validity)
• 의미론적 정확성 (semantic correctness)

자유 형식 추출기(free-form extractor)가 취약함

이 추출기는 출력의 마지막 숫자를 선택합니다.

정답 뒤에 추가적인 숫자 텍스트가 있으면 잘못된 점수가 생성될 수 있습니다.

모델이 채팅 템플릿(chat template)을 통해 프롬프트되지 않음

원시 프롬프트(raw prompt)가 지시어 튜닝된(instruction-tuned) 모델에 직접 전달되었습니다.

이를 토크나이저(tokenizer)의 의도된 채팅 템플릿과 비교하는 과정이 필요합니다.

토큰 마스크(token mask)가 바이트 단위로 정확하지 않음

각 어휘 토큰(vocabulary token)을 개별적으로 디코딩하는 것은 검토(inspection)를 위해 유용합니다.

실제 서비스용 구현(production implementation)에서는 기저에 있는 토큰 바이트(token bytes)와 UTF-8 동작에 대해 신중하게 고려해야 합니다.

제약 조건은 정적(static)입니다

숫자 프로세서(digit processor)는 로짓 마스킹(logit masking)을 보여주는 것이지, 파서 기반의 제약된 디코딩(parser-driven constrained decoding)을 보여주는 것이 아닙니다.

이러한 한계점들은 단순한 부연 설명이 아닙니다.

이것들은 실험으로부터 어떤 결론을 도출할 수 있고 없는지를 정의합니다.

다음 구현 단계

다음으로 유용한 이정표는 제한된 출력 언어를 위한 작은 상태 의존적 디코더(state-dependent decoder)를 만드는 것입니다. 예를 들면 다음과 같습니다:

{"answer":"<digits>"}

구현 시 다음 사항을 수행해야 합니다:

• 언어를 오토마타(automaton) 또는 파서(parser)로 정의
• 토크나이저(tokenizer) ID를 바이트 시퀀스(byte sequences)로 매핑
• 현재 파서 상태(parser state) 추적
• 후보 토큰 바이트(candidate token bytes) 시뮬레이션
• 유효성을 유지하는 토큰만 허용
• 수락 상태(accepting state)에서만 중단
• 매 단계마다 마스크 크기와 지연 시간(latency) 기록

이것이 작동하면 다음과 같은 사항들을 비교하는 것이 가능해집니다:

• 프롬프팅(prompting)만 사용
• 파싱(parsing) 및 복구(repair)
• 정규 표현식(regex) 또는 유한 상태 제약(finite-state constraints)
• JSON-schema 제약
• 다양한 토큰 필터링 전략

비교 시 모델, 데이터셋, 프롬프트 내용, 그리고 의미론적 점수(semantic scoring)를 최대한 통제된 상태로 유지해야 합니다.

유용한 구분

“유효한 JSON만 반환하라”는 여전히 유용한 지시어입니다.

이는 실패를 줄이고, 가독성을 높이며, 모델의 의도된 출력을 더 명확하게 만들 수 있습니다.

하지만 이것은 디코딩 제약(decoding constraint)이 아닙니다.

프롬프팅(Prompting)은 모델에게 구조를 따르라고 요청하는 것입니다.

검증(Validation)은 모델이 구조를 따랐는지 확인하는 것입니다.

제약된 디코딩(Constrained decoding)은 구조를 위반하는 연속(continuations)을 제거하는 것입니다.

이러한 접근 방식들은 서로 보완할 수 있지만, 동일한 보장을 제공하지는 않습니다.

실험을 위한 코드, 원시 출력(raw outputs) 및 노트는 여기에서 확인할 수 있습니다:

Constrained Decoding Lab