Bangun BPE Tokenizer: Kenapa Modelmu Tak Bisa Menghitung Huruf R

Ada dua cara yang tampak jelas untuk memasukkan teks ke jaringan, dan keduanya gagal karena alasan yang layak dipahami, sebab kegagalan itulah yang membentuk solusi.

Kata. Pecah berdasarkan spasi, beri setiap kata sebuah angka. Bahasa Inggris punya ratusan ribu bentuk kata dan model membutuhkan satu baris embedding untuk masing-masing, sehingga kosakata — dan lapisan keluaran, yang harus menghasilkan skor untuk setiap entri — menjadi sangat besar. Yang lebih buruk terjadi saat inference: kata yang tidak pernah dilihat model saat training tidak punya angka. Itulah masalah out-of-vocabulary, dan tambalan yang biasa dipakai adalah memetakan semua yang tidak dikenal ke satu token <UNK>, yang membuang informasinya. Selain itu, “kata” bukan konsep yang terdefinisi rapi: bahasa Mandarin dan Jepang tidak menaruh spasi antar kata, dan bahasa Jerman bisa menggabungkan satu nomina ke nomina lain tanpa batas.

Karakter. Tidak ada masalah out-of-vocabulary, dan kosakatanya hanya sekitar seratus simbol. Namun urutannya menjadi sangat panjang, dan Bab 9 akan menunjukkan bahwa biaya attention tumbuh kuadratik terhadap panjang urutan. Dokumen 1000 kata kira-kira berisi 5000 karakter — urutan empat hingga lima kali lebih panjang dari yang semestinya, dengan harga kuadratik. Dan tiap karakter hampir tidak membawa makna sendiri, sehingga beberapa lapisan pertama habis untuk menyusun ulang kata yang sebenarnya bisa diserahkan tokenizer dalam keadaan utuh.

Jawabannya ada di tengah: subword. Kata umum menjadi satu token, kata langka terpecah menjadi potongan, dan tidak ada yang pernah tidak dikenal karena potongan paling dasarnya adalah byte individual. Bagian menariknya adalah tidak ada orang yang merancang pemecahannya. Tokenizer dilatih, pada jenis data yang sama seperti model, dan ia belajar urutan byte mana yang layak punya angkanya sendiri dengan menghitung seberapa sering urutan itu muncul bersama.

Algoritme ini berasal dari 1994, dan dulunya adalah algoritme kompresi. Philip Gage menerbitkannya di C Users Journal sebagai cara memperkecil file dengan berulang kali mengganti pasangan byte bersebelahan yang paling sering muncul dengan byte yang tidak muncul dalam data.¹ Ia diam di sana selama dua puluh dua tahun sampai Sennrich, Haddow, dan Birch memakainya kembali untuk machine translation pada 2016 demi memecahkan masalah out-of-vocabulary.² Sekarang, pada dasarnya inilah cara setiap large language model membaca.

Loop training-nya adalah empat langkah yang diulang:

Ini seluruh trainer-nya:

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

Jalankan pada 151.191 byte prosa Inggris dan cetak dua belas merge pertama saat terjadi. Bagian ini layak dibaca pelan-pelan, karena tidak ada yang memberi tahu algoritme apa pun tentang bahasa Inggris:

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)

Ada tiga hal dalam daftar itu yang layak ditunjuk.

Merge 12 adalah kata “the” — dengan spasi di depannya dan spasi di belakangnya, sebagai satu unit, ditemukan pada iterasi kedua belas dari loop yang menghitung pasangan. Tidak ada yang memberi kamus. Ia muncul karena lima byte itu lebih sering muncul bersama daripada lima byte lain dalam bahasa Inggris.

Merge 3 sama sekali bukan teks. \xe2\x80 adalah dua byte pertama dari encoding UTF-8 untuk tanda baca tipografis — em dash, curly quotes. Algoritme tidak tahu UTF-8 itu ada, dan ia baru saja menemukan kembali sepotong strukturnya, karena encoding multi-byte secara konstruksi adalah urutan byte yang selalu muncul bersama.

Sebagian besar merge awal melibatkan spasi, dan spasi itu biasanya berada di kiri. Inilah asal salah satu perilaku yang paling membingungkan dalam praktik, yang akan kita kembali bahas sebentar lagi.

