Bài 3: BPE (Byte-Pair Encoding) — thuật toán token hóa của GPT

Sau khi đọc xong bài này, bạn sẽ:

• Hiểu vì sao BPE là lựa chọn mặc định cho GPT và nhiều LLM khác.
• Mô phỏng được thuật toán train BPE bằng tay trên 1 corpus nhỏ.
• Phân biệt BPE thuần (character-level) và byte-level BPE.
• Dùng tiktoken để encode/decode và so sánh chi phí token giữa cl100k_base và o200k_base.
• Nhận diện những pitfall quen thuộc: tokenization số, tiếng Việt có dấu, anomalous tokens.

Bài 2 đã giải thích vì sao LLM cần tokenization; bài này tập trung vào thuật toán cụ thể mà GPT sử dụng.

BPE không phải sinh ra cho NLP. Nó được Philip Gage giới thiệu năm 1994 trong bài "A New Algorithm for Data Compression" đăng trên tạp chí The C Users Journal. Mục đích ban đầu: nén dữ liệu bằng cách thay cặp byte phổ biến nhất bằng 1 byte chưa dùng.

Sennrich, Haddow, Birch (2016) trong paper Neural Machine Translation of Rare Words with Subword Units (arXiv:1508.07909) đưa BPE vào NMT để xử lý từ hiếm và OOV (out-of-vocabulary). Đây là bước ngoặt: thay vì vocab cố định theo từ, model học các subword unit có thể ghép thành từ mới.

OpenAI GPT-2 (2019) chuyển sang biến thể byte-level BPE để loại bỏ hoàn toàn vấn đề OOV với Unicode. GPT-3, GPT-3.5, GPT-4 đều dựa trên cùng họ thuật toán này, chỉ khác vocab size và corpus train.

Một số mốc quan trọng:

• 1994: Gage — BPE cho compression.
• 2016: Sennrich et al. — BPE cho NMT (subword unit).
• 2019: GPT-2 — byte-level BPE, vocab 50,257.
• 2023: GPT-4 — vocab cl100k_base 100,000+.
• 2024: GPT-4o — vocab o200k_base ~200,000, tối ưu cho non-English.

BPE là một thuật toán greedy, lặp đi lặp lại 1 thao tác duy nhất:

"Tìm cặp 2 token kề nhau xuất hiện nhiều nhất trong corpus, gộp chúng thành 1 token mới, ghi nhớ luật gộp này."

Bắt đầu với vocab gồm các ký tự đơn (hoặc byte). Sau mỗi lần merge, vocab tăng đúng 1 phần tử. Lặp đến khi vocab đạt size mục tiêu (ví dụ 50,000 hoặc 100,000).

Kết quả thu được hai thứ:

1. Vocabulary: bảng map token (chuỗi ký tự) ↔ ID (số nguyên).
2. Merge rules: danh sách có thứ tự các luật gộp. Thứ tự rất quan trọng vì inference phải áp đúng thứ tự đã học.

Pseudo-code mô tả quá trình train:

Input:  corpus (tập text), vocab_size (size mong muốn)
Output: vocab (set token), merges (list (a, b) -> ab)

1. Tách corpus thành các "word" (theo whitespace hoặc regex).
2. Mỗi word biểu diễn thành list các character (hoặc byte).
3. Khởi tạo vocab = tập hợp tất cả character/byte xuất hiện.
4. While len(vocab) < vocab_size:
       a. Đếm tần suất mọi cặp (a, b) kề nhau trong toàn corpus.
       b. Chọn cặp (a*, b*) có tần suất cao nhất.
       c. Tạo token mới t = a* + b*.
       d. Trong mọi word, thay (a*, b*) liền kề bằng t.
       e. Thêm t vào vocab, thêm (a*, b*) -> t vào merges.

Các điểm cần chú ý:

• Pre-tokenization: trước bước 1, GPT dùng 1 regex chia text theo whitespace, dấu câu, chữ số. Nhờ đó merge không nhảy qua ranh giới từ.
• End-of-word marker: Sennrich 2016 dùng </w> ở cuối mỗi từ; GPT-2 không dùng marker mà nhúng dấu cách (ký tự Ġ trong vocab GPT-2) vào đầu token.
• Tie-breaking: khi nhiều cặp có cùng tần suất, implementation chọn theo thứ tự cố định (ví dụ thứ tự xuất hiện đầu tiên) để đảm bảo reproducible.

