Tokenisation is NP-Complete

生成日: 2026-05-24 02:20

# Tokenisation is NP-Complete

- トークナイザを、データ集合を高々 δ 個の記号へ圧縮するものとして定式化し、その最適化問題を扱う。
- 語彙を直接選ぶ direct tokenisation と、結合操作列を選ぶ bottom-up tokenisation の二つについて、判定問題が NP 完全であることを示す。
- 結果は、Byte Pair Encoding（BPE）や UnigramLM のような近似的手法を用いる実務上の理由を、計算量の側から説明する。

## 論文の面白いところ

この論文は、日常的に使われるトークン化を、かなり素朴な問いに戻して扱う。すなわち、限られた語彙数のもとで、訓練データをもっとも短いトークン列にできるか、という問いである。言語モデルの性能評価では、トークナイザはしばしば前処理として置かれ、主役にはなりにくい。しかし、数の桁区切りや単語の分割がモデルの振る舞いを変えることは、実験的にはよく知られている。著者らはその経験的な問題を、圧縮を目的関数とする離散最適化問題として定義し、最適な解を効率よく求めることの難しさを証明する。対象は、語彙を直接選んで最短分割を行う方式と、BPE のように隣接する記号を順に結合する方式である。どちらも自然な定式化であり、現在の自然言語処理の道具立てと近い。結論は控えめだが重要で、最適トークナイザを一般に多項式時間で求める期待は持ちにくい、というものである。

## 問題設定

入力は、文字列の集合として表されるデータセット D である。トークナイザは、文字列を部分語列に変換し、その部分語列から元の文字列へ戻せるものとして扱われる。論文では、圧縮を目的とし、トークン列の長さを小さくすることをよいトークン化とみなす。direct tokenisation では、許された数 K だけ新しい部分語を語彙に加え、その語彙を用いて各文字列を最短の部分語列へ分割する。bottom-up tokenisation では、K 個の結合操作を選び、文字単位の列に順に適用して圧縮する。判定問題は、与えられた D、K、しきい値 δ に対し、全体を δ 個以下の記号に圧縮できる語彙または結合操作列が存在するかを問う。圧縮だけを目的とする点は、実際の下流性能を完全に表すものではない。それでも、列長、推論費用、多言語間のトークン数の差に直接関係するため、十分に意味のある近似目標として置かれている。

## 提案手法

本論文の主な貢献は、新しい学習アルゴリズムではなく、計算量の証明である。著者らは、最大 2 充足可能性問題（max-2-SAT）からトークン化の判定問題への多項式時間帰着を構成する。direct tokenisation では、各真偽変数に対して、真を表す部分語と偽を表す部分語を用意し、語彙選択が真偽割当と対応するように文字列集合を作る。ある節が満たされると、その節に対応する文字列がより短く圧縮されるように設計されている。したがって、十分な数の節を満たす割当が存在することと、しきい値 δ 以下へ圧縮できる語彙が存在することが一致する。bottom-up tokenisation では、結合操作の順序と形を制約するため、より多くの補助文字列を使う。こちらも、許された結合操作の選択が真偽割当を表し、満たされた節の数が圧縮量に反映されるように構成される。さらに、候補解の検証が多項式時間でできることを示し、NP 困難性だけでなく NP 完全性を得ている。

## 結果

結論として、direct tokenisation の判定問題は NP 完全である。語彙が与えられた後に、各文字列を最短に分割すること自体は、位置を節点とする有向非巡回グラフの最短路として多項式時間で解ける。しかし、どの語彙を選べばデータセット全体が最も短くなるかを探す段階が難しい。bottom-up tokenisation の判定問題も NP 完全である。これは、BPE 型の結合操作列を最適に選ぶ問題が、単なる貪欲探索の実装上の問題ではなく、一般には計算量の壁を持つことを示している。論文は、重複を除いたデータセットや、単一の長い文字列として入力を与える場合の変種にも触れている。特に bottom-up tokenisation では、単一文字列の場合にも NP 完全性が残ることが述べられる。一方で、著者らは限界も明記しており、証明は圧縮を目的とする場合に限られ、固定された小さなアルファベットで同じ難しさが成り立つかは未解決である。

## 具体例

たとえば、データセットに「ababab」「abac」「baba」のような文字列が多く含まれ、語彙に二つだけ新しい部分語を加えられるとする。direct tokenisation なら、候補として「ab」や「ba」や「aba」を語彙に入れることを考え、各文字列をできるだけ少ない部分語に分ける。「ab」を選べば「ababab」は「ab」「ab」「ab」と短くなるが、「baba」には「ba」のほうが効くかもしれない。bottom-up tokenisation なら、まず a と b を結合して「ab」を作る、次に「ab」と「ab」を結合する、といった操作列を選ぶ。ここで難しいのは、ある操作が一部の文字列にはよく効いても、別の文字列で使いたい結合の余地を奪うことである。論文の証明では、この選択の競合を max-2-SAT の真偽割当になぞらえる。真を選ぶと圧縮される文字列、偽を選ぶと圧縮される文字列を人工的に作り、同じ変数で真と偽を同時に選びにくいようにする。期待される出力は、しきい値 δ 以下まで短くできる語彙または結合操作列が存在するかという真偽値である。間違えやすい点は、語彙が決まった後の分割問題と、語彙そのものを最適に選ぶ問題を混同することで、論文が難しいと示しているのは主に後者である。

