技術要約：インクリメンタル BPE トークナイゼーション

問題提起

現代の大規模言語モデル（LLM）のパイプラインは、トークナイゼーションにバイトペアエンコーディング（BPE）を多用している。しかし、現在の最先端の実装（例：Hugging Faceの tokenizers や OpenAIの tiktoken）は、主にオフラインのプロセスとして設計されている。これらは、入力シーケンス全体または事前にセグメント化されたチャンクが完全に観測されるまで、正規のトークナイゼーションを生成できない。このアーキテクチャ上の制限により、トークナイゼーションとモデルのプリフィル（pre-filling）を並列ではなく逐次的に実行せざるを得ず、ストリーミングや長文脈推論におけるレイテンシを増大させている。

さらに、既存の実装は、全入力に対してマージを選択するためにヒープベースの優先度付きキューに依存することが多く、その結果、グローバルな性質を持ち、バイト単位の更新への適応が困難な定式化となっている。一部のツールは、マージコストを制限するために正規表現による事前セグメント化を使用しているが、この手法は脆弱であり、病理的な入力（例：極端な文字の反復）に対して性能低下やスタック枯渇を招くことがあり、一部のツールでは $O(n^2)$ の挙動を示す。

手法

著者らは、入力テキストのあらゆるプレフィックス（接頭辞）に対するBPEトークナイゼーションの結果をリアルタイムで維持する、インクリメンタル BPE トークナイゼーションのための新しいアルゴリズムを提案している。このアプローチは、BPEの構造的特性に基づいたものであり、いくつかの主要なアルゴリズム的革新を導入している。

1. 構造的基礎

• プレフィックスの一貫性（Prefix Consistency）: 有効なBPEトークナイゼーションは自由に切り詰め可能であるという性質を利用し、成長する文字列のトークナイゼーションを、短いプレフィックスの前の有効なトークナイゼーションの拡張としてモデル化する（再計算ではなく）。
• ラストトークン ($\theta(s)$): アルゴリズムは、現在の文字列 $s$ の「ラストトークン」の維持に焦点を当てる。完全なトークナイゼーションは、ラストトークンのシーケンスによって暗黙的にエンコードされ、バックトラッキングを通じて取得可能である。
• サクセッサー・フォレスト（Successor Forest）とサフィックス・サクセッサー・ツリー（Suffix-Successor Tree）: 語彙は正規のトークンに正規化され、サクセッサー・フォレストと呼ばれる位相構造を形成する。任意の入力に対し、新しいラストトークンの探索空間は、すべての潜在的なサフィックス・トークンを整理したサフィックス・サセッサー・ツリー内に限定される。

2. モノトニック・パス特性（The Monotonic Path Property）

核心となる理論的貢献は、モノトニック・パス特性である。これは、任意の入力文字列に対して、最終トークンとして機能し得るサフィックス・トークンの集合が、サフィックス・サセッサー・ツリー内において単一の連続したパスを形成することを確立している。このパスはルート（原子トークン）に固定されており、真のラストトークン $\theta(s)$ まで延びている。この特性により、探索空間をツリー全体から単一のパスへと縮小し、効率的な検証を可能にしている。

3. アルゴリズムの実装

インクリメンタルな更新プロセスは、主に2つのステップで構成される。

1. 探索空間の特定: 持続的な平方根タイリング（square-root tiling）で拡張されたAho–Corasickオートマトンを使用し、$O(1)$ 時間で最長のサフィックス・トークン $\tau(sc)$ を特定し、境界となるサフィックス・サセッサー・ツリーを定義する。
2. パス拡張探索: 最も深い有効なノードを見つけるために、重心分解（Centroid Decomposition）を採用する。アルゴリズムは、高さ $O(\log |\tau|)$ の事前計算された重心探索木（CST）をトラバースする。各ステップにおいて、DFS線形化区間を用いてプレフィックス・ラストトークン条件（到達可能性と優先度の優位性のチェック）を検証する。これにより、アルゴリズムは $O(\log |\tau|)$ 時間で有効なパスの方向を決定できる。

4. イーガー出力メカニズム（Eager Output Mechanism）

