論文の概要: Length Generalization for Transformers via Compression

• arxiv url: http://arxiv.org/abs/2609.08851v1
• Date: Tue, 08 Sep 2026 15:03:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-10 19:44:08.681656
• Title: Length Generalization for Transformers via Compression
• Title（参考訳）: 圧縮による変圧器長一般化
• Abstract要約: C-RASP仮説は、ある解が C-RASP 言語で表現可能であることと、その解が C-RASP 言語で表現可能であることを条件として、変換器がタスクに対して長さ一般化するものであることを仮定する。 計算可能な長さの一般化境界は C-RASP には存在せず、一見矛盾する実験が発見されている。 このことは、C-RASP予想を詳細に分析し、それに対する実験的な証拠の矛盾を解消することを示す。
• 参考スコア（独自算出の注目度）: 11.064928874016438
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent advancements in transformer length generalization theory enable us to reliably predict when a transformer can learn to solve a task. In particular, the C-RASP hypothesis (a formalized version of the so-called RASP-l conjecture) posits that transformers length-generalize on a task if and only if a solution is expressible in the C-RASP language. While this hypothesis has strong empirical validation, theoretical problems arise from the fact that no computable length generalization bounds exist for C-RASP, alongside the discovery of seemingly contradictory experiments. To address these problems, we refine the C-RASP hypothesis utilizing the recently-proposed fragments C-RASP+ and C-RASP1. These fragments have computable length generalization bounds, though in the worst case requiring an extremely large (double exponential) sample size. It is an open question whether these sample size bounds are tight. In this paper, we resolve this open question by providing an exponentially tighter bound. In doing so, we show a polynomial length generalization bound for transformers if we adopt compressed strings, via a novel connection to power words. As an application, we show how this yields a fine-grained analysis of the C-RASP conjecture that resolves contradicting experimental evidence against it.
• Abstract（参考訳）: 変圧器長一般化理論の最近の進歩により、変圧器がタスクを解くことをいつ学べるかを確実に予測できる。 特に、C-RASP仮説(いわゆる RASP-l 予想の形式化されたバージョン)は、解が C-RASP 言語で表現可能である場合に限って、トランスフォーマーがタスクに対して長さ一般化するものである。 この仮説には強い経験的検証があるが、理論上の問題は、計算可能な長さの一般化境界がC-RASPに対して存在しないという事実と、一見矛盾する実験の発見から生じる。 これらの問題に対処するため,最近提案された C-RASP+ と C-RASP1 を用いた C-RASP 仮説を改良する。 これらの断片は計算可能な長さ一般化境界を持つが、最悪の場合、非常に大きな(二重指数的な)サンプルサイズを必要とする。 これらのサンプルサイズ境界がきついかどうかは、明らかな問題である。 本稿では、指数関数的に厳密な境界を与えることにより、この開問題を解決する。 そこで, 圧縮文字列を採用する場合, パワーワードへの新たな接続を通じて, 変圧器の多項式長一般化を示す。 応用として、このことがC-RASP予想のきめ細かい解析をいかに引き起こすかを示し、それに対する実験的証拠の矛盾を解消する。

関連論文リスト

• On the Ability of Transformers to Verify Plans [50.65678452287009]
  本稿では,デコーダのみのモデルを用いて,与えられた計画が与えられた計画インスタンスを正しく解決するかどうかを検証する。 本稿では,C*-RASPについて紹介する。C*-RASPは変圧器の長さの一般化を保証するために設計されたC-RASPの拡張である。 提案手法は,変圧器が長期計画の検証を確実に学べる,古典的計画領域の大規模なクラスを同定するものである。
  論文  参考訳（メタデータ） (2026-03-20T13:55:29Z)
