BPE Tokenizer 만들기: 모델이 R 개수를 세지 못하는 이유

텍스트를 네트워크에 넣는 명백한 방법은 두 가지가 있고, 둘 다 실패합니다. 그 실패를 이해할 가치가 있습니다. 실패가 곧 해법의 형태를 결정하기 때문입니다.

단어. 공백으로 나누고 각 단어에 숫자를 배정합니다. 영어에는 수십만 개의 단어 형태가 있고, 모델은 각각에 대해 embedding 행이 필요합니다. 그래서 어휘집, 그리고 모든 항목에 점수를 내야 하는 출력층이 거대해집니다. 더 나쁜 문제는 inference 때 발생합니다. 모델이 훈련 중 한 번도 보지 못한 단어에는 숫자가 없습니다. 이것이 out-of-vocabulary 문제이며, 흔한 임시방편은 모르는 모든 것을 하나의 <UNK> token으로 매핑하는 것입니다. 그러면 정보가 사라집니다. 게다가 「단어」는 잘 정의된 개념도 아닙니다. 중국어와 일본어는 단어 사이에 공백을 넣지 않고, 독일어는 명사를 끝없이 합성합니다.

문자. out-of-vocabulary 문제는 없고, 어휘도 백여 개 기호면 충분합니다. 하지만 시퀀스가 매우 길어집니다. Chapter 9에서 보겠지만 attention 비용은 시퀀스 길이에 대해 제곱으로 증가합니다. 1000단어짜리 문서는 대략 5000자입니다. 필요한 것보다 네다섯 배 긴 시퀀스가 되고, 비용은 제곱으로 치릅니다. 또한 각 문자는 그 자체로 거의 의미를 담지 않으므로, 앞쪽 몇 개 층은 tokenizer가 온전한 단어로 넘겨줄 수 있었던 것을 다시 조립하는 데 쓰입니다.

답은 그 중간에 있습니다. subword입니다. 흔한 단어는 하나의 token이 되고, 드문 단어는 조각으로 나뉘며, 조각은 마지막에 개별 byte까지 내려가기 때문에 모르는 입력은 절대 없습니다. 흥미로운 점은 이 분할을 사람이 설계하지 않는다는 것입니다. tokenizer는 훈련됩니다. 모델과 같은 종류의 데이터에서 훈련되며, 어떤 byte 시퀀스에 자체 번호를 줄 가치가 있는지 함께 나타나는 빈도를 세어 학습합니다.

이 알고리즘은 1994년에 나온 압축 알고리즘입니다. Philip Gage는 C Users Journal에, 데이터에 나타나지 않는 byte로 가장 빈번한 인접 byte 쌍을 반복적으로 대체해 파일을 줄이는 방법으로 이를 발표했습니다.¹ 그 뒤 22년 동안 그대로 있다가, 2016년에 Sennrich, Haddow, Birch가 machine translation에서 out-of-vocabulary 문제를 해결하기 위해 다시 활용했습니다.² 이제 본질적으로 모든 large language model이 읽는 방식입니다.

훈련 루프는 네 단계를 반복합니다.

전체 trainer는 다음과 같습니다.

def get_stats(ids):
    counts = {}
    for a, b in zip(ids, ids[1:]):
        counts[(a, b)] = counts.get((a, b), 0) + 1
    return counts


def merge(ids, pair, idx):
    out, i = [], 0
    while i < len(ids):
        if i < len(ids) - 1 and ids[i] == pair[0] and ids[i + 1] == pair[1]:
            out.append(idx)
            i += 2
        else:
            out.append(ids[i])
            i += 1
    return out


class BPE:
    def __init__(self):
        self.merges = {}
        self.vocab = {i: bytes([i]) for i in range(256)}

    def train(self, text, vocab_size):
        ids = list(text.encode("utf-8"))
        for i in range(vocab_size - 256):
            stats = get_stats(ids)
            if not stats:
                break
            pair = max(stats, key=stats.get)      
            idx = 256 + i                         
            ids = merge(ids, pair, idx)           
            self.merges[pair] = idx               
            self.vocab[idx] = self.vocab[pair[0]] + self.vocab[pair[1]]
        return ids

151,191byte의 영어 산문에서 실행하고, 처음 열두 개 병합이 일어나는 순간을 출력해 봅니다. 이 부분은 천천히 읽을 가치가 있습니다. 알고리즘에게 영어에 대해 아무것도 알려주지 않았기 때문입니다.