Corpus (lặp lại để tần suất rõ):

low low low low low lower lower
newest newest newest newest newest newest
widest widest widest

Sau pre-tokenization theo whitespace, có 4 từ unique với tần suất:

• low × 5
• lower × 2
• newest × 6
• widest × 3

Mỗi từ ban đầu được tách thành character (dùng · để biểu diễn ranh giới rõ):

low    -> l · o · w     (×5)
lower  -> l · o · w · e · r   (×2)
newest -> n · e · w · e · s · t   (×6)
widest -> w · i · d · e · s · t   (×3)

Vocab khởi tạo: {d, e, i, l, n, o, r, s, t, w} — 10 ký tự.

Iter 1. Đếm cặp:

• (e, s): 6 (newest) + 3 (widest) = 9
• (s, t): 6 + 3 = 9
• (l, o): 5 + 2 = 7
• (o, w): 5 + 2 = 7
• ...

(e, s) và (s, t) đồng hạng. Implementation thông thường chọn (e, s) (đứng trước theo thứ tự duyệt). Merge → token mới es.

newest -> n · e · w · es · t   (×6)
widest -> w · i · d · es · t   (×3)

Iter 2. Cặp (es, t): 6 + 3 = 9 — cao nhất. Merge → est.

newest -> n · e · w · est   (×6)
widest -> w · i · d · est   (×3)

Iter 3. Cặp (l, o): 5 + 2 = 7 — cao nhất. Merge → lo.

Iter 4. Cặp (lo, w): 5 + 2 = 7. Merge → low.

Iter 5. Cặp (n, e): 6 — cao nhất. Merge → ne.

Iter 6. Cặp (ne, w): 6. Merge → new.

Iter 7. Cặp (new, est): 6. Merge → newest.

Sau 7 merge, "newest" đã thành 1 token duy nhất. Tiếp tục thêm vài iter nữa sẽ có low, lower, widest cũng thành token đơn. Đây là cơ chế khiến từ phổ biến chiếm 1 ID, còn từ hiếm được tách thành nhiều subword.

Khi đã có merge rules, encode 1 chuỗi mới gồm các bước:

1. Pre-tokenize bằng regex giống lúc train.
2. Tách mỗi đoạn thành character/byte.
3. Áp các merge rule theo đúng thứ tự đã học. Mỗi bước, tìm cặp kề nhau khớp với rule sớm nhất, merge, lặp đến khi không còn cặp nào khớp.
4. Map chuỗi token còn lại sang ID.

Ví dụ với rules đã train ở bước 5, encode từ mới lowest:

l · o · w · e · s · t
-> (es)   l · o · w · es · t
-> (est)  l · o · w · est
-> (lo)   lo · w · est
-> (low)  low · est
Kết quả: [low, est]

Token lowest chưa bao giờ xuất hiện trong corpus train, nhưng vẫn ghép được từ subword đã học. Đây là tính chất giúp BPE xử lý từ chưa thấy mà không cần token <UNK>.

BPE thuần (Sennrich) thao tác trên character. Có 1 vấn đề: nếu corpus train không chứa ký tự X (ví dụ chữ Hán hiếm, ký hiệu emoji), vocab khởi tạo sẽ không có X → token đó vẫn OOV.

GPT-2 giải quyết bằng cách thao tác trên byte (UTF-8). Vocab khởi tạo cố định là 256 byte (0–255), thêm các merge tạo ra trong train. Đặc điểm:

• Mọi chuỗi Unicode đều mã hoá được sang byte → không có OOV.
• Một ký tự Unicode có thể chiếm 1–4 byte; chữ tiếng Việt có dấu thường là 2–3 byte (mỗi byte là 1 token ban đầu).
• Vocab GPT-2 thực tế là 50,257 = 256 byte + 50,000 merge + 1 token đặc biệt <|endoftext|>.

Trade-off: byte-level BPE an toàn về OOV nhưng làm các ngôn ngữ non-Latin (Trung, Nhật, Hàn, Việt) tốn nhiều token hơn so với English. Bước 12 sẽ đo cụ thể.

