💬 NLP

Tokenisation via Convex Relaxations

本論文は、語彙構築を凸最適化により解ける線形計画問題として定式化する新たなトークナイゼーションアルゴリズム ConvexTok を導入し、これにより従来の貪欲法よりも内在的指標および言語モデルの効率性において優れつつ、最適性からの近さについて保証された境界を提供する。

原著者： Jan Tempus, Philip Whittington, Craig W. Schmidt, Dennis Komm, Tiago Pimentel

公開日 2026-05-22

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Jan Tempus, Philip Whittington, Craig W. Schmidt, Dennis Komm, Tiago Pimentel

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

「Tokenisation via Convex Relaxations」という論文を、平易な言葉と創造的な比喩を用いて解説します。

全体像：スーツケースへの詰め込み

あなたが友人に送るために、巨大な図書館の本を一台のスーツケース（コンピュータのメモリ）に詰め込もうとしている状況を想像してください。これを効率的に行うためには、トークナイザが必要です。

AI の世界において、トークナイザはカスタムスタンプのセットのようなものです。すべての本のすべての文字を一つずつ送る（これは遅く、かさばります）のではなく、トークナイザは文字を「チャンク」や「トークン」（単語全体や一般的なフレーズなど）にグループ化し、それらを代わりに送ります。目標は、到着時に本を完全に復元できるようにしつつ、スーツケースを可能な限り小さくすること（高圧縮）です。

問題点：「欲張り」なパッカー

現在、ほとんどの AI モデルはBPE（Byte-Pair Encoding：バイトペア符号化）と呼ばれる手法を使用しています。BPE は欲張りなパッカーのようなものです。

仕組み： パッカーは本を見て、隣り合って現れる最も一般的な 2 つの文字（例えば「t」と「h」）を見つけ、それらを新しいスタンプ（「th」）に貼り合わせ、このプロセスを繰り返し行います。
欠点： パッカーはその次の瞬間のステップしか見ていない（局所的に最適）ため、今すぐには役立つように見える 2 つの文字を貼り合わせても、後になってスーツケースに収まりきらない奇妙で非効率な形を作ってしまう可能性があります。彼らは小さな良い判断を積み重ねることで、結果的に悪い全体像を生み出してしまいます。彼らは「全体像」を見渡すために一歩引くことを決してしません。

解決策：「建築家」アプローチ（ConvexTok）

この論文の著者である Jan Tempus とその同僚たちは、欲張りなパッカーの使用を中止することにしました。代わりに、彼らは建築家を構築しました。

彼らは、スーツケースを完璧に詰める方法を見つけることは、コンピュータが通常あきらめてしまうほど難しい数学的問題（「NP 困難」）であると気づきました。しかし、彼らは巧妙なトリックを見つけました。**凸緩和（Convex Relaxation）**です。

比喩： 家を建てるために山脈の最も低い地点を見つけようとしている状況を想像してください。欲張りなパッカーは、小さな谷に到達するまで下り坂を歩き、そこが底だと考えてそこで立ち止まります。
建築家のトリック： 著者たちは、ギザギザした山々を完璧に滑らかなボウル（「凸」の形状）に滑らかにしました。この滑らかなボウルの中では、絶対的な最低点を数学的に見つけることが容易です。
結果： 彼らは**線形計画（Linear Program: LP）**と呼ばれるツールを使って、この滑らかで簡単なバージョンの問題を解きました。これにより、完璧な詰め込みの「設計図」が得られました。

落とし穴：設計図から現実へ

滑らかなボウルから得られた設計図には問題がありました。それは「半分のスタンプ」を使用することを提案していたのです。例えば、「『th』スタンプを 0.7 個、『ing』スタンプを 0.3 個使用せよ」といった具合です。実際には半分のスタンプを印刷することはできません。

これを修正するために、彼らはこれらの数字を整数のスタンプに丸める（0.7 を 1 に切り上げるなど）3 つの方法を考案しました。

決定論的（Det）： 最も高いスコアを持つ上位 $K$ 個のスタンプを選択する。
バイアス付き（Bias）： スコアがわずかに低くても、短く効率的なスタンプを選択する。
整数（Int）： 設計図が 99% 確信を持っていたスタンプのみを選択する。

発見した点（結果）

チームは、新しいConvexTok手法を、標準的な欲張りな BPE 手法と比較してテストしました。以下がその結果です。