merge   1: b'e' + b' '   -> b'e '     (occurred 4433 times)
merge   2: b' ' + b't'   -> b' t'     (occurred 3302 times)
merge   3: b'\xe2' + b'\x80' -> b'\xe2\x80'  (occurred 3247 times)
merge   4: b' ' + b'a'   -> b' a'     (occurred 2335 times)
merge   5: b' t' + b'h'  -> b' th'    (occurred 2253 times)
merge   6: b'i' + b'n'   -> b'in'     (occurred 2011 times)
merge   7: b't' + b' '   -> b't '     (occurred 1904 times)
merge   8: b'e' + b'r'   -> b'er'     (occurred 1813 times)
merge   9: b'd' + b' '   -> b'd '     (occurred 1703 times)
merge  10: b'o' + b'u'   -> b'ou'     (occurred 1554 times)
merge  11: b' ' + b's'   -> b' s'     (occurred 1467 times)
merge  12: b' th' + b'e '-> b' the '  (occurred 1270 times)

이 목록에서 짚어볼 만한 점이 세 가지 있습니다.

12번째 병합은 단어 「the」입니다. 앞의 공백과 뒤의 공백까지 포함해 하나의 단위로, 쌍을 세는 루프의 열두 번째 반복에서 발견되었습니다. 아무도 사전을 제공하지 않았습니다. 이 다섯 byte가 영어에서 다른 어떤 다섯 byte보다도 더 자주 함께 나타나기 때문에 거기에 있는 것입니다.

3번째 병합은 텍스트가 전혀 아닙니다. \xe2\x80는 typographic punctuation, 즉 em dash와 curly quote의 UTF-8 인코딩 앞 두 byte입니다. 알고리즘은 UTF-8이 존재한다는 사실을 전혀 모릅니다. 그런데 multi-byte 인코딩은 구조상 항상 함께 나타나는 byte 시퀀스이기 때문에, 그 구조의 한 조각을 방금 재발견한 것입니다.

초기 병합 대부분은 공백을 포함하고, 공백은 대개 왼쪽에 있습니다. 이것이 실제 사용에서 가장 혼란스러운 동작 중 하나의 출발점입니다. 곧 다시 돌아오겠습니다.

병합이 하나 일어날 때마다 시퀀스는 짧아지고 어휘는 커집니다. 어디까지 밀어붙일지는 실제 결정사항이며, 측정할 수 있습니다. 같은 151,191byte에서 측정하면 다음과 같습니다.

수확 체감이 눈에 보입니다. 512에서 1024로 두 배 늘리면 token당 0.78byte를 얻습니다. 2048에서 4096으로 두 배 늘리면 1.07을 얻습니다. 여기서는 더 좋아 보이지만, 이 corpus가 작아서 긴 병합이 계속 보상을 주기 때문입니다. 실제 corpus에서는 곡선이 훨씬 빠르게 평평해집니다.

그리고 더 큰 어휘의 비용은 메모리만이 아닙니다. 모든 token에는 embedding 행이 필요하고, 더 비싸게는 모델의 출력층이 매 단계마다 어휘의 모든 항목에 대해 점수를 만들어야 합니다. 따라서 마지막 matrix multiply는 어휘 크기에 따라 증가합니다. 실제 모델은 32,000에서 200,000 사이에 있습니다. GPT-2는 50,257개를 사용했고, GPT-4의 cl100k는 100,277개를 사용하며, GPT-4o의 o200k는 그보다 대략 두 배입니다. 추세는 위쪽이고, 그 이유는 다음 절에 있습니다.

같은 문단을 번역한 뒤, OpenAI가 실제로 제공하는 tokenizer로 측정하면 다음과 같습니다.

같은 내용, 같은 의미인데 cl100k에서는 러시아어 버전이 token을 두 배 반이나 더 소비합니다. API는 token 단위로 과금되고 context window는 token으로 측정되므로, 이는 언어학적 호기심이 아닙니다. 영어로 일하지 않는 모든 사람에게 예산의 한 줄, 더 짧은 실질 context window, 더 느린 응답이 동시에 발생하는 문제입니다.

