論文の概要: Copying Under Repetition: From Prefix Matching to Position Hashing

• arxiv url: http://arxiv.org/abs/2610.26722v1
• Date: Mon, 19 Oct 2026 16:50:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-23 00:40:06.073837
• Title: Copying Under Repetition: From Prefix Matching to Position Hashing
• Title（参考訳）: 繰り返しのコピー: プレフィックスマッチングから位置ハッシュへ
• Abstract要約: 我々は、$O(loglog N)$-bitの精度を持つ2層変換器が、選択した水平線を最大$N$までコピーし、任意の繰り返しで正しく終了できることを示す。 また, 逐次有限精度ソフトマックス蓄積下での複写における幅非依存的不合理性も証明した。
• 参考スコア（独自算出の注目度）: 14.734100061603963
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Frontier LLMs can copy random text almost flawlessly, yet they often overrun or truncate long blocks of repeated characters. In repeated strings, matching local content no longer reliably identifies where copying should continue or when it should stop. Nevertheless, we show that a two-layer transformer with $O(\log\log N)$-bit precision and $O(\log N/\log\log N)$ width can copy every string up to a chosen design horizon $N$ and terminate correctly under arbitrary repetition. We use RoPE-style rotations of attention values and outputs (VO-rotations) with small prime periods to encode distances from delimiter anchors modulo those primes. By the Chinese Remainder Theorem, these periodic encodings jointly distinguish all required distances, allowing one retrieval rule to select either the next source token or the end marker. In contrast, we prove a width-independent impossibility result for copying under sequential finite-precision softmax accumulation. It applies to transformers whose only positional input is an additive attention bias that eventually becomes constant, including NoPE and a recursive implementation of ALiBi. Once an identical-token run exceeds the resulting saturation threshold, further repetitions leave the logits unchanged. If this threshold grows sublinearly with $N$, these models cannot both complete a long all-identical copy and stop correctly, a pattern resembling the termination errors of frontier LLMs. In synthetic copying experiments, baseline transformer models fail on long repeated strings even within the training range. Trained VO models, by contrast, generalize beyond the training lengths with near-perfect accuracy up to length $\approx 5005$, the selected primes' period product.
• Abstract（参考訳）: フロンティアLSMはランダムテキストをほとんど完璧にコピーできるが、しばしば繰り返し文字の長いブロックをオーバーランまたは切り捨てる。 繰り返し文字列では、ローカルコンテンツとのマッチングは、コピーの継続場所や停止時期を確実に特定することができない。 それでも、$O(\log\log N)$-bit精度と$O(\log N/\log\log N)$幅の2層トランスフォーマーは、選択した設計水平線まですべての文字列をコピーし、任意の繰り返しで正しく終了することができる。 注意値と出力(VO回転)のRoPEスタイルの回転を小さな素周期で行い、それらの素周期を変調するデリミターアンカーからの距離を符号化する。 中国語のRemainder Theoremによると、これらの周期的なエンコーディングは、すべての必要な距離を共同で区別し、1つの検索ルールで次のソーストークンかエンドマーカーのいずれかを選択することができる。 対照的に、逐次有限精度ソフトマックス蓄積下での複写における幅非依存的不合理性の結果が証明される。 唯一の位置入力は、NoPEやALiBiの再帰的な実装を含む、最終的に一定となる付加的な注意バイアスであるトランスフォーマーに適用される。 同一のトーケン実行が結果の飽和しきい値を超えると、さらなる繰り返しはロジットを変更せずに済む。 このしきい値が$N$でサブライン的に増加すると、これらのモデルは長い完全同一のコピーを完了して、フロンティアLSMの終了エラーに似たパターンを正しく停止することはできない。 合成複写実験では、ベースライントランスモデルはトレーニング範囲内でも長い繰り返し弦で失敗する。 対照的に訓練されたVOモデルは、訓練期間を超えて、選択された素数周期積である$\approx 5005$までのほぼ完全な精度で一般化する。

関連論文リスト

• Universality and Generalization of Causal Transformers Across Context Lengths [29.587685183870775]
  固定された正規化水平線をサンプリングする任意の長さの列に対して因果トークン・ツー・トケンマップを均一に近似できるかを検討した。 分解能間の連続性の概念は、長さに依存しないパラメータを持つ単一変圧器により、コンパクトな入力クラスに一様近似を許容する因果族を特徴づける。 物理時系列の実験は、データセット依存の適応指数を持つ観測スケールでのHlder-regularトークンモデルをサポートし、テキスト入力の埋め込みは対照的なケースを提供する。
  論文  参考訳（メタデータ） (2026-09-28T12:50:27Z)
• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• HEAT: Faster Fully Homomorphic Inference via Approximations-Weights Co-Adaptation [56.14416807766864]
  同型暗号化により、サーバは暗号化されたユーザープロンプト上で言語モデルを直接実行することができる。 既存のアプローチでは、各サイトのエラー許容度を調整するのではなく、モデル全体のイテレーションカウントを均一に修正する。 非線形反復回数を学習可能にする微調整法であるHAT(Hymomorphic Encryption-Aware Training)を導入する。
  論文  参考訳（メタデータ） (2026-09-01T18:02:02Z)
• On the Role of Normalization in Binary Iterative Hard Thresholding for 1-bit Compressed Sensing [18.637825309463125]
  Binary Iterative Hard Thresholding (BIHT) は、1ビットの符号測定からスパースベクトルを復元するための単純かつ効果的で欲求的な方法である。 このアルゴリズムの収束解析は [Jac+11] の入門研究に残され、10年以上未解決のままである。 本論文は, アルゴリズムによる定位正規化が必要とされる場合に, ギャップを解消し, 特徴付ける。
  論文  参考訳（メタデータ） (2026-07-17T00:44:33Z)
• ShortOPD: Recovering Pruned LLMs with Short-to-Long On-Policy Distillation [72.54604107217669]
  textscpass@$k$は圧縮後にほぼ消滅するが、textscpass@$k$は繰り返しサンプリングの下でほぼ回復する。 回復は、密集したトークンレベルの監督の下で、圧縮されたモデル自身のオン政治状態で訓練すべきである。 我々は,教師が確認した反復接尾辞を検知する短時間のOPDスケジュールであるtextbfshortopdを提案する。
  論文  参考訳（メタデータ） (2026-07-14T17:50:50Z)
• Tight Sample Complexity of Transformers [28.82044197167549]
  We map a input sequence of length $T$ to a single output, established a upper bound of $O(L W log (T W))$ and a nearly matching lower bound of $(L W log (T W / L))$。 さらに,教師の強制力を示すトランスフォーマーを用いたチェーン・オブ・シークレット学習の複雑さを強く特徴付ける。
  論文  参考訳（メタデータ） (2026-06-08T16:56:24Z)
• Copy-as-Decode: Grammar-Constrained Parallel Prefill for LLM Editing [2.6382975801439836]
  LLMは、入力中にほとんどのトークンが冗長に見える場合でも、全出力を自動回帰的に再生することでテキストとコードを編集する。 Copy-as-Decodeは、2プリミティブ文法上の構造化復号化として生成を再キャストする復号化機構である。
  論文  参考訳（メタデータ） (2026-04-20T12:29:53Z)
• Rethinking Thinking Tokens: LLMs as Improvement Operators [80.12087211785949]
  推論トレーニングは、LLMに長い思考の連鎖(長いCoT)を生み出す動機を与え、自己チェックによるソリューション戦略を探索することを可能にする。 これにより、精度が高くなりますが、コンテキストの長さ、トークン/計算コスト、応答レイテンシが膨らみます。 現在のモデルはメタ認知を活用して、このParetoフロンティアで他の組み合わせを提供できるのでしょうか? i) 多様なドラフトを並列に生成し、(ii) それらを有界なテキストワークスペースに蒸留し、(iii) このワークスペース上に条件付き精製する。
  論文  参考訳（メタデータ） (2025-10-01T17:08:59Z)
• DiffuSpec: Unlocking Diffusion Language Models for Speculative Decoding [66.40658898418316]
  DiffuSpecは、事前訓練された拡散言語モデル(DLM)を用いて、単一のフォワードパスでマルチトークンのドラフトを生成する、トレーニングフリーのドロップインフレームワークである。 ベンチマーク全体を通じて、DiffuSpecは最大3倍のウォールクロックスピードアップを達成し、投機的復号化のための自己回帰型ドラフトラの堅牢な代替手段として拡散ベースのドラフトを確立する。
  論文  参考訳（メタデータ） (2025-09-28T07:00:15Z)
• Mitigating the Learning Bias towards Repetition by Self-Contrastive Training for Open-Ended Generation [92.42032403795879]
  GPT2のような事前訓練された言語モデル(LM)は、繰り返しテキストを生成する傾向にあることを示す。 トークンレベルの反復確率の過大評価は学習バイアスに起因している。 LMは文レベルの繰り返しループの原因となる非繰り返しトークンよりも長い範囲依存を用いて繰り返しトークンを予測する。
  論文  参考訳（メタデータ） (2023-07-04T07:53:55Z)

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

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