저는 몇 주 동안 제약 조건이 있는 디코딩 엔진 (constrained decoding engine)을 구축하는 데 시간을 보낼 예정이라, 2019년에 발표된 논문을 읽는 것으로 시작했습니다.

GPT-2 논문의 섹션 2.2는 약 반 페이지 분량입니다. 이 섹션은 훈련 데이터셋 (training dataset) 섹션과 모델 아키텍처 (model architecture) 섹션 사이에 위치하며, 쉽게 지나치기 쉽습니다. 또한 제가 파악한 바로는, 제가 곧 작업하게 될 분야에서 가장 어려운 단일 문제의 기원이기도 합니다.

다음은 논문에 적힌 내용이며, 제가 직접 토크나이저 (tokenizer)를 실행하여 확인한 내용이자, 마지막에 예상치 못하게 발견한 사실입니다.

모두가 이미 알고 있는 부분

모델은 숫자로 계산합니다. 텍스트는 문자입니다. 이 둘 사이를 연결하는 무언가가 필요하며, 이를 수행하는 세 가지 명확한 방법이 있습니다.

단어 수준 (Word level). 모든 단어를 ID로 매핑합니다. 모든 굴절, 오타, 합성어가 새로운 항목이 되기 때문에 어휘 사전 (vocabulary)이 폭발적으로 늘어나며, 모델이 훈련 중에 보지 못한 모든 것은 <UNK>가 됩니다. 모델은 이에 대해 눈이 멀게 됩니다.

문자 수준 (Character level). 모든 문자를 ID로 매핑합니다. 무엇이든 철자를 적을 수 있기 때문에 어휘 사전에서 벗어나는 것 (out of vocabulary)이 전혀 없습니다. 하지만 시퀀스 (sequence)가 대략 5배 길어지며, 트랜스포머 어텐션 (transformer attention) 비용은 시퀀스 길이의 제곱에 비례하여 증가합니다. 또한 모델이 의미를 배우기도 전에 철자법부터 배우게 만듭니다.

서브워드 수준 (Subword level). 조각으로 나눕니다. 흔한 단어는 통째로 유지되고, 희귀한 단어는 모델이 다른 문맥에서 보았던 파편들로 분해됩니다. 시퀀스는 짧아지고, 어휘 사전에서 벗어나는 문제도 없습니다.

Byte Pair Encoding (BPE)은 승리한 서브워드 방식입니다. 이는 1994년 데이터 압축 알고리즘에서 유래되었으며, 2015년 Sennrich 등에 의해 NLP (자연어 처리)를 위해 용도가 변경되었습니다. 훈련 루프는 네 줄의 의사 코드 (pseudocode)로 이루어집니다:

1. 코퍼스 (corpus)에 있는 모든 개별 심볼의 기본 어휘 사전으로 시작합니다.
2. 인접한 모든 심볼 쌍을 계산합니다.
3. 가장 빈번한 쌍을 새로운 심볼로 병합하고 어휘 사전에 추가합니다.
4. 목표 크기에 도달할 때까지 2단계로 돌아갑니다.

그것이 전부입니다. 만약 t h가 지속적으로 나타난다면, th 토큰을 얻게 됩니다. 그다음 th e가 지속적으로 나타나면, the를 얻게 됩니다. 이 과정을 5만 번 반복하면 흔한 영어 단어들은 단일 토큰이 되는 반면, 드문 단어들은 파편(fragments) 상태로 남게 됩니다.

기억해야 할 속성은 다음과 같습니다: 이것은 탐욕적(greedy)이며, 빈도 기반(frequency based)이고, 전적으로 코퍼스(corpus, 말뭉치)에 의존합니다. 결과로 나온 어휘 사전(vocabulary)에는 언어학적 원리(linguistically principled)가 전혀 담겨 있지 않습니다. 그저 훈련 데이터를 압축한 결과물일 뿐입니다. 이것이 서로 다른 토크나이저(tokenizer)가 동일한 단어를 다르게 분할하는 이유이며, 숫자와 코드가 종종 임의적인 방식으로 토큰화되는 이유입니다.

GPT-2가 실제로 기여한 점

당시의 표준 BPE(Byte Pair Encoding)는 유니코드(Unicode) 코드 포인트(code points)를 대상으로 실행되었습니다. 유니코드는 130,000개가 넘는 코드 포인트를 가지고 있기 때문에, 아무것도 병합하기 전부터 기본 어휘 사전(base vocabulary)이 거대하며, 설정된 집합 이외의 것에 대해서는 여전히 공백(holes)이 존재합니다.

GPT-2는 대신 UTF-8 바이트(bytes)에 대해 BPE를 실행합니다.

