BPEトークナイザ

実装: llm/bpe/ / 実行: go test ./llm/bpe/

LLM は文字列を直接扱わず、トークン ID の列を受け取る。その切り方を決めるのがトークナイザで、GPT 系が使う BPE は「コーパスで最も頻出する隣接ペアを 1 つに併合する」を繰り返すだけの貪欲アルゴリズムでできている。この章では併合の学習と encode / decode を Go で実装し、語彙サイズと系列長のトレードオフ、日本語がトークン効率で不利になる理由まで確かめる。

この章で作るもの

言語モデルは文字列をそのまま読まない。読むのは、決められた語彙のどれに当たるかを表す番号(トークン ID)の列になる。この編で後から作るモデルも、入口と出口はすべてこの ID 列になる。文字列をその ID 列に変える入口が、この章で作るトークナイザだ。

素朴には 2 つの極端がある。1 文字 = 1 トークンにすると語彙は小さいが系列が長くなりすぎる。後で作るモデルの中心部(attention)は系列長の2乗で重くなるので、これは効く。1 単語 = 1 トークンにすると系列は短いが語彙が数百万に膨れ、しかも辞書に無い語(新語、タイポ、固有名詞)を扱えない。BPE(byte-pair encoding)はこの間を取る。頻出する並びだけを 1 トークンに育てることで、よく出る語は丸ごと 1 トークン、珍しい語は細かい部品の組み合わせで表す。

コーパス: low low low lower lower newest

rune 単位      [l][o][w]   [ ][l][o][w][e][r]   [ ][n][e][w][e][s][t]
併合1 (l,o)    [lo][w]     [ ][lo][w][e][r]     変化なし
併合2 (lo,w)   [low]       [ ][low][e][r]       変化なし
併合3 (␣,low)  [low]       [ low][e][r]         変化なし

BPE の学習。rune 単位から始めて、最頻の隣接ペアを 1 トークンに併合する操作を繰り返す。頻出語 low は 2 手で 1 トークンになり、先頭の空白ごと併合されるトークンも生まれる

順に見ていく。

学習 = 頻出ペアの併合の繰り返し: 数えて、最多を併合して、また数える。それだけで頻出語が 1 トークンに育つ
チャンク分割が忠実性を守る: 空白を次の語の先頭に付けて割り、チャンク内だけで併合する。連結すれば必ず元に戻るので decode が壊れない
語彙サイズは設計変数: 併合回数がそのまま語彙数になる。増やせば系列は短くなるが、埋め込み表が太る

① チャンク分割: 空白は次の語に付ける

学習の前に、テキストを併合の及ぶ単位に割っておく。空白で切るが、空白を捨てずに次の語の先頭に付けるのが GPT-2 流だ:


// chunks はテキストを「空白は次の語の先頭に付ける」単位に割る。
// "low lower" → ["low", " lower"]。どんな入力でも連結すれば元に戻るので、
// チャンク内だけで併合しても decode の忠実性が壊れない。
func chunks(text string) []string {
	var out []string
	var cur []rune
	for _, r := range text {
		if r == ' ' && len(cur) > 0 {
			out = append(out, string(cur))
			cur = cur[:0]
		}
		cur = append(cur, r)
	}
	if len(cur) > 0 {
		out = append(out, string(cur))
	}
	return out
}

"low lower" は ["low", " lower"] になる。この分割には 2 つの意味がある。まず、チャンクを連結すれば必ず元の文字列に戻るので、encode → decode の往復が構造的に保証される。次に、語の先頭かどうかが区別される。実物の GPT でも "low" と " low"(文中の low)は別トークンで、これはこの分割の帰結だ。

② 学習: 数えて、併合して、また数える

学習本体は驚くほど単純で、「隣接ペアをチャンク頻度の重み付きで数え、最多のペアを 1 トークンに併合する」を指定回数繰り返す:


// Train はコーパスから numMerges 回の併合規則を学習する。
// 各ステップで「最も頻出する隣接ペア」を選ぶ。同数のペアは辞書順の
// 小さい方を選び、実行のたびに同じ結果になる(決定的)。
func Train(corpus string, numMerges int) *Tokenizer {
	freq := map[string]int{}
	var order []string
	for _, c := range chunks(corpus) {
		if freq[c] == 0 {
			order = append(order, c)
		}
		freq[c]++
	}

	// 各チャンクをシンボル列(最初は rune 単位)に展開する。
	seqs := make([][]string, len(order))
	baseSet := map[string]bool{}
	for i, c := range order {
		for _, r := range c {
			seqs[i] = append(seqs[i], string(r))
			baseSet[string(r)] = true
		}
	}

	vocab := append([]string{"<unk>"}, sortedKeys(baseSet)...)
	var merges []Pair
	for len(merges) < numMerges {
		// 隣接ペアをチャンク頻度の重み付きで数える。
		count := map[Pair]int{}
		for i, s := range seqs {
			w := freq[order[i]]
			for j := 0; j+1 < len(s); j++ {
				count[Pair{s[j], s[j+1]}] += w
			}
		}
		best, ok := bestPair(count)
		if !ok {
			break // もう併合できる隣接ペアが無い
		}
		merges = append(merges, best)
		vocab = append(vocab, best.Left+best.Right)
		for i := range seqs {
			seqs[i] = applyMerge(seqs[i], best)
		}
	}

	ids := make(map[string]int, len(vocab))
	for i, v := range vocab {
		ids[v] = i
	}
	return &Tokenizer{merges: merges, vocab: vocab, ids: ids}
}

// bestPair は最多ペアを返す。同数は (Left, Right) の辞書順で決定的に選ぶ。
func bestPair(count map[Pair]int) (Pair, bool) {
	var best Pair
	bestN := 0
	for p, n := range count {
		if n > bestN || (n == bestN && less(p, best)) {
			best, bestN = p, n
		}
	}
	return best, bestN > 0
}

func less(a, b Pair) bool {
	if a.Left != b.Left {
		return a.Left < b.Left
	}
	return a.Right < b.Right
}

func sortedKeys(set map[string]bool) []string {
	out := make([]string, 0, len(set))
	for k := range set {
		out = append(out, k)
	}
	for i := 1; i < len(out); i++ {
		for j := i; j > 0 && out[j] < out[j-1]; j-- {
			out[j], out[j-1] = out[j-1], out[j]
		}
	}
	return out
}

// applyMerge はシンボル列の中の (Left, Right) 隣接をすべて 1 トークンに
// 置き換えた新しい列を返す。左から一度だけ走査する。
func applyMerge(s []string, p Pair) []string {
	out := make([]string, 0, len(s))
	for i := 0; i < len(s); {
		if i+1 < len(s) && s[i] == p.Left && s[i+1] == p.Right {
			out = append(out, p.Left+p.Right)
			i += 2
		} else {
			out = append(out, s[i])
			i++
		}
	}
	return out
}

押さえておく点が 2 つある。1 つは貪欲であること。各ステップの最多ペアを取るだけで、全体最適の切り方を探索してはいない。それでも実用上十分に効くというのが BPE の発見だった。もう 1 つは決定性で、同数のペアは辞書順でタイブレークするので、同じコーパスからは必ず同じ語彙ができる。テストでは同数ペアの選択順まで固定して確かめている。

③ encode / decode: 学習と同じ順で適用する

encode は、学習した併合規則を学習時と同じ順でテキストに適用し直すだけだ:


// Tokens は学習した併合規則を順に適用してトークン文字列の列を返す。
// 学習時と同じ順で適用するので、同じ文字列は必ず同じ切り方になる。
func (t *Tokenizer) Tokens(text string) []string {
	var out []string
	for _, c := range chunks(text) {
		var s []string
		for _, r := range c {
			s = append(s, string(r))
		}
		for _, m := range t.merges {
			s = applyMerge(s, m)
		}
		out = append(out, s...)
	}
	return out
}

// Encode はテキストをトークン ID 列にする。学習コーパスに無かった rune は
// <unk>(ID 0) になる。実物は基底をバイトにすることで未知を根絶している
// (byte-level BPE)。ここでは教材のため rune 基底 + <unk> で単純化する。
func (t *Tokenizer) Encode(text string) []int {
	toks := t.Tokens(text)
	out := make([]int, len(toks))
	for i, tk := range toks {
		if id, ok := t.ids[tk]; ok {
			out[i] = id
		}
	}
	return out
}

decode は語彙表を引いて連結するだけで済む。チャンク分割が空白を保存しているので、特別な復元処理は要らない:


// Decode はトークン ID 列を文字列に戻す。<unk> と範囲外は � になる。
func (t *Tokenizer) Decode(ids []int) string {
	var b strings.Builder
	for _, id := range ids {
		if id <= 0 || id >= len(t.vocab) {
			b.WriteString("�")
			continue
		}
		b.WriteString(t.vocab[id])
	}
	return b.String()
}

テストでは、学習コーパスと新規テキストの両方で encode → decode の往復一致、併合を増やすとトークン数が減ること(圧縮)、未知 rune が <unk> に落ちることを固定している。

動かす