より良い詰め込み： ConvexTok のスーツケースは、BPE のスーツケースよりも一貫して小さく（圧縮率が高く）、AI モデルが同じ量のテキストをより少ない「トークン」で読み取れることを意味しました。
「ほぼ完璧」な保証： 彼らの数学の最も素晴らしい点の一つは、「下限」を提供することです。これは「完璧なスーツケースのサイズは少なくともこれほど小さいことは分かっている」という証明書のようなものです。彼らは、ConvexTok のスーツケースがその完璧な理論的サイズから1% 以内であることを発見しました。つまり、数学的に可能な限りほぼ完璧に近いということです。
AI の性能： これらの新しいスーツケースを使用して AI モデルを訓練したとき：
- モデルはテキストの理解においてわずかに優れていました（「ビット・パー・バイト」で測定）。
- 複雑な推論タスク（論理パズルの回答など）では、結果は混在していました。ConvexTok が優れることもあれば、BPE が優れることもありましたが、ConvexTok が著しく劣ることは決してありませんでした。
安定性： 欲張りな BPE 手法は非常に安定しており、わずかに異なる本を与えても同じスタンプを作成します。新しい ConvexTok 手法は、見た特定の書籍に少し敏感であり、トレーニングデータを変更するとスタンプがわずかに変化する可能性があります。

まとめ

この論文は、AI に読み方を教えるために「欲張り」な手法を使い続けてきたと主張しています。彼らは、全体の問題を一度に見るために高度な数学（凸最適化）を使用することで、ConvexTokと呼ばれる新しいトークナイザを創り出しました。

それは、盲目的に最も一般的な文字を貼り合わせる人から、スーツケースのレイアウト全体を一度に設計する建築家へと切り替えるようなものです。その結果、テキストを圧縮するより効率的な方法が生まれ、これら AI の「スーツケース」をどれほど小さくできるかという理論的な限界に、私たちがより近づきました。

技術的サマリー：凸緩和によるトークナイズ

問題定義

トークナイズは、自然言語処理（NLP）パイプラインの基本的な構成要素であり、言語モデル（LM）向けにバイト列をトークン系列に変換する。近年の研究では、トークナイズの圧縮効率と下流のLM性能との間に相関があることが示唆されているが、最適なトークナイザを見つける問題はNP困難である。現在の最先端手法であるバイトペアエンコーディング（BPE）やユニグラムなどは、貪欲アルゴリズムに依存している。これらの手法は、結果として生じる語彙の全局的最適性を考慮することなく、局所的に最適な決定（例えば、最も頻度の高いトークン対を反復的にマージする）を下す。その結果、不要な中間トークンを生成したり、最大限の圧縮を達成できなかったりする可能性がある。本論文が扱う核心的な課題は、貪欲ヒューリスティックの限界を超え、効率的に全局的に最適なトークナイザを近似する方法である。

手法

著者は、整数計画（IP）の凸緩和から導出された線形計画（LP）としてトークナイザの構築を定式化する、新しいトークナイズアルゴリズム「ConvexTok」を提案する。

1. グラフ定式化

本問題は、まず有向非巡回グラフ（DAG）上の最短経路問題として再定式化される：

頂点: データセットのバイト列におけるバイト間の位置を表す。
辺:
- バイト辺: 隣接するバイトを接続する（個々の文字を表す）。
- トークン辺: 非隣接の頂点を接続し、複数のバイトからなる潜在的なトークンを表す。
着色: トークン辺は、表す特定のバイト列に基づいて着色される。「色」は一意のトークンに対応する。
目的: 高々 $K$ 個の異なる色（トークン）を用いた語彙において、経路の総長さ（圧縮）を最小化する、グラフの始点から終点までの経路を見つけること。

2. 整数計画（IP）

このグラフ問題は整数計画へと翻訳される。著者は、フリー辺（バイト辺）とプライス付き辺（トークン辺）の結合行列、および色分割行列を定義する。最適化変数は、以下のバイナリベクトルを表す：

セグメンテーションで使用される辺（フリー辺 $f$ 、プライス付き辺 $p$ ）。
語彙に選択される色（トークン） $c$ 。
目的は、有効な経路を確保するフロー制約と、選択される色の数を $K$ に制限する予算制約の下で、経路の総長さを最小化することである。

3. 凸緩和（LP）

IPを解くことはNP困難であるため、著者は離散制約（ $x \in \{0, 1\}$ ）を連続区間（ $x \in [0, 1]$ ）に緩和する。これにより問題は線形計画（LP）へと変換され、標準的なソルバー（具体的にはNVIDIA CuOPT内のPDLP法）を用いて効率的に解くことができる。