바이트는 256개의 가능한 값을 가집니다. 이것이 당신의 전체 기본 어휘 사전이 됩니다. 그리고 모든 가능한 유니코드 문자열은 어떤 UTF-8 바이트 시퀀스로 인코딩(encode)되기 때문에, 어휘 사전 외 단어(out of vocabulary, OOV) 사례가 발생하지 않습니다. 어떤 언어도, 이모지도, 잘못된 입력(malformed input)도 예외가 아닙니다. 그 어떤 문자열이라도 말이죠.

이것이 바이트 수준 BPE(byte level BPE)의 실제 핵심이며, 저는 이것이 보통 잘못 설명되고 있다고 생각합니다. 이것은 일차적으로 효율성 측면의 이득이 아닙니다. 아주 작은 기본 어휘 사전을 대가로 얻은 커버리지(coverage, 범위) 보장입니다.

논문은 또한 그들이 처음 이것을 시도했을 때 무엇이 문제였는지에 대해서도 솔직하게 밝히고 있습니다. 바이트에 BPE를 순진하게(naively) 적용하면 잘못된 병합이 발생했는데, 탐욕적 빈도 휴리스틱(greedy frequency heuristic)이 dog, dog., dog!, dog?를 각각 별개의 토큰으로 학습했기 때문입니다. 단어 하나에 네 개의 어휘 사전 슬롯을 사용하게 된 것입니다. 그래서 그들은 문자 범주 간의 병합을 차단했습니다: 즉, 문자는 문장 부호와 병합되지 않습니다.

이 방식이 효과가 있었는지 확인할 수 있습니다:

'dog' -> ['dog'] [9703]
'dog.' -> ['dog', '.'] [9703, 13]
'dog!' -> ['dog', '!'] [9703, 0]
...

네 가지 경우 모두 동일한 dog 토큰(ID 9703)입니다. 문장 부호는 매번 별도로 분리됩니다.

그다음 그들은 공백(spaces)에 대해 예외를 두었습니다. 모든 범주 간 병합을 차단하면 일반적인 텍스트가 심하게 파편화되기 때문입니다. 공백은 앞의 토큰이 아니라 뒤에 오는 토큰에 붙습니다:

'hello world' -> ['hello', 'Ġworld']

Ġ는 GPT-2의 어휘 사전 (vocabulary)에서 앞부분의 공백을 렌더링하는 방식입니다. 이것은 접두사 (prefix)이며, 이는 hello와 Ġhello가 서로 다른 두 개의 ID(31373 및 23748)를 가진 서로 다른 토큰임을 의미합니다. 동일한 다섯 글자가 동일한 순서로 있더라도, 앞에 공백이 왔는지 여부에 따라 모델에게는 서로 다른 심볼 (symbol)이 됩니다.

이 점을 유념해 두세요.

아무도 깔끔하게 설명해주지 않는 트레이드오프 (trade-off)

어휘 사전 크기 (vocabulary size)는 양쪽 모두에 실질적인 비용이 발생하는 조절 노브 (knob)와 같습니다.

어휘 사전이 커지면 동일한 텍스트에 대해 시퀀스 (sequence) 길이가 짧아지므로, 같은 내용을 말하기 위한 디코딩 (decode) 단계가 줄어듭니다. 하지만 임베딩 행렬 (embedding matrix)과 최종 소프트맥스 레이어 (softmax layer) 모두 어휘 사전 크기에 따라 확장되므로, 파라미터 (parameters)와 출력 투영 (output projection) 연산량 측면에서 비용을 지불해야 합니다.

어휘 사전이 작아지면 임베딩과 소프트맥스 비용은 저렴해지지만, 시퀀스 길이는 길어집니다. 그리고 디코딩은 토큰당 하나의 순차적인 순전파 (sequential forward pass) 과정이며, 디코딩은 추론 (inference) 단계에서 메모리 대역폭에 제한을 받는 (memory bound) 부분이기 때문에, 토큰이 많아지면 실제 소요 시간 (wall clock time)도 직접적으로 늘어납니다.

50,257은 GPT-2가 내놓은 해답이었습니다. 이것은 자연의 상수 (constant of nature)가 아닙니다.

이제 제가 실제로 알고 싶었던 부분

위의 모든 내용은 배경 지식입니다. 제가 이것을 읽은 이유는 다음과 같습니다.

제약 조건 디코딩 (Constrained decoding)은 모델의 출력이 특정 스키마 (schema)를 따르도록 강제하는 기술입니다. 생성 (generation)의 매 단계마다, 샘플링 (sampling)을 하기 전, 스키마를 위반하게 될 모든 토큰의 로짓 (logits)을 마이너스 무한대 (-∞)로 설정합니다. 소프트맥스 (softmax)를 거치고 나면 이 토큰들의 확률은 정확히 0이 됩니다. 모델은 이들을 내뱉을 수 없습니다. 유효성 (Validity)은 더 이상 바라는 대상이 아니라 구조적인 요소가 됩니다.