下のデモは、この実装をそのまま移植して学習過程を 1 併合ずつ追える。コーパスは上の図と同じで、各ステップで「どのペアが何回出て併合されたか」と、サンプル文の切り方がどう粗くなっていくかが見える。未知文字を含む文に切り替えると <unk> の挙動も確かめられる。

デモBPE(併合の学習)rune 単位

コーパス: low low low lower lower newestlow lowernewest lowestbox lower(未知)

学習済みの併合規則(適用順)

(まだ無し)

「low lower」の切り方 9 トークン

low␣lower

併合ゼロ = rune 単位の切り方。ここから「最頻の隣接ペアを 1 つに併合する」を繰り返して語彙を育てる

1 / 9

␣ は語の先頭に付いた空白。頻出語 low は 2 手で 1 トークンになり、文中形の「␣low」も 1 トークンに育つ。コーパスに無い文字(b, x)は語彙に無いので <unk> に落ちる。実物はバイト基底にすることで未知そのものを無くしている。

設計の観点

語彙サイズのトレードオフ: 語彙を増やすと系列が短くなり、系列長の2乗で効く attention のコストが下がるが、埋め込み表と出力射影(語彙 × d 次元)が太る。GPT-2 は約 5 万、最近のモデルは 10〜25 万。多言語対応ほど大きくする圧力がかかる
なぜ日本語は不利か: 併合はコーパスの頻度で決まる。英語中心のコーパスで学習すると日本語の並びは併合が育たず、同じ内容でも英語より多くのトークンを消費する。API 課金もコンテキストウィンドウもトークン単位なので、これは実利用のコスト差になる
byte-level BPE: 基底を rune でなくバイトにすると、どんな入力も必ず 256 種の基底で表せて未知が原理的に消える。GPT-2 以降の標準。この章の <unk> はその手前の教材的単純化
トークナイザはモデルと不可分: 併合規則が 1 つ違えば同じテキストが別の ID 列になる。学習済みモデルは自分のトークナイザとしか組めず、語彙の拡張は再学習や埋め込みの継ぎ足しを要する
トークン化由来の失敗: 「strawberry に r は何個か」にモデルが誤答しがちなのは、strawberry が 1〜2 トークンに併合され文字の並びとして見えていないため。数字の切られ方が算術の精度に響くのも同根

メリット・デメリットと実例

方式	学習	未知語	実例
BPE(頻度併合)	頻出ペアの貪欲併合	byte-level なら根絶	GPT-2 以降の GPT 系(tiktoken)、RoBERTa
WordPiece	尤度が最も上がるペアを併合	`##` 接頭辞 + `[UNK]`	BERT
Unigram(SentencePiece)	大きい語彙から尤度で削る	基底文字に分解	Llama、T5、Gemma
文字 / バイト単位	学習不要	なし	ByT5(バイト直入力の研究系)

裏どり:

Sennrich らの論文(2015): 機械翻訳の未知語対策として BPE をサブワード分割に転用した原典。圧縮アルゴリズム(1994)の再発見だった
tiktoken: OpenAI の BPE 実装。GPT-4o 系の o200k_base など、モデルごとに固定の併合規則が公開されている
SentencePiece: 空白も含めて生テキストから直接学習する Google のツール。Llama 系や T5 が採用し、オープンモデルでは BPE と並ぶ標準
Karpathy の minbpe: 教材実装の定番。この章と同じく「数えて併合するだけ」を数百行で示している

簡略化したこと

基底が rune: 実物はバイト基底(byte-level BPE)で <unk> が存在しない。rune 基底は未知文字が残るが、併合の仕組み自体は同じ
事前分割が空白のみ: 実物は正規表現で句読点・数字・大文字境界なども切ってから併合する(GPT-2 の pattern が有名)
正規化なし: Unicode 正規化(NFC)や制御文字の扱いは持たない
特殊トークンなし: 実物にある文頭・文末・会話区切りなどの特殊トークン(<|endoftext|> 等)は扱わない

参考資料

Sennrich et al., Neural Machine Translation of Rare Words with Subword Units(2015) — BPE をサブワード分割に使った原典
tiktoken — OpenAI の BPE 実装と公開語彙
Kudo & Richardson, SentencePiece(2018) — Unigram 方式と生テキスト学習
minbpe (Karpathy) — 最小 BPE 実装の教材
実装: llm/bpe

BPEトークナイザ ​

この章で作るもの ​

① チャンク分割: 空白は次の語に付ける ​

② 学習: 数えて、併合して、また数える ​

③ encode / decode: 学習と同じ順で適用する ​

動かす ​

設計の観点 ​

メリット・デメリットと実例 ​

簡略化したこと ​

参考資料 ​