トークナイズ多面体: この緩和されたLPの解空間は、「部分的」なトークン（分数値）を許容し、潜在的な語彙の凸結合を表す。

4. 丸め手法

LMには離散的な語彙が必要であるため、分数のLP解を離散化する必要がある。本論文では、3つの丸め手法を提案し評価する：

決定論的（Det）: LP値が最も高い $K$ 個の色を選択する。
バイアス（Bias）: 各色のLP値をトークン長（ $c / \text{length}(c)$ ）で割った比率で色をランク付けし、スコアが同程度の場合、短いトークンを優先する。
整数のみ（Int）: LP値がすでに1に近い色のみを選択する（実質的に緩和によって「強制」されたもの）。これはしばしば予算 $K$ よりも小さい語彙をもたらす。

主要な貢献

定式化: 本論文は、多面体手法を用いた線形計画としてのトークナイザ構築の最初の定式化を提供し、トークナイズを彩色グラフ上の最短経路問題と明示的に結びつけた。
アルゴリズム（ConvexTok）: BPEなどの貪欲アプローチに内在する局所最適を回避し、全局的に最適なトークナイザを近似する新しいアルゴリズムを導入した。
最適性の証明: LP解は、与えられたデータセット上の任意のトークナイザが達成し得る圧縮の証明可能な下限を提供する。これにより、研究者は特定のトークナイザ（例えばBPEやConvexTok）が理論的な最適値にどの程度近いかを証明できる。
丸め分析: 分数のLP解を実用的なトークナイザに変換するための3つの異なる丸め戦略を体系的に評価した。

実験結果

著者は、ClimbMix400BデータセットとGPTスタイルのデコーダのみのトランスフォーマーを用いて、様々な語彙サイズ（8kから256k）においてConvexTokをBPEと比較評価した。

LP解の品質: 語彙サイズが増加するにつれて、LP解はより整数的（0または1に近い）になり、大規模なスケールでは最適なトークン選択が曖昧でなくなることを示唆している。
最適性ギャップ: LPの下限は、既存のトークナイザが驚くほど最適に近いことを明らかにしている。一般的な語彙サイズ（128k、256k）において、BPEおよびConvexTokの両変種は、最適圧縮境界の1%以内にある。
内在的指標:
- バイアス丸め手法は、語彙利用率、タイプ・トークン比、圧縮率などの内在的指標において、BPEおよび他の手法を一貫して上回った。
- BPEは、データの異なるランダム部分集合で再トレーニングされた際、ConvexTok変種よりも安定していた。これはおそらく、その頻度駆動型の局所的な性質によるものである。
言語モデル性能:
- バイトあたりのビット数（BpB）: **決定論的（Det）**丸め手法は、特に大規模な語彙サイズにおいて、BPEを上回ることも多く、一貫して最高のBpBスコアを達成した。
- 下流タスク（CORE）: 下流ベンチマーク（推論、多肢選択、常識）の結果は混合であった。ConvexTok変種はBPEと競争力があったが、すべてのタスクおよびモデルの深さにわたって一貫した顕著な優位性を示すことはなかった。
安定性: BPEは、トレーニングデータのサンプリングに関してConvexTokよりも高い安定性を示したが、整数のみ丸め手法は他のConvexTok変種よりも高い安定性を示した。

意義と主張

本論文は、全局的に最適化されたトークナイズが、局所的な貪欲なマージベース手法に対する有望な代替手段であると主張する。主な意義は、以下の点にある：

グローバルなトークナイズの解決: トークナイズが貪欲ヒューリスティックではなく、凸最適化を通じてアプローチできることを実証する。
性能の証明: 任意のトークナイザが理論的な最適値からどの程度離れているかを測定するための厳密な下限を提供する。著者は経験的に、標準的な語彙サイズにおいて、現在の手法はすでにこの最適値に非常に近い（1%以内）ことを発見した。
圧縮の改善: BPEはすでに最適に近いが、特定の丸め手法（例えばバイアス）は、わずかに優れた内在的圧縮指標をもたらす可能性があることを示す。

著者は、下流タスクの改善については控えめな見解を示しており、BpBが一貫して改善された一方で、下流のCOREタスクにおける改善は一貫性がなかったと指摘している。彼らは結論として、彼らの手法は理論的に優位な枠組みと証明可能な境界を提供するが、現在の大規模言語モデルトレーニングの文脈において、高度に調整された貪欲手法（BPEなど）に対する実用的な利益は漸進的であると述べている。