Vocab càng lớn, mỗi token mã hoá được nhiều ký tự hơn → input ngắn hơn nhưng embedding table lớn hơn. Vocab nhỏ giảm bộ nhớ nhưng tăng độ dài chuỗi token.

tiktoken là thư viện open-source OpenAI publish (github.com/openai/tiktoken), viết core bằng Rust nên nhanh hơn implementation Python thuần khoảng 3–6×. Cài đặt:

pip install tiktoken

Encode/decode cơ bản:

import tiktoken

enc = tiktoken.get_encoding("cl100k_base")  # GPT-3.5/GPT-4
tokens = enc.encode("Hello, AI Engineer!")
print(tokens)
# Ví dụ: [9906, 11, 15592, 29455, 0]

for tok in tokens:
    print(tok, repr(enc.decode([tok])))
# 9906   'Hello'
# 11     ','
# 15592  ' AI'
# 29455  ' Engineer'
# 0      '!'

Lấy tokenizer theo tên model (tiện hơn vì OpenAI có thể đổi encoding):

enc = tiktoken.encoding_for_model("gpt-4o")
print(enc.name)  # o200k_base

Đếm token để ước lượng chi phí:

def count_tokens(text: str, model: str = "gpt-4o") -> int:
    enc = tiktoken.encoding_for_model(model)
    return len(enc.encode(text))

print(count_tokens("Xin chào, đây là một câu tiếng Việt."))

Một implementation tối giản (~30 dòng) đủ để hiểu cơ chế. Đây là phiên bản character-level, không pre-tokenization:

from collections import Counter

def get_pairs(tokens: list[str]) -> Counter:
    pairs = Counter()
    for i in range(len(tokens) - 1):
        pairs[(tokens[i], tokens[i + 1])] += 1
    return pairs

def merge(tokens: list[str], pair: tuple[str, str]) -> list[str]:
    out, i = [], 0
    while i < len(tokens):
        if i < len(tokens) - 1 and (tokens[i], tokens[i + 1]) == pair:
            out.append(tokens[i] + tokens[i + 1])
            i += 2
        else:
            out.append(tokens[i])
            i += 1
    return out

def train_bpe(text: str, num_merges: int):
    tokens = list(text)
    merges = []
    for _ in range(num_merges):
        pairs = get_pairs(tokens)
        if not pairs:
            break
        best = pairs.most_common(1)[0][0]
        tokens = merge(tokens, best)
        merges.append(best)
    return tokens, merges

corpus = "low low low low low lower lower newest newest newest widest widest"
tokens, merges = train_bpe(corpus, num_merges=10)
print("Merges:", merges)
print("Final tokens:", tokens)

Code này không tối ưu (O(N) mỗi merge cho toàn corpus) nhưng đủ để chạy với corpus vài KB. Để hiểu một implementation production-grade nhưng vẫn ngắn, tham khảo karpathy/minbpe trên GitHub: chỉ ~3 file (base.py, basic.py, regex.py), tổng dưới 500 dòng, có notebook giải thích từng bước.

Bài 4 sẽ đi sâu, nhưng tóm lược nhanh:

SentencePiece là 1 framework chứ không phải thuật toán mới — bên trong có thể chọn BPE hoặc Unigram. Điểm phân biệt chính: nó không cần pre-tokenize theo whitespace, nhờ vậy hoạt động tốt với ngôn ngữ không có space rõ rệt như tiếng Nhật, tiếng Trung.

Khi GPT-4o ra mắt 2024, OpenAI thay tokenizer từ cl100k_base (~100K) sang o200k_base (~200K). Vocab lớn hơn được train trên corpus đa ngôn ngữ phong phú hơn, giảm đáng kể số token cần thiết cho non-English. Code so sánh:

import tiktoken

text = "Học máy là một nhánh của trí tuệ nhân tạo nghiên cứu cách máy tính học từ dữ liệu."

cl100k = tiktoken.get_encoding("cl100k_base")
o200k = tiktoken.get_encoding("o200k_base")

print("cl100k:", len(cl100k.encode(text)), "tokens")
print("o200k :", len(o200k.encode(text)),  "tokens")

Kết quả thực tế (chạy với tiktoken 0.7+) cho thấy o200k giảm xấp xỉ 35–50% token cho tiếng Việt, vì các âm tiết có dấu (như "trí", "máy") trước đây bị tách thành 2–3 byte token, nay được học thành 1 token đơn.

Hệ quả thực tế khi build sản phẩm tiếng Việt:

• Cùng 1 đoạn text, dùng GPT-4o thường rẻ hơn GPT-3.5/GPT-4 ngay cả khi giá per-token cao hơn.
• Context window 128K của GPT-4o với tokenizer o200k chứa được nhiều nội dung tiếng Việt hơn so với cl100k.

BPE train trên 1 corpus (thường là crawl web), nhưng LLM train trên corpus khác (đã filter). Khi corpus train tokenizer chứa các chuỗi hiếm — ví dụ username trên Reddit, log spam, đoạn HTML lặp — chúng có thể chiếm 1 token ID nhưng gần như không xuất hiện trong dữ liệu train model. Token đó được embedding chưa được tinh chỉnh, dẫn đến hành vi lạ khi user nhập vào.

Trường hợp nổi tiếng là SolidGoldMagikarp (username Reddit), được phát hiện bởi Jessica Rumbelow và Matthew Watkins (2023). Khi yêu cầu GPT-3 lặp lại từ này, model trả lời nhầm sang từ khác, hoặc câu vô nghĩa. Các token tương tự: petertodd, StreamerBot, davidjl... Bài viết "SolidGoldMagikarp (plus, prompt generation)" trên LessWrong tổng hợp 100+ trường hợp.

Ý nghĩa thực tế:

• Tokenizer và model phải được audit cùng nhau.
• Khi build ứng dụng, không assume mọi token ID đều có embedding "khỏe mạnh".
• Với model nội bộ, có thể loại bỏ token rare khỏi vocab khi fine-tune.

Một số vấn đề BPE gây ra mà LLM engineer hay gặp:

• Tokenization số kém: 1234567 có thể bị tách 123 + 4567 hoặc 12 + 34 + 567 tùy tokenizer. Model khó "đếm" hoặc cộng số dài chính xác. Llama 3 mitigate bằng cách ép split mỗi digit thành 1 token.
• Reverse string khó: prompt "đảo ngược chuỗi 'hello'" thường sai vì model thấy 1–2 token chứ không thấy từng ký tự. Workaround: chèn space giữa các ký tự để force tách.
• Tiếng Việt có dấu: 1 âm tiết như "trường" có thể tốn 4–6 token trong cl100k. Tăng chi phí và giảm độ dài hiệu dụng của context.
• Whitespace nhạy cảm: " hello" và "hello" là 2 token khác nhau trong byte-level BPE. Tab vs space cũng khác. Khi build prompt template, để ý từng ký tự trắng.
• Trailing space khi streaming: nếu prompt kết thúc bằng space, model có thể không sinh tốt vì token tiếp theo gần như chắc chắn không bắt đầu bằng space.

Công cụ debug nhanh: platform.openai.com/tokenizer — paste text vào, xem token split trực quan. Có thể chuyển giữa các encoding.

Bài 1. Cài tiktoken, encode chuỗi "Llama-3 là model mạnh" với cả cl100k_base và o200k_base. So sánh số token và in từng token (gồm phần text).

Bài 2. Implement bước merge BPE bằng tay cho corpus 5 từ tự chọn (ví dụ: lower lowest low slow slower). Chạy 5 iter, ghi lại merge list.

Bài 3. Dùng tiktoken tìm 1 từ tiếng Anh có ≥ 5 token với cl100k_base (gợi ý: thử từ hiếm, từ ghép dài, hoặc tên riêng).

Bài 4. Lấy 1 đoạn tiếng Việt ~200 từ (ví dụ 1 đoạn báo VnExpress). Tính tỉ lệ tokens / words với cl100k_base và o200k_base. Ghi nhận chênh lệch.

Bài 5 (nâng cao). Clone karpathy/minbpe, train tokenizer trên file taylor.txt trong repo với vocab_size=512. So sánh tokens output với tiktoken cho cùng input.

Bài 4 sẽ đi vào SentencePiece và WordPiece — tokenizer của BERT (Google) và họ Llama / T5. Cùng họ subword với BPE nhưng tiêu chí merge và xử lý whitespace khác.