Fugu-MT 論文翻訳(概要): Online Tokenization with Optimal Delay in Linear Time

論文の概要: Online Tokenization with Optimal Delay in Linear Time

arxiv url: http://arxiv.org/abs/2610.19139v1
Date: Tue, 13 Oct 2026 20:08:40 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-15 21:06:15.782043
Title: Online Tokenization with Optimal Delay in Linear Time
Title（参考訳）: 最適遅延時間によるオンライントークン化
Abstract要約: オンライントークン化を形式化し、解決する。我々は OpenAI の Tiktoken と HuggingFace のトークン化ツールからトークン化ツールの実用的なバリエーションを実装した。
参考スコア（独自算出の注目度）: 7.856476469597698
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Tokenization is an essential preprocessing step in almost all large language models (LLMs). One of the most popular frameworks is BPE tokenization, which consists of special token segmentation, pretokenization, and byte-pair encoding (BPE). However, existing algorithms are sequential, with each stage only processing complete output from the previous stage. In order to reduce latency and memory footprints, recent works (Jiang and Gong, ICML 2026) (Li, Yang and Mamouras, ASPLOS 2026) (Mamouras, Li and Yang, PLDI 2026) have initiated the study of online algorithms for subroutines such as pretokenization and BPE with a goal of streaming input to output as the input arrives online. However, the search for efficient online tokenization remains open. In this work, we formalize and resolve online tokenization. We introduce the notion of delay for online tokenization which characterizes the extent to which the algorithm output lags behind the (possibly computationally intractable) optimum. We give a near-linear time algorithm with optimal delay (up to constant factors). We complement this algorithm with a conditional lower bound: unless $\mathbf{P} = \mathbf{NP}$, there is no polynomial time algorithm that beats the delay of our algorithm by more than a constant factor. We implement a practical variant for tokenizers from OpenAI's tiktoken and HuggingFace's tokenizers. We obtain a $7.9\times$-$34.8\times$ latency advantage (measured as time to first token) over tiktoken (as well as the recent gigatoken tokenizer) and our implementation maintains approximately constant memory usage independent of input size. Our implementation also achieves a $2.4\times$-$7.0\times$ improvement in throughput over tiktoken and $15.8\times$-$38.1\times$ over tokenizers.
Abstract（参考訳）: トークン化は、ほとんど全ての大きな言語モデル(LLM)において、必須の事前処理ステップである。最も一般的なフレームワークの1つは、特別なトークンセグメンテーション、プリトークン化、バイトペア符号化(BPE)からなるBPEトークン化である。しかし、既存のアルゴリズムは逐次的であり、各ステージは前のステージからの完全な出力のみを処理する。レイテンシとメモリフットプリントを削減するため、最近の研究(Jiang and Gong, ICML 2026) (Li, Yang and Mamouras, ASPLOS 2026) (Mamouras, Li and Yang, PLDI 2026) は、入力がオンラインに届くと入力をストリーミングする目的でプリトークン化やBPEのようなサブルーチンのオンラインアルゴリズムの研究を開始した。しかし、効率的なオンライントークン化の探索は依然として行われている。本研究では,オンライントークン化を形式化し,解決する。本稿では,オンライントークン化における遅延の概念を紹介し,アルゴリズムが(計算に難易度の高い)最適解に遅れを生じる程度を特徴付ける。最適遅延(定数要素まで)を持つニア線形時間アルゴリズムを提案する。このアルゴリズムを条件付き下界で補う: $\mathbf{P} = \mathbf{NP}$ がなければ、定数因子以上の遅延を解く多項式時間アルゴリズムは存在しない。我々は OpenAI の Tiktoken と HuggingFace のトークン化ツールからトークン化ツールの実用的なバリエーションを実装した。 7.9\times$-34.8\times$ latency advantage ( time to first token) over tiktoken (および最近のgiatoken tokenizer)。当社の実装では、Tiktokenよりもスループットが向上する$2.4\times$-$7.0\times$と、トークン化ツールよりも$15.8\times$-$38.1\times$も実現しています。

関連論文リスト