이를 위해, 스키마를 상태 머신 (state machine)으로 컴파일합니다. 어떤 상태에서든 다음에 올 수 있는 문자가 무엇인지 알 수 있으므로, 다음에 올 수 있는 토큰이 무엇인지 알 수 있고, 따라서 무엇을 마스킹 (mask)해야 하는지 알 수 있습니다.

하지만 문제는 스키마는 문자를 기준으로 정의되어 있는 반면 모델은 토큰을 생성하며, 이 두 가지가 서로 일치하지 않는다는 점입니다.

시작하기 전부터 이 사실을 추상적으로는 알고 있었습니다. 제가 간과했던 것은 이 둘이 얼마나 심하게 어긋나 있는가 하는 점이었습니다. 그래서 저는 GPT-2의 토크나이저 (tokenizer)를 몇 가지 JSON 데이터에 실행해 보았습니다.

import tiktoken
enc = tiktoken.get_encoding("gpt2")
print(enc.encode('{"'))        # [4895]
...

{"는 하나의 토큰입니다. 여는 중괄호와 첫 번째 키의 여는 따옴표가 결합되어 ID 4895라는 단일 심볼이 되었습니다.

":는 하나의 토큰입니다. 키의 닫는 따옴표와 그 뒤에 오는 콜론이 결합되어 ID 1298이 되었습니다.

"},{"는 하나의 토큰입니다. ID 11919입니다. 다섯 개의 문자, 즉 문자열 닫기, 객체 닫기, 쉼표, 객체 열기, 문자열 열기가 포함되어 있습니다. 여러분이 작성할 그 어떤 JSON 문법 (grammar)에서도 이는 다섯 개의 별개 전이 (transitions)이지만, 모델은 이들을 하나의 나눌 수 없는 단위로서 전부 내뱉거나 혹은 전혀 내뱉지 않습니다.

전체 도구 호출 (tool call)은 다음과 같이 보입니다:

'{"location": "Jaipur", "unit": "celsius"}'

['{"', 'location', '":', 'Ġ"', 'Ja', 'ip', 'ur', '",',
...

16개의 토큰입니다. 경계가 어디에 형성되는지 보십시오. 구조적 구분자 (structural delimiters) 중 어느 것도 단독으로 존재하지 않습니다. {", ":, ",, Ġ", "}. 문법의 알파벳과 모델의 알파벳은 서로 다른 알파벳이며, 모델의 알파벳은 문법이 가장 중요하게 여기는 바로 그 지점들에서 훨씬 더 거칠게 (coarser) 구성되어 있습니다.

어휘 사전 (vocabulary)의 50,257개 항목 중 50,001개가 단일 문자보다 깁니다. 이는 99.5퍼센트에 달합니다. 그중 311개는 { } [ ] " : , 중 적어도 하나를 포함하고 있으며, 그중 92개는 영숫자 (alphanumerics)까지 포함하고 있습니다. 이는 구조 (structure)와 내용 (content) 사이의 경계에 걸쳐 있는 단일 토큰이 거의 백 개에 달한다는 것을 의미합니다.

이것이 정확도를 떨어뜨리는 이유

현재 제가 이해하고 있는 메커니즘은 다음과 같습니다. 이것이 확정된 사실이라기보다는 이 분야의 유력한 설명이라는 점을 분명히 하고 싶으며, 이를 테스트하는 것이 제가 하려는 작업의 큰 부분입니다.

모델이 영수증을 파싱 (parsing)하고 있고 올바른 합계가 0.46이라고 가정해 봅시다. 제약이 없다면, 모델은 다음과 같이 토큰화 (tokenize)합니다:

'0.46' -> ['0', '.', '46']   [15, 13, 3510]

세 개의 토큰이며, 46은 그중 하나인 id 3510입니다. 이것은 모델이 훈련 과정에서 수천 번이나 걸어온 경로입니다.

이제 여기에 제약을 가해 봅시다. 문법 (grammar)이 숫자를 기대하는 어떤 상태에 있고, 여러분의 오토마타 (automaton)가 어떻게 구축되었는지와 이전 토큰이 어디에 위치했는지에 따라, 동일한 문자열을 철자하기 위해 모델을 다른 토큰 경로로 강제하는 방식으로 마스킹 (masking)이 이루어질 수 있습니다. 출력은 여전히 유효한 JSON입니다. 단지 이 문맥에서 모델이 훈련 중에 거의 가보지 않은 분포 (distribution) 경로를 택했을 뿐이며, 그 시점 이후에 생성되는 모든 것은 모델이 스스로 선택하지 않은 접두사 (prefix)에 조건화 (conditioned)됩니다.

BAML은 이에 대한 구체적인 사례를 발표했습니다. 영수증 파싱 작업에서 제약된 디코딩 (constrained decoding)은 정답이 0.46인 곳에서 1을 반환했습니다. 해당 작업 전체에서 그들이 측정한 정확도는 자유 형식 파싱 (free form parsing)의 93.63퍼센트에 비해 제약 시 91.37퍼센트였습니다.

2퍼센트의 격차는 흥미로운 부분이 아닙니다. 흥미로운 점은 1이 완벽하게 유효한 JSON이라는 것입니다. 여러분의 스키마 (schema)는 검증되었고, 타입 (types)도 확인되었으며, 파이프라인 (pipeline)은 성공을 보고했습니다. 예외도, 파싱 에러 (parse error)도, 무언가 잘못되었다는 신호도 어디에도 없습니다. 실패는 구조적으로 침묵합니다 (silent by construction). 왜냐하면 제약의 전체 목적이 유효하지 않은 출력을 불가능하게 만드는 것이었고, 그것이 성공했기 때문입니다.

더 큰 규모의 연구에서는, Tam 등이 엄격한 제약 조건 하에서 형식 제한(format restrictions)이 벤치마크 상의 추론 정확도를 최대 27포인트까지 저하시킨다는 것을 측정했습니다 (EMNLP 2024). 이 수치는 그 조건들이 생략된 채 자주 인용되므로, 헤드라인으로 받아들이기보다는 특정 설정 하에서의 상한선(upper bound)으로 취급해야 합니다. 하지만 그 방향성은 이후 독립적으로 재현되었습니다.

토큰 힐링 (Token healing), 그리고 그것이 존재하는 이유

이 문제의 경계(boundary) 측면에 대한 부분적인 해결책이 존재하며, 이는 한동안 Guidance에 포함되어 있었습니다.

제약 조건이 자연스럽게 하나의 토큰이 되었을 내용을 중간에 잘라버릴 때, 깨끗한 토큰 경계(token boundary)로 되돌아가서 거기서부터 다시 제약을 겁니다. 이렇게 하면 모델이 경계에 걸쳐 있는 토큰을 조각조각 나누어 철자를 맞추도록 강요받는 대신, 경계를 가로지르는 하나의 토큰을 선택할 수 있게 됩니다.

이를 토큰 힐링 (token healing)이라고 부르며, GPT-2의 섹션 2.2를 읽는 것이 왜 이것이 존재해야만 하는지를 이해하게 된 계기였습니다. 이것은 허술한 구현을 위한 임시방편(workaround)이 아닙니다. 이는 2019년에 완전히 다른 이유로 내려진 설계 결정의 직접적인 결과입니다: 코드 포인트 (code points) 대신 바이트 (bytes) 사용, 탐욕적 빈도 병합 (greedy frequency merges), 다음 단어 앞에 붙는 공백 등입니다. 이러한 선택 중 그 어느 것도 문법을 염두에 두고 이루어진 것이 아니었습니다. 왜냐하면 문법으로 제약된 생성 (grammar constrained generation)은 당시 존재하지 않았기 때문입니다.

XGrammar 논문은 제가 할 수 있는 것보다 더 정확하게 동일한 내용을 설명합니다. 그들의 프레임워크에 따르면, 토큰은 완전한 의미 단위 (semantic units)에 대응하지 않을 수 있고 유니코드 (Unicode) 문자를 분할할 수도 있는 고정된 문자열이며, 이것이 구조화된 생성 (structured generation)의 근본적인 과제입니다. 저는 문제를 수동으로 파악한 후에야 이 문장을 발견했는데, 이는 제가 올바른 문제를 보고 있었다는 유용한 확인이 되었습니다.

아직 내가 모르는 것들

가정하기보다는 측정하고 싶은 두 가지가 있습니다.

첫째, 관찰된 성능 저하(degradation)가 실제로 경계 문제(boundary problem) 때문인지, 아니면 다른 후보 메커니즘 때문인지의 정도입니다. 그 후보 메커니즘이란 스키마(schema)가 정답을 도출할 추론(reasoning)이 일어나기도 전에 모델로 하여금 answer 필드를 확정하도록 강제한다는 것입니다. 저의 사전 지식(prior)으로는, 추론(reasoning) 작업에서는 후자가 지배적이고 추출(extraction) 작업에서는 전자가 지배적일 것이라고 생각하지만, 이는 추측일 뿐이며 어디에서도 이 둘이 깔끔하게 분리된 것을 본 적이 없습니다.

둘째, 이러한 성능 저하가 크기(size)에 의존적인지 여부입니다. 만약 작은 모델이 큰 모델보다 더 큰 피해를 입는지, 혹은 그 반대인지에 따라, 그 곡선의 형태는 이것이 용량(capacity) 문제인지 아니면 분포(distributional) 문제인지에 대해 무언가를 말해줄 것입니다.