• Length Generalization Bounds for Transformers [9.186207021992535]
  長さ一般化は、任意の長さの入力に対する正確な予測を可能にする学習アルゴリズムの重要な特性である。 このような保証を得るためには、モデルが一般化されることを保証した長さ一般化境界を計算できる必要がある。 本稿では,変換器に密接な関係を持つ言語クラスであるCRASPに対して,そのような一般化境界の計算可能性に関するオープンな問題について述べる。
  論文  参考訳（メタデータ） (2026-02-13T14:49:27Z)
• Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization [53.89723291716722]
  AI推論に関する重要な問題は、モデルが学習した推論パターンを外挿して、より長いチェーン・オブ・シークレット(CoT)で難しいタスクを解決できるかどうかである。 状態追跡問題の代数構造が、学習されたCoTの外挿の度合いをいかに支配するかを数学的に証明する。 定数深度変換器はCoTで$mathsfNC1$-complete問題を確実に学習することを保証する。
  論文  参考訳（メタデータ） (2025-11-10T18:40:24Z)
• Quantitative Bounds for Length Generalization in Transformers [58.175107357008876]
  変圧器における長さ一般化(LG)問題について検討する。 LGは、長い列上の変圧器の内部挙動が短い列上の振舞いによって「シミュレート」できるときに発生する。
  論文  参考訳（メタデータ） (2025-10-30T21:31:36Z)
• Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilities [58.742178800799614]
  We study a family of $textitretrieval$ and $textitcopying$ tasks inspired by Liu et al。 我々は、事前訓練されたモデルがクエリトークンの左(アンチインダクション)よりも右(インダクション)へのトークンの検索が優れているような、$textitinduction-versus-anti-induction$ asymmetricを観察する。 力学解析により、この非対称性は、事前学習された変圧器内の誘導の強度と反誘導回路の強度の違いに関係していることが明らかになった。
  論文  参考訳（メタデータ） (2025-05-27T21:36:50Z)
• On Vanishing Variance in Transformer Length Generalization [23.706900145711913]
  また,今日のフロンティアモデルにおいても,より長いシーケンス長はマルチヘッドアテンションモジュールの出力のばらつきを減少させることを示した。 分析では, この改善は分散の消失による分布シフトを完全に排除したものではないものの, 削減したと考えられる。
  論文  参考訳（メタデータ） (2025-04-03T17:59:56Z)
• The Role of Sparsity for Length Generalization in Transformers [58.65997625433689]
  そこで本研究では,次の予測課題に対する長さの一般化を研究するための理論的枠組みを提案する。 予測された各トークンが前のトークンの小さな(固定された)数に依存する限り、長さの一般化が生じることを示す。 本稿では,位置結合手法で使用する位置IDを予測するために,変圧器を訓練する予測位置結合を導入する。
  論文  参考訳（メタデータ） (2025-02-24T03:01:03Z)
• A Formal Framework for Understanding Length Generalization in Transformers [14.15513446489798]
  因果変換器における長さ一般化を解析するための厳密な理論的枠組みを導入する。 我々は,この理論を,アルゴリズムおよび形式言語タスクにおける長さ一般化の成功と失敗の予測器として実験的に検証した。
  論文  参考訳（メタデータ） (2024-10-03T01:52:01Z)
• Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective [39.47116013338394]
  CoT(Chain-of-Thought prompting)は,大規模言語モデル(LLM)の性能を劇的に向上させる 我々は、CoTが動的プログラミング(Dynamic Programming)として知られる一般的な意思決定問題に対処できることを示します。
  論文  参考訳（メタデータ） (2023-05-24T17:59:21Z)
• Causal Expectation-Maximisation [70.45873402967297]
  ポリツリーグラフを特徴とするモデルにおいても因果推論はNPハードであることを示す。 我々は因果EMアルゴリズムを導入し、分類的表現変数のデータから潜伏変数の不確かさを再構築する。 我々は、反事実境界が構造方程式の知識なしにしばしば計算できるというトレンドのアイデアには、目立たずの制限があるように思える。
  論文  参考訳（メタデータ） (2020-11-04T10:25:13Z)

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

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