Online Differentially Private Consistent Clustering [75.99116543456606]
オンラインストリーミング環境における差分プライベート(DP)$k$-meansと$k$-medianクラスタリングについて検討した。入力ストリームの半コアセットであるプライベートストリームに(感性)入力ストリームを変換する汎用的なリダクションを与える。
論文参考訳（メタデータ） (2026-08-28T04:03:01Z)
Incremental BPE Tokenization [12.857819598120676]
本稿では,インクリメンタルByte Pairのための新しいアルゴリズムを提案する。モデル(BPE)トークン化。病理学的入力に対するOpenAIのTiktokenよりも大幅に遅延を減少させることを示した。
論文参考訳（メタデータ） (2026-05-29T04:04:32Z)
Learning to Parallel: Accelerating Diffusion Large Language Models via Learnable Parallel Decoding [21.609237262034636]
大規模言語モデル(LLM)における自己回帰復号には、$n$トークンに対して$mathcalO(n)$シーケンシャルステップが必要である。本稿では,並列デコード学習(Learn2PD)を提案する。これは軽量かつ適応的なフィルタモデルをトレーニングし,各トークン位置に対して,現在の予測が最終出力と一致するかどうかを予測するフレームワークである。この学習されたフィルタは、正しく予測された場合にのみトークンをアンマスクするオラクル並列復号法を近似する。
論文参考訳（メタデータ） (2025-09-29T17:59:54Z)
Leuvenshtein: Efficient FHE-based Edit Distance Computation with Single Bootstrap per Cell [9.554839026375568]
編集距離計算は、DNAシークエンスアライメントのようなファイナンスやゲノム学にまたがる応用において不可欠である。本稿では,Leuvenshteinと呼ばれる距離計算の編集コストを大幅に削減する最適化アルゴリズムを提案する。
論文参考訳（メタデータ） (2025-08-20T09:40:06Z)
Hardware-Aware Parallel Prompt Decoding for Memory-Efficient Acceleration of LLM Inference [23.633481089469836]
LLM(Large Language Models)の自動回帰デコーディングは、ハードウェアの性能に大きなオーバーヘッドをもたらす。トレーニング可能なパラメータを0.0002$%しか必要とせず,A100-40GBのGPUをたった16時間で効率的にトレーニングできる並列プロンプトデコーディングを提案する。我々のアプローチでは、最大2.49$times$ スピードアップを示し、最小のメモリオーバーヘッドは0.0004$%である。
論文参考訳（メタデータ） (2024-05-28T22:19:30Z)
Replicable Learning of Large-Margin Halfspaces [46.91303295440005]
我々は,大マージンハーフスペースを学習する問題に対して,効率的なアルゴリズムを提供する。 Impagliazzo, Lei, Pitassi, Sorrellによるアルゴリズム [STOC 2022] の改良を行った。
論文参考訳（メタデータ） (2024-02-21T15:06:51Z)
SkipDecode: Autoregressive Skip Decoding with Batching and Caching for Efficient LLM Inference [17.947904697850433]
バッチ推論とKeyValueキャッシュのためのトークンレベルの早期終了メソッドであるSkipDecodeを提案する。これは、各シーケンス位置のバッチ内の各トークンに対して特異レベル出口を設定することで、以前の制約を克服する。また、イグジットポイントの単調な減少を保証するため、前のトークンに対してKVキャッシュを再コンパイルする必要がなくなる。
論文参考訳（メタデータ） (2023-07-05T19:59:09Z)
Vcc: Scaling Transformers to 128K Tokens or More by Prioritizing Important Tokens [65.4435926060951]
本稿では,超長周期の変換器の効率を,各層でより小さな表現に圧縮することで向上することを提案する。我々のアルゴリズムは効率的であるだけでなく(4Kと16Kのベースラインに比べて3倍以上の効率向上を達成する)、多数のタスクで競合/ベターパフォーマンスを提供する。
論文参考訳（メタデータ） (2023-05-07T10:32:18Z)
Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文参考訳（メタデータ） (2021-10-15T00:54:04Z)
Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
論文参考訳（メタデータ） (2021-06-01T19:51:55Z)

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

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