Setiap merge membuat urutan lebih pendek dan kosakata lebih besar. Seberapa jauh mendorongnya adalah keputusan nyata, dan bisa diukur — di sini pada 151.191 byte yang sama:

Diminishing returns, terlihat jelas. Menggandakan dari 512 ke 1024 memberi 0,78 byte per token; menggandakan dari 2048 ke 4096 memberi 1,07 — lebih baik di sini hanya karena korpus ini cukup kecil sehingga merge yang lebih panjang masih terus membayar. Pada korpus sungguhan, kurvanya cepat mendatar.

Dan biaya kosakata yang lebih besar bukan hanya memori. Setiap token membutuhkan satu baris embedding, dan — lebih mahal lagi — lapisan keluaran model harus menghasilkan skor untuk setiap entri dalam kosakata pada setiap langkah, sehingga perkalian matriks terakhir berskala mengikuti ukuran kosakata. Model sungguhan berada di antara 32.000 dan 200.000: GPT-2 memakai 50.257, cl100k milik GPT-4 memakai 100.277, o200k milik GPT-4o kira-kira menggandakannya. Trennya naik, dan alasannya ada di bagian berikutnya.

Ini paragraf yang sama, diterjemahkan, diukur dengan tokenizer nyata yang dikirimkan OpenAI:

Konten yang sama, makna yang sama, dan dengan cl100k versi Rusia mengonsumsi token dua setengah kali lebih banyak. Karena API menagih per token dan context window diukur dalam token, ini bukan sekadar rasa ingin tahu linguistik — ini adalah baris dalam anggaran, context window efektif yang lebih pendek, dan respons yang lebih lambat, ketiganya sekaligus, bagi siapa pun yang tidak bekerja dalam bahasa Inggris.

Mekanismenya adalah data training. Tokenizer yang dilatih terutama pada bahasa Inggris menghabiskan anggaran merge-nya untuk urutan byte bahasa Inggris. Bahasa Spanyol berbagi alfabet Latin sehingga masih mendapat sebagian manfaat; bahasa Rusia hampir tidak mendapatkannya, karena karakter Kiril memakai dua byte dalam UTF-8 dan hanya sedikit dari pasangan itu yang cukup umum dalam korpus training untuk mendapatkan merge. Bahasa Jepang lebih buruk lagi: tiga byte per karakter, dan 72 karakter menjadi 79 token — lebih banyak token daripada karakter.

Kolom o200k menunjukkan bahwa ini masalah yang bisa diselesaikan dan sedang diselesaikan. Menggandakan kosakata dan menyeimbangkan ulang data training memangkas overhead Spanyol dari +39 % menjadi +16 %, dan Rusia dari +152 % menjadi +39 %. Itulah alasan sebenarnya kosakata terus membesar: bukan kompresi demi kompresi, melainkan fakta bahwa generasi sebelumnya diam-diam membebankan biaya ekstra kepada sebagian besar dunia.

Training menghasilkan daftar merge yang berurutan. Encoding teks baru memutar ulang daftar itu — dan harus memutarnya dalam urutan yang sama, karena merge 12 menggabungkan hasil dari merge 5 dan 1. Terapkan dalam urutan berbeda dan kamu mendapatkan tokenization yang berbeda dan salah, yang tidak akan cocok dengan apa pun yang dilihat model saat training.

    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")

Decoding jauh lebih sepele jika dibandingkan: cari byte milik tiap id, gabungkan, decode sebagai UTF-8. Perhatikan errors="replace": model bisa mengeluarkan urutan token yang berakhir di tengah karakter, dan itu bukan hipotetis — itulah yang terjadi saat respons streaming terpotong di tengah emoji, itulah sebabnya API streaming melakukan buffer pada byte parsial alih-alih decoding token demi token.

Round-trip bekerja pada apa pun, dan itulah janji BPE level byte:

'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

Setelah mekanismenya jelas, sekumpulan keluhan yang tampak tidak berhubungan ternyata adalah keluhan yang sama.

Aritmetika. Angka tidak dipecah dengan cara yang konsisten:

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']

Untuk menjumlahkan 1234 dan 12345, model harus lebih dulu mengetahui bahwa ['123','4'] dan ['123','45'] adalah angka yang digitnya sejajar dengan cara tertentu — dan penyelarasannya berbeda untuk setiap pasangan angka. Digit sebuah angka tidak berada di tempat yang sama dari satu angka ke angka berikutnya. Beberapa tokenizer yang lebih baru memaksa digit terpecah menjadi grup konsisten berisi tiga tepat untuk menghilangkan hambatan ini, dan model yang dilatih dengannya terbukti lebih baik dalam aritmetika.