Tokenisation is NP-Complete

トークナイザを、データ集合を高々 δ 個の記号へ圧縮するものとして定式化し、その最適化問題を扱う。
語彙を直接選ぶ direct tokenisation と、結合操作列を選ぶ bottom-up tokenisation の二つについて、判定問題が NP 完全であることを示す。
結果は、Byte Pair Encoding（BPE）や UnigramLM のような近似的手法を用いる実務上の理由を、計算量の側から説明する。

論文の面白いところ

この論文は、日常的に使われるトークン化を、かなり素朴な問いに戻して扱う。すなわち、限られた語彙数のもとで、訓練データをもっとも短いトークン列にできるか、という問いである。言語モデルの性能評価では、トークナイザはしばしば前処理として置かれ、主役にはなりにくい。しかし、数の桁区切りや単語の分割がモデルの振る舞いを変えることは、実験的にはよく知られている。著者らはその経験的な問題を、圧縮を目的関数とする離散最適化問題として定義し、最適な解を効率よく求めることの難しさを証明する。対象は、語彙を直接選んで最短分割を行う方式と、BPE のように隣接する記号を順に結合する方式である。どちらも自然な定式化であり、現在の自然言語処理の道具立てと近い。結論は控えめだが重要で、最適トークナイザを一般に多項式時間で求める期待は持ちにくい、というものである。

問題設定

入力は、文字列の集合として表されるデータセット D である。トークナイザは、文字列を部分語列に変換し、その部分語列から元の文字列へ戻せるものとして扱われる。論文では、圧縮を目的とし、トークン列の長さを小さくすることをよいトークン化とみなす。direct tokenisation では、許された数 K だけ新しい部分語を語彙に加え、その語彙を用いて各文字列を最短の部分語列へ分割する。bottom-up tokenisation では、K 個の結合操作を選び、文字単位の列に順に適用して圧縮する。判定問題は、与えられた D、K、しきい値 δ に対し、全体を δ 個以下の記号に圧縮できる語彙または結合操作列が存在するかを問う。圧縮だけを目的とする点は、実際の下流性能を完全に表すものではない。それでも、列長、推論費用、多言語間のトークン数の差に直接関係するため、十分に意味のある近似目標として置かれている。

提案手法

本論文の主な貢献は、新しい学習アルゴリズムではなく、計算量の証明である。著者らは、最大 2 充足可能性問題（max-2-SAT）からトークン化の判定問題への多項式時間帰着を構成する。direct tokenisation では、各真偽変数に対して、真を表す部分語と偽を表す部分語を用意し、語彙選択が真偽割当と対応するように文字列集合を作る。ある節が満たされると、その節に対応する文字列がより短く圧縮されるように設計されている。したがって、十分な数の節を満たす割当が存在することと、しきい値 δ 以下へ圧縮できる語彙が存在することが一致する。bottom-up tokenisation では、結合操作の順序と形を制約するため、より多くの補助文字列を使う。こちらも、許された結合操作の選択が真偽割当を表し、満たされた節の数が圧縮量に反映されるように構成される。さらに、候補解の検証が多項式時間でできることを示し、NP 困難性だけでなく NP 完全性を得ている。

結果

結論として、direct tokenisation の判定問題は NP 完全である。語彙が与えられた後に、各文字列を最短に分割すること自体は、位置を節点とする有向非巡回グラフの最短路として多項式時間で解ける。しかし、どの語彙を選べばデータセット全体が最も短くなるかを探す段階が難しい。bottom-up tokenisation の判定問題も NP 完全である。これは、BPE 型の結合操作列を最適に選ぶ問題が、単なる貪欲探索の実装上の問題ではなく、一般には計算量の壁を持つことを示している。論文は、重複を除いたデータセットや、単一の長い文字列として入力を与える場合の変種にも触れている。特に bottom-up tokenisation では、単一文字列の場合にも NP 完全性が残ることが述べられる。一方で、著者らは限界も明記しており、証明は圧縮を目的とする場合に限られ、固定された小さなアルファベットで同じ難しさが成り立つかは未解決である。

具体例

たとえば、データセットに「ababab」「abac」「baba」のような文字列が多く含まれ、語彙に二つだけ新しい部分語を加えられるとする。direct tokenisation なら、候補として「ab」や「ba」や「aba」を語彙に入れることを考え、各文字列をできるだけ少ない部分語に分ける。「ab」を選べば「ababab」は「ab」「ab」「ab」と短くなるが、「baba」には「ba」のほうが効くかもしれない。bottom-up tokenisation なら、まず a と b を結合して「ab」を作る、次に「ab」と「ab」を結合する、といった操作列を選ぶ。ここで難しいのは、ある操作が一部の文字列にはよく効いても、別の文字列で使いたい結合の余地を奪うことである。論文の証明では、この選択の競合を max-2-SAT の真偽割当になぞらえる。真を選ぶと圧縮される文字列、偽を選ぶと圧縮される文字列を人工的に作り、同じ変数で真と偽を同時に選びにくいようにする。期待される出力は、しきい値 δ 以下まで短くできる語彙または結合操作列が存在するかという真偽値である。間違えやすい点は、語彙が決まった後の分割問題と、語彙そのものを最適に選ぶ問題を混同することで、論文が難しいと示しているのは主に後者である。