最適なトークナイザーの発見（15 分読了）

本稿では、特定の条件下において最適なトークナイザーを計算可能にしたアルゴリズムについて紹介します。この結果は魅力的です。なぜなら、最適化されたトークン化は理論的には困難な問題 [theoretically intractable](https://arxiv.org/abs/2411.08671) であるにもかかわらず、実際には解決可能に見えるからです。私の発見は、困難な事例であっても [カット平面法 (cutting-plane)](https://en.wikipedia.org/wiki/Cutting-plane_method) の手法を用いて最適解を導き出せることがある「巡回セールスマン問題 (TSP)」に関する様々な結果と非常に似ています。 この結果が魅力的である一方で、必ずしも *有用* ではない理由がいくつかあります。第一に、既存の最先端技術はすでに最適解に近い状態（多くの場合 1% 以内）にあります。第二に、トークナイザーが *トレーニングデータ* 上で最適であっても、保持されたテストデータで評価した際、他のトークナイザーほど一般化しない可能性があります。最後に、非効率的なトークナイザーも基本的に問題ありません：語彙サイズをわずかに増やすことで、非効率なトークナイザーのコストを相殺できます。 上記の注意点があるにもかかわらず、このプロジェクトに取り組む時間は非常に楽しく、他の人々もこの問題のフロンティアを広げることに興味を持っていただけることを願っています。 ## 背景：トークナイザー フロンティア型大規模言語モデル（LLM）は通常、*トークン*と呼ばれる整数のシーケンスを学習データとして訓練されます。各トークンはあるバイト列を指し、これらのバイト列はしばしば一般的な単語に対応しています。例えば、GPT-5 トークナイザーでは、トークン 290 はバイト列" the"に対応し、6602 は" token"に対応するため、テキスト" the token"はシーケンス [290, 6602] として符号化できます。 トークンからバイトへのマッピングは「語彙（vocabulary）」と呼ばれ、LLM が訓練される前に固定されます。通常、訓練データの断片を圧縮する語彙を見つけることを目指します。具体的には、データサイズに対して必要なトークンの数を最小化する、固定サイズの語彙を選択したいと考えています。このような語彙を見つけるための支配的な手法は、数十年の歴史を持つ貪欲型圧縮アルゴリズムである[バイトペアエンコーディング（BPE）](http://www.pennelynn.com/Documents/CUJ/HTML/94HTML/19940045.HTM)です。 最近の研究論文で、[Tempus 他](https://arxiv.org/abs/2605.22821) は、トークナイゼーションを整数線形計画法（integer linear programming）と結びつけました。彼らのアプローチの基本的な考え方は、データセット全体のトークナイゼーションを一連の整数変数として表現することです。 この定式化では、各可能な語彙エントリに対して「色」変数が存在します。具体的には、データセット内のすべての一意な部分文字列ごとに 1 つの色変数を作成します。対応するバイト列が語彙に含まれている場合、その色変数は 1 となり、そうでない場合は 0 となります。また、色変数の合計が目標とする語彙サイズに等しくなるよう、単一の制約を追加します。 色は特定のバイト列に対応しますが、あるバイト列の組み合わせはデータセット全体で多数回出現する可能性があります。色の各出現に対して、それぞれ個別の「エッジ」変数が存在します。これらのエッジは協力して、データセットの実際のトークン化を符号化します。もしエッジが 1 であれば、そのエッジに対応するトークンがこの特定の場所で使用されていることを意味します。線形計画問題の目的関数は、すべてのエッジ変数の合計、つまりデータセットを符号化するのに使用されるトークンの数を最小化することです。 例えば、以下の図では、「Queue」という単語を ["Q", "ue", "ue"] というトークン列としてトークン化しています。代わりに ["Qu", "e", "ue"] としてもよかったのですが、これは現在の ILP（整数線形計画）解が示すトークン化ではありません。なぜなら、最初の「Qu」および「e」に対応するエッジ変数の値が 0 であるためです。 ![image](https://blog.aqnichol.com/2026/06/10/optimal-tokenizers/img/integer-tokenization.png) 私たちは線形計画問題（LP）を 2 つの制約によって制限します。第一に、語彙に含まれていないトークンを使用することはできません。そのために、各辺変数を対応する色変数以下に制限します。第二に、データセットがちょうど 1 つの有効な方法でトークン化されることを保証したいのです。そのためにフロー制約を追加します：データセット内の各バイト位置について、この位置に流入する辺の和が、この位置から流出する辺の和と等しくなるようにします（境界を除く）。最初の位置と最後の位置については、流出または流入の量が 1 になるようにします。整数解においては、フロー制約は次のことを主張していると見なすことができます：*エッジが入る点は、最初と最後の位置を除き、必ずエッジが出ていなければならない*。 すべての変数が整数で [0, 1] に制限されていれば、この線形計画問題は最適なトークン化を符号化するのに十分です。しかし、任意の整数線形計画問題（ILP）を効率的に解くことはできないため、Tempus らは ILP を連続的な LP に緩和し、高度に最適化されたソルバーでこれを解きます。 連続 LP の解は一般に整数値になるとは限りません。以下にその例を示します。単語「Queue」に対して、2 つの重なり合うトークン化を行う場合、["Q", "ue", "ue"] として符号化するか、["Qu", "e", "ue"] として符号化するかのどちらかになります。この解の問題点は、色の変数の合計が 2.5 になる一方で、実際に使用した色の総数が 4 つであるため、サイズ 3 の最適な語彙を見つけたことにはならないという点です。一般的に、目標とする実際の語彙サイズよりもはるかに多くの非ゼロの色変数が生じてしまう可能性があります。 ![image](https://blog.aqnichol.com/2026/06/10/optimal-tokenizers/img/fractional-tokenization.png) Tempus たちは、色の変数をいくつかの方法で「丸める」ことを提案し、整数値でありながら最適解ではない ILP（整数計画問題）の解を得ています。連続 LP の解は、最適解のトークン数に対する*下限*を与え、一方、丸められたトークナイザーは上限を与えることになります。 この研究についてもう一つ注意点を述べておく必要があります：扱いやすくするために、データセットを事前分割（単語に分割）し、重複する単語をマージしています（目的関数における重みは、その単語の出現回数に基づいて対応付けられます）。これにより線形計画問題 (LP) の変数の数が劇的に削減されますが、その結果、得られる解は事前分割器の下での「ほぼ最適」なものに限定されてしまいます。今日はこの制限を除去しようとは思いませんが、これは将来の研究として興味深い方向性となるでしょう。 ## カット平面法 昨年は、巡回セールスマン問題 (TSP) について学びました。この問題は整数計画問題 (ILP) としても定式化できます。私たちはしばしば [カット平面法](https://en.wikipedia.org/wiki/Cutting-plane_method) を用いてこの ILP を解くことができます：まず、ILP を連続的な線形計画問題 (LP) に変換し、最適解が整数値となるまで追加の制約条件を追加していきます。これらの制約は証明可能に「有効」でなければなりません。つまり、実際の整数解に対して決して違反してはならないのです。理論的には、*任意の* ILP を追加の制約を持つ連続的な LP に「変換」することは可能ですが、その魔法のような追加制約を見つけることが計算上困難な場合もあります。TSP ソルバーでは、実用的なケースにおいて効率的にそのような制約を見つけるために多数のヒューリスティック手法を用いています。Corcorde（TSP ソルバー）の著者たちは、有用なカットを見つけるための技法について書籍全体を執筆しています。 Tempus 氏らの論文を読んだ後、カット平面法をトークナイゼーションの ILP（整数計画問題）に適用できないかと考えました。この手法は次のように機能します：まず初期の LP（線形計画問題）を解いて最適トークナイゼーションに対する下限と上限を取得し、その後、有効なカットを追加して LP を再求解することでこれらの境界値を徐々に近づけ、最終的に最適解で一致させるのです。 ILP に有用な「カット族」を考案するには多大な労力と創造性が必要となるため、自分で頭を打ち付けるのではなく、このタスクを Codex に任せることにしました。当初、Codex が発見したのはほとんど何もありませんでした–いくつかのカットは LP の境界値をわずかに改善しましたが、試されたものの多くは表面的な単語のヒューリスティクスに過ぎませんでした。 次に別のアプローチを試みました：総当たり法です。「カット」とは、すべての整数解に対して満たされる制約ですが、現在の分数 LP 解に対しては違反するものです。各可能な整数解ごとに 1 つの制約を持つ補助線形計画問題を構築し、分数解の違反度を最大化するように最適化することで、カットを見つけることができます。LP の全体に対してこれを行うことはできません。なぜなら、行数が指数関数的に膨れ上がってしまうからです。しかし、LP の小さな興味深い「射影」に対してであれば実行可能です。Codex は、共通の分数色を持つ単語のペアまたはトリプルのすべての変数に注目することを提案しました。 上記の手法は、丸められたトークナイザーを改善し、下限を引き上げる非常に優れたカットを見つけました。しかし、このアプローチは非常に非効率的です。なぜなら、膨大な数の単語ペアに対して（かなり大きな）補助 LP を解く必要があるからです。次のトリックとして、Codex に実際に見つけたカット自体を分析させることにしました。 brute force cuts を調べることで、Codex はより効率的に見つけられるいくつかのカットテンプレートを見つけました。最も効果的なファミリーは、Codex が「サイクル制約」と名付けたものです。この手法では、現在の LP 解において重なり合う分数エッジのペアを見つけます。例えば、色 A と B の間で重なり合う（つまり競合する）エッジのペアが見つかるかもしれません。次に、共通の色を共有するいくつかのペア、例えば色 B と C の別のペアや、色 C と A の別のペアを見つけます。その後、対応するエッジと色の変数から制約を作成します。これは連続的な LP 解によってしばしば違反されますが、有効な整数解では決して違反されません。 競合するペア AB, BC, CA のサイクルを見つけるには、巧妙なトリックが使えます：頂点を色とし、現在の解で分数エッジとして重なり合う色のペアをすべて結ぶグラフを構築します。このグラフができたら、DFS を実行してその中のサイクルを見つけます。Codex はこれを完全に自律的に実装しましたが、これはおそらくオリジナルのトリックではないでしょう。 ## 実験設定 このプロジェクトではハードウェアの制約が大きく、Mac Studio と Mac mini のみを使用しました。このハードウェア向けに優れた GPU 加速 LP ソルバーが存在しないため、主に [HiGHS](https://highs.dev/) のシングルコアシンプレックスソルバーに頼りました。残念ながら、このソルバーは特に後続の反復処理において、多くの（潜在的に退化した）カットを適用した場合などに停止することがあることがわかりました。 このハードウェアで合理的な時間内に実験を行うために、私は単一の電子書籍を対象としました。CPU 上で解ける範囲に LP を小さく保つ必要があったため、Tempus 他による事前トークン化のアプローチを採用しました。 最後に、LP をさらに小さくするために Tempus 他からのいくつかのヒューリスティックを採用しました。例えば、5 回未満しか出現しない部分文字列に対するカラー変数を削除するなどです。また、カラーに対してバイト長制限（この場合は 16 バイト）を課しました。8 バイト制限の場合と比較すると、最適なトークン化がわずかに劣る結果となるため、この変更は効果的でした。 ## 結果 少なくともいくつかの玩具問題において、証明可能な最適なトークナイザーを見つけることができました。私が最も誇りに思うのは、『傲慢と偏見』に対する語彙サイズ 512 の最適トークナイザーです。このアルゴリズムは約 12 回の反復で収束し、所要時間は 1 日強でした。 この同じ問題に対して、語彙サイズを512から1024に増やしてみたところ、サイクル制約だけでは最適解を見つけるのに十分ではないことがわかりました。他のカット族を再び追加した後でも、下限は依然として大幅に変動し続けており、私の最新のランはまだ完了していません。間違いなく、ここにも発見すべき他のカット族が存在しており、1024語彙の問題を解決するにはそれらの一部が不可欠である可能性さえあります。 ## 今後の課題 現時点で、私の実験における主なボトルネックは線形計画法（LP）の求解時間です。多くの実験において、各LP求解には数時間から数日がかかります。HiGHS、SCIP内のソルバー、そしてOR-Tools PDLPといういくつかのソルバーを試しましたが、すべてが高度に制約された私のLPに対して処理能力を失い始めました。私の推測では、カット平面法（cutting plane approach）によって退化したLPが生じており、これが改善の余地がある潜在的な領域であると考えられます。 一般的には、誰かがこの取り組みをより大規模なコーパスへとスケールアップし続ける姿を見てみたいです。私が探求してきたカット族が、より困難な問題に対して十分であるとは考えにくく、探索すべきアイデアの豊かな空間が存在することは間違いありません。 また、pretok enizer を削除する試みも見てみたいと思います。現在、この pretokenizer があるために LPs が非常に大きくなっており、繰り返し出現する単語をマージすることができないためです。Pretokenizer を削除すると、単語ベースのカット戦略を使用できなくなります。例えば、私の一部のカット戦略では、各単語に対して有効な整数解のすべてを列挙し、これらの組み合わせを変数の部分集合に投影します。これらの戦略は、「単一の巨大な単語」からなるデータセットに対して完全に再構築する必要があります。 ## 結論 これは面白いプロジェクトであり、私からのわずかなガイダンスだけで Codex が研究ループ全体を実行する様子を見られたのは楽しかったです。今後もこれを使って遊びたいと強く願っていますが、それは「LP の実行が遅い」という問題に対する解決策を見出すことに依存しています。 このプロジェクトにおける非常にハック的な Codex による実装は [Github](https://github.com/unixpickle/tokenizer_lp) で公開されています。参考までに、私が発見した [Pride and Prejudice](https://www.gutenberg.org/cache/epub/37431/pg37431.txt) のための最適化された語彙は [こちら](https://gist.github.com/unixpickle/55079366aca7818f65697da36aca0652) にあります（コードベースが 2 つの特殊トークンを予約しているため、実際の語彙サイズは 510 です）。

最適なトークナイザーの発見（15 分読了）

背景や根拠まで確認しますか？

調べる

選ぶ

サイト