論文の概要: Component-Weighted Centroid Search for Exact Incremental BPE

• arxiv url: http://arxiv.org/abs/2609.40016v1
• Date: Wed, 30 Sep 2026 15:55:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:27.994345
• Title: Component-Weighted Centroid Search for Exact Incremental BPE
• Title（参考訳）: 特異な増分BPEのための成分重み付きセントロイド探索
• Abstract要約: 特別な増分BPEは付加バイト毎に標準トークン化状態を維持する。 固定アルファベット上で正規化された適切なBPEファミリーを構築する。 Rustの実装は、テストされたインスタンス毎に予測されたプローブ数と一致します。
• 参考スコア（独自算出の注目度）: 22.892102324405826
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Exact incremental BPE maintains the canonical tokenization state after every appended byte. The recent algorithm of Jiang and Gong (2026) does this in $O(\log^2 t)$ worst-case time, where $t$ is the maximum canonical token length. Its centroid search visits $O(\log t)$ components and can pay another $O(\log t)$ for ordered point location at each one. Within Jiang and Gong's normalized/proper merge-stage model, we change only that local search. Each interval is weighted by the size of the recursive component it selects, so a move from size $m$ to size $m'$ costs $O(1+\log(m/m'))$. These charges telescope, giving $O(\log t)$ time per append and $O(n\log t)$ over an $n$-byte stream, with the same BPE semantics and asymptotic space. We also construct a normalized proper BPE family over a fixed alphabet where count-balanced search uses $Θ(\log^2 t)$ probes on a reachable update, while the weighted search uses $Θ(\log t)$. A Rust implementation matches the predicted probe counts on every tested instance. On ordinary vocabularies the queried degrees are small, however, and the improvement is a worst-case guarantee rather than an average-speed result.
• Abstract（参考訳）: 特別な増分BPEは付加バイト毎に標準トークン化状態を維持する。 Jiang and Gong (2026) の最近のアルゴリズムでは、$O(\log^2 t)$ worst-case time, where $t$は最大標準トークン長である。 そのセントロイド検索は$O(\log t)$コンポーネントを訪問し、各コンポーネントの順序点位置に対して$O(\log t)$を支払うことができる。 Jiang and Gong's normalized/proper merge-stage modelでは、ローカル検索のみを変更します。 各間隔は、選択した再帰成分のサイズによって重み付けされるので、$m$から$m'$への移動は$O(1+\log(m/m'))$になる。 これらのチャージ望遠鏡は、加算当たり$O(\log t)$時間と$O(n\log t)$を$n$バイトのストリームに与え、同じBPEセマンティクスと漸近空間を持つ。 また、固定アルファベット上で正規化された正規化された適切なBPEファミリーを構築し、そこでは、カウントバランス付き検索が到達可能な更新で$(\log^2 t)$プローブを使用し、重み付き検索は$(\log t)$を使用する。 Rustの実装は、テストされたインスタンス毎に予測されたプローブ数と一致します。 通常の語彙では、クエリされた度合いは小さいが、改善は平均的な速さよりも最悪のケースで保証される。

関連論文リスト

• Actively Learning Halfspaces without Synthetic Data [34.777547976926456]
  我々は、点合成なしでハーフスペースを学習するための効率的なアルゴリズムを設計する。 コーナリーとして、軸整合半空間に対して最適な$O(d + log n)$クエリ決定論的学習器を得る。 我々のアルゴリズムはブール関数を$f$ over $n$要素で学習するより一般的な問題を解く。
  論文  参考訳（メタデータ） (2025-09-25T07:39:25Z)
• On the Communication Complexity of Approximate Pattern Matching [2.4167127333650202]
  上界が$O(n/m cdot k log2 m)$ bitsであることを証明する。 また、$O(n/m cdot k log2 m)$ bits は、$k$-error 発生毎に$P$ in $T$ のエンコードを可能にする。
  論文  参考訳（メタデータ） (2024-03-27T17:57:16Z)
• Run Time Bounds for Integer-Valued OneMax Functions [0.9012198585960443]
  探索空間 $mathbbZn$ を多値決定変数 $0,ldots,r-1n$ の観点から考える。 ステップサイズ適応のRSSが$Theta(n cdot log(|a|_1))$の最適化時間を達成することを示す。 本稿では,これらのアルゴリズムを離散探索空間に対するCMA-ESの変種と比較し,実験的な解析を行った。
  論文  参考訳（メタデータ） (2023-07-21T18:49:06Z)
• A Formal Perspective on Byte-Pair Encoding [100.75374173565548]
  Byte-Pairimation (BPE) は、当初圧縮法として考案されたものの、NLPでデータをトークン化するために使われる一般的なアルゴリズムである。 我々は、ランタイムの複雑さを$mathcalOleft(N log Mright)$から$mathcalOleft(N log Mright)$に改善するBPEのより高速な実装を提供しています。
  論文  参考訳（メタデータ） (2023-06-29T10:29:23Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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