Indentasi Python.

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

Empat spasi dan delapan spasi adalah token tunggal yang berbeda, dan tab menyatu dengan karakter setelahnya. Indentasi, yang dalam Python adalah sintaks, direpresentasikan secara tidak konsisten — ini adalah bagian besar dari alasan model dulu menghasilkan Python dengan indentasi yang keliru secara halus, dan alasan tokenizer yang berfokus pada kode menambahkan token eksplisit untuk deretan indentasi umum.

Ejaan dan membalik kata. Penyebabnya sama seperti menghitung huruf r: meminta model membalik strawberry berarti memintanya menyusun ulang huruf di dalam tiga id yang buram. Model melakukannya dengan menghafal ejaan selama training, bukan dengan melihat, itulah sebabnya mereka melakukannya dengan baik untuk kata umum dan buruk untuk kata langka.

Glitch token. Kasus paling mencolok adalah SolidGoldMagikarp dan sekumpulan string serupa yang membuat GPT-2 dan GPT-3 berperilaku aneh — menolak mengulanginya, menghasilkan output tidak terkait, kadang menghina pengguna. Penjelasannya biasa saja dan mengikuti langsung dari fakta bahwa tokenizer dilatih terpisah dari model: string itu sering muncul dalam korpus training tokenizer (mereka adalah username Reddit), sehingga mendapat token sendiri, tetapi langka atau tidak ada dalam korpus training model. Hasilnya adalah baris embedding yang diinisialisasi secara acak dan hampir tidak pernah diperbarui. Model punya simbol yang pada dasarnya belum pernah ia lihat, dan perilakunya di sana adalah apa pun yang kebetulan dihasilkan inisialisasi acak.

Tokenizer adalah antarmuka lossy antara teks dan angka, dan setiap perilaku aneh dalam bab ini adalah antarmuka itu yang terlihat menembus. Perlu dijelaskan bahwa pertukarannya disengaja: BPE level byte berarti tidak ada input yang pernah tidak dapat direpresentasikan, urutan empat hingga lima kali lebih pendek daripada jika memakai karakter, dan kata umum datang dalam keadaan utuh.

Harganya adalah atom model bukan atom kita. Ia bernalar tentang teks yang tidak bisa ia eja, dalam unit yang dipilih oleh hitungan frekuensi atas korpus yang tidak ia lihat, dengan biaya per bahasa yang tidak pernah dinegosiasikan siapa pun.

Sekarang kamu punya urutan integer. Itulah format input untuk semua hal di sisa Bagian II.

Yang belum kamu punya adalah alasan kenapa satu integer mengikuti integer lain. Bab berikutnya memperkenalkan objektif yang dipakai untuk melatih setiap language model, dan objektif itu sangat sederhana: dengan token sejauh ini, prediksi token berikutnya. Satu objektif itu — tanpa label, tanpa anotasi, hanya teks dengan masa depannya sendiri sebagai target — adalah yang mengubah seluruh internet menjadi data training, dan dari sanalah representasi asli pertama model muncul.

Ini juga membutuhkan chain rule probabilitas dari Bab 2 benar-benar tepat, karena klaim bahwa memprediksi satu token pada satu waktu sama dengan memodelkan seluruh dokumen adalah faktorisasi, bukan metafora.

Bab 8 adalah objektif autoregresif, embeddings, dan tempat pertama model mempelajari sesuatu yang tidak pernah ditaruh siapa pun di sana.

Kudo, T. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (arXiv:1804.10959) memperkenalkan model Unigram; Kudo dan Richardson, SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing (arXiv:1808.06226) adalah implementasi yang dipakai sebagian besar model multilingual; Schuster dan Nakajima, Japanese and Korean Voice Search (ICASSP 2012) adalah asal WordPiece. Let's build the GPT Tokenizer dari Andrej Karpathy dan repository karpathy/minbpe pendampingnya adalah leluhur langsung kode dalam bab ini dan melangkah jauh lebih lanjut, termasuk regex GPT-4 dan penanganan special-token. Bab 6 Hugging Face LLM Course membahas ketiga algoritme berdampingan dengan contoh yang dikerjakan.