메커니즘은 훈련 데이터입니다. 주로 영어로 훈련된 tokenizer는 병합 예산을 영어 byte 시퀀스에 씁니다. 스페인어는 라틴 알파벳을 공유하므로 여전히 일부 이득을 얻습니다. 러시아어는 거의 얻지 못합니다. 키릴 문자는 UTF-8에서 2byte를 쓰고, 그 쌍들 중 훈련 corpus에서 충분히 흔해 병합을 얻은 것이 거의 없기 때문입니다. 일본어는 더 나쁩니다. 문자당 3byte이고, 72자가 79 tokens가 됩니다. 문자보다 token이 더 많습니다.

o200k 열은 이것이 해결 가능한 문제이며 실제로 해결되고 있음을 보여줍니다. 어휘를 두 배로 늘리고 훈련 데이터를 재조정하면 스페인어 overhead는 +39 %에서 +16 %로, 러시아어는 +152 %에서 +39 %로 줄어듭니다. 어휘가 계속 커지는 진짜 이유가 여기에 있습니다. 압축 그 자체가 아니라, 이전 세대가 조용히 전 세계의 큰 일부에게 추가 비용을 청구하고 있었다는 사실입니다.

훈련은 순서 있는 병합 목록을 만들었습니다. 새 텍스트를 인코딩할 때는 그것을 재생합니다. 그리고 반드시 같은 순서로 재생해야 합니다. 12번째 병합은 5번째와 1번째 병합의 결과를 결합하기 때문입니다. 다른 순서로 적용하면 다르고 잘못된 tokenization이 나오며, 모델이 훈련 중 본 것과 일치하지 않습니다.

    def encode(self, text):
        ids = list(text.encode("utf-8"))
        while len(ids) >= 2:
            stats = get_stats(ids)
            # the pair whose merge came FIRST during training wins   
            pair = min(stats, key=lambda p: self.merges.get(p, float("inf")))   
            if pair not in self.merges:
                break
            ids = merge(ids, pair, self.merges[pair])
        return ids

    def decode(self, ids):
        return b"".join(self.vocab[i] for i in ids).decode("utf-8", errors="replace")

디코딩은 비교하면 사소합니다. 각 id의 byte를 찾아 이어 붙이고 UTF-8로 디코딩하면 됩니다. errors="replace"에 주목하세요. 모델은 문자 중간에서 끝나는 token 시퀀스를 내보낼 수 있습니다. 이는 가정이 아닙니다. 스트리밍 응답이 이모지 중간에서 끊길 때 실제로 일어나는 일이며, 그래서 스트리밍 API는 token별로 디코딩하지 않고 부분 byte를 버퍼링합니다.

왕복 변환은 무엇에 대해서도 작동합니다. 이것이 byte-level BPE의 약속입니다.

'strawberry'                            -> 6 tokens, decode == original: True
'Alice was beginning to get very tired' -> 14 tokens, decode == original: True
'café — naïve — 日本語'                   -> 23 tokens, decode == original: True

메커니즘이 분명해지면, 서로 관련 없어 보이던 불만들이 결국 같은 불만임을 알 수 있습니다.

산술. 숫자는 일관된 방식으로 쪼개지지 않습니다.

1234     -> 2 tokens  ['123', '4']
12345    -> 2 tokens  ['123', '45']
1000000  -> 3 tokens  ['100', '000', '0']
3.14159  -> 4 tokens  ['3', '.', '141', '59']
2024     -> 2 tokens  ['202', '4']

1234와 12345를 더하려면 모델은 먼저 ['123','4']와 ['123','45']가 특정 방식으로 자릿수가 정렬되는 숫자라는 사실을 알아내야 합니다. 그리고 그 정렬은 숫자 쌍마다 달라집니다. 한 숫자의 digit 위치는 다음 숫자에서도 같은 자리에 있지 않습니다. 일부 최신 tokenizer는 바로 이 장애물을 제거하기 위해 digit을 일관된 세 자리 그룹으로 강제로 나누며, 그런 tokenizer로 훈련된 모델은 산술에서 측정 가능할 만큼 더 좋습니다.

Python 들여쓰기.

'    x = 1'      -> 5 tokens  ['   ', ' x', ' =', ' ', '1']
'        x = 1'  -> 5 tokens  ['       ', ' x', ' =', ' ', '1']
'\tx = 1'        -> 4 tokens  ['\tx', ' =', ' ', '1']

