論文の概要: Tokenisation over Bounded Alphabets is Hard

• arxiv url: http://arxiv.org/abs/2511.15709v1
• Date: Wed, 19 Nov 2025 18:59:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-20 15:51:28.955901
• Title: Tokenisation over Bounded Alphabets is Hard
• Title（参考訳）: 境界のAlphabetに対するトークン化は難しい
• Authors: Violeta Kastreva, Philip Whittington, Dennis Komm, Tiago Pimentel,
• Abstract要約: 近年の研究では、トークン化はNP完全であることが示されている。 制限付き$n$-aryアルファベット上でトークン化を分析することで、このギャップを埋める。 単一アルファベットに適用しても, 直接トークン化はNP完全であることを示す。
• 参考スコア（独自算出の注目度）: 16.03769637630728
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent works have shown that tokenisation is NP-complete. However, these works assume tokenisation is applied to inputs with unboundedly large alphabets -- an unrealistic assumption, given that in practice tokenisers operate over fixed-size alphabets, such as bytes or Unicode characters. We close this gap by analysing tokenisation over bounded $n$-ary alphabets, considering two natural variants: bottom-up tokenisation and direct tokenisation, where we must, respectively, select a sequence of merge operations or a vocabulary whose application optimally compresses a dataset. First, we note that proving hardness results for an $n$-ary alphabet proves the same results for alphabets of any larger size. We then prove that even with binary alphabets, both variants are not only NP-complete, but admit no polynomial-time approximation scheme (unless P=NP). We further show that direct tokenisation remains NP-complete even when applied to unary alphabets. While unary alphabets may not be practically useful, this result establishes that the computational intractability of tokenisation is not an artifact of large alphabets or complex constructions, but a fundamental barrier. Overall, our results explain why practical algorithms such as BPE and UnigramLM are heuristic, and points toward approximation algorithms being an important path going forward for tokenisation research.
• Abstract（参考訳）: 近年の研究では、トークン化はNP完全であることが示されている。 しかし、これらの研究はトークン化が非有界な大きなアルファベットを持つ入力に適用されることを前提としており、これは非現実的な仮定であり、実際にはバイトやUnicode文字のような固定サイズのアルファベット上でトークン化が実行されることを前提としている。 我々は、ボトムアップトークン化と直接トークン化という2つの自然な変種を考慮して、有界な$n$-aryアルファベット上のトークン化を分析して、このギャップを埋める。 まず、$n$-aryアルファベットに対する硬さの証明結果が、任意の大きなアルファベットに対して同じ結果を示すことに留意する。 次に、二進アルファベットであっても、どちらの変種もNP完全であるだけでなく、多項式時間近似スキーム(P=NPがなければ)を認めないことを証明する。 さらに、単一アルファベットに適用しても、直接トークン化はNP完全であることを示す。 一元文字は実用的には有用ではないかもしれないが、この結果は、トークン化の計算的難読性は大きなアルファベットや複雑な構成の人工物ではなく、基本的な障壁であることを証明している。 全体として、BPEやUnigramLMのような実用的アルゴリズムがヒューリスティックな理由を説明し、トークン化研究において近似アルゴリズムが重要な道であることを示す。

関連論文リスト

• On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach [59.589793281734636]
  我々は,アルファベットサイズと入力長の両方が状態数である場合に,統計的クエリの硬さを確立することができることを示す。 この結果は、半オートマタの内部状態遷移構造からのみ導かれる。
  論文  参考訳（メタデータ） (2025-10-05T09:35:35Z)
• A Partition Cover Approach to Tokenization [24.595558878756787]
  トークン化とは、文字列を一定の語彙サイズのトークンに符号化するプロセスである。 Byte-Pair corpora (BPE) は、トークン化問題を圧縮問題として定式化し、マージのシーケンスを実行することでそれに取り組む。 GreedTokは圧縮においてBPEやUnigramよりも優れており、GreedWMCに匹敵するカバースコアが得られることを示す。
  論文  参考訳（メタデータ） (2025-01-08T17:07:07Z)
• Tokenization as Finite-State Transduction [24.19959327497118]
  正規言語の全てのトークン化を効率的にエンコードできる有限状態フレームワークを導入する。 そのByte-Pairを示します。 Match(BPE)とMaxPiece(WordPiece)がこのフレームワークに適合する。 これの応用は、あるパターンにマッチするように言語モデルの出力を制約するガイド付き生成である。
  論文  参考訳（メタデータ） (2024-10-21T07:10:07Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Constructing a BPE Tokenization DFA [0.0]
  決定論的有限オートマトン(DFA)の効率的な構築と解析 本稿では,文字列とそれらの正しいトークン化の関係を正確に記述した入力決定型文字列列列変換器の構築方法について述べる。
  論文  参考訳（メタデータ） (2024-05-13T11:59:24Z)
• Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
  4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。 我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。 EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
  論文  参考訳（メタデータ） (2023-10-23T18:26:00Z)
• Linear-Time Modeling of Linguistic Structure: An Order-Theoretic Perspective [97.57162770792182]
  文字列内のトークンのペア間の関係をモデル化するタスクは、自然言語を理解する上で不可欠な部分である。 これらの徹底的な比較は避けられ、さらに、トークン間の関係を文字列上の部分順序としてキャストすることで、複雑さを線形に減らすことができる。 提案手法は,文字列中の各トークンの実際の数を並列に予測し,それに従ってトークンをソートすることで,文字列内のトークンの総順序を決定する。
  論文  参考訳（メタデータ） (2023-05-24T11:47:35Z)
• Better Than Whitespace: Information Retrieval for Languages without Custom Tokenizers [48.036317742487796]
  語彙マッチング検索アルゴリズムのための新しいトークン化手法を提案する。 教師なしのデータから自動的に構築できるWordPieceトークンライザを使用します。 以上の結果から,mBERTトークン化器は,ほとんどの言語において,"アウト・オブ・ザ・ボックス(out of the box)"を検索するための強い関連信号を提供することがわかった。
  論文  参考訳（メタデータ） (2022-10-11T14:32:46Z)
• Improving Tokenisation by Alternative Treatment of Spaces [7.596737214110957]
  空間は常に個々のトークンとして扱われる別のトークン化アプローチを実験する。 修正アルゴリズムにより、下流のNLPタスクのパフォーマンスが向上することがわかった。
  論文  参考訳（メタデータ） (2022-04-08T13:22:30Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。