真のストリーミングをサポートするため、著者らはイーガー出力アルゴリズムを導入している。これは、トークナイゼーション・ツリーの「アクティブ・フロンティア（Active Frontier）」、すなわち将来のトークンの親となる可能性のあるプレフィックスの範囲を特定する。これらの候補の動的な部分グラフを維持することで、境界が不変になった（すなわち、すべてのアクティブなパスが仮想ルートの単一の子に収束した）時点でトークンを放出でき、モデル推論との完全なパイプライン化が可能になる。

主な貢献

• アルゴリズムの計算量: 提案されたアルゴリズムは、各入力バイトを、最大トークン長 $t$ に対して厳密な最悪時間計算量 $O(\log_2 t)$ で処理する。これにより、長さ $n$ の入力に対して全体で $O(n \log_2 t)$ の計算量を実現する。
• ストリーミング能力: 本手法は標準的なBPEステージのドロップイン・リプレースメントとして機能し、周囲のプリプロセッシング工程の正当性を変更することなく、ストリーミング設定での効率的な部分的トークナイゼーションを可能にする。
• イーガー出力: イーガー出力メカニズムの導入により、リアルタイムのストリーミングとモデル推論とのパイプライン化が可能になり、境界解決と同時にトークンを放出できる。
• 堅牢性: 病理的な入力に対して $O(n^2)$ の挙動を示す可能性がある既存のツールとは異なり、本アプローチは安定した性能保証を維持する。
• フル・プレフィックス・サポート: すべてのプレフィックスのトークナイゼーションへのアクセスを必要とするシナリオ（例：「fill-in-the-middle」タスクやトークン・ヒーリング）を自然にサポートする。

結果

著者らはアルゴリズムをRustで実装し、Hugging Faceの tokenizers および OpenAIの tiktoken と比較したベンチマークを行った。

• スループット: インクリメンタルなアプローチは、特に正規表現による事前セグメント化を欠くシナリオ（例：CodeLlama）において、Hugging Faceのトークナイザーに対して最大 $\sim 3\times$ のエンドツーエンドのスループット向上を達成した。
• 病理的入力におけるレイテンシ: 大規模な反復を含む入力において、tiktoken は $O(n^2)$ の計算量と一致するスループットの低下を示す。対照的に、提案手法は安定したスループットを維持し、このような病理的なケースにおいて大幅なレイテンシ削減を実証した。
• イーガー出力のオーバーヘッド: イーガー出力メカニズムは、非イーガーのインクリメンタル版と比較して、エンドツーエンドのスループットにおいて約 10% のオーバーヘッドを導入する。著者らは、このコストはトークナイゼーションがI/Oや推論とパイプライン化されているシステムにおいて、相殺（amortize）可能であると指摘している。

意義と主張

本論文は、標準的なBPEとの正確な意味的互換性を維持しながら、BPEトークナイゼーションを厳密な最悪ケースの保証を持ってインクリメンタルに行えることを示している。

著者らは、彼らの研究が、理論的な形式化（プレフィックスの安定性を示唆するもの）と、実用的なエンジニアリング（グローバルかつオフラインの処理に依存してきたもの）の間の溝を埋めるものであると主張している。$O(n \log_2 t)$ の計算量を持つアルゴリズムを提供することで、本研究は以下を可能にする：

1. レイテンシの低減: トークナイゼーションをモデル推論と完全にパイプライン化できるようにすることで、ストリーミング推論における逐次的なボトルネックを取り除く。
2. システムの堅牢性: 現在のトークナイザーが持つ $O(n^2)$ の脆弱性を利用した、アルゴリズム複雑性攻撃（例：巧妙に作られた入力によるDoS攻撃）のリスクを軽減する。
3. パイプラインの最適化: グローバルなBPEコストを制限するためだけに設計された特定の事前セグメント化工程をアルゴリズム的に冗長にし、よりクリーンで効率的なパイプライン設計を可能にする。

著者らは、厳密なアルゴリズム的保証を実用的なレイテンシのメリットへと変換することにより、より堅牢で応答性が高く、エネルギー効率の高いLLMパイプラインへの道を開くものであると結論付けている。