공백 네 개와 공백 여덟 개는 서로 다른 단일 tokens이고, tab은 그 뒤의 문자와 융합되어 있습니다. Python에서 문법인 들여쓰기가 일관되지 않게 표현됩니다. 이는 과거 모델이 미묘하게 잘못 들여쓴 Python을 만들어내던 큰 이유이며, code-focused tokenizer가 흔한 들여쓰기 run에 명시적 token을 추가하는 이유입니다.

철자와 뒤집기. r의 개수를 세는 것과 같은 원인입니다. 모델에게 strawberry를 뒤집으라고 하는 것은 세 개의 불투명한 id 안에 들어 있는 글자들을 재배열하라고 요구하는 것입니다. 모델은 직접 보고 하는 것이 아니라 훈련 중 철자를 암기해 해냅니다. 그래서 흔한 단어는 잘하고, 드문 단어는 못합니다.

Glitch tokens. 가장 인상적인 사례는 SolidGoldMagikarp와 비슷한 문자열 집합입니다. GPT-2와 GPT-3가 이를 만나면 이상하게 행동했습니다. 반복하기를 거부하거나, 무관한 출력을 만들거나, 때로는 사용자를 모욕하기도 했습니다. 설명은 평범하며, tokenizer가 모델과 별도로 훈련된다는 사실에서 곧장 나옵니다. 그 문자열들은 tokenizer의 훈련 corpus에서는 자주 등장했습니다. Reddit 사용자명이었기 때문입니다. 그래서 자체 token을 얻었습니다. 하지만 모델의 훈련 corpus에서는 드물거나 없었습니다. 결과는 무작위로 초기화된 뒤 거의 업데이트되지 않은 embedding 행입니다. 모델에게는 사실상 한 번도 본 적 없는 기호가 있고, 그 지점의 행동은 무작위 초기화가 우연히 만든 그대로입니다.

tokenizer는 텍스트와 숫자 사이의 손실 있는 인터페이스이며, 이 장의 모든 이상한 동작은 그 인터페이스가 비쳐 보이는 순간입니다. 이 trade-off가 의도적이라는 점은 분명히 해둘 필요가 있습니다. byte-level BPE 덕분에 어떤 입력도 표현 불가능하지 않고, 시퀀스는 문자 기반일 때보다 네다섯 배 짧으며, 흔한 단어는 온전하게 도착합니다.

대가는 모델의 원자가 우리의 원자가 아니라는 것입니다. 모델은 철자를 볼 수 없는 텍스트에 대해, 자신이 보지 못한 corpus의 빈도 세기가 고른 단위로, 누구도 협상하지 않은 언어별 비용을 안고 추론합니다.

이제 정수의 시퀀스가 생겼습니다. 이것이 Part II의 나머지 모든 것에 대한 입력 형식입니다.

아직 없는 것은 한 정수 뒤에 왜 다른 정수가 와야 하는지에 대한 이유입니다. 다음 장에서는 모든 language model이 훈련되는 objective를 소개합니다. 놀랄 만큼 단순합니다. 지금까지의 tokens가 주어졌을 때, 다음 token을 예측하는 것입니다. label도, annotation도 없고, 그저 자신의 미래를 target으로 삼은 텍스트만 있습니다. 이 단일 objective가 전체 인터넷을 훈련 데이터로 바꾸며, 모델의 첫 진짜 representation이 생겨나는 곳도 여기입니다.

또한 Chapter 2의 확률의 chain rule이 정확히 맞아야 합니다. token을 하나씩 예측하는 것이 전체 문서를 modeling하는 것과 같다는 주장은 은유가 아니라 factorization이기 때문입니다.

Chapter 8은 autoregressive objective, embeddings, 그리고 모델이 누구도 넣어주지 않은 무언가를 처음 학습하는 장소를 다룹니다.

Kudo, T. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (arXiv:1804.10959)는 Unigram 모델을 소개합니다. Kudo and Richardson, SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing (arXiv:1808.06226)는 대부분의 multilingual 모델이 사용하는 구현입니다. Schuster and Nakajima, Japanese and Korean Voice Search (ICASSP 2012)는 WordPiece의 기원입니다. Andrej Karpathy의 Let's build the GPT Tokenizer와 함께 제공되는 karpathy/minbpe repository는 이 장 코드의 직접적인 조상이며, GPT-4 regex와 special-token 처리까지 포함해 훨씬 더 나아갑니다. Hugging Face LLM Course의 Chapter 6은 세 알고리즘을 worked example과 함께 나